Deflection routing is a simple, decentralized, and adaptive method for routing data packets in communication networks. The focus of this work is on deflection routing in the Manhattan street network (a two-dimensional directed mesh), although the analytic approach should apply to any regular network. Two approximate performance models that give sharp estimates of the steady-state throughput and the average packet delay for packets admitted to the network are presented. The results of extensive simulation experiments are reported, which corroborate the models' predictions. The results show that deflection routing is very effective. Two measures of the merit of a network for deflection routing are its diameter and its deflection index. Networks are presented whose diameter and deflection index are near the optimal values.>

Binary exponential backoff is a randomized protocol for regulating transmissions on a multiple-access broadcast channel. Ethernet, a local-area network, is built upon this protocol. The fundamental theoretical issue is stability: Does the backlog of packets awaiting transmission remain bounded in time, provided the rates of new packet arrivals are small enough? It is assumedn≥ 2 stations share the channel, each having an infinite buffer where packets accumulate while the station attempts to transmit the first from the buffer. Here, it is established that binary exponential backoff is stable if the sum of the arrival rates is sufficiently small. Detailed results are obtained on which rates lead to stability whenn= 2 stations share the channel. In passing, several other results are derived bearing on the efficiency of the conflict resolution process. Simulation results are reported that, in particular, indicate alternative retransmission protocols can significantly improve performance.

We consider the stochastic behavior of binary exponential backoff, a probabilistic algorithm for regulating transmissions on a multiple access channel. Ethernet, a local area network, is built upon this algorithm. The fundamental theoretical issue is stability: does the backlog of packets awaiting transmission remain bounded in time, provided the rates of new packet arrivals are small enough?