Doc.: IEEE 802.11-05/0588r2



IEEE P802.11

Wireless LANs

|Proactive Mesh Network Framework |

|Date: 2005-09-12 |

|Author(s): |

|Name |Company |Address |Phone |email |

|Bing Zhang |National Institute of Information |3-5 Hikaridai, Seika-cho, |+81-774-98-6820 |zhang@nict.go.jp |

| |and Communications Technology |Soraku-gun, Kyoto, Japan | | |

|Oyunchimeg Shagdar |ATR Adaptive Communication Research|2-2-2 Hikaridai, Seika-cho, |+81-774-95-1532 |oyunaa@atr.jp |

| |Laboratories |Soraku-gun, Kyoto, Japan | | |

|Suhua Tang |ATR Adaptive Communication Research|2-2-2 Hikaridai, Seika-cho, |+81-774-95-1544 |shtang@atr.jp |

| |Laboratories |Soraku-gun, Kyoto, Japan | | |

|Youiti Kado |Oki Electric Industry Co., Ltd. |2-5-7 Honmachi, Chuo-ku, Osaka,|+81-6-6260-0700 |kado567@ |

| | |Japan | | |

|Masanori Nozaki |Oki Electric Industry Co., Ltd. |2-5-7 Honmachi, Chuo-ku, Osaka,|+81-6-6260-0700 |nozaki765@ |

| | |Japan | | |

|Number |Category |Name |Coverage |Notes |References |

| | | |(Complete | | |

| | | |/Partial/ None) | | |

|FR1 |TOPO_RT_FWD |Mesh Topology |Complete | | |

| | |Discovery | | | |

|FR2 |TOPO_RT_FWD |Mesh Routing Protocol |Complete | | |

|FR3 |TOPO_RT_FWD |Extensible Mesh |Partial | | |

| | |Routing Architecture | | | |

|FR4 |TOPO_RT_FWD |Mesh Broadcast Data |Complete | | |

| | |Delivery | | | |

|FR5 |TOPO_RT_FWD |Mesh Unicast Data |Complete | | |

| | |Delivery | | | |

|FR6 |TOPO_RT_FWD |Support for Single and|Complete | | |

| | |Multiple Radios | | | |

|FR7 |TOPO_RT_FWD |Mesh Network Size |Complete | | |

|FR8 |SECURITY |Mesh Security |Partial | | |

|FR9 |MEAS |Radio-Aware Routing |Partial | | |

| | |Metrics | | | |

|FR10 |SERV_CMP |Backwards |Complete | | |

| | |compatibility with | | | |

| | |legacy BSS and STA | | | |

|FR11 |SERV_CMP |Use of WDS 4-Addr |Complete | | |

| | |Frame or Extension | | | |

|FR12 |DISC_ASSOC |Discovery and |Complete | | |

| | |Association with a | | | |

| | |WLAN Mesh | | | |

|FR13 |MMAC |Amendment to MAC with |Complete | | |

| | |no PHY changes | | | |

| | |required | | | |

|FR14 |INTRWRK |Compatibility with |Complete | | |

| | |higher-layer protocols| | | |

Table of Contents

1. Executive Summary 6

2. Definitions 6

3. Abbreviations and Acronyms 7

4. Mesh MAC Frame Formats 9

4.1. Mesh Data Frame Format 9

4.2. Mesh Management Frame 9

4.3. Mesh Management Frame Type and Subtype 9

4.4. Specific Management Frame Subtypes 10

4.4.1. Beacon Frame Format 10

4.4.2. Association Request Frame Format 11

4.4.3. Association Response Frame Format 11

4.4.4. Probe Request Frame Format 11

4.4.5. Probe Response Frame Format 11

4.4.6. Action Frame Format 12

5. Proactive Layer-2 Routing Protocol for Mesh Networks 13

5.1. WLAN Mesh Architecture 13

5.2. Topology Discovery 13

5.2.1. Hello Frame Exchange 13

5.2.2. MPR Selection 15

5.2.3. Topology Control Messages 16

5.2.4. Associated Station Address Table 17

5.3. Unicast Routing 18

5.4. Broadcast Routing 19

5.5. Multicast Routing 20

5.6. Routing with Different Metrics 21

5.6.1. Distribution of Link Metrics 21

5.6.2. Routing table calculation 21

5.6.3. Pseudo Flow-based Load Balancing 23

5.6.3.1. Pseudo Flow Management 23

5.6.3.2. Pseudo Flow Table 23

5.6.3.3. Extended Routing Table with the Load Related Metric 24

5.6.4. Selection of Strong Links 25

6. QoS Support for Multimedia Communications 27

6.1. Priority Control 27

6.1.1. Motivation 27

6.1.2. Delay-based Priority Control Schemes 28

6.1.3. Priority Control Scheme based on Number of Hops 28

6.1.4. Priority Control Scheme based on Congestion Condition at Relay MPs 29

6.1.5. Priority Control Scheme based on Time-stamp 31

6.1.6. Mesh Measurement Frame Format Details 32

6.2. Frame Aggregation 34

6.2.1. Motivation 34

6.2.2. Frame Aggregation Schemes 34

6.2.2.1. Tun(Tunneling) Aggregation Scheme 34

6.2.2.2. NH(Next Hop) Aggregation Scheme 35

6.2.2.3. MC(MultiCast) Aggregation (Optional) Scheme 35

6.2.3. Queuing Model 35

6.2.3.1. Push Model with Aggregration Delay 36

6.2.3.2. Pull Model for the Congested Mesh Networks 36

6.2.4. BEANS( Backward Explicit Aggregation Notification Scheme) 36

6.2.4.1. Hybrid Frame Aggregation Scheme 36

6.2.4.2. Frame Aggregation Procedures 37

7. Channel Assignment 39

7.1. Distributed Channel Assignment 39

7.1.1. Motivations 39

7.1.2. Multi Channel Operation in a WLAN Mesh 40

7.1.2.1. Basic Assumption 40

7.1.2.2. Determination of the Common Channel 41

7.1.2.3. Channel Assignment for Non-common Channels 42

7.1.2.4. Global CA (GCA) 45

7.1.2.5. Local CA (LCA) 47

7.1.2.6. Operation after Channel Update 49

7.2. Portal-Driven Channel Assignment 50

7.2.1 Backgrounds 50

7.2.2 Segmentation Strategy 50

7.2.2.1. Channel Assignment by Segmenting 51

7.2.2.2. Channel Assignment at Merger of Mesh 52

8. WLAN Mesh Security 55

8.1 Authentication of Newly Arrived MP 55

8.2 Link Establishment between Neighboring MPs 56

9. Summary 57

References 58

List of Figures

Figure 1 - Data Frame Format. 9

Figure 2 - Mesh Control Field. 9

Figure 3 - Management Frame Format. 9

Figure 4 – Proposed WLAN mesh network model. 13

Figure 5 – Transmission of Hello frame over the WLAN mesh. 14

Figure 6 - The MAC address list of 1-hop and 2-hop neighbors for MP-A, MP-B and MP-D. 14

Figure 7 - Transmission of MPR-adv frames to advertise the MPR set information. 15

Figure 8 – Transmission of TC-adv frame including the links to all MPs of its MPR selector set. 16

Figure 9 – Transmission of ASAT-adv frame 17

Figure 10 - Transmission of the data frame from STA-G to STA-H 18

Figure 11 - Transmissions of broadcast frame from STA-G. 19

Figure 12 – Transmission of multicast frame from MAP-A 20

Figure 13 - Normal TC message with hop count as the metric. 21

Figure 14 - New TC message with metric other than hop count. 21

Figure 15 - Assignment of multiple flows to the same destination. 23

Figure 16 - Emergent Reassignment of a flow to an alternative path. 25

Figure 17 - Assignment of multiple flows with handling multiple channels. 25

Figure 18 – Metric corresponding to RSSI. 26

Figure 19 - Flow performance is highly dependant on number of hops it traverse and congestion condition at its relay MPs. 27

Figure 20 - Priority control scheme based on number of hops (K=2). 29

Figure 21 - Measuring queue length of individual buffers 30

Figure 22 - Information exchange of queue length at each MP 30

Figure 23 - Initializing and updating "delay" field. 32

Figure 24 – An Example of Frame Aggregation 34

Figure 25 – Tunneling Aggregation Frame Format 35

Figure 26 - Next Hop Aggregation Frame Format 35

Figure 27 - Two Queuing Models 36

Figure 28 – Mesh AP with Multiple Queues 37

Figure 29 – Example of Frame Aggregation with Flow 1 38

Figure 30 – Example of Frame Aggregation with Flow 2 38

Figure 31 – Example of Frame Aggregation with Flow 3 38

Figure 32 – Example of Frame Aggregation with Flow 4 38

Figure 33 - An example of CA. 40

Figure 34 - From disconnected network to connected network (with GW). 42

Figure 35 - From disconnected network to connected network (without GW). 42

Figure 36 - Global CA manner and the CA result. 44

Figure 37 - CA steps in Global CA & Local CA 44

Figure 38 - Global CA operation. 46

Figure 39 - An Example of a Mesh Topology. 51

Figure 40 - Flooding Tree from Mesh Portal. 51

Figure 41 - Result of Channel Assingment. 52

Figure 42 - Discretely Formed Networks of a Mesh ID. 53

Figure 43 - Beginning of Mesh Merger. 53

Figure 44 - Result of Mesh Merger. 54

Figure 45 - A connection establishment for a new mesh AP. 55

Figure 46 – The flow chart of the authenticator selection. 56

Figure 47 - Connection reestablishment between the restored mesh portal and mesh network. 57

List of Tables

Table 1 – Valid Type and subtype combinations 9

Table 2 - Valid mesh type and mesh subtype combinations 10

Table 3 – Beacon frame body additions 10

Table 4 – Association Request frame body additions 11

Table 5 – Association Response frame body additions 11

Table 6 – Probe Request frame body additions 11

Table 7 – Probe Response frame body additions 11

Table 8 – Category of action frame field 12

Table 9 - Examples of Pseudo Flow Table (cf. Figure 15) 24

Table 10 - Example of Extended Routing Table ( cf. Figure 15) 24

Table 11 - Example of Extended Routing Table with 2 RF Modules ( cf.Figure 17) 24

Table 12 - Mesh Measurement Frame Format 32

Table 13 - New elements in the beacon frame 41

Table 14 - Modified hello message 43

Table 15 - New frame format for CA 43

Executive Summary

This document describes a full proposal for a proactive, flexible, compatible and secure 802.11s WLAN mesh network. The proposal provides a framework for a WLAN mesh network with the wireless multihop communication between mesh access points, which accommodate the legacy stations associated with them. Here, we recommend to use a proactive routing protocol, for the reason that the mesh access points are generally considered to have the low mobility and the network scale is moderate (the maximum size is expected to be about 32), and then the problem of the overhead is not remarkable, to keep a routing before a transmission starts. The document specifies a layer-2 proactive routing with strong links and flow-based load balancing; QoS support mechanism, frame aggregation scheme especially for VoIP application, channel assignment for supporting multiple radios, and finally security system. This proposal is intended to provide a broad deployable system with diverse applications such as residential, office, campus/community/public access networks, and public safety.

Definitions

1. WLAN Mesh – A WLAN Mesh is an IEEE 802.11-based WDS which is part of a DS, consisting of a set of two or more Mesh Points interconnected via IEEE 802.11 links and communicating via the WLAN Mesh Services. A WLAN Mesh may support zero or more entry points (Mesh Portals), automatic topology learning and dynamic path selection (including across multiple hops).

2. WLAN Mesh Services – The set of services provided by the WLAN Mesh that support the control, management, and operation of the WLAN Mesh, including the transport of MSDUs between Mesh Points within the WLAN Mesh. WLAN Mesh Services supplement DSS (Distribution System Services).

3. Mesh Point – Any IEEE 802.11 entity that contains an IEEE 802.11–conformant Medium Access Control (MAC) and Physical Layer (PHY) interface to the Wireless Medium (WM), is within a WLAN Mesh, and supports WLAN Mesh Services.

4. Mesh AP – Any Mesh Point that is also an Access Point.

5. Mesh Portal - A point at which MSDUs exit and enter a WLAN Mesh to and from other parts of a DS or to and from a non-802.11 network. A Mesh Portal can be collocated with an IEEE 802.11 portal.

6. Mesh Link - A direct IEEE 802.11 link between two Mesh Points.

7. Mesh Path - A concatenated set of connected Mesh Links from a source Mesh Point to a destination Mesh Point.

8. Mesh Path Selection – The process of selecting Mesh Paths.

9. Path Metric –Criteria used for Mesh Path Selection.

10. Mesh Topology – A graph consisting of the full set of Mesh Points and Mesh Links in a WLAN Mesh.

11. Mesh Neighbor - Any Mesh Point that is directly connected to another Mesh Point with a Mesh Link.

12. Mesh Unicast - Frame forwarding mechanism for transporting MSDUs to an individual Mesh Point within a WLAN Mesh.

13. Mesh Multicast - Frame forwarding mechanism for transporting MSDUs to a group of Mesh Points within a WLAN Mesh.

14. Mesh Broadcast - Frame forwarding mechanism for transporting MSDUs to all Mesh Points within a WLAN Mesh.

Abbreviations and Acronyms

|Term |Description |

|AP |Access Point |

|ASAT |Associated Station Address Table |

|CA |Channel Assignment |

|CAS |Channel Sequence Number |

|CC |Control Channel |

|CI |Control Interface |

|CRC |Cyclic Redundancy Check |

|CTS |Clear to Send |

|DC |Data Channel |

|DI |Data Interface |

|EAPOL |Extensible authentication protocol over LAN (aka 802.1X) |

|ESS |Extended Service Set |

|FCS |Frame Check Sequence |

|IE |Information Element |

|LLC |Logical Link Control |

|MAC |Medium Access Controller |

|MMPDU |MAC Management Protocol Data Unit |

|MP |Mesh Point |

|MPDU |MAC Protocol Data Unit |

|MPT |Mesh Portal |

|MPR |Multi Point Relay |

|MSDU |MAC Service Data Unit |

|MT |Mesh Type |

|MST |Mesh Sub Type |

|NAV |Network Allocation Vector (a MAC-level carrier-sense) |

|PHY |Physical Layer |

|QC |QoS Control |

|QoS |Quality of service |

|RSSI |Receive Signal Strength Indicator |

|RTS |Request to send |

|RX |Receiver |

|SAP |Service Access Point |

|SN |Sequence Number |

|SSID |Service Set Identifier |

|STA |Station |

|TBC |To be confirmed |

|TBD |To be determined |

|TGe |802.11 Task Group e - Quality of Service |

|TTL |Time to Live |

|TX |Transmitter |

|TXOP |Transmission Opportunity |

|WDS |Wireless Distribution System |

Mesh MAC Frame Formats

1 Mesh Data Frame Format

The proposed data frame format for the ESS mesh is defined in Figure 1. The QC field provided by 802.11e and MC field specified by the ESS mesh is added to the regular WDS frame. The unit of the field is an octet.

|2 |2 |6 |6 |

|MT |MST |TTL |SN |

Figure 2 - Mesh Control Field.

2 Mesh Management Frame

The management frame format for the ESS mesh is described in Figure 3. The maximum number of address is 3. Similarly to the data frame, the MC field is also added.

|2 |2 |6 |6 |

|00 |Management |1110 |For Mesh management |

|01 |Control |0000 |For Mesh control |

|10 |Data |1101 |For Mesh data |

To specify the more detailed subtypes of management frames for the ESS mesh, the MT included in the MC field shown in Figure 2, can be referred to define the detailed mesh types and subtypes. Table 2 shows a list of mesh type and subtype to define the routing-related control frame, probe frame, beacon frame, action frame, etc.

Table 2 - Valid mesh type and mesh subtype combinations

|Mesh type value |Type description |Mesh subtype value |Subtype description |

|b3 b2 | |b7 b6 b5 b4 | |

|00 |Management |0000 |Association Request |

|00 |Management |0001 |Association Response |

|00 |Management |0010 |Probe Request |

|00 |Management |0011 |Probe Response |

|00 |Management |0100 |Beacon |

|00 |Management |0101 |Disassociation |

|00 |Management |0110 |Hello |

|00 |Management |0111 |MPR Advertisement |

|00 |Management |1000 |TC Advertisement |

|00 |Management |1001 |ASAT Advertisement |

|00 |Management |1010 |Action |

|00 |Management |1011 – 1111 |Reserve |

|01 |Control |0000 – 1111 |Reserve |

|10 |Data |0000 |WDS Unicast |

|10 |Data |0001 |WDS Broadcast |

|10 |Data |0010 |WDS Multicast |

|10 |Data |0011 |WDS Tun-Agg Unicast |

|10 |Data |0100 |WDS NH-Agg Unicast |

|10 |Data |0101 – 1111 |Reserve |

|11 |Reserve |0000 – 1111 |Reserve |

3 Specific Management Frame Subtypes

The following subsections specify the details of management frame subtypes, which is included in the frame body of the IEEE802 standard management frame.

1 Beacon Frame Format

Table 3 – Beacon frame body additions

|Information |Note |

|Mesh Capability Info |Mesh capability information. |

| |E.g. Mesh Point or Mesh Access Point |

|Mesh ID |An identifier of mesh network. |

|RF Info |RF channel information. |

| |E.g. Number of RF devices, channel selection, etc |

|Power Info |Available transmission power. |

| |E.g. Battery or fixed power supply |

|Routing Info |Routing parameters. |

| |E.g. Metric, routing protocol, etc. |

|Multicast Info |Multicast group information. |

| |E.g. MAC address of multicast group leader. |

2 Association Request Frame Format

Table 4 – Association Request frame body additions

|Information |Note |

|Mesh Capability Info |Mesh capability information. |

| |E.g. Mesh Point or Mesh Access Point |

|Mesh ID |An identifier of mesh network. |

|RF Info |RF channel information. |

| |E.g. Number of RF devices, channel selection, etc |

|Power Info |Available transmission power. |

| |E.g. Battery or fixed power supply |

3 Association Response Frame Format

Table 5 – Association Response frame body additions

|Information |Note |

|Mesh Capability Info |Mesh capability information. |

| |E.g. Mesh Point or Mesh Access Point |

|Mesh ID |An identifier of mesh network |

4 Probe Request Frame Format

Table 6 – Probe Request frame body additions

|Information |Note |

|Mesh ID |An identifier of mesh network |

5 Probe Response Frame Format

Table 7 – Probe Response frame body additions

|Information |Note |

|Mesh Capability Info |Mesh capability information. |

| |E.g. Mesh Point or Mesh Access Point |

|Mesh ID |An identifier of mesh network |

|RF Info |RF channel information. |

| |E.g. Number of RF devices, channel selection, etc |

|Power Info |Available transmission power. |

| |E.g. Battery or fixed power supply |

|Authentication Info |Authentication method information. |

6 Action Frame Format

Table 8 – Category of action frame field

|Category |Command |Note |

|Mesh Measurement |Request |Collection of statistic information. |

| | |E.g. Round trip time, BER, frame loss rate, etc |

| |Report |Statistic information reports. |

|Channel Assignment |Request |Request to assign channel. |

| |Reply |Success or Failure. |

| |Global CA |Assign channels for all the links, initiated by GW. |

|Multicast |Advertisement |Multicast group leader (ex. Mesh Portal) advertises the address table of |

| | |multicast group member to all MPs. |

| |Join request |Request to join in multicast group. |

| |Join reply |OK or NG. |

| |Depart request |Request to quit from multicast group. |

| |Depart reply |OK or NG. |

Proactive Layer-2 Routing Protocol for Mesh Networks

Many layer-3 routing protocols have been proposed for wireless multi-hop communications [1]-[2]. Based on the route discovery methods, they can be mainly classified into reactive and proactive routing protocols. Because the mesh APs are generally considered to have the low mobility and the scale of mesh network is moderate (Maximum size is 32), the proactive routing is more beneficial, and its overhead is also tolerant. Here, we propose a proactive layer-2 routing protocol for mesh networks, which build a globally optimal route for each destination, and adapts to the topology variation. The features of our proposed scheme are, (a) accommodating the legacy stations associated with Mesh APs, (b) building the topology of the whole network by exchanging the neighbor information and topology control information, (c) optimizing the route with different link metrics, such as RSSI strength and load balance, (d) supporting the WDS unicast/multicast/broadcast.

1 WLAN Mesh Architecture

The topology for WLAN mesh network is illustrated inFigure 4. MPs in the WLAN mesh are connected based on a layer-2 proactive routing, to achieve a multi-hop communication. The interference between channels is decreased by allocating the different channels to the connections of MPs, Mesh APs and Legacy STAs. In order to alleviate the throughput degradation due to the multi-hop communication, the connections between Mesh APs can be connected with two or more channels.

Figure 4 – Proposed WLAN mesh network model.

2 Topology Discovery

1 Hello Frame Exchange

The Hello message is periodically exchanged over MPs for the neighborhood detection, as shown in Figure 5. The format of Hello frame is specified by the proposed mesh management format in section 4.3. MP-D (denoted as Mesh AP-D in Figure 4) sends the Hello frame denoted as (1) in Figure 5, by setting DA to the broadcast address (FF:FF:FF:FF:FF:FF) and SA to the MAC address of MP-D. The 1-hop neighbor information of MP-D is involved in the MAC frame body. In the case where no neighbor MP is detected, the null data is transmitted. Similarly to MP-D, MP-B and MP-A periodically broadcast the Hello frames of (2) and (3), respectively. Upon receiving the Hello frame from MP-D, MP-B adds the MAC address of MP-D to its 1-hop neighbor list. Every MP can acquire the MP information that is included in the 1-hop neighbor list of its neighbor, but not included in itself 1-hop neighbor list. Then, MP adds this information into its 2-hop neighbor list. For example, MP-D detects MP- B and C as 1-hop neighbors, and adds MP-E, A and F into 2-hop neighbors. By exchanging the Hello frames, 1-hop neighbor address list and 2-hop address list for every MP in Figure 4 can be obtained. Figure 6 shows the list of 1-hop and 2-hop neighbors for MP-A, MP-B and MP-D.

