Date: Sat, 10 Apr 1999 16:09:14 +0200 (CEST) From: Remy Nonnenmacher <remy@synx.com> To: luigi@labinfo.iet.unipi.it Cc: net@FreeBSD.ORG Subject: Re: possible dummynet enhancement (random pkt reordering) Message-ID: <199904101409.QAA20704@rt2.synx.com> In-Reply-To: <199904091852.UAA01251@labinfo.iet.unipi.it>
next in thread | previous in thread | raw e-mail | index | archive | help
On 9 Apr, Luigi Rizzo wrote: > Some time ago, a few people asked me on how to simulate pkt reordering > with dummynet. I did have a few ideas but not so clear. However, > the following seems a reasonably good method if someone feels like > implementing it. (this is an excerpt from a reply i sent to Rick Jones > at HP): > > ... reordering is slightly harder to do in a realistic way. I had an > email exchange with somebody who wanted to implement it, and turned > out that the simplest way would be to randomly decide to swap a > pair of packets while they are in the first queue (the bw limiter). > This way you preserve the throughput. Depending on which pkts you > swap and how frequently you might have different effects which i > have not studied in detail. But one reasonable way could be: > > whenever you can move a pkt from the R-queue to the P-queue, > swap the first two pkts (i.e. the one that you would move, and the > next one) with a random probability. Then, move the pkt to the > P-queue. > This would be a fair easy thing to do. However, it has some main drawbacks especially at low bandwidth or when there is a great amount of concurrent sessions : (hereafter, a 'session' is an established TCP stream defined by the Quple ((IP/Port)src, (IP/Port)dest) ). - At low bandwidth, streaming sessions (ie: FTP) would cause starvation of interactive (ie: Telnet) ones due to the ratio of packets from one type over the other in the R-queue. This is especially true is dummynet is used at the receiving side in an hope to limit incoming bandwidth. - At great amount of streaming sessions, random packet reordering would force the receiver to reassembly and, aside memory usage, will forbid 'smooth' data delivery at application level. (and unfortunetly, user seems to prefer a low, continous, bandwidth over nothing-then-all). I see two way (over many others) to limit that problem without entering the complexity of real Fair Queuing : - Rotating queues - Tagged placement The rotating queue is proposed on the GPS (Generalized Processor Sharing) algo and on the interesting idea of the Stateless-Core FQ. The idea behind is to build a limited set of queues that will receive packets based on their classification (either an internally generated number for each session Quple, or an hash value extracted from the Quple). Each session goes into only one queue of the set, thus preserving packets ordering. The extracting process rotates under the queue heads and extracts from each queue one packet at a time. This limits (but not prevents) interactive starvation. Full FQ is the case where the session identifier uniquely identify a single queue over a number of queue equal to the so-called WFI (Worst-case Fair Index), that is roughly the max number of concurrent session). The tagged placement approximates this by inserting packets of a session contiguously inside a single queue and then, simulate multiple queues extraction in the same way of rotating queues. In this case, multiple queues are only pointers inside the real queues where a group of packets of a session starts/ends. Roughly, this achieves the same goal with less memory (?) but with higher, near-perfect, WFI (?), and rough ly same complexity (???) (? = personnal doubts). The idea behind tagged placement is that the queue size will force a limit to the WFI since the queue will drop packets when becoming full, thus limiting the WFI to the max number of packets in the queue. These two ways solves the smooth delivery problem but doesn't guaranty anti-starvation (alegedly, TP would). The rotating queue is fairly easy to implement in dummynet. Basically this means : - replace the R-queue by a set of smaller R-queues. (eg: 16) - Build a function generating the input R-queue number to be used when presented a Quple (can be just a modulo sum of all low bytes of the elements of the Quples (wteg: &0x0f) - slightly modify the R-queue extractions to use R-queues. (wteg: queue[i++&0xf]). Please note that this will _not_ address the problem of remote limiting wich is more complex and need to delay acks packets based on their session identifier. Comments, please. ------ Note: I also found a fairly easy way to share bandwidth between queues but this mail is too short. (Nope, not playing Ferma ;), it's only not the subject but i would like to discuss it with interested peoples). RN. ItM To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-net" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199904101409.QAA20704>