Senior Design Project

OPNET Modeler &

Short-Range Wireless Routing

Erin Butler & Emmy Lai

Advisor: Professor H. C. Chang
 Grant
Funded by a grant from CRA-W, a
subset of the National Science
Foundation,
 Objective of Project
Research Existing Wireless Routing
Algorithms
Design and Implement these Algorithms
Explore OPNET Modeler
 A network technology development
environment
Simulate a Variety of Networks,
Observing Performance Metrics
 OPNET Modeler
Three Main Domains
 Network
 Node

 Process
 Network Domain
Subnetworks
 Encapsulates other network objects
Communication Nodes
 Model network objects with definable internal
structure
Communication Links
 Mechanism to transport information between
nodes
Fixed, Mobile, Satellite Variations
 Node Domain
Node Model defines the internal structure of the
communication nodes
Node Modules
 Processor: primary building block, sends/receives packets, overall
processing
 Queue: extended functionality of processor, array of internal
resources, subqueues
 Transmitter: interface between internal packet streams & external
communication links
 Receiver: interface between external communication links &
internal packet streams
 Connections:
 Packet Stream: support flow of data between modules
 Statistic Wires: support transmission of numerical state information
 Logical Associations: bind two modules, allowing them to perform
function together
 Process Domain
The Process Model defines the behavior of
the processor and queue modules
Interrupt Driven Execution:
 Caused by the invocation of an event
 Alternating Blocked and Active states
Dynamic Processes:
 Processes invoked by other processes
 Share Memory Architecture
 Parent-Child establish pair establish block of
memory for two-way communication
Process Domain (cont.)
Dynamic Library operations
State Transition Diagrams:
 State: a mode the process can enter, state information
 Enter & Exit Executives
 Unforced state: wait for interrupt
 Forced state: continual execution of state
 Transition: possible movements of a process from state to
state
 Source & destination state, condition & executive expression
Input & Output Streams
 Data Analysis
Analysis Tool
 Graphs
 Statistics

 Output Scalar Files: data collected in

vector files during a simulation run,
combine results from multiple simulations
 OPNET Editors
Project Editor Interface Control
Node Editor Information Editor
Process Model Editor Probability Density
Link Model Function Editor
Path Editor
Probe Editor
Packet Format Editor
Simulation Tool
Antenna Pattern Editor
Analysis Tool
Filter Editor
Project Editor
Main staging area for
creating a network
simulation
Create a network model
using models from the
standard library
Collect statistics about
the network
Run the simulation
View Results
 Node Editor
Define the behavior,
which is defined by
modules, of each
network object
A network object is
made up of multiple
modules defining its
behavior
Each module models
some internal aspect of
the node behavior (ex:
data creation/storage)
Process Model Editor
Create process models
which control the underlying
functionality of the node
models created in node
editor
Represented by finite state
machines
Created with icons that
represent states and lines
that represent transitions
between states
Operations performed in
each state or for a transition
are described in embedded c
or c++ code blocks
 Link Model
Create new types of
link objects
Each new type of
link can have
different attribute
interfaces and
representation
Path Editor
Create new path
objects which define
a traffic route
Any protocol model
that uses logical
connections or
virtual circuits
(MPLS, ATM, Frame
Relay…etc) can use
paths to route traffic
 Packet Format Editor
Defines the internal
structure of a packet as
a set of fields
A packet format
contains one or more
fields, represented in
the editor as colored
rectangular boxes
Size of the box is
proportional to the
number of bits specified
as the field’s size
Antenna Pattern Editor
Models the direction
dependent gain
properties of
antennas
Gain patterns are
used to determine
gain values, given
knowledge of the
relative positions of
nodes
Interface Control Information Editor

Defines the internal

structure of ICIs
(Interface Control
Information) which
are used to
formalize interrupt-
based inter-process
communication
Probability Density Function Editor

Describes the spread of

probability over a range
of possible outcomes
Models the likelihoods
associated with packet
interarrival times
Models the probability
of transmission errors
 Probe Editor
Specifies the statistic to be
collected during simulation
Sets additional
characteristics of each
probe
Different probes collect
different statistics including
global statistics, link
statistics, node statistics,
attribute statistics, and
several types of animation
statistics.
Simulation Tool
Specifies additional
simulation constraints
Simulation sequences
are represented by
simulation icons which
contain a set of
attributes that control
that simulation’s run-
time characteristics
 Analysis Tool
