Method and apparatus for flow control of data in a mesh network

• US 8,605,579 B2
• Filed: 10/16/2006
• Issued: 12/10/2013
• Est. Priority Date: 10/17/2005
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Abraham, Santosh, Nandagopalan, Saishankar, Nanda, Sanjiv
• Primary Examiner(s): Huq, Obaidul
• Application Number:
  US11/549,823
• Publication Number:
  US 20070127380A1
• Time in Patent Office: 2,612 Days
• Field of Search: 370229-462
• US Class Current: 370/230
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/17 Interaction among intermediate nodes, e.g. hop by hop
• CPC Class Codes: H04L 47/25 with rate being modified by the source upon detecting a change of network conditions
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/286 Time to live
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers
• 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: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 28/021 in wireless networks with changing topologies, e.g. ad-hoc networks self-organizing networks H04W84/18
• CPC Class Codes: H04W 28/0231 based on communication conditions dynamic wireless traffic scheduling definition based on channel quality criteria H04W72/54
• CPC Class Codes: H04W 28/10 Flow control between communication endpoints
• CPC Class Codes: H04W 28/22 Negotiating communication rate
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: H04W 74/08 Non-scheduled access, e.g. ALOHA hybrid access H04W74/02
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]
• CPC Class Codes: H04W 84/18 : Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Flows admitted to a mesh node may be controlled through contention access parameters. The admitting node may determine a desired transmission opportunity duration, and a transmission opportunity frequency. Furthermore, the node may achieve the flow rate and delay bound requirements of the admitted flow based at least in part upon the desired transmission opportunity duration, and the transmission opportunity frequency. The data rate and the access frequency of the admitted node may be monitored at the physical access level. The flow rate requirement may be accomplished based at least in part upon an adjustment to the transmission opportunity duration. The delay bound requirement may be accomplished at least in part upon manipulation of the contention access parameters. The transmission opportunity duration and the access parameters may be determined by the upstream admitting nodes, which may reduce congestion near mesh portals, and accomplish increased data transfer.

Claims

1. A method of controlling a flow of data within a mesh network that includes a plurality of mesh nodes, comprising:

receiving a transmit specification including a flow rate and a delay bound of a data flow at a first of the plurality of mesh nodes from a second of the plurality of mesh nodes to negotiate admission of the data flow through the first and second mesh nodes, wherein each of the plurality of mesh nodes functions as a wireless repeater that is separated from a given mesh portal within the mesh network by a given number of hops to other mesh nodes, the given mesh portal corresponding to a gateway between the plurality of mesh nodes and one or more external networks;

measuring, at the first mesh node, a channel characteristic of a channel on which the data flow associated with the received transmit specification will be transmitted on by the second mesh node to the first mesh node;

determining, at the first mesh node, a desired transmission rate based at least in part on the channel characteristic; and

determining, at the first mesh node, a transmission opportunity duration to achieve the flow rate at the desired transmission rate for a transmission of the data flow by the second mesh node to the first mesh node.

2. The method of claim 1 further comprising:

determining a desired overhead to achieve the delay bound at the desired transmission rate; and

adjusting a medium access parameter to achieve the desired overhead.

3. The method of claim 2 wherein the desired overhead is the minimum overhead required to achieve the delay bound.

4. The method of claim 2 further comprising receiving a reverse direction grant from the second mesh node.

5. The method of claim 2 wherein the desired overhead is the minimum overhead required to accommodate a reverse direction flow and achieve the delay bound.

6. The method of claim 1 wherein the transmission opportunity duration is determined at least in part by the equation:

7. The method of claim 1 further comprising determining a contention window parameter to achieve the flow rate at the desired transmission rate.

8. The method of claim 7, wherein the contention window parameter corresponds to a contention window threshold value.

9. The method of claim 8, wherein the contention window threshold value corresponds to a minimum value associated with a range of a contention window.

10. The method of claim 1 further comprising determining an arbitration inter-frame space time to achieve the flow rate at the desired transmission rate.

11. The method of claim 1, wherein the data flow corresponds to an upstream data flow that originates from one of the plurality of mesh nodes and is intended for transmission to the one or more external networks through the given mesh portal.

12. The method of claim 11, wherein the first mesh node forwards the data flow from the second mesh node to the given mesh portal via hopping to one or more additional mesh nodes.

13. The method of claim 11, wherein the second mesh node directly or indirectly receives from the data flow originator mesh node.

14. The method of claim 1, wherein the data flow corresponds to a downstream data flow that arrives at the given mesh portal and is intended for transmission to a destination node among the plurality of mesh nodes.

15. The method of claim 14, wherein the first mesh node forwards the data flow from the second mesh node to the destination node via hopping to one or more additional mesh nodes.

16. The method of claim 14, wherein the second mesh node directly or indirectly receives from the data flow from the given mesh portal.

17. The method of claim 1, wherein the given mesh portal corresponds to a Wireless Local Area Network (WLAN) Access Point.

