Technique for resolving output port contention in a high speed packet switch
First Claim
1. Apparatus for resolving contention occurring in a packet switch having input and output modules between incoming packets each having a predefined routing address field which designates a particular one of the output modules of the switch, said apparatus comprisinga first and a second register for each input module, said first and second registers having a first field for storing the address of an incoming packet and a second field for registering whether that incoming packet had priorly lost a contention resolution in the apparatus,means for serially comparing said second registers of each input line with all first registers of said input modules,means for registering matches for each input module indicating contentions between incoming packets,combinatorial logic means responsive to said first and second registers for each input module,first output register means connected to each said logic means for determining the value of said second fields of said first and second registers, andsecond output register means connected to each said logic means for providing an output indicative of the resolution of the contention.
9 Assignments
0 Petitions
Accused Products
Abstract
Apparatus, and accompanying methods for use therein, for a large (e.g. approximately 1 Terabit/second), fault tolerant packet switch (200), particularly suited for asynchronous mode transfer (ATM) communication, which utilizes cell address look-ahead in conjunction with parallel, planes of self-routing cross-points (550), staggered time phased contention resolution and shared memory based input and output modules (260 and 270, respectively). The contention resolution involves storing for each input packet in two registers the address of the incoming packet and an indication of whether that packet had priorly lost a contention resolution. In that way a fairness factor is added to the contention resolution.
140 Citations
15 Claims
-
1. Apparatus for resolving contention occurring in a packet switch having input and output modules between incoming packets each having a predefined routing address field which designates a particular one of the output modules of the switch, said apparatus comprising
a first and a second register for each input module, said first and second registers having a first field for storing the address of an incoming packet and a second field for registering whether that incoming packet had priorly lost a contention resolution in the apparatus, means for serially comparing said second registers of each input line with all first registers of said input modules, means for registering matches for each input module indicating contentions between incoming packets, combinatorial logic means responsive to said first and second registers for each input module, first output register means connected to each said logic means for determining the value of said second fields of said first and second registers, and second output register means connected to each said logic means for providing an output indicative of the resolution of the contention.
-
4. Apparatus for a packet switch and comprising
a plurality of output module means, a plurality of input module means to which a plurality of streams of incoming packets are applied on a substantially simultaneous basis, each one of said incoming packets having a pre-defined routing address field which designates a particular output module means to which the one packet is destined; -
switch means connected between said input module means and said output module means; and a contention resolution circuit for resolving output contention occurring among ones of the incoming packets for individual ones of said output module means, said contention resolution circuit comprising arbitration means responsive to the pre-defined routing address fields appearing in each of the incoming packets for comparing each of said address fields against every other one of said address fields in order to determine whether at least two of the address fields match, wherein each of said address fields defines a request and matching ones of said address fields for any one of said output module means define contending requests therefor, and for selecting, in a pre-defined manner and in response to contending requests, one of the contending requests to be applied to said switch means, and means responsive to said arbitration means for generating control signals and applying said control signals to said plurality of input module means, wherein each of said control signals specifies whether an incoming packet is to be applied to said switch means, and said arbitration means further comprises means, responsive to prior states of the control signals, for determining the selected contending request for each of said output module means for which contending requests occur. - View Dependent Claims (5, 6)
-
-
7. Apparatus for a packet switch having a switching circuit with inputs and outputs, said apparatus comprising
a contention resolution circuit for resolving output contention occurring among ones of incoming packets for individual ones of said outputs, each one of said incoming packets having a pre-defined routing address field which designates a particular one of the outputs to which the one packet is destined and input module means responsive to a plurality of streams of incoming packets for providing the incoming packets therefrom, wherein said packets are applied on a substantially simultaneous basis to switching circuit inputs and each of said packets is applied to a different corresponding one of said inputs, and wherein each of said incoming packets comprises an incoming asynchronous transfer mode (ATM) cell having a routing header prepended thereto, said header comprising said predefined routing address field: - and
said contention resolution circuit comprising arbitration means, responsive to the pre-defined routing address field appearing in each of said incoming packets, for comparing each of said address fields against every other one of said address fields in order to determine whether at least two of said address fields match, wherein each of said address fields defines a corresponding request and matching ones of said address fields for any one of said outputs define contending requests therefor, the remaining address fields defining non-contending requests for remaining ones of said outputs, and for selecting, in a pre-defined manner and in response to the contending requests for each of said outputs for which contending requests occur, one of the contending requests therefor to be applied to said switching circuit for routing thereto to said each output, means responsive to said arbitration means for generating control signals, and means for selectively applying said control signals to said input module means, wherein each of said control signals specifies whether an incoming packet is to be applied to said switching circuit; said arbitration means further comprising means responsive to a pre-defined physical ranking of said incoming packets for determining said one selected contending request for each of said outputs for which contending requests occur, means responsive to a priority value of each of said incoming packets for determining said one selected contending request for each of said outputs for which contending requests occur, and means responsive to prior states of said control signals for determining said one selected contending request for each of said outputs for which contending requests occur. - View Dependent Claims (8, 9, 10, 11, 12)
- and
-
13. In apparatus for a packet switch having a switching circuit with inputs and outputs and a contention resolution circuit for resolving output contention occurring among ones of incoming packets for individual ones of said outputs, each one of said incoming packets having a pre-defined routing address field which designates a particular one of the outputs to which the one packet is destined, a method comprising in the contention resolution circuit the steps of:
-
comparing, in response to the predefined routing address field appearing in each incoming packet, each of said address fields against every other one of said address fields in order to determine whether at least two of the address fields match, wherein each of said address fields defines a corresponding request and matching ones of said address fields for any one of said outputs define contending requests therefor, the remaining address fields defining non-contending requests for remaining ones of said outputs, selecting in a pre-defined manner and in response to the contending requests for each of said outputs for which contending requests occur one of the contending requests routing of its incoming packet to each said output, and generating control signals in response to said comparing and selecting steps, wherein each of said control signals specifies whether a corresponding one of the incoming packets is to be applied to a corresponding input of the switching circuit, said corresponding one packet being applied to said corresponding input in the event said corresponding one packet is associated with a selected contending request or a non-contending request, and wherein said selecting steps comprises; (a) the step of determining, in response to a pre-defined physical ranking of the incoming packets, said one selected contending request for each of said outputs for which said contending requests occur, (b) the step of determining, in response to a priority value of each of said incoming packets, said one selected contending request for each of said outputs for which contending requests occur, and (c) the step of determining, in response to prior states of said control signals, said one selected contending request for each of said outputs for which contending requests occur. - View Dependent Claims (14, 15)
-
Specification