Creates scalar
graphs and
parametric studies
Defines templates to
which statistical data
is applied
Creates analysis
configurations
Filter Editor
Creates additional
filters on top of the
ones that are
already provided by
OPNET
Built by combining
existing models with
each other
OPNET Overview Layout
 Carrier Sense Multiple
Access Protocol (CSMA)
Protocols in which stations listens for a
carrier or transmission and act
accordingly
Three versions of CSMA
 1 persistent
 non persistent

 p persistent
 1 – persistent CSMA
When a station has data to send, it first listens to the
channel to see if anyone else is transmitting at that
moment
If the channel is busy, the station waits until it
becomes idle
 When the station detects an idle channel, it transmits a
frame
If a collision occurs, the station waits a random
amount of time and starts all over again
Transmits with a probability of 1 whenever it finds the
channel idle
 Non-persistent CSMA
Attempts to be less greedy than 1-persistent
Before sending, a station senses the channel
 If no one else is sending, the station begins doing
so itself
 If the channel is already in use, it waits a random
period of time and then repeats the algorithm
Leads to a better channel utilization and
longer delays than 1-persistent
 p-persistent CSMA
Applies to slotted channels
When a station becomes ready to send, it senses the channel
If it is idle, it transmits with a probability p
A probability of q=1-p is deferred until the next slot
 If that slot is also idle, it either transmits or defers again, with the
probabilities p and q
 Process repeats until either the frame has been transmitted or
another station has begun transmitting
If another station has begun transmitting, it acts as if there had
been a collision (ie, it waits a random time and starts again)
If the station initially senses the channel busy, it waits until the
next slot and applies the above algorithm
 OPNET & CSMA
Basic Components
 CSMA project network
 Transmitter Node Model – sends packets

 Receiver Node Model – performs network

monitoring
CSMA Process Model
Verifies the channel
is free before
transmitting
If channel is not
free, enters the
wt_free state until a
“channel goes free”
interrupt is received
 CSMA
At the node level,
the statistic wire is
triggered when the
busy statistic
changes to 0.0.
The trigger is
activated by
enabling the wire’s
falling edge trigger
attribute
CSMA Scenario
CSMA network
model
20 transmitter nodes
Uses transmitter
nodes designed
previously in node
editor
Network is ready for
simulation
 CSMA Simulation

Change attributes to run simulation

 Duration time
 Seed
 Value per statistics
In this case, for the CSMA, seed is changed to 11
CSMA Simulation Results

Graph of channel
throughput S vs.
channel traffic G
Achieves maximum
throughput at about
0.5
Comparing Protocols
(CSMA vs. Aloha)
Introduction to Dynamic
Wireless Networks
These networks consist of mobile hosts that
communicate to one another over wireless
links without any static network interaction
 Due to the limited range of wireless transceivers,
mobile hosts’ communication links only
implemented in their geographic reason
Need for a complex network to handle and
maintain the forwarding of data packets
 Previous Work &
Routing Standards
Set of Conventional Standards
 Simplicity
 Loop-free
 Low Convergence time
 Low computation & transmission overhead
Problems in terms of Dynamic Networks
 Frequent broadcast cause high overhead due to
changing topology
 Heavy computational burden
 Limited bandwidth in wireless networks
 Temporally Ordered
Routing Algorithm (TORA)
A network routing protocol which has been designed
for use in Mobile Wireless Networks
Envisioned as a collection of routers which are free to
move about arbitrarily
Routers are equipped with wireless
receivers/transmitters
Status of communication links between routers is a
function of their positions, transmission power levels,
antenna patterns, cochannel interference levels….etc
Designed to minimize reaction to topological changes
Properties that makes TORA well suited for
use in the mobile wireless networking
environment

Executes distributedly
Provides loop-free routes
Provides multiple routes (to alleviate
congestion)
Establishes routes quickly (so as to be used
before the topology changes)
Minimize algorithmic
reactions/communication overhead (to
conserve available BW and increase
adaptability)
 Methods to minimize overhead &
maximize routing efficiency

Establish routes only when necessary by

