Quality of service scheduling scheme for a broadband wireless access system

• US 6,856,786 B2
• Filed: 01/26/2001
• Issued: 02/15/2005
• Est. Priority Date: 01/26/2000
• Status: Expired due to Term

• Current Assignee: Xenogenic Development Limited Liability Company (Intellectual Ventures LLC)
• Original Assignee: VYYO, Ltd.
• Inventors: Belostotsky, Arkady, Leiman, Baruch
• Primary Examiner(s): Kincaid, Lester G.
• Assistant Examiner(s): Bhattacharya, Sam
• Application Number:
  US09/771,165
• Publication Number:
  US 20020052205A1
• Time in Patent Office: 1,481 Days
• Field of Search: 455/3.03, 455/3.04, 455/3.06, 725/97, 725/91, 725/95, 725/101, 725/103
• US Class Current: 455/3.03
• CPC Class Codes: H04L 12/2801 Broadband local area networks
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/56 implementing delay-aware scheduling
• 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/23 in the downlink direction of a wireless link, i.e. towards a terminal
• CPC Class Codes: H04W 72/542 using measured or perceived quality
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

A dynamic quality of service maintenance system for use with a broadband wireless or cable access system comprising a plurality of wireless modems and a wireless hub, the dynamic quality of service maintenance system maintaining adequate bandwidth for the wireless modems based upon the services provided to the wireless modems by the broadband wireless access system.

Claims

1. A wireless communication system, comprising:

a wireless hub configured to send downstream communications on at least one downstream channel and receive upstream communications from at least one client device on at least one upstream channel;

wherein;

said wireless hub comprises,

a timeline, having timed storage allocations for scheduled services to be provided in conjunction with at least one client device that is communicating with said wireless hub,

a scheduling mechanism configured to,

receive service requests from said client devices,

determine available time for provision of the requested service, and

place a marker identifying the requesting client and the service to be provided in a timed storage location of said timeline corresponding to the available time, and

a scheduler configured to retrieve markers in a time window of said timeline and build a message that describes time interval allocation on an upstream channel for said time window;

said scheduler comprises,

a global scheduler configured to make allocations in said time line for preliminary global time scheduling for STATION IDs according to the admitted Services by marking the Time Line with periodic potential or actual Time Line Elements (grants), and

a local scheduler configured to process incoming bandwidth requests and generate data grants in accordance with a service, registered for the requesting client;

said timeline comprises,

a local window comprising an array of time line elements, and

a global window comprising a table of periodic triplets;

said local scheduler is further configured to search for holes in said array of time line elements and assign said bandwidth requests to said holes;

said local scheduler includes a hole list comprising a list, sorted by size, of unallocated contiguous mini-slots; and

said search comprises matching a bandwidth request to said hole list.

2. The wireless communication system according to claim 1, wherein said wireless communication system is a broadband wireless access system.

3. The wireless communication system according to claim 1, wherein said client devices are Wireless Modem Units.

4. The wireless communication system according to claim 1, wherein said timeline is a data structure having a set of timeline elements including a STATION ID, identifying a requesting client, GRANT SIZE, identifying an amount of time allocated to a corresponding STATION ID, JITTER, identifying an amount of jitter associated with the corresponding STATION ID, and Actual/Potential, identifying whether the timeline element is an actual time grant or a potential element based on potential use of a subscribed service.

5. The wireless communication system according to claim 4, wherein said potential use of a subscribed service is a minimal Reserved Rate in the frame of a Best Effort service.

6. The wireless communication system according to claim 1, wherein said wireless hub further comprises an admission device that accepts and approves services ordered by said client devices.

7. The wireless communication system according to claim 6, wherein said services ordered include minimal reserved frame rates in a best effort type service.

8. The wireless communication system according to claim 1, wherein said scheduler includes a model configured to determine time grants needed for supported services.