[pic]

Figure 5 – Transmission of Hello frame over the WLAN mesh.

[pic]

Figure 6 - The MAC address list of 1-hop and 2-hop neighbors for MP-A, MP-B and MP-D.

2 MPR Selection

MP determines the OLSR (Optimized Link State Routing) based MPR (Multipoint Relay) set to retransmit all the broadcast frames. MPR can be calculated through the 1-hop neighbors, which can reach all symmetric 2-hop neighbors. For example (see Figure 4), when MP-D forwards the broadcast frames, MP-B and MP-C are candidates to flood the frames. In the case of MP-C selected as MPR set, to reach MP-A and MP-E in the 2-hop neighbor of MP-D, the hop number is 1 and 2, respectively. In the case of MP-B selected as MPP set, to reach both of MP-A and MP-E, the hop number is one. Thus, the number of retransmissions by MP-B is smaller than by MP-C, and then MP-B should be selected as MPR set of MP-D. The OLSR-based MPR also can be calculated based on the willingness of MP to do as a MPR. MPs advertise their MPR information in the periodic Hello frames denoted as MPR-adv frame in Figure 7. To do this, MP sets DA as the broadcast address, SA as itself MAC address, and involves the MPR information in the frame body of MPR-adv frame. Upon receiving this broadcast frame, neighbor MP adds the MAC address of SA in MPR-adv frame to its MPR selector set, if itself MAC address is not included in the MPR set written in the frame body. For example, upon receiving the MPR-adv frame from MP-D, MP-B adds the MAC address of MP-D to its MPR selector set if its MAC address is involved in the MPR set written in the frame body of MPR-adv. Then, MP-B retransmits the broadcast frame from MP-D to its MRP selector set.

[pic]

Figure 7 - Transmission of MPR-adv frames to advertise the MPR set information.

3 Topology Control Messages

To advertise the links to all MPs of its MPR selector set, MP generates a TC (Topology Control) frame disseminated to the entire network, shown in Figure 8. For example, upon receiving the TC-adv frame from MP-D denoted as (1) in Figure 8, MP-B holds a table including the links to all MPs of its MPR selector set based on the frame body, and then forwards it by resetting TA from the MAC address of MP-D to the MP-B’s one, denoted as (2). In this way, MP can take the MPR selector set information of all MPs based on the periodic TC-adv frame transmission, to build the whole network topology. Based on the network topology information, the optimal routing to all MPs can be obtained, which is kept in the OLSR-based routing table. Note that SA in the TC-adv frame header is fixed to the address of MP-D in Figure 8, which is the originator address of MPR selector set information. When the address 3 of management is used to express the other address such as Mesh ID, shown in Figure 3, etc. the originator address for the MPR selector set information can be included in the frame body.

[pic]

Figure 8 – Transmission of TC-adv frame including the links to all MPs of its MPR selector set.

4 Associated Station Address Table

Because the routing table does not include the route information to the legacy STA associated with Mesh APs, the information which mesh AP is associated with, is needed. Here, we propose that mesh AP generates an ASAT (Associated Station Address Table) frame, which records a MAC address table of legacy STAs associated with it. Figure 9 describes the transmission of ASAT frame to advertise the ASAT information, by setting DA to the broadcast address, and TA and SA to itself MAC address. For example, upon receiving the ASAT frame from MP-D, MP-B takes the ASAT information of MP-D based on the frame body, and adds this information to its ASAT (see Figure 9). Due to MP-B selected as the MPR selector set of MP-D, it forwards the ASAT frame to the neighbors, denoted as (1). Thus, mesh AP can obtain the ASAT information of all mesh AP by flooding the ASAT frames. Based on the ASAT, the routing table can be obtained to forward the frame destinated to the STA to the associated mesh AP.

[pic]

Figure 9 – Transmission of ASAT-adv frame

3 Unicast Routing

Figure 10 shows the procedures how the frame from a STA can be forwarded to another STA based on the routing and association tables kept by every MP. In (1), STA-G sends a data frame by setting DA to the MAC address of STA-H, SA to the MAC address of STA-G, BSSID to MAC address of mesh-AP-D. In (2), upon receiving the frame from STA-G, mesh-AP-D learns that STA-H is associated with mesh-AP-A from its ASAT, and then forwards this frame to mesh-AP-B based on its routing table. In (3), similarly with (2), mesh-AP-B forwards the frame to mesh-AP-A by setting RA to mesh-AP-A, TA to mesh-AP-B. In (4), mesh-AP-A detransforms the WDS frame into the frame of infra-mode, and finally sends it to STA-H.

[pic]

Figure 10 - Transmission of the data frame from STA-G to STA-H

4 Broadcast Routing

Figure 11 shows the procedures how the frame from STA-G can be broadcasted to all STAs. First, STA-G sends the frame of (1) by setting DA to the broadcast address, SA to itself MAC address and BSSID to the MAC address of mesh-AP-D. Upon receiving the frame from STA-G, mesh-AP-D then broadcasts the frame of (2) to all neighbor MPs by setting TA to the MAC address of mesh-AP-D, and the frame of (3) to all STAs associated with it, by setting BSSID to the MAC address of mesh-AP-D. Due to mesh-AP-B selected as the MPR of mesh-AP-D, it broadcasts the frame of (4) to all neighbor MPs by setting TA to the MAC address of mesh-AP-B, and the frame of (5) to all STAs associated with it, by setting BSSID to the MAC address of mesh-AP-B. Finally, mesh-AP-A broadcasts the frame of (6) to all STAs associated with it, by setting BSSID to the MAC address of mesh-AP-A.

[pic]

Figure 11 - Transmissions of broadcast frame from STA-G.

5 Multicast Routing

To deliver the multicast frames, it is necessary to make a management table recording a list of the MAC address of MPs belonging to the multicast group. This management table is maintained by the multicast group leader, such as Mesh Portal, and broadcasted periodically on the whole network. Thus, the information of the multicast group can be shared by each MP in the mesh network. When MP wants to participate in the multicast group, it sends a control frame of "Join Request" to the group reader. Upon receiving the control frame of “Join Request”, the group leader determines whether the MP may participate in the group. In the case where the request for participation is not permitted for some reasons such as the restriction of the number of group member, the group leader notifies it by unicasting a control frame of “Join Reply”. In another case where the request for participation is permitted, the multicast group leader notifies to all MPs in the networks by broadcasting the control frame of “Join Reply”. MP that receives the control frame of "Join reply" updates its management table including the MAC address list of the multicast group members. Based on the management table of multicast group hold by each MP, when MP receives the multicast WDS frames, it can know whether to forward it or not. Figure 12 shows the transmission of multicast frames from MAP-A to the multicast group members MAP-B, D and G.

[pic]

Figure 12 – Transmission of multicast frame from MAP-A

By referring to the multicast management table, routing table and ASTA, respectively, each MP retransmits the received multicast frame if the multicast member is located in the area where it can be connected with number of hops. When MP wants to quit from the multicast group, it sends a control frame of "Depart request" to the group reader. Similarly to the participation in the multicast group, the group leader notifies the permission or no permission of secession by sending a control frame of “Depart reply”.

6 Routing with Different Metrics

1 Distribution of Link Metrics

By default, hop count is used as the routing metric. But hop count can not actually reflect the cost of forwarding packets. Some other metrics are necessary. In order to use link metrics other than hop count, each MP in the network has to monitor the link status and map some kinds of link quality into link metric. The link status includes traffic load over a link, the average delay of the transmission of a packet by the link, the instantaneous RSSI of the link, In general, OLSR TC message only carries the link state entry. In order to distribute the link metric together with the topology, a flag in TC message reflects what kind of link metric is being used. All the MPs must agree to use the same link metric.

|Message Size |Time To Live |Metric type=HOPCOUNT |

|Advertised Neighbor Main Address1 |

|Advertised Neighbor Main Address2 |

Figure 13 - Normal TC message with hop count as the metric.

|Message Size |Time To Live |Metric type | |

|Advertised Neighbor Main Address1 |Metric1 |

|Advertised Neighbor Main Address2 |Metric2 |

Figure 14 - New TC message with metric other than hop count.

2 Routing table calculation

• Initial conditions:

Topology table ttable, each topology entry, te, has three important members:

te->originator, the originator of the message

te->neighbor[i], the ith neighbor of the originator

te->linkmetric[i], the link metric between the originator and its ith neighbor

• Procedures for calculating the routing table rtable

1. All the entries in rtable are removed.

2. Find te in ttable so that te->originator equals self address, add self address to rtable as rt with rt->metric 0, set rt->processed flag to true.

3. For each neighbor te->neighbor[i] with a flag SYM or MPR

add {dst=te->neighbor[i], next= te->neighbor[i], metric=te->linkmetric[i]} to rtable

set rt->interface to the interface through which te->neighbor[i] is reachable.

4. find rtm with the minimum metric among the routes with processed flag not set.

5. If (rtm == NULL) rtable is calculated, end;

6. Find in ttable the entry, te, te->originator == rtm->dst

7. For each neighbor in the topology entry, te->neighbor[i] with a flag SYM or MPR

newmetric = rtm->metric + te->linkmetric[i]

find the route entry rt in rtable, rt->dst == te->neighbor[i]

if (!rt)

add {dst=te->neighbor[i], next= rtm->next, metric=newmetric} to rtable

set rt->interface to the interface through which rtm->next is reachable

else if (rt->metric >= newmetric)

replace rt with {dst=te->neighbor[i], next= rtm->next, metric=newmetric}

set rt->interface to the interface through which rtm->next is reachable

8. Set rtm->processed flag to be true.

9. Go to step 4

3 Pseudo Flow-based Load Balancing

Since every traffic flow over the WLAN Mesh tends to choose the same minimum hop route, it then results that some MPs / links are heavily loaded. Those MPs / links have a high risk to become congested, and hence the quality of the corresponding traffic is degraded. To solve this problem, dissolving the concentration by dispersing the load is needed.

1 Pseudo Flow Management

The load dispersing can be performed by forming multiple paths from an MP to a destination MP. However, if load is balanced by dispersing per packet toward the multiple paths irrespective of the each service traffic flow, the packet arrival in the same flow may be disordered. Thus, the mechanism of keeping the packets of the same flow in order is favourable. Though a certain traffic flow cannot be exactly discriminated with the MAC frame header, a flow can be roughly identified with a pair of “Source Address” and “Destination Address” or a pair of “Transmitter Address” and “Destination Address” in the WDS frames (see Table 9). Here, we call the flow identified with the above method as “Pseudo Flow” The Pseudo Flow is managed by assigning the Pseudo Flows to a path based on the monitor of Pseudo Flow load. Once the allocation of a Pseudo Flow to a path is finished, it is considered to be unchanged as long as the Pseudo Flow is active (i.e. packets flow through the Pseudo Flow), to keep the packet of the same flow in order. Figure 15 shows how to assign multiple flows of f2 and f3 to the same destination. The f1 and f2 already exit, and the load of f2 is heavier than f1. When a new flow of f3 comes, the same path with the flow of f2 is usually chose, when the routing metric is calculated only by hop count. In our scheme, a different path with f2 can be selected by using the load related metric.

