On the stability of shuffle-exchange and bidirectional shuffle-exchange deflection networks

In a stable packet-switched network, throughput equals offered load and packet backlogs do not build up in an unbounded manner, A network with an unstable operating region poses the problem that it may evolve eventually to a stable but saturated operating point with a low throughput. This paper considers the shuffle-exchange and bidirectional shuffle networks when operated with deflection routing, It is shown that both 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 prevent instability.