J. Cent. South Univ. Technol. (2007)03-0386-07

DOI: 10.1007/s11771-007-0076-2               

New multicast scheme based on

D­­­ynamic mobility prediction in mobile IPv6 environment

HUANG Guo-sheng(黄国盛)^1,2, CHEN Zhi-gang(陈志刚)², ZHAO Ming(赵 明)²,

WANG Lu-lu(王路露)², HUO Ying(霍 英)², LIU An-feng(刘安丰)²

( 1. College of Physics Science and Information Engineering, Jishou University, Jishou 416000, China;

2. School of Information Science and Engineering, Central South University, Changsha 410083, China)

Abstract: A new mobile multicast scheme called mobility prediction based mobile multicast(MPBMM) was proposed. In MPBMM, when a mobile node (MN) roams among subnets during a multicast session, MN predicts the next subnet, to which MN will attach, by the information of its position and mobility speed, consequently speeds up the handoff procedure. Simulation results show that the proposed scheme can minimize the loss of multicast packets, reduce the delay of subnet handoff, decrease the frequency of multicast tree reconfiguration, and optimize the delivery path of multicast packets. When MN moves among subnets at different speeds (from 5 to 25 m/s), the maximum loss ratio of multicast packets is less than0.2%, the maximum inter-arrival time of multicast packets is 117 ms, so the proposed scheme can meet the QoS requirements of real-time services. In addition, MPBMM can support the mobility of multicast source.

Key words: mobile multicast; mobile IPv6; hierarchical structure; dynamic mobility prediction

1 Introduction

Mobile IP is a solution for mobility on the global Internet, which allows nodes to maintain all ongoing communications while changing links. Recently, con- siderable research efforts have been drawn to provide multicast service for mobile nodes (MNs) in mobile IP environment. Because multicast is efficient for one-to-many communication over the Internet, which effectively conserves the network bandwidth and processing capability of source host, it is significant to provide multicast mechanism in wireless mobile IP environment^[1-2].

The mobile multicast protocol must deal not only with dynamic group membership but also with dynamic member location. Obviously, mobile multicast protocol is more complicated than the multicast protocol in wired network^[2].

Mobile IP offers two methods of multicast service for mobile hosts, namely MIP-RS and MIP-BT^[3].

In MIP-RS, the MNs that are members of a group always re-subscribe to the current multicast group and reconstruct the multicast tree when MNs change foreign link^[1-2]. The advantages of this protocol are that it can use the existing multicast protocols directly, and avoid the problem of triangle routing^[1-2]. However, if the MN is highly mobile, the performance of MIP-RS will drop seriously, and MNs re-subscribing to multicast group frequently will suffer from a large join and graft latencies, which may cause the interruption of multicast service and the loss of multicast packets and influence the stability of multicast session.

In MIP-BT, Home Agents(HAs) join the multicast group on behalf of its MNs attached to a foreign link, consequently, MNs hide the mobility from all other members of the multicast group. There is no need to reconstruct the multicast tree when MN attaches to another subnet^[1-4]. However, in MIP-BT, there exist problems of triangle routing and tunnel convergence^[3-5]. Furthermore, while multicast packets are transmitted via bi-directional tunnel, the HA must use IP-in-IP encapsulation and delivery the packets by a long distance form HA to MN, so MIP-BT produces considerable overhead and high delivery delay.

HARRISON et al^[5] proposed the mobile multicast (MoM) protocol. MoM protocol chooses one of the HAs as the designated multicast service provider (DMSP) for each multicast group in each foreign network. Only the DMSP of a multicast group in a foreign network is allowed to tunnel a copy of multicast packets for the group to the corresponding foreign agent^[4]. So MoM can solve the tunnel convergence problem in MIP-BT^{[2-3, 5]}. But MoM protocol has the same problem of triangle routing as MIP-BT. Furthermore, when MN moves among subnets, MoM introduces the need for DMSP handoff, which increases the handoff delay and causes the loss of multicast packets^[2].