constructing a direct acyclic graph rooted at
the destination using a query/reply process
React to link failure only when necessary (ex:
when a node loses its last downstream link)
Scope of failure reactions minimized (ie: the
number of nodes that must participate)
No reaction to link activation
TORA’s Link Reversal Algorithm

When a node has no downstream links, it reverses

the direction of one or more links
Links are directed based on a metric, maintained by
nodes in the network, that can conceptually be
viewed as a height
Goals:
 Discover routes on demand
 Provide multiple routes to a destination
 Establish routes quickly
 Minimize overhead
 Make shortest path routing of second importance
TORA Basic Functions
Creating Routes – Query/Reply on demand
 Query packet (QRY) is flooded through network
 Update packet (UPD) propagates back if routes
exist
Maintaining Routes – Base on “link-reversal”
algorithm
 UPD packets reorient the route structure
Erasing Routes –
 Clear packet (CLR) is flooded through network to
erase invalid routes
TORA FSM
Create Route State Diagram
Maintain Route State Diagram
Erase Route State Diagram
 TORA Application
A separate copy of TORA is run at each node
Node adjust height at a discovery of an
invalid route
Node without neighbor of finite height with
respect to destination, attempts to find new
route
Sends CLR packet upon network partition
Exchange of UPD packets
TORA Application cont…
Complete path can be found using
distance table
Each router maintains its own
information with respect to its neighbor
 Node Height
Each height table for a node contains the following
information
 Hi = (i, oid, ri, i, i)
 I = time tag
 oid = originator ID
 ri = bit used to divide each reference level into 2 sublevels
 I = integer used to order nodes
 I = unique identifier of node
Height of each node (except for the destination) is
initially set to NULL: Hi = ( -, -, -, -, i)
 Route Creation
(-,-,-,-,A)
(-,-,-,-,B)
QRY
(-,-,-,-,C)

(-,-,-,-,E)
(-,-,-,-,D)
(-,-,-,-,G) (-,-,-,-,F)

(-,-,-,-,H) DEST
 Route Creation
(-,-,-,-,A) QRY
(-,-,-,-,B)

(-,-,-,-,C)

(-,-,-,-,E)
QRY (-,-,-,-,D)
(-,-,-,-,G) (0,0,0,0,F)

(-,-,-,-,H) DEST
 Route Creation
(-,-,-,-,A)
(-,-,-,-,B)

(-,-,-,-,C)

(-,-,-,-,E)
(-,-,-,-,D)
(-,-,-,-,G) (0,0,0,0,F)

(0,0,0,1,H) DEST
 Route Creation
(-,-,-,-,A)
(-,-,-,-,B)

(-,-,-,-,C)

(0,0,0,1,E)
(0,0,0,2,D)
(0,0,0,2,G) (0,0,0,0,F)

(0,0,0,1,H) DEST
 Route Creation
(0,0,0,3,A)
(0,0,0,2,B)

(0,0,0,3,C)

(0,0,0,1,E)
(0,0,0,2,D)
(0,0,0,2,G) (0,0,0,0,F)

(0,0,0,1,H) DEST
Route Creation Complete
(0,0,0,3,A)
(0,0,0,2,B)

(0,0,0,3,C)

(0,0,0,1,E)
(0,0,0,2,D)
(0,0,0,2,G) (0,0,0,0,F)

(0,0,0,1,H) DEST
Cluster-Based Algorithm for
Dynamic Network Routing
Main objective: To
replace individual nodes
(mobile hosts) with a
cluster
 Lower overhead during
topology changes
Basic algorithm
 Divide the graph into a
number of overlapping
clusters
 Change in topology =
change in cluster
membership
 Cluster Definitions
Graphs: an organization of nodes or mobile hosts
Node: list of neighbors, list of clusters it belongs to, list of
boundary nodes
Boundary nodes: connection from one cluster to another
Clusters:
 Size of cluster C, S(C) = number of nodes
 Edges: edges between the nodes that are members of the
clusters
 Cluster-connected graph: union of clusters covers the whole
graph, a path from exists from each node to every other in
the graph
 Redundant cluster, if removed, does not affect the
connection between a pair
Four Main Topology Changes

H5 turns ON

H6 turns OFF

HA connects to HB

HA disconnects from
HB
Procedures & Data Structures

Two main Procedures: Switch ON,

Switch OFF
 Each execute a similar algorithm of cluster
