Q & A on Teoretical ANalysis of Router Systems

Q: Simple IP routers have only one FIFO (First-in-first-out first-come-first-served) queue for the packets. That has the drawback that some users may achieve much higher data rate than others, for example if their packets are long in average, if their TCP sessions have long duration, and thus they avoid TCP slow-start, and if the IP packets only traverse a few routers. That is not fair. To address this problem, modern routers support fair packet scheduling algorithms, such as the Weighted Fair Queuing algorithm. This means that each flow (=stream=session) of IP packets has its own FIFO queue, instead of one common FIFO queue. If we only consider best-effort traffic (without QoS guarantees), then the router controls that backlogged flows (with at least on packet in queue) get equal bit rate, independently of packet sizes, TCP session durations, number of passed routers, etc. If we consider several routers, all flows do not achieve equal bandwith, but the minimum bandwith that a user can achieve is maximized. This is called max-min fairness. (I hope my terminology is correct.)

A flow is identified as a unique combination of source and destination IP address and TCP port number. This mean that a user who simultaneously communicates with N different hosts, or N different TCP ports, will achieve N times higher data rate than a user who communicates with only one host and one TCP port. I.M.O., that is not fair. I think that if several packets goes to [from] the same IP host, and that host is situated in the same (sub)net as the IP router, then they should be considered as the same flow irrespectively of the source [destination] and the TCP port numbers. I haven't seen any discussion about it in scientific papers, or in CISCO knowledge database, so I guess that CISCO routers do not support this. Do you have some idea why?

In the academic world, a lot of other fair resource sharing algorithms are studied, such as deficit round robin, and algorithms for proportional fairness. Do you know if these algorithms are supported by routers existing on the market today?

A: You are correct that the academic world is overrun with theoretical studies of packet scheduling and traffic engineering. Researchers in the area of Performance Evaluation have had little impact in operating systems and databases; now they are applying the same techniques to networks. In fact, everyone I know who used to write papers on performance of something is now writing papers on performance of networks. Recently, I had a visitor in my office who told me he was shocked to discover that the academic work was almost completely ignored by industry -- engineers bulding switches and routers didn't find that the analysis worked in practice.

So, you are discussing a few details, when the important question is whether the whole scheme is worthwhile. Many of us in networking think that it is not -- scheduling will NEVER be a satisfactory solution to the resource problme. The notion of ``equal pain'' didn't work for operating systems, doesn't work for automobile traffic, and it won't work for networks. The only viable long-term solution is increasing resources (the ``big bandwidth'' solution).