Transcript Yeh-TMC09-slide

Jui-Hung Yeh, Jyh-Cheng Chen,
and Prathima Agrawal
Presented By Yinan Li
Oct. 20, 2009
Agenda
 Introduction
 Related Work
 Design Principles
 Proposed FINCH
 Performance Analysis
 Numerical Results
 Conclusions
Introduction
 WiMAX (IEEE 802.16)
 A promising standard for next-generation broadband
wireless access networks
 Mobility support for users moving at vehicular speed
 Components


Access Service Network (ASN)
 providing radio access to WiMAX subscribers (mobile stations or
MSs)
 Consisting of one or more ASN Gateways (ASN GWs) and Base
Stations (BSs)
Connectivity Service Network (CSN)
 providing IP connectivity services
 ASNs are connected by CSN
Generic Mobile WiMAX Network
Architecture
Introduction
 Mobility Management
 Inter-domain (inter-CSN)


Mobile IP (MIP) is suitable inter-CSN mobility management
It is not suitable for intra-CSN mobility management, due to
 Large HO latency and signaling cost; large end-to-end delay
 Intra-domain (intra-CSN)



Localizing location handoff and update operations to reduce the
signaling cost
Tunneling-based
 MIP, HMIP, IDMP
Host-specific-routing-based
 Cellular IP and HAWAII
Fast Intra-Network and Cross-layer
Handover (FINCH)
 Proposed for intra-CSN (intra-domain) mobility





management
Achieving fast handover (HO), especially for real-time
services
Cooperating with Mobile IP
Localizing location update to reduce the handover latency
and signaling cost in Mobile IP
Cross-layer design: considering HO in both link and
network layers (L2 and L3)
FINCH is a generic protocol for other IEEE 802-series
standards
Related Work (1/5)
 Inter-domain Mobility Management Protocols
 Mobile IP (MIP)


Mobility support in the IP layer
MIPv4 and MIPv6 (with route optimization)
 Session Initiation Protocol (SIP)

Mobility support in the application layer
 Host Identity Protocol (HIP)



A new protocol layer, HIP, lies in between the network and transport
layers
The roles of locator and identifier of IP addresses is decoupled
 IP address is only used for packet routing, a Host Identifier (HI), which
is a public key, is used to represent the host identity
Rendezvour Server (RVS) maps HIs of MSs to their IP addresses
Related Work (2/5)
 Intra-domain Mobility Management Protocols
 Tunneling-based


Tunneling-based protocols generally employ a hierarchical mobility
architecture (e.g., a tree structure) or require a gateway to tunnel
packets to and from MSs
HMIP, Intra-domain Mobility Management Protocol (IDMP), and
Dynamic Mobile Anchor Point (DMAP)
 Host-specific-routing-based



Host-specific-routing-based protocols generally adopt new routing
protocols to support intra-domain mobility management
Location information of MSs is maintained by access routers (AP) in a
distributed location cache and is updated by regular packet routing
Cellular IP and HAWAII
Related Work (3/5)
 Fast Handover (Fast HO; RFC 4988 & RFC 4068)
 Another technique for reducing HO latency and packet loss rate
 Fast HOs for MIPv4 and MIPv6 (F-MIPv4 and F-MIPv6)


The basic idea is that an MS can determine whether it is moving to a new
access router (NAR) before the HO happens
The previous access router (PAR) of the MS forwards packets destined to
the MS to its NAR, which buffers the packets for the MS
 Two modes of operations


Predictive: PAR forwards packets to NAR, which starts buffering packets
before L2 HO; Packets buffered by the NAR can be forwarded to the MS
immediately after L2 HO.
Reactive: The tunnel between the PAR and NAR for packet forwarding is
established after L2 HO. PAR forwards packets to NAR after L2 HO,
which then forwards packets to the MS.
Related Work (4/5)
PAR starts forwarding
received packets to NAR
before the HO
NAR delivers buffered
packets to the MS after
the HO
L2 HO
Related Work (5/5)
Tunnel between PAR and NAR
is established after the HO
L2 HO
PAR forwards received
packets to NAR after the
tunnel is established
NAR delivers packets to
the MS after the HO
Design Principles
 Fast HO: Supporting fast HO for real-time services
 Cross-layer: Reducing not only HO delay, but also packet delivery
overhead
 Scalability: Avoid using centralized management facilities,
operation of the protocol should be distributed
 Paging Support: Paging is an effective solution that enables
mobile nodes to reduce unnecessary location update
 Timely of deployment: Considering only IPv4 /Ethernet because
IPv4 over Ethernet like link model is most likely to be deployed for
current WiMAX networks
 Flexibility: the proposed FINCH should be a generic protocol for
