idnits 2.17.1 draft-ietf-rmt-gra-arch-02.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: ---------------------------------------------------------------------------- ** 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? == 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 separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** The abstract seems to contain references ([SRM,RMTP,, [ACTIVE], [PGM], [LSM], [LABEL], [GMTS,BFS], TKP]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. 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 (20 July 2001) is 8314 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) == Unused Reference: 'KKT' is defined on line 896, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'ACTIVE' -- Possible downref: Non-RFC (?) normative reference: ref. 'BFS' -- Possible downref: Non-RFC (?) normative reference: ref. 'GMTS' -- Possible downref: Non-RFC (?) normative reference: ref. 'KKT' -- Possible downref: Non-RFC (?) normative reference: ref. 'LABEL' -- Possible downref: Non-RFC (?) normative reference: ref. 'LSM' == Outdated reference: A later version (-07) exists of draft-speakman-pgm-spec-03 ** Downref: Normative reference to an Experimental draft: draft-speakman-pgm-spec (ref. 'PGM') -- Possible downref: Non-RFC (?) normative reference: ref. 'RMTP' -- Possible downref: Non-RFC (?) normative reference: ref. 'SRM' -- Possible downref: Non-RFC (?) normative reference: ref. 'TKP' Summary: 7 errors (**), 0 flaws (~~), 3 warnings (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 RMT Working Group Generic Router Assist (GRA) Brad Cain 3 INTERNET-DRAFT for Multicast Transport Protocols Cereva Networks 4 Tony Speakman 5 Expires January 2002 cisco 6 Don Towsley 7 UMASS 9 20 July 2001 11 Generic Router Assist (GRA) Building Block 12 Motivation and Architecture 13 15 Status of this Memo 17 This document is an Internet-Draft and is in full conformance with 18 all provisions of Section 10 of RFC2026. 20 Internet-Drafts are working documents of the Internet Engineering 21 Task Force (IETF), its areas, and its working groups. Note that 22 other groups may also distribute working documents as Internet- 23 Drafts. 25 Internet-Drafts are draft documents valid for a maximum of six months 26 and may be updated, replaced, or obsoleted by other documents at any 27 time. It is inappropriate to use Internet- Drafts as reference 28 material or to cite them other than as "work in progress." 30 The list of current Internet-Drafts can be accessed at 31 http://www.ietf.org/ietf/1id-abstracts.txt 33 The list of Internet-Draft Shadow Directories can be accessed at 34 http://www.ietf.org/shadow.html. 36 Abstract 38 Generic Router Assist (GRA) is a network-based service that enables 39 end-to-end multicast transport protocols to take advantage of infor- 40 mation distributed across the network elements in a given multicast 41 distribution tree. The service consists of a canonical set of simple 42 functions which network elements may apply to selected packets in the 43 transport session as they traverse the distribution tree. The choice 44 of function and the packet parameters to which it is applied can be 45 defined and customized for a given transport session in a highly con- 46 trolled fashion that still permits enough flexibility for GRA to be 47 used to address a wide range of multicast transport problems not 48 amenable to end-to-end solution. This document provides the motiva- 49 tion and an architecture for GRA. 51 Table of Contents 53 1. Introduction ............................................... 4 54 2. Scope of Generic Router Assist ............................. 6 55 3. Canonical Services and Functional Models/Examples .......... 11 56 4. Implementation Considerations .............................. 19 57 Abbreviations .................................................. 22 58 References ..................................................... 23 59 Revision History ............................................... 24 60 Authors' Addresses ............................................. 24 61 1. Introduction 63 The development of scalable end-to-end multicast protocols poses a 64 tremendous challenge to network protocol designers. For example the 65 development of reliable multicast protocols has received considerable 66 attention in recent years. Most protocols are based on an end-to-end 67 solution [SRM, RMTP, TKP] and have found the problem of scaling to 68 1000s or even 100s of receivers daunting. The primary obstacles to 69 the development of scalable protocols have been feedback implosion 70 and transmission isolation. The first of these concerns the diffi- 71 culty of a large multicast application to limit feedback from 72 receivers to a data source or to each other. The second concerns the 73 difficulty of limiting the transmission of data to the subset of a 74 multicast group that requires it. 76 Several proposals have been made to add functionality to routers for 77 the purpose of improving the performance of multicast applications, 78 particularly reliable multicast. Papadopoulos and Parulkar [LSM] 79 introduced additional forwarding functionality to a router which 80 would allow each router to identify a "special outgoing interface" 81 over which to transmit a particular class of packets. They showed how 82 this "turning point functionality" could be used to improve the per- 83 formance of reliable multicast protocols. Levine and Garcia-Luna- 84 Aceves [LABEL] proposed the addition of "routing labels" to routing 85 tables which could be used to direct packets over specific inter- 86 faces. One of these, called a distance label, was shown to be quite 87 useful in reliable multicast for directing requests for repairs to 88 nearby repair servers. The third and, perhaps most relevant proposal 89 is the PGM protocol [PGM]. Briefly, PGM is a reliable multicast pro- 90 tocol which uses negative acknowledgements (NAKs). The PGM protocol 91 is an end-to-end transport protocol that contains a router component 92 which performs NAK elimination and retransmission subcasting func- 93 tionality. This proposal, like others [GMTS, BFS], is primarily 94 motivated by PGM and the recognition of the benefits of exporting a 95 set of flexible, simple router-based functionality for the purpose of 96 multicast protocol design. Such functionality can significantly sim- 97 plify the design of a large class of scalable multicast transport 98 protocols. 100 In this draft, we present Generic Router Assist (GRA) functionality 101 intended to help protocol designers deal with the two problems of 102 feedback implosion and transmission isolation. This functionality is 103 designed to assist in the scaling of receiver feedback information 104 and in providing subcasting for large multicast groups. It consists 105 of simple filtering functions that reside within routers. 107 Signaling protocols are used by hosts to set up and invoke this func- 108 tionality. Briefly, a data source first initializes one or more 109 desired services on its multicast tree using GRA setup messages. The 110 GRA-capable routers on the tree then selectively eliminate feedback 111 from receivers and/or isolate transmissions through the use of 112 filters set by either the sender or the receivers. For robustness, 113 periodic transmissions of setup messages on the multicast tree are 114 used to refresh GRA state in the face of routing changes and other 115 possible errors. It should be stressed that GRA services are only 116 invoked for certain packets; data packets are usually not treated any 117 differently and will not cause any additional processing in routers. 119 GRA is not intended to provide sophisticated services which are dif- 120 ficult or impossible to implement in routers. GRA functionality is 121 implemented at the IP layer and provides unreliable, best-effort ser- 122 vices. Transport protocols which make use of GRA must be robust in 123 the face of failures and the absence of GRA-capable routers in the 124 network. 126 Before describing the details of GRA, we present a simple example in 127 the context of a PGM-like reliable multicast protocol. 129 Consider a NAK-based reliable multicast protocol which places the 130 responsibility of packet loss detection on each receiver. Each time 131 that a receiver detects a loss (based on a gap in the sequence 132 numbers of the packets that it receives), it unicasts a request for a 133 repair (NAK) to the sender. Upon receipt of a NAK for a specific 134 packet, the sender retransmits the packet to all receivers. 136 This protocol faces considerable challenges in dealing with multiple 137 NAKs for the same packet. First, there is the problem of the sender 138 having to process many NAKs. Second, there is the problem of limiting 139 the number of retransmissions to the same packet. GRA can be used to 140 address these two problems. Prior to the transfer of any data, the 141 application sets up a NAK elimination service at each GRA-capable 142 router using a setup message. This service is set up to eliminate 143 NAKs generated for the same packet. In addition, the service main- 144 tains information regarding the interfaces over which it has received 145 NAKs so that it can subcast the retransmission on the portion of the 146 multicast tree that contains receivers requiring a retransmission of 147 the packet. 149 In Figure 1, we show how GRA can be used to eliminate feedback infor- 150 mation in a reliable multicast transport protocol. In this figure, a 151 multicast source (Src 1) transmits to two receivers (Rec 1 and Rec 152 2). The data packets from Src 1 are treated as regular multicast 153 packets and forwarded accordingly. On the link between router R1 and 154 router R2, a data packet is lost. Assuming a NAK based reliable mul- 155 ticast protocol, this loss causes the receivers to each send a NAK to 156 the source for the packet that was lost. In the example, receivers 157 include a GRA header in NAKs sent to the source. Router R2 treats 158 these NAKs in a special manner, elminating the redundant NAKs to the 159 source. Therefore, only one NAK arrives at the source. We see from 160 this example that only certain types of packets require additional 161 processing at GRA routers and that the majority of end-to-end packets 162 are forwarded according to normal multicast forwarding rules (i.e. 163 without additional router processing). 165 Src 1 166 ^ | | 167 | | | data packet 168 | | | 169 R1 | 170 ^ | | 171 | | V 172 R2 eliminates | | X data packet dropped 173 duplicate +--->R2 <---+ 174 NAK | --- --- | 175 | | | | 176 | | | | 177 | | | | 178 R3 R4 179 GRA ^ | | ^ GRA 180 NAK | | | | NAK 181 | | | | 182 Rec 1 Rec 2 184 Figure 1. Example of network support for transport protocols. 186 GRA may be used on all types of multicast forwarding trees. However, 187 GRA state is per-transport-session state and so requires per- 188 transport-session state in routers in addition to the underlying mul- 189 ticast routing state. 191 2. Scope of Generic Router Assist 193 The types of services implemented with GRA are bounded by constraints 194 and limitations of routing devices. In this section we explicitly 195 describe the limitations and constraints of routing devices and 196 explain some reasonable services to implement in routers. 198 We specifically describe router limitations in order to limit the 199 scope of GRA. A small set of GRA services in routers can assist in 200 scaling many of the problems in end-to-end multicast. Previous 201 proposals[ACTIVE] have proposed complex elements that reside in 202 routers to provide sophisticated capabilities. These are probably 203 unreasonable for current generation routers. The approach of GRA is 204 to provide a simple fixed set of services which give the maximum 205 benefit with the least cost. 207 2.1. Service Properties 209 GRA services are performed on a subset of packets sent between end- 210 to-end transport protocols on the multicast distribution tree between 211 a GRA Source and the set of GRA receivers. Only routers on the dis- 212 tribution tree for a particular GRA source act upon GRA packets. The 213 advantages of GRA type services can only be realized when the actions 214 are performed on packets that are directly on the forwarding tree of 215 a multicast group. 217 In order to describe the requirements of GRA, we first describe the 218 properties of appropriate services. 220 Fixed: by fixed services we mean those which are statically part 221 of router software or hardware. We DO NOT mean dynamically load- 222 able modules. A fixed set of simple services will probably suf- 223 fice for most of the scaling issues in transport protocols. 225 Simple: We include only those services that are reasonable to be 226 implemented in the forwarding path in routers. These are services 227 which can be performed with minimum CPU and memory overhead. 229 Short Term: We provide services for which state and processing 230 overhead is short lived. GRA makes use of soft-state design prin- 231 ciples. 233 2.2. GRA Requirements 235 When considering the service and architecture of GRA, we adhere to 236 the following principles: 238 1. GRA services should be simple and must be fixed. They must not 239 require excessive processing in routing devices and they must not 240 buffer packets. 242 2. GRA services are not substitutes for well-engineered end-to-end 243 protocol designs. We support the end-to-end design principles of 244 transport protocols. GRA is an assist service which is designed 245 to assist protocols in scaling aspects. 247 3. GRA services will not take on active networking attributes such 248 as dynamically uploadable modules or programming language propo- 249 sals. 251 4. GRA services should not directly participate in transport pro- 252 tocols. GRA should not be required for any transport protocols 253 nor should any GRA services directly support a particular proto- 254 col. 256 5. GRA services should be those which may assist all or a reason- 257 able subset of transport protocols. 259 6. GRA services should be used for assisting in control packet 260 operations. GRA services should not be for the majority of pack- 261 ets in a multicast group. 263 2.3. Constraints of networking devices 265 Current generation routers perform processing of packets and execute 266 routing and signaling protocols. Routers perform fast packet for- 267 warding on the forwarding path. This is usually performed by 268 hardware and software specifically designed for the forwarding of 269 packets (and may include other functions such as policing, shaping, 270 etc). This is in contrast to the control plane of a router where 271 control protocols are run in protocol-specific control components. 272 Examples of these types of protocols are routing, management and sig- 273 naling protocols. 275 We now describe the role and impact of GRA services on these two 276 planes of a router. 278 Forwarding path: A router forwarding path usually consists of spe- 279 cialized hardware and software which is designed specifically for 280 the purpose of forwarding packets. Newer routers also have abili- 281 ties to perform other actions such as marking or policing for ser- 282 vices such as QoS. In general, the forwarding path of routers is 283 very limited in the amount of state and complexity of processing 284 that can be performed. The processing complexity and state over- 285 head of GRA services may limit the extent to which they may be 286 implemented in the forwarding path. 288 Control plane: Router control planes run embedded or general 289 operating systems. On top of these operating systems are imple- 290 mentations of IP control protocols such as routing, signaling, and 291 network management. The processing power and memory of a control 292 plane depends highly on the hardware design of the router. Most 293 routers use general purpose CISC or RISC processors for running 294 the control plane operating system and protocols. The control 295 plane is limited in processing by its hardware and the load gen- 296 erated from the other processes or tasks running. We expect that 297 complex or stateful GRA operations will be performed in the con- 298 trol plane where state and processing power are more readily 299 available. However, we do stress that routers generally have 300 fairly slow control plane hardware. This is to keep the cost low 301 and because the processing required for control plane protocols is 302 usually low. 304 2.4. State Constraints 306 As we evaluate particular services which are candidates for inclusion 307 in GRA, constraints in router state are an important consideration. 308 We should select services which will not create substantial or long- 309 lived state. 311 2.4.1. Session State 313 Routers which perform multicast forwarding contain per-tree forward- 314 ing state. For trees rooted at multicast sources, this amounts to 315 per-source, per-group forwarding entries. This state must be kept in 316 both the forwarding as well as the control plane. GRA services are 317 per-session, or per-source. This is simply because GRA services are 318 per-transport-session. 320 The session state of GRA imposes additional state on routers. Each 321 session requires a state block describing the desired services. 322 Other types of state may also be created during the course of a GRA 323 session. The GRA session state is the only state required for the 324 length of a session; other state is set up and torn down in smaller 325 intervals. 327 2.4.2. Per-Packet State 329 The implementation of particular services may require per-packet 330 state in GRA routers. Services which require per-packet state should 331 use short-lived timers to tear down this state so as to avoid an 332 explosion in the amount of state at routers. An example of a service 333 which causes per-packet state is NAK elimination. The use of small 334 timers should minimize problems in state growth. 336 2.4.3. Buffering 338 GRA services must not buffer packets. GRA services may drop or 339 modify packets in transit, but they will never buffer packets. 341 The buffering of packets in routing devices is generally unacceptable 342 due to the unpredictable behavior of such a service. In addition 343 this is, in general, an unreasonable service for routers to support 344 without a significant payback in end-to-end scaling. 346 2.5. Processing Constraints 348 GRA services may require differing amount of computation. As a gen- 349 eral rule, GRA services should require minimal computation and packet 350 manipulation. 352 2.5.1. Computation 354 Most GRA services should require minimal computation. Services which 355 require minimal computation are reasonable to implement in routing 356 devices and minimize security risk. Examples of some appropriate 357 operations are: 359 Comparison Operations: comparison operations may be performed on 360 GRA packets against the GRA session state in the router in order 361 to determine whether a service should be invoked. Examples of 362 comparison operations are: equal to, less than, greater than, etc. 364 Update Operations: When receiving a GRA packet, a router may be 365 required to update its GRA session state. The operations required 366 for updating the state should remain simple. Example of simple 367 operations are addition, subtraction, etc. 369 In order to limit the computational complexity of GRA services, GRA 370 operations should remain singular. The combination of predicates and 371 operations creates problems in both router processing and in GRA 372 specifications themselves. This restriction will avoid problems 373 regarding operator and action precedence. 375 2.5.2. Buffer Operations 377 One can define services requiring extensive packet manipulation by 378 GRA routers. This is probably expensive and therefore unreasonable 379 for routers. GRA services should be invoked without extensive mani- 380 pulation of packets. Services which update or overwrite fields are 381 acceptable. Services which require the formation of new packets or 382 accumulate information into new packets are unacceptable. 384 2.6. Examples of Reasonable Services 386 In this section we briefly describe two GRA services and the ways in 387 which they meet the above requirements. The two example services are 388 those that provide general functions which do not incur large amounts 389 of state or processing. 391 Elimination: Elimination is the selected dropping of redundant 392 signaling. An example of elimination is NAK elimination in a 393 reliable multicast protocol. Elimination is a service which 394 requires little computational overhead. It does however, require 395 per-packet (or per-sequence-block) state. This state can be con- 396 trolled by the use of short soft state timers. 398 Subcasting: Subcasting is the forwarding of a multicast packet to 399 a subset of the multicast tree. Subcasting is useful for a 400 variety of multicast protocols. Subcasting does not require a 401 large amount of processing. The state required is an identifier 402 for the subtree and a list of outgoing interfaces. This state is 403 similar to multicast forwarding tree state. 405 3. Canonical Services and Functional Models/Examples 407 While a variety of mechanisms must come together to enable a specific 408 GRA service in a distribution tree (session path messages to estab- 409 lish session parameters and neighbour information, a control protocol 410 to define, enable, and disable specific filtering services, etc.), 411 the basic mechanism of GRA consists of router based services that can 412 be described in the language of filters, keys, and conditional func- 413 tions (binary predicates and their outcomes). 415 Using the example of reliable multicast presented in Figure 1., this 416 section expands the model and terminology of filters to describe the 417 full flexibility of GRA. The intent here is to generalize the 418 mechanism fully enough to be able to accommodate currently unspeci- 419 fied requirements for multicast transport services as they emerge. 421 Revisiting the example in Figure 1., note that the receipt of a loss 422 report at a router implies several things. The packet type implies 423 that a type of filter should be established for the transport ses- 424 sion, that the filter key is (a sequence number) of a particular 425 length at a particular offset, that the loss report in hand should be 426 forwarded, that the interface upon which the loss report was received 427 should be recorded and associated with the key in the filter, and 428 that subsequent matching loss reports on any interface should be 429 eliminated. The filter itself has other implied characteristics. It 430 eliminates only for a certain interval after forwarding any subse- 431 quent loss report, and it has an implied lifetime after which it is 432 locally expired by the router. 434 Similarly in the case of sub-casting, the receipt of a retransmis- 435 sion at a router implies several things. The packet type implies 436 that the packet should be matched against an existing filter type 437 based on a key of a particular length and at a particular offset, 438 that the packet itself should be forwarded on all interfaces for 439 which a loss report associated with the key was recorded, and that 440 the key's state should be discarded. By implication, unmatched 441 retransmissions should not be forwarded. 443 From this example some generalities emerge which, once they are 444 extricated from their specific semantics, can be re-assembled in a 445 variety of useful ways to provide router-based assistance for a 446 broader class of transport services. 448 3.1. General Model 450 The general model is one in which packets carry one of a tightly con- 451 strained set of signals that alert the router to apply a pre-defined 452 filtering service. 454 The packet-borne signal conveys 456 a filter type, 457 an associated action, 458 a key, 459 and possible packet operands. 461 The filter type specifies a particular router-based service. The 462 associated action specifies a particular function to carry out in the 463 context of the service. The key and any packet operands specify 464 values upon which to operate in the context of the action. 466 Canonical filtering services in routers can be defined by 468 a filter type, 469 associated supported actions, 470 predicated on specific conditions, 471 and three functions gated on that predicate whether TRUE or FALSE: 473 f(p): how to dispose of the packet, 474 f(s): how to transform the key's state, and 475 f(v): how to transform the outgoing interface (OIF) list 476 associated with the key. 478 All of these as well as the offsets and lengths of the key and any 479 packet operands for each supported action constitute the definition 480 of the filtering service. 482 3.2. An Example of Elimination and Subcasting for ARQ 484 Given this model, the handling of retransmissions in PGM can be 485 described as a predicate eliminating and subcasting filter. 487 Let IIF be the interface on which a packet is received. Let RETX 488 denote whether a packet retransmission has been requested either in a 489 loss report (RQST RETX), as interface state (OIF RETX), or as key 490 state (KEY RETX). Let ET be the elimination timer for a particular 491 key's state, and LT be the life timer for a particular key's state. 493 The filtering service in the router supports two actions, one inbound 494 (RCVR_UPDATE) and one outbound (FORWARD). 496 3.2.1. RCVR_UPDATE 498 For RCVR_UPDATE, in addition to a transport session identifier, the 499 following are defined for the signal in the packet: 501 ELIM_SUBC is the filter type 502 RCVR_UPDATE is the action 503 SQN is the key 504 RETX is a packet-borne operand 505 (value of one in the PGM example) 507 For RCVR_UPDATE, the following are defined for the filtering service 508 in the router: 510 In case the key fails to match existing key state: 512 predicate: NOOP 513 f(v): OIF RETX = 1 for IIF 514 f(s): start ET, start LT, KEY RETX = RQST RETX 515 f(p): reverse forward to upstream neighbour 517 In case the key matches existing key state: 519 predicate: NOOP 520 f(v): OIF RETX = 1 for IIF 521 f(s): restart LT 522 f(p): discard 524 3.2.2. FORWARD 526 For FORWARD, in addition to a transport session identifier, the fol- 527 lowing are defined for the signal in the packet: 529 ELIM_SUBC is the filter type 530 FORWARD is the action 531 SQN is the key 533 For FORWARD, the following are defined for the filtering service in 534 the router: 536 In case the key fails to match existing key state: 538 predicate: NOOP 539 f(v): NOOP 540 f(s): NOOP 541 f(p): discard 543 In case the key matches existing key state: 545 predicate: for all OIF RETXs, OIF RETX NE 0 547 In case the predicate is TRUE: 549 f(v): decrement OIF RETX 550 f(s): NOOP 551 f(p): forward on OIF 553 In case the predicate is FALSE: 555 f(v): NOOP 556 f(s): NOOP 557 f(p): discard 559 Associated with the filtering service would be an additional house- 560 keeping function which would discard a key's state if either LT 561 expired or all the OIF COUNTs were zero. 563 The point of this and subsequent examples is to demonstrate that this 564 model for GRA can accommodate a highly functional set of router-based 565 services which, given a transport-layer- independent implementation, 566 could be provided by routers for general deployment by transport pro- 567 tocols engineered to signal the routers in a generic way. We now 568 present a refinement of the PGM example adding forward error correc- 569 tion. 571 3.3. An Example of Elimination and Subcasting with FEC 573 In this example, a packet operand is used to carry a count of parity 574 packets requested with the additional implication that the interface 575 upon which the loss report was received along with the count of par- 576 ity packets requested should be recorded and associated with the key 577 in the filter, and that subsequent matching loss reports on any 578 interface should be eliminated unless they request a larger number of 579 parity packets than has been requested on any interface. 581 Similarly upon forwarding parity packets implies that the packet 582 itself should be forwarded on all interfaces with non-zero counts 583 recorded as state associated with the key, that the corresponding 584 count should be decremented by 1 per interface until it reaches 0, 585 and that the key's state should be discarded once all counts are 586 zero. 588 The handling of parity NAKs and parity retransmissions in PGM can be 589 described as a predicate eliminating and subcasting filter augmented 590 by a packet operand, the number of parity packets requested. 592 Let IIF be the interface on which a packet is received. Let COUNT be 593 the number of parity packets requested and recorded either in the 594 loss report (RQST COUNT), as interface state (OIF COUNT), or as key 595 state (HIGH COUNT). Let ET be the elimination timer for a particular 596 key's state, and LT be the life timer for a particular key's state. 598 The filtering service in the router supports two actions, one inbound 599 (RCVR_UPDATE) and one outbound (FORWARD). 601 3.3.1. RCVR_UPDATE 603 For RCVR_UPDATE, in addition to a transport session identifier, the 604 following are defined for the signal in the packet: 606 ELIM_SUBC is the filter type 607 RCVR_UPDATE is the action 608 SQN is the key 609 COUNT is a packet-borne operand 611 For RCVR_UPDATE, the following are defined for the filtering service 612 in the router: 614 In case the key fails to match existing key state: 616 predicate: NOOP 617 f(v): OIF COUNT for IIF = MAX(RQST COUNT, 0) 618 f(s): start ET, start LT, HIGH COUNT = RQST COUNT 619 f(p): reverse forward to upstream neighbour 621 In case the key matches existing key state: 623 predicate: ET is running or RQST COUNT LEQ HIGH COUNT 625 In case the predicate is TRUE: 627 f(v): OIF COUNT for IIF = MAX(RQST COUNT, OIF COUNT for IIF) 628 f(s): restart LT 629 f(p): discard 631 In case the predicate is FALSE: 633 f(v): OIF COUNT for IIF = MAX(RQST COUNT, OIF COUNT for IIF) 634 f(s): restart ET, HIGH COUNT = RQST COUNT 635 f(p): reverse forward to upstream neighbour 637 3.3.2. FORWARD 639 For FORWARD, in addition to a transport session identifier, the fol- 640 lowing are defined for the signal in the packet: 642 ELIM_SUBC is the filter type 643 FORWARD is the action 644 SQN is the key 646 For FORWARD, the following are defined for the filtering service in 647 the router: 649 In case the key fails to match existing key state: 651 predicate: NOOP 652 f(v): NOOP 653 f(s): NOOP 654 f(p): discard 656 In case the key matches existing key state: 658 predicate: for all OIF COUNTs, OIF COUNT NE 0 660 In case the predicate is TRUE: 662 f(v): decrement OIF COUNT 663 f(s): NOOP 664 f(p): forward on OIF 666 In case the predicate is FALSE: 668 f(v): NOOP 669 f(s): NOOP 670 f(p): discard 672 Associated with the filtering service would be an additional house- 673 keeping function which would discard a key's state if either LT 674 expired or all the OIF COUNTs were zero. 676 3.4. An Example of a Surrogate Service for Subcasting 678 The "turning point functionality" in LMS [LSM] cited above can be 679 conceived of as enlisting the help of a willing surrogate to provide 680 funtionality that may not supported natively in the network but may 681 be supported by distinguished servers at the edge of the network 682 (such as retransmitters). 684 This example describes how surrogates can be supported in GRA. A 685 router first establishes state that enables a surrogate. This state 686 is maintained per TSI and consists of the network-layer unicast 687 address of the surrogate, the surrogate interface, and the surrogate 688 current cost. The state is established after receiving advertise- 689 ments from surrogates. It is assumed that surrogates send such adver- 690 tisements periodically. The router selects the surrogate that adver- 691 tises the lowest cost. 693 When a packet arrives requesting a service provided by the surrogate, 694 the router forwards the packet as follows: if the packet came from 695 the surrogate interface or no surrogate is known, it is forwarded 696 upstream. Otherwise, the packet is unicast to a known surrogate 697 after recording the address of the incoming interface and the address 698 of the surrogate interface in the GRA header. 700 Finally, the surrogate unicasts a response packet to the router to be 701 multicast on the interface on which the original request arrived. 703 For each transport session, let SURR_ADDR be the network layer uni- 704 cast address of the surrogate (initially NULL), let SURR_IF be the 705 surrogate interface (initially NULL), and let SURR_COST be the cost 706 of the current surrogate interface (initially infinity). Let IIF be 707 the interface on which a packet is received. 709 The filtering service in the router supports three actions: 710 SURR_UPDATE. FWD_TP, and FWD_OIF. 712 SURR_UPDATE is the surrogate election action, FWD_TP is the turning 713 point locator service, and FWD_OIF is the subcast service. 715 Note that a packet using the service FWD_TP does not carry the turn- 716 ing point Information (i.e the PKT_IIF and PKT_OIF are NULL). 718 3.4.1. 720 For SURR_UPDATE, the following are defined for the signal in the 721 packet: 723 SURROGATE is the filter type 724 SURR_UPDATE is the action 725 ADDR is a packet-borne operand 726 COST is a packet-borne operand 728 For SURR_UPDATE, the following are defined for the filtering service 729 at the router: 731 predicate: COST < SURR_COST 732 In case the predicate is true: 734 f(v): NOOP 735 f(s): SURR_ADDR = ADDR, SURR_IF = IIF, SURR_COST = COST 736 f(p): reverse forward to upstream neighbor 738 In case the predicate is false: 740 f(v): NOOP 741 f(s): NOOP 742 f(p): discard 744 3.4.2. 746 For FWD_TP, the following are defined for the signal in the packet. 748 SURROGATE is the filter type 749 FWD_TP is the action 750 PKT_IIF, PKT_OIF are packet_borne variables 752 For FWD_TP, the following are defined for the filtering service at 753 the router: 755 predicate: ((SIF != NULL) && (IIF != SIF)) 757 In case the predicate is TRUE 759 f(v): NOOP 760 f(s): NOOP 761 f(p): PKT_IIF = IIF and PKT_OIF = Surrogate IF 762 (i.e Insert the Turning Point information) 763 Unicast to SURR_ADDR 765 In case the predicate is FALSE 767 f(v): NOOP 768 f(s): NOOP 769 f(p): Unicast to upstream GRA neighbour 771 3.4.3. 773 For FWD_OIF the following are defined for the signal in the packet: 775 SURROGATE is the filter type 776 FWD_OIF is the action 777 PKT_OIF is a packet-borne operand 779 For FWD_OIF, the following are defined for the filtering service at 780 the router: 782 predicate: for all interfaces in PKT_OIF list: 783 f(v): NOOP 784 f(s): NOOP 785 f(p): Multicast the packet on PKT_OIF 786 to the S,G associated with the TSI 788 3.5. Summary 790 The point of these examples is to demonstrate that this model for GRA 791 can accommodate a highly functional set of router-based services 792 which, given a transport-layer-independent implementation, could be 793 provided by routers for general deployment by transport protocols 794 engineered to signal the routers in a generic way. Now that we have 795 established the context and a model for GRA, the next section 796 discusses implementation considerations in the interest of making the 797 mechanisms of GRA more concrete, and highlighting their practical and 798 performance consequences to traditional multicast forwarding. 800 4. Implementation Considerations 802 4.1. Signalling Protocol - GRA service indicators 804 A consideration of the implementation issues attending GRA strongly 805 determines the class of functions that may be realized with this 806 mechanism. These considerations relate to both security of the 807 router and performance in the forwarding path. The former will be 808 dealt with in another section. This section outlines the time and 809 space scaling consequences of GRA to the forwarding path. 811 To be a generic network layer service, it's clear that some minimal 812 indicator is required in the network layer to signal the presence of 813 GRA signal on a packet. As has been previously noted, remember that 814 the GRA indicator is typically NOT borne by basic data packets. 815 These are switched without exception in the usual forwarding path. 816 In this section, packets bearing a GRA indicator will be referred to 817 as GRA packets. 819 A network layer indicator frees forwarding engines from the burden of 820 having to walk into and parse transport headers on every switched 821 packet. It's highly efficient to encode the GRA indicator on the 822 network layer header since that header is typically already within 823 the grasp of the forwarding engine. In PGM, this indicator is imple- 824 mented with an IP Router Alert option, but a single bit in the basic 825 IP header would function just as well (even better, actually, for 826 legacy routers). 828 Once GRA packets can be detected in the forwarding path, the next 829 step is to locate and parse the GRA parameters: the filter type, the 830 action, the key, and the operands from above. These should be 831 encoded as TLVs located somewhere between the end of the network 832 layer header and the beginning of the transport layer payload or SDU. 834 It's tempting in the case of the key and the packet operands to con- 835 sider encoding their offsets and lengths in a TLV that could be used 836 to locate the actual values themselves in the transport header or, 837 more wildly, in the SDU, but this would amount to providing a near 838 programmatic directive to the network element which is fraught with 839 risk. So note that, in the example of elimination above, the number 840 of loss reports requested would, in this model, be encoded both in 841 its natural place in the transport header, and also as a GRA-specific 842 operand in a separate GRA TLV. 844 An alternative is to establish the location and length of keys and 845 packet operands as attributes of the filtering service defined in the 846 network element itself so that the only vulnerability to the network 847 elements would derive from abuse of the setup protocol in the control 848 plane in place of vulnerability in the forwarding path or data plane. 850 The location of GRA TLVs before, inside, or after the transport layer 851 header is at the crux of whether GRA is regarded as integral to a 852 specific layer or as a shim layer between layers. The answer to the 853 question determines not just where to locate the TLVs but also where 854 to implement the service in host protocol stacks. 856 As for forwarding-time implementation of GRA services, we take it as 857 a requirement for this specification that some services must be 858 light-weight enough to be candidates for optimized implementations in 859 hardware or firmware, while others may be sufficiently complex to 860 warrant software implementations. Soft-state-based services that do 861 not maintain per-packet state may be in the first class; services 862 that maintain per-packet state and therefor require a 863 sorted/searchable data structure may be in the second class. 865 Beyond these very GRA-specific issues are the more general control 866 protocol issues of how to interoperate network elements with 867 disparate GRA capabilities, and all of the specifics of defining, 868 enabling, and disabling filters themselves. These issues are best 869 treated once a solid model of the GRA mechanism itself is esta- 870 blished. 872 4.2. Control Protocol - Filter definition, enabling, and disabling 873 4.3. Control Protocol - Session path messages and neighbour informa- 874 tion 875 Abbreviations 877 IIF Incoming Interface 878 NAK Negative Acknowledgement 879 NOOP No Operation 880 OIF Outgoing Interface 881 SDU Service Data Unit 882 SQN Sequence Number 883 TLV Type Length Value 884 References 886 [ACTIVE] L.H. Lehman, S.J. Garland, D. L. Tennenhouse. "Active Reli- 887 able Multicast", Proc. INFOCOM'98, 1998. 889 [BFS] Koichi Yano, Steven McCanne, "The Breadcrumb Forwarding Service 890 and the Digital Fountain Rainbow: Toward a TCP-Friendly Reliable Mul- 891 ticast", UCB/CSD Technical Report No. UCB//CSD-99-1068 893 [GMTS] Brad Cain, Don Towsley, "Generic Multicast Transport Services 894 (GMTS)", Nortel Networks Technical Report, December 1998. 896 [KKT] S. Kasera, J. Kurose, D. Towsley. "A Comparison of Server-Based 897 and Receiver-Based Local Recovery Approaches for Scalable Reliable 898 Multicast", Proc. INFOCOM'98, 1998. 900 [LABEL] B.N. Levine, J.J. Garcia-Luna-Aceves. "Improving Internet 901 Multicast with Routing Labels", Proc. ICNP-97, pp. 241-250, Oct. 902 1997. 904 [LSM] C. Papadopoulos, G. Parulkar. "An Error Control Scheme for 905 Large-Scale Multicast Applications", Proc. INFOCOM'98. 907 [PGM] T. Speakman, D. Farinacci, S. Lin, A. Tweedly. "PGM Reliable 908 Transport Protocol", IETF draft-speakman-pgm-spec-03.txt, June, 1999. 910 [RMTP] J. Lin, S. Paul. "RMTP: A reliable multicast transport proto- 911 col", Proc. of IEEE INFOCOM'95, 1995. 913 [SRM] S. Floyd, V. Jacobson, S. McCanne, C. Lin, L. Zhang. "A Reli- 914 able Multicast Framework for Light-weight Sessions and Application 915 Level Framing", IEEE/ACM Trans on Networking, vol. 5, 784-803, Dec. 916 1997. 918 [TKP] D. Towsley, J. Kurose, S. Pingali. "A comparison of sender- 919 initiated and receiver-initiated reliable multicast protocols" IEEE 920 JSAC, April 1997. 922 Revision History 924 draft-ietf-rmt-gra-00.txt October 1999 926 Original draft. 928 draft-ietf-rmt-gra-01.txt March 2000 930 Added the example of simple elmination and subcasting. 932 draft-ietf-rmt-gra-02.txt July 2001 934 Replaced references to "suppression" and "aggregation" with 935 "elimination". 936 Replaced references to "aggregate" with "accumulate". 937 Changed "should" to "must" in principle #1. 938 Added the surrogate example. 940 Authors' Addresses 942 Brad Cain 943 bcain@cereva.com 945 Tony Speakman 946 speakman@cisco.com 948 Don Towsley 949 towsley@cs.umass.edu