HK1126597A - Method and apparatus for managing data flow through a mesh network - Google Patents

Abstract

Traffic streams through mesh points in a mesh network are managed. Data arriving at the mesh point are aggregated in packet queues. The packet queues segregate arriving data by the data's Quality of Service (QoS) requirement. An appropriate communication channel is selected. The communication channel is accessed through a contention access schema. An M-Request-To-Send (MRTS) message is sent to potential receiving mesh points with receiving mesh points responding with an M-Clear-to-Send (MCTS) message. Data from the packet queues is transmitted to the next mesh point. A mesh point power save mode allows battery operated mesh points to sleep preserving power.

Description

Method and apparatus for managing data flow through a mesh network

Claiming priority under 35U.S.C. § 119

This patent application claims priority based on provisional application No. 60/727,642, filed on 10/17/2005, which is assigned to the present assignee and is expressly incorporated herein by reference.

Technical Field

The present patent application relates to mesh networks. More particularly, the present patent application relates to a method and apparatus for managing data flows through a mesh network.

Background

In recent years, the demand for widespread access to high-speed data services has increased. The telecommunications industry has responded to this increase in demand by providing various wireless products and services. To try to make these products and services interoperable, the Institute of Electrical and Electronics Engineers (IEEE) promulgates a set of Wireless Local Area Network (WLAN) standards, such as IEEE 802.11. Products and services that conform to these standards are typically networked in a wireless point-to-multipoint configuration. In this configuration, individual wireless devices (e.g., stations) may communicate directly with an internet access point, and each of the wireless devices shares the available bandwidth.

A more efficient and resilient network can be achieved by using a mesh network. A mesh network is a distributed network with multiple wireless mesh points. Each mesh point in the mesh network may act as a repeater that receives traffic, transmits or transmits a stream (TS) and relays the TS to the next mesh point. TSs travel from an originating mesh point to a destination mesh point by "hopping" from mesh point to mesh point. TS routing algorithms ensure efficient routing of TSs from an originating mesh point to a destination mesh point. The TS routing algorithm may dynamically adapt to changes in the mesh network and make the mesh network more efficient and resilient. For example, a TS routing algorithm may route TSs to a destination mesh point via other mesh points if the mesh point is overly busy manipulating the TSs or the mesh point has exited the mesh network.

The destination mesh point is typically a mesh portal. TSs arriving at an ingress may be decoded and reformatted for retransmission over other networks, such as the internet. A TS originating at a mesh point and traveling toward a mesh portal is referred to as an upstream TS. A TS from a mesh portal and traveling towards a destination mesh point is referred to as a downstream TS. Mesh points that are a single hop away from a mesh portal are referred to as rank 1 mesh points. Mesh points that require at least two hops to reach a mesh portal are referred to as rank 2 mesh points. Generally, a mesh point that requires n hops to reach a mesh portal is referred to as an n-tier mesh point.

A large percentage of the traffic flows of a mesh network are upstream and downstream TSs. Upstream TSs typically hop from higher level mesh points to lower level mesh points before leaving via a mesh portal. Downstream TSs typically hop from lower mesh points to higher mesh points. Thus, lower rank mesh points support the traffic flows of higher rank mesh points, resulting in more TS congestion around the lower rank mesh points. In general, a rank 1 mesh point is likely to support more upstream and downstream TSs than a rank 2 mesh point. Similarly, a mesh point of rank 2 is likely to support more TSs than a mesh point of higher rank (e.g., 3, 4, etc.).

Mesh network topologies where lower mesh points support upstream and downstream traffic flows from higher mesh points tend to result in TS flow congestion at mesh points near mesh portals. Flow congestion is caused by a number of factors, including (but not limited to): neighboring mesh points attempt to access the communication channel medium overly frequently, neighboring mesh points transmit at a lower than optimal data rate at the physical access layer, neighboring mesh points transmit bursts that occasionally exceed negotiated access throughput, and poor radio conditions between downstream and upstream mesh points that result in lower than expected throughput.

Those skilled in the art have recognized that apparatus and methods for reducing mesh congestion and improving data manipulation at individual mesh points may improve the efficiency and reliability of a mesh network.

Disclosure of Invention

TSs may be managed individually by each mp. Prior to receiving the TS, the mesh point receives an admission request with a Traffic Specification (TSPEC). The mesh point may determine whether there is adequate capacity to admit the TS and accept or reject the admission request. If the admit request is accepted, the mesh point may aggregate data from that TS with data from other TSs. The mesh point may broadcast a request to send a message containing an ordered sequence of responses. The receiving mp may respond in sequence with a clear to send. The mesh point may send the data packet to the receiving mesh point. The receiving mesh point may acknowledge receipt of the packet block using a data block acknowledgement message depending on the acknowledgement policy specified during TS setup. The mp may have a power save mode to conserve energy. The mesh point may also select transmission channels to balance mesh load or increase mesh throughput.