not only WiMAX, but also other types of IP networks
Mobility Management in WiMAX:
Current Status
 MAC Layer Handover (L2 HO)
 When an MS moves from one BS to another BS, L2 HO is
needed
 IEEE 802.16e standardizes the MAC layer (L2) HO only
 Network Layer Handover (L3 HO)
 When an MS moves to a new BS in a different subnet, a new CoA
(NCoA) is acquired and registered with its HA
 Packet delivery follows the standard MIP procedure
 MIP is chosen by the WiMAX Forum to deal with mobility
management in the network layer (L3)

The Home Agent (HA) of a MS is located in the CSN of the MS’s
Home Network Service Provider (H-ISP); ASN GW supports the
Foreign Agent (FA) functionality
Cross-Layer Design
 Motivation
 Simplifying the HO procedure

Two HO procedures if L2 and L3 are considered separately
 Reducing the overhead and latency

Reducing the number of ARP messages
 Approach
 Integrated mobility management and packet routing within a
domain (CSN) through the so-called Forwarding Table (FT)


A special table lookup technique that works in both link and
network layers
 Location updates in the link layer and network layer are coupled
together
Completely replaces ARP in Ethernet over IPv4
The Forwarding Table (FT)
 Used by both L2 and L3 devices
 FT replaces routing tables in L3 devices and bridging tables in L2 devices
 FT Fields
 MS MAC Address
 MS IP Address: HoA or permanent address
 Forwarding MAC address: specifying to which the IP packets destined to
the MS should be forwarded to
 Wireless port: if the MS is maintained by a BS
 Time stamp
The FT in BS1
Packet Forwarding - Algorithm
Packet Forwarding - Examples
 From the perspective of BS1
 Packets destined to MS1 currently attached to BS1
 The packet can be directly transmitted to the MS using MS’s
MAC address as specified in the 1st column of BS1’s FT
 Packets destined to MS2 currently in CSN-2/ASN-2
 Encapsulated into a MAC frame and forwarded to ASN-1’s GW
whose MAC address is specified in the 3rd column of BS1’s FT
 The FT of ASN-1’s GW is looked at to find out the forwarding
MAC address of the next node to which the packet should be
forwarded
 ASN-1’s GW encapsulates the packet into a MAC frame and
forwards the frame to the next node using the MAC address
specified in the 3rd column of its FT
 The process is repeated until the packet reaches the destination
Packet Forwarding (Cond.)
 The Usage of the FT
 The 1st column of the FT is used as indices by L2 devices
 The 2nd column of the FT is used as indices by L3 devices
 The 3rd column is used to find out the forwarding MAC address
 NULL if the 1st column is used as the destination MAC address, i.e., the
destination MS is currently attached to the BS.
 ARP in IPv4 over Ethernet is replaced by simple lookup in the FT
 The 1st and 2nd columns form a mapping between IP and MAC addresses
Reducing ARP Messages
 Address Resolution Protocol (ARP) in WiMAX
 Broad-and-reply nature


wasting bandwidth and causing extra delay
Executed frequently if an MS moves frequently
 To achieve fast HO, address resolution should be highly efficient
 The Solution of FINCH: FT replaces ARP
 Mapping between the IP address and MAC address of an MS is done
by simple table lookup in the FT
 Whenever an IP packet comes in, the IP address field of the FT is
searched to locate the entry for the target MS
 The IP packet is then encapsulated into a MAC frame using either the
target MS’s MAC address as specified in the 1st column or the
Forwarding MAC Address as specified in the 3rd column
Handover and Location Update
 Packet forwarding relies on the correctness of the FT
 FT should be properly updated each time when an MS moves
 HO Procedure
 When an MS handovers to a new BS, it sends the new BS a MAC frame




to update its entry in the new BS’s FT; the new BS then forwards the
MAC to all adjacent nodes
All nodes that received the MAC frame also forward the MAC frame to
their adjacent nodes in the same domain
All nodes that received the MAC frame including the old BS, the new
BS, and other nodes update their FTs accordingly to the following
algorithms
If a node has already received the MAC frame, it will not rebroadcast it
As the frame propagates, new routes through the network can be
established to reach the MS
Location Update Algorithm
Location Update Algorithm (cond.)
Crossover
Node
Forwarding
direction
P-FINCH: Paging Extension for FINCH (1/3)
 Motivation
 Enhancing the energy efficiency and minimizing the signaling
overhead of location update
 An optional component in FINCH
 Paging Group (PG)
 Each BS in a WiMAX system is assigned to a PG, which is




similar to a cluster
The assignment can be based on geographical or load-balancing
considerations
Each PG has a unique PG Identifier (PGI)
In each PG, there is a Paging Controller (PC)
An idle MS performs location update only when it moves to
another PG, otherwise, the MS keeps silent
P-FINCH: Paging Extension for FINCH (2/3)
 Paging Procedure
 Entering Idle Mode
 When an MS intends to enter Idle Mode, it sends the current serving BS a
Deregistration message to initiate the Idle Mode
 The serving BS sends an IM-Entry_MS_State_Change request to the PC of the
PG to which the BS belongs, which then registers the MS to a paging list and
sends out a location update message on behalf of the MS
 Future packets destined to the MS will be forwarded to and buffered by the PC
 Handover while in Idle Mode
 When the MS handovers to a new PG while it is still in Idle Mode, it must send a
location update message to the PC of the new
 The PC of the new PG will send out a location update message on behalf of the
MS
 After the location update, packets sent to the MS will be forwarded to and
buffered by the new PC
P-FINCH: Paging Extension for FINCH (3/3)
 Paging Procedure
 When the PC wants to awake the MS and deliver buffered packets
to the MS, it sends a paging request to all the BSs within the PG
 Upon receiving the request, the MS sends a location update
message to the PC
 Upon receiving the location update, the PC removes the entry for
the MS in the paging list and starts delivering buffered packets to
the MS
 Energy Conservation
 Because location update is required only when an MS handovers to
a new PG, the paging extension significantly reduces the energy
consumption of the MS
Performance Analysis: Handover Latency (1/3)
 HO Latency: the time interval during which an MS cannot receive
and transmit packets due to the HO procedure
 The time interval between the time the MS loses the L2 connection
and the time it can receive or transmit packets through the new BS
 HO Latency consists of
 Link layer switching latency, which reflects the 802.16e L2 HO
latency
 IP connectivity latency, which includes the duration of IP layer
movement detection, IP address acquisition, and configuration
 Location update latency, which includes the latency for binding
update and the latency for forwarding packets to the MS’s new IP
address through the new BS
DHO  DL 2  DIP  DLU
Handover Latency (2/3)
DHO, FINCH  DL 2  DIP  DLU  DL 2  DIP  2  tCR  MS  t Mi H
One-way delay for packet
transmission between the
crossover node(CR) and the MS
Computation delay of the hostspecific-routing-based micromobility management protocols
DHO, MIP  DL 2  DIP  DLU  DL 2  DIP  t AR  2  t HA MS  t MIP
Address
resolution
delay
One way delay for packet
transmission between HA
and the MS
DHO, FIP Pre  DL 2  t AR  2  t NAR  MS
IP connectivity latency is eliminated
in F-MIP-Pre because the new CoA
can be configured before L2 HO
One way delay for packet
transmission between NAR
and the MS
Handover Latency (3/3)
DHO, FIP Re  DL 2  t IP  mv  t AR  3  t PAR NAR  2  t NAR  MS
Latency for IP layer movement
detection; this is needed because the
tunnel between PAR and NAR is
established after L2 HO
One way delay for packet
transmission between PAR
and NAR
DHO,CIP  DHO, HAW AII  DL 2  DIP  t AR  2  tCR  MS  t Mi H
One-way delay for packet
transmission between the
crossover node and the MS
DHMIP  DL 2  DIP t AR 2  tCR  MS  t MiT
Computation delay of the
tunneling-based micro-mobility
management protocols
Performance Analysis: Packet Loss (1/2)
LHO, FINCH   p  ( DHO, FINCH  tCR  MS )
In FINCH, packets are lost when the location update
messages are still propagating to the crossover node
LHO, MIP   p  ( DHO, MIP  t HA MS )
In MIP, packets are lost before an MS registers its new CoA
with its HA
LHO, F  MIP Pre  max{ 0,  p  ( DHO, F  MIP Pre  t NAR  MS )  BufferNAR }
In F-MIP predictive mode, packets are lost if the coordination of fast HO
signaling is not correct or packets are failed to be buffered in NAR.
Packet Loss (2/2)
LHO, F  MIP Re   p  ( DL 2  t IP  mv  t AR  t PAR NAR  t NAR  MS )
In F-MIP reactive mode, packets are lost in PAR before the tunnel between
PAR and NAR is established and packets can be forwarded to the MS
LHO,CIP  LHO, HAW AII   p  ( DHO,CIP  tCR  MS )
In CIP and HAWAII, packets are lost when the location
update messages are still propagating to the crossover node
LHO, HMIP   p  ( DHO, HMIP  tCR  MS )
In HMIP, packets are lost when the location update
messages are still propagating to the crossover node (GFA)
Network Topology
Each domain (CSN) is
modeled as a complete
binary tree with K leaf
nodes (ASNs)
ASN-GWs are
abstracted as leaf nodes
An MS is assumed to move
i steps (ASNs) from the
kth node (ASN)
Performance Analysis: Location Update Cost (1/7)
 Parameters
  : Call to Mobility Ratio (CMR)
U : the average cost of location update to an MS’s HA in
MIP

: the cost of setting up a single link when the intra-domain
mobility management protocol sets up the path in the intradomain

: the cost of address resolution
 V : the cost of a unicast signaling message between the PC
and the BS. The cost is used for location update from the BS
to the PC and paging request from the PC to the BS
 L: the cost of setting up the direct connection between the
NAR and PAR in F-MIP
S
A
Location Update Cost (2/7)

CMIP (  )   iU (i ) 
i 0
U

The probability that an MS moves i steps
between two consecutive packet arrivals

C F  MIP (  )   i (U  L) (i ) 
i 0
U L

F-MIP reduces the HO latency by forwarding packets from
PAR to NAR. However, there is an additional signaling cost
to setup the direct connection between PAR and NAR
Location Update Cost (3/7)
n
(n)   log(( 2 j  1)  (2 j  3)) 
j 2
Based on the given network topology, the number of
hops for a location update message when an MS moves
from the first cell to the nth cell within the complete
binary tree. Deriving this quantity is equivalent to
finding the height of the crossover node or the lowest
common ancestor problem.
Location Update Cost (4/7)
g  f m* ( ) 


f m (t )e t dt  g
i 0
The cell residence time is assumed to be a random variable with a
general density function fm(t) with the Laplace transform g;
lambda is the packet arrival rate
1 g

if i  0
 1   ,
(1  g ) 2 K j q
 (i)  
 ( jK  q) 
(g ) g
2 i 1
(
1

g
)
g
g

, if i  0


Because an MS can move across several
domains, let i = jK + q, where j is the
number of domains crossed
Location Update Cost (5/7)
The signaling cost of location
registration with the HA
The signaling cost of intradomain location update
Location Update Cost (6/7)
In HAWAII, an MS only needs to register with
the Domain Root Router (DRR) by using the
same message of MIP registration
The cost of address
resolution (ARP) is
considered
CHMIP ( , K ,  )  CCIP ( , K ,  )  CHAWAII ( , K ,  )
Location Update Cost (7/7)
Assuming that each PG is rooted at
the PC and has P (P=2^n) nodes.
The location update cost
consists of the normal
location update cost
originated by the PC and
the unicast location update
cost from BS to the PC
Performance Analysis: Overall Cost (1/3)
 Overall cost = location update cost + packet delivery cost
 Parameters
 M: the packet delivery cost of MIP
 F: the packet forwarding/routing cost in a single CSN
 T: the additional re-encapsulation and decapsulation cost of MIP,
F-MIP, and HMIP
 B: the cost for buffering packets at NAR in F-MIP
TMIP (  )  CMIP  M  T 
U

 M T
TF  MIP (  )  CF  MIP  M  2T  F  B 
Additional forwarding cost,
encapsulation cost, and buffering cost
U

 M  2T  F  B
Overall Cost (2/3)
HA first tunnels packets to the
serving CSN, which then forwards
them to the MS hop by hop
HA first tunnels packets to the
serving CSN, which then forwards
them to the MS hop by hop
Overall Cost (3/3)
When packets arrive (M)
1) the PC must page all P cells in the
PG to locate an MS (PV)
2) Upon receiving the paging request,
the MS sends the PC a location
update message, which traverse
(log(P) hops (Slog(P))
3) Packets will be forwarded to the MS
by the PC (F)
HMIP incurs additional
encapsulation/decapsulation
costs (T)
Energy Consumption (1/2)
 Mainly determined by the location update signaling
 FINCH vs. P-FINCH
 Parameters
 Each uplink transmission consumes u units of energy
 In active mode, each MS also consumes r units of energy
per time unit while the receiver is on
 An MS in idle mode consumes b units of energy per time
unit

r
u


EFINCH (  )   i  (u  )   (i ) 
i 0

r

Energy Consumption (2/2)
Numerical Results: Parameters
Numerical Results: Handover Latency
Numerical Results: Packet Loss
Numerical Results: Location Update Cost
Numerical Results: Location Update Cost (Cond.)
Numerical Results: Overall Cost
Numerical Results: Energy Conservation
Conclusion
 Mobile WiMAX designed to support MSs moving at vehicular
speed
 MIP is designed for inter-domain mobility management, but
not suitable for intra-domain mobility management
 Cannot support fast HO for MSs moving frequently
 Exaggerated for real-time services
 FINCH is proposed to support fast intra-domain mobility
management
 Complementary to MIP
 Cross-layer design that reduces both location update and overall
costs
 P-FINCH: Paging Extension for FINCH
 Reduces the signaling overhead and energy consumption
Questions?