idnits 2.17.1 draft-coras-lisp-re-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (July 9, 2012) is 4307 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-10) exists of draft-farinacci-lisp-lcaf-09 == Outdated reference: A later version (-06) exists of draft-farinacci-lisp-mr-signaling-00 == Outdated reference: A later version (-12) exists of draft-farinacci-lisp-te-01 == Outdated reference: A later version (-24) exists of draft-ietf-lisp-23 ** Obsolete normative reference: RFC 4601 (Obsoleted by RFC 7761) Summary: 1 error (**), 0 flaws (~~), 5 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group F. Coras 3 Internet-Draft A. Cabellos-Aparicio 4 Intended status: Informational J. Domingo-Pascual 5 Expires: January 10, 2013 Technical University of 6 Catalonia 7 F. Maino 8 D. Farinacci 9 cisco Systems 10 July 9, 2012 12 LISP Replication Engineering 13 draft-coras-lisp-re-00 15 Abstract 17 This document describes a method to build and optimize inter-domain 18 LISP router distribution trees for locator-based unicast and 19 multicast replication of EID-based multicast packets. 21 Status of this Memo 23 This Internet-Draft is submitted in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF). Note that other groups may also distribute 28 working documents as Internet-Drafts. The list of current Internet- 29 Drafts is at http://datatracker.ietf.org/drafts/current/. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 This Internet-Draft will expire on January 10, 2013. 38 Copyright Notice 40 Copyright (c) 2012 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents 45 (http://trustee.ietf.org/license-info) in effect on the date of 46 publication of this document. Please review these documents 47 carefully, as they describe your rights and restrictions with respect 48 to this document. Code Components extracted from this document must 49 include Simplified BSD License text as described in Section 4.e of 50 the Trust Legal Provisions and are provided without warranty as 51 described in the Simplified BSD License. 53 Table of Contents 55 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 56 2. Definition of Terms . . . . . . . . . . . . . . . . . . . . . 4 57 3. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 58 4. Overlay Distribution Tree . . . . . . . . . . . . . . . . . . 6 59 4.1. LISP Replication Node Database . . . . . . . . . . . . . . 7 60 4.2. Building the Distribution Tree . . . . . . . . . . . . . . 7 61 5. Distribution Tree Optimization . . . . . . . . . . . . . . . . 8 62 5.1. Topology Discovery . . . . . . . . . . . . . . . . . . . . 9 63 5.2. Optimization Algorithm . . . . . . . . . . . . . . . . . . 9 64 6. Security Considerations . . . . . . . . . . . . . . . . . . . 11 65 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 66 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 11 67 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 68 9.1. Normative References . . . . . . . . . . . . . . . . . . . 11 69 9.2. Informative References . . . . . . . . . . . . . . . . . . 12 70 Appendix A. MADDBST heuristic . . . . . . . . . . . . . . . . . . 13 71 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 13 73 1. Introduction 75 The Locator/Identifier Separation Protocol (LISP) [I-D.ietf-lisp] 76 provides the mechanisms for the separation of Location and Identity 77 semantics presently overloaded by IP addresses. The split results in 78 the creation of two namespaces that unambigously identify edge-site 79 network objects, Endpoint IDs (EIDs), and core routing objects, 80 Routing LOCators (RLOCs). Apart from aiding the scalablity of the 81 core routing infrastructure, the decoupling also enables the 82 (re)implementation of new or existing inter-domain routing 83 mechanisms. 85 One such mechanism is inter-domain IP source-specific multicast (SSM) 86 [RFC4607]. In this sense, [I-D.ietf-lisp-multicast] defines the 87 procedures carried out for delivering multicast packets from a source 88 host in a LISP site to receivers residing in the same domain or in 89 other LISP or non-LISP sites when an underlying multicast 90 infrastructure exists. The signaling protocol it specifies for 91 conveying (S-EID,G) state and building the distribution tree 92 connecting the xTRs of the source and receiver domains is PIM 93 [RFC4601]. An alternative method that uses Map-Requests instead of 94 PIM for propagating (S-EID,G) state from multicast receiver site ETRs 95 to source site ITR is established in 96 [I-D.farinacci-lisp-mr-signaling]. 98 Although desirable to use multicast routing in the core network when 99 available, a mismatch between the multicast capabilities of receiver 100 ETRs and source ITR might impede their multicast interconnection. In 101 such a case, unicast RLOC encapsulation will be necessary to deliver 102 multicast packets directly to the ETRs. This however leads to high 103 ITR head-end replication for large sets of receiving ETRs. 104 Therefore, to reduce the replication load of the ITR and scale the 105 service with the number of multicast receivers, the ITR may choose to 106 offload replication to a set of RTRs. 108 The current document describes how multicast RTRs can be used to 109 build an inter-domain distribution tree rooted at the ITR that can 110 perform unicast and/or multicast encapsulated replication of 111 multicast packets. This concept, of distributing the replication 112 load from ITR to other RTRs downstream on the core overlay 113 distribution tree, is known as Replication Engineering or LISP-RE. 114 Since unicast replication in such overlays can be suboptimal when 115 compared to the underlay network, methods to optimize packet delivery 116 over the distribution tree are also presented. 118 This specification does not describe how (S-EID,G) state is built in 119 source and receiver domains, nor does it describe how such state is 120 propagated from receiver ETRs to source ITR. This specification 121 defines how (S-EID,G) map-cache state is built in the ITR, RTRs and 122 ETRs participating in the overlay distribution tree when they are not 123 connectable by multicast. 125 2. Definition of Terms 127 The terminology in this document is consistent with the definitions 128 in [I-D.ietf-lisp] and [I-D.ietf-lisp-multicast] however, it is 129 extended to account for LISP-RE concepts: 131 Delivery Group (DG): The outer destination address of a multicast 132 encapsulated multicast packet with an EID source. 134 Replication Target: A unicast locator or Delivery Group towards 135 which a multicast packet may be encapsulated and replicated. 137 Replication List: A locator-set associated to a multicast map-cache 138 entry (S-EID,G) as defined in [I-D.farinacci-lisp-te]. Locators 139 in the set may be either unicast RLOCs or Delivery Groups. When 140 used by a LISP router, a multicast packet matching the map-cache 141 entry must be replicated to all members of the set. The unicast 142 RLOCs are used to encapsulate multicast packets for unicast 143 delivery on the underlying network. Delivery Groups are used to 144 encapsulate multicast packets for multicast delivery on the 145 underlay. 147 Unicast Replication: Is the notion of replicating a multicast packet 148 with an EID source address at an ITR or RTR by encapsulating it 149 into a unicast packet. That is, the oif-list of a multicast map- 150 cache entry can not only have interfaces present for link-layer 151 replication and multicast encapsulation but also for unicast 152 encapsulation. 154 Overlay Distribution Tree: A degree-constrained spanning tree that 155 represents the path followed by unicast and/or multicast 156 encapsulated multicast packets from the root (ITR) to the leaves 157 (ETRs) through intermediary nodes (RTRs). The ITR and RTRs 158 unicast and/or multicast replicate packets to their tree children. 159 Such tree is built and maintained by the overlay distribution tree 160 controller either by using LISP signaling defined in 161 [I-D.ietf-lisp-multicast] and [I-D.farinacci-lisp-mr-signaling] or 162 by programming the mapping database directly by using ELPs to 163 describe network-wide fanout. 165 Distribution Tree Controller (DTC): A central entity that manages 166 the overlay distribution tree, such entity can be either the ITR 167 or an external orchestration system. 169 LISP Replication Node: A router (either the ITR or an RTR) 170 participating and replicating packets downstream in the 171 distribution tree. 173 Multicast Ingress Tunnel Router (ITR): An ITR as specificed in 174 [I-D.ietf-lisp] that participates as the root in the distribution 175 tree. 177 Multicast Egress Tunnel Router (ETR): An ETR as specified in 178 [I-D.ietf-lisp] that participates as a leaf in the distribution 179 tree. ETR are the only members of the tree that do not unicast 180 replicate. 182 Multicast Re-encapsulating Tunnel Router (RTR): An RTR as specified 183 in [I-D.farinacci-lisp-te] that participates as an intermediary 184 node in the distribution tree. 186 Explicit Locator Path (ELP): an explicit and strictly ordered list 187 of replication targets a packet must travel to. An ELP may be 188 used to source route a LISP-encapsulated packet on an explicit 189 path of RTRs, however the path between two RTRs is determined by 190 the underlying routing protocol. ELP format is described in 191 [I-D.farinacci-lisp-lcaf] and their use in 192 [I-D.farinacci-lisp-te]. 194 3. Overview 196 This specification describes a method to diminish the replication 197 load of the ITR by using RTRs to build an inter-domain distribution 198 tree. The tree is centrally managed either by the ITR itself or by 199 an external orchestration system. An advantage of this orchestration 200 system is that it offloads signaling from the ITR. The entity that 201 manages the tree is generally referred to as the distribution tree 202 controller (DTC). 204 In order to offload unicast replication of multicast packets the DTC 205 uses a ITR and a set of RTRs. RTRs willing to participate in the 206 distribution tree associated to the (S-EID,G) multicast channel must 207 join the distribution tree by sending a Map-Request/Join-Request 208 [I-D.farinacci-lisp-mr-signaling] to the DTC. Using this procedure 209 the DTC learns the RLOCs of the available RTRs. Additionally, the 210 DTC must learn the replication capacity of each RTR using out-of-band 211 signaling or by manual configuration. 213 Given that the ITR and RTRs have a limited replication capacity the 214 distribution tree is a degree-constrained spanning-tree. This means 215 that the root is the ITR, the intermediary members are RTRs while 216 leaves are always ETRs. Multicast packets are addressed to (S-EID,G) 217 and are unicast and/or multicast encapsulated when being transported 218 downstream the tree. 220 In order to build and maintain the overlay distribution tree the DTC 221 must configure state in the replication nodes (ITR and RTRs). This 222 is done by means of the signaling specified in 223 [I-D.ietf-lisp-multicast] and [I-D.farinacci-lisp-mr-signaling]. 224 Particularly, the DTC receives Map-Requests from RTRs (also from the 225 ITR if the DTC is an external orchestration system) addressed to 226 (S-EID,G). Upon inspection of the source RLOC of the Map-Request the 227 controller determines the originating ITR/RTR and generates an ad-hoc 228 Map-Reply containing the specific replication list for that 229 particular node according to the topology of the tree. For a LISP 230 replication node, the replication list specifies the set of RTRs/ETRs 231 to which it has to replicate packets, i.e., its overlay distribution 232 tree children. Alternatively, an external orchestration system may 233 directly program the mapping database with ELPs that describe the 234 topology of the overlay distribution tree. Ways of achieving this 235 will be discussed in future versions of the document. 237 The DTC determines the specific topology of the overlay distribution 238 tree using a centralized algorithm. The only requirements for this 239 algorithm are that it builds a tree that guarantees that ETRs receive 240 the encapsulated multicast packets, that the replication capacity of 241 the ITR and RTRs is not exceeded and that forwarding loops are 242 avoided. 244 In some cases the network administrator may want an optimized overlay 245 distribution tree, although this specification does not standardize 246 any particular algorithm it suggests one in Section 5.2. In order to 247 build an optimized tree this algorithm makes use of the distance 248 (e.g., latency) between the tree members and the amount of multicast 249 receivers connected to each ETR. Such metrics are not provided by 250 LISP and therefore must be obtained using out-of-band signaling. 252 4. Overlay Distribution Tree 254 This section describes how the DTC can build an overlay distribution 255 tree using the signaling and mechanisms defined in 256 [I-D.ietf-lisp-multicast] and [I-D.farinacci-lisp-mr-signaling]. 258 4.1. LISP Replication Node Database 260 The DTC maintains per (S-EID,G) multicast channel a LISP Replication 261 Node Database (LRND) that stores information about the distribution 262 tree state. This information includes among others the RLOCs of the 263 ITR, RTRs and ETRs that constitute the distribution tree and define 264 the overlay replication topology (i.e., the parent-child relations). 265 Said data may be obtained by the DTC from the standard signaling 266 messages exchanged with the RTRs and ETRs. Additionally, by means of 267 out-of-band signalling the DTC should obtain information about the 268 replication capacity of RTRs. 270 If the operator chooses to build an optimized tree, more information 271 must be available at the LRND, this is further discussed in 272 Section 5.2. 274 4.2. Building the Distribution Tree 276 This section describes the procedures followed by ETRs and RTRs when 277 attaching to the distribution tree. All procedures assume that the 278 DTC has a LRND consistent with the state of the overlay distribution 279 tree and is aware of the replication capacity of participating RTRs. 281 The decision of an RTR to join the overlay distribution tree depends 282 on out-of-band signalling (e.g., orchestration system, manual 283 configuration). But, its attachment to the distribution tree is done 284 by means of one of the following two procedures: 286 1. The RTR explicitly signals the ITR by sending a Join-Request for 287 (S-EID,G) and is replied to with a replication list. 289 2. If an orchestration system programs the mapping database with 290 ELPs describing the overlay distribution tree, an RTR Map- 291 Requests for (S-EID,G) and receives as reply an ELP that defines 292 its distribution tree fanout. Ways of encoding the tree topology 293 into ELPs will be discussed in future versions of this document. 295 For RTRs using option 1 the DTC, an ITR in this case, will perform 296 the same processing as for joining ETRs. The following sequence of 297 steps is used to attach an ETR to the overlay distribution tree: 299 1. The DTC receives a Map-Request/Join-Request for (S-EID,G) from an 300 ETR. 302 2. If multicast replication is requested, the DTC proceeds as 303 defined in [I-D.farinacci-lisp-mr-signaling] and no further steps 304 are taken. 306 3. If unicast replication is requested, the DTC must choose a 307 position for the ETR in the distribution tree topology. 308 Specifically, it initiates a search within the LRND for a node 309 (either the ITR or a RTR) with enough spare replication capacity 310 that will replicate multicast traffic towards the ETR. This tree 311 member will become the parent of the ETR and once it is selected 312 the LRND is updated accordingly. The search algorithm depends on 313 operational requirements and this specification does not 314 standardize one, however Section 5.2 provides an example 315 algorithm. Note also that certain algorithms may require the 316 complete or partial re-shape the tree based on certain 317 performance metrics. 319 4. The DTC must create/update the (S-EID,G) associated replication 320 state for the selected parent using the mechanisms defined in 321 [I-D.ietf-lisp] and [I-D.farinacci-lisp-mr-signaling] (e.g., 322 Solicit-Map-Request). This results in the parent sending a Map- 323 Request for (S-EID,G), in turn, the DTC Map-Replies with an ad- 324 hoc replication list of locator-sets according to topology stored 325 at the LRND. If the algorithm results in a complete or partial 326 re-shape of the tree then state at multiple tree members must be 327 created/updated. In order to avoid packet loss this must be done 328 synchronously. It will be discussed in future versions of this 329 document how to achieve this. 331 5. Once the distribution tree is configured to replicate multicast 332 traffic to the ETR the DTC Map-Replies (as specified in 333 [I-D.farinacci-lisp-mr-signaling]) with the destination EID- 334 prefix set to (parent-RLOC, ETR-RLOC). 336 When a LISP replication node signals its departure from the tree, the 337 information stored at the LRND is updated accordingly. For ETRs, the 338 state of the parent member must be updated as described in step 4. 339 For RTRs both the state of the parent and its children must be 340 updated however, such updates may result in packet loss. Moreover, 341 certain optimization algorithms may result in a re-shape of the tree 342 and as a consequence the state of multiple tree members must be 343 created/updated according to the new topology. How to manage these 344 updates with no packet loss will be discussed in future versions of 345 this document. 347 5. Distribution Tree Optimization 349 Operators wishing to improve the performance of the distribution tree 350 need to implement at least one topology discovery mechanism and 351 choose a set of optimization algorithms. Due to the centralized 352 group management, on-line switching between optimization algorithms 353 may be possible in accordance to the required performance. However, 354 their use is dependent on the presence of overlay topological 355 information. The following logical modules need to be implemented in 356 order to support overlay optimizations with LISP-RE: 358 Topology Discovery Coordinator: It is in charge of organizing the 359 topology measurements and building a database that stores the 360 topological distances (i.e., a metric must be chosen) between 361 overlay members. 363 Distribution Tree Computation Unit: It is a component that with the 364 help of an algorithm or heuristic, given as input the topology of 365 the overlay and a constraint, or constraint set, can compute an 366 optimal, or close to optimal, degree-constrained minimum spanning 367 tree that may be used for multicast content distribution. 369 Whether to implement the above modules in the ITR or in other network 370 elements is the decision of the network administrator. 372 5.1. Topology Discovery 374 The present document does not specify any topology discovery 375 mechanisms. Both active and passive topology measurements could be 376 used. A choice between the two, of the policy and admission control 377 used or of the network element in charge of coordinating these 378 measurements could be made in the future based on practical 379 experience. Alternatively, precomputed network maps like the ones 380 offered by [IPLANE] and/or out-of-band signalling may be used. 382 5.2. Optimization Algorithm 384 The current document does not recommend an optimization algorithm. 385 However, it provides as an example a low computation cost heuristic, 386 which, in the scenarios simulated in [LCAST-TR], can produce 387 latencies between the ITR and the multicast receivers close to 388 unicast ones. Its choice is to be influenced by operational 389 requirements and the hardware constraints of the equipment in charge 390 of running it. Future experiments might result in a recommendation. 392 In what follows, we use the term "distance" when referring to a 393 relative length or amplitude of a metric, observed on a path 394 connecting two points, but when the exact nature of the metric is of 395 no interest. 397 Considering as goal the delivery of content for delay sensitive 398 applications, the function the algorithm minimizes is the maximum 399 distance (e.g. latency or number of AS hops) from a multicast 400 receiver to the ITR source. Notice that the reference is the 401 multicast receiver host and not an ETR. Thus, what matters in 402 deciding a member's position in the distribution tree is not solely 403 its distance to the ITR but also the number of multicast receivers it 404 serves. Then, a router close to the source but serving few receivers 405 might find itself lower in the distribution tree than another with a 406 slightly higher distance to the source but with a larger receiver 407 set. The algorithm optimizes the quality of experience for multicast 408 receivers and not for tunnel routers. 410 The problem described above, that searches for a minimum average 411 distance, degree-bounded spanning tree (MADDBST), can be formally 412 stated as: 414 Definition: Given an undirected complete graph G=(V,E), a designated 415 vertex r belonging to V, for all vertices v in V, a degree bound 416 d(v) <= dmax, dmax a positive integer, a vertex weight function 417 c(v) with positive integer values, and an edge weight function 418 w(e) with positive values, for all edges e in E. Let W(r,v,T) 419 represent the cost of the path linking r and v in the spanning 420 tree T. Find the spanning tree T of G, routed at r, satisfying 421 that d(v) <= dmax and the distance to the source per multicast 422 receiver is minimized. 424 The heuristic used to solve this problem works by incrementally 425 growing a tree, starting at the root node r, until it becomes a 426 spanning tree. For each node v, not yet a tree member, it selects a 427 potential parent node u in the tree T, such that the distance per 428 receiver to r, is minimized. At each step, the node with the 429 smallest metric value is added to the tree and the parent selection 430 is redone. The pseudocode of the heuristic is provided in 431 Appendix A. 433 [SHI] and [BAN] have previously defined and solved similar 434 optimization problems. Shi et al. [SHI] also prove that a 435 particular instance of the problem, where all vertices have weight 1, 436 is NP-complete for degree constraints 2 <= dmax <= |V|-1. 438 The algorithm can optimize an unicast overlay however, it should not 439 be used to optimize multicast underlay delivery. As a result, if 440 multicast is used as underlay between part of the overlay members, 441 once one of the members of such Delivery Group is added to the 442 distribution tree, the others should be marked as attached also. 443 These nodes should receive multicast encapsulated multicast packets 444 from the chosen node over the underlying multicast distribution tree. 446 Finally, since the RTRs do not replicate packets for multicast 447 receiver hosts, prior to applying the MADDBST heuristic, a Minimum 448 Spanning Tree (MST) algorithm should be used to compute the RTR 449 distribution tree. In this case, the MADDBST heuristic should start 450 attaching ETRs having as input the tree resulting from MST. 452 6. Security Considerations 454 Security concerns for LISP-RE the same as for 455 [I-D.ietf-lisp-multicast] and [I-D.farinacci-lisp-mr-signaling]. 457 7. IANA Considerations 459 This memo includes no request to IANA. 461 8. Acknowledgements 463 TODO 465 9. References 467 9.1. Normative References 469 [I-D.farinacci-lisp-lcaf] 470 Farinacci, D., Meyer, D., and J. Snijders, "LISP Canonical 471 Address Format (LCAF)", draft-farinacci-lisp-lcaf-09 (work 472 in progress), July 2012. 474 [I-D.farinacci-lisp-mr-signaling] 475 Farinacci, D., Spencer, T., and N. Napierala, "LISP 476 Control-Plane Multicast Signaling", 477 draft-farinacci-lisp-mr-signaling-00 (work in progress), 478 July 2012. 480 [I-D.farinacci-lisp-te] 481 Farinacci, D., Lahiri, P., and M. Kowal, "LISP Traffic 482 Engineering Use-Cases", draft-farinacci-lisp-te-01 (work 483 in progress), July 2012. 485 [I-D.ietf-lisp] 486 Farinacci, D., Fuller, V., Meyer, D., and D. Lewis, 487 "Locator/ID Separation Protocol (LISP)", 488 draft-ietf-lisp-23 (work in progress), May 2012. 490 [I-D.ietf-lisp-multicast] 491 Farinacci, D., Meyer, D., Zwiebel, J., and S. Venaas, 492 "LISP for Multicast Environments", 493 draft-ietf-lisp-multicast-14 (work in progress), 494 February 2012. 496 [RFC4601] Fenner, B., Handley, M., Holbrook, H., and I. Kouvelas, 497 "Protocol Independent Multicast - Sparse Mode (PIM-SM): 498 Protocol Specification (Revised)", RFC 4601, August 2006. 500 [RFC4607] Holbrook, H. and B. Cain, "Source-Specific Multicast for 501 IP", RFC 4607, August 2006. 503 9.2. Informative References 505 [BAN] Banerjee, S., Kommareddy, C., Kar, K., Bhattacharjee, B., 506 and S. Khuller, "Construction of an efficient overlay 507 multicast infrastructure for real-time applications", 508 INFOCOM , 2002. 510 [IPLANE] Madhyastha, H., Katz-Bassett, E., Anderson, T., 511 Krishnamurthy, A., and A. Venkataramani, "iPlane: An 512 Information Plane for Distributed Services", USENIX OSDI , 513 2009. 515 [LCAST-TR] 516 Coras, F., Cabellos, A., Domingo, J., Maino, F., and D. 517 Farinacci, "Inter-Domain Multicast: LISP Edge Based 518 Trees", Technical 519 Report http://personals.ac.upc.edu/fcoras/lcast-tr.pdf, 520 2012. 522 [SHI] Shi, S., Turner, J., and M. Waldvogel, "Dimensioning 523 server access bandwidth and multicast routing in overlay 524 networks", NOSSDAV , 2001. 526 Appendix A. MADDBST heuristic 528 INPUT: G = (V,E); r; dmax; w(u,v); c(v); u, v in V 529 OUTPUT: T 531 FOREACH v in V DO 532 delta(v) = w(r,v)/c(v); 533 p(v) = r; 534 END FOREACH 536 T takes (U = {r}, D={}); 537 WHILE U != V DO 538 LET u in U-V be the vertex with the smallest delta(u); 539 U = U U {u}; L = L U {(p(u),u)}; 540 FOREACH v in V-U DO 541 delta(v) = infinity; 542 FOREACH u in U DO 543 IF d(u) < dmax and 544 W{r,u,T} + w(u,v)/c(v) < delta(v) THEN 545 delta(v) = W{r,u,T} + w(u,v)/c(v); 546 p(v) = u; 547 END IF 548 END FOR 549 END FOR 550 END WHILE 552 Figure 1 554 Authors' Addresses 556 Florin Coras 557 Technical University of Catalonia 558 C/Jordi Girona, s/n 559 BARCELONA 08034 560 Spain 562 Email: fcoras@ac.upc.edu 564 Albert Cabellos-Aparicio 565 Technical University of Catalonia 566 C/Jordi Girona, s/n 567 BARCELONA 08034 568 Spain 570 Email: acabello@ac.upc.edu 571 Jordi Domingo-Pascual 572 Technical University of Catalonia 573 C/Jordi Girona, s/n 574 BARCELONA 08034 575 Spain 577 Email: jordi.domingo@ac.upc.edu 579 Fabio Maino 580 cisco Systems 581 Tasman Drive 582 San Jose, CA 95134 583 USA 585 Email: fmaino@cisco.com 587 Dino Farinacci 588 cisco Systems 589 Tasman Drive 590 San Jose, CA 95134 591 USA 593 Email: dino@cisco.com