LIN et al^[6] proposed the range-based mobile multicast protocol (RBMoM), and introduced the concepts of multicast home agent (MHA) and service range. As shown in Fig.1, the MHA joins the multicast group on behalf of MNs, and tunnels multicast Datagrams to the foreign link to which the MH is currently attached. When the MN is out of the service range of MHA, the MHA handoff will occur^[6]. When the service range of MHA changes, RBMoM trades off between the shortest delivery path and the frequency of the multicast tree reconfiguration^[6]. But RBMoM has the same problems of MHA handoff and loss of packets caused by handoff，and has the problem of choosing a dynamic service range according to the actual network environment^{[2-3, 6]}.

Fig.1 Service range of MHA and handoff of MHA in RBMoM

In this study, a new mobility prediction based mobile multicast scheme (MPBMM) was proposed. MPBMM combines the ideas of mobility prediction and hierar- chical mobility management in mobile multicast, it intends to minimize the loss of multicast packets and reduce the delay of subnet handoff by dynamic mobility prediction. Furthermore, MPBMM manages to decrease the frequency of multicast tree reconfiguration and optimize the delivery path of multicast packets by hierarchical mobility management. Consequently the quality of service and the performance of mobile multicast can be improved.

2 New multicast scheme based on dynamic mobility prediction

2.1 Network model

MPBMM used a hierarchical network model, which is similar to that of HMIPv6^[7-9]. As shown in Fig.2, the network is divided into different domains according to geographic position. Each of the domains has a domain mobile multicast agent(DMMA), which can join the multicast group on behalf of MNs within the domain. At the same time，DMMA can also be regarded as a mobility anchor point(MAP) of MNs^[7]. Each domain is divided into several subnets, and every subnet has a wireless multicast access router(WMAR), which can provide wireless access service for MN visiting the subnet. In Fig.2, each circle represents the wireless transmission range of a subnet, and CN is a corresponding node of MN.

Fig.2 Network model of MPBMM

Upon arriving in a foreign domain, MN will discover the addresses of the WMARs and DMMA in the visited network by listening router advertise- element(RAs). All position coordinates of WMARs in the wireless domain are stored in DMMA. After entering a subnet, MN can obtain the WMARs coordinates of its visited subnet and neighbour subnet from DMMA.

2.2 Joining/leaving of multicast group

Both WMAR and DMMA keep a list of multicast groups that have group members. The record format in the list is as follows:

 (G, T_G, Group members list)

where  G is a multicast group address, T_G is a timer associated with address G. The WMAR and DMMA will send a MLD query message after the expiration of the timer.

When a MN roams in a foreign subnet (for example, subnet S₁), after registration, the MN will sent a MLD report message to the WMAR of subnet S₁ for joining multicast group G.

After receiving a MLD report message, the actions of the WMAR can be described as follows:

// Pseudo code of MLD report processing of WMAR

// Note:  B is a set of group address in the multicast group list of WMAR, C is a set of MN’s LCoA(On-link care of address) in the group member list of group G , and M is the IP address of MN.

If  (GB) {

B=B∪{G}；

C=C∪{M}

Initialize timer T_G ；

Forward the MLD report to DMMA;}

Else {

If (MC) {

C=C∪{M}；

Initialize timer T_G;}

}

If (MN is a sender of multicast)

//MN is multicast source

{WMAR encapsulates the succeeding multicast packets received from MN and tunnels them to DMMA;}

Else

   //MN is a receiver of multicast

{WMAR delivers the succeeding multicast packets tunneled from DMMA to MNs within the subnet by subnet-level multicast;}

//End.

   Upon receiving the MLD report message forwarded from WMAR, the operations of DMMA can be described as follows:

// Pseudo code of MLD report processing of DMMA

// Note:  D is a set of group addresses in the multicast group list of DMMA, E is a set of WMARs’ addresses in the group member list of group G, and W is the IP address of WMAR.

If  (GD) {

   DMMA joins group G on behalf of MN according to multicast protocols of fixed nodes, and establishes multi- cast tree;

D=D∪{G};

E=E∪{W}; Initialize timer T_G;

}

Else {

If  (WE) {

E=E∪{W}; Initialize timer T_G;}

}

If (MN is a sender of multicast)

//MN is multicast source

{DMMA decapsulates succeeding multicast packets tunneled from MN’s current WMAR and forwards them to the multicast tree;}

Else

//MN is a receiver of multicast

{DMMA tunnels the succeeding multicast packets received from multicast group G  to the WMAR in its group member list of group G;}