A method for managing traffic flows (TSs) at a mesh point in a mesh network. The method may include: receiving a data packet; placing data from a data packet in one or more packet queues; aggregating data from one or more packet queues into a transmit data packet; and transmitting the transmission data packet during a transmission opportunity duration.

Drawings

The features, objects, and advantages of the disclosure will become more apparent from the detailed description set forth below when taken in conjunction with the drawings in which:

fig. 1 is a mesh network according to an aspect.

Fig. 2 shows a timing diagram illustrating contention access at the exemplary mesh point of fig. 1 according to an aspect.

Fig. 3 shows a portion of the mesh network of fig. 1 illustrating access control at an exemplary mesh point, according to an aspect.

Fig. 4 is a block diagram showing data aggregation at an exemplary mesh point in the mesh network of fig. 1, according to an aspect.

Fig. 5 is a block diagram showing MRTS and MCTS message structures of the mesh network of fig. 1 according to an aspect.

Fig. 6 is a block diagram showing an exemplary beacon message transmitted from the mesh point in fig. 1 in accordance with an aspect.

Fig. 7 is a diagram of a portion of the mesh network of fig. 1 including two meshes with two separate channels according to an aspect.

Fig. 8 is a flow diagram of a method of TS management at an exemplary mesh point, according to an aspect.

Fig. 9 is a flow diagram of a method of energy management at an exemplary mesh point, according to an aspect.

Fig. 10 is a flow diagram of a method of channel management at an exemplary mesh point in accordance with an aspect.

Fig. 11 is a block diagram illustrating exemplary components of an apparatus for managing traffic flows in accordance with an aspect.

Fig. 12 is a block diagram illustrating exemplary components of an apparatus for TS management at an exemplary mesh point according to an aspect.

Detailed Description

Methods and systems that implement aspects of the various features of the present disclosure will now be described with reference to the drawings. The drawings and associated descriptions are provided to illustrate aspects of the disclosure and not to limit the scope of the disclosure. Reference in the specification to "one aspect" or "an aspect" is intended to indicate that a particular feature, structure, or characteristic described in connection with the aspect is included in at least one aspect of the disclosure. The appearances of the phrase "in one embodiment" or "an aspect" in various places in the specification are not necessarily all referring to the same aspect. Throughout the drawings, reference numerals are reused to indicate correspondence between the referenced elements. In addition, the first digit of each reference number indicates the figure in which the element first appears.

Fig. 1 shows an exemplary mesh network 100 according to an aspect. Mesh network 100 may include one or more mesh portals, such as mesh points 102 and 104. A mesh portal is a mesh point connected to a wired network, such as the internet 106. A mesh portal may serve as a gateway between a wired network and a wireless mesh network. Mesh portals are referred to as level 0 mesh points since they form gateways into and out of the mesh network 100.

The mesh network 100 may also have mesh points (e.g., mesh points 106, 108, 110, 112, 114, 116, and 118) that are not mesh portals but are capable of communicating directly with one or more mesh portals. These mesh points are rank 1 because the TSs at these mesh points make one hop to reach the mesh portals (e.g., mesh points 102 and 104). Some mesh points (e.g., mesh points 120, 122, 124, 126, 128, and 130) are not able to communicate directly with mesh portals 102 and 104 but communicate with mesh portals 102 and 104 via another mesh point. These mesh points are rank 2 because the TSs at these mesh points make at least two hops to reach the mesh portals (e.g., mesh points 102 and 104). A TS originating at mesh point 120 may make a first hop to mesh point 108 or mesh point 118 before hopping to mesh point 102 (mesh portal). Other mesh points are not able to communicate with a mesh portal 102 or 104 (e.g., mesh point 132) with fewer than two hops. A TS originating at mesh point 132 may make a first hop to mesh point 122 before hopping to mesh portal 102 and before hopping to mesh point 108 or mesh point 118. Mesh point 132 is rank 3 because it makes at least three hops to reach a mesh portal (e.g., mesh points 102 and 104). In general, the rank of any mesh point may be determined by calculating the minimum number of hops for a TS originating at the mesh point to reach a mesh portal.

The TSs bound for lower level mesh points are referred to as upstream traffic flows. The TSs bound for higher rank mesh points are referred to as downstream traffic flows. Thus, TSs destined for mesh portals (e.g., mesh points 102 and 104) are upstream traffic flows and TSs entering the mesh network 100 at mesh portals (e.g., mesh points 102 and 104) are downstream traffic flows. Since many of the traffic in the mesh network 100 is likely to arrive at and leave the mesh network 100 at the mesh points 102 and 104, there is an increased likelihood of TS congestion around the mesh portals 102 and 104 and other lower-level mesh points.

Fig. 2 shows a timing diagram illustrating contention access at the exemplary mesh point of fig. 1 according to an aspect. The mesh point channel assignments may include a transmission opportunity (TxOP) duration, a contention window minimum (CW)_min) Contention window maximum (CW)_max) And arbitrating at least one access parameter for an inter-frame space (AIFS) time to control access to the communication channel. Mesh points transmitting via the communication channel may contend for access to the communication channel.

