Multicast Based Micro-Mobility: Design and Analysis.



Introduction

With the proliferation of compact laptops and other Internet enabled devices such as mobile phones, palmtops etc. more people are accessing the web while on the move. Mobile IP [Perki1] provides the primary framework for mobility in the IP layer. Streaming video and audio are also becoming increasingly popular. With the increased use of multimedia, it is important for the protocols that support mobility, to provide seamless connectivity to these devices.

Today's protocols that support mobility [Perki1] lack in many respects. Mobile IP has the disadvantage of contacting the home agent every time a handoff takes place, which leads to long delays and packet loss. This adversely affects the performance of the transport protocols. In Mobile IP, the time taken to exchange registration / authentication and handoff messages is of the order of roundtrip time [Helm3], [Myso1] between the home agent and the mobile node (MN). When the MN moves from one sub-domain to another, within a domain, authentication and registration messages have to be sent all the way to the home agent. This can be large in case of a wide area network. Such long and frequent periods of packet loss and delays can be detrimental to the performance of real-time applications. The effect of frequent handoffs (every time the MN changes its foreign agent) can be very annoying to the user. One of the solutions is to hide the micromobility (micro-mobility - mobile node moving between the sub-domains of a single domain) from the home agent so that the MN need not incur performance degradation during intra-domain handoff. When multicast based mobility protocol is used to achieve micro-mobility, a significant reduction in handoff delays is observed [Helm3], [Helm4]. The following figure illustrates the intended use of Multicast based Micro-mobility Protocol.

Overview
Figure 1 : Architectural Overview



Some of the goals [Helm3] of such a micro-mobility protocol are:


The main goal of this work is to design the Multicast based Micro-mobility Protocol keeping [Helm4] as the primary framework for the architecture. The proposed architecture in [Helm4] is Mobile IP for inter-domain mobility and multicast based mobility scheme for intra-domain mobility. When the mobile node moves into the new domain, it will do a Mobile IP handoff from the previous domain. In the new domain, the MN is assigned a domain wide IP address, which becomes its care of address (COA) and the domain specific multicast address is inferred from the COA using algorithmic mapping as described in [Helm4]. The packets destined to the MN are tunnelled to it through a multicast tree. As the MN moves, the multicast tree is extended to the new LAN by sending join messages to that multicast group.

Route level simulations carried out on large and varied topology sets in [Helm3] and [Helm4] have shown that the performance of multicast based scheme is better than other IP micro-mobility protocols. These simulations however do not include packet level simulation. Packet level simulations are required to evaluate other important parameters like handoff delay, packet loss and jitter. Simulations carried out in [Camp2], [Ramj2] and [Valk1] to evaluate the performance of Handoff-Aware Wireless Access Internet Infrastructure (HAWAII) [Camp3] and Cellular IP (CIP) [Ramj1] are limited to a very small set of topologies with many simplistic assumptions like perfect wireless interface, no control packet loss etc. Extensive and realistic simulations over a wide range of topologies and scenarios are needed to evaluate the performance of the above protocols.

The micro-mobility schemes like CIP and HAWAII run their own protocol to setup the trees or routes where as, the multicast based mobility protocols make use of the existing multicast protocol to deliver packets from the domain wide foreign agent to the mobile node. Significant amount of work has been done in designing and refining multicast protocols taking robustness and other issues into consideration. Hence it is best to reuse the existing multicast routing protocol rather than go through the same process of redesigning and refining the tree building / routing protocols run by other micro-mobility protocols.

The main aim of this work is design and evaluation of Multicast based Micromobility Protocol. It involves interaction of multicast protocols, the Multicast based Micro-Mobility Protocol and the Medium Access Control (MAC) protocols in the last hop wireless link. So far, no detailed study of this interaction has been done. One of the goals of this study is to understand the intricacies of such protocol interactions. STRESS methodology has been used to do this study. The Multicast based Micro-Mobility Protocol has been modelled using STRESS semantics to investigate scenarios involving loss of control messages. Some of the issues that have been addressed while designing the multicast based mobility protocol are choice of the underlying multicast protocol, mobility detection procedure and its associated messages, handoff procedure and its associated timers and messages. These timers in turn interact with other timers to produce different results under different scenarios. Each of the above is discussed in detail in various sections of my thesis.


