My research primarily focusses
on Control of Communication Networks .
We are taking a systems approach to model the Internet and are working
towards designing better algorithms to reduce the over all delay in the
network, while maintaining stability.
Robustness
of Active Queue Management Schemes in the Internet Routers
In my Master's thesis,
we considered two major classes of
AQM (Active Queue Management) schemes, one which
marks packets based on
some function
of the queue length and the other which marks packets as a function of
a counter maintained by the router. The counter, known as the virtual queue, is the size of a
fictitious queue that is served by a link whose capacity is slightly
smaller than the capacity of the real link. The idea here
is that the virtual queue length is always larger than the real
queue length (since the virtual queue capacity is smaller than
the real queue capacity) and hence it provides early warning about
congestion.
Our main result was that
the
additional degree of freedom available in the choice of the capacity of
the virtual queue ensures that virtual queue-based schemes are
robust. By robustness, we mean that virtual queue-based AQM schemes,
when used in conjunction with TCP congestion control, remain stable and
ensure small queue lengths even in the presence of bursty traffic,
while real queue-based schemes can not. Thus, for example, RED
implemented in a virtual queue is more robust than the usual form of
RED.
Stability
of Internet Congestion Control Schemes with File Arrivals and Departures
Congestion control
schemes
have been typically studied
under the assumption that the number of file transfers in progress
is fixed. However, in reality,
files arrive and depart and the question we wished to answer in this
project is the
following: are congestion control schemes stable in the presence of
file arrivals and departures? By stability, here we mean that the
number of file transfers in the network is bounded in some
appropriate stochastic sense. Assuming exponentially distributed file
sizes,
it has been proved by others that the Internet is stable provided
that the load on each link is less than the link capacity. Our goal
was to answer this question for general file-size distributions.
At this point, we have
been
able
to obtain partial solutions to this problem. Given some traffic
statistics and a network topology,
we have developed a numerical test based on a technique called the
Sum-of-Squares (SoS)
method, which can verify the stability of the network. We have
applied this technique successfully
for small examples of networks with a star topology or a linear
topology.
Priority-based
Differentiation of Mice and Elephants in
Internet Routers
It is well-known that file
sizes in the Internet have a very
large variance. One implication of this is that most of the files are
small and contribute to a small amount of the total
traffic, while a few large files account for most of the traffic in the
Internet. If all the files share the available capacity in a fair
manner, then short files may experience long delays. In this work,
we studied the performance of a simple priority scheme at the
router which preferentially treats short-flows. Using simple fluid
models, we were able to show that such a priority scheme improves the
performance of short-flows significantly while the
performance of long-flows does not deteriorate much.
Buffer Sizing in the core Internet routers
Large buffers in the Internet routers can limit the achievable
throughput as one has to use off-chip DRAMs. A general
rule of thumb for buffer design is B = RT T × C. Recently,
it was shown that this design rule is outdated and one can
get away with using small buffers due to statistical multi-
plexing. However, the results were based on a static net-
work with fixed number of long-lived flows. In this work, we
study the effects of small buffers in networks with arrivals
and departures. Our results are in complete contrast with the earlier works. We show that on congested routers, it is impossible to use to small buffers with the current TCP-type protocols. Whenever routers do get congested, by increasing the buffer size, it is possible to achieve upto an order of magnitude improvement in the flow completion times. On routers that are not congested, O(1) buffers turn out to be sufficient.
On the brighter side, it turns out that, due to significant differences (roughly about 3 orders of magnitude) in the operating speeds of the core routers and the access links, core routers do not get congested even when the operating load is as high as 95%. Thus, very small buffers (O(1)) can be employed in the core routers. Unlike earlier works, our results indicate that statistical multiplexing plays an insignificant role in determining the buffer size. It turns out that even under high loads of upto 95%, there will not be enough flows to saturate the core router and therefore, losses are hardly seen on the core router.
RCP is a novel congestion control algorithm that has been shown to
reduce flow-completion times for typical Internet flows by an order
of magnitude as compared to the existing (TCP NewReno) and the more
recently proposed (XCP) congestion control algorithms. RCP achieves
this by explicitly emulating processor sharing among flows. So far,
RCP has been studied in simulations and has limited analysis. In this
work, we do a performance analysis of RCP. In particular we show
that RCP is stable under flow arrivals and departures on a single
congested link and we calculate the amount of buffering needed by RCP
routers for a bounded packet loss probability. We further go on to validate our results with simulations.
PUBLICATIONS
1.
A. Lakshmikantha, C.
L.
Beck and R. Srikant ``Robustness of Real
and Virtual
Queue based AQM schemes
", Proceedings of American Control
Conference held in Denver,2003
2. A. Lakshmikantha, C.
L. Beck and R. Srikant ``Connection level
Stability Analysis of the Internet using Sum of Squares (SoS)
Techiniques", appeared in Conference on on Information
Sciences and
Systems held at Princeton University, 2004. Also appeared as a
tutorial session paper in American Control Conference (ACC) 2005.
3. A. Lakshmikantha
and M. Babbar ``A Modified
NSGA-II to solve noisy
multi-objective
problems ", Proceedings of
Genetic
and Evolutionary Computation
Conference held in Chicago, 2003
4. A. Lakshmikantha,
C.L. Beck and R. Srikant ``Performance
Analysis of Priority
Queueing
Schemes in Internet Routers", appeared in the Conference on on
Information
Sciences and Systems at John Hopkins University, 2004.
5. A.
Lakshmikantha, C. L. Beck and R. Srikant ``Robustness
of Real and Virtual Queue based AQM schemes ",
appeared in
IEEE-Transactions on Networking, 2005.
6. A. Lakshmikantha, C.
L.
Beck and R. Srikant "A simple
fluid model to analyze resource sharing in the Internet routers", shorter version to appear in the Conference on Decision and Control, San Diego, December 2006.
|