Each of the mesh points may monitor the communication channel and the transmitting mesh point may idle for a latency equal to its respective assigned AIFS time when the communication channel becomes available. During the AIFS time, the idle mesh points may continue to monitor the communication channel, and if the communication channel becomes busy, the mesh points may continue to idle and wait until the communication channel becomes available, and then wait for another time period equal to their respective assigned AIFS time. The mesh point may set a backoff timer when the communication channel has been available for a period of time equal to its AIFS time. The length of time set on the back-off timer is random. By taking from the assigned CW_minAnd CW_maxThe number of uniform distributions therebetween to determine the length of time set on the compensation timer.

Three possible results of contention access for individual mesh points are shown on the three time lines of fig. 2. The first timeline shows mesh points that successfully contend for access when a communication channel becomes available. Timeline with mesh point monitoring busyThe lu 202 communication channel starts. When the communication channel is busy 202, the mesh point's transmitter is idle. When a channel becomes available, the mesh point's transmitter continues to idle for a period of time equal to its AIFS time 204. While idle, the mesh point continues to monitor the communication channel. At the end of the AIFS time 204, the mesh point may schedule the data by starting with the CW having the minimum value_min207 and a maximum value CW_maxThe uniform distribution 205 of 209 selects a number to randomly select the backoff slots. This selected number is multiplied by a standard defined time slot (e.g., a time slot may be about 9 microseconds) and the result is referred to as a backoff time. The backoff time defines the length of the backoff window 206. The mesh point's transmitter continues to idle and monitor the communication channel until the backoff timer determines that a length of time equal to the backoff window 206 has expired. At the end of the backoff window 206, the mesh point's transmitter has a TxOP 208 during which the mesh point may transmit information to the receiving mesh point. At the end of TxOP 208, the mesh point's transmitter is again idle and begins to wait for the AIFS time, starting the contention access process again.

The second timeline shows another possible outcome of contention access. The result may occur when another station begins transmitting during the AIFS time. The timeline may begin with the mesh point monitoring a busy 212 communication channel. When the communication channel becomes available, the mesh point's transmitter may idle and the mesh point may begin to wait a time equal to the AIFS time 214. During AIFS time 214, another mesh point with a shorter AIFS time may begin transmitting and the communication channel may again become busy 216. The mesh point's transmitter may continue to idle and the mesh point waits for the communication channel to become available again. When a communication channel becomes available, the mesh point may wait another AIFS time 218 before selecting the backoff time defined by the backoff window 220 and starting the backoff window counter.

The third timeline shows another possible outcome of contention access. The result may occur when another station interrupts during the backoff window of the mesh point. The timeline begins with the mesh point monitoring the communication channel while the communication channel is busy 222. During this time, the mesh point's transmitter may be idle. When a communication channel becomes availableThe mesh point's transmitter may continue to idle for a period of time equal to the AIFS time 224. While idle, the mesh point may continue to monitor the communication channel. At the end of the AIFS time 224, the mesh point may schedule the next CW from the minimum time_min207 and maximum time CW_max.The uniform distribution 205 of 209 selects a time to randomly select the backoff time. The mesh point's transmitter may continue to idle until the backoff timer counts a length of time equal to the backoff window 226. When idle, the mesh point may continue to monitor the communication channel. When the backoff counter counts, another mp may begin transmitting and the communication channel may become busy 228. The backoff counter may be stopped. When the communication channel becomes available, the mesh point's transmitter may continue to idle and wait for a period of time equal to the AIFS time 230. At the end of the AIFS time 230, the backoff counter may start counting again from the time it stopped.

Can be adjusted by adjusting the TxOP duration, CW_min、CW_maxAnd AIFS time to control the transmission frequency and transmission data rate of the mesh point. A large TxOP duration allows a mesh point to transmit a large amount of data each time the mesh point accesses a receiving mesh point, resulting in a large data rate. A small AIFS time relative to neighboring mesh points competing for access to the communication channel increases the probability of access, resulting in a large number of medium accesses (and thus more txops assuming the TxOP is constant for each access) and a large data rate. Similarly, small CWs relative to neighboring mesh points_minAnd CW_maxIncreasing the probability of selecting a small backoff time and increasing the probability of access to the receiving mesh point, resulting in a large number of txops and a large data rate. Similarly, small TxOP, large AIFS time, or large CW_minAnd CW_maxWhich may result in a low data rate.

By passing through access parameters TxOP, CW_min、CW_maxAnd AIFS time to control transmission frequency may also adjust quality of service (QoS). To reduce TS delay, CW can be reduced_min、CW_maxOr AIFS time, thereby increasing the probability of successful access to the receiving mesh point. To compensate for more frequent accesses, it may be reducedTxOP duration to free up channel capacity for other mesh points. Reducing the TS delay by increasing successful media access may be achieved at a certain price. Each media access may have Media Access Control (MAC) overhead. The MAC overhead consumes communication channel bandwidth that would otherwise be available for the TS.