Architectural Framework

Significant amount of work has been done in the field of IP mobility. Mobile IP forms the primary framework for most designs. Multicast based mobility architecture takes advantage of the following characteristics of multicast to deliver packets to the mobile node.

Once the MN  is registered in the new domain, it receives a domain wide Regional Care of Address (RCOA). The RCOA is a special address as it is valid through out the domain. All the routers in a domain can recognise the domain wide RCOA and infer its corresponding multicast care of address (MCOA) using the algorithmic mapping proposed in [Helm4]. The scope of MCOA is local to the domain where as the scope of RCOA is global. Depending on the handoff scheme in use, the mobile node sensing movement into another sub-domain, either presents its domain wide unicast IP address to the router, so that the router can infer its multicast address and send joins or sends an explicit join to the multicast group to which it belongs to. Issues of domain wide unicast address assignment, address duplication and algorithmic mapping of the unicast to multicast address are described in detail in [Helm4].


The following figure shows the functioning of a typical multicast based mobility protocol. Nodes 8 through 11 act as the wireless base stations, connecting the wired and the wireless networks. Source at node 0 is communicating with the MN. A multicast tree is built, rooted at the source. Packets from the source are delivered to the MN through the multicast delivery tree.




M&M



Figure 2: MN receiving packets from source (node 0).

When the mobile node moves from the coverage of base station 8 to that of 9, it initiates a handoff procedure, which causes the packets to be delivered from Node 1 to the MN through Node 4 as shown in Figure 3. The handoff procedure at its simplest involves the MN joining the multicast group to which it belongs after it moves into the area covered by another base station. The other branch of the multicast tree through Node 3 either times out or is explicitly pruned by the leave message sent by the mobile node before handoff. Figure 2.2 also depicts the old and unused branch of the multicast being pruned.

M&M


Figure 3: Illustration of packets being delivered to new branch.




For further infomation on design, analysis of Multicast based Micro-Mobility Protocol, please refer to my thesis.


Performance Analysis

Performance Analysis Simulation is the primary method that has been used to evaluate the performance of the Multicast based Micro-mobility Protocol. The network simulator, ns-2 [ISI1] has been modified to incorporate the Multicast based Micro-mobility Protocol. The implementation of the base station class was changed to incorporate multicast routing. The implementation of the mobile node class was changed to incorporate the mobility detection and handoff schemes. Simulations were conducted over varied set of topologies taking into account various factors that can affect the performance of the protocols.

The following performance metrics are used to evaluate the performance of multicast based micro-mobility protocol 

Packet loss is not considered as a metric for evaluation of the protocol as it is a function of packet rate, handoff delay and mobility of MN. To compare the performance of different micro mobility protocols, similar mobility detection and handoff mechanisms have to be used. It is extremely important to 45 compare protocols using similar schemes as mobility detection and handoff profoundly affects the performance of the micro mobility protocols. Mobility detection need not necessarily be a part of the micro-mobility protocol as this can be better achieved with additional information from lower layers.

Simulation Scenarios : To study the factors affecting the performance of the micro-mobility protocols, a rich set of scenarios have been simulated. Both mesh and tree like topologies with varying depths have been used. Random mobility pattern is used to stress the handoff mechanism. The primary objective of performance evaluation was to observe the effects of the micro-mobility protocol mechanisms on performance metrics and packet delivery. To prevent mechanisms of other protocols (like congestion control mechanism of TCP) affecting the performance metrics, CBR over UDP was chosen over FTP over TCP.

Simulation results

