Method for scheduling upstream communications

• US 7,333,495 B2
• Filed: 02/15/2001
• Issued: 02/19/2008
• Est. Priority Date: 10/27/1999
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Sala, Dolors, Gummalla, Ajay Chandra V., Protus, Richard, Limb, John O.
• Primary Examiner(s): Pham; Chi
• Assistant Examiner(s): HOANG, THAI D
• Application Number:
  US09/783,404
• Publication Number:
  US 20010053152A1
• Time in Patent Office: 2,560 Days
• Field of Search: 370/389, 370/391, 370/395.21, 3703954-39543, 370420-421, 370/537, 370/538, 370412-418, 370/468
• US Class Current: 370/395.21
• CPC Class Codes: H04L 12/2801 Broadband local area networks
• CPC Class Codes: H04L 12/6418 Hybrid transport
• CPC Class Codes: H04L 2012/6481 Speech, voice
• CPC Class Codes: H04L 2012/6494 Silence suppression
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 41/5022 by giving priorities, e.g. assigning classes of service
• CPC Class Codes: H04L 41/5087 wherein the managed service relates to voice services management of VoIP services H04M7/0081
• CPC Class Codes: H04L 41/509 wherein the managed service relates to media content delivery, e.g. audio, video or TV
• CPC Class Codes: H04L 41/5093 wherein the managed service relates to messaging or chat services
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/245 using preemption
• CPC Class Codes: H04L 47/35 by embedding flow control information in regular packets, e.g. piggybacking
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/60 implementing hierarchical scheduling
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/80 Responding to QoS
• CPC Class Codes: H04L 9/40 : Network security protocols
• CPC Class Codes: H04M 7/006 : Networks other than PSTN/ISDN providing telephone service, e.g. Voice over Internet Protocol (VoIP) , including next generation networks with a packet-switched transport layer H04L65/00 takes precedence; aspects not specific to the type of network H04M3/00; special services in those networks H04M3/42
• CPC Class Codes: H04N 21/2385 : Channel allocation H04N21/266 takes precedence; Bandwidth allocation H04N21/24 takes precedence ; allocation of channels according to the instantaneous demands of the users in time-division multiplex systems H04J3/1682; admission control, resource allocation in open networks H04L12/5692; arrangements for maintenance or administration in data switching networks involving bandwidth and capacity management H04L41/0896; negotiating bandwidth in wireless networks H04W28/16
• CPC Class Codes: H04N 21/42676 : for modulating an analogue carrier signal to encode digital information or demodulating it to decode digital information, e.g. ADSL or cable modem
• CPC Class Codes: H04N 21/437 : Interfacing the upstream path of the transmission network, e.g. for transmitting client requests to a VOD server flow control in data networks H04L47/10; streaming protocols, e.g. RTP or RTCP, H04L65/65; scheduling or organising the servicing of application requests in data packet switching networks H04L67/60
• CPC Class Codes: H04N 21/44209 : Monitoring of downstream path of the transmission network originating from a server, e.g. bandwidth variations of a wireless network arrangements for maintenance or administration in data switching networks involving bandwidth and capacity management H04L41/0896
• CPC Class Codes: H04N 21/6118 : involving cable transmission, e.g. using a cable modem
• CPC Class Codes: H04N 21/6168 : involving cable transmission, e.g. using a cable modem
• CPC Class Codes: H04N 21/6377 : directed to server one-way streaming services wherein the source is controlled by the destination H04L65/613
• CPC Class Codes: H04N 7/17309 : Transmission or handling of upstream communications

Abstract

A system and method is provided for scheduling transmissions from a plurality of services operating over a widely distributed communications network. A headend communications device (such as a cable modem termination system) arbitrates bandwidth among a plurality of cable modems configurable for bi-directional communications. The headend grants a bandwidth region to a specified cable modem or assigns contention regions for a group of cable modems. Each cable modem contains a local scheduler that sends requests for bandwidth according to local policies or rules. Upon receipt of a grant from the headend, the local scheduler selects packets to be transmitted to best serve the needs of the services associated with the cable modem. Accordingly, a service requesting bandwidth may not be the service utilizing the grant corresponding to bandwidth request. Nonetheless, the local scheduler manages bandwidth allocation among its local services such that all requesting services eventually receive bandwidth.

Claims

1. In a distributed communications network having at least one remote node and one or more local nodes, each local node providing one or more services and at least one local node having a local scheduler, a method for managing upstream communications from the local scheduler, comprising the steps of:

(a) sending a request to transmit data related to a requesting service;

(b) receiving a grant specification from a remote node, said grant specification providing authorization to transmit data related to the requesting service;

(c) considering the needs of a plurality of services, said plurality of services including the requesting service and at least one other service;

(d) scheduling packets for said plurality of services in response to said considering step; and

(e) transmitting a burst based on the scheduled packets to the remote node.

2. A method of claim 1, further comprising the step of evaluating the current state of queues for each of said plurality of services.

3. A method of claim 1, further comprising the step of evaluating at least one of throughput and latency to consider the needs of said plurality of services.

4. A method of claim 1, further comprising the step of drawing data from a higher priority queue prior to drawing data from a lower priority queue to implement said scheduling packets.

5. A method of claim 1, further comprising the step of sending a piggyback bandwidth request with the burst.

6. A method of claim 5, further comprising the step of appending said piggyback bandwidth request to the burst.

7. A method of claim 6, further comprising the step of appending said piggyback bandwidth request to a voice packet.

8. A method of claim 5, further comprising the step of sending said piggyback bandwidth request as a message.

9. A method of claim 5, further comprising the step of sending said piggyback bandwidth request in a header frame.

10. A method of claim 1, further comprising the step of sending multiple piggyback bandwidth requests with the burst.