Scheduling methodology for connections with quality of service (QoS) constraints in a polling based media access control (MAC)

• US 6,657,987 B1
• Filed: 03/24/2000
• Issued: 12/02/2003
• Est. Priority Date: 03/24/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ramachandran, Lakshmi, Kumar, Apurva
• Primary Examiner(s): Ngo, Ricky
• Assistant Examiner(s): Swickhamer, Christopher M
• Application Number:
  US09/535,920
• Time in Patent Office: 1,348 Days
• Field of Search: 370/229, 370/230-236, 370/252, 370/253, 370/395--39, 370/412, 370/445-451, 370/238, 370/414, 370/346
• US Class Current: 370/346
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket

Abstract

Media Access Control (MAC) Scheduling for Quality of Service (QoS) uses the bandwidth and delay requirements of a connection to calculate the polling interval, which is the maximum time that the scheduler can be away from the connection. The methodology involves deadline-based scheduling and adapts deadlines based on the number of packets actually arriving to take advantage of any excess bandwidth that is available.

Claims

1. A method of scheduling of connections with quality of service (QoS) constraints in a polling based media access control (MAC) scheduling methodology for Master-driven Time Division Duplex (TDD) systems comprising the steps of:

a) calculating a polling interval, T_s, according to $T_s=k_s<br><br>L_s^{\max }<br><br>\left(\frac{1}{r_s}-\frac{1}{R}\right),$

where r_s is a token rate, R is a service rate, k_s is a number of packets served in each session s, and L_s^max is a maximum packet length for session s;

b) calculating a deadline as deadline(i)=current time+T_i;

c) finding a queue with the earliest deadline;

d) serving the queue with up to k_s packets, a number of packets served being k_sⁱ, where i is the i^th visit to the session s;

e) if k_sⁱ equals k_s and the number of packets, N_i, left in the queue is greater than zero, then setting deadline(s) equal to the current time plus a polling interval calculated as $T_s^i=\max <br><br>\left(\left(T_s+\frac{N_s^i<br><br>L_s^{\max }}{R}\right),T_s-B_s\right),$

where B_s is a bucket size for the session s;

f) if k_sⁱ is less than k_s, then setting deadline(s) equal to the current time plus a polling interval calculated as $T_s^i=\min <br><br>\left(\left(T_s+\frac{\left(k_s-k_s^i\right)<br><br>L_s^{\max }}{R}\right),T_s+B_s\right);<br><br>$

g) if k_sⁱ equals k_s and the number of packets, N_i, left in the queue is zero, then setting deadline(s) equal to the current time plus a polling interval calculated as in step a);

h) if a new connection has arrived, repeat beginning at step a);

i) else go back to step c).

2. The method of scheduling recited in claim 1, further comprising the step of using a polling interval, which is a maximum time that a scheduler can stay away from a connection.

3. The method of scheduling recited in claim 1, further comprising the step of using per-queue deadlines which are computed using the polling interval.

4. The method of scheduling recited in claim 1, further comprising the steps of:

recording the number of packets left in the queue when a scheduler leaves the queue; and

using the recorded information on the number of packets left in the queue to extend or advance the polling interval for the next visit to the same queue.

5. The method of scheduling recited in claim 1, further comprising the steps of:

recording a number of slots missed in each link due to wireless errors; and

using the recorded information on the number of slots missed to compensate the link.

6. The method of scheduling recited in claim 1, further comprising the steps of calculating the polling interval for a link based on rate and delay requirements of the connection while taking into account the maximum size of a packet for the connection.

7. The method of scheduling recited in claim 1, wherein per-connection deadlines are used.

8. The method of scheduling recited in claim 1, wherein a guaranteed connection with required Token rate r and Latency L and Token Bucket B is modeled as a periodic task with period P (in slots) and packet size C slots, satisfying the following:

9. The method of scheduling recited in claim 8, further comprising the step of selecting packet sizes and polling intervals for guaranteed bi-directional links with possibly different requirements in forward and reverse directions in a polling based TDD MAC.

10. The method of scheduling recited in claim 9, wherein the step of selecting packet sizes comprises the step of finding periods of forward and reverse periods, p₁ and p₂, respectively, and service times for forward and reverse tasks, c₁ and c₂, respectively.

11. The method of scheduling recited in claim 10, wherein the step of finding comprises the steps of:

setting p₁=p₂=p;

determining p, c₁, c₂ according to