Transcript An Efficient Quorum-based Fault-Tolerant Approach for Mobility

An Efficient Quorum-based FaultTolerant Approach for Mobility
Agents in Wireless Mobile
Networks
Yeong-Sheng Chen Chien-Hsun Chen Hua-Yin
Fang
Department of Computer Science, National
Taipei University of Education
Outline





Introduction
Related Work
Cyclic Quorum-based Replication
Mechanism
Performance Evaluation
Conclusion
Introduction


Mobile IP Protocol is a protocol to
support Hosts mobility.
The architecture of mobile IP


Mobile Host (Mobile Node)
Mobility Agent


Home Agent
Foreign Agent
Introduction
RAN
HA
Router
MN
Home Agent
Radio Access Network
Introduction
FA
RAN
HA
FA
Router
Router
Internet
Router
Router
Router
MN
FA
FA
Introduction
Register
FA
RAN
HA
FA
Router
Router
Internet
Router
Router
HA allocates an address
and maintains the MN
Send data to A through HA and FA1
Router
MN
FA
A
FA1
Introduction
Allocate
CoA or
DHCP
Request
Care-of
Address
FA
RAN
HA
FA
Tell HA stores MN’s CoA
MN
Router
FA
FA
Introduction
MN
FA
RAN
FA
HA
A wants to send data to MN
Router
FA
A
FA
Introduction


In multiple mobility agents environment, data
will be distributed stored in the different
agent.
Distributed data processing will cause some
problem



Fault tolerance
Registration delay
Load balance
Introduction

HA crashed
FA
FA
HA
MN
FA
FA
Introduction

To offer solutions to these problems,
many fault-tolerant approaches have
been proposed.
Related Work-
FTMIPP
Update HA’s bindings
Registration
request
RAN
FA
HA
Router
Router
Acquire Home Address
under HA
Router
A
Update HA’s bindings
FA
R. Ghosh and G. Varghese, “Fault-Tolerant Mobile IP,” Technical Report WUCS-98-11,
Washington Univ., Apr. 1998.
Related Work
The drawback of FTMIPP



FTMIPP
Long registration time
Low resource utilization
Conclusion

Use fully redundant mobile agent to solve
fault tolerant problem
Related Work
Response
Search MNs
Request to store the bindings
FA
HA
FA
Manage the region
belong to HA
Detect failed
OA&M
(Operation Administration
and Maintenance)
A
FA
J. W. Lin and J. Arul, “An Efficient Fault-Tolerant Approach for Mobile IP in Wireless
Systems,” IEEE Transactions on Mobile Computing, VOL. 2, NO. 3, Jul.-Sep.
2003. .
Related Work
Request to Restore
FA
HA
FA
HA recovered
A
FA
OA&M
Related Work

The drawback of the scheme

Spend extra time on



Searching MNs
Delivering bindings
Extra hardware cost
Goal

The backup mechanism




should maintain and backup bindings
efficiently
should not bring heavy system load
should balance
Many researches use quorum-based
mechanisms to backup data in
distributed systems.
Cyclic Quorum-based
Replication Mechanism

Assumption

Not all HAs of a quorum in a home network will
fail at the same time.

Whenever a HA crashes, any data in the volatile
media of the HA will be gone

The failure occurs in the network only by reason
of the faulty HA

The home network will divide into several network
segments and each HA will take charge of one of
the segments.
Cyclic Quorum-based
Replication Mechanism


To balance the backup load, the author
uses quorum to achieve the goal
Per-allocate the storage place with
location by using quorum
Cyclic Quorum-based
Replication Mechanism

Cyclic Quorum-based could balance the
load
1
1
2
3
Cyclic Quorum-based
Replication Mechanism
Quorum type
Voting
Grid

Quorum
proposed
Quorum Size
Weighted Majority
N

 2  1
Hierarchical Quorum
Consensus
N 0.63
Rectangular Grid
N=R*C
Square Grid
2 N 1
Triangular Grid
2 N
Tree
Tree
Cycle
Circle
 N  1
 2 
N
M. J. Yang, Y. M. Yeh, and Y. M. Chang, “Legion Structure for Quorum-Based
Location Management in Mobile Computing,” Journal of Information Science and
Engineering, Vol. 20, pp. 191-202, 2004.
Cyclic Quorum-based
Replication Mechanism


There are N HAs in the networks and N
distinct quorum
According to Cyclic Quorum, each HAs
need backup N bindings of other HAs
1
Cyclic Quorum-based
Replication Mechanism

Example:



There are 8 MAs in the network
The Quorum sets ={Q1,Q2,Q3….,Q8}
Ex.
Q1={HA1,HA2,HA3},
Q2={HA2,HA3,HA4},
Q3={HA3,HA4,HA5},……Q8={HA8,HA1,HA2}

HA1 selects Q1, HA2 selects Q2
…………,HAN selects QN
8
1
7
2
6
3
5
4
Cyclic Quorum-based
Replication Mechanism
8
8
1
7
2
6
3
4
5
7
2
6
3
1
8
2
6
3
Q5
4
7
2
6
3
6
3
8
6
3
Q6
4
Q4
8
1
7
2
6
3
5
4
5
4
5
1
2
1
2
Q3
7
5
8
1
7
Q2
7
5
4
5
Q1
8
8
1
1
7
2
6
3
4
5
Q7
Q8
4
Cyclic Quorum-based
Replication Mechanism


HA1 stores in 3 quorums
EX. HA1 stores in {Q1,Q7,Q8} for backup
8
8
1
8
1
7
2
7
2
6
3
6
3
5
4
5
Q7
Q8
4
1
7
2
6
3
4
5
Q1
Cyclic Quorum-based
Replication Mechanism

HA1 will sends the bindings to HA7 and
HA8 periodly
RAN
HA1
Router
Router
Router
MN
HA8
HA7
Cyclic Quorum-based
Replication Mechanism

If HA1 failed, HA7 and HA8 will takeover
the member of HA1
8
8
1
8
1
1
7
2
7
2
7
2
6
3
6
3
6
3
4
5
Q1
5
4
5
Q7
Q8
4
Cyclic Quorum-based
Replication Mechanism

If HA1recovers, HA7 and HA8 will sends
the bindings to HA1
8
8
1
8
1
1
7
2
7
2
7
2
6
3
6
3
6
3
4
5
Q1
5
4
5
Q7
Q8
4
Performance Evaluation

Simulator :QualNet

Compare with FTMIPP
Performance Evaluation
FTMIPP
Bindings per backup HA
CQFTP
Number of MNs
Performance Evaluation
FTMIPP
Extra Backup Message
CQFTP
Performance Evaluation
Number of registered MN per Backup HA
FTMIPP
CQFTP
9
16
25
36
49
Number of Multiple HAs
64
81
Performance Evaluation
FTMIPP
Average Registration Delay (Sec)
CQFTP
2
4
6
8
10 12 14 16
Number of Multiple HAs
18
20
Performance Evaluation
FTMIPP
Average Registration Delay (Sec)
CQFTP
Mobility Rate
Conclusion

The authors proposed a mechanism




Don’t need any extra hardware cost
Reduce backup bindings by using the small
quorum size
Balance the load of take over process
Low registration overhead