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

Claim 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.

Claim 4

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.

Claim 5

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

Claim 6

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.