Dynamic Traffic Load Balancing Mechanism for SHAKE Architecture
Hiroshi Esaki,
Hiroki Kan
Graduate School of Information Science and Technology, The University of Tokyo, Japanhiroshi@wide.ad.jp
kohki@hongo.wide.ad.jp
Abstract
In the mobile ad-hoc network, we frequently
experience the case where only the small bandwidth cellpone links are available without sharing these expensive
bandwidth’s, while high bandwidth wireless LAN link isavailable among end-stations. SHAKE, SHAred multiple
paths protocol for cluster networK, is the architectureusing the mobile IP so as to share the multiple external
cell-phone links via the wireless LAN link. Since thetraffic load balancing in the existing SHAKE system is ofstatic, the actual available bandwidth for the end-station
goes to bad performance. This is because the available
bandwidth for each cell-phone links is not stable anddynamically changed.
In this paper, the dynamic traffic balancing
mechanism for SHAKE system with available bandwidth
measurement is proposed and is proposed and performeda preminary evaluation. The prototype system
implementing the proposed mechanism can achieve large
performance improvement.

1. Introduction
High speed 3G cell-phone-card and PHS-data-card
provide a large bandwidth link to access the Internet formobile end-stations. However, comparing to the available
bandwidth provided by WiFi system, it is far smaller.
Though the bandwidth provided by WiFi system can beshared among the end-stations on the same link, thebandwidth’s of each cell-phone-card or PHS-data-card can
not be shared among the end-stations.
In the ad-hoc network environment, we frequently
experience the case where the high speed wired
connectivity via WiFi link is not available, while somesmall bandwidth cell-phone or PHS links provided by theend-stations are available. This is not a disconnected adhoc network, but is the network has multiple exclusively
available small bandwidth connectivity’s for eachindividual mobile end-station. In order to obtain the larger
available bandwidth, the end-station wants to aggregate
the external links that could be offered by the end-stations
with their small bandwidth external links, and these endstations must work as router, instead of as host. This (ad-hoc) network is so called as a multi-homing network,
which has multiple network connectivity’s to the different
network providers. There are many architectural proposals
to achieve multi-homing.
SHAKE [1], SHAred multiple paths protocol for cluster
networK, is one of the architecture for multi-homing, using
the mobile IP[2]. In SHAKE, the mobile IP operation isused to share the multiple external cell-phone links
provided by co-operative end-stations. These cooperative end-stations are connected to each other via thehigh bandwidth WiFi link.
However, since the traffic load balancing in the existing
SHAKE system is of static based on the link bit-rate of theexternal link, the actual available bandwidth for the endstation goes to bad performance. This is because theavailable bandwidth for each cell-phone links is not stable,
is dynamically changed and is different from the link bitrate. The link bit-rate and the available bandwidth arealways not identical. In this paper, the dynamic trafficbalancing mechanism for SHAKE system with theavailable bandwidth measurement is proposed andevaluated. The prototype system implementing theproposed mechanism shows that the proposed system
can achieve large performance improvement
Section 2 describes the SHAKE and related works.
Section 3 describes the proposed mechanisms, i.e.,
available bandwidth measurement scheme and loadbalancing, to improve the performance of existing SHAKE
system. Section 4 describes the prototype implementationand it’s performance evaluation. Finally, section 5 gives
brief summary of this paper.

2. Related Works
In this section, the related works with this paper arepresented.

2.1. Mobile IP [2]
In a legacy network, an IP address belonging to thecorresponding physical network segment is allocated.
When a node moves to the other network segment, it’s IP
address will be changed and the node can not preserve
the TCP connections without applying some mechanisms,
such as SCTP[3], parallel TCP[4], M/TCP[5] or mobile IP.

Here, we call the node, which change the location, asMN(Mobile Node). Mobile IP can preserve all the TCP
connections, even when an MN moves from somesegment to the other segment. This is because the source
IP address of every TCP connections will not be changed,
due to the change of network segment where the node
belongs to. Of course, it is the case where thedisconnected period, due to location change, is shortenough to avoid the termination of TCP connection by theexpiration of TCP’s persistent timer.
MN has multiple IP addresses, i.e., HoA(HomeAddress) and CoA(Care of Address). HoA is used toestablish the TCP connection with the corresponding
destination nodes. When MN is away from the network
segment where HA belongs to, HA(Home Agent) is thenode intercepting the IP packets, that are forwarded to theMN, and forward these IP packets toward the mobile node
having the corresponding HoA using the IP-in-IP
tunneling [6]. HA advertises the routing information,
which includes all the IP address of MNs taken care of by
the corresponding HA, the Internet. In order to intercept
the IP packets to the particular MNs, that are away fromthe home network, every MN being away from it’s homenetwork performs the registration of CoA to HA.

