Internet Draft Satish Jamadagni Expires March 2003 Praveen C H Informational Sasken Communication Technologies Ltd October 2002 OSPF extensions for flexible CSPF algorithm support draft-satish-ospf-cspf-support-00 1. Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of [RFC-2026]. 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. 2. Abstract The fundamental problem of Constrained Shortest Path First (CSPF) computation which is typical of quality of service routing, is that the problem is NP-hard. While standard approximation methods exist, their complexity may often be prohibitive in terms of scalability. Recently pre-computation and caching techniques have been suggested [3] [4] to achieve better on-demand computation costs. The motivation for pre- computation and path caching is to reduce as much of the on-demand computational overhead as possible. To fully utilize Pre-computation and caching of QoS paths at a source, mechanisms should be available to verify the validity of either the full or a partial subset of the pre-computed paths. The mechanisms should preferably support verification of the consistency of either partial or the full pre-computed path cache. In an IP control plane, CSPF is expected to work in conjunction with OSPF-TE [1] and RSVP-TE [2] protocols. To support CSPF algorithms that might want to use pre-computation and caching techniques rooted at a source or an identified core in the network, we propose mechanisms to dynamically setup OSPF "virtual links" and describe setting up of "virtual areas" to enable OSPF based selective network monitoring and updation. Such an extension will help deploy flexible CSPF algorithms that might be distributed, partially distributed or utilize pre-computation or caching techniques. Satish et al [Page 1] Internet Draft OSPF extensions for CSPF support Oct 2002 3. 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]. 4. Introduction Constrained Shortest Path First algorithms are NP-hard. While standard approximation methods exist [6], their complexity may still be prohibitive in terms of scalability. To achieve better on-demand computational cost as well as scalability, distributed, semi distributed or CSPF methods which utilize pre-computation and caching techniques [2] [3] [7] could be possible implementation options. The idea behind pre-computation and path caching is to avoid as much of on-demand computation as possible. To achieve distributed, semi distributed CSPF implementations along with support for Pre-computation and caching of QoS paths at a source, protocol support in terms of being able to update or maintain partial or full QoS path consistency specific to individual paths or small regions of a network topology is essential. This article assumes OSPF link-state explicit routing architecture. Link state routing protocols use reliable flooding to exchange link state information, enabling all routers to construct the same link state database (LSDB). Given complete topological information and the state of resource availability, each router finds the least costly path that still satisfies the resource requirements of a flow. To support distributed, semi distributed QOS path computation algorithms along with pre-computation and QoS constrained paths rooted at a source or at a core, we propose extending the "virtual link" mechanism described in RFC 2328 to enable dynamic setting up of a virtual link. This helps in a source (supporting pre-computation CSPF mechanism) setting up virtual neighbors to maintain QoS paths specific to selective sub-regions of a pre-computed QoS cache. Dynamic setup of virtual paths helps enable realize different classes of CSPF implementations namely, distributed, semi distributed implementations with pre-computation and caching support. Provision to dynamically setup and teardown virtual links helps a source node to designate core nodes, which help in partial fast topology or LS database updates. The source node running the CSPF algorithm identifies and contacts those partial list of nodes for its link state update. It is predicted that much of the CSPF and OSPF functionalities will have to be tightly coupled in future QOS networks. The exact details of CSPF algorithms and implementation methodologies are not the subject of this draft. Satish et al [Page 2] Internet Draft OSPF extensions for CSPF support Oct 2002 Dynamic virtual link setup helps in a source node setting up virtual neighbors to maintain QoS paths specific to selective sub-regions of a topology graph. This draft focuses on dynamic Virtual link provisioning in OSPF. 5. OSPF support for flexible CSPF algorithms QoS based routing algorithms use network state information to determine a path with the given performance conditions. Because the network state information is highly dynamic, the precision of the state information will depend on the distance from the source of the state information i.e. further from a source node; less precise will be the state information. Localizing state information would lead to non-information about far off nodes. Typical IP control planes for optical network end- to-end QoS provisioning can span a few thousand kilometers. Regular OSPF flooding to maintain network can cause scalability problems. Also this would not help in the maintenance or consistency verification of pre-computed or cached CSPF paths leading to an increase in QoS path computation frequency in QoS networks. RT1(Virtual link setup requesting Source) RT2 o------------o-----------o /|\ | |\ / | \ | | \ / | \ | | \ o | o | | \ N7 o N5 | | \ N6 | | \ N4 o---------o RT3 \ / / \ / / RT10 o-------o / / N3 o-----o RT4 (Virtual link setup Target) /| / | / | RT5 o o RT6 / | / | / | N2 o o N1 Figure 1: A source rooted tree, identifying RT4 for selective probing and possible forwarding functions In the diagram above a dynamic virtual link setup between RT1 and RT4 allows selective probing by RT1 of RT4 neighbors. RT4 can also act as a core for RT1's destinations that are beyond RT4. Satish et al [Page 3] Internet Draft OSPF extensions for CSPF support Oct 2002 Two additional functionalities to existing OSPF functionalities are needed to support flexible and distributed CSPF algorithms, they include 1. Dynamic virtual link setup and teardown to support selective probing 2. A virtual area specification to scope the selective probing +-------+ /--| | / | OSPF |-------Network / | | / +-------+ / | / | +-------+ +-------+ | | | | | CSPF |------| TED | | | | | +-------+ +-------+ TED - Traffic Engineering Database Figure 2: CSPF - OSPF interaction to setup a virtual link 5.1 Pre-computation triggers in CSPF module The CSPF algorithm update trigger module determines when to verify the local path cache. It also decides which source destination pairs in the cache to update. Based on this the CSPF module will generate local link state update triggers. There can be a variety of triggering based on policies like periodic, threshold based triggering, and class based triggering. This module might also implement a hold-down timer that enforces minimum spacing between two consecutive update triggering from the same node. Pre-computation trigger module determines when to perform QoS path pre-computation. 5.2. OSPF dynamic virtual link provisioning Currently the OSPF RFC [1] described the notion of a virtual link between two physically separate components of a backbone network. If any single backbone area is disconnected some areas of the Autonomous System will become unreachable. To establish/maintain connectivity of the backbone, virtual links can be configured through non-backbone areas. The two endpoints of a virtual link are specified to be area border routers. The virtual link must be configured in both routers with the configuration information in each router specifying the other virtual endpoint. The non-backbone area the two routers have in common is called the Transit area. Satish et al [Page 4] Internet Draft OSPF extensions for CSPF support Oct 2002 Adjacency is established between nodes at either end of the virtual link. Such an adjacency has been referred to as "virtual adjacency". Details about configuring a virtual link can be found in [1]. The OSPF virtual link functionality as described in [1] is currently manually configured. Dynamic configuration provision of virtual links between a requesting source and a target router helps CSPF applications as detailed in the previous sections. Dynamic configuration involves a source node requesting a target router to include it in its virtual link configuration. The other details concerning dynamic virtual link setup are as follows: o A virtual area or region is identified by the CSPF module. LSAs corresponding to this virtual region are summarized over virtual adjacencies during the Database Exchange process. o The cost of a virtual link will have to be computed by the CSPF module itself and maintained in its cache. This cost appears in the virtual link's corresponding routing cache entry. o Just as the virtual link's cost and viability are maintained by the CSPF pre-computation and caching process, the IP interface address for the virtual interface and the virtual neighbor's IP address are maintained by the OSPF entity. These are used when sending OSPF protocol packets over the virtual link. o In each endpoint's router-LSA, the virtual link is represented as a Type 4 link whose Link ID is set to the virtual neighbor's OSPF Router ID and whose Link Data is set to the virtual interface's IP address. o The time between link state retransmissions, requested during a dynamic configured for a virtual link should be well over the expected round-trip delay between the two routers. 6. Messages supporting dynamic virtual link setup To be able to request and setup virtual Path dynamically by other application or protocol entities (like multicast or CSPF modules) through OSPF a new OSPF message type is suggested, the virtual link setup request and response message. This is apart from the five messages supported by the ospf protocol currently. The description of the new message is presented below. Satish et al [Page 5] Internet Draft OSPF extensions for CSPF support Oct 2002 +-------+ +-------+ | | | | ------| | | | Trigger |(OSPF) | ----------------------> |(OSPF) | (CSPF) |Source | 1a. V_link_setup_Req |Target | |virtual| <---------------------- |virtual| |link | 1b. V_link_setup_Rsp |link | |node | |node | | | | | +-------+ +-------+ Figure 3: Automatic virtual link establishment Protocol 6.1 The virtual link setup message This message achieves the purpose of an initial probe and probe response message as well as act as a virtual link configuration message. The message establishes a connection with an identified target node to request for a virtual link setup. 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 | sub-Type | Packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source Area ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Target Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Checksum | AuType | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Virtual area specification | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Virtual link Configuration parameters | | | | | Satish et al [Page 6] Internet Draft OSPF extensions for CSPF support Oct 2002 The type can be '6' as five message types are already defined within ospf [1]. The sub-type field specifies whether it is a 'request' or a 'response' message. The target router ID specifies the requested virtual link endpoint. The virtual area specification is the specify geographic area or a set of routers for monitoring (LSA notifications to be sent back to the source) or can explicitly list the routers to include to form a virtual area. The virtual link configuration parameters specify the configuration details. The virtual link setup message can be routed through a tunnel or on a hop-by-hop basis depending on the tunneling support that might be available. 7. Security Considerations A configurable access control policy determines the degree to which features described herein are delivered. The access control policy requires user identification and authorization. As stated above, the new protocol must not introduce security holes nor consume excessive resources (e.g., CPU, bandwidth). It also must not be exploitable by those launching DoS attacks. 8. Conclusions Dynamic configuration of the virtual link capability defined in the OSPF RFC is suggested. This is primarily motivated by requirements for flexible limited scope probing to accommodate various possible CSPF implementations. This draft is in its preliminary version and will subsequently be enhanced to exactly specify virtual regions and possible SRLG implications. 8. References [1] Moy, J., "OSPF Version 2", RFC 2328, March 1998. [2] QoS routing mechanisms and OSPF extensions, RFC 2676, IETF, August 1999. Satish et al [Page 7] Internet Draft OSPF extensions for CSPF support Oct 2002 [3] Kia Seong Teng; Maheswaran. M, Limited scope probing: a distributed approach for QoS-based routing, IEEE International Symposium on Network Computing and Applications, 2001, Page(s): 350 -353. [4] George Apostolopoulos, Satish K. Tripathi, On Reducing the Processing Cost of On-Demand QoS Path Computation. [5] Deep Medhi, QoS Routing Computation with Path Caching: A Framework and Network Performance, IEEE communications magazine. [6] F.A. Kuipers., T. Korkmaz, M. Krunz and P. Van Mieghem, A Review of Constraint-Based Routing Algorithms. [7] Norihito Fujita and Atsushi Iwata, Adaptive and Efficient Multiple Path Pre-computation for QoS Routing Protocols, IEEE, 2001. [8] QoS Routing Mechanisms and OSPF Extensions, RFC 2676, Aug 1999 IETF. (work in progress) 9. Acknowledgements We would like to thank Soumen Sarkar for his encouragement and useful discussions. 10. Author's Addresses Satish Jamadagni Sasken Communication Technologies Ltd #139/25, Amar Jyoti Layout, Ring Road, Domlur P.O, Bangalore 560071, India Phone: +91 80 5355501 Email: satishj@sasken.com Praveen C H Sasken Communication Technologies Ltd #139/25, Amar Jyoti Layout, Ring Road, Domlur P.O, Bangalore 560071, India Phone: +91 80 5355501 Email: praveenc@sasken.com 11. Full Copyright Statement Copyright (C) The Internet Society (2002). 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 Satish et al [Page 8] Internet Draft OSPF extensions for CSPF support Oct 2002 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.