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

• US 6,563,829 B1
• Filed: 03/25/1999
• Issued: 05/13/2003
• Est. Priority Date: 11/15/1995
• Status: Expired due to Fees

• Current Assignee: Com21, Inc., Telesis Technologies Laboratory, 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): Ton, Dang
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US09/276,434
• Time in Patent Office: 1,510 Days
• Field of Search: 370/230, 370/353, 370/355, 370/395, 370/397, 370/414, 370/416, 370/418, 370/431, 370/461, 370/462, 370/465, 370/468, 370/447, 370/395.2, 370/395.21, 370/395.4, 370/395.41, 370/395.42, 370/395.43, 370/395.5, 370/395.7, 370/412
• US Class Current: 370/395.21
• 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 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.

2. The method of claim 1, wherein the request for authorization to transmit packets specifies packets of a fixed size.

3. The method of claim 1, wherein the request for authorization to transmit packets specifies packets of a variable size.

4. 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.

5. 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.

6. The method of claim 1, further comprising:

sorting said transmission scheduling list in accordance with a lexicographic sort.

7. 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.

9. 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.

10. 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.

8. 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.