Scheduling for links having changing parameters

• US 7,139,251 B1
• Filed: 04/09/2002
• Issued: 11/21/2006
• Est. Priority Date: 05/29/2001
• Status: Expired due to Fees

• Current Assignee: Monument Bank of Intellectual Property, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Aperto Networks
• Inventors: Varma, Subir
• Primary Examiner(s): Ngo, Ricky Q.
• Assistant Examiner(s): Shew, John
• Application Number:
  US10/120,209
• Time in Patent Office: 1,687 Days
• Field of Search: 370/252, 370276-296, 370/328, 370/329, 370/337, 370/347, 370/437, 370/444, 370/455, 370/458, 455/422.1, 455/435.3, 455/452.2, 455/507, 455/509, 455/512, 455/515, 455/517
• US Class Current: 370/280
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/527 Quantum based scheduling, e.g. credit or deficit based scheduling or token bank
• CPC Class Codes: H04L 47/566 Deadline varies as a function of time spent in the queue
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: H04W 28/02 Traffic management, e.g. flow control or congestion control
• CPC Class Codes: H04W 72/12 Wireless traffic scheduling
• CPC Class Codes: H04W 72/569 of the traffic information
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

The invention provides a method and system for scheduling for links having changing parameters. The method and system for scheduling for links having changing parameters is responsive to variations in communication capacity of communication links, such as wireless communication links in a wireless communication system. A BSC communicates with a plurality of CPE, including dynamically varying communication parameters for each CPE and substantially simultaneously scheduling traffic for each such CPE in response to those varying communication parameters. The BSC can schedule communication with each individual CPE in response to both (1) requested communication bandwidth and (2) varying communication capacity of the communication link between the BSC and that individual CPE. In a preferred embodiment, the BSC communicates with each CPE during a TDD frame. Sequences of such frames can each have differing communication parameters and can each be separately processed by the scheduling technique.

Claims

1. A method of managing time division duplexing across plural channels, including the steps of:

establishing a communication session between two or more stations using a duplex protocol, said stations including some combination of customer premises equipment and at least one base station controller each having a system identification code (SID);

defining one or more classes of service for data flows to and from each one of said stations, whereby said classes include (1) a guaranteed transfer rate, and (2) a best efforts transfer rate;

assigning a priority for transmission of data based on some combination of said classes of service and a data time-stamp, said time-stamp indicative of the age of said data; and

scheduling data for transmission based on said priority;

wherein said step of scheduling further includes the steps of

generating different classes of upstream and down stream data flows, said data flows including class of service and quality of service parameters;

selecting data for transmission based on the variable symbol rates and constellation types of said customer premises equipment; and

maximizing transmission of each time division duplex frame at the physical wireless and media access control levels.

2. The method of claim 1, wherein said scheduling maximizes the payload for each time division duplex frame.

3. The method of claim 1, wherein said two or more stations are in wireless communication with each other.

4. The method of claim 1, wherein said step of generating further includes the steps of

constructing a downstream map, wherein all wireless payload data units in a guaranteed transfer rate class of service that have packets waiting are scheduled for transmission;

determining whether any space remains in said time division duplex frame for additional data, said space being potentially available as a result of an under-used guaranteed transfer rate assigned to a particular SID; and

choosing the data to fill said space.

5. The method of claim 4, wherein said step of choosing includes the step of determining priority of transmission based on said time-stamp and said class of service of a packet.

6. The method of claim 4, wherein priority of transmission is given to said guaranteed transfer rate class.

7. The method of claim 1, wherein said step of generating further includes the steps of

constructing an upstream map, wherein all wireless payload data units in one or more identified classes that have packets waiting are scheduled for transmission;

determining whether any space remains in said time division duplex frame for additional data, said space being potentially available as a result of an under-used guaranteed transfer rate assigned to a particular SID; and

choosing data to fill said space.

8. The method of claim 7, wherein said step of choosing includes the step of determining priority based on some combination of said time-stamp and said class of service of a said packet.

9. The method of claim 1, wherein said step of maximizing includes the steps of

selecting the position of data within a time division duplex frame such that co-channel interference within a communication cell is minimized;

utilizing unused portions of guaranteed bandwidth for other data to be transmitted;

adjusting operation dynamically to account for wireless payload data unit errors and acknowledgment requests;

compensating for wireless related channel impairments; and

integrating media access control messages within a time division duplex frame structure.

10. A base station controller communicating with at least one customer premises equipment over a communication link, said base station controller comprising a transceiver and a controller that performs the steps of:

establishing a communication session between two or more stations using a duplex protocol, said stations including some combination of customer premises equipment and said base station controller, wherein each said customer premises equipment has an associated system identification code (SID);

defining one or more classes of service for data flows to and from each one of said stations, whereby said classes include (1) a guaranteed transfer rate, and (2) a best efforts transfer rate;

