Quality of service over paths having a wireless-link

• US 20010024434A1
• Filed: 02/22/2001
• Published: 09/27/2001
• Est. Priority Date: 02/23/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation), University of Waikato
• Original Assignee: Microsoft Corporation
• Inventors: Moore, Timothy M., Ayyagari, Arun, Bernet, Yoram
• Granted Patent: US 7,079,508 B2
• Time in Patent Office: Days
• US Class Current: 370/347
• 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 with a pre-assigned Quality-of-Service over a path comprising at least one wireless link over a wireless medium, the path comprising a sending node, a receiving node and any intermediate nodes between the sending and the receiving nodes, the method comprising the steps of:

specifying a priority level for a packet from a plurality of priority levels at a node;

reserving resources at least one node in the path in accordance with a requested level of service; and

detecting, prior to commencing transmitting the packet by the node the wireless medium to be idle for a time interval variably generated based on at least (1) prior failed attempts transmit the packet and (2) the priority level of the packet from the plurality of priority levels.

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 including the step of assigning at least a default priority level from the plurality of priority levels to a packet.

4. The method of

claim 1

further including the step of discovering, at a node in the path, the next node in the path.

5. The method of

claim 1

further including the step of discovering, at a node managing a node in the path, the next node in the path.

6. The method of

claim 1

further including the step of employing a requested priority level from the plurality of priority levels as the priority level of the packet.

7. The method of

claim 1

further including the steps of 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 another 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.

8. The method of

claim 7

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 failure to transmit at the high and low priority levels respectively.

9. The method of

claim 7

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 failure to transmit at the high and low priority levels respectively.

10. The method of

claim 7

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 failure to transmit at the high and low priority levels respectively.

11. The method of

claim 7

wherein the path includes at least one access-point for establishing a wireless connection with another node in the path.

12. The method of

claim 7

wherein the access-point is associated with a subnet bandwidth manager.

13. The method of

claim 12

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 at least one wireless link, should be honored.

14. The method of

claim 12

wherein the subnet bandwidth manager associated with the access-point generates a reservation message and forwards the reservation message to the next node in the path.

15. The method of

claim 14

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.

16. A computer-readable medium having computer executable instructions for performing the steps of a method for transmitting a packet with a pre-assigned Quality-of-Service over a path comprising at least one wireless link over a wireless medium, the path comprising a sending node, a receiving node and any intermediate nodes between the sending and the receiving nodes, the method comprising the steps of:

specifying a priority level for a packet from a plurality of priority levels at a node;

reserving resources at least one node in the path in accordance with a requested level of service; and

detecting, prior to commencing transmitting the packet by the node the wireless medium to be idle for a time interval variably generated based on at least (1) prior failed attempts transmit the packet and (2) the priority level of the packet from the plurality of priority levels.

17. The computer readable medium of

claim 16

further having computer executable instructions 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.

18. The computer readable medium of

claim 16

further including computer executable instructions for carrying out the step of assigning at least a default priority level from the plurality of priority levels to a packet.

19. The computer readable medium of

claim 16

having computer executable instructions for carrying out the additional step of discovering, at a node in the path, the next node in the path.

20. The computer readable medium of

claim 17

further having computer executable instructions for carrying out the step of discovering, at a node managing a node in the path, the next node in the path.

21. The computer readable medium of

claim 16

having computer executable instructions for carrying out the step of employing a requested priority level from the plurality of priority levels as the priority level of the packet.

22. The computer readable medium of

claim 21

further having computer executable instructions for carrying out the steps of 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 another 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.

23. The computer readable medium of

claim 21

having computer executable instructions 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 failure to transmit at the high and low priority levels respectively.

24. The computer readable medium of

claim 23

having computer executable instructions 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 failure to transmit at the high and low priority levels respectively.

25. The computer readable medium of

claim 21

having computer executable instructions 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 failure to transmit at the high and low priority levels respectively.

26. The computer readable medium of

claim 25

having computer executable instructions wherein the path includes at least one access-point for establishing a wireless connection with another node in the path.

27. The computer readable medium of

claim 26

having computer executable instructions wherein the access-point is associated with a subnet bandwidth manager.

28. The computer readable medium of

claim 27

having computer executable instructions 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 at least one wireless link, should be honored.

29. The computer readable medium of

claim 28

having computer executable instructions wherein the subnet bandwidth manager associated with the access-point generates a reservation message and forwards the reservation message to the next node in the path.

30. The computer readable medium of

claim 29

having computer executable instructions wherein the policy includes checking if a sender of the reservation message is authorized to request resources.

31. The computer readable medium of

claim 29

having computer executable instructions 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.

32. An access point providing a quality of service guarantees with access to a wired network to at least one wireless device connected to the access point over a wireless link, the access point comprising:

a subnet bandwidth manager for reserving resources to support a requested quality of service and generating a reservation message to reserve resources at nodes on a path from the wireless device to a target device; and

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

36. The access point of

claim 32

having a second module to generate a time interval associated with a random number, the random number selected from a range such that the range is smaller if the node ready to transmit has previously failed to transmit the packet.

33. The access point of method 32 wherein the reservation message is an RSVP message.

34. The access point of

claim 33

having 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 in the path will not honor the requested quality of service.

35. The access point of method 32 wherein the prior failed attempts transmit the packet includes detecting the wireless medium to be busy when attempting to transmit the packet.