//End.

   When MN leaves a multicast group G, it sends a MLD Done message to the WMAR in MN’s current subnet. Subsequently, WMAR will delete the MN’s address from the member list of group G.

Upon finding that there is no member in the member list of group G, WMAR will delete group G from its multicast group list, and send a MLD Done message to its DMMA. Then, DMMA will delete the WMAR’s address from the member list of group G.

If DMMA finds that there is no member in the member list of group G, DMMA will delete group G from its multicast group list, stop forwarding multicast packets of group G, and leave group G.

   After performing the procedures mentioned above, DMMA can join/leave a multicast group on behalf of MNs within the domain, the MN’s mobility in the domain is transparent to the multicast delivery tree. So there is no need to reconstruct multicast tree when MNs move among subnets within a domain.

2.3 Mobility prediction algorithm of MPBMM

In order to improve the mobile multicast perfor- mance when MN switches between subnets rapidly, in this paper, a dynamic mobility prediction algorithm was proposed.

When a MN roams from a subnet to another, the mobility pattern is not completely random (for example, a MN moves along a highway)^[10-12]. We can predict the next subnet, to which the MN will attach, by the information of position and mobility speed obtained from global positioning system(GPS), and inform the MNs’ current DMMA and the WMAR in the next subnet to get ready for subnet handoff, consequently, speed up the subnet handoff procedure, reduce/avoid the loss of multicast packets caused by handoff.

As shown in Fig.3, MN currently locates in subnet₀, and it is moving away from subnet₀. Subnet₁ and subnet₂ are the neighborhoods of subnet₀, WMAR₀-WMAR₂ are wireless multicast access routers in the three subnets respectively. The dotted circle indicates the wireless transmission range of each subnet. Assuming the wireless transmission radius of each subnet is R. r₀，r₁ and r₂ are distance vectors from MN to WMAR₀, WMAR₁ and WMAR₂, respectively.

Fig.3 Model of dynamic mobility prediction

   Let (x₀, y₀) be the coordinate of WMAR₀, and (x_t, y_t) be that of MN at time t. Let v(t) be the mobility speed of MN, and θ be the included angle between speed v(t) of MN and X-axis. After a time Δt, the distance between MN and WMAR₀ can be written as

(1)

It is assumed that MN moves from its current coordinate (x_t, y_t), the remainder resident time in subnet₀ is T_left, i.e., the MN will cost time T_left to arrive at the Border of subnet_0, it can be obtainted

=R                  (2)

Let a=x_t-x₀，b=y_t-y₀，and substitute Eqn.(2) into Eqn.(1), then

                                        (3)

Similarly, it is assumed that there are N neighbor subnets around subnet₀, the current coordinate of MN is (x_t, y_t). Then, after a time Δt, the distance between MN and WMAR_i of subnet i (i∈[1, N]) can be presented as

 (4)

where  (x_i, y_i) is the coordinate of WMAR_i(i∈[1,N]).

Assuming it will cost T_i for MN to move from its current position (x_t, y_t) to the border of subnet i, we can have

=R                  (5)

   Let a_i=x_t-x_i，b_i=y_t-y_i，substituting Eqn.(5) into Eqn.(4), we can obtain

    (6)

If T_i >0, T_i can be regarded as the predicted time for MN to arrive at its neighbor subnet_i. If T_i<0, or Eqn.(4) has no solution, it is impossible for MN to enter subnet_i according to the MN’s current mobility pattern.

In order to realize fast handoff, the MN must send a Handoff_Notification message to its DMMA in current domain and the WMAR in the next subnet and inform them to get ready for subnet handoff before MN arrives at the boundary of the current subnet. Let T_h be the time that the MN should inform DMMA and WMAR in advance. Since the Handoff_Notification message has to pass along the path , the value of T_h couldn’t be less than the round trip time(RTT) from MN to DMMA. Considering the processing delay of Handoff_Notification message in WMAR and DMMA, the value of T_h can be set as

T_h = 2RTT_MN-DMMA            (7)

The Handoff_Notification message format is defined as

Handoff_Notification(G，M-ID，W-ID ，S-ID)

where  G is group address, M-ID is the regional care-of address(RCoA) of MN, W-ID is the address of WMAR_k  in subnet_k that MN will visit, S-ID is a flag:

