idnits 2.17.1 draft-ietf-rmt-bb-tree-config-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing document type: Expected "INTERNET-DRAFT" in the upper left hand corner of the first 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. ** The document is more than 15 pages and seems to lack a Table of Contents. == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Introduction section. (A line matching the expected section header was found, but with an unexpected indentation: ' 2. Overview' ) ** 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.) ** There are 740 instances of too long lines in the document, the longest one being 16 characters in excess of 72. ** The abstract seems to contain references ([YGS95], [HPW00], [ECTP02], [WCMKT02], [LPG98], [K01], [WLKHFL01], [KV02], [DEE89], [HOD98], [WCPKT00], [WCPKT01], [HWKFV00], [SV02], [CST00], [HC00], [PTM93]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 427 has weird spacing: '...of this docum...' == Line 1036 has weird spacing: '...ate the start...' == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: - SolicitPeriod: Each receiver MUST not send more than one QUERY message per SolicitPeriod. When SN's responds to QUERY messages, it also suppresses its ADVERTISE message if one has been sent less than SolicitPeriod ago. This parameter is used to control the amount of control traffic during tree construction if ERS is used. -- 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. 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 section? 'WLKHFL01' on line 1282 looks like a reference -- Missing reference section? 'HWKFV00' on line 1260 looks like a reference -- Missing reference section? 'WCPKT00' on line 97 looks like a reference -- Missing reference section? 'WCPKT01' on line 110 looks like a reference -- Missing reference section? 'LPG98' on line 1270 looks like a reference -- Missing reference section? 'DEE89' on line 1241 looks like a reference -- Missing reference section? 'HC00' on line 1249 looks like a reference -- Missing reference section? 'CST00' on line 279 looks like a reference -- Missing reference section? 'YGS95' on line 1286 looks like a reference -- Missing reference section? 'HPW00' on line 1256 looks like a reference -- Missing reference section? 'WCMKT02' on line 1278 looks like a reference -- Missing reference section? 'HOD98' on line 1252 looks like a reference -- Missing reference section? 'ECTP02' on line 1244 looks like a reference -- Missing reference section? 'K01' on line 1264 looks like a reference -- Missing reference section? 'KV02' on line 1267 looks like a reference -- Missing reference section? 'PTM93' on line 1275 looks like a reference -- Missing reference section? 'SV02' on line 1292 looks like a reference Summary: 10 errors (**), 0 flaws (~~), 5 warnings (==), 19 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 RMT Working Group Brian Whetten/Consultant 2 Internet Engineering Task Force Dah Ming Chiu/Sun Microsystems 3 Internet Draft Miriam Kadansky/Sun Microsystems 4 draft-ietf-rmt-bb-tree-config-03.txt Seok Joo Koh/ETRI/KOREA 5 18 November, 2002 Gursel Taskale/Tibco 6 Expires 18 May, 2003 Brian Neil Levine/Umass 8 Reliable Multicast Transport Building Block: Tree Auto-Configuration 10 12 Status of this Memo 14 This document is an Internet-Draft and is in full conformance with 15 all provisions of Section 10 of RFC2026. 17 Internet-Drafts are valid for a maximum of six months and may be 18 updated, replaced, or obsoleted by other documents at any time. It 19 is inappropriate to use Internet-Drafts as reference material or to 20 cite them other than as a "work in progress". 22 The list of current Internet-Drafts can be accessed at 23 http://www.ietf.org/ietf/1id-abstracts.txt 25 The list of Internet-Draft Shadow Directories can be accessed at 26 http://www.ietf.org/shadow.html. 28 Abstract 30 The Reliable Multicast Transport Working Group has been chartered 31 to standardize multicast transport services. This working group 32 expects to initially standardize three protocol instantiations. 33 This draft is concerned with the requirements of the tree-based 34 ACK protocol. In particular, it is concerned with defining the 35 building block for auto-configuration of the logical ACK-tree. 36 According to the charter, a building block is "a coarse-grained 37 modular component that is common to multiple protocols along with 38 abstract APIs that define a building block's access methods and 39 their arguments." For more information, see the Reliable 40 Multicast Transport Building Blocks and Reliable Multicast Design 41 Space documents [WLKHFL01][HWKFV00]. 43 Table of Contents 45 1. Introduction 46 1.1 Terminology 47 1.2 Assumptions 49 INTERNET DRAFT draft-ietf-rmt-bb-tree-config-03.txt 1 50 1.3 Requirements 51 1.4 Applicability Statement 52 2. Overview 53 3. Session Announcement 54 4. Service Node Discovery and Selection 55 4.1 Service Node Discovery Algorithms 56 4.1.1 Static 57 4.1.2 ERS 58 4.1.3 Mesh 59 4.2 Distance Metrics 60 4.2.1 TTL Hop-Count 61 4.2.2 Number of Levels 62 4.2.3 Delay 63 4.2.4 Address 64 4.2.5 Static 65 4.2.6 GRA 66 4.3 Service Node Selection 67 5. Tree Formation 68 6. Tree Maintenance 69 6.1 Monitoring Parents and Children 70 6.2 Optimizing the Tree 71 7. Messages 72 8. External Interfaces 73 8.1 Interfaces to the BB 74 8.1.1 start 75 8.1.2 end 76 8.1.3 incomingMessage 77 8.1.4 getStatistics 78 8.1.5 getSNs 79 8.1.6 setSN 80 8.1.7 acceptChild 81 8.1.8 removeChild 82 8.1.9 treeLevelUpdate 83 8.1.10 lostSN 84 8.1.11 setOptimization 85 8.1.12 recordSNs 86 8.2 Interfaces from the BB 87 8.2.1 outgoingMessage 88 8.2.2 SNlist 89 9. References 90 Authors' Addresses 92 1. Introduction 94 The Reliable Multicast Transport (RMT) working group has been 95 chartered to standardize IP multicast transport services. This 96 draft is concerned with the requirements of the tree-based ACK 97 protocol [WCPKT00]. In particular, this draft defines a building 98 block for auto-configuration of a tree comprised of a single 99 Sender, Service Nodes, and Receivers into a tree (called a Session 101 INTERNET DRAFT draft-ietf-rmt-bb-track-01.txt 2 102 Tree in this document). The design goals of this draft are 103 motivated by the needs of TRACK-based protocols, however the trees 104 it constructs are useful for other services. 106 This building block can be interfaced to any other BB or PI 107 wishing to use a tree structure. To actually use this BB's 108 features, the PI needs to includes the messages described in this 109 BB in its packets. An example of how to use this BB can be found 110 in the TRACK PI[WCPKT01]. 112 The process of session tree construction is difficult for IP 113 multicast. The best session trees match the underlying multicast 114 routing tree topology [LPG98], however the multicast service model 115 [DEE89] does not provide explicit support for discovering routing 116 tree topology. 118 Furthermore, deployed multicast architectures can vary; for 119 example, hosts may be restricted to multicast reception and not 120 transmission with Source-Specific multicast routing [HC00]; and 121 routers may provide special extended routing services with Generic 122 Router Assist [CST00]. The RMT charter does not restrict the use 123 of any particular network service in constructing the tree. It 124 only suggests preferred scenarios. Accordingly, there are several 125 viable solutions for constructing a tree, depending on network 126 conditions. 128 The optimality of a tree may also depend on other factors, such as 129 the need for load balancing, and the need to minimize the depth 130 when used for collecting feedback information. The goal of this 131 building block is to specify a distributed procedure for 132 automatically constructing a tree that is loop-free and as 133 efficient as possible given the information available. 135 This draft describes a unified solution for tree construction in 136 the presence of different multicast service models and routing 137 protocols. In particular, it specifies a single procedure which 138 may be used with various techniques for service node discovery and 139 distance measurements, several of which are specified within this 140 document. The difference in these techniques primarily affects the 141 optimality of the tree. The unified algorithm ensures that 142 different implementations can interoperate and construct a loop- 143 free tree. 145 In order to accommodate various multicast deployments, this 146 document divides the tree building process into the following 147 major components: 149 1. Several techniques for discovering neighboring service nodes. 150 In particular: Static, Expanding Ring Search, and Mesh. 151 Discovering neighboring service nodes is a necessary 152 condition for getting connected, so each node in the session 154 INTERNET DRAFT draft-ietf-rmt-bb-track-01.txt 3 155 must implement at least one of the above techniques. 157 2. Several algorithms for selecting neighboring service nodes. 158 In particular, the measurement and use of neighbor distance 159 and sender distance are described. These service node 160 selection algorithms help produce a good tree. 162 3. A single distributed procedure for construction and 163 maintenance of loop-free Session Trees. 165 1.1 Terminology 167 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 168 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in 169 this document are to be interpreted as described in RFC 2119. 171 Session 173 A session is used to distribute data over a multicast address. A 174 Session Tree is used to provide reliability and feedback services 175 for a session. 177 Sender 179 The single sender of data on a multicast session. The Sender is the 180 root of the Session Tree. 182 Receiver 184 A receiver receives data from the sender via the multicast session. 186 Session Identifier 188 A fixed-size number, chosen either by the application that creates 189 the session or by the transport. Senders and Receivers use the 190 Session Identifier to distinguish sessions. The size of this 191 number is specified by the Protocol Instantiation (PI). 193 Service Node (SN) 195 A node within the tree which receives and retransmits data, and 196 aggregates and forwards control information toward the Sender. The 197 Sender operates as the root Service Node in any session tree. 198 Service Nodes MAY be dedicated servers within a network designed to 199 participate in multiple Sessions and support multiple trees, or 200 they MAY be Receivers participating in an individual session. SNs 201 MAY limit the number of Children they choose to service, and MAY 202 also make other restrictions on the characteristics of each Child 203 (distance, location, etc.). An SN that has accepted Children for a 204 session is called a Parent. 205 In other documents, Service Node is sometimes referred to as Repair 207 INTERNET DRAFT draft-ietf-rmt-bb-track-01.txt 4 208 Head (RH). 210 Session Tree (ST) 212 The Session Tree is a tree spanning all receivers of a multicast 213 session. It is rooted at the Sender, consisting of zero of more 214 Service Nodes as interior nodes, and zero or more receivers as leaf 215 nodes. An ST is constructed for the forwarding of control 216 information back to the Sender as well as for the resending of 217 missed data to the Receivers. The ST for a particular session may 218 change over the course of the session. 220 Parent 222 A Parent is an SN or Receiver's predecessor in the ST on the path 223 toward the Sender. Every SN or Receiver on the tree except the 224 Sender itself has a parent. Each Parent communicates with its 225 children using either an assigned multicast address or through 226 unicast. If a multicast address is used, this may be the same 227 address used by the session, or one specifically assigned to the 228 Parent. 230 Children 232 The set of Receivers and SNs for which an SN or the Sender is 233 providing repair and feedback services. 235 Tree Level 237 A number indicating the number of "generations" a node is from the 238 root. The sender is at TL=0. Those that use the sender as their 239 parent are at TL=1 and so on. When a receiver is not connected to 240 the tree yet, it has a tree level value greater or equal to 128. 241 The reason for reserving part of the space (of tree levels) for 242 indicating "off-tree" is so that special measures can be used to 243 prevent forming loops. The largest value is 255, so the range of 244 off-tree levels are in the range 128 - 255. Initially, all 245 receivers have a TL value of 128. Once a Node joins the tree, its 246 Tree Level is updated to be one more than its Parent's level. 248 Distance Metric 250 There are several techniques to quantify distances between nodes 251 (Receivers, SNs, and the Sender) in a session. Each type of 252 quantification is called a distance metric. Several Distance 253 Metrics are described in this draft. 255 Sender Distance 257 The distance from a node to the Sender. 259 INTERNET DRAFT draft-ietf-rmt-bb-track-01.txt 5 260 Neighbor Distance 262 The distance from a node to a Neighbor. 264 Neighbor 266 A node's (Receiver or SN) Neighbors are SNs that are close to the 267 node, according to the Distance Metric(s) used by the node. 269 1.2 Assumptions 271 This document describes how to build trees under the following 272 conditions: 274 a. The multicast group has only a single sender. 275 b. A single SN can serve multiple sessions. 276 c. Sessions can take advantage of a pre-deployed infrastructure 277 of SNs (ones that are not necessarily aware of a session 278 before the receivers), or recruit Receivers to be SNs. 279 d. Generic Router Assist[CST00] and Expanding Ring Search[YGS95] 280 are not required of the network infrastructure, but if 281 available they should be able to be utilized. 283 1.3 Requirements 285 The following are specifically required: 287 a. While tree-building may take advantage of information from the 288 routing layer, the mechanisms described are independent of the 289 routing protocol(s) used by the underlying multicast tree. 290 b. All trees constructed must be loop-free 291 c. These mechanisms must support late joiners and tree 292 optimization 294 1.4 Applicability Statement 296 The authors recognize that automatic tree construction is a very 297 difficult problem. Nonetheless, complete reliance on manual 298 configuration is very user unfriendly and error prone as well. 300 This building block describes a procedure for constructing loop- 301 free trees when there is minimal manual configured information 302 available. 304 This is analogous to providing a system with default configurations 305 that allow the system to work correctly, but not necessarily 306 optimally. 308 There are many possible criteria for tree optimality. This BB does 310 INTERNET DRAFT draft-ietf-rmt-bb-track-01.txt 6 311 not attempt to define a single optimality criterion, nor does it 312 try to produce an optimal tree. It is, however, the goal of the 313 BB to construct better trees as more configuration and measurement 314 data are introduced to the procedure. 316 This BB describes only a subset of the possible parameters for 317 constructing optimal trees, in particular sender distance and 318 neighbor distance. There are many techniques for measuring these 319 distances. Some of the techniques may not be applicable globally. 321 Expanding ring search (ERS) is an effective technique in a local 322 subnet or intranet (especially when the IP multicast routing 323 protocol is dense-mode based). On the other hand, it is not 324 practical in a multi-domain network; it is not effective when the 325 routing protocol is sparse-mode based; and it can add significant 326 control traffic overhead. 328 Generic Router Assist (GRA) can provide measurement hooks to 329 determine SNs that are located along the path for multicast data 330 distribution. However, such facilities may not be available in all 331 networks. 333 The tree construction procedure does allow manual configuration and 334 various distance measurement techniques to be selectively and 335 independently applied for different subgroups of receivers and SNs, 336 to achieve incremental improvement to the quality of the tree. 338 There are many other criteria for tree-building than what is 339 described in this document, for instance, methods based on load 340 balancing and minimizing feedback latency. 342 2. Overview 344 The tree building process described within this document builds 345 logical trees which consist of: 347 1. A root node (the Sender) 348 2. Intermediate nodes (Service Nodes or SNs) which may be 349 either Receivers or nodes specifically allocated to the 350 task of repair and aggregation 351 3. Leaf nodes which are Receivers only 353 Session trees are spanning trees rooted at the Sender. Session 354 trees can be used for the forwarding of control information (i.e. 355 ACKs) towards the root, or for forwarding of data (i.e. repairs) 356 towards the leaf nodes. 358 Session trees are constructed per Sender; each node wishing to join 359 the tree discovers its neighboring SNs and then selects its best 360 parent based on locally available information, such as the relative 362 INTERNET DRAFT draft-ietf-rmt-bb-track-01.txt 7 363 sender distances and neighbor distances. This document specifies 364 several techniques for measuring distances. 366 It is important to note that SNs may be actual Receivers (e.g. 367 Receivers willing and able to also function as SNs) or pre-deployed 368 "specialized" servers that are signaled to join the tree by 369 Receivers. We use the term Service Node to refer to either a 370 Receiver or "server" which is participating as part of the logical 371 tree formation. 373 Tree construction, regardless of SN discovery and selection 374 algorithm, proceeds generically as follows. 376 1. Session Announcement 378 Receivers of a session use standard out-of-band mechanisms 379 for discovery of a session's existence (e.g. Session 380 Advertisement ([HPW00], URL, etc). In this way, a Receiver 381 discovers the multicast group address, the Sender's address, 382 and other information necessary for logical tree construction. 383 Sessions may be announced in two parts, the first part 384 containing generic information about the session, such as the 385 multicast address, and the second part, announced on the 386 multicast address, containing additional information. 388 2. Measurements to the Sender (optional) 390 All SNs and Receivers that know about the session optionally 391 determine their distance to the Sender. 393 3. Neighbor Discovery 395 Meanwhile, each Receiver discovers nearby SNs (candidate 396 parents) for the Session using the neighbor discovery 397 algorithm(s). 399 4. Service Node Selection 401 Once a Receiver (or SN needing to join the tree) discovers a 402 nearby SN, it obtains the SN's distance to the Sender as well 403 as the SN's distance to the Receiver, tree level, and other 404 suitability values, if available. After discovery is complete, 405 the best SN is selected. 407 5. Binding to Service Node 409 The Receiver or SN then binds to the chosen SN. If a bind is 410 unsuccessful, the Receiver or SN retries with another nearby 411 SN, or starts the discovery process all over again. Once an 412 SN receives a bind from a child, that SN must then also join 414 INTERNET DRAFT draft-ietf-rmt-bb-track-01.txt 8 415 the tree if it has not already, discovering an SN of its own, 416 possibly using a different method than leaf Receivers. 418 6. Optimization (optional) and Fault Recovery 420 During a session, a Receiver or SN may change to a different 421 SN for a number of reasons described below, including fault 422 tolerance. The Session Tree is maintained and optimized over 423 time. 425 This building block provides mechanisms for maintaining and 426 optimizing the tree, as well as tearing it down when the Sender is 427 done with it. In the rest of this document, the term 'Node' 428 denotes a Receiver or SN. 430 +--------------------+ 431 | 1. Session | 432 | Advertisement | 433 +--------------------+ 434 | 435 | Node receives tree-building parameters 436 V 437 +--------------------+ 438 | 2. Measurements |<-------------------------| 439 | to the Sender | | 440 | (optional) | | 441 +--------------------+ | 442 | | 443 | | 444 V | 445 +--------------------+ | 446 | 3. Neighbor | | 447 | Discovery | | 448 +--------------------+ | 449 | | 450 | | 451 V | 452 +--------------------+ | 453 | 4. Service Node | | 454 | Selection | | 455 +--------------------+ | 456 | | 457 | Node picks best Neighbor | 458 V | 459 +--------------------+ | 460 | 5. Binding to |--------------------------- 461 | Service Node | 6. Optimization (optional) 462 | | and Fault Recovery 463 +--------------------+ 465 INTERNET DRAFT draft-ietf-rmt-bb-track-01.txt 9 466 3. Session Announcement 468 The first step in the tree-building process is for a node to be 469 informed of the session's existence. This can be done using some 470 out-of-band method, such as Session Advertisement [HPW00], URL, e- 471 mail, etc. 473 SNs do not necessarily receive these advertisements. If an SN is 474 not a Receiver, it obtains the advertisement information once it 475 is contacted by a Receiver. 477 The advertisement includes the multicast address being used, the 478 Sender's address, the Session Identifier, any specific port numbers 479 to be used, and any global information useful for tree construction. 480 The advertisement may also contain information about one or more 481 Service Node Discovery options (such as Static, ERS, and Mesh) 482 that can possibly be used by Receivers in the session. 484 4. Service Node Discovery and Selection 486 Discovery is the process by which a node determines a suitable 487 Service Node. During the discovery process, suitable neighbors are 488 found, Sender distances are optionally exchanged, and the best SN 489 is selected. 491 4.1 Service Node Discovery Algorithms 493 This draft describes three algorithms for discovering SNs: Static, 494 Expanding Ring Search (ERS), and Mesh. 496 Multiple algorithms may be used within a single session. For 497 example, SNs may use the Mesh algorithm, while the receivers use 498 static configuration to discover the SNs; alternatively, some 499 Receivers may use static configuration while other Receivers depend 500 on ERS (in an intranet where ERS is available). Each Receiver may 501 pre-configure which algorithm to use before it starts. 503 The transport protocols request the following information from this 504 BB using the getSNs interface. 506 Service Nodes: 508 1. ParentAddress: the address and port of the parent node to 509 which the node should connect 510 2. UDPListenPort: the number of the port on which the node will 511 listen for its children's control messages 512 3. RepairAddr: the multicast address, UDP port, and TTL on 513 which this node sends control messages to its 514 children. 516 INTERNET DRAFT draft-ietf-rmt-bb-track-01.txt 10 517 Receivers: 519 1. ParentAddress. 521 Senders: 523 1. UDPListenPort 525 2. RepairAddr 527 After the above information is obtained from auto-tree-config, the 528 transport protocol may perform the necessary Bind operations for 529 participating in the Session Tree. 531 4.1.1 Static 533 Static algotirhm relies on a functional entity, named Tree 534 Configurator (TC), which is pre-configured by Sender for tree 535 configuration in a static manner. TC may be simply implemented by 536 a program and thus installed at Sender or any other host. It is 537 not necessarily specialized infrastructure. 539 Static scheme is a typical top-down tree configuration approach. TC 540 is used to govern the tree building based on its own (session- 541 specific) tree configuration and SN(s) selection rules for the new 542 joiners. 544 If a TC is used for tree building, its address and port MUST be 545 included with the session advertisement. Receivers and SNs will 546 realize there is a TC for the session via Session Announcement, 547 and they can contact with the TC to get a list of candidate SNs by 548 sending a unicast Query message. 550 In response to a Query message, the TC replies with a Advertise 551 message that contains a list of candidate SNs available to the new 552 joiner. The rule of determining such candidate SNs may depend on 553 the pre-configured mechanism taken by TC. For example, TC may 554 determine the candidate SN list for a Node among the possible SNs 555 (it contains at that time) by considering which SNs are in the 556 same network domain with the Node (i.e., via comparing their 557 network prefix), or by considering the load balancing for the tree 558 topology it has configured until then. For this purpose, TC 559 maintains a pool of active SNs for the session. The list of 560 candidate SNs carried by Advertise message is ordered in 561 decreasing levels of preference, in which a lower number 562 represents a higher preference. 564 When a Receiver Node receives the responding Advertise message from 565 TC, the Node MAY proceed to try to bind to a candidate SN 566 following the given order by sending a BindRequestmessage, and 568 INTERNET DRAFT draft-ietf-rmt-bb-track-01.txt 11 569 then waits for the responding message such as BindConfirm or 570 BindReject from TC. These binding steps will be done according to 571 the TRACK mechanism, as described in the TRACK PI [WCMKT02] 573 In the Static algorithm, SN discovery with a TC proceeds as 574 follows: 576 1. The node joins the multicast session and learns of the 577 location of TC (from the session announcement). 579 2. The node optionally discovers its distance from the Sender. 580 Any metric described in Section 4.2 may be used. 582 3. The node sends a Query message to the TC for a parent. The 583 request includes (optionally) the node's distance to the 584 sender and whether the node functions as an SN or not. 586 4. The TC chooses one or more candidate parents (SNs) for the 587 node from the active SNs by its own tree configuration rule. 588 The selection of candidate parents may be done by comparing 589 the network prefix or by referring to any other information 590 such as the number of currently attached children, etc. 592 5. The TC MUST responds to the Query message with an Advertise 593 message, which include the candidate parent list. In the 594 list, each entry contains the corresponding IP address and 595 port of an SN. 597 All the entries in the list SHOULD be arranged in the 598 decreasing order of preference levels. 600 In the rejection case, the Advertise message does not 601 include any candidate parent. In this case, the Node may 602 resort to the other mechanism such as ERS and Mesh. 604 In the success case, the node will be enrolled as an active 605 SN by the TC, if it functions as an SN in the session. Each 606 active SN (functioning as a parent for the Session Tree) 607 SHOULD send the TC the periodic Query messages with a flag 608 indicating that it is active over a specific time interval. 609 Based on the Query messages, the TC updates a pool of active 610 SNs in the session. In response to the Query message, the TC 611 sends a Advertise with a flag simply indicating that the 612 Query message is received. 614 6. After receiving a successful Advertise message from the TC, 615 the node will try to connect to its parent by sending 616 BindRequest messages based on the candidate parent list, as 617 described in Section 5. 619 INTERNET DRAFT draft-ietf-rmt-bb-track-01.txt 12 620 4.1.2 ERS 622 ERS is a typical bottom-up tree configuration approach, which can 623 be used only in the network environments where IP multicast 624 transmissions are allowed by Receivers and SNs. 626 In ERS algorithm, SN discovery with a TC proceeds as follows: 628 1. The Nodes first look for Neighbors using a multicast Query 629 message. The initial TTL value in the Query message, 630 TTLNeighborInit, is specified in the session announcement 631 and may be as large as the session TTL (TTLSession). 633 An SN that is able to handle additional Children MUST 634 respond to a Query message by multicasting an Advertise 635 message. 637 If the SN is not yet a Parent, the TTL used in this response 638 is the same TTL used in the Query message. If the SN is a 639 Parent, the TTL used is the greater of the Query TTL and the 640 Parent's current Advertise TTL. 642 2. The Node listens for Advertise messages after sending the 643 Query message. If one or more Advertise messages are 644 received during a SolicitPeriod, the best SN among them is 645 selected as described in section 4.3. 647 3. If no Advertise messages are received, the Node sends 648 another multicast Query message with a TTL that is 649 incremented by TTLIncrement. The process of sending the 650 multicast Query message with an increasing TTL value 651 continues until a response is received. 653 The TTL value is limited by a value, TTLMax, also specified 654 in the session announcement. TTLMax defaults to the value 655 of TTLSession. 657 If the TTL value required to reach the soliciting Node is 658 greater than the TTL used to reach the SN, an Advertise 659 message may not reach the Node. However, if future Query 660 messages have increased TTL values, the TTL may eventually 661 be large enough for the Advertise message to reach the Node. 662 However, it is possible that the Node will not locate any 663 SNs using Expanding Ring Search. It is advisable that a 664 backup method, such as static, be available. 666 4. SNs MUST suppress sending Advertise messages in response to 667 Query messages if one was sent with at least the Query's TTL 668 within the last SolicitPeriod. 670 INTERNET DRAFT draft-ietf-rmt-bb-track-01.txt 13 671 After multicasting a Query message, a node MUST wait for an 672 interval, BetweenQuery, before sending another Query message. 673 Nodes SHOULD suppress sending Query messages for 674 BetweenQuery seconds when they first start in order to 675 collect information from Advertise messages already 676 solicited by other nodes. 678 5. Getting a successful Advertise message via ERS, the Node 679 will try to connect to the parent by sending BindRequest 680 messages, which are described in Section 5. 682 The following variables are used in the Expanding Ring Search 683 algorithm. 685 - TTLNeighborInit: This is the initial TTL value to be used by the 686 ERS if no other TTL value is specified by the algorithm. 688 - TTLIncrement: This is the periodic increment for the TTL used in 689 ERS. 691 - TTLMax: This is a configured maximum TTL value to be used by 692 either Query or Advertise messages. 694 - TTLSession: This is the session TTL value for the multicast 695 session. 697 - SolicitPeriod: Each receiver MUST not send more than one QUERY 698 message per SolicitPeriod. When SN's responds to QUERY messages, 699 it also suppresses its ADVERTISE message if one has been sent 700 less than SolicitPeriod ago. This parameter is used to control 701 the amount of control traffic during tree construction if ERS is 702 used. 704 - BetweenQuery: This is the time interval a node must wait before 705 sending successive Query messages. 707 - MaxBindAttempts: This variable is an integer used to control how 708 many times a receiver tries to bind to a SN before giving up and 709 try another one. 711 - BindPeriod: In order to prevent loops, sometimes a SN must reject 712 a BindRequest (for example, when the SN is not on the tree yet 713 and has a BindRequest outstanding itself) from a receiver. In 714 this case, if the receiver needs to retry binding to the same SN 715 again (perhaps because the receiver does not discover any 716 alternative SN's), then it must wait for BindPeriod seconds. 718 4.1.3 Mesh 720 The mesh approach relies on a set of SN's already deployed as 722 INTERNET DRAFT draft-ietf-rmt-bb-track-01.txt 14 723 infrastructure servers. These SN's are on-line, but are not 724 necessarily aware of any particular session unless informed by the 725 following mechanisms. 727 SN's in the mesh are configured to know who their neighbor SN's are, 728 and exchange reachability information with their neighbors in a way 729 analogous to routers in a network. The actually protocol used by 730 SN's to exchange such reachability information is outside the scope 731 of this BB. (In principle, a routing protocol such as shortest- 732 path-first, or a link-state-protocol can be adapted for this 733 purpose). Instead, this BB specifies the following properties that 734 the mesh of SN's MUST satisfy: 736 a) Each SN knows a subset of SN's in the mesh as its immediate 737 neighbors. 739 b) Each SN has a "forwarding table", such that given any other 740 (destination) SN in the mesh, the forwarding table gives a 741 "next-hop" SN that can be used to reach the destination SN, 742 plus the distance to the destination SN from the local SN. 744 c) A given SN in the mesh can "broadcast" information to all 745 other SN's in the mesh (in the sense of having a means of 746 sending the same information to all other SN's, but not 747 necessarily simultaneously). 749 d) All potential sender and receivers of a multicast session 750 can discover a "neighboring" SN in the mesh, using the 751 neighbor discovery mechanisms described in Section 4.1. 753 The reason for running a routing-like algorithm to maintain the 754 forwarding tables in each SN is to provide fault tolerance when 755 some SN's in the mesh fail. When that happens, the remaining SN's 756 exchange information with each other to update the forwarding 757 tables. In steady state, the mesh of SN's must still satisfy the 758 above 4 properties. 760 In the simplest form, each SN in the mesh has a forwarding table 761 that contains all other SN's in the mesh. This is called a fully- 762 connected mesh. 764 As mentioned earlier, the Mesh scheme assumes that there is a pre- 765 deployed infrastructures of SN servers. That is, the SN-SN bindings 766 and Sender-SN (Sender's SNs) will be performed internally by the 767 provider's own policy. The only thing done by Sender is to inform 768 its SN's that a session starts. The relationships between Sender 769 and its SN's (i.e., Sender-SN bindings) MUST also be pre- 770 configured. 772 For example, the internal bindings between Sender and SN's MAY be 773 done as follows: 775 INTERNET DRAFT draft-ietf-rmt-bb-track-01.txt 15 776 1. The sender locates a neighbor SN in the mesh by a pre- 777 configured mechanism. This SN is referred to as the sender's 778 SN. 780 2. The sender sends the multicast session id, address and port 781 (all these can be set as a abbreviated session announcement 782 message) to the sender's SN. 784 3. The sender's SN in turn "broadcasts" the session information 785 to all SN's in the mesh; since SN's can support multiple 786 sessions simultaneously, they keep the information about 787 each session in an entry in a session table. 789 4. After the Sender-SN bindings, Sender will multicasts its 790 session announcement to the multicast receivers. Then, the 791 sender's SN binds to the sender by sending a BindRequest 792 message. 794 During the internal processings of Sender-SN binding described 795 until now, any Query and Advertise messages are not used. 797 When a session starts, the bindings between SN and Receivers will 798 be done. The tree binding of SN-receiver is done with the Tree 799 Configurator (TC), which was used in the Static algorithm. The 800 main difference between Static algorithm with TC and Mesh 801 algorithm with TC is that the active SNs are considered as 802 candidate SNs in the Static scheme, while the pre-deployed 803 SNs are considered as candidates in the Mesh scheme. That is, in 804 the Mesh scheme, the TC is required to already get the information 805 on the locations of the pre-deployed SNs. 807 Then the tree buildings between receivers and SNs are done as 808 follows: 810 1. When a session starts, a receiver sends a Query message to 811 the TC. The receiver may optionally discovers its distance 812 from the Sender. Any metric described in Section 4.2 may be 813 used. 815 2. The TC chooses one or more candidate parents SNs for the 816 receiver from the pre-deployed SNs by its own tree 817 configuration rule, as described in Section 4.1.1. 819 3. TC MUST respond to the Query message with an Advertise 820 message, which include the candidate parent list. In the list, 821 each entry contains the corresponding IP address and port of 822 the parent. 824 4. Receiving a successful Advertise message from the TC, the 825 Node will try to connect to its parent by sending BindRequest 827 INTERNET DRAFT draft-ietf-rmt-bb-track-01.txt 16 828 messages based on the candidate parent list, as described in 829 Section 5. 831 Once a receiver is connected to a parent SN, the SN-SN bindings 832 will also be done internally by the pre-configured provider's 833 policy. For example, each SN in the mesh tries to bind to its 834 "next-hop" SN. If the "next-hop" SN is not reachable for some 835 reason, an SN may also try to bind to any neighbor SN as a back-up 836 alternative. These procedures will be devised to ensure that the 837 loop freedom is guaranteed in section 5. 839 4.2. Distance Measurement 841 Different techniques can be used to determine distances between 842 nodes in a session. The distances of interest are: 844 Sender distance - the distance from a SN to sender 846 Neighbor distance - the distance from a receiver to a 847 neighboring SN 849 These distances can be used in selecting a Service Node ifseveral 850 are discovered. 852 These techniques quantify distance differently. Each specific way 853 of quantifying distance is called a metric. Different Metrics are 854 not necessarily comparable. For example, if distance between A 855 and B is X using metric m1, and distance between A and C is Y 856 using metric m2, then X > Y does not necessarily imply B is 857 farther from A than C. 859 Only distances of the same metric should be compared and ranked. 860 Therefore, a receiver SHOULD only rank two SN's based on their 861 respective sender distance if those distances are based on the same 862 metric. 864 On the other hand, it is not necessary for all receivers to use the 865 same metric to select theirneighboring SN to connect to. Suppose 866 receivers use neighbor distance as a selection criterion. One 867 receiver may determine neighbor distances to SN's based on hop 868 count, whereas another receiver may determine neighbor distances 869 to its neighboring SN's based on delay. 871 4.2.1 TTL Hop-Count 873 If this metric is used, a node periodically sends a Beacon message 874 on the Session's multicast address. The Beacon message includes 875 the original time-to-live value set by the node. The distance to 876 the node is then calculated as 878 INTERNET DRAFT draft-ietf-rmt-bb-track-01.txt 17 879 Beacon's original TTL - Beacon's current TTL 881 One node is closer than another if its distance is a lower number. 882 Note that the TTL value may not be available in some implementation 883 environments. 885 4.2.2 Number of Levels 887 One metric a receiver can use for SN selection is the number of 888 levels the SN is from the sender. For example, given two SN's in 889 close proximity to a receiver, if one SN is n levels from the 890 sender and the other is m levels, where m