Quality of service scheduling scheme for a broadband wireless access system

• US 20020052205A1
• Filed: 01/26/2001
• Published: 05/02/2002
• Est. Priority Date: 01/26/2000
• Status: Active Grant

• Current Assignee: Xenogenic Development Limited Liability Company (Intellectual Ventures LLC)
• Original Assignee: VYYO, Ltd.
• Inventors: Belostotsky, Arkady, Leiman, Baruch
• Granted Patent: US 6,856,786 B2
• Time in Patent Office: Days
• US Class Current: 455/452.2
• 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 dynamic quality of service maintenance system for use in a broadband wireless access system comprising a plurality of wireless modems and a wireless hub, the scheduler maintaining adequate bandwidth for the wireless modems based upon the services provided to the wireless modems by the broad band wireless access system, comprising a map scheduler;

local scheduler;

global Scheduler;

admission decision maker; and

policy and statistics manager.

2. 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 map scheduler configured to retrieve markers in a time window of said timeline and build a MAP message that describes time interval allocation on an upstream channel for said time window.

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

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

5. The wireless communication system according to claim 2, wherein said timeline is a data structure having a set of timeline elements including 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.

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

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

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

9. The wireless device according to claim 7, wherein said scheduler comprises,

a global scheduler configured to make allocations in said time line for preliminary global time scheduling for SIDs 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.

10. The wireless device according to claim 2, wherein said scheduler comprises,

a global scheduler configured to make allocations in said time line for preliminary global time scheduling for SIDs 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.

11. The wireless device according to claim 10, wherein 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.

12. The wireless device according to claim 11, wherein:

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

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

13. The wireless device according to claim 11, wherein 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.

14. The wireless device according to claim 2, wherein said scheduler includes a model configured to determine time grants needed for supported services.

15. The wireless device according to claim 2, further comprising:

a timeline API configured to set and retrieve time storage allocations to/from said timeline.

16. The wireless device according to claim 15, wherein:

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

18. The method according to claim 17, wherein:

said step of scheduling comprises the steps of,

scheduling periodic grants across an entire length of said timeline; and

scheduling bandwidth requests from said clients in a local time window of said timeline;

wherein said local time window is a portion of said timeline to be allocated in a next MAP message(s) communicated in said communicating step.

19. The method according to claim 18, further comprising the step of modeling admitted services and making grants in said timeline based on said modeling.

20. The method according to claim 17, wherein said step of building a MAP message comprises the steps of:

closing a buffer for incoming bandwidth requests at a predetermined time interval;

extracting a portion of elements from the timeline;

shifting a start time pointer indicating a start of a local time window on said timeline for bandwidth request allocations; and

constructing said MAP message.

22. The device according to claim 20, wherein said at least one shared communication line is a broadband wireless communication channel.

23. The device according to claim 20, wherein said clients are a set of wireless modems in a point to multi-point broadband wireless system.

17. A method of service scheduling of an upstream channel in a point to multi-point communication system, wherein said point is a hub device, and said multi-point is a set of client devices communicating with said hub, comprising the steps of:

scheduling said services in a timeline so as to identify a client device;

building a MAP message comprising at least a portion of the services scheduled in said timeline; and

communicating said timeline to said client devices.

21. A device for determining time grants for at least one shared communication line, comprising:

means for storing time grants;

means for placing periodic time allocations in said storing means for services admitted to devices using said shared communication line; and

means for placing bandwidth requests into said storing means for bandwidth requested by said devices;

means for building a message indicating which clients may access said at least one shared communication line during specified time intervals; and

means for communicating said message to said clients.