[pic]

Figure 15 - Assignment of multiple flows to the same destination.

2 Pseudo Flow Table

A Pseudo Flow is identified with a pair of “Source Address” and “Destination Address” or a pair of “Transmitter Address” and “Destination Address” in the WDS frame (see Table 9). Using such an identifier, the load of the Pseudo Flow can be monitored.

Table 9 - Examples of Pseudo Flow Table (cf. Figure 15)

Type 1 Type 2

|PF Index |SA |DA |load | |

|p1 |3 |7 |9 |f1 |

|p2 |4 |7 |13 |f3 |

|p3 |4 |10 |12 |f2 |

To measure the load, we can monitor the lengths of every intermediate MP’s buffer queues, or count the number of frames from the current MP to the destination MP. Main triggers to update the Extended Routing Table are the activation of a Pseudo Flow and the detection of inactivity of a Pseudo Flow. Additionally, when the resource like buffer on a certain path is seriously exhausted, it should also become a trigger. Such exhaustion occurs as a result of the increase of some Pseudo Flows’ load and it means a risk (or a fact) of congestion in the path. It should become a trigger of Emergent Reassignment. Figure 16 shows this Emergent Reassignment case where the Pseudo Flow f4 from MP-9 to MP-10 already assigned to the path of p3 from MP-0 to MP-10 through MP-4. When the Pseudo Flow f4’s traffic increases, it then results in a critical tightness of resources on the path p2 and p3. Since Pseudo Flow f3 from MP-9 to MP-7 has an alternative path of p1 whose resource is not tight yet, the Pseudo Flow f3 can be reassigned to the path of p1 from MP-0 to MP-7 through MP-3.

When two or more RF modules are used by some MPs, for example two RF modules are used on a link between MP-0 and MP-4, pathes are identified by more indexes in addition to the channel information (see Table 11).

Table 11 - Example of Extended Routing Table with 2 RF Modules ( cf.Figure 17)

|Path Index |RA |DA |channel |load metric |assignment |

|p1 |3 |7 |0 |9 |f1 |

|p2 |4 |7 |0 |6 | |

|p3 |4 |7 |1 |7 |f3 |

|p4 |4 |10 |0 |5 | |

|p5 |4 |10 |1 |7 |f2 |

[pic]

Figure 16 - Emergent Reassignment of a flow to an alternative path.

[pic]

Figure 17 - Assignment of multiple flows with handling multiple channels.

4 Selection of Strong Links

When hop count is used as the path metric in the wireless mesh networks, the routes tend to have a short hop count and contain weak links. High PER of weak links causes retransmissions, which consume bandwidth. In addition, it takes much more time for the weak links to transmit a packet at a low communication rate. As a result, the weak links become the bottleneck of a route. This adversely affects Communications over other strong links sharing the same wireless channel. Hence, the throughput of the whole network is degraded.

When OLSR routing protocol is running, each MP periodically exchanges the hello packet. Upon receiving a hello packet, an MP knows the RSSI for the current link. If the RSSI is very weak, the weak link is substituted by some other link. In order to select the strong links, RSSI can be divided into several non-overlapping range, each mapping to one link metric, with the big RSSI corresponding to smaller link metric, as shown in the Figure.

[pic]

Figure 18 – Metric corresponding to RSSI.

QoS Support for Multimedia Communications

1 Priority Control

1 Motivation

Multimedia applications require the QoS (Quality of Service) support, which is a challenging task over wireless networks. The DCF channel access scheme of the IEEE802.11 LAN standard [3] tries to provide the channel access with equal probabilities to all stations contending for the channel access in a distributed manner. However, equal access probabilities are not desirable among stations with different priority flows (traffics). Therefore, Task Group E introduces the Enhanced Distributed Channel Access (EDCA) [4], which is an extended DCF for QoS enhancement.

Although the EDCA provides differentiated service to flows with different priorities, it suffers from inability to provide fair-service to the flows that have an equal priority, especially when the network is characterized by a multi-hop wireless topology. This can be explained as follows. With the EDCA, a single MAC has multiple queues that work independently, in parallel, for different priorities. As a result, frames with a higher priority can get a higher chance in accessing to the channel compared to frames with a lower priority. On the other hand, the frames that have the equal priority are inserted to the same FIFO buffer in MPs, and thus have the equal chance on accessing to the channel. However, it does not mean that the flows with the same priority can achieve the equivalent performance. For example, if we consider delay-sensitive traffics, having the same priority in the EDCA protocol does not mean that they can obtain the equivalent delay for all traffics. This is because end-to-end delay of a frame is highly dependant on the number of hops it traverses and the congestion-condition at its relay MPs.

Here, we consider an example shown in Figure 19. Four VoIP flows exist in the nine-MP mesh topology. As the flows are in the same type of traffics, all the frames have the equal chance on accessing to the channel.

[pic]

Figure 19 - Flow performance is highly dependant on number of hops it traverse and congestion condition at its relay MPs.

Let us compare delay characteristics of Flow1 and Flow2. Flow1 is relayed three times until it reaches its destination whereas Flow2 is relayed only once. Therefore, Flow1 may get longer end-to-end delay compared to Flow2 does. Obviously, if difference of the number of hops is very large, it may even result to the situation that Flow1 is not be able to meet its delay requirements, but Flow2 reaches its destination with time to spare. This could be the critical QoS issue in a mesh network because of its multi-hop nature. Now, let us consider of Flow3 and Flow4. Although both flows traverse two hops, Flow3 may get a longer end-to-end delay compared to Flow 4 gets. This is because Flow3 is relayed by MP-5 which already has two more flows (Flow2, Flow1) in addition to Flow3. Therefore, compared to Flow4, frames of Flow3 would be kept longer in the MP-5’s buffer, because of its congested condition. Again, this problem could be the issue in multi-hop mesh networks.

From the examples above, it is clear that the end-to-end delay characteristic of a flow is highly dependant on the number of hops and/or the congestion condition at its relay MPs. It is obvious that these QoS issues will be left unsolved even IEEE 802.11e technique is applied to mesh networks. To extend the IEEE 802.11e EDCA techinique, we introduce several schemes to provide delay-based priority control among flows that have the same priority in the IEEE 802.11e.

2 Delay-based Priority Control Schemes

In this section, we describe three delay-based priority control schemes to enhance the IEEE 802.11e EDCA scheme for flows, that are in the same AC (access category). The first scheme is based on the number of hops; which then is the simplest among the three. Opposed to it, the second and third proposed schemes, which are based on congestion condition at relay nodes and time-stamp, respectively, require additional information exchange among nodes. Note that we here do not consider flows that are in different access categories in the EDCA. In this case, the EDCA MAC network is equivalent to the DCF MAC network where all the nodes have a single FIFO buffer on their MAC layer.

3 Priority Control Scheme based on Number of Hops

As it is mentioned earlier, larger the number of hops is longer the end-to-end delay. Therefore, we propose a scheme that enables relay MPs (including source MPs) to provide priority control among flows based on number of hops they traverse. The priority control scheme takes the following steps, shown in Figure 20.

1) An MP becomes ready to send a frame from a certain buffer.

2) The MP checks number of hops for the first K frames in the buffer, where K is an integer (K>0). Here, number of hops can be defined as the number of hops the frame traverses either a) from the node itself to the destination or b) from the source to the destination (end-to-end). Depending on which way is in use, the MP knows number of hops corresponding to a frame as follows.

a) By referring the destination address on the frame’s header, the MP gets the number of hops from itself to the destination node from the routing table.

b) By referring the addresses of the source and the destination on the frame’s header, the MP calculates the end-to-end number of hops by adding the number of hops from itself to the destination and from itself to the source.

3) The MP compares the values of number of hops for the first K frames in the buffer.

4) The node sends the frame which has the largest number of hops value.

Figure 20 - Priority control scheme based on number of hops (K=2).

4 Priority Control Scheme based on Congestion Condition at Relay MPs

Although the previous scheme does not require any extra information exchange among MPs, it does not consider congestion condition at relay MPs. Here, we describe another scheme based on congestion condition at relay MPs. Congestion condition at an MP is measured by the mean queue length of its buffers. The mean queue length of a buffer is measured periodically at each MP and broadcasted throughout the network. The mechanism to measure congestion condition for a buffer is as follows.

1) In every time period τ, the MP measures the average queue length of each buffer.

2) If the buffer has been empty for the time period τ, the queue length is set to zero.

In this way, each MP measures queue length for its individual buffers (see Figure 21).

[pic]

Figure 21 - Measuring queue length of individual buffers

The priority control scheme takes the following steps.

1) In order to exchange information on congestion condition at each relay MP, a “cumulative queue length” field is created on routing table at each MP.

2) After measuring queue length of each buffer, MPs create mesh measurement frames (refer to 6.1.6 for the frame format) and broadcast them throughout the network for information exchange.

3) When a MP received queue length information from its neighbor MP, it further forwards the frame after updating the information of the congestion condition of the neighbour node.

4) By repeating the step 3) throughout the network, it enables each MP to know the congestion condition of any other MP in the network.

5) When a MP determines a route to any destination in the network, it calculates the cumulative queue length corresponding to the route (see Figure 22), by summing up all the queue lengths at each relay MPs on the path. The calcuted value is set in the “cumulative queue length” field of its routing table.

[pic]

Figure 22 - Information exchange of queue length at each MP

Finally when an MP is ready to send a frame from a buffer, it follows the steps below.

1) Becomes ready to send a frame from a specific buffer.

2) Checks the cumulative queue length field on the routing table for the first K frames in the buffer.

3) Sends the frame which has the longest cumulative queue length.

5 Priority Control Scheme based on Time-stamp

We consider a priority control scheme based on time-stamp. End-to-end delay for a traffic is estimated by using mesh measurement frames. Transmitter MPs of the traffic perform delay-based priority control based on this measurement result. As shown in Figure 23-(a), creating a measurement frame and updating process is performed with the following steps.

1) The source MP originates a mesh measurement frame, where the command field is set to 0 (a request frame), the element field is set to 1 and the delay field is set to 0 (refer to 6.1.6 for the frame format).

2) The source inserts the frame to its appropriate buffer.

3) When the source is ready to send the frame, it updates the field by the sojourn time of the frame in its buffer. Each relay MP of the frame updates the delay field by adding sojourn time of the frame in their buffer to the previous value of the delay field (see Figure 23).

The sojourn time of a frame at a transmitter MP is calculated as 4)-5).

4) Each transmitter MP (including the source MP) records the mesh measurement frame’s arrival time (arrival_time), when it receives the frame.

5) The “delay” field is updated at each transmitter by addition of the difference value between the current time denotes as current_time and arrival_time”, just before the frame being sent out (see Figure 23-(b)). The value calculated with “current_time-arrival_time” represents sojourn time of the frame in the buffer.

