- Project Context
- Testbed Describtion
- Wireless Mesh Networks Overwiew
- IEEE 802.11s Overview:
- Testbed Implementation:
- System Design:
- Code:
- Data Forwarding Code
- Routing Code
- Link Quality Measurment Code
- Author: R.Abid
aui.ma - Last Update: July, 29th, 2009
Project Context:
This project is relevant to the fullfilment of the Ph.D degree requirements, in Computer Science, at Auburn University. The project is mainly about "IEEE 802.11s Wireless Mesh Networks for Last-mile Internet Access: Performance Evaluation" and it is supervised by Dr. Biaz.
Testbed Description:
The testbed is wireless mesh network that spans two separate locations in the second floor of the Shelby Center at Auburn University. See next Figure. The two WMN are connected to each other via Internet. The testbed is meant to study the performance of the ongoing new IEEE 802.11s standard and suggest ways to improve its performance, e.g., by suggesting new frameworks for wireless link quality characterization. In this project, we propose a new framework that adapts the Physical Interference Model for practical use in WMNs. Such an adaptation allows a quite accurate Interferences levels estimation.
NB: To acsetain the functionality of the testbed, both TCP and UDP traffic have been tested: Wifi-enabled stations can have real Internet sessions using the testbed as a backhaul,
Wireless Mesh Networks Overview:
WMNs are multi-hop wireless networks with static nodes. WMNs are largely benefiting from the valuable research lead so far in MANETs (Mobile Ad hoc Networks). These later, which failed to attract good civil applications, have tremendously contributed to the proliferating success of WMNs: many WMNs protocols have been borrowed from MANETs. e.g., HWMP, AOVD, DSR, OLSR; However, the migration of such protocols should strongly profit from the actual alleviation on the stringent constraints of mobility and power consumption, constraints that were inherent in MANETs.
Thanks to their easy-to-deploy and self-healing features, WMNs are indeed emerging as a very promising technology. Solutions are already commercialized, e.g., Strix Systems, Cisco , Nortel. WMNs are easy-to-deploy as setting a WMN involves minimum cabling and configuration overhead: Settling down the WMN nodes and powering them on is all what is required to maneuver a WMN. WMNs are self-healing thanks to the redundancy of wireless links, i.e., failure tolerance: a failure in a link incites the network to look for an alternative link in order to continuously maintain the network operational.
WMNs have a rich set of applications, e.g. Last-mile Wireless Internet access, wireless community networks, wireless enterprise networks, transportation systems, home networking, etc. Providing last-mile wireless internet access is the most promising application as WMNs tremendously reduce the cost and configuration overhead when compared with current solutions. e.g. Wi-Fi (802.11) WLANs. The proliferation of Wi-Fi LANs played a tremendous role in the promising success of WMNs. Even though very successful, 802.11 WLANs still suffer from the valuable cost and overhead of setting the wired backbone that connects the different 802.11 APs (Access Points), a fact stemming from the last-wireless-hop nature of 802.11 LANs.
In 802.11 WLANs, covering a cell requires the deployment of an AP which should to be cabled to the Internet through a wired backbone network. When another adjacent cell is to be connected, another AP has to be settled and wired to the Internet too and so on. This way, the settlement of further APs becomes more and more costly when the cells to cover are quite far from the backbone network. Furthermore, in case of dense regions, a parallel dense deployment of APs is needed to meet customers needs resulting in more cabling and settlement overhead. Even though, APs are relatively cheap, cabling APs and finding the appropriate canals for the wires is still expensive. In WMNs, no cabling is required except for the AP which will serve as a gateway towards the Internet (Even the gateway can be wirelessly connected to the Internet). All other APs do serve as routers and do route data on behalf of each other towards/from the gateway AP which is connected to the wired backbone network. This way covering a further cell is reduced to placing, without any cabling, an additional AP. Easing wireless coverage increases wireless coverage, a fact which is of tremendous importance to industry since more coverage involves more user connections and hence more return to industry. In this context, IETF is hardly striving to finalize the IEEE 802.11s standard which will pave the way towards a successful worldwide industrialization of this very promising technology.
In 2005, IETF did set a mesh networking TG to standardize IEEE 802.11s, the work is still in progress and the standardization process is expected to be final by late 2009. The last IEEE 802.11s TG meeting was held in last January, 2009. Even though the standard is not final yet, the main traits of the standard have been already set, e.g. IEEE 802.11s architecture and routing using MAC addresses. The IEEE 802.11s TG did set HWMP (Hybrid Wireless Mesh Protocol) as a default routing protocol to be present in all 802.11s compliant devices. Besides, Airtime has been set a default link quality metric to accompany HWMP as well - These two amendments are for the purpose of maitaining minimum compatibility between 802.11s devices. HWMP is a hybrid protocol that combines both a reactive and a proactive routing protocol. The novelty of the protocol is that it uses MAC addresses for routing.
IEEE 802.11s Overview:
802.11s started initially as a study group in 2003 then it was entitled as a Task Group in July 2004. The first draft was accepted in March 2006. The last draft, D2.00, was discussed in the last TG meeting in last January 2009 \cite{ieee}. The finalization of the standard is expected by late 2009. The standard is concerned with five main areas: 1. Architecture 2. Routing in MAC layer 3. MAC enhancements 4. Internetworking and 5. Security. In this work we are basically concerned with the first two and the fourth components. The next two paragraphs do highlight the main features of the first components.
IEEE 802.11s Architecture:
IEEE 802.11s defines three types of stations:
The end-user, which is at station 1, is connected to a legacy 802.11
network through a mesh access point (MAP). The MAP is
forwarding/routing user data towards/from the WMN and has mesh point
MP2 as a next hop. Mesh point MP2 has MP4 as its next hop and MP7
afterwards. This later forwards data towards Mesh Portal Point
MPP1 which serves as a gateway towards the Internet where the web
server lies. The role of the routing protocol is to determine the best
sequence of next hops for a data frame to get to its final destination.
In 802.11s, routing is performed using MAC addresses and uses Airtime
as a default routing metric.
IEEE 802.11s MAC Routing:
Multi-hop routing is a key element in 802.11s. 802.11s performs routing using MAC addresses. To our understanding, the main motivation behind using MAC addresses, for routing, is allowing the MAC layer to access link quality measurements, a fact which will tremendously optimize routing decisions. In fact, routing metrics are, in wireless networks, at the heart of routing performance [4]. Unlike, wired networks, the quality of the wireless link is not stable and this is due basically to the inherent broadcast nature of the wireless link which results in interferences from undesired communication. Interferences, which are absent in wired networks, are the major inducer of frame losses in wireless networks, a fact that substantially affects wireless throughput specially with multiple wireless hops which is case with WMNs. Hence, wireless networks and especially multi-hop ones need access to link quality measurements in order to optimize routing performance and cope for the degradation in throughput. Access to wireless link measurements is by principle impossible at Network layer, when conforming to the OSI model, unless a cross layer design is adopted between the Network and MAC layers. In IEEE 802.11s, a cross-layer design between MAC and Network is implicitly incorporated without affecting the OSI model, this way and in a smart way the 802.11s MAC layer is still compact and transparent to above layers while performing routing.
802.11s uses either four or six MAC addresses for routing depending on the nature of the traffic. When both the source and destination are mesh points in the WMN, only four addresses are used. When at least the source or the destination is outside the WMN, i.e., a non-mesh point, e.g. a 802.11s legacy station, six addresses are used instead. 802.11s header frames bear an AE (Address Extension) mode bit that discriminates between the two modes. In case where WMNs are used for Last-mile Internet access, the AE bit is always set to 1 as both destinations and sources are non-mesh points.\\
Adding two extra MAC addresses, to the ordinary four 802.11 ones, is meant to preserve the MAC addresses of the non-mesh source and non-mesh destination, these later would be lost once the frame enters the mesh network. The six MAC addresses are:
HWMP is a hybrid routing protocol that has both a Reactive and Proactive components. For the nature of this application, which is IEEE 802.11s WMNs for Last-mile Interent access, where are using the Proactive components. This later is an adaptation of the well-known AODV protocol which uses Airtime as a routing metric.
Implementation:
The system is made of three modules, see Figure 3, that communicate between each other using IPC (Inter Process Communication) shared memories: 1. Routing, 2. Data forwarding and 3. Link quality measurements. Only the last module (link quality measurement) is identical in all WMN nodes, i.e., MAPs, MPs and MPPs. For the two other modules, their implementation depends on the type of the node. Next sections detail implementation for each module and highlights how the implementations differ according to the type of the mesh point.
The routing module implementation depends on the type of the mesh node:
1. Routing in MPPs:
In MPPs, the Routing module is made of two sub-modules:
2. Routing in MPs:
In MPs, the MP-PREQ-Processing module processes two types of messages: PREQ and RREP messages.
3. Routing in MAPs:
Upon reception of a PREQ message, the MAP_PREQ _Processing module retrieves the MAC address of the MPP which issued the PREQ message. The MAP retrieves then the entry, from the Proxying Table, that corresponds to the sender MPP and checks the freshness of the current PREQ message against the already stored freshness. If the PREQ message corresponds to a fresher route or corresponds to an equal freshness route with better routing metric, the corresponding entry in the MAP Proxying Table is updated. Afterwards, the routing metric value is updated the same way as with MPs.
However, the processed PREQ message can correspond to only a local better route, i.e., the best route leading to a specific MPP. Hence, there may be better routes to other MPPs. Selecting the MPP that has the best routing metric would fail in case the entry was updated a long time ago or in case the MPP is off. This problem was highlighted in section 5.1.1. To address this problem, we do timestamp all MPP routing entries in the proxying table. The timestamps correspond to the time at which the MPP routing entry was updated. This way we select the MPP that has the better route as well as a fresher route by comparing its timestamp to the current running time. We set a time threshold which is twice the MPP broadcast periods. We choose a twice period to account for the case when a broadcast has been accidentally lost. The best MPP is marked in the proxying table.\\
Once the proxying table is updated, a RREP message is formed and sent back to the selected MPP. The RREP message acknowledges the receipt of the MPP PREQ message and it plays also the role of an association message telling the MPP to associate the MAP with it. The RREP message bears mainly the MAC address of the MAP as well as the corresponding routing metric.
The Data Forwarding module implementation depends on the type of the mesh node.
1. Data Forwarding in MPPs:
MPPs have two network interfaces: an 802.3 interface and an 802.11 ad-hoc interface, a fact which results in processing two different types of frames.
2. Upon reception of an 802.11s frame in its ad-hoc interface, the MPP reads the 802.11s header frame, gets the originator MAC address and its IP address and inserts an entry for it in the MPP association table. The entry contains the IP address, the MAC address and the associated MAP MAC address. Afterwards, the MPP strips off the 802.11s frame header and replaces it with an 802.3 frame header containing as a destination MAC address the default gateway (in the LAN interface) and as a source address the local MPP MAC address.\end{itemize}
2. Data Forwarding in MPs:
In contrast to MPPs, Data Forwarding in MPs is quite straightforward as it deals only with one type frames, i.e. 802.11s frames. However, the MP still receives two types of frames that differ in terms of their final destination being it either an 802.3 or an 802.11 network, i.e. is the final destination an MPP or a MAP?
The proxy type, i.e. a MPP or an MPP, is made transparent in our implementation by having the same type of entry in the MP forwarding table for all proxies.
Upon reception of an 802.11s frame, the MP extracts the destination proxy address, i.e., the MPP or MAP MAC address, consults its forwarding table and retrieves the corresponding entry which contains the next hop MAC address. The 802.11s frame is then updated by changing only two of the six MAC addresses in the 802.11s frame header, the remaining four ones are kept intact. The two updated MAC addresses are the destination MAC address and the source MAC address which become respectively the retrieved next hop MAC address and the MP MAC address.
3. Data Forwarding in MAPs:
MAPs have two network interfaces, an 802.11 Access Point interface and an ad-hoc 802.11s interface, which results in processing two different types of frames.
2. On the other side, upon reception of a 802.11s frame in its ad-hoc interface, the 802.11s header frame is stripped off and replaced by a broadcast 802.11 header frame. Thereafter, the final 802.11 legacy destination will look up its IP address in the broadcasted 802.11 frame.
1. ETX
The ETX module is made of two sub-modules: The ETX-Broadcast module and the ETX-Collect module.
2. Airtime
Reads the corresponding transmission rates using the "/Prof/file" system, gets the ETX values reported by the ETX module and then computes the corresponding Airtime value as specified by IEEE 802.11s.
3. ICE
To compute ICE, we used the capability of the Madwifi driver in allowing the creation of multiple virtual interfaces in the same card. We created two virtual interfaces in every mesh node: One is set to the "ad-hoc" mode and the other is set to the "monitor" mode.
In the monitor mode, the network interface card can overhear all all ongoing singals, hence having access to their strengths, rates and lengths ...etc. These different values are used to compute the SINR under the physical interference model by using a given probabilstic 802.11 traffic model.
This project is relevant to the fullfilment of the Ph.D degree requirements, in Computer Science, at Auburn University. The project is mainly about "IEEE 802.11s Wireless Mesh Networks for Last-mile Internet Access: Performance Evaluation" and it is supervised by Dr. Biaz.
Testbed Description:
The testbed is wireless mesh network that spans two separate locations in the second floor of the Shelby Center at Auburn University. See next Figure. The two WMN are connected to each other via Internet. The testbed is meant to study the performance of the ongoing new IEEE 802.11s standard and suggest ways to improve its performance, e.g., by suggesting new frameworks for wireless link quality characterization. In this project, we propose a new framework that adapts the Physical Interference Model for practical use in WMNs. Such an adaptation allows a quite accurate Interferences levels estimation.
NB: To acsetain the functionality of the testbed, both TCP and UDP traffic have been tested: Wifi-enabled stations can have real Internet sessions using the testbed as a backhaul,
Wireless Mesh Networks Overview:
WMNs are multi-hop wireless networks with static nodes. WMNs are largely benefiting from the valuable research lead so far in MANETs (Mobile Ad hoc Networks). These later, which failed to attract good civil applications, have tremendously contributed to the proliferating success of WMNs: many WMNs protocols have been borrowed from MANETs. e.g., HWMP, AOVD, DSR, OLSR; However, the migration of such protocols should strongly profit from the actual alleviation on the stringent constraints of mobility and power consumption, constraints that were inherent in MANETs.
Thanks to their easy-to-deploy and self-healing features, WMNs are indeed emerging as a very promising technology. Solutions are already commercialized, e.g., Strix Systems, Cisco , Nortel. WMNs are easy-to-deploy as setting a WMN involves minimum cabling and configuration overhead: Settling down the WMN nodes and powering them on is all what is required to maneuver a WMN. WMNs are self-healing thanks to the redundancy of wireless links, i.e., failure tolerance: a failure in a link incites the network to look for an alternative link in order to continuously maintain the network operational.
WMNs have a rich set of applications, e.g. Last-mile Wireless Internet access, wireless community networks, wireless enterprise networks, transportation systems, home networking, etc. Providing last-mile wireless internet access is the most promising application as WMNs tremendously reduce the cost and configuration overhead when compared with current solutions. e.g. Wi-Fi (802.11) WLANs. The proliferation of Wi-Fi LANs played a tremendous role in the promising success of WMNs. Even though very successful, 802.11 WLANs still suffer from the valuable cost and overhead of setting the wired backbone that connects the different 802.11 APs (Access Points), a fact stemming from the last-wireless-hop nature of 802.11 LANs.
In 802.11 WLANs, covering a cell requires the deployment of an AP which should to be cabled to the Internet through a wired backbone network. When another adjacent cell is to be connected, another AP has to be settled and wired to the Internet too and so on. This way, the settlement of further APs becomes more and more costly when the cells to cover are quite far from the backbone network. Furthermore, in case of dense regions, a parallel dense deployment of APs is needed to meet customers needs resulting in more cabling and settlement overhead. Even though, APs are relatively cheap, cabling APs and finding the appropriate canals for the wires is still expensive. In WMNs, no cabling is required except for the AP which will serve as a gateway towards the Internet (Even the gateway can be wirelessly connected to the Internet). All other APs do serve as routers and do route data on behalf of each other towards/from the gateway AP which is connected to the wired backbone network. This way covering a further cell is reduced to placing, without any cabling, an additional AP. Easing wireless coverage increases wireless coverage, a fact which is of tremendous importance to industry since more coverage involves more user connections and hence more return to industry. In this context, IETF is hardly striving to finalize the IEEE 802.11s standard which will pave the way towards a successful worldwide industrialization of this very promising technology.
In 2005, IETF did set a mesh networking TG to standardize IEEE 802.11s, the work is still in progress and the standardization process is expected to be final by late 2009. The last IEEE 802.11s TG meeting was held in last January, 2009. Even though the standard is not final yet, the main traits of the standard have been already set, e.g. IEEE 802.11s architecture and routing using MAC addresses. The IEEE 802.11s TG did set HWMP (Hybrid Wireless Mesh Protocol) as a default routing protocol to be present in all 802.11s compliant devices. Besides, Airtime has been set a default link quality metric to accompany HWMP as well - These two amendments are for the purpose of maitaining minimum compatibility between 802.11s devices. HWMP is a hybrid protocol that combines both a reactive and a proactive routing protocol. The novelty of the protocol is that it uses MAC addresses for routing.
IEEE 802.11s Overview:
802.11s started initially as a study group in 2003 then it was entitled as a Task Group in July 2004. The first draft was accepted in March 2006. The last draft, D2.00, was discussed in the last TG meeting in last January 2009 \cite{ieee}. The finalization of the standard is expected by late 2009. The standard is concerned with five main areas: 1. Architecture 2. Routing in MAC layer 3. MAC enhancements 4. Internetworking and 5. Security. In this work we are basically concerned with the first two and the fourth components. The next two paragraphs do highlight the main features of the first components.
IEEE 802.11s Architecture:
IEEE 802.11s defines three types of stations:
- MPs (Mesh Points): Wireless stations that perform routing only. MPs do not provide access point services.
- MAPs (Mesh Access Points): MAPs are mesh points, i.e having routing capabilities, with access point capabilities. MAPs do aggregate traffic from/towards legacy 802.11 stations. A MAP can be thaught of as a legacy Access Point which performs routing also.
- MPPs (Mesh Point Portal): MPPs are mesh points serving as gateways to other types of networks. MPPs do aggregate traffic from/towards the wired backbone network.
IEEE 802.11s MAC Routing:
Multi-hop routing is a key element in 802.11s. 802.11s performs routing using MAC addresses. To our understanding, the main motivation behind using MAC addresses, for routing, is allowing the MAC layer to access link quality measurements, a fact which will tremendously optimize routing decisions. In fact, routing metrics are, in wireless networks, at the heart of routing performance [4]. Unlike, wired networks, the quality of the wireless link is not stable and this is due basically to the inherent broadcast nature of the wireless link which results in interferences from undesired communication. Interferences, which are absent in wired networks, are the major inducer of frame losses in wireless networks, a fact that substantially affects wireless throughput specially with multiple wireless hops which is case with WMNs. Hence, wireless networks and especially multi-hop ones need access to link quality measurements in order to optimize routing performance and cope for the degradation in throughput. Access to wireless link measurements is by principle impossible at Network layer, when conforming to the OSI model, unless a cross layer design is adopted between the Network and MAC layers. In IEEE 802.11s, a cross-layer design between MAC and Network is implicitly incorporated without affecting the OSI model, this way and in a smart way the 802.11s MAC layer is still compact and transparent to above layers while performing routing.
802.11s uses either four or six MAC addresses for routing depending on the nature of the traffic. When both the source and destination are mesh points in the WMN, only four addresses are used. When at least the source or the destination is outside the WMN, i.e., a non-mesh point, e.g. a 802.11s legacy station, six addresses are used instead. 802.11s header frames bear an AE (Address Extension) mode bit that discriminates between the two modes. In case where WMNs are used for Last-mile Internet access, the AE bit is always set to 1 as both destinations and sources are non-mesh points.\\
Adding two extra MAC addresses, to the ordinary four 802.11 ones, is meant to preserve the MAC addresses of the non-mesh source and non-mesh destination, these later would be lost once the frame enters the mesh network. The six MAC addresses are:
- Destination MAC Address: It corresponds to the next hop MAC address.
- Source MAC Address: MAC address of the source.
- Destination Proxy Address: The MAC address of the MPP/MAP from where the frame will leave the mesh network.
- Source Proxy Address: The MAC address of the MPP/MAP from where the frame entered to the mesh network.
- Final Destination Address: The MAC address of the final non-mesh destination.
- Originator Address: The MAC address of the non-mesh station that originated the frame.
HWMP is a hybrid routing protocol that has both a Reactive and Proactive components. For the nature of this application, which is IEEE 802.11s WMNs for Last-mile Interent access, where are using the Proactive components. This later is an adaptation of the well-known AODV protocol which uses Airtime as a routing metric.
Implementation:
The system is made of three modules, see Figure 3, that communicate between each other using IPC (Inter Process Communication) shared memories: 1. Routing, 2. Data forwarding and 3. Link quality measurements. Only the last module (link quality measurement) is identical in all WMN nodes, i.e., MAPs, MPs and MPPs. For the two other modules, their implementation depends on the type of the node. Next sections detail implementation for each module and highlights how the implementations differ according to the type of the mesh point.
1. Routing in MPPs:
In MPPs, the Routing module is made of two sub-modules:
- PREQ-Broadcast Module: periodically broadcasts PREQ messages containing basically the MAC address of the local MPP, an incremental sequence number and a routing metric field.
- The RREP-Processing Module: processes RREP messages forwarded by intermediate MPs and originated from different MAPs. Upon reception of a RREP message, the MPP gets the MAC address of the sender MAP, looks up its entry it the MPP-Proxying-Table and updates the corresponding routing metric and the corresponding next hop. The RREP messages do set the forward path towards MAPs.
2. Routing in MPs:
In MPs, the MP-PREQ-Processing module processes two types of messages: PREQ and RREP messages.
- Upon reception of a PREQ message, the module has to check its freshness in order to process it as only fresher messages are to be considered. Every PREQ message bears a sequence number that is incremented by the issuing MPP. The module extracts first the MAC address of the sender MPP from the PREQ message then uses this address to look up its corresponding entry in the Forwarding Table. The Forwarding Table entries store, among other values, the last fresh sequence number of the concerned MPPs. Once the last fresh sequence number is retrieved, the PREQ message is discarded in case it corresponds to a non-fresh message, i.e. of lesser sequence number. If the PREQ message is a fresher one then the routing module updates its reverse path entry, towards the concerned MPP, in the MP-Forwarding-Table. Afterwards, the PREQ message is updated by adjusting the routing metric value: The module retrieves the corresponding routing metric value, e.g. ETX, ETT or Airtime, for the link from where it received the PREQ message, adds it to the current PREQ routing metric then rebroadcast the message. If the PREQ message is of equal freshness as the current sequence number, the PREQ message is then processed only and only if it corresponds to a better route. If it is the case, the PREQ is processed as if it was a fresh PREQ message.
- Upon reception of a RREP message, the MP gets the MAC address of the sending MAP, looks up its entry in the forwarding fable, and then updates the corresponding forward path to the MAP. To forward the RREP message, the MP looks up the destination MPP MAC address and retrieves its entry from the forwarding table. The retrieved entry contains the next hop towards the concerned MPP. Afterwards, the routing metric in the RREP message is updated and then forwarded to the next hop.
3. Routing in MAPs:
Upon reception of a PREQ message, the MAP_PREQ _Processing module retrieves the MAC address of the MPP which issued the PREQ message. The MAP retrieves then the entry, from the Proxying Table, that corresponds to the sender MPP and checks the freshness of the current PREQ message against the already stored freshness. If the PREQ message corresponds to a fresher route or corresponds to an equal freshness route with better routing metric, the corresponding entry in the MAP Proxying Table is updated. Afterwards, the routing metric value is updated the same way as with MPs.
However, the processed PREQ message can correspond to only a local better route, i.e., the best route leading to a specific MPP. Hence, there may be better routes to other MPPs. Selecting the MPP that has the best routing metric would fail in case the entry was updated a long time ago or in case the MPP is off. This problem was highlighted in section 5.1.1. To address this problem, we do timestamp all MPP routing entries in the proxying table. The timestamps correspond to the time at which the MPP routing entry was updated. This way we select the MPP that has the better route as well as a fresher route by comparing its timestamp to the current running time. We set a time threshold which is twice the MPP broadcast periods. We choose a twice period to account for the case when a broadcast has been accidentally lost. The best MPP is marked in the proxying table.\\
Once the proxying table is updated, a RREP message is formed and sent back to the selected MPP. The RREP message acknowledges the receipt of the MPP PREQ message and it plays also the role of an association message telling the MPP to associate the MAP with it. The RREP message bears mainly the MAC address of the MAP as well as the corresponding routing metric.
The Data Forwarding module implementation depends on the type of the mesh node.
1. Data Forwarding in MPPs:
MPPs have two network interfaces: an 802.3 interface and an 802.11 ad-hoc interface, a fact which results in processing two different types of frames.
- Upon reception of an 802.3 frame, the MPP Data-Forwarding module extracts the destination IP address from the 802.3 frame then fetches the corresponding MAC address and the associated MAP MAC address from the MPP Association Table. Once having the destination MAP MAC address, the corresponding next hop MAC address is retrieved from the MPP Proxying-Table and the appropriate 802.11s header frame is built. This later contains basically the six MAC addresses that will be used to get the frame through the 802.11s ad-hoc network, to its final destination. The six MAC addresses are built as follows:
- Destination MAC address: corresponds to the next-hop MAC address retrieved from the MPP-Proxying-Table
- Source MAC address: The MAC address of the sender, i.e., the MPP MAC address in this case
- Destination Proxy MAC address: The MAC address of the corresponding MAP
- Source Proxy MAC address: The MAC address of the MPP
- Final Destination MAC address: The destination MAC address which is retrieved from Association Table.
- Originator MAC address: The source MAC address in the received 802.3 frame
2. Upon reception of an 802.11s frame in its ad-hoc interface, the MPP reads the 802.11s header frame, gets the originator MAC address and its IP address and inserts an entry for it in the MPP association table. The entry contains the IP address, the MAC address and the associated MAP MAC address. Afterwards, the MPP strips off the 802.11s frame header and replaces it with an 802.3 frame header containing as a destination MAC address the default gateway (in the LAN interface) and as a source address the local MPP MAC address.\end{itemize}
2. Data Forwarding in MPs:
In contrast to MPPs, Data Forwarding in MPs is quite straightforward as it deals only with one type frames, i.e. 802.11s frames. However, the MP still receives two types of frames that differ in terms of their final destination being it either an 802.3 or an 802.11 network, i.e. is the final destination an MPP or a MAP?
The proxy type, i.e. a MPP or an MPP, is made transparent in our implementation by having the same type of entry in the MP forwarding table for all proxies.
Upon reception of an 802.11s frame, the MP extracts the destination proxy address, i.e., the MPP or MAP MAC address, consults its forwarding table and retrieves the corresponding entry which contains the next hop MAC address. The 802.11s frame is then updated by changing only two of the six MAC addresses in the 802.11s frame header, the remaining four ones are kept intact. The two updated MAC addresses are the destination MAC address and the source MAC address which become respectively the retrieved next hop MAC address and the MP MAC address.
3. Data Forwarding in MAPs:
MAPs have two network interfaces, an 802.11 Access Point interface and an ad-hoc 802.11s interface, which results in processing two different types of frames.
- Upon reception on an 802.11 frame, from its Access Point interface, the MAP first reads the source MAC address, and formulates the six MAC addresses in the 802.11s header frame as follows:
- Destination MAC address: It corresponds to the next hop MAC address, towards the best MPP, which is retrieved from the MAP Proxying-Table.
- Source MAC address: the MAC address of the local MAP.
- Destination Proxy Address: the MAC address of the MPP to which to forward the frame. It is retrieved from the MAP Proxying-Table
- Source Proxy Address: the MAC address of Local MAP
- Final Destination: Unknown at this stage. A NULL address is put in.
- Originator: the source MAC address in the received 802.11 frame.
2. On the other side, upon reception of a 802.11s frame in its ad-hoc interface, the 802.11s header frame is stripped off and replaced by a broadcast 802.11 header frame. Thereafter, the final 802.11 legacy destination will look up its IP address in the broadcasted 802.11 frame.
1. ETX
The ETX module is made of two sub-modules: The ETX-Broadcast module and the ETX-Collect module.
- The ETX-Broadcast module does periodically broadcast probe frames embedding the number of probe frames received in the reverse path from neighboring MPs during a certain time period T. The ETX-Broadcast gets these values from the ETX-Collect module.
- The ETX-Collect module reads probe frames broadcasted by other MPs, meanwhile looking up the corresponding number of probe frames received in the forward direction by the other MPs. The number of received probe frames in forward direction was embedded in by the ETX-Broadcast module. This later retrieved values are used to compute the forward delivery ratios. Besides, the ETT-Collect module records the number of received probe frames, in the reverse direction, from each neighboring MP during a certain period T and make it available to ETX-Broadcast. This number is used to compute the reverse delivery ratio.
2. Airtime
Reads the corresponding transmission rates using the "/Prof/file" system, gets the ETX values reported by the ETX module and then computes the corresponding Airtime value as specified by IEEE 802.11s.
3. ICE
To compute ICE, we used the capability of the Madwifi driver in allowing the creation of multiple virtual interfaces in the same card. We created two virtual interfaces in every mesh node: One is set to the "ad-hoc" mode and the other is set to the "monitor" mode.
In the monitor mode, the network interface card can overhear all all ongoing singals, hence having access to their strengths, rates and lengths ...etc. These different values are used to compute the SINR under the physical interference model by using a given probabilstic 802.11 traffic model.