ARCHITECTURAL SOLUTIONS FOR END-USER MOBILITY
5.2.4 Micro- and Macromobility Support
In this section we first describe a handover decision algorithm and then describe two approaches, for providing both intradomain and interdomain handoff support.
5.2.4.1 Vertical Handover Decision Scheme Using 802.21. A decision algo- rithm for vertical intra- and interdomain handovers, in IEEE 802.21-enabled [17]
networks, is presented in reference 18. The vertical handoff decision combines the strengths of both traditional RSS evaluation and multiple attributes decision making-based (MADM) algorithms. MADM methods are used to maximize the QoS
MESH NETWORKS 169 experienced by each user. In addition, the scheme leverages on network information provided by an 802.21 MIH information server. The performance of the scheme in terms of handover times and dropping rate compares favorably to traditional RSS- based and cost-function-based [19] vertical handover methods. Simulation results show that the dropping rate of the proposed scheme provides about 10% and 5%
improvement respectively to the RSS-based and cost function-based schemes.
In detail, since the handover decision problem deals with making the selection among a limited number of candidate networks with respect to different criteria, it is modeled as a fuzzy MADM problem. Fuzzy logic is used to represent the impre- cise information about traffic classes (i.e., conversational, streaming, background, and interactive). The fuzzy MADM method consists of two steps. The first step is to convert the fuzzy data into a real number. Analytic hierarchical process (AHP) [20] is used to derive the weights of QoS traffic parameters (attributes) for the differ- ent alternative networks. This is done by performing a pairwise comparison of these QoS parameters with respect to their importance to reaching a successful handover.
The parameters considered are traffic priority, data rate, error rate, delay, and jit- ter. The comparison scale uses the range of 1 to 9, each representing entries, as follows: 1 =equally important, 3 =moderately more important, 5 =strongly more important, 7 =very strongly more important, 9 =extremely more important.
The results of these comparisons are entered into a matrix, as shown in Table 5.1:
that matrix, if the number representing the greater weight is put into position (i, j), the reciprocal of that number must be put into position (j, i). AHP matrices can be calculated for each traffic class (conversational, streaming, background, and inter- active). To verify the consistency in judgement of the comparisons, the consistency ratio (CR) is used as an indicator. A matrixAis considered to be consistent if the following condition is satisfied:
aik∗akj=aij for alli, j, k=1, . . . , n
The essential idea of the AHP is that a matrixAof ranknis only consistent if it has one positive eigenvalueλmax=nwhile all other eigenvalues are zero. Further, the consistency index(CI) is used to measure the deviation from a consistent matrix:
CI=(λmax−n)/(n−1) Table 5.1 AHP Matrix for a Traffic Class
Priority Bit Rate Delay PER Jitter
Priority 1 7 1 7 1
Bandwidth 17 1 17 1 17
Delay 1 7 1 7 1
PER 17 1 17 1 17
Jitter 1 7 1 7 1
170 ARCHITECTURAL SOLUTIONS FOR END-USER MOBILITY
Table 5.2 Weights for the Given Traffic Class
Priority Bit Rate Delay PER Jitter
0.3149 0.0276 0.3149 0.0276 0.3149
Theconsistency ratio(CR) is then is defined as the ratio of theCIto the so-called random index (RI), which is aCIof randomly generated matrices:
CR=CI/RI
Forn(matrix rank) = 3,CRshould be less than 0.05, forn= 4 it should be less than 0.08, and forn≥5 it should be less than 0.10. The weights are computed using the geometric mean method, which is thenroot of their product. The resulting weights for the example in Table 5.1 are shown in Table 5.2.
The second step is to use classical MADM algorithms to determine the ranking order of the candidate networks by computing their score. There can be several meth- ods: in reference 21, two of them are presented, namely, simple additive weighting (SAW) and multiplicative exponent weighting (MEM). The score of selected network iby SAW is the weighted sum of all the attribute values:
Score(i)=n
j=1ωjrij
wherenis the number of attributes,ris the normalized attribute value, andωis the weighting value.
Normalization is required to efficiently compare attributes values of different networks.
In MEW, the score of network iis determined by the weighted product of the attributes:
Score(i)=n
j=1xωijj
wherexis the attribute value,nis the number of attributes, andωis the weighting value.
The proposed handover decision scheme is shown in Figure 5.5 and works in WiFi and WiMAX networks. The handover is triggered by the information of RSS level from PHY layer. Once a WiFi or WiMAX network interface is discovered and its received signal is acceptable, the terminal will start the network selection process.
Network information is retrieved by querying the MI information server (MIIS) [17].
The information provided by the MIIS includes neighbors, operation mode, user priority, data rate, delay, jitter, packet error rate, and updating time. An example of an information base stored in MIIS is shown in Table 5.3. The IEEE 802.21-enabled terminal is able to periodically get this information by using its current network interface. If the RSS is smaller than the predefined RSS threshold, the algorithm calculates all possible networks score functions and selects the best one. In terms of
MESH NETWORKS 171
Current network is WiFi?
Rss<Rss trigger?
Y
802.11&16 neighbor discovey & MIIS query
information
Rss<Rss threshold?
Calculate networks score functions and choose the
best one
Y
N
N
N
802.11&16 neighbor discovey & MIIS query
information
Any AP nearby?
N
AP score higher than current score?
N
Handover
Y
Figure 5.5 The proposed MADM handover decision scheme for vertical handover between WiFi and WiMAX.
172 ARCHITECTURAL SOLUTIONS FOR END-USER MOBILITY
Table 5.3 Information Base in MIIS
SSID MAC address Operation Mode Connection # PER Update
AP1 00:90:3E:23:04:A2 11g 12 3.28e-3 11:10:52
AP2 00:14:7C:4E:21:7A 11g 3 1.40e-4 11:10:51
BS1 00:8A:5F:D1:7E:14 16e 5 1.15e-3 11:10:48
priority, WiFi networks are assumed to have higher priority than WiMAX networks since they have high data rate and they are cost-effective. For this reason, if the current network connection is WiMAX and a WiFi network with higher score than the current one is discovered nearby, then an handover is triggered.
The performance of the handover decision scheme is evaluated by simulation and is compared with two other schemes:RSS-based schemeandcost-function-based scheme. The RSS-based vertical handover algorithm triggers an handover if an 802.11 access point or a WiMAX base station with stronger RSS is found nearby. The cost function-based algorithm computes the cost of networkias
Cost(i)=n
j=1EijQij where:
n is the number of attributes.
Eij is the elimination factor. It indicates whether the minimum constraint for attributej can be met. It results in a large value if constraint cannot be met (1 if constraint is satisfied).
Qij is the QoS factor. It is the normalized natural log value of attributej.
The cost-function-based algorithm then selects the network with lowest cost func- tion. The attributes include user priority, data rate, delay, jitter, error rate and RSS.
The simulation result showed that the proposed schemes provide better perfor- mance than the RSS and cost-function-based schemes in terms of total handover time and average dropping rates.
5.2.4.2 SMesh. The first approach for micro- and macromobility provisioning is SMesh [22]. SMesh provides a 802.11 mesh network architecture and protocols that optimize routing, to provide both intradomain and interdomain handoff.
Intradomain handoff is achieved by working inad hoc mode(IBSS), controlling the handoff from the mesh infrastructure, and by using multicast in the mesh network to send data through multiple paths to the mobile client during handoff. APs in the vicinity of the client monitor the connectivity quality and synchronize on which should be the one to handle that client. Until this happens, data packets from the Internet gateway to the client are duplicated by the system in the client’s vicinity.
Interdomain handoff is achieved by using multicast groups through the wired network to coordinate decisions and seamlessly transfer connections between Internet gateways as mobile clients move between APs.
MESH NETWORKS 173 The communication infrastructure of SMesh relies on an overlay messaging sys- tem, which is used by APs for forwarding connections and for the coordination be- tween them.
SMesh assumes that all mesh routers use the same AP channel, which is the domi- nant deployment strategy in 802.11 WLANs, where reduced interference is obtained by assigning nonoverlapping channels to the AP channels of adjacent mesh routers.
This implies that a mobile station needs neither scan other channels nor switch to the AP channel of the new MR during the Layer-2 handoff, thus reducing the hand- off latency. However, this assumption can represent a hard constraint. Furthermore, SMesh minimizes the handoff latency at the price of high signaling cost: overhead is generated for managing clients during handoff and for maintaining network topology.
The experiments demonstrate that the management overhead for intradomain hand- offs grows linearly with the number of clients, in the worst case at a rate of about 2 Kbps per client. The interdomain overhead, instead, is directly proportional to the number of connections each client has, and it can be remarkable.
The experiments demonstrate that the overhead caused by duplicate packets during handover is low. For example, when a full-duplex VoIP stream is sent between a mobile client and an Internet host, most handoffs experience about two duplicates toward the mobile clients and none in the other direction.
SMesh Detailed Description. The software architecture of SMesh is composed of two main components: the communication infrastructure and the interface with mobile clients (Figure 5.6).
The communication infrastructure of SMesh relies on the Spines messaging sys- tem [23]. The Spines overlay network interconnects all mesh nodes through direct links in the wireless network and through virtual links in the wired network. Each wireless mesh node instantiates a Spines daemon to forward messages within the wireless mesh. Spines also allows to use multicast and anycast functionality. Each Spines daemon keeps track of its own direct neighbors by sending out periodic hello messages. Based on the available connectivity, each node creates logical wireless links with its direct neighbors. A link-state protocol [24], which is based on the graph of the connectivity to the entire network, is used by nodes to exchange routing infor- mation with other nodes. The nodes flood link-state information (topology changes) using reliable links between direct neighbors.
In the SMesh architecture, a mobile client maintains the same network information (IP address, Netmask and Default Gateway). Connectivity information is provided by DHCP servers, which run on each mesh node. The IP address assigned to each mobile client is computed using a hash function on the client’s MAC address (mapped to a private address) and is advertised on a multicast control group (Client Data Group—
CDG). In case of a hash collision, the client with the smallest MAC keeps the current IP and any other client in the collision gets a managed IP. The default gateway is set to a virtual IP address, which is mapped to a mesh node hardware address.
As discussed above, each mobile client is associated with a multicast group (CDG), which comprises mesh nodes in its neighborhood. A mesh node joins a CDG if it believes it has the best connectivity to a mobile client based on link quality metrics
174 ARCHITECTURAL SOLUTIONS FOR END-USER MOBILITY
Mesh Network DHCP Client
DHCP Server
Intra-domain Handoff Algorithm
Unmodified Mobile Client Device
Interdomain Handoff Algorithm
Overlay Router
Link-state Routing Group Multicast
Internet Client Link Quality
Control Group
Internet Gateway Control Group NAT Client
Data Group ARP
Communication InfrastructureInterface with Mobile Clients
Applications
Figure 5.6 The SMesh architecture.
it receives from other nodes. If the destination of a packet is a SMesh client, the packet is sent by Spines to the SMesh nodes that joined that client’s Data Group using a multicast tree. With this mechanism, a client could receive duplicate IP packets.
However, duplicate IP packets are dropped gracefully at the receiver (TCP duplicates are dropped at the transport level, and applications using UDP are supposed to handle duplicates).
If the destination of a packet is the Internet, then the packet is sent by the originating client’s access point to the closest Internet gateway by forwarding it to an anycast group that all Internet gateways join (an anycast data message follows a single path in a tree to the closest member of the group).
In SMesh, mobile clients and APs are configured in ad hoc mode (IBSS). This is done for saving the time for scanning and for associating to the new AP. Furthermore, this is chosen to actually control the handover solely from the APs.
In SMesh, the intradomain handover process is composed of two distinct processes:
mobile client monitoringandclient handoff.
Mobile Client Monitoring (Seamless Heartbeat). Each SMesh node periodically com- putes a client link quality evaluation based on one of the two following metrics:
observed loss of a client’s DHCP requests or ARP responses.
MESH NETWORKS 175 When using the SMesh DHCP monitor, each DHCP server instructs the mobile clients to periodically renew their IP address, thus serving as a heartbeat to keep track of the client. This is achieved by setting theT1 (Renew) timer of the standard DHCP protocol [25], which instructs the client to start unicasting DHCP requests (DHCPREQUEST) after the timer expires. The main drawback of this method is that it employs a non-negligible overhead as aDHCPREQUEST packet is at least 300 bytes long, aDHCPACK that is about 548 bytes. Another downside is that when the firstDHCPREQUESTis lost, the time between this request and the next is platform-dependent and usually more than several seconds [26].
In the ARP monitoring scheme, each mesh node in a CDG periodically sends an ARP request to the client, and all nodes in the vicinity use the reply to compute the metric. ARP [27] protocol is used for mapping an IP address to a hardware address (MAC). ARP is used when a host wants to communicate with another host inside the same network, but it does not know its MAC address. When a host receives an ARP request, it compares the destination IP with its own IP address: the IP address matches, it will issue an (unicast) ARP reply, filling in the information contained in the MAC field with its own MAC address. The advantage of using this approach is that, unlike DHCP, ARP packets are very small (only 28 bytes).
The client link quality metric computed by each SMesh node is based on the observed loss of a client’s DHCP requests or ARP responses, using the weighted average decay function:
Mnew=Mold∗Df +Current∗(1−Df), 0< Df <1
whereMis the link quality measure andDf is the decay factor (the value used in SMesh is 0.8).Currentis a constant value that is set to 0 if an access point did not receive any DHCP or ARP probe packet’s responses in the expected time, or is set to a maximum value (50) if a probe packet is received. If two or more access points have the same integer metric, the access point with the lowest IP is chosen.
To get a more reliable measure of the monitored link quality, the decay function described above is combined with RSSI (received signal strength indicator) and loss rate measurements. RSSI measurement is obtained by configuring the wireless inter- face of the mesh nodes in monitor mode. In that configuration, an additional header is added by the wireless driver, which contains the RSSI information. Loss rate refers to the number of packet retransmissions of the 802.11 protocol. Every unicast packet transmitted in 802.11 needs to be acknowledged by the recipient. If the packet is lost, the sender retransmits the packet and sets a retransmit flag in the 802.11 header.
In addition to the previously described CDG, used to forward data packets in SMesh toward the APs serving the client, the APs in the client’s neighborhood join a different multicast group specific to that client, called Client Control Group (CCG).
CCG is used to share with other mesh nodes in the client’s vicinity the link quality metric for a client and to decide which AP is best to serve that client. A mesh node joins a client’s Control Group when it receives one heartbeat from the client, and it leaves the group after not hearing from the client for some time.
176 ARCHITECTURAL SOLUTIONS FOR END-USER MOBILITY
Intradomain Handoff. To provide a transparent handoff to clients, mesh nodes ad- vertise a virtual gateway IP address to all clients as part of their DHCP offers and acknowledgments (DHCPOFFERandDHCPACK). Mobile clients set their de- fault gateway to this virtual IP address regardless of which AP they are connected to. This virtual IP address is then mapped to the real gateway MAC address with the mechanism described in the following.
The handoff process starts when a mesh node believes it has the best connectivity to the client and its metric is at leastThresholdhigher than the metric of the current AP serving that client (i.e.,Metric > MetriccurrentAP∗(1+Threshold)). Typical value for theThresholdis 12%.
The mesh node then sends a gratuitous ARP message as a unicast, directly to the client. A gratuitous ARP is an ARP reply packet that is not sent as a reply to an ARP request, but is rather sent in the local network voluntarily. Upon receiving such a packet, a mobile client will update the MAC address of its default gateway, in its ARP cache, with the value contained in the ARP message sent by the mesh node.
In addition to sending a gratuitous ARP to the mobile client, the mesh node joins its Data Group so that packets destined to the client start flowing through this access point. If another node is also a member of the Data Group, packets destined to this client are forwarded to both mesh nodes, and each of them forwards the packets directly to the mobile client, which may receive duplicate packets. The use of multicast during handoff has the significant advantage to achieve uninterrupted connectivity by (1) sending packets through multiple access points to the mobile client, to deal with unexpected client movements while the best access point for the client is chosen, and (2) avoiding loss while route changes take place in the wireless mesh. The main drawback of this mechanism is the generation of local multicast overhead. However, as described in the following, this traffic can be narrowed. When a mesh node that is a member of a CDG receives a link quality metric update that shows that a different node in the Data Group is better connected, it issues aLeave Request. A Leave Request can be acknowledged only by a node in the Data Group that believes it has the best connectivity to the client. A node may leave the Data Group if and only if its request is acknowledged by at least one other node.
Another drawback of this solution is that the performance of handoff depends on the value of the parameters for indicating the link quality metric. In general, the smaller the decay factor in the link quality metric, the quicker the client will be able to react to changing conditions. However, a small decay factor can trigger unnecessary handoffs and increase the amount of overhead in the system. In contrast, a large decay factor can delay handoffs for too long and lead to loss. In short, these tradeoffs must be balanced to achieve the desired performance.
Interdomain Handoff. As mentioned above, in SMesh communication between mo- bile clients and the Internet is relayed through the closest Internet gateway to improve wireless usage. When the client moves to a different connectivity island, packets might be relayed to a different gateway closer to the client. Changing one endpoint of the connection (i.e., the IP address of the Internet gateway) is often impossible without