Reservation ring mechanism for providing fair queued access in a fast packet switch networks

• US 5,689,508 A
• Filed: 12/21/1995
• Issued: 11/18/1997
• Est. Priority Date: 12/21/1995
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Lyles, Joseph B.
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): VU, HUY DUY
• Application Number:
  US08/576,099
• Time in Patent Office: 698 Days
• Field of Search: 370/351, 370/389, 370/390, 370/391, 370/392, 370/393, 370/394, 370/395, 370/396, 370/397, 370/398, 370/399, 370/411, 370/412, 370/413, 370/414, 370/415, 370/416, 370/417, 370/418, 370/419, 370/422, 370/423, 370/424, 370/426, 370/427, 370/428, 370/429, 370/356, 370/355, 370/252, 370/253, 370/235, 370/236, 370/431, 370/442, 370/443 , 370/462, 370/464, 370/465
• US Class Current: 370/391
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5612 Ring
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5672 Multiplexing, e.g. coding, scrambling
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• 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: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction

Abstract

A non-blocking switching network for routing packets from a plurality of inputs to a plurality of outputs includes a reservation ring mechanism for resolving conflicts among inputs contending for access to specified ones of said outputs. This reservation ring performs a sequence of step and compare operations in top-to-bottom ring-like order during at least one arbitration cycle for granting contending inputs access to said specified outputs in a top-to-bottom order that is also consistent with the order required by self-clocked weighted fair queueing or, alternatively, virtual clock, with up to a maximum permissible plural number of contenders being given access to such an output on each of the arbitration cycles.

Claims

1. In a finite bandwidth distributed multiplexing system which is configured to simultaneously route packets for a given class of service from up to k different inputs, where k≧

1, to a given output in response to service requests made by a potentially larger number of inputs on behalf of packets at said inputs;

each of said inputs being assigned a predetermined share of said bandwidth for feeding packets to said output and having at least one storage queue for said packets pending service grants;

an improved process for resolving scheduling conflicts among said packets, said process comprising the steps of

labeling each of the service requests made by said inputs upon their receipt (i) with an identifier which uniquely identifies the input making the request and (ii) with a virtual finishing time, said virtual finishing time being computed from a current virtual time by adding an offset that is weighted in accordance with the bandwidth share assigned to the input making the request;

entering the labeled service requests into a distributed queue;

sorting the labeled requests in said queue, each time a new request is entered into said queue, in accordance with their respective virtual finishing times to organize the labeled requests in ascending order of virtual finishing times; and

taking up to the first k labeled requests off said queue for service during each cycle of said multiplexing system.

2. The process of claim 1 wherein

said distributed queue is defined by a reservation ring which runs an arbitration process for resolving said scheduling conflicts;

and

the sorting of said labeled requests is performed by said arbitration process.

3. The process of claim 1 wherein said virtual finishing times are defined by binary values of constrained bit length.

4. The process of claim 3 wherein said virtual finishing times are expressed as relative times within a constrained range which is greater than twice the ratio of a largest one of the assigned bandwidth shares to a smallest one of the assigned bandwidth shares.

5. The process of claim 4 wherein

said distributes queue is defined by a reservation ring which runs a cyclical arbitration process on said distributes queue for resolving said scheduling conflicts;

and

the sorting of said labeled requests is performed by said arbitration process.

6. The process of claim 5 wherein the virtual finishing time for determining said current virtual time is determined by monitoring said arbitration process.

7. The process of claim 6 wherein said current virtual time is determined based on the virtual finishing time of the request with the largest virtual finishing time of the requests taken off said distributed queue during a most recent arbitration cycle.

8. The process of any of claims 1, 2, 4, 5 or 7 wherein said packets have identical bit lengths.

9. The process of claim 8 wherein said multiplexing system includes a non-blocking asynchronous transfer mode switching fabric for distributing aid packets from said inputs to selected ones of a plurality of outputs.

10. The process of claim 9 wherein k≧

2.

11. The process of any of claims 1, 2, 4, 5 or 7 wherein

said system routes packets for a plurality of different service classes, including a reserved traffic class and a best efforts class;

said packets are first sorted into said service classes before said service request are made,

class of service dependent operations are performed on service requests within said distributed queue to provide timely routing of reserved traffic class packets.

12. The process of claim 11 wherein, at least under certain conditions,

said current virtual is determined, for any service request made on behalf of a reserved traffic class packet, based on a theoretical packet finishing time;

where the theoretical finishing time for a given packet over a link having the bandwidth that is assigned to the input making the service request on behalf of the given packet.

13. The process of claim 12 wherein said multiplexing system includes a non-blocking asynchronous transfer mode switching fabric for distributing aid packets from said inputs to selected ones of a plurality of outputs.