US6205151B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
ATM cell scheduler which uses a heap memory and associates timestamps with each channel
Assignee: Texas Instruments Inc
•
Filing: 1997-12-18
•
Granted: 2001-03-20
•
Expires: 2017-12-18
Abstract
Abstract A network hub and Asynchronous Transfer Mode (ATM) translator system ( 5 ) for use in a Local Area Network (LAN)-based communications system is disclosed. The network hub and ATM translator system ( 5 ) includes a host controller ( 10 ) that serves as the LAN hub, and which interfaces with a translator card ( 15 ) which includes a segmentation and reassembly device ( 12 ) in connection with SONET receive/transmit circuitry ( 20 ) that communicates with a transceiver ( 22 ) to transmit and receive ATM packet cells over a communications facility (FO). The translator card ( 15 ) also includes a scheduler ( 14 ) that includes a heap sort state machine ( 36 ) which maintains a sorted list of entries, in a heap fashion, in on-chip parameter memory ( 44 ) and off-chip parameter memory ( 18 ). The entries include, for each ATM channel, a channel identifier and a timestamp that indicates the time at which the next cell for the channel will be due for transmission. A due comparator ( 40 ) compares the timestamp of the root value in the heap (i.e., the channel with the next due cell) to a global time generated by a reference timer ( 38 ), and indicates to a source behavior processor ( 24 ) in the scheduler ( 14 ) that a cell is due for transmission. The scheduler than issues a transmit credit for the cell, and communicates this event with the SAR device ( 12 ) to effect the transmission as appropriate.
Inventors
- 👤 Jeffrey R. Quay
- 👤 Brian J. Karguth
- 👤 Sharat Prasad
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 13:26
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/5678; H04L2012/5679
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
126 words
A method of scheduling the transmission of packet cells associated with a plurality of communications channels, comprising the steps of: sorting channel entries in a heap memory, each channel entry comprising a timestamp value associated with each channel, the timestamp value indicating a time at which the transmission of a cell for the associated channel is next due, the sorting step identifying a root channel entry corresponding to the next due channel; comparing the timestamp value of the root channel entry to a global time generated by a reference timer; and responsive to the comparing step determining that the global time has at least reached the timestamp value of the root channel entry, issuing a transmit credit for the channel associated with the root channel entry.
Claim 2
Independent Claim
126 words
A method of scheduling the transmission of packet cells associated with a plurality of communications channels, comprising the steps of: sorting channel entries in a heap memory, each channel entry comprising a timestamp value associated with each channel, the timestamp value indicating a time at which the transmission of a cell for the associated channel is next due, the sorting step identifying a root channel entry corresponding to the next due channel; comparing the timestamp value of the root channel entry to a global time generated by a reference timer; and responsive to the comparing step determining that the global time has at least reached the timestamp value of the root channel entry, issuing a transmit credit for the channel associated with the root channel entry.
Claim 3
Dependent Claim
58 words
The method of claim 1 , further comprising: after the step of issuing a transmit credit, retrieving an allowed cell rate value from a parameter memory for the channel associated with the root channel entry; deriving a new timestamp value for the channel associated with the root channel entry; and then repeating the sorting, comparing, and issuing steps.
Claim 4
Independent Claim
217 words
A method of scheduling the transmission of packet cells associated with a plurality of communications channels, comprising the steps of: sorting channel entries in a heap memory, each channel entry comprising a timestamp value associated with each channel, the timestamp value indicating a time at which the transmission of a cell for the associated channel is next due, the sorting step identifying a root channel entry corresponding to the next due channel; comparing the timestamp value of the root channel entry to a global time generated by a reference timer; and responsive to the comparing step determining that the global time has at least reached the timestamp value of the root channel entry, issuing a transmit credit for the channel associated with the root channel entry; after the step of issuing a transmit credit, retrieving an allowed cell rate value from a parameter memory for the channel associated with the root channel entry; deriving a new timestamp value for the channel associated with the root channel entry, the deriving step comprising: generating an offset timestamp value based upon a scheduler clock frequency divided by the allowed cell rate value; adding the offset timestamp value to a base timestamp value to produce the new timestamp value; and after the deriving step, repeating the sorting, comparing, and issuing steps.
Claim 5
Independent Claim
217 words
A method of scheduling the transmission of packet cells associated with a plurality of communications channels, comprising the steps of: sorting channel entries in a heap memory, each channel entry comprising a timestamp value associated with each channel, the timestamp value indicating a time at which the transmission of a cell for the associated channel is next due, the sorting step identifying a root channel entry corresponding to the next due channel; comparing the timestamp value of the root channel entry to a global time generated by a reference timer; and responsive to the comparing step determining that the global time has at least reached the timestamp value of the root channel entry, issuing a transmit credit for the channel associated with the root channel entry; after the step of issuing a transmit credit, retrieving an allowed cell rate value from a parameter memory for the channel associated with the root channel entry; deriving a new timestamp value for the channel associated with the root channel entry, the deriving step comprising: generating an offset timestamp value based upon a scheduler clock frequency divided by the allowed cell rate value; adding the offset timestamp value to a base timestamp value to produce the new timestamp value; and after the deriving step, repeating the sorting, comparing, and issuing steps.
Claim 6
Dependent Claim
20 words
The method of claim 3 , wherein the base timestamp value equals the timestamp value of the root channel entry.
Claim 7
Dependent Claim
15 words
The method of claim 3 , wherein the base timestamp value equals the global time.
Claim 8
Dependent Claim
84 words
The method of claim 1 , wherein the sorting step comprises: identifying first and second groups of the plurality of channels, the first group of the plurality of channels having timestamp values that are nearer due than the timestamp values of the second group of the plurality of channels; storing channel entries for the first group of the plurality of channels in a first parameter memory; and storing channel entries for the second group of the plurality of channels in a second parameter memory.
Claim 9
Independent Claim
230 words
A method of scheduling the transmission of packet cells associated with a plurality of communications channels, comprising the steps of: sorting channel entries in a heap memory, the sorting step performed by circuitry in a scheduler integrated circuit, each channel entry comprising a timestamp value associated with each channel, the timestamp value indicating a time at which the transmission of a cell for the associated channel is next due, the sorting step identifying a root channel entry corresponding to the next due channel, and the sorting step comprising: identifying first and second groups of the plurality of channels, the first group of the plurality of channels having timestamp values that are nearer due than the timestamp values of the second group of the plurality of channels; storing channel entries for the first group of the plurality of channels in a first parameter memory implemented in the scheduler integrated circuit; and storing channel entries for the second group of the plurality of channels in a second parameter memory implemented into memory external to the scheduler integrated circuit; comparing the timestamp value of the root channel entry to a global time generated by a reference timer; and responsive to the comparing step determining that the global time has at least reached the timestamp value of the root channel entry, issuing a transmit credit for the channel associated with the root channel entry.
Claim 10
Independent Claim
230 words
A method of scheduling the transmission of packet cells associated with a plurality of communications channels, comprising the steps of: sorting channel entries in a heap memory, the sorting step performed by circuitry in a scheduler integrated circuit, each channel entry comprising a timestamp value associated with each channel, the timestamp value indicating a time at which the transmission of a cell for the associated channel is next due, the sorting step identifying a root channel entry corresponding to the next due channel, and the sorting step comprising: identifying first and second groups of the plurality of channels, the first group of the plurality of channels having timestamp values that are nearer due than the timestamp values of the second group of the plurality of channels; storing channel entries for the first group of the plurality of channels in a first parameter memory implemented in the scheduler integrated circuit; and storing channel entries for the second group of the plurality of channels in a second parameter memory implemented into memory external to the scheduler integrated circuit; comparing the timestamp value of the root channel entry to a global time generated by a reference timer; and responsive to the comparing step determining that the global time has at least reached the timestamp value of the root channel entry, issuing a transmit credit for the channel associated with the root channel entry.
Claim 11
Dependent Claim
59 words
The method of claim 1 , further comprising: after the step of issuing a transmit credit, retrieving an allowed cell rate value for the one of the plurality of channels associated with the root channel entry; deriving a new timestamp value for the channel associated with the root channel entry; and then repeating the sorting, comparing, and issuing steps.
Claim 12
Independent Claim
300 words
A method of scheduling the transmission of packet cells associated with a plurality of communications channels, comprising the steps of: sorting channel entries in a heap memory, each channel entry comprising a timestamp value associated with each channel, the timestamp value indicating a time at which the transmission of a cell for the associated channel is next due, the sorting step identifying a root channel entry corresponding to the next due channel; comparing the timestamp value of the root channel entry to a global time generated by a reference timer; and responsive to the comparing step determining that the global time has at least reached the timestamp value of the root channel entry, issuing a transmit credit for the channel associated with the root channel entry; after the step of issuing a transmit credit, retrieving an allowed cell rate value for the one of the plurality of channels associated with the root channel entry; deriving a new timestamp value for the channel associated with the root channel entry, the deriving step comprising: generating an offset timestamp value based upon a scheduler clock frequency divided by the allowed cell rate value; adding the timestamp value for the channel associated with the root channel entry to the offset timestamp value to derive a future credit time value; comparing the future credit time value with the global time; responsive to the comparing step determining that the future credit time value is later than the global time, setting the new timestamp value to the future credit time value; and responsive to the comparing step determining that the future credit time value is earlier than the global time, adding the offset timestamp value to the global time to generate the new timestamp value; and after the deriving step, repeating the sorting, comparing, and issuing steps.
Claim 13
Independent Claim
300 words
A method of scheduling the transmission of packet cells associated with a plurality of communications channels, comprising the steps of: sorting channel entries in a heap memory, each channel entry comprising a timestamp value associated with each channel, the timestamp value indicating a time at which the transmission of a cell for the associated channel is next due, the sorting step identifying a root channel entry corresponding to the next due channel; comparing the timestamp value of the root channel entry to a global time generated by a reference timer; and responsive to the comparing step determining that the global time has at least reached the timestamp value of the root channel entry, issuing a transmit credit for the channel associated with the root channel entry; after the step of issuing a transmit credit, retrieving an allowed cell rate value for the one of the plurality of channels associated with the root channel entry; deriving a new timestamp value for the channel associated with the root channel entry, the deriving step comprising: generating an offset timestamp value based upon a scheduler clock frequency divided by the allowed cell rate value; adding the timestamp value for the channel associated with the root channel entry to the offset timestamp value to derive a future credit time value; comparing the future credit time value with the global time; responsive to the comparing step determining that the future credit time value is later than the global time, setting the new timestamp value to the future credit time value; and responsive to the comparing step determining that the future credit time value is earlier than the global time, adding the offset timestamp value to the global time to generate the new timestamp value; and after the deriving step, repeating the sorting, comparing, and issuing steps.
Claim 14
Dependent Claim
206 words
A network hub and ATM translator system, comprising: a host controller, having an interface for receiving local communications; and an ATM translator subsystem, comprising: a transceiver interface, coupled to a high data rate communications facility; segmentation and reassembly circuitry, coupled to the transceiver interface and to the host controller; parameter memory, for storing entries associated with each of a plurality of ATM communications channels; and a scheduler, coupled to the parameter memory and to the segmentation and reassembly processor, for scheduling the transmission of packet cells associated with the plurality of ATM communications channels by a sequence of operations, the scheduler comprising: heap sort circuitry for sorting channel entries in the parameter memory, each channel entry comprising a timestamp value associated with each channel, the timestamp value indicating a time at which the transmission of a cell for the associated channel is next due, and for identifying a root channel entry corresponding to the next due channel; a reference timer for generating a global time; a comparator for comparing the timestamp value of the root channel entry to the global time; and source behavior processor circuitry, coupled to the segmentation and reassembly circuitry issuing a transmit credit for the channel associated with the root channel entry.
Claim 15
Dependent Claim
206 words
A network hub and ATM translator system, comprising: a host controller, having an interface for receiving local communications; and an ATM translator subsystem, comprising: a transceiver interface, coupled to a high data rate communications facility; segmentation and reassembly circuitry, coupled to the transceiver interface and to the host controller; parameter memory, for storing entries associated with each of a plurality of ATM communications channels; and a scheduler, coupled to the parameter memory and to the segmentation and reassembly processor, for scheduling the transmission of packet cells associated with the plurality of ATM communications channels by a sequence of operations, the scheduler comprising: heap sort circuitry for sorting channel entries in the parameter memory, each channel entry comprising a timestamp value associated with each channel, the timestamp value indicating a time at which the transmission of a cell for the associated channel is next due, and for identifying a root channel entry corresponding to the next due channel; a reference timer for generating a global time; a comparator for comparing the timestamp value of the root channel entry to the global time; and source behavior processor circuitry, coupled to the segmentation and reassembly circuitry issuing a transmit credit for the channel associated with the root channel entry.
Claim 16
Dependent Claim
16 words
The system of claim 10 , wherein the scheduler is integrated into a single integrated circuit.
Claim 17
Dependent Claim
92 words
The system of claim 11 , wherein the scheduler further comprises: on-chip parameter memory implemented into the same integrated circuit with the scheduler, for storing timestamp values associated with a first group of the plurality of channels; wherein the parameter memory is external to the scheduler integrated circuit, and is for storing timestamp values associated with a second group of the plurality of channels, the first group of the plurality of channels having timestamp values that are nearer due than the timestamp values of the second group of the plurality of channels.
Claim 18
Dependent Claim
67 words
The system of claim 10 , wherein the source behavior processor circuitry is also for retrieving an allowed cell rate value from a parameter memory for the channel associated with the root channel entry after issuing a transmit credit and wherein the scheduler further comprises: circuitry, coupled to the heap sort circuitry, for deriving a new timestamp value for the channel associated with the root channel entry.
Claim 19
Dependent Claim
52 words
The system of claim 10 , wherein the deriving circuitry comprises: a divider for generating an offset timestamp value based upon a scheduler clock frequency divided by the allowed cell rate value; and an adder for adding the offset timestamp value to a base timestamp value to produce the new timestamp value.
Claim 20
Dependent Claim
20 words
The system of claim 14 , wherein the base timestamp value equals the timestamp value of the root channel entry.
Claim 21
Dependent Claim
220 words
The system of claim 14 , wherein the deriving circuitry further comprises: a multiplexer, having a first input for receiving the global time from the reference timer, having a second input for receiving the timestamp value of the root channel entry, having an output coupled to the adder to communicate the base timestamp value thereto, and having a control input for selecting either the global time or the timestamp value of the root channel entry for the base timestamp value; and a multiplexer control function, for generating a select signal applied to the control input of the multiplexer, by performing the operations of: generating an offset timestamp value based upon a scheduler clock frequency divided by the allowed cell rate value; adding the timestamp value for the channel associated with the root channel entry to the offset timestamp value to derive a future credit time value; comparing the future credit time value with the global time; and responsive to the comparing step determining that the future credit time value is later than the global time, setting the new timestamp value to the future credit time value; and responsive to the comparing step determining that the future credit time value is earlier than the global time, adding the offset timestamp value to the global time to generate the new timestamp value.
References Cited (Backward Citations)
US5796735A
Cited
US5917822A
Cited
EP0782303A2
Cited
US5812527A
Cited
WO1997042735A1
Cited
US5926459A
Cited
US6006270A
Cited
US5844890A
Cited
US6028843A
Cited
US6115360A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-03-19 | 2004-09-18 | 2005-03-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-03-19 | 2008-09-18 | 2009-03-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-03-19 | 2012-09-18 | 2013-03-20 | $7700.00 | Window Closed / Lapsed |