Method for providing integrated packet services over a shared-media network

• US 5,917,822 A
• Filed: 04/12/1996
• Issued: 06/29/1999
• Est. Priority Date: 11/15/1995
• Status: Expired due to Term

• Current Assignee: Arris International, Inc. (CommScope Holding Company, Inc.), Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Com21, Inc., Telesis Technologies Laboratory, Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Laubach, Mark E., Lyles, Joseph Bryan, Quinn, Scott M.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US08/631,507
• Time in Patent Office: 1,173 Days
• Field of Search: 370/389, 370/342, 370/397, 370/399, 370/404, 370/412, 370/431, 370/443, 370/449, 370/468, 370/395, 348/7, 348/12, 348/13, 348/309
• US Class Current: 370/395.4
• CPC Class Codes: H04L 12/2801 Broadband local area networks
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5605 Fibre
• CPC Class Codes: H04L 2012/5606 Metallic
• CPC Class Codes: H04L 2012/5615 Network termination, e.g. NT1, NT2, PBX
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions
• CPC Class Codes: H04L 2012/5638 Services, e.g. multimedia, GOS, QOS
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections
• CPC Class Codes: H04Q 2213/13056 Routines, finite state machines
• CPC Class Codes: H04Q 2213/13103 Memory
• CPC Class Codes: H04Q 2213/13166 Fault prevention
• CPC Class Codes: H04Q 2213/13251 Restricted service, class of service
• CPC Class Codes: H04Q 2213/13322 Integrated circuits
• CPC Class Codes: H04Q 2213/13349 Network management

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.

Claims

1. A method for selectively authorizing transmission of packet-based communications signals in a hybrid fiber-coax network, said hybrid fiber-coax network having a bandwidth allocation unit and a plurality of terminal equipment units, wherein each one of said plurality of terminal equipment units are operatively coupled to a head-end controller co-located with the bandwidth allocation unit, the method, executed by the bandwidth allocation unit, comprising:

(a) receiving a transmission authorization request signal from an identified terminal equipment, said transmission authorization request signal being associated with a requested transmission;

(b) generating a virtual scheduling time for the requested transmission, based on (1) the time of arrival of said transmission authorization request signal, (2) a class of service associated with the requested transmission, and (3) a virtual scheduling time of a previous transmission authorization request made on behalf of the identified terminal equipment;

(c) adding to a transmission scheduling list an entry corresponding to the requested transmission, said entry encoding a value derived from said virtual scheduling time;

(d) sorting the transmission scheduling list in accordance with a lexicographic sort; and

(e) sending a transmission authorization signal to the identified terminal equipment in accordance with the position of said virtual scheduling time in the sorted transmission scheduling list.

2. The method of claim 1, wherein:

(i) each entry in the transmission scheduling list has a class-of-service indicator; and

(ii) said entries in the transmission scheduling list are sorted first by class of service indicators and second by virtual scheduling times.

3. The method of claim 1, wherein the transmission authorization request signal is generated by the head-end controller as a result of previous negotiation or provisioning.

4. The method of claim 1, wherein said virtual scheduling time is generated by a rate-based queuing process.

5. The method of claim 4, wherein the rate-based queuing process is a weighted fair queuing process.

6. The method of claim 1, wherein said virtual scheduling time is associated with a reserve traffic class and is generated by a virtual clock algorithm.

7. The method of claim 2, wherein:

(i) said transmission authorization request signal is one of a series of transmission authorization request signals generated by the identified terminal equipment for authorization to transmit packets of a fixed size;

(ii) said head-end controller maintains a representation of a queue for each traffic class for said terminal equipment in the form of a counter of the aggregate number of requests received but not yet granted for the identified terminal equipment; and

(iii) only one virtual scheduling time per terminal equipment is kept in said transmission scheduling list.

19. A 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 a method in accordance with any of claims 1 through 18.

20. A program storage device encoding a machine-readable copy of a program of instructions, said program of instructions being executable by a bandwidth allocation unit for performing a method in accordance with any of claims 1 through 18.

8. A method of selectively authorizing transmission of packet-based communications signals on a shared-media packet based network, said packet based network having a centralized bandwidth allocation unit and a network access unit wherein said network access unit is operatively coupled to said bandwidth allocation unit, the method, executed by the bandwidth allocation unit, comprising:

(a) receiving a transmission authorization request signal from the network access unit, said transmission authorization request signal being associated with a requested transmission;

(b) generating a virtual scheduling time for the requested transmission based on (1) a time of arrival for said transmission authorization request signal, (2) a class of service associated with said requested transmission, and (3) a virtual scheduling time of a previous transmission authorization request made by or on behalf of the network access unit;

