Quality of service over paths having a wireless-link

• US 7,079,508 B2
• Filed: 02/22/2001
• Issued: 07/18/2006
• Est. Priority Date: 02/23/2000
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation), University of Waikato
• Original Assignee: Microsoft Corporation
• Inventors: Moore, Timothy M., Ayyagari, Arun, Bernet, Yoram
• Primary Examiner(s): Hsu, Alpus H.
• Application Number:
  US09/792,765
• Publication Number:
  US 20010024434A1
• Time in Patent Office: 1,972 Days
• Field of Search: 370/230, 370/229, 370/338, 370/445, 370/448, 370/236, 370/447, 370/347, 370/329, 370/349, 709/249, 709/200, 455/452.2
• US Class Current: 370/329
• CPC Class Codes: H04L 1/1803 Stop-and-wait protocols
• CPC Class Codes: H04L 1/187 Details of sliding window management
• CPC Class Codes: H04L 1/1874 Buffer management
• CPC Class Codes: H04L 1/1887 Scheduling and prioritising arrangements
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/18 End to end
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/724 at intermediate nodes, e.g. resource reservation protocol [RSVP]
• CPC Class Codes: H04L 47/746 Reaction triggered by a failure
• 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/83 based on usage prediction
• CPC Class Codes: H04W 28/02 Traffic management, e.g. flow control or congestion control
• CPC Class Codes: H04W 28/24 Negotiating SLA [Service Level Agreement]; Negotiating QoS [Quality of Service]
• CPC Class Codes: H04W 28/26 Resource reservation
• CPC Class Codes: H04W 74/0808 using carrier sensing, e.g. carrier sense multiple access [CSMA]
• CPC Class Codes: H04W 74/0875 with assigned priorities based access
• CPC Class Codes: H04W 8/04 : Registration at HLR or HSS [Home Subscriber Server]

Abstract

The invention provides Quality of Service assurances in a manner expected in other media to communications over paths that include one or more wireless links. The invention combines a subnet bandwidth manager (“SBM”) at an access point (“AP”) to track allocations of wireless bandwidth. The invention further incorporates multiple priority levels for packet transmission in a two-prong stochastic scheme. The first prong reserves bandwidth at each of the intermediate nodes in a transmission path subject to a veto by any intermediate node. The second prong modulates the transmission probability of a packet based on the previous failed attempts at transmission and the priority level of the packet. The overall result of this hybrid scheme is to not shut out users with the lowest priority, e.g., “best effort” priority, while assuring adequate bandwidth to higher priority applications.

Claims

1. A method for transmitting a packet over a path comprising at least one wireless link, the path comprising a sending node and a receiving node, the method comprising:

specifying a priority level for the packet;

reserving resources at a node in the path other than the sending node in accordance with a requested level of service;

detecting, prior to transmitting the packet, the wireless link to be idle for a time interval, the time interval based on at least (1) a number of prior failed attempts to transmit the packet and (2) the specified priority level of the packet; and

establishing a wireless connection with another node in the path with the use of at least one access point, once the sending node has established a connection with said access point.

2. The method of claim 1 wherein at least one of the prior failed attempts to transmit the packet includes detecting the wireless link to be busy when attempting to transmit the packet.

3. The method of claim 1 further comprising:

assigning at least a default priority level to the packet.

4. The method of claim 1 further comprising:

discovering, at a node in the path, a next node in the path.

5. The method of claim 1 further comprising:

employing a requested priority level as the priority level of the packet.

6. The method of claim 1 further comprising:

detecting, at a node ready to transmit, a collision with another node;

placing the node ready to transmit into a backoff state in response to detecting the collision with the other node;

generating a randomly generated time delay within a contention window wherein the contention window is augmented if the node ready to transmit has previously failed to transmit the packet; and

waiting for the time delay prior to attempting to transmit the packet from the node ready to transmit.

7. The method of claim 6 wherein if the priority level of the packet is high, then using a smaller contention window for selecting the time delay compared to when the priority level of the packet is low with a similar number of prior failures to transmit at the high and low priority levels, respectively.

8. The method of claim 6 wherein if the priority level of the packet is high, then an upper end of the contention window for selecting the time delay is smaller compared to when the priority level of the packet is low with a similar number of prior failures to transmit at the high and low priority levels, respectively.

