Transcript Analysis and Simulation of Optical Networks

Analysis and simulation of
Optical Networks
Xin Liu
Outline
• Analytic Approach
Probability: Expectation values, Variance
Network Global Expectation Model
Stochastic Process: Markov chain
Packet Delay in OCS networks
• Simulation
Discrete Event Simulation Model
OCS and OBS extension on NS
Analytic Approach
• Methods:
formal derivation, considered approximation,
semi-empirical observation.
• Intent:
To formulate analytic or closed form;
To complement, not supplant more accurate,
but computationally intensive tools based on
numerical simulation.
Simulation
• Methods:
To implement discrete event simulation
model using generic languages;
To extend known simulation platform.
• Intent:
To be close to the real network.
Network Global Expectation Model
• Key idea: Use expectation values to
describe required quantities of key network
and network element resources.
• Significance: Provide approximate results
for the preliminary evaluation and design of
dynamic networks.
• Assumption: single-tier backbone networks,
location-independent traffic demands.
Network Global Expectation Model
CT
vi
ci
the total network cost
the number of network elements of type i
the unit cost of network element of type i.
CT 
c
i
i
CT 
v c
i i
i
Challenge: vi
Network Global Expectation Model
• Expectation value
1
 q 
m
m
q
i
i 1
• Example: L is the number of links and N is
the number of nodes.
CT  L  cl   N  cn 
Primary Model Variables (Input)
• Network graph G( L, N )
[ gij ] adjacent matrix
• Network traffic
T : the total ingress/egress traffic
D : the number of demands
[dij ] : demand matrix
Primary Model Variables
• Specify the difference between one-way and
two-way links
Links:
L  L2  L1 2
Total Traffic:
T  T2  T1 2
Total Demands: D  D2  D1 2
Output
• Number of Demands
D1 
N
d
ij
 N  d n
i, j
• Traffic Demand Bit-Rate
T1 T2


D1 D2
• Degree of Node
L1
  
N
Output
• Number of Hops
1
well known
a demand model
[ gij ] 
[hij ] 
  h 
D
D
h
ij
i j
Number of Hops
N 1
nodes
 
 4
 h 

N 2
   1
square root relation
Divide the network into 4 sectors
centered on the selected node
Number of Hops
The Moore bound results
from the construction of a
tree whose root is the
parent of  vertices and
each subsequent vertex is
itself the parent of   1
vertices.
 max
1

max  1

Logarithmic relation
0-hop
1-hop
2-hops
D=3-hops
Number of Hops
n  1   max
D

( max  1) h 1  1   max
h 1
Dmin
( max  1) D  1
 max  2

 max  2 
ln 1  (n  1)

 max 


ln( max  1)
  2

ln 1  (n  1)
 

h
ln(  1)
Output
• Demands on Link
1
o
 W 
L
D  h   d  h 
1  hij 

L
 
i j
D

• Restoration Capacity
 W k  W o  (1  k )
ab
 k 
   b
Inverse dependency upon the
degree of the nodes
Output
• Traffic on Link
D
T
   W    h    h 
L
L
• Number of Ports
 P  PADD    PDROP    PTHRU 
Number of ports
Drop+Thru
Add 
Add+Thru
Drop 
d
 PADD  PDROP  d 
 PTHRU  d  ( h  1)
d
Packet Delay in OCS Networks
• The paper first presents the queue length
distribution and the packet delay
distribution in a single logical buffer of the
edge router, and then extends that
discussion to a network of edge routers.
• To ensure computational tractability, the
framework approximates the evolution of
each buffer independently.
Model Formulation
• A circuit is a unidirectional lightpath
connecting a pair of source-destination edge
routers capable of transmitting C b/s
uninterruptedly for a period of T seconds.
• Circuits are allocated to the logical buffers
using a policy R based on the queue lengths
at all logical buffers.
Model Formulation
• Consider J data streams, each associated with
a source-destination pair of edge routers, Qos
class, a route and wavelength assignment
sequence from the source to the destination,
and other external classifications.
• So there are J logical buffers.
Model Formulation
• Normalized lightpath arrival rates
{ Aj ,1  j  J }
• Normalized lightpath transmission rates K
• Circuit switching decision epoch n
Model Formulation
• The queue length in logical buffer j at epoch n
X j ( n)
• The system state at epoch n
X(n)  ( X 1 (n), X 2 (n),
, X J (n))
• A binary vector indicating which of the logical
buffers are allocated circuits at state X(n)
δ R ( x)  (1R ( x),  2R ( x),
,  JR ( x))
Mathematical Model
• The process (X(n), n  0) is a Markov chain.
• But each X j (n) is not a Markov chain.
X j (n  1)  [ X j (n)  Aj   jR (X(n)) K ]
• Let  j (i, n) be the probability that algorithm R
allocates a circuit to buffer j with length i at
epoch n.


[
i

A

K
]
, with probability  j (i, n);

