Patent US2196399A successfully refreshed from Google Patents.
Patent US5579302A successfully refreshed from Google Patents.
US5579302A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for regulating virtual-channel cell transmission
Assignee: Hewlett Packard Development Co LP
•
Filing: 1995-07-05
•
Granted: 1996-11-26
•
Expires: 2015-07-05
Abstract
Abstract In order to schedule the transmission onto a link of cells associated with different virtual channels, a transmission schedule is set up associating virtual channels with respective transmission time slots. Each time a cell is sent, the corresponding virtual channel is re-allocated to a time slot that is offset from the current one by an amount dependent on the desired rate of transmission. This desired rate is specified for each virtual channel in a corresponding transmission rate indicator including a fixed integer part, a fixed fractional part, and a variable accumulation part. The fixed parts of the indicator define the desired rate whilst the accumulation part is used in calculating each successive offset. More particularly, to determine the offset of the time slot next to be allocated to a virtual channel, the three parts of the corresponding transmission rate indicator are added up and the integer component of the result is used as the offset, the fractional remainder being stored back to the accumulation part of the transmission rate indicator. This arrangement permits a fine control to be achieved on the average transmission rate. A similar approach can be used to control the rate of credit generation in systems where transmit credits are used to regulate cell transmission.
Inventors
- 👤 David Banks
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 10:25
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/5629; H04L2012/5631; H04L2012/5632; H04L2012/5636; H04L2012/5678; H04L2012/5679
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
148 words
A method of regulating the transmission of cells onto a link, the cells being associated with a plurality of different virtual channels, the method comprising the steps of: (a) providing for each virtual channel a control data item having a fixed integer part, a fixed fractional part, and a variable accumulation part; (b) periodically determining for each virtual channel a control number, this determination involving: adding together said three parts of the control data item for the channel concerned to produce a result with an integer component and a fractional remainder; using the integer component of the result to set said control number; and storing said fractional remainder as said accumulation part of said control data item for the virtual channel concerned; and (c) regulating cell transmission for the virtual channel concerned according to the value of said control number determined in step (b) for the virtual channel.
Claim 2
Independent Claim
148 words
A method of regulating the transmission of cells onto a link, the cells being associated with a plurality of different virtual channels, the method comprising the steps of: (a) providing for each virtual channel a control data item having a fixed integer part, a fixed fractional part, and a variable accumulation part; (b) periodically determining for each virtual channel a control number, this determination involving: adding together said three parts of the control data item for the channel concerned to produce a result with an integer component and a fractional remainder; using the integer component of the result to set said control number; and storing said fractional remainder as said accumulation part of said control data item for the virtual channel concerned; and (c) regulating cell transmission for the virtual channel concerned according to the value of said control number determined in step (b) for the virtual channel.
Claim 3
Dependent Claim
106 words
A method according to claim 1, wherein said cells are transmitted onto the link in respective transmission time slots according to a transmission schedule associating transmission time slots and virtual channels; step (b) being performed for a particular virtual channel each time a cell is transmittted onto the link in respect of that channel, and the control number thereby determined being used in step (c) to update the transmission schedule by seeking to set as the next time slot for transmitting a cell for the virtual channel concerned, a time slot offset from the current one by a number of slots corresponding to said control number.
Claim 4
Dependent Claim
48 words
A method according to claim 1, wherein the transmission of cells for a particular virtual channel is dependent on the availability of transmit credits for that channel, said control number determined for each channel being used to regulate the rate at which credits are generated for the channel.
Claim 5
Dependent Claim
50 words
A method according to claim 3, wherein for each channel, each time step (b) is performed, a fixed credit increment is effected for the virtual channel concerned, said control number determined in step (b) being used to determine when step (b) is next to be performed for that virtual channel.
Claim 6
Dependent Claim
35 words
A method according to claim 3, wherein for each channel, step (b) is carried out at regular intervals, said control number determined being used to determine a size of credit increment for the channel concerned.
Claim 7
Independent Claim
250 words
A method of controlling the rate of transmission of cells onto a link, the cells being associated with a plurality of different virtual channels and being transmitted onto the link in respective transmission time slots according to a transmission schedule associating transmission time slots and virtual channels; the method comprising the steps of: (a) providing for each virtual channel a transmission rate indicator having a fixed integer part, a fixed fractional part, and a variable accumulation part; (b) each time a cell is transmitted on the link in respect of a particular virtual channel according to said transmission schedule, determining for that virtual channel, at least in the case that another cell is available for sending on that channel, a desired next time slot for transmitting a cell for the channel, said desired next time slot being determined in terms of its offset, in slots, from the current time slot, this determination involving: adding together said three parts of the transmission rate indicator for the channel concerned to produce a result with an integer component and a fractional remainder; using the integer component of the result as said offset; and storing said fractional remainder as said accumulation part of said transmission rate indicator for the virtual channel concerned; and (c) updating the transmission schedule by using the offset determined in step (b), in determining the next time slot in which a cell is to be transmitted for the virtual channel concerned, and then associating that time slot with that channel.
Claim 8
Independent Claim
250 words
A method of controlling the rate of transmission of cells onto a link, the cells being associated with a plurality of different virtual channels and being transmitted onto the link in respective transmission time slots according to a transmission schedule associating transmission time slots and virtual channels; the method comprising the steps of: (a) providing for each virtual channel a transmission rate indicator having a fixed integer part, a fixed fractional part, and a variable accumulation part; (b) each time a cell is transmitted on the link in respect of a particular virtual channel according to said transmission schedule, determining for that virtual channel, at least in the case that another cell is available for sending on that channel, a desired next time slot for transmitting a cell for the channel, said desired next time slot being determined in terms of its offset, in slots, from the current time slot, this determination involving: adding together said three parts of the transmission rate indicator for the channel concerned to produce a result with an integer component and a fractional remainder; using the integer component of the result as said offset; and storing said fractional remainder as said accumulation part of said transmission rate indicator for the virtual channel concerned; and (c) updating the transmission schedule by using the offset determined in step (b), in determining the next time slot in which a cell is to be transmitted for the virtual channel concerned, and then associating that time slot with that channel.
Claim 9
Dependent Claim
30 words
A method according to claim 6, wherein said integer and fractional parts of each said transmission rate indicator are directly stored as numbers representing whole and partial time slots respectively.
Claim 10
Dependent Claim
52 words
A method according to claim 6, wherein the integer and fractional parts of each said transmission rate indicator are stored jointly in the form of a number representing the transmission rate it is desired to achieve, this number being converted into units and fractions of said time slots when determining said offset.
Claim 11
Dependent Claim
76 words
A method according to claim 6, wherein said virtual channels are assigned respective priorities and in step (c), in the event of the slot indicated by said offset being already associated with another virtual channel, a conflict resolution procedure is carried out based on the relative priorities of the channels concerned, the higher priority channel ending up being associated with that slot and the lower priority channel being thereafter associated with the first subsequent slot available.
Claim 12
Independent Claim
230 words
A method of controlling the rate of transmit credit generation in a system in which cells associated with a plurality of different virtual channels are transmitted onto a link in respective time slots, the transmission of cells for a particular virtual channel being dependent on the availability of transmit credits for that channel; the method comprising the steps of: (a) providing for each virtual channel a credit-generation rate indicator having a fixed integer part, a fixed fractional part, and a variable accumulation part; (b) maintaining a list having entry slots for storing identifiers of the virtual channels to which credit is to be allocated; and (c) advancing through said list at a predetermined slot rate and each time a said identifier is encountered, increasing the transmit credit level of the corresponding virtual channel and reinserting said identifier in the list at a forward offset determined according to the following sub-steps: adding together said three parts of the credit-generation rate indicator for the channel concerned to produce a result with an integer component and a fractional remainder; using the integer component of the result to set said offset; and storing said fractional remainder as said accumulation part of said credit-generation rate indicator for the virtual channel concerned; a conflict resolution procedure being carried out in the event that the position in said list indicated by said forward offset is already occupied.
Claim 13
Independent Claim
230 words
A method of controlling the rate of transmit credit generation in a system in which cells associated with a plurality of different virtual channels are transmitted onto a link in respective time slots, the transmission of cells for a particular virtual channel being dependent on the availability of transmit credits for that channel; the method comprising the steps of: (a) providing for each virtual channel a credit-generation rate indicator having a fixed integer part, a fixed fractional part, and a variable accumulation part; (b) maintaining a list having entry slots for storing identifiers of the virtual channels to which credit is to be allocated; and (c) advancing through said list at a predetermined slot rate and each time a said identifier is encountered, increasing the transmit credit level of the corresponding virtual channel and reinserting said identifier in the list at a forward offset determined according to the following sub-steps: adding together said three parts of the credit-generation rate indicator for the channel concerned to produce a result with an integer component and a fractional remainder; using the integer component of the result to set said offset; and storing said fractional remainder as said accumulation part of said credit-generation rate indicator for the virtual channel concerned; a conflict resolution procedure being carried out in the event that the position in said list indicated by said forward offset is already occupied.
Claim 14
Independent Claim
170 words
A method of controlling the rate of transmit credit generation in a system in which cells associated with a plurality of different virtual channels are transmitted onto a link in respective time slots, the transmission of cells for a particular virtual channel being dependent on the availability of transmit credits for that channel; the method comprising the steps of: (a) providing for each virtual channel a credit-increment size indicator having a fixed integer part, a fixed fractional part, and a variable accumulation part; and (b) at regular intervals, incrementing the transmit credit level of each virtual channel by a respective increment amount determined for that incrementing operation according to the following sub-steps: adding together said three parts of the credit-increment size indicator for the channel concerned to produce a result with an integer component and a fractional remainder; using the integer component of the result to set said increment amount; and storing said fractional remainder as said accumulation part of the 1 credit-increment size indicator for the virtual channel concerned.
Claim 15
Independent Claim
170 words
A method of controlling the rate of transmit credit generation in a system in which cells associated with a plurality of different virtual channels are transmitted onto a link in respective time slots, the transmission of cells for a particular virtual channel being dependent on the availability of transmit credits for that channel; the method comprising the steps of: (a) providing for each virtual channel a credit-increment size indicator having a fixed integer part, a fixed fractional part, and a variable accumulation part; and (b) at regular intervals, incrementing the transmit credit level of each virtual channel by a respective increment amount determined for that incrementing operation according to the following sub-steps: adding together said three parts of the credit-increment size indicator for the channel concerned to produce a result with an integer component and a fractional remainder; using the integer component of the result to set said increment amount; and storing said fractional remainder as said accumulation part of the 1 credit-increment size indicator for the virtual channel concerned.
Claim 16
Dependent Claim
296 words
Apparatus for transmitting a stream of cells onto a link, the cells being associated with a plurality of different virtual channels each of which is identified in the apparatus by a respective virtual-channel identifier (VCN); the apparatus including a scheduler for scheduling the transmission of cells of each virtual channel, said scheduler comprising: storage means for storing for each virtual channel a transmission rate indicator having a fixed integer part, a fixed fractional part, and a variable accumulation part; list means for maintaining a list having a number of entry slots each capable of storing a single VCN, the list containing the VCNs of virtual channels with cells to transmit; control means for advancing through the list slot by slot and, if a VCN is found in the current slot of interest, responding thereto by transmitting a cell of the corresponding virtual channel, the control means being further operative to remove the VCN, if any, in the current slot of interest, and to re-insert the VCN in a slot offset ahead of the current slot by an predetermined offset amount, the control means including determination means for determining said offset amount, said determination means comprising: means for adding together said three parts of the transmission rate indicator for the channel concerned to produce a result with an integer component and a fractional remainder, means for setting said offset amount in dependence on the integer component of the result, and means for storing said fractional remainder back into said storage means as said accumulation part of said transmission rate indicator for the virtual channel concerned; the control means further including conflict resolution means for resolving conflicts arising from the slot that is offset from the current one by said predetermined offset, being already occupied by a VCN.
Claim 17
Dependent Claim
296 words
Apparatus for transmitting a stream of cells onto a link, the cells being associated with a plurality of different virtual channels each of which is identified in the apparatus by a respective virtual-channel identifier (VCN); the apparatus including a scheduler for scheduling the transmission of cells of each virtual channel, said scheduler comprising: storage means for storing for each virtual channel a transmission rate indicator having a fixed integer part, a fixed fractional part, and a variable accumulation part; list means for maintaining a list having a number of entry slots each capable of storing a single VCN, the list containing the VCNs of virtual channels with cells to transmit; control means for advancing through the list slot by slot and, if a VCN is found in the current slot of interest, responding thereto by transmitting a cell of the corresponding virtual channel, the control means being further operative to remove the VCN, if any, in the current slot of interest, and to re-insert the VCN in a slot offset ahead of the current slot by an predetermined offset amount, the control means including determination means for determining said offset amount, said determination means comprising: means for adding together said three parts of the transmission rate indicator for the channel concerned to produce a result with an integer component and a fractional remainder, means for setting said offset amount in dependence on the integer component of the result, and means for storing said fractional remainder back into said storage means as said accumulation part of said transmission rate indicator for the virtual channel concerned; the control means further including conflict resolution means for resolving conflicts arising from the slot that is offset from the current one by said predetermined offset, being already occupied by a VCN.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-11-26 | 2000-05-27 | 2000-11-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-11-26 | 2004-05-27 | 2004-11-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-11-26 | 2008-05-27 | 2008-11-26 | $7700.00 | Window Closed / Lapsed |