Patent US6167049A successfully refreshed from Google Patents.
US6167049A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Non-zero minimum cell rate for available bit rate ATM service
Assignee: Toshiba Corp
•
Filing: 1997-11-18
•
Granted: 2000-12-26
•
Expires: 2017-11-18
Abstract
Abstract A scheduler in accord with the invention schedules available bit rate (ABR) traffic over an asynchronous transfer mode (ATM) link in such a manner as to provide circuits having the ABR traffic service a minimum cell rate (MCR) that may be greater than zero. The scheduler uses static scheduling information to schedule traffic for high priority services, such as constant bit rate service. The static information also specifies transmit opportunities for an ABR circuit, in a manner analogous to that for CBR traffic. The statically scheduled transmit opportunities provide a negotiated minimum cell rate that is greater than zero, for the ABR circuit. The scheduler maintains dynamic scheduling information, which it uses to schedule traffic in otherwise available transmit times. For example, the scheduler may use the dynamic information to create a work list of virtual circuit connections for ABR service. During any cell transmit time that is not used by a higher priority service (e.g. CBR or MCR), the scheduler goes to the work list to find a circuit with a cell ready for transmission and initiates transmission of the cell for that circuit. The ABR circuit having a non-zero MCR receives service from the statically scheduled opportunities and from the dynamically scheduled opportunities.
Inventors
- 👤 Tong-Bi Pei
- 👤 Kohei Abe
- 👤 Robert E. Thomas
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 21:29
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L2012/5638; H04L2012/5678; H04L2012/5679
Claims Analysis
Total Claims: 41
Claim 1
Independent Claim
167 words
A method of scheduling transmission of asynchronous transfer mode (ATM) cell traffic over a link, the method comprising: statically scheduling cell transmission in a first cell transmit time for a first virtual circuit, identified by a first virtual path identifier and a first virtual circuit identifier, associated with a high priority service and associated with an available bit rate service to provide a predetermined minimum cell rate that is greater than zero; statically scheduling cell transmission in a second cell transmit time for a second virtual circuit, identified by a second virtual path identifier and a second virtual circuit identifier, associated with a low priority service; and dynamically scheduling in said second cell transmit time cell transmission for another virtual circuit, identified by said second virtual path identifier and another virtual circuit identifier, associated with the available bit rate service in said second cell transmit time when no ATM cell carrying data is ready for transmission in said second cell transmit time for said second virtual circuit.
Claim 2
Independent Claim
167 words
A method of scheduling transmission of asynchronous transfer mode (ATM) cell traffic over a link, the method comprising: statically scheduling cell transmission in a first cell transmit time for a first virtual circuit, identified by a first virtual path identifier and a first virtual circuit identifier, associated with a high priority service and associated with an available bit rate service to provide a predetermined minimum cell rate that is greater than zero; statically scheduling cell transmission in a second cell transmit time for a second virtual circuit, identified by a second virtual path identifier and a second virtual circuit identifier, associated with a low priority service; and dynamically scheduling in said second cell transmit time cell transmission for another virtual circuit, identified by said second virtual path identifier and another virtual circuit identifier, associated with the available bit rate service in said second cell transmit time when no ATM cell carrying data is ready for transmission in said second cell transmit time for said second virtual circuit.
Claim 3
Dependent Claim
91 words
A method as in claim 1, wherein the statically scheduling said first virtual circuit associated with the available bit rate service comprises: indexing a line of a scheduling table stored in memory for the first cell transmit time, and identifying the virtual circuit from the indexed line of the scheduling table, and the method further includes transmitting a cell in the first cell transmit time for the identified virtual circuit associated with the available bit rate service regardless whether the cell with the identified virtual circuit has data ready for transmission.
Claim 4
Dependent Claim
73 words
A method as in claim 1, wherein the dynamically scheduling the identified virtual circuit associated with the available bit rate service comprises: indexing a line of a scheduling table stored in memory, identifying said second virtual circuit from the indexed line of the scheduling table, determining if the cell associated with said second virtual circuit has data was ready for transmission in said second cell transmit time, and identifying said another virtual circuit.
Claim 5
Dependent Claim
50 words
A method as in claim 2, wherein the scheduling table comprises one table having a plurality of lines indexed by cell transmit times for identifying said first virtual circuit associated with a constant bit rate service and for identifying said second virtual circuit associated with a variable bit rate service.
Claim 6
Dependent Claim
77 words
A method as in claim 2, wherein the scheduling table comprises: a static scheduling table having a plurality of lines including one of the following: (a) said virtual path identifier and said virtual circuit identifier associated with said high priority service and (b) said virtual path identifier and said virtual circuit identifier associated with a low priority service; and at least one dynamic scheduling table comprising lines identifying virtual circuits associated with the available bit rate service.
Claim 7
Dependent Claim
36 words
A method as in claim 3, wherein the dynamically scheduling further comprises modifying dynamic data for identifying the virtual circuit after transmission in the second cell transmit time, to reschedule service to the identified virtual circuit.
Claim 8
Dependent Claim
62 words
A method as in claim 6, wherein the modifying of the dynamic data comprises moving the dynamic data used to identify the virtual circuit from the line of the scheduling table indexed during the first transmit time down the table a predetermined number of lines to a line of the dynamic table that may be indexed during a third cell transmit time.
Claim 9
Dependent Claim
38 words
A method as in claim 7, wherein the number of lines is determined at least in part based on the reciprocal of the difference between allowable cell rate for the virtual circuit and the predetermined minimum cell rate.
Claim 10
Dependent Claim
42 words
A method as in claim 3, wherein the dynamically scheduling further comprises: adding an identity of the virtual circuit to a work list, and in the second cell transmit time, scheduling cell transmission for the identified virtual circuit using the work list.
Claim 11
Dependent Claim
18 words
A method as in claim 9, wherein the indexing does not occur during the first cell transmit time.
Claim 12
Independent Claim
170 words
A device for scheduling transmission of asynchronous transfer mode (ATM) cell traffic over a link, in a plurality of cell transmit times, comprising: means for statically scheduling cell transmission in a first cell transmit time for a first virtual circuit, identified by a first virtual path identifier and a first virtual circuit identifier, associated with a high priority service and an available bit rate service to provide a predetermined minimum cell rate that is greater than zero; means for statically scheduling cell transmission in a second cell transmit time for a second virtual circuit, identified by a second virtual path identifier and a second virtual circuit identifier, associated with a low priority service; and means for dynamically scheduling in said second cell transmit time cell transmission for another virtual circuit, identified by said second virtual path identifier and another virtual circuit identifier, associated with the available bit rate service when no ATM cell carrying data is ready for transmission in said second cell transmit time for said second virtual circuit.
Claim 13
Independent Claim
170 words
A device for scheduling transmission of asynchronous transfer mode (ATM) cell traffic over a link, in a plurality of cell transmit times, comprising: means for statically scheduling cell transmission in a first cell transmit time for a first virtual circuit, identified by a first virtual path identifier and a first virtual circuit identifier, associated with a high priority service and an available bit rate service to provide a predetermined minimum cell rate that is greater than zero; means for statically scheduling cell transmission in a second cell transmit time for a second virtual circuit, identified by a second virtual path identifier and a second virtual circuit identifier, associated with a low priority service; and means for dynamically scheduling in said second cell transmit time cell transmission for another virtual circuit, identified by said second virtual path identifier and another virtual circuit identifier, associated with the available bit rate service when no ATM cell carrying data is ready for transmission in said second cell transmit time for said second virtual circuit.
Claim 14
Dependent Claim
17 words
A device as in claim 11, comprising a scheduler included in an ATM segmentation and reassembly circuit.
Claim 15
Dependent Claim
21 words
A device as in claim 12, wherein the ATM segmentation and reassembly circuit is implemented in an ATM user network interface.
Claim 16
Independent Claim
342 words
A device, comprising: an asynchronous transfer mode (ATM) cell transmitter for transmitting ATM cells over a link; a scheduler controlling transmission of cells by the ATM transmitter; a static scheduling table stored in memory for use by the scheduler, the static scheduling table comprising a plurality of lines indexed by respective cell transmit times, each said line of the static scheduling table including a first field for data identifying a virtual circuit associated with a high priority service or an available bit rate service to provide a minimum cell rate that is greater than zero and assigned a respective cell transmit time as a transmit opportunity, the scheduler controlling the ATM transmitter arranged to send an ATM cell for each virtual circuit associated with the high priority service or the available bit rate service identified in the field of the static scheduling table line during the respective cell transmit time; a dynamic scheduling table maintained in memory by the scheduler, the dynamic scheduling table having a plurality of lines indexed by cell transmit times, each line of the dynamic scheduling table containing data which the scheduler uses to identify at least one virtual circuit associated with the available bit rate service; and a list maintained in memory by the scheduler of one or more virtual circuits identified from processing of the dynamic scheduling table, wherein the scheduler is arranged to access the list during an available cell transmit time in which there was no cell transmission scheduled as a result of no ATM cell carrying data being ready for transmission when indexed in the static table, wherein the scheduler is arranged to use the accessed information from the lists to identify a virtual circuit associated with the available bit rate service and having an ATM cell ready to transmit, and wherein the scheduler controls the ATM transmitter to transmit a ready cell during the available cell transmit time, wherein each said line of the static scheduling table includes a second field for data identifying a virtual circuit associated with a low priority.
Claim 17
Independent Claim
342 words
A device, comprising: an asynchronous transfer mode (ATM) cell transmitter for transmitting ATM cells over a link; a scheduler controlling transmission of cells by the ATM transmitter; a static scheduling table stored in memory for use by the scheduler, the static scheduling table comprising a plurality of lines indexed by respective cell transmit times, each said line of the static scheduling table including a first field for data identifying a virtual circuit associated with a high priority service or an available bit rate service to provide a minimum cell rate that is greater than zero and assigned a respective cell transmit time as a transmit opportunity, the scheduler controlling the ATM transmitter arranged to send an ATM cell for each virtual circuit associated with the high priority service or the available bit rate service identified in the field of the static scheduling table line during the respective cell transmit time; a dynamic scheduling table maintained in memory by the scheduler, the dynamic scheduling table having a plurality of lines indexed by cell transmit times, each line of the dynamic scheduling table containing data which the scheduler uses to identify at least one virtual circuit associated with the available bit rate service; and a list maintained in memory by the scheduler of one or more virtual circuits identified from processing of the dynamic scheduling table, wherein the scheduler is arranged to access the list during an available cell transmit time in which there was no cell transmission scheduled as a result of no ATM cell carrying data being ready for transmission when indexed in the static table, wherein the scheduler is arranged to use the accessed information from the lists to identify a virtual circuit associated with the available bit rate service and having an ATM cell ready to transmit, and wherein the scheduler controls the ATM transmitter to transmit a ready cell during the available cell transmit time, wherein each said line of the static scheduling table includes a second field for data identifying a virtual circuit associated with a low priority.
Claim 18
Dependent Claim
13 words
A device as in claim 14, wherein the list comprises a work list.
Claim 19
Dependent Claim
37 words
A device as in claim 15, wherein the scheduler uses data from a line of the dynamic scheduling table to add identifications of one or more virtual circuits to the work list during predetermined cell transmit times.
Claim 20
Dependent Claim
63 words
A device as in claim 14, wherein: each line of the static scheduling table identifies one virtual path connection from among a plurality of virtual path connections which may utilize bandwidth on the link, and any virtual circuit connection identified in the field of each line of the static scheduling table is a virtual circuit connection associated with the one virtual path connection.
Claim 21
Dependent Claim
30 words
A device as in claim 17, wherein the dynamic scheduling table comprises a plurality of dynamic scheduling tables each of which is associated with one of the virtual path connections.
Claim 22
Dependent Claim
26 words
A device as in claim 18, wherein the list comprises a plurality of lists each of which is associated with one of the virtual path connections.
Claim 23
Dependent Claim
68 words
A device as in claim 14, further comprising a media access control interface for receiving data relating to a plurality of data communication services from one or more data devices; and a segmentation processor for segmenting data received via the media access control interface, for adapting the segmented data into ATM cells and supplying the ATM cells to the ATM transmitter for scheduled transmission over the ATM link.
Claim 24
Independent Claim
324 words
A device, comprising: an asynchronous transfer mode (ATM) cell transmitter for transmitting ATM cells over a link; a scheduler controlling transmission of cells by the ATM transmitter; a scheduling table stored in memory for use by the scheduler, the scheduling table comprising a plurality of lines indexed by respective cell transmit times, each line of the scheduling table including a static portion and a dynamic portion, the static portion of each line including a high priority field for data identifying a virtual circuit associated with a high priority service or an available bit rate service to provide a minimum cell rate that is greater than zero and being assigned a respective cell transmit time as a transmit opportunity, the scheduler controlling the ATM transmitter to send an ATM cell for each virtual circuit connection identified in the high priority field during the respective cell transmit time, the dynamic portion of each line may contain data which the scheduler uses to identify at least one virtual circuit associated with the available bit rate service; and a list maintained in memory by the scheduler of one or more virtual circuits identified from processing of the dynamic portion of the scheduling table, wherein the scheduler is arranged to access the list during an available cell transmit time in which there was no cell transmission scheduled as a result of no ATM cell carrying data being ready for transmission when indexed in the first cell transmit time in the static portion, the scheduler being arranged to use accessed information from the list to identify a virtual circuit associated with the available bit rate service and having an ATM cell ready to transmit, and the scheduler being arranged to control the ATM transmitter to transmit the ready cell during the available cell transmit time, wherein each said line of the scheduling table includes a low priority field for data identifying a virtual circuit associated with a low priority service.
Claim 25
Independent Claim
324 words
A device, comprising: an asynchronous transfer mode (ATM) cell transmitter for transmitting ATM cells over a link; a scheduler controlling transmission of cells by the ATM transmitter; a scheduling table stored in memory for use by the scheduler, the scheduling table comprising a plurality of lines indexed by respective cell transmit times, each line of the scheduling table including a static portion and a dynamic portion, the static portion of each line including a high priority field for data identifying a virtual circuit associated with a high priority service or an available bit rate service to provide a minimum cell rate that is greater than zero and being assigned a respective cell transmit time as a transmit opportunity, the scheduler controlling the ATM transmitter to send an ATM cell for each virtual circuit connection identified in the high priority field during the respective cell transmit time, the dynamic portion of each line may contain data which the scheduler uses to identify at least one virtual circuit associated with the available bit rate service; and a list maintained in memory by the scheduler of one or more virtual circuits identified from processing of the dynamic portion of the scheduling table, wherein the scheduler is arranged to access the list during an available cell transmit time in which there was no cell transmission scheduled as a result of no ATM cell carrying data being ready for transmission when indexed in the first cell transmit time in the static portion, the scheduler being arranged to use accessed information from the list to identify a virtual circuit associated with the available bit rate service and having an ATM cell ready to transmit, and the scheduler being arranged to control the ATM transmitter to transmit the ready cell during the available cell transmit time, wherein each said line of the scheduling table includes a low priority field for data identifying a virtual circuit associated with a low priority service.
Claim 26
Dependent Claim
67 words
A device as in claim 21 including the scheduler, wherein each said line of the scheduling table identifiers one virtual path from among a plurality of virtual paths for utilizing a bandwidth on the link and wherein any virtual circuit identified in the field of the static portion of a line of the scheduling table is a virtual circuit connection associated with the one virtual path connection.
Claim 27
Dependent Claim
38 words
A device as in claim 22, wherein any virtual circuit connection identified using the data from the dynamic portion of a line of the scheduling table is a virtual circuit connection associated with the one virtual path connection.
Claim 28
Dependent Claim
27 words
A device as in claim 22, wherein the list comprises a plurality of work lists each of which is associated with one of the virtual path connections.
Claim 29
Dependent Claim
69 words
A device as in claim 21, further comprising a media access control interface for receiving data relating to a plurality of data communication services from one or more data devices; and a segmentation processor for segmenting data received via the media access control interface, for adapting the segmented data into the ATM cells and supplying the ATM cells to the ATM transmitter for scheduled transmission over the ATM link.
Claim 30
Independent Claim
314 words
A method of scheduling available bit rate traffic and other traffic over an asynchronous transfer mode (ATM) link in a sequence of cell transmit times, the method comprising: (a) during each cell transmit time, identifying one virtual path connection that is assigned the cell transmit time from among a plurality of virtual path connections that may utilize bandwidth on the link; (b) during each cell transmit time, determining from static scheduling information if there is a high priority virtual circuit connection that is assigned a first cell transmit time from among a plurality of high priority virtual circuit connections associated with the one virtual path connection, (c) in each cell transmit time in which there is a high priority virtual circuit connection assigned, transmitting a cell for the assigned high priority virtual circuit connection over the link, determining if the high priority virtual circuit connection has available bit rate service, and if so executing a flow control procedure for that high priority virtual circuit connection; (d) during at least some of the cell transmit times, accessing dynamic scheduling information to identify at least one available bit rate service virtual circuit connection from among a plurality of available bit rate service virtual circuit connections associated with the one virtual path connection, and adding an identity of the at least one available bit rate service virtual circuit connection to a work list, wherein one of the available bit rate virtual circuit connections identified in the dynamic scheduling information is the high priority virtual circuit connection having available bit rate service; and (e) during any cell transmit time in which there is no cell transmitted for a high priority virtual circuit connection, accessing the work list to identify an available bit rate service virtual circuit connection having a cell ready, and transmitting the cell for the identified available bit rate service virtual circuit connection over the link.
Claim 31
Independent Claim
314 words
A method of scheduling available bit rate traffic and other traffic over an asynchronous transfer mode (ATM) link in a sequence of cell transmit times, the method comprising: (a) during each cell transmit time, identifying one virtual path connection that is assigned the cell transmit time from among a plurality of virtual path connections that may utilize bandwidth on the link; (b) during each cell transmit time, determining from static scheduling information if there is a high priority virtual circuit connection that is assigned a first cell transmit time from among a plurality of high priority virtual circuit connections associated with the one virtual path connection, (c) in each cell transmit time in which there is a high priority virtual circuit connection assigned, transmitting a cell for the assigned high priority virtual circuit connection over the link, determining if the high priority virtual circuit connection has available bit rate service, and if so executing a flow control procedure for that high priority virtual circuit connection; (d) during at least some of the cell transmit times, accessing dynamic scheduling information to identify at least one available bit rate service virtual circuit connection from among a plurality of available bit rate service virtual circuit connections associated with the one virtual path connection, and adding an identity of the at least one available bit rate service virtual circuit connection to a work list, wherein one of the available bit rate virtual circuit connections identified in the dynamic scheduling information is the high priority virtual circuit connection having available bit rate service; and (e) during any cell transmit time in which there is no cell transmitted for a high priority virtual circuit connection, accessing the work list to identify an available bit rate service virtual circuit connection having a cell ready, and transmitting the cell for the identified available bit rate service virtual circuit connection over the link.
Claim 32
Dependent Claim
43 words
A method as in claim 26, further comprising the step of rescheduling a cell transmit opportunity for any available bit rate service virtual circuit connection that transmits a cell, for future addition to the work list in accord with a predetermined scheduling algorithm.
Claim 33
Dependent Claim
44 words
A method as in claim 27, wherein the predetermined scheduling algorithm is based at least in part on the difference between the bandwidth allocated to one virtual path connection and total minimum cell rate bandwidth for virtual circuit connections within that virtual path connection.
Claim 34
Dependent Claim
43 words
A method as in claim 27, wherein the predetermined scheduling algorithm is based at least in part on the reciprocal of the difference between allowable cell rate and minimum cell rate, for the high priority virtual circuit connection having available bit rate service.
Claim 35
Dependent Claim
51 words
A method as in claim 26, wherein the dynamic scheduling table comprises a plurality of scheduling tables each of which is associated with one of the virtual path connections, and the work list comprises a plurality of work lists each of which is associated with one of the virtual path connections.
Claim 36
Dependent Claim
17 words
A method as in claim 1, wherein the high priority service is a constant bit rate service.
Claim 37
Dependent Claim
17 words
A device as in claim 11, wherein the high priority service is a constant bit rate service.
Claim 38
Dependent Claim
17 words
A device as in claim 14, wherein the high priority service is a constant bit rate service.
Claim 39
Dependent Claim
17 words
A device as in claim 21, wherein the high priority service is a constant bit rate service.
Claim 40
Dependent Claim
17 words
A method as in claim 1, wherein the low priority service is a variable bit rate service.
Claim 41
Dependent Claim
17 words
A device as in claim 11, wherein the low priority service is a variable bit rate service.
References Cited (Backward Citations)
EP0471379A2
Cited
US5463620A
Cited
US5818842A
Cited
US5392280A
Cited
US5515363A
Cited
EP0700186A1
Cited
US5619502A
Cited
EP0717532A1
Cited
US5745477A
Cited
US5793747A
Cited
US5706288A
Cited
US5754530A
Cited
US5953336A
Cited
US5864538A
Cited
US5864540A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-12-26 | 2004-06-26 | 2004-12-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-12-26 | 2008-06-26 | 2008-12-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-12-26 | 2012-06-26 | 2012-12-26 | $7700.00 | Window Closed / Lapsed |