Abstract In an asynchronous transfer mode (ATM) switch having a Batcher sorting network followed by a plurality of banyan routing networks for switching packets from trunk grouped inputs to non-trunk grouped outputs via virtual circuits, order is maintained among the packets that are switched to the outputs by appending a bit, called the "stopper ID," to the destination address of each packet. This bit is computed on an input-by-input basis by a reservation ring that gives all inputs that are contending for access to any given output fair, round robin access to that output depending upon the round robin position of the particular input, so it is a valid sort key for preserving cell order. However, when packets are switched from trunk grouped inputs to trunk grouped outputs, a secondary sort key is employed for preserving the ordering of packets that are transferred via the same virtual circuit. This secondary sort key suitably is provided by using a k bit wide count (where k equals the number of banyan networks) to identify the ordering of packets on any given virtual circuit. A sort performed with this secondary sort key preserves the ordering of all packets on the same virtual circuit if no packets are permitted to join in on an arbitration session that is in progress or if priority is given during each arbitration session to any packets that lost during the preceding arbitration session.
In a switch having a non-blocking, self routing switching fabric for switching packets from non-trunk grouped inputs to trunk grouped and non-trunk group outputs on virtual circuits that are specified by said packets, said switching fabric having a sorting network coupled to a plurality of routing networks for providing plural inputs to said sorting network simultaneous access to the same output port of said routing networks; the improvement comprising means for preserving packet order on each of said virtual circuits.
Claim 2
Dependent Claim
80 words
In a switch having a non-blocking, self routing switching fabric for switching packets from non-trunk grouped inputs to trunk grouped and non-trunk group outputs on virtual circuits that are specified by said packets, said switching fabric having a sorting network coupled to a plurality of routing networks for providing plural inputs to said sorting network simultaneous access to the same output port of said routing networks; the improvement comprising means for preserving packet order on each of said virtual circuits.
Claim 3
Dependent Claim
80 words
In a switch having a non-blocking, self routing switching fabric for switching packets from trunk grouped inputs to trunk grouped and non-trunk group outputs on virtual circuits that are specified by said packets, said switching fabric having a sorting network coupled to a plurality of routing networks for providing plural inputs to said sorting network simultaneous access to the same output port of said routing networks; the improvement comprising means for preserving packet order on each of said virtual circuits.
Claim 4
Dependent Claim
80 words
In a switch having a non-blocking, self routing switching fabric for switching packets from trunk grouped inputs to trunk grouped and non-trunk group outputs on virtual circuits that are specified by said packets, said switching fabric having a sorting network coupled to a plurality of routing networks for providing plural inputs to said sorting network simultaneous access to the same output port of said routing networks; the improvement comprising means for preserving packet order on each of said virtual circuits.