S-ID=1:  Indicating MN is a multicast receiver;

S-ID=0:  Indicating MN is a multicast source.

In MPBMM，the mobility prediction algorithm of MN can be described as

// Pseudo code of the mobility prediction algorithm

// Input:

//  v: The size of MN’s mobility speed;

// θ: The mobility direction of MN;

//  (x_t, y_t):  The coordinate of MN at time t;

//  (x_i , y_i): The coordinate of WMAR_i.

// Output:

//  k: The next subnet that MN will visit;

while   ≤0     do

{Compute  according to Eqn.(1);

Delay (Interval1);}

while T_left >T_h  do

{Compute T_left  according to Eqn.(3);

Delay (Interval2);}

for (i= 1; i≤N; i++)

{Compute T_i according to Eqn.(6); }

Let T = {T_i│i∈[1,N]};

T_k=min{h_i| h_i∈T, h_i>0}                   

;

MN sends a Handoff_Notification to WMAR_k via DMMA;

//End

After receiving a Handoff_Notification message, the operations of the DMMA can be described as follows:

// Pseudo code of Handoff_Notification processing of DMMA

// F is a set of WMARs’ addresses in group member list of group G, and W_k is the IP address of WMAR_k

If  (W_k  F) {

F=F∪{W_k}；

Initialize timer T_G;

Forwards the Handoff_Notification message to WMAR_k, inform WMAR_k to add group address G to its multicast group list;}

If (S-ID = 1)

// MN is a receiver of multicast

{DMMA forward a copy of the succeeding multicast packets to WMAR_k;}

Else

   // MN is multicast source

   {DMMA sets down the sequence number of the last received packet. }

//End.

2.4 Delivery of multicast packets

2.4.1 MN as multicast receiver

Because DMMA joined group G on behalf of MNs, the multicast packets sent to MNs will firstly be forwarded to the DMMA in the visited domain of MNs. After consulting the member list of group G, DMMA tunnels the multicast packets to the WMAR in the current subnet of MN, then WMAR caches the packets tunneled from DMMA, and uses subnet-level multicast to send the multicast packets to MNs attached to the subnet.

When MN switches between subnets, MN predicts the next subnet (subnet_k) to which it will attach by mobility prediction, and requires DMMA to forward a copy of multicast packets of group G to WMAR_k in advance before the occurrence of handoff by Handoff_Notification message. Consequently, after reaching the new subnet, MN can obtain these multicast packets cached in WMAR_k rapidly. In MPBMM, we use a method of dynamic prediction, so the predicted result has a high accuracy. As a reserved scheme, if MN find the predicted result is incorrect after handoff, MN will establish a tunnel from WMAR_k to WMAR_new, and tunnel the lost packets during handoff to the new foreign link to which MN attaches, so MPBMM can minimize the loss of multicast packets caused by handoff.

2.4.2 MN as multicast source

The multicast packets sent by MN will be delivered to WMAR of MN’s current subnet firstly, WMAR encapsulates them, and tunnels them to DMMA. Then, DMMA will decapsulate packets tunneled from WMAR and deliver them to the multicast tree.

  Similarly，When MN switches between subnets, MN predicts the next subnet(subnet k) to which it will attach, by mobility prediction algorithm, and informs  DMMA about the predicted result in advance, by Handoff_Notification message. Then, DMMA sets down the sequence number (SEQ_last-DMMA) of the last received packet. DMMA informs MN about SEQ_last-DMMA immediately after a handoff. MN checks the sequence number (SEQ_last-MN) of the last sent packet, and tunnels the packets between SEQ_last-DMMA and SEQ_last-MN to DMMA, hence the loss of multicast packets caused by handoff can also be reduced when MN is a multicast source.

3 Simulation and performance analysis

MPBMM was simulated shown by VC++, and the network model is shown in Fig.2. The simulation topology is a 8×8 mesh in which each vertex is a wireless subnet. There are 16 MNs joining the same multicast group. Initially, these MNs are distributed randomly in the 8×8 mesh network. The wireless transmission radius of each wireless subnet is 500 m, and the distance between two neighbor WMARs is 900 m.

   Assuming CN is a multicast source, it sends a constant bit rate(CBR) multicast flow at a speed of 80 Kbps to MNs. The interval of adjacent two packets is 20 ms, the size of each multicast packet is 200 byte.

