Internet DRAFT - draft-dovolsky-ccamp-ospf-limited-flooding
draft-dovolsky-ccamp-ospf-limited-flooding
CCAMP Working Group D. Dovolsky (Movaz Networks)
I. Bryskin (Movaz Networks)
D. Awduche (Isocore)
Internet Draft
Expiration Date: May 2003 November 2002
Document: draft-dovolsky-ccamp-ospf-limited-
flooding-00.txt
Limited Flooding as a scalability improvement to OSPF
draft-dovolsky-ccamp-ospf-limited-flooding-00.txt
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026 [1].
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.
Abstract
This draft describes a limited flooding approach to address the
problem of routing scalability in link state IGPs. The solution is
based on decomposition of a routing area into ôzonesö and the
restriction of the exchange of routing information between zones.
This approach introduces an extra level in the isolation of
knowledge within a routing domain. The advantage of this solution is
that it considerably decreases the amount of information flooded in
link state advertisements and reduces the size of the link-state
database (and traffic engineering entries) on network elements
utilizing link state protocols. The technique presented in this
document has been particularized to OSPF in order to make the
discussion practical and concrete. However, the underlying concepts
are very general and similar modifications can be easily applied to
other IGPs, such as ISIS.
Table Of Contents
Dovolsky, Bryskin, Awduche Expires May 2003 1
draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002
1. Summary for Sub-IP Area
1.1. Summary
This document describes a generic mechanism to enhance the
scalability of IGP routing protocols. More particularly, it
specifies extensions to the OSPF routing protocol to make the
protocol even more scalable in support of Generalized Multi-Protocol
Label Switching (GMPLS). The method described is quite general and
can be applied to other link state protocols, such as ISIS.
1.2. Where does it fit in the Picture of the Sub-IP Work
This work fits squarely in either the CCAMP or OSPF box.
1.3. Why is it Targeted at this WG
This draft is targeted at the CCAMP or the OSPF WG, because it
specifies extensions to the OSPF routing protocols in support of
GMPLS, because GMPLS is within the scope of the CCAMP WG, and
because OSPF is within the scope of the OSPF WG.
1.4. Justification
The WG should consider this document as it specifies the extensions
to the OSPF routing protocols in support of GMPLS.
2. Overview
This document proposes a method to enhance the scalability of link
state interior gateway routing protocols (IGPs). The proposed
solution is applicable to traditional link state routing protocols
such as OSPF [1]. The proposed solution is even more pertinent in
MPLS and GMPLS networks, where the IGP has been extended and
equipped with traffic engineering and GMPLS extensions.
The main idea behind the proposed approach is the reduction of a
single routing area into multiple ôzonesö and the control of routing
information between the zones. With this approach, it is no longer
the case that network elements in the same routing area will
necessarily have an identical copy of the area link state database.
An important attribute of the zone concept is that it requires
minimal modifications to the existing IGPs. Another important
attribute is that it supports asymmetric exchange of routing
information between network elements in different zones. The
proposed approach also allows to: (1) decrease the size of the link
state database on each node, (2) restrict the amount of routing
information, (3) decrease the overhead associated with flooding, and
(4) decrease the complexity of path selection.
Dovolsky, Bryskin, Awduche Expires May 2003 2
draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002
To make the discussions in this document concrete and practical, we
have used OSPF to illustrate the concepts. The solution is, however,
quite general and applies to other link state routing protocols,
such as ISIS, with very minor modifications.
2.1 Background: Scalability of Interior Gateway Routing Protocols
Context
Routing scalability is an important issue in operational networks.
This issue becomes even more acute with the advent of GMPLS, which
enables the use of IP routing protocols (after appropriate
extensions) for different types of transport networks.
The scalability of interior gateway routing protocols (IGPs) for IP
networks and other types of transport networks is a particularly
critical issue in operational networks, and is an important
requirement for major service providers. Yet, many aspects of this
issue have yet to be satisfactorily resolved. The most generic
approach to addressing the routing scalability problem is the
decomposition of a routing domain into multiple routing areas. This
approach has become an integral part of existing IGP routing
protocols such as OSPF [1]. Because the concept of routing areas by
itself is not sufficient to address all nuances of the routing
scalability problem, new improvements and workarounds have been
proposed [4, 5, 6]. The intention of virtually all of the proposed
solutions is to limit the amount of information advertised and to
limit the amount of information maintained and managed by each
routing engine on a network element.
There are many dimensions that demand consideration in attempting to
address the scalability of routing protocols. The main
manifestations of lack of scalability in routing protocols is
excessive consumption of CPU and memory resources on a network
element, and undue transaction of state information between network
elements to synchronize their routing databases. The transient
behavior of the routing protocol is another aspect that could also
have severe ramifications for scalability.
In the worst case, the impact of lack of routing protocol
scalability on the network itself can be devastating. In certain
circumstances, lack of scalability can result in severe instability
and a complete collapse of the network itself. Congestive collapse
of the routing system can also occur because of the duplication of
packet transmission inherent in the flooding mechanism [8]. In the
best case, lack of routing scalability can result in inefficient
network operation. Other manifestations of lack of routing
scalability include: long convergence time, large path computation
time, and slow forwarding time.
Path computation time is a function of the number of routes, the
size of the link-state database, the amount of traffic engineering
parameters, and the types of user preference associated with a
particular instance of the path computation process. All recently
Dovolsky, Bryskin, Awduche Expires May 2003 3
draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002
proposed solutions attempt to improve the routing scalability by
applying different algorithms to achieve one or more of the
following objectives: increase the number of SPF calculations [5],
avoid unnecessary flooding [6], restrict the database information
exchange to only traffic-engineering link-state advertisements [4],
etc.
It is important to note that the most common operational network
scenario for link state routing protocols is a single area, which
encompasses the entire network. In many modern networks (especially
those utilizing MPLS or GMPLS), the single routing area will
implement the traffic engineering extensions (for example [2]). In
such environments, the routing protocol disseminates the traditional
link state information as well as traffic engineering data and other
constraint information. Very large autonomous systems encompassing
entire continents containing only one routing area are in operation
today.
It is also important to note that the issue of multi-area traffic
engineering is an area in which the industry has not yet reached
consensus on an effective solution. As an example, the classical
approach suggested in [1] of breaking the network into multiple
areas cannot be used to good effect.
A typical service provider network is built of network elements with
different capabilities, such as computational resources and memory.
Some of them (for instance, routers installed on metro networks) may
have more resources for keeping large databases and performing fast
forwarding and path computation than the other (for instance,
routers installed on access networks).
The solution proposed in this draft is to break a single link state
routing area into ôrouting zones.ö Routers and other network
elements within the same zone maintain a synchronized topology state
database among themselves. This means that network elements within
the same zone receive full routing information (link-sate, traffic-
engineering advertisements) from each other.
2.2 The Zone Concept
The zone concept refers to a ôsoftö partitioning of a routing area
into sub-domains, which allows to control the amount of routing
information exchange between the sub-domains in the area. The zone
concept also allows to decouple the advertisement of traditional
LSAs defined in the original OSPF specification ([1]) from the
advertisement of Traffic Engineering LSAs defined in the TE and
GMPLS extensions.
The zone concept allows grouping a collection of network elements
into a ôzoneö which can be viewed as a single logical network
entity. Each zone is associated with one or more zone border routers
(ZBR). A ZBR exists at the boundary between a zone and the remainder
of the routing area exterior to the zone. That is, a ZBR has routing
IGP routing adjacencies with network elements within and outside the
Dovolsky, Bryskin, Awduche Expires May 2003 4
draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002
zone. On the other hand, we say a network element is in the
æinteriorÆ of a zone if it maintains IGP routing adjacencies with
only network elements within its zone.
We define three types of routing visibility to support the zone
concept:
(1) full visibility,
(2) limited visibility, and
(3) zero visibility.
In the following discussion, when we say a ônetwork element,ö we
mean a network element participating in the link state routing
protocol.
To fix these ideas, let us consider two zones, say zone æAÆ and zone
æBÆ. We say that network elements within zone æAÆ have ôfull
visibilityö of zone æBÆ if the network elements participating in the
link state routing protocol in zone æAÆ receive routing information
from all network elements in zone æBÆ.
We say that network elements within zone æAÆ have ôlimited
visibilityö of zone æBÆ if they receive zero routing information
from network elements in the interior of zone æBÆ, with the
exception of LSAs from one or more Zone Border Routers (ZBRs) at the
boundary between the two zones.
Lastly, we say that network elements within zone æAÆ have ôzero
visibilityö of zone B if they receive zero routing information from
any router that belongs to zone B.
As a general concept, the notion of visibility defined above is not
symmetric. Thus, it may be the case that zone æAÆ can have limited
or zero visibility of zone æBÆ, while zone æBÆ may have full
visibility of zone æAÆ.
An immediate application of this concept in IP over circuit switch
networks occurs within the context of the peer and augmented models.
In such settings, some IP routers may have limited or full
visibility into the circuit switch network, but it may not be
beneficial for the circuit switch network elements to have full
visibility into the IP network.
Note, that routers within a given zone may have full visibility of
some zones while having limited or zero visibility of other zones.
For example, in an circuit switch network utilizing GMPLS, access
network elements within an æaccess zoneÆ may have limited
visibility of a metro-area network zone and zero visibility of a
long-haul network zone, while metro-area network elements may have
full visibility of some access network zones and limited visibility
of a long-haul network zone.
This draft allows decoupling the advertisement of æregular LSAsÆ
from the advertisement of traffic engineering LSAsÆ. So that
Dovolsky, Bryskin, Awduche Expires May 2003 5
draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002
different types of visibility can be applied with respect to
advertisement of regular LSAs and traffic engineering LSAs. For
example, routers within zone æAÆ may have full visibility of zone
æBÆ with respect to regular LSA advertisements, but limited or zero
visibility with respect to traffic engineering advertisements. The
nature of routing visibility (full, limited or zero) between two
zones can be asymmetrical, as noted earlier. This important
characteristic of the zone concept is certainly worth emphasizing.
For example, routers within zone æAÆ may have limited visibility of
zone æBÆ, while routers with zone æBÆ may have full visibility of
zone æAÆ.
Routing visibility between two zones æAÆ and æBÆ is configured on
ZBR(s) that belong(s) to both zones by limiting the flooding of the
routing information of certain types (regular link-state
advertisements, traffic-engineering advertisements, or both) through
ZBR interfaces connecting zone æAÆ and zone æBÆ. ZBRs are
responsible for advertising themselves as default routes for network
elements within their zones, to support routing with zones that have
limited or zero visibility with respect to the target zone.
Transitive characteristics of zone visibility: If zone æAÆ is not
adjacent to zone æBÆ (i.e. no ZBRs in common), then we say that
network elements within zone æAÆ have full visibility of zone æBÆ if
they have full visibility of zone æCÆ, which is adjacent to zone æAÆ
and have full visibility of zone æBÆ. Otherwise, zone æAÆ has zero
visibility of zone æBÆ. This is an expression of the transitive
characteristics of zone visibility.
[---]
-------[ B ]----------
| [---] |
| |
[---]Limited Visibility [---]
[ A ] Zone1 [ C ]
[---] [---]
| [---] |
-------[ZBR]----------
-------[---]----------
| |
[---] Full Visibility [---]
[ D ] Zone [ E ]
[---] [---]
| |
| [---] |
-------[ZBR]----------
-------[---]----------
| |
[---]Limited Visibility [---]
[ E ] Zone2 [ F ]
[---] [---]
| |
| [---] |
Dovolsky, Bryskin, Awduche Expires May 2003 6
draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002
-------[ G ]----------
[---]
In the example above routers A, B, C are within Limited Visibility
Zone1. They contain full routing and traffic engineering
information about each other. However, the only information they
have about the rest of the network is the one that was generated by
the upper ZBR. Likewise, routers E, F and G are within Limited
Visibility Zone2. Routers D and E are within Full Visibility Zone.
They contain full routing and traffic engineering information about
all other routers in all zones.
The approach described in this draft is advantageous because it
allows controlling and decreasing the amount of routing information
and associated processing overhead on network elements. In some
types of network elements, it may also decrease convergence time and
boost the routing/forwarding performance. The traffic engineering
capabilities also become more scalable because constraint-based path
selection, and tunnel setup and management can be distributed
between access network elements and ZBR(s).
This approach does not require changes to the routing protocol
packet format. And it is enough to have only ZBR(s) routers
supporting this feature.
3. Proposed solution
A routing area may be divided into multiple zones by appropriately
configuring the interfaces of zone boarder routers (ZBRs). Each pair
of adjacent zones may be configured to have full or limited routing
visibility with each other. Each pair of adjacent zones may have one
or more ZBRs in common. Each ZBR in turn may have a number of
interfaces configured with one or more zone identifiers (zone IDs)
and flooding type. The flooding type indicates the type of routing
information that may be flooded across the interface. It may have
one of the following values:
. link-state advertisements only;
. traffic engineering advertisements only;
. both
The zone concept requires a slight modification to the OSPF Neighbor
state machine and flooding procedures [1]. The OSPF Neighbor state
machine defined in [1] should be amended as follows:
ô10.3. The Neighbor state machine
à
State(s): ExStart
Event: NegotiationDone
New state: Exchange
Action: The router must list the contents of its entire
area link state database in the neighbor Database summary list.
Dovolsky, Bryskin, Awduche Expires May 2003 7
draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002
If an interface associated with this neighbor is configured with
limited flooding option and one or more zone IDs, each non self-
originated link-state and/or traffic engineering database entry must
be considered for inclusion into the Database Summary List according
to the following rule:
. non self-originated database entries must be included only if
they are received from incoming interfaces that have non-zero
overlapping list of zone IDs with the interface in question;
. self-originated entries must be included regardless of the
interface in question zone IDs;
. both self-originated and non self-originated database entries
that are disallowed to be distributed over the interface in
question by its configured flooding type MUST NOT be included;
ô13.3. Next step in the flooding procedure
à
Depending upon the LSA's LS type, the LSA can be flooded out
only certain interfaces. These interfaces, defined by the
following, are called the eligible interfaces:
à
When flooding an LSA, which has just been received, each
outgoing interface must be considered on whether it is eligible
outgoing candidate or not by comparing itÆs list of configured
zone IDs with one configured for the interface the LSA has
arrived on. The interface in question must be considered as
eligible outgoing candidate if all following conditions are
true:
. it has a non-zero overlapping list of zone IDs with the
incoming interface;
. this LSA type is allowed to be flooded over the interface in
question by its configured flooding type.
In every place in the protocol implementation, where a locally
originated Router LSA is needed to be flooded to a neighbor, the
following procedure should be performed:
For interfaces configured with one or more zone IDs and limited
flooding option the Default Route stub network link (0.0.0.0/0) must
be added to locally originated Router LSA. The Router LSA header
link number, length and checksum should be updated appropriately.
As a result of the described extensions routers within a particular
zone will receive the routing information only from routers within
the same zone and from other zones, which are fully visible from the
router. They will also receive Router LSAs originated on ZBRs that
belong to the zones, which the routers have limited visibility to
(these LSAs contain Default Route stub network links identifying
default routes that point to the ZBRs). They will receive no routing
information from routers within zones with zero routing visibility.
4. Distributed Traffic Engineering across multiple zones
Dovolsky, Bryskin, Awduche Expires May 2003 8
draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002
As a consequence of the flooding type definition (see 3.) the
limited visibility of a router to a particular zone may apply to:
a) link-state information;
b) traffic engineering information;
c) both.
If the router is presented with a request to establish a traffic
engineering tunnel that should go through one or more zones with the
limited traffic engineering visibility, the path selection and
tunnel setup is performed in the distributed way. Specifically, the
originating router can define a path for the tunnel and signal the
tunnel only up to one of ZBRs of a limited visibility zone towards
the destination. Note, that routers learn about ZBRs via Default
Route stub network links (0.0.0.0/0) found in received Router LSAs.
When the setup message arrives on the ZBR, it repeats the process.
Specifically, it defines the path and signal the tunnel either to
the destination or to ZBR of next zone towards the destination
depending on whether the destination is located in the zone fully
visible from the computing ZBR or not. This process completes when
the tunnel is established.
If a router has full visibility towards the tunnel destination as
far as link-state information is concerned, but has the limited
traffic engineering visibility, it can use the full link-state
visibility while deciding which ZBR to forward the tunnel setup
message to in case he knows about more than one.
5. Topological Considerations Relating to Zones
It may be necessary to impose some topological restrictions on the
connectivity of zones within a routing area, especially for
traditional hop by hop routing. Such restrictions are necessary to
in order to avoid routing anomalies such as blackholes and routing
loops.
For getting end-to-end routing connectivity and avoiding black
holes, some central (core) zone should be configured with full
visibility. Hierarchical configured zones donÆt have to have direct
connectivity to this core zone.
6. Example Network
+--------------+
| Zone A |
+--------------+
*/LF-Z1 *\ LF-Z2
*/ *\
*/ *\
+---------+ +---------+
| Zone B | | Zone X |
| | | |
Dovolsky, Bryskin, Awduche Expires May 2003 9
draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002
+---------+ +---------+
LF-Z3 */ \ LF-Z4 LF-Z5 / *\ LF-Z6
*/ \ / *\
+--------+ +--------+ +--------+ +--------+
| Zone C | | Zone D | | Zone Y | | Zone Z |
| X | | | | | | |
+--------+ +--------+ +--------+ +--------+
The above figure provides an example topology consisting of seven
(7) zones. While not a requirement, a likely configuration of zones
will be aligned with some topological or geographic regions. For
example, zone A may map to a network backbone, zones B and X may map
to local (interconnected) POPs, and zones C, D, Y and Z may map to
separate access networks. In such a configuration, the zones could
operate in the following fashion:
. the zones C, D, Y and Z, have a limited visibility of directly
attached zones, i.e., B and X respectively;
. the zones B and X have full visibility of directly attached
zones C, D, Y and Z, while having a limited visibility of zone
A;
. zone A has a full visibility of the directly connected zones B
and X, and therefore also a full visibility of the subtending
zones C, D Y and Z (and thus, becoming a backbone zone for the
whole network)
This example network can support both standard IP forwarding as well
as MPLS Label Switch Paths (LSPs). To illustrate, consider an LSP
terminating at endpoints at zone C (router C) and zone Y (router Y).
Since, router C does not have information about router Y, it will
route the LSP to ZBR of the directly attached zone (A, router LF-
Z3). Since router LF-Z3 does not have information about router Y, it
too will route the LSP to the ZBR of the directly zone (A, router
LF-Z1). Lastly, since router LF-Z1 has full information about all
routers on the network, it calculate a complete route for remaining
portion of the LSP.
7. Compatibility Issues
There should be no interoperability issues with routers and other
network elements utilizing OSPF that do not implement this proposal.
8. Security Considerations
This document does not raise new security issues beyond those that
exist in OSPF with traffic engineering and GMPLS extensions. The
method described in this document can actually enhance security
because it can be used to block certain types of routing data from
being advertised to a subset of network elements.
9. References
Dovolsky, Bryskin, Awduche Expires May 200310
draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002
[1] Moy, J., "OSPF Version 2", RFC 2328, April 1998.
[2] Katz, D., D. Yeung and K. Kompella, "Traffic Engineering
Extensions to OSPF", work in progress.
[3] Coltun, Rob, "The OSPF Opaque LSA Option", RFC 2370, FORE
Systems, July 1998.
[4] Venkata Naidu, "OSPF TE Only Option", draft-venkata-ospf-te-
only-option-00.txt, April 2002.
[5] A. S. Maunder, G. Choudhury, "Explicit Marking and Prioritized
Treatment of Specific IGP Packets for Faster IGP Convergence and
Improved Network Scalability and Stability", <draft-ietf-ospf-
scalability-00.txt>, March, 2001.
[6] Alex Zinin, Mike Shand, "Flooding optimizations in link-state
routing protocols", <draft-ietf-ospf-isis-flood-opt-01.txt>, March
2001.
[7] Yong Xue at all, "Carrier Optical Services Requirements",
<draft-ietf-ipo-carrier-requirements-01.txt>, March, 2002.
[8] Ash et al, ôCongestion Avoidance and Control for OSPF
Networks,ÆÆ <draft-ash-manral-ospf-congestion-control-00.txt>,
April 2002.
10. Acknowledgements
The authors of this document would like to acknowledge the valuable
inputs from Lou Berger.
11. Author's Addresses
Dan Dovolsky
Movaz Networks
7926 Jones Branch Dr., Suite 615
McLean, VA 22102
Phone: (703)847-2438
Email: ddovolsky@movaz.com
Igor Bryskin
Movaz Networks
7926 Jones Branch Dr., Suite 615
McLean, VA 22102
Phone: (703)847-4208
Email: ibryskin@movaz.com
Daniel Awduche
Isocore Corporation
8201 Greensboro Drive, Suite 102
McLean, VA 22102
Phone: (703)298-5291
Email: awduche@awduche.com
