Stoica, I., Shenker, S. and Zhang, H., “Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks”, Proceedings of ACM SIGCOMM’98.
By 1998, even though the need for fair resource allocation within the core routers of the networks was very much accepted, the proposed algorithms such as Deficit Round Robin (DRR) were still to complex and costly to be used in high speed core routers (it is interesting to know 10 years later how wide spread is their usage!?).
Core-Stateless Fair Queueing (CFSQ) is a proposal for the architecture for the islands of routers (possibly at the heart of ISPs) which should be able to allocate resources almost fairly. The attempt of the CFSQ architecture is to keep the high speed highly loaded core routers as simple and stateless as possible while the edge routers (working at much lower line rates) carry most of the burden of per flow management and control. Edge routers estimate the arrival rates of the flows and label them with corresponding rates. At core routers, if the fair share of a flow is below its estimated rate, the packet is dropped probabilistically (the core router is basically thinning the random process). The interesting fact is that core routers only need a single label attached to each packet and there is no per flow state at any router (there is much more detail to this which you can find them in the paper).
The simulation results show that CSFQ outperformed regular non-fair schemes (e.g. FIFO and RED) drastically while working better or close to FRED and below DRR. Just by reading the description of architecture I had assumed that CSFQ should perform much closer to DRR (the precise fair queueing algorithm with much implementation complexity) but interestingly that is not the case and CSFQ perform below DRR and not too close. The authors also mention that they are still not aware of the reason behind this difference. Can the inaccuracy in the estimations cause such a difference? Disregard of this observation, the result is brilliant since it enables almost fair allocation with much less complexity and therefore cost.
It is also interesting to think about the scope of this architecture and what can be considered as an island of routers? Will you have multiple islands within an ISP, one island within an ISP or expand it to multiple ISPs and possibly the whole internet? Trust will be crucial in drawing the boundaries of these islands in addition to obvious policy and economical reasons.
Very interesting work and paper!
By 1998, even though the need for fair resource allocation within the core routers of the networks was very much accepted, the proposed algorithms such as Deficit Round Robin (DRR) were still to complex and costly to be used in high speed core routers (it is interesting to know 10 years later how wide spread is their usage!?).
Core-Stateless Fair Queueing (CFSQ) is a proposal for the architecture for the islands of routers (possibly at the heart of ISPs) which should be able to allocate resources almost fairly. The attempt of the CFSQ architecture is to keep the high speed highly loaded core routers as simple and stateless as possible while the edge routers (working at much lower line rates) carry most of the burden of per flow management and control. Edge routers estimate the arrival rates of the flows and label them with corresponding rates. At core routers, if the fair share of a flow is below its estimated rate, the packet is dropped probabilistically (the core router is basically thinning the random process). The interesting fact is that core routers only need a single label attached to each packet and there is no per flow state at any router (there is much more detail to this which you can find them in the paper).
The simulation results show that CSFQ outperformed regular non-fair schemes (e.g. FIFO and RED) drastically while working better or close to FRED and below DRR. Just by reading the description of architecture I had assumed that CSFQ should perform much closer to DRR (the precise fair queueing algorithm with much implementation complexity) but interestingly that is not the case and CSFQ perform below DRR and not too close. The authors also mention that they are still not aware of the reason behind this difference. Can the inaccuracy in the estimations cause such a difference? Disregard of this observation, the result is brilliant since it enables almost fair allocation with much less complexity and therefore cost.
It is also interesting to think about the scope of this architecture and what can be considered as an island of routers? Will you have multiple islands within an ISP, one island within an ISP or expand it to multiple ISPs and possibly the whole internet? Trust will be crucial in drawing the boundaries of these islands in addition to obvious policy and economical reasons.
Very interesting work and paper!
