Transcript Masters Thesis Slides

AN INTEGRATED ROUTING AND DISTRIBUTED
SCHEDULING APPROACH FOR HYBRID IEEE 802.16E
MESH NETWORKS FOR VEHICULAR BROADBAND
COMMUNICATIONS
Rahul Amin
Electrical and Computer Engineering
Clemson University
M.S Thesis Defense, 11/25/2008
Advisor – Dr. Kuang-Ching Wang
®
Outline
• Background and Relevant Work
• Objective
• Network Model
• Routing and Scheduling Solution
• Analytical Model and Simulation studies
• Conclusions and Future Work
®
Background – WiMAX Operation Modes
• WiMAX – Worldwide Interoperability for Microwave Access
– IEEE 802.16-2004
– IEEE 802.16e-2005 (Mobile WiMAX) extends mobility (handover) support
• Point-to-Multipoint (PMP)
– Subscriber Stations (SS) connect via Base Station (BS)
– BS in charge of coming up with a transmission schedule
– Five Classes of Service defined to support QoS
• Mesh
– SSs and BSs can communicate directly to other SSs and BSs
– Scheduling solution can be centralized or distributed
– QoS differentiation is on packet-by-packet basis
®
Background – PMP Mode Frame Structure
• Each frame divided into uplink and downlink sub-frame
• Uplink-to-downlink ratio adjusted according to traffic demand
• Sub-frame further divided into mini-slots to send data bursts
®
Background – Mesh Mode Frame Structure
• Each frame divided into control and data sub-frame
• No uplink or downlink sub-frame distinction
• Control sub-frame length depends on length of the mesh
®
Background – WiMAX Handover Support
• Standard Handover
– Defined only for PMP mode in IEEE 802.16e-2005
– Each Mobile Station (MS) maintains an up-to-date CINR for
target BSs
– Either BS or MS can initiate the handover procedure
– MS decides the target BS
• Two optional fast handover methods
– Macro-Diversity Handover (Soft Handover)
– Fast Base Station Switching (Hard Handover)
®
Background – Relevant Work
• WiMAX network architecture
–
–
–
–
Coverage: IEEE 802.16j workgroup (Relay Station Infrastructure)
Link-level performance: [Hartzog 2006]
Last mile Connectivity: [Bennett 2006], [Wongthavarawat 2003]
Mobile Ad Hoc Networks (MANET): [Sherman 2006], [Lebrun 2006]
• Scheduling schemes
– PMP Mode: [Zhe 2007], [Jayaparvathy 2005], [Lera 2007], [Lin 2008]
– Mesh Mode
• Centralized: [Wei 2005], [Chen 2006], [Qing 2006]
• Distributed: [Cao 2007]
®
Objective
• Challenge – WiMAX requires routing and scheduling
packets for rapidly changing network
topology due to fast moving vehicles
• Goals:
– Develop Network Architecture
– Routing and Scheduling solution
– Throughput performance analysis
®
Network Model
Tactical Network
Gateway
Core Command
Network
MBS
MSS
MBS
MSS
MSS
MSS
Tactical Network
MBS
MSS
MSS
®
MSS
MSS
MBS: Mesh BS
MSS: Mesh SS
MS
MBS
Network Model Components
• Routing
– Mobility-Aware Intra-Gateway Routing (MAIGR)
– Ad Hoc Routing Protocols and Mobile IP
• Scheduling
– PMP mode: between MS and MBS/MSS
– Mesh mode: among MSS and MBS
• Handover
– Scheduling options migrate from current BS to target BS
®
BS Protocol Architecture
Mesh BS
Mobile IP
Home/foreign agents
IP
– Dual radios (PMP mode, Mesh mode)
– Routing: MAIGR
MAIGR
PMP
LINK + PHY
• Base stations (MBS and MSS)
support:
Mesh
LINK + PHY
• MBS also supports:
– Routing: IP and Mobile IP
Mesh SS
MAIGR
PMP
LINK + PHY
Mesh
LINK + PHY
®
MS Protocol Architecture
MS
Application
• Mobile Station (MS) supports:
Transport
(TCP, UDP)
– Single radio (PMP mode)
– Routing: IP
– Transport layer protocols
– Application specific protocols
IP
PMP
LINK + PHY
®
Network Operation
I.
1.
2.
3.
4.
5.
All MBSs use existing ad-hoc solutions to reach core network
All MSSs find closest path to MBS using MAIGR’s mesh topology discovery phase
All BSs (MSS and MBS) come up with initial mesh schedule using centralized mesh scheduler
All BSs maintain Mesh Link Capacity for PMP scheduler using the initially derived mesh schedule
All BSs use PMP scheduler to communicate with MS
II.
6.
7.
Mobile Station Setup
MS sets up routes to transmit/receive traffic to/from MBS using MAIGR
MS uses PMP scheduler to communicate with MSS/MBS
III.
8.
9.
10.
Base Station Setup
Operational Phase
Depending on PMP traffic load at each BS, Mesh scheduler at each BS adapts its schedule
PMP scheduling options for a MS migrate to the target BS during the handover procedure
Mobile IP used by MBSs to assign care-of address to MS that switches routing zones
®
Base Station Route Setup
I.
1.
2.
3.
4.
5.
All MBSs use existing ad-hoc solutions to reach core network
All MSSs find closest path to MBS using MAIGR’s mesh topology discovery phase
All BSs (MSS and MBS) come up with initial mesh schedule using centralized mesh scheduler
All BSs maintain Mesh Link Capacity for PMP scheduler using the initially derived mesh schedule
All BSs use PMP scheduler to communicate with MS
II.
6.
7.
Mobile Station Setup
MS sets up routes to transmit/receive traffic to/from MBS using MAIGR
MS uses PMP scheduler to communicate with MSS/MBS
III.
8.
9.
10.
Base Station Setup
Operational Phase
Depending on PMP traffic load at each BS, Mesh scheduler at each BS adapts its schedule
PMP scheduling options for a MS migrate to the target BS during the handover procedure
Mobile IP used by MBSs to assign care-of address to MS that switches routing zones
®
Base Station Route Setup
Core
Network
MSS: Mesh SS
MBS: Mesh BS
MS: Mobile Station
Traditional Ad Hoc
Routing Solutions
MSS
MSS
MBS
MSS
MSH_NCFG:
Entry
Zone 1
MSS
MSS
MSS
MBS
MSH_NCFG:
Entry
Zone 2
®
MSS
MSS
Base Station Scheduler Setup
I.
1.
2.
3.
4.
5.
All MBSs use existing ad-hoc solutions to reach core network
All MSSs find closest path to MBS using MAIGR’s mesh topology discovery phase
All BSs (MSS and MBS) come up with initial mesh schedule using centralized mesh scheduler
All BSs maintain Mesh Link Capacity for PMP scheduler using the initially derived mesh schedule
All BSs use PMP scheduler to communicate with MS
II.
6.
7.
Mobile Station Setup
MS sets up routes to transmit/receive traffic to/from MBS using MAIGR
MS uses PMP scheduler to communicate with MSS/MBS
III.
8.
9.
10.
Base Station Setup
Operational Phase
Depending on PMP traffic load at each BS, Mesh scheduler at each BS adapts its schedule
PMP scheduling options for a MS migrate to the target BS during the handover procedure
Mobile IP used by MBSs to assign care-of address to MS that switches routing zones
®
Base Station Scheduler Setup
MSS: Mesh SS
MBS: Mesh BS
MS: Mobile Station
Core
Network
MSS
x
2x
MSS
x
x
MSH_CSCH:
Request
MSS
3x
MBS
3x
x
x
MSH_CSCH:
Grant
®
MSS
2x
MSS
x
x
MSS
x
MSH_CSCH:
Request
Centralized Mesh Scheduling Solution
• Interference-aware solution achieving near-optimal
throughput [Wei 2005, VTC]
– Procedure:
• Transmission occurs in order of highest transmission demand
• Non-interfering links transmit simultaneously
– Proposed changes:
• QoS considered
– Constraints:
• Unidirectional traffic considered

MSS
x



2x
3x
3x
MSS
Rx
MSS
Tx
®
MBS
Tx
Carrier Sense Range: 1
MSS
Rx


2x
x
MSS
MSS
Mobile Station Setup
I.
1.
2.
3.
4.
5.
All MBSs use existing ad-hoc solutions to reach core network
All MSSs find closest path to MBS using MAIGR’s mesh topology discovery phase
All BSs (MSS and MBS) come up with initial mesh schedule using centralized mesh scheduler
All BSs maintain Mesh Link Capacity for PMP scheduler using the initially derived mesh schedule
All BSs use PMP scheduler to communicate with MS
II.
6.
7.
Mobile Station Setup
MS sets up routes to transmit/receive traffic to/from MBS using MAIGR
MS uses PMP scheduler to communicate with MSS/MBS
III.
8.
9.
10.
Base Station Setup
Operational Phase
Depending on PMP traffic load at each BS, Mesh scheduler at each BS adapts its schedule
PMP scheduling options for a MS migrate to the target BS during the handover procedure
Mobile IP used by MBSs to assign care-of address to MS that switches routing zones
®
Mobile Station Setup
MSS: Mesh SS
MBS: Mesh BS
MS: Mobile Station
Core
Network
MSS
x
x
2x
MSS
x
MSS
3x
MBS
x
DHCP
Service
REQ
Flow: REP
REQ
MSS
x
DHCP
REP
®
3x
2x
MSS
x
x
MSS
x
Operational Phase Scheduler Interaction
I.
1.
2.
3.
4.
5.
All MBSs use existing ad-hoc solutions to reach core network
All MSSs find closest path to MBS using MAIGR’s mesh topology discovery phase
All BSs (MSS and MBS) come up with initial mesh schedule using centralized mesh scheduler
All BSs maintain Mesh Link Capacity for PMP scheduler using the initially derived mesh schedule
All BSs use PMP scheduler to communicate with MS
II.
6.
7.
Mobile Station Setup
MS sets up routes to transmit/receive traffic to/from MBS using MAIGR
MS uses PMP scheduler to communicate with MSS/MBS
III.
8.
9.
10.
Base Station Setup
Operational Phase
Depending on PMP traffic load at each BS, Mesh scheduler at each BS adapts its schedule
PMP scheduling options for a MS migrate to the target BS during the handover procedure
Mobile IP used by MBSs to assign care-of address to MS that switches routing zones
®
PMP Mode Scheduler
UGS
ertPS
rtPS
nrtPS
BE
New Flow Requests
No
Pending Connection
Queue Empty?
Pending Connection
Queue
Yes
Yes
Queue Size
>
Threshold?
Yes
No
Enough Free Slots
Available?
Mesh link limitation?
Yes
Distributed
Adaptation
No
Active Connection
Queue
Reject Flow
PMP Scheduler
®
Centralized
Scheduling
Mesh Scheduler
Mesh Scheduler Distributed Adaptation
(General Case)
MSS
x
x
MSS
0
2x
MSS
x
0
MSS
3x
MBS
3x
x
2x
MSS
2x
MSS
x
MSS
2x
MSS
x
3x
MBS
3x
MSS
x
2x
MSS
x
– Up to x slots can be borrowed in general
®
x
x
MSS
x
x
MSS
x
Mesh Scheduler Distributed Adaptation
(Upper Bound)
MSS
x
x
MSS
2x
MSS
x
0
0
MSS
3x
MBS
3x
x
3x
MSS
3x
MSS
0
MSS
2x
x
3x
MBS
3x
MSS
x
MSS
x
MSS
x
2x
MSS
x
x
MSS
x
• Case I:
– Borrowing occurs from MSS away from MBS
– 2x slots can be borrowed as an upper bound
®
x
Mesh Scheduler Distributed Adaptation
(Upper Bound)
MSS
x
x
MSS
2x
MSS
x
1.5x
1.5x
MSS
MSS
3x
MBS
3x
x
1.5x
0
MSS
x
MSS
2x
x
3x
MBS
3x
MSS
x
MSS
x
x
2x
MSS
x
x
x
• Case II:
– Borrowing occurs from MSS closer to MBS
– x/2 slots can be borrowed as upper bound
®
MSS
MSS
x
Operational Phase Handover Scenario
I.
1.
2.
3.
4.
5.
All MBSs use existing ad-hoc solutions to reach core network
All MSSs find closest path to MBS using MAIGR’s mesh topology discovery phase
All BSs (MSS and MBS) come up with initial mesh schedule using centralized mesh scheduler
All BSs maintain Mesh Link Capacity for PMP scheduler using the initially derived mesh schedule
All BSs use PMP scheduler to communicate with MS
II.
6.
7.
Mobile Station Setup
MS sets up routes to transmit/receive traffic to/from MBS using MAIGR
MS uses PMP scheduler to communicate with MSS/MBS
III.
8.
9.
10.
Base Station Setup
Operational Phase
Depending on PMP traffic load at each BS, Mesh scheduler at each BS adapts its schedule
PMP scheduling options for a MS migrate to the target BS during the handover procedure
Mobile IP used by MBSs to assign care-of address to MS that switches routing zones
®
Operation Phase Handover Scenario
Tactical
Network
Gateway
MSS: Mesh SS
MBS: Mesh BS
MS: Mobile Station
Mobile IP Msg
MSS
MSS
MBS
MSS
MSS
HO_IND
Msg
MSS
MSS
MBS
Care-of
Address
MS
Zone 1
Zone 2
®
MSS
MSS
Analytical Model
• Throughput Comparison
a) centralized only mesh scheduling algorithm
b) centralized with distributed adaptation algorithm
• Topology considered
– Symmetric Chain Topology
– Single Intersection Topology
• Throughput bounds derived for
– Dense Network
– Sparse Network
®
Percentage Increase in Network Throughput per
Routing Zone (Dense Network)
MSS
3’
Link 3’
x
x – q3’
Link 2’
MSS
2’
2x
x – q2’
MSS
1’
x – q1’
Link 1’
3x
Link 1
MBS
3x
MSS
1
x – q1
Link 2
2x
MSS
2
Link 3
x
x – q2
Parameter
Description
qi
Number of unused PMP data slots at base station i
z
Total number of data slots per Mesh Frame
n+n’
Total number of MSS in routing zone
k
Borrowing MSS’s # of hops from MBS
Case I:
Case II:
®
MSS
3
x – q3
Percentage Increase in Network Throughput per
Routing Zone (Sparse Network)
MSS
3’
Link 3’
x
0
Link 2’
MSS
2’
2x
x-q2’
MSS
1’
0
Link 1’
3x
Link 1
MBS
3x
MSS
1
0
Link 2
2x
MSS
2
Link 3
x
0
Parameter
Description
qi
Number of unused PMP data slots at base station i
x
PMP data slots per frame at Lender
k
Borrowing MSS’s # of hops from MBS
Case I:
Case II:
®
MSS
3
0
Simulation Studies
• Network Simulator ns-2 used
– Based on NIST IEEE 802.16 module (version pre-release2)
• Supports PMP mode, standard handover
• Scheduler functionality added
• Extension made to support:
– TDD mesh links between base stations (emulated with wired links)
– Dual radios at each base station
– Chain topology presented
– Carrier sensing range equal to communication range assumed
– Analytical Model verified using simulation results
®
Mesh Mode Simulation Parameters
Parameter
Value
Channel Bandwidth
10 MHz
Modulation Scheme
OFDM_64QAM_3_4
Bits/Symbol
856
Symbol/Slot
1
Frame Duration
10 ms
Slots/Frame
221
Control Sub-Frame
7 * MSH_CTRL_LEN = 49
Data Sub-Frame
221 – (7 * MSH_CTRL_LEN) = 172
Pending Queue Threshold
0
Communication Range
1
Carrier Sensing Range
1
Maximum Routing Zone Rate
18.91 Mbps (14.72 Mbps for Data)
®
Simulation Model – Dense Network
Internet Sink
Tactical Network
Gateway
MSS
0
28
MSS
1
56
MSS
2
28-12
28-4
28-12
28-12
MS
MS
MS
84
MBS
MS
84
MSS
3
56
MSS
4
28
MSS
5
28-12
28-12
28-12
MS
MS
MS
MS
MS
2 * 0.64 Mbps UGS
Flows per MS
(16 Data Slots)
.
.
®
Simulation Results – Dense Network (Stationary)
9
8
7
6
5
4
3
2
1
0
Throughput (Mbps)
Pending Flows
1
2
3
4
9
8
7
6
5
4
3
2
1
0
Throughput(Mbps)
Pending Flows
1
5
2
3
4
5
Group Size (Number of MS)
Group Size (Number of MS)
Centralized Scheduling Only
Distributed Adaptation Scheduling
Centralized
Distributed
Throughput (Mbps)
8.27 (13 flows)
8.95 (14 flows)
Pending Flows
0/1/3/5/7
0/0/2/4/6
®
Simulation Model – Sparse Network
Internet Sink
Tactical Network
Gateway
MSS
0
28-4
28
MSS
1
56
0
MSS
2
0
84
MBS
84
MSS
3
0
56
MSS
4
0
28
MSS
5
0
MS
MS
MS
1 * 0.64 Mbps UGS
Flow per MS
(8 Data Slots)
MS
MS
®
Simulation Model – Sparse Network
Internet Sink
Tactical Network
Gateway
MSS
0
0
28
MSS
1
56
28-4
MSS
2
0
84
MBS
84
MSS
3
0
56
MSS
4
0
28
MSS
5
0
MS
MS
MS
1 * 0.64 Mbps UGS
Flow per MS
(8 Data Slots)
.
.
.
®
Simulation Results – Sparse Network (Stationary)
7
Throughput (Mbps)
6
5
4
Centralized Only
Distributed Adaptation
3
2
1
0
5 MSs
10 MSs
Centralized
Throughput
(Mbps)
Distributed
Throughput
(Mbps)
5 MSs
1.92 (3 flows)
3.19 (5 flows)
10 MSs
1.92 (3 flows)
6.38 (10 flows) 232
®
% Increase
66
Conclusions
• The network architecture simplifies scheduling recomputation by only involving base-stations as opposed
to a complete ad-hoc solution
• Distributed adaptation does not increase the
throughput significantly under dense network
conditions (~8.2 %) due to the inability of neighboring
BSs to lend slots
• Distributed adaptation increases throughput
significantly under sparse network conditions (~ 232 %)
®
Future Work
• Different topologies such as grid topology need to be
studied
• Borrowing from 1-hop neighbor only is not optimal and
studies needs to be expanded to determine the
performance improvement if borrowing from multi-hop
neighbors is allowed
®
Thank You
®
Backup - Routing Partitions
®
Mobility-Aware Intra-Gateway Routing
• Mesh Topology discovery
– Each Mesh BS sends a flooding message at periodic intervals
– Each Mesh SS records the next hop towards the closest Mesh BS
• Packet Forwarding from Mesh BS to MS
– At serving BS, the next hop is the connection identifier (CID) of MS’s data
connection established during network entry or handover
– At non-serving BS, the next hop is a mesh link CID which is obtained in one
of two ways
• When receiving a packet from neighboring BS forwarded by an unknown MS,
record the neighboring BS as next hop to the unknown MS
• When notified of a handover of currently associated MS, record target BS as
next hop to MS
• Packet Forwarding from MS to Mesh BS
– At MS, the next hop is always the CID of currently serving BS’s data connection
– At subsequent Mesh SS’s, the next hop is the mesh link CID towards the closest
Mesh BS obtained during Mesh Topology discovery phase
®
Scheduling Solution
• PMP Mode Scheduling
– Order determined according to service classes
(UGS, ertPS, rtPS, nrtPS, BE)
– Same service classes are serviced in FIFO order
• Mesh Mode Scheduling
– Centralized interference-aware solution
• Transmission occurs in order of highest transmission demand [Wei]
– Distributed Adaptation
• Need-based borrowing
®
Mesh Mode Scheduler
• Initial schedule using centralized algorithm
– Upon network deployment
– Every time BS is added to the mesh
– Uses average traffic load information if available, else
assumes uniform traffic distribution
• Distributed adaptation copes with changes in traffic
loads
– Whenever pending queue length exceeds predefined
threshold
– Slots borrowed from immediate (1-hop) neighbors
– Three-way handshake technique used
®
Distributed Adaptation
®
Centralized Algorithm
®