ON THE STABILITY OF SHUFFLE-EXCHANGE AND BIDIRECTIONAL SHUFFLE-EXCHANGE DEFLECTION NETWORKS

In a stable packet-switched network, throughput equals offered load an d packet backlogs do not build up in an unbounded manner, A network wi th an unstable operating region poses the problem that it may evolve e ventually to a stable but saturated operating point with a low through put. This paper considers the shuffle-exchange and bidirectional shuff le networks when operated with deflection routing, It is shown that bo th networks exhibit instability when packet contention is resolved in a random manner, However, instability can be avoided if contention is resolved in a manner that favors packets closest to their destinations , This obviates the need for complicated network access control to pre vent instability.