Files in this item
Files  Description  Format 

application/pdf 9124446.pdf (5MB)  (no description provided) 
Description
Title:  Communication with few buffers: Analysis and design 
Author(s):  Krishna, Arvind 
Doctoral Committee Chair(s):  Hajek, Bruce 
Department / Program:  Electrical and Computer Engineering 
Discipline:  Electrical and Computer Engineering 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Engineering, Electronics and Electrical
Operations Research Computer Science 
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 shuffleexchange 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 circuitswitched 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 perroute arrival rate converges to zero with a fixed bound on the sum of rates at links, then the wellknown reducedload 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 Nnode 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 kpartially 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. 
Issue Date:  1991 
Type:  Text 
Language:  English 
URI:  http://hdl.handle.net/2142/20036 
Rights Information:  Copyright 1991 Krishna, Arvind 
Date Available in IDEALS:  20110507 
Identifier in Online Catalog:  AAI9124446 
OCLC Identifier:  (UMI)AAI9124446 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Electrical and Computer Engineering
Dissertations and Theses in Electrical and Computer Engineering