Method and system for scheduling traffic in a wireless network

• US 20050036466A1
• Filed: 08/13/2003
• Published: 02/17/2005
• Est. Priority Date: 08/13/2003
• Status: Active Grant

• Current Assignee: Image Processing Technologies, LLC (General Patent Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Malik, Rahul, Tan, Pek Yew, Lim, Wei Lih
• Granted Patent: US 7,460,543 B2
• Time in Patent Office: Days
• US Class Current: 370/338
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/788 Autonomous allocation of resources
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/824 Applicable to portable or mobile terminals
• CPC Class Codes: H04L 47/826 Involving periods of time
• CPC Class Codes: H04W 28/02 Traffic management, e.g. flow control or congestion control
• CPC Class Codes: H04W 74/02 Hybrid access
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

The present invention provides a method and system for efficiently scheduling wireless LAN traffic, giving the network the ability to serve both real-time and non-real time applications concurrently, while maintaining a requested level of quality of service for the real time application. It describes a method for scheduling quality of service traffic and a method to optimize this schedule thereby reducing the overall amount of time that is required for serving quality of service traffic (which is coordinated by a centralized network coordinator entity) and increasing the bandwidth available for non-real-time traffic. One application of such a scheduler would be WLANs that carry AV streams, such as may be found in a home based WLAN. Furthermore, a method is provided for announcing the schedule to all nodes in a wireless network to, for example, implement a power savings feature, thereby optimizing battery life and reducing the size and weight of portable network access terminals.

Claims

1. A system for the transmission of two different types of traffic in a wireless network, including time bounded repetitive traffic, and randomly generated traffic, the system comprising:

repeating frame durations comprising a period for the transmission of time bounded repetitive traffic and a period for randomly generated traffic;

a centralized coordinating node responsible for bandwidth management, resource scheduling and time coordination among nodes of the wireless network; and

at least one wireless node capable of transmitting and receiving information between other nodes.

2. A system for the transmission of traffic requiring a certain level of quality of service, the system comprising:

a centralized network coordinator responsible for bandwidth management, resource scheduling and time coordination among nodes of the wireless network, capable of interpreting a stream requirement furnished to it by a transmitting node, performing stream admission control and stream scheduling based on the stream requirements; and

a plurality of nodes capable of specifying respective traffic stream requirements to the centralized coordinator.

3. A method for a centralized coordinating node to schedule traffic in a wireless network, requiring a stated level of quality of service, the method comprising:

receiving stream specification requirements from a node wishing to initiate a traffic stream;

performing stream admission control based on bandwidth requested by the node and resources available in the network;

generating a traffic schedule based on a maximum duration available for the traffic requiring the quality of service, in the wireless network having repeating frame durations comprising a period for the transmission of time bounded repetitive traffic and a period for randomly generated traffic;

verifying conformance of the schedule based on the requirements of a maximum tolerable interval between medium grants, for all streams;

computing a reduction of required duration for coordinated transmission of traffic in the wireless network frame and optimizing the schedule; and

broadcasting the schedule information to all stations at a start of every wireless network frame.

5. The method according to claim 3, the reception of the stream specification requirements, comprising:

receiving information regarding a destination address of the stream and information regarding parameters describing characteristics of the stream.

6. The method according to claim 3, the performance of stream admission control further comprising:

computing a time required during each network frame for serving the stream based on information specific to the wireless network, including frame length and overheads associated with transmission, and parameters describing the characteristics of the stream; and

comparing required resources associated with the stream with the available network resources to determine whether the stream can be admitted.

7. The method according to claim 6, the computing further comprising:

computing an integer number of medium grants of maximum duration required during each network frame, to serve the stream; and

computing an actual transmission time using the integer number, accounting for a transmission rate, physical layer overheads, and a retransmission compensation factor.

8. The method according to claim 3, the generating of the traffic schedule for medium grants within the maximum duration in the network frame for the traffic requiring the quality of service, further comprising:

computing a minimum number of medium grants required to serve a stream, based on a maximum duration of a medium grant for the wireless network;

rounding up the minimum number of medium grants required for each stream in a manner to minimize an increase in the minimum number of medium grants required for each stream, wherein the rounding yields a set of numbers that are factors of the largest minimum number of medium grants required to serve all streams;

dividing a portion of the frame available for coordinated transmissions into uniform grant intervals, based on a largest value of the number of medium grants required determined during the rounding; and

allocating medium grants of different streams to the grant intervals, while minimizing the variance in unutilized time of each of the grant intervals.

9. The method according to claim 8, the dividing further comprising:

computing a global parameter of the grant intervals, defined as the period between recurrence of successive medium grants for the stream having a largest number of medium grants in a network frame, using parameters comprising;

a maximum duration in the network frame available for coordinated transmissions, and the maximum value of the medium grants required per network frame for all streams.

10. The method according to claim 8, the allocating further comprising:

creating a data structure to track available duration, in units of time, within each grant interval;

allocating medium grants to different grant intervals in a periodic manner, while minimizing the variance between the un-utilized time in each grant interval, using the data structure to track the resources available in each grant interval; and

wherein if medium grants cannot be allocated for a particular stream, then the value of medium grants required per grant interval for the particular stream is rounded up to a next highest factor of a maximum value of the minimum number of medium grants required to serve all streams, and again attempting to allocate the medium grants to different grant intervals.

11. The method according to claim 10, wherein the data structure comprises a vector comprising a number of elements corresponding to the number of grant intervals that the coordinated transmission period of each network frame is divided into, each element being initialized to the duration of the computed grant interval.

12. The method according to claim 10, the allocation of medium grants, further comprising computing a stream specific parameter of the grant allocation interval, wherein the stream specific parameter of the grant allocation interval is the periodicity in terms of grant intervals with which medium grants need to be allocated for a particular stream, wherein the input parameters are the set of medium grants required per network frame, for all admitted streams.

13. The method according to claim 3, the verifying further comprising:

computing a difference between a maximum medium grant interval, and a duration between the last medium grant in a wireless network frame to the first medium grant of the same stream in a next frame, as determined by the scheduling of medium grants; and

determining if any of the values in the difference between the maximum medium grant interval and the duration between the last medium grant are negative, indicating that stream requirements on maximum medium grant interval of the stream is being violated, wherein the requesting stream cannot be admitted.

14. The method according to claim 3, the computing further comprising:

computing an upper-bound on a possible reduction of the coordinated transmission period using a computed difference between a maximum medium grant interval, and a duration between a last medium grant in a wireless network frame to a first medium grant of the same stream in the next frame, as determined by the scheduling of medium grants computing an upper-bound on a maximum reduction in time per grant interval;

determining the actual reduction per grant interval as the minimum of all the elements in a data structure to track available duration within each grant interval after scheduling has been performed, and the upper-bound on the maximum reduction in time per grant interval is determined; and

reducing the grant intervals by the actual reduction per grant interval and rescheduling the medium grants allocated the streams.

15. The method according to claim 14, further comprising announcing the optimized schedule arrived at by the medium coordinator, the optimized schedule comprising, a source address of the streams;

a relative time of medium grants;

a duration of medium grants; and

;

a destination address of the stream.

16. The method according to claim 15, wherein the nodes in the wireless network can perform timing synchronization by adjusting their local clocks on receipt of broadcast frames transmitted by the medium coordinator, including the frames containing the optimized schedule.

17. The method according to claim 15, further comprising using the optimized schedule in a power saving mode, comprising:

transmitting the optimized schedule from the medium coordinator as part of a Signal-startCTP packet, signaling the start of a new wireless network frame;

determining at each node, based on the received schedule, when the node must wake-up to transmit and when the node is due to receive a transmission during the coordinated transmission period, such that during a remainder of the coordinated transmission period, the node may operate in the power savings mode; and

wherein a last entry of the schedule can be used by the medium coordinator to inform all nodes to power-on their receivers until a next schedule is received.

18. The method according to claim 14, further comprising a method for nodes to dynamically request additional bandwidth from the medium coordinator, comprising:

sending a supplementary bandwidth request frame to the medium coordinator during a granted medium grant; and

wherein the medium coordinator may grant a supplementary medium grant to the requesting station depending on an extent of reduction in the coordinated transmission period obtained by the optimization of the schedule.

4. A system for scheduling traffic requiring a stated level of quality of service in a wireless network having repeating frame durations comprising a period for transmission of bounded repetitive traffic and a period for transmission of randomly generated traffic, the system comprising:

a centralized coordinating node that receives stream specification requirements from a node wishing to initiate a traffic stream, that performs stream admission control based on bandwidth requested by the node and resources available in the network, that generates a traffic schedule based on a maximum duration available for the traffic requiring the quality of service, that verifies conformance of the schedule based on the requirements of a maximum tolerable interval between medium grants for all streams, that computes a reduction of a required duration for coordinated transmission of traffic in the wireless network frame and optimizes the schedule, and that broadcasts schedule information to all nodes of the network at a start of every wireless network frame.