Wednesday, September 10, 2008

Core-Stateless Fair Queuing: Achieving Approximately Fair Bandwidth Allocation s in High Speed Networks (CMU '98)

Core-Stateless Fair Queuing (CSFQ) is an approximation of FQ implementation. It is designed to lessen the expense of implementing the full-blown version of FQ. CSFQ operates over an "island" of routers (s.t. inner routers are called core, and the perimeter called edge), where flow classification needs to be done once only at the edges. Core routers merely operate and propagate flow information. Like the other paper, CSFQ is compared with a handful of other alternatives, in this case both the hypothetical upper bound and other cheaper implementations that abstract away flow-states or multiple buffers.

CSFQ does not explicitly keep track of separate flow buffers, rather it keeps a small number of per-flow states (i.e. drop rate, arrival index). It computesthe drop probability for a incoming packet. In essence, it achieves similar desired effects of providing protection and being fair. It's also sensitive to burstiness of flow, which is a good thing (i.e. bursty flows can have good turn around time).

It's great that probabilistic method minimize the states we have to keep. Now, i see more reason why packets can be delivered out of order. Dropping packets randomly and regularly in the middle of a packet stream correspondingly adds burden on the endpoints to deal with these random "holes". Thus, we can see this as pushing the complexity away from the network and into the end-points.

Although the paper address the cost issue with FQ, it didn't give the full details on the bottleneck. I would like to see more on that in terms of implementation issues. I am also skeptical about the core-edge separation. Heterogeneity impedes scalability, in general. CSFQ also assumes that flow goes through a fixed set of routes, which doesn't map well to dynamic routing.

The paper explicitly talked about the concept of "punishment", which seems controversial. Basically, users who are nice are rewarded with more bandwidth while barbbling idiots get their share cut backed. This assumes that everyone is equal. But the reality is there are stratifications, like class, authority and etc. Should users with superior hardware and technology not be rewarded? Should everyone use the network the same?

No comments: