Scheduler system and method thereof

• US 20060052088A1
• Filed: 10/10/2003
• Published: 03/09/2006
• Est. Priority Date: 10/17/2002
• Status: Active Grant

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Soomro, Amjad, Nandagopalan, Sai Shankar, Pavon, Javier del Prado
• Granted Patent: US 7,633,946 B2
• Time in Patent Office: Days
• US Class Current: 455/414.100
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04W 72/12 Wireless traffic scheduling
• CPC Class Codes: H04W 72/21 in the uplink direction of a wireless link, i.e. towards the network
• CPC Class Codes: H04W 84/12 WLAN [Wireless Local Area Networks]

Abstract

Disclosed is a method and system based on MAC frames for enabling a QAP to seamlessly operate between granting polls for upstream and sidestream traffic while sending downstream frames. The inventive scheduling method uses a minimum set of mandatory TSPEC parameters to generate a schedule, which provides minimum performance requirement in wireless local area networks (WLANs).

Claims

1. A method for scheduling the transmission of a data stream in a wireless communications network having at least one access point (QAP) (103) and at least one station (WSTA) (110, 112, 114), the method comprising the steps of:

receiving a request to send at least one data stream for transmission from at least one WSTA (110, 112, 114) by said QAP(103);

granting, by said QAP(103), said request to send said at least one data stream;

transmitting, by said at least one WSTA(110, 112, 114), a MAC frame comprised of a set of parameters defining the characteristics of said at least one data stream; and

,

calculating, by said QAP(103), service and transmission times according to a schedule algorithm for servicing said at least one WSTA(110, 112, 114).

2. The method of claim 1, wherein said schedule algorithm is operative to schedule the transmission of said at least one data stream at said calculated service and transmission times.

3. The method of claim 1, further comprising the step of generating, at said QAP(103), polling frames or downlink frames at said calculated service and transmission times allocated to said at least one WSTA(110, 112, 114) for transmission of said at least one data stream.

4. The method of claim 1, wherein said at least one data stream is parameterized traffic stream.

5. The method of claim 1, wherein the parameters of said MAC frame includes:

Mean Data Rate (ρ

_i), Nominal MSDU Size (L_i), and Maximum Service Interval or Delay Bound (D_i).

6. The method of claim 1, wherein the step of calculating said service and transmission times comprises the steps of:

determining a Service Interval (SI) and determining a TXOP duration for said SI.

7. The method of claim 6, wherein the step of determining said SI comprises the steps of:

selecting a number that is lower than said Maximum Service Intervals, and

selecting a number that is lower than said calculated SI and is a submultiple of a beacon interval.

8. The method of claim 6, wherein the step of determining said TXOP uses additional parameters:

Transmission Rate (R_i), Size of Maximum MSDU (M_i), and Overheads in Time units (O_i).

9. The method of claim 6, wherein the step of determining said TXOP duration comprises the step of:

calculating the number of MSDUs (N_i) that arrived at said Mean Data Rate (ρ

_i), during said SI according to the following equation;

$N_i=\lceil <br><br>\frac{\mathrm{SI}\times <br><br>{\mathrm{\rho <br><br>}}_i}{L_i}\rceil <br><br>$

calculating said TXOP_i duration as a maximum of (i) time to transmit number of MSDUs (N_i) frames at said Transmission Rate (R_i), (ii) time to transmit one maximum size MSDU at said R_i, and (iii) Overhead in time units (O) according to the following equation;

${\mathrm{TXOP}}_i=\max <br><br>\left(\frac{N_i\times <br><br>L_i}{R_i}+O,\frac{M}{R_i}+O\right)$

10. The method of claim 5, wherein the step of calculating said service and transmission times are performed if an admission control condition is satisfied, as follows:

${\mathrm{TXOP}}_{i+1}/D_{i+1}+\underset{i=1}{\overset{k}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{TXOP}}_i/D_i\le <br><br>1,<br><br>{\mathrm{TXOP}}_i=N_i<br><br>L_i/R_i+O<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}<br><br>\text{\hspace{1em}<br><br>}<br><br>N_i=D_i<br><br>{\mathrm{\rho <br><br>}}_i/L_{i.}$

where R_i represents a transmission Rate, N_i represents number of frames arriving during D_i, and O represents overheads in time units.

11. A method for scheduling the transmission of a data stream in a wireless communications network having at least one access point (QAP)(103) and at least one station (WSTA) (110, 112, 114), the method comprising the steps of:

determining, at said QAP(103), whether at least one data stream is originated from said at least one WSTA(110, 112, 114) based on a MAC frame comprised of a set of parameters defining the characteristics of said at least one upstream sidestream or downstream traffic stream;

computing service and transmission times, at said QAP(103), for servicing said at least one WSTA(110, 112, 114) in accordance with a schedule algorithm; and

,

transmitting, by said at least one WSTA(110, 112, 114), said at least one data stream at said computed service and transmission times.

12. The method of claim 11, wherein said at least one data stream is parameterized traffic stream.

13. The method of claim 11, wherein the parameters of said MAC frame includes:

Mean Data Rate (ρ

_i), Nominal MSDU Size (L_i), and Maximum Service Interval or Delay Bound (D_i).

14. The method of claim 11, wherein the step of calculating said service and transmission times comprises the steps of:

determining a Service Interval (SI) and determining a TXOP duration for said SI.

15. The method of claim 14, wherein the step of determining said SI comprises the steps of:

selecting a number that is lower than said Maximum Service Intervals, and selecting a number that is lower than said calculated SI and is a submultiple of a beacon interval.

16. The method of claim 14, wherein the step of determining said TXOP uses additional parameters:

Transmission Rate (R_i), Size of Maximum MSDU (M_i), and Overheads in Time units (O_i).

17. The method of claim 14, wherein the step of determining said TXOP duration comprises the step of:

calculating the number of MSDUs (N_i) that arrived at said Mean Data Rate (ρ

_i), during said SI according to the following equation;

$N_i=\lceil <br><br>\frac{\mathrm{SI}\times <br><br>{\mathrm{\rho <br><br>}}_i}{L_i}\rceil <br><br>$

calculating said TXOP_i duration as a maximum of (i) time to transmit number of MSDUs (N_i) frames at said Transmission Rate (R_i), (ii) time to transmit one maximum size MSDU at said R_i, and (iii) Overheads in time units (O) according to the following equation;

${\mathrm{TXOP}}_i=\max <br><br>\left(\frac{N_i\times <br><br>L_i}{R_i}+O,\frac{M}{R_i}+O\right)$

18. A system for seamlessly granting polls for upstream and/or sidestream traffic while simultaneously sending downstream traffic from said (AP)(103) to said at least one WSTA(110, 112, 114), the system comprising:

a memory for storing a computer-readable code; and

,

a processor operatively coupled to said memory, said processor configured to;

(1) receive a request to send at least one data stream for transmission from at least one WSTA(110, 112, 114) by said QAP(103);

(2) grant said request to send said at least one data stream by said WSTA (110, 112, 114) or QAP(103);

(3) transmit, by said at least one WSTA(110, 112, 114), a MAC frame comprised of a set of parameters defining the characteristics of said at least one data stream; and

,

(4) calculate, by said QAP(103), service and transmission times according to a schedule algorithm for servicing said at least one WSTA(110, 112, 114).

19. The system of claim 19, wherein the parameters of said MAC frame includes:

Mean Data Rate (ρ

_i), Nominal MSDU Size (L_i), and Maximum Service Interval or Delay Bound (D_i).

20. A system for scheduling the transmission of a data stream in a wireless communications network having at least one access point (QAP)(103) and at least one station (WSTA) (110, 112, 114), the system comprising:

means for determining, at said QAP(103), whether at least one data stream is originated from said at least one WSTA(110, 112, 114) based on a MAC frame comprised of a set of parameters defining the characteristics of said at least one data stream;

means for computing service and transmission times, at said QAP(103), for servicing said at least one WSTA(110, 112, 114) in accordance with a schedule algorithm; and

,

means for transmitting, by said at least one WSTA(110, 112, 114), said at least one data stream at said computed service and transmission times.

21. The system of claim 20, wherein the parameters of said MAC frame includes:

Mean Data Rate (ρ

_i), Nominal MSDU Size (L_i), and Maximum Service Interval or Delay Bound (D_i).

22. The system of claim 20, wherein the means for calculating said service and transmission times further comprises means for determining a Service Interval (SI) and a TXOP duration for said SI.

23. The method of claim 22, wherein the step of determining said SI comprises the steps of:

selecting a number that is lower than said Maximum Service Intervals, and

selecting a number that is lower than said calculated SI and is a submultiple of the beacon interval.

24. The system of claim 22, wherein the step of determining said TXOP uses additional parameters:

Transmission Rate (R_i), Size of Maximum MSDU (M_i), and Overheads in Time units (O_i).

25. The system of claim 24, wherein said TXOP duration is determined by:

$N_i=\lceil <br><br>\frac{\mathrm{SI}\times <br><br>{\mathrm{\rho <br><br>}}_i}{L_i}\rceil <br><br>$

calculating the number of MSDUs (N_i) that arrived at said Mean Data Rate (ρ

_i) during said SI according to the following equations;

${\mathrm{TXOP}}_i=\max <br><br>\left(\frac{N_i\times <br><br>L_i}{R_i}+O,\frac{M}{R_i}+O\right)$

calculating said TXOP_i duration as a maximum of time to transmit number of MSDUs (N_i) frames at said Transmission Rate (R_i), and time to transmit one maximum size MSDU at said R_i, and Overheads in time units (O) according to the following equation;

${\mathrm{TXOP}}_i=\max <br><br>\left(\frac{N_i\times <br><br>L_i}{R_i}+O,\frac{M}{R_i}+O\right)$

26. The system of claim 21, wherein the step of calculating said service and transmission times are performed if an admission control condition is satisfied, as follows:

${\mathrm{TXOP}}_{i+1}/D_{i+1}+\underset{i=1}{\overset{k}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{TXOP}}_i/D_i.\le <br><br>1,<br><br>{\mathrm{TXOP}}_i=N_i<br><br>L_i/R_i+O<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}<br><br>\text{\hspace{1em}<br><br>}<br><br>N_i=D_i<br><br>{\mathrm{\rho <br><br>}}_i/L_i.$

where R_i represents a transmission Rate, N_i represents number of frames arriving during D_i, and O represents overheads in time units.