idnits 2.17.00 (12 Aug 2021) /tmp/idnits7526/draft-lu-fn-transport-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (July 11, 2011) is 3967 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Outdated reference: A later version (-03) exists of draft-csaszar-ipfrr-fn-00 Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group W. Lu 3 Internet-Draft S. Kini 4 Intended status: Standards Track A. Csaszar, Ed. 5 Expires: January 12, 2012 G. Enyedi 6 J. Tantsura 7 Ericsson 8 July 11, 2011 10 Transport of Fast Notification Messages 11 draft-lu-fn-transport-02 13 Abstract 15 This document specifies a fast, light-weight event notification 16 protocol, called Fast Notification (FN) protocol. The draft 17 discusses the design goals, the message container and options for 18 delivering the notifications to all routers within a routing area. 20 Status of this Memo 22 This Internet-Draft is submitted in full conformance with the 23 provisions of BCP 78 and BCP 79. 25 Internet-Drafts are working documents of the Internet Engineering 26 Task Force (IETF). Note that other groups may also distribute 27 working documents as Internet-Drafts. The list of current Internet- 28 Drafts is at http://datatracker.ietf.org/drafts/current/. 30 Internet-Drafts are draft documents valid for a maximum of six months 31 and may be updated, replaced, or obsoleted by other documents at any 32 time. It is inappropriate to use Internet-Drafts as reference 33 material or to cite them other than as "work in progress." 35 This Internet-Draft will expire on January 12, 2012. 37 Copyright Notice 39 Copyright (c) 2011 IETF Trust and the persons identified as the 40 document authors. All rights reserved. 42 This document is subject to BCP 78 and the IETF Trust's Legal 43 Provisions Relating to IETF Documents 44 (http://trustee.ietf.org/license-info) in effect on the date of 45 publication of this document. Please review these documents 46 carefully, as they describe your rights and restrictions with respect 47 to this document. Code Components extracted from this document must 48 include Simplified BSD License text as described in Section 4.e of 49 the Trust Legal Provisions and are provided without warranty as 50 described in the Simplified BSD License. 52 Table of Contents 54 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 55 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3 56 1.2. Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . 3 57 2. Design Goals . . . . . . . . . . . . . . . . . . . . . . . . . 4 58 3. Transport Logic - Distribution of the Notifications . . . . . 4 59 3.1. Duplicate Check . . . . . . . . . . . . . . . . . . . . . 5 60 4. Message Encoding . . . . . . . . . . . . . . . . . . . . . . . 6 61 4.1. Seamless Encapsulation . . . . . . . . . . . . . . . . . . 6 62 4.2. Dedicated FN Message . . . . . . . . . . . . . . . . . . . 6 63 4.2.1. Authentication . . . . . . . . . . . . . . . . . . . . 8 64 4.2.1.1. Areas-scoped and Link-scoped Authentication . . . 9 65 4.2.1.2. Simple Password Authentication . . . . . . . . . . 9 66 4.2.1.3. Cryptographic Authentication for FN . . . . . . . 9 67 4.2.1.4. MD5 . . . . . . . . . . . . . . . . . . . . . . . 10 68 4.2.1.5. SHA256 . . . . . . . . . . . . . . . . . . . . . . 11 69 4.2.1.6. Digital Signatures . . . . . . . . . . . . . . . . 12 70 5. Security Considerations . . . . . . . . . . . . . . . . . . . 12 71 6. FN Packet Processing Summary . . . . . . . . . . . . . . . . . 12 72 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13 73 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 13 74 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13 75 9.1. Normative References . . . . . . . . . . . . . . . . . . . 13 76 9.2. Informative References . . . . . . . . . . . . . . . . . . 14 77 Appendix A. Further Options for Transport Logic . . . . . . . . . 14 78 A.1. Multicast Tree-based Transport . . . . . . . . . . . . . . 14 79 A.1.1. Fault Tolerance of a Single Distribution Tree . . . . 15 80 A.1.2. Pair of Redundant Trees . . . . . . . . . . . . . . . 15 81 A.2. Unicast . . . . . . . . . . . . . . . . . . . . . . . . . 17 82 A.2.1. Method . . . . . . . . . . . . . . . . . . . . . . . . 17 83 A.2.2. Sample Operation . . . . . . . . . . . . . . . . . . . 18 84 A.3. Gated Multicast through RPF Check . . . . . . . . . . . . 18 85 A.3.1. Loop Prevention - RPF Check . . . . . . . . . . . . . 19 86 A.3.2. Operation . . . . . . . . . . . . . . . . . . . . . . 19 87 A.4. Further Multicast Tree based Transport Options . . . . . . 20 88 A.4.1. Source Specific Trees . . . . . . . . . . . . . . . . 20 89 A.4.2. A Single Bidirectional Shared Tree . . . . . . . . . . 21 90 A.5. Layer 2 Networks . . . . . . . . . . . . . . . . . . . . . 21 91 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22 93 1. Introduction 95 Draft [I-D.lu-fast-notification-framework] describes the 96 architectural framework to enable fast dissemination of a network 97 event to routers in a limited area. Existing use cases involve new 98 approaches for IP Fast ReRoute such as [I-D.csaszar-ipfrr-fn], and 99 faster dissemination of link state information for routing protocols 100 [I-D.kini-ospf-fast-notification] in order to speed up convergence. 102 A hop by hop control plane based flooding mechanism is used widely 103 today in link state routing protocols such as OSPF and ISIS to 104 propagate routing information throughout an area. In this mechanism, 105 the information is processed in the control plane at each hop before 106 being forwarded to the next. The extra processing, scheduling, and 107 communications overhead causes unnecessary delays in the 108 dissemination of the information. 110 This draft proposes a generic fast notification (FN) protocol as a 111 separate transport layer, which focuses on delivering notifications 112 quickly in a secure manner. It can be used by many existing 113 applications to enhance the performance of those applications, as 114 well as to enable new services in the network. 116 1.1. Requirements Language 118 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 119 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 120 document are to be interpreted as described in RFC 2119 [RFC2119]. 122 1.2. Acronyms 124 FN - Fast Notification 126 IGP - Interior Gateway Protocol 128 IS-IS - Intermediate System to Intermediate System 130 MD5 - Message Digest 5 132 OSPF - Open Shortest Path First 134 RPF - Reverse Path Forwarding 136 SHA - Secure Hash 137 SPT - Shortest Path Tree 139 STP - Spanning Tree Protocol 141 2. Design Goals 143 A light-weight event notification mechanism that could be used to 144 facilitate quick dissemination of information in a limited area 145 should have the following properties. 147 1. The mechanism should be fast. It should provide low end to end 148 propagation delay for the notifications. 150 2. The signaling mechanism should offer a high degree of reliability 151 under network failure conditions. 153 3. The mechanism should be secure; that is, it should provide means 154 to verify the authenticity of the notifications. 156 4. The new protocol should not be dependent upon routing protocol 157 flooding procedures. 159 5. The mechanism should have low processing overhead 161 These design goals present a trade-off. Proper balance needs to be 162 found that offers good authentication and reliability while keeping 163 processing complexity sufficiently low to enable implementation in 164 dataplane. This draft proposes solutions that take the above goals 165 and trade-offs into considerations. 167 3. Transport Logic - Distribution of the Notifications 169 The distribution of a notification to multiple receivers can be 170 implemented in many ways. The main body of this draft describes one 171 such option, a flooding-like approach. 173 In flooding mode, the IGP configures the dataplane cards to replicate 174 each received FN message to each interface with a neighbour router in 175 the same area. 177 This happens by making use of bidirectional multicast forwarding. In 178 bidir multicast, all interfaces added to the multicast group can be 179 incoming and outgoing interfaces as well. The principle is that a 180 router replicates the incoming packet to *all* assigned interfaces 181 except the incoming interface. If the local router is the source of 182 the packet to be forwarded, then the packet is replicated to all 183 interfaces. That is, the decision about which interfaces should 184 actually be used as outgoing is determined on demand. 186 First, the FN service is assigned a multicast group address, let us 187 call this MC-FN address. Then, the IGP assigns all interfaces to 188 MC-FN which lead to neighbouring routers. 190 When the FN service is instructed to disseminate a message, it 191 creates an IP packet (as described below in Section 4) and sets its 192 IP destination address to the MC-FN multicast address. This IP 193 packet is then multicasted to all IGP neighbours in the area. 195 Recipients of FN multicast-forward the packet according to the rules 196 of bidirectional multicast, i.e. to all interfaces which the local 197 IGP pre-configured except the incoming interface. As this may cause 198 loops without pre-caution (consider three routers in a triangle). 199 Before forwarding, therefore, the forwarding engine has to perform 200 duplicate check. 202 3.1. Duplicate Check 204 Duplicate check can be performed in numeruous ways. 206 Duplicate check can be performed by maintaining a short queue of 207 previously forwarded FN messages. Before forwarding, if the FN 208 message is found in the queue, then it was forwarded beforehand, so 209 it may be dropped. Otherwise it should be forwarded and it should be 210 added to the queue. 212 Alternatively, the queue may contain a signature of the previously 213 forwarded FN messages, such as an MD5 or SHA256 signature or any 214 other hash. This signature may be carried in the packet, e.g. due to 215 authentication purposes, such as with the authentication mechanisms 216 described in Section 4.2.1. 218 In either of the above queue-based mechanisms, the size of the queue 219 can be set to a value that corresponds to the maximal number of legal 220 FN messages generated by a single event. For instance, if FN is used 221 to broadcast failure identifiers in case of failures, then it is 222 likely that the failure of the node with the most neighbours will 223 trigger the most FN messages (1 from each neighbour). 225 It is also possible to use application-dependent duplicate check: the 226 state machine of the FN-application can be left responsible to decide 227 whether the information carried in the packet contains new 228 information or it is a duplicate. This is only useful in the case if 229 the application can perform the duplicate check faster then the above 230 generic mechanisms. 232 4. Message Encoding 234 4.1. Seamless Encapsulation 236 An application may define its own message for FN to distribute 237 quickly. In this case, only the special destination address (e.g. 238 MC-FN) shows that the message was sent using the FN service. 240 In this case, the entire payload of the IP packet is determined by 241 the application including sequence numbering and authentication. The 242 IP packet's protocol field can also be set by the application. 244 4.2. Dedicated FN Message 246 An alternative option is for the FN messages to be distributed in UDP 247 datagrams with well-known port values in the UDP header that need to 248 be allocated by IANA. 250 The FN packet format inside a UDP datagram is the following: 252 0 1 2 3 253 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 254 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 255 | | 256 +- -+ 257 | IP Header | 258 +- +-------------+ -+ 259 | | Protocol=UDP| | 260 +- +-------------+ -+ 261 | | 262 +- -+ 263 | | 264 +---------------------------------------------------------------+ 265 | UDP Source Port = FN | UDP Destination Port = FN | 266 +---------------------------------------------------------------+ 267 | UDP Header cont'd | 268 +---------------------------------------------------------------+ 269 | FN Header | 270 +---------------------------------------------------------------+ 271 | ... | 272 . . 273 . FN Payload . 274 . . 275 | ... | 276 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 277 | ... | 278 . . 279 . Authentication (optional) . 280 . . 281 | ... | 282 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 284 Figure 1: FN packet format as a UDP datagram 286 The encoding of the FN Header is as follows: 288 0 1 2 3 289 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 290 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 291 | FN Length | FN App Type | AuType|unused | 292 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 294 Figure 2: FN Header encoding 296 FN Length (16 bits) 297 The length of the FN message in bytes including the FN Header and 298 the FN Payload. The authentication data optionally appended to 299 the FN packet is not considered part of the FN message: the 300 authentication data is not included in the FN Length field, 301 although it is included in the length field of the packet's IP 302 header. 304 FN App Type (8 bits) 305 Identifies the application which should be the receiver of the 306 notification. A value for each application needs to be assigned 307 by IANA. 309 AuType 310 Identifies the authentication procedure to be used for the packet. 311 Authentication options are discussed in Section 4.2.1 of the 312 specification. 314 4.2.1. Authentication 316 Fast Notification intends to provide a trustable service option, so 317 that receivers of FN packets are able to verify that the packet is 318 sent by an authentic source. Simple password authentication and hash 319 based authentication methods (with Md5 or SHA256) are described in 320 the following subsections. 322 If AuType is set to 0x0, then the FN packet is not carrying an 323 Authentication field at the end of the packet. If AuType is zero, 324 AuLength must also be zero. Note that even in this case the FN 325 application in the payload may still use its own authentication 326 mechanism. 328 If AuType is non null, an Authentication field must be appended after 329 the FN message. The encoding of this field is as described below. 331 0 1 2 3 332 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 333 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 334 | AuLength | ... Authentication Data ... | 335 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 336 | ... | 338 Figure 3: Authentication field in FN packets 340 AuLength 341 Describes the length of the entire Authentication field in bytes. 343 4.2.1.1. Areas-scoped and Link-scoped Authentication 345 Since FN is a solution to disseminate an event notification from one 346 source to a whole area of nodes, the simplest approach would be to 347 use per-area authentication, for example. a common password, a common 348 pre- shared key among all nodes in the area as described in the 349 following sub-sections, or digital signatures. 351 Carriers may, however, prefer per-link authentication. In order not 352 to lose the speed (simple per-hop processing, fast forwarding 353 property) of FN, link-scoped authentication is suggested only if the 354 forwarding plane supports it, i.e. if there is hardware support to 355 verify and re-generate authentication hop-by-hop. In such cases, the 356 operator may need to configure a common pre-shared key only on 357 routers connected by the same link. It is even possible that there 358 is no authentication on some links considered safe. 360 4.2.1.2. Simple Password Authentication 362 Simple password authentication guards against routers inadvertently 363 joining the routing area; each router must first be configured with a 364 password before it can participate in Fast Notification. 366 The password is stored in the Authentication Data field. AuLength is 367 set to the length of the password in bytes plus 1. Two AuType values 368 for simple password authentication need to be allocated by IANA: one 369 for area-scope and another for link-scoped. 371 With per-link authentication mode, the Authentication field must be 372 stripped and regenerated hop-by-hop. 374 Simple password authentication, however, can be easily compromised as 375 anyone with physical access to the network can read the password. 377 4.2.1.3. Cryptographic Authentication for FN 379 Using this authentication type, a secret key is used to generate/ 380 verify a "message digest" that is appended to the end of the FN 381 packet. The message digest is a one-way function of the FN packet 382 and the secret key. This authentication mechanism resembles the 383 cryptographic authentication mechanism of [RFC2328]. 385 4.2.1.4. MD5 387 The packet signature is created by an MD5 hash performed on an object 388 which is the concatenation of the FN message, including the FN 389 header, and the pre-shared secret key. The resulting 16 byte MD5 390 message digest is appended to the FN message into the Authentication 391 field as shown below. 393 The AuType in the FN header is set to indicate cryptographic 394 authentication, the specific value is to be assigned by IANA both for 395 area-scoped and for link-scoped versions. 397 0 1 2 3 398 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 399 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 400 | AuLength | Key ID | Unused | 401 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 402 | Message Digest (bytes 1-4) | 403 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 404 | Message Digest (bytes 5-8) | 405 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 406 | Message Digest (bytes 9-12) | 407 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 408 | Message Digest (bytes 13-16) | 409 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 411 Figure 4: Authentication field in FN packets with MD5 cryptographic 412 authentication. 414 AuLength 415 AuLength is set to 20 bytes. 417 Key ID 418 This field identifies the algorithm and secret key used to create 419 the message digest appended to the FN packet. This field allows 420 that multiple pre-shared keys may exist in parallel. 422 Message Digest 423 The 16 byte long MD5 hash performed on an object which is the 424 concatenation of the FN message, including the FN header, and the 425 pre-shared secret key identified by Key ID. 427 When receiving an FN message, if the FN header indicates MD5 428 authentication, then the last 20 bytes of the FN message are set 429 aside. The recipient forwarding plane element calculates a new MD5 430 digest of the remainder of the FN message to which it appends its own 431 known secret key identified by Key ID. The calculated and received 432 digests are compared. In case of mismatch, the FN message is 433 discarded. 435 In per-link authentication mode, the Authentication field must be 436 regenerated hop-by-hop using the key of the outgoing link. 438 4.2.1.5. SHA256 440 Similarly to how MD5 authentication works, it is possible to use 441 Secure Hash 256 hash. Currently this is a more secure hash function 442 than MD5. The Authentication field would look like this: 444 0 1 2 3 445 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 446 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 447 | AuLength | Key ID | Unused | 448 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 449 | Message Digest (bytes 1-4) | 450 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 451 | Message Digest (bytes 5-8) | 452 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 453 | . . . | 454 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 455 | Message Digest (bytes 25-28) | 456 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 457 | Message Digest (bytes 29-32) | 458 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 460 Figure 5: Authentication field in FN packets with MD5 cryptographic 461 authentication. 463 AuLength 464 AuLength is set to 36 bytes. 466 Key ID 467 This field identifies the algorithm and secret key used to create 468 the message digest appended to the FN packet. This field allows 469 that multiple pre-shared keys may exist in parallel. 471 Message Digest 472 The 32 bytes long SHA256 value calculated on an object which is 473 the concatenation of the FN message, including the FN header, and 474 the pre-shared secret key identified by Key ID. 476 When receiving an FN message, if the FN header indicates SHA256 477 authentication, then the last 68 bytes of the FN message are set 478 aside. The recipient forwarding plane element calculates a new 479 SHA256 digest of the remainder of the FN message to which it appends 480 its own known secret key identified by Key ID. The calculated and 481 received digests are compared. In case of mismatch, the FN message 482 is discarded. 484 In per-link authentication mode, the Authentication field must be 485 regenerated hop-by-hop using the key of the outgoing link. 487 4.2.1.6. Digital Signatures 489 A router may choose to use public key cryptography to digitally sign 490 the notification to provide certification of authenticity. This 491 mechanism can avoid shared secret that is required for other 492 authentication mechanisms described in this document. This 493 authentication mechanism resembles the authentication mechanism of 494 OSPF with digital signatures as defined in [RFC2154]. 496 5. Security Considerations 498 This draft has described basic optional procedures for 499 authentication. The mechanism, however, does not protect against 500 replay attacks. 502 If an application of FN require protection against replay attacks, 503 then these applications should provide their own specific sequence 504 numbering within the FN payload. Recipient applications should 505 accept FN messages only if the included sequence number is valid. 507 Since the message digest of cryptographic authentication also covers 508 the payload, even if an attacker knew how to construct the new 509 sequence number, it would not be able to generate a correct message 510 digest without the pre shared key. This way, a sequence number in 511 the payload combined with FN's cryptographic authentication offers 512 sufficient protection against replay attacks. 514 6. FN Packet Processing Summary 516 When receiving an FN packet, a node has to perform the following 517 steps. 519 It has to identify that the packet is an FN packet. This can be done 520 utilising the destination IP address (MC-FN) or by inspecting the UDP 521 port field. 523 If the flooding like transport logic described in Section 3 is used 524 the node has to perform duplicate check following the teachings in 525 Section 3.1. 527 If AuType is non-null, the node has to perform authentication check 528 as discussed in Section 4.2.1. 530 To protect against replay attacks, the node shall perform 531 verification of the sequence number provided by the application. 533 Punt and forward. The notification may need to be multicasted but it 534 also needs to be punted to the local application on the linecard to 535 start processing. 537 Authentication check, sequence number check and punting/forwarding 538 may commence in any order deemed necessary by the operator. If the 539 operator prefers highest level of security, then both checks should 540 be performed before forwarding. If, however, the operator prefers 541 per-hop performance but still wants to ensure that malice packets 542 cannot harm the network, then authentication and sequence number 543 checks may also happen after punting the packet, i.e. before 544 processing the information contained inside the FN payload. In this 545 case, malicious packets may get propagated to every node but they 546 still do not cause any change in the configuration. 548 7. IANA Considerations 550 A UDP port value needs to be assigned by IANA for FN. IANA also 551 needs to maintain values for FN App Type as applications are being 552 proposed. 554 Multicast addresses used for the distribution trees are either 555 allocated by IANA or they can be a configuration parameter within the 556 local domain. 558 8. Acknowledgements 560 The authors owe thanks to Acee Lindem, Joel Halpern and Jakob Heitz 561 for their review and comments. Also thanks to Alia Atlas for 562 constructive feedback. 564 9. References 566 9.1. Normative References 568 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 569 Requirement Levels", BCP 14, RFC 2119, March 1997. 571 [RFC5015] Handley, M., Kouvelas, I., Speakman, T., and L. Vicisano, 572 "Bidirectional Protocol Independent Multicast (BIDIR- 573 PIM)", RFC 5015, October 2007. 575 9.2. Informative References 577 [Eny2009] Enyedi, G., Retvari, G., and A. Csaszar, "On Finding 578 Maximally Redundant Trees in Strictly Linear Time, IEEE 579 Symposium on Computers and Communications (ISCC)", 2009. 581 [I-D.csaszar-ipfrr-fn] 582 Kini, S., Csaszar, A., and G. Envedi, "IP Fast Re-Route 583 with Fast Notification", draft-csaszar-ipfrr-fn-00 (work 584 in progress), March 2011. 586 [I-D.kini-ospf-fast-notification] 587 Kini, S., Lu, W., and A. Tian, "OSPF Fast Notification", 588 draft-kini-ospf-fast-notification-01 (work in progress), 589 March 2011. 591 [I-D.lu-fast-notification-framework] 592 Lu, W., Tian, A., and S. Kini, "Fast Notification 593 Framework", draft-lu-fast-notification-framework-00 (work 594 in progress), October 2010. 596 [RFC2154] Murphy, S., Badger, M., and B. Wellington, "OSPF with 597 Digital Signatures", RFC 2154, June 1997. 599 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. 601 Appendix A. Further Options for Transport Logic 603 The options described in this appendix represent alternative 604 solutions to the flooding based approach described in Section 605 Section 3. 607 It is left for WG discussion and further evaluation to decide whether 608 any of these options should potentially be preferred instead of 609 redundant trees. 611 A.1. Multicast Tree-based Transport 613 One way of transporting an identical piece of information to several 614 receivers at the same time is to use multicast distribution trees. A 615 tree based transport solution is beneficial since multicast support 616 is already implemented in all forwarding entities, so it is possible 617 to use existing implementations. 619 With multicast or tree based transport, the Fast Notification (FN) 620 packet can be recognized by a pre-configured or well known 621 destination IP address, denoted by MC-FN in the following, which is 622 the group address of the FN service. 624 If the FN service is triggered to send out a notification, the 625 notification will be encapsulated in a new IP packet, where the 626 destination IP address is set to MC-FN. 628 A.1.1. Fault Tolerance of a Single Distribution Tree 630 Several solutions described in this draft use a single tree to 631 disseminate a notification from one given source. 633 The single tree solution is simple, however it is not redundant: a 634 single failure may partition the tree, which will prevent 635 notifications from reaching some nodes in the area. 637 Different applications may have different needs for reliability. For 638 example, when we use fast notification to disseminate network failure 639 information, all nodes surrounding the failure can detect and 640 originate the failure notifications independently. Any one of these 641 notifications (or a subset of them) may be sufficient for the 642 application to make the right decision. This draft provides several 643 different transport options from which an applications can choose. 645 A.1.2. Pair of Redundant Trees 647 If an FN application needs the exact same data to be distributed in 648 the case of any single node or any single link failure, the FN 649 service could opt to run in "redundant tree mode". 651 A pair of "redundant trees" ensures that at each single node or link 652 failure each node still reaches the common root of the trees through 653 at least one of the trees. A redundant tree pair is a known prior- 654 art graph-theoretical object that is possible to find on any 2-node 655 connected network. Even better, it is even possible to find 656 maximally redundant trees in networks where the 2-node connected 657 criterion does not "fully" hold (e.g. there are a few cut vertices) 658 [Eny2009]. 660 Note that the referenced algorithm(s) build a pair of trees 661 considering a specific root. The root can be selected in different 662 ways, the only thing that is important that each node makes the same 663 selection, consistently. For instance, the node with the highest or 664 lowest router ID can be used. 666 #1 tree #2 tree 667 +---+ +---+ +---+ +---+ 668 | B |=======| | | B |=======| | 669 +---+ +---+ +---+ +---+ 670 // \\ // \ 671 // \\ // \ 672 +---+ +---+ +---+ +---+ 673 | A |---------------------| R | | A |=====================| R | 674 +---+ +---+ +---+ +---+ 675 \ // \\ / 676 \ // \\ / 677 +---+ +---+ +---+ +---+ 678 | |=======| | | |=======| | 679 +---+ +---+ +---+ +---+ 681 Figure 6: Example: a pair of redundant trees (double lines) of a 682 common root R 684 There is one special constraint in building the redundant trees. A 685 (maximally) redundant tree pair is needed, where in one of the trees 686 the root has only one child in order to protect against the failure 687 of the root itself. Algorithms presented in [Eny2009] produce such 688 trees. 690 In redundant-tree mode, each node multicasts the requested 691 notification on both trees, if it is possible, but at least along one 692 of the trees. Redundant trees require two multicast group addresses. 693 MC-FN identifies one of the trees, and MC-FN-2 identifies the other 694 tree. 696 Each node multicast forwards the received notification packet (on the 697 same tree). The root node performs as every other node but in 698 addition it also multicast the notification on the other tree! I.e. 699 it forwards a replica of the incoming notification in which it 700 replaces the destination address identifying the other multicast 701 distribution tree. 703 When the network remains connected and the root remains operable 704 after a single failure, the root will be reached on at least one of 705 the trees. Thus, since the root can reach every node along at least 706 one of the trees, all the notifications will reach each node. 707 However, when the root or the link to the root fails, that tree, in 708 which the root has only one child, remains connected (the root is a 709 leaf there), thus, all the nodes can be reached along that tree. 711 For example, let us consider that in Figure 6 FN is used to 712 disseminate failure information. If link A-B fails, the 713 notifications originating from node B (e.g. reporting that the 714 connectivity from B to A is lost) will reach R on tree #1. 715 Notifications originating from A (e.g. reporting that the 716 connectivity from A to B is lost) will reach R on tree #2. From R, 717 each node is reachable through one of the trees, so each node will be 718 notified about both events. 720 A.2. Unicast 722 This method addresses the need in a unique way. It has the following 723 properties: 725 Plain simple, without the need of any forwarding plane change or 726 cooperation; 728 Short turnaround time (i.e. ready for next hit); 730 100% link break coverage (may not work in certain node failure 731 cases); 733 Little change to OSPF (need encapsulation for IS-IS). 735 A.2.1. Method 737 The method is simple in design, easy to implement and quick to 738 deploy. It requires no topology changes or specific configurations. 739 It adds little overhead to the overall system. 741 The method sends the event message to every router in the area in an 742 IP packet. This appears burdensome to the sending router which has 743 to duplicate the packet sending effort many times. Practical 744 experience has shown, however, that the amount of effort is not a big 745 concern in reasonable sized networks. 747 Normal flooding (regular or fast) process requires a router to 748 duplicate the packet to all flooding eligible interfaces. All 749 routers have to be fast-flooding-aware. This implies new code to 750 every router in control plane and/or forwarding plane. 752 The method uses a different approach. It takes advantage of the 753 given routing/forwarding table in each router in the IP domain. The 754 originating router of the flooding information simply sends multiple 755 copies of the packet to each and every router in the domain. These 756 packets are forwarded to the destination routers at forwarding plane 757 speed, 759 just like the way the regular IP data traffic is handled. No special 760 handling in any other routers is needed. 762 This small delay on the sender can be minimized by pre-downloading 763 the link-broken message packets to the forwarding plane. Since the 764 forwarding plane already has the list of all routers which are part 765 of the IGP routing table, the forwarding plane can dispatch the 766 packet directly. 768 In essence, the flooding in this method is tree based, just like a 769 multicast tree. The key is that no special tree is generated for 770 this purpose; the normal routing table which is an SPF tree (SPT) 771 plays a role of the flooding tree. This logic guarantees that the 772 flooding follows the shortest path and no flooding loop is created. 774 A.2.2. Sample Operation 776 Figure 7 depicts a scenario where router A wants to flood its message 777 to all other routers in the domain using the unicast flooding method. 779 Instead of sending one packet to each of its neighbor, and letting 780 the neighbor flood the packet further, router A directly send the 781 same packet to each router in the domain, one at a time. In this 782 sample network, router A sends out 5 packets. 784 A---B---C---D 785 \ 786 --E---F 788 1. Packet(A->B); 789 2. Packet(A->C); 790 3. Packet(A->D); 791 4. Packet(A->E); 792 5. Packet(A->F). 794 Figure 7: Multiple Unicast Packets 796 The unicast flooding procedure is solely controlled by the sending 797 router. No action is needed from other routers other than their 798 normal forwarding functionalities. This method is extremely simple 799 and useful for quick prototyping and deployment. 801 A.3. Gated Multicast through RPF Check 803 This method fulfills the purpose with the following characters: 805 1. No need to build the multicast tree. It is the same as the SPT 806 computed by the IGP routing process; 808 2. Flooding loops are prevented by RPF Check. 810 The method has all the benefits of multicast flooding. It, however, 811 does not require running multicast protocol to setup the multicast 812 tree. The unicast shortest path tree is used as a multicast tree. 814 A.3.1. Loop Prevention - RPF Check 816 In this mechanism, the distribution tree is not explicitly built. 817 Rather, each node will first do a Reverse Path Forwarding (RPF) check 818 before it floods the notification to other links. 820 A special multicast address is defined and is subject to IANA 821 approval. This address is used to qualify the notification packet 822 for fast flooding. When a notification packet arrives, the receiving 823 node will perform an IP unicast routing table lookup for the 824 originator IP address of the notification and find the outgoing 825 interface. Only when the arriving interface of the notification is 826 the same as the outgoing interface leading towards the originator IP 827 address, will the notification be flooded to other interfaces. 829 IP Multicast forwarding with RPF check is available on most of the 830 routing/switching platforms. To support flooding with RPF check, a 831 special IP multicast group must be used. A bi-directional IP 832 multicast forwarding entry is created that consists of all interfaces 833 within the flooding scope, typically an IGP area. 835 A.3.2. Operation 837 The Gated flooding operation is illustrated in Figure 8. 839 All Routers, IGP Process: 840 if (SPT ready) { 841 duplicate the SPT as Bidir_Multicast_tree; 842 download the multicast_tree to forwarding plane; 843 } 844 add FNF_multicast_group_addr; 846 Sender of the FNF notification: 847 if (breakage detected) { 848 pack the notification in a packet; 849 send the packet to the FNF_multicast_group_addr; 850 } 852 Receiver of the FNF notification: 853 if (notification received) { 854 if (RPC_interface == incoming_interface) { 855 multicast the notification to all other interfaces; 856 } 857 forward the notification to IGP for processing; 858 } 860 Figure 8: Gated flooding operation 862 Figure 9 shows a sample operation on a four-router mesh network. The 863 left figure is the topology. The right figure is the shortest path 864 tree rooted at A. 866 Router A initiates the flooding. But the downstream routers B, C, 867 and D will drop all messages except the ones that come from their 868 shortest path parent node. For example, A's message to C via B is 869 dropped by C, because C knows that its reverse path forwarding (RPF) 870 nexthop is A. 872 A A 873 /|\ / \ 874 B---C B C 875 \|/ \ 876 D D 878 Figure 9: Loop Prevention through the RPF check 880 A.4. Further Multicast Tree based Transport Options 882 A.4.1. Source Specific Trees 884 One implementation option is to rely on source specific multicast. 885 This means that even though there is only a single multicast group 886 address (MC-FN) allocated to the FN service, the FIB of each router 887 is configured with forwarding information for as many trees as many 888 FN sources (nodes) there are in the routing area, i.e. to each 889 (S_i,MC-FN) pair. 891 A.4.2. A Single Bidirectional Shared Tree 893 In the previous solution each source specific tree is a spanning 894 tree. It is possible to reduce the complexity of managing and 895 configuring n spanning trees in the area by using bidirectional 896 shared trees. By building a bidirectional shared tree, all nodes on 897 the tree can send and receive traffic using that single tree. Each 898 sent packet from any source is multicasted on the tree to all other 899 receivers. 901 The tree must be consistently computed at all routers. For this, the 902 following rules may be given: 904 The tree can be computed as a shortest path tree rooted at e.g. the 905 highest router-id. When multiple paths are available, the 906 neighbouring node in the graph e.g. with highest router-id can be 907 picked. When multiple paths are available through multiple 908 interfaces to a neighbouring node, e.g. a numbered interface may be 909 preferred over an unnumbered interface. A higher IP address may be 910 preferred among numbered interfaces and a higher ifIndex may be 911 preferred among unnumbered interfaces. 913 Note, however, that the important point is that the rules are 914 consistent among nodes. That is, a router may pick the lower router 915 IDs if it is ensured that ALL routers will do the same to ensure 916 consistency. 918 Multicast forwarding state is installed using such a tree as a bi- 919 directional tree. Each router on the tree can send packets to all 920 other routers on that tree. 922 Note that the multicast spanning tree can be built using [RFC5015] so 923 that each router within an area subscribes to the same multicast 924 group address. Using BIDIR-PIM in such a way will eventually build a 925 multicast spanning tree among all routers within the area. (BIDIR- 926 PIM is normally used to build a shared, bidirectional multicast tree 927 among multiple sources and receivers.) 929 A.5. Layer 2 Networks 931 Layer 2 (e.g. Ethernet) networks offer further options for 932 distributing the notification (e.g. using spanning trees offered by 933 STP). Definition of these is being considered and will be included 934 in a future revision of this draft. 936 Authors' Addresses 938 Wenhu Lu 939 Ericsson 940 300 Holger Way 941 San Jose, California 95134 942 USA 944 Email: Wenhu.Lu@ericsson.com 946 Sriganesh Kini 947 Ericsson 948 300 Holger Way 949 San Jose, California 95134 950 USA 952 Email: Sriganesh.Kini@ericsson.com 954 Andras Csaszar (editor) 955 Ericsson 956 Irinyi J utca 4-10 957 Budapest 1117 958 Hungary 960 Email: Andras.Csaszar@ericsson.com 962 Gabor Sandor Enyedi 963 Ericsson 964 Irinyi J utca 4-10 965 Budapest 1117 966 Hungary 968 Email: Gabor.Sandor.Enyedi@ericsson.com 969 Jeff Tantsura 970 Ericsson 971 300 Holger Way 972 San Jose, California 95134 973 USA 975 Email: Jeff.Tantsura@ericsson.com