It is obvious that delay value of the frame at any transmitter indicates the time cost for the frame from the source to the transmitter. Therefore, when the previous steps have been performed until a transmitter MP, the MP would only know the delay of the frame from the source MP to itself. For delay-based priority control, the transmitter MPs may need to know the end-to-end delay of a frame. In order to enable transmitter MPs to know the end-to-end delay of the path, a report frame is created and used as follows.

6) After steps 4) and 5) have been performed at each transmitter MP, the request frame reaches its destination MP with a cumulative delay record that indicates the end-to-end delay of the path.

7) When the destination MP receives the request frame, it creates a report frame, where command field is set to 1, element field is set to 1 and the delay field is set to a copy of the delay field of the correspondent request frame. After creating the report frame, the destination MP sends the frame back to source MP of the request frame.

8) When the report frame arrives at a transmitter MP, the MP keeps a copy of the end-to-end delay value of the report frame and forwards the report frame to the source MP of the request frame.

[pic]

Figure 23 - Initializing and updating "delay" field.

From steps (1)-(7), any transmitter MP on a path learns (a) the end-to-end delay from the delay field of a report frame, and (b) the delay from the source MP to itself from a request frame. Therefore, delay from the MP to the destination can be calculated as the difference between the delay values (a) and (b).

Finally when an MP is ready to send a frame, it takes the following steps.

1) Ready to send a frame from a particular buffer

2) Compares delay values of the first K frames in the buffer

3) Sends the frame which has the longest delay

6 Mesh Measurement Frame Format Details

In 6.1.4 and 6.1.5, MPs exchange information (queue length and delay) to perform delay based priority control. For these information exchanges, action frames of mesh measurement category are used. Table 12 shows the frame body format of the mesh measurement frame (refer to subsection 4.4.6 about action frame).

Table 12 - Mesh Measurement Frame Format

|Category (2 bits) |Command (4 bits) |TID (4 bits) |Element (2 bits) |Value (4 octets) |

|0 (Mesh Measurement) |0 (Request) |TID |0 (Queue length time) |Queue length |

| |1 (Report) | |1 (Time Stamp) |delay |

| | | | | |

As shown in Table 12, mesh measurement action frame’s body contains category, command, TID, element, and value fields. The command field indicates whether the frame is a request or a report of the measurement. The TID field indicates which traffic category the measurement involves. The element field indicates the measuring element (queue length, time stamp etc), and the value field contains the measured value.

2 Frame Aggregation

1 Motivation

When the CSMA/CA method is used, the throughput obtained by the different size of the transmitted data frame may be different. For instance, the throughput is degraded when the frame size becomes small, even though the totlal amount of transmitted data is the same. One of reasons is that the number of generated data frame increases as the frame size becomes small, which results in the overhead increasing. Another reason is that because it is needed to wait for a random backoff time for the transmition of one data frame, the entire waiting time increases as the number of frames increases, which also results in the throughput degradation, Here, we consider a VoIP(Voice over IP) application that the frame with a small size continues. Thus, the desirable throughput for the VoIP application may not be achieved due to the VoIP frames with a small size. To solve this problem, we propose a frame aggregation scheme by integrating two or more short frames into one frame on the Mesh AP. Our proposed scheme can improve the throughput by decreasing the number of transmitted data frame, which results in the reduction of the total amount of waiting time and overhead.

2 Frame Aggregation Schemes

In this subsection, we propose three frame aggregation schemes in consideration of the features of WLAN Mesh network. Figure 24 shows an example of frame aggregation based on the proposed three schemes.

[pic]

Figure 24 – An Example of Frame Aggregation

1 Tun(Tunneling) Aggregation Scheme

Here,, we consider the case where STA1 and STA2 associated with the MAP4 have the same address of DA such as R1 shown in the figure. In this case, the frames from STA1 and STA2 are relaid to MAP1 that is connected to R1 Because STA1 and STA2 have no need to learn the routing information from MAP4 to MAP1, it can be considered that a tunnel path is set between MAP4 and MAP1. This aggregation scheme can be applied to aggregate the frames with the same address of tunnel path exit into one frame. Figure 25 shows an example of Tun-aggregation frame format, where the information on the number of aggregrated frames, sizes and tolerant delay is included in the AggInfo field.

[pic]

Figure 25 – Tunneling Aggregation Frame Format

2 NH(Next Hop) Aggregation Scheme

We here consider the case where STA4 and STA3 are associated with MAP5 and MAP3, respectively, which DA addresses are different, shown in Figure 24. In this case, two or more frames are transmitted by aggregrating these frame into one frame, when these frames traverse cross the same link between the intermediate MAPs (Next Hop MAP). The frames from STA3 and STA4 are aggregated on the link between MAP3 and MAP2. Based on the proposed scheme, the frames are aggregated on every link. Moreover, Figure 26 shows an example of NH-Aggregration frame format.

[pic]

Figure 26 - Next Hop Aggregation Frame Format

3 MC(MultiCast) Aggregation (Optional) Scheme

When two or more frames are relaid to the different neighbour MAPs, these frames can be transmitted by aggregrating these frames into one frame with a local multicast address (or broadcast address). However, since the problem such as what timing the frame aggregation is executed and which MAP sends the ACK frame, is unsettled, this mechanism can be performed as an optional function.

3 Queuing Model

To perform the frame aggregation, two or more frames should temporarily be buffered in MAP. Here, we discuss two kinds of queuing model, shown as Figure 27.

[pic]

Figure 27 - Two Queuing Models

1 Push Model with Aggregration Delay

When the frames to the same forwarding destination arrive during the time of "Maximum Aggregation Delay", which is set for each queue, these frames can be aggregated into one frame. In the case where the VoIP application is considered, the "Maximum Aggregation Delay" is set to be a smaller value than the arrival interval of VoIP frame. Hence, it can be prevented that two or more frames from the same STA are queued. Though this scheme can be easily deployed, it has the disadvantage that the delay for the frame waiting to be aggregrated occurs.

2 Pull Model for the Congested Mesh Networks

When one frame transmission is finished, the MP inquires of the queue, where the frames to the same forwarding destination are saved. If the frame remains in the queue, the frame aggregation will be performed. This scheme implies that the frame aggregration is executed only when the frame exists in the queue, that is, the congestion over the WLAN Mesh network may occurs. Hence, the average delay for the frame waiting to be aggregrated can be reduced, because the frame aggregration is not performed all the time.

4 BEANS( Backward Explicit Aggregation Notification Scheme)

1 Hybrid Frame Aggregation Scheme

In this subsection, we propose a hybrid frame aggregration scheme, which adaptively uses the above two queuing models. The proposed hybrid scheme can achieve an effective frame aggregation by combining with Tun-Aggregation scheme and NH-Aggregation scheme. Figure 28 shows an example of a mesh AP with multiple queues, which hold the frames from the STA and MAP. Based on this scheme, the queuing model can be switched according to the aggregation state of the frame received from the opposite direction.

[pic]

Figure 28 – Mesh AP with Multiple Queues

2 Frame Aggregation Procedures

The procedures for the frame aggregration based on the proposed schemes are shown as follows.

1. STA1 and STA2 associated with the MAP4, establish VoIP sessions with the external terminal via gateway (R1), respectively, shown in Figure 29. Since the congestion over the mesh network does not occurs, the frame is individually transmitted to MAP1 without the frame aggregration.

2. Similarly to Step 1, STA3 and STA4 associated with MAP2 and MAP5, respectively, establish VoIP session with the external terminal, shown in Figure 30. Adding to the traffic from MAP4, the traffic between MAP1 and MAP2 will increases.

3. Here, we consider the case where the increase of traffic results in the congestion occurs on MAP1 and MAP2, shown in Figure 31. Since the frames are accumulated in the transmission queue of MAP1 and MAP2, the frame aggregration based on Pull model can be performed. As a result, the downstream frames to STA1 and STA2 are also aggregrated on MAP1. The frame aggregation is detected on MAP4, which receives the frames to STA1 and STA2.

4. When MAP4 detects the frame aggregation, it considers the congestion occurs on the relay MPs, and then changes into Push scheme from Pull scheme to perform the Tun-Aggregation, shown as Figure 32. Thus, Tun-aggregation is executed on MAP4 for the upstream frames from STA1 and STA2.

Based on the above procedures, the congestion on the relay MP is possibly detected by receiving the aggregated frames. According to the congestion state, the frame aggregation can be changed to Push model. Because the delay due to congestion occurs on the Relay MP, it should not be a problem for the delay due to the push model. On the wireless link without congestion, the frame aggregation can be actively performed. Since the proposed scheme notifies the frame aggregation to the backward channel, we call this scheme as BEANS(Backward Explicit Aggregation Notification Scheme),

[pic]

Figure 29 – Example of Frame Aggregation with Flow 1

[pic]

Figure 30 – Example of Frame Aggregation with Flow 2

[pic]

Figure 31 – Example of Frame Aggregation with Flow 3

[pic]

Figure 32 – Example of Frame Aggregation with Flow 4

Channel Assignment

1 Distributed Channel Assignment

1 Motivations

If a single channel is used throughout the mesh network, the collision and co-channel interference get very serious in the presence of heavy traffic load. Though it is not realistic that all MPs are equipped with multiple interfaces for its high mobility and compactness, some of MPs, especially Mesh APs, can be designed with multiple interfaces to meet the high performance requests. When an MP is equipped with multiple interfaces, by utilizing CA, multiple channels can be used simultaneously between MPs. Since the traffic can be parallelized over all the available channels, the system performance can be largely improved.

The utilization of multiple channels can either be in the MAC layer [5]-[6], determining the channel for each outgoing frame by exchanging RTS/CTS, or in the above layer through CA [7]-[9]. Since CA is performed per-frame in the MAC layer, it requires utilization of RTS/CTS for each unicast frame. After the necessary backoff, an MP transmits a RTS to the communication peer when it detects a clear channel and the NAV is not set. The peer MP responds with a CTS. In RTS/CTS, both the duration and the channel negotiation information are contained. A successful RTS/CTS dialogue allocates a data channel for the following transmission of the data frame. All the MPs maintain an NAV for each data channel. When an MP overhears either RTS or CTS, it sets the NAV for the allocated channel.

Though MAC-based CA is simple, it requires RTS/CTS for each frame, even for short frames of real time voice traffic. To transmit RTS/CTS for CA, all the MPs share a single common channel. When the network is heavily loaded, the frequent collision in the common channel degrades the system performance. It is also possible to improve the channel allocation efficiency in the MAC layer. Each time a TXOP is allocated when multiple data frames can be transmitted through a single RTS/CTS dialogue.