18. The method of claim 17, wherein the WLAN Access Point operates in accordance with Institute for Electrical and Electronics Engineers (IEEE) 802.11.

19. A method for controlling a flow of data in a mesh network that includes a plurality of mesh nodes, comprising:

determining a desired flow rate, an achievable data rate on a link and a media access control overhead;

determining an access rate from a desired delay bound using an arbitration inter-frame space time and a contention window parameter; and

selecting a transmission opportunity duration for a transmission of a data flow between a first of the plurality of mesh nodes and a second of the plurality of mesh nodes based on at least one of the desired flow rate, the achievable data rate on the link or the media access control overhead,

wherein each of the plurality of mesh nodes functions as a wireless repeater that is separated from a given mesh portal within the mesh network by a given number of hops to other mesh nodes, the given mesh portal corresponding to a gateway between the plurality of mesh nodes and one or more external networks.

20. The method of claim 19 further comprising adjusting access parameters based on at least one of the desired flow rate, the achievable data rate on the link, a measured signal to noise ratio or an access success or failure rate.

21. The method of claim 19 further comprising adjusting the transmission opportunity duration based on at least one of the desired flow rate, the achievable data rate on the link, a measured signal to noise ratio or an access success or failure rate.

22. The method of claim 19 wherein the media access control overhead is selected from a group consisting of a preamble, an inter-frame spacing, and a block acknowledgement.

23. A non-transitory computer readable medium containing instructions stored thereon, which, when executed by a first mesh node within a mesh network that includes a plurality of mesh nodes, cause the first mesh node to perform operations, the instructions including:

instructions for processing a received transmit specification including a flow rate and a delay bound of a data flow from a second of the plurality of mesh nodes to negotiate admission of the data flow through the first and second mesh nodes, wherein each of the plurality of mesh nodes functions as a wireless repeater that is separated from a given mesh portal within the mesh network by a given number of hops to other mesh nodes, the given mesh portal corresponding to a gateway between the plurality of mesh nodes and one or more external networks;

instructions for measuring a channel characteristic of a channel on which the data associated with the received transmit specification will be transmitted on from the second mesh node to the first mesh node;

instructions for determining a desired transmission rate based at least in part on the channel characteristic; and

instructions for determining a transmission opportunity duration to achieve the flow rate at the desired transmission rate for a transmission of the data flow by the second mesh node to the first mesh node.

24. An apparatus for controlling a flow of data within a mesh network that includes a plurality of mesh nodes, the apparatus corresponding to a first of the plurality of mesh nodes, comprising:

a receiving module configured to receive a transmit specification including a flow rate and a delay bound of a data flow from a second of the plurality of mesh nodes to negotiate admission of the data flow through the first and second mesh nodes, wherein each of the plurality of mesh nodes functions as a wireless repeater that is separated from a given mesh portal within the mesh network by a given number of hops to other mesh nodes, the given mesh portal corresponding to a gateway between the plurality of mesh nodes and one or more external networks;

a measuring module configured to measure a channel characteristic of a channel on which the data associated with the received transmit specification will be transmitted on from the second mesh node to the first mesh node; and

a determining module configured to determine a desired transmission rate based at least in part on the channel characteristic and determine a transmission opportunity duration to achieve the flow rate at the desired transmission rate for a transmission of the data flow by the second mesh node to the first mesh node,

wherein one or more of the receiving module, the measuring module and the determining module includes a hardware component.

25. The apparatus of claim 24 further comprising an adjusting module configured to adjust a medium access parameter to achieve the desired overhead and wherein the receiving module is further configured to receive the transmit specification including the delay bound of the data flow from the mesh node and the determining module is further configured to determine a desired overhead to achieve the delay bound at the desired transmission rate.

26. The apparatus of claim 25 wherein the desired overhead is the minimum overhead required to achieve the delay bound.

27. The apparatus of claim 25 wherein the receiving module is further configured to receive a reverse direction grant from the second mesh node.

28. The apparatus of claim 25 wherein the desired overhead is the minimum overhead required to accommodate a reverse direction flow and achieve the delay bound.

29. The apparatus of claim 24 wherein the transmission opportunity duration is determined at least in part by the equation:

30. The apparatus of claim 24 wherein the determining module is further configured to determine a contention window parameter to achieve the flow rate at the desired transmission rate.

31. The apparatus of claim 24 wherein the determining module is further configured to determine an arbitration inter-frame space time to achieve the flow rate at the desired transmission rate.

32. An electronic device for controlling a data flow within a mesh network that includes a plurality of mesh nodes, the electronic device corresponding to a first of the plurality of mesh nodes, comprising:

a processor configured to measure a channel characteristic of a channel on which data associated with a transmit specification that is received from a second of the plurality of mesh nodes, including a desired flow rate and a delay bound for the data flow, will be transmitted on, from the second mesh node to the first mesh node, to negotiate admission of the data flow through the first and second mesh nodes, to determine a desired transmission rate based at least in part on the channel characteristic, and to determine a transmission opportunity duration to achieve the flow rate at the desired transmission rate for a transmission of the data flow by the second mesh node to the first mesh node; and

