CCAMP Working Group Dimitri Papadimitriou (Alcatel)
Category: Internet Draft Fabrice Poppe (Alcatel)
Expires: May 2003 Sudheer Dharanikota (Consult)
Riad Hartani (Caspian)
Raj Jain (Nayna)
Jim Jones (Alcatel)
Senthil Venkatachalam (OPNet)
Yong Xue (WorldCom)
November 2002
Shared Risk Link Groups Encoding and Processing
draft-papadimitriou-ccamp-srlg-processing-01.txt (*)
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts. Internet-Drafts are draft documents valid for a maximum of
six months and may be updated, replaced, or obsoleted by other
documents at any time. It is inappropriate to use Internet-Drafts as
reference material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
(*) Formerly draft-many-inference-srlg-02.txt
Abstract
The Shared Risk Link Group (SRLG) concept introduced in [IPO-FRM]
and extended in [CCAMP-SRG] is considered as one of the most
important criteria concerning the constraint-based path computation
of optical channel routes. By applying the SRLG disjointness
criteria to the constraint-based path computation, one can select a
route taking into account both resource and logical structure
disjointness. That implies a lower probability of simultaneous
optical channel failure.
This document describes the various physical and logical resource
types considered in the SRLG concept. The proposed method focuses on
D.Papadimitriou et al. - Expires May 2003 1
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
the inference of SRLG information between the network physical and
logical layers. The main applications of the proposed model are
related to the Constraint-based Shortest Path First (CSPF) algorithm
for optical channel route computation and the aggregation of the
SRLG information flooded throughout traffic engineering extensions
of the IGP routing protocols (such as OSPF and IS-IS).
1. Introduction
Many proposals include the Shared Risk Link Group (SRLG) concept
when considering the disjointness for the constraint-based path
computation of optical channel routes. In the optical domain, the
SRLG concept is used for deriving a path, which is disjoint with
respect to physical (or passive) and logical (or active) resources.
[CROCH] describes algorithms that can use the SRLG information
inferred using the mechanisms described in this document, in order
to determine survivable logical topologies on top of a given
physical topology.
The corresponding requirements have already been described in [IPO-
IMP] while considering physical network topology and associated
risks. In the scope of this document, these requirements can be
summarized as follows:
1. The SRLG encoding mechanism should reduce the path computation
complexity.
2. The SRLG information flooding should be scoped to reduce the
amount of information that is exchanged across domains.
3. The SRLG encoding should accommodate the physical and logical
restrictions imposed on the diversity requirements.
However, the definition of SRLG in the current format described in
[GMPLS-OSPF] and [GMPLS-ISIS] does not provide:
1. The relationship between physical (or logical) resources and
between physical and logical resources. For example, a fiber
could be part of a sequence of fiber segments or an optical
channel may cover several fibers links.
2. The risk assessment during path computation implying the
assignment of a conditional failure probability to the SRLGs.
3. The analysis of the specifics aspects of constraint-based path
computation and path re-optimization taking SRLG information into
account.
This document proposes among others a technique to compute the SRLG
with respect to a given risk type. This is achieved by identifying
for a given physical layer the resources belonging to an SRLG. The
proposed model also permits to compute the dependencies of these
resources to the lower (passive) physical layers. The result of the
computation also enables to determine the risk associated to each of
the SRLGs, that is, the probability that two entities (both using
network resources belonging to a given SRLG) go simultaneously down
if one of them goes down (thus defining a conditional failure
probability).
D.Papadimitriou et al. - Expires April 2003 2
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
The remainder of this memo is organized as follows. In section 3, we
present the hierarchical model of the network resources and the
corresponding SRLG encoding. In section 4, we discuss the use of the
proposed approach for risk assessment during path computation and
selection. Considerations on topology summarization and path
disjointness with respect to SRLG are proposed in section 5.
2. Conventions used in this document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in
this document are to be interpreted as described in RFC-2119 [1].
The reader is assumed to be familiar to the terminology and concepts
detailed in [GMPLS-RTG], [GMPLS-OSPF] and [GMPLS-ISIS].
3. Hierarchical Model
The proposed approach is based on a representation of the network
resources in terms of a hierarchy. This hierarchical structure is
related to the fiber topology (or more generally the physical
resources) of the optical network and the channels built on top of
this physical topology.
The encoding of the SRLG could be either mapped on this hierarchical
model or simply use a flat encoding scheme. Difference between both
encoding relies on the extended usage of the SRLG identifiers in the
context of diverse route computation (i.e. path disjointness). Since
a link can belong to more than one SRLG, an SRLG identifier list (in
the SRLG Sub-TLV), as described in [GMPLS-OSPF] and [GMPLS-ISIS] is
associated with each link (i.e. the SRLG Sub-TLV is defined as a
Sub-TLV of the TE Link TLV). This results in a linear, unordered and
non-structured information from which the underlying structure
cannot be deduced.
Consequently, either a type field indicating the type of network
resource (or logical structure) to which this SRLG identifier refers
extends the flat encoding scheme or the encoding itself translates
the underlying hierarchical structure. Worth mentioning here is that
a hierarchical encoding (since depending on the physical layer which
is static by definition) needs an additional mapping structure in
order to keep the relationship with link identifiers.
3.1 Network Resource Hierarchy
The network (physical and logical) resource model considered in the
inference of the Shared Risk Link Groups (SRLGs) is based on
premises detailed in [IPO-FRM] and [IPO-IMP]. The network resource
hierarchy includes the logical resources built on top of the
physical resource hierarchy belonging to the optical network.
The concepts around network resource hierarchy are based on the
following logical resource definitions:
D.Papadimitriou et al. - Expires April 2003 3
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
- Sub-Channel: a dedicated container included within a given optical
channel uniquely identifies a sub-channel.
- Channel(*): an optical channel is uniquely identified by its
corresponding and dedicated wavelength (sub-)interface identifier.
(*) when conversion or amplification is non-collocated with the
corresponding interface capability, the passive components are
logically embedded into the fiber link (see below definition).
These resources are built on top of the physical resource hierarchy
composed by the following physical resources considered as a common
denominator of most Optical Transport Network (OTN) environments:
- Fiber Link: a fiber connects two node ports communicating through
one or more optical channel if their interfaces support (Dense)
Wavelength Division Multiplexing û (D)WDM, also a fiber link can
be decomposed as a sequence of fiber spans separated by optical
amplifiers
- Fiber Sub-segment: a group of fiber links, any fiber link of a
sub-segment start and terminates at the same location
- Fiber Segment: a group of fiber sub-segments, any fiber sub-
segment of segment start and terminates at the same location
Moreover, one can consider sequences of fiber (sub-)segment starting
and terminating at the same node and defined them as fiber trunks
(also referred to as cable or fiber duct).
Thus, the approach developed here extends the definition and
concepts given in [IPO-FRM] and [IPO-IMP] by enabling fiber
topologies not strictly limited to point-to-point physical inter-
connections between nodes.
As represented in Figure 1, the fiber trunk going from location N[1]
to location N[3] is composed by the fiber segments A and B and the
fiber trunk from location N[1] to location N[2] includes the fiber
segments A, C and D.
Location N[1] Location N[3]
Sub-Segment A[1] Sub-Segment B[1]
---------------------------------------------------------------
=== . . . ====== Fiber Fiber ====== . . . ====
=== . . . ====== Fiber Fiber ====== . . . ====
--------------------------------------------------------------
Segment A Segment B
------------------------------ -----------------------------
=== . . . ====== Fiber | | Fiber ====== . . . ====
=== . . . ====== Fiber | | Fiber ====== . . . ====
------------------------- | | -------------------------
D.Papadimitriou et al. - Expires April 2003 4
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
Sub-Segment A[n] | | | | Sub-Segment B[n]
| | | |
| | | | Segment C
| | | |
Sub-Segment D[1] | | | | Sub-Segment E[1]
------------------------- | | -------------------------
=== . . . ====== Fiber | | Fiber ====== . . . ====
=== . . . ====== Fiber | | Fiber ====== . . . ====
------------------------------ ------------------------------
Segment D Segment E
---------------------------------------------------------------
=== . . . ====== Fiber Fiber ====== . . . ====
=== . . . ====== Fiber Fiber ====== . . . ====
---------------------------------------------------------------
Sub-Segment D[n] Sub-Segment E[n]
Location N[2] Location N[4]
Figure 1. Example of Physical Topology
In this figure, the Segment A is composed by the fiber sub-segments
A[1], A[2], ..., A[i], ..., A[n]. The same terminology applies for
the segments B, C, D and E.
Consequently, the fiber trunk from location N[2] to location N[4]
includes the sub-segments D[2] to D[n] and their corresponding sub-
segments within the segment E: E[2] to E[n]. The fiber trunk from
location N[1] to location N[2] includes the fiber sub-segments A[n],
C[1] and D[1].
3.3 SRLG Definition and Properties
A SRLG is defined as the set of links (or optical lines) sharing a
common physical resource (including fiber links, sub-segment and
segment) i.e. sharing a common risk. For instance, a set of links L
belongs to the same SRLG s, if established over the same fiber link
l.
3.3.1 SRLG Properties
The SRLG properties can be summarized as follows:
1) A link belongs to more than one SRLG if and only if it crosses
(at least) one of the resources covered by each of these SRLGs
For instance: fiber link l belongs to the SRLG s1 and s2, if and
only if it crosses the fiber sub-segment A[1] and B[1]
2) Two links belonging to the same SRLG can belong individually to
other (one or more) SRLGs
D.Papadimitriou et al. - Expires April 2003 5
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
For instance: fiber links l1 and l2 belong to SRLG s3 (segment A)
while l1 belongs to SRLG s1 (since it covers sub-segment A[1]) and
l2 to SRLG s4 (since it covers sub-segment D[1])
3.4.2 SRLG Disjointness
To define the LSP SRLG disjointness notion, we first introduce the
following definition: an LSP (i.e. sequence of links) covers an SRLG
if and only if it crosses one of the links belonging to that SRLG.
For instance: LSP p1 covers SRLG s1 (since it crosses link l1)
LSP SRLG disjointness can then be defined as follows.
1) Two LSPs are disjoint with respect to an SRLG s1 if and only if
at most one of them covers this SRLG.
For instance: LSPs p1 and p2 are disjoint with respect to SRLG s1
since only p1 covers SRLG s1.
2) Two LSPs are disjoint with respect to a set of SRLG S if and only
if the sets of SRLGs they individually cover are completely disjoint
For instance: LSP p1 and p3 are disjoint with respect to set of SRLG
S = {s1, s2, s3} since only p1 covers SRLG set S.
3.5 Computational Model Capabilities
This section briefly describes guidelines for an SRLG computational
model described in appendix A and based on the above definitions.
The main features of this model are:
- Support Constraint-based Shortest Path First (CSPF) algorithm for
explicit route (or path) computation by considering SRLG
disjointness with respect to one or more risk types
- Encompass hierarchical dependencies between physical resources
(inference of SRLG sets using bottom-up computation)
- CSPF computation including the relationship between physical
resources and topological structures. For instance:
. a fiber link can be part of given fiber trunk
. a fiber cable passing through an earthquake region
- Provide risk assessment during path computation implying
allocation of conditional failure probabilities with SRLGs
- SRLG information flooding well-scoped to reduce the amount of
link-state advertisements by using summarization
Consequently, the above features suggest an SRLG encoding mechanism
that enables:
- Accommodation of the physical and topological hierarchies
- Reduction of the path (i.e. explicit route) optimality
D.Papadimitriou et al. - Expires April 2003 6
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
3.6 SRLG Encoding
Using the above definitions and properties, the objective of the
hierarchical encoding is to achieve aggregation of the SRLG
Identifiers on top of the (passive) optical network topology. For
this purpose, we propose a linear encoding scheme including a type
field. This provides abstraction of the physical layer structure and
should facilitate the management of the SRLG Identifiers.
The proposed SRLG sub-TLV of the TE Link top level TLV includes the
following SRLG Identifier (64-bit field):
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Weight |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Within the SRLG Identifier field (64 bits), the Type field (8 bits)
defines the resource type (also generically referred to as the link
type) to which the Identifier (32 bits) integer value refers. The
weight field (24 bits) assigned on a per-SRLG basis along with the
Identifier is defined in Section 4.
The following Type field values are currently defined for physical
resources, any other value being reserved:
Type Value
-------------------- ------
Reserved 0x00
Fiber Trunk 0x10
Fiber Segment 0x20
Fiber Sub-segment 0x30
Fiber Link 0x40
Node(*) 0xFF
(*) represents a non-GMPLS capable switching elements
Logical resources such as optical channels and TDM circuits (or
optical sub-channels) can take one of the following values:
Type Value
------------------- ------
Optical Channel 0x50
Optical Sub-Channel 0x60
Since a given physical or logical resource (for instance a fiber
link) can belong to more than one SRLG, the SRLG Identifier
structure is defined in the general case as a list of SRLG
Identifier (n x 64-bit):
D.Papadimitriou et al. - Expires April 2003 7
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Weight |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Weight |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
// ... //
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Weight |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Therefore, though we propose a linear encoding, the aggregation of
the SRLG is still possible. This encoding also enables to perform
summarization (which is not equivalent to aggregation) at the
boundaries of structures defining the spatial coverage of an SRLG
Identifier list while overcoming the drawbacks of full hierarchical
encoding schemes. In this context, the weight value follows the
rules defined in the Section 4.
4. Risk Assessment
Risk assessment is defined as the quantification process of the
potential risk associated to the inclusion of a given resource
(belonging to a given resource type) located within a given logical
structure such as a geographical location for a given logical
network resource such as an optical channel.
4.1 Rationale for Risk Assessment
Consider the following example, where the client device makes the
following connection requests to the optical network:
- Request for a persistent connection with 99.999 % percent of
availability or equivalently a downtime less than X minutes per
year.
- Request for protection for a portion of the traffic (at the
expense of more charging) compared to other portion of the
traffic left unprotected and considered as extra traffic by the
server.
D.Papadimitriou et al. - Expires April 2003 8
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
Such requirements will be translated into path specific requests.
Such path specific requests can be grouped into path selection
requirements and path characterization requirements.
1. Path selection requirements
These typically dictate which physical path should be taken to
achieve the availability requirements of the client request. These
requirements are typically related to the logical and physical
diversity as mentioned in Section 3.
2. Path characterization requirements
Path characterization requirements typically dictate the recovery
mechanisms as specified by the client connection request. This can
be achieved in the form of section and/or path recovery but also
depending on the ring or meshed topology of the optical network.
However, these considerations are out of the scope of this document.
The components that need formalization in this example are:
- Step 1. Specification of the client requirements (service level).
- Step 2. Configuration of the network that helps in assessing the
service specifics such as the availability.
- Step 3. Propagation of the above-configured information.
- Step 4. Processing of the above-propagated information.
Step 1 of specifying the requirements is not in the scope of this
document. Steps 2 to 4 are discussed in the following sections where
we elaborate on the risk assessment during path selection.
4.2 Risk Assessment
Risk (the complementary of availability) assessment is defined as
the evaluation of the potential risk associated to the inclusion for
a given path of a specific network resource (i.e. belonging to a
given resource type). Given that an SRLG Identifier list is used to
encode the group of logical and physical resources, if a mechanism
is devised to assign the risk of failure associated with the
corresponding resource, the availability of the path using these
resources can be computed. This, in order to meet the connection
availability as requested by the client request.
A simple approach is to assign the conditional failure probability
to each of the SRLG Identifiers. This information is encoded in the
weight (24 bits) field along with the SRLG information as defined in
Section 3.3. The associated weights can be used to either increase
or decrease the potential usage of the resource (i.e. inclusion into
the selected route). The Weight field is defined as a 24-bit length
encoded integer number (maximum value 2^24 - 1) to be divided by
(2^24 û 1) and multiplied by 100 to get the corresponding value in
percents. For instance a conditional failure probability of 0.99999
corresponds to a weight of 16.777.047 and 0.00005 to 839.
D.Papadimitriou et al. - Expires April 2003 9
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
For instance, we can associate a conditional failure probability of
25% (weight = 4.194.304) to any fiber sub-segment. It means that by
selecting two (or more than two) different optical channel paths
including the same SRLG identifier with respect to fiber sub-segment
failure, if one of these connections fails, then the probability
that the other connection fails is 25%.
The failure probability of a fiber can also depend on the length of
the fiber. In addition, a fiber can pass across different regions
with different failure probabilities. In this case, we need to
consider an aggregated failure probability per fiber taking into
account each of the failure probabilities of its sub-components.
For instance, if we refer to our previous example and by considering
1. a conditional failure probability of 5% is associated to any
fiber link
2. a conditional failure probability of 1% is associated to any
fiber segment
Then by selecting two different optical channels included within the
same SRLG with respect to fiber segment failure, we obtain a
simultaneous connection failure probability of 1%. Consequently,
when a protected connection service is requested, by choosing fiber
segment path disjointness, the simultaneous connection failure
probability is also of 1%. However, if two optical channels flowing
through the same fiber link are selected, then we have a probability
of 5% that both optical channels fail simultaneously.
More generically, if one assigns a conditional failure probability
c[i] to each SRLG Identifier i, the resulting conditional failure
probability C for a logical resource (a connection, for instance)
using these N resources is given by:
C = 1 - (1 û c[1]) x (1 û c[2]) x . . . x (1 û c[N])
When all the conditional failure probabilities c[i] are small (i.e.
c[i] << 1) C can be approximated by (1 - Sum[i]c[i]).
4.3 Risk Assessment Application
The relationship between the availability of the service requested
by the client (i.e. a working and a protection connection) and the
conditional failure probabilities of the physical resource elements
included within the corresponding paths can be described as follows.
If we consider for instance 1) a conditional failure probability of
1% if fiber links are selected within the same fiber trunk 2) a
conditional failure probability of 1% if fiber links are selected
within the same fiber segment and 3) the corresponding failure are
independent events.
Then the availability of a connection whose backup is established
over fiber links (in same fiber segment) and within the same fiber
D.Papadimitriou et al. - Expires April 2003 10
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
trunks as the primary connection itself is approximately 98% (by
using the above formula).
Note that the initial value of the conditional failure probability
needs to be statically encoded; however, based on the history of the
failures these values could be dynamically re-evaluated. The
corresponding mechanism needs to be specified and is left for
further study.
5. Applications
The SRLG method developed here results in applications related to
the CSPF explicit route computation and the SRLG identifier sets
summarization. The latter enables in turn, intra- and inter-area
diverse path computation. For that purpose we first extend the SRLG
concept for logical resources such as optical channels and optical
sub-channels (i.e. TDM connections).
5.1 Extension to the Logical Resources
The SRLG concept can be extended to logical structures and resources
by taking into account the following:
1. Given the physical decomposition of the optical network
topology, the SRLG encoding can be hierarchically structured.
The hierarchical encoding helps in constructing the logical
topology abstraction, which in turn can be used in SRLG
summarization and loose-path computation. The link semantic may
also be extended to accommodate virtual links.
2. Propagate the SRLG information related to these logical
(structures and resources) links, for instance (a set of)
optical channels using IGP flooding for intra- and inter-area
routing purposes.
3. Reduce the amount of the flooded information and hence explicit
route computation optimality and extend the flooding scope of
the propagated information to accommodate logical resources
(i.e. optical channels and TDM circuits).
5.2 SRLG Information Flooding and Summarization
The SRLG set of each link (i.e. physical and logical resources) is
encoded as described in Section 3.3. This information is propagated
once at initial configuration between the various nodes using the
GMPLS Traffic Engineering extensions to IGPs (see [GMPLS-OSPF] and
IS-IS [GMPLS-ISIS]). After this initial SRLG identifier exchange,
corresponding values do not change over time.
Nevertheless, the propagation of SRLG information will be necessary
whenever a new link is added or an existing link is removed.
Initially, it is assumed that the failure probabilities of the
various resources are (statically) configured. However, it is
D.Papadimitriou et al. - Expires April 2003 11
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
envisioned that after a certain running period, the failure
probability associated to the SRLG and propagated along with the
SRLG sub-TLV itself (as described in Section 3.3) will change over
time and thus give rise to a dynamic metric.
5.3 Bottom-Up Computation of SRLG Relationships
Once the traffic engineering (topology-related) link information is
received by the node, the corresponding SRLG relationships can be
computed on a regular basis.
The fiber trunk SRLG relationships are used to compute the fiber
segment SRLG relationships, which in turn are used to compute the
fiber sub-segment SRLG relationships and finally the fiber SRLG
relationships. To each SRLG relationship (at each level), which
defines the membership of a resource to a particular SRLG, we
associate the conditional failure probability between two resources
belonging to this level (for instance, between two fibers that have
a common fiber sub-segment).
5.4 Topology Summarization and Route Computation
A direct application of this model is the Constraint-based Shortest
Path First (CSPF) algorithm used for explicit route computation
(i.e. traffic-engineered LSP creation) to maximize the connection
disjointness and so decrease their common failure probability. Given
an existing set of connections across the network, the objective is
to compute, for a newly requested connection, an explicit route
across the optical network topology such that this connection is
diversely routed from an existing given set of connections.
The diversity requirement is a routing constraint, that can be
expressed in terms of a conditional failure probability with respect
to an existing (set of) connections and more generally any kind of
resources. Hence, in addition to the other traffic-engineering
constraints, the diversity constraint requires that the conditional
failure probability does not exceed a given threshold. The CSPF
algorithm needs to be updated to take the routing diversity
constraint into account.
The SRLG concept generates another dimension to the existing
constraint-based path computation methods traditionally used in
hierarchical networks. The SRLG constraints comes in addition to the
common traffic-engineering constraints such as bandwidth
availability, link metrics and TE attributes (see [OSPF-TE]). The
specificity of the routing diversity constraint requires the use of
a path computation algorithm that provides not only complete multi-
path disjointness but also partial multi-path disjointness with
respect to various risk factors. In a similar way, appropriate
mechanisms should also be used in order to perform path re-
optimization following various recovery strategies.
D.Papadimitriou et al. - Expires April 2003 12
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
The specific aspect of complete and partial multi-path disjointness
is related to the fact that a path may with respect to SRLG be fully
or partially disjoint from a given set of path. In brief, one speaks
about SRLG partial or full multi-path disjointness. This means that
a connection may be disjoint from another but only to some extent
with respect to some risk factors. Thus when referring to path
disjointness with respect to SRLG one may also include the ratio of
disjointness with respect to various risk type assigned to their
component resources. Consider for instance the LSPs p1 and p2 using
j1 and j2 resources respectively, m of these resources having an
SRLG in common, with m =< j1 and m =< j2, then [(j1-m) + (j2-
m)]/(j1+j2) provides the disjointness ratio. For instance, if j1=13,
j2=7 and m=1, this ratio equals 0.90, thus corresponding path p1 and
p2 are SRLG disjoint at 90%.
As such, this feature differentiates path disjointness constraint
from any other constraint commonly considered in path computation.
6. Scalability Considerations
6.1 OSPF Scalability Considerations
A node SHOULD minimize the amount of routing information it floods.
Each time a SRLG sub-TLV is configured or removed that information
shall be flooded (not necessarily immediately) to all nodes in the
routing domain. This results in updating an existing LSA or flushing
an existing LSA. Removing an LSA from the (TE) Link State DataBase
(TE LSDB) can be accomplished in OSPF by prematurely aging the LSA.
The LSA is re-flooded with an LSA age equal to MaxAge. Each node
receiving an existing LSA with MaxAge removes it from its link state
database.
Also, the usage of OSPF implies each LSA must be refreshed
periodically (when the LSA age field reaches the LSRefreshTime, see
[RFC-2328]) to avoid age timeout and removal from the link state
database. This periodical LSA flooding and processing applies
particularly to the TE link capability sub-TLVs defined in this
document since their variation period is expected to be much larger
than the LSRefreshTime.
An Opaque LSA has a length field of 16 bits indicating the length of
the LSA, including the header. Thus, the length of OSPF packets can
be up to 65535 octets (including the IP header). Moreover, an OSPF
packet can contain several (Opaque) LSAs. OSPF relies if necessary
on the IP fragmentation to transmit large packets without any loss
of functionality. However this is not recommended and it is
suggested to split packets that are too large into several smaller
packets.
Therefore, the proposed SRLG sub-TLVs defined in this document (and
included in the top level TE Link TLV) MUST not exceed the maximum
OSPF packet size. This limits the number of SRLG identifiers that a
sub-TLV can include to approximately 125 (also this number largely
D.Papadimitriou et al. - Expires April 2003 13
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
depends on the other sub-TLVs included in the corresponding TE LSA
constraining to take for the sake of this application a conservative
approach).
6.2 IS-IS Scalability Considerations
TBD.
7. Compatibility Considerations
7.1 OSPF Compatibility Considerations
There should be no interoperability issues with GMPLS-capable nodes
that do not implement the proposed SRLG extensions since the sub-
TLVs proposed in this document is optional and thus will be silently
ignored.
The result of having such nodes that do not implement the proposed
SRLG extensions is largely detailed in this memo. However, SRLG
constraint paths can still be calculated using the SRLG sub-TLVs as
proposed in [GMPLS-OSPF].
The present memo mandates these sub-TLVs to be mutually exclusive
i.e. they MUST never appear simultaneously as sub-TLV of the same
top level Link TLV [OSPF].
7.2 IS-IS Compatibility Considerations
TBD.
8. Security Considerations
Security considerations related to SRLG and related applications are
left for further study.
9. References
[CROCH] O.Crochat, J.-Y. Le Boudec and O. Gerstel, "Protection
Interoperability for WDM Optical Networks", IEEE/ACM
Transactions on Networking, Vol. 8, No. 3, June 2000,
pp. 384-395.
[IEEE-ORL] J.Strand et al., æIssues for Routing in the Optical
LayerÆ, IEEE Communication Magazine, Volume 39, Number
2, FebÆ01.
[GMPLS-ISIS] K.Kompella et al., æISIS Extensions in Support of
Generalized MPLSÆ, Internet Draft, Work in Progress,
draft-ietf-isis-gmpls-extensions-14.txt.
[GMPLS-OSPF] K.Kompella et al., æOSPF Extensions in Support of
Generalized MPLSÆ, Internet Draft, Work in Progress,
draft-ietf-ccamp-ospf-gmpls-extensions-08.txt.
D.Papadimitriou et al. - Expires April 2003 14
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
[GMPLS-RTG] K.Kompella et al., æRouting Extensions in Support of
Generalized MPLS,Æ Internet Draft, Work in Progress,
draft-ietf-ccamp-gmpls-routing-05.txt.
[IPO-FRM] J.Luciani et al., æIP over Optical Networks A
FrameworkÆ, Internet Draft, Work in progress, draft-
ietf-ipo-framework-03.txt.
[IPO-IMP] J.Strand et al., æImpairments And Other Constraints On
Optical Layer RoutingÆ, Internet Draft, Work in
progress, draft-ietf-ipo-impairments-02.txt.
[MPLS-BDL] K.Kompella et al., æLink Bundling in MPLS Traffic
EngineeringÆ, Internet Draft, Work in progress, draft-
ietf-mpls-bundle-04.txt.
[OSPF-TE] D.Katz, D.Yeung and K.Kompella, ôTraffic Engineering
Extensions to OSPFö, draft-katz-yeung-ospf-traffic-
08.txt, Internet Draft, Work in Progress.
[RFC-2328] J.Moy, RFC 2328, ôOSPF Version 2ö, STD 54, IETF
Standard Track, April 1998.
[RFC-2370] R.Coltun, RFC 2370, Standard Track, "The OSPF Opaque
LSA Option", July 1998.
10. Acknowledgments
The authors would like to thank Bernard Sales, Emmanuel Desmet and
Gert Grammel for their constructive comments, David Griffith for its
active contribution and Bart Rousseau for its revision efforts.
11. Author's Addresses
Dimitri Papadimitriou (Editor)
Francis Wellesplein, 1
B-2018 Antwerpen, Belgium
Phone: +32 3 240-8491
Email: dimitri.papadimitriou@alcatel.be
Fabrice Poppe (Alcatel)
Francis Wellesplein, 1
B-2018 Antwerpen, Belgium
Phone: +32 3 240-8006
Email: fabrice.poppe@alcatel.be
Jim Jones (Alcatel)
3400 W. Plano Parkway,
Plano, TX 75075, USA
Phone: +1 972 519-2744
Email: jim.d.jones@alcatel.com
D.Papadimitriou et al. - Expires April 2003 15
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
Senthil Venkatachalam (OPNet)
Email: svenkatachalam@opnet.com
Sudheer Dharanikota (Consulting)
Email: sudheer@ieee.org
Raj Jain (Nayna Networks)
157 Topaz St.,
Milpitas, CA 95035, USA
Phone: +1 408 956-8000X309
Email: raj@nayna.com
Riad Hartani (Caspian Networks)
170 Baytech Drive,
San Jose, CA 95134, USA
Phone: +1 408 382-5216
Email: riad@caspiannetworks.com
Yong Xue (WorldCom)
Ashburn, VA, USA
Phone: +1 703 886-5358
Email: yong.xue@wcom.com
Appendix A: SRLG Computational Model
A.1 SRLG Concept and Example
The present model is intended to be used to automate the discovery
of the Shared Risk Link Groups (SRLGs) at a given layer for a given
physical resource type.
Note that a typical resource type can be a fiber, a fiber sub-
segment, a fiber segment or a fiber trunk. SRLG definition and
properties were described in Section 3.
Example:
The following example referring to Figure 5 (for the physical
network topology) offers some clarification. Let assume that
- N1, N2, N3, and N4 represent locations that are linked by the
fiber sub-segments,
- A, B, C, D and E be fiber segments,
- and F1 (ACD), F2 (AB), F3 (BCD) and F4 (DE) are fiber links routed
over the fiber segment topology.
N1 N2
| |
| | F1
|A |D N1 ------------ N2
| | | |
| | | |
| C | | |
D.Papadimitriou et al. - Expires April 2003 16
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
x-------------x |F2 |F4
| | | |
| | | |
| | | F3 |
|B |E N3 ------------ N4
| |
| |
N3 N4
Figure 4. Correlation between Fiber segment and Fiber link topology
In such a physical topology the obvious SRLGs are the following:
- {F1, F2} both going down when segment A breaks
- {F1, F3} both going down when segment C breaks
- {F1, F4} both going down when segment D breaks
- {F2, F3} both going down when segment B breaks
- {F3, F4} both going down when segment E breaks
These five SRLGs can be replaced by two SRLGs, S1 = {F1, F2, F3} and
S2 = {F1, F3, F4}, where S1 and S2 constitute the minimum edge
covering with cliques of the Shared Risk Relationship (SRR) graph
that can be drawn between F1, F2, F3, F4 (see Figure 5). A clique of
a graph G is a sub-graph of G in which every two nodes are connected
by an edge. This decomposition is unique. If there was an additional
dependency between F2 and F4, there would be a unique SRLG, S = {F1,
F2, F3, F4}.
F1 ------- F4
| \ |
| \ |
| \ |
| \ |
| \ |
| \ |
| \ |
F2 ------- F3
Figure 5. SRR Graph between fiber link and segment
Although R1 = F1-F2-F3 and R2 = F4 are diverse path between
locations N2 and N4 in the fiber topology (link and node
disjointness), they are not diverse with respect to SRLGs. This is
because both R1 and R2 cover SRLG S2, which contains F1, F3 (part of
R1) and F4 (part of R2). SRLGs are thus a way of formalizing the
propagation of (link-based) risk dependencies from server to client
layers.
The rules guiding the definition of minimum set of SRLGs for more
complex physical network topologies will be addressed in a future
version of this document.
A.2 Risk Type
D.Papadimitriou et al. - Expires April 2003 17
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
As specified up to now, the current approach considers that each of
the network resource may experience one or more failure type(s). The
same applies to geographical locations: a given location might
experience one or more failure types. Moreover, by applying the SRLG
properties, a network resource failure can potentially cover more
than one geographical location. Consequently, some heuristics must
be introduced to keep the SRLG computational complexity limited.
In order to limit the computational complexity, we define the
following heuristics when considering the SRLG computation with
respect to the type of risk:
1. The set of risk types associated to network resources corresponds
exactly to the set of resource type failure.
- So, for instance, the risk type associated to a fiber segment
is a fiber segment failure. The same principle applies for
other network resources such as fiber link, fiber sub-segment
and fiber trunk. Consequently, the current approach does not
consider a finest granularity for the network resource failure
than the one referred by their type.
2. A risk type associated to a geographical structure covers exactly
the region where it is defined. Moreover, a geographical failure
is limited to a given location and does not contaminate the
neighboring locations or generate another failure
- For instance, we consider that an earthquake covers exactly
one region or one area and that such a failure does not
generate a hurricane impacting the neighboring locations. So,
there is no correlation between geographical failures.
3. Each of the network resources covers exactly one geographical
logical structure.
- Consequently, when a geographical failure occurs, it
generates a failure impacting the entire network resources
included within the corresponding location. Hence, there is
an ON/OFF relationship between geographical and network
resource failures.
Consequently, when considering network resources, the risk type
associated to an SRLG is defined as the potential failure of one (or
more than one) instance belonging to a given resource type or the
potential failure of any of its hierarchical resource dependence.
Thus, we define the concept of SRLG with respect to a given resource
type and subsequently to the Risk Type (RT) to which this resource
type refers. Moreover, for a given resource type (or class), each of
the resources are identified by a Resource Identifier (RID). Since
each of these resource classes corresponds to an SRLG class, we can
assign an identifier to each of the SRLG classes members and define
their value as the SRLG identifier.
Moreover, by applying the defined heuristics above, the SRLG
identifiers can be grouped together by taking into account their
D.Papadimitriou et al. - Expires April 2003 18
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
geographical location. The latter is encoded by identifying the
region identifier (region ID) including the resource identifiers to
which the SRLG refers.
A.3 Calculation of Shared Risk Link Groups
In the calculation method, shared-risk(RID i, RID j, RT) is TRUE
only if the resource identifiers RID i and RID j belong to the same
SRLG with respect to the risk type RT. The risk types considered
here are related the fiber segment, the fiber sub-segment and the
fiber link risk failure.
A recursive calculation of shared-risk proceeds as follows:
shared-risk(RID i, RID j, RT) =
at-risk(RID i, RT)
and at-risk(RID j, RT)
and (RID i = RID j
or (exists RID k, RID l
such that
depends-on(RID i, RID k)
and depends-on(RID j, RID l)
and shared-risk(RID k, RID l, RT)))
In this calculation:
- at-risk(RID i, RT) is TRUE only if RID is susceptible to a risk of
type RT, either directly, or indirectly, through the failure of
one of the resources it depends on.
- depends-on(RID i, RID j) is TRUE only if RID i fails as soon as
RID j fails.
If we refer to the example detailed in section 1.1, then shared-
risk(F1, F2, [fiber segment failure]) = TRUE because depends-on(F1,
A) = TRUE, depends-on(F2, A) = TRUE and at-risk(A, [fiber segment
failure]) = TRUE, the latter simply because A is a fiber segment.
A.4 Practical Method for SRLG Calculation
The recursive formula presented in the previous section does not
directly lead to an efficient algorithm. ItÆs top-down nature
illustrates nicely the recursive nature of the SRLG concept, but the
calculation of the SRLGs in a top-down fashion would be totally
inefficient, entailing the calculation of the same SRLGs in lower
network layers over and over again.
A more efficient algorithm can be obtained from a bottom-up
calculation. Figure 6 illustrates this by using the example we
introduced in the Section A.1 and in by introducing the concept of
Shared Risk Relationship Graph (SRR) which defines the membership of
a resource belonging to the same SRLG.
F1 ---------- F4
D.Papadimitriou et al. - Expires April 2003 19
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
| \ ^ |
| \ | |
| \ | | Fiber SRR Graph
--->| \ | |<---
| | \ | | | where F1=ACD, F2=AB, F3=BCE, F4=DE
| | ^\ | | |
| | | \| | |
| | | | | |
| | | |\ | |
| | | | \ | |
| F2 ----|--|-- F3 |
| ^ | | |
| | | | |
+++++++++++++++++++++++++++++
| | | | |
| | | | |
--- A | | -- D |
| | |
| | |
| C | Fiber Segment SRR Graph
| |
| |
B -- E ---
Figure 6. Bottom-up calculation of Shared Risk Relationships
For the calculation of a set of SRLGs, we need to calculate a Shared
Risk Relationship (SRR) graph. The bottom-up calculation of the
fiber SRR graph proceeds as follows:
- Step 1. For each fiber segment, there is an SRR between every two
fibers contained in that segment (vertical arrows in Figure 6.)
- Step 2. For every SRR between two fiber segments, there is an SRR
between every two fibers contained in either of the two fiber
segments.
In the previous example, there are no SRRs between fiber segments,
and the calculation stops after Step 1.
A.5 Application of the Model
The model is intended to be used to automate the discovery of the
SRLGs at a given layer for a given risk type (RT).
The dependencies may be confined to one layer, e.g. the dependency
of an optical link on a node (for instance, a DWDM system) to which
it is connected, when the RT = [Node failure]. Dependencies may also
extend over layer boundaries, e.g. the dependency of a TDM circuit
(or sub-channel) in an SDH network established by using an optical
channel (or wavelength) through the optical network that is the
server layer of the SDH network, when RT = [fiber failure].
D.Papadimitriou et al. - Expires April 2003 20
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
Let two optical network resources RID i and RID j within the same
layer share a common risk of type RT. Let this risk type be tied to
a lower layer, referred to as the risk layer. To enable this layer
to infer shared-risk(RID i, RID j, RT), its server layer should
advertise the following information:
shared-risk(component_1, component_2, RT)
where component_1 are services of the server layer on which RID i
relies and component_2 are services of the serving layer on which
RID j relies, respectively.
If the server layer is not the risk layer, the latter has to infer
this knowledge from what its server layer is advertising. If shared
risk relationships are not advertised, client layers should at least
be able to query from their server layer the shared risk
relationships between the services they receive.
Some dependencies do not lend themselves easily to automatic
discovery. For instance, it is hardly imaginable that the process of
finding out through which fiber segments a fiber goes can be
automated. This means that part of the image of depends-on (RID i,
RID j) will have to be provided æmanuallyÆ by the operator or be at
least statically configured into a centralized repository.
More formally, an efficient calculation of shared risk link
relationships relies on two things:
- In the lowest network layer with elements susceptible to the risk
type RT that is considered, every network element RID j
susceptible to the risk RT constitutes an SRR on its own, that is,
(RID j, RID j) satisfies the recursive formula;
- Every SRR that has been discovered in one network layer leads to
SRRs in the next higher network layer. In particular, two next
higher layer network elements (RID i, RID j) depending on lower
layer network elements that have an SRR satisfy the recursive
formula. In order to allow an efficient calculation of the shared
risk relationships in the next higher layer (e.g. the fiber
layer), the shared risk relationships that were discovered in
lower layers (e.g. the fiber segment layer) are stored in SRR
graphs. This way, the recalculation of lower layer shared risk
relationships can be avoided.
D.Papadimitriou et al. - Expires April 2003 21
draft-papadimitriou-ccamp-srlg-processing-01.txt November 2002
Full Copyright Statement
"Copyright (C) The Internet Society (date). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph
are included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."
D.Papadimitriou et al. - Expires April 2003 22