CA on the link layer adopts a different policy. An MP can assign a different channel for each of its links, and the combination between channel and link can last for a relatively long time due to the low mobility for the MP, like that in the cell communication. CA in such situations falls into two categories: with common channel and without common channel. Without the specialized common channel, fewer interfaces are required to use a certain number of channels, or more channels can be used with the same number of interfaces. However, both CA and routing get difficult in the absence of common channel. Though by transmitting the routing and management frames over all the channels can partially solve the problem, it requires quick channel switch capability. Sometimes new problems arise. For example, the receiver based CA [9] tries to evenly use all the channels. But the per-frame channel-switch may lead to serious hidden terminal problem because the sender may miss the RTS/CTS and interfere with its neighbor’s reception. The utilization of common channel greatly simplifies the connectivity problem and broadcast/multicast in the mesh networks. In the following CA with common channel is presented. Each MP should monitor the same common channel, over which the control messages and broadcasting messages are transmitted. By this means, each MP within the transmission range can receive the control message and the simple distributed CA protocol is enabled, which simplifies the network auto-configuration.

Our CA is a pairwise scheme. Both ends of each link always share at least one channel and the data frames are always transmitted over the assigned channel. Both the sender and the receiver keeps monitoring the channel, the hidden terminal problem and deafness problem in other schemes will not occur here.

2 Multi Channel Operation in a WLAN Mesh

1 Basic Assumption

All the MPs in the mesh network have at least one interface, and MPs may be equipped with multiple interfaces so as to distribute the traffic over all the channels and benefit from channel diversity. So there is necessity to assign channels for the links. In the mesh networks, some MPs, especially Mesh APs, seldom move, so the channel assignment can keep for a relatively long time, just like in the cell communications.

Following are the assumptions for CA of a mesh network:

1. In the Mesh Network, a channel is used as the common channel. This channel is statically configured or selected with a distributed protocol.

2. Each MP has at least one interface. Each MP should monitor the common channel with its common interface.

3. If a MP has two or more interfaces, except the common interface for the common channel, it can use other interfaces as the data interfaces to communicate over the non-common channels with its neighbors that also have two or more interfaces.

4. If an MP has two or more interfaces, the MP should distribute traffic over the non-common channels. Control messages and broadcast/ multicast traffic should be transmitted over the common channel.

5. Each MP should periodically broadcast in the beacon frame, which contains the common channel information.

Figure 33 gives an example. In Figure 33-(a), MP-1 is GW and has four interfaces. MP-2, MP-3, MP-4, MP-5, MP-6, MP-11 have two interfaces. MP-7, MP-8, MP-9, MP-10 have only one interface. Figure 33-(b) gives the result of CA, where links 3-7, 4-10, 7-8, 8-9, 9-10 must use the common channel, while links 1-2, 1-6, 1-11, 3-4, 4-5 can use extra data channels.

[pic] [pic]

(a) Before CA (b) After CA

Figure 33 - An example of CA.

2 Determination of the Common Channel

Some MPs may start almost at the same time and work on different common channels. So the mesh network may be disconnected. It is necessary for all the MPs to share the same common channel so as to maintain the connectivity. This is achieved by appending the common channel information in the periodical beacon frames.

Table 13 - New elements in the beacon frame

|CAS |CAS manager ID |CAS_FLAG |New common channel |Multi-ch capability |

In generally, it is up to GW to manage the common channel. If GW does not exist, the MP with the biggest ID becomes the new manager of the common channel. Following are the procedures for the MPs to negotiate a common channel within the mesh network.

1. When the common channel is statically configured, it should be the same for all the MPs.

2. When the common channel is selected dynamically, all the MPs have to maintain the CAS in a distributed way so that all the MPs can finally use the same common channel. A flag CAS_FLAG is used together CAS.

3. When there is a GW in the mesh network, GW should manage the CAS and set GW_CAS bit in CAS_FLAG.

4. When there is no GW, or when an MP fails to detect the GW, the MP with the biggest ID in the mesh network becomes the manager of CAS, it sets TEMP_CAS bit in CAS_FLAG. GW_CAS has higher priority than TEMP_CAS. In the absence of GW, all the connected MPs adopt the same common channel.

5. Periodically each MP tries to broadcast a beacon with CAS, CAS manager ID, CAS_FLAG, New common channel and Multi-ch capability. If the MP is the manager of CAS, it increases CAS, sets CAS_FLAG, puts its ID in the CAS manager ID field, and sets the new common channel in the beacon. Otherwise, the MP copies the saved CAS, CAS manager ID, CAS_Flag and New common channel into the beacon. If the MP has multiple interfaces, it should set the Multi-ch capability field; otherwise, it should clear this field.

6. When an MP receives a beacon

if GW_CAS is set, the MP is not GW, and CAS is fresh

it saves CAS, CAS manager ID, CAS_FLAG and New common channel

else if GW_CAS is not set but TEMP_CAS is set, the MP is neither GW nor the one owning the biggest ID, and CAS is fresh

it saves CAS, CAS_FLAG, CAS manager ID, and New common channel.

it copies the Multi-ch capability field to the link entry for the sender

If the new common channel is different from before, the MP

broadcasts a beacon over the old common channel with the new common channel information

updates the common channel

takes some special operations, as is described in section 0.

7. When an MP is not connected to GW, it periodically scans all the channels, either passively or actively. If it receives a beacon with GW_CAS set, it sends a beacon over the old common channel with the new common channel information; then it switches to the new common channel, and finishes some other required operations, as is described in section 0.

8. When the CAS is managed by the MP with the biggest ID, each time an MP calculates the routing table, it also checks whether the MP with the biggest ID is still-reachable. If negative, it becomes the new CAS manager when it has the new biggest ID.

9. MP ID can be the maximum MAC address of all the interfaces owned by an MP. In the mesh network, OLSR routing protocol is used. By exchanging the topology message, each MP knows the MP ID of all the MPs in the network.

10. When a new MP joins the mesh network, it passively or actively scans the channels. If it receives a beacon with GW_CAS or TEMP CAS, it switches to the new common channel, and finishes some other required operations, as is described in section 0.

[pic] [pic]

(a) Disconnected (b) Connected

Figure 34 - From disconnected network to connected network (with GW).

[pic] [pic]

(a) Disconnected (b) Connected

Figure 35 - From disconnected network to connected network (without GW).

Figure 34 and Figure 35 give the convergence of the common channels for a network with GW and a network without GW respectively. In either case, all MPs finally utilize the same common channel.

4 Channel Assignment for Non-common Channels

By the operation in section 7.1.2.2, all the MPs in the mesh network share the same common channels. Each MP knows whether itself is capable of multi-ch. By periodically exchanging beacons, each MP also learns whether its neighbors are capable of multiple-ch. Then all the MPs with multiple interfaces try to assign channels for the links to its neighbors that also have the multi-ch capability.

In CA, it is important that both ends of a link support the multi-ch capability. In order to balance the traffic over all channels, it is necessary to select the least used channel for the link. Following are the two key factors: By periodically exchanging the beacons, an MP knows whether its neighbors have multi-ch capability; in the neighbor entry, it records the multi-ch capability.

Within an MP, each interface keeps monitoring the assigned channel and calculating the percentage of busy time as the channel usage. The interfaces of an MP are using different channels. So the MP learns current channel usage within its transmission area. Periodically each MP sends the modified OLSR hello message, carrying the channel usage information, as is shown in Table 14. When an MP receives channel usage information from the adjacent MPs, it also learns the usage of other channels. An MP calculates the average of the channel usage received from its neighbors and the channel usage it has detected. In this way, an MP knows all the usage of all the available channels and may determine whether a channel is over burdened and take operation to balance the usage.

Table 14 - Modified hello message

|Number of Neighbors=M |

|N_1 |N_2 |… |N_M |

|Number of assigned channels=N |

|Ch_1 |Ch_1 usage |

|Ch_2 |Ch_2 usage |

|… |… |

The CA contains two kinds of operations: Global CA and the Local CA. Global CA is initiated by GW and performed in an expanding ring way from GW to the leaf MPs. Global CA involves the CA operation for each link. When an MP detects that a channel over a link is over burdened, it can perform Local CA for the specific link.

Distributed CA is through special CA frames. CA Request (CAReq), CA Reply (CARep) and GlobalCA. These frames are defines in the frame body of the Action frame. CAReq and CARep are used for the pairwise CA for a specific link while GlobalCA is used to control the Global CA operation in an expanding ring way. The CA control frames should be transmitted over the common channel through the common interface.

Table 15 - New frame format for CA

|Type=00 |Subtype=1010 |Duration |DA |SA |

Frame body for CARep

|Category=CA |Command=Reply |CA Type |Desired Channel |CAS |Result |Option |

Frame body for GlobalCA

|Category=CA |

|Command= GlobalCA |CAS |

|Channel numbers |

|Available Channel 1 |Channel 1 usage |

|Available Channel 2 |Channel 2 usage |

|… |… |

[pic] [pic]

(a) Before Global CA (b) After Global CA

Figure 36 - Global CA manner and the CA result.

Figure 36 gives an example of Global CA operation. Figure 37 presents the detailed procedure for Global CA and Local CA. In Figure 37 (a), MP-3 assignes channels for the links to MP-7 and MP-4 respectively; then it notifies MP-4 and MP-7 to continue the CA operation. In Figure 37 (b), MP-3 only assigns channel for the link 3-7.

[pic] [pic]

(a) CA steps in Global CA (b) CA steps in Local CA

Figure 37 - CA steps in Global CA & Local CA

5 Global CA (GCA)

All MPs have already known whether itself is capable of multi-ch and whether its neighbors support multi-ch. When an MP receives a GlobalCA message from its upstream MPs, it starts its round of CA as the temporary initiator. In each round of Global CA procedure, an initiator MP assigns channels for the links to its neighbors that are capable of multi-ch.

Figure 38 gives an example of a single round of Global CA, where MP-1 is GW and has three interfaces. In the figure, MP-1 is the initiator. Of its neighbors, MP-2, 3, 5 and 6 are capable of multi-ch, while MP-4 and 7 do not support multi-ch. MP-1 has three interfaces. One is used for monitoring common channel. The other two interfaces can be assigned channels in any way. So MP-1 gradually determines which channel to be used for a link and which channel to be used for an interface. The channel selection for a link is limited both by the available channels and by the number of interfaces. In the interface table, each entry contains CAS. In the neighbor table, each entry contains CAS. The bigger CAS means freshness in CA procedure. The older CAS means that the interface/link needs CA.

Following is the channel selection procedure an initiator takes for a link in Global CA operation:

1) Check whether there is a free data interface with older CAS than that in the GlobalCA message.

2) If such a data interface is found, the initiator should choose for the interface a new channel in the least-used-first manner (check CA usage in Global CA).

3) If such a data interface does not exist, that is, all the interfaces are used up, of the channels for all interfaces, including both the common interface and the data interface, a channel is selected, either randomly or in the least-used-first manner.

4) If the selected channel is already used by an interface with a fresh CAS, use that interface for the link.

Following is the post-CA procedure

5) If the CA for the link is really successful, the assigned channel together with CAS and CA type should be copied to the corresponding neighbor entry.

6) The assigned channel together with CAS and CA type should be copied to the interface entry. If the new channel is different from the old one, the channel of the CARD needs update.

7) The association between the link and the interface should be updated.

