×

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
First Claim
Patent Images

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

View all claims
  • 4 Assignments
Timeline View
Assignment View
    ×
    ×