Bounds on evacuation time for deflection routing

Summary Upper bounds are given on the timeT needed to evacuatek packets from a synchronous packet network using deflection routing, whereby all packets that arrive at a node during one time slot leave the node during the next slot. For example,Tn+2(k–1) for a binaryn-cube network when priority is given to packets closer to their destination, and for a single destination networkT is less than or equal to the network diameter plusk–1 times the network deflection index. Deflection routing for one pass through an omega network is also considered.Bruce Hajek received a B.S. in Mathematics and an M.S. in Electrical Engineering from the University of Illinois and a Ph.D. in Electrical Engineering from the University of California at Berkeley. He is a Professor in the Coordinated Science Laboratory and the Department of Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign, where he has been since August, 1979. His research interests include communication and computer network algorithms, information theory, random processes, and combinatorial optimization.Supported by the National Science Foundation under contract NSF ECS 83 52030 with matching funds provided by AT&T. Postal address: CSL, 1101 W. Springfield, Urbana IL 61801, USA.