idnits 2.17.1 draft-coras-lisp-re-08.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 (November 1, 2015) is 3091 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-12) exists of draft-farinacci-lisp-te-09 == Outdated reference: A later version (-22) exists of draft-ietf-lisp-lcaf-11 ** 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 (~~), 3 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: May 4, 2016 Technical University of Catalonia 6 F. Maino 7 cisco Systems 8 D. Farinacci 9 lispers.net 10 November 1, 2015 12 LISP Replication Engineering 13 draft-coras-lisp-re-08 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-sourced 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 May 4, 2016. 38 Copyright Notice 40 Copyright (c) 2015 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 . . . . . . . . . . . . . . . . . . . . . . . . 2 56 2. Definition of Terms . . . . . . . . . . . . . . . . . . . . . 3 57 3. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 5 58 4. Overlay Signaling . . . . . . . . . . . . . . . . . . . . . . 5 59 4.1. RTR Registration . . . . . . . . . . . . . . . . . . . . 6 60 4.2. ETR/RTR Subscription . . . . . . . . . . . . . . . . . . 6 61 4.3. ETR/RTR Unsubscription . . . . . . . . . . . . . . . . . 7 62 5. Overlay Management . . . . . . . . . . . . . . . . . . . . . 8 63 5.1. RLOC Failure and Unreachability . . . . . . . . . . . . . 8 64 5.2. Other Overlay Management Considerations . . . . . . . . . 8 65 5.3. Automated Computation of RTR Level . . . . . . . . . . . 9 66 5.3.1. Algorithm for Computing Optimized Distribution Trees 9 67 6. Security Considerations . . . . . . . . . . . . . . . . . . . 10 68 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 69 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 11 70 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 71 9.1. Normative References . . . . . . . . . . . . . . . . . . 11 72 9.2. Informative References . . . . . . . . . . . . . . . . . 12 73 Appendix A. MADDBST heuristic . . . . . . . . . . . . . . . . . 12 74 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 12 76 1. Introduction 78 The Locator/Identifier Separation Protocol (LISP) [RFC6830] provides 79 the mechanisms for the separation of Location and Identity semantics 80 presently overloaded by IP addresses. The split results in the 81 creation of two namespaces that unambigously identify edge-site 82 network objects, Endpoint IDs (EIDs), and core routing objects, 83 Routing LOCators (RLOCs). Apart from aiding the scalablity of the 84 core routing infrastructure, the decoupling also enables the 85 (re)implementation of new or existing inter-domain routing 86 mechanisms. 88 One such mechanism is inter-domain IP source-specific multicast (SSM) 89 [RFC4607]. In this sense, [RFC6831] defines the procedures carried 90 out for delivering multicast packets from a source host in a LISP 91 site to receivers residing in the same domain or in other LISP or 92 non-LISP sites when an underlying multicast infrastructure exists. 93 The signaling protocol it specifies for conveying (S-EID,G) state and 94 building the distribution tree that connects the source ITR and the 95 receiving ETRs is PIM [RFC4601]. An alternative method that uses 96 Map-Requests for propagating (S-EID,G) state from ETRs to the ITR is 97 established in [I-D.farinacci-lisp-mr-signaling]. 99 Although desirable to use multicast routing in the core network when 100 available, a mismatch between the multicast capabilities of receiver 101 ETRs and source ITR might impede their interconnection. In such a 102 case, unicast RLOC encapsulation is necessary to deliver multicast 103 packets directly to the ETRs. This however leads to high ITR head- 104 end replication for large sets of ETRs. Therefore, to reduce the 105 replication load of the ITR and scale the service with the number of 106 multicast receivers, the ITR may choose to offload replication to a 107 set of RTRs. 109 The current document describes how multicast RTRs can be used to 110 build an inter-domain distribution tree rooted at the ITR that can 111 perform unicast and/or multicast encapsulated replication of 112 multicast packets. This concept, of distributing the replication 113 load from ITR to other RTRs downstream on the core overlay 114 distribution tree, is known as Replication Engineering or LISP-RE. 115 Since unicast replication in such overlays can be suboptimal when 116 compared to the underlay network, methods to optimize packet delivery 117 over the distribution tree are also presented. 119 This specification does not define the mechanisms used to build 120 (S-EID,G) state in source and receiver domains, nor does it describe 121 the messages used to propagate such state from receiver ETRs to 122 source ITR. What it defines is how (S-EID,G) state is built in the 123 ITR, RTRs and ETRs participating in the overlay distribution tree. 125 2. Definition of Terms 127 The terminology in this document is consistent with the definitions 128 in [RFC6830] and [RFC6831] however, it is extended to account for 129 LISP-RE concepts: 131 Delivery Group (DG): This is the outer destination address of a 132 packet when LISP encapsulating a multicast packet with an EID 133 source within a multicast packet. 135 Re-encapsulating Tunnel Router (RTR): An RTR is a router that 136 implements the re-encapsulating tunnel function detailed in 137 Section 8 of the main LISP specification [RFC6830]. Such router 138 performs packet re-routing by chaining ETR and ITR functions, 139 whereby they first remove the LISP header of ingressing packets 140 and then prepend a new one prior to forwarding them. 142 Unicast Replication: Is the notion of replicating a multicast packet 143 with an EID source address at an ITR or RTR by encapsulating it 144 into a unicast packet. That is, the oif-list of a multicast map- 145 cache entry can not only have interfaces present for link-layer 146 replication and multicast encapsulation but also for site-facing 147 interfaces and unicast encapsulation. 149 Overlay Distribution Tree: A degree-constrained spanning tree that 150 represents the path followed by unicast and/or multicast 151 encapsulated multicast packets from the root (ITR) to the leaves 152 (ETRs) through intermediary nodes (RTRs). The ITR and RTRs 153 unicast and/or multicast replicate packets to their tree children. 155 LISP Replication Node: A router (either the ITR or an RTR) 156 participating and replicating packets downstream in the 157 distribution tree. 159 Multicast Ingress Tunnel Router (ITR): An ITR as specificed in 160 [RFC6830] that supports multicast and participates as the root in 161 the distribution tree. In this document we use the term "ITR" to 162 mean a multicast capable ITR. 164 Multicast Egress Tunnel Router (ETR): An ETR as specified in 165 [RFC6830] that participates as a leaf in the distribution tree. 166 ETR are the only members of the tree that do not unicast 167 replicate. In this document we use the term "ETR" to mean a 168 multicast capable ETR. 170 Multicast Re-encapsulating Tunnel Router (RTR): An RTR as specified 171 in [I-D.farinacci-lisp-te] that participates as an intermediary 172 node in the distribution tree. In this document we use the term 173 "RTR" to mean a multicast capable RTR. 175 Replication Target: A multicast channel-id (S-EID,G) or a set of 176 multicast channel-ids (S-EID-prefix,G). 178 Joining-OIF-list: Represents a collection of state per multicast 179 routing table entry at an RTR or ETR that is created by received 180 Map-Request/Join-Request. 182 Forwarding-OIF-list: Represents the outgoing RLOC list a multicast 183 router stores per multicast routing table entry such that it knows 184 to which RLOCs to replicate multicast packets. Although the 185 Joining-OIF-list contains sufficient information to allow the 186 forwarding of encapsulated multicast packets, using it is 187 inefficient. Thereby, an RTR implementation may wish to build an 188 efficient Forwarding-OIF-list. Ways of implementing a Forwarding- 189 OIF-list are out of the scope of this document. 191 Upstream: Towards the root of the tree. 193 Downstream: Away from the root of the tree. 195 3. Overview 197 This document describes a method to diminish the ITR's replication 198 load by using RTRs to build an inter-domain distribution tree. The 199 tree is managed by the source domain's Map-Server. RTRs join the 200 overlay due to either manual or automatic configuration and advertise 201 to the Map-Server their availability to replicate traffic for a 202 multicast channel (S-EID,G). Out of all the RTRs registering for the 203 same multicast channel, the Map-Server builds one mapping and 204 organizes the RLOCs in a multi-level hierarchy. The hierarchy is 205 rooted at the ITR and computed based on the configured information 206 RTRs register or by means of local policy and algorithms. ETRs 207 always join the overlay as leaves and their attachment prompts the 208 creation of a path, which traverses the RTR hierarchy, from the ITR. 209 The path is built at receiver request by incrementally linking all 210 distribution tree levels, starting at the joining ETR up to the 211 source ITR. 213 The way the distribution tree is built has several benefits. First, 214 it ensures that packets in the source domain do not reach the ITR if 215 no ETR is joined. Second, it ensures that packets are forwarded from 216 ITR to all ETRs without mapping database lookups since the state that 217 defines the distribution tree, i.e., the replication hierarchy, is 218 created prior to forwarding/replicating the packets. Finally, the 219 multicast source is allowed to roam since a first level RTR, when 220 informed of the roam event, can do a new database lookup to find the 221 new ITR to join to. 223 It is worth pointing out that because of the receiver-initiated 224 approach multicast employs to build distribution trees, whereby 225 receivers join upstream sources, LISP-RE operates backwards from LISP 226 point of view. That is, ETRs are the ones to send Map-Requests to 227 discover potential upstream parents and the ITR answers with Map- 228 Replies to joining downstream clients. 230 4. Overlay Signaling 232 This section describes the signaling the ITR, RTRs and ETRs use in 233 order to participate in the overlay and build a distribution tree. 234 The signaling messages used are described in 235 [I-D.farinacci-lisp-mr-signaling] and [RFC6831]. 237 4.1. RTR Registration 239 RTR participation in the overlay is condition by the configuration of 240 a replication target, a multicast channel (S-EID,G) or set of 241 channels (S-EID-prefix,G), the RTR is to perform replication for. 242 Once configured, manually or by automated mechanisms, an RTR Map- 243 Registers its replication target with merge-semantics to the 244 appropriate Map-Server. In the registration it also provides its 245 list of RLOCs to be used by overlay peers and a set of corresponding 246 weights and priorities. If present, information about the level of 247 the hierarchy where the RTR should attach is also conveyed by means 248 of an Replication List Entry canonical address [I-D.ietf-lisp-lcaf]. 250 Due to the merge-semantics, the Map-Server aggregates all RTR 251 originated Map-Register messages in a single, per replication target 252 mapping. If no level information is provided or if so configured, 253 the Map-Server should use local policy to compute a hierarchy and 254 associate a level within it to each entry in the list (more details 255 in Section 5.3). It should be noted that the entries that are 256 pointed to in the resulting mapping are not RLOCs but Replication 257 List entries. 259 4.2. ETR/RTR Subscription 261 When an ETR creates (S-EID,G) state from a site based multicast join, 262 i.e., its oif-list goes non-empty, it must send an upstream Join 263 request. If the ETR does not have multicast connectivity to its 264 upstream and unicast replication must be performed, the ETR requests 265 that a path from ITR to itself, over the RTR hierarchy be 266 constructed. The following procedure is followed to build the path: 268 1. ETR sends a Map-Request/Join-Request for (S-EID,G) multicast 269 channel to the mapping database system which further ensures its 270 delivery to the authoritative Map-Server. 272 2. The Map-Server looks up the mapping associated to (S-EID,G) and, 273 out of the distribution tree hierarchy encoded within, it selects 274 a set of leaf RTRs, i.e., members of the level furthest away from 275 the ITR, with spare replication capacity. The set of potential 276 parents is encoded in a new (S-EID, G) mapping the Map-Server 277 conveys to the ETR in a Map-Reply. 279 3. From the list it receives, the ETR selects the best upstream RTR 280 RLOC according to local policy, taking into account the 281 associated priorities and weights and sends to the owning RTR a 282 Map-Request/Join-Request for (S-EID,G). If the ETR itself has 283 multiple RLOCs it wishes to use in the overlay, it may convey 284 them all to the upstream RTR encoded in the Map-Reply field of 285 the Map-Request/Join-Request together with associated priorities 286 and weights. 288 4. The RTR stores the ETR's subscription information in the join- 289 oif-list associated to (S-EID,G) and inserts the RLOC obtained 290 after evaluating the priorities and weights in the oif-list for 291 (S-EID,G). It then confirms the ETR's subscription with a Map- 292 Reply. 294 5. If not already a member of (S-EID,G), the RTR initiates it's own 295 attachment to the distribution tree by repeating the steps 1-4. 296 An important difference at step 2, the Map-Server replies to a 297 joining RTR with a list of RTRs in the adjacent upstream layer, 298 as opposed to a list of leaf RTRs, like in the case of an ETR 299 join. This procedure may recurse upstream up to when the ITR or 300 an RTR already attached to the distribution tree is joined. On 301 completion, there should exist a path from ITR to joining ETR. 303 6. If the ITR is already member of (S-EID,G) the process stops. 304 Otherwise, the ITR sends a PIM join to the intra-domain multicast 305 source ensuring the creation of a path from the multicast source 306 to the receiver end-hosts. 308 If at any point, when creating a link between two adjacent layers, 309 native multicast replication can be performed, instead of unicast 310 replication, the router joining its upstream could set as source of 311 the Map-Request/Join-Request a delivery group. However, group naming 312 must be coordinated between the participating parties in this case, 313 if core network replication is to be exploited. 315 4.3. ETR/RTR Unsubscription 317 When an ETR's oif-list goes empty a Map-Request/Leave-Request is sent 318 to the upstream RTR which will result in the removal of the ETR's 319 associated entry from the RTR's oif-list. The procedure is repeated 320 by the RTR, and it may recurse upstream, if its own oif-list also 321 goes empty. 323 When an RTR with active dowstreams departs, it should first change 324 the priority of the RLOCs it registers with the Map-Server to 255 and 325 set its locators as unreachable in the RLOC-Probing replies it sends 326 downstream. Finally, once all adjacent lower level members have sent 327 Map-Request/Leave-Request messages the RTR can stop registering 328 (S-EID,G) with the mapping database system and thus leave the 329 overlay. 331 5. Overlay Management 333 5.1. RLOC Failure and Unreachability 335 RLOC failure is detected at control-plane level through RLOC-probing 336 [RFC6830] by both upstream and downstream routers. When an RTR 337 detects the failure of an downstream RLOC, it ceases replicating 338 towards it. The affected RLOC is removed from the forwarding-oif- 339 list and marked as unreachable in the join-oif-list. If a backup 340 RLOC was provided by the downstream router in the Map-Request/Join- 341 Request, it is instead inserted in the forwarding-oif-list and the 342 failure results in no packet loss. 344 The routers downstream of a failed RTR RLOC, or who lost connectivity 345 to said RLOCs, remove their Map-Request/Join-Request associated state 346 and reperform the join procedure. Packet loss in this case must be 347 solved by out-of-band mechanisms that are out of the scope of the 348 current document. 350 5.2. Other Overlay Management Considerations 352 An overloaded RTR, i.e., one whose fan-out can not be increased, 353 should change the priority of the RLOCs it registers with the mapping 354 database system to 255. In such a situation, the Map-Server updates 355 the associated mapping and informs all routers having requested it 356 about the change through solicit Map Request (SMR) messages. Both 357 new ETRs attaching to the distribution tree and those already 358 connected but reperforming the join procedure must not use the RLOCs 359 with a priority of 255 as specified in [RFC6830]. However, routers 360 having performed Join-Requests prior to the change should not break 361 their existing connections to the affected RTR. 363 All routers part of an (S-EID,G) multicast channel should re-evaluate 364 their attachment point to the distribution tree whenever the Map- 365 Server updates the associated mapping. This ensures the overlay 366 member routers attach to the best suited parent when new RTRs join or 367 previously attached ones stop being overloaded. Change of a parent 368 should be done following a "make before break" procedure. 369 Specifically, the router changing attachment point first connects to 370 the new parent and only afterwards sends the Leave-Request. 372 When a downstream RTR subscribes to a set of channel-ids (S-EID- 373 prefix,G) using multiple RLOCs in a load-balancing configuration, the 374 upstream RTR may choose to load-split channel-ids (S-EID,G) over the 375 given set of RLOCs. 377 5.3. Automated Computation of RTR Level 379 Operators wishing to automate the RTR joining procedure may wish to 380 use an algorithm for computing an optimized distribution tree. The 381 algorithm could be implemented in the Map-Server and its output 382 should be used to associate to all RTRs a level in the distribution 383 tree. Due to the centralized management, on-line switching between 384 algorithms may be possible in accordance to the required distribution 385 tree performance. However, their use of such algorithms is dependent 386 on the presence of overlay topological information. Ways of 387 obtaining topological information will be discussed in future 388 versions of this document. 390 5.3.1. Algorithm for Computing Optimized Distribution Trees 392 The current document does not recommend an algorithm for computing 393 optimized distribution trees. However, it provides as an example a 394 low computation cost heuristic, which, in the scenarios simulated in 395 [LCAST], can produce latencies between the ITR and the multicast 396 receivers close to unicast ones. Its choice is to be influenced by 397 operational requirements and the hardware constraints of the 398 equipment in charge of running it. Future experiments might result 399 in a recommendation. 401 In what follows, we use the term "distance" when referring to a 402 relative length or amplitude of a metric, observed on a path 403 connecting two points, but when the exact nature of the metric is of 404 no interest. 406 Considering as goal the delivery of content for delay sensitive 407 applications, the function the algorithm minimizes is the maximum 408 distance (e.g. latency or number of AS hops) from a multicast 409 receiver to the ITR source. Notice that the reference is the 410 multicast receiver host and not an ETR. Thus, what matters in 411 deciding a member's position in the distribution tree is not solely 412 its distance to the ITR but also the number of multicast receivers it 413 serves. Then, a router close to the source but serving few receivers 414 might find itself lower in the distribution tree than another with a 415 slightly higher distance to the source but with a larger receiver 416 set. The algorithm optimizes the quality of experience for multicast 417 receivers and not for tunnel routers. 419 The problem described above, that searches for a minimum average 420 distance, degree-bounded spanning tree (MADDBST), can be formally 421 stated as: 423 Definition: Given an undirected complete graph G=(V,E), a designated 424 vertex r belonging to V, for all vertices v in V, a degree bound 425 d(v) <= dmax, dmax a positive integer, a vertex weight function 426 c(v) with positive integer values, and an edge weight function 427 w(e) with positive values, for all edges e in E. Let W(r,v,T) 428 represent the cost of the path linking r and v in the spanning 429 tree T. Find the spanning tree T of G, routed at r, satisfying 430 that d(v) <= dmax and the distance to the source per multicast 431 receiver is minimized. 433 The heuristic used to solve this problem works by incrementally 434 growing a tree, starting at the root node r, until it becomes a 435 spanning tree. For each node v, not yet a tree member, it selects a 436 potential parent node u in the tree T, such that the distance per 437 receiver to r, is minimized. At each step, the node with the 438 smallest metric value is added to the tree and the parent selection 439 is redone. The pseudocode of the heuristic is provided in 440 Appendix A. 442 [SHI] and [BAN] have previously defined and solved similar 443 optimization problems. Shi et al. [SHI] also prove that a 444 particular instance of the problem, where all vertices have weight 1, 445 is NP-complete for degree constraints 2 <= dmax <= |V|-1. 447 The algorithm can optimize an unicast overlay however, it should not 448 be used to optimize multicast underlay delivery. As a result, if 449 multicast is used as underlay between part of the overlay members, 450 once one of the members of such Delivery Group is added to the 451 distribution tree, the others should be marked as attached also. 452 These nodes should receive multicast encapsulated multicast packets 453 from the chosen node over the underlying multicast distribution tree. 455 Finally, since the RTRs do not replicate packets for multicast 456 receiver hosts, prior to applying the MADDBST heuristic, a Minimum 457 Spanning Tree (MST) algorithm should be used to compute the RTR 458 distribution tree. In this case, the MADDBST heuristic should start 459 attaching ETRs having as input the tree resulting from MST. 461 6. Security Considerations 463 Security concerns for LISP-RE the same as for [RFC6831] and 464 [I-D.farinacci-lisp-mr-signaling]. 466 7. IANA Considerations 468 This memo includes no request to IANA. 470 8. Acknowledgements 472 The authors would like to thank Noel Chiappa for his technical and 473 editorial commentary. 475 9. References 477 9.1. Normative References 479 [I-D.farinacci-lisp-mr-signaling] 480 Farinacci, D. and M. Napierala, "LISP Control-Plane 481 Multicast Signaling", draft-farinacci-lisp-mr-signaling-06 482 (work in progress), February 2015. 484 [I-D.farinacci-lisp-te] 485 Farinacci, D., Kowal, M., and P. Lahiri, "LISP Traffic 486 Engineering Use-Cases", draft-farinacci-lisp-te-09 (work 487 in progress), September 2015. 489 [I-D.ietf-lisp-lcaf] 490 Farinacci, D., Meyer, D., and J. Snijders, "LISP Canonical 491 Address Format (LCAF)", draft-ietf-lisp-lcaf-11 (work in 492 progress), September 2015. 494 [RFC4601] Fenner, B., Handley, M., Holbrook, H., and I. Kouvelas, 495 "Protocol Independent Multicast - Sparse Mode (PIM-SM): 496 Protocol Specification (Revised)", RFC 4601, 497 DOI 10.17487/RFC4601, August 2006, 498 . 500 [RFC4607] Holbrook, H. and B. Cain, "Source-Specific Multicast for 501 IP", RFC 4607, DOI 10.17487/RFC4607, August 2006, 502 . 504 [RFC6830] Farinacci, D., Fuller, V., Meyer, D., and D. Lewis, "The 505 Locator/ID Separation Protocol (LISP)", RFC 6830, 506 DOI 10.17487/RFC6830, January 2013, 507 . 509 [RFC6831] Farinacci, D., Meyer, D., Zwiebel, J., and S. Venaas, "The 510 Locator/ID Separation Protocol (LISP) for Multicast 511 Environments", RFC 6831, DOI 10.17487/RFC6831, January 512 2013, . 514 9.2. Informative References 516 [BAN] Banerjee, S., Kommareddy, C., Kar, K., Bhattacharjee, B., 517 and S. Khuller, "Construction of an efficient overlay 518 multicast infrastructure for real-time applications", 519 INFOCOM , 2002. 521 [LCAST] Coras, F., Cabellos, A., Domingo, J., Maino, F., and D. 522 Farinacci, "Lcast: Software-defined inter-domain 523 multicast", Computer Networks , 2014. 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 558 Florin Coras 559 Technical University of Catalonia 560 C/Jordi Girona, s/n 561 BARCELONA 08034 562 Spain 564 Email: fcoras@ac.upc.edu 566 Albert Cabellos-Aparicio 567 Technical University of Catalonia 568 C/Jordi Girona, s/n 569 BARCELONA 08034 570 Spain 572 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