Generally an MP assigns channels for its links one by one. For each neighbor that is capable of multi-ch, the initiator first chooses a channel for the link in question according to the above rule. Then it sends a CAReq and waits for a CARep. If everything is OK, it will receive a CARep with Result=Success confirming the success of the desired CA. If the Result in CARep is Failure, MP-1 should set the common channel for the link. Some of the links may already have been assigned channels because the peer MPs are nearer to GW than the initiator. In such cases, these links need no CA operation. However, they already occupied some of the interfaces. This factor has been reflected in the channel selection rule. The responder (e.g. MP-2, 3, 5, 6 in Figure 38) may have no free interface to work on the desire channel. In such cases, the responder may suggest the initiator to use one of its currently assigned channels for the link, specifying the suggested channel in the option of CARep. When an initiator receives a CARep with an option, it starts a new CAReq/CARep dialogue with the peer MP, either with the suggested channel if it agrees with the peer MP, or with the common channel if it disagrees with the peer MP.

[pic]

Figure 38 - Global CA operation.

Global CA procedures:

1. GW constructs a new GlobalCA message, zeros the channel usages, increases its CAS and copies the CAS into the GlobalCA message. All the MPs share a single copy of GlobalCA message. The GlobalCA message is forwarded throughout the mesh network, from GW to the leaf MPs, hop by hop; each intermediate node immediately updates the channel usages in the GlobalCA message after it finishes assigning a channel for one of its links.

2. For a temporary initiator MP (including GW),

1. The initiator attributes all the neighbors to the common channel group if it does not support multi-ch; otherwise, it attributes the neighbors that do not support multi-ch to the common channel group. The links belonging to the common channel group are assigned the common channel. The initiator only needs to perform the post-CA operation with common interface and common channel for each of these links.

2. If the initiator supports multi-ch, for each of the links to its neighbors capable of multi-ch.

1. If the neighbor entry for the responder already contains a fresh CAS no less than that in the GlobalCA message, CA for the link is already finished (CA by the upstream MPs).

2. Otherwise, the initiator selects a channel for the link according to the channel selection procedure.

3. The initiator sends a CAReq with CA Type=GCA to the responder. CAS for the CAReq is copies from the GlobalCA message. The desired channel for the link is contained in CAReq.

4. The initiator starts a timer and waits for the CARep.

5. When the initiator receives a CARep with a fresh CAS of GCA type,

if the Result is Success and there is no option

it performs the post-CA procedure with the assigned channel and the related interface.

else if the Result is Failure, but it contains an option

if the suggested channel in the option is usable

it goes to 2.2.3 and starts a new CAReq/CARep dialogue with the suggested channel.

else

it goes to 2.2.3 and starts a new CAReq/CARep dialogue with the common channel.

else

it performs post-CA procedure with the common channel& interface.

6. If the timer expires, the initiator increases the failure count. If the failure count is less than the maximum allowable failures, the initiator goes to 2.2.3; otherwise, it performs the post-CA procedure with the common interface & channel.

7. After the initiator finishes CA for a single link, it updates the channel usage in the GlobalCA message. The channel usage will affect the channel selection for the next link.

3. When the initiator finishes the above operation, that is, all its links have channels with a fresh CAS, it forwards GlobalCA in a unicast way to all its neighbors that CA operation has just been done to, including the neighbors capable of multi-ch and incapable of multi-ch.

3. For a temporary responder

When an MP receives a CAReq with a fresh CAS of GCA type, it acts as a temporary responder.

1. If the requested channel in the CAReq is the common channel, the responder should send a CARep with Result=Success.

2. The responder then checks whether itself has multi-ch capability. If negative, it sends a CARep with Result=Failure, and the option contains the common channel.

3. Otherwise, the responder checks whether is has a data interface with a fresh CAS and the same data channel. If affirmative, it sends a CARep with Result=Success, containing the specified channel.

4. Otherwise, if the responder finds a data interface with a CAS smaller than that in CAReq. Then it sends a CARep with Result=Success, containing the specified channel.

5. Otherwise, it sends a CARep with Result= Failure, and the option contains the common channel.

After sending a CARep with Result=Success, the responder performs the post-CA procedure for the link with the assigned channel and the related interface.

When an MP receives a GlobalCA with a fresh CAS, it becomes the temporary CA initiator and starts to perform CA for all the non-assigned links.

4. When a new MP joins the mesh network, GW may initiate the Global CA operation.

6 Local CA (LCA)

GW initiates Global CA at the start, when a new MP joins the mesh network, or when it detects that the common channel is shared by an adjacent mesh network. It will affect all the links. In the contrary, local CA is to locally adjust the channel for a single link. In order to locally assign a new channel to a link, the procedures below must be followed.

1. When an MP itself is capable of multi-ch, it periodically checks the channel usage. When a channel is overused and the peer MP is also capable of multi-ch, the MP may try to adjust the data channel.

2. For the temporary initiator

1. Channel/link selection

The initiator finds which interface is using the overused channel and how many links are sharing the channel/interface. Then one of the links using the channel is chosen for the local CA. The adjustment of data channel for a link sometimes affects other links because the related interface may have to use a channel different from before and some other links are also sharingthe interface.

1. If a free interface is available, the initiator chooses a channel/interface according to the channel selection procedure.

2. If the interface related with the link in question is only used by this link, the interface can use any new channel for the link. The initiator chooses a channel according to the channel selection procedure

3. Otherwise, if the interface related with the link is also used by some other links, the initiator checks whether the channel load can be balanced if other currently used interface/channel is used for the link. If affirmative, the initiator chooses a channel according to the channel selection procedure.

2. For the chosen link

1. The initiator sends a CAReq of LCA type with the desired new channel. The CAS is cleared to 0.

2. The initiator starts a timer and waits for CARep

3. When the initiator receives CARep of LCA type, if the Result is Failure, and no option, the MP should stick to the old channel.

4. Otherwise, if the Result is Success, the initiator performs post-CA procedure for the link.

5. Otherwise, if the Result is Failure and the option field contains a valid channel, and the initiator finds that some other interface is already using the channel, that interface will be used for the link. Then the initiator should go to 2.2.1, sending a new CAReq with the channel in the option.

6. Otherwise, if the link in question is the only affected link or a free interface exists, the initiator may adopt the recommended channel, and go to 2.2.1, sending a new CAReq with the channel in the option.

3. For a temporary responder

1. When an MP receives a CAReq message of LCA type, it acts as a responder.

2. If it finds that one of its interfaces happens to use the same channel as specified in the CAReq, it sends back a CARep message with the same channel to the sender, with Result=Success. Then it performs the post-CA procedure.

3. Otherwise, if none of its interfaces in the responder is using the specified channel, and the related interface only services a single link, the responder sends a CARep message with the same channel to the sender, with Result=Success. Then it performs the post-CA procedure.

4. Otherwise, if none of its interfaces in the responder is using the specified channel, and the related interface services two or more links, the responder sends a CARep with Result=Failure with the option containing the least used channel in use.

5. Otherwise, it sends back a CARep, with Result=Failure without option.

4. When a new MP joins the mesh network, it can establish the data channel with its neighbors by the Local CA operations.

7 Operation after Channel Update

During CA operation, some of the interfaces may have new channels, and then the association between the interface and channel should be changed. An MP’s connection with its neighbors through one interface may get broken. By using a different interface, a new link can be established. In such case, the post-CA procedure updates the neighbor table and interface table to reflect the actual variations. The routing table also needs refreshment so that each outgoing frame carries the correct interface information, enters the correct interface queue, is transmitted over the desired channel, and is finally received by the peer MP. Only updating the routing table is not enough. Some packets may already wait in the queue with the out-of-date interface information. In the case of frequent Local CA operation, an MP may optionally update the interface information of the packets in the queue so as to reduce the packet loss.

2 Portal-Driven Channel Assignment

As more channels can be used in a network with less number of radio modules, the graph topology of assigned channels tends to be complex with strong constraints for channel selection. And the condition of connections between MPs changes with the fluctuation of radio environment, the movement of MPs or the status of transmission of MPs. When the change is frequent enough, the reassignment of the channels to MPs become to be critical. If the distribution of the assigned channels is oriented to be well-fragmented, on the contrary, a MP’s channel reassignment reacts on many other MPs’ and the chain reaction propagates. This propagating chain reaction makes it irreasonable to reassign channels. Also, radio interference range is enough large, then fragmentation of assigned channels is not so effective. This means “well-fragmented” is no more a good feature. Therefore, another strategy of channel assignment is needed, that is, assigning a common channel and assigning the rest of the available channels to the same number of non-fragmented segments of MPs. Communication traffic that goes out of the network passes the Mesh Portals. Then it would be good for channel assignment to start the segmentation from a Mesh Portal.

1 Backgrounds

If the radio modules one MP can handle are same with its channel number, there is only one strategy that a channel is assigned to a radio module one after another. Then every MP can handle all available channels. When the number of radio modules in one MP is smaller than one of the usable channels, an MP cannot handle all channels at one time. Each MP tries to assign some channels to connect to adjacent MPs choosing least used channels for each link to adjacent MPs, and when there remains radio modules unused, MP assign them least used channels. AS MPs’ density increases, the number of adjacent MPs increases. Then if the adjacent MPs use various channels, it tends to be unable to assign radio modules all of channels that the adjacent MPs use. It is because the radio modules tend to be less than the used channels by the adjacent MPs. Therefore it is needed that adjacent MPs use the not more number of channels than the number of radio modules each MP has. This requires segmenting the assembly of MPs. In general, a network should use as many channels as it can use for maximizing the available throughput in the Mesh. But then MPs are enough many, it is okay that one MP use only one or two channels. Each channel is used by some number of MPs and all channels are used by MPs in the network. Non-fragmented segmentation seems to prevent the channel reuse in a network, but it is not easier even for well-fragmentedly channel assigned network to reuse the channel within a network because one MP’s radio interferes at least 10 times as large area as it enable transmissions. Assupting a practical case such that the number of MPs is less than a hundred and the number of available channels less than ten, equipping two radio modules is enouth for each MP: one for transmission in a segment MP belongs and one for primary transmission like initial, instant and inter-segment transmission.

2 Segmentation Strategy

The strategy of segmenting the the assembly of MPs can be various. Some are suitable for bursty traffic like P2P within the Mesh and some are for other ones. The point is what can be assumed the most critical service traffic. Here considering the constant bit rate traffic that goes through Mesh Portals the most critical, we introduce segmenting methods Mesh Portals drive. As MPs exchange topology information proactively using a channel, reserving the channel as a common one, a Mesh Portal can resolve its multi-hopped broadcasting tree that is flooding tree. Then the Mesh Portal determines the segmentation for MPs in the Mesh.

1 Channel Assignment by Segmenting

See the figures.

[pic]

Figure 39 - An Example of a Mesh Topology.

[pic]

Figure 40 - Flooding Tree from Mesh Portal.

[pic]

Figure 41 - Result of Channel Assingment.

Segmenting CA procedures:

2 Channel Assignment at Merger of Mesh

See the figures.

[pic]

Figure 42 - Discretely Formed Networks of a Mesh ID.

