Modeling Networks
that Drop Packets
The objective of this research is to gain a quantitative understanding of
the performance of networks that drop packets to resolve resource contention.
We have analyzed the performance of a butterfly network built with packet-dropping
switches under simple input traffic assumptions. We are currently studying
other networks for the same purposes.
Projects:
- The Performance of Simple Routing Algorithms that Drop Packets
with Professor R.K. Sitaraman, U. Massachusetts [Appeared in SPAA 97]
ABSTRACT :
Several modern high-speed networks implement routing algorithms that resolve
contention for resources such as buffer space by dropping (i.e., deleting)
packets. In this paper, we analyze the performance of such routing algorithms
for the commonly-used butterfly network. We assume that each switch of the
butterfly has a buffer that can hold a bounded number of packets, and any
packet attempting to enter a switch with a full buffer is simply dropped
from the network. We study three significant metrics that characterize routing
performance: expected throughput of the network, packet loss rate, and expected
delay of a packet. Our main results are analytic expressions for these three
performance metrics in terms of the network-size, size of the buffer at each
switch, and the packet arrival rate. Our analyses for the throughput and
packet loss rate hold for any non-predictive queuing protocol, including
simple, often-implemented protocols such as first-in first-out (FIFO) and
fixed-priority scheduling. Our delay expressions hold for the FIFO protocol.
Several facts of interest to a network designer fall out of our analysis.
Further, our results provide quantitative insights into how the three performance
metrics tradeoff against each other. Also, we present simulation results
to bolster the results of our analysis. Finally, we outline preliminary results
for routing on other networks such as the crossbar.
- Convergence and Concentration Results for
Packet Routing Networks with Professor R.K. Sitaraman,
U. Massachusetts [Appeared in SIROCCO 99]
ABSTRACT :
This paper focuses on two key issues in the performance analysis of packet
routing networks. The first issue is that of convergence, i.e., the
time it takes for a network that is initially in some arbitrary state to
approach steady state. The second issue is that of concentration of
performance metrics, such as throughput, about their expected values. We
model and study packet routing in arbitrary acyclic networks, where each
switch can buffer a bounded number of packets and packets that attempt to
enter full queues are dropped. We derive an upper-bound on the convergence
time T_{N}(e) which is the time taken for the
state distribution of network N to converge to within an e distance of its stationary(i.e., steady-state) distribution.
Further, we show that the throughput is concentrated about its expected value
by deriving bounds on the tail of its probability distribution. We illustrate
our results by applying them to the well-studied problem of routing uniform
traffic in a butterfly network with bounded-sized buffers. Our work makes
novel use of the method of bounded differences and recent advances in the
probabilistic technique of path coupling.
Please send me email if you want copies of these papers.
Back to my homepage
Last Modified Tue, 20 Apr 2004 02:07:17 GMT