Transcript Boundary-Moving Solutions

A Two-Tier Heterogeneous
Mobile Ad Hoc Network Architecture and
Its Load-Balance Routing Problem
C.-F. Huang, H.-W. Lee, and Y.-C. Tseng
Department of Computer Science and Information Engineering
National Chiao-Tung University
IEEE VTC 2003.
Speaker: Chung-Hsien Hsu
Nov. 19, 2003
Outline



Introduction
System Model
Solutions




Boundary-Moving Solutions
Host-Partitioning Solutions
Simulation
Conclusions
Introduction

Most of the existing works have assumed a
stand-alone MANET.

It would be more attractive if one can
simultaneously enjoy both:


The flexibility provided by MANET
The tremendous services/data provided in the Internet.
System Model
High-Tier
(PHS, GPRS, 802.11…etc.)
Low-Tier
( 802.11...etc. )
System Model – Problem Statement

Assumption:

The two-tier architecture is mainly used to support
Internet access.


Do not take intra-MANET communications into account.
The key issue:

How to utilize the bandwidths provided by the high-tier
gateways efficiently.

Load-balance routing.
System Model – Problem Statement (cont.)
(a, Ca=384 Kbps)
(b, Cb=115.2 Kbps)
(a, Ta)
(d, Td)
(c, Tc)
(b, Tb)
(i, Ti)
(f, Tf)
(c, Cc=11 Mbps)
(l, Tl)
(g, Tg)
(e, Te)
(h, Th)
(k, Tk)
(j, Tj)
(m, Tm)
System Model – Problem Statement (cont.)

To evaluate how balanced a routing scheme can achieve

Load Index (LI)


iS
i  Ti
x
Cx
Load-Balance Index (LBI)


Lx


max Lx min Lx
LBI 
max Lx
Goal:

To reduce the LBI of the whole network.
Boundary-Moving Solutions

The boundaries define the service range of each
gateway host for low-tier hosts to route their
traffics.

Boundary-Moving Solutions

Shortest-Path (SP) Routing


Based on routing distances.
Minimum Load-Index (MLI) Routing

Based on gateways’ loads.
Boundary-Moving Solutions
– Shortest-Path Routing

The dominance of p over q:


dom p, q   x x  S ,  x, p    x, q 
The service region of a gateway p:

reg  p  
 dom p, q 
qS ' p
Boundary-Moving Solutions
– Shortest-Path Routing (cont.)
Serving gateway: a, 0
Default gateway: a
a
Advertisement message: (a, 0)
Serving gateway: a,
1
c, 0
Default gateway: e
c
d
g
Serving gateway: a, 0
Default gateway: a
h
b
k
l
f
Advertisement message: (a, 1)
i
j
e
Serving gateway: a,
1
c, 0
m
Default gateway: e
c
n
o
c
p
Advertisement message: (c, 0)
q
r
Boundary-Moving Solutions
– Shortest-Path Routing (cont.)
a
d
g
e
f
h
i
j
b
k
l
n
c
p
m
o
q
r
Boundary-Moving Solutions
– Shortest-Path Routing (cont.)

This scheme can not achieve the goal of loadbalance routing in many cases.


The traffic demands from hosts are not necessarily.
Hosts may not be evenly distributed to all gateways.
Boundary-Moving Solutions
– Minimum Load-Index Routing


The boundaries between gateways will be adjusted
dynamically.
The scheme is fully distributed and is run by each
host independently.
Boundary-Moving Solutions
– Minimum Load-Index Routing (cont.)
Assumption:
Serving gateway: a, 0.7
Advertisement message: (a, 0.7)
a
Default gateway:
Gateway-switch
load athreshold= 0.5
Serving gateway: a, 0.7
d
Default gateway: e
Check:
g
a, 0.7 eT
(1) The serving time Serving
if over agateway:
time threshold
f
Default gateway: a
h
Tx  
Tx 

message: (a, 0.7)
L
g
'

L
g




 i l = Advertisement
(2)
(0.7 – 5/20) / ( 0.3 + 5/20) = 0.81 > 0.5
Cg '  
Cg 

j
b
k
l
Serving gateway: a,
0.7
c, 0.3
m
Default gateway: e
c
n
o
c
p
Advertisement message: (c,0.3)
q
r
Boundary-Moving Solutions
– Minimum Load-Index Routing (cont.)
a
d
g
e
f
h
i
j
b
k
l
n
c
p
m
o
q
r
Boundary-Moving Solutions
– Minimum Load-Index Routing (cont.)