9. The wireless communication system according to claim 1, wherein said timeline is a data structure having a set of timeline elements including a STATION ID, identifying a requesting client, GRANT SIZE, identifying an amount of time allocated to a corresponding STATION ID, JITTER, identifying an amount of jitter associated with the corresponding STATION ID, and Actual/Potential, identifying whether the timeline element is an actual time grant or a potential element based on potential use of a subscribed service.

10. A wireless communication system, comprising:

a wireless hub configured to send downstream communications on at least one downstream channel and receive upstream communications from at least one client device on at least one upstream channel;

wherein;

said wireless hub comprises,

a timeline, having timed storage allocations for scheduled services to be provided in conjunction with at least one client device that is communicating with said wireless hub,

a scheduling mechanism configured to,

receive service requests from said client devices,

determine available time for provision of the requested service, and

place a marker identifying the requesting client and the service to be provided in a timed storage location of said timeline corresponding to the available time, and

a scheduler configured to retrieve markers in a time window of said timeline and build a message that describes time interval allocation on an upstream channel for said time window;

said scheduler comprises,

a global scheduler configured to make allocations in said time line for preliminary global time scheduling for STATION IDs according to the admitted Services by marking the Time Line with periodic potential or actual Time Line Elements (grants), and

a local scheduler configured to process incoming bandwidth requests and generate data grants in accordance with a service, registered for the requesting client;

said timeline comprises,

a local window comprising an array of time line elements, and

a global window comprising a table of periodic triplets;

said local scheduler is further configured to search for holes in said array of time line elements and assign said bandwidth requests to said holes; and

said global scheduler assigns said grants in a table of periodic triplets, including, i, n, k, in which each group of n mini-slots, starting from the i^th mini-slot, a group of k mini-slots is assigned.

11. The wireless communication system according to claim 10, wherein said scheduler includes a model configured to determine time grants needed for supported services.

12. The wireless communication system according to claim 10, wherein said timeline is a data structure having a set of timeline elements including a STATION ID, identifying a requesting client, GRANT SIZE, identifying an amount of time allocated to a corresponding STATION ID, JITTER, identifying an amount of jitter associated with the corresponding STATION ID, and Actual/Potential, identifying whether the timeline element is an actual time grant or a potential element based on potential use of a subscribed service.

13. The wireless communication system according to claim 10, wherein said wireless communication system is a broadband wireless access system.

14. The wireless communication system according to claim 10, wherein said client devices are Wireless Modem Units.

15. A wireless communication system, comprising:

a wireless hub configured to send downstream communications on at least one downstream channel and receive upstream communications from at least one client device on at least one upstream channel;

wherein;

said wireless hub comprises,

a timeline, having timed storage allocations for scheduled services to be provided in conjunction with at least one client device that is communicating with said wireless hub,

a scheduling mechanism configured to,

receive service requests from said client devices,

determine available time for provision of the requested service, and

place a marker identifying the requesting client and the service to be provided in a timed storage location of said timeline corresponding to the available time, and

a scheduler configured to retrieve markers in a time window of said timeline and build a message that describes time interval allocation on an upstream channel for said time window;

said wireless communication device further comprises a timeline applications programming interface configured to set and retrieve time storage allocations to/from said timeline;

said timeline further comprises a local window comprising an array of time line elements, and

a global window comprising a table of periodic triplets; and

said timeline applications programming interface includes functions for at least one of Get, configured to get an element of the timeline, Put, configured to put an element on the timeline, GetPortion, configured to get a number of elements in a time interval, BeginSession, configured to close access to the timeline until and end of a session, EndSession, configured to open access to the timeline, PutPeriodicAllocation, configured to place a triplet into the global time area, and GetPeriodicAllocation, configured to get a triplet from the global time area.

16. The wireless communication system according to claim 15, wherein said scheduler includes a model configured to determine time grants needed for supported services.

17. The wireless communication system according to claim 15, wherein said client devices are Wireless Modem Units.

18. The wireless communication system according to claim 15, wherein said wireless communication system is a broadband wireless access system.