Communication with few buffers: Analysis and design
Krishna, Arvind
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/20036
Description
Title
Communication with few buffers: Analysis and design
Author(s)
Krishna, Arvind
Issue Date
1991
Doctoral Committee Chair(s)
Hajek, Bruce
Department of Study
Electrical and Computer Engineering
Discipline
Electrical and Computer Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Engineering, Electronics and Electrical
Operations Research
Computer Science
Language
eng
Abstract
Various schemes for routing in high speed networks with few buffers are investigated. Deflection routing is an adaptive strategy for datagram routing which tries to diffuse congestion wherever it arises in the network. Deflection routing on a shuffle-exchange network under uniform traffic is analyzed by using approximate state equations to predict the distribution of packet states. Whenever two packets simultaneously attempt to traverse a link, a conflict resolution rule is invoked to determine which packet is deflected. It is shown that giving priority to packets closest to their destinations is the optimal conflict resolution rule, in a certain sense. The state equations, for two different priority rules, are also used to derive bounds on the probable amount of time needed for the network to empty and to explore the relationship between delay and throughput in steady state. It is demonstrated that the choice of priority rule greatly influences the performance of the network. Deflection routing is also studied on some other networks based on shuffle interconnections.
The second topic is concerned with circuit-switched communication networks in which each route is two links long, and each link can carry one call at a time. No symmetry assumption is made. Simple bounds, depending on the maximum call arrival rate and the maximum sum of rates at a link, are given on the blocking probabilities. An implication is that if the maximum per-route arrival rate converges to zero with a fixed bound on the sum of rates at links, then the well-known reduced-load blocking approximation is asymptotically exact, uniformly over all network topologies.
The third and final topic studied is packet routing on bounded degree networks, where the size of the buffers at each node is constrained to be small. An algorithm is presented which does packet routing on an N-node butterfly in time O(log N) with small constants. The algorithm is based on Ranade's probabilistic PRAM emulation. Bounds on performance of the algorithm are proven for permutation routing and partially balanced traffic. The network is divided into 2$\sp n$ disjoint sets of n nodes, N = n2$\sp n$, and k-partially balanced traffic is such that no given set of nodes has to send or receive more than kn packets. The main results are upper bounds on the probability that the routing time exceeds t for a fixed queue size. It is shown that if t = $\Omega$(log N), then the probability is less than $c\alpha\sp t$, where $c$,$\alpha$ $<$ 1. Bounds on the routing time for uniform, random traffic follow as a special case of partially balanced traffic.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
