Semilattice Characterization of Nonblocking Networks

In a nonblocking network, no call need be lost because of link mismatch or junctor unavailability. Efficient nonblocking networks were invented by Charles Clos and, although they are not in common use at the present time, they are distinct possibilities for practical applications in the future, and they have substantial theoretical interest as outer limits on possible designs. Two degrees or strengths of the nonblocking property have been distinguished. 1 2 A connecting network is called strictly nonblocking if no call is blocked in any s t a t e ; it is nonblocking in the wide sense if there exists a rule for routing calls through the network so as to avoid all states in which calls are blocked, and yet still satisfy all demands 697 698 THE BELL SYSTEM TECHNICAL JOURNAL, MAY-JUNE 1 9 7 3 for connection as they arise, without disturbing calls already in progress. These properties have been given 1,2 topological characterizations, and examples of each are known, although it must be said t h a t examples of efficient wide-sense nonblocking networks are yet to be found. Our aim in this paper is to give new alternative characterizations of the nonblocking properties in terms of the semilattice structures of the set of network states and of the set of assignments the states realize; a key role is played by the homomorphism 7 (·) t h a t carries each state into the assignment it realizes. T h e property of being nonblocking in the wide sense lies between two other properties: t h a t of being strictly nonblocking (nonblocking in the strict sense) and t h a t of being rearrangeable.