Patent US6563829B1 successfully refreshed from Google Patents.
US6563829B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for providing integrated packet services over a shared-media network
Assignee: Xerox Corp
•
Filing: 1999-03-25
•
Granted: 2003-05-13
•
Expires: 2019-03-25
Abstract
Abstract A method in accordance with the invention allocates bandwidth, fairly and dynamically, in a shared-media packet switched network to accommodate both elastic and inelastic applications. The method, executed by or in a head-end controller, allocates bandwidth transmission slots, converting requests for bandwidth into virtual scheduling times for granting access to the shared media. The method can use a weighted fair queuing algorithm or a virtual clock algorithm to generate a sequence of upstream slot/transmission assignment grants. The method supports multiple quality of service (QoS) classes via mechanisms which give highest priority to the service class with the most stringent QoS requirements.
Inventors
- 👤 Joseph Bryan Lyles
- 👤 Mark E. Laubach
- 👤 Scott M. Quinn
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 08:35
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04L12/28; H04L12/2801; H04L47/00; H04L47/10; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L2012/5603; H04L2012/5604; H04L2012/5605; H04L2012/5606; H04L2012/5614; H04L2012/5615; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5636; H04L2012/5638; H04L2012/5678; H04L2012/5679; H04Q2213/00; H04Q2213/13056; H04Q2213/13103; H04Q2213/13166; H04Q2213/13251; H04Q2213/13322; H04Q2213/13349
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
175 words
A method for selectively authorizing transmission of packet-based communications signals in a shared-media packet based network, said shared-media packet based network having a centralized bandwidth allocation unit, said bandwidth allocation unit capable of accommodating elastic, inelastic, and burst transmission authorization requests, and a plurality of network access units wherein each of said plurality of network access units are operatively coupled to the bandwidth allocation unit, the method, executed by the bandwidth allocation unit, comprising: (a) receiving a transmission authorization request signal from at least one of said network access units, said transmission authorization request signal being associated with a requested transmission by said network access unit; (b) adding to a transmission scheduling list an entry corresponding to said requested transmission; and (c) transmitting a transmission authorization signal to said network access unit in accordance with a weighted fair queuing scheduling of entries in said transmission scheduling list; and (d) wherein the transmission authorization request signal is one of plurality of transmission authorization request signals generated by said network access unit for authorization to transmit packets.
Claim 2
Independent Claim
175 words
A method for selectively authorizing transmission of packet-based communications signals in a shared-media packet based network, said shared-media packet based network having a centralized bandwidth allocation unit, said bandwidth allocation unit capable of accommodating elastic, inelastic, and burst transmission authorization requests, and a plurality of network access units wherein each of said plurality of network access units are operatively coupled to the bandwidth allocation unit, the method, executed by the bandwidth allocation unit, comprising: (a) receiving a transmission authorization request signal from at least one of said network access units, said transmission authorization request signal being associated with a requested transmission by said network access unit; (b) adding to a transmission scheduling list an entry corresponding to said requested transmission; and (c) transmitting a transmission authorization signal to said network access unit in accordance with a weighted fair queuing scheduling of entries in said transmission scheduling list; and (d) wherein the transmission authorization request signal is one of plurality of transmission authorization request signals generated by said network access unit for authorization to transmit packets.
Claim 3
Dependent Claim
20 words
The method of claim 1 , wherein the request for authorization to transmit packets specifies packets of a fixed size.
Claim 4
Dependent Claim
20 words
The method of claim 1 , wherein the request for authorization to transmit packets specifies packets of a variable size.
Claim 5
Dependent Claim
27 words
The method of claim 1 , wherein only one virtual scheduling time for each queue in each network access unit is kept in said transmission scheduling list.
Claim 6
Dependent Claim
31 words
The method of claim 1 , wherein the bandwidth allocation unit maintains a representation of a queue for each traffic less class of each of said plurality of network access units.
Claim 7
Dependent Claim
19 words
The method of claim 1 , further comprising: sorting said transmission scheduling list in accordance with a lexicographic sort.
Claim 8
Dependent Claim
67 words
The method of claim 1 , further comprising in place of said paragraph (c): (c) generating a virtual scheduling time for said requested transmission, based on: (1) a time of arrival of said transmission authorization request; (2) a class of service associated with said transmission authorization request; and (3) a virtual scheduling time of a previous transmission authorization request made on behalf of said network access unit.
Claim 9
Independent Claim
186 words
A method for selectively authorizing transmission of packet-based communications signals in a shared-media packet based network, said shared-media packet based network having a centralized bandwidth allocation unit, said bandwidth allocation unit capable of accommodating elastic, inelastic, and burst transmission authorization requests, and a plurality of network access units wherein each of said plurality of network access units are operatively coupled to the bandwidth allocation unit, the method, executed by the bandwidth allocation unit, comprising: (a) receiving a transmission authorization request signal that is one of a plurality of transmission authorization request signals generated by one of said network access units for authorization to transmit packets, said transmission authorization request signal being associated with a requested transmission by said network access unit; (b) adding to a transmission scheduling list an entry corresponding to said requested transmission; (c) transmitting a transmission authorization signal to said network access unit in accordance with a weighted fair queuing scheduling of entries in said transmission scheduling list; and (d) wherein the bandwidth allocation unit maintains a representation of a queue for each traffic class of each said plurality of network access units.
Claim 10
Independent Claim
186 words
A method for selectively authorizing transmission of packet-based communications signals in a shared-media packet based network, said shared-media packet based network having a centralized bandwidth allocation unit, said bandwidth allocation unit capable of accommodating elastic, inelastic, and burst transmission authorization requests, and a plurality of network access units wherein each of said plurality of network access units are operatively coupled to the bandwidth allocation unit, the method, executed by the bandwidth allocation unit, comprising: (a) receiving a transmission authorization request signal that is one of a plurality of transmission authorization request signals generated by one of said network access units for authorization to transmit packets, said transmission authorization request signal being associated with a requested transmission by said network access unit; (b) adding to a transmission scheduling list an entry corresponding to said requested transmission; (c) transmitting a transmission authorization signal to said network access unit in accordance with a weighted fair queuing scheduling of entries in said transmission scheduling list; and (d) wherein the bandwidth allocation unit maintains a representation of a queue for each traffic class of each said plurality of network access units.
Claim 11
Dependent Claim
41 words
The bandwidth allocation unit comprising (a) a processor and (b) a program storage device that is readable by the processor and that encodes a program of instructions for performing said method in accordance with any of claims 1 through 8 .
Claim 12
Dependent Claim
38 words
The program storage device encoding a machine-readable copy of a program of instructions, said program of instructions being executable by said bandwidth allocation unit for performing a method in accordance with any of claims 1 through 8 .
References Cited (Backward Citations)
US5163046A
Cited
US5291481A
Cited
US5313454A
Cited
US5463620A
Cited
US5425027A
Cited
US5699532A
Cited
US5579312A
Cited
US5579302A
Cited
US5559999A
Cited
US5572517A
Cited
US5544161A
Cited
US5586121A
Cited
US5613191A
Cited
US5684791A
Cited
US5917822A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-05-12 | 2006-11-11 | 2007-05-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-05-12 | 2010-11-11 | 2011-05-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-05-12 | 2014-11-11 | 2015-05-13 | $7700.00 | Window Closed / Lapsed |