Communication with few buffers: Analysis and design

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.U of I OnlyETDs are only available to UIUC Users without author permissio