OSPF extensions for flexible CSPF algorithm support
draft-satish-ospf-cspf-support-00

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.

Authors

Satish Jamadagni

(Note: The e-mail addresses provided for the authors of this Internet-Draft may no longer be valid.)