In the mesh network 100, at least one access parameter may be assigned based on rank, amount of traffic carried, and available rate. Lower rank mesh points may carry more traffic and may be assigned lower AIFS, CW_min、CW_maxA value and a larger TxOP duration. The descriptor may be provided with a TS, the descriptor identifying an average bit rate of the TS and a peak bit rate of the TS. The access parameters may be adjusted to accommodate the average bit rate and the peak bit rate of the TS. The available bit rate between two mesh points at the physical layer may also be used to tune the access parameters. The access parameters may also be adjusted when new flows and mesh points are added to the mesh network 100.

In another aspect, at least one access parameter may be adjusted based on a rank of a mesh point. The mesh portal may then broadcast these access parameters to neighboring mesh points, which in turn broadcast these access parameters to their neighboring mesh points until all mesh points have their respective access parameters. Alternatively, the access parameters may be preset by the provider.

Fig. 3 shows a portion of the mesh network 100 of fig. 1 illustrating access control at an exemplary mesh point, according to an aspect. Admission control of TSs to mesh points may be performed by each of the mesh points in the mesh network 100. Each mesh point in the mesh network 100 may broadcast load information in its beacon. For example, mesh point 118 may broadcast its load information L₁₁₈302, mp 120 may broadcast its load information L₁₂₀304, the mp 130 may broadcast its load information L₁₃₀306, the MP 122 may broadcast its load information L₁₂₂308 and the mp 102 broadcasts its load information L₁₀₂310。

Each of the mesh points may use the load informationAdmission control on a new TS. For example, mesh point 120 may use L₁₁₈302 to determine whether mesh point 118 is able to accommodate the new TS. If mesh point 120 determines that mesh point 102 is capable of handling the new TS, it may send an admit request to mesh point 118. Mesh point 118 may determine whether there are sufficient idle periods in its neighborhood to accommodate a TxOP for the new TS and, if so, allow the new TS in. Otherwise, mesh point 118 may deny the admission request.

Admission control may be controlled by each mesh point in the mesh network 100. The downstream mesh point may negotiate a TxOP for the upstream TS with the upstream mesh point. An upstream mesh point may negotiate a TxOP for downstream TSs with a downstream mesh point. Alternatively, the downstream mesh point may negotiate a TxOP for the upstream TS with the downstream TS, thereby saving a TxOP large enough to accommodate the upstream TS and the downstream TS.

Fig. 4 is a block diagram showing data aggregation at an exemplary mesh point 118 in the mesh network 100 of fig. 1, according to an aspect. Mesh point 118 may parse packets 402 arriving from mesh points 120, 130, and 122 into two or more QoS data types. The data may be parsed into a high QoS and a best available QoS and stored in respective packet queues or locations 404 and 406. Data from incoming data packets 402 may be aggregated in QoS packet queues 404 and 406. The data packet generator 408 may use the data in the packet queues 404 and 406 to generate data packets and give priority to the high QoS data stored in the packet queue 404. The data packet transmitter 408 may forward the packet to one or more mesh points. In this example, the packet transmitter 408 may forward the packet to the mesh point 102.

The aggregation of data packets allows for more efficient use of the communication medium. The aggregate size should be large enough so that many bits can be transmitted for each media access reducing the required media access frequency and its associated overhead. The aggregation size may also be small enough such that the aggregation delay does not adversely affect the negotiated QoS by causing unacceptable TS latency.

Thus, TS flow control may be performed at any mesh point in the mesh network via access control, assignment of contention access parameters, and use of QoS identifiers. Backpressure applications may extend from low rank mesh points to high rank mesh points. Backpressure may be applied as explained herein and mesh points may use explicit backpressure messages or broadcast backpressure messages directed at a particular mesh point. A mesh point may command another mesh point to adjust its throughput or its medium access frequency. The backpressure messages may be piggybacked or aggregated with other data packets.

Acknowledgement of receipt of packet 402 may be performed using block acknowledgement. Upon receiving a data block of a predetermined length for a particular QoS, the mesh point may send a block acknowledgement to the transmitting mesh point. For example, mesh point 118 may send block acknowledgement messages to mesh points 120, 122, and 130. Packet sequencing may also be performed at the mesh point. For example, mesh point 118 may assign a new number of sequences when packets are aggregated in packet generator 408. Mesh point 118 may hold the block of data packets before forwarding until a complete block of data packets is received and any missing packets from the block of data packets are recovered. In this manner, data packets forwarded in the mesh network 100 may be held at each mesh point hop until a complete block of data packets is received.