assigning a priority for transmission of data based on some combination of said classes of service and a data time-stamp, said time-stamp indicative of the age of said data; and

scheduling data for transmission based on said priority;

wherein said step of scheduling includes performing the steps of

generating different classes of upstream and down stream data flows, said data flows including class of service and quality of service parameters;

selecting data for transmission based on the variable symbol rates and constellation types of said customer premises equipment; and

maximizing transmission of each time division duplex frame at the physical wireless and media access control levels.

11. The base station controller of claim 10, wherein said scheduling maximizes the payload for each time division duplex frame.

12. The base station controller of claim 10, wherein said two or more stations are in wireless communication with each other.

13. The base station controller of claim 10, wherein said step of generating further includes the steps of

constructing a downstream map, wherein all wireless payload data units in a guaranteed transfer rate class of service that have packets waiting are scheduled for transmission;

determining whether any space remains in said time division duplex frame for additional data, said space being potentially available as a result of an under-used guaranteed transfer rate assigned to a particular SID; and

choosing the data to fill said space.

14. The base station controller of claim 13, wherein said step of choosing includes the step of determining priority of transmission based on said time-stamp and said class of service of a packet.

15. The base station controller of claim 13, wherein priority of transmission is given to said guaranteed transfer rate class.

16. The base station controller of claim 10, wherein said step of generating further includes the steps of

constructing an upstream map, wherein all wireless payload data units in one or more identified classes that have packets waiting are scheduled for transmission;

determining whether any space remains in said time division duplex frame for additional data, said space being potentially available as a result of an under-used guaranteed transfer rate assigned to a particular SID; and

choosing data to fill said space.

17. The base station controller of claim 16, wherein said step of choosing includes the step of determining priority based on some combination of said time-stamp and said class of service of a packet.

26. The base station controller of claim 10, wherein said step of maximizing includes the steps of

selecting the position of data within a time division duplex frame such that co-channel interference within a communication cell is minimized;

utilizing unused portions of guaranteed bandwidth for other data to be transmitted;

adjusting operation dynamically to account for wireless payload data unit errors and acknowledgment requests;

compensating for wireless related channel impairments; and

integrating media access control messages within a time division duplex frame structure.

18. A computer-readable memory storing information including computer-executable instructions, said instructions executed by a processor to manage time division duplexing across plural channels, the instructions comprising:

establishing a communication session between two or more stations using a duplex protocol, said stations including some combination of customer premises equipment and at least one base station controller each having a system identification code (SID);

defining one or more classes of service for data flows to and from each one of said stations, whereby said classes include (1) a guaranteed transfer rate, and (2) a best efforts transfer rate;

assigning a priority for transmission of data based on some combination of said classes of service and a data time-stamp, said time-stamp indicative of the age of said data; and

scheduling data for transmission based on said priority;

wherein said step of scheduling includes performing the steps of

generating different classes of upstream and down stream data flows, said data flows including class of service and quality of service parameters;

selecting data for transmission based on the variable symbol rates and constellation types of said customer premises equipment; and

maximizing transmission of each time division duplex frame at the physical wireless and media access control levels.

19. The memory of claim 18 including instructions for maximizing the payload of each time division duplex frame.

20. The memory of claim 18, wherein said step of generating further includes the steps of

constructing a downstream map, wherein all wireless payload data units in a guaranteed transfer rate class of service that have packets waiting are scheduled for transmission;

determining whether any space remains in said time division duplex frame for additional data, said space being potentially available as a result of an under-used guaranteed transfer rate assigned to a particular SID; and

choosing the data to fill said space.

21. The memory of claim 20, wherein said step of choosing includes the step of determining priority of transmission based on said time-stamp and said class of service of a packet.

22. The memory of claim 20, wherein priority of transmission is given to said guaranteed transfer rate class.

23. The memory of claim 18, wherein said step of generating further includes the steps of

constructing an upstream map, wherein all wireless payload data units in one or more identified classes that have packets waiting are scheduled for transmission;

determining whether any space remains in said time division duplex frame for additional data, said space being potentially available as a result of an under-used guaranteed transfer rate assigned to a particular SID; and

choosing data to fill said space.

24. The memory of claim 23, wherein said step of choosing includes the step of determining priority based on some combination of said time-stamp and said class of service of a said packet.

25. The memory of claim 18, wherein said step of maximizing includes the steps of

selecting the position of data within a time division duplex frame such that co-channel interference within a communication cell is minimized;

utilizing unused portions of guaranteed bandwidth for other data to be transmitted;

adjusting operation dynamically to account for wireless payload data unit errors and acknowledgment requests;

compensating for wireless related channel impairments; and

integrating media access control messages within a time division duplex frame structure.