2.3. SHAKE [1]SHAKE is the architecture to share the small bandwidth
external links among the end-stations, which areconnected via a large bandwidth local link such as WiFi.
From the view point of an end-station, the multiple
external links can be aggregated in order to increase theavailable bandwidth so as to communicate with any nodein the global Internet space. It is said that, by using themultiple external links, the improvement of communication
qualities, associated with bandwidth, latency androbustness, could be achieved. It has been proposed
three types of SHAKE implementations. These are (1)Web SHAKE implemented at application layer, (2) TCPSHAKE implemented at TCP layer like SCTP, and (3) IPSHAKE implemented at IP layer with MIP.
In this paper, we discuss about IP SHAKE with MIP,
that is called as Mobile IP SHAKE. In this architecture,
HA works as the load balancer to use multiple paths
toward the destination node (i.e., MN). Figure 1 and 2
show the architecture and IP packet transmission in
Mobile IP SHAKE system.

2.2.Multi-homing with MIP and NEMO
Framework [7][8][9]Multi-homing and multi-path technology improves theavailability of host and network connectivity. Since thenode and network behavior of mobile networking andstatic networking are different, the different architecture
has been discussed and proposed. This architecture
provides the common architecture both for mobile andstatic networking environment, using the MIP andNEMO(Network Mobility) [8] framework. The proposedarchitecture only requires (1) modification of Mobile IP sothat multiple-CoA can be used, (2) policy control protocol
for multiple-path packet transmission.
Paper [7] and [9] propose the concept of “virtual” home
network for nodes. We do not need the physical home
network for MNs or mobile network. Multiple HAs shouldbe geographically distributed across the Internet, for theimprovement of service availability and for the loadbalancing/distribution.
When all the multiple HAs
advertise the same network prefix to their adjacentrouter/network, the traffic is automatically routed to thenearest HA from the view point of routing protocol
topology. Multiple tunneling paths between HA andmulti-homed node (host/router) should be able to beestablished.

Figure 1. IP packet transmission from CN to MN

Figure 2 IP packet transmission from MN1 to CN
As shown in figure 1 and 2, mobile nodes (MN2 and MN3in the figures) allow to use their bandwidth by MN1. MN2and MN3 work as a kind of router, i.e., forward thereceived IP packets, and take care of IP tunneling. The IPpackets from CN to MN1 are distributed into three paths
at HA. The IP packets from MN1 to CN are distributed
into three paths by MN1.
The algorithms of IP packets distribution implemented in
the existing Mobile IP SHAKE are a simple round robin
and the weighted round robin proportional to the links’
bit-rate.

traffic volume for bandwidth measurement is generally oftrade-off parameters.

3.1. Available bandwidth measurement
In this subsection, we discuss and propose themechanism for available bandwidth to be applied in theproposed system.
---

Simple round robin
All paths are equally used. When the latency
diversity and/or the available bandwidth among themultiple paths is large enough, the system
experiences serious performance degradation. The
performance degradation will occur due to the packet
re-ordering observed at the destination node (MN1),
and the performance is suffered from the worst
quality and the smallest available bandwidth path.
Weighted round robin proportional to the links’ bitrate
IP packets are distributed in proportional to the links’
bit-rate. When the latency is the same among themultiple paths and the available bandwidths’ areactually proportional to the corresponding link bitrate, the system should achieve good performance.
However, in general, the latency among the multiple
paths are not identical, and the actually available
bandwidth versus it’s link bit-rate is not identicalamong multiple paths and it is changed according thenetwork status.

-3.Proposed Traffic Distribution Mechanism forSHAKE System
In this section, the mechanisms of the traffic
distribution so as to improve the actual available
bandwidth performance of IP packet delivery in theexisting SHAKE system.
As discussed in the previous section, the existing
SHAKE system applies the simple weighted round robinbased on link’s bit-rate. However, in the actual system, theavailable bandwidth would not proportional to thecorresponding link bit-rate, and the available bandwidth ischanged according to the network condition.
We propose the IP packet distribution mechanism,based on the available bandwidth measurement for eachalternative path. The IP packets are distributed at HA, in
proportional to the measured available bandwidth. Here,
since the external links do not have large bandwidth, wehave to carefully choose the bandwidth estimation
mechanism. Especially with the actual measurement
mechanism, the accuracy of measurement and the requires

One way path bandwidth measurement
Since an MN has multiple up-stream paths (from MNto CN) and down-stream paths (from CN to MN via
HA), we have to measure all of these uni-directional
paths. We could measure the bandwidth against theround-trip path. However, since the available
bandwidth for up-stream and down-stream is not
generally symmetric, the bandwidth measurement
should be for one way path.
Bandwidth measurement by packet pair
There are passive and active for bandwidth
measurement. With passive measurement, we haveto analyze the bandwidth using the user packets.
User packets would not be always transmitted fromthe nodes, and it would not be easy to obtain theavailable bandwidth with small latency. On thecontrary, with active measurement, we generate theprobe packets to measure the bandwidth. Though wemust waste the bandwidth by these probe packets, itwould be easier to obtain accurate results with smalllatency. Therefore, we propose to use the active
measurement in the proposed system. There are a lotof active measurement mechanisms for available
bandwidth. With the consideration from the view
point of bandwidth consumption by the probing
packet. we pick up the packet pair. This is because
the packet pair does not need a lot of packet
transmission and does not need large size packet
transmission.

3.2. Path selection for traffic distribution--

