Internet Working Group D. Papadimitriou
Internet Draft F. Poppe
Document: draft-many-inference-srlg-01.txt J. Jones
Category: Internet Draft S. Venkatachalam
Expires: January 2002 Alcatel
S. Dharanikota
R. Jain
Nayna Networks
R. Hartani
Caspian Networks
D. Griffith
NIST
Yong Xue
UUNet
July 2001
Inference of Shared Risk Link Groups
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026 except that the right to
produce derivative works is not granted.
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.
D.Papadimitriou et al. - Expires January 2002 1
draft-many-inference-srlg-01.txt July 2001
Abstract
The Shared Risk Link Group (SRLG) concept introduced in [IPO-Frame]
is considered as one of the most important criteria concerning the
constrained-based path computation of optical channel routes. By
applying the SRLG constraint criteria to the constrained-based path
computation, one can select a route taking into account resource and
logical structure disjointness that implies a lower probability of
simultaneous lightpath failure. This contribution describes the
various physical and logical resource types considered in the SRLG
concept. The proposed model focuses on the inference of SRLG
information between the network physical layers as well as logical
structures such as geographical locations. 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 SRLG concept when considering the
disjointness of the constraint-based path computation for optical
channel routes. In optical domains this concept of SRLG is used for
deriving a path, which is disjoint from the physical resource and
logical topology point-of-view. The SRLG concept and the
corresponding requirements have already been described in [IPO-OLCP]
while considering physical network topology and associated risks.
Within 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 sent 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 as described
in [GMPLS-OSPF] and [GMPLS-ISIS] does not provide:
1. The relationship between logical structures or physical resources
For example, a fiber could be part of a sequence of fiber
segments, which is included in a given geographical region.
2. The risk assessment during path computation implying the
allocation of a conditional failure probabilities with the SRLGs
3. The analysis of the specifications of constraint-based path
computation and path re-optimization taking SRLG information into
account.
The model described in this document proposes 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
D.Papadimitriou et al. - Expires January 2002 2
draft-many-inference-srlg-01.txt July 2001
these resources on the resources belonging to lower physical layers.
The result of the computation also enables to determine the risk
associated to each of the SRLGs.
The remainder of this memo is organized as follows. In section 3, we
present the hierarchical model of the resources and the
corresponding SRLG encoding. In section 4, we discuss the use of
such a model for the risk assessment for the path computation.
Future work is proposed in section 5, which is followed by
references in section 6. Appendix 1 provides an elaborate discussion
on the inference of SRLGs.
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].
3. Hierarchical Model
The model described in this proposal includes two hierarchies
defined as follows:
- Physical hierarchy, which is related to the fiber topology (more
generally the physical resources) of the optical network including
the wavelengths built on top of this physical topology.
- Logical hierarchy, which is related to the geographical topology
of the network.
Between these two hierarchies, the nodes such as Optical Cross-
Connect (OXC) and Photonic Cross-Connect (PXC) constitute the
boundary layer. Each of these concepts is elaborated in the
following sections.
The encoding of the SRLG could be either mapped on this hierarchical
model or simply use a flat encoding scheme. Both methods seam
feasible. Difference between both approaches relies on the extended
usage of the SRLGs 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 (i.e. the SRLG Sub-TLV), as described in
[GMPLS-OSPF] and [GMPLS-ISIS] is associated with the link to which
this link belongs (i.e. the SRLG Sub-TLV is defined as a Sub-TLV of
the 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 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 that an
hierarchical encoding (since depending on the physical layer which
is by definition static) needs an additional mapping structure in
D.Papadimitriou et al. - Expires January 2002 3
draft-many-inference-srlg-01.txt July 2001
order to keep the relationship with link identifiers. Nevertheless,
the computational model developed in Appendix 1 does not depend on
the encoding scheme.
3.1 Physical Hierarchy (or Network Resource Hierarchy)
The network (physical) resource model considered in the inference of
the Shared Risk Link Groups (SRLGs) is based on concepts detailed in
[IPO-FRAME] and [IPO-OLCP]. The concepts around network resource
hierarchy developed within this document are based on the following
definitions:
- Sub-Channel: a dedicated container included within a given channel
uniquely identifies a sub-channel
- Channel (or wavelength): a channel is uniquely identified by a
dedicated wavelength (i.e. lambda)
- Fiber Link: a fiber connects two node ports communicating through
one optical channel or more than one optical channel if the node
interfaces support Wavelength Division Multiplexing (WDM).
- Fiber Sub-segment: grouping of several fiber links forms a fiber
sub-segment.
- Fiber Segment: a fiber segment includes a collection of fiber sub-
segments.
- Fiber Trunks: a fiber trunk is a sequence of fiber segments,
including one or more fiber segments starting and terminating at
the same node.
The model developed extends the definition given within [IPO-OLCP]
and [IPO-FRAME] by enabling æfiber topologyÆ non-limited to point-
to-point node connections. Physical resources considered within this
model are a common denominator of most Optical Transport Network
(OTN) environments.
As represented in Figure 1, the fiber trunk from the location N1 to
the location N3 is composed by the fiber segments A and B and the
fiber trunk from the location N1 to the location N2 includes the
fiber segment A, C and D.
Location N1 Location N3
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
---------------------------------------------------------------
=== . . . ====== Fiber Fiber ====== . . ====
=== . . . ====== Fiber Fiber ====== . . . ====
--------------------------------------------------------------
Sub-Segment A[1] Sub-Segment B[1]
------------------------------ -----------------------------
=== . . . ====== Fiber | | Fiber ====== . . . ====
=== . . . ====== Fiber | | Fiber ====== . . . ====
------------------------- | | -------------------------
+++++++++++++++++++++++++ | | | | +++++++++++++++++++++++++
Segment A + | | | | + Segment B
+ | | | | +
+ | | | | +
D.Papadimitriou et al. - Expires January 2002 4
draft-many-inference-srlg-01.txt July 2001
+ | | | | + Segment C
+ | | | | +
+ | | | | +
Segment D + | | | | + Segment E
+++++++++++++++++++++++++ | | | | +++++++++++++++++++++++++
------------------------- | | -------------------------
=== . . . ====== Fiber | | Fiber ====== . . . ====
=== . . . ====== Fiber | | Fiber ====== . . . ====
------------------------------ ------------------------------
Sub-Segment D[1] Sub-Segment E[1]
---------------------------------------------------------------
=== . . . ====== Fiber Fiber ====== . . . ====
=== . . . ====== Fiber Fiber ====== . . . ====
---------------------------------------------------------------
Sub-Segment D[n] Sub-Segment E[n]
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Location N2 Location N4
Figure 1. An example for the 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 N2 to location N4
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 N1 to location N2 includes the fiber sub-segments A[n],
C[1] and D[1].
3.2 Geographical Hierarchy (or Logical Hierarchy)
Concerning the geographical hierarchy, the SRLG model developed in
this document, includes the following definitions going from the
less to the most extended logical structure partitioning of the area
covered by the optical network (as shown in Figure 2.)
- Node: a node is a single device or active element included within
the optical network; a node could be an Optical Cross-Connect
(OXC) or a Photonic Cross-Connect (PXC). Exit points of a node are
defined as the node ports.
- Zone: a zone includes one or more nodes whose location is limited
to a confined area for the sake of maintainability. Zones have a
fixed number of exit points and are non-overlapping meaning that a
given node belongs to only one zone.
- Region: a region includes one or more zones whose location covers
the individual locations of each of the area composing this
region. Regions have a fixed number of exit points and are non-
overlapping meaning that a given zone belongs to only one region.
D.Papadimitriou et al. - Expires January 2002 5
draft-many-inference-srlg-01.txt July 2001
Hence, a region could include one or more than one non-overlapping
zone each of these zones could include one or generally more than
one node.
+---------------------------------------------------------------+
| Region 2 |
| +--------------------------+ +---------------------------+ |
| | | | Zone 2 | |
| | | | +----------+ +----------+ | |
| | | | | | | A----B | | |
| | Region 1 | | | Zone 1 | | | | | | |
| | | | | | | C----D | | |
| | | | +----------+ +----------+ | |
| | | | | |
| +--------------------------+ +---------------------------+ |
| |
| +---------------------------+ |
| | | |
| | +----------+ +----------+ | |
| | | | | | | |
| | | Zone 3 | | Zone 4 | | |
| | | | | | | |
| | +----------+ +----------+ | |
| | Region 3 | |
| +---------------------------+ |
| |
+---------------------------------------------------------------+
Figure 2. An example for the logical topology
Note: A zone could correspond to an IGP area such as an OSPF area,
and a region to an OSPF Autonomous System (or BGP Autonomous
Systems). However, the model does not exclude network topologies
where the SRLG geographical hierarchy does not map the routing
hierarchical topology.
3.3 Hierarchical SRLG encoding
The objective of the hierarchical encoding is to achieve aggregation
(i.e. summarization) of the SRLG Identifiers at the boundary of
geographical structures defined logically on top of the 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.
Consequently, the detailed encoding of an SRLG includes:
1. SRLG Location (32-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
D.Papadimitriou et al. - Expires January 2002 6
draft-many-inference-srlg-01.txt July 2001
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Region ID | Zone ID | Reserved (16-bit) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The SRLG Location field identifies the logical structure into which
the common resource(s) defining the SRLG are included. For
simplicity, we say that the SRLG Location field identifies the
location of the SRLG.
The Location field includes the Region ID (8-bit) which identifies a
Region and the Zone ID (8-bit) identifying a Zone belonging to this
Region.
2. SRLG Identifier (32-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 | Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Within the SRLG Identifier, the Type field defines the resource type
(i.e. the ôlinkö type) to which the Identifier defined as a 24-bit
integer value. The following resource types (i.e. ôlinkö type) are
currently defined:
Type Value
----------------- -----
Reserved 0x00
Fiber Trunk 0x01
Fiber Segment 0x02
Fiber Sub-segment 0x03
Fiber Link 0x04
Logical resources such as optical channels and TDM circuits (or
optical sub-channels) can be also defined as described in Section 3:
Type Value
------------------- -----
Optical Channel 0x05
Optical Sub-Channel 0x06
Since a given resource (for instance a fiber link) can belong to
more than one SRLG, the SRLG Identifier structure is defined in the
most general case as a list of SRLG Identifier (n x 32-bit):
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 | Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
D.Papadimitriou et al. - Expires January 2002 7
draft-many-inference-srlg-01.txt July 2001
/ ... /
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Therefore, though we propose a linear encoding, the summarization of
the SRLG (at the logical structure boundaries) is still possible
since the SRLG identifiers are structured as follows:
- An SRLG Location field (32 bits): Region (8 bits) + Zone (8
bits) + Unspecified (16 bits)
- An SRLG Identifier field (32 bits): Type (8 bits) +
Identifier (24 bits)
This encoding enables one to perform summarization at the boundaries
of logical structures defining the spatial coverage of an SRLG
Identifier List while overcoming the drawbacks of full hierarchical
encoding scheme.
Note: the proposed encoding does not include the conditional failure
probability as defined in section 4.2
4. Risk Assessment
Risk assessment is defined as the quantification process of the
potential risk associated to the inclusion of a given resource (this
resource belongs to a given resource type located within a given
logical structure such as a geographical location) in a given
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 % (well known 5
9s) of availability or equally a down time less than X minutes per
year.
- Request a high-protection for a portion of the traffic (at the
expense of more charging) compared to other low-priority traffic.
Such requirements will be translated into path specific request.
Such path specific request 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. These
requirements are typically the logical and physical diversity as
mentioned in the hierarchical encoding section (see section 3).
2. Path characterization requirements
D.Papadimitriou et al. - Expires January 2002 8
draft-many-inference-srlg-01.txt July 2001
Path characterization requirements typically dictate the protection
mechanisms as specified by the client connection request. This can
be achieved in the form of optical ringed protection, meshed
protection mechanisms, or combination of both linear and ringed
protection. However, these are out of the scope of this document.
The components that need formalization in this example are:
- Step 1. Specification of the user requirements (such as the
example above)
- Step 2. Configuring the network that helps in assessing the
features such as the availability
- Step 3. Propagating the above-configured information.
- Step 4. Using 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 remainder of this
document.
As an example for this discussion we elaborate on the risk
assessment for a selected path.
4.2 Quantifying the Risk Assessment
Risk (the complementary of availability) assessment is defined as
the evaluation of the potential risk associated to the inclusion of
a specific resource (this resource belongs to a given resource type
located within a given logical structure such as a geographical
location) in a given path.
Given that an SRLG Identifier list is used to encode the group of
logical or physical resources, if a mechanism is devised to assign
the risk associated with the corresponding resource, we can
calculate the availability of the corresponding path. This, in order
to meet the connection availability as requested by the client.
A simple approach is to assign the conditional failure probability
with each of the SRLG Identifier. This information can be encoded as
an optional parameter along with the SRLG information as defined in
Section 3.3. In addition, weights can be associated to each of the
SRLG to either increase or decrease the potential usage of the
resource (i.e. inclusion into the selected route).
In this approach the configurable parameters are:
- SRLG Resource and SRLG Location Identifiers
- Conditional failure probability per SRLG
- Weight for the selection of the SRLG
As mentioned above, the resource failure probability is defined as a
conditional probability. For instance, we can associate a
conditional failure probability of 25% to any fiber sub-segment
located within the same zone. It means that by selecting two (or
more than two) different optical channel routes including the same
D.Papadimitriou et al. - Expires January 2002 9
draft-many-inference-srlg-01.txt July 2001
SRLG identifier with respect to fiber sub-segment failure, if one of
these lightpaths fails, then the probability that the other
lightpath fails is 25%.
Moreover, the failure probability of a fiber can also depend on the
zone into which the fiber is located as well as the length of the
fiber. In addition, a fiber can pass across different zones with
different failure probabilities. In this case, we need to consider
an aggregated failure probability per fiber taking into account each
of the failure probability of the sub-components.
For instance, if we refer to our previous example and by considering
that:
1. a conditional failure probability of 50% is associated to any
fiber link
2. a conditional failure probability of 1% to any fiber segment
located within the same zone
Then by selecting two different optical channels included within the
same SRLG with respect to fiber segment failure (S1, for instance),
we obtain a simultaneous lightpath failure probability of 1%.
Consequently, if the client asks for a protected path, by choosing
fiber segment path disjointness, the simultaneous lightpath failure
probability is also of 1%. However, choose two optical channels
flowing through the same fiber (r1, for instance), then we have a
probability of 50% that both optical channels fail simultaneously.
4.3 Risk Assessment Application
Up to now we didnÆt define the association between the high
availability of the path and SRLG conditional failure probability. A
simple way to define the relationship is to consider the
availability of the service requested by the client (i.e. a working
and a protected path from the provider point of view) and
conditional failure probability of the sequence of physical resource
elements included within the corresponding paths. So if we consider,
1. a path whose source is located is zone 1 and whose destination in
zone 2 (same region)
2. a conditional failure probability of 1% if fiber links are
selected within the same fiber trunk (and located within the zone
1)
3. a conditional failure probability of 1% if fiber links are
selected within the same fiber trunk (and located within the zone
2)
4. the conditional failure probabilities are independent and
weighted equally
Then, the availability of the service concerning the fiber link
availability is of 98% since in this specific case conditional
failure probabilities are additive.
Note that currently, the initial conditional failure probability
value need to be statically encoded; however, based on the ôhistoryö
of the failures these values could be dynamically re-evaluated. The
D.Papadimitriou et al. - Expires January 2002 10
draft-many-inference-srlg-01.txt July 2001
corresponding mechanism still needs to be specified and left for
further study.
5. SRLG Inference Model Application
The SRLG Inference Model applications are related to the CSPF
lightpath route computation and the SRLG identifier sets
summarization in order to enable intra- and inter-area diverse
routing. For that purpose we first extend the SRLG concept for
logical resources such as optical channels and optical sub-channels
(i.e. TDM circuits).
5.1 Extension of the SRLG Concept to Logical Structures and Resources
The SRLG concept can be extended to logical-level structures and
resources by taking into account the following purposes:
1. Given the physical and geographical-level decomposition of the
optical network topology, the SRLG encoding can be hierarchically
structured. The hierarchical encoding helps in constructing the
logical-level topological abstraction, which in turn can be used
in the SRLG summarization and loose-path computation. The link
semantics could be also extended to accommodate the inter-region
and inter-zonal links.
2. Propagate these additional logical-level (structures and
resources) links using the IGP routing protocols for intra- and
inter-area routing purposes.
3. To reduce the amount of the flooded information and hence
lightpath route computation complexity, the flooding scope of the
information propagation is extended to accommodate logical
structures (i.e. region and zone) and logical resources (i.e.
optical channels and TDM circuits).
5.2 Propagation SRLG Information
The SRLG of each link (i.e. physical and logical resources) is
encoded as described in Section 3.3, and this information is
propagated once at configuration between the various nodes using the
traffic engineering extensions to the IGP routing protocols such as
OSPF [GMPLS-OSPF] and IS-IS [GMPLS-ISIS]. After this initial SRLG
identifier exchange, corresponding values do not change over the
time.
This propagation of SRLG information will be necessary whenever a
new link is added or an existing link is removed. Initially the
probability of failure of the various resources are assumed to be
configured; it is envisioned that at some later time, the
probability of failure of the SRLG will be propagated along with the
SRLG itself (as described in Section 3.3).
D.Papadimitriou et al. - Expires January 2002 11
draft-many-inference-srlg-01.txt July 2001
5.3 Bottom-Up Computation of the SRR Relations
Once the traffic-engineering topological information is received by
the node, the Shared Risk Relationship (SRR) graph can be calculated
on a regular basis, using the bottom up method described in Appendix
1.4. The fiber trunk SRR is used to compute the fiber segment SRR,
which in turn is then used to compute the fiber sub-segment SRR
until the fiber SRR computation is achieved. To the SRR which
defines the membership of a resource belonging to the same SRLG set,
we associate at each resource level (for instance, with this fiber
SRR), the conditional failure probability between two elements
belonging to this level (for instance, between two fibers).
5.4 Summarization in Topology and Resource Distribution
By combining recursively several dependency graphs of known
structures into a higher-level dependency graph, the number of SRLG
sets and the number of element they include can be further reduced
(i.e. the SRLG identifier information is aggregated). Consequently,
the applications of the extended model will also cover the reduction
of the SRLG advertisements in the Topology and Resource Distribution
running instance (i.e. the traffic engineering extensions to the
link-state advertisements of the IGP protocol). In turn, this
improvement will reduce the CSPF algorithm complexity for optical
channel path calculation (i.e. engineered lightpath setup).
5.5 CSPF Route Computation
Applications of this model are directly related to the Constraint-
based Shortest Path First (CSPF) algorithm used for lightpath route
computation (i.e. traffic-engineered lightpath creation) to maximize
the lightpath disjointness and so decrease their common failure
probability. Given an existing set of lightpaths across the network,
the objective is thus to compute a route across the optical network
topology for a newly requested lightpath such that this lightpath is
diversely routed from a given set of existing lightpaths.
The diversity requirement is a routing constraint, and is expressed
as the conditional failure probability of a requested lightpath with
respect to the failure of an existing (set of) lightpath. Hence, in
addition to the other traffic-engineering constraints, the diversity
constraint requires that the conditional failure probability not
exceed a given threshold. Therefore, the CSPF algorithm needs to be
updated to take the routing diversity constraint into account.
Moreover, the SRLG concept generates another dimension to the
existing constraint-based path computation methods traditionally
used in MPLS (or PNNI) based hierarchical networks. The SRLG
constraints provide an additional dimension to the common traffic-
engineering constraints such as bandwidth availability, link metrics
and other parameters. The routing diversity constraint specificity
requires the use of more appropriate path computation algorithms
that provide not only complete multi-path disjointness but also
D.Papadimitriou et al. - Expires January 2002 12
draft-many-inference-srlg-01.txt July 2001
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
restoration strategies.
6. Security Considerations
Security considerations related to SRLG Inference model and its
applications are left for further study.
7. References
1. [GMPLS-OSPF] K.Kompella et al., æOSPF Extensions in Support of
Generalized MPLSÆ, Internet Draft, Work in Progress, draft-kompella-
ospf-gmpls-extensions-01.txt, February 2001.
2. [GMPLS-ISIS] K.Kompella et al., æISIS Extensions in Support of
Generalized MPLSÆ, Internet Draft, Work in Progress, draft-ietf-
isis-gmpls-extensions-01.txt, February 2001.
3. [IEEE-ORL] John Strand et al., æIssues for Routing in the Optical
LayerÆ, IEEE Communication Magazine, Volume 39, Number 2, February
2001.
4. [IPO-BUNDLE] B. Rajagopalan et al., æLink Bundling in Optical
NetworksÆ, Internet Draft, Work in progress, draft-rs-optical-
bundling-01.txt, October 2000.
5. [IPO-FRAME] J. Luciani et al., æIP over Optical Networks A
FrameworkÆ, Internet Draft, Work in progress, draft-many-ip-optical-
framework-03.txt, March 2001.
6. [IPO-OLCP] J. Strand, A.Chiu et al., æImpairments And Other
Constraints On Optical Layer RoutingÆ, Internet Draft, Work in
progress, draft-ietf-ipo-impairments-00.txt, April 2001.
7. [MPLS-BUNDLE] K.Kompella et al., æLink Bundling in MPLS Traffic
EngineeringÆ, Internet Draft, Work in progress, draft-kompella-mpls-
bundle-05.txt, March 2001.
8. Acknowledgments
The authors would like to thank Bernard Sales, Emmanuel Desmet, Hans
De Neve, Fabrice Poppe and Gert Grammel for their constructive
comments and input.
9. Author's Addresses
Dimitri Papadimitriou (Editor)
Alcatel IPO NSG-NA
Francis Wellesplein, 1
B-2018 Antwerpen, Belgium
Phone: +32 3 240-8491
D.Papadimitriou et al. - Expires January 2002 13
draft-many-inference-srlg-01.txt July 2001
Email: dimitri.papadimitriou@alcatel.be
Fabrice Poppe
Alcatel IPO-NSG
Francis Wellesplein, 1
B-2018 Antwerpen, Belgium
Phone: +32 3 240-8006
Email: fabrice.poppe@alcatel.be
Jim Jones
Alcatel TND-USA
3400 W. Plano Parkway,
Plano, TX 75075, USA
Phone: +1 972 519-2744
Email: jim.d.jones1@usa.alcatel.com
Senthil Venkatachalam
Alcatel CID-USA
45195 Business Court, Suite 400
Dulles, VA 20166, USA
Phone: +1 703 654-8635
Email: senthil.venkatachalam@usa.alcatel.com
Sudheer Dharanikota
Nayna Networks
157 Topaz St.,
Milpitas, CA 95035, USA
Phone: +1 408 956-8000X357
Email: sudheer@nayna.com
Raj Jain
Nayna Networks
157 Topaz St.,
Milpitas, CA 95035, USA
Phone: +1 408 956-8000X309
Email: raj@nayna.com
David W. Griffith
Advanced Network Technologies Division
National Institute of Standards and Technology (NIST)
100 Bureau Drive, Stop 8920
Gaithersburg, MD 20899-8920, USA
Phone: +1 301 975-3512
Email: david.griffith@nist.gov
Riad Hartani
Caspian Networks
170 Baytech Drive,
San Jose, CA 95134, USA
Phone: +1 408 382-5216
Email: riad@caspiannetworks.com
Yong Xue
D.Papadimitriou et al. - Expires January 2002 14
draft-many-inference-srlg-01.txt July 2001
Global Network Architecture
UUNET/WorldCom
Ashburn, VA, USA
Phone: +1 703 886-5358
Email: yxue@uu.net
D.Papadimitriou et al. - Expires January 2002 15
draft-many-inference-srlg-01.txt July 2001
Appendix 1: SRLG Inference Model
This appendix describes in detail the concept of SRLG.
1.1 Definition of the 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. This resource type could be located within a
given region and zone.
Note that a typical resource type can be a fiber, a fiber sub-
segment, a fiber segment or a fiber trunk and a typical resource
location can be a zone, a region or a node. For a given resource
type, when the resource location is not specified, the resource
location is limited to the nodes.
Definitions and assumptions:
- An SRLG is a set of links sharing a common physical resource i.e.
a common risk.
- The set of links said to belong to the same SRLG, if they are
established over fibers that go through the same fiber sub-
segments (so through the same fiber trunk) and through the same
fiber segment between two nodes.
- A lightpath is defined to cover an SRLG iff (if and only if) it
crosses one of the links belonging to that SRLG.
- Two lightpaths are defined as diverse with respect to a set of
SRLGs iff the sets of SRLGs they cover are disjoint.
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 fibers routed over
the fiber segment topology.
N1 N2
| |
| | F1
|A |D N1 ------------ N2
| | | |
| | | |
| C | | |
x-------------x |F2 |F4
| | | |
| | | |
| | | F3 |
|B |E N3 ------------ N4
D.Papadimitriou et al. - Expires January 2002 16
draft-many-inference-srlg-01.txt July 2001
| |
| |
N3 N4
Figure 4. A Correlation between Fiber segment topology 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 (note: A clique of a graph G is a sub-graph of
G in which every two nodes are connected by an edge) of the Shared
Risk Relationship (SRR) graph that can be drawn between F1, F2, F3,
F4 (see Figure 5). This decomposition is unique. If there was a
dependency between r2 and r4, there would be a unique SRLG, S = {F1,
F2, F3, F4}.
F1 ------- F4
| \ |
| \ |
| \ |
| \ |
| \ |
| \ |
| \ |
F2 ------- F3
Figure 5. SRR Graph between Fiber link and (shared) Fiber segment
failure risk relationship
Although R1 = F1-F2-F3 and R2 = F4 are diverse lightpath routes
between N2 and N4 in the fiber topology (link and node
disjointness), they are not diverse with respect to the SRLGs,
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 risk dependencies from server layers 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 study.
1.2 Rationale for the Model
We define the routing diversity requirement of a lightpath as the
SRLG Inclusion Set (SIS) of all the lightpaths from which a given
lightpath must be physically diverse. When client layers implement
D.Papadimitriou et al. - Expires January 2002 17
draft-many-inference-srlg-01.txt July 2001
their own recovery mechanism, they may not want to request protected
lightpaths (for instance, a client could only request unprotected
lightpaths from the optical network). However, the client may
request that some of these unprotected lightpaths be diverse
throughout the optical network, such that corresponding links in the
client layer topology do not fail together or at least, are unlikely
to fail together.
The SLRG Inclusion Set (SIS) of a lightpath is defined as the set of
SRLGs covered by this lightpath. As mentioned in before, routing
diversity could be related to the following physical optical network
resources:
- Optical network element (not considered in this document)
- Fiber link
- Fiber sub-segment
- Fiber segment
- Fiber trunk
The resource identifiers (Resource ID) corresponding to the optical
network resources can be defined by considering a hierarchical
encoding:
- Optical device: Node ID
- Fiber link: Identified by a Fiber ID (and a Fiber ID û Port ID
mapping table)
- Fiber sub-segment: Identified by a Fiber Sub-segment ID
- Fiber segment: List of fiber sub-segments included within the same
segment; coded as Fiber Segment ID
- Fiber trunk: Sequence of fiber sub-segments connecting two nodes
1.2.1 Lightpath Creation
When a client node sends a lightpath create request to the boundary
node, it can only reference lightpath(s) from which the new
lightpath j should be diverse. This because we assume that the
client only knows about the lightpaths it has already established.
The purpose is to avoid the set of SRLGs contained in the SISs of
lightpath 1, lightpath 2, ..., lightpath N when routing lightpath j.
The node will process this request by considering the Shared Risk
Link Groups (SRLGs) of the lightpath 1, lightpath 2, ..., lightpath
N and find a physical route for the lightpath j whose SIS does not
contain any of the SRLGs covered by the lightpath 1, lightpath 2,
..., lightpath N. Consequently, the SIS of the lightpath j could be
represented as the union of the SIS of the lightpaths from which the
lightpath j has to be diverse.
Each of the physical resources included within the optical network
could be allocated to a lightpath. Consequently, there is a
corresponding list of lightpaths sharing a common resource
identified by a resource type and a resource ID that could be
represented as a resource allocation array:
D.Papadimitriou et al. - Expires January 2002 18
draft-many-inference-srlg-01.txt July 2001
[<<RT 1; RID 1> ; <LPSet[1,1]>>
<<RT 1; RID 2> ; <LPSet[1,2]>>
...
<<RT 1; RID N[1]> ; <LPSet[1,n]>>
...
<<RT 2; RID 1> ; <LPSet[2,1]>>
<<RT 2; RID 2> ; <LPSet[2,2]>>
...
<<RT 2; RID N[2]> ; <LPSet[2,n]>>
...
...
<<RT M; RID 1> ; <LPSet[m,1]>>
<<RT M; RID 2> ; <LPSet[m,2]>>
...
<<RT M; RID N[M]> ; <LPSet[m,n]>>]
where
- RT: Resource Type (such as Fiber, Fiber sub-segment, Fiber
segment, Fiber trunk)
- RID: Resource Identifier for a given RT.
- LPSet[i,j] := Set of Lightpaths covering a RT i having a RID j
Since each of these lightpath sets shares a common resource each of
these resources constitutes a shared risk. Hence, in the optical
channel layer, the corresponding lightpath sets constitutes an SRLG
for a given (RT, RID) pair.
If we consider the fiber set allocated to the optical network
topology, then there is a corresponding list of fibers sharing a
common resource and identified by a (RT, RID), as illustrated below:
[<<RT 1; RID 1> ; <FLSet[1,1]>>
<<RT 1; RID 2> ; <FLSet[1,2]>>
...
<<RT 1; RID N[1]> ; <FLSet[1,n]>>
...
<<RT 2; RID 1> ; <FLSet[2,1]>>
<<RT 2; RID 2> ; <FLSet[2,2]>>
...
<<RT 2; RID N[2]> ; <FLSet[2,n]>>
...
...
<<RT M; RID 1> ; <FLSet[m,1]>>
<<RT M; RID 2> ; <FLSet[m,2]>>
...
<<RT M; RID N[M]> ; <FLSet[m,n]>>]
where
- FLSet[i, j] := Set of Fiber Links covering a RT i having a RID j
In this case, each of these fiber sets shares a common resource
meaning that each of these resources constitutes a shared risk Hence
in the physical layer, the corresponding fiber sets constitutes an
D.Papadimitriou et al. - Expires January 2002 19
draft-many-inference-srlg-01.txt July 2001
SRLG for a given (RT, RID) pair. Note that this discussion including
the one related to the LPSet does not include the logical structure
to which a resource belongs.
Consequently, the routing diversity of a lightpath X (so, extendedly
the SRLG Inclusion Set of a lightpath X will be defined as the
corresponding complement) can be represented as the list of all the
resources covered by all the lightpaths from which this lightpath X
has to be physically diverse from (i.e. the set of resources that
must not be used the lightpath X):
[<<RT 1>; <RID 1, RID 2, ..., RID K>>
<<RT 2>; <RID 1, RID 2, ..., RID L>>
...
<<RT N>; <RID 1, RID 2, ..., RID M>>]
This means exclude lightpath X from:
- RT 1 is identified by excluding <RID1,..., RID K>
- RT 2 is identified by excluding <RID1,..., RID L>
- ...
- and RT N is identified by excluding <RID1,..., RID M>.
However, this interpretation does not permit to find the
relationship between logical structures or physical resources: for
instance a fiber is included in a fiber sub-segment, which is
included in a fiber segment. Moreover, several lightpaths can be
included within the same fiber (or link). As defined in [IPO-FRAME],
the notable characteristic of SRLGs is that a given link could
belong to more than one SRLG, and two links belonging to a given
SRLG may individually belong to two other SRLGs. The algorithm
described in the section 1.4, propose a method to dynamically
discover these relationships.
As specified up to now, the SRLG model specification considers that
each of the resource (as used in the lightpath computation) may
experience one or more failure type(s). The same applies to
geographical locations - a given location might be subjected to more
than one failure type. Moreover, by applying the SRLG properties, a
network resource failure could 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
D.Papadimitriou et al. - Expires January 2002 20
draft-many-inference-srlg-01.txt July 2001
and fiber trunk. Consequently, we donÆt 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 impact the
neighboring locations or generate another geographical failure
type.
- 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 (defined by a region ID or a zone ID).
- 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 of the resource belonging to a given
resource type or the potential failure of one (or more than one)
instance of the resource depending on one (or more than one) of the
instance of this given resource.
In the previous section, we defined the concept of SRLG with respect
to a given resource type (and by extension to the risk type to which
this resource type refers) and a given resource identifier by means
of the lightpath and fiber set concept. This definition can be
extended to include the fiber sub-segment and fiber segment set
concept. Since each instance of these sets corresponds to an SRLG
class, we assign an identifier to each of the SRLG classes members
and define this value as a SRLG identifier.
Moreover, by applying the defined heuristics above, the SRLG
identifiers can be grouped together by taking into account their
geographical location. The latter is encoded by identifying the
region identifier (region ID) and the zone identifier (zone ID)
including the resource identifiers to which the SRLG refers.
1.3 Calculation of Shared Risk Link Groups
In the calculation method, shared_risk(RID i, RID j, RT)is TRUE only
if RID i and RID j belong to the same SRLG with respect to the type
of risk (RT). The risk types considered here are related the fiber
trunk, the fiber segment, the fiber sub-segment and the fiber link
risk failure.
D.Papadimitriou et al. - Expires January 2002 21
draft-many-inference-srlg-01.txt July 2001
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 elements 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(r2, A) = TRUE and at_risk(A,
[fiber segment failure]) = TRUE (the latter simply because A is a
fiber segment).
1.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 far more efficient algorithm can be obtained by a bottom-up
calculation. Figure 6 illustrates this by using the example we
introduced in the section 1.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
| \ ^ |
| \ | |
| \ | | Fiber SRR Graph
--->| \ | |<---
| | \ | | | where F1=ACD, F2=AB, F3=BCE, F4=DE
| | ^\ | | |
| | | \| | |
| | | | | |
| | | |\ | |
| | | | \ | |
| F2 ----|--|-- F3 |
D.Papadimitriou et al. - Expires January 2002 22
draft-many-inference-srlg-01.txt July 2001
| ^ | | |
| | | | |
+++++++++++++++++++++++++++++
| | | | |
| | | | |
--- 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.
1.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 end-system) to
which it is connected, when the RT = [Node failure]. Dependencies
may also extend over layer boundaries, e.g. the dependency of an TDM
circuit in an SDH network established on an optical channel (or
wavelength) through the optical network that is the server of the
SDH network, when RT = [fiber failure].
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, which we will call the risk layer. To enable the
layer to infer shared_risk(RID i, RID j, RT), its serving layer
should advertise the following information:
shared_risk(component_1, component_2, RT)
where:
- component_1 are services of the serving layer on which RID i
D.Papadimitriou et al. - Expires January 2002 23
draft-many-inference-srlg-01.txt July 2001
rely and
- component_2 are services of the serving layer on which RID j
rely.
If the serving layer is not the risk layer, the latter has to infer
this knowledge itself from what its serving layer is advertising.
If shared risk relationships are not advertised, client layers
should at least be able to query from their serving 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.
1.6 Generalized SRLG Inference Model
By referring to the example provided in the section 1.1, we can
deduce the following statements:
- First, given a physical network, we must assign in the optical
network the fibers to fiber sub-segments (this is usually trivial
since a fiber sub-segment will correspond to a fiber bundle), and
we must (less trivially) assign fiber sub-segments to fiber
segments.
- Then, given a physical network, every fiber sub-segment that is
connected to a location Ni must belong to a common fiber segment.
However one can argue that a location should be allowed to have
multiple fiber segments connected to it. Consider for instance the
D.Papadimitriou et al. - Expires January 2002 24
draft-many-inference-srlg-01.txt July 2001
example of a central office in a SDH/SONET network, which may be
connected to a metro ring and a local access ring or a linear
cascade of nodes. We can represent such a facility by a location
vertex that is connected to four fiber segments in the two-ring case
(two segments associated with each ring). A logistical issue is how
the network will know that a particular section of a fiber bundle
belongs to a particular fiber segment.
1.6.1 Connectivity Graph
So in the general case, any network at the fiber segment level can
be represented as a graph G([N,X], S), where N is the set of
vertices that correspond to locations set N {N1, N2, ... , Nn}, X is
the set of vertices that are not locations but are meeting points
for fiber segments (we call these vertices {X1, X2, ... , Xm}), and
S is the set of fiber segments {S1, S2, ... , Sp}.
Similarly, the network can be represented by a fiber connectivity
graph C(N,F), where the set N is equal to the set N in the fiber
segment graph above, and the set F is the set of edges indicating
fiber connectivity between the elements of the set N. Specifically,
an edge Fi exists between two vertices Ni and Nj if and only if
there exists at least one direct fiber link connection between the
two locations corresponding to Ni and Nj. Furthermore, we can say
that for every edge {Ni, Nj} in C(N,F), there is a walk that can be
represented as a path {Ni, Xa1, Xa2, ... , Xak, Nj} or equivalently
as a trail {Sa1, Sa2, ... , Sa(k+1)} in G([N,X],S), where {Sa1, Sa2,
... , Sa(k+1)} is the trail of fiber segments (the fiber trunk) that
connects Ni to Nj, and that every such walk corresponds to a fiber
trunk that connects the two locations.
F1
N1 ------------ N2
| |
| |
| |
|F2 |F4
| |
| |
| F3 |
N3 ------------ N4
Figure 7. Connectivity Graph C(N,F)
However, it is important to note that not every path in G([N,X],S)
of the form {Ni, Xa1, Xa2, ... , Xak, Nj} maps to an edge in C(N,
F). There must be a corresponding edge in C(N,F) to obtain such a
mapping. When referring to the above example, {N1, X1, X2, N4} is a
path from N1 to N4 whose only members that are elements of N are its
endpoints, but there is no direct connection between N1 and N4, as
can be seen from the connectivity graph C(N,F).
D.Papadimitriou et al. - Expires January 2002 25
draft-many-inference-srlg-01.txt July 2001
1.6.2 Shared Risk Relationship (SRR) Graph
In order to construct the SRR graph, we need to find a way to
combine the information in C(N,F) and G([N,X],S) to form a new
graph, H(F,E) that defines the Shared Risk Relationship (SRR). In
this new graph, the members of the connectivity graph C(N,F) edge
set become the vertices of the SRR graph, while the edge set in
H(F,E), E, is formed from subsets of the fiber segments set S.
We can perform this by using the following algorithm:
1. From the nodes of C(N,F) using the elements of F from the
connectivity graph C.
2. Examine each pair of nodes Fi and Fj in F. Each element of F is
associated with a set of element of S, the fiber segment set. For
instance, in the above example, if the intersection of Fi and Fj
is not empty, create an edge connection Fi and Fj and associate
it with the set Fi (union) Fj. Using the example above, the
elements, the elements of F are the following:
- F1 = {A, C, D}
- F2 = {A, B}
- F3 = {B, C, E}
- F4 = {D, E}
Taking all possible intersections of these sets enables us to
construct the SRR graph H(F,E) as shown here below:
D
F1 ------------ F4
| \ |
| \ |
| \ |
|A \ C |E
| \ |
| \ |
| B \ |
F2 ------------ F3
Figure 8. Shared Risk Relationship Graph H(F,E)
In addition, if there are any fiber segments that are not contained
in the union over the set of all pairwise intersections of elements
of F, these should be added to the SRR graph H(F,E). The formal
criteria for identifying these fiber segments, is as follows: a
segment Si is a non-overlapped segment if it is not a member of:
(union) Fi (intersect) Fj
i,j
D.Papadimitriou et al. - Expires January 2002 26
draft-many-inference-srlg-01.txt July 2001
For each segment Si that meets the above criteria, add an edge to
the SRR graph H(F,E) using the following procedure. Find the node
that corresponds to the fiber path that contains Si. Attach a loop
to the node and label it Si.
3. Form the set of first-tier SRLGs by first taking the set of all
edges of the graph H(F,E). Next examine the vertices of H(F,E).
If there are any elements of any of the FiÆs that are not
contained in the set of first-tier SRLGs, add these elements to
the set as well.
4. A second-tier set of SRLGs can be developed by forming a
covering of H(F,E). A simple way to do this is to require that
the covering be composed using cliques. (A clique is a sub-graph
in which every vertex is connected to every other vertex and
there are no loops or multiple connections between any vertex
pairs.) The SRLG associated with a clique is the union of the set
of fiber segments that are associated with the edges of the
clique.
Each element of S defines an arc in G([N,X],S), rather than an edge,
since in the general case we cannot assume that the existence of a
connection between two nodes in a given direction implies the
existence of a connection between those two nodes in the other
direction.
In the example that we have considered, each arc in the SRR graph
has only one fiber segment associated with it, but this does not
have to be the case in general. Consider the network shown in
Figure 9. In this case we also have five distinct fiber segments,
but the topology gives us the graphs G([N,X],S) and C(N,F) as shown
in Figure 10(a) and Figure 10(b), respectively. When we form the
SRR graph, we get H(R,E) as shown in Figure 11. Note that in this
case the intersection of fiber paths F2 = {S1, S3, S4} and F3 =
{S2, S3, S4} yields the set {S3, S4}, which is the SRLG associated
with those two fiber paths because the loss of either fiber segment
s3 or segment S4 will result in the disruption of traffic on both
fiber paths.
To obtain the full set of first-tier SRLGs for the network in Figure
9, we first examine the edges of the SRR graph in Figure 11 are S1,
S2, {S3, S4}, and S4. Examining the vertices of the SRR graph
reveals that we must add S5 to the list of first-tier SRLGs as well
(S5 is an SRLG unto itself). There are two cliques that are sub-
graphs of the SRR graph; these give us the second-tier SRLGs {S1,
S2, S3, S4} and {S3, S4, s5}.
xxxxxx xxxxxx
N1 ---x----x-----------------x----x--- N2
---x----x----- -----x----x---
xxxxxx | | xxxxxx
S1 | | S2
xxxxxxxxx
D.Papadimitriou et al. - Expires January 2002 27
draft-many-inference-srlg-01.txt July 2001
S3 x| |x
xxxxxxxxx
| |
| | xxxxxx
| -----x----x---
-----------x----x--- N3
--------x----x---
| xxxxxx
xxxxx S4
S5 x | x
xxxxx
|
N4
Figure 9. A second example of network topology.
Note that fiber paths {S1, S3, S4} and {S2, S3, S4} can be broken by
the loss of fiber segment S3 or fiber segment S4.
The following figures represent the graphs G([N,X],S) and C(N,F)
for the network topology defined by Figure 9.
S1 S2 F1
N1 ------ X1 ------ N2 N1 --------------- N2
| | /
| | /
| | /
| | /
| S3 F2 | / F3
| | /
| | /
| | /
| | /
N3 ------ X2 ------ N4 N3 --------------- N4
S4 S5 F4
(a) (b)
Figure 10. G([N,X],S) and C(N,F)
In Figure 10(b), the FiÆs (i.e. the fiber paths) are defined as
follows:
- F1 = {S1, S2}
- F2 = {S1, S3, S4}
- F3 = {S2, S3, S4}
- F4 = {S4, S5}
s5
---
/ \
\ /
\ /
D.Papadimitriou et al. - Expires January 2002 28
draft-many-inference-srlg-01.txt July 2001
{S4,öS5ö} V S4 {S2,S3,S4}
O------------------O
| /|
| / |
| {S3,S4} / |
| / |
S4 | / | S2
| / |
| / |
| / |
| / |
O------------------O
{S1,S3,S4} S1 {S1,S2}
Figure 11. The SRR graph H(F,E) for the network in Fig. 9.
Then we consider the case where fiber segments are not terminated at
intermediate nodes. An example of this would be a ring network
where certain fibers are not attached to local add-drop multiplexers
at a given station because none of the traffic that they are
carrying needs to be groomed at that node. An example network is
shown in Figure 12.
+----+
------| N1 |-------
| +----+ |
xxxxx xxxxx
S3 x | x x | x S2
xxxxx xxxxx
| |
+----+ | +----+
| N2 | | | N3 |
+----+ | +----+
| | |
| xxxxxxxxx
xxxxx +----+ x | | x
S4 x | x | N4 |----x- | x
xxxxx +----+ x | x S3
| x | x
-----------------x----- x
xxxxxxxxx
Figure 12. A ring network with fiber pass-through at some nodes.
The connections from N1 to N4 and N2 to N3 are
passed through nodes N3 and N4, respectively.
In the network in Figure 12, there are four fiber segments, as
shown, and the following three fiber paths: {S1}, {S2, S3} and
{S3, S4}. We can build a set of SRLGs for this network using the
techniques described above. However, we should note that if node
N3 experiences a catastrophic failure, this will impact two of the
three fiber paths shown. Thus it is desirable to expand the
D.Papadimitriou et al. - Expires January 2002 29
draft-many-inference-srlg-01.txt July 2001
definition of a fiber path to include traversed vertices in the set
N in addition to elements of S. If we do this, the fiber paths in
Figure 12 become {S1}, {S2, N3, S3}, and {S3, N4, S4}. The SRR graph
H(F,E) for this network is left for further study.
Finally we consider another example of this would be a network where
certain fibers are not attached to local add-drop multiplexers at a
given station because none of the traffic that they are carrying
needs to be groomed at that node. An example is shown in Figure 13.
S1 S2 S3
xxxxxx xxxxxx xxxxxx
+----+ x x +----+ x x +----+ x x +----+
| N1 |--x----x--| N2 |--x----x--| N3 |--x----x--| N4 |
+----+ x x +----+ x x +----+ x x +----+
| | x x x x | x x |
| +----x----x----------x----x----+ x x |
+------x----x----------x----x----------x----x----+
xxxxxx xxxxxx xxxxxx
Figure 13. A network with fiber pass-through at some nodes.
The connection from N1 to N4 passes through nodes
N2 and N3 without undergoing O/E/O conversion.
Likewise the connection from N1 to N3 passes
through node N2 without being terminated there.
In the network in Figure 12, there are three fiber segments, as
shown, and the following fiber paths: {S1}, {S2}, {S3}, {S1, S2},
and {S1, S2, S3}. We can build a set of SRLGs for this network using
the techniques described above. However, we should note that if
either node N2 or N3 experiences a catastrophic failure, this will
impact multiple fiber paths. Thus it is desirable to expand the
definition of a fiber path to include traversed vertices in the set
N in addition to elements of S. If we do this, the fiber paths in
Figure 13 become {S1}, {S2}, {S3}, {S1, N2, S2}, and {S1, N2, S2,
N3, S3}. The SRR graph H(F,E) for this network has the form shown in
Figure 14.
In Figure 14 we have applied the rules for constructing the SRR
graph that were discussed previously. The graph reflects the fact
that a failure at N2 will affect fiber path F4 and F5. Note also
that node N3 is represented by a loop attached to vertex F5, as that
node affects only the fiber path from N1 to N4.
F4 = {S1,N2,S2}
----------------O----------------
| | |
| | |
| S1 | S2 |
| | |
| | |
D.Papadimitriou et al. - Expires January 2002 30
draft-many-inference-srlg-01.txt July 2001
F1 = {S1} O |{S1,N2,S2} O F2 = {S2}
| | |
| | |
| S1 | S2 |
| | |
| | |
----------------O----------------
/ / \ F5 = {S1,N2,S2,N3,S3}
F3 = {S3} O------------ / \
S3 / \
-------
N3
Figure 14. SRR graph for the network in Figure 13.
D.Papadimitriou et al. - Expires January 2002 31
draft-many-inference-srlg-01.txt July 2001
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 January 2002 32