Fig. 5 shows an exemplary timeline for an M Request To Send (MRTS) message 502 from mesh point 122 to mesh points 118 and 108 followed by M Clear To Send (MCTS) messages 504 and 506 from mesh points 118 and 108, respectively, in response to the MRTS. TS collisions in the mesh network 100 may be minimized by the transmitting mesh point transmitting an RTS message and each potential receiving mesh point responding with a CTS message. Traffic collisions for CTS responses may be minimized by using M extensions to RTS and CTS messages. For example, mesh point 122 may broadcast an RTS message with an M-extension that identifies mesh points 118 and 10 and the order they should follow in response to MCTS messages. Mesh points 118 and 108 may respond with MCTSs in the order specified in the MRTS message. The response may be a broadcast (omni-directional) message or the response may be a directional message. The directional message may be directed using beam steering or multiple-input multiple-output (MIMO) transmission.

The RTS and CTS transmission handshake along with the data block acknowledgement may be used to protect data transmission over the medium. Once the RTS and CTS handshakes occur, other mesh points in the neighborhood may suspend transmissions that may interfere with the link established between the transmitting mesh point (e.g., mesh point 122) and the receiving mesh points (e.g., mesh points 108 and 118). This reduces the chance of collisions caused by hidden mps that may be transmitting, but may not be known to the mp 122 due to shadowing or environmental conditions. RTS and CTS transmission handshakes with block acknowledgements may also be implemented in MRTS and MCTS message structures.

After transmitting the data block to the receiving mesh point, the transmitting mesh point (e.g., mesh point 122) may make a reverse direction grant allowing the receiving mesh points (e.g., mesh points 108 and 118) to transmit downstream TSs. The reverse direction grant is not necessarily a new TxOP, but may be part of a TxOP that has been saved for the original transmitting mesh point.

After negotiating successful media access via an RTS/CTS or MRTS/MCTS handshake, the transmitting mesh point may transmit data during the TxOP duration. If all data is transmitted, the transmitting mesh point may reset its access parameters. TS flow control may be employed via buffers such as a high QoS packet queue 404 and a best available QoS packet queue 406. One way to control the flow rate may be to set the scheduling service interval to one quarter of the total allowable hop delay interval for the TS.

Fig. 6 is a block diagram showing an exemplary beacon message 602 transmitted from a mesh point in accordance with an aspect. The beacon message may include a mesh portal identifier 604, the number of hops to the mesh portal 606, and the number of mesh points in the mesh network 608. The mesh network 100 may have more than one mesh if some of the mesh points have more than a single channel of operational capability. In this case, each of the mesh points may use the beacon message 602 to select a channel for its TS.

Each mesh point may monitor the beacons of mesh points in its neighborhood to determine which channel to use. The mesh point may use the measured beacon signal strength as a metric to select a channel based on the achievable data rate on the channel. The mesh point may also attempt to equalize the load on the mesh network 100 by selecting the least congested channel.

Fig. 7 shows the mesh network 100 of fig. 1 in which mesh points 102 (mesh portals) may operate on more than one channel. Thus, two or more meshes may be present simultaneously. Mesh portal 102 may broadcast its beacon 602 on channels 1 and 2. Neighboring mesh points 106, 108, and 118 may monitor beacons 1 and 2. Neighboring mesh points 106, 108, and 118 may select channels or balance the load based on the strength of the beacon received on each channel. Mesh points 106 and 108 may select channel 1 and mesh point 118 may select channel 2. Each of these level 1 mesh points may broadcast its own beacon.

Mesh point 122, in turn, may monitor the beacons of its neighboring mesh points 108 and 118. Mesh point 122 may communicate with mesh point 118 via a channel 2 mesh if mesh point 118 has only single channel capability. If mesh point 108 has dual channel capability, then mesh point 122 may choose to communicate with mesh point 108 via a channel 2 mesh. TSs received by mesh point 108 may be received on a channel 2 mesh and may be forwarded to mesh point 102 via a channel 1 mesh.

The mesh point may periodically monitor the channels it is not using and switch channels to improve throughput. Such dynamic load balancing may be performed less frequently to minimize disruption of communications.

Occasionally, a mesh point may use a channel that may not be appropriate for TS traffic flow. The mesh point may scan for other beacons and determine its load. If a suitable alternate channel is found, the mesh point may broadcast a change channel message to its child mesh point (the mesh point providing the TS). The child mesh point may in turn broadcast a change channel request to any of its child mesh points. For example, mesh point 108 may only have single channel capability and may choose to change channels from channel 1 to channel 2. It may broadcast a change request to mesh point 122 (its only child mesh point). Mesh point 122, in turn, may broadcast a change channel message to mesh point 130 (not shown), which is its only child mesh point. Mesh point 108 may wait until the channel change is affected by its child mesh point before making the channel change. Likewise, mesh point 122 may wait until a channel change is affected before making the channel change.

A mesh point with only single channel capability may also be separated from another mesh point if it receives a change channel request and is unable to change channels without the ability to increase channels because the mesh point is communicating with other mesh points via other channels. For example, if mesh point 118 broadcasts a change channel request (to change to channel 1), mesh point 122 may detach from mesh point 118 if it has only single channel capability.

