US5689508A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Reservation ring mechanism for providing fair queued access in a fast packet switch networks
Assignee: Xerox Corp
•
Filing: 1995-12-21
•
Granted: 1997-11-18
•
Expires: 2015-12-21
Abstract
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.
Inventors
- 👤 Joseph B. Lyles
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 22:42
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L49/00; H04L49/15; H04L49/1553; H04L49/1561; H04L49/20; H04L49/201; H04L49/203; H04L49/30; H04L49/3081; H04L2012/5603; H04L2012/5609; H04L2012/5612; H04L2012/5638; H04L2012/5646; H04L2012/5651; H04L2012/5672; H04L2012/5678; H04L2012/5679
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
229 words
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.
Claim 2
Dependent Claim
229 words
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.
Claim 3
Dependent Claim
38 words
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.
Claim 4
Dependent Claim
19 words
The process of claim 1 wherein said virtual finishing times are defined by binary values of constrained bit length.
Claim 5
Dependent Claim
44 words
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.
Claim 6
Dependent Claim
43 words
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.
Claim 7
Dependent Claim
23 words
The process of claim 5 wherein the virtual finishing time for determining said current virtual time is determined by monitoring said arbitration process.
Claim 8
Dependent Claim
41 words
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.
Claim 9
Dependent Claim
19 words
The process of any of claims 1, 2, 4, 5 or 7 wherein said packets have identical bit lengths.
Claim 10
Dependent Claim
32 words
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.
Claim 11
Dependent Claim
7 words
The process of claim 9 wherein k≧2.
Claim 12
Dependent Claim
72 words
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.
Claim 13
Dependent Claim
67 words
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.
Claim 14
Dependent Claim
32 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-11-17 | 2001-05-19 | 2001-11-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-11-17 | 2005-05-19 | 2005-11-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-11-17 | 2009-05-19 | 2009-11-18 | $7700.00 | Window Closed / Lapsed |