(c) adding to a transmission scheduling list an entry corresponding to said transmission authorization request signal, said entry encoding a value derived from said virtual scheduling time;

(d) sorting said transmission scheduling list in accordance with a lexicographic sort; and

(e) transmitting a transmission authorization signal to the network access unit in accordance with the position of said virtual scheduling time in the transmission scheduling list.

9. The method of claim 8, wherein:

(i) each entry in the transmission scheduling list has a class-of-service indicator; and

(ii) said entries in the transmission scheduling list are sorted first by class of service indicators and second by virtual scheduling times.

10. The method of claim 8, wherein the transmission authorization request signal is generated by the bandwidth allocation unit as a result of previous negotiation or provisioning.

11. The method of claim 8, wherein said virtual scheduling time is generated by a rate-based queuing process.

12. The method of claim 11, wherein said rate-based queuing process is a weighted fair queuing process.

13. The method of claim 12, wherein said virtual scheduling time is associated with a reserve traffic class and is generated by a virtual clock algorithm.

14. The method of claim 11, wherein

(i) said transmission authorization request signal is one of a plurality of transmission authorization request signals generated by the network access unit for authorization to transmit packets of a fixed size;

(ii) said bandwidth allocation unit maintains a representation of a queue for each traffic class of the network access unit in the form of a counter of the aggregate number of requests received but not yet granted for said network access unit; and

(iii) only one virtual scheduling time per network access unit is kept in said transmission scheduling list.

15. 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 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, said transmission authorization request signal being associated with a requested transmission;

(b) adding to a transmission scheduling list an entry corresponding to said requested transmission;

(c) transmitting a transmission authorization signal to one of said plurality of network access units in accordance with a round-robin scheduling of entries in said transmission scheduling list;

(d) wherein;

(i) the transmission authorization request signal is one of a plurality of transmission authorization request signals generated by a specified network access unit for authorization to transmit packets of a fixed size;

(ii) the bandwidth allocation unit maintains a representation of a queue for each traffic class of each of said plurality of network access units in the form of a counter of the aggregate number of requests received but not yet granted for each network access unit; and

(iii) only one virtual scheduling time per network access unit is kept in said transmission scheduling list.

16. The method of claim 15, wherein the transmission authorization request signal is generated by the bandwidth allocation unit as a result of previous negotiation between the bandwidth allocation unit and said one of said plurality of network access units.

17. A method for selectively authorizing transmission of packet-based communications signals in a cable television network, said network having a bandwidth allocation unit and a plurality of cable modems, wherein each one of said plurality of cable modems is operatively coupled to a head-end controller co-located with the bandwidth allocation unit, the method, executed by the bandwidth allocation unit, comprising:

(a) receiving a transmission authorization request signal from an identified cable modem, said transmission authorization request signal being associated with a requested transmission;

(b) using a weighted fair queuing algorithm to generate a virtual scheduling time for the requested transmission, based on (1) the time of arrival of said transmission authorization request signal, (2) a class of service associated with the requested transmission, and (3) a virtual scheduling time of a previous transmission authorization request made on behalf of the identified cable modem;

(c) adding to a transmission scheduling list an entry corresponding to the requested transmission, said entry encoding a value derived from said virtual scheduling time;

(d) sorting the transmission scheduling list in accordance with a lexicographic sort; and

(e) sending a transmission authorization signal to the identified cable modem in accordance with the position of said virtual scheduling time in the sorted transmission scheduling list.

18. A method for selectively authorizing transmission of packet-based communications signals in a cable television network, said network having a bandwidth allocation unit and a plurality of set-top boxes, wherein each one of said plurality of set-top boxes is operatively coupled to a head-end controller co-located with the bandwidth allocation unit, the method, executed by the bandwidth allocation unit, comprising:

(a) receiving a transmission authorization request signal from an identified set-top box, said transmission authorization request signal being associated with a requested transmission;

(b) using a weighted fair queuing algorithm to generate a virtual scheduling time for the requested transmission, based on (1) the time of arrival of said transmission authorization request signal, (2) a class of service associated with the requested transmission, and (3) a virtual scheduling time of a previous transmission authorization request made on behalf of the identified set-top box;

(c) adding to a transmission scheduling list an entry corresponding to the requested transmission, said entry encoding a value derived from said virtual scheduling time;

(d) sorting the transmission scheduling list in accordance with a lexicographic sort; and

(e) sending a transmission authorization signal to the identified set-top box in accordance with the position of said virtual scheduling time in the sorted transmission scheduling list.