idnits 2.17.1 draft-ietf-idmr-cbt-spec-09.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-20) 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. ** 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 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 an Authors' Addresses Section. ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 11 instances of too long lines in the document, the longest one being 2 characters in excess of 72. ** There are 41 instances of lines with control characters in the document. ** The abstract seems to contain references ([1,5,, 6], [1]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. == There are 2 instances of lines with multicast IPv4 addresses in the document. If these are generic example addresses, they should be changed to use the 233.252.0.x range defined in RFC 5771 Miscellaneous warnings: ---------------------------------------------------------------------------- -- 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.) -- The document date (May 1997) is 9837 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: 'HOLDTIME' on line 634 -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' ** Obsolete normative reference: RFC 1700 (ref. '4') (Obsoleted by RFC 3232) -- Possible downref: Non-RFC (?) normative reference: ref. '5' ** Downref: Normative reference to an Experimental RFC: RFC 1949 (ref. '6') -- Possible downref: Non-RFC (?) normative reference: ref. '7' -- Possible downref: Non-RFC (?) normative reference: ref. '8' Summary: 15 errors (**), 0 flaws (~~), 2 warnings (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Inter-Domain Multicast Routing (IDMR) A. Ballardie 2 INTERNET-DRAFT Consultant 4 May 1997 6 Core Based Trees (CBT version 2) Multicast Routing 8 -- Protocol Specification -- 10 12 Status of this Memo 14 This document is an Internet Draft. Internet Drafts are working doc- 15 uments of the Internet Engineering Task Force (IETF), its Areas, and 16 its Working Groups. Note that other groups may also distribute work- 17 ing documents as Internet Drafts). 19 Internet Drafts are draft documents valid for a maximum of six 20 months. Internet Drafts may be updated, replaced, or obsoleted by 21 other documents at any time. It is not appropriate to use Internet 22 Drafts as reference material or to cite them other than as a "working 23 draft" or "work in progress." 25 Please check the I-D abstract listing contained in each Internet 26 Draft directory to learn the current status of this or any other 27 Internet Draft. 29 Abstract 31 This document describes the Core Based Tree (CBT version 2)) network 32 layer multicast routing protocol. CBT builds a shared multicast dis- 33 tribution tree per group, and is suited to inter- and intra-domain 34 multicast routing. 36 CBT may use a separate multicast routing table, or it may use that of 37 underlying unicast routing, to establish paths between senders and 38 receivers. The CBT architecture is described in [1]. 40 This document is progressing through the IDMR working group of the 41 IETF. CBT related documents include [1, 5, 6]. For all IDMR-related 42 documents, see http://www.cs.ucl.ac.uk/ietf/idmr. 44 TABLE OF CONTENTS 46 1. Changes Since Previous version............................. 4 48 2. Introduction & Terminology................................. 4 50 3. CBT Functional Overview.................................... 5 52 4. CBT Protocol Specificiation Details........................ 7 54 4.1 CBT HELLO Protocol..................................... 7 56 4.1.1 Sending HELLOs................................... 8 58 4.1.2 Receiving HELLOs................................. 9 60 4.2 JOIN_REQUEST Processing................................ 9 62 4.2.1 Sending JOIN_REQUESTs............................ 9 64 4.2.2 Receiving JOIN_REQUESTs.......................... 10 66 4.3 JOIN_ACK Processing.................................... 10 68 4.3.1 Sending JOIN_ACKs................................ 11 70 4.3.2 Receiving JOIN_ACKs.............................. 11 72 4.4 QUIT_NOTIFICATION Processing........................... 11 74 4.4.1 Sending QUIT_NOTIFICATIONs....................... 11 76 4.4.2 Receiving QUIT_NOTIFICATIONs..................... 12 78 4.5 CBT ECHO_REQUEST Processing............................ 12 80 4.5.1 Sending ECHO_REQUESTs............................ 13 82 4.5.2 Receiving ECHO_REQUESTs.......................... 13 84 4.6 ECHO_REPLY Processing.................................. 13 86 4.6.1 Sending ECHO_REPLYs.............................. 14 88 4.6.2 Receiving ECHO_REPLYs............................ 14 90 4.7 FLUSH_TREE Processing.................................. 14 92 4.7.1 Sending FLUSH_TREE Messages...................... 14 94 4.7.2 Receiving FLUSH_TREE Messages.................... 15 96 5. Timers and Default Values.................................. 15 98 6. CBT Packet Formats and Message Types....................... 16 100 6.1 CBT Common Control Packet Header....................... 16 102 6.2 HELLO Packet Format.................................... 17 104 6.3 JOIN_REQUEST Packet Format............................. 17 106 6.4 JOIN_ACK Packet Format................................. 18 108 6.5 QUIT_NOTIFICATION Packet Format........................ 19 110 6.6 ECHO_REQUEST Packet Format............................. 19 112 6.7 ECHO_REPLY Packet Format............................... 20 114 6.8 FLUSH_TREE Packet Format............................... 21 116 7. Core Router Discovery...................................... 21 118 7.1 "Bootstrap" Mechanism Overview........................ 22 120 7.2 Bootstrap Message Format.............................. 23 122 7.3 Candidate Core Advertisement Message Format........... 23 124 8. Interoperability Issues.................................... 23 126 Acknowledgements.............................................. 24 128 References.................................................... 24 130 Author Information............................................ 26 132 1. Changes from CBT version 1 134 This version of the CBT protocol specification differs significantly 135 from the previous version. Consequently, this version represents ver- 136 sion 2 of the CBT protocol. CBT version 2 is not, and was not, 137 intended to be backwards compatible with version 1; we do not expect 138 this to cause extensive compatibility problems because we do not 139 believe CBT is at all widely deployed at this stage. However, any 140 future versions of CBT can be expected to be backwards compatible 141 with this version. 143 The most significant changes to version 2 compared to version 1 144 include: 146 +o new LAN mechanisms, including the incorporation of an HELLO pro- 147 tocol. 149 +o new simplified packet formats, with the definition of a common 150 CBT control packet header. 152 +o each group shared tree has only one active core router. 154 This specification revision is a complete re-write of the previous 155 revision. 157 2. Introduction & Terminology 159 In CBT, a "core router" (or just "core") is a router which acts as a 160 "meeting point" between a sender and group receivers. The term "ren- 161 dezvous point (RP)" is used equivalently in some contexts [2]. Each 162 core router is configured to know it is a core router. 164 A router that is part of a CBT distribution tree is known as an "on- 165 tree" router. An on-tree router maintains active state for the group. 167 We refer to a broadcast interface as any interface that supports mul- 168 ticast transmission. 170 An "upstream" interface (or router) is one which is on the path 171 towards the group's core router with respect to this router. A "down- 172 stream" interface (or router) is one which is on the path away from 173 the group's core router with respect to this router. 175 Other terminology is introduced in its context throughout the text. 177 3. CBT Functional Overview 179 The CBT protocol is designed to build and maintain a shared multicast 180 distribution tree that spans only those networks and links leading to 181 interested receivers. 183 To achieve this, a host first expresses its interest in joining a 184 group by multicasting an IGMP host membership report [3] across its 185 attached link. On receiving this report, a local CBT aware router 186 invokes the tree joining process (unless it has already) by generat- 187 ing a JOIN_REQUEST message, which is sent to the next hop on the path 188 towards the group's core router (how the local router discovers which 189 core to join is discussed in section 7). This join message must be 190 explicitly acknowledged (JOIN_ACK) either by the core router itself, 191 or by another router that is on the path between the sending router 192 and the core, which itself has already successfully joined the tree. 194 The join message sets up transient join state in the routers it tra- 195 verses, and this state consists of . "Incoming interface" and "outgoing interface" may be 197 "previous hop" and "next hop", respectively, if the corresponding 198 links do not support multicast transmission. "Previous hop" is taken 199 from the incoming control packet's IP source address, and "next hop" 200 is gleaned from the routing table - the next hop to the specified 201 core address. This transient state eventually times out unless it is 202 "confirmed" with a join acknowledgement (JOIN_ACK) from upstream. The 203 JOIN_ACK traverses the reverse path of the corresponding join mes- 204 sage, which is possible due to the presence of the transient join 205 state. Once the acknowledgement reaches the router that originated 206 the join message, the new receiver can receive traffic sent to the 207 group. 209 Loops cannot be created in a CBT tree because a) there is only one 210 active core per group, and b) tree building/maintenance scenarios 211 which may lead to the creation of tree loops are avoided. For exam- 212 ple, if a router's upstream neighbour becomes unreachable, the router 213 immediately "flushes" all of its downstream branches, allowing them 214 to individually rejoin if necessary. Transient unicast loops do not 215 pose a threat because a new join message that loops back on itself 216 will never get acknowledged, and thus eventually times out. 218 The state created in routers by the sending or receiving of a 219 JOIN_ACK is bi-directional - data can flow either way along a tree 220 "branch", and the state is group specific - it consists of the group 221 address and a list of local interfaces over which join messages for 222 the group have previously been acknowledged. There is no concept of 223 "incoming" or "outgoing" interfaces, though it is necessary to be 224 able to distinguish the upstream interface from any downstream inter- 225 faces. In CBT, these interfaces are known as the "parent" and "child" 226 interfaces, respectively. 228 With regards to the information contained in the multicast forwarding 229 cache, on link types not supporting native multicast transmission an 230 on-tree router must store the address of a parent and any children. 231 On links supporting multicast however, parent and any child informa- 232 tion is represented with local interface addresses (or similar iden- 233 tifying information, such as an interface "index") over which the 234 parent or child is reachable. 236 When a multicast data packet arrives at a router, the router uses the 237 group address as an index into the multicast forwarding cache. A copy 238 of the incoming multicast data packet is forwarded over each inter- 239 face (or to each address) listed in the entry except the incoming 240 interface. 242 Each router that comprises a CBT multicast tree, except the core 243 router, is responsible for maintaining its upstream link, provided it 244 has interested downstream receivers, i.e. the child interface list is 245 not NULL. A child interface is one over which a member host is 246 directly attached, or one over which a downstream on-tree router is 247 attached. This "tree maintenance" is achieved by each downstream 248 router periodically sending a CBT "keepalive" message (ECHO_REQUEST) 249 to its upstream neighbour, i.e. its parent router on the tree. One 250 keepalive message is sent to represent entries with the same parent, 251 thereby improving scalability on links which are shared by many 252 groups. On multicast capable links, a keepalive is multicast to the 253 "all-cbt-routers" group (IANA assigned as 224.0.0.15); this has a 254 suppressing effect on any other router for which the link is its par- 255 ent link. If a parent link does not support multicast transmission, 256 keepalives are unicast. 258 The receipt of a keepalive message over a valid child interface 259 prompts a response (ECHO_REPLY), which is either unicast or multi- 260 cast, as appropriate. The ECHO_REPLY message carries a list of 261 groups for which the corresponding interface is a child interface. 263 It cannot be assumed all of the routers on a multi-access link have a 264 uniform view of unicast routing; this is particularly the case when a 265 multi-access link spans two or more unicast routing domains. This 266 could lead to multiple upstream tree branches being formed (an error 267 condition) unless steps are taken to ensure all routers on the link 268 agree which is the upstream router for a particular group. CBT 269 routers attached to a multi-access link participate in an explicit 270 election mechanism that elects a single router, the designated router 271 (DR), as the link's upstream router for all groups. Since the DR 272 might not be the link's best next-hop for a particular core router, 273 this may result in join messages being re-directed back across a 274 multi-access link. If this happens, the re-directed join message is 275 unicast across the link by the DR to the best next-hop, thereby pre- 276 venting a looping scenario. This re-direction only ever applies to 277 join messages. Whilst this is suboptimal for join messages, which 278 are generated infrequently, multicast data never traverses a link 279 more than once (either natively, or encapsulated). 281 In all but the exception case described above, all CBT control mes- 282 sages are multicast over multicast supporting links to the "all-cbt- 283 routers" group, with IP TTL 1. The IP source address of CBT control 284 messages is the outgoing interface of the sending router. The IP des- 285 tination address of CBT control messages is either the "all-cbt- 286 routers" group address, or the IP address of a router reachable over 287 one of the sending router's interfaces, depending on whether the 288 sender's outgoing link supports multicast transmission. All the nec- 289 essary addressing information is obtained as part of tree set up. 291 If CBT is implemented over a tunnelled topology, when sending a CBT 292 control packet over a tunnel interface, the sending router uses as 293 the packet's IP source address the local tunnel end point address, 294 and the remote tunnel end point address as the packet's IP destina- 295 tion address. 297 4. Protocol Specification Details 299 Details of the CBT protocol are presented in the context of a single 300 router implementation. 302 4.1. CBT HELLO Protocol 304 The HELLO protocol is used to elect a designated router (DR) on 305 broadcast-type links. It is also used to elect a designated border 306 router (BR) when interconnecting a CBT domain with other domains (see 307 [5]). Alternatively, the designated BR may be elected as a matter of 308 local policy. 310 A router represents its status as a link's DR by setting the DR-flag 311 on that interface; a DR flag is associated with each of a router's 312 broadcast interfaces. This flag can only assume one of two values: 313 TRUE or FALSE. By default, this flag is FALSE. 315 A network manager can preference a router's DR eligibility by option- 316 ally configuring an HELLO preference, which is included in the 317 router's HELLO messages. Valid configuration values range from 1 to 318 254 (decimal), 1 representing the "most eligible" value. In the 319 absence of explicit configuration, a router assumes the default HELLO 320 preference value of 255. The elected DR uses HELLO preference zero 321 (0) in HELLO advertisements, irrespective of any configured prefer- 322 ence. The DR continues to use preference zero for as long as it is 323 running. 325 HELLO messages are multicast periodically to the all-cbt-routers 326 group, 224.0.0.15, using IP TTL 1. The advertisement period is 327 [HELLO_INTERVAL] seconds. 329 HELLO messages have a suppressing effect on those routers which would 330 advertise a "lesser preference" in their HELLO messages; a router 331 resets its [HELLO_INTERVAL] if the received HELLO is "better" than 332 its own. Thus, in steady state, the HELLO protocol incurs very little 333 traffic overhead. 335 The DR election winner is that which advertises the lowest HELLO 336 preference, or the lowest-addressed in the event of a tie. 338 The situation where two or more routers attached to the same broad- 339 cast link are advertising HELLO preference 0 should never arise. How- 340 ever, should this situation arise, all but the lowest addressed zero- 341 advertising router relinquishes its claim as DR immediately by unset- 342 ting the DR flag on the corresponding interface. The relinquishing 343 router(s) subsequently advertise their previously used preference 344 value in HELLO advertisements. 346 4.1.1. Sending HELLOs 348 When a router starts up, it multicasts two HELLO messages over each 349 of its broadcast interfaces in successsion. The DR flag is initially 350 unset (FALSE) on each broadcast interface. This avoids the situation 351 in which each router on a multi-access subnet believes it is the DR, 352 thus preventing the multiple forwarding of join-requests should they 353 arrive during this start up period. If no "better" HELLO message is 354 received after HOLDTIME seconds, the router assumes the role of DR on 355 the corresponding interface. 357 A router sends an HELLO message whenever its [HELLO_INTERVAL] 358 expires. Whenever a router sends an HELLO message, it resets its 359 hello timer. 361 4.1.2. Receiving HELLOs 363 A router does not respond to an HELLO message if the received HELLO 364 is "better" than its own, or equally preferenced but lower addressed. 366 A router must respond to an HELLO message if that received is lesser 367 preferenced (or equally preferenced but higher addressed) than would 368 be sent by this router over the same interface. This response is 369 immediate. 371 4.2. JOIN_REQUEST Processing 373 A JOIN_REQUEST is the CBT control message used to register a member 374 host's interest in joining the distribution tree for the group. 376 4.2.1. Sending JOIN_REQUESTs 378 A JOIN_REQUEST can only ever be originated by a leaf router, i.e. a 379 router with directly attached member hosts. This join message is sent 380 hop-by-hop towards the core router for the group (see section 7). 381 The originating router caches state 382 for each join it originates. This state is known as "transient join 383 state". The absence of a "downstream interface" (NULL) indicates 384 that this router is the join message originator, and is therefore 385 responsible for any retransmissions of this message if a response is 386 not received within [RTX_INTERVAL]. It is an error if no response is 387 received after [JOIN_TIMEOUT] seconds. If this error condition 388 occurs, the joining process may be re-invoked by the receipt of the 389 next IGMP host membership report from a locally attached member host. 391 Note that if the interface over which a JOIN_REQUEST is to be sent 392 supports multicast, the JOIN_REQUEST is multicast to the all-cbt- 393 routers group, using IP TTL 1. If the link does not support multi- 394 cast, the JOIN_REQUEST is unicast to the next hop on the unicast path 395 to the group's core. 397 4.2.2. Receiving JOIN_REQUESTs 399 On broadcast links, JOIN_REQUESTs which are multicast may only be 400 forwarded by the link's DR. Other routers attached to the link may 401 process the join (see below). JOIN_REQUESTs which are multicast over 402 a point-to-point link are only processed by the router on the link 403 which does not have a local interface corresponding to the join's 404 network layer (IP) source address. Unicast JOIN_REQUESTs may only be 405 processed by the router which has a local interface corresponding to 406 the join's network layer (IP) destination address. 408 With regard to forwarding a received JOIN_REQUEST, if the receiving 409 router is not on-tree for the group, and is not the group's core 410 router, the join is forwarded to the next hop on the path towards the 411 core. The join is multicast, or unicast, according to whether the 412 outgoing interface supports multicast. The router caches the follow- 413 ing information with respect to the forwarded join: . 416 If this transient join state is not "confirmed" with a join acknowl- 417 edgement (JOIN_ACK) message from upstream, the state is timed out 418 after [TRANSIENT_TIMEOUT] seconds. 420 If the receiving router is the group's core router, the join is "ter- 421 minated" and acknowledged by means of a JOIN_ACK. Similarly, if the 422 router is on-tree and the JOIN_REQUEST arrives over an interface that 423 is not the upstream interface for the group, the join is acknowl- 424 edged. 426 If a JOIN_REQUEST for the same group is scheduled to be sent over the 427 corresponding interface (i.e. awaiting a timer expiry), the 428 JOIN_REQUEST is unscheduled. 430 If this router has a cache-deletion-timer [CACHE_DEL_TIMER] running 431 on the arrival interface for the group specified in a multicast join, 432 the timer is cancelled. 434 4.3. JOIN_ACK Processing 436 A JOIN_ACK is the mechanism by which an interface is added to a 437 router's multicast forwarding cache; thus, the interface becomes part 438 of the group distribution tree. 440 4.3.1. Sending JOIN_ACKs 442 The JOIN_ACK is sent over the same interface as the corresponding 443 JOIN_REQUEST was received. The sending of the acknowledgement causes 444 the router to add the interface to its child interface list in its 445 forwarding cache for the group, if it is not already. 447 A JOIN_ACK is multicast or unicast, according to whether the outgoing 448 interface supports multicast transmission or not. 450 4.3.2. Receiving JOIN_ACKs 452 The group and arrival interface must be matched to a from the router's cached transient state. If no 454 match is found, the JOIN_ACK is discarded. If a match is found, a 455 CBT forwarding cache entry for the group is created, with "upstream 456 interface" marked as the group's parent interface. 458 If "downstream interface" in the cached transient state is NULL, the 459 JOIN_ACK has reached the originator of the corresponding 460 JOIN_REQUEST; the JOIN_ACK is not forwarded downstream. If "down- 461 stream interface" is non-NULL, a JOIN_ACK for the group is sent over 462 the "downstream interface" (multicast or unicast, accordingly). This 463 interface is installed in the child interface list of the group's 464 forwarding cache entry. 466 Once transient state has been confirmed by transferring it to the 467 forwarding cache, the transient state is deleted. 469 4.4. QUIT_NOTIFICATION Processing 471 A CBT tree is "pruned" in the direction downstream-to-upstream when- 472 ever a CBT router's child interface list for a group becomes NULL. 474 4.4.1. Sending QUIT_NOTIFICATIONs 476 A QUIT_NOTIFICATION is sent to a router's parent router on the tree 477 whenever the router's child interface list becomes NULL. If the link 478 over which the quit is to be sent supports multicast transmission, if 479 the sending router is the link's DR the quit is unicast, otherwise it 480 is multicast. 482 A QUIT_NOTIFICATION is not acknowledged; once sent, all information 483 pertaining to the group it represents is deleted from the forwarding 484 cache immediately. 486 To help ensure consistency between a child and parent router given 487 the potential for loss of a QUIT_NOTIFICATION, a total of [MAX_RTX] 488 QUIT_NOTIFICATIONs are sent, each HOLDTIME seconds after the previous 489 one. 491 The sending of a quit (the first) also invokes the sending of a 492 FLUSH_TREE message over each downstream interface for the correspond- 493 ing group. 495 4.4.2. Receiving QUIT_NOTIFICATIONs 497 The group reported in the QUIT_NOTIFICATION must be matched with a 498 forwarding cache entry. If no match is found, the QUIT_NOTIFICATION 499 is ignored and discarded. If a match is found, if the arrival inter- 500 face is a valid child interface in the group entry, how the router 501 proceeds depends on whether the QUIT_NOTIFICATION was multicast or 502 unicast. 504 If the QUIT_NOTIFICATION was unicast, the corresponding child inter- 505 face is deleted from the group's forwarding cache entry, and no fur- 506 ther processing is required. 508 If the QUIT_NOTIFICATION was multicast, and the arrival interface is 509 a valid child interface for the specified group, the router sets a 510 cache-deletion-timer [CACHE_DEL_TIMER]. 512 Because this router might be acting as a parent router for multiple 513 downstream routers attached to the arrival link, [CACHE_DEL_TIMER] 514 interval gives those routers that did not send the QUIT_NOTIFICA- 515 TION, but received it over their parent interface, the opportunity to 516 ensure that the parent router does not remove the link from its child 517 interface list. Therefore, on receipt of a multicast 518 QUIT_NOTIFICATION over a parent interface, a receiving router sched- 519 ules a JOIN_REQUEST for the group for sending at a random interval 520 between 0 (zero) and HOLDTIME seconds. If a multicast JOIN_REQUEST 521 is received over the corresponding interface (parent) for the same 522 group before this router sends its own scheduled JOIN_REQUEST, it 523 unschedules the multicasting of its own JOIN_REQUEST. 525 4.5. ECHO_REQUEST Processing 527 The ECHO_REQUEST message allows a child to monitor reachability to 528 its parent router for a group (or range of groups if the parent 529 router is the parent for multiple groups). Group information is not 530 carried in ECHO_REQUEST messages. 532 4.5.1. Sending ECHO_REQUESTs 534 Whenever a router creates a forwarding cache entry due to the receipt 535 of a JOIN_ACK, the router begins the periodic sending of ECHO_REQUEST 536 messages over its parent interface. The ECHO_REQUEST is multicast to 537 the "all-cbt-routers" group over multicast-capable interfaces, and 538 unicast to the parent router otherwise. 540 ECHO_REQUEST messages are sent at [ECHO_INTERVAL] second intervals. 541 Whenever an ECHO_REQUEST is sent, [ECHO_INTERVAL] is reset. 543 If no response is forthcoming, any groups present on the parent 544 interface will eventually expire [GROUP_EXPIRE_TIME]. This results in 545 the sending of a QUIT_NOTIFICATION upstream, and sends a FLUSH_TREE 546 message downstream for each group for which the upstream interface 547 was the parent interface. 549 4.5.2. Receiving ECHO_REQUESTs 551 If an ECHO_REQUEST is received over any valid child interface, the 552 receiving router schedules an ECHO_REPLY message for sending over the 553 same interface; the scheduled interval is between 0 (zero) and HOLD- 554 TIME seconds. This message is multicast to the "all-cbt-routers" 555 group over multicast-capable interfaces, and unicast otherwise. 557 If a multicast ECHO_REQUEST message arrives via any valid parent 558 interface, the router resets its [ECHO_INTERVAL] timer for that 559 upstream interface, thereby suppressing the sending of its own 560 ECHO_REQUEST over that upstream interface. 562 4.6. ECHO_REPLY Processing 564 ECHO_REPLY messages allow a child to monitor the reachability of its 565 parent, and help ensure the group state information is consistent 566 between them. 568 4.6.1. Sending ECHO_REPLY messages 570 An ECHO_REPLY message is sent in response to receiving an 571 ECHO_REQUEST message, provided the ECHO_REQUEST is received over any 572 one of this router's valid child interfaces. An ECHO_REPLY reports 573 all groups for which the link is its child. 575 ECHO_REPLY messages are unicast or multicast, as appropriate. 577 4.6.2. Receiving ECHO_REPLY messages 579 An ECHO_REPLY message must be received via a valid parent interface. 581 For each group reported in an ECHO_REPLY, the downstream router 582 attempts to match the group with one in its forwarding cache for 583 which the arrival interface is the group's parent interface. For each 584 successful match, the entry is "refreshed". If however, after 585 [GROUP_EXPIRE_TIME] seconds a group has not been "refreshed", a 586 QUIT_NOTIFICATION is sent upstream, and a FLUSH_TREE message is sent 587 downstream, for the group. 589 If this router has directly attached members for any of the flushed 590 groups, the receipt of an IGMP host membership report for any of 591 those groups will prompt this router to rejoin the corresponding 592 tree(s). 594 4.7. FLUSH_TREE Processing 596 The FLUSH_TREE (flush) message is the mechanism by which a router 597 invokes the tearing down of all its downstream branches for a partic- 598 ular group. The flush message is multicast to the "all-cbt-routers" 599 group when sent over multicast-capable interfaces, and unicast other- 600 wise. 602 4.7.1. Sending FLUSH_TREE messages 604 A FLUSH_TREE message is sent over each downstream (child) interface 605 when a router has lost reachability with its parent router for the 606 group (detected via ECHO_REQUEST and ECHO_REPLY messages). All group 607 state is removed from an interface over which a flush message is 608 sent. A flush can specify a single group, or all groups 609 (INADDR_ANY). 611 4.7.2. Receiving FLUSH_TREE messages 613 A FLUSH_TREE message must be received over the parent interface for 614 the specified group, otherwise the message is discarded. 616 The flush message must be forwarded over each child interface for the 617 specified group. 619 Once the flush message has been forwarded, all state for the group is 620 removed from the router's forwarding cache. 622 5. Timers and Default Values 624 This section provides a summary of the timers described above, 625 together with their recommended default values. Other values may be 626 configured; if so, the values used should be consistent across all 627 CBT routers attached to the same network. 629 +o [HELLO_INTERVAL]: the interval between sending an HELLO message. 630 Default: 60 seconds. 632 +o [HELLO_PREFERENCE]: Default: 255. 634 +o [HOLDTIME]: generic response interval. Default: 3 seconds. 636 +o [MAX_RTX]: default maximum number of retransmissions. Default 3. 638 +o [RTX_INTERVAL]: message retransmission time. Default: 5 seconds. 640 +o [JOIN_TIMEOUT]: raise exception due to tree join failure. 641 Default: 3.5 times [RTX_INTERVAL]. 643 +o [TRANSIENT_TIMEOUT]: delete (unconfirmed) transient state. 644 Default: (1.5*RTX_INTERVAL) seconds. 646 +o [CACHE_DEL_TIMER]: remove child interface from forwarding cache. 647 Default: (1.5*HOLDTIME) seconds. 649 +o [ECHO_INTERVAL]: interval between sending ECHO_REQUEST to parent 650 routers. Default: 60 seconds. 652 +o [EXPECTED_REPLY_TIME]: consider parent unreachable. Default: 70 653 seconds. 655 6. CBT Packet Formats and Message Types 657 CBT control packets are encapsulated in IP. CBT has been assigned IP 658 protocol number 7 by IANA [4]. 660 6.1. CBT Common Control Packet Header 662 All CBT control messages have a common fixed length header. 664 0 1 2 3 665 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 666 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 667 | vers | type | addr len | checksum | 668 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 670 Figure 1. CBT Common Control Packet Header 672 This CBT specification is version 2. 674 CBT packet types are: 676 +o type 0: HELLO 678 +o type 1: JOIN_REQUEST 680 +o type 2: JOIN_ACK 682 +o type 3: QUIT_NOTIFICATION 683 +o type 4: ECHO_REQUEST 685 +o type 5: ECHO_REPLY 687 +o type 6: FLUSH_TREE 689 +o type 7: Bootstrap Message (optional) 691 +o type 8: Candidate Core Advertisement (optional) 693 +o Addr Length: address length in bytes of unicast or multicast 694 addresses carried in the control packet. 696 +o Checksum: the 16-bit one's complement of the one's complement 697 sum of the entire CBT control packet. 699 6.2. HELLO Packet Format 701 0 1 2 3 702 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 703 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 704 | CBT Control Packet Header | 705 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 706 | Preference | option type | option len | option value | 707 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 709 Figure 2. HELLO Packet Format 711 HELLO Packet Field Definitions: 713 +o preference: sender's HELLO preference. 715 +o option type: the type of option present in the "option value" 716 field. One option type is currently defined: option type 0 717 (zero) = BR_HELLO; option value 0 (zero); option length 0 718 (zero). This option type is used with HELLO messages sent by a 719 border router (BR) as part of designated BR election (see [5]). 721 +o option len: length of the "option value" field in bytes. 723 +o option value: variable length field carrying the option value. 725 6.3. JOIN_REQUEST Packet Format 727 0 1 2 3 728 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 729 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 730 | CBT Control Packet Header | 731 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 732 | group address | 733 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 734 | target router | 735 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 736 | originating router | 737 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 738 | option type | option len | option value | 739 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 741 Figure 3. JOIN_REQUEST Packet Format 743 JOIN_REQUEST Field Definitions 745 +o group address: multicast group address of the group being 746 joined. For a "wildcard" join (see [5]), this field contains 747 the value of INADDR_ANY. 749 +o target router: target (core) router for the group. 751 +o originating router: router that originated this JOIN_REQUEST. 753 +o option type, option len, option value: see HELLO packet format, 754 section 6.2. 756 6.4. JOIN_ACK Packet Format 758 JOIN_ACK Field Definitions 760 +o group address: multicast group address of the group being 761 joined. 763 +o target router: router (DR) that originated the corresponding 764 0 1 2 3 765 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 766 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 767 | CBT Control Packet Header | 768 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 769 | group address | 770 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 771 | target router | 772 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 773 | option type | option len | option value | 774 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 776 Figure 4. JOIN_ACK Packet Format 777 JOIN_REQUEST. 779 +o option type, option len, option value: see HELLO packet format, 780 section 6.2. 782 6.5. QUIT_NOTIFICATION Packet Format 784 0 1 2 3 785 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 786 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 787 | CBT Control Packet Header | 788 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 789 | group address | 790 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 791 | originating child router | 792 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 794 Figure 5. QUIT_NOTIFICATION Packet Format 796 QUIT_NOTIFICATION Field Definitions 798 +o group address: multicast group address of the group being 799 joined. 801 +o originating child router: address of the router that originates 802 the QUIT_NOTIFICATION. 804 6.6. ECHO_REQUEST Packet Format 806 0 1 2 3 807 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 808 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 809 | CBT Control Packet Header | 810 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 811 | originating child router | 812 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 814 Figure 6. ECHO_REQUEST Packet Format 816 ECHO_REQUEST Field Definitions 818 +o originating child router: address of the router that originates 819 the ECHO_REQUEST. 821 6.7. ECHO_REPLY Packet Format 823 0 1 2 3 824 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 825 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 826 | CBT Control Packet Header | 827 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 828 | originating parent router | 829 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 830 | group address #1 | 831 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 832 | group address #2 | 833 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 834 | ...... | 835 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 836 | group address #n | 837 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 839 Figure 7. ECHO_REPLY Packet Format 841 ECHO_REPLY Field Definitions 842 +o oringinating parent router: address of the router originating 843 this ECHO_REPLY. 845 +o group address: a list of multicast group addresses for which 846 this router considers itself a parent router w.r.t. the link 847 over which this message is sent. 849 6.8. FLUSH_TREE Packet Format 851 0 1 2 3 852 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 853 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 854 | CBT Control Packet Header | 855 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 856 | group address | 857 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 858 | ...... | 859 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 860 | group address #n | 861 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 863 Figure 8. FLUSH_TREE Packet Format 865 FLUSH_TREE Field Definitions 867 +o group address(es): multicast group address(es) of the group(s) 868 being "flushed". 870 7. Core Router Discovery 872 There are two available options for CBTv2 core discovery; the "boot- 873 strap" mechanisms (as currently specified with the PIM sparse mode 874 protocol [2]) is applicable only to intra-domain core discovery, and 875 allows for a "plug & play" type operation with minimal configuration. 876 The disadvantage of the bootstrap mechanism is that it is much more 877 difficult to affect the shape, and thus optimality, of the resulting 878 distribution tree. Also, to be applicable, all CBT routers within a 879 domain must implement the bootstrap mechanism. 881 The other option is to manually configure leaf routers with mappings (note: leaf routers only); this imposes a degree of 883 administrative burden - the mapping for a particular group must be 884 coordinated across all leaf routers to ensure consistency. Hence, 885 this method does not scale particularly well. However, it is likely 886 that "better" trees will result from this method, and it is also the 887 only available option for inter-domain core discovery currently 888 available. 890 7.1. "Bootstrap" Mechanism Overview 892 It is unlikely that the bootstrap mechanism will be appended to a 893 well-known network layer protocol, such as IGMP [3], though this 894 would facilitate its ubiquitous (intra-domain) deployment. Therefore, 895 each multicast routing protocol requiring the bootstrap mechanism 896 must implement it as part of the multicast routing protocol itself. 898 A summary of the operation of the bootstrap mechanism follows 899 (details are provided in [7]). It is assumed that all routers within 900 the domain implement the "bootstrap" protocol, or at least forward 901 bootstrap protocol messages. 903 A subset of the domain's routers are configured to be CBT candidate 904 core routers. Each candidate core router periodically (default every 905 60 secs) advertises itself to the domain's Bootstrap Router (BSR), 906 using "Core Advertisement" messages. The BSR is itself elected 907 dynamically from all (or participating) routers in the domain. The 908 domain's elected BSR collects "Core Advertisement" messages from can- 909 didate core routers and periodically advertises a candidate core set 910 (CC-set) to each other router in the domain, using traditional hop- 911 by-hop unicast forwarding. The BSR uses "Bootstrap Messages" to 912 advertise the CC-set. Together, "Core Advertisements" and "Bootstrap 913 Messages" comprise the "bootstrap" protocol. 915 When a router receives an IGMP host membership report from one of its 916 directly attached hosts, the local router uses a hash function on the 917 reported group address, the result of which is used as an index into 918 the CC-set. This is how local routers discover which core to use for 919 a particular group. 921 Note the hash function is specifically tailored such that a small 922 number of consecutive groups always hash to the same core. Further- 923 more, bootstrap messages can carry a "group mask", potentially 924 limiting a CC-set to a particular range of groups. This can help 925 reduce traffic concentration at the core. 927 If a BSR detects a particular core as being unreachable (it has not 928 announced its availability within some period), it deletes the rele- 929 vant core from the CC-set sent in its next bootstrap message. This is 930 how a local router discovers a group's core is unreachable; the 931 router must re-hash for each affected group and join the new core 932 after removing the old state. The removal of the "old" state follows 933 the sending of a QUIT_NOTIFICATION upstream, and a FLUSH_TREE message 934 downstream. 936 7.2. Bootstrap Message Format 938 0 1 2 3 939 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 940 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 941 | CBT common control packet header | 942 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 943 | For full Bootstrap Message specification, see [7] | 944 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 946 Figure 9. Bootstrap Message Format 948 7.3. Candidate Core Advertisement Message Format 950 0 1 2 3 951 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 952 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 953 | CBT common control packet header | 954 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 955 | For full Candidate Core Adv. Message specification, see [7] | 956 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 958 Figure 10. Candidate Core Advertisement Message Format 960 8. Interoperability Issues 962 Interoperability between CBT and DVMRP is specified in [5]. 964 Interoperability with other multicast protocols will be fully speci- 965 fied as the need arises. 967 Acknowledgements 969 Special thanks goes to Paul Francis, NTT Japan, for the original 970 brainstorming sessions that brought about this work. 972 The emergence of CBTv2 owes much to Clay Shields and his work on 973 Ordered CBT (OCBT) [8]. Clay identified and proved several failure 974 modes of CBT as it was specified with multiple cores, and also sug- 975 gested using an unreliable quit mechanism, which appears in this 976 specification as the QUIT_NOTIFICATION. Clay has also provided more 977 general constructive comments on the CBT architecture and specifica- 978 tion. 980 Others that have contributed to the progress of CBT include Ken Carl- 981 berg, Eric Crawley, Jon Crowcroft, Mark Handley, Ahmed Helmy, Nitin 982 Jain, Alan O'Neill, Steven Ostrowsksi, Radia Perlman, Scott Reeve, 983 Benny Rodrig, Martin Tatham, Dave Thaler, Sue Thompson, Paul White, 984 and other participants of the IETF IDMR working group. 986 Thanks also to 3Com Corporation and British Telecom Plc for funding 987 this work. 989 References 991 [1] Core Based Trees (CBT) Multicast Routing Architecture; 992 A. Ballardie; ftp://ds.internic.net/internet-drafts/draft-ietf-idmr- 993 cbt-arch-**.txt. Working draft, April 1997. 995 [2] Protocol Independent Multicast (PIM) Sparse Mode/Dense Mode; D. 996 Estrin et al; ftp://netweb.usc.edu/pim Working drafts, 1996. 998 [3] Internet Group Management Protocol, version 2 (IGMPv2); W. Fenner; 999 ftp://ds.internic.net/internet-drafts/draft-ietf-idmr-igmp-v2-**.txt. 1000 Working draft, 1996. 1002 [4] Assigned Numbers; J. Reynolds and J. Postel; RFC 1700, October 1003 1994. 1005 [5] CBT Border Router Specification for Interconnecting a CBT Stub 1006 Region to a DVMRP Backbone; A. Ballardie; ftp://ds.internic.net/inter- 1007 net-drafts/draft-ietf-idmr-cbt-dm-interop-**.txt. Working draft, 1008 March 1997. 1010 [6] Scalable Multicast Key Distribution; A. Ballardie; RFC 1949, July 1011 1996. 1013 [7] A Dynamic Bootstrap Mechanism for Rendezvous-based Multicast Rout- 1014 ing; D. Estrin et al.; Technical Report; ftp://catarina.usc.edu/pim 1016 [8] The Ordered Core Based Tree Protocol; C. Shields and J.J. Garcia- 1017 Luna-Aceves; In Proceedings of IEEE Infocom'97, Kobe, Japan, April 1018 1997; http://www.cse.ucsc.edu/research/ccrg/publications/info- 1019 comm97ocbt.ps.gz 1021 Author Information: 1023 Tony Ballardie, 1024 Research Consultant, 1026 e-mail: ABallardie@acm.org