idnits 2.17.1 draft-banerjea-qosmic-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-26) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 15 longer pages, the longest (page 10) being 66 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 34 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 20 instances of too long lines in the document, the longest one being 6 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 268 has weird spacing: '...authors state...' == Line 549 has weird spacing: '...scussed later...' == Line 1229 has weird spacing: '...ast and with ...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- Couldn't find a document date in the document -- date freshness check skipped. -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: '25' is mentioned on line 1346, but not defined ** Downref: Normative reference to an Historic RFC: RFC 2201 (ref. '1') -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' -- Possible downref: Non-RFC (?) normative reference: ref. '5' -- Possible downref: Non-RFC (?) normative reference: ref. '7' -- Possible downref: Non-RFC (?) normative reference: ref. '8' -- Possible downref: Non-RFC (?) normative reference: ref. '9' ** Obsolete normative reference: RFC 2117 (ref. '10') (Obsoleted by RFC 2362) -- Possible downref: Non-RFC (?) normative reference: ref. '11' -- Possible downref: Non-RFC (?) normative reference: ref. '12' -- Possible downref: Non-RFC (?) normative reference: ref. '13' -- Possible downref: Non-RFC (?) normative reference: ref. '14' -- Possible downref: Non-RFC (?) normative reference: ref. '15' -- Possible downref: Non-RFC (?) normative reference: ref. '16' -- Possible downref: Non-RFC (?) normative reference: ref. '17' -- Possible downref: Non-RFC (?) normative reference: ref. '18' == Outdated reference: A later version (-04) exists of draft-ietf-idmr-gum-00 -- Possible downref: Normative reference to a draft: ref. '19' -- Possible downref: Non-RFC (?) normative reference: ref. '20' -- Possible downref: Non-RFC (?) normative reference: ref. '21' -- Possible downref: Non-RFC (?) normative reference: ref. '22' -- Possible downref: Non-RFC (?) normative reference: ref. '23' -- Possible downref: Non-RFC (?) normative reference: ref. '24' -- Possible downref: Non-RFC (?) normative reference: ref. '26' -- Possible downref: Non-RFC (?) normative reference: ref. '27' Summary: 12 errors (**), 0 flaws (~~), 8 warnings (==), 26 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 INTERNET-DRAFT Anindo Banerjea (U. of Toronto) 3 Inter-Domain Multicast Routing Michalis Faloutsos (U. of Toronto) 4 Expires: October 1998 Rajesh Pankaj (QUALCOMM) 5 File: draft-banerjea-qosmic-00.txt 7 Designing QoSMIC: A Quality of Service sensitive 8 Multicast Internet protoCol 10 STATUS OF THIS MEMO 12 This document is an Internet-Draft. Internet-Drafts are working 13 documents of the Internet Engineering Task Force (IETF), its areas, and 14 its working groups. Note that other groups may also distribute working 15 documents as Internet-Drafts. 17 Internet-Drafts are draft documents valid for a maximum of six months 18 and may be updated, replaced, or obsoleted by other documents at any 19 time. It is inappropriate to use Internet- Drafts as reference material 20 or to cite them other than as "work in progress." 22 To view the entire list of current Internet-Drafts, please check the 23 "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow 24 Directories on 26 ftp.is.co.za (Africa), ftp.nordu.net (Northern Europe), ftp.nis.garr.it 27 (Southern Europe), munnari.oz.au (Pacific Rim), ftp.ietf.org (US East 28 Coast), ftp.isi.edu (US West Coast). 30 ABSTRACT 32 We present, QoSMIC, a multicast protocol for the Internet that 33 supports QoS-sensitive routing, and minimizes the importance of a priori 34 configuration decisions (such as core selection). The protocol is 35 resource-efficient, robust, flexible, and scalable. In addition, our 36 protocol is provably loop-free. 38 Our protocol starts with a resources-saving tree (Shared Tree) and 39 individual receivers switch to a QoS-competitive tree (Source-Based 40 Tree) when necessary. In both trees, the new destination is able to 41 choose the most promising among several paths. An innovation is that we 42 use dynamic routing information without relying on a link state exchange 43 protocol to provide it. Our protocol limits the effect of pre- 44 configuration decisions drastically, by separating the management from 45 the data transfer functions; administrative routers are not necessarily 46 part of the tree. This separation increases the robustness, and 47 flexibility of the protocol. Furthermore, QoSMIC is able to adapt 48 dynamically to the conditions of the network. 50 The QoSMIC protocol introduces several new ideas that make it more 51 flexible than other protocols proposed to date. In fact, many of the 52 other protocols, (such as YAM, PIM-SM, BGMP, CBT) can be seen as special 54 Draft The QoSMIC Multicast Protocol April 1998 56 cases of QoSMIC. The goal of this document is to present the motivation 57 behind, and the design of QoSMIC, and to provide both analytical and 58 experimental results to support our claims. 60 NOTE: The text version of the draft is missing several figures, that 61 facilitate the understanding of the work. For this, the authors suggest 62 the postscript version. 64 Contents 66 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 67 2 Model Definition and Background Work 6 69 2.1 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . 8 71 3 Overview 9 4 Detailed Description 11 73 4.1 The Search for Candidates . . . . . . . . . . . . . . . . . . 11 74 4.2 Connection Establishment . . . . . . . . . . . . . . . . . . .14 75 4.3 Leaving a Group . . . . . . . . . . . . . . . . . . . . . . . 15 76 4.4 Candidate Selection. . . . . . . . . . . . . . . . . . . . . .15 77 4.5 Manager and Inter-domain Issues . . . . . . . . . . . . . . . 17 79 5 The Control Overhead 18 6 Experimental Results 21 81 6.1 Routing Efficiency . . . . . . . . . . . . .. . . . . . . . . .22 82 6.2 Overhead Complexity . . . . . . . . . . . . . . . . . . . . . 23 84 7 Implementation Details 25 86 7.1 Intree Router State . . . . . . . . . . . . . . . . . . . . . 25 87 7.2 Router Actions . . . . . . . . . . . . . . . . . . . . . . . . 27 89 7.2.1 Joining a session . . . . . . . . . . . . . . . . . . . . . .27 90 7.2.2 Leaving a Group . . . . . . . . . . . . . . . . . . . . . . .28 91 7.2.3 The TAKE-OVER procedure. . . . . . . . . . . . . . . . . . . 28 92 7.3 Source Specific State . . . . . . . . . . . . . . . . . . . .. 29 94 8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . 30 95 A Efficiency Parameters of Multicast Protocols . . . . . . . . . 33 97 1 Introduction 99 Multicasting can be defined as the distribution of the 100 same information stream from one to many nodes concurrently. In the last 101 few years, multicast routing has attracted a lot of attention from the 103 Draft The QoSMIC Multicast Protocol April 1998 105 networks community, since many emerging applications are of multicast 106 nature, such as teleconferencing, tele-education, and computer supported 107 collaborative work. A multicast connection can substitute for many 108 unicast connections carrying the same information, while reducing the 109 load on the network. Multicast algorithms try to minimize the routing 110 cost of the tree, which forms the simple multicast routing problem, or 111 Steiner tree problem [24]. In practice, the applications and practical 112 constraints complicate the problem with additional requirements [7]. 114 The Internet is a packet-switching network that principally provides 115 best-effort service. That is, there are no guarantees for the services 116 and applications that run over it; applications may "starve", end-to-end 117 delays may be arbitrary, and packets may be lost. Traditional Internet 118 routing protocols do not consider Quality of Service (QoS) metrics. For 119 the support of multicast connections, a multicast backbone (MBone) was 120 introduced as a virtual network "on top" of the Internet [9] in 1992. 121 The MBone is expected to be phased out, as the routers in the Internet 122 become multicast capable. In the rest of this document, we use the term 123 router to imply a "multicast capable Internet router", unless otherwise 124 stated. 126 Our work is motivated by the need to support QoS-sensitive multicast 127 applications. The marketability of any kind of service depends heavily 128 on its ability to to provide a level of quality. Currently, the services 129 over the Internet are limited by the best-effort nature of the network. 130 However, the scope of our work extends beyond the current use of the 131 Internet to a fully-commercialized environment with competing service 132 providers. We are convinced that such commercial services will need to 133 guarantee their QoS, and that some users will be willing to pay to have 134 such guarantees. 135 In addition, QoS in multicasting is not as problematic as in 136 point-to-point connections. The reason is that in multicasting we keep 137 anyway connection specific state in routers. Thus, adding QoS 138 connection specific information is straightforward and increases 139 the routing state only by a constant. 141 A multicast protocol that considers QoS in its routing phase can create 142 a tree better suited to the needs of QoS-sensitive applications. 143 However, the straightforward approach of exchanging dynamic link-state 144 metrics to compute QoS based routes does not scale to large networks. We 145 can distinguish two categories among Internet multicast protocols based 146 on QoS considerations: QoS-oblivious protocols [1] [10], [19] [17]; and 147 QoS-sensitive 148 protocols [3] [25]. An overview of the above protocols is presented in 149 the next section. 151 Our protocol was designed with the following primary goals [27]. 153 Draft The QoSMIC Multicast Protocol April 1998 155 1. QoS Support. We want to provide a framework to support arbitrary 156 QoS requirements of users. To achieve this, we have to consider multiple 157 paths, and handle the link asymmetry, e.g. for satellite connections. 158 Note, that multiple paths can also be necessary for policy reasons. ffl 160 2. Limited Impact of Pre-configuration Decisions. We want to limit the 161 impact of any a priori configuration decisions, such as the choice of 162 special status routers (PIM-SM, CBT, and BGMP), or a special 163 partitioning of the multicast address space (BGMP [19] [12]). 165 In our effort to propose an improved protocol, we identified a group of 166 weaknesses of some of the current and proposed MBone protocols. We 167 transformed this group into the following list of secondary design 168 guidelines. 170 1. Efficiency. Our protocol should construct distribution trees that use 171 the network resources efficiently. 173 2. Application sensitive. It should accommodate diverse applications 174 types with minimal user input. 176 3. Scalability. It should scale well for large networks, many groups, large 177 group-sizes etc 179 4. Robustness. It should be robust to failures, even of special status 180 components, e.g. core routers. 5. Loop-freedom. It should not create 181 cycles. 183 Our protocol constructs trees based on a greedy heuristic [18], that 184 connects each user to the "closest" branch of the existing tree and 185 leads to efficient resource use. Using the greedy approach, our protocol 186 offers alternate paths to enable the support of QoS requirements. The 187 protocol uses dynamic routing information, without assuming an 188 underlying protocol to provide it. Another innovation is that our 189 protocol does not require pre-configuration decisions; its efficiency 190 does not depend on the selection of a special status router, or a 191 special partitioning of the multicast address space. Finally, our 192 protocol can be seen as a flexible framework that encompasses the 193 behaviour of most of the previous protocols, when sensitivity to QoS is 194 not required. 196 The rest of this document is structured as follows. In Section 2, we 197 present our model and related work. Section 3, we present an overview of 199 Draft The QoSMIC Multicast Protocol April 1998 201 our protocol, while in Section 4, we offer a more detailed description. 202 In Section 5, 203 we compare the resource and control efficiency of our protocol with that 204 of other protocols. Section 6 provides some simulation results 205 concerning resource and message efficiency. In Section 7, we present 206 some implementation details of our protocol. In Section 8, we summarize 207 our work. 209 2 Model Definition and Background Work 211 Conceptually, the structure of 212 the Internet can be decomposed into three levels (see Fig.1). The 213 workstations (hosts) of the users are connected to a Local Area Network 214 (LAN) such as Ethernet. Each LAN has a Designated router which 215 communicates directly with each host using the Internet Group Membership 216 Protocol (IGMP) [6]. This is the first or LAN level. We use the term 217 Destination to refer to the designated router that has a group member in 218 its LAN. The designated router is connected with other routers forming 219 domains, which is the second or intra-domain level. The domains are 220 interconnected with routers that are called Border routers. The network 221 of domains is the third or inter-domain level. This creates a three 222 level hierarchy that allows the co-existence of different technologies 223 and facilitates the scalability of the network. We can have different 224 protocols at the intra-domain and inter-domain levels, as long as they 225 can interoperate. Routing at the inter-domain level imposes more 226 restrictions due to scalability considerations. Our protocol could be 227 used in both levels. It is flexible enough to adapt to the needs of 228 different environments, and scales well in the inter-domain case. 230 A multicast group is associated with a Class-D or multicast address. A 231 host knows the address of the group it wants to join through an 232 advertising or query mechanism such as the Session Description Protocol 233 (SDP) [15]. A multicast group can have multiple sources and the 234 distribution of the packets can be done in two ways. First, each source 235 can create its own distribution tree, called a Source-Based Tree, with 236 itself as the root. Second, all sources can distribute their packets 237 using the same tree, called a Shared Tree. Source-Based Trees have 238 better end-to-end performance (e.g. lower delay), and distribute the 239 traffic of each group across the network, but lead to large routing 241 Draft The QoSMIC Multicast Protocol April 1998 243 tables [2] [23]. 244 [NOTE: Source-Based Trees require a routing entry per source per group, while 245 Shared Trees require a single routing entry per group.] 246 On the other hand, Shared Trees concentrate the 247 traffic of a group onto a few links in the network. This concentration 248 is bad in the case where all sources are active simultaneously (e.g. 249 Distributed Interactive Simulation), but it can be beneficial when 250 sources take turns in transmitting (e.g. audio-conferencing). The two 251 approaches have complementary behavior, and are both useful in different 252 situations. 254 The efficiency of a multicast protocol can be defined by set of 255 functional properties. End-to-end delay and setup time are properties of 256 interest to the application, while traffic concentration, packet 257 replication, routing state and control overhead are important to the 258 service provider. Scalability of the above properties to large networks 259 is an overriding concern for protocol and network architecture design. 260 In Appendix A, we present an extended list of the efficiency aspects of 261 protocols. 263 In our protocol, we compare paths in terms of their ability to support 264 an application at a specific QoS level. Quality of Service (QoS) denotes 265 the user-perceived quality. Recently, Zappala et al. [25] used the term 266 Quality of Route (QoR) to refer to multiple static parameters of the 267 route (e.g. link capacity, delay, or reliability), and this was adopted 268 in the YAM protocol [3] (In a private communication, the authors stated 269 that they have also been considering the use of dynamic information.). 270 In our work, we suggest the use of dynamic 271 metrics, (e.g. available bandwidth, current delay), because these 272 provide paths that can meet QoS requirements at a given moment. 273 Furthermore, routing with dynamic metrics can respond pro-actively to 274 link congestion. However, exchange of dynamic link-state metrics has 275 scaling problems. Thus, we do not require the use of dynamic metrics in 276 the link state exchange protocol. Dynamic metrics are used instead to 277 evaluate and select from the alternate paths proposed by our protocol. 278 This distinction will become more clear after the protocol overview. To 279 summarize, our protocol enjoys the benefits of QoS routing, 280 without suffering from the scalability restrictions. 282 For the rest of this document, the term "QoS of a route" denotes the 283 quality that the route is expected to deliver to a connection given its 285 Draft The QoSMIC Multicast Protocol April 1998 287 current state, and is calculated from dynamic metrics of properties such 288 as bandwidth or delay. However, the terms "distance" and "proximity" for 289 routers are defined using static metrics of the same properties. It is 290 important to stress that our protocol is compatible with any metric of 291 the routing quality of a path, and the specific metric to use is 292 application dependent. 294 2.1 Previous Work 296 QoS-oblivious protocols. These protocols provide one 297 route when a new member joins, and QoS is not considered in the 298 selection of the route. Example of such protocols are Core Based Trees 299 (CBT) [1], Protocol Independent Multicasting - Sparse Mode (PIM-SM) 300 [10], Border Gateway Multicast Protocol (BGMP) [19], and Multicast 301 Internet Protocol (MIP) [17]. All these protocols assume rooted trees, 302 with a core router which is the center of the distribution tree. BGMP 303 and MIP imply the use of rooted trees. In BGMP, for example, each 304 domains "owns" an address space and is the root of the distribution tree 305 with such an address. In all these protocols, the tree is the union of 306 the reverse shortest paths between the core and each destination. 307 Reverse shortest paths are used because they can be computed from the 308 unicast routing database without requiring additional information. CBT 309 creates only Shared Trees while PIM-SM and BGMP, permit the creation of 310 Source-Based Trees for very active sources (high data rate). The MIP 311 protocol introduces novelties on administrative and correctness issues, 312 and guarantees loop-free Shared Trees and Source-Based Trees. The 313 assumption of rooted trees simplifies routing, but introduces the core 314 selection [20] and address partitioning [12] problems, which can affect 315 the protocol performance significantly. 317 QoS-sensitive protocols. These protocols offer multiple routes to a new 318 member, who selects the best such path. Carlberg and Crowcroft [3] [4] 319 suggested the YAM protocol, which creates Shared Tree considering 320 multiple routes. The destination router searches its neighborhood and 321 finds routers that are part of the tree of the desired group. This way, 322 the new router selects the most promising route. Routing in YAM relies 323 mainly on this neighborhood search, but this procedure can increase the 324 control overhead significantly. A suggested method to address this 325 problem requires a sense of source/root domain, which is not applicable 326 in Shared Trees unless we assume an address partitioning mechanism. 327 Zappala et al. [25] suggested 328 a multicast protocol that provides alternate routes to avoid a 329 bottleneck link. This protocol does not seem applicable in the case 330 where QoS suffers from several mildly-congested links. Finally, both 331 protocols use only static routing information, which can lead to poor 332 QoS performance3. An analogy from real life is driving: when we drive we 333 want to have the option of multiple routes, but also we want up to date 335 Draft The QoSMIC Multicast Protocol April 1998 337 information of the traffic on each of them. Following small streets is 338 faster than driving on a congested highway. 340 The YAM protocol can be seen to implement the greedy heuristic. The 341 greedy routing scheme has been shown to outperform the commonly used 342 Shortest Paths routing in various analytical [18] [16] [13] and 343 experimental [21] [8] [22] studies. On average, the studies suggest a 344 10-30% advantage of the greedy approach in the efficiency (cost) of the 345 distribution tree. 347 3 Overview 349 [**] 350 Figure 2: An overview of QoSMIC. 352 Our protocol creates Shared Trees by 353 default and Source-Based Trees when needed. In both cases, the protocol 354 offers alternate paths for each connection (see Fig. 2(a)). 356 We introduce the notion of a Manager router of a group. The Manager 357 administers a specific multicast group, and facilitates the joining of 358 the new group members. The fundamental difference between a core router 359 and a 360 Manager is that the distribution tree is not rooted at the Manager. This 361 way, the selection of the Manager has marginal effect on the topology of 362 the tree. Furthermore, we can have multiple Managers and change the 363 Managers during the lifetime of the group without any data loss, as we 365 Draft The QoSMIC Multicast Protocol April 1998 367 will see later in this section. 369 Joining a group. The Designated router of the new member, which we call 370 New router, will try to connect to the most promising path to the tree, 371 according dynamic metrics defined by the application. The New router 372 identifies several intree routers as Candidates or potential points to 373 join to the tree. This search is conducted by two procedures: one from 374 the side of the New router (Local Search), and one from the side of the 375 tree (Multicast Tree Search) (see Fig.2.b), both operating in parallel. 376 For the moment, we consider a purely intra-domain or purely inter-domain 377 scenario. 379 1. The Local Search Procedure. The New router searches its neighbor 380 hood, using a reverse path multicast of probe messages, with scope 381 limited by use of the time-to-live (TTL) field for its closest intree 382 router. Every intree router that receives the probe message is 383 considered a Candidate router, and responds with an "advertisement 384 message" unicast to the New router. This procedure is also used in the 385 YAM protocol. 387 2. The Multicast Tree Search Procedure. The New router contacts the 389 Manager router of the group, and the Manager router "informs" the tree 390 of the New router. Some intree routers are selected as Candidates. They 391 advertise themselves to the New router with a unicast "advertisement" 392 message. In the next section, we propose several mechanisms, centralized 393 and distributed, to select Candidates. 395 Eventually, the New router compares all the possible connection paths, 396 and selects the best path according to the needs of the application. The 397 New router sends one more message (JOIN) towards the selected Candidate, 398 to set up the routing state along the path and the chosen router starts 399 forwarding the data. The routing state is soft-state, but pinned, so 400 that as long as the New router keeps sending JOIN refreshes, the route 401 does not change. It should be clear from the above description that our 402 protocol implements a greedy routing heuristic. 404 The path chosen by the advertisement messages depends on the static QoR 405 metrics contained in the routing information base. The specific metric 406 used by the routing protocol depends on the needs of the application. 407 For example, real-time applications will prefer paths of minimum end- 408 to-end delay, while data transfers may prefer paths of maximum bandwidth 409 or low 410 packet loss ratio. Current routing protocols already have the ability to 412 Draft The QoSMIC Multicast Protocol April 1998 414 carry multiple static metrics. 416 However, the advertisement messages can collect up-to-date dynamic QoS 417 metrics along the path that they travel (e.g, by interacting with RSVP 418 [26], or using measurement based metrics). Thus, although the paths that 419 the Candidates choose is restricted by the static information in the 420 routing information base, the New router selects among these paths using 421 dynamic routing information. 423 Source-Based Trees. Using Shared Trees minimizes the routing table 424 information to an entry per group. However, Shared Trees may fail in the 425 following two cases. First, when a group has many highly active sources 426 simultaneously, the bandwidth of the shared links may not be able to 427 accommodate all the traffic. Second, when the QoS requirements of a user 428 are not met along the Shared Tree, we have to find a different source- 429 to destination path. In both these cases, we resort to Source-Based 430 Trees. The switch from a Shared Tree to a Source-Based Tree of a 431 specific source is initiated by the Designated router of a receiver. The 432 procedure for establishing the Source-Based Tree is similar to the 433 procedure of the Shared Tree and uses the Local Search and the Multicast 434 Tree Search procedure to identify routers in the Source-Based Tree. To 435 avoid packet duplication, the Shared Tree is pruned on a source-specific 436 basis, for the sources for which Source-Based Trees have been 437 established. More details for the co-existence the two types of trees is 438 provided in Section 7. 440 4 Detailed Description 442 In this section, we describe the messages and 443 mechanisms used by our protocol in detail. After that, we explain the 444 process of Candidate selection, Manager selection, and interdomain 445 operation. Table 1 lists the different roles of the routers. Table 2 446 contains a list of the protocol messages. 448 4.1 The Search for Candidates 450 We assume that the New router receives a 451 request to join a multicast group. To simplify the presentation, we 452 assume that the new member is a receiver4. 454 A source joins a group in a way similar to a receiver; it connects to 455 the closest router of the Shared Tree. A difference is that the dynamic 456 metrics of the path are collected "towards the tree", i.e., in the 457 direction the data will flow. 459 Table 1 -- START 461 Router Name --- Role 463 Manager router: Supervises the group and facilitates the 464 joining procedure; does not necessarily participate in the 465 data distribution tree. 467 Candidate router: Considered as possible joining point for a new 469 Draft The QoSMIC Multicast Protocol April 1998 471 connection. 473 Designated router: Connected to a set of users (e.g. LAN), 474 receives requests 475 from users (e.g., using IGMP) and initiates searches. 477 New router: Designated router of the LAN containing the new member. 479 Destination router: Designated router of a LAN that has active group 480 members. 482 Intree router: All routers that are part of the distribution tree. 484 Intermediate router: Intree router that is not a Destination or a Source. 486 Border router: Router that connects multiple domains. 488 Table 1: The different roles of the routers. -- END 490 Table 2 --- START 492 MESSAGE Explanation 494 BID-REQ: New router searches locally for intree neighbors 496 BID: Candidate "proposes" to the New router; Message 497 collects dynamic QoS metrics along the path 499 M-JOIN: New router contacts the Manager who initiates a 500 Multicast Tree Search 502 BID-ORDER: The Manager "orders" the intree nodes to 503 send bids 505 JOIN: The New router sends a message up its selected 506 path to the tree to establish/refresh routing state 508 PRUNE: Departing Destination tears down unwanted part 509 of tree; can be for a source or for a group 511 Table 2: An explanation of the messages of our protocol. --- END 513 Draft The QoSMIC Multicast Protocol April 1998 515 [***] 516 Figure 3: The Take-Over procedure: an intree router that lies in the 517 path from the Candidate to the New router can replace the Candidate. 519 The Join is received via IGMP on a LAN at the intra-domain level, or 520 from an intra-domain protocol at a Border router at the inter-domain 521 level. If the New router is part of the group already, the connection is 522 established locally. If the New router is not part of the group, the 523 Local Search and the Multicast Tree Search procedures are employed. 525 Local Search. The New router tries to identify neighboring intree 526 routers. 528 1. The New router "floods" a BID-REQ message in its neighborhood. 529 Reverse path multicasting with scope controlled by the Time To Live 530 (TTL) field is used to control the message complexity of this phase. 531 This procedure is the same as proposed in YAM, but because we also have 532 the Multicast Tree Search, we can keep the final TTL much smaller. This 533 advantage is quantified later analytically and experimentally. 2. Every 534 intree router that receives a BID-REQ message, becomes a Candidate 535 router, and replies with a BID message, which is unicast to the 536 New router. The BID message on its way collects information on the 537 expected performance of the path, based on dynamic QoS metrics. The 538 Candidate router considers the New router as a tentative dependant, and 539 cannot leave the tree unless the tentative status is timed out. 541 3. The New router collects the BID messages. The procedure terminates 542 unsuccessfully, if the New router does not receive any replies before 543 the expiration of a timer set for this purpose. Otherwise, we enter the 544 phase of establishing the connection (see Section 4.2). 546 Multicast Tree Search. The New router contacts the Manager and the 547 Manager causes some of the intree nodes to propose themselves as 548 Candidate routers. The selection of Candidates is an important aspect of 549 our protocol and it is discussed later in this section. The sequence 550 of actions is as follows: 552 1. New router sends an M-JOIN message to the Manager of the group. 553 2.The Manager "orders" a bidding session with a BID-ORDER message. 554 Some subset of the routers that receive the BID-ORDER are selected as 555 Candidates. 556 3. The Candidates unicast BIDs to the New router. The BIDs 557 are identical to the BIDs in the Local Search. 559 Draft The QoSMIC Multicast Protocol April 1998 561 For both the Local and the Multicast Tree Search, if an intree router 562 receives a BID message (for the same tree), the router takes the place 563 of the Candidate by "dumping" the original BID and initiating a new BID 564 message in a procedure called Take-Over (see Fig. 3). This is important 565 to prevent multiple copies of packets. If a router with tentative state 566 (i.e., one that has received a BID but not yet established a 567 connection), receives a BID for the same (tree, New router, Candidate), 568 the BID is discarded to maintain loop freedom. 570 4.2 Connection Establishment 572 Having performed the BIDding phase, we will 573 examine how the connection is established. 575 1. The New router selects the best Candidate according to the dynamic 576 QoS metrics collected by the BIDs. 577 2. The New router sends a JOIN message to its best BID. This message 578 traverses in the opposite direction the path used by the BID message, 579 and establishes soft state along the path. 580 3. When the chosen Candidate receives the JOIN message, it changes 581 state to the connected state, and starts transmitting data packets on 582 the newly set up path. 583 4. If an intree router receives a JOIN message 584 for a different Candidate, 585 it performs a TAKE-OVER, terminates the message and starts forwarding 586 data on the newly set up path. 588 4.3 Leaving a Group 590 A Designated router receives a leave request through 591 the same protocol that communicated the join request. The request can be 592 for a whole group or for a source of a group. Whenever a router senses5 593 a change in the membership, it removes the link from the distribution 594 tree, and checks whether it has become a leaf of the related tree. If 595 so, it sends a PRUNE message up the tree and removes state for the tree 596 from its database, thereby ceasing to be an intree router for that tree. 598 4.4 Candidate Selection. 600 During the Multicast Tree Search, the Manager 601 must select an appropriate subset of the intree routers as Candidates. 602 This can proceed in a centralized or a distributed way. 604 1. Centralised Selection. If the Manager has sufficient knowledge of the 605 tree and the network topology, the manager can select the set of 606 Candidates directly. This can happen if the domain is running a link 607 state protocol, or if the manager has access to a routing information 608 database. In this case, the Manager identifies promising Candidates, 610 Draft The QoSMIC Multicast Protocol April 1998 612 either on demand or statically. Then, the Manager unicasts the BIDORDER 613 to them. If the selection is based on accurate information, we can find 614 the right Candidates with limited overhead cost. Note, that with this 615 mechanism, our protocol can behave like CBT or BGMP; a Manager can 616 trivially act as a core router by considering itself as the only 617 Candidate. 618 2. Distributed Selection. In the absence of centralized 619 information, each 620 intree router has to decide whether to become a Candidate in a 621 distributed way. We assume that each router has a static estimate of its 622 distance to the New router. We have the Manager join the tree as a 623 source6 and multicast the BID-ORDER along the tree 624 (Note, that this does not contradict the flexibility of the role of the 625 Manager, since 626 it only transmits control messages and receives nothing. For example, 627 the Manager can change without disrupting the data distribution.). 628 All intree routers 629 receive the BID-ORDER and decide in a distributed way if they should 630 become Candidates. Naturally, the more intree routers become Candidates, 631 the more "accurately" we find the closest Candidate to 632 the New router, but the more the control overhead. We propose the 633 following orthogonal mechanisms that can be used in combination to 634 strike the balance in this trade-off. 636 (a) Directivity. We discourage distant routers from becoming Candidates. 637 The BID-ORDER keeps track of the (so far) minimum distance of 638 the tree and the New router. A router with a distance greater than this 639 minimum does not become a Candidate, and, if the relative distance 640 exceeds a threshold, the BID-ORDER is not forwarded further. 641 (Note that a similar mechanism appears in YAM [3], but it is used to 642 reduce the overhead of its Local Search. YAM needs to assume rooted 643 trees for this). 645 (b) Local Minima. In absence of global knowledge, we select locally 646 optimal routers as Candidates. As the BID-ORDER message travels along a 647 branch, the distance to the New router of the previous two routers is 648 included in the message. If router i + 1 sees that router i was closer 649 to the destination than both routers i+1 and i- 1, it sends a 650 message back to router i, which becomes a Candidate. 652 (c) Fractional Choice. We can choose as Candidates a representative 654 Draft The QoSMIC Multicast Protocol April 1998 656 fraction (1/n) of either all intree routers or the ones that meet the 657 other two criteria. For the implementation, we only need a log n-bit 658 wrap-around counter in the BID-ORDER message. 660 Choice of Mechanisms. We identify combinations of the previous 661 mechanisms that seem more promising. The final choice will have to 662 consider the network topology and the traffic behavior. Some preliminary 663 analysis is presented in Section 5. More detailed simulation studies are 664 needed in this direction. 666 If topology information for the entire domain is available, Manager 667 Selection offers the lowest control overhead for a reasonable selection 668 of Candidates. In the absence of such information, Fractional Choice and 669 Directivity together is simple to implement, and may lead to 670 satisfactory solution with a careful choice of parameters. Local Minima, 671 Fractional Choice and Directivity is more sophisticated and promises 672 improved results, but we want to determine if the gain justifies the 673 slightly increased complexity. 675 4.5 Manager and Inter-domain Issues 677 Manager Address Distribution. For the Multicast Tree Search, 678 the New router needs to know the address of 679 the Manager and of the group and both addresses can be made known 680 through the same mechanism (e.g. Session Directory tool [15]). 681 Alternatively, the address of a local Manager within a domain can be 682 broadcasted via the Domain Wide Reporting [14] or can be provided on 683 demand (by the Border routers or an administrative database). 685 Manager versus Core Router. The main purpose of the Managers is to 686 invoke the Multicast Tree Search. Since Managers are not key routers for 687 data distribution, we can replace a Manager during a session by simply 688 advertising a new Manager. In contrast to a core change, a Manager 689 change does not cause any data loss or any change in the distribution 690 tree. For a smooth transition, the old Manager can "resign", after the 691 new Manager has been around for a sufficiently long time (depending on 692 the size of the network). 694 Multi-Domain Multi-Level Operation. Our protocol can be used at both the 695 intra-domain and the inter-domain level. If the domain already has 696 active group members, the search for Candidate routers is carried out 697 within the domain. If not, the connection has an intra-domain and an 698 interdomain part. Inside the domain, the New router contacts one or more 699 Border routers. The Border routers find their best path to the group at 701 Draft The QoSMIC Multicast Protocol April 1998 703 the inter-domain level. If the inter-domain protocol is QoSMIC, then the 704 Border routers initiate searches using the procedures of QoSMIC. Each 705 Border router that finds a path to the tree proposes itself to the New 706 router (BID message). The New router chooses the "best" Border router. 707 The selected Border router becomes the Designated Border router for this 708 group (or Source-Based Tree). Finally, if one of the levels is running a 709 different protocol, an interface similar to that in [19] will allow 710 interoperation. 712 Selecting Manager Routers. In practice, we want to have multiple 713 Managers that will co-operate for efficient and scalable solutions with 714 reduced set-up time. For this we have concluded in the following scheme. 715 We have at least one Manager per domain. This way the intra-domain and 716 inter-domain protocol can be independent. We prefer Border routers for 717 Managers. This way, the Manager can communicate with routers inside and 718 outside the domain more easily. Thus, by default, we select the 719 Designated Border router of the group to be the Manager in a domain. In 720 the creation of a session, the Border router nearest to the session 721 initiator becomes the Designated router. For a domain that joins the 722 distribution tree, the selection of the Designated router was described 723 in the previous paragraph. 725 Table 3 -- START 726 Symbol: Explanation 728 t: The maximum TTL value of the Local Search 729 c: The number of Candidates 730 w: The average degree of a router 731 T: The average size of a multicast tree 732 Hop(a; b): The average distance in hops from a to b 733 Hop_avg: The average hop distance between Manager and Candidates 734 Join(c): The message complexity of the joining part with c Candidates 736 Table 3: Analysis parameters and their symbols. 738 For a Source-Based Tree, we select the source as the Manager in its own 739 domain to simplify the administration of the tree. It is important to note 740 that these choices are the default ones, but as the execution progresses, we 741 can change to more appropriate Managers without any service disruption. 743 5 The Control Overhead 745 We compare the control overhead of YAM and 746 QoSMIC with analytical methods. We do not consider other protocols, 747 since they do not try to achieve QoS and resource optimized trees. Table 748 3 lists the parameters and their symbols. Most of these parameters 749 depend on the topology and the membership behavior of the applications. 750 In Table 3, the first two parameters can be altered by the protocol; t 751 depends on protocol decisions solely in all cases, while c, the number 752 of Candidates for the Multicast Tree Search is directly defined by the 753 protocol for the centralized case, and indirectly controlled for the 755 Draft The QoSMIC Multicast Protocol April 1998 757 distributed cases. Note that the protocol can modify its parameters 758 during the life-time of the group, and this accounts for the 759 adaptability of our protocol. 761 The Complexity of Selecting Candidates. The Local Search. Assume w to be 762 the average degree of a router. For simplicity, we consider only one 763 search with the a maximum TTL value of t. We consider the complexity to 764 be a function of the t, since the average degree, w, is given. In a 765 broadcast, a router that receives a message will forward it to w Gamma 766 1 links on average. Assuming a reverse path multicasting method, every 767 router in the neighborhood receives such a message exactly 768 once. This way, the complexity8 of the Local Search with one expanding 769 search is as follows 771 Local(t) = w *(w-1)^(t-1) 773 While for multiple expanding rings the complexity becomes 775 Local(t) = Sum_[i=1 to t] w * (w-1)^i 777 Since YAM depends entirely on the Local Search to find the Candidates, 778 we can assume that YAM will need to perform expanding rings search to 779 keep the complexity under control, while QoSMIC can perform a single 780 search with a small t, which explains the complexity difference in Table 781 5. 783 Draft The QoSMIC Multicast Protocol April 1998 785 The Multicast Tree Search. This procedure exists only in QoSMIC, and can 786 differ depending on which Candidate mechanism is used. The complexity is 787 c Centralised mechanism and loosely upper bounded by the size of the 788 tree, jT j, in the distributed mechanisms. In more detail, Table 4 789 demonstrates the complexity of the selection procedure and the relative 790 advantages for each of the four Candidate mechanisms we saw earlier. 792 The Complexity of Joining. In any case, the joining overhead is low 793 compared to the overhead of the search. Assume we have c Candidates. 794 Each of them sends a BID message to the New router. The New router sends 795 a JOIN message to one selected Candidate. The associated complexity 796 is approximately the same in both YAM and QoSMIC 797 as long as the number of candidates selected is kept roughly equal. 799 We compare the performance of the selection of Candidates in QoSMIC and 800 YAM protocols according to: the message complexity of searching, the 801 type of the selection, the information used in the selection. The 802 comparison is shown in Table 5. In terms of messages, QoSMIC can reduce 803 drastically the complexity given that it can rely on the Multicast Tree 804 Search procedure. In the centralised case it can be limited arbitrarily 805 (down to one Candidate), 807 [NOTE We calculate an upper bound of the complexity based on the average 808 degree of a the graph. A more precise bound would depend on the 809 topological properties of the graph. Such a study extends beyond the 810 scope of this document.] 812 Draft The QoSMIC Multicast Protocol April 1998 814 [**] 815 Table 4: Comparing the four Candidate selection methods in the Multicast 816 Tree Search. 818 [**] 819 Table 5: A comparison of the search procedures of QoSMIC and YAM. 820 Adaptable complexity type means that during the execution the protocol 821 can limit the overhead control while still offering at least one path 822 per join. 824 Table 6 -- START 826 Symbol: Protocol: Comments 828 Offline: -- : The off-line greedy algorithm used for reference 829 QoSMIC: QoSMIC, YAM: Greedy on-line using minimum cost join path 831 Draft The QoSMIC Multicast Protocol April 1998 833 RSP: PIM-SM, CBT, BGMP: Reverse Shortest Paths using a hop metric. 835 SP : -- : PIM-SM, CBT, BGMP could do Shortest Paths routing. 837 Table 6: The protocols in our simulations. --- END 839 and if necessary, we can also 840 dispense completely with the Local Search. In the distributed case the 841 Multicast Tree Search complexity is upper bounded by the size of the 842 tree. YAM relies uniquely on the Local Search procedure whose extent 843 should be large enough to reach the tree, and thus 844 we claim that the Local Search of YAM is more expensive. 846 6 Experimental Results 848 We study several aspects of our protocol through 849 simulations. Here, we present only two of our studies. We compare the 850 resource efficiency of the greedy routing scheme (YAM and QoSMIC) with 851 the Shortest Paths routing scheme of other protocols. We also examine 852 the overhead complexity of the Local Search, which dominates the 853 overhead complexity of YAM and QoSMIC. Other parameters necessary to 854 complete the efficiency profile of a protocol are end-to-end QoS, set-up 855 delay, traffic concentration and robustness. 857 We vary two parameters in the experiments. The group density (Grp) is 858 defined as the ratio of the group size over the network size (both 859 measured in nodes). The maximum asymmetry A is defined as the maximum 860 ratio of the opposite edges between a pair of routers, for all such 861 pairs. Naturally, for A = 1, we have an undirected graph. For each 862 figure, we supply the values of these two previous parameters. 864 For our network, we use the map of the major routers of the MBone in May 865 1994 produced by Casner [5]. This graph is appropriate for our 866 experiments, since it represents an actual instance of the inter-domain 867 multicast network. We eliminate routers with only one incident edge, 868 since such routers do not affect routing. We create a directed version 869 of the map replacing its unidirectional edge with a pair of directed 870 edges which we call opposite edges. The final graph has 32 routers, 80 871 pairs of opposite edges, and average degree of 2:5 . 873 For QoS-sensitive routing, the model should consider more than just a 874 hop metric. We need to include the notions of QoS performance of links 875 and of asymmetry (e.g. satellite links). For this reason, each link is 876 associated with a cost; a higher cost can be interpreted as congestion 877 or low QoS ability of the link. In our simulator, we initialize the cost 878 of each pair of directed links to a constant and then introduce 879 uniformly distributed asymmetry between 1 and A. Naturally, the cost of 880 a tree is the sum of the cost of its edges. 882 The protocols we simulate are presented in Table 6. We present 884 Draft The QoSMIC Multicast Protocol April 1998 886 measurements of the path lengths of a new branch and the efficiency of 887 the distribution tree. More accurately, we focus on the Shared Tree that 888 is created between one core (PIM, CBT) or one source (YAM, QoSMIC, BGMP) 889 and a set of receivers. Recall that PIM, CBT, BGMP create their Shared 890 Tree using the reverse shortest paths (receiver towards source) based on 891 the hop count metric that we denote by RSP. We use hop counts rather 892 than the cost metric for RSP, because that is what these protocols do, 893 and also because it is better than using the actual cost in the wrong 894 direction in an asymmetric link. However, we think that these three 895 protocols can easily become cost and direction sensitive, which would 896 correspond to the the Shortest Paths approach (SP). 898 In creating a session, we choose the participants and the core/source 899 randomly. We start from the core/source and add one receiver at a time. 900 We run every experiment 45 times to smooth the irregularities of special 901 cases. The 95% confidence interval was roughly within 5% of the plotted 902 value, and it is displayed when this does not clutter the figure. 904 6.1 Routing Efficiency In Figure 4, we study the cost of the 905 distribution tree of the different protocols. Figure 4(a) shows the tree 906 cost versus the group density for an asymmetry of ten. In Figure 4(b), 907 we plot the tree cost versus the maximum asymmetry for a group density 908 of 18%. Given the uniform distribution of the asymmetry, the average 909 asymmetry is (A + 1)=2 , A=2. Based on these figures, we make the 910 following observations. 912 QoSMIC and YAM create more efficient trees. The greedy routing of QoSMIC 913 and YAM outperforms SP by up to 20% (Fig.4(a)) and RSP by up to 60% 914 (Fig.4(b)), in agreement with previous literature (see Sec.3). 916 Direction-aware routing is crucial. In asymmetric environments the 917 awareness of the data flow is significant. The direction-aware Shortest 918 Paths approach, SP, outperforms RSP by as much 42%. This suggests that 919 the 921 Draft The QoSMIC Multicast Protocol April 1998 923 [**] 924 (a) Tree Cost versus group density (b) Tree Cost versus maximum 925 asymmetry 926 Figure 4: Routing Efficiency relative to the Offline multicast 927 tree. 929 PIM, CBT, BGMP can benefit greatly from a consideration of the directed 930 cost. 932 6.2 Overhead Complexity The complexity of Local Search depends on the 933 TTL value, which should be at least as large as the expected hop- 934 distance between the New router and the closest point to the tree. In 935 Figure 5, we study the paths that QoSMIC and YAM use for their joins. In 936 Figure 5(a), we plot the average path length versus the group density 937 for a symmetric network. In Figure 5(b), we plot the distribution of 938 paths according to their length in a symmetric network for groups up to 939 half the size of the network. For comparison, we plot the path 940 distribution of SP. We extract the following two conclusions. 942 Using Local Search pays off. In Figure 5(a), path length reduces quickly 943 as the group density increases. This way, the Local Search can be useful 944 even for relatively sparse groups. This is supported also by the 945 evidence in Figure 5(b): more than 50% of the paths (first two columns) 946 have length less than 2. Therefore, we conclude that a Local Search even 947 with a small TTL value can be beneficial. 949 The importance of Multicast Tree Search. In Figure 5(b), we see that a 950 small percentage of the paths have lengths as large as 8. If we rely 951 uniquely on the Local Search (as YAM does) then the TTL of the search 952 should be at least as large or else some routers would be excluded from 953 some 955 Draft The QoSMIC Multicast Protocol April 1998 957 [**] 958 (a) Average path length versus group density. (A = 1; Grp = 1 Gamma 959 100% ) 960 (b) The number of paths versus the path length (A = 1; Grp = 3 Gamma 961 50%) 962 Figure 5: The path length of a new join for QoSMIC. 964 distant multicast 965 sessions. This suggests that Local Search alone would need large TTL 966 values, which increases the overhead complexity significantly. 968 As a conclusion, we want to have a limited Local Search to take 969 advantage of the many "short" joins, but we need a second search 970 mechanism to provide solutions when the Local Search falls short. For 971 this environment, a single Local Search of 2 hops seems a reasonable 972 choice for QoSMIC, while YAM would have to go up to 8. 974 Scalability of message complexity. Using data from our simulations, we 975 calculate of the overhead of the searches of YAM and QoSMIC using the 976 analysis of Section 5. Namely, from the experiment of Figure 5(b), we 977 get the number of joins, and the distance of the node from the tree. 979 YAM: The maximum TTL of a Local Search should be at least as large as 980 the maximum path length or else some routers would be excluded from some 981 distant multicasts. Thus, the maximum TTL is set equal to the path 982 length of the join. We increase the diameter of each expanding ring by 983 one. This way, although the set-up delay may suffer, we attempt to 984 minimize the message complexity of YAM. 986 Draft The QoSMIC Multicast Protocol April 1998 988 QoSMIC: The Local Search does not have to succeed for every join, since 989 we have the Multicast Tree Search to fall back on. This way, we choose a 990 maximum TTL value of 2, as suggested earlier. In addition, we over- 991 estimate 993 [**] 994 Figure 6: The control overhead of the Candidate search in YAM and 995 QoSMIC. 997 the messages of Multicast Tree Search by considering it equal to the 998 number of intree nodes. However, using the mechanisms, the number of 999 messages should be smaller in practice. 1001 In Figure 6, we calculate the message complexity per join for various 1002 average degrees. The message complexity of YAM increases dramatically 1003 with the average degree, due to its large Local Search. In comparison, 1004 QoSMIC avoids this problem: having the Multicast Tree Search to fall 1005 back to we can afford to keep the Local Search small. Similarly, YAM 1006 would suffer from large networks, where the TTL value of the Local 1007 Search would have to be large. As a conclusion, YAM can be applied in 1008 small or sparse networks, but QoSMIC scales well to dense or large 1009 networks. 1011 7 Implementation Details The goal of this section is to highlight some 1012 implementation details of our protocol. 1014 7.1 Intree Router State 1016 For clarity, when we discuss the routing 1017 information of a router, we associate every link with a set of entries 1018 for each group. Note, that we try to use the terminology of the PIM-SM 1019 proposal [10] [11] to facilitate the readers familiar with these works. 1020 Furthermore, some of the actions of our protocol are done in a similar 1021 way to that of PIM-SM and we refer the interested 1023 Draft The QoSMIC Multicast Protocol April 1998 1025 [**] 1026 Router A Figure 7: The entries at the routing table for Shared Trees, 1027 Source Based trees and their transition. The figure shows the flow of 1028 packets from the source. 1030 reader there. 1032 We can distinguish the following routing entries for each link. 1034 A (*, G) entry corresponds to the shared tree of a group. By 1035 default, it is bidirectional. 1037 An (S, G) entry corresponds to a source-based tree of source S of 1038 group G. It is by definition uni-directional, so we can distinguish IN-only 1039 (S, G, IN) and OUT-only (S, G, OUT) entries. 1041 We enable source-specific pruning that we denote by (not-S, G). A 1042 packet that arrives from a link with such state is dropped. The main 1043 reason is to avoid packet duplication for destinations that have joined 1044 an Source-Based Tree. 1046 We use (*/S, G) as an abbreviation of the expression (*, G) or (S,G). 1048 Draft The QoSMIC Multicast Protocol April 1998 1050 7.2 Router Actions 1052 Here we study the actions of a router as triggered by control messages. 1054 7.2.1 Joining a session Join request. 1056 The request (*/S, G) can be either to the Designated router (via the 1057 IGMP protocol) or the border router (via an intradomain protocol). 1059 If the router is already part of the requested (*,G) or (S,G) tree, the 1060 join is accommodated there. If not, the router considers itself a 1061 destination router that we denote as New router, and performs the Local 1062 Search and Multicast Tree Search procedures. For the Multicast Tree 1063 Search, the New router sends an M-JOIN(*/S, G, New router) to the 1064 Manager of the group. For the Local Search, the New router broadcasts 1065 BID-REQ(*/S, G, New router, TTL) message in expanding rings. The 1066 messages follow a reverse path multicast. The TTL is initialised to a 1067 value as we saw before. A timer is set to monitor the responses. If the 1068 timer expires before any responses, then a new broadcast (ring) takes 1069 place with an increased TTL. The value of the TTL is bounded by a 1070 default value or is explicitly specified. When the timer expires for the 1071 maximum TTL value, without any responses, the procedure terminates 1072 unsuccessfully. 1074 BID-REQ(*/S, G, New router, TTL) message. On reception of a BID- 1075 REQ(*/S,G) message, a router that is part of the tree in question 1076 replies with a BID message. In a Source-Based Tree, the Candidate 1077 incorporates in the message estimates of the QoS it experiences (quality 1078 of the path from the source to the Candidate), when these are available. 1079 Note, that this way, we can maximize the end-to-end QoS that the New 1080 router will receive. In more detail, the BID message is of the form 1081 BID(*/S, G, New router, Candidate, Metrics): it includes the address of 1082 the Candidate, and estimates of the QoS of the path. The BID message on 1083 its way updates its metrics at each router to estimate the quality of 1084 the path. 1086 MJOIN(*/S, G, New router) message. This message is unicasted to the 1087 Manager of the group. For a (*,G) message, the manager sends BID- 1088 ORDER(*/S, G, bid-mechanism). The "bid-mechanism" represents the 1089 selection mechanisms that we saw earlier. The BID-ORDER can be either 1090 multicasted over the tree, or unicasted to pre-selected routers 1091 depending on the mechanism in use. 1093 BID-ORDER(*/S, G, New router, bid-mechanism) message. The actions on 1094 this message depend on the "bid-mechanism". In general, 1096 Draft The QoSMIC Multicast Protocol April 1998 1098 the message is either unicasted to the chosen Candidate or multicasted 1099 over the tree. In the first case, on receiving the message, the router 1100 unicasts a BID(*/S, G, Metrics) to the New router. In the second case, 1101 the router examines the criteria defined by the bid-mechanism, and if 1102 they are fulfilled, a BID message is sent to the New router, and the 1103 BID-ORDER is forwarded further along the tree. 1105 BID(*/S, G, New router, Candidate, Metrics) message. On receiving this 1106 message, if the router is the New router specified in the message, it 1107 updates a list of the best BIDs. An intree router invokes the TAKE-OVER 1108 procedure, and the router replace the Candidate. Any other router that 1109 receives a BID message, updates the Metrics field and forwards the 1110 packet. 1112 JOIN(*/S, G, New router, Candidate) message. This message travels 1113 towards the selected Candidate. When the Candidate router receives the 1114 message, it considers the connection as permanent (as opposed to 1115 tentative) and sets-up the path. Any intree router that receives the 1116 message invokes the TAKE-OVER procedure and starts forwarding data. 1118 7.2.2 Leaving a Group 1120 The leave request (*/S, G) can be either to the 1121 Designated router (via the IGMP protocol), the border router (via an 1122 intradomain protocol), or with a PRUNE message, or the result of state 1123 time out (assuming soft state refresh mechanism). If the request arrived 1124 from a LAN with active group members, the router does not do anything. 1125 In any other case, the link is removed from the distribution tree. Then, 1126 the router examines whether it has become a leaf of the tree. 1128 1. If the router has become a leaf of the (*/S,G) tree 1129 [Note, that leaf here implies also that the router does not have any 1130 hosts attached to its LAN.], it sends a 1131 PRUNE(*/S,G) message to its only tree link. 1133 2. If the router has two or more links in the tree (tentative or real), 1134 it does not take any further actions. 1136 7.2.3 The TAKE-OVER procedure. 1138 An intree router that receives a message 1139 between the Candidate and New router, may be able to take the position 1140 of the Candidate(see Fig. 3). This 1141 could lead to shorter delays and more efficient trees. This interception 1143 Draft The QoSMIC Multicast Protocol April 1998 1145 can happen in the messages: BID, JOIN. 1147 * The message is (*, G). 1149 - If the router is in (*, G), then TAKE-OVER. - If the router is in 1150 (S,G), then just forward the message. 1152 * The message is (S, G). 1154 - If the router is in (S,G), then TAKE-OVER. Optional refinement: 1155 if the current QoS from the source to here is worse than the expected 1156 QoS along the bidding path, then switch to the best path. 1158 - If the router is in (*,G). If the current QoS is not worse than the 1159 QoS of the bidding path, then TAKE OVER. If not, then just forward the 1160 message. 1162 7.3 Source Specific State 1164 The source-specific pruning is similar to that 1165 of PIM (see Fig. 7). A router that is part of both the (S, G) and the 1166 (*, G) tree, ignores packets from source S that do not arrive from the 1167 (S,G, IN) link. Furthermore, when a router receives an (S,G) packet from 1168 another link (the link that the Shared Tree used for the S-packets), it 1169 sends an S-specific prune message on that link. We denote by (not-S, G) 1170 the state of such a Shared Tree link. 1172 When we switch from the (*, G) to the (S, G) tree (see Fig.7), we want 1173 to minimize the data loss by stopping the reception of packets from the 1174 (*,G) tree only when data starts to arrive from the (S,G) tree. We use a 1175 flag SBTFLAG, which is similar to the SPT-bit of the PIM-SM protocol. 1176 When the request for Source-Based Tree is sent, we install an (S,G, 1177 SBT-FLAG= OFF) entry, but we continue to forward S-packets that we 1178 receive from the (*,G) link. The first data packet from the (S,G) link 1179 sets the flag (SBT-FLAG= ON). When this happens, we drop any S-packets 1180 coming from the (*, S) link, and we send S-specific PRUNE(S) messages 1181 along these links to stop the transmission of the S-packets from the 1182 previous router. This continues recursively along the path that does not 1183 require S-packets anymore. 1185 8 Conclusions 1187 We propose QoSMIC, a protocol for supporting QoS-sensitive 1188 multicast applications over the MBone. Our protocol identifies multiple 1189 paths, and selects the most promising one using dynamic information that 1190 the control messages collect. Our protocol creates Shared Trees by 1191 default and destinations switch to Source-Based Trees in order to 1192 accommodate the needs of different applications. This switch can take 1194 Draft The QoSMIC Multicast Protocol April 1998 1196 place for highly active sources or when the QoS requirements of 1197 receivers are not met. 1199 Our protocol includes the main concepts of the YAM protocol [3], and 1200 introduces several new ideas. Below, we list the characteristics of our 1201 protocol that differentiate it from YAM and/or the other protocols. 1203 1. Limited Impact of Pre-configuration Decisions. 1204 We separate the management from the data transfer functions, by 1205 introducing the concept of the group Manager in the place of the core 1206 router (PIM, CBT, BGMP, MIP). The choice of the Manager does not 1207 affect the distribution tree. This way we eliminate the problems of 1208 core router selection and the address partitioning problems of other 1209 protocols. 1211 2. Dynamic Routing Information. 1212 Our protocol uses dynamic routing information without relying on 1213 external mechanisms/protocols for information exchange. 1215 3. Scalability. We introduce the Multicast Tree Search, 1216 which allows us to reduce the scope of the Local Search. The 1217 complexity of the Local Search appears as the bottleneck in YAM. 1219 4. Efficient Resource Use. 1220 QoSMIC uses a greedy routing policy, which has been shown to outperform 1221 the Reverse Shortest Paths routing used by other protocols. 1223 5. Sensitivity to direction. 1224 QoSMIC takes care to compute metrics in the direction that the data will 1225 flow. This ensures much better performance in asymmetric networks. 1227 6. Robustness. 1228 The only special status router of QoSMIC are the Managers. If they fail, 1229 the recovery can be fast and with minimal data loss. Having multiple 1230 managers further enhances the robustness. 1232 7.Adaptivity during execution time. 1233 In the MBone it is rather difficult to foresee the behavior of the 1234 application and the users. Our protocol can adapt to the changing 1235 network conditions and requirements during the life of the group, for 1236 example, by changing the protocol parameters (see Section 5) or by 1237 switching Managers. 1239 Our simulations and analysis support the above claims. 1241 Future work. Several functions of our protocol, such as the candidate 1242 selection, can be implemented in different ways. A number of parameters 1243 of the protocol also need to be selected. While we have some analytic 1245 Draft The QoSMIC Multicast Protocol April 1998 1247 bounds on the expected behaviour, more detailed evaluation is needed to 1248 finalize the details. Currently, we are simulating in more detail our 1249 protocol and intend to implement a prototype. In parallel, we are interested 1250 in the QoS metric selection problem: we are examining the type of routing 1251 information appropriate for the different stages of our protocol, to 1252 describe the QoR and QoS of the routes. We believe that with the 1253 appropriate routing information our protocol can become an efficient 1254 solution for QoS-sensitive applications. 1256 References 1258 [1] A. Ballardie. Core Based Trees (CBT version 2) multicast routing. 1259 Internet Draft: IETF RFC 2201, 1997. 1261 [2] T. Billhartz, J. B. Cain, E. Farey-Goudreau, D. Fieg, and S. G. 1262 Batsell. Performance and resource cost comparisons for CBT and PIM 1263 mulitcast routing protocols. IEEE Journal of Selected Areas in 1264 Communications, 15(3):304-315, April 1997. 1266 [3] K. Carlberg and J. Crowcroft. Building shared trees using a one-to- 1267 many joining mechanism. ACM Computer Communication Review, pages 5-11, 1268 January 1997. 1270 [4] K. Carlberg and J. Crowcroft. Yet another multicast (YAM) routing 1271 protocol: Specification version 1. Unpublished manuscript, 1997. 1273 [5] S. Casner. Major MBONE routers and links. Available from 1274 ftp.isi.edu:mbone/mbone-topology.ps, 1994. 1276 [6] S. Deering. Host extensions for IP multicasting. Internet-Draft: 1277 IETF RFC 1112, 1989. 1279 [7] C. Diot, W. Dabbous, and J. Crowcroft. Multipoint communications: A 1280 survey of protocols, functions, and mechanisms. IEEE Journal of Selected 1281 Areas in Communications, 15(13):277-290, April 1997. 1283 Draft The QoSMIC Multicast Protocol April 1998 1285 [8] M. Doar and I. Leslie. How bad is naive multicast routing? Proc. 1286 IEEE INFOCOM, pages 82-89, 1993. 1288 [9] H. Eriksson. Mbone: The multicast backbone. ACM Communications, 1289 37(8):54-60, 1994. 1291 [10] D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M. 1292 Handley, V. Jacobson, C. Liu, F. Sharma, and L. Wei. Protocol independent 1293 multicast-sparse mode (PIM-SM): Protocol specification. Internet-Draft: 1294 IETF RFC 2117 available from ftp://ftp.ietf.org/internet-drafts/, 1997. 1296 [11] D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M. 1297 Handley, V. Jacobson, C. Liu, F. Sharma, and L. Wei. The PIM architecture 1298 for wide area multicast routing. IEEE/ACM Transactions on Networking, 1299 4(2):153-161, April 1997. 1301 [12] D. Estrin, M. Handley, S. Kumar, and D. Thaler. The Multicast 1302 Address Set Claim protocol. Internet-Draft:draft-ietf-idmr-masc-00.txt, 1997. 1304 [13] M. Faloutsos, R. Pankaj, and K. C. Sevcik. Bounds for the on-line 1305 multicast problem in directed graphs. Proceedings of 4th International 1306 Colloquium on Structural Information and Communication Complexity 1307 (SIROCCO '97), Monte Verita', Ascona, Switzerland July 24-26, pages 81- 1308 98, 1997. 1310 [14] W. Fenner. Domain wide multicast group membership reports. 1311 Distributed in the IDMR mailing list. To appear as a Working Draft, 1997. 1313 [15] M. Handley and V. Jacobson. SDP: Session description protocol. 1314 Internet Draft. Work in porgress., 1995. 1316 Draft The QoSMIC Multicast Protocol April 1998 1318 [16] M. Imase and B.M. Waxman. Dynamic Steiner tree problem. SIAM 1319 Journal on Discrete Mathematics, 4:369-384, 1991. 1321 [17] M. Parsa and J. J. Garcia-Luna-Aceves. A protocol for scalable 1322 loop-free multicast routing. IEEE Journal of Selected Areas in Communications, 1323 15(13):316- 331, April 1997. 1325 [18] H. Takahashi and A. Matsuyama. An approximate solution for the 1326 Steiner problem in graphs. Math. Japonica, 24(6):573-577, 1980. 1328 [19] D. Thaler, D. Estrin, and D. Meyer. Grand Unified Multicast (GUM): 1329 Protocol specification. Internet-Draft: draft-ietf-idmr-gum-00.txt, 1997. 1331 [20] D.G. Thaler and C.V. Ravishankar. Distributed center-location 1332 algorithms. IEEE Journal of Selected Areas in Communications, 15(13):291-303, 1333 April 1997. 1335 [21] B. M. Waxman. Routing of multipoint connections. IEEE Journal of 1336 Selected Areas in Communications, pages 1617-1622, 1988. 1338 [22] B. M. Waxman. Performance evaluation of multipoint routing 1339 algorithms. Proc. IEEE INFOCOM, pages 980-986, 1993. 1341 [23] L. Wei and D. Estrin. The trade-offs of multicast trees and 1342 algorithms. International Conference on Computer Communications and 1343 Networks, 1994. 1345 [24] P. Winter. Steiner problem in networks: a survey. Networks, 1346 17:129-167, 1987. [25] D. Zappala, D. Estrin, and S. Shenker. Alternate 1347 path routing and pinning for interdomain multicast routing. Technical 1348 Report USC CS TR 97-655, U. of South California, 1997. 1350 Draft The QoSMIC Multicast Protocol April 1998 1352 [26] L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala. RSVP: 1353 A new resource reservation protocol. IEEE Network, September 1993. 1355 [27] M. Faloutsos and A. Banerjea and R. Pankaj, 1356 QoSMIC: a QoS Multicast Internet protoCol, ACM SIGCOMM Sep 2-4, 1357 Vancouver BC, 1998. 1359 APPENDIX 1361 A Efficiency Parameters of Multicast Protocols 1363 The efficiency of a 1364 multicast protocol can be defined by set of functional properties. 1366 1. The efficiency of the multicast tree can be measured by the packet 1368 replication which reflects the number of packets that a single piece of 1369 information causes. In more detail, this can be defined as the number of 1370 packets exchanged between neighbor routers, Px, over the number of 1371 packets with distinct content, Pd, over the number of receivers, M : 1372 Px=(Pd finition, we can characterize trees independently of the amount 1373 of data transmitted (Pd) or the group size (M ). 1375 2. The end-to-end delay is defined as the time it takes a packet to 1376 travel from the source to a destination router. 1378 The maximum and average end-to-end delay over all source and 1379 destinations pairs could be used to characterize the end-to-end 1380 performance of the tree. 1382 3. The traffic concentration can be defined as the maximum link load 1383 over the average link load (for the traffic of a given multicast group 1384 or of all groups). 1386 4. The control overhead represents the number of control packets that 1387 are required to support multicast connections. 1389 5. The routing table is the table maintained by each router to support 1390 multicasting. 1392 6. The set-up time is the time it takes a user to join a group: the time 1393 from the join request until the arrival of the first data packet. 1395 CONTACT INFORMATION 1397 Anindo Banerjea 1398 Dept. of Electrical and ComputerEngineering 1399 University of Toronto 1400 10 King's College Road Toronto, 1401 Ontario M5S 3G4 Canada 1402 banerjea@comm.toronto.edu 1404 Draft The QoSMIC Multicast Protocol April 1998 1406 Michalis Faloutsos 1407 Dept. of Computer Science 1408 U. of Toronto Toronto 1409 ON M5S 3G4 Canada 1410 mfalou@cs.toronto.edu 1412 Rajesh Pankaj 1413 Qualcomm Inc 1414 6455 Lusk Blvd San Diego CA 92121 USA 1415 pankaj@qualcomm.com