Modification to a reservation ring mechanism for controlling contention in a broadband ISDN fast packet switch suitable for use in a local area network

• US 5,519,698 A
• Filed: 08/09/1993
• Issued: 05/21/1996
• Est. Priority Date: 05/20/1992
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Bell, Alan G., Lyles, Joseph B.
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Nguyen, Chau T.
• Application Number:
  US08/104,458
• Time in Patent Office: 1,016 Days
• Field of Search: 370/60, 370/60.1, 370/61, 370/58.1, 370/58.2, 370/94.1, 370/94.2, 340/825.52, 340/825.50
• US Class Current: 370/411
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 49/107 using shared medium
• CPC Class Codes: H04L 49/1561 Distribute and route fabrics, e.g. Batcher-Banyan
• CPC Class Codes: H04L 49/203 ATM switching fabrics with multicast or broadcast capabilities
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A switching network having a sorting network followed by a plurality of routing networks for routing packets from a plurality of inputs to a plurality of outputs in accordance with destination addresses specified by the packets includes a reservation ring mechanism for resolving conflicts among inputs contending for access to identical outputs. This reservation ring mechanism performs a sequence of step and compare operations in top-to-bottom ring-like order during one or more arbitration cycles for granting contending inputs access to the outputs for which those inputs are contending in top-to-bottom order. Each of the routing networks can route packets from any input to any output, so up to k packets are routed to each output during each arbitration cycle, where k equals the number of routing networks that are employed.

Claims

1. An arbitration process for resolving contention for output ports of a self-routing, non-blocking switch whenever an arbitration session is initiated while an excessive number of packets are pending at respective input ports of said switch in a ready state for routing to any one of said output pods;

said switch having a plurality of input ports, a plurality of uniquely addressable output pods, and k routers coupled between said input ports and said output ports for routing packets from said input ports to selected ones of said output ports in accordance with output port addresses which are specified by the respective packets, where k>

2;

each arbitration session being composed of at least one arbitration cycle;

said process comprising the steps of

initiating an arbitration cycle for said arbitration session;

comparing for equality and in a ring-like order the output port address specified by each packet pending at an input port of said switch with the respective output port addresses that are specified by any packets pending at other input pods of said switch, said addresses being compared just once to identify any packets that are ready for routing to identical output ports of said switch;

discriminating between any packets that are found to be ready for routing to identical output ports of said switch in accordance with predetermined eligibility rules which distinguish packets that are eligible to contend for such routing from packets that are ineligible to contend therefor under said eligibility rules;

resolving any contention among packets that are determined to be eligible to contend for routing to any given output port in favor of one and up to k of such eligible packets, with such contention being resolved in favor of less than all of the packets that are eligible to contend for routing to any particular output port only when there are more than k packets eligible to contend for that particular output port;

releasing one and up to k of said pending packets, including all packets for which contention is favorably resolved during the resolving step, into said switch for routing to said selected output pods to complete said arbitration cycle; and

repeating the initiating, comparing, discriminating, resolving and releasing steps until all packets that are pending at any of said input ports in a ready state for routing when said arbitration session is initiated are routed, with each arbitration cycle being biased to cause all packets that are pending in a ready state for routing to any designated output port when said arbitration session is initiated to be routed to said designated output port at least as early as any packet that is received for routing to said designated output port after said arbitration session is initiated.

2. The method of claim 1 wherein said non-blocking switch comprises a Batcher sorting network coupled to and followed by k Banyan routing networks.

3. The method of any of claims 1 or 2 wherein said predetermined order is a top-to-bottom order, whereby any contention is resolved in top-to-bottom round robin order.

4. The method of claims 1 or 2 wherein said steps are linear and systolic.

5. The method of any of claims 1 or 2 wherein new packets are free to be released into said switch for routing to an output port during the final cycle of an arbitration session for that output port if there are fewer than k retained packets for said final cycle.