Dear LATRC and devotees,
I have developed some Linux queueing disciplines. I developed them for
my masters project. You are free to use or distribute my work.
Here is the abstract from my dissertation:-
This is a project to implement a Mice and Elephants queuing discipline
on Linux. My project has three aims. The first aim was to produce a
prototype Mice and Elephants router for the purpose of further
evaluation of the Mice and Elephants strategy. The second aim was to
make a contribution to Linux by making my implementation as code that
would be both fit for distribution with Linux and useful in a small
business or domestic setting. The third aim was to explore and document
a method of creating Linux queuing disciplines.
The rest of my dissertation, manual pages on my queuing disciplines, my own
HOWTO on how to write queueing disciplines, manual pages on the kernal interface
for queuing disciplines, and the tarball sourcode are all avaiable from:-
http://www.sci.usq.edu.au/staff/braithwa/MastProj/index.html
Please read the HOWTO for instructions on how to build and install.
Please direct questions about this to braith@dodo.com.au
Apart from Mice and Elephants queueing disciplines, an ARED queueing
discipline is there also.
Yours sincerely,
Stephen Braithwaite
P.S. :-
I would like to "sell" (not really - of course its all free) you the
concept of mice and elephants. So here is some cut and paste from my
master''s dissertation:-
A "Mice and Elephants" strategy (also called Shortest Job First) is
one
which favours the short flows over long flows. In a mice and elephants
strategy the short flows or the packets from them are called mice, and
the long flows or the packets from them are called elephants. It
involves identifying flows and associating packet with their flows in
order to be able to treat long flows different to short flows. One way
to favor the mice is to give the mice priority when dequeueing. Another
is to avoid dropping mouse packets by dropping elephant packets before
the queue is full.
Proponents of "Mice and Elephants" queuing strategies argue that equal
throughput for each flow or host (sometimes called "Processor Sharing"
or "Fair Queueing") is the wrong goal. Mice and Elephants strategy
response times are significantly better than those obtained using Fair
Queuing.
Shortest Remaining Processing Time (SRPT) has been shown to give better
results than Processor Sharing for a range of measures including average
task turnover time [36]. [36] uses mean task turnover time divided by
job length as a measure of starva- tion, and shows both analytically and
by simulation that no class of jobs are worse off when the the job sizes
are heavy tailed (as they are in internet traffic).
In reality, SRPT would be difficult in a queuing discipline, because we
dont know the length of each job, we only know the size of a job so far.
But Shortest Job First (SJF) has been shown to be a sufficiently good
approximation to SRPT, to enjoy the same benefits over Processor Sharing
that SRPT does. [49] shows that shortest job first gives near optimal
response time regardless of which group of flows we care to observe.
For example, Shortest Job First gives as good a result to medium length
jobs than if we were to give them absolute priority. Simulation of an
implementation of Shortest Job First is described in [13], with results
that show significant gains over other strategies
Two cases of congested queues fed by Poisson Pareto Burst Proccesses
were math- ematically modelled. [14] One had a Pareto distribution
shape parameter of 1.4 (heavy tails) and the other had a Pareto
distribution shape parameter of 1.2 (very heavy tails). Both cases
were modelled with a Mice and Elephants strategy and without. The
benefit from the Mice and Elephants strategy was assessed by
calculating the extra capacity needed when the Mice and Elephant
strategy was not used in order that at most 5% of flows are delayed by
more than 20%. In the heavy tails case, 16% more capacity was required.
In the very heavy tails case 40% more capacity was required. The
modelling showed that the benefit of a mice and elephants strategy
would be quite significant.
Long flows consitute a small minority, but make up the vast majority of
traffic. About 20% of the flows have more than 10 packets but these
flows carry 85% of the total traffic. [60] [24] During periods of
traffic congestion the long flows account for an even greater
percentage of the traffic than they do if we take overall traffic mea-
surments. In [15] an example was given where the short flows accounted
for 89% of the traffic flow and the long flows accounted for the other
11% of the traffic flow over- all. During periods of high congestion,
the long flows accounted for a disproportionate amount of the traffic
flow - perhaps 88%.
It stands to reason that interactive short flows are delay sensitive as
far as the per- ceived quality of service is concerned, because a human
being will have an active process happening and will be impatient to
wait for a result from her mouse click or keystroke. For example, the
keystrokes in a telnet session will have to wait in a queue congested
by packets from long flows.
It is also worth mentioning that short flows are particuarly sensitive
to dropped packets [35] . Treating mice and elephants equally is not
truly "fair", and it would be more fair to assist the mice in order to
achieve a better perceived quality of service.
Stephen, this sounds interesting. One question : did you address the ''arms race'' with file sharing application developers ? What I mean is that giving preference to short flows seems like a fine idea until footorrent or whatever comes along that has the strategy of opening zillions of short-lived connections to a large number of servers. Now all the flows are short and there are no long flows to give lower priority to. Thoughts ? (I did read quickly through your thesis but couldn''t see anything on this. Apologies if I missed it).
David, I am a newbie to the list - and dont know how to to reply on the correct thread - but here goes:- Your objection is spot on. Bit torrent seems to present a real challenge. The definition of a flow need not be the TCP definition of a flow. I am not sure if it will help, but any the queuing discipline and ingress que filter are able to work with any combination of protocol, source port number, source ip, dest port, dest ip as the definition of a flow. This may or may not help. -----Original Message----- From: David Boreham [mailto:david_list@boreham.org] Sent: Sun 10/16/2005 12:14 AM To: Stephen Braithwaite Cc: lartc@mailman.ds9a.nl Subject: Re: [LARTC] FW: Some queueing disciplines that I wrote. Stephen, this sounds interesting. One question : did you address the ''arms race'' with file sharing application developers ? What I mean is that giving preference to short flows seems like a fine idea until footorrent or whatever comes along that has the strategy of opening zillions of short-lived connections to a large number of servers. Now all the flows are short and there are no long flows to give lower priority to. Thoughts ? (I did read quickly through your thesis but couldn''t see anything on this. Apologies if I missed it).
I have an objection too: VoIP (Voice over IP), video and audio streaming are "elephants". They are big flows, yet people don''t like movies played as picture slideshows and interrupted audio or phone calls. End of objection. Trying to build a solution: Making the hipothesis. I think "intrractive traffic" shoud be defined and recognized not by it''s packet size nor by duration of the connection nor by ports it comes or goes. We do not have a "computerized" definition of "interactive traffic", so we cannot separate it from "bulk traffic". We know that "interractive traffic" = traffic that should have such priority that the user can interract with the network without being annoyed by network latency. "Bulk traffic" = traffic that the user don''t care if is delayed for a few seconds, but has to take place and finnish in resonable time. The conclusions: 1. Now that the definitions are given, how can we sepparate the two, living no chance for programmers to "cheat" the algorithm? Or maybe we can trust them and ask them for help and set for interractive applications'' traffic some bits that the routers can recognize and build some queues accordingly. 2. How many classes do we need and what applications could be into each of them? Waiting for some ideas... __________________________________ Yahoo! Music Unlimited Access over 1 million songs. Try it free. http://music.yahoo.com/unlimited/
> I have an objection too: > VoIP (Voice over IP), video and audio streaming are > "elephants". They are big flows, yet people don''t like > movies played as picture slideshows and interrupted > audio or phone calls. > End of objection. - Panca SorinPanca Sorin is correct. Video and audio streaming would suffer if classified as elephants. Fortunately they have a different type of service and are likely to be associated with certain port numbers. Linux is flexible and allows you to separate these streams using something like . If you used video or audio streaming you would separate these out, probably using the u32 classifier. Because these are fixed rate, and because they require their fixed rate, these streams need to be given absolute priority. So the prio classful queuing discipline would be a suitable contianer. Within the prio classful queuing discipline, the fixed rate flows should be channeled into a simple drop tail, while the remainder could be channeled into a mice and elephants queueing discipline such as meredt. _______________________________________________ LARTC mailing list LARTC@mailman.ds9a.nl http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc
Stephen Braithwaite wrote:>The definition of a flow need not be the TCP definition of a flow. >I am not sure if it will help, but any the queuing discipline and ingress que filter are >able to work with any combination of protocol, source port number, source ip, dest port, dest ip as the definition of a flow. This may or may not help. > >Ah, that''s very interesting. So you could assign all traffic to/from a ''hog'' ISP customer to the elephant category.
> > The definition of a flow need not be the TCP definition of a > > flow. I am not sure if it will help, but any the queuing > > discipline and ingress que filter are able to work with any > > combination of protocol, source port number, source ip, dest > > port, dest ip as the definition of a flow. This may or may > > not help. > > Ah, that''s very interesting. So you could assign all traffic to/from a > ''hog'' ISP customer to the elephant category.You cannot assign it as such, it has to happen automaically. If you made the definition of a flow to be the source/destination IP number then the flow consisting of traffic to/from a ''hog'' computer would find itself soon find itself designated as an elephant. If this is deployed on the router where the NAT occurs, then the queuing discipline sees the internal IP numbers. The time scales over which a flow becomes/ceases to be an elephant are configurable. There is also a mechanism to have the queuing discipline not purely mice and elephant and not purely fair queueing, but somewhere in between.