[pic]

Figure 43 - Beginning of Mesh Merger.

[pic]

Figure 44 - Result of Mesh Merger.

Merger CA procedures:

WLAN Mesh Security

To enhance 802.11i for mesh networks, we here propose a feasible WLAN mesh security scheme performing the authentication and key distribution for secure communications. We propose authentication and authenticator selection mechanisms for multihop mesh topology. These mechanisms establish the secure links between neighboring mesh APs. Therefore, if a problem like the key leakage occurs on the specific link, it does not influence other links by separating the corresponding Mesh AP(s). The proposed scheme can be applied to inter-mesh networks, and able to restore troubles on the Mesh Portal.

8.1 Authentication of Newly Arrived MP

The following is the procedures of connection establishment for newly arrived MP (see Figure 45).

1. The newly arrived MP (MP-5) receives beacon frames from neighbor MPs.

2. MP-5 associates to an MP (MP-2).

3. MP-2 forwards an authentication request from MP-5 to AS. If MP-5 is accepted to be connected, AS creates a key to MP-5.

The procedures above establish a secure link between the newly arrived MP and its neighbor.

[pic]

Figure 45 - A connection establishment for a new mesh AP.

2 Link Establishment between Neighboring MPs

After connecting the newly arrived MP to its neighbor MP, it is needed to create secure connections from this MP to any other non-connected neighbor MPs. In order to obtain PTK for the pair MPs, one of them has to become an authenticator to communicate with AS. The following is the procedures of authenticator selection to establish the linkslink between unconncected MP and its neighbor MPs (see Figure 46).

1. An MP receives a beacon frame from non-connected neighbor MP

2. Authenticator selection mechanism is as follows

• If one of the MPs has a route to AS but the other does not, the one which has the route becomes authenticator, and the remaining MP becomes supplicant.

• If both of the MPs have routes to AS, the MPs compare hop counts to AS, and the MP that has the shorter hop count is selected as an authenticator, and the remaining MP becomes supplicant.

3. The selected authenticator sends authentication request to AS.

4. If AS permits the request, it creates a PTK for the connection.

The procedures above establish a secure link between an MP and any of its non-connected MP.

[pic]

Figure 46 – The flow chart of the authenticator selection.

Now, we consider the case where a Mesh Portal has got some troubles and the connection between Mesh Portal and its neighbour MP is broken. After the Mesh Portal is recovered from the troubles, it communicates with the AS and performs the authentication procedure separately from the mesh network. After being authenticated, a connection procedure between Mesh Portal and the mesh network is performed as shown in Figure 47. The authentication and creation of the secure link between the Mesh Portal and its neighbor MP follows the procedures above.

In our proposal, the secure link is established between neighboring MPs. Therefore, when any trouble occurs on the specific MP, the influence can be localized by separating the corresponding MP.

[pic]

Figure 47 - Connection reestablishment between the restored mesh portal and mesh network.

Summary

In this document, we describe a proposal that provides a framework for the 802.11s ESS Mesh standard. The proposed scheme has the following basic properties

• A proactive layer-2 routing protocol is specified, which allows the WLAN mesh AP to accommodate the legacy STAs associated with it.

• The proposed OLSR-based routing protocol is enhanced by using the RSSI information and performing the flow-based load balancing.

• The proposed scheme can provide the QoS support by using the delay-based priority control mechanism, to extend the IEEE 802.11e to the WLAN mesh networks.

• To support the multiple radios, a distributed channel assignment scheme with common channel is proposed, which perform the channel assignment in the link layer.

• Authentication and authenticator selection mechanisms for multihop mesh network are specified. The mechanisms establish the secure links between neighboring MPs in the network.

To confirm the effectiveness of the proposal, we are currently in the process of performing simulation experiments, and doing the further improvement and refinement.

References

1] C.E.Perkin, E. Belding-Royer and S. Das, Ad hoc on-demanc distance vector (AODV ) routing, RFC3561, July 2003.

2] P. Jacquet, P. Muhlethaler, T. Clausen et. al., Optimized link state routing protocol for ad hoc networks, Proc. IEEE, pp.62-68, Decemeber 2001.

3] IEEE Std 802.11®-1999 (Reaff 2003)

Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications.

4] IEEE P802.11e/D13.0, January 2005

(Draft Amendment to ANSI/IEEE Std 802.11, 1999 Edition (Reaff 2003))

Medium Access Control (MAC) Quality of Service (QoS) Enhancements.

5] Jain, N.; Das, S.R.; Nasipuri, A., A multichannel CSMA MAC protocol with receiver-based channel selection for multihop wireless networks, ICCN 2001, pp.432 – 439, 2001.

6] W.C.Hung, K.L.Eddie Law, and A. Leon-Garcia, A dynamic multi-channel mac for ad hoc LAN, 21st Biennial Symposium on Communications, pp. 31–35, 2002.

7] A.Raniwala, K.Gopalan, T. Chiueh, Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks, ACM Mobile Computing and Communications Review (MC2R), Vol 8, No 2, 2004.

8] R.Draves, J.Padhye, B.Zill, Routing in multi-radio, multi-hop wireless mesh networks, MobiCom 2004, pp.114-128, 2004.

9] Pradeep Kyasanur and Nitin H. Vaidya, Routing in Multi-Channel Multi-Interface Ad Hoc Wireless Networks, CS dept. UIUC Technical Report, December 2004.

-----------------------

Notice: This document has been prepared to assist IEEE 802.11. It is offered as a basis for discussion and is not binding on the contributing individual(s) or organization(s). The material in this document is subject to change in form and content after further study. The contributor(s) reserve(s) the right to add, amend or withdraw material contained herein.

Release: The contributor grants a free, irrevocable license to the IEEE to incorporate material contained in this contribution, and any modifications thereof, in the creation of an IEEE Standards publication; to copyright in the IEEE’s name any IEEE Standards publication even though it may include portions of this contribution; and at the IEEE’s sole discretion to permit others to reproduce in whole or in part the resulting IEEE Standards publication. The contributor also acknowledges and accepts that this contribution may be made public by IEEE 802.11.

Patent Policy and Procedures: The contributor is familiar with the IEEE 802 Patent Policy and Procedures , including the statement "IEEE standards may include the known use of patent(s), including patent applications, provided the IEEE receives assurance from the patent holder or applicant with respect to patents essential for compliance with both mandatory and optional portions of the standard." Early disclosure to the Working Group of patent information that might be relevant to the standard is essential to reduce the possibility for delays in the development process and increase the likelihood that the draft publication will be approved for publication. Please notify the Chair as early as possible, in written or electronic form, if patented technology (or technology under patent application) might be incorporated into a draft standard being developed within the IEEE 802.11 Working Group. If you have questions, contact the IEEE Patent Committee Administrator at .

0

2

9

13

1

p3

2

p4

p2

Mesh Portal

7

p2

p3

p1p12

f3

f2

f1

p3

p2

p1

10

7

ÿRelay MP

ÿUnique MP

ÿShiftable MP

1

ÿLinks for flooding from Mesh Portal

31

30

29

28

27

26

25

24

23

：Relay MP

：Unique MP

：Shiftable MP

1

：Links for flooding from Mesh Portal

31

30

29

28

27

26

25

24

23

5

6

4

3

0

2

9

1

8

The number of hops for Frame 2 is larger than one of Frame 1 for both from itself to the destination and end-to-end hops

↓

Frame2 is sent first with a higher priority

Frame1: Src =MP-3, Dst =MP-1

Frame2: Src =MP-3, Dst = MP-4

Routing Table at MP-2

|Dst |TTL (Metric ) |

|1 |1 |

|3 |1 |

|4 |2 |

3. 1

1. 1

4 2

Flow2

Flow1

4

3

1

6

2

5t

22

31

27

25

26

24

23

20

21

29

22

28

17

16

15

14

13

3

p2

f4

f3

f2

f1

p3

p2

p1

p1

10

7

5

10

6

4

2

1

3

9

4

6

2

20

19

18

17

7

16

11

Frame has been arrived

Routing Table at MP-1

Routing Table at MP-3

|Destination |Next hop|Cumulative queue length |

| | |Buffer1 |Buffer2 |

|1 |2 |60 |80 |

|4 |2 |80 |120 |

|5 |2 |60 |80 |

|2 |2 |10 |20 |

|Destination |Next hop |Cumulative queue length |

| | |Buffer1 |Buffer2 |

|3 |2 |70 |100 |

|5 |4 |40 |70 |

|2 |2 |20 |40 |

|4 |4 |20 |40 |

|Buffer |Queue length |

| |[Kbyte] |

|1 |20 |

|2 |40 |

|Buffer |Queue length |

| |[Kbyte] |

|1 |20 |

|2 |30 |

|Buffer |Queue length |

| |[Kbyte] |

|1 |10 |

|2 |40 |

|Buffer |Queue length |

| |[Kbyte] |

|1 |50 |

|2 |60 |

3

3

|Buffer |Queue length |

| |[Kbyte] |

|1 |10 |

|2 |20 |

8

p2

4

1

2

5t

8

19

5

Abstract

This document describes an extensible WLAN mesh networking proposal for 802.11s. The proposal provides a framework for a WLAN mesh network with the wireless multihop communication between mesh access points, which accommodate the legacy stations associated with them. It specifies a layer-2 proactive routing protocol, which includes the topology discovery and supports the WDS unicast/multicast/broadcast. To enhance the routing protocol, the strong link is selected by using the Received Signal Strength Indicator (RSSI), and Pseudo flow-based load balancing is also performed. Moreover, the proposed scheme provides the QoS support mechanisms with the extensible IEEE802.11e, by performing a delay-based priority control, and also supports the multiple radios with the distributed channel assignment. Finally, the secure links for the mesh network are built based on an extensible 802.11i security mechanism.

Buffer1

Buffer2

Buffer3

|Buffer |Queue length |

|1 |q1 |

|2 |q2 |

|3 |q3 |

| | |

|8 |q8 |

Flow2

Flow4: VoIP, number of hops: 2, Source: MP-2, Destination: MP-6

Flow3: VoIP, number of hops: 2, Source: MP-2, Destination: MP-8

Flow1: VoIP, number of hops: 3, Source: MP-4, Destination: MP-9

Flow2: VoIP, number of hops: 1, Source: MP-5, Destination: MP-6

Flow1

Flow4

Flow3

12

18

30

5

6

4

1

2

9

3

8

p3

p5

p1

f3

f2

f1

p5

p3

p1

10

7

5

6

4

0

2

9

8

1

(a) Recording arrival time when frame has been arrived

Send the frame

Update the “delay” field:

delay =+ current_time-arrival_time

Frame is ready to be sent

No

Yes

Insert the frame to the appropriate buffer

Initialize the delay field: delay = 0

Is it the source MP?

Record the arrival time: arrival_time = current_time

15

14

13

12

10

9

8

7

6

5

4

3

21

11

1

Mesh Portal

7

31

27

25

26

24

23

20

21

29

22

28

17

16

15

14

13

10

11

19

12

18

30

5

6

4

1

2

9

3

8

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download