TY - GEN

T1 - On the average delay for routing subject to independent deflections

AU - Hajek, Bruce

AU - Cruz, Rene L.

N1 - Funding Information:
This research was supported by the National Science Foundation under contracts NSF-NCR-90-04355 and NSF-89-04029. The authors wish to thank Andrew Barron, Jack Brassil, Albert Greenberg, and Jack Wolf for useful suggestions.
Publisher Copyright:
© 1991 Institute of Electrical and Electronics Engineers Inc. All rights reserved.

PY - 1991

Y1 - 1991

N2 - Consider a packet walking along a directed graph with each node having two edges directed out. The packet is headed towards one of N destinations, chosen according to a probability distribution p. At each step, the packet is forced to use a nonpreferred edge with some probability q, independently of past events. Using information theory and sequential analysis, it is shown that the mean number of steps required by the packet to reach the destination is, roughly, at least H{p)l(l - h(q)), where h is the binary entropy function and H(p) is the entropy (base two) of p. This lower bound is shown to be asymptotically achievable under the restriction that the packet always begins at a fixed node. The work is motivated by the search for graphs which work well in conjunction with deflection routing in communication networks.

AB - Consider a packet walking along a directed graph with each node having two edges directed out. The packet is headed towards one of N destinations, chosen according to a probability distribution p. At each step, the packet is forced to use a nonpreferred edge with some probability q, independently of past events. Using information theory and sequential analysis, it is shown that the mean number of steps required by the packet to reach the destination is, roughly, at least H{p)l(l - h(q)), where h is the binary entropy function and H(p) is the entropy (base two) of p. This lower bound is shown to be asymptotically achievable under the restriction that the packet always begins at a fixed node. The work is motivated by the search for graphs which work well in conjunction with deflection routing in communication networks.

UR - http://www.scopus.com/inward/record.url?scp=85067460880&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85067460880&partnerID=8YFLogxK

U2 - 10.1109/ISIT.1991.695209

DO - 10.1109/ISIT.1991.695209

M3 - Conference contribution

AN - SCOPUS:85067460880

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 153

BT - Proceedings - 1991 IEEE International Symposium on Information Theory, ISIT 1991

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 1991 IEEE International Symposium on Information Theory, ISIT 1991

Y2 - 24 June 1991 through 28 June 1991

ER -