idnits 2.17.1 draft-ietf-rmt-gra-arch-01.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: ---------------------------------------------------------------------------- == Line 142 has weird spacing: '... filter is se...' -- 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 (March 2000) is 8800 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 792, 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 (~~), 4 warnings (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 RMT Working Group Generic Router Assist (GRA) Brad Cain 2 INTERNET-DRAFT for Multicast Transport Protocols Nortel 3 Tony Speakman 4 Expires September 2000 cisco 5 Don Towsley 6 UMASS 8 March 2000 10 Generic Router Assist (GRA) Building Block 11 Motivation and Architecture 12 14 Status of this Memo 16 This document is an Internet-Draft and is in full conformance with 17 all provisions of Section 10 of RFC2026. 19 Internet-Drafts are working documents of the Internet Engineering 20 Task Force (IETF), its areas, and its working groups. Note that 21 other groups may also distribute working documents as Internet- 22 Drafts. 24 Internet-Drafts are draft documents valid for a maximum of six months 25 and may be updated, replaced, or obsoleted by other documents at any 26 time. It is inappropriate to use Internet- Drafts as reference 27 material or to cite them other than as "work in progress." 29 The list of current Internet-Drafts can be accessed at 30 http://www.ietf.org/ietf/1id-abstracts.txt 32 The list of Internet-Draft Shadow Directories can be accessed at 33 http://www.ietf.org/shadow.html. 35 Abstract 37 Generic Router Assist (GRA) is a network-based service that enables 38 end-to-end multicast transport protocols to take advantage of infor- 39 mation distributed across the network elements in a given multicast 40 distribution tree. The service consists of a canonical set of simple 41 functions which network elements may apply to selected packets in the 42 transport session as they traverse the distribution tree. The choice 43 of function and the packet parameters to which it is applied can be 44 defined and customized for a given transport session in a highly con- 45 trolled fashion that still permits enough flexibility for GRA to be 46 used to address a wide range of multicast transport problems not 47 amenable to end-to-end solution. This document provides the motiva- 48 tion and an architecture for GRA. 50 Table of Contents 52 1. Introduction ............................................... 4 53 2. Scope of Generic Router Assist ............................. 6 54 3. Canonical Services and Functional Models/Examples .......... 11 55 4. Implementation Considerations .............................. 17 56 Abbreviations .................................................. 19 57 References ..................................................... 20 58 Revision History ............................................... 21 59 Authors' Addresses ............................................. 21 60 1. Introduction 62 The development of scalable end-to-end multicast protocols poses a 63 tremendous challenge to network protocol designers. For example the 64 development of reliable multicast protocols has received considerable 65 attention in recent years. Most protocols are based on an end-to-end 66 solution [SRM, RMTP, TKP] and have found the problem of scaling to 67 1000s or even 100s of receivers daunting. The primary obstacles to 68 the development of scalable protocols have been "feedback implosion" 69 and "transmission isolation". The first of these concerns the diffi- 70 culty of a large multicast application to limit feedback from 71 receivers to a data source or to each other. The second concerns the 72 difficulty of limiting the transmission of data to the subset of a 73 multicast group that requires it. 75 Several proposals have been made to add functionality to routers for 76 the purpose of improving the performance of multicast applications, 77 particularly reliable multicast. Papadopoulos and Parulkar [LSM] 78 introduced additional forwarding functionality to a router which 79 would allow each router to identify a ``special outgoing interface'' 80 over which to transmit a particular class of packets. They showed how 81 this ``turning point functionality'' could be used to improve the 82 performance of reliable multicast protocols. Levine and Garcia-Luna- 83 Aceves [LABEL] proposed the addition of ``routing labels'' to routing 84 tables which could be used to direct packets over specific inter- 85 faces. One of these, called a distance label, was shown to be quite 86 useful in reliable multicast for directing requests for repairs to 87 nearby repair servers. The third and, perhaps most relevant proposal 88 is the PGM protocol [PGM]. Briefly, PGM is a reliable multicast pro- 89 tocol which uses negative acknowledgements (NAKs). The PGM protocol 90 is an end-to-end transport protocol that contains a router component 91 which performs NAK suppression and retransmission subcasting func- 92 tionality. This proposal, like others [GMTS, BFS], is primarily 93 motivated by PGM and the recognition of the benefits of exporting a 94 set of flexible, simple router-based functionality for the purpose of 95 multicast protocol design. Such functionality can significantly sim- 96 plify the design of a large class of scalable multicast transport 97 protocols. 99 In this draft, we present Generic Router Assist (GRA) functionality 100 intended to help protocol designers deal with the two problems of 101 feedback implosion and transmission isolation. This functionality is 102 designed to assist in the scaling of receiver feedback information 103 and in providing subcasting for large multicast groups. It consists 104 of simple filtering and aggregation functions that reside within 105 routers. 107 Signaling protocols are used by hosts to set up and invoke this 108 functionality. 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 aggregate feedback from 111 receivers and/or isolate transmissions through the use of filters set 112 by either the sender or the receivers. For robustness, periodic 113 transmissions of setup messages on the multicast tree are used to 114 refresh GRA state in the face of routing changes and other possible 115 errors. It should be stressed that GRA services are only invoked for 116 certain packets; data packets are usually not treated any differently 117 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'' 122 services. Transport protocols which make use of GRA must be robust 123 in 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 (partially) solve these two problems. Prior to the transfer of any 141 data, the application sets up a NAK aggregation filter at each GRA- 142 capable router using a setup message. This filter is set up to 143 suppress NAKs generated for the same packet. In addition, the router 144 maintains information regarding the interfaces over which it has 145 received NAKs so that it can subcast the retransmission on the por- 146 tion of the multicast tree that contains receivers requiring a 147 retransmission of the packet. 149 In Figure 1, we show how GRA can be used to aggregate 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 invoke GRA to send the NAKs to the source. Router R2 treats these 158 NAKs in a special manner, removing the redundant NAKs to the source. 159 Therefore, only one NAK arrives at the source. We see from this exam- 160 ple that only certain types of packets require additional processing 161 at GRA routers and that the majority of end-to-end packets are for- 162 warded according to normal multicast forwarding rules (i.e. without 163 additional router processing). 165 Src 1 166 ^ | | 167 | | | data packet 168 | | | 169 R1 | 170 ^ | | 171 | | V 172 R2 suppresses | | 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 We conclude the introduction by commenting on the relationship of GRA 187 to the multicast routing algorithm. GRA works on all types of multi- 188 cast forwarding trees. However, GRA state is per session state and 189 requires per session state in routers. If a source-based tree routing 190 protocol is used to forward multicast packets, then this per session 191 state will already exist in routers in the form of multicast forward- 192 ing entries. If a shared tree type multicast routing protocol is 193 being used, then GRA per session state must be maintained on the 194 shared tree. This is simply because GRA provides per session func- 195 tionality. 197 2. Scope of Generic Router Assist 199 The types of services implemented with GRA are bounded by constraints 200 and limitations of routing devices. In this section we explicitly 201 describe the limitations and constraints of routing devices and 202 explain what we believe to be reasonable services to implement in 203 routers. 205 We specifically describe router limitations in order to limit the 206 scope of GRA. We believe that a small set of GRA services in routers 207 can assist in scaling many of the problems in end-to-end multicast. 208 Previous proposals[ACTIVE] have proposed complex elements that reside 209 in routers to provide sophisticated capabilities. We feel that these 210 are unreasonable for current generation routers. The approach of GRA 211 is to provide a simple fixed set of services which give the maximum 212 benefit with the least cost. 214 2.1. Service Properties 216 GRA services are performed on subset of packets sent between end-to- 217 end transport protocols on the multicast distribution tree between a 218 GRA Source and the set of GRA receivers. Only routers on the distri- 219 bution tree for a particular GRA source act upon GRA packets. The 220 advantages of GRA type services can only be realized when the actions 221 are performed on packets that are directly on the forwarding tree of 222 a multicast group. 224 In order to describe the requirements of GRA, we first describe the 225 properties of what we feel are appropriate services. 227 Fixed: by fixed services we mean those of which are statically 228 part of router software or hardware. We DO NOT mean dynamically 229 loadable modules. We feel that a fixed set of simple services 230 will suffice for most of the scaling issues in transport proto- 231 cols. 233 Simple: We wish only to include those services that we feel are 234 reasonable to be implemented in routers. These are services which 235 can be performed with minimum CPU and memory overhead. 237 Short Term: We wish to provide services for which state and pro- 238 cessing overhead is short lived. GRA makes use of soft-state 239 design principles. 241 2.2. GRA Requirements 243 When considering the service and architecture of GRA, we adhere to 244 the following principles: 246 1. GRA services should be simple and fixed. They should not 247 require excessive processing in routing devices nor should they 248 buffer messages. 250 2. GRA services are not substitutes for well-engineered end-to-end 251 protocol designs. We support the end-to-end design principles of 252 transport protocols. GRA is an "assist" service which is designed 253 to assist protocols in scaling aspects. 255 3. GRA services will not take on active networking attributes such 256 as dynamically uploadable modules or programming language propo- 257 sals. 259 4. GRA services should not directly participate in transport pro- 260 tocols. GRA should not be required for any transport protocols 261 nor should any GRA services directly support a particular proto- 262 col. 264 5. GRA services should be those which may assist all or a reason- 265 able subset of transport protocols. 267 6. GRA services should be used for assisting in *control* packet 268 operations. GRA services should not be for the majority of pack- 269 ets in a multicast group. 271 2.3. Constraints of networking devices 273 Current generation routers perform processing of packets and execute 274 routing and signaling protocols. Routers perform fast packet for- 275 warding on the "forwarding path". This is usually performed by 276 hardware and software specifically designed for the forwarding of 277 packets (and may include other functions such as policing, shaping, 278 etc). This is in contrast to the "control plane" of a router where 279 control protocols are run under an operating system. Examples of 280 these types of protocols are routing, management and signaling proto- 281 cols. 283 We now describe the role and impact of GRA services on these two 284 "planes" of a router. 286 Forwarding path: A router forwarding path usually consists of spe- 287 cialized hardware and software which is designed specifically for 288 the purpose of forwarding packets. Newer routers also have abili- 289 ties to perform other actions such as marking or policing for ser- 290 vices such as QoS. In general, the forwarding path of routers is 291 very limited in the amount of state and complexity of processing 292 that can be performed. Although we do not rule out GRA services 293 being implemented in the forwarding path of routers, we do not see 294 this as feasible at this point in time. This is because of the 295 more complicated processing rules for GRA packets (in comparison 296 with basic forwarding operations) and the amount of state that is 297 sometimes involved in performing GRA operations. 299 Control plane: Router control planes run embedded or general 300 operating systems. On top of these operating systems are imple- 301 mentations of IP control protocols such as routing, signaling, and 302 network management. The processing power and memory of a control 303 plane depends highly on the hardware design of the router. Most 304 routers use general purpose CISC or RISC processors for running 305 the control plane operating system and protocols. The control 306 plane is limited in processing by its hardware and the load gen- 307 erated from the other processes or tasks running. We expect that 308 most GRA operations will be performed in the control plane where 309 state and processing power are more readily available. However, 310 we do stress that routers generally have fairly slow control plane 311 hardware. This is to keep the cost low and because the processing 312 required for control plane protocols is usually low. 314 2.4. State Constraints 316 As we evaluate particular services which are candidates for inclusion 317 in GRA, constraints in router state are an important consideration. 318 We wish to select services which will not create substantial or 319 long-lived state. 321 2.4.1. Session State 323 Routers which perform multicast forwarding contain per tree forward- 324 ing state. For trees rooted at multicast sources, this amounts to 325 per source per group forwarding entries. This state must be kept in 326 both the forwarding as well as the control plane. GRA services are 327 per session, or per source. This is simply because GRA services are 328 per transport session. 330 The session state of GRA does not impose much additional state to 331 routers. Each session requires a state block describing the desired 332 services. Other types of state may also be created during the course 333 of a GRA session. The GRA session state is the only state required 334 for the length of a session; other state is set up and torn down in 335 smaller intervals. 337 2.4.2. Packet State 339 The implementation of particular services may require per packet 340 state in GRA routers. Services which require per packet state should 341 use short-lived timers to tear down this state so as to avoid an 342 explosion in the amount of state at routers. An example of a service 343 which causes per packet state is NAK elimination. We feel the use of 344 small timers will minimize problems in state growth. 346 2.4.3. Buffering 348 GRA services are not allowed to buffer packets. GRA services may 349 drop or modify packets in transit, but they will never buffer pack- 350 ets. 352 We feel that the buffering of packets in routing devices is unaccept- 353 able due to the unpredictable behavior of such a service. In addi- 354 tion we feel that this is an unreasonable service for routers to sup- 355 port without a significant payback in end-to-end scaling. 357 2.5. Processing Constraints 359 GRA services may require differing amount of computation. As a gen- 360 eral rule, GRA services should require minimal computation and packet 361 manipulation. 363 2.5.1. Computation 365 We expect most GRA services to require minimal computation. Services 366 which require minimal computation are reasonable to implement in 367 routing devices and minimize security risk. Examples of operations 368 which we feel are appropriate are: 370 Comparison Operations: comparison operations may be performed on 371 GRA packets against the GRA session state in the router in order 372 to determine whether a service should be invoked. Examples of 373 comparison operations are: equal to, less than, greater than, etc. 375 Update Operations: When receiving a GRA packet, a router may be 376 required to update its GRA session state. The operations required 377 for updating the state should remain simple. Example of simple 378 operations are addition, subtraction, etc. 380 In order to limit the computational complexity of GRA services, we 381 recommend that GRA operations remain singular. The combination of 382 predicates and operations creates problems in both router processing 383 and in GRA specifications themselves. We wish to avoid problems 384 regarding operator and action precedence. 386 2.5.2. Buffer Operations 388 One can define services requiring extensive packet manipulation by 389 GRA routers. We believe this to be expensive and therefore unreason- 390 able for routers. GRA services should be invoked without extensive 391 manipulation of packets. Services which update or overwrite fields 392 are acceptable. Services which require the formation of new packets 393 or aggregate information into new packets are unacceptable. 395 2.6. Examples of "Reasonable" Services 397 In this section we briefly describe two GRA services which we feel 398 are appropriate and why we feel they meet the above requirements. 399 The two example services are those that provide general functions 400 which do not incur large amounts of state or processing. 402 Elimination: Elimination is the selected dropping of redundant 403 signaling. An example of elimination is NAK suppression in a 404 reliable multicast protocol. Elimination is a service which 405 requires little computational overhead. It does however, require 406 per packet (or per sequence block) state. This state can be con- 407 trolled by the use of short soft state timers. 409 Subcasting: Subcasting is the forwarding of a multicast packet to 410 a subset of the multicast tree. Subcasting is useful for a 411 variety of multicast protocols. Subcasting does not require a 412 large amount of processing. The state required is an identifier 413 for the subtree and a list of outgoing interfaces. This state is 414 similar to multicast forwarding tree state. 416 3. Canonical Services and Functional Models/Examples 418 While a variety of mechanisms must come together to enable a specific 419 GRA service in a distribution tree (session path messages to estab- 420 lish session parameters and neighbour information, a control protocol 421 to define, enable, and disable specific filtering services, etc.), 422 the basic mechanism of GRA consists of router based services that can 423 be described in the language of filters, keys, and conditional func- 424 tions (binary predicates and their outcomes). 426 Using the example of reliable multicast presented earlier, this sec- 427 tion expands the model and terminology of filters to describe the 428 full flexibility of GRA. The intent here is to generalize the 429 mechanism fully enough to be able to accommodate currently unspeci- 430 fied requirements for multicast transport services as they emerge. 432 Revisiting the example of predicate elimination, note that the 433 receipt of a loss report at a router implies several things. The 434 packet type implies that a type of filter should be established for 435 the transport session, that the filter key is (a sequence number) of 436 a particular length at a particular offset, that the loss report in 437 hand should be forwarded, that the interface upon which the loss 438 report was received should be recorded and associated with the key in 439 the filter, and that subsequent matching loss reports on any inter- 440 face should be eliminated. The filter itself has other implied 441 characteristics. It eliminates only for a certain interval after 442 forwarding any subsequent loss report, and it has an implied lifetime 443 after which it is locally expired by the router. 445 Similarly in the example of sub-casting, the receipt of a retransmis- 446 sion at a router implies several things. The packet type implies 447 that the packet should be matched against an existing filter type 448 based on a key of a particular length and at a particular offset, 449 that the packet itself should be forwarded on all interfaces for 450 which a loss report was recorded associated with the key, and that 451 the key's state should be discarded. By implication, unmatched 452 retransmissions should not be forwarded. 454 From this example some generalities emerge which, once they are 455 extricated from their specific semantics, can be re-assembled in a 456 variety of useful ways to provide router-based assistance for a 457 broader class of transport services. 459 3.1. General Model 461 The general model is one in which packets carry one of a tightly con- 462 strained set of signals that alert the router to apply a pre-defined 463 filtering service. 465 The packet-borne signal conveys 467 a filter type, 468 an associated action, 469 a key, 470 and possible packet variables 472 Canonical filtering services in routers can be defined by 474 a filter type, 475 associated supported actions, 476 predicated on specific conditions, 477 and three functions gated on that predicate whether TRUE or FALSE: 479 f(p): how to dispose of the packet, 480 f(s): how to transform the key's state, and 481 f(v): how to transform the outgoing interface (OIF) list 482 associated with the key. 484 All of these as well as the offsets and lengths of the key and any 485 packet variables for each supported action constitute the definition 486 of the filtering service. 488 3.2. An Example Using the General Model 490 Given this model, the handling of retransmissions in PGM can be 491 described as a predicate eliminating and subcasting filter. 493 Let IIF be the interface on which a packet is received. Let RETX 494 denote whether a packet retransmission has been requested either in a 495 loss report (RQST RETX), as interface state (OIF RETX), or as key 496 state (KEY RETX). Let ET be the elimination timer for a particular 497 key's state, and LT be the life timer for a particular key's state. 499 The filtering service in the router supports two actions, one inbound 500 (RCVR_UPDATE) and one outbound (FORWARD). 502 3.2.1. RCVR_UPDATE 504 For RCVR_UPDATE, in addition to a transport session identifier, the 505 following are defined for the signal in the packet: 507 ELIM_SUBCis the filter type 508 RCVR_UPDATE is the action 509 SQNis the key 510 RETX is a packet-borne variable (value of one in the PGM example) 512 For RCVR_UPDATE, the following are defined for the filtering service 513 in the router: 515 In case the key fails to match existing key state: 517 predicate: NOOP 518 f(v):OIF RETX = 1 for IIF 519 f(s):start ET, start LT, KEY RETX = RQST RETX 520 f(p):reverse forward to upstream neighbour 522 In case the key matches existing key state: 524 f(v): OIF RETX = 1 for IIF 525 f(s): restart LT 526 f(p): discard 528 FORWARD 530 For FORWARD, in addition to a transport session identifier, the fol- 531 lowing are defined for the signal in the packet: 533 ELIM_SUBCis the filter type 534 FORWARD is the action 535 SQNis the key 537 For FORWARD, the following are defined for the filtering service in 538 the router: 540 In case the key fails to match existing key state: 542 predicate: NOOP 543 f(v):NOOP 544 f(s):NOOP 545 f(p):discard 547 In case the key matches existing key state: 549 predicate: for all OIF RETXs, OIF RETX NE 0 551 In case the predicate is TRUE: 553 f(v): decrement OIF RETX 554 f(s): NOOP 555 f(p): forward on OIF 557 In case the predicate is FALSE: 559 f(v): NOOP 560 f(s): NOOP 561 f(p): discard 563 Associated with the filtering service would be an additional house- 564 keeping function which would discard a key's state if either LT 565 expired or all the OIF COUNTs were zero. 567 The point of this and subsequent examples is to demonstrate that this 568 model for GRA can accommodate a highly functional set of router-based 569 services which, given a transport-layer- independent implementation, 570 could be provided by routers for general deployment by transport pro- 571 tocols engineered to signal the routers in a generic way. We now 572 present a refinement of the PGM example adding forward error correc- 573 tion. 575 In this example, a packet variable is used to carry a count of parity 576 packets requested with the additional implication that the interface 577 upon which the loss report was received along with the count of par- 578 ity packets requested should be recorded and associated with the key 579 in the filter, and that subsequent matching loss reports on any 580 interface should be eliminated unless they request a larger number of 581 parity packets than has been requested on any interface. 583 Similarly upon forwarding parity packets implies that the packet 584 itself should be forwarded on all interfaces with non-zero counts 585 recorded as state associated with the key, that the corresponding 586 count should be decremented by 1 per interface until it reaches 0, 587 and that the key's state should be discarded once all counts are 588 zero. 590 3.3. Another Example Using the General Model 592 The handling of parity NAKs and parity retransmissions in PGM can be 593 described as a predicate eliminating and subcasting filter this time 594 augmented by a packet variable, the number of parity packets 595 requested. 597 Let IIF be the interface on which a packet is received. Let COUNT be 598 the number of parity packets requested and recorded either in the 599 loss report (RQST COUNT), as interface state (OIF COUNT), or as key 600 state (HIGH COUNT). Let ET be the elimination timer for a particular 601 key's state, and LT be the life timer for a particular key's state. 603 The filtering service in the router supports two actions, one inbound 604 (RCVR_UPDATE) and one outbound (FORWARD). 606 3.3.1. RCVR_UPDATE 608 For RCVR_UPDATE, in addition to a transport session identifier, the 609 following are defined for the signal in the packet: 611 ELIM_SUBC is the filter type 612 RCVR_UPDATE is the action 613 SQN is the key 614 COUNT is a packet-borne variable 616 For RCVR_UPDATE, the following are defined for the filtering service 617 in the router: 619 In case the key fails to match existing key state: 621 predicate: NOOP 622 f(v): OIF COUNT for IIF = MAX(RQST COUNT, 0) 623 f(s): start ET, start LT, HIGH COUNT = RQST COUNT 624 f(p): reverse forward to upstream neighbour 626 In case the key matches existing key state: 628 predicate: ET is running or RQST COUNT LEQ HIGH COUNT 630 In case the predicate is TRUE: 632 f(v): OIF COUNT for IIF = MAX(RQST COUNT, OIF COUNT for IIF) 633 f(s): restart LT 634 f(p): discard 636 In case the predicate is FALSE: 638 f(v): OIF COUNT for IIF = MAX(RQST COUNT, OIF COUNT for IIF) 639 f(s): restart ET, HIGH COUNT = RQST COUNT 640 f(p): reverse forward to upstream neighbour 642 3.3.2. FORWARD 644 For FORWARD, in addition to a transport session identifier, the fol- 645 lowing are defined for the signal in the packet: 647 ELIM_SUBC is the filter type 648 FORWARD is the action 649 SQN is the key 651 For FORWARD, the following are defined for the filtering service in 652 the router: 654 In case the key fails to match existing key state: 656 predicate: NOOP 657 f(v): NOOP 658 f(s): NOOP 659 f(p): discard 661 In case the key matches existing key state: 663 predicate: for all OIF COUNTs, OIF COUNT NE 0 665 In case the predicate is TRUE: 667 f(v): decrement OIF COUNT 668 f(s): NOOP 669 f(p): forward on OIF 671 In case the predicate is FALSE: 673 f(v): NOOP 674 f(s): NOOP 675 f(p): discard 677 Associated with the filtering service would be an additional house- 678 keeping function which would discard a key's state if either LT 679 expired or all the OIF COUNTs were zero. 681 3.4. Summary 683 The point of this example (eventually, "these examples") is to 684 demonstrate that this model for GRA can accommodate a highly func- 685 tional set of router-based services which, given a transport-layer- 686 independent implementation, could be provided by routers for general 687 deployment by transport protocols engineered to signal the routers in 688 a generic way. Now that we have established the context and a model 689 for GRA, the next section discusses implementation considerations in 690 the interest of making the mechanisms of GRA more concrete, and 691 highlighting their practical and performance consequences to tradi- 692 tional multicast forwarding. 694 4. Implementation Considerations 696 4.1. Signalling Protocol - GRA service indicators 698 A consideration of the implementation issues attending GRA strongly 699 determines the class of functions that may be realized with this 700 mechanism. These considerations relate to both security of the 701 router and performance in the forwarding path. The former will be 702 dealt with in another section. This section outlines the time and 703 space scaling consequences of GRA to the forwarding path. 705 To be a generic network layer service, it's clear that some minimal 706 indicator is required in the network layer to signal the presence of 707 GRA signal on a packet. As has been previously noted, remember that 708 the GRA indicator is typically NOT borne by basic data packets. 709 These are switched without exception in the usual forwarding path. 710 In this section, packets bearing a GRA indicator will be referred to 711 as GRA packets. 713 A network layer indicator frees forwarding engines from the burden of 714 having to walk into and parse transport headers on every switched 715 packet. It's highly efficient to encode the GRA indicator on the 716 network layer header since that header is typically already within 717 the grasp of the forwarding engine. In PGM, this indicator is imple- 718 mented with an IP Router Alert option, but a single bit in the basic 719 IP header would function just as well (even better, actually, for 720 legacy routers). 722 Once GRA packets can be detected in the forwarding path, the next 723 step is to locate and parse the GRA parameters: the filter type, the 724 action, the key, and the variables from above. These should be 725 encoded as TLVs located somewhere between the end of the network 726 layer header and the beginning of the transport layer payload or SDU. 728 It's tempting in the case of the key and the packet variables to con- 729 sider encoding their offsets and lengths in a TLV that could be used 730 to locate the actual values themselves in the transport header or, 731 more wildly, in the SDU, but this would amount to providing a near 732 programmatic directive to the network element which is fraught with 733 risk. So note that, in the example of elimination above, the number 734 of loss reports requested would, in this model, be encoded both in 735 its natural place in the transport header, and also as a GRA-specific 736 variable in a separate GRA TLV. 738 An alternative is to establish the location and length of keys and 739 packet variables as attributes of the filtering service defined in 740 the network element itself so that the only vulnerability to the net- 741 work elements would derive from abuse of the setup protocol in the 742 control plane in place of vulnerability in the forwarding path or 743 data plane. 745 The location of GRA TLVs before, inside, or after the transport layer 746 header is at the crux of whether GRA is regarded as integral to a 747 specific layer or as a shim layer between layers. The answer to the 748 question determines not just where to locate the TLVs but also where 749 to implement the service in host protocol stacks. 751 As for forwarding-time implementation of GRA services, we take it as 752 a requirement for this specification that some services must be 753 light-weight enough to be candidates for optimized implementations in 754 hardware or firmware, while others may be sufficiently complex to 755 warrant software implementations. Soft-state-based services that do 756 not maintain per-packet state may be in the first class; services 757 that maintain per-packet state and therefor require a 758 sorted/searchable data structure may be in the second class. 760 Beyond these very GRA-specific issues are the more general control 761 protocol issues of how to interoperate network elements with 762 disparate GRA capabilities, and all of the specifics of defining, 763 enabling, and disabling filters themselves. These issues are best 764 treated once a solid model of the GRA mechanism itself is esta- 765 blished. 767 4.2. Control Protocol - Filter definition, enabling, and disabling 769 4.3. Control Protocol - Session path messages and neighbour informa- 770 tion 771 Abbreviations 773 IIF Incoming Interface 774 NAK Negative Acknowledgement 775 NOOP No Operation 776 OIF Outgoing Interface 777 SDU Service Data Unit 778 SQN Sequence Number 779 TLV Type Length Value 780 References 782 [ACTIVE] L.H. Lehman, S.J. Garland, D. L. Tennenhouse. ``Active Reli- 783 able Multicast'', Proc. INFOCOM'98, 1998. 785 [BFS] Koichi Yano, Steven McCanne, "The Breadcrumb Forwarding Service 786 and the Digital Fountain Rainbow: Toward a TCP-Friendly Reliable Mul- 787 ticast", UCB/CSD Technical Report No. UCB//CSD-99-1068 789 [GMTS] Brad Cain, Don Towsley, "Generic Multicast Transport Services 790 (GMTS)", Nortel Networks Technical Report, December 1998. 792 [KKT] S. Kasera, J. Kurose, D. Towsley. ``A Comparison of Server- 793 Based and Receiver-Based Local Recovery Approaches for Scalable Reli- 794 able Multicast'', Proc. INFOCOM'98, 1998. 796 [LABEL] B.N. Levine, J.J. Garcia-Luna-Aceves. ``Improving Internet 797 Multicast with Routing Labels'', Proc. ICNP-97, pp. 241-250, Oct. 798 1997. 800 [LSM] C. Papadopoulos, G. Parulkar. ``An Error Control Scheme for 801 Large-Scale Multicast Applications'', Proc. INFOCOM'98. 803 [PGM] T. Speakman, D. Farinacci, S. Lin, A. Tweedly. "PGM Reliable 804 Transport Protocol", IETF draft-speakman-pgm-spec-03.txt, June, 1999. 806 [RMTP] J. Lin, S. Paul. ``RMTP: A reliable multicast transport proto- 807 col'', Proc. of IEEE INFOCOM'95, 1995. 809 [SRM] S. Floyd, V. Jacobson, S. McCanne, C. Lin, L. Zhang. ``A Reli- 810 able Multicast Framework for Light-weight Sessions and Application 811 Level Framing'', IEEE/ACM Trans on Networking, vol. 5, 784-803, Dec. 812 1997. 814 [TKP] D. Towsley, J. Kurose, S. Pingali. ``A comparison of sender- 815 initiated and receiver-initiated reliable multicast protocols'' IEEE 816 JSAC, April 1997. 818 Revision History 820 draft-ietf-rmt-gra-00.txt October 1999 822 Original draft. 824 Authors' Addresses 826 Brad Cain 827 bcain@nortelnetworks.com 829 Tony Speakman 830 speakman@cisco.com 832 Don Towsley 833 towsley@cs.umass.edu