| dc.description.abstract | Despite its rapid and tremendous growth, the basic packet delivery service in the Internet has largely remained best-effort and egalitarian. Consequently, the Internet from the outset lacks powerful mechanisms for fair arbitration of its own shared resources among the users it serves. For example, user flows injecting more bytes per time unit can proportionally receive more service, at the expense of others with lower rates. In the extreme case, certain flows or users can completely be denied of service (i.e., access to link and buffer resources) in the network.
A lot of research has been conducted to correct the fairness limitation and two general, yet complementary, approaches have been followed: end-to-end based (e.g., TCP) and network-based. The first solutions are congestion control algorithms doubling as fairness control algorithms as their secondary goal. However, they require on the part of end hosts universal adoption which limits the scope of their applicability. The latter approaches are to be enabled at the routers and can in turn be classified into two categories: perflow fair queueing (or scheduling) schemes and queue management mechanisms. While the former are powerful in providing high-quality fairness among flows, they are plagued by lack of scalability features as they require complex per packet operations and maintenance of perflow states. The queue management schemes, to the contrary, are generally simpler and hence more scalable, but lack generality and quality flow protection and fairness.
In this thesis, we propose a host of simple, stateless or statelet network-based single aggregate queue mechanisms for enforcing flow fairness, and/or flow protection in the Internet.
For flow fairness, which is the stronger requirement, we approximate the maxmin fairness of perflow fair queueing using a single queue serving all traversing flows. By assigning sorting tags to arriving packets, we can not only differentiate service priorities of flows but also eliminate the complex buffer partitioning normally required in perflow queueing schemes. Our proposed scheme has several desirable features. It is statelet as the flow state requirement is limited mainly to those flows taking relatively more bandwidth than the fair share. We leverage the limited flow state to develop a packet drop policy which helps avoid unwanted lockout (unfairness) behavior. We demonstrate by extensive simulations that the scheme is highly fair, efficient in resource utilization and suitable for a wide range of traffic adopting heterogenous TCP congestion control algorithms.
For flow protection, we require that the resource share of the high bandwidth flows should be bounded. To that end, we propose, model and analyze a suite of active queue management schemes, which generalize the well-known CHOKe scheme. Network operators can control the desired flow protection level by tuning a configurable parameter which also indexes the specific scheme chosen. Our flow protection framework not only remains simple and completely stateless, but is also highly effective in controlling the resource share of aggressive flows, as proved and verified by the tight bounds on flow buffer space shares and link utilizations. This allows well-behaved sources to obtain better service, i.e., low queueing delays and higher throughput, in the network.
Another key contribution of the thesis is the first analysis on the transient behavior of CHOKe queue following a change in the source rate of the unresponsive flow. The observed dynamic behaviors seem counter-intuitive as the flow’s throughput is moving in a direction opposite to the changes in the flow’s source rate. We present two models that characterize and explain these “perplexing” transient behaviors. | nb_NO |
