Internet Draft Bala Rajagopalan Expiration Date: July, 25, 1999 NEC USA Qingming Ma Cisco Systems January, 20, 1999 An Overlay Model for Constraint-Based Routing draft-rajagopalan-CR-overlay-00.txt Status of this Memo This document is an Internet-Draft. 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." To learn the current status of any Internet-Draft, please check the "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). ABSTRACT This draft considers an overlay model for constraint-based intra- domain routing and describes a mechanism for efficient update propagation that can be used as the basis for this model. As a specific example, the incorporation of a constraint-based routing overlay on the OSPF protocol is discussed. 1. INTRODUCTION The term "constraint-based routing" (CR) has been coined in the MPLS context to refer to the routing of virtual trunks (label switched paths) subject to their resource and performance requirements [AMAD98]. A CR scheme would take into account network resource availability and/or policy constraints while computing paths. Constraint-based routing is a rather broadly defined concept; it may include the routing of fine and coarse- [Page 1] Internet Draft draft-rajagopalan-CR-overlay-00.txt Jan, 1999 grain IP flows, flow aggregates or virtual trunks, subject to QoS or grade of service requirements. Furthermore, depending on the application, a CR scheme may take into account relatively slowly or frequently changing network state information. Thus, is a generalization of QoS-based routing [AMAD98] for which a framework has been defined [CNRS98]. In this draft, we consider an overlay architecture for intra- domain constraint-based routing. This approach is briefly discussed in [AMAD98]. In essence, this approach creates a separate CR overlay over traditional shortest-path link state (LS) routing schemes. This is illustrated in Figure 1 where CR runs as a protocol distinct from LS routing, with a local interface for interaction and a logically distinct database (in principle, the databases can be physically integrated, but this is an implementation issue). This approach differs from previously implemented QoS-based routing schemes such as QOSPF that rely on QoS enhancements to specific LS routing protocols [GWPK98, ZSSC97]. +------------------+ +------------------+ To Peers | Constraint-Based |_________| Constraint-Based | <-------| Routing Protocol| | Routing Database | +------------------+ +------------------+ \ / \ / +-----------------------+ | Topology mapping and | | other interface | | functions | +-----------------------+ | | +------------------+ +--------------+ To Peers | Intradomain LS |_______| Link State | <-----| Routing Protocol | | Database | +------------------+ +--------------+ Figure 1. Constraint Based Routing Overlay on LS Protocols The overlay approach has the following advantages: first, routing exchanges for CR can be designed independent of the underlying LS routing scheme. Second, other than a well-defined interface between the underlying LS routing scheme and the CR scheme, it is not necessary to enhance each specific LS routing scheme with QoS capabilities. Finally, the overlay model allows the efficient propagation of link and nodal state updates necessary for building [Page 2] Internet Draft draft-rajagopalan-CR-overlay-00.txt Jan, 1999 and maintaining the CR databases. Indeed, the foundation for the overlay architecture is the mechanism for CR update propagation. Unlike the flooding mechanism used in LS routing protocols (e.g., OSPF [MOY98], IS-IS [C90]), this mechanism must be efficient to improve the scalability of CR. This is especially so if state updates are generated frequently (e.g., QoS-based routing [CNRS98]). The rest of this draft describes an efficient tree- based update propagation mechanism and the interaction required between CR and LS routing to realize the overlay architecture shown in Figure 1. As a specific example, the incorporation of a CR overlay on OSPF is described. 2. OVERLAY MODEL - HIGH LEVEL The essential idea proposed in this draft is to utilize the LS routing information to build a spanning tree of the network topology to propagate link and nodal state information necessary for CR. This is shown in Figure 2. Here, a network and a broadcast tree are shown. There are many ways to construct such trees [DM78, R96], and in this example, we assume that the tree is the minimum spanning tree (MST) of the network (see Section 6 for a discussion on this topic). Update propagation along this tree would work as follows: the source of an update sends a copy along each directly attached branch. Each node receiving the update forwards it along each tree branch other than the one on which the message was received. A B A B O-----------O O-----------O |\ /| |\ | | \ / | | \ | | \ / | | \ | | \ / | | \ | | \ / | | \ | O-----O-----O O O O C D E C D E Figure 2: A network and its spanning tree With tree-based forwarding, updates are sent only along links that are part of the tree whereas with flooding a copy of an update message is transmitted on every link in the network. Thus, tree-based forwarding clearly reduces update overheads compared to flooding, especially in dense topologies. As with flooding, a problem with this scheme is how to ensure that every node has the same state information about a given link eventually, in the face of topological changes in the network. This problem is illustrated [Page 3] Internet Draft draft-rajagopalan-CR-overlay-00.txt Jan, 1999 in Figure 3. Here, node A originates an update. Before node E can receive the update, the link B - E fails. In the new tree constructed after the failure, node D is the ancestor of E, but D has already received and processed the update from A. Thus, node E does not receive the current update from A. To solve this problem, note that it is not necessary to ensure that every update is received by every node. Rather, it is adequate that the link state information at various nodes are kept synchronized most of the time, even if an individual node may occasionally not receive some updates. For instance, it is acceptable that some updates are missed by some nodes during topological changes, but the state information be synchronized shortly after the topology stabilizes, based on the most recent updates. Thus, with respect to Figure 2, node E may not receive several updates originated by node A when the new tree is being established. These loses do not matter as long as the most current information is established at E soon after the new tree is formed. This is the approach proposed in this draft (for a discussion of other work related to this proposal, please see [R96]). A B A B O-----------O O-----------O |\ | |\ | \ | | \ | \ | | \ | \ | | \ | \ | | \ O O O O O-----O C D E C D E Figure 3: Trees before and after the failure of link B-E Under this proposal, the topology information maintained by the underlying LS routing scheme is used to create the broadcast tree and recompute it after topology changes. Nodes interact only with their tree neighbors to synchronize state information after topological changes. Furthermore, updates between neighbors are sent reliably and there is no need for periodic refreshing of updates by the sources. In the absence of topological changes, this method requires much less overhead for propagating link state updates, compared to flooding. Also, as described later, there is no need for sequence numbers in update messages. This simplifies message processing and avoids the algorithmic complexity that arises in using such numbers for synchronization [BG87]. It can be shown that the [Page 4] Internet Draft draft-rajagopalan-CR-overlay-00.txt Jan, 1999 eventual synchronization of link and nodal state information is achieved at all nodes that are in the same network partition. Furthermore, convergence can be shown to be quick, occurring in time proportional to the diameter of the network partition [R96]. 3. LINK AND NODAL STATE UPDATE PROPAGATION 3.1 Local computation of the MST At each router, the topology database maintained by the underlying LS routing scheme is used to compute the MST of the topology. In this tree, the nodes and edges are exactly those found in the topology database. The MST computation requires that a cost be assigned to each edge. The cost is assigned as follows: if the underlying LS routing scheme utilizes administratively defined costs for interfaces (e.g., OSPF) then the edge cost for MST is derived from this (see Section 5.1). Otherwise, a cost of 1 is assigned to each edge. Given the topology and the edge costs, the MST algorithm is straightforward (see [GHS83] for references). When the MST computation encounters a tie situation while selecting a tree branch, a well-defined tie-breaking methodology is used thereby ensuring consistent locally computed MSTs in all routers (see Section 5.2). Once the MST is computed, a short forwarding table is created, listing all the interfaces that lead to tree neighbors. It is possible that some of these interfaces are to broadcast LANs. For each broadcast network interface, it is assumed that the addresses of all neighboring routers attached to the network are available (see Section 3.3). (Note: Although we consider the possibility of broadcast LANs, their usage in an environment where resources must be reserved seems doubtful.) 3.2 Recomputation of the MST A router evaluates if the MST must be recomputed whenever the underlying LS routing scheme receives a topology or administrative cost change update. The recomputation of the MST is triggered when the topology update indicates: - an increase in cost or the failure of a link which is part of the existing MST - a reduction in the cost of a link that is not part of the existing MST, or - the introduction of a new link [Page 5] Internet Draft draft-rajagopalan-CR-overlay-00.txt Jan, 1999 As a result of recomputation, the MST forwarding table at a router may change. If a new local interfaces has been newly added to the forwarding table then the router must synchronize its link and nodal state database with the new neighbor (see Section 3.4). Thus, recomputation of the MST can be expensive. Note that recomputation will be triggered less often if the MST is based on hop count (i.e., unit cost for links). In general, if we assume that changes in topology and administrative costs are relatively rare, then recomputation will be a relatively rare event. A special case of MST recomputation occurs when a router is started up. In this case, the computation of the MST is triggered after the underlying LS routing scheme has synchronized the topology database with its neighbors (see Section 5.3). 3.3 Transmission of updates from a router to a neighbor It is assumed that the network is unreliable, i.e., routers and links may fail unpredictably, and the transmission delay over a functioning link, while finite, is subject to fluctuations. It is further assumed that bidirectional communication is possible between neighboring routers. A router sends an update message as as a unicast packet over a point-to-point tree interface. On a broadcast LAN interface, the update is sent to a special IP multicast address whose scope is restricted to the local subnet. An update message may carry link and nodal state announcements from more than one source router. For each such announcement, the address of the originating router is indicated. Furthermore, the update message carries the address of the sending router. Reliable transmission of an update message over an interface is accomplished by requiring the sender retransmit the message until either acknowledgments are received from all neighbors or a timeout occurs. In the latter case, the interface is deemed non- functional and a new MST will be computed after the underlying LS routing scheme updates its topology database. It is assumed that update messages sent between neighbors are sequenced (e.g., utilizing a sliding window protocol for retransmissions). Each router is required to process updates from a neighbor in the same sequence as they were sent. The most recently processed update originated by a source replaces any previously written update from the same source in the database. [Page 6] Internet Draft draft-rajagopalan-CR-overlay-00.txt Jan, 1999 3.4 Database synchronization When a new interface is added to the MST forwarding table at a router, the router must synchronize its CR database with that of its new neighbor(s). If the interface is to a point-to-point link then the database synchronization is carried out with the peer at the other end. If the interface is to a broadcast subnet then the synchronization is carried out with all neighbors on the subnet. A router initiating the synchronization process utilizes its MST information to first determine the set of destinations from which it would forward updates over the newly added interface (note that since updates are forwarded over a tree, exactly one router would forward updates from a given destination on to a subnet or a link). It then collects the most recent updates from these destinations, as found in its database, and schedules them for (reliable) transmission over the new interface. If the interface is to a broadcast subnet then the updates are multicast, as described before. Each update message transmitted by the router carries a flag requesting database synchronization. Each router on the corresponding subnet (or link) that receives such an update message determines the set of destinations from which it would forward updates onto the subnet (or link). The router then reliably transmits the updates from these destinations, as found in its database, to the initiating router. On a newly established point-to-point link, one of the routers is established as the initiator of synchronization, based on some well-defined rule (e.g., comparison of router IDs). On a broadcast link, each router to which an interface is newly added becomes the synchronization initiator (in practice, it may be rare that more than one router initiates synchronization at a given time. We therefore limit our discussion to the case where exactly one router initiates sychronization at a time). The synchronization process in a broadcast subnet is illustrated in Figure 4. Here, router A is the initiator. After computing the MST based on the (synchronized topology information, Figure 4a), A determines the set of sources from which it would forward updates on to "Net" (i.e., nodes E - I). It then multicasts the most recent updates from E - I (as obtained from the upstream tree neighbor) on "Net" while requesting synchronization. In response, each neighbor on "Net" send updates to A originated by destinations from which they would forward updates onto "Net" (Figure 4b). A router that starts up will have more than one network interface. In this case, the MST is computed after the underlying LS routing scheme has completed the synchronization of the topology database over all functional interfaces. The synchronization of the CR database is done after the MST is computed. [Page 7] Internet Draft draft-rajagopalan-CR-overlay-00.txt Jan, 1999 +---+ <----------| A |\ To tree nodes +---+ \ E - I \____ / \ +---+ To tree nodes J - M * Net *---| B |-----------> \____/ +---+ / | To tree nodes +---+ / | <------------| C |/ | N - Q +---+ +---+ To tree nodes R - W | D |-------------> +---+ (Figure 4a: Spanning Tree with a Broadcast Subnet) +---+ <----------| A |\ A: Mcast updates from E - I, request sync. +---+ \ \____ B: Unicast updates from J - M to A / \ +---+ * Net *---| B |-----------> \____/ +---+ C: Unicast updates / | from N - Q to A / | D: Unicast updates from / | R - W to A +---+ +---+ <----------| C | | D |-------------> +---+ +---+ (Figure 4b: Synchronization Request from A and Responses) Figure 4: Synchronization over a Broadcast Subnet 4. THE UPDATE PROPAGATION SCHEME 4.1 Description The update propagation scheme can be summarized with reference to a specific source router that generates local link and nodal state information. The generation of such updates is driven by events which are outside the scope of this draft (e.g., changes in resource availability). [Page 8] Internet Draft draft-rajagopalan-CR-overlay-00.txt Jan, 1999 A. At the source router: I. When an update is generated: - Replace the old information in the database with the new update. - Reliably forward a copy of the update over each interface that is part of the (locally computed) MST. B. At all other routers: I. When an update is received over an interface that is part of the (locally computed) MST: - Retreive the old update from the source, if any, from the database. - If the new update is different from the old, o Replace the old update in the database with the new update. o Reliably forward a copy of the update over each tree interface other than the one over which the update was received. II. When an update is received over an interface that is not part of the MST: - Drop the update. C. At all routers: I. When the MST changes: 1. If a new interface is added to the MST forwarding table: - Generate updates for the corresponding local link and replace the old information in the database, if any, with the new updates. - Compute the set of sources whose updates will be forwarded over the new interface. - Reliably transmit the updates over the new interface, with a synchronization request flag set in each update message. [Page 9] Internet Draft draft-rajagopalan-CR-overlay-00.txt Jan, 1999 2. If some nodes in the old MST are now unreachable: - Remove the updates from these destinations from the database. II. When a synchronization request is received from a neighbor: - Compute the set of sources whose updates will be forwarded over the interface over which the request was received. - Retrieve updates from these sources from the database and send them reliably to the neighbor (Receiver will follow step B) _____________________________ Some optimizations are possible in this scheme. First, updates from several sources may be bundled in a single message between neighbors. Second, a source may send updates about all its directly attached links in each message instead of generating a separate message for each link. Finally, as described, if a node determines that an update received from a neighbor is identical to the update in its own database then it need not propagate it further. 4.2 Update propagation under hierarchical routing Constraint-based routing may involve a multilevel hierarchy. For instance, a CR overlay on OSPF would involve two-level hierarchical routing, where the hierarchy would be defined by the OSPF routing areas. The update propagation method described in Section 4.1 can easily be generalized to multilevel hierarchies. In essence, each router builds a separate MST for each hierarchical level for which the underlying LS routing scheme provides topology information. The MST for a given hierarchical level is used to propagate CR updates that the router must process at that level. What is exactly represented by the updates at a given level of the hierarchy is independent of the update propagation scheme. Further discussion of this can be found in Section 5.1. 4.3 Synchronization without sequence numbers The proposed update propagation scheme does not require update messages originaged by each source be sequenced. Flooding protocols require a monotonically increasing sequence number for each update message generated by a given source. This sequence number indicates to a router whether an update is more recent than the one it already has in its database. With tree-based forwarding, a router receives updates originated by a given [Page 10] Internet Draft draft-rajagopalan-CR-overlay-00.txt Jan, 1999 source from a specific upstream tree neighbor and the update propagation scheme guarantees that this neighbor will eventually deliver the most recent update from the source. Thus, a router always "trusts" the update received from the upstream tree neighbor and there is no need for a source to sequence the updates it generates. There is an advantage to not requiring sequence numbers in update messages. In essence, when sequence numbers can wrap around, sequence number comparisons alone cannot be used to reconcile more recent state information in one set of nodes, with stale information in others, after a long loss of connectivity between these sets of nodes [BG87]. Additional mechanisms, such as periodic refreshing of updates from the source together with update aging [PER83], or further synchronization among nodes which are not necessarily neighbors [BSS91] may be needed. Thus, even though the underlying LS routing scheme might employ sequence numbers for topology updates, this complexity is not duplicated for constraint-based routing under the present proposal. 4.4 Consistency of State Information It can be shown that the CR link and nodal state information maintained by all routers in a network partition converge to consistent values under certain standard assumptions. Furthermore, within a network partition, convergence after a topological change can be shown to be achieved quickly, in time proportional to the diameter of the partition. Interested readers are referred to [R96]. 5. CR OVERLAY ON OSPF The essential idea of the overlay model is not to require changes to the OSPF protocol itself, but a well-defined interface at each router between the OSPF protocol module and the CR module. The functionality that must be supported by such an interface is considered in this section. 5.1 The CR database The CR overlay on OSPF is a two-level hierarchical routing scheme, where the hierarchy is defined by the OSPF areas. The update propagation scheme therefore works at two levels; each router belonging to an OSPF area must compute the MST of the area topology to propagate updates within the area. Each router belonging to the OSPF backbone area must compute the MST of the backbone topology to propagate updates in the backbone. This is [Page 11] Internet Draft draft-rajagopalan-CR-overlay-00.txt Jan, 1999 shown in Figure 5. Here, each RTi is a router and Ni a subnet. Figure 5a depicts the area organization and Figure 5b the MSTs computed in each area. For the MST computation, the cost of an edge is derived as follows: an interface to a broadcast subnet is modeled as a link to the logical node that represents the subnet, with the link cost being the same as the interface cost. The cost of a point-to-point link is taken to be the average cost of the two router interfaces. In the figure, the link cost is 1 unless indicated otherwise. It can be seen from Figure 5b that even though MSTs are computed in each area an internal node in an area might receive an external update along more than one path. For instance, both RT3 and RT4 forward external updates onto N3. At the first glance, this might seem to be a problem, since the MST forwarding and synchronization algorithms rely on receiving updates from a given destination along exactly one path. But this is not really an issue for the following reason. Regardless of the update propagation method used, some well defined rule must be used within an area to select between two border routers originating updates to the same external destination. To do this, - either the border routers must run a protocol amongst themselves to elect a single router that would propagate updates from external destinations into the area, or - the update from a given external destination d propagated by a border router R1 is considered distinct from the one propagated by router R2. For instance, this method might be used let internal routers select the best border to reach an external destination based on path information both internal and external to the area. Now, the contents of the update messages propagated in any area is not of concern in this draft. Also, what information is injected by an area border router into a particular area is also outside the scope of this draft. Clearly, these details would depend on the specifics of the CR scheme and may very well differ from the manner in which OSPF works. For example, the CR routing scheme might require area border routers to propagate summarized version of external area topologies. As far as update propagation is concerned, these details are not relevant; at a router, it is sufficient to extract the appropriate information from OSPF to build the required MSTs. This is the main function of the interface between the CR and OSPF modules at a router. As described before, the CR database at a router is logically a distinct entity, containing the representation of the network topology along with associated link and nodal state information. When overlaid on OSPF, the CR database has two components: [Page 12] Internet Draft draft-rajagopalan-CR-overlay-00.txt Jan, 1999 complete topology and state information pertaining to the area(s) to which the router belongs and summarized information about external areas. For the computation of the MST(s) at a router, only the area topologies are required. As an implementation detail, the database component pertaining to the local area(s) may be physically realized at a router via enhancements to the OSPF topology database. A physically distinct database realization, on the other hand, may be designed independent of OSPF and may be used with other LS routing schemes (e.g., IS-IS). ........................... . + . . | +---+ . . N1|--|RT1|\ . . | +---+ \ . Backbone Area . + | \ ____ . . | / \ +---+ +---+ . 7| * N3 *---|RT4|------|RT5|--------+ . | \____/ +---+ +---+ | . + | / \ . \ | | . | +---+ / \ . \ | | . N2|--|RT2|/ \ . \ | | . | +---+ +---+ \+-----+ | . + \ |RT3|----| RT6 | | . 7\ +---+ +-----+ | . \ / . | | . \ / . | | . +-----------+ . | | .Area 1 N4 . | | ........................... | | +----+ +---+ ......|RT10|.....|RT7|....... . +----+ +---+ . . / \ __|_ . +----+ \ / \ . <------------|RT11| * N6 * . +----+ \____/ . . \ | . . \ +---+ . . \__________|RT8| . . 7 +---+ . . | . . | . . +--------+ . . N7 . .Area 2 . ............................. (Figure 5a: Network Topology) [Page 13] Internet Draft draft-rajagopalan-CR-overlay-00.txt Jan, 1999 ........................... . + . . | +---+ . . N1|--|RT1|\ . . | +---+ \ . Backbone Area . + \ ____ . . / \ +---+ +---+ . * N3 *---|RT4| |RT5|--------+ . \____/ +---+ +---+ | . + / \ . \ | | . | +---+ / \ . \ | | . N2|--|RT2|/ \ . \ | | . | +---+ +---+ \+-----+ | . + |RT3|----| RT6 | | . +---+ +-----+ | . / . | | . / . | | . +-----------+ . | | .Area 1 N4 . | | ........................... | | +----+ +---+ ......|RT10|.....|RT7|....... . +----+ +---+ . . / \ __|_ . +----+ \ / \ . <------------|RT11| * N6 * . +----+ \____/ . . | . . +---+ . . |RT8| . . +---+ . . | . . | . . +--------+ . . N7 . .Area 2 . ............................. (Figure 5b: MSTs in different areas) Figure 5: MSTs with OSPF A physically distinct constraint-based routing database requires the determination of the topology representation along with the format for node identifiers. This representation would be independent of the underlying LS routing protocol. A mapping function is then required to generate this topology information [Page 14] Internet Draft draft-rajagopalan-CR-overlay-00.txt Jan, 1999 from the OSPF topology information. Such a mapping function would map all physical and virtual links in the OSPF topology representation of an area onto links in the CB topology representation. The definition of the link and nodal state parameters (kept in the CR database) is outside the scope of the update propagation protocol. This protocol, however, defines the envelope for carrying the state information, i.e., the update message exchanged between CR modules at neighboring routers. The format of this message also is independent of the underlying LS routing scheme, in this case OSPF. 5.2 Computing the MST The computation of the MST is driven by the following events: - Establishment of an adjacency - Reception of an LSA by the OSPF module - Failure of a local interface The OSPF module should trigger the MST computation after each recomputation of the OSPF routing table. The MST computation is therefore triggered after the OSPF topology database is stable, i.e., after the database synchronization with a neighbor is complete. The interface between the routing modules must allow the following: 1. The triggering of the topology database mapping function after each recomputation of the OSPF routing table. 2. The triggering of MST computation for the appropriate area(s) after the topology has been mapped. Conditions under which a new MST is computed were described in Section 3.2. To evaluate whether a new MST for an area must be computed, the mapping function used in Step 1 must give an indication of which links were added/deleted from the previous topology, or whether an increase or decrease of administrative cost occurred for a previously existing link. The CR module computes the MST forwarding table after step 2. The MST algorithm must ensure that every router in an area comes up with the same MST of the area topology. This can be done by following well-defined rules to make a selection when there are multiple choices. For instance, router ids may be used as tie breaker where applicable. Following such rules, the same MST can be computed at every router as long as the topology information is consistent. When there are transient inconsistencies in topology information, inconsistent MSTs may be computed. But it can be shown that the MST information converges with the topology [R96]. [Page 15] Internet Draft draft-rajagopalan-CR-overlay-00.txt Jan, 1999 5.3 Synchronization CR database synchronization is a procedure separate from the OSPF database synchronization process. CR synchronization occurs after the OSPF synchronization process is complete. As described in Section 3.4, the CR synchronization procedure is different from OSPF procedures. Specifically, the notion of a designated router was not used in our description. Thus, after the recomputation of the MST, no OSPF-specific information is required during CR synchronization. It may be recalled that a router initiating synchronization transmits updates from all destinations that it would normally forward over the newly added interface. This would include not only destinations within the same OSPF area, but also all the external destinations for which the router received updates over other existing MST interfaces. 6. SUMMARY AND CONCLUSIONS In this draft, an overlay model for realizing constraint-based routing was discussed. Under this model, CR coexists with traditional link state routing schemes. The LS routing scheme is used to provide the topology information necessary to build spanning trees which are used for propagating link and nodal state information necessary for CR. The essential components of the update propagation scheme were described in this draft and CR overlay on OSPF was briefly discussed. A question that might arise in considering the present proposal is whether other types of spanning trees, such as source-based or centered trees can be used for update propagation. Source-based trees minimize the delay in propagating updates and they can be computed by each router from the topology information. To derive these trees, however, each router must compute shortest paths rooted at each node in the network and also store the incident branches in all such trees. This option is discussed in [R96]. An alternative is a single centered tree which minimizes the average or maximum diameter [W80]. Such a tree can also be computed from the topology information, but its computation is more complex than that of an MST. A centered tree may be considered if there is a possibility that the diameter of an MST might be large, leading to significant delays in propagating updates from some sources. In real networks with relatively dense topologies, it is possible to employ simple heuristics to generate an MST while attempting to reduce its diameter. This assumes that more than one MST is possible for the given topology, which is likely with dense topologies with similar link costs (or unit link costs). [Page 16] Internet Draft draft-rajagopalan-CR-overlay-00.txt Jan, 1999 Another question that arises with the overlay model is the utility of the underlying LS routing scheme beyond supporting the CR scheme. It is natural to consider deriving both best-effort and constraint-based forwarding information using the CR scheme itself. Does this render the underlying LS routing scheme redundant? This might perhaps be the case from the LS routing table point of view, but much of an LS routing scheme deals with building the topology database which is vital for the functioning of the CR scheme. Thus, the LS scheme takes care of much of the complexity (hopefully in a scalable manner) and thereby simplifies the design of the CR overlay. Given that there is much experience with LS schemes like OSPF and IS-IS, it seems possible to success- fully develop an overlay CR scheme rather than designing a CR scheme from scratch. We note that while the focus in this draft was on CR overlay over LS routing schemes, it is possible to develop CR overlays on distance or path vector routing schemes, using the spanning tree methodology presented. For instance, the algorithm presented in [GHS83] can be used to compute MSTs in distance vector routing environments. [R96] describes an approach that can be used in path vector routing environments. Finally, the descriptions in this draft were high-level, and further details are needed to gain a deeper understanding of the overlay model and constraint- based routing itself. Specifically, details on the structure of hierarchical CR schemes, the organization of the CR database, the selection of QoS parameters and path computation algorithms, interaction with reservation protocols, interdomain routing and the deployment of CR in various settings such as MPLS and diffserv are some of the open issues. REFERENCES [AMAD98] D. O. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, and J. McManus, "Requirements for Traffic Engineering Over MPLS," draft-ietf-mpls-traffic-eng-00.txt, October,1998. [BG87] D. Bertsekas and R. Gallager, Data Networks, Prentice Hall Inc., Englewood Cliffs, NJ, 1987. [BSS91] K. Birman, A. Schiper, and P. Stephenson, "Lightweight Causal and Atomic Group Multicast," ACM Trans. Computer Systems, August, 1991. [C90] R. Callon, "Use of OSI IS-IS for Routing in TCP/IP and Dual Environments," RFC 1195, December, 1990. [Page 17] Internet Draft draft-rajagopalan-CR-overlay-00.txt Jan, 1999 [CNRS98] E. Crawley, R. Nair, B. Rajagopalan and H. Sandick, "A Framework for QoS-Based Routing in the Internet," RFC 2386, August, 1998. [DM78] Y. K. Dalal and R. Metcalfe, "Reverse Path Forwarding of Broadcast Packets," Comm. ACM, December, 1978. [GHS83] R. Gallagher, P. Humblet and P. Spira, "A Distributed Algorithm for Minimum-Weight Spanning Trees," ACM Trans. Programming Lang. Systems, Vol. 5 (7), 1983. [GWPK98] R. Guerin, D. Williams, A. Przygienda, S. Kamat and A. Orda, "QoS Routing Mechanisms and OSPF extensions", draft-guerin-qos-routing-ospf-04.txt, December, 1998. [MOY98] J. Moy, "OSPF Version 2," RFC 2328, April, 1998. [PER83] R. Perlman, "Fault-Tolerant Broadcast of Routing Information," Proc. IEEE Infocom, 1983 . [R96] B. Rajagopalan, "Efficient QoS-Based Link State Routing," draft available from the author, braja@ccrl.nj.nec.com. [W80] D. Wall, "Mechanisms for Broadcast and Selective Broadcast," Tech. Report #190, Dept. of EE and CS, Stanford Univ, 1980. [ZSSC97] Z. Zhang, C. Sanchez, B. Salkewicz, and E. Crawley, " "QoS Extensions to OSPF," Internet Draft, draft-zhang-qos-ospf-02.ps, September, 1997. AUTHORS' ADDRESS Bala Rajagopalan Qingming Ma NEC C&C Research Labs Cisco Systems 4 Independence Way 170 West Tasman Dr. Princeton, NJ 08540 San Jose, CA 95134 U.S.A U.S.A Ph: +1-609-951-2969 Ph: +1-408-261-3566 Email: braja@ccrl.nj.nec.com Email: qma@cisco.com ***** This draft expires on July, 25, 1999 ****** [Page 18]