A Multi-constraint based Real-time Routing Scheme using Simulation Methodology : A Multi-constraint based Real-time Routing Scheme using Simulation Methodology
Outline : Outline DEVS model continuity
Multi-constraint routing problem
Simulation-based Path Discovery
Application of PSSM in real-time network routing
DEVS (Discrete Event System Specification) Model Continuity : DEVS (Discrete Event System Specification) Model Continuity Develop model in DEVS formalism
Verify and validate through simulation
Replace the DEVS-simulator by DEVS-real time executor
Result is a real-time software system with proven properties
Multi-constraint Routing Problem in Optical Networks : Multi-constraint Routing Problem in Optical Networks Optical network have different parameters of operation than electrical networks. These parameters, basically the impairments:
Polarization mode dispersion
Chromatic dispersion
Linear/Non-linear impairments
In addition to advances in Optical networking, critical are the improvements in the “Optical Layer Control Plane” – the software used to determine routings and establish and maintain connections
Background – Multi-constraint Routing Problem : Background – Multi-constraint Routing Problem Control plane architectures based on Data network protocols like MPLS take bandwidth availability into consideration
Success will depend strongly on ability to adapt to multiple constraints
related with networking physics (e.g. Optical)
NOT additive.
Physical/analog attributes of packets/links include:
Energy
Attenuation
Noise
Additional physical state information for routing algorithms for each impairment that limits routes
Physical layer attributes in Optical networks)
don’t change value rapidly
can be stored in database
BUT must be measured and updated
May depend on throughput in link
Therefore -- Complex routing potentially beyond the capability of analytic or graphic theoretic solutions Ref: J. Strand, A. L. Chiu, and R. Tkach, “Issues for Routing in the Optical Layer, 2001
History : History Wu completed Doctoral thesis in MPLS traffic engineering for optical networking
Designed routing algorithm that took account of attributes
Using OPNET was not able to verify utility of algorithm
So we subsequently collaborated to develop the DEVS based simulation approach
Path Selection Using Simulation (PSSM) : Path Selection Using Simulation (PSSM) Heuristic algorithm using discrete event simulation method
Finding a path that can meet the multi-constrained requirements by sending data from source using a simulation-based search method
Executes the following steps in the order
Based on network topology and resources, a network simulation model is built
A ‘requirement’ (Simulation-Packet) is created that defines the paths’ source, destination and QoS requirements/constraints
Simulation is run by flooding the packets from source to destination with each packet carrying the information
Destination
Path constraint requirements
Traveled path
Traveled path’s attributes
The first packet that reaches destination stops the simulation
The path is then reported as a ‘feasible’ path satisfying requirements/constraints
Slide8 : DEVS Simulation Model DEVS simulation model consists of:
Router model
Link model
Packet model Request for a path from source X Traversed path and the accrued info, stopping the further simulation Packet dropped as it failed to meet requirements Node Done, simulation can only go in one direction
Application in ASON (Automatically Switched Optical Network) : Application in ASON (Automatically Switched Optical Network) PSSM can be employed to derive real-time routing scheme.
ASON has its connections end-to-end.
An edge ASON router is proposed to have DEVS-engine that executes the PPSM algorithm.
Monitoring in Real-time : Monitoring in Real-time Efficient ‘Routing’ is highly dependent on knowledge of the state of the link-state database.
With Optical Networks, physical parameters don’t change that often, but the links/routers do keep going up/down.
PSSM updates the link-state database in two ways
Periodic method
each router updates its topology base periodically flooding the network with LSAs
Quantized method
each router updates its topology and link state metrics only when a new requirement arrives or there is a change in the configuration of the network.
Since links are multi-attribute and analog values, a ‘quantum’ is defined, based on which LSAs are triggered
Current Status & Future Directions : Current Status & Future Directions DEVS model is developed and verified.
Validation needs accurate parameter and attribute data to calibrate and validate the model.
Assess the speed at which the simulation can generate good feasible paths.
Extend link model to predict the behavior of link attributes with physics based refinements -- reduce the amount of updating needed from network measurements.
Exploit generic capabilities:
apply general framework to SCOPE command HF network -- small number of nodes but links are subject to frequent change in attributes, e.g., to ionosphere properties.
wireless Gigabit Ethernet where it is necessary to have intelligent nodes that can route effectively with incomplete network-information updates and where attention management is needed