Packet-by-packet path selection
HA must pick up one of available paths, whenever it
receives the IP packet. The selection of path can beaware of TCP/UDP session or unaware of. Since it ishard to predict the actual traffic pattern and volume
for each TCP/UDP session, we propose to pick up
session un-aware path selection. It means thetransmission path is selected packet-by-packet.
Allocation of bandwidth for each path
Figure 3 shows the example how the bandwidth isallocated to each path. First, the whole of bandwidthis equally divided among the MNs, which isexcepting the MN without the reception of ACK
message against packet pair probing. MN1 and MN2

in the figure has just registered to HA, but have notcompleted the bandwidth measurement. MN5 does
not respond to the packet pair probing. Second, theallocated bandwidth for the path with completed
bandwidth measurement is re-divided in proportion
to the measured bandwidth for each path.

--

Bit-rate for access link for MN
Ø MN1 : 128 kbps
Ø MN2 : 576 kbps
File size to be transmitted from CN to MN1
Ø 1MB, 3MB, 5MB, 10MB

Figure 4 Evaluation system
Figure 3 Allocation of bandwidth for each path

4. Implementation of Prototype andPerformance Evaluation
In this section, we describe the prototype
implementation and it’s performance evaluation.

4.1. Prototype System Implementation
As discussed in the previous section, we use the packet
pair for bandwidth measurement. We use the “bing”
software [11]. “bing” uses ping messages with different
size of ICMP packet to the target two nodes. HA and MN
are implemented on Vine Linux 2.5.

4.2. Evaluation System
Figure 4 shows the evaluation system. We do not use
actual wireless link for MN. The wireless links betweenRouter to MN1 and Router to MN1 is emulated by thewired link applying the “dymmynet”. By applying thedummynet at Router, MN1 and MN2, the available
bandwidth for these links can be controlled, so as tofluctuate their available bandwidth.

4.3. Evaluation Results
Figure 5 shows the performance evaluation, associatedwith the effective end-to-end throughout using SCP(Secure Copy Protocol). Using the dummynet, the link bitrate for MN1 and MN2 is set as below. Here, in theevaluation, we have not change the available bandwidth
for these links.

Figure 5 Result of Performance Evaluation

5. Conclusion
In this paper, the dynamic traffic balancing mechanism
for SHAKE system with available bandwidth measurement
is proposed and performed a preminary evaluation. The
prototype system implementing the proposed mechanism
can achieve large performance improvement.
SHAKE is the architecture using the mobile IP so as toshare the multiple external cell-phone links via the wireless
LAN link. The evaluation performed in this paper is justpreminary. We must evaluate the proposed mechanismwith more realistic condition, e.g., using the real cell-phone
link or using the link whose available link is dynamicallychanged.

REFERENCES[1] Kenji Koyama, Yosuke Ito, Hiroshi Mineno, Susumu
Ishihara, ``Performance evaluation of TCP on Mobile IP
SHAKE," IPSJ Journal, Vol.45, No.10, pp.2270-2278,
Oct.2004.
[2] C. Perkins, “IP Mobility Support for IPv4”, RFC3344,
August 2002.
[3] R. Stewart, Q. Xie, K. Morneault, C. Sharp, H.
Schwarzbauer, T. Taylor, I. Rytina, M. Kalla, L. Zhang, V.
Paxson, “Stream Control Transmission Protocol”,
RFC2960, October 2000.
[4] Thomas J. Hacker, Brian D. Athey, “The End-to-End
Performance Effects of Parallel TCP Sockets on a Lossy
Wide-Area Network”, Proceedings of the 16th IEEECS/ACM International Parallel and Distributed Processing
Symposium, 2002.
[5] K. Rojviboonchai, H. Aida, “An Evaluation of Multi-path
Transmission Control Protocol (M/TCP) with Robust
Acknowledgement Schemes”, Internet Conference 2002,
October, 2002.
[6] C. Perkins., “IP Encapsulation within IP”, RFC2003,
October 1996.
[7] S.Uda, N.Ogashiwa, K,nagami, K.Kondo, I.Nakagawa,Y.Shinoda, H.Esaki, "Design and Implementation ofOverlaying Multi-Homing Architecture", Workshop on
IPv6 and Application at IEEE/IPSJ SAINT2004, January2004.
[8] H.Esaki, "Multi-Homing and Multi-Path Architecture Using
Mobile IP and NEMO Framework", Panel 1 (The Future of
the Internet Architecture) at IEEE/IPSJ SAINT2004,
January 2004.
[9] K.nagami, S.Uda, N.Ogashiwa, R.Wakikawa, H.Esaki,H.Onishi, "Multi-homing for small scale fixed network
Using Mobile IP and NEMO", (work-in-progress), IETF
Internet-Draft, draft-nagami-mip6-nemo-multihome-fixednetwork-03.txt, Feburary 2005.
[10] V.Devarapalli, R.Wakikawa, A.Petrescu, P.Thubert,"Network Mobility (NEMO) Basic Support Protocol",IETF RFC3963, January 2005.
[11] Satellite Link Simulation,
http://ai3.asti.dost.gov.ph/sat/index.html