The mesh points may be battery operated or have limited power. These mesh points may have a power save mode. The power save mode may include periods in which the mesh point is "asleep" and not transmitting or receiving information. The mesh point may broadcast the sleep time and duration in its beacon. Mesh points monitoring the beacon may use this information to calculate radio metrics for routing.

A sleeping mesh point may send a trigger at the end of its sleep time. The mesh point may transmit the buffered data packet to the waking mesh point. The routing algorithm may account for increased delay times due to dormant mesh points. If an alternate path is available, the routing algorithm may route TSs around mesh points with power save mode.

Fig. 8 is a flow diagram of a method 800 of TS management at an exemplary mesh point in accordance with an aspect. A mesh point may receive data packets transmitted from one or more mesh points (802). The mesh point may parse the packet and classify the data in the packet according to QoS. The mesh point may place the data in one or more packet queues 804. Each of the packet queues may store data corresponding to a particular QoS. The QoS packet queues may be, for example, high priority or best available. The packet queue may act as a leaky bucket policer (leaky bucket) that stores and buffers data to control the rate of mesh point outgoing data. The mesh point may aggregate data from one or more packet queues into transmit data packets 806.

The mesh point may contend for access to the communication channel (808). Mesh points may adjust their contention access parameters, e.g., AIFS time, CW, in response to a command from another mesh point_min、CW_maxAnd a TxOP duration. After successfully accessing the communication channel, the mesh point may send an MRTS message (810). The M portion of the message may have an ordered list of expected response orders for neighboring mesh points. The mesh point may receive MCTSs from one or more of the neighboring mesh points 812. The mesh point may transmit one or more data packets during its TxOP duration (814). The mp may receive a block acknowledgement in response.

Fig. 9 is a flow diagram of a method of energy conservation at an exemplary mesh point, according to an aspect. The mesh point may transmit its power save mode frequency and duration in a beacon message (902). The mesh point may then enter a power save mode at a predetermined time 904. The power-save mode may prevent the transmission and other functions that use large amounts of energy. The mesh point may resume when a time equal to the power save duration expires (906). The waking mesh point may transmit a trigger message to the neighboring mesh point to alert the neighboring mesh point that it may now transmit to the mesh point (908). The mesh point may receive buffered data packets from neighboring mesh points (910).

Fig. 10 is a flow diagram of a method 1000 of selecting a channel in a multi-channel mesh network according to an aspect. Each mesh point may broadcast a beacon over each channel on which it is operating (1010). For example, a mesh point operating on two channels may transmit a first beacon over a first channel and a second beacon over a second channel. The mesh point may also monitor the communication channel for beacons (1020), which may include load information or other signals. The mesh point may determine the signal strength of each of the received beacons (1030). The beacon message may contain information about the mesh load on the channel. The mesh point may use the mesh load information, signal strength information, or other applicable information to select a communication channel (1040). The mesh point may then transmit over the selected communication channel.

Fig. 11 is a block diagram illustrating exemplary components of an apparatus of a device 1100 for managing traffic flows. One or more modules shown in fig. 11 may be used as components of a means for an apparatus for managing traffic flows. The modules may be implemented using hardware, software, or a combination thereof. One or more modules may be added or deleted depending on the configuration of the apparatus 1100. For example, the devices may be implemented or performed with a general purpose processing device, a digital signal processing Device (DSP), an Application Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, software modules, or any combination thereof designed to perform the functions described herein.

The apparatus 1100 may include: an optional module for receiving 1102 configured to receive a data packet; a module for storing 1104 configured to store data from the data packets into one or more packet queues; a module for aggregating 1106 configured to aggregate data from one or more packet queues into transmit data packets; and a module for transmitting 1108 configured to transmit the transmission data packet during a transmission opportunity duration.

Fig. 12 is a block diagram illustrating exemplary components of an apparatus 1200 for TS management at an exemplary mesh point, according to an aspect. One or more modules shown in fig. 12 may be used as components of a means for an apparatus for managing traffic flows. The modules may be implemented using hardware, software, or a combination thereof. One or more modules may be added or deleted depending on the configuration of the apparatus 1200. For example, the devices may be implemented or performed with a general purpose processing device, a digital signal processing Device (DSP), an Application Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, software modules, or any combination thereof designed to perform the functions described herein.

The apparatus 1200 may include: the apparatus includes means for broadcasting a transmission beacon via a plurality of channels 1202, means for monitoring one or more received signals (e.g., beacons or loads) on the plurality of channels 1204, means for determining a signal strength of the one or more received signals 1206, and means for selecting a channel from the plurality of channels based on the signal strength of the one or more received beacons or loads 1208.

Those of skill in the art would appreciate that the various illustrative logical blocks, modules, circuits, and algorithms described in connection with the aspects disclosed herein may be implemented as electronic hardware, computer software, or combinations of both. To illustrate this interchangeability of hardware and software, various illustrative components, blocks, modules, circuits, and algorithms have been described above generally in terms of their functionality. Whether such interchangeability is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present disclosure.