9. The method of claim 6 wherein if the priority level of the packet is high, then a lower end of a contention window for selecting the time delay is smaller compared to when the priority level of the packet is low with a similar number of prior failures to transmit at the high and low priority levels, respectively.

10. The method of claim 1 wherein the access point is associated with a subnet bandwidth manager.

11. The method of claim 10 wherein the subnet bandwidth manager associated with the access point decides whether a request for resources from the sending node, the resources including bandwidth over the wireless link, should be honored.

12. The method of claim 10 wherein the subnet bandwidth manager associated with the access point generates a reservation message and forwards the reservation message to a next node in the path.

13. The method of claim 12 wherein if the reservation message can be honored by the next node, based on its policy and already allocated resources, then the next node forwards the reservation message to a node next to the next node in the path.

14. A computer-readable medium having computer-executable instructions for performing a method for transmitting a packet over a path comprising at least one wireless link, the path comprising a sending node and a receiving node, the method comprising:

specifying a priority level for the packet;

reserving resources at a node in the path other than the sending node in accordance with a requested level of service;

detecting, prior to transmitting the packet, the wireless link to be idle for a time interval, the time interval based on at least (1) a number of prior failed attempts to transmit the packet and (2) the specified priority level of the packet; and

establishing a wireless connection with another node in the path with the use of at least one access point, once the sending node has established a connection with said access point.

15. The computer-readable medium of claim 14 wherein at least one of the prior failed attempts to transmit the packet includes detecting the wireless link to be busy when attempting to transmit the packet.

16. The computer-readable medium of claim 14 further comprising computer-executable instructions for:

assigning at least a default priority level to the packet.

17. The computer-readable medium of claim 14 further comprising computer-executable instructions for:

discovering, at a node in the path, a next node in the path.

18. The computer-readable medium of claim 14 further comprising computer-executable instructions for:

employing a requested priority level as the priority level of the packet.

19. The computer-readable medium of claim 14 further comprising computer-executable instructions for:

detecting, at a node ready to transmit, a collision with another node;

placing the node ready to transmit into a backoff state in response to detecting the collision with the other node;

generating a randomly generated time delay within a contention window wherein the contention window is augmented if the node ready to transmit has previously failed to transmit the packet; and

waiting for the time delay prior to attempting to transmit the packet from the node ready to transmit.

20. The computer-readable medium of claim 19 wherein if the priority level of the packet is high, then using s smaller contention window for selecting the time delay compared to when the priority level of the packet is low with a similar number of prior failures to transmit at the high and low priority levels, respectively.

21. The computer-readable medium of claim 19 wherein if the priority level of the packet is high, then an upper end of the contention window for selecting the time delay is smaller compared to when the priority level of the packet is low with a similar number of prior failures to transmit at the high and low priority levels, respectively.

22. The computer-readable medium of claim 19 wherein if the priority level of the packet is high, then a lower end of a contention window for selecting the time delay is smaller compared to when the priority level of the packet is low with a similar number of prior failures to transmit at the high and low priority levels, respectively.

23. The computer-readable medium of claim 14 wherein the access point is associated with a subnet bandwidth manager.

24. The computer-readable medium of claim 23 wherein the subnet bandwidth manager associated with the access point decides whether a request for resources from the sending node, the resources including bandwidth over the wireless link, should be honored.

25. The computer-readable medium of claim 24 wherein the subnet bandwidth manager associated with the access point generates a reservation message and forwards the reservation message to a next node in the path.

26. The computer readable medium of claim 25 wherein if the reservation message can be honored by the next node, based on its policy and already allocated resources, then the next node forwards the reservation message to a node next to the next node in the path.

27. An access point with access to a wireless device via a wireless link, the access point comprising:

a subnet bandwidth manager for reserving resources to support a requested quality of service for a packet and for generating a reservation message to reserve resources at a node other than the access point on a path from the wireless device to a target device, once a sending node has established a connection with said access point; and

a first module for detecting the wireless link to be idle for a time interval based on at least (1) a number of prior failed attempts to transmit the packet and (2) a priority level of the packet.

28. The access point of claim 27 wherein the reservation message is an RSVP message.

29. The access point of claim 27 further comprising:

a second module to free previously reserved resources at the access point if a response to the reservation message indicates that at least one node on the path will not honor the requested quality of service.