US5835494A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multi-level rate scheduler
Assignee: Cisco Technology Inc
•
Filing: 1997-03-27
•
Granted: 1998-11-10
•
Expires: 2017-03-27
Abstract
Abstract A method and apparatus are provided for scheduling when each of a plurality of virtual connections supported by a transmit device will be serviced by the transmit device. The transmit device includes a transmission control unit that uses a plurality of calendars to schedule when each of the plurality of virtual connections will be serviced. Virtual connections with faster transfer rates are scheduled using higher granularity calendars, while virtual connections with slower transfer rates are scheduled using lower granularity calendars. Each entry in the calendars is associated with a time interval ("cell slot") during which the transmit device is able to service one virtual connection. During a given cell slot, linked lists associated with the calendar entries that correspond to the cell slot are added to a service queue, and the virtual connection at the head of the service queue is serviced. After a virtual connection is serviced, the next service time for the virtual connection is scheduled by attaching the virtual connection to the head of a linked list associated with the appropriate entry of the appropriate calendar. The appropriate entry is determined by incrementing a fixed-point "desired service time" value that represents the cell slot for which the virtual connection was last scheduled, by a fixed-point inter-gap value that represents the how many cell slots ideally elapse between sequential service times of the virtual connection.
Inventors
- 👤 David A. Hughes
- 👤 Daniel E. Klausmeier
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 04:45
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04L47/00; H04L47/10; H04L47/24; H04L47/2441; H04L47/50; H04L47/56; H04L47/568; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L2012/5638; H04L2012/5646; H04L2012/5649; H04L2012/5678; H04L2012/5679; H04L2012/5681
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
78 words
A method for scheduling a service time for a virtual connection, the method comprising the computer-implemented steps of: determining a transfer rate associated with said virtual connection; if said transfer rate falls within a first range of transfer rates, then scheduling said service time for said virtual connection using a first calendar; and if said transfer rate falls within a second range of transfer rates, then scheduling said service time for said virtual connection using a second calendar.
Claim 2
Independent Claim
78 words
A method for scheduling a service time for a virtual connection, the method comprising the computer-implemented steps of: determining a transfer rate associated with said virtual connection; if said transfer rate falls within a first range of transfer rates, then scheduling said service time for said virtual connection using a first calendar; and if said transfer rate falls within a second range of transfer rates, then scheduling said service time for said virtual connection using a second calendar.
Claim 3
Dependent Claim
227 words
The method of claim 1 wherein: said first calendar includes a first plurality of entries; each of said first plurality of entries is associated with a cell slot; the cell slot associated with each entry in said first plurality of entries occurs a first predetermined interval after the cell slot associated with the entry that immediately precedes said entry in said first calendar; said step of scheduling said service time for said virtual connection using said first calendar includes the steps of: determining a cell slot for said virtual connection; and associating said virtual connection with the entry of said first plurality of entries that is associated with said cell slot; said second calendar includes a second plurality of entries; each of said second plurality of entries is associated with a cell slot; the cell slot associated with each entry in said second plurality of entries occurs a second predetermined interval after the cell slot associated with the entry that immediately precedes said entry in said second calendar, said second predetermined interval being different from said first predetermined interval; said step of scheduling said service time for said virtual connection using said second calendar includes the steps of: determining a cell slot for said virtual connection; and associating said virtual connection with the entry of said second plurality of entries that is associated with said cell slot.
Claim 4
Dependent Claim
91 words
The method of claim 2 wherein: the step of associating said virtual connection with the entry of said first plurality of entries that is associated with said cell slot includes the step of adding the virtual connection to a cell slot linked list associated with said cell slot; and the step of associating said virtual connection with the entry of said second plurality of entries that is associated with said cell slot includes the step of adding the virtual connection to a cell slot linked list associated with said cell slot.
Claim 5
Dependent Claim
58 words
The method of claim 3 wherein: the cell slot linked list associated with said cell slot has a head and a tail; and the step of adding the virtual connection to a cell slot linked list associated with said cell slot includes the step of adding the virtual connection to the head of said cell slot linked list.
Claim 6
Dependent Claim
83 words
The method of claim 2 wherein: said step of determining a cell slot for said virtual connection includes the steps of generating an inter-cell gap value for said virtual connection based on the transfer rate of said virtual connection; incrementing a desired service time value that represents a previous desired service time of said virtual connection by said inter-cell gap value to generate a new desired service time value; and determining a cell slot that corresponds to said new desired service time value.
Claim 7
Dependent Claim
73 words
The method of claim 5 wherein: said step of generating an inter-cell gap value comprises generating a first fixed-point number; said step of incrementing a desired service time value that represents a previous desired service time of said virtual connection by said inter-cell gap value to generate a new desired service time value comprises the step of adding said first fixed-point number to a second fixed-point number to generate a third fixed-point number.
Claim 8
Dependent Claim
43 words
The method of claim 6 wherein said step of determining a cell slot that corresponds to said new desired service time value includes the steps of: converting said third fixed-point number to an integer; and determining said cell slot based upon said integer.
Claim 9
Dependent Claim
101 words
The method of claim 2 further comprising the steps of: for each of said first plurality of entries, during the cell slot associated with said entry, adding the virtual connections associated with said entry to a first service queue; for each of said second plurality of entries, during the cell slot associated with said entry, adding the virtual connections associated with said entry to a second service queue; servicing virtual connections in said first service queue and said second service queue based on the order in which said virtual connections appear in said first service queue and said second service queue.
Claim 10
Dependent Claim
20 words
The method of claim 8 wherein said first service queue is the same linked list as said second service queue.
Claim 11
Dependent Claim
128 words
The method of claim 8 wherein said first service queue is different from said second service queue, the method further comprising performing the following steps during each cell slot: if said first service queue is not empty, performing the steps of servicing the virtual connection at the head of said first service queue; removing the virtual connection from the head of said first service queue; and scheduling a new service time for said virtual connection using said first calendar; if said first service queue is empty, performing the steps of servicing the virtual connection at the head of said second service queue; removing the virtual connection from the head of said second service queue; and scheduling a new service time for said virtual connection using said second calendar.
Claim 12
Independent Claim
120 words
A method, for use in a transmit device, for scheduling a service time for a virtual connection, comprising the steps of: receiving a cell that includes a connection identifier corresponding to said virtual connection: reading a fixed-point inter-cell gap value from a location in a table of fixed-point inter-cell gap values indicated by said connection identifier, said fixed-point inter-cell gap value being based on a transfer rate of said virtual connection; incrementing a fixed-point desired service time value by said fixed-point inter-cell gap value to generate a new fixed-point desired service time value; determining an entry in a calendar that corresponds to said new fixed-point desired service time value; and associating said virtual connection with said entry in said calendar.
Claim 13
Independent Claim
120 words
A method, for use in a transmit device, for scheduling a service time for a virtual connection, comprising the steps of: receiving a cell that includes a connection identifier corresponding to said virtual connection: reading a fixed-point inter-cell gap value from a location in a table of fixed-point inter-cell gap values indicated by said connection identifier, said fixed-point inter-cell gap value being based on a transfer rate of said virtual connection; incrementing a fixed-point desired service time value by said fixed-point inter-cell gap value to generate a new fixed-point desired service time value; determining an entry in a calendar that corresponds to said new fixed-point desired service time value; and associating said virtual connection with said entry in said calendar.
Claim 14
Dependent Claim
48 words
The method of claim 11 further comprising the steps of: generating said fixed-point inter-cell gap value by dividing a transfer rate of said transmit device by the transfer rate of said virtual connection; and storing said fixed-point inter-cell gap value in said table of fixed-point inter-cell gap values.
Claim 15
Dependent Claim
27 words
The method of claim 11 further comprising the step of selecting said calendar from a plurality of calendars based on the transfer rate of said virtual connection.
Claim 16
Dependent Claim
108 words
A transmit device comprising: a cell buffer for storing cells to be transmitted over a plurality of virtual connections; a memory having stored therein a plurality of calendars; a transmission control unit configured to schedule service times for said plurality of virtual connections, wherein said transmission control unit is configured to select a calendar of said plurality of calendars for each of said plurality of virtual connections based on a transfer rate associated with each of said plurality of virtual connections; and schedule service times for each virtual connection using the calendar that was selected for said virtual connection based on the transfer rate of said virtual connection.
Claim 17
Dependent Claim
108 words
A transmit device comprising: a cell buffer for storing cells to be transmitted over a plurality of virtual connections; a memory having stored therein a plurality of calendars; a transmission control unit configured to schedule service times for said plurality of virtual connections, wherein said transmission control unit is configured to select a calendar of said plurality of calendars for each of said plurality of virtual connections based on a transfer rate associated with each of said plurality of virtual connections; and schedule service times for each virtual connection using the calendar that was selected for said virtual connection based on the transfer rate of said virtual connection.
Claim 18
Dependent Claim
126 words
The transmit device of claim 14 wherein: each of said calendars includes a plurality of entries; each of said plurality of entries is associated with a cell slot; the cell slot associated with each entry in said plurality of entries occurs a predetermined interval after the cell slot associated with the entry that immediately precedes said entry in said calendar; said predetermined interval is different for each calendar of said plurality of calendars; the transmission control unit is configured to schedule a service time for each virtual connection using the calendar that was selected for said virtual connection by: determining a cell slot for said virtual connection; and associating said virtual connection with the entry of said selected calendar that is associated with said cell slot.
Claim 19
Dependent Claim
85 words
The transmit device of claim 15 wherein: said transmission control unit is configured to determine a cell slot for said virtual connection by generating an inter-cell gap value for said virtual connection based on the transfer rate of said virtual connection; incrementing a desired service time value that represents a previous desired service time of said virtual connection by said inter-cell gap value to generate a new desired service time value; and determining a cell slot that corresponds to said new desired service time value.
References Cited (Backward Citations)
US5179556A
Cited
US5241536A
Cited
US5463620A
Cited
US5499238A
Cited
GB2288097A
Cited
US5577035A
Cited
US5515363A
Cited
US5533020A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-11-09 | 2002-05-11 | 2002-11-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-11-09 | 2006-05-11 | 2006-11-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-11-09 | 2010-05-11 | 2010-11-10 | $7700.00 | Window Closed / Lapsed |