idnits 2.17.1 draft-coras-lisp-re-04.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 (October 21, 2013) is 3832 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-06) exists of draft-farinacci-lisp-mr-signaling-03 == Outdated reference: A later version (-12) exists of draft-farinacci-lisp-te-03 == Outdated reference: A later version (-22) exists of draft-ietf-lisp-lcaf-03 ** Obsolete normative reference: RFC 4601 (Obsoleted by RFC 7761) ** Obsolete normative reference: RFC 6830 (Obsoleted by RFC 9300, RFC 9301) Summary: 2 errors (**), 0 flaws (~~), 4 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: April 24, 2014 Technical University of 6 Catalonia 7 F. Maino 8 cisco Systems 9 D. Farinacci 10 lispers.net 11 October 21, 2013 13 LISP Replication Engineering 14 draft-coras-lisp-re-04 16 Abstract 18 This document describes a method to build and optimize inter-domain 19 LISP router distribution trees for locator-based unicast and 20 multicast replication of EID-sourced multicast packets. 22 Status of this Memo 24 This Internet-Draft is submitted in full conformance with the 25 provisions of BCP 78 and BCP 79. 27 Internet-Drafts are working documents of the Internet Engineering 28 Task Force (IETF). Note that other groups may also distribute 29 working documents as Internet-Drafts. The list of current Internet- 30 Drafts is at http://datatracker.ietf.org/drafts/current/. 32 Internet-Drafts are draft documents valid for a maximum of six months 33 and may be updated, replaced, or obsoleted by other documents at any 34 time. It is inappropriate to use Internet-Drafts as reference 35 material or to cite them other than as "work in progress." 37 This Internet-Draft will expire on April 24, 2014. 39 Copyright Notice 41 Copyright (c) 2013 IETF Trust and the persons identified as the 42 document authors. All rights reserved. 44 This document is subject to BCP 78 and the IETF Trust's Legal 45 Provisions Relating to IETF Documents 46 (http://trustee.ietf.org/license-info) in effect on the date of 47 publication of this document. Please review these documents 48 carefully, as they describe your rights and restrictions with respect 49 to this document. Code Components extracted from this document must 50 include Simplified BSD License text as described in Section 4.e of 51 the Trust Legal Provisions and are provided without warranty as 52 described in the Simplified BSD License. 54 Table of Contents 56 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 57 2. Definition of Terms . . . . . . . . . . . . . . . . . . . . . 4 58 3. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 59 4. Overlay Signaling . . . . . . . . . . . . . . . . . . . . . . 6 60 4.1. RTR Registration . . . . . . . . . . . . . . . . . . . . . 6 61 4.2. ETR/RTR Subscription . . . . . . . . . . . . . . . . . . . 6 62 4.3. ETR/RTR Unsubscription . . . . . . . . . . . . . . . . . . 8 63 5. Overlay Management . . . . . . . . . . . . . . . . . . . . . . 8 64 5.1. RLOC Failure and Unreachability . . . . . . . . . . . . . 8 65 5.2. Other Overlay Management Considerations . . . . . . . . . 8 66 5.3. Automated Computation of RTR Level . . . . . . . . . . . . 9 67 5.3.1. Algorithm for Computing Optimized Distribution 68 Trees . . . . . . . . . . . . . . . . . . . . . . . . 9 69 6. Security Considerations . . . . . . . . . . . . . . . . . . . 11 70 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 71 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 11 72 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 73 9.1. Normative References . . . . . . . . . . . . . . . . . . . 11 74 9.2. Informative References . . . . . . . . . . . . . . . . . . 12 75 Appendix A. MADDBST heuristic . . . . . . . . . . . . . . . . . . 13 76 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 13 78 1. Introduction 80 The Locator/Identifier Separation Protocol (LISP) [RFC6830] provides 81 the mechanisms for the separation of Location and Identity semantics 82 presently overloaded by IP addresses. The split results in the 83 creation of two namespaces that unambigously identify edge-site 84 network objects, Endpoint IDs (EIDs), and core routing objects, 85 Routing LOCators (RLOCs). Apart from aiding the scalablity of the 86 core routing infrastructure, the decoupling also enables the 87 (re)implementation of new or existing inter-domain routing 88 mechanisms. 90 One such mechanism is inter-domain IP source-specific multicast (SSM) 91 [RFC4607]. In this sense, [RFC6831] defines the procedures carried 92 out for delivering multicast packets from a source host in a LISP 93 site to receivers residing in the same domain or in other LISP or 94 non-LISP sites when an underlying multicast infrastructure exists. 95 The signaling protocol it specifies for conveying (S-EID,G) state and 96 building the distribution tree that connects the source ITR and the 97 receiving ETRs is PIM [RFC4601]. An alternative method that uses 98 Map-Requests for propagating (S-EID,G) state from ETRs to the ITR is 99 established in [I-D.farinacci-lisp-mr-signaling]. 101 Although desirable to use multicast routing in the core network when 102 available, a mismatch between the multicast capabilities of receiver 103 ETRs and source ITR might impede their interconnection. In such a 104 case, unicast RLOC encapsulation is necessary to deliver multicast 105 packets directly to the ETRs. This however leads to high ITR head- 106 end replication for large sets of ETRs. Therefore, to reduce the 107 replication load of the ITR and scale the service with the number of 108 multicast receivers, the ITR may choose to offload replication to a 109 set of RTRs. 111 The current document describes how multicast RTRs can be used to 112 build an inter-domain distribution tree rooted at the ITR that can 113 perform unicast and/or multicast encapsulated replication of 114 multicast packets. This concept, of distributing the replication 115 load from ITR to other RTRs downstream on the core overlay 116 distribution tree, is known as Replication Engineering or LISP-RE. 117 Since unicast replication in such overlays can be suboptimal when 118 compared to the underlay network, methods to optimize packet delivery 119 over the distribution tree are also presented. 121 This specification does not define the mechanisms used to build 122 (S-EID,G) state in source and receiver domains, nor does it describe 123 the messages used to propagate such state from receiver ETRs to 124 source ITR. What it defines is how (S-EID,G) state is built in the 125 ITR, RTRs and ETRs participating in the overlay distribution tree. 127 2. Definition of Terms 129 The terminology in this document is consistent with the definitions 130 in [RFC6830] and [RFC6831] however, it is extended to account for 131 LISP-RE concepts: 133 Delivery Group (DG): This is the outer destination address of a 134 packet when LISP encapsulating a multicast packet with an EID 135 source within a multicast packet. 137 Re-encapsulating Tunnel Router (RTR): An RTR is a router that 138 implements the re-encapsulating tunnel function detailed in 139 Section 8 of the main LISP specification [RFC6830]. Such router 140 performs packet re-routing by chaining ETR and ITR functions, 141 whereby they first remove the LISP header of ingressing packets 142 and then prepend a new one prior to forwarding them. 144 Unicast Replication: Is the notion of replicating a multicast packet 145 with an EID source address at an ITR or RTR by encapsulating it 146 into a unicast packet. That is, the oif-list of a multicast map- 147 cache entry can not only have interfaces present for link-layer 148 replication and multicast encapsulation but also for site-facing 149 interfaces and unicast encapsulation. 151 Overlay Distribution Tree: A degree-constrained spanning tree that 152 represents the path followed by unicast and/or multicast 153 encapsulated multicast packets from the root (ITR) to the leaves 154 (ETRs) through intermediary nodes (RTRs). The ITR and RTRs 155 unicast and/or multicast replicate packets to their tree children. 157 LISP Replication Node: A router (either the ITR or an RTR) 158 participating and replicating packets downstream in the 159 distribution tree. 161 Multicast Ingress Tunnel Router (ITR): An ITR as specificed in 162 [RFC6830] that supports multicast and participates as the root in 163 the distribution tree. In this document we use the term "ITR" to 164 mean a multicast capable ITR. 166 Multicast Egress Tunnel Router (ETR): An ETR as specified in 167 [RFC6830] that participates as a leaf in the distribution tree. 168 ETR are the only members of the tree that do not unicast 169 replicate. In this document we use the term "ETR" to mean a 170 multicast capable ETR. 172 Multicast Re-encapsulating Tunnel Router (RTR): An RTR as specified 173 in [I-D.farinacci-lisp-te] that participates as an intermediary 174 node in the distribution tree. In this document we use the term 175 "RTR" to mean a multicast capable RTR. 177 Replication Target: A multicast channel-id (S-EID,G) or a set of 178 multicast channel-ids (S-EID-prefix,G). 180 Joining-OIF-list: Represents a collection of state per multicast 181 routing table entry at an RTR or ETR that is created by received 182 Map-Request/Join-Request. 184 Forwarding-OIF-list: Represents the outgoing RLOC list a multicast 185 router stores per multicast routing table entry such that it knows 186 to which RLOCs to replicate multicast packets. Although the 187 Joining-OIF-list contains sufficient information to allow the 188 forwarding of encapsulated multicast packets, using it is 189 inefficient. Thereby, an RTR implementation may wish to build an 190 efficient Forwarding-OIF-list. Ways of implementing a Forwarding- 191 OIF-list are out of the scope of this document. 193 Upstream: Towards the root of the tree. 195 Downstream: Away from the root of the tree. 197 3. Overview 199 This document describes a method to diminish the ITR's replication 200 load by using RTRs to build an inter-domain distribution tree. The 201 tree is managed by the source domain's Map-Server. RTRs join the 202 overlay due to either manual or automatic configuration and advertise 203 to the Map-Server their availability to replicate traffic for a 204 multicast channel (S-EID,G). Out of all the RTRs registering for the 205 same multicast channel, the Map-Server builds one mapping and 206 organizes the RLOCs in a multi-level hierarchy. The hierarchy is 207 rooted at the ITR and computed based on the configured information 208 RTRs register or by means of local policy and algorithms. ETRs 209 always join the overlay as leaves and their attachment prompts the 210 creation of a path, which traverses the RTR hierarchy, from the ITR. 211 The path is built at receiver request by incrementally linking all 212 distribution tree levels, starting at the joining ETR up to the 213 source ITR. 215 The way the distribution tree is built has several benefits. First, 216 it ensures that packets in the source domain do not reach the ITR if 217 no ETR is joined. Second, it ensures that packets are forwarded from 218 ITR to all ETRs without mapping database lookups since the state that 219 defines the distribution tree, i.e., the replication hierarchy, is 220 created prior to forwarding/replicating the packets. Finally, the 221 multicast source is allowed to roam since a first level RTR, when 222 informed of the roam event, can do a new database lookup to find the 223 new ITR to join to. 225 It is worth pointing out that because of the receiver-initiated 226 approach multicast employs to build distribution trees, whereby 227 receivers join upstream sources, LISP-RE operates backwards from LISP 228 point of view. That is, ETRs are the ones to send Map-Requests to 229 discover potential upstream parents and the ITR answers with Map- 230 Replies to joining downstream clients. 232 4. Overlay Signaling 234 This section describes the signaling the ITR, RTRs and ETRs use in 235 order to participate in the overlay and build a distribution tree. 236 The signaling messages used are described in 237 [I-D.farinacci-lisp-mr-signaling] and [RFC6831]. 239 4.1. RTR Registration 241 RTR participation in the overlay is condition by the configuration of 242 a replication target, a multicast channel (S-EID,G) or set of 243 channels (S-EID-prefix,G), the RTR is to perform replication for. 244 Once configured, manually or by automated mechanisms, an RTR Map- 245 Registers its replication target with merge-semantics to the 246 appropriate Map-Server. In the registration it also provides its 247 list of RLOCs to be used by overlay peers and a set of corresponding 248 weights and priorities. If present, information about the level of 249 the hierarchy where the RTR should attach is also conveyed by means 250 of an Replication List Entry canonical address [I-D.ietf-lisp-lcaf]. 252 Due to the merge-semantics, the Map-Server aggregates all RTR 253 originated Map-Register messages in a single, per replication target 254 mapping. If no level information is provided or if so configured, 255 the Map-Server should use local policy to compute a hierarchy and 256 associate a level within it to each entry in the list (more details 257 in Section 5.3). It should be noted that the entries that are 258 pointed to in the resulting mapping are not RLOCs but Replication 259 List entries. 261 4.2. ETR/RTR Subscription 263 When an ETR creates (S-EID,G) state from a site based multicast join, 264 i.e., its oif-list goes non-empty, it must send an upstream Join 265 request. If the ETR does not have multicast connectivity to its 266 upstream and unicast replication must be performed, the ETR requests 267 that a path from ITR to itself, over the RTR hierarchy be 268 constructed. The following procedure is followed to build the path: 270 1. ETR sends a Map-Request/Join-Request for (S-EID,G) multicast 271 channel to the mapping database system which further ensures its 272 delivery to the authoritative Map-Server. 274 2. The Map-Server looks up the mapping associated to (S-EID,G) and, 275 out of the distribution tree hierarchy encoded within, it selects 276 a set of leaf RTRs, i.e., members of the level furthest away from 277 the ITR, with spare replication capacity. The set of potential 278 parents is encoded in a new (S-EID, G) mapping the Map-Server 279 conveys to the ETR in a Map-Reply. 281 3. From the list it receives, the ETR selects the best upstream RTR 282 RLOC according to local policy, taking into account the 283 associated priorities and weights and sends to the owning RTR a 284 Map-Request/Join-Request for (S-EID,G). If the ETR itself has 285 multiple RLOCs it wishes to use in the overlay, it may convey 286 them all to the upstream RTR encoded in the Map-Reply field of 287 the Map-Request/Join-Request together with associated priorities 288 and weights. 290 4. The RTR stores the ETR's subscription information in the join- 291 oif-list associated to (S-EID,G) and inserts the RLOC obtained 292 after evaluating the priorities and weights in the oif-list for 293 (S-EID,G). It then confirms the ETR's subscription with a Map- 294 Reply. 296 5. If not already a member of (S-EID,G), the RTR initiates it's own 297 attachment to the distribution tree by repeating the steps 1-4. 298 An important difference at step 2, the Map-Server replies to a 299 joining RTR with a list of RTRs in the adjacent upstream layer, 300 as opposed to a list of leaf RTRs, like in the case of an ETR 301 join. This procedure may recurse upstream up to when the ITR or 302 an RTR already attached to the distribution tree is joined. On 303 completion, there should exist a path from ITR to joining ETR. 305 6. If the ITR is already member of (S-EID,G) the process stops. 306 Otherwise, the ITR sends a PIM join to the intra-domain multicast 307 source ensuring the creation of a path from the multicast source 308 to the receiver end-hosts. 310 If at any point, when creating a link between two adjacent layers, 311 native multicast replication can be performed, instead of unicast 312 replication, the router joining its upstream could set as source of 313 the Map-Request/Join-Request a delivery group. However, group naming 314 must be coordinated between the participating parties in this case, 315 if core network replication is to be exploited. 317 4.3. ETR/RTR Unsubscription 319 When an ETR's oif-list goes empty a Map-Request/Leave-Request is sent 320 to the upstream RTR which will result in the removal of the ETR's 321 associated entry from the RTR's oif-list. The procedure is repeated 322 by the RTR, and it may recurse upstream, if its own oif-list also 323 goes empty. 325 When an RTR with active dowstreams departs, it should first change 326 the priority of the RLOCs it registers with the Map-Server to 255 and 327 set its locators as unreachable in the RLOC-Probing replies it sends 328 downstream. Finally, once all adjacent lower level members have sent 329 Map-Request/Leave-Request messages the RTR can stop registering 330 (S-EID,G) with the mapping database system and thus leave the 331 overlay. 333 5. Overlay Management 335 5.1. RLOC Failure and Unreachability 337 RLOC failure is detected at control-plane level through RLOC-probing 338 [RFC6830] by both upstream and downstream routers. When an RTR 339 detects the failure of an downstream RLOC, it ceases replicating 340 towards it. The affected RLOC is removed from the forwarding-oif- 341 list and marked as unreachable in the join-oif-list. If a backup 342 RLOC was provided by the downstream router in the Map-Request/ 343 Join-Request, it is instead inserted in the forwarding-oif-list and 344 the failure results in no packet loss. 346 The routers downstream of a failed RTR RLOC, or who lost connectivity 347 to said RLOCs, remove their Map-Request/Join-Request associated state 348 and reperform the join procedure. Packet loss in this case must be 349 solved by out-of-band mechanisms that are out of the scope of the 350 current document. 352 5.2. Other Overlay Management Considerations 354 An overloaded RTR, i.e., one whose fan-out can not be increased, 355 should change the priority of the RLOCs it registers with the mapping 356 database system to 255. In such a situation, the Map-Server updates 357 the associated mapping and informs all routers having requested it 358 about the change through solicit Map Request (SMR) messages. Both 359 new ETRs attaching to the distribution tree and those already 360 connected but reperforming the join procedure must not use the RLOCs 361 with a priority of 255 as specified in [RFC6830]. However, routers 362 having performed Join-Requests prior to the change should not break 363 their existing connections to the affected RTR. 365 All routers part of an (S-EID,G) multicast channel should re-evaluate 366 their attachment point to the distribution tree whenever the Map- 367 Server updates the associated mapping. This ensures the overlay 368 member routers attach to the best suited parent when new RTRs join or 369 previously attached ones stop being overloaded. Change of a parent 370 should be done following a "make before break" procedure. 371 Specifically, the router changing attachment point first connects to 372 the new parent and only afterwards sends the Leave-Request. 374 When a downstream RTR subscribes to a set of channel-ids (S-EID- 375 prefix,G) using multiple RLOCs in a load-balancing configuration, the 376 upstream RTR may choose to load-split channel-ids (S-EID,G) over the 377 given set of RLOCs. 379 5.3. Automated Computation of RTR Level 381 Operators wishing to automate the RTR joining procedure may wish to 382 use an algorithm for computing an optimized distribution tree. The 383 algorithm could be implemented in the Map-Server and its output 384 should be used to associate to all RTRs a level in the distribution 385 tree. Due to the centralized management, on-line switching between 386 algorithms may be possible in accordance to the required distribution 387 tree performance. However, their use of such algorithms is dependent 388 on the presence of overlay topological information. Ways of 389 obtaining topological information will be discussed in future 390 versions of this document. 392 5.3.1. Algorithm for Computing Optimized Distribution Trees 394 The current document does not recommend an algorithm for computing 395 optimized distribution trees. However, it provides as an example a 396 low computation cost heuristic, which, in the scenarios simulated in 397 [LCAST-TR], can produce latencies between the ITR and the multicast 398 receivers close to unicast ones. Its choice is to be influenced by 399 operational requirements and the hardware constraints of the 400 equipment in charge of running it. Future experiments might result 401 in a recommendation. 403 In what follows, we use the term "distance" when referring to a 404 relative length or amplitude of a metric, observed on a path 405 connecting two points, but when the exact nature of the metric is of 406 no interest. 408 Considering as goal the delivery of content for delay sensitive 409 applications, the function the algorithm minimizes is the maximum 410 distance (e.g. latency or number of AS hops) from a multicast 411 receiver to the ITR source. Notice that the reference is the 412 multicast receiver host and not an ETR. Thus, what matters in 413 deciding a member's position in the distribution tree is not solely 414 its distance to the ITR but also the number of multicast receivers it 415 serves. Then, a router close to the source but serving few receivers 416 might find itself lower in the distribution tree than another with a 417 slightly higher distance to the source but with a larger receiver 418 set. The algorithm optimizes the quality of experience for multicast 419 receivers and not for tunnel routers. 421 The problem described above, that searches for a minimum average 422 distance, degree-bounded spanning tree (MADDBST), can be formally 423 stated as: 425 Definition: Given an undirected complete graph G=(V,E), a designated 426 vertex r belonging to V, for all vertices v in V, a degree bound 427 d(v) <= dmax, dmax a positive integer, a vertex weight function 428 c(v) with positive integer values, and an edge weight function 429 w(e) with positive values, for all edges e in E. Let W(r,v,T) 430 represent the cost of the path linking r and v in the spanning 431 tree T. Find the spanning tree T of G, routed at r, satisfying 432 that d(v) <= dmax and the distance to the source per multicast 433 receiver is minimized. 435 The heuristic used to solve this problem works by incrementally 436 growing a tree, starting at the root node r, until it becomes a 437 spanning tree. For each node v, not yet a tree member, it selects a 438 potential parent node u in the tree T, such that the distance per 439 receiver to r, is minimized. At each step, the node with the 440 smallest metric value is added to the tree and the parent selection 441 is redone. The pseudocode of the heuristic is provided in 442 Appendix A. 444 [SHI] and [BAN] have previously defined and solved similar 445 optimization problems. Shi et al. [SHI] also prove that a 446 particular instance of the problem, where all vertices have weight 1, 447 is NP-complete for degree constraints 2 <= dmax <= |V|-1. 449 The algorithm can optimize an unicast overlay however, it should not 450 be used to optimize multicast underlay delivery. As a result, if 451 multicast is used as underlay between part of the overlay members, 452 once one of the members of such Delivery Group is added to the 453 distribution tree, the others should be marked as attached also. 454 These nodes should receive multicast encapsulated multicast packets 455 from the chosen node over the underlying multicast distribution tree. 457 Finally, since the RTRs do not replicate packets for multicast 458 receiver hosts, prior to applying the MADDBST heuristic, a Minimum 459 Spanning Tree (MST) algorithm should be used to compute the RTR 460 distribution tree. In this case, the MADDBST heuristic should start 461 attaching ETRs having as input the tree resulting from MST. 463 6. Security Considerations 465 Security concerns for LISP-RE the same as for [RFC6831] and 466 [I-D.farinacci-lisp-mr-signaling]. 468 7. IANA Considerations 470 This memo includes no request to IANA. 472 8. Acknowledgements 474 The authors would like to thank Noel Chiappa for his technical and 475 editorial commentary. 477 9. References 479 9.1. Normative References 481 [I-D.farinacci-lisp-mr-signaling] 482 Farinacci, D. and M. Napierala, "LISP Control-Plane 483 Multicast Signaling", draft-farinacci-lisp-mr-signaling-03 484 (work in progress), September 2013. 486 [I-D.farinacci-lisp-te] 487 Farinacci, D., Lahiri, P., and M. Kowal, "LISP Traffic 488 Engineering Use-Cases", draft-farinacci-lisp-te-03 (work 489 in progress), July 2013. 491 [I-D.ietf-lisp-lcaf] 492 Farinacci, D., Meyer, D., and J. Snijders, "LISP Canonical 493 Address Format (LCAF)", draft-ietf-lisp-lcaf-03 (work in 494 progress), September 2013. 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 [RFC6830] Farinacci, D., Fuller, V., Meyer, D., and D. Lewis, "The 504 Locator/ID Separation Protocol (LISP)", RFC 6830, 505 January 2013. 507 [RFC6831] Farinacci, D., Meyer, D., Zwiebel, J., and S. Venaas, "The 508 Locator/ID Separation Protocol (LISP) for Multicast 509 Environments", RFC 6831, January 2013. 511 9.2. Informative References 513 [BAN] Banerjee, S., Kommareddy, C., Kar, K., Bhattacharjee, B., 514 and S. Khuller, "Construction of an efficient overlay 515 multicast infrastructure for real-time applications", 516 INFOCOM , 2002. 518 [LCAST-TR] 519 Coras, F., Cabellos, A., Domingo, J., Maino, F., and D. 520 Farinacci, "Lcast: Software-defined Inter-Domain 521 Multicast", Technical 522 Report http://personals.ac.upc.edu/fcoras/lcast-tr.pdf, 523 2012. 525 [SHI] Shi, S., Turner, J., and M. Waldvogel, "Dimensioning 526 server access bandwidth and multicast routing in overlay 527 networks", NOSSDAV , 2001. 529 Appendix A. MADDBST heuristic 531 INPUT: G = (V,E); r; dmax; w(u,v); c(v); u, v in V 532 OUTPUT: T 534 FOREACH v in V DO 535 delta(v) = w(r,v)/c(v); 536 p(v) = r; 537 END FOREACH 539 T takes (U = {r}, D={}); 540 WHILE U != V DO 541 LET u in U-V be the vertex with the smallest delta(u); 542 U = U U {u}; L = L U {(p(u),u)}; 543 FOREACH v in V-U DO 544 delta(v) = infinity; 545 FOREACH u in U DO 546 IF d(u) < dmax and 547 W{r,u,T} + w(u,v)/c(v) < delta(v) THEN 548 delta(v) = W{r,u,T} + w(u,v)/c(v); 549 p(v) = u; 550 END IF 551 END FOR 552 END FOR 553 END WHILE 555 Figure 1 557 Authors' Addresses 559 Florin Coras 560 Technical University of Catalonia 561 C/Jordi Girona, s/n 562 BARCELONA 08034 563 Spain 565 Email: fcoras@ac.upc.edu 567 Albert Cabellos-Aparicio 568 Technical University of Catalonia 569 C/Jordi Girona, s/n 570 BARCELONA 08034 571 Spain 573 Email: acabello@ac.upc.edu 574 Jordi Domingo-Pascual 575 Technical University of Catalonia 576 C/Jordi Girona, s/n 577 BARCELONA 08034 578 Spain 580 Email: jordi.domingo@ac.upc.edu 582 Fabio Maino 583 cisco Systems 584 Tasman Drive 585 San Jose, CA 95134 586 USA 588 Email: fmaino@cisco.com 590 Dino Farinacci 591 lispers.net 593 Email: farinacci@gmail.com