a memory coupled to the processor,

wherein each of the plurality of mesh nodes functions as a wireless repeater that is separated from a given mesh portal within the mesh network by a given number of hops to other mesh nodes, the given mesh portal corresponding to a gateway between the plurality of mesh nodes and one or more external networks.

33. The electronic device of claim 32 wherein the processor is further configured to adjust a medium access parameter to achieve the desired overhead, to receive the delay bound of the data flow from the mesh node, and to determine a desired overhead to achieve the delay bound at the desired transmission rate.

34. The electronic device of claim 33 wherein the desired overhead is the minimum overhead required to achieve the delay bound.

35. The electronic device of claim 33 wherein the processor is configured to receive a reverse direction grant from the second mesh node.

36. The electronic device of claim 33 wherein the desired overhead is the minimum overhead required to accommodate a reverse direction flow and achieve the delay bound.

37. The electronic device of claim 32 wherein the processor is configure to determine the transmission opportunity duration at least in part by the equation:

38. The electronic device of claim 32 wherein the processor is further configured to determine a contention window parameter to achieve the flow rate at the desired transmission rate.

39. The electronic device of claim 38 wherein the processor is further configured to determine an arbitration inter-frame space time to achieve the flow rate at the desired transmission rate.

40. An apparatus for controlling a flow of data within a mesh network that includes a plurality of mesh nodes, the apparatus corresponding to a first of the plurality of mesh nodes, comprising:

means for receiving a transmit specification including a flow rate and a delay bound of a data flow from a second of the plurality of mesh nodes to negotiate admission of the data flow through the first and second mesh nodes, wherein each of the plurality of mesh nodes functions as a wireless repeater that is separated from a given mesh portal within the mesh network by a given number of hops to other mesh nodes, the given mesh portal corresponding to a gateway between the plurality of mesh nodes and one or more external networks;

means for measuring a channel characteristic of a channel on which the data associated with the received transmit specification will be transmitted on from the second mesh node to the first mesh node;

means for determining a desired transmission rate based at least in part on the channel characteristic; and

determining a transmission opportunity duration to achieve the flow rate at the desired transmission rate for a transmission of the data flow by the second mesh node to the first mesh node.

41. The apparatus of claim 40 further comprising:

means for receiving the transmit specification including a delay bound of the data from the mesh node;

means for determining a desired overhead to achieve the delay bound at the desired transmission rate; and

means for adjusting a medium access parameter to achieve the desired overhead.

42. The apparatus of claim 41 wherein the desired overhead is the minimum overhead required to achieve the delay bound.

43. The apparatus of claim 41 further comprising means for receiving a reverse direction grant from the second mesh node.

44. The apparatus of claim 41 wherein the desired overhead is the minimum overhead required to accommodate a reverse direction flow and achieve the delay bound.

45. The apparatus of claim 40 wherein the transmission opportunity duration is determined at least in part by the equation:

46. The apparatus of claim 40 further comprising means for determining a contention window parameter to achieve the flow rate at the desired transmission rate.

47. The apparatus of claim 40 further comprising means for determining an arbitration inter-frame space time to achieve the flow rate at the desired transmission rate.

48. A non-transitory computer readable medium having instructions stored thereon, which, when executed by a given mesh node within a mesh network that includes a plurality of mesh nodes, cause the given mesh node to perform operations, the instructions including:

instructions for determining a desired flow rate, an achievable data rate on a link and a media access control overhead;

instructions for determining an access rate from a desired delay bound using an arbitration inter-frame space time and a contention window parameter; and

instructions for selecting a transmission opportunity duration for a transmission of a data flow between a first of the plurality of mesh nodes and a second of the plurality of mesh nodes based on at least one of the desired flow rate, the achievable data rate on the link or the media access control overhead,

wherein each of the plurality of mesh nodes functions as a wireless repeater that is separated from a given mesh portal within the mesh network by a given number of hops to other mesh nodes, the given mesh portal corresponding to a gateway between the plurality of mesh nodes and one or more external networks.

49. An electronic device configured to control a flow of data within a mesh network that includes a plurality of mesh nodes, comprising:

means for determining a desired flow rate, an achievable data rate on a link and a media access control overhead;

means for determining an access rate from a desired delay bound using an arbitration inter-frame space time and a contention window parameter; and

means for selecting a transmission opportunity duration for a transmission of a data flow between a first of the plurality of mesh nodes and a second of the plurality of mesh nodes based on at least one of the desired flow rate, the achievable data rate on the link or the media access control overhead,

wherein each of the plurality of mesh nodes functions as a wireless repeater that is separated from a given mesh portal within the mesh network by a given number of hops to other mesh nodes, the given mesh portal corresponding to a gateway between the plurality of mesh nodes and one or more external networks.