Dynamical boundaries:



Lower traffic load will extend its service range.
Higher traffic load will shrink its service range.
This routing can lead to a more load-balanced
status compared to the SP routing.
Host-Partitioning Solutions

Hosts will be divided into groups, each to be
served by a gateway.

Host-Partitioning Solutions


Centralized Assignment (CA)
Distributed Assignment (DA)
Host-Partitioning Solutions
– Centralized Assignment

Assumption:

There is a centralized server



Gathering the traffic load information of all hosts.
Assigning hosts to gateways.
This problem is strongly related to the renowned
number-partitioning problem.
Host-Partitioning Solutions
– Centralized Assignment (cont.)

Execution steps:


Step 1: Sort all low-tier hosts into a list in a descending
order of their traffic indices.
Step 2: Sequentially assign each host x in the list to the
gateway g with the minimum L’g,
where L’g = Lg + Tx / Cg, until the whole list is
examined.
Host-Partitioning Solutions
– Centralized Assignment (cont.)

This scheme is costly


There will be a lot of message exchanges in the
network.
Without considering the hop-count factor.

The central server may assigns a host to a gateway which is far
away from it.
Host-Partitioning Solutions
– Distributed Assignment

Basic idea:

To configure a logical network to connect all gateways
together.



For gateways to exchange load and capacity information and to
trade low-tier hosts.
Logical links are constructed by low-tier links.
The logical network can be of any topology, but must be
connected.
Host-Partitioning Solutions
– Distributed Assignment


Low-tier hosts inform their traffic demands to their
current serving gateways.
Gateways delegate hosts to other gateways.
Host-Partitioning Solutions
– Distributed Assignment (cont.)
Load: 0.052
Capacity: 115.2 kbps
Load: 0.083
Capacity: 384 kbps
(a, 5)
Load: 0.00136
Capacity: 11 Mbps
(c, 5)
(b, 5)
Deldgate_to(b)
(d, 5)
(i, 5)
(f, 5)
(l, 5)
(g, 7)
(e, 5)
(h, 5)
(k, 5)
(j, 5)
(m, 5)
[Step 5]
1]
2]
3]
4]
Each
To
Gateway
compute
choose
gateway
aanotifies
tothe
host
determine
periodically
expected
which
host can
gthe
LBI
this
conveys
reduce
candidate
ifdecision
host
its
LBI
i is
load
gateways
with
greatly.
delegated
and
a Deldgate_to(b)
capacity
toto
which
gateway
information
it may
message.
b. delegate hosts.
to its
In
thisneighboring
example,
: 0.083/0.052
gateways.
g will be chosen.
= 1.596 > 1 (assumption: load threshold = 1)
Lg Lg '  lhost
Host-Partitioning Solutions
– Distributed Assignment (cont.)
Load: 0.083
Capacity: 384 kbps
Load: 0.052
Capacity: 115.2 kbps
(a, 5)
(d, 5)
Load: 0.00136
Capacity: 11 Mbps
(i, 5)
(f, 5)
(c, 5)
(b, 5)
(l, 5)
(g, 7)
(e, 5)
(h, 5)
(k, 5)
(j, 5)
[Step 6]
5]
Wait
for one
information-exchange
interval
go to step 2. message.
Gateway
a notifies
host g this decision
with and
a Deldgate_to(b)
(m, 5)
Simulation

Environment:


Area: 500 * 500 square area.
Host: 100~200 hosts are randomly generated.




Transmission distance: 100 units
Traffic load: uniformly distributed between 1~20 kbps.
Hosts can roam around randomly.
Gateway: 4 hosts with no mobility.
Simulation (cont.)

Four combinations of gateway capacities:





(128 K, 128K, 128K, 128K)
(128 K, 256K, 384K, 512K)
(128 K, 256K, 512K, 1024K)
(1024 K, 1024K, 1024K, 1024K)
Dividing the network unit square area evenly into four
250 * 250 regions.

The four gateways are each placed at the center of one region.
Simulation (cont.)
Conclusions

In this paper:

Extending the definition of ad hoc networks.


Providing two-tier heterogeneous mobile ad hoc network
architecture.
Proposing several solution for load-balance routing in
this architecture.

Boundary-Moving solutions



Easy to implement and compatible with current IP routing.
But in many cases can not lead to a load-balanced status.
Host-Partitioning solutions

Able to handle situations very well by paying some more routing
overheads.
a
d
g
e
f
h
i
j
b
k
l
n
c
p
m
o
q
r