Simulations were carried out over different topologies, varying various parameters like beacon timer, overlap of wireless coverage and link delays. Since mobility detection can be more efficiently done at the lower layers and mobility detection mechanism itself not being a part of the protocol, simulations were set-up such that mobility detection always happened when the MN moved from one base station to the other. Since overlap of wireless coverage is also a factor not controlled by the micro-mobility protocol, overlap of 30m (same as the one used in [Camp2]) was used. Simulations were conducted using lesser overlap and larger beacon intervals (several times greater than 200ms). There were situations when a very large number of packets were lost. This was mainly due to failure of mobility detection rather than the failure of micro-mobility protocol. To prevent failure of mobility detection from affecting performance parameters, simulations were set up such that mobility detection always happened correctly. All the graphs follow a common format. Each parameter is evaluated for Multicast based Micro-mobility protocol, CIP and HAWAII (in that order from left to right). Each graph consists of three such sets corresponding to link delays of 10ms, 5ms and 2ms (again from left to right). This is indicated clearly on the  x  axis. For each protocol, the performance parameters are recorded for different path lengths from fork router to old and new base station. This is indicated on the  y  axis. The shading of the bars corresponding to different path lengths is indicated by the legend. The  z  axis represents the performance parameters being evaluated.


Handoff Delay: Figures 4 illustrates the handoff delays incurred by Multicast based Micromobility Protocol, CIP and HAWAII for topology 2 with link delays 10, 5 and 1ms. From the graphs, we observe that the handoff delay for M&M and CIP is extremely small as compared to that of HAWAII. The main reason for this is the difference in handoff schemes being used by HAWAII as compared to that of CIP and Multicast based Micro-mobility Protocol. CIP and Multicast based Micromobility Protocol use bi-casting for smooth handoff. The transition from one base station to another base station is so smooth when bi casting is used that the mobile node sees no handoff delay. However, the HAWAII using the MSF, a buffer and forward scheme consistently incurs long handoff delays.


Delay

Figure 4: Handoff Delay


Handoff Jitter:  The variation in handoff delay is negligible for Multicast based Micro-mobility Protocol and CIP. In spite of the changes in the path length from the fork router to the old and new base station, there is no variation. This indicates that the handoff delay is independent of the path lengths. The variation in handoff delay for HAWAII is large and of the order of the link delays. The greater the difference in like delays, the greater is the handoff delay. It can be concluded from the graphs that the jitter in MSF type of handoff in HAWAII is dependent on the difference in the number of links from the fork router to the old and new base station.


Packet Reordering: Packet reordering is measured in two parts, the depth of packets reordered and the duration for which the reordering occurs.

depth

Figure 5: Depth of Reordering


Figures 5 shows the depth of reordered packets. This is measured as the maximum difference in sequence numbers of consecutive packets. Depth of reordering rather than the number of packets reordered is measured because depth of reordering indicates the size of buffer needed to re-sequence the out of order packets. It is clear from the graph that the depth of reordering is small for Multicast based Micro-mobility protocol and CIP, where as it is large for HAWAII. The out of sequence packets in Multicast based Micro-mobility Protocol and CIP is dependent on the difference in the link delays from fork router to old and new base stations. The greater the difference, the greater will be the depth of reordering. However, the reordering depth in HAWAII is large, as in the MSF handoff scheme, the old base station buffers packets and then forwards it to the new base station via the crossover router. The crossover router will forward the new incoming packets to the new base station at the same time. This results in packets reaching the new base station out of order. The depth of reordering is heavily dependent on the buffering duration and the link delays from the cross over router to the old base station.

Its also important to observe the duration for which reordering of packets occur. In Multicast based Micro-mobility and CIP, the reordering occurs as long as bi casting is done. However, in HAWAII, reordering duration depends on the number of packets buffered at the old base station and the link delay from the old base station to the crossover point. Figure 6 illustrates the duration for which reordering occurs in topology 2.


Duration

Figure 6: Reordering Duration


Packet Duplication: Multicast based Micro-mobility protocol and CIP incur heavy packet duplication. Packet duplication occurs due to bi casting. The duration for which packet duplication occurs is same as the duration of bi casting. MSF scheme of HAWAII incurs no packet duplication. Here the duration of packet duplication is considered rather than the absolute number of packets duplicated, as it depends on packet rate. The bi casting duration is usually fixed and it depends on the topology and wireless coverage overlap. Figures 6 is a  good indicator of duplication duration for Multicast based Micro-mobility protocol and CIP. The duplication duration is zero for HAWAII, as MSF handoff does not duplicate packets.

Routing Efficiency: Assuming the root of the tree starts at the border router, multicast based micro mobility protocol and CIP use the shortest path to the MN. The path taken by data packets in HAWAII depends on the topology and mobility of the MN. The following figures illustrate the path taken by packet in HAWAII.

sub1
Figure 7: Suboptimal routing in HAWAII.



The above figure illustrates packets being delivered to the MN from the correspondent host. Node 0 is assumed to be the border router and also the root of the tree. The mobile node moves from base station 11 towards base station 7. As the MN moves, the routing algorithm of HAWAII finds the cross over router and establishes route from it to the new base station. (Cross over router is the router at the intersection of the shortest path from old base station to the root of the tree and the shortest path from new base station to the old base station). Here the cross over router happens to be node 11. As the node moves from base station to base station, it establishes routes from the old base station to the new base station as shown in the following figure. The following figure illustrates the effect of the definition of  cross over router  on routing efficiency.

sub2

Figure 8: Suboptimal routing in HAWAII.


As the MN moves from base station 10 towards base station 7, the packets are forwarded from 10 to 9 and then from 9 to 7. The following figure illustrates the path taken by packet originating from 0, destined to the MN.


sub3

Figure 9: Suboptimal routing in HAWAII





sub4


Figure 10: Suboptimal routing in HAWAII

(The NAM animation trace file for the above scenario is available here.)

The routing efficiency of HAWAII is a function of topology and node mobility. Routing in HAWAII is generally less efficient than that of Multicast based Micromobility protocol and CIP.


Analysis of Simulation Results

From simulations conducted, the following observations can be made


Other Observations: HAWAII and CIP create MN specific routing entries to route packets from the BR to the MN. Multicast based Micro-mobility Protocol, however creates multicast entries specific to the MN s MCOA. Assuming the root of the tree is the BR, the number of entries for Multicast based Micro-mobility Protocol and CIP are the same as both use shortest path tree. In case of HAWAII, the number of routing entries may be more due to inefficient routing. State scaling properties of the three protocols are the same as all of them create mobile specific routes. It is not very clear how HAWAII and CIP handle situations where the domain has more than one border router (BR). If packets enter the domain from a border router and leave the domain from another border router, routing in CIP fails. Multicast based Micro-mobility protocol handles these situations very easily, as mechanisms exist in PIM-SM to deliver packets to the RP irrespective of the location of the sender (BR at which the packet enters the domain). Such a situation however decreases the routing efficiency, as packets will need to be first tunnelled to the RP and then delivered to the MN through the multicast tree. To alleviate this situation, PIM-SM can be configured such that only the BRs get elected as the RPs. Doing this ensures efficient routing within a domain. The routing protocol of multicast has been designed taking into account intermediate routers connected to LANs. To fix the routing of CIP and HAWAII in such cases require emulation of the routing mechanism of multicast protocols.



Conclusion

The design of Multicast based Micro-mobility Protocol has given an insight in to the mechanisms required for protocol correctness. Extensive and rich set of simulations has shown the performance of the Multicast based Micro-mobility Protocol as well as the other micro-mobility protocol critically depends on the mobility detection and handoff scheme being used. This is very apparent while comparing the performance of Multicast based Micro-mobility protocol with that of CIP and HAWAII. Multicast based Micro-mobility protocol and CIP using the bi casting handoff scheme perform very similar (with respect to packet delivery parameters) where as HAWAII using a MSF, a different handoff scheme compared to bi casting, performs very different. Hence we can conclude that the type of mobility detection and handoff mechanism being used dominates the packet delivery performance. At the routing level, Multicast based Micro-mobility protocol and CIP use the shortest path to route packets from the BR to MN, whereas HAWAII can construct sub-optimal routes under certain conditions. Architecturally, Multicast based Micro-mobility scores over both CIP and HAWAII with the ability to handle situations where packets can enter / exit the domain through more than one border router. CIP routing fails is such cases where as no mechanism is specified for HAWAII to handle such situations. From this exercise, it can be concluded that Multicast based Micro-mobility Protocol is a promising approach to micromobility.



References