09-11-2012, 04:07 PM
Fast Simulation of Service Availability in Mesh Networks With Dynamic Path Restoration
[attachment=38788]
Abstract
A fast simulation technique based on importance
sampling is developed for the analysis of path service availability
in mesh networks with dynamic path restoration. The method
combines the simulation of the path rerouting algorithm with
a “dynamic path failure importance sampling” (DPFS) scheme
to estimate path availabilities efficiently. In DPFS, the failure
rates of network elements are biased at increased rates until path
failures are observed under rerouting. The simulated model uses
“failure equivalence groups,” with finite/infinite sources of failure
events and finite/infinite pools of repair personnel, to facilitate
the modeling of bidirectional link failures, multiple in-series link
cuts, optical amplifier failures along links, node failures, and more
general geographically distributed failure scenarios. The analysis
of a large mesh network example demonstrates the practicality of
the technique.
INTRODUCTION
THE concept of a mesh network architecture is being
adopted increasingly in the field in the development and
deployment of new networks or in the replacement, migration,
or evolution of existing networks. In a generic mesh network, a
set of nodes is interconnected with links following an arbitrary
topology. The routes of end-to-end “paths” (i.e., end-to-end
physical or virtual circuits) over the links can be arbitrary. The
routes of backup or protection paths can also be arbitrary and
even be generated dynamically. This generality is in contrast to
traditional network architectures that are typically more rigid
in form with fault tolerance provided using, for example, rings,
extra dedicated protection links, or preestablished protection
connections. Advantages of mesh networking include the enabling
of more general routing schemes, more flexible traffic
engineering, simplification of network operations and management
functions, more cost-effective use of redundant network
capacity, the enabling of more general self-configuration and
self-healing mechanisms, and potentially higher levels of service
availability.
DYNAMIC PATH RESTORATION
The failure of a particular link results in the failure of all circuits
that use the link. The failure of a circuit can lead to the possible
failure of a path. When a path experiences a circuit failure,
the dynamic mesh network will attempt to reroute the affected
path over circuits that are operational. The process of rerouting
a failed path in response to a failed circuit is called dynamic
path restoration. The type of restoration method assumed here
is quite general. It may be one that finds the next shortest route in
terms of working circuits, subject to the prevailing circuit bandwidth
constraints. It may be one that finds a route that maximizes
the minimum remaining capacity over all working circuits in the
network. The restoration method could also reroute some or all
paths in the network (“network repacking”) to maximize some
objective function. The method could also reroute paths in response
to the completion of link repairs.
FAILURE AND REPAIR MODELING WITH FEG
We now define the modeling of failures and repairs in the network.
To enable the construction of mesh network models with
features that can reflect network characteristics commonly seen
in practice, we define and use the concept of a failure equivalence
group (FEG). A FEG is defined to be a particular subset
of unidirectional links together with an associated failure and
repair process. A particular link may belong to one or more
groups. At any point in time, each group is in either an operational
or a failed state. When a group is in a failed state, all the
unidirectional links in the group are unusable. A unidirectional
link is usable if and only if all the groups to which it belongs
are operational. Each group experiences the arrival of failure
events that cause the group to be in a failed state. The failure
events in a particular group are repaired by a finite or infinite
pool of repair personnel that is dedicated to the group. When a
group is operational and a failure event arrives in the group, the
group enters the failed state and the repair of the failure event
is started by a repair person. While in the failed state, a group
may also experience additional independent arrivals of failure
events.
DYNAMIC PATH-FAILURE SAMPLING
The DIS simulation method developed here for estimating
path availabilities in mesh networks with dynamic path restoration
is called dynamic path-failure importance sampling
(DPFS). In DPFS, the goal is to bias the system state trajectory
specifically toward path failures that the restoration algorithm
is unable to restore. This is achieved by setting the failure
rates in the FEG at an increased level until path failures are
observed to occur (or state is reached). Once a path
failure is realized, the group failure rates are set back to their
original values. Note that if we simply biased failure rates until
a group failure occurred, then this would not be effective in
general since, under dynamic path restoration, the failure of a
group does not always necessarily lead to the failure of paths.
MESH NETWORK EXAMPLES
We present two mesh network examples. The first is a small
test network to validate the theory and demonstrate the efficiency
of DPFS. The second is a larger network example to illustrate
the practical application of DPFS to a modeling problem
of a size that can typically be encountered in practice. In both
examples, we assume that the initial paths are the shortest paths
and that the dynamic path restoration algorithm reroutes a path
by determining the next shortest operational route using Dijkstra’s
algorithm [26], subject to the prevailing circuit bandwidth
constraints.
CONCLUDING REMARKS
The DPFS simulation technique developed here is a practical
and effective method for estimating service availability in mesh
networks with dynamic path restoration. It enables one to obtain
useful confidence interval widths on path service availabilities
in reasonable simulation run times. The developed failure and
repair modeling with FEG is sufficiently general so that it can
be used to faithfully represent many of the types of failure and
repair mechanisms that appear in practice. The assumed path
restoration algorithm is sufficiently general to accommodate almost
any algorithm, at least ones that return paths to their initial
paths once all element repairs have been made.
[attachment=38788]
Abstract
A fast simulation technique based on importance
sampling is developed for the analysis of path service availability
in mesh networks with dynamic path restoration. The method
combines the simulation of the path rerouting algorithm with
a “dynamic path failure importance sampling” (DPFS) scheme
to estimate path availabilities efficiently. In DPFS, the failure
rates of network elements are biased at increased rates until path
failures are observed under rerouting. The simulated model uses
“failure equivalence groups,” with finite/infinite sources of failure
events and finite/infinite pools of repair personnel, to facilitate
the modeling of bidirectional link failures, multiple in-series link
cuts, optical amplifier failures along links, node failures, and more
general geographically distributed failure scenarios. The analysis
of a large mesh network example demonstrates the practicality of
the technique.
INTRODUCTION
THE concept of a mesh network architecture is being
adopted increasingly in the field in the development and
deployment of new networks or in the replacement, migration,
or evolution of existing networks. In a generic mesh network, a
set of nodes is interconnected with links following an arbitrary
topology. The routes of end-to-end “paths” (i.e., end-to-end
physical or virtual circuits) over the links can be arbitrary. The
routes of backup or protection paths can also be arbitrary and
even be generated dynamically. This generality is in contrast to
traditional network architectures that are typically more rigid
in form with fault tolerance provided using, for example, rings,
extra dedicated protection links, or preestablished protection
connections. Advantages of mesh networking include the enabling
of more general routing schemes, more flexible traffic
engineering, simplification of network operations and management
functions, more cost-effective use of redundant network
capacity, the enabling of more general self-configuration and
self-healing mechanisms, and potentially higher levels of service
availability.
DYNAMIC PATH RESTORATION
The failure of a particular link results in the failure of all circuits
that use the link. The failure of a circuit can lead to the possible
failure of a path. When a path experiences a circuit failure,
the dynamic mesh network will attempt to reroute the affected
path over circuits that are operational. The process of rerouting
a failed path in response to a failed circuit is called dynamic
path restoration. The type of restoration method assumed here
is quite general. It may be one that finds the next shortest route in
terms of working circuits, subject to the prevailing circuit bandwidth
constraints. It may be one that finds a route that maximizes
the minimum remaining capacity over all working circuits in the
network. The restoration method could also reroute some or all
paths in the network (“network repacking”) to maximize some
objective function. The method could also reroute paths in response
to the completion of link repairs.
FAILURE AND REPAIR MODELING WITH FEG
We now define the modeling of failures and repairs in the network.
To enable the construction of mesh network models with
features that can reflect network characteristics commonly seen
in practice, we define and use the concept of a failure equivalence
group (FEG). A FEG is defined to be a particular subset
of unidirectional links together with an associated failure and
repair process. A particular link may belong to one or more
groups. At any point in time, each group is in either an operational
or a failed state. When a group is in a failed state, all the
unidirectional links in the group are unusable. A unidirectional
link is usable if and only if all the groups to which it belongs
are operational. Each group experiences the arrival of failure
events that cause the group to be in a failed state. The failure
events in a particular group are repaired by a finite or infinite
pool of repair personnel that is dedicated to the group. When a
group is operational and a failure event arrives in the group, the
group enters the failed state and the repair of the failure event
is started by a repair person. While in the failed state, a group
may also experience additional independent arrivals of failure
events.
DYNAMIC PATH-FAILURE SAMPLING
The DIS simulation method developed here for estimating
path availabilities in mesh networks with dynamic path restoration
is called dynamic path-failure importance sampling
(DPFS). In DPFS, the goal is to bias the system state trajectory
specifically toward path failures that the restoration algorithm
is unable to restore. This is achieved by setting the failure
rates in the FEG at an increased level until path failures are
observed to occur (or state is reached). Once a path
failure is realized, the group failure rates are set back to their
original values. Note that if we simply biased failure rates until
a group failure occurred, then this would not be effective in
general since, under dynamic path restoration, the failure of a
group does not always necessarily lead to the failure of paths.
MESH NETWORK EXAMPLES
We present two mesh network examples. The first is a small
test network to validate the theory and demonstrate the efficiency
of DPFS. The second is a larger network example to illustrate
the practical application of DPFS to a modeling problem
of a size that can typically be encountered in practice. In both
examples, we assume that the initial paths are the shortest paths
and that the dynamic path restoration algorithm reroutes a path
by determining the next shortest operational route using Dijkstra’s
algorithm [26], subject to the prevailing circuit bandwidth
constraints.
CONCLUDING REMARKS
The DPFS simulation technique developed here is a practical
and effective method for estimating service availability in mesh
networks with dynamic path restoration. It enables one to obtain
useful confidence interval widths on path service availabilities
in reasonable simulation run times. The developed failure and
repair modeling with FEG is sufficiently general so that it can
be used to faithfully represent many of the types of failure and
repair mechanisms that appear in practice. The assumed path
restoration algorithm is sufficiently general to accommodate almost
any algorithm, at least ones that return paths to their initial
paths once all element repairs have been made.
