< draft-lu-fn-transport-01.txt		draft-lu-fn-transport-02.txt >
	Network Working Group W. Lu		Network Working Group W. Lu
	Internet-Draft S. Kini		Internet-Draft S. Kini
	Intended status: Standards Track A. Csaszar		Intended status: Standards Track A. Csaszar, Ed.
	Expires: September 15, 2011 G. Enyedi		Expires: January 12, 2012 G. Enyedi
	J. Tantsura		J. Tantsura
	A. Tian
	Ericsson		Ericsson
	March 14, 2011		July 11, 2011
	Transport of Fast Notification Messages		Transport of Fast Notification Messages
	draft-lu-fn-transport-01		draft-lu-fn-transport-02
	Abstract		Abstract
	This document specifies a fast, light-weight event notification		This document specifies a fast, light-weight event notification
	protocol, called Fast Notification (FN) protocol. The draft		protocol, called Fast Notification (FN) protocol. The draft
	discusses the design goals, the message container and options for		discusses the design goals, the message container and options for
	delivering the notifications to all routers within a routing		delivering the notifications to all routers within a routing area.
	area.
	Status of this Memo		Status of this Memo
	This Internet-Draft is submitted in full conformance with the		This Internet-Draft is submitted in full conformance with the
	provisions of BCP 78 and BCP 79.		provisions of BCP 78 and BCP 79.
	Internet-Drafts are working documents of the Internet Engineering		Internet-Drafts are working documents of the Internet Engineering
	Task Force (IETF). Note that other groups may also distribute		Task Force (IETF). Note that other groups may also distribute
	working documents as Internet-Drafts. The list of current Internet-		working documents as Internet-Drafts. The list of current Internet-
	Drafts is at http://datatracker.ietf.org/drafts/current/.		Drafts is at http://datatracker.ietf.org/drafts/current/.
	Internet-Drafts are draft documents valid for a maximum of six months		Internet-Drafts are draft documents valid for a maximum of six months
	and may be updated, replaced, or obsoleted by other documents at any		and may be updated, replaced, or obsoleted by other documents at any
	time. It is inappropriate to use Internet-Drafts as reference		time. It is inappropriate to use Internet-Drafts as reference
	material or to cite them other than as "work in progress."		material or to cite them other than as "work in progress."
	This Internet-Draft will expire on September 15, 2011.		This Internet-Draft will expire on January 12, 2012.
	Copyright Notice		Copyright Notice
	Copyright (c) 2011 IETF Trust and the persons identified as the		Copyright (c) 2011 IETF Trust and the persons identified as the
	document authors. All rights reserved.		document authors. All rights reserved.
	This document is subject to BCP 78 and the IETF Trust's Legal		This document is subject to BCP 78 and the IETF Trust's Legal
	Provisions Relating to IETF Documents		Provisions Relating to IETF Documents
	(http://trustee.ietf.org/license-info) in effect on the date of		(http://trustee.ietf.org/license-info) in effect on the date of
	publication of this document. Please review these documents		publication of this document. Please review these documents
	skipping to change at page 2, line 15 ¶		skipping to change at page 2, line 14 ¶
	the Trust Legal Provisions and are provided without warranty as		the Trust Legal Provisions and are provided without warranty as
	described in the Simplified BSD License.		described in the Simplified BSD License.
	Table of Contents		Table of Contents
	1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3		1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
	1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3		1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3
	1.2. Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . 3		1.2. Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . 3
	2. Design Goals . . . . . . . . . . . . . . . . . . . . . . . . . 4		2. Design Goals . . . . . . . . . . . . . . . . . . . . . . . . . 4
	3. Transport Logic - Distribution of the Notifications . . . . . 4		3. Transport Logic - Distribution of the Notifications . . . . . 4
	3.1. Multicast Tree-based Transport . . . . . . . . . . . . . . 4		3.1. Duplicate Check . . . . . . . . . . . . . . . . . . . . . 5
	3.1.1. Fault Tolerance of a Single Distribution Tree . . . . 5		4. Message Encoding . . . . . . . . . . . . . . . . . . . . . . . 6
	3.1.2. Pair of Redundant Trees . . . . . . . . . . . . . . . 5		4.1. Seamless Encapsulation . . . . . . . . . . . . . . . . . . 6
	4. Message Encoding . . . . . . . . . . . . . . . . . . . . . . . 7		4.2. Dedicated FN Message . . . . . . . . . . . . . . . . . . . 6
	4.1. Seamless Encapsulation . . . . . . . . . . . . . . . . . . 7		4.2.1. Authentication . . . . . . . . . . . . . . . . . . . . 8
	4.2. Dedicated FN Message . . . . . . . . . . . . . . . . . . . 7		4.2.1.1. Areas-scoped and Link-scoped Authentication . . . 9
	4.2.1. Authentication . . . . . . . . . . . . . . . . . . . . 9		4.2.1.2. Simple Password Authentication . . . . . . . . . . 9
	4.2.1.1. Areas-scoped and Link-scoped Authentication . . . 10		4.2.1.3. Cryptographic Authentication for FN . . . . . . . 9
	4.2.1.2. Simple Password Authentication . . . . . . . . . . 10		4.2.1.4. MD5 . . . . . . . . . . . . . . . . . . . . . . . 10
	4.2.1.3. Cryptographic Authentication for FN . . . . . . . 10		4.2.1.5. SHA256 . . . . . . . . . . . . . . . . . . . . . . 11
	4.2.1.4. MD5 . . . . . . . . . . . . . . . . . . . . . . . 11		4.2.1.6. Digital Signatures . . . . . . . . . . . . . . . . 12
	4.2.1.5. Digital Signatures . . . . . . . . . . . . . . . . 12		5. Security Considerations . . . . . . . . . . . . . . . . . . . 12
	5. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 12		6. FN Packet Processing Summary . . . . . . . . . . . . . . . . . 12
	6. Security Considerations . . . . . . . . . . . . . . . . . . . 12		7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13
	7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12		8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 13
	8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13		9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13
	8.1. Normative References . . . . . . . . . . . . . . . . . . . 13		9.1. Normative References . . . . . . . . . . . . . . . . . . . 13
	8.2. Informative References . . . . . . . . . . . . . . . . . . 13		9.2. Informative References . . . . . . . . . . . . . . . . . . 14
	Appendix A. Further Options for Transport Logic . . . . . . . . . 13		Appendix A. Further Options for Transport Logic . . . . . . . . . 14
	A.1. Unicast . . . . . . . . . . . . . . . . . . . . . . . . . 14		A.1. Multicast Tree-based Transport . . . . . . . . . . . . . . 14
	A.1.1. Method . . . . . . . . . . . . . . . . . . . . . . . . 14		A.1.1. Fault Tolerance of a Single Distribution Tree . . . . 15
	A.1.2. Sample Operation . . . . . . . . . . . . . . . . . . . 15		A.1.2. Pair of Redundant Trees . . . . . . . . . . . . . . . 15
	A.2. Gated Multicast through RPF Check . . . . . . . . . . . . 15		A.2. Unicast . . . . . . . . . . . . . . . . . . . . . . . . . 17
	A.2.1. Loop Prevention - RPF Check . . . . . . . . . . . . . 16		A.2.1. Method . . . . . . . . . . . . . . . . . . . . . . . . 17
	A.2.2. Operation . . . . . . . . . . . . . . . . . . . . . . 16		A.2.2. Sample Operation . . . . . . . . . . . . . . . . . . . 18
	A.3. Further Multicast Tree based Transport Options . . . . . . 18		A.3. Gated Multicast through RPF Check . . . . . . . . . . . . 18
	A.3.1. Source Specific Trees . . . . . . . . . . . . . . . . 18		A.3.1. Loop Prevention - RPF Check . . . . . . . . . . . . . 19
	A.3.2. A Single Bidirectional Shared Tree . . . . . . . . . . 18		A.3.2. Operation . . . . . . . . . . . . . . . . . . . . . . 19
	A.4. Layer 2 Networks . . . . . . . . . . . . . . . . . . . . . 19		A.4. Further Multicast Tree based Transport Options . . . . . . 20
	Appendix B. Computing maximally redundant trees . . . . . . . . . 19		A.4.1. Source Specific Trees . . . . . . . . . . . . . . . . 20
	B.1. Simple pair of maximally redundant trees in		A.4.2. A Single Bidirectional Shared Tree . . . . . . . . . . 21
	2-connected networks . . . . . . . . . . . . . . . . . . . 19		A.5. Layer 2 Networks . . . . . . . . . . . . . . . . . . . . . 21
	B.2. Non-2-connected networks . . . . . . . . . . . . . . . . . 21		Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22
	B.3. Finding maximally redundant trees in distributed
	environment . . . . . . . . . . . . . . . . . . . . . . . 22
	Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 23
	1. Introduction		1. Introduction
	Draft [fn-framework] describes the architectural framework to enable		Draft [I-D.lu-fast-notification-framework] describes the
	fast dissemination of a network event to routers in a limited area.		architectural framework to enable fast dissemination of a network
	Existing use cases involve new approaches for IP Fast ReRoute such as		event to routers in a limited area. Existing use cases involve new
	[ipfrr-fn], and faster dissemination of link state information for		approaches for IP Fast ReRoute such as [I-D.csaszar-ipfrr-fn], and
	routing protocols [ospf-fn] in order to speed up convergence.		faster dissemination of link state information for routing protocols
			[I-D.kini-ospf-fast-notification] in order to speed up convergence.
	A hop by hop control plane based flooding mechanism is used widely		A hop by hop control plane based flooding mechanism is used widely
	today in link state routing protocols such as OSPF and ISIS to		today in link state routing protocols such as OSPF and ISIS to
	propagate routing information throughout an area. In this mechanism,		propagate routing information throughout an area. In this mechanism,
	the information is processed in the control plane at each hop before		the information is processed in the control plane at each hop before
	being forwarded to the next. The extra processing, scheduling, and		being forwarded to the next. The extra processing, scheduling, and
	communications overhead causes unnecessary delays in the		communications overhead causes unnecessary delays in the
	dissemination of the information.		dissemination of the information.
	This draft proposes a generic fast notification (FN) protocol as a		This draft proposes a generic fast notification (FN) protocol as a
	skipping to change at page 3, line 37 ¶		skipping to change at page 3, line 38 ¶
	1.1. Requirements Language		1.1. Requirements Language
	The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",		The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
	"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this		"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
	document are to be interpreted as described in RFC 2119 [RFC2119].		document are to be interpreted as described in RFC 2119 [RFC2119].
	1.2. Acronyms		1.2. Acronyms
	FN - Fast Notification		FN - Fast Notification
	RPF - Reverse Path Forwarding
	IGP - Interior Gateway Protocol		IGP - Interior Gateway Protocol
	SPT - Shortest Path Tree		IS-IS - Intermediate System to Intermediate System
	STP - Spanning Tree Protocol		MD5 - Message Digest 5
	OSPF - Open Shortest Path First		OSPF - Open Shortest Path First
	IS-IS - Intermediate System to Intermediate System		RPF - Reverse Path Forwarding
	MD5 - Message Digest 5		SHA - Secure Hash
			SPT - Shortest Path Tree
			STP - Spanning Tree Protocol
	2. Design Goals		2. Design Goals
	A light-weight event notification mechanism that could be used to		A light-weight event notification mechanism that could be used to
	facilitate quick dissemination of information in a limited area		facilitate quick dissemination of information in a limited area
	should have the following properties.		should have the following properties.
	1. The mechanism should be fast. It should provide low end to end		1. The mechanism should be fast. It should provide low end to end
	propagation delay for the notifications.		propagation delay for the notifications.
	skipping to change at page 4, line 27 ¶		skipping to change at page 4, line 30 ¶
	3. The mechanism should be secure; that is, it should provide means		3. The mechanism should be secure; that is, it should provide means
	to verify the authenticity of the notifications.		to verify the authenticity of the notifications.
	4. The new protocol should not be dependent upon routing protocol		4. The new protocol should not be dependent upon routing protocol
	flooding procedures.		flooding procedures.
	5. The mechanism should have low processing overhead		5. The mechanism should have low processing overhead
	These design goals present a trade-off. Proper balance needs to be		These design goals present a trade-off. Proper balance needs to be
	found that offers good authentication and reliability while keeping		found that offers good authentication and reliability while keeping
	processing complexity sufficiently low. This draft proposes		processing complexity sufficiently low to enable implementation in
	solutions that take the above goals and trade-offs into		dataplane. This draft proposes solutions that take the above goals
	considerations.		and trade-offs into considerations.
	3. Transport Logic - Distribution of the Notifications		3. Transport Logic - Distribution of the Notifications
	The distribution of a notification to multiple receivers can be		The distribution of a notification to multiple receivers can be
	implemented in many ways. The main body of this draft describes one		implemented in many ways. The main body of this draft describes one
	such option: dual redundant trees. This option allows each		such option, a flooding-like approach.
	notification to be delivered to any node in the area in case of
	single node or link failure.
	3.1. Multicast Tree-based Transport
	One way of transporting an identical piece of information to several
	receivers at the same time is to use multicast distribution trees. A
	tree based transport solution is beneficial since multicast support
	is already implemented in all forwarding entities, so it is possible
	to use existing implementations.
	With multicast or tree based transport, the Fast Notification (FN)
	packet can be recognized by a pre-configured or well known
	destination IP address, denoted by MC-FN in the following, which is
	the group address of the FN service.
	If the FN service is triggered to send out a notification, the
	notification will be encapsulated in a new IP packet, where the
	destination IP address is set to MC-FN.
	3.1.1. Fault Tolerance of a Single Distribution Tree
	Several solutions described in this draft use a single tree to
	disseminate a notification from one given source.
	The single tree solution is simple, however it is not redundant: a
	single failure may partition the tree, which will prevent
	notifications from reaching some nodes in the area.
	Different applications may have different needs for reliability. For
	example, when we use fast notification to disseminate network failure
	information, all nodes surrounding the failure can detect and
	originate the failure notifications independently. Any one of these
	notifications (or a subset of them) may be sufficient for the
	application to make the right decision. This draft provides several
	different transport options from which an applications can choose.
	3.1.2. Pair of Redundant Trees		In flooding mode, the IGP configures the dataplane cards to replicate
			each received FN message to each interface with a neighbour router in
			the same area.
	If an FN application needs the exact same data to be distributed in		This happens by making use of bidirectional multicast forwarding. In
	the case of any single node or any single link failure, the FN		bidir multicast, all interfaces added to the multicast group can be
	service should be run in "redundant tree mode".		incoming and outgoing interfaces as well. The principle is that a
			router replicates the incoming packet to *all* assigned interfaces
			except the incoming interface. If the local router is the source of
			the packet to be forwarded, then the packet is replicated to all
			interfaces. That is, the decision about which interfaces should
			actually be used as outgoing is determined on demand.
	A pair of "redundant trees" ensures that at each single node or link		First, the FN service is assigned a multicast group address, let us
	failure each node still reaches the common root of the trees through		call this MC-FN address. Then, the IGP assigns all interfaces to
	at least one of the trees. A redundant tree pair is a known prior-		MC-FN which lead to neighbouring routers.
	art graph-theoretical object that is possible to find on any 2-node
	connected network. Even better, it is even possible to find
	maximally redundant trees in networks where the 2-node connected
	criterion does not "fully" hold (e.g. there are a few cut vertices)
	[Eny2009].
	Note that the referenced algorithm(s) build a pair of trees		When the FN service is instructed to disseminate a message, it
	considering a specific root. The root can be selected in different		creates an IP packet (as described below in Section 4) and sets its
	ways, the only thing that is important that each node makes the same		IP destination address to the MC-FN multicast address. This IP
	selection, consistently. For instance, the node with the highest or		packet is then multicasted to all IGP neighbours in the area.
	lowest router ID can be used.
	#1 tree #2 tree		Recipients of FN multicast-forward the packet according to the rules
	+---+ +---+ +---+ +---+		of bidirectional multicast, i.e. to all interfaces which the local
	| B |=======| | | B |=======| |		IGP pre-configured except the incoming interface. As this may cause
	+---+ +---+ +---+ +---+		loops without pre-caution (consider three routers in a triangle).
	// \\ // \		Before forwarding, therefore, the forwarding engine has to perform
	// \\ // \		duplicate check.
	+---+ +---+ +---+ +---+
	| A |---------------------| R | | A |=====================| R |
	+---+ +---+ +---+ +---+
	\ // \\ /
	\ // \\ /
	+---+ +---+ +---+ +---+
	| |=======| | | |=======| |
	+---+ +---+ +---+ +---+
	Figure 1: Example: a pair of redundant trees (double lines) of a		3.1. Duplicate Check
	common root R
	There is one special constraint in building the redundant trees. A		Duplicate check can be performed in numeruous ways.
	(maximally) redundant tree pair is needed, where in one of the trees
	the root has only one child in order to protect against the failure
	of the root itself. Algorithms presented in [Eny2009] produce such
	trees. The algorithm is also described in Appendix B in this
	specification.
	In redundant-tree mode, each node multicasts the requested		Duplicate check can be performed by maintaining a short queue of
	notification on both trees, if it is possible, but at least along one		previously forwarded FN messages. Before forwarding, if the FN
	of the trees. Redundant trees require two multicast group addresses.		message is found in the queue, then it was forwarded beforehand, so
	MC-FN identifies one of the trees, and MC-FN-2 identifies the other		it may be dropped. Otherwise it should be forwarded and it should be
	tree.		added to the queue.
	Each node multicast forwards the received notification packet (on the		Alternatively, the queue may contain a signature of the previously
	same tree). The root node performs as every other node but in		forwarded FN messages, such as an MD5 or SHA256 signature or any
	addition it also multicast the notification on the other tree! I.e.		other hash. This signature may be carried in the packet, e.g. due to
	it forwards a replica of the incoming notification in which it		authentication purposes, such as with the authentication mechanisms
	replaces the destination address identifying the other multicast		described in Section 4.2.1.
	distribution tree.
	When the network remains connected and the root remains operable		In either of the above queue-based mechanisms, the size of the queue
	after a single failure, the root will be reached on at least one of		can be set to a value that corresponds to the maximal number of legal
	the trees. Thus, since the root can reach every node along at least		FN messages generated by a single event. For instance, if FN is used
	one of the trees, all the notifications will reach each node.		to broadcast failure identifiers in case of failures, then it is
	However, when the root or the link to the root fails, that tree, in		likely that the failure of the node with the most neighbours will
	which the root has only one child, remains connected (the root is a		trigger the most FN messages (1 from each neighbour).
	leaf there), thus, all the nodes can be reached along that tree.
	For example, let us consider that in Figure 1 FN is used to		It is also possible to use application-dependent duplicate check: the
	disseminate failure information. If link A-B fails, the		state machine of the FN-application can be left responsible to decide
	notifications originating from node B (e.g. reporting that the		whether the information carried in the packet contains new
	connectivity from B to A is lost) will reach R on tree #1.		information or it is a duplicate. This is only useful in the case if
	Notifications originating from A (e.g. reporting that the		the application can perform the duplicate check faster then the above
	connectivity from A to B is lost) will reach R on tree #2. From R,		generic mechanisms.
	each node is reachable through one of the trees, so each node will be
	notified about both events.
	4. Message Encoding		4. Message Encoding
	4.1. Seamless Encapsulation		4.1. Seamless Encapsulation
	An application may define its own message for FN to distribute		An application may define its own message for FN to distribute
	quickly. In this case, only the special destination address (e.g.		quickly. In this case, only the special destination address (e.g.
	MC-FN) shows that the message was sent using the FN service.		MC-FN) shows that the message was sent using the FN service.
	In this case, the entire payload of the IP packet is determined by		In this case, the entire payload of the IP packet is determined by
	skipping to change at page 8, line 37 ¶		skipping to change at page 7, line 37 ¶
	. .		. .
	| ... |		| ... |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	| ... |		| ... |
	. .		. .
	. Authentication (optional) .		. Authentication (optional) .
	. .		. .
	| ... |		| ... |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	Figure 2: FN packet format as a UDP datagram		Figure 1: FN packet format as a UDP datagram
	The encoding of the FN Header is as follows:		The encoding of the FN Header is as follows:
	0 1 2 3		0 1 2 3
	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		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
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	| FN Length | FN App Type | AuType|unused |		| FN Length | FN App Type | AuType|unused |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	Figure 3: FN Header encoding		Figure 2: FN Header encoding
	FN Length (16 bits)		FN Length (16 bits)
	The length of the FN message in bytes including the FN Header and		The length of the FN message in bytes including the FN Header and
	the FN Payload. The authentication data optionally appended to		the FN Payload. The authentication data optionally appended to
	the FN packet is not considered part of the FN message: the		the FN packet is not considered part of the FN message: the
	authentication data is not included in the FN Length field,		authentication data is not included in the FN Length field,
	although it is included in the length field of the packet's IP		although it is included in the length field of the packet's IP
	header.		header.
	FN App Type (8 bits)		FN App Type (8 bits)
	Identifies the application which should be the receiver of the		Identifies the application which should be the receiver of the
	notification. A value for each application needs to be assigned		notification. A value for each application needs to be assigned
	by IANA.		by IANA.
	AuType		AuType
	Identifies the authentication procedure to be used for the packet.		Identifies the authentication procedure to be used for the packet.
	Authentication options are discussed in Section 4.2.1. of the		Authentication options are discussed in Section 4.2.1 of the
	specification.		specification.
	4.2.1. Authentication		4.2.1. Authentication
	Fast Notification intends to provide a trustable service option, so		Fast Notification intends to provide a trustable service option, so
	that receivers of FN packets are able to verify that the packet is		that receivers of FN packets are able to verify that the packet is
	sent by an authentic source. Simple password authentication and MD5		sent by an authentic source. Simple password authentication and hash
	authentication is described in the following subsections.		based authentication methods (with Md5 or SHA256) are described in
			the following subsections.
	If AuType is set to 0x0, then the FN packet is not carrying an		If AuType is set to 0x0, then the FN packet is not carrying an
	Authentication field at the end of the packet. Note that even in		Authentication field at the end of the packet. If AuType is zero,
	this case the FN application in the payload may still use its own		AuLength must also be zero. Note that even in this case the FN
	authentication mechanism.		application in the payload may still use its own authentication
			mechanism.
	If AuType is non null, an Authentication field must be appended after		If AuType is non null, an Authentication field must be appended after
	the FN message. The encoding of this field is as follows:		the FN message. The encoding of this field is as described below.
	0 1 2 3		0 1 2 3
	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		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
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	| AuLength | ... Authentication Data ... |		| AuLength | ... Authentication Data ... |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	| ... |		| ... |
	Figure 4: Authentication field in FN packets		Figure 3: Authentication field in FN packets
	AuLength		AuLength
	Describes the length of the entire Authentication field in bytes.		Describes the length of the entire Authentication field in bytes.
	4.2.1.1. Areas-scoped and Link-scoped Authentication		4.2.1.1. Areas-scoped and Link-scoped Authentication
	Since FN is a solution to disseminate an event notification from one		Since FN is a solution to disseminate an event notification from one
	source to a whole area of nodes, the simplest approach would be to		source to a whole area of nodes, the simplest approach would be to
	use per-area authentication, for example. a common password, a common		use per-area authentication, for example. a common password, a common
	pre- shared key among all nodes in the area as described in the		pre- shared key among all nodes in the area as described in the
	skipping to change at page 10, line 48 ¶		skipping to change at page 9, line 48 ¶
	Simple password authentication, however, can be easily compromised as		Simple password authentication, however, can be easily compromised as
	anyone with physical access to the network can read the password.		anyone with physical access to the network can read the password.
	4.2.1.3. Cryptographic Authentication for FN		4.2.1.3. Cryptographic Authentication for FN
	Using this authentication type, a secret key is used to generate/		Using this authentication type, a secret key is used to generate/
	verify a "message digest" that is appended to the end of the FN		verify a "message digest" that is appended to the end of the FN
	packet. The message digest is a one-way function of the FN packet		packet. The message digest is a one-way function of the FN packet
	and the secret key. This authentication mechanism resembles the		and the secret key. This authentication mechanism resembles the
	cryptographic authentication mechanism of [OSPF].		cryptographic authentication mechanism of [RFC2328].
	4.2.1.4. MD5		4.2.1.4. MD5
	The packet signature is created by an MD5 hash performed on an object		The packet signature is created by an MD5 hash performed on an object
	which is the concatenation of the FN message, including the FN		which is the concatenation of the FN message, including the FN
	header, and the pre-shared secret key. The resulting 16 byte MD5		header, and the pre-shared secret key. The resulting 16 byte MD5
	message digest is appended to the FN message into the Authentication		message digest is appended to the FN message into the Authentication
	field as shown below.		field as shown below.
	The AuType in the FN header is set to indicate cryptographic		The AuType in the FN header is set to indicate cryptographic
	authentication, the specific value is to be assigned by IANA both for		authentication, the specific value is to be assigned by IANA both for
	area-scoped and for link-scoped versions.		area-scoped and for link-scoped versions.
	0 1 2 3		0 1 2 3
	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		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
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	| AuLength | Key ID | Unused |		| AuLength | Key ID | Unused |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	| Message Digest (bytes 1-4) |		| Message Digest (bytes 1-4) |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	| Message Digest (bytes 5-8) |		| Message Digest (bytes 5-8) |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	| Message Digest (bytes 9-12) |		| Message Digest (bytes 9-12) |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	| Message Digest (bytes 13-16) |		| Message Digest (bytes 13-16) |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	Figure 5: Authentication field in FN packets with MD5 cryptographic		Figure 4: Authentication field in FN packets with MD5 cryptographic
	authentication.		authentication.
	AuLength		AuLength
	AuLength is set to 20 bytes.		AuLength is set to 20 bytes.
	Key ID		Key ID
	This field identifies the algorithm and secret key used to create		This field identifies the algorithm and secret key used to create
	the message digest appended to the FN packet. This field allows		the message digest appended to the FN packet. This field allows
	that multiple pre-shared keys may exist in parallel.		that multiple pre-shared keys may exist in parallel.
	skipping to change at page 12, line 10 ¶		skipping to change at page 11, line 10 ¶
	authentication, then the last 20 bytes of the FN message are set		authentication, then the last 20 bytes of the FN message are set
	aside. The recipient forwarding plane element calculates a new MD5		aside. The recipient forwarding plane element calculates a new MD5
	digest of the remainder of the FN message to which it appends its own		digest of the remainder of the FN message to which it appends its own
	known secret key identified by Key ID. The calculated and received		known secret key identified by Key ID. The calculated and received
	digests are compared. In case of mismatch, the FN message is		digests are compared. In case of mismatch, the FN message is
	discarded.		discarded.
	In per-link authentication mode, the Authentication field must be		In per-link authentication mode, the Authentication field must be
	regenerated hop-by-hop using the key of the outgoing link.		regenerated hop-by-hop using the key of the outgoing link.
	4.2.1.5. Digital Signatures		4.2.1.5. SHA256
			Similarly to how MD5 authentication works, it is possible to use
			Secure Hash 256 hash. Currently this is a more secure hash function
			than MD5. The Authentication field would look like this:
			0 1 2 3
			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
			+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
			| AuLength | Key ID | Unused |
			+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
			| Message Digest (bytes 1-4) |
			+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
			| Message Digest (bytes 5-8) |
			+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
			| . . . |
			+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
			| Message Digest (bytes 25-28) |
			+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
			| Message Digest (bytes 29-32) |
			+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
			Figure 5: Authentication field in FN packets with MD5 cryptographic
			authentication.
			AuLength
			AuLength is set to 36 bytes.
			Key ID
			This field identifies the algorithm and secret key used to create
			the message digest appended to the FN packet. This field allows
			that multiple pre-shared keys may exist in parallel.
			Message Digest
			The 32 bytes long SHA256 value calculated on an object which is
			the concatenation of the FN message, including the FN header, and
			the pre-shared secret key identified by Key ID.
			When receiving an FN message, if the FN header indicates SHA256
			authentication, then the last 68 bytes of the FN message are set
			aside. The recipient forwarding plane element calculates a new
			SHA256 digest of the remainder of the FN message to which it appends
			its own known secret key identified by Key ID. The calculated and
			received digests are compared. In case of mismatch, the FN message
			is discarded.
			In per-link authentication mode, the Authentication field must be
			regenerated hop-by-hop using the key of the outgoing link.
			4.2.1.6. Digital Signatures
	A router may choose to use public key cryptography to digitally sign		A router may choose to use public key cryptography to digitally sign
	the notification to provide certification of authenticity. This		the notification to provide certification of authenticity. This
	mechanism can avoid shared secret that is required for other		mechanism can avoid shared secret that is required for other
	authentication mechanisms described in this document. This		authentication mechanisms described in this document. This
	authentication mechanism resembles the authentication mechanism of		authentication mechanism resembles the authentication mechanism of
	OSPF with digital signatures as defined in [RFC2154].		OSPF with digital signatures as defined in [RFC2154].
	5. Acknowledgements		5. Security Considerations
	The authors owe thanks to Acee Lindem, Joel Halpern and Jakob Heitz
	for their review and comments.
	6. Security Considerations
	This draft has described basic optional procedures for		This draft has described basic optional procedures for
	authentication. The mechanism, however, does not protect against		authentication. The mechanism, however, does not protect against
	replay attacks.		replay attacks.
	If an application of FN require protection against replay attacks,		If an application of FN require protection against replay attacks,
	then these applications should provide their own specific sequence		then these applications should provide their own specific sequence
	numbering within the FN payload. Recipient applications should		numbering within the FN payload. Recipient applications should
	accept FN messages only if the included sequence number is valid.		accept FN messages only if the included sequence number is valid.
	Since the message digest of cryptographic authentication also covers		Since the message digest of cryptographic authentication also covers
	the payload, even if an attacker knew how to construct the new		the payload, even if an attacker knew how to construct the new
	sequence number, it would not be able to generate a correct message		sequence number, it would not be able to generate a correct message
	digest without the pre shared key. This way, a sequence number in		digest without the pre shared key. This way, a sequence number in
	the payload combined with FN's cryptographic authentication offers		the payload combined with FN's cryptographic authentication offers
	sufficient protection against replay attacks.		sufficient protection against replay attacks.
			6. FN Packet Processing Summary
			When receiving an FN packet, a node has to perform the following
			steps.
			It has to identify that the packet is an FN packet. This can be done
			utilising the destination IP address (MC-FN) or by inspecting the UDP
			port field.
			If the flooding like transport logic described in Section 3 is used
			the node has to perform duplicate check following the teachings in
			Section 3.1.
			If AuType is non-null, the node has to perform authentication check
			as discussed in Section 4.2.1.
			To protect against replay attacks, the node shall perform
			verification of the sequence number provided by the application.
			Punt and forward. The notification may need to be multicasted but it
			also needs to be punted to the local application on the linecard to
			start processing.
			Authentication check, sequence number check and punting/forwarding
			may commence in any order deemed necessary by the operator. If the
			operator prefers highest level of security, then both checks should
			be performed before forwarding. If, however, the operator prefers
			per-hop performance but still wants to ensure that malice packets
			cannot harm the network, then authentication and sequence number
			checks may also happen after punting the packet, i.e. before
			processing the information contained inside the FN payload. In this
			case, malicious packets may get propagated to every node but they
			still do not cause any change in the configuration.
	7. IANA Considerations		7. IANA Considerations
	An IP protocol value needs to be assigned by IANA for FN. IANA also		A UDP port value needs to be assigned by IANA for FN. IANA also
	needs to maintain values for FN App Type as applications are being		needs to maintain values for FN App Type as applications are being
	proposed.		proposed.
	Multicast addresses used for the distribution trees are either		Multicast addresses used for the distribution trees are either
	allocated by IANA or they can be a configuration parameter within the		allocated by IANA or they can be a configuration parameter within the
	local domain.		local domain.
	8. References		8. Acknowledgements
	8.1. Normative References		The authors owe thanks to Acee Lindem, Joel Halpern and Jakob Heitz
			for their review and comments. Also thanks to Alia Atlas for
			constructive feedback.
			9. References
			9.1. Normative References
	[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate		[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
	Requirement Levels", BCP 14, RFC 2119, March 1997.		Requirement Levels", BCP 14, RFC 2119, March 1997.
	[BIDIR-PIM] Handley, M., Kouvelas, I., Speakman, T., and L. Vicisano,		[RFC5015] Handley, M., Kouvelas, I., Speakman, T., and L. Vicisano,
	"Bidirectional Protocol Independent Multicast (BIDIR-		"Bidirectional Protocol Independent Multicast (BIDIR-
	PIM)", RFC 5015, October 2007.		PIM)", RFC 5015, October 2007.
	8.2. Informative References		9.2. Informative References
	[Eny2009] Enyedi, G., Retvari, G., and A. Csaszar, "On Finding		[Eny2009] Enyedi, G., Retvari, G., and A. Csaszar, "On Finding
	Maximally Redundant Trees in Strictly Linear Time, IEEE		Maximally Redundant Trees in Strictly Linear Time, IEEE
	Symposium on Computers and Communications (ISCC)", 2009.		Symposium on Computers and Communications (ISCC)", 2009.
	[ipfrr-fn]		[I-D.csaszar-ipfrr-fn]
	Kini, S., Csaszar, A., and G. Envedi, "IP Fast Re-Route		Kini, S., Csaszar, A., and G. Envedi, "IP Fast Re-Route
	with Fast Notification", draft-csaszar-ipfrr-fn-00 (work		with Fast Notification", draft-csaszar-ipfrr-fn-00 (work
	in progress), March 2011.		in progress), March 2011.
	[ospf-fn]		[I-D.kini-ospf-fast-notification]
	Kini, S., Lu, W., and A. Tian, "OSPF Fast Notification",		Kini, S., Lu, W., and A. Tian, "OSPF Fast Notification",
	draft-kini-ospf-fast-notification-01 (work in progress),		draft-kini-ospf-fast-notification-01 (work in progress),
	March 2011.		March 2011.
	[fn-framework]		[I-D.lu-fast-notification-framework]
	Lu, W., Tian, A., and S. Kini, "Fast Notification		Lu, W., Tian, A., and S. Kini, "Fast Notification
	Framework", draft-lu-fast-notification-framework-00 (work		Framework", draft-lu-fast-notification-framework-00 (work
	in progress), October 2010.		in progress), October 2010.
			[RFC2154] Murphy, S., Badger, M., and B. Wellington, "OSPF with
			Digital Signatures", RFC 2154, June 1997.
	[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.		[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
	Appendix A. Further Options for Transport Logic		Appendix A. Further Options for Transport Logic
	The options described in this appendix represent alternative		The options described in this appendix represent alternative
	solutions to the redundant tree based approach described in Section		solutions to the flooding based approach described in Section
	3.1.2.		Section 3.
	It is left for WG discussion and further evaluation to decide whether		It is left for WG discussion and further evaluation to decide whether
	any of these options should potentially be preferred instead of		any of these options should potentially be preferred instead of
	redundant trees.		redundant trees.
	A.1. Unicast		A.1. Multicast Tree-based Transport
			One way of transporting an identical piece of information to several
			receivers at the same time is to use multicast distribution trees. A
			tree based transport solution is beneficial since multicast support
			is already implemented in all forwarding entities, so it is possible
			to use existing implementations.
			With multicast or tree based transport, the Fast Notification (FN)
			packet can be recognized by a pre-configured or well known
			destination IP address, denoted by MC-FN in the following, which is
			the group address of the FN service.
			If the FN service is triggered to send out a notification, the
			notification will be encapsulated in a new IP packet, where the
			destination IP address is set to MC-FN.
			A.1.1. Fault Tolerance of a Single Distribution Tree
			Several solutions described in this draft use a single tree to
			disseminate a notification from one given source.
			The single tree solution is simple, however it is not redundant: a
			single failure may partition the tree, which will prevent
			notifications from reaching some nodes in the area.
			Different applications may have different needs for reliability. For
			example, when we use fast notification to disseminate network failure
			information, all nodes surrounding the failure can detect and
			originate the failure notifications independently. Any one of these
			notifications (or a subset of them) may be sufficient for the
			application to make the right decision. This draft provides several
			different transport options from which an applications can choose.
			A.1.2. Pair of Redundant Trees
			If an FN application needs the exact same data to be distributed in
			the case of any single node or any single link failure, the FN
			service could opt to run in "redundant tree mode".
			A pair of "redundant trees" ensures that at each single node or link
			failure each node still reaches the common root of the trees through
			at least one of the trees. A redundant tree pair is a known prior-
			art graph-theoretical object that is possible to find on any 2-node
			connected network. Even better, it is even possible to find
			maximally redundant trees in networks where the 2-node connected
			criterion does not "fully" hold (e.g. there are a few cut vertices)
			[Eny2009].
			Note that the referenced algorithm(s) build a pair of trees
			considering a specific root. The root can be selected in different
			ways, the only thing that is important that each node makes the same
			selection, consistently. For instance, the node with the highest or
			lowest router ID can be used.
			#1 tree #2 tree
			+---+ +---+ +---+ +---+
			| B |=======| | | B |=======| |
			+---+ +---+ +---+ +---+
			// \\ // \
			// \\ // \
			+---+ +---+ +---+ +---+
			| A |---------------------| R | | A |=====================| R |
			+---+ +---+ +---+ +---+
			\ // \\ /
			\ // \\ /
			+---+ +---+ +---+ +---+
			| |=======| | | |=======| |
			+---+ +---+ +---+ +---+
			Figure 6: Example: a pair of redundant trees (double lines) of a
			common root R
			There is one special constraint in building the redundant trees. A
			(maximally) redundant tree pair is needed, where in one of the trees
			the root has only one child in order to protect against the failure
			of the root itself. Algorithms presented in [Eny2009] produce such
			trees.
			In redundant-tree mode, each node multicasts the requested
			notification on both trees, if it is possible, but at least along one
			of the trees. Redundant trees require two multicast group addresses.
			MC-FN identifies one of the trees, and MC-FN-2 identifies the other
			tree.
			Each node multicast forwards the received notification packet (on the
			same tree). The root node performs as every other node but in
			addition it also multicast the notification on the other tree! I.e.
			it forwards a replica of the incoming notification in which it
			replaces the destination address identifying the other multicast
			distribution tree.
			When the network remains connected and the root remains operable
			after a single failure, the root will be reached on at least one of
			the trees. Thus, since the root can reach every node along at least
			one of the trees, all the notifications will reach each node.
			However, when the root or the link to the root fails, that tree, in
			which the root has only one child, remains connected (the root is a
			leaf there), thus, all the nodes can be reached along that tree.
			For example, let us consider that in Figure 6 FN is used to
			disseminate failure information. If link A-B fails, the
			notifications originating from node B (e.g. reporting that the
			connectivity from B to A is lost) will reach R on tree #1.
			Notifications originating from A (e.g. reporting that the
			connectivity from A to B is lost) will reach R on tree #2. From R,
			each node is reachable through one of the trees, so each node will be
			notified about both events.
			A.2. Unicast
	This method addresses the need in a unique way. It has the following		This method addresses the need in a unique way. It has the following
	properties:		properties:
	Plain simple, without the need of any forwarding plane change or		Plain simple, without the need of any forwarding plane change or
	cooperation;		cooperation;
	Short turnaround time (i.e. ready for next hit);		Short turnaround time (i.e. ready for next hit);
	100% link break coverage (may not work in certain node failure		100% link break coverage (may not work in certain node failure
	cases);		cases);
	Little change to OSPF (need encapsulation for IS-IS).		Little change to OSPF (need encapsulation for IS-IS).
	A.1.1. Method		A.2.1. Method
	The method is simple in design, easy to implement and quick to		The method is simple in design, easy to implement and quick to
	deploy. It requires no topology changes or specific configurations.		deploy. It requires no topology changes or specific configurations.
	It adds little overhead to the overall system.		It adds little overhead to the overall system.
	The method sends the event message to every router in the area in an		The method sends the event message to every router in the area in an
	IP packet. This appears burdensome to the sending router which has		IP packet. This appears burdensome to the sending router which has
	to duplicate the packet sending effort many times. Practical		to duplicate the packet sending effort many times. Practical
	experience has shown, however, that the amount of effort is not a big		experience has shown, however, that the amount of effort is not a big
	concern in reasonable sized networks.		concern in reasonable sized networks.
	skipping to change at page 15, line 11 ¶		skipping to change at page 18, line 17 ¶
	forwarding plane already has the list of all routers which are part		forwarding plane already has the list of all routers which are part
	of the IGP routing table, the forwarding plane can dispatch the		of the IGP routing table, the forwarding plane can dispatch the
	packet directly.		packet directly.
	In essence, the flooding in this method is tree based, just like a		In essence, the flooding in this method is tree based, just like a
	multicast tree. The key is that no special tree is generated for		multicast tree. The key is that no special tree is generated for
	this purpose; the normal routing table which is an SPF tree (SPT)		this purpose; the normal routing table which is an SPF tree (SPT)
	plays a role of the flooding tree. This logic guarantees that the		plays a role of the flooding tree. This logic guarantees that the
	flooding follows the shortest path and no flooding loop is created.		flooding follows the shortest path and no flooding loop is created.
	A.1.2. Sample Operation		A.2.2. Sample Operation
	Figure 6 depicts a scenario where router A wants to flood its message		Figure 7 depicts a scenario where router A wants to flood its message
	to all other routers in the domain using the unicast flooding method.		to all other routers in the domain using the unicast flooding method.
	Instead of sending one packet to each of its neighbor, and letting		Instead of sending one packet to each of its neighbor, and letting
	the neighbor flood the packet further, router A directly send the		the neighbor flood the packet further, router A directly send the
	same packet to each router in the domain, one at a time. In this		same packet to each router in the domain, one at a time. In this
	sample network, router A sends out 5 packets.		sample network, router A sends out 5 packets.
	A---B---C---D		A---B---C---D
	\		\
	--E---F		--E---F
	1. Packet(A->B);		1. Packet(A->B);
	2. Packet(A->C);		2. Packet(A->C);
	3. Packet(A->D);		3. Packet(A->D);
	4. Packet(A->E);		4. Packet(A->E);
	5. Packet(A->F).		5. Packet(A->F).
	Figure 6: Multiple Unicast Packets		Figure 7: Multiple Unicast Packets
	The unicast flooding procedure is solely controlled by the sending		The unicast flooding procedure is solely controlled by the sending
	router. No action is needed from other routers other than their		router. No action is needed from other routers other than their
	normal forwarding functionalities. This method is extremely simple		normal forwarding functionalities. This method is extremely simple
	and useful for quick prototyping and deployment.		and useful for quick prototyping and deployment.
	A.2. Gated Multicast through RPF Check		A.3. Gated Multicast through RPF Check
	This method fulfills the purpose with the following characters:		This method fulfills the purpose with the following characters:
	1. No need to build the multicast tree. It is the same as the SPT		1. No need to build the multicast tree. It is the same as the SPT
	computed by the IGP routing process;		computed by the IGP routing process;
	2. Flooding loops are prevented by RPF Check.		2. Flooding loops are prevented by RPF Check.
	The method has all the benefits of multicast flooding. It, however,		The method has all the benefits of multicast flooding. It, however,
	does not require running multicast protocol to setup the multicast		does not require running multicast protocol to setup the multicast
	tree. The unicast shortest path tree is used as a multicast tree.		tree. The unicast shortest path tree is used as a multicast tree.
	A.2.1. Loop Prevention - RPF Check		A.3.1. Loop Prevention - RPF Check
	In this mechanism, the distribution tree is not explicitly built.		In this mechanism, the distribution tree is not explicitly built.
	Rather, each node will first do a Reverse Path Forwarding (RPF) check		Rather, each node will first do a Reverse Path Forwarding (RPF) check
	before it floods the notification to other links.		before it floods the notification to other links.
	A special multicast address is defined and is subject to IANA		A special multicast address is defined and is subject to IANA
	approval. This address is used to qualify the notification packet		approval. This address is used to qualify the notification packet
	for fast flooding. When a notification packet arrives, the receiving		for fast flooding. When a notification packet arrives, the receiving
	node will perform an IP unicast routing table lookup for the		node will perform an IP unicast routing table lookup for the
	originator IP address of the notification and find the outgoing		originator IP address of the notification and find the outgoing
	interface. Only when the arriving interface of the notification is		interface. Only when the arriving interface of the notification is
	the same as the outgoing interface leading towards the originator IP		the same as the outgoing interface leading towards the originator IP
	address, will the notification be flooded to other interfaces.		address, will the notification be flooded to other interfaces.
	IP Multicast forwarding with RPF check is available on most of the		IP Multicast forwarding with RPF check is available on most of the
	routing/switching platforms. To support flooding with RPF check, a		routing/switching platforms. To support flooding with RPF check, a
	special IP multicast group must be used. A bi-directional IP		special IP multicast group must be used. A bi-directional IP
	multicast forwarding entry is created that consists of all interfaces		multicast forwarding entry is created that consists of all interfaces
	within the flooding scope, typically an IGP area.		within the flooding scope, typically an IGP area.
	A.2.2. Operation		A.3.2. Operation
	The Gated flooding operation is illustrated in Figure 7.		The Gated flooding operation is illustrated in Figure 8.
	All Routers, IGP Process:		All Routers, IGP Process:
	if (SPT ready) {		if (SPT ready) {
	duplicate the SPT as Bidir_Multicast_tree;		duplicate the SPT as Bidir_Multicast_tree;
	download the multicast_tree to forwarding plane;		download the multicast_tree to forwarding plane;
	}		}
	add FNF_multicast_group_addr;		add FNF_multicast_group_addr;
	Sender of the FNF notification:		Sender of the FNF notification:
	if (breakage detected) {		if (breakage detected) {
	pack the notification in a packet;		pack the notification in a packet;
	send the packet to the FNF_multicast_group_addr;		send the packet to the FNF_multicast_group_addr;
	}		}
	Receiver of the FNF notification:		Receiver of the FNF notification:
	if (notification received) {		if (notification received) {
	if (RPC_interface == incoming_interface) {		if (RPC_interface == incoming_interface) {
	multicast the notification to all other interfaces;		multicast the notification to all other interfaces;
			}
			forward the notification to IGP for processing;
	}		}
	forward the notification to IGP for processing;
	}
	Figure 7: Gated flooding operation		Figure 8: Gated flooding operation
	Figure 8 shows a sample operation on a four-router mesh network. The		Figure 9 shows a sample operation on a four-router mesh network. The
	left figure is the topology. The right figure is the shortest path		left figure is the topology. The right figure is the shortest path
	tree rooted at A.		tree rooted at A.
	Router A initiates the flooding. But the downstream routers B, C,		Router A initiates the flooding. But the downstream routers B, C,
	and D will drop all messages except the ones that come from their		and D will drop all messages except the ones that come from their
	shortest path parent node. For example, A's message to C via B is		shortest path parent node. For example, A's message to C via B is
	dropped by C, because C knows that its reverse path forwarding (RPF)		dropped by C, because C knows that its reverse path forwarding (RPF)
	nexthop is A.		nexthop is A.
	A A		A A
	/|\ / \		/|\ / \
	B---C B C		B---C B C
	\|/ \		\|/ \
	D D		D D
	Figure 8: Loop Prevention through the RPF check		Figure 9: Loop Prevention through the RPF check
	A.3. Further Multicast Tree based Transport Options		A.4. Further Multicast Tree based Transport Options
	A.3.1. Source Specific Trees		A.4.1. Source Specific Trees
	One implementation option is to rely on source specific multicast.		One implementation option is to rely on source specific multicast.
	This means that even though there is only a single multicast group		This means that even though there is only a single multicast group
	address (MC-FN) allocated to the FN service, the FIB of each router		address (MC-FN) allocated to the FN service, the FIB of each router
	is configured with forwarding information for as many trees as many		is configured with forwarding information for as many trees as many
	FN sources (nodes) there are in the routing area, i.e. to each		FN sources (nodes) there are in the routing area, i.e. to each
	(S_i,MC-FN) pair.		(S_i,MC-FN) pair.
	A.3.2. A Single Bidirectional Shared Tree		A.4.2. A Single Bidirectional Shared Tree
	In the previous solution each source specific tree is a spanning		In the previous solution each source specific tree is a spanning
	tree. It is possible to reduce the complexity of managing and		tree. It is possible to reduce the complexity of managing and
	configuring n spanning trees in the area by using bidirectional		configuring n spanning trees in the area by using bidirectional
	shared trees. By building a bidirectional shared tree, all nodes on		shared trees. By building a bidirectional shared tree, all nodes on
	the tree can send and receive traffic using that single tree. Each		the tree can send and receive traffic using that single tree. Each
	sent packet from any source is multicasted on the tree to all other		sent packet from any source is multicasted on the tree to all other
	receivers.		receivers.
	The tree must be consistently computed at all routers. For this, the		The tree must be consistently computed at all routers. For this, the
	skipping to change at page 18, line 47 ¶		skipping to change at page 21, line 40 ¶
	Note, however, that the important point is that the rules are		Note, however, that the important point is that the rules are
	consistent among nodes. That is, a router may pick the lower router		consistent among nodes. That is, a router may pick the lower router
	IDs if it is ensured that ALL routers will do the same to ensure		IDs if it is ensured that ALL routers will do the same to ensure
	consistency.		consistency.
	Multicast forwarding state is installed using such a tree as a bi-		Multicast forwarding state is installed using such a tree as a bi-
	directional tree. Each router on the tree can send packets to all		directional tree. Each router on the tree can send packets to all
	other routers on that tree.		other routers on that tree.
	Note that the multicast spanning tree can be built using [BIDIR-PIM]		Note that the multicast spanning tree can be built using [RFC5015] so
	so that each router within an area subscribes to the same multicast		that each router within an area subscribes to the same multicast
	group address. Using BIDIR-PIM in such a way will eventually build a		group address. Using BIDIR-PIM in such a way will eventually build a
	multicast spanning tree among all routers within the area. (BIDIR-		multicast spanning tree among all routers within the area. (BIDIR-
	PIM is normally used to build a shared, bidirectional multicast tree		PIM is normally used to build a shared, bidirectional multicast tree
	among multiple sources and receivers.)		among multiple sources and receivers.)
	A.4. Layer 2 Networks		A.5. Layer 2 Networks
	Layer 2 (e.g. Ethernet) networks offer further options for		Layer 2 (e.g. Ethernet) networks offer further options for
	distributing the notification (e.g. using spanning trees offered by		distributing the notification (e.g. using spanning trees offered by
	STP). Definition of these is being considered and will be included		STP). Definition of these is being considered and will be included
	in a future revision of this draft.		in a future revision of this draft.
	Appendix B. Computing maximally redundant trees
	Here we describe a possible, not optimal, way of computing maximally
	redundant trees. First, we suppose that the network is 2-connected
	and that we have a central processor computing the trees, then we
	lift these assumptions.
	B.1. Simple pair of maximally redundant trees in 2-connected networks
	Finding a simple pair of maximally redundant trees in a 2-connected
	network is quite simple. We call a node "ready", if it was already
	added to the trees. Initially, the only ready node is the common
	root (node r in the sequel).
	When we have at least one node x in the network, which is not ready,
	find two node-disjoint paths from x either to r or to two distinct
	ready nodes. Since the network is 2-connected, there are always two
	node-disjoint paths from x to r. It is possible that one or both of
	these paths reaches another ready node sooner than r, in which case
	we have the two node-disjoint paths to distinct nodes. Combining the
	undirected links of these paths makes up an *ear*.
	x---a
	\
	b
	|
	c
	/
	y---d
	Figure 9: An *ear* connected to node x and y (x and y are ready)
	Let x and y be the two ready endpoints of an ear, and first suppose
	that they are different nodes and none of them is r. Note that both
	x and y are in the two trees (since they are "ready") and if x is an
	ancestor of y in the first tree (x is on the path from y to r), then
	x cannot be the ancestor of y along the second tree at the same time.
	Thus, it is safe to connect the nodes of the freshly found ear to x
	in the first tree and to y in the second tree, if either x is an
	ancestor of y in the first tree, or y is an ancestor of x in the
	second tree. Considering the example in Figure 9, this means that
	links d-c-b-a-x should be added to the first tree, and a-b-c-d-y
	should be added to the second one.
	In the case, when either x=r or y=r or when neither x is an ancestor
	of y nor y is an ancestor of x in any of the trees, the endpoints are
	not firmly bound to one of the trees, it is only important to put the
	links to one endpoint in one of the trees and put the links towards
	the other endpoint to the other tree. In our example this means that
	either d-c-b-a-x or a-b-c-d-y could be added to the first tree.
	Naturally, then the other endpoint must be selected for the second
	tree.
	In order to protect against the failure of the root r, we need to
	construct (maximally) redundant trees, where there is only one edge
	entering to the root on one of the trees. This makes the root a leaf
	in that tree. To achieve this, we should add the ear to the second
	tree through r only if both endpoints are r. Moreover, we need to
	select an ear with different endpoints when it is possible.
	Finding an ear is relatively simple and can be done in different
	ways. Probably the simplest way is to find a ready node q (q is not
	the root) with a non-ready neighbor w, (virtually) remove q from the
	topology, and to find a path from w to r; since the network is 2-
	connected, such a path either reaches r, or reach another ready node.
	Moreover, when only r is ready such a node q does not exist, so we
	select one of r's neighbors as w, and remove not r but the link
	between them.
	e---d
	/ / \
	r---c f
	\ \ /
	a---b
	Figure 10: A 2-connected network
	e---d e---d
	/ / \
	r c f r---c f
	\ \ / \
	a---b a---b
	Figure 11: The two maximally redundant trees found in the network
	Now, a simple example is in order. Consider the network depicted in
	Figure 10, and suppose that the common root is node r. We have only
	r in the trees, so we select one of its neighbors, let it be a,
	remove the link between them, and select a path (let it be the
	shortest one) from a to r; this path is a-b-c-r, so the ear is
	r-a-b-c-r. Since both endpoints of the ear are r, selecting the
	right tree is not important, e.g., we can add c-b-a-r to the first
	tree, and a-b-c-r to the second one (Figure 11). This way, r, a, b
	and c form the set of "ready" nodes. From the ready set, c and d are
	not the root and have non-ready neighbors. Let us select, e.g., c.
	The shortest path from d to r when c is removed is d-e-r, so we have
	ear c-d-e-r, we add d-e-r to the first tree and e-d-c to the second
	one (recall that we do not want to create a new neighbor for r in the
	second tree). Finally, the last non-ready node is f, and the ear is
	b-f-d. Since neither is b an ancestor of d nor is d an ancestor of b
	in any of the trees, we can connect f to the trees in both ways.
	E.g., add f-b to the first tree, and f-d to the second one.
	B.2. Non-2-connected networks
	When, however, the network is not 2-connected, it is not always
	possible to find a pair of node-disjoint paths from any node x to
	root r, which makes our previous algorithm unable to find the trees.
	However, while the network is connected, it is made up by 2-connected
	components bordered by "cut-vertices" (naturally, some of these
	components may contain only one node). A node is a cut-vertex, if
	removing that node splits the network into two.
	A simple algorithm to find the components and the cut-vertices can be
	to (virtually) remove each vertex one by one, and check connectivity
	with BFS or DFS. Moreover, nodes a and b are in the same 2-connected
	component, if a remains reachable from b after removing any single
	node. Note that linear time algorithms do exist that find both the
	2- connected components and the cut-vertices.
	Now, we can build up redundant trees in each component. In
	components containing r, the root of such trees must be r.
	Otherwise, in the remaining components the root must be the last node
	in the component along a path to the root. Recall, that this must be
	a cut-vertex, so it is the same for each path emanating from that
	component.
	At this point, we are ready, if there is no cut-edge in the network.
	However, if some 2-connected components are connected by a cut-edge,
	we must add that edge to both of the trees.
	e---d i
	/ / \ /|
	r---c f--g |
	\ \ / \|
	a---b j
	Figure 12: Non-2-connected network
	e---d i e---d i
	/ /| / \ |
	r c f--g | r---c f--g |
	\ \ / | \ \|
	a---b j a---b j
	Figure 13: The two maximally redundant trees found in the network
	As an example consider the network depicted in Figure 12. Observe
	that now we have two 2-connected components, one contains r, a, b, c,
	d, e, f and the other contains g, i, j. Moreover, these components
	have no common node, they are connected with a cut-edge.
	Finding the trees in the component containing r is simple, these
	trees are the same as previously. Moreover, the other component is a
	cycle, so it will be covered by a single ear. Finally we must add
	link f-g to both of the trees, to get the trees depicted in
	Figure 13.
	B.3. Finding maximally redundant trees in distributed environment
	If we need to compute exactly the same maximally redundant trees at
	each of the routers, consistency needs to be ensured by tie-breaking
	mechanisms. Observe that the previous algorithm has multiple choices
	when it selects how to connect nodes to the trees when only r is
	ready, how to select ready node q and non-ready node w for a later
	ear and when neither of the endpoints is an ancestor of the other
	one.
	All the previous problems can easily be handled. E.g., the first ear
	should be connected in such a way, that the neighbor of r with the
	lowest ID must be directly connected to r in the first tree.
	Moreover, later we should choose ready router with non-ready neighbor
	as q and its non-ready neighbor with the lowest ID as w. Finally,
	when neither of the endpoint is an ancestor of the other one, connect
	the ear to the endpoint with the lower ID in the first tree.
	Authors' Addresses		Authors' Addresses
	Wenhu Lu		Wenhu Lu
	Ericsson		Ericsson
	300 Holger Way		300 Holger Way
	San Jose, California 95134		San Jose, California 95134
	USA		USA
	Email: Wenhu.Lu@ericsson.com		Email: Wenhu.Lu@ericsson.com
	Sriganesh Kini		Sriganesh Kini
	Ericsson		Ericsson
	300 Holger Way		300 Holger Way
	San Jose, California 95134		San Jose, California 95134
	USA		USA
	Email: Sriganesh.Kini@ericsson.com		Email: Sriganesh.Kini@ericsson.com
	Andras Csaszar		Andras Csaszar (editor)
	Ericsson		Ericsson
	Irinyi utca 4-10		Irinyi J utca 4-10
	Budapest 1117		Budapest 1117
	Hungary		Hungary
	Email: Andras.Csaszar@ericsson.com		Email: Andras.Csaszar@ericsson.com
	Gabor Sandor Enyedi		Gabor Sandor Enyedi
	Ericsson		Ericsson
	Irinyi utca 4-10		Irinyi J utca 4-10
	Budapest 1117		Budapest 1117
	Hungary		Hungary
	Email: Gabor.Sandor.Enyedi@ericsson.com		Email: Gabor.Sandor.Enyedi@ericsson.com
	Jeff Tantsura		Jeff Tantsura
	Ericsson		Ericsson
	300 Holger Way		300 Holger Way
	San Jose, California 95134		San Jose, California 95134
	USA		USA
	Email: Jeff.Tantsura@ericsson.com		Email: Jeff.Tantsura@ericsson.com
	Albert Tian
	Ericsson
	300 Holger Way
	San Jose, California 95134
	USA
	Email: Albert.Tian@ericsson.com
End of changes. 78 change blocks.
	429 lines changed or deleted		395 lines changed or added
This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/