Reservation ring mechanism for providing fair queued access in a fast packet switch networks
AssigneeXerox Corporation
InventorJoseph B. Lyles
Life of this patent
Estimating the term…
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.
Claims13
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.gtoreq.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.
Dependencies are inferred from the claim text.