The various illustrative logical blocks, modules, and circuits described in connection with the aspects disclosed herein may be implemented or performed with a general purpose processing device, a digital signal processing Device (DSP), an Application Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein. A general purpose processing device may be a microprocessor device, but in the alternative, the processing device may be any conventional processing device, microprocessor device, or state machine. A processing device may also be implemented as a combination of computing devices, e.g., a combination of a DSP and a microprocessing device, a plurality of microprocessing devices, one or more microprocessing devices in conjunction with a DSP core, or any other such configuration.

The apparatus, methods, or algorithms described in connection with the embodiments disclosed herein may be embodied directly in hardware, in software, or in a combination of the two. When implemented in software, the method or algorithm may be embodied in one or more instructions that are readable and/or executable by a processing device and stored on a computer-readable medium as part of a computer program product. The instructions may reside in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art. An exemplary storage medium is coupled to the processing device such that the processing device can read information from, and write information to, the storage medium. In the alternative, the storage medium may be integral to the processing device. The processing device and the storage medium may reside in an ASIC. The ASIC may reside in a user terminal. In the alternative, the processing device and the storage medium may reside as discrete components in a user terminal.

The previous description of the disclosed aspects is provided to enable any person skilled in the art to make or use the present disclosure. Various modifications to these aspects will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other aspects without departing from the spirit or scope of the disclosure. Thus, the present disclosure is not intended to be limited to the aspects shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

The present patent application may be embodied in other specific forms without departing from its spirit or essential characteristics. The described aspects are to be considered in all respects only as illustrative and not restrictive, and the scope of the patent application is, therefore, indicated by the appended claims rather than by the foregoing description. All changes which come within the meaning and range of equivalency of the claims are to be embraced within their scope.

Claims (57)

1. A method for managing traffic flows (TSs) at a mesh point in a mesh network, comprising: receiving a data packet from an access point via a wireless transmission;

storing data from the data packets in one or more packet queues;

aggregating data from the one or more packet queues into transmit data packets; and transmitting the transmission data packet during a transmission opportunity duration.

2. The method of claim 1 wherein placing comprises placing the data into one first packet queue storing high quality of service data and a second packet queue storing best available quality of service data.

3. The method of claim 1, further comprising contending for access to a communication channel.

4. The method of claim 1, further comprising adjusting an arbitration interframe space (AIFS) period to control data flow rates.

5. The method of claim 1, further comprising adjusting an arbitration interframe space (AIFS) period to control channel access frequency.

6. The method of claim 1, further comprising adjusting a contention access window to control a data flow rate.

7. The method of claim 1, further comprising adjusting a contention access window to control a channel access frequency.

8. The method of claim 1, further comprising adjusting a transmission opportunity duration to control a data flow rate.

9. The method of claim 1, further comprising adjusting a transmission opportunity duration to control a channel access frequency.

10. A method of managing traffic flows (TSs) between a first mesh point and a second mesh point in a mesh network, comprising:

generating at least one access parameter;

generating, at the first mesh point, a message including the at least one access parameter; and

transmitting the message from the first mesh point to a second mesh point, the message including at least one access parameter for use by the second mesh point.

11. The method of claim 10, wherein the at least one access parameter comprises a transmission opportunity duration, a contention window minimum, a contention window maximum, and an arbitration inter-frame space time.

12. The method of claim 10, wherein the at least one access parameter comprises an average bit rate and a peak bit rate.

13. The method of claim 10, further comprising transmitting an M-request-to-send (MRTS) message.

14. The method of claim 10, further comprising receiving an M Clear To Send (MCTS) message.

15. The method of claim 14, wherein the MCTS message is directed or unguided.

16. A method of selecting a channel at a mesh point, comprising:

broadcasting a transmission beacon via a plurality of channels;

monitoring one or more received signals on the plurality of channels;

determining a signal strength of the one or more received signals; and

selecting a channel from the plurality of channels based on the signal strength of the one or more received signals.

17. The method of claim 16, wherein the transmission beacon has a mesh point identifier.

18. The method of claim 16, wherein the transmission beacon has a value indicating a number of hops to the mesh point.

19. The method of claim 16, wherein the transmission beacon has a value indicating a number of mesh points operating on each of the plurality of channels.

20. The method of claim 16 wherein the mesh point selects a channel corresponding to the received beacon or load with the strongest signal strength.

21. The method of claim 16 wherein the mesh point selects the channel with the least amount of traffic.

22. The method of claim 16, wherein the signal comprises a beacon or a load.

23. A computer program product, comprising:

a computer-readable medium, comprising:

instructions for receiving a data packet;

instructions for storing data from the data packet in one or more packet queues;

instructions for aggregating data from the one or more packet queues into transmit data packets; and

instructions for transmitting the transmission data packet during a transmission opportunity duration.

24. An apparatus for managing traffic flows (TSs) at a mesh point in a mesh network, comprising:

