Partial state routers: design, analysis and evaluation

Abstract

The current Internet traffic is distributed in a heavy tailed fashion between Web mice (short web connections which are numerous in number but carry only a small proportion of data) and elephants (long term bulk data flows). Routers require the capability of detecting the non-responsive component of the elephants and penalize them in order to protect the responsive component of the elephants as well as the interactive traffic like Web mice. In this thesis, we motivate the use of partial state schemes in a wide variety of network applications. Partial state can be used to arrive at a list of high bandwidth flows which can be made use of in containing non-responsive flows, providing better QoS to web traffic, and alleviate certain Denial of Service (DoS) attacks. We show the practical feasibility of partial state based schemes by implementing a novel partial state scheme, LRU-FQ, on Linux platform. The scheme makes use of an LRU cache to classify the incoming flows into high-bandwidth and low-bandwidth classes. A class-based Fair Queuing algorithm is used to obtain a policy driven control of the proportion of link bandwidth allocated to high bandwidth flows being serviced at the router. The thesis presents an analysis of the LRU partial state. Empirical data is presented to bring out the stated use of partial state schemes.