j
X j (n  1)  
with probability 1   j (i , n);

i  Aj ,
Simulation
• Discrete Event Simulation Model.
• OCS and OBS extension on NS.
Discrete Event Simulation Model
INIT（）Initialize System
1. simulation timer
2. system status
3. event list
4. performance statistics
TIMING（）Timing control
1. Schedule events according
to the event list, return the
next event to happen
2. Modify timer
EVENT（）Handle different
events from TIMING()
1. Modify system status
2. Modify performance statistics
3. Get the time of the next
event and add it into event list
N
Simulation Over
Y
1. Obtain performance statistics
2. Print results
Event handling
• Accept
Execute RWA for connection requests;
Modify the number of arriving requests, the
number of successfully established working path;
Modify the information of network resource.
Create the next event according to assumed
distribution and append it into event list.
• Service Over
Release the resource of working channel which is
not alive.
Basic Modules
• Phy-Topo : Generate physical topology, such as TORUS, NSFNet.
• Routing : Implement known routing algorithms, such as Dijkstra’s
Algorithm, Floyd-based SPF, K-Shortest-With-Loop-Path.
• Graph Theory Algorithm : provide basic graph theory algorithms,
such as MaxFlow, MinCost-Flow.
• Survival : provides protection and restoration schemes.
• Resource : Different policies, such as routing, wavelength
assignment, control management, survivability schemes, will lead to
different efficiency in resource usage.
• Wave-Assign : Combined with routing Module, it completes the RWA
function in WDM networks.
• V-Topo : This module controls the virtual topology in IP layer.
• Traffic : It contains Poisson, Gaussian, Self-Similar traffic module. It
is used to generate the random sequence of connection requests.
• Pseudo-Random Number : Generate random number in (0, 1)
uniformly.
• DES : discrete event simulation module.
• Performance Metrics Statistic : In each DES process, track interested
statistics variables. After simulation is over, prints out the values of
performance metrics.
Basic Modules
Wave-Assign
Virtual
Topology
Graph Theory
Traffic
Arrive
Routing
PseudoRandom
Number
Link-FailureOccur
Physical
Topology
Timing
Link-FailureOver
Survival
Performance
Metrics
Statistic
Server Over
Resource
OBS extension on NS
• OBS-ns (UMBC)
Use centralized structure to assign resource;
Add new classes for new types;
Ignore the architecture of NS.
• OBS-extension
Keep to the distributed architecture of NS;
Add new component in existing composite
classes for new features.
OBS-extension Task
• WDM link extension
No multi-channel link model in NS;
To add a multi-server queue in normal link
model.
• Assembly Module in Ingress Nodes of OBS
Networks
• Signaling, Qos and contention resolution
Normal Link Model
Link
head_
enqT_
queueT_
drophead_
deqT_
linkT_
ttlT_
revT_
drpT_
head_
The entry of a link
queue_
The queue reference of a link
link_
The reference of a link with delay and bandwidth property
ttl_
The reference of TTL management
drophead_
The reference of the head of the drop queue
WDM link extension
WvAssign
WvAssign : Queue
WaveClassifier : Classifier
Wavelength classifier
queueT_
Wavelength Classifier
Receive packet
Process packet head
Get Wavelength
number
Support Wavelength
conversion
N
Y
Execute WA
algorithm
Wavelength available
N
Y
Any port available
N
Y
return -1
Modify packet head
return wavelength
number
return wavelength
number
return -1
WDM link extension
Link
WvAssign
head_
enqT_
deqT_
linkT_
ttlT_
revT_
queueT_
drophead_
drpT_
#Create WDM link
$ns duplex-link $n3 $n4 1Mb 20ms WvAssign 4 FirstFit 1
OBS extension
• Redirector
Redirecting table and redirecting buffer.
Similar to route table and cache in
traditional router.
• Assembly Agent
Set assembly scheme, parameters and
signaling .
OBS extension
CBR
NULL
UDP
Disssembly
IP router
Assembly
WDM
core
Ingress
OBS
Packet flow
Burst flow
egress
Assembly agent
Port
classifier
Address
classifier
Assembly
Redirector
OBS ingress node
WDM link
Packet flow
Burst flow
WDM link
Test
Reference
•
•
•
•
•
Steven K. Korotky, “Network Global Expectation Model:
A Statistical Formalism for Quickly Quantifying
Network Needs and Costs”, Journal of Lightwave
Technology Preprint, 2004.
Zvi Rosberg, “Packet Delay in Optical Circuit-Switched
Networks”, 2004.
Zvi Rosberg, “Analysis of OBS Networks with Limited
Wavelength Conversion”, 2004.
Jean-Francois Labourdette, “Fast Approximate
Dimensioning and Performance Analysis of Mesh
Optical Networks”, Design of Reliable Communication
Networks 2003, 428-438.
Damon J. Wischik, “Mathematical Modeling of Optical
Burst-Switched (OBS) Networks”, 2004.