a storage module configured to store data from a data packet in one or more packet queues;

an aggregation module configured to aggregate data from the one or more packet queues into transmit data packets; and

a transmission module configured to transmit the transmission data packet during a transmission opportunity duration.

25. The apparatus of claim 24, wherein the one or more packet queues comprise a first packet queue storing high quality of service data and a second packet queue storing best available quality of service data.

26. The apparatus of claim 24, further comprising a contention module configured to contend for access to a communication channel.

27. The apparatus of claim 24, further comprising an adjustment module configured to adjust an arbitration interframe space (AIFS) period to control data flow rates.

28. The apparatus of claim 24, further comprising an adjustment module configured to adjust an arbitration interframe space (AIFS) period to control channel access frequency.

29. The apparatus of claim 24, further comprising an adjustment module configured to adjust a contention access window to control a data flow rate.

30. The apparatus of claim 24, further comprising an adjustment module configured to adjust a contention access window to control a channel access frequency.

31. The apparatus of claim 24, further comprising an adjustment module configured to adjust a transmission opportunity duration to control a data flow rate.

32. The apparatus of claim 24, further comprising an adjustment module configured to adjust a transmission opportunity duration to control a channel access frequency.

33. The apparatus of claim 24, further comprising a receive module configured to receive the data packet.

34. An apparatus for managing traffic flows (TSs) at a mesh point in a mesh network, comprising:

means for receiving a data packet;

means for storing data from the data packet in one or more packet queues;

means for aggregating data from the one or more packet queues into transmit data packets; and

means for transmitting the transmission data packet during a transmission opportunity duration.

35. The apparatus of claim 34, wherein the one or more packet queues comprise a first packet queue storing high quality of service data and a second packet queue storing best available quality of service data.

36. The apparatus of claim 34, further comprising means for contending for access to a communication channel.

37. The apparatus of claim 34, further comprising means for adjusting an arbitration interframe space (AIFS) period to control data flow rates.

38. The apparatus of claim 34, further comprising means for adjusting an arbitration interframe space (AIFS) period to control channel access frequency.

39. The apparatus of claim 34, further comprising means for adjusting a contention access window to control a data flow rate.

40. The apparatus of claim 34, further comprising means for adjusting a contention access window to control a channel access frequency.

41. The apparatus of claim 34, further comprising means for adjusting a transmission opportunity duration to control a data flow rate.

42. The apparatus of claim 34, further comprising means for adjusting a transmission opportunity duration to control a channel access frequency.

43. An apparatus for selecting a channel at a mesh point, comprising:

means for broadcasting a transmission beacon via a plurality of channels;

means for monitoring one or more received beacons or loads on the plurality of channels;

means for determining a signal strength of the one or more received beacons or loads; and

means for selecting a channel from the plurality of channels based on the signal strength of the one or more received beacons or loads.

44. The apparatus of claim 43, wherein the transmission beacon has a mesh point identifier.

45. The apparatus of claim 43, wherein the transmission beacon has a value indicating a number of hops to the mesh point.

46. The apparatus of claim 43, wherein the transmission beacon has a value indicating a number of mesh points operating on each of the plurality of channels.

47. The apparatus of claim 43, wherein the mesh point selects a channel corresponding to the received beacon or load with the strongest signal strength.

48. The apparatus of claim 43 wherein the mesh point selects the channel with the least traffic.

49. The apparatus of claim 43, wherein the signal comprises a beacon or a load.

50. A computer program product, comprising:

a computer-readable medium, comprising:

instructions for broadcasting a transmission beacon via a plurality of channels;

instructions for monitoring one or more received beacons or loads on the plurality of channels;

instructions for determining a signal strength of the one or more received beacons or loads; and

instructions for selecting a channel from the plurality of channels based on the signal strength of the one or more received beacons or loads.

51. An apparatus for managing traffic flows (TSs) between a first mesh point and a second mesh point in a mesh network, comprising:

means for generating at least one access parameter;

means for generating, at a first mesh point, a message comprising the at least one access parameter; and

means for transmitting the message from the first mesh point to a second mesh point, the message comprising at least one access parameter for use by the second mesh point.

52. The apparatus of claim 51, wherein the at least one access parameter comprises a transmission opportunity duration, a contention window minimum, a contention window maximum, and an arbitration inter-frame space time.

53. The apparatus of claim 51, wherein the at least one access parameter comprises an average bit rate and a peak bit rate.

54. The apparatus of claim 51, further comprising transmitting an M-request-to-send (MRTS) message.

55. The apparatus of claim 51, further comprising receiving an M Clear To Send (MCTS) message.

56. The apparatus of claim 55, wherein the MCTS message is directed or unguided.

57. A computer program product, comprising:

a computer-readable medium, comprising:

instructions for generating at least one access parameter;

instructions for generating, at the first mesh point, a message including the at least one access parameter; and

instructions for transmitting the message from the first mesh point to a second mesh point, the message including at least one access parameter for use by the second mesh point.