The wired link from DMMA to WMAR has a bandwidth of 10 Mbps with a link delay of 5 ms. The wireless link from WMAR to MN has a bandwidth of     5 Mbps, and the link delay is 5 ms. Assuming the delay of Internet connection from DMMA to CN and HA is T_D with a default value of 15 ms. The mobility speed of MN is 5-25 m/s.

In the simulation, the frequency of multicast tree reconstruction, average loss ratio of multicast packets when MN moving among subnets at different speeds were measured, and the inter-arrival time of multicast packets was computed. The simulation results are shown in Figs.4-7.

Fig.4 shows the relationship between the mobility speed of MN and the frequency of multicast delivery tree reconfiguration. Among the three protocols of MIP-RS, RBMoM and MPBMM, it is found that MIP-RS has the maximum frequency of multicast tree reconfiguration, while MPBMM has the minimal frequency of that. This enhancement is expected since in MIP-RS, MN must rejoin the multicast group every time MN switches between subnets, in RBMoM, MN must rejoin the multicast group when MHA handoff occurs. In MPBMM, by using hierarchical mobility management, DMMA joins multicast group on behalf of MNs. When MN moves among subnets within the same domain, there is no need to reconfigure the multicast tree. So, MPBMM can reduce the protocol overheads, conserve the network resources, and improve the performance of multicast service.

Fig.4 Average frequency of multicast tree reconfiguration

Fig.5 Average multicast packet loss ratio

(Multicast buffer size for each MN is 3)

Fig.6 Multicast buffer size for each MN offered by WMAR vs average multicast packet loss ratio

Compared with MIP-BT, in MPBMM, the multi- cast packets delivered to MN have no need to be forwarded via a long tunnel from HA to the MN’s visited subnet，the delivery path of multicast packets is optimal. So MPBMM can avoid the problems of triangle routing and tunnel convergence existing in MIP-BT, decrease the transmission delay of packets, and reduce the protocol overhead. Although from DMMA to WMAR, the packets are delivered by a tunnel, the distance from DMMA to WMAR is so near that the overhead is very small, so MPBMM has a better performance than that of MIP-BT.

Fig.7 Inter-arrival time of multicast packet

(Multicast buffer size for each MN is 6)

Fig.5 shows the average loss ratio of multicast packets when MN moves among subnets at different speeds. It is found that MPBMM has a lower multicast packet loss ratio than that of RBMoM, MIP-BT and MIP-RS. This is because the loss of multicast packets mainly occurs in the procedure of handoff, and MPBMM can reduce the packets loss by using mobility prediction algorithm. When MN is a multicast receiver, MN can require DMMA to forward a copy of multicast packets to the new WMAR in advance before the occurrence of handoff. After handoff, MN can obtain these packets immediately from the new WMAR^[3]. Hence, MPBMM can realize smooth handoff and reduce the loss of multicast packets caused by handoff.

Fig.6 shows the relationship between multicast buffer size and the loss ratio of multicast packets. It is found that the larger the multicast buffer size of WMAR, the lower the loss ratio of multicast packets. In the simulation, when WMAR offers a buffer size of 6 packets to each MN, the loss of multicast packets caused by handoff can be minimized, and a good handoff performance can be obtained.

The influences of MN’s handoff on real-time services were also measured. As shown in Fig.7, in the simulation, the maximum inter-arrival time of multicast packets is 117 ms. Obviously, the maximum inter-arrival time of multicast packets is caused by subnet handoff. Related studies show that the maximum tolerable delay for real-time services is approximately 200 ms^[9]. So this scheme can meet the QoS requirements of real-time communications. In Fig.7, it is also found that the inter-arrival time of multicast packets from sequence number 2 502-2 505 is very small. This is because MN can obtain the multicast packets cached in the multicast buffer of WMAR rapidly after a handoff completed.

4 Conclusions

Mobile IP is an important research field in IPnG, and multicast technology will be applied widely in IP network since it can efficiently conserve network resources^[1-3,12-15]. However, it is a challenging problem to provide multicast support for mobile nodes in mobile IP environment^[1-3,7]. In this paper, a new multicast scheme based on dynamic mobility prediction called MPBMM in mobile IPv6 environment was proposed. In MPBMM, wireless network is divided into different domains, each domain has a DMMA that joins multicast group on behalf of MNs within the domain. MPBMM shields the mobility of MNs from multicast tree by hierarchical mobility management, MN can move freely among subnets within a domain without reconstructing of multicast tree. MPBMM can reduce the handoff delay, optimize the delivery path of multicast packets, and avoid the problems of triangle routing and tunnel convergence. Furthermore, by using mobility prediction algorithm, MPBMM can minimize the loss of multicast packets during a handoff, speed up the handoff procedure, and improve the performance of mobile multicast.

References

[1] BEGAIN K A, CAO Y W, ALAMEH K. A DBT-based mobile multi- cast protocol[C]// Proceedings of the 2005 Systems Commu- nications (ICW’05). Montreal: IEEE, 2005: 255-260.

[2] WU Qian, WU Jian-ping, XU Ke, et al. A survey of the research on IP multicast in mobile internet[J]. Journal of Software, 2003, 14(7): 1324-1335. (in Chinese)

[3] HUANG Guo-sheng, CHEN Zhi-gang, ZHAO Ming, et al. A mobility prediction based hierarchical mobile multicast protocol[J]. Computer Engineering and Applications, 2006, 15: 26-29. (in Chinese)

[4] JOHNSON D B, PERKINS C, ARKKO J. Mobility Support in IPv6[R]. IETF, RFC3775. 2004: 114-115.

[5] HARRISON T G, WILLIAMSON C L, MACKRELL W L, et al. Mobile multicast (MoM) protocol: Multicast support for mobile hosts[C]// ACM International Conference on Mobile Computing and Networking (MOBICOM). Budapest: ACM, 1997: 151-160.

[6] LIN C H R, WANG K M. Scalable multicast protocol in IP-based mobile networks [J]. Wireless Networks, 2002, 8: 27-36.

[7] SOLIMAN H, CASTELLUCCIA C, MALKI K E, et al. Hierarchical Mobile IPv6 Mobility Management[R]. IETF, RFC4140. 2005: 1-30.

[8] SUN Li-min, LIAO Yong, ZHENG Jian-ping et al. A mobile multicast algorithm based on hierarchical architecture[J]. Journal of Software, 2003, 14 (9): 1608-1610. (in Chinese)

[9] TAN C L, PINK S. MobiCast: A multicast scheme for wireless networks[J]. ACM/Baltzer Mobile Networks and Applications, 2000, 5(4): 259-271.

[10] SU W, LEE S J, GERLA M. Mobility prediction and routing in Ad Hoc wireless networks[J]. International Journal of Network Management, 2001, 11(1): 3-30.

[11] WANG Jian-xin, DENG Shu-guang, CHEN Song-qiao, et al. A new routing protocol based on mobility prediction in mobile Ad Hoc wireless networks[J]. High Technology Letters, 2002, 3(4): 263-267. (in Chinese)

[12] ZHUANG Hong-cheng, ZHANG Guang-zhao. Mobile IP predic- tive mobility management[J]. Journal of Circuits and Systems, 2002, 7(2): 77-82. (in Chinese)

[13] WANG Guo-jun, LIAO lin, CAO Jian-nong, et al. A novel secure multicast scheme in mobile Internet[J]. Journal of Central South University of Technology, 2005, 12(6): 720-725.

[14] HUANG Guo-sheng. Analysis and Improvement of Mobile IP[D]. Changsha: Central South University, 2001. (in Chinese)

[15] WANG J X, HUANG G S, CHEN S Q, et al. An improved network layer protocol based on mobile IPv6[J]. Journal of Central South University of Technology, 2001, 8(4): 263-267.

(Edited by LI Xiang-qun)

Foundation item: Project (60573127) supported by the National Natural Science Foundation of China; Project (20040533036) supported by the Specialized Research Fund for the Doctoral Program of Higher Education of China; Project (05JJ40131) supported by the Natural Science Foundation of Hunan Province, China; Project(03C326) supported by the Natural Science Foundation of Education Department of Hunan Province, China

Received date: 2006-04-08; Accepted date: 2006-07-27

Corresponding author: CHEN Zhi-gang, Professor; Tel: + 86-731-8830797 ; E-mail: czg@mail.csu.edu.cn