manipulation
 CreateCluster
 FindEssential
 FindRedundant
Data Structures:
 Clus_List: list of clusters
 Bound_List: list of boundary nodes
Performance Metrics
Time Complexity
 Number of steps for a
network to form after
topology change
Communication Complexity
 Number of messages
required to form new
network
Routing Overhead
 Ratio of path length
between source and
destination
 Dynamic Cluster
Implementation
Bottom-Up approach
 Process Model – defines behavior of
nodes, state diagram and transitions
 Node Model – contains objects (receiver,
transmitter, processor) consisting of
process models
 Network Model – overall topology
 Process Models
Decision “Tree”: Switch ON or Switch OFF
Switch ON State Diagram
Switch OFF State Diagram
 Node Model
Wireless LAN Model: MAC sublayer, Physical Layers
Network Model
 C Language Implementation:
Main Functions & Data Structures
Three Basic Functions
 CreateCluster
 FindEssential
 FindRedundant

Globally Declared Data Structures

 NeighborList: list of all neighbors of each
node
 Clus_List: contains list of clusters
C Language Implementation:
CreateCluster
Input Parameter: node ID
Using the the node ID and its
NeighborList, determines all existing
clusters
allList[0]: 1 0
allList[1]: 1 2 0
allList[2]: 1 2 0
allList[3]: 1 0 0
allList[4]: 1 0 0
allList[5]: 1 3 0
allList[6]: 2 0
allList[7]: 2 1 0
allList[8]: 2 1 0
allList[9]: 2 3 0
allList[10]: 2 3 0
allList[11]: 2 0 0
allList[12]: 2 0 0
allList[13]: 2 4 0
allList[14]: 4 0
allList[15]: 4 0 0
allList[16]: 4 0 0
allList[17]: 4 2 0
allList[18]: 4 2 0
allList[19]: 4 3 0
C Language Implementation:
FindEssential
Input Parameter: node ID
Ensures that no one node, except the
node ID, exists in more than one
“essential” class
Design: series of reiterative looping and
comparisons
 If all nodes are found in another “essential”
cluster, cluster is marked “non-essential”
C Language Implementation:
FindRedundant
Input Parameter: node ID
Uses “essential” list
Determines whether or not the removal
of a cluster affects the cluster-
connectivity between any pair of nodes
Output is the final Clus_List for the node
ID
C Language Implementation:
Simulation (initial)
D y n a mi c C l u sters Simulation
C A S E 0 : I n i tial Topology and Clusters, node 0
= = = = == = = = = = =====================================
a l l L is t [ 0 ] : 1 0
a l l L is t [ 1 ] : 1 2 0
a l l L is t [ 2 ] : 1 2 0
a l l L is t [ 3 ] : 1 0 0
a l l L is t [ 4 ] : 1 0 0
a l l L is t [ 5 ] : 1 3 0
a l l L is t [ 6 ] : 2 0
a l l L is t [ 7 ] : 2 1 0
a l l L is t [ 8 ] : 2 1 0
a l l L is t [ 9 ] : 2 3 0
a l l L is t [ 1 0 ] : 2 3 0
a l l L is t [ 1 1 ] : 2 0 0
a l l L is t [ 1 2 ] : 2 0 0
a l l L is t [ 1 3 ] : 2 4 0
a l l L is t [ 1 4 ] : 4 0
a l l L is t [ 1 5 ] : 4 0 0
a l l L is t [ 1 6 ] : 4 0 0
a l l L is t [ 1 7 ] : 4 2 0
a l l L is t [ 1 8 ] : 4 2 0
a l l L is t [ 1 9 ] : 4 3 0
E s s e nt i a l : 2
E s s e nt i a l : 1
E s s e nt i a l : 0
= = = = == = = = = = ====
E s s e nt i a l : 4
E s s e nt i a l : 3
E s s e nt i a l : 0
= = = = == = = = = = ====
A f t e rR e d u n d ant: 2
A f t e rR e d u n d ant: 1
A f t e rR e d u n d ant: 0
= = = = == = = = = = ====
A f t e rR e d u n d ant: 4
A f t e rR e d u n d ant: 3
A f t e rR e d u n d ant: 0
= = = = == = = = = = ====
C Language Implementation:
Simulation (H5 ON, nodeID=0)
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
C A S E 5 : N o d e 5 t u r n s o n , n o d e 0
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
a l l L i s t [ 0 ] : 1 0
a l l L i s t [ 1 ] : 1 2 0
a l l L i s t [ 2 ] : 1 2 0
a l l L i s t [ 3 ] : 1 0 0
a l l L i s t [ 4 ] : 1 0 0
a l l L i s t [ 5 ] : 1 3 0
a l l L i s t [ 6 ] : 2 0
a l l L i s t [ 7 ] : 2 1 0
a l l L i s t [ 8 ] : 2 1 0
a l l L i s t [ 9 ] : 2 3 0
a l l L i s t [ 1 0 ] : 2 3 0
a l l L i s t [ 1 1 ] : 2 0 0
a l l L i s t [ 1 2 ] : 2 0 0
a l l L i s t [ 1 3 ] : 2 4 0
a l l L i s t [ 1 4 ] : 4 0
a l l L i s t [ 1 5 ] : 4 0 0
a l l L i s t [ 1 6 ] : 4 0 0
a l l L i s t [ 1 7 ] : 4 2 0
a l l L i s t [ 1 8 ] : 4 2 0
a l l L i s t [ 1 9 ] : 4 3 0
a l l L i s t [ 2 0 ] : 4 3 0
a l l L i s t [ 2 1 ] : 4 5 0
E s s e n t i a l : 2
E s s e n t i a l : 1
E s s e n t i a l : 0
= = = = = = = = = = = = = = =
E s s e n t i a l : 4
E s s e n t i a l : 3
E s s e n t i a l : 0
= = = = = = = = = = = = = = =
E s s e n t i a l : 4
E s s e n t i a l : 5
E s s e n t i a l : 0
= = = = = = = = = = = = = = =
A f t e r R e d u n d a n t : 2
A f t e r R e d u n d a n t : 1
A f t e r R e d u n d a n t : 0
= = = = = = = = = = = = = = =
A f t e r R e d u n d a n t : 4
A f t e r R e d u n d a n t : 3
A f t e r R e d u n d a n t : 0
= = = = = = = = = = = = = = =
A f t e r R e d u n d a n t : 4
A f t e r R e d u n d a n t : 5
A f t e r R e d u n d a n t : 0
= = = = = = = = = = = = = = =
C Language Implementation:
Simulation (H2 OFF, node 5)
= = = = == = == = = ==========================
C A S E 7 : N o d e 2 turns off, node 5
= = = = == = == = = ==========================
a l l L is t [0 ] : 4 5
a l l L is t [1 ] : 4 0 5
a l l L is t [2 ] : 4 0 5
a l l L is t [3 ] : 4 3 5
a l l L is t [4 ] : 4 3 5
a l l L is t [5 ] : 4 5 5
a l l L is t [6 ] : 3 5
a l l L is t [7 ] : 3 1 5
a l l L is t [8 ] : 3 1 5
a l l L is t [9 ] : 3 4 5
a l l L is t [1 0 ] : 3 4 5
a l l L is t [1 1 ] : 3 5 5
E s s e nt i al : 4
E s s e nt i al : 0
E s s e nt i al : 5
= = = = == = == = = ====
E s s e nt i al : 3
E s s e nt i al : 1
E s s e nt i al : 5
= = = = == = == = = ====
A f t e rR e du n d ant: 4
A f t e rR e du n d ant: 0
A f t e rR e du n d ant: 5
= = = = == = == = = ====
A f t e rR e du n d ant: 3
A f t e rR e du n d ant: 1
A f t e rR e du n d ant: 5
= = = = == = == = = ====
C Language Implementation:
Simulation (H3 disconnect H4,
node 0)
==========================================
CASE 8: Disconnection between node 3 and n
==========================================
allList[0]: 1 0
allList[1]: 1 0 0
allList[2]: 1 0 0
allList[3]: 1 3 0
allList[4]: 4 0
allList[5]: 4 0 0
allList[6]: 4 0 0
allList[7]: 4 5 0
Essential: 1
Essential: 3
Essential: 0
===============
Essential: 4
Essential: 5
Essential: 0
===============
AfterRedundant: 1
AfterRedundant: 3
AfterRedundant: 0
===============
AfterRedundant: 4
AfterRedundant: 5
AfterRedundant: 0
===============
AND NOW…GRADUATION!!