State Analysis and Aggregation Study for Multicast-based Micro Mobility
State Analysis and Aggregation Study for Multicast-based Micro Mobility
Ahmed Helmy
Electrical Engineering – Systems Department
University of Southern California, Los Angeles, CA 90089
helmy@https://www.wendangku.net/doc/418632722.html,
Abstract- We propose intra-domain multicast-based mobility as a solution for IP mobility. Our architecture addresses serious problems with existing IP mobility proposals; mainly scalability and handoff performance. In our scheme mobility proxies are used to allocate per-domain multicast addresses to mobiles for use in micro mobility. State aggregation is studied as an essential element to improve scalability of our approach. We introduce a simple, yet very efficient aggregation algorithm, based on bit-wise lossy aggregation. An important result obtained indicates that state tends to be concentrated in less than 20% of the nodes and that our scheme is extremely efficient in reducing the state in those nodes. We show that our scheme achieves much higher aggregation gain than conventional prefix-based aggregation.
I. I NTRODUCTION
IP mobility addresses the problem of changing network point-of-attachment transparently during movement. Mobile IP[4][5] is the current IP mobility standard. However, several studies [1][3][7] have shown that Mobile IP has poor performance during handoff due to communication overhead with the home agent. Micro-mobility techniques attempt to improve handoff performance by either using per-domain foreign agents[7][26][27] (or hierarchical approaches) or by using complex caching and forwarding techniques between the previous location and the new location[5][24][25]. In this paper, we introduce a new multicast-based mobility scheme for micro-mobility and show that it outperforms other micro-mobility approaches while, at the same time, providing a simpler solution.
In multicast-based mobility each mobile node is assigned a multicast address to which it joins through base stations it visits throughout its movement. Handoff is performed using standard join/prune mechanisms. Multicast-based architecture for inter-domain mobility suffers from serious scalability problems concerning multicast state growth with the growth in number of mobile nodes. The architecture also requires ubiquitous multicast deployment and more complex security measures. To alleviate these problems, we propose an intra-domain multicast-based mobility solution, in which a mobile node is assigned a multicast address within a domain that it uses for micro mobility. The allocated multicast address is locally scoped (i.e., unique only domain-wide). This allows for a domain-wide address allocation scheme, in which a group of mobility proxies allocate multicast addresses for visiting mobiles. These addresses are locally-scoped and are used temporarily by the mobiles for micro mobility while moving within the domain. Mobile proxies perform inter-domain mobility on behalf of visiting mobiles, then multicast-tunnel the packets to the mobile. The multicast address of a mobile does not change while moving in-domain.
Since the multicast addresses are locally-scoped and the joins go through the mobility proxy, the multicast address allocation scheme is performed per-domain (as opposed to requiring an inter-domain architecture). Also, this provides potential for multicast state aggregation opportunities. As an main contribution of this paper we thoroughly study and evaluate various multicast aggregation techniques. Our analysis shows that our new bit-wise lossy aggregation achieves aggregation gain much higher than the traditional prefix-based aggregation schemes. We observe that multicast state distribution in our case is non-uniform among network nodes, and that our scheme achieves substantial state reduction for nodes with high state concentration. This study is the first to address state aggregation for IP mobility and one of the very few to address multicast state aggregation.
The rest of this paper is organized as follows. Section II gives an overview of multicast-based mobility, its promise and its problems. Section III presents our inter-domain multicast-based architecture for micro-mobility. Section IV discusses state aggregation, while Section V presents simulation results and analysis. Related work is discussed in Section VI and Section VII concludes.
II. Multicast-based Mobility
In multicast-based mobility, each mobile node (MN) is assigned a multicast address. The MN, throughout its movement, would join this multicast address through the locations it visits. Nodes wishing to send to the MN send their packets to a multicast address, instead of sending their packets to a unicast address. Because the movement will be to a geographical vicinity, it is highly likely that the join from the new location (to which the mobile has recently moved) will traverse a small number of hops to reach the already-established multicast distribution tree. Hence, performance during handoff will be improved drastically. An overview of this architecture is given in Figure 1. As the MN moves, it joins to the assigned multicast address through the new base station. Once the MN starts receiving packets through the new location, it sends a prune message to the old base station to stop the flow of the packets down that path. Thus completing the smooth handoff process.
Handoff performance is function of the number of links traversed by control messages to bring data packets to the new location. As shown in Figure 2, in mobile IP (MIP) [4], registration request is sent to the HA; i.e., traverses path ‘B’, whereas in MIPv6 with route optimization [5], the binding updates are sent to the CN; i.e., path ‘C’. Another class of protocols uses what is called seamless handoff[24][25], in which packets to the new location are forwarded by the
previous location traversing ‘P’ links, as in Figure 2 (b). In our multicast-based mobility approach join messages need to reach the multicast tree traversing ‘L’ links. Besides being the simplest of the above approaches, our approach achieves the best handoff performance where average B/L and C/L are between 2.3 and 4.1, and average P/L is above 1.251.
Figure 1. Multicast-based mobility. As the MN moves, as in (b) and (c), the MN joins the distribution tree through the new location and prunes through
the old location.
Correspondent
Figure 2. (a) Triangle Routing . (b) As the MN moves from node 1 to 2,added links ‘L’ is 3 and links to previous location ‘P ’ (dashed lines) is 2. As it moves from 2 to 3, L =0, P =2.
In spite of such promise, many compelling issues need to be properly addressed to realize multicast-based mobility in today’s Internet. These issues raise major concerns about the practicality and applicability of multicast-based mobility,including scalability of multicast state, multicast address allocation, requiring ubiquitous deployment of multicast, and security overhead during handoff. We discuss these issues and present an architecture offering a common solution to alleviate and hopefully eliminate these problems.
Scalability of Multicast State. Each mobile node is assigned a multicast address to which it joins throughout its movement.The state created in the routers en-route from the MN to the sender is source-group (S,G ) specific state. With the growth in number of mobile nodes, and subsequently, number of groups (G ), the number of states kept in the router increases.In general, if there are ‘x’ MNs, each communicating with ‘y’senders on average, with average path length of ‘l ’ then routers in the network should create ‘x.y.l’ (S,G) states. This does not scale.
Multicast Address Allocation. The problem of multicast address allocation is a research problem in the Internet
1
This was obtained through extensive simulations not shown here for
brevity. For more detail see[1]. This is not the focus of this paper, however.
community [10]. This problem is exasperated by requiring each MN to have a globally-unique multicast address. Aside from the fact that the multicast address space is restricted for IPv4, using a global multicast address for each MN may be wasteful and requiring uniqueness may not be practical.
Ubiquitous Multicast Deployment. In order to implement inter-domain multicast-based mobility, inter-domain multicast routing needs to be in place. Unfortunately, this requirement restricts the applicability of our inter-domain mobility architecture.
Security Overhead. Security is critical for mobility support,where the continuous movement and change of attachment point is part of the normal operation. Such setting is prone to remote redirection attacks, where a malicious node redirects to itself packets that were originally destined to the mobile node. In general, authentication should be used with any message revealing information about the mobile node. The problem is even more complex with multicast, where any node may join the multicast address as per the IP-multicast host model. These security measures are complex and may incur a lot of overhead. If such measures are invoked with every handoff, however, it may overshadow the benefits of efficient handoff mechanisms .
To alleviate these problems, we propose an intra-domain multicast-based mobility solution.
III. Intra-domain Architectural Overview
In our intra-domain architecture, a mobile node is assigned a multicast address to which it joins while moving.The multicast address, however, is assigned only within a domain (e.g., autonomous system) and is used for intra-domain micro mobility. While moving between domains, an inter-domain mobility protocol is invoked (e.g., Mobile IP).We do not assume a specific protocol for inter-domain, only that such a protocol exists. For the sake of illustration, we take MIP as an example, when needed.
1) M o b i l e c o n t a c t s b a s t s t a t i o n (B S )2) B S s e n d s r e q u e s t t o m o b i l i t y p r o x y (M P )
3.a ) M P p e r f o r m s i n t e r -d o m a i n m o b i l i t y h a n d o f f
3.b ) M P s e n d s r e p l y t o B S w i t h t h e a s s i g n e d m u l t i c a s t a d d r e s s
When a mobile node moves into a new domain, it contacts the entry point base station (the first base station it encounters). This entry point base station (BS) performs the necessary per-domain authentication and security measures,then assigns a unicast care-of-address (CoA) for the mobile node to use in that subnet. As shown in Figure 3, the BS then sends a request message to the mobility proxy (MP) to obtain a multicast address for the visiting MN. The request message
includes the home address of the mobile node and its home agent’s address. Upon receiving the request the MP performs two tasks. The first is to execute the inter-domain handoff on behalf of the MN. In the case of Mobile IP, for example, this means that the MP registers its own address with the MN’s home agent. The second task is for the MP to assign a multicast address for the visiting MN, send a reply message to the BS and keep record of this mapping. The mapping is used for packet encapsulation later on.
Once this step is complete, the visiting MN joins the assigned multicast address (G). The joins are sent to (MP,G) and are processed as per the underlying multicast routing2. The MN continues to move within the same domain using the same multicast address. The assigned multicast address is locally scoped to the domain. Handoff is performed using standard join/prune mechanisms and only lightweight intra-domain security is required in this case.
When packets are sent to the MN, they are forwarded to the MP using inter-domain mobility. The packets are then encapsulated by the MP, based on the mapping, and multicast to the MN. For example, in Mobile IP the home agent encapsulates the packets and sends them to the MP. The MP looks into the inner header to know the home address of the destination, performs the mapping, strips off the outer header and encapsulates the inner packet with multicast header. The packets flow from the MP down the multicast tree to the MN. Architectural Discussion
We would like to point out how our scheme addresses design issues previously mentioned. In terms of scalability, our scheme attempts to address the limitations of the inter-domain multicast-based mobility. In terms of multicast state scalability we note that the multicast state growth is O(G) for the architecture presented in this study, as opposed to O(S x G) in [1][2]. However, there is still some concern for state concentration on certain paths (i.e., in certain routers) in the network. To further improve scalability of multicast state we investigate several aggregation techniques in the next section. We believe this is quite essential to achieve a scalable solution. Address allocation is performed by the mobility proxies on a per-domain basis, the multicast address assignment is now a local mechanism, and the multicast addresses are locally scoped within the domain. This facilitates address allocation and provides per-domain privacy as the multicast packets are not forwarded out of the domain. With regards to incremental multicast deployment, our architecture allows for incremental deployment of multicast, based on per-domain approach. This way, the best handoff performance can be attained using our architecture without requiring inter-domain multicast. Security overhead during handoff is reduced by using lightweight intra-domain security mechanisms while moving within a domain.
2 This is not a source-group state. Rather, it is for all sources sending to the MN (G). This is similar in concept to the (*,G) tree established towards the Rendezvous Point (RP) in PIM-SM [9], but can be achieved using any multicast routing protocol.
Robustness is crucial to ensure proper operation in the face of crashes and failures. To avoid single-point-of-failure scenarios (especially for the mobility proxy) we provide several mechanisms to enhance our protocol robustness. Instead of having only one mobility proxy (MP) per-domain, we propose to have multiple MPs (typically, five to ten per-domain). These MPs are typically placed/configured at the border of the domain or at the center of the network3. Each MP sends periodic liveness messages to a well-known domain-specific group called MP-announcement-group. All base station routers join this group and receive the liveness messages. Each such router maintains a live-MP list and maintains a timer for each MP that is reset by the liveness message from that MP. When a base station router is first contacted by a visiting MN, it performs a hash procedure to select one of the MPs from the MP-list. We use a hash procedure to avoid distributing explicit mapping (an approach that does not scale). The hash procedure assigns a weight to each MP i using hash(MNaddress, MP i), then selects the highest weight MP to which it sends the request message. This scheme has two advantages. First, it distributes the visiting MNs equally over the MP-list. Second, if a MP fails only those MNs that hashed to it are re-hashed, other MNs are not affected. See [21] for more detail. Moreover, if a new MP is added to the pool of MPs (i.e., the change in the list was not caused by failure) no re-hashing is done. Failure of a MP is detected by the base station routers when the MP timer expires. If the router uses the failed MP for some of its MNs, it does re-hashing for those MNs to select a live MP4.
IV . State Aggregation
The main problem with multicast-based mobility is scalability of multicast state with the increase in number of visiting mobile nodes. This is especially a problem where state concentration is expected to occur, as in the mobility proxies. Hence, it is quite crucial to use an effective multicast state aggregation technique to alleviate such a problem.
Most previous work on state aggregation uses prefix aggregation (PxA). That is, two states can be aggregated only if they have the same address prefix. For example, the two addresses 128.125.50.2 and 128.125.50.3 can be aggregated as one entry as 128.125.50.2/31, where 31 is the mask length. This has proven to be efficient for aggregating unicast routing tables in the Internet, since a domain/subnet has a specific unicast prefix. It is not clear, however, if this benefit applies for multicast addresses that are not geographically significant.
3 The center(s) of the network are the nodes with min(max) distance to reach any node in the network[16].
4 The MN keeps the multicast and MP addresses. In case of MP failure during handoff, the new BS gets the multicast and MP addresses from the MN, and checks if the MP is alive. If not, the BS performs the hashing and obtains a new live MP to which it sends a request. This mechanism obviates the need for mapping state replication among MPs. If the MN crashes during handoff (we assume it is configured with its home address), then the new BS performs the hashing, gets the MP address and sends a request to the MP.
We propose another kind of aggregation called the bit-wise aggregation (BA). As the name suggests BA works with bits instead of prefixes. For example, 128.125.0.2 and 128.125.1.2 may be aggregated as 128.12.0.2\9, where 9 is the position of the aggregated bit. Intuitively, BA provides more opportunity for aggregation, hence we expect it, on average, to provide better aggregation.
However, a deeper look at the two schemes shows us scenarios where PxA leads to more aggregation than BA. For example, a sequence of {0,4,1,2,3} leads to 3 states with BA, whereas with PxA it leads to 2 states. We perform further analysis to understand behavior of these schemes. We define aggregation ratio (AR) as the number of states before aggregation (x) to the number of states after aggregation (y);
i.e. AR=x/y. AR provides a good measure of the state reduction due to aggregation. In the above example, AR for BA is 5/3 whereas AR for PxA is 5/2. Figure 4 shows the AR for in-order
numbers, where both schemes have identical AR. Figure 4. Aggregation ratio for in-sequence numbers. Identical gain for bit-
wise and prefix aggregation.
Figure 5. Aggregation ratio for random numbers. Bit-wise aggregation outperforms prefix aggregation up to 80% of the number population.. Figure 5 shows the AR when the numbers are random. That is, out of 0 to 999, distinct numbers are chosen randomly until the whole number population is covered5. The random arrival of addresses is a more likely scenario, since MNs arrive at different entry points and experience various movement patterns. The following table presents the results: 5 We obtained similar results with several other number populations.
Av. prefix Av. bit-wise Av. bit-wise/prefix 80% population 1.40 1.84 1.32
100% population 2.48 1.98 1.19
Note the interesting cross-over-point at 80% population. The overall average AR for PxA is ‘2.48’ and for BA is ‘1.98’. Up to 80% of the population, however, BA outperforms PxA by a factor of 1.32. Hence, we choose bit-wise over prefix aggregation for our scheme.
We further classify multicast aggregation as perfect (PA) or lossy aggregation (LA). A multicast state consists of {Src, Grp, iif, oifList}, where iif is the incoming interface and oif is the outgoing interface. Src is the source of the multicast (the MP) and iif points towards the MP. In PA, groups can only be aggregated if the oifList if the same. For LA, however, states are aggregated even though the interfaces may be different. LA achieves better aggregation at the expense of extra network overhead, as the data packets may be sent down an extra link that does not reach a receiver. We study lossy bit-wise (LBA) and perfect bit-wise aggregation (PBA).
V. Simulation and Analysis
The first step to solve the scalability problem of multicast state is to understand the state distribution in the routers. We then apply aggregation and analyze the state reduction obtained under the different aggregation techniques. Aggregation gain, in general, depends on several factors, including topology, MP placement, number of MNs, among others. We study and evaluate this problem across different dimensions of various network sizes and number of mobile nodes and mobility proxies.
A. Simulation Setup
We use the network simulator (NS-2)[15] for simulation. Two sets of simulation scenarios were investigated. In the first set, called dynamic scenarios, 1000 MNs randomly enter the domain, and move to random nodes within the domain, each time joining through the new location and pruning through the old location, thus capturing the dynamics of the multicast tree. Up to 250k moves were simulated. In the second set of scenarios, called snapshot scenarios, MNs enter the domain at random entry nodes and at random times, but they do not move. Thus simulating a snapshot of the domain where nodes may exist at random locations. This approach allows us to scale our simulations to up to 250k MNs. In both simulation scenarios, we use up to 4 mobility proxies placed at well-connected backbone nodes. With every move or new entry, the MN randomly establishes new connections to the proxies, and maintains a number of already-existing connections. We have simulated several topologies likely to represent intra-domain networks (see Table 1).
name nodes links av deg name nodes links av deg ARPA4768 2.89TS-200200372 3.72
TS-100100185 3.7TS-250250463 3.72
TS-150150276 3.71TS-300300559 3.73 Table 1 Simulation Topologies. TS: transit stub, ARPA: arpanet based on real data.
B. Analysis and Results
We first discuss analysis of a topology with 100 nodes and 1 MP. This illustrates our analysis method to understand state distribution and aggregation gains. Then we present results for various topologies and multiple MPs.
i) 100 Nodes with 1 MP: The first topology used for the simulation is that given in Figure 6, with 100 nodes, transit-
stub structure, and one mobility proxy (MP) placed at node 0.
Figure 6. 100 node transit-stub topology (TS-100)
For dynamic scenarios, Figure 7 shows the multicast state distribution across the nodes for 40k moves 6. We notice that much of the multicast state in the network is concentrated at the backbone nodes 0,1,2 and 3. In general, we have noticed that only 17-20% of the nodes hold more than the average number of states. Also, 40-60% hold less than 1% of the total number of MNs and 66-71% hold less than 2%. That is, we observed a very high concentration of states in only a small fraction of the nodes .
Figure 7. State distribution without aggregation
6
We only show the first 50 nodes and start the graph at 250MNs for clarity.
Figure 8. State distribution with lossy aggregation.
We conducted a similar simulation experiment with lossy aggregation. The state distribution across the nodes is shown in Figure 8. It is clear from the two previous graphs that the nodes where aggregation is most effective are those nodes with maximum state; e.g., nodes 0,1 and 2. We take a closer look at those nodes in Figure 9. The number of states at node 0 dropped below 10 states. Notable reduction in state was also observed for nodes 1 and 2. The average AR for the 20%of nodes with maximum state was 10.07 (i.e, 90% reduction).
The overall number of states over the 100 nodes is given in Figure 10. As shown, lossy aggregation obtains good state reduction (factor of 2, or 50% reduction, for average number of states and around 1.5 for 90th percentile)7. Also, we noticed a significant decrease in variance
of states across the nodes.
Figure 9. Number of states (w/o agg: without aggregation, w/ agg: with aggregation)
Figure 10. Overall average and 90 percentile.
7
Without aggregation, in case of random movement, the average number of
states=MNs.PL/Nodes, where MNs is the number of mobile nodes (1000), PL is the average path length in the topology (4 in our case), and Nodes is the number of nodes in the topology (100). I.e., average number of states is 40.
For snapshot scenarios , with 250k MNs, the state distribution across time is given in Figure 11 (data is shown for 50 nodes and starts from 10k MNs, for clarity). Again, we see concentration of the state at nodes 0 through 3. We also observe surges in other nodes (the darker areas of the graph).
A closer look at the state distribution at the end of simulation (i.e., the last snapshot) is given in Figure 12. The average state per node is 10,830 states 8. However, only 20%of the nodes had 10k or more states, and around 60% of the nodes have around 2500 states (i.e., 1% of the total number of MNs). This is consistent with our earlier findings and is a strong indication that the state distribution is skewed, with potential for efficient aggregation in nodes with large number of states, where state reduction is mostly needed.
Figure 11.
Distribution of state across nodes and time, for 250k MNs.
Figure 12.
Number of states indexed by the node ID after 250k MNs.
To further understand the aggregation performance, we apply both lossy and perfect aggregation techniques to the snapshot scenarios (up to 40k MNs). For both techniques, we measure the average AR, 90th percentile and maximum state ratios 9. As shown, these ratios increase with the increase of number of MNs. Also, it is clear that the lossy aggregation achieves better ratios than perfect aggregation. For lossy aggregation the average AR approaches 2 for large number of MNs, whereas for perfect aggregation AR approaches 1.4.
8 Theoretically the average is 250k x 4 hops/100nodes = 10k states.
9
Max state ratio=Max State Before Aggregation/Max State After Aggregation , and
similarly for the 90th percentile ratio.
ii) Various Topologies with Multiple MPs: We now
investigate lossy and perfect aggregation techniques over several topologies. We also analyze aggregation trends with multiple mobility proxies. We simulated snapshot scenarios with 10k MNs. AR results for lossy aggregation are shown in Figure 14, and are summarized in the following table:
MPs/Nodes 501001502002503001 1.99 1.84 1.71 1.71 1.64 1.632 1.48 1.40 1.36 1.36 1.36 1.323 1.38 1.33 1.31 1.31 1.29 1.284
1.33 1.29 1.27 1.27 1.26 1.25
(for 300 nodes 4 MPs) to 1.99 (for 50 nodes with 1 MP). We note several important trends; for the same number of MNs,as the number of nodes in the topology increases, the state concentration in the nodes decreases and the AR decreases.Also, as the number of MPs increases, the concentration of states in the nodes decreases and the AR decreases.
Figure 14. Aggregation ratio for lossy aggregation with various topologies
and multiple MPs
Simulation results for the perfect aggregation are given in Figure 15, and are summarized in the following table:
MPs/Nodes
501001502002503001 1.43 1.32 1.25 1.27 1.23 1.232 1.27 1.18 1.16 1.17 1.15 1.163 1.21 1.17 1.15 1.16 1.15 1.154
1.19
1.15
1.14
1.14
1.14
1.14
The average aggregation ratio ranges from 1.14 (for 300nodes with 4 MPs) to 1.43 (for 50 nodes with 1 MP).
Evidently, lossy aggregation achieves better AR. The trends for both aggregation techniques are quite similar.
Figure 15. Aggregation ratio for perfect aggregation with various topologies
and multiple MPs.
VI. RELATED WORK
Several architectures have been proposed to provide IP mobility support. In Mobile IP (MIP) [4], every mobile node (MN) is assigned a home address and home agent (HA) in its home subnet. When the MN moves to another foreign subnet, it acquires a care-of-address (COA) through a foreign agent (FA). The MN informs the HA of its COA via registration. Packets destined to the MN are sent to the HA, then are tunneled to the MN. This is known as triangle routing. Route optimization [6] attempts to avoid triangle routing by sending binding updates, containing the current COA of the MN to the sender. Overhead during handoff, however, renders this scheme unsuitable for micro mobility. In[8] a scheme based on dynamic DNS updates is proposed. When MN moves, it obtains a new IP-address and updates the DNS mapping for its host name. This incurs handoff latency due to DNS update delays and is not suitable for delay bounded applications. Also, this scheme is not transparent to the transport protocol that is aware of the mobility. In[3] the HA tunnels packets using a pre-arranged multicast group address. The access router, to which the MN is currently connected, joins the group to get data packets over the multicast tree. This approach suffers from the triangle routing problem; packets are sent to HA first and then to MN. Multicast-based mobility is proposed in [1] and [2]. Each MN is assigned a unique multicast address. Packets sent to the MN are destined to that multicast address and flow down the multicast distribution tree to the MN. The sender tunnels the packets using the multicast address. This approach avoids triangle routing, in addition to reducing handoff latency and packet loss. The study in [1] quantifies the superiority of handoff performance for multicast-based mobility over Mobile IP protocols. These schemes, however, suffer from several serious practical issues, including scalability of multicast state, address allocation and dependency on inter-domain multicast. We address these issues in our work.
Several approaches have been proposed for micro mobility[23]. The general approaches include mobile-specific routing, hierarchical approaches and seamless handoff. Mobile-specific route approaches include cellular IP[17] and Hawaii[18]. A domain-gateway registers its address with the HA and forwards the packets to the MN. The MN’s home address is used within the domain. These approaches need special signaling to update mobile-specific routes and require changes in packet forwarding and unicast routing in all the routers. In cellular IP[17], signaling is data-triggered to create paths by having routers snoop on the data packets. Hawaii[18] proposes a separate routing protocol and requires explicit signaling from the mobiles. In a way, these approaches attempt to create a distribution tree using extra routing entries for the mobile, similar to what multicast does. Our approach builds upon existing multicast mechanisms as opposed to re-creating them. Approaches based on seamless handoff between old and new access routers, involve fairly complex signaling, buffering and synchronization procedures. Router-assisted smooth handoff in MIP[5], edge mobility[24] and fast handoff[25] belong to this category. Approaches using a hierarchy employ a gateway per-domain and need to keep a location database to map identifiers into locations. This mapping suffers from scalability and robustness problems as was noted earlier in this paper. In[7] a hierarchy of foreign agents is created at the local, administrative domain and global levels. In[26] a multi-level hierarchy is used in which packets from the HA arrive at a root FA where they are tunneled to a lower level FA and then to the MN. Hierarchical MIP[27] builds a network of tunnels (overlay network) between FAs. [29][30] also use a notion of mobility agent for localized handoff within a domain. During handoff, MN contacts the domain FA. Our approach clearly outperforms hierarchical approaches in handoff delay, and is simpler as it re-uses existing standard multicast mechanisms.
Very little work has been done in the area of multicast state aggregation. Work in[19] proposes an interface-centric model for aggregation. This approach, however, benefits from having a large number of group members, which does not apply in our case. [29] studies strict, pseudo-strict and lossy prefix aggregations for wide-area multicast routing. Unlike most previous studies, however, we show that the bit-wise usually achieves better gains than prefix aggregation.
VII. CONCLUSIONS
In this paper, we presented a new intra-domain multicast-based protocol for supporting micro mobility. Our scheme uses mobility proxies to assign domain-scoped multicast addresses to visiting mobiles. A mobile uses its assigned address during its movement throughout the domain. Our study shows that such scheme clearly outperforms other IP mobility approaches in handoff delays. In our architecture we address serious drawbacks of inter-domain multicast-based mobility approaches. Particularly, we addresses issues of multicast state scalability, multicast address allocation,
incremental multicast deployment and overhead of security during handoff.
We feel, however, that the main contribution of our paper is the work on multicast state aggregation. Unlike previous work, our extensive simulations and thorough analysis shows that, for multicast aggregation, bit-wise aggregation is a better choice than prefix aggregation. Furthermore, we observe that multicast state tends to be distributed unevenly across the nodes in the topology. For one mobility proxy, for example, 20% or less of the nodes had more than the average state per node, and up to 60% of the nodes had states/entries less than 1% of the number of MNs. Such state concentration facilitates efficient aggregation.
We have shown through extensive simulation over various topologies and multiple mobility proxies that bit-wise lossy aggregation obtains the best aggregation gains. Average aggregation ratios between 1.25 and 2 were obtained in our simulations. This translates into 20% to 50% reduction in multicast state. The average ratio goes up to 10 (i.e., 90% reduction) for the top 20% nodes in state concentration.
Our findings indicate that the aggregation ratio increases with the increase in number of visiting mobile nodes, the decrease in number of mobility proxies, and the decrease in number of nodes in the topology.
Our work is the first to address state aggregation in IP mobility, and one of the very few to address multicast state aggregation. We hope that the understanding developed in this paper will help design more scalable efficient solutions for IP mobility.
REFERENCES
[1] A. Helmy, "A Multicast-based Protocol for IP Mobility Support", ACM
Second International Workshop on Networked Group Communication (NGC), Palo Alto, November 2000.
[2]J. Mysore, V. Bharghavan, “A New Multicasting-based Architecture
for Internet Host Mobility”, Proceedings of ACM MobiCom, 1997. [3]S. Seshan, H. Balakrishnan, R. Katz, “Handoffs in Cellular Wireless
Networks: The Daedalus Implementation and Experience”, Kluwer Journal on Wireless Networks, 1995.
[4] C. Perkins, “IP Mobility Support”, IETF RFC 2002, Oct 96.
[5] C. Perkins and D. Johnson, “Mobility Support in IPv6”, Proceedings of
MobiCom’96, November 1996.
[6] C. Perkins, D. Johnson, “Route Optimization in Mobile IP”, Internet
Draft, IETF, February 2000.
[7]R. Caceres, V. Padmanabhan, “Fast and Scalable Handoffs for Wireless
Internetworks” MobiCom ’96.
[8] A. Snoeren, H. Balakrishnan, “An End-to-End Approach to Host
Mobility”, ACM MobiCom, Aug 00.[9] D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, V. Jacobson,
M. Handley, C. Liu, P. Sharma, “Protocol Independent Multicast –Sparse Mode: Protocol Specification”, IETF RFC 2362, March '98. [10]S. Kumar, P. Radoslavov, D. Thaler, C. Alaettinoglu, D. Estrin, M.
Handley, “The MASC/BGMP Architecture for Inter-domain Multicast Routing”, Proceedings of ACM SIGCOMM, August 1998.
[11] B. Cain, S. Deering, I. Kouvelas, A. Thyagarajan, “Internet Group
Management Protocol, version3”, Internet draft of the IETF, March 2000.
[12]K. Calvert, M. Doar, E. Zegura, “Modeling Internet Topology”, IEEE
Comm, p. 160-163, June 1997.
[13]G. Phillips, S. Shenker, H. Tangmunarunkit, “Scaling of Multicast
Trees: Comments on the Chuang-Sirbu scaling law”, SIGCOMM’99.
[14]P. Radoslavov, H. Tangmunarunkit, H. Yu, R. Govindan, S. Shenker,
D. Estrin, "On characterizing network topologies and analyzing their
impact on protocol design", USC-CS-TR-00-731, March 2000.
[15]L. Breslau, D. Estrin, K. Fall, S. Floyd, J. Heidemann, A. Helmy, P.
Huang, S. McCanne, K. Varadhan, Y. Xu, H. Yu, “Advances in Network Simulation”, IEEE Computer, vol. 33(5), p. 59-67, May 2000.
[16] E. Fleury, Yih Huang, P.K. McKinley. “On the performance and
feasibility of multicast core selection heuristics”, Int’l Conference on Computer Communications and Networks, Page(s): 296 –303, 1998. [17] A. Campbell, J. Gomez, S. Kim, A. Valko, C. Wan, Z. Turanyi,
“Design, implementation, and evaluation of cellular IP” IEEE Personal Communications , Volume: 7 Issue: 4 , Page(s): 42 –49, Aug. 2000. [18]R. Ramjee, T. La Porta, L. Salgarelli, S. Thuel, K. Varadhan, L. Li,
“IP-based access network infrastructure for next-generation wireless data networks”, IEEE Personal Communications , Volume: 7 Issue: 4 , Page(s): 34 –41, Aug. 2000.
[19] D. Thaler, M. Handley, “On the aggregatability of multicast forwarding
state”, IEEE INFOCOM 2000, Page(s): 1654 -1663 vol.3, 2000. [20]P. Radoslavov, D. Estrin, R. Govindan, “Exploiting the Bandwidth-
Memory Tradeoff in Multicast State Aggregation", USC-CS-TR99-697, Computer Science Department, USC, July 1999.
[21] D. Estrin, M. Handley, A. Helmy, P. Huang, D. Thaler, "A Dynamic
Bootstrap Mechanism for Rendezvous-based Multicast Routing", Proceedings of IEEE INFOCOM '99, New York, March 1999.
[22]D. Zappala, “Alternate path routing for multicast”, INFOCOM 2000
[23] A. T. Campbell and J. Gomez IP Micro-Mobility Protocols, ACM
SIGMOBILE Mobile Computer and Communication Review, 2001 [24] A. O’Neill, G. Tsirtsis, S. Corson, Edge Mobility Architecture,
Internet-draft, draft-oneill-ema-02.txt, July 2000.
[25]G. Dommety, et al, “Fast Handovers for Mobile IPv6”, Internet Draft,
draft-ietf-mobileip-fast-mipv6-02.txt, July 2001.
[26] E. Gustafsson, A. Jonsson, C. Perkins, Mobile IP Regional
Registration, draft-ietf-mobileip-reg-tunnel-02, March 2000.
[27]H. Soliman, C. Castelluccia, K. Elmalki, L. Bellier, “Hierarchical
Mobile IPv6”, draft-ietf-mobileip-hmipv6-04.txt, July 2001.
[28]P. Radoslavov, D. Estrin, R. Govindan, “Exploiting the Bandwidth-
Memory Tradeoff in Multicast State Aggregation",USC-CSTR, July99.
[29]J. Kempf, P. Calhoun, C. Pairla, Foreign Agent Assisted Handover,
draft-calhoun-mobileip-proactive-fa-01.txt, June 00.
[30]G. Dommety, “Local and Indirect Registration for Anchoring
Handoffs”,draft-dommety-mobileip-anchor-handoff-01, Dec 00