draft-ietf-rtgwg-bgp-pic-07.txt		draft-ietf-rtgwg-bgp-pic-08.txt
	Network Working Group A. Bashandy, Ed.		Network Working Group A. Bashandy, Ed.
	Internet Draft C. Filsfils		Internet Draft Arrcus
	Intended status: Informational Cisco Systems		Intended status: Informational C. Filsfils
	Expires: September 2018 P. Mohapatra		Expires: March 2019 Cisco Systems
			P. Mohapatra
	Sproute Networks		Sproute Networks
	March 30, 2018		September 26, 2018
	BGP Prefix Independent Convergence		BGP Prefix Independent Convergence
	draft-ietf-rtgwg-bgp-pic-07.txt		draft-ietf-rtgwg-bgp-pic-08.txt
	Abstract		Abstract
	In the network comprising thousands of iBGP peers exchanging millions		In the network comprising thousands of iBGP peers exchanging millions
	of routes, many routes are reachable via more than one next-hop.		of routes, many routes are reachable via more than one next-hop.
	Given the large scaling targets, it is desirable to restore traffic		Given the large scaling targets, it is desirable to restore traffic
	after failure in a time period that does not depend on the number of		after failure in a time period that does not depend on the number of
	BGP prefixes. In this document we proposed an architecture by which		BGP prefixes. In this document we proposed an architecture by which
	traffic can be re-routed to ECMP or pre-calculated backup paths in a		traffic can be re-routed to ECMP or pre-calculated backup paths in a
	timeframe that does not depend on the number of BGP prefixes. The		timeframe that does not depend on the number of BGP prefixes. The
	skipping to change at page 2, line 19 ¶		skipping to change at page 2, line 22 ¶
	documents at any time. It is inappropriate to use Internet-Drafts		documents at any time. It is inappropriate to use Internet-Drafts
	as reference material or to cite them other than as "work in		as reference material or to cite them other than as "work in
	progress."		progress."
	The list of current Internet-Drafts can be accessed at		The list of current Internet-Drafts can be accessed at
	http://www.ietf.org/ietf/1id-abstracts.txt		http://www.ietf.org/ietf/1id-abstracts.txt
	The list of Internet-Draft Shadow Directories can be accessed at		The list of Internet-Draft Shadow Directories can be accessed at
	http://www.ietf.org/shadow.html		http://www.ietf.org/shadow.html
	This Internet-Draft will expire on September 30, 2018.		This Internet-Draft will expire on March 27, 2019.
	Copyright Notice		Copyright Notice
	Copyright (c) 2018 IETF Trust and the persons identified as the		Copyright (c) 2018 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 8, line 38 ¶		skipping to change at page 8, line 38 ¶
	-------- +-------+ -------- +----------+		-------- +-------+ -------- +----------+
	VPN-IP1-->|BGP-NH1|-->IGP-IP1(BGP NH1)--->|IGP NH1,I1|--->Adjacency1		VPN-IP1-->|BGP-NH1|-->IGP-IP1(BGP NH1)--->|IGP NH1,I1|--->Adjacency1
	| |BGP-NH2|-->.... | |IGP NH2,I2|--->Adjacency2		| |BGP-NH2|-->.... | |IGP NH2,I2|--->Adjacency2
	| +-------+ | +----------+		| +-------+ | +----------+
	| |		| |
	| |		| |
	v v		v v
	OutLabel-List: OutLabel-List:		OutLabel-List: OutLabel-List:
	+----------------------+ +----------------------+		+----------------------+ +----------------------+
	|VPN-L11 (VPN-IP1, NH1)| |IGP-L11 (IGP-IP1, NH1)|		|VPN-L11 (VPN-IP1, NH1)| |IGP-L11 (IGP-IP1, NH1)|
	|VPN-L12 (VPN-IP1, NH2)| |IGP-L12 (IGP-IP1, NH2)|		|VPN-L21 (VPN-IP1, NH2)| |IGP-L12 (IGP-IP1, NH2)|
	+----------------------+ +----------------------+		+----------------------+ +----------------------+
	Figure 2 Shared Hierarchical Forwarding Chain at iPE		Figure 2 Shared Hierarchical Forwarding Chain at iPE
	The forwarding chain depicted in Figure 2 illustrates the first		The forwarding chain depicted in Figure 2 illustrates the first
	pillar, which is sharing and hierarchy. We can see that the BGP		pillar, which is sharing and hierarchy. We can see that the BGP
	pathlist consisting of BGP-NH1 and BGP-NH2 is shared by all NLRIs		pathlist consisting of BGP-NH1 and BGP-NH2 is shared by all NLRIs
	reachable via ePE1 and ePE2. As such, it is possible to make changes		reachable via ePE1 and ePE2. As such, it is possible to make changes
	to the pathlist without having to make changes to the NLRIs. For		to the pathlist without having to make changes to the NLRIs. For
	example, if BGP-NH2 becomes unreachable, there is no need to modify		example, if BGP-NH2 becomes unreachable, there is no need to modify
	skipping to change at page 16, line 11 ¶		skipping to change at page 16, line 11 ¶
	ASBR13 via IGP using the same distance.		ASBR13 via IGP using the same distance.
	We will make the following assumptions about the labels		We will make the following assumptions about the labels
	o The VPN labels advertised by ePE1 and ePE2 for prefix VPN-IP1 are		o The VPN labels advertised by ePE1 and ePE2 for prefix VPN-IP1 are
	VPN-L11 and VPN-L21, respectively		VPN-L11 and VPN-L21, respectively
	o The VPN labels advertised by ePE2 and ePE3 for prefix VPN-IP2 are		o The VPN labels advertised by ePE2 and ePE3 for prefix VPN-IP2 are
	VPN-L22 and VPN-L32, respectively		VPN-L22 and VPN-L32, respectively
	o The labels advertised by ASBR11 to iPE using BGP-LU [3] for the		o The labels advertised by ASBR11 to iPE using BGP-LU [3] for the
	egress PEs ePE1 and ePE2 are LASBR11(ePE1) and LASBR11(ePE2),		egress PEs ePE1 and ePE2 are LASBR111(ePE1) and LASBR112(ePE2),
	respectively.		respectively.
	o The labels advertised by ASBR12 to iPE using BGP-LU [3] for the		o The labels advertised by ASBR12 to iPE using BGP-LU [3] for the
	egress PEs ePE1 and ePE2 are LASBR12(ePE1) and LASBR12(ePE2),		egress PEs ePE1 and ePE2 are LASBR121(ePE1) and LASBR122(ePE2),
	respectively		respectively
	o The label advertised by ASBR13 to iPE using BGP-LU [3] for the		o The label advertised by ASBR13 to iPE using BGP-LU [3] for the
	egress PE ePE3 is LASBR13(ePE3)		egress PE ePE3 is LASBR13(ePE3)
	o The IGP labels advertised by the next hops directly connected to		o The IGP labels advertised by the next hops directly connected to
	iPE towards ASBR11, ASBR12, and ASBR13 in the core of domain 1		iPE towards ASBR11, ASBR12, and ASBR13 in the core of domain 1
	are IGP-L11, IGP-L12, and IGP-L13, respectively.		are IGP-L11, IGP-L12, and IGP-L13, respectively.
			o Both the routers ASBR21 and ASBR22 of Domain 2 advertise the same
			label LASBR21 and LASBR22 to the egress PEs ePE1 and ePE2,
			respectively, to the routers ASBR11 and ASBR22 of Domain 1
			o The router ASBR23 of Domain 2 advertises the label LASBR23 for
			the egress PE ePE3 to the router ASBR13 of Domain 1
	Based on these connectivity assumptions and the topology in Figure		Based on these connectivity assumptions and the topology in Figure
	4, the routing table on iPE is		4, the routing table on iPE is
	65000: 198.51.100.0/24		65000: 198.51.100.0/24
	via ePE1 (192.0.2.1), VPN Label: VPN-L11		via ePE1 (192.0.2.1), VPN Label: VPN-L11
	via ePE2 (192.0.2.2), VPN Label: VPN-L21		via ePE2 (192.0.2.2), VPN Label: VPN-L21
	65000: 203.0.113.0/24		65000: 203.0.113.0/24
	via ePE1 (192.0.2.2), VPN Label: VPN-L22		via ePE1 (192.0.2.2), VPN Label: VPN-L22
	via ePE2 (192.0.2.3), VPN Label: VPN-L32		via ePE2 (192.0.2.3), VPN Label: VPN-L32
	192.0.2.1/32 (ePE1)		192.0.2.1/32 (ePE1)
	Via ASBR11, BGP-LU Label: LASBR11(ePE1)		Via ASBR11, BGP-LU Label: LASBR111(ePE1)
	Via ASBR12, BGP-LU Label: LASBR12(ePE1)		Via ASBR12, BGP-LU Label: LASBR121(ePE1)
	192.0.2.2/32 (ePE2)		192.0.2.2/32 (ePE2)
	Via ASBR11, BGP-LU Label: LASBR11(ePE2)		Via ASBR11, BGP-LU Label: LASBR112(ePE2)
	Via ASBR12, BGP-LU Label: LASBR12(ePE2)		Via ASBR12, BGP-LU Label: LASBR122(ePE2)
	192.0.2.3/32 (ePE3)		192.0.2.3/32 (ePE3)
	Via ASBR13, BGP-LU Label: LASBR13(ePE3)		Via ASBR13, BGP-LU Label: LASBR13(ePE3)
	192.0.2.4/32 (ASBR11)		192.0.2.4/32 (ASBR11)
	via Core, Label: IGP-L11		via Core, Label: IGP-L11
	192.0.2.5/32 (ASBR12)		192.0.2.5/32 (ASBR12)
	via Core, Label: IGP-L12		via Core, Label: IGP-L12
	192.0.2.6/32 (ASBR13)		192.0.2.6/32 (ASBR13)
	via Core, Label: IGP-L13		via Core, Label: IGP-L13
	skipping to change at page 18, line 26 ¶		skipping to change at page 18, line 26 ¶
	+-|-+-\-+ +-/-+-\-+		+-|-+-\-+ +-/-+-\-+
	| \ / \		| \ / \
	| \ / \		| \ / \
	| \ / \		| \ / \
	| \ / \		| \ / \
	v \ / \		v \ / \
	+-----+ +-----+ +-----+		+-----+ +-----+ +-----+
	+----+ ePE1| |ePE2 +-----+ | ePE3+-----+		+----+ ePE1| |ePE2 +-----+ | ePE3+-----+
	| +--+--+ +-----+ | +--+--+ |		| +--+--+ +-----+ | +--+--+ |
	v | / v | v		v | / v | v
	+-------------+ | / +-------------+ | +-------------+		+--------------+ | / +--------------+ | +-------------+
	|LASBR11(ePE1)| | / |LASBR11(ePE2)| | |LASBR13(ePE3)|		|LASBR111(ePE1)| | / |LASBR112(ePE2)| | |LASBR13(ePE3)|
	+-------------+ | / +-------------+ | +-------------+		+--------------+ | / +--------------+ | +-------------+
	|LASBR12(ePE1)| | / |LASBR12(ePE2)| | Outlabel-List		|LASBR121(ePE1)| | / |LASBR122(ePE2)| | Outlabel-List
	+-------------+ | / +-------------+ | For ePE3		+--------------+ | / +--------------+ | For ePE3
	Outlabel-List | / Outlabel-List |		Outlabel-List | / Outlabel-List |
	For ePE1 | / For ePE2 |		For ePE1 | / For ePE2 |
	| / |		| / |
	| / |		| / |
	| / |		| / |
	v / v		v / v
	+---+---+ Shared Pathlist +---+ Pathlist		+---+---+ Shared Pathlist +---+ Pathlist
	| 0 | 1 | For ePE1 and ePE2 | 0 | For ePE3		| 0 | 1 | For ePE1 and ePE2 | 0 | For ePE3
	+-|-+-\-+ +-|-+		+-|-+-\-+ +-|-+
	| \ |		| \ |
	skipping to change at page 19, line 21 ¶		skipping to change at page 19, line 21 ¶
	+------------+ +-------+ +-------+ +------------+		+------------+ +-------+ +-------+ +------------+
	| VPN-L11 |<---|VPN-IP1| | VPN-IP2|--->| VPN-L22 |		| VPN-L11 |<---|VPN-IP1| | VPN-IP2|--->| VPN-L22 |
	+------------+ +---+---+ +---+---+ +------------+		+------------+ +---+---+ +---+---+ +------------+
	| VPN-L21 | | | | VPN-L32 |		| VPN-L21 | | | | VPN-L32 |
	+------------+ | | +------------+		+------------+ | | +------------+
	| |		| |
	| |		| |
	| |		| |
	Flattened | | Flattened		Flattened | | Flattened
	pathlist V V pathlist		pathlist V V pathlist
	+===+===+ +===+===+===+ +=============+		+===+===+ +===+===+===+ +==============+
	+--------+ 0 | 1 | | 0 | 0 | 1 +---->|LASBR11(ePE2)|		+--------+ 0 | 1 | | 0 | 0 | 1 +---->|LASBR112(ePE2)|
	| +=|=+=\=+ +=/=+=/=+=\=+ +=============+		| +=|=+=\=+ +=/=+=/=+=\=+ +==============+
	v | \ / / \ |LASBR12(ePE2)|		v | \ / / \ |LASBR122(ePE2)|
	+=============+ | \ +-----+ / \ +=============+		+==============+ | \ +-----+ / \ +==============+
	|LASBR11(ePE1)| | \/ / \ |LASBR13(ePE3)|		|LASBR111(ePE1)| | \/ / \ |LASBR13(ePE3) |
	+=============+ | /\ / \ +=============+		+==============+ | /\ / \ +==============+
	|LASBR12(ePE1)| | / \ / \		|LASBR121(ePE1)| | / \ / \
	+=============+ | / \ / \		+==============+ | / \ / \
	| / \ / \		| / \ / \
	| / + + \		| / + + \
	| + | | \		| + | | \
	| | | | \		| | | | \
	v v v v \		v v v v \
	+------+ +------+ +------+		+------+ +------+ +------+
	+----|ASBR11| |ASBR12+---+ |ASBR13+---+		+----|ASBR11| |ASBR12+---+ |ASBR13+---+
	| +------+ +------+ | +------+ |		| +------+ +------+ | +------+ |
	v v v		v v v
	+-------+ +-------+ +-------+		+-------+ +-------+ +-------+
	skipping to change at page 21, line 7 ¶		skipping to change at page 21, line 7 ¶
	o Suppose the hashing by the forwarding engine picks the second		o Suppose the hashing by the forwarding engine picks the second
	path in the flattened pathlist associated with the leaf "VPN-		path in the flattened pathlist associated with the leaf "VPN-
	IP2".		IP2".
	o Because the second path has the index "0", the label "VPN-L22" is		o Because the second path has the index "0", the label "VPN-L22" is
	pushed on the packet		pushed on the packet
	o Next the forwarding engine picks the second label from the		o Next the forwarding engine picks the second label from the
	Outlabel-Array associated with the flattened pathlist. Hence the		Outlabel-Array associated with the flattened pathlist. Hence the
	next label that is pushed is "LASBR12(ePE2)"		next label that is pushed is "LASBR122(ePE2)"
	o The forwarding engine now moves to the parent of the flattened		o The forwarding engine now moves to the parent of the flattened
	pathlist corresponding to the second path. The parent is the IGP		pathlist corresponding to the second path. The parent is the IGP
	label leaf corresponding to "ASBR12"		label leaf corresponding to "ASBR12"
	o So the packet is forwarded towards the ASBR "ASBR12" and the IGP		o So the packet is forwarded towards the ASBR "ASBR12" and the IGP
	label at the top will be "L12"		label at the top will be "L12"
	Based on the above steps, a packet arriving at iPE and destined to		Based on the above steps, a packet arriving at iPE and destined to
	the prefix VPN-L22 reaches its destination as follows		the prefix VPN-L22 reaches its destination as follows
	o iPE sends the packet along the shortest path towards ASBR12 with		o iPE sends the packet along the shortest path towards ASBR12 with
	the following label stack starting from the top: {L12,		the following label stack starting from the top: {L12,
	LASBR12(ePE2), VPN-L22}.		LASBR122(ePE2), VPN-L22}.
	o The penultimate hop of ASBR12 pops the top label "L12". Hence the		o The penultimate hop of ASBR12 pops the top label "L12". Hence the
	packet arrives at ASBR12 with the label stack {LASBR12(ePE2),		packet arrives at ASBR12 with the label stack {LASBR122(ePE2),
	VPN-L22} where "LASBR12(ePE2)" is the top label.		VPN-L22} where "LASBR12(ePE2)" is the top label.
	o ASBR12 swaps "LASBR12(ePE2)" with the label "LASBR22(ePE2)",		o ASBR12 swaps "LASBR122(ePE2)" with the label "LASBR22(ePE2)",
	which is the label advertised by ASBR22 for the ePE2 (the egress		which is the label advertised by ASBR22 for the ePE2 (the egress
	PE).		PE).
	o ASBR22 receives the packet with "LASBR22(ePE2)" at the top.		o ASBR22 receives the packet with "LASBR22(ePE2)" at the top.
	o Hence ASBR22 swaps "LASBR22(ePE2)" with the IGP label for ePE2		o Hence ASBR22 swaps "LASBR22(ePE2)" with the IGP label for ePE2
	advertised by the next-hop towards ePE2 in domain 2, and sends		advertised by the next-hop towards ePE2 in domain 2, and sends
	the packet along the shortest path towards ePE2.		the packet along the shortest path towards ePE2.
	o The penultimate hop of ePE2 pops the top label. Hence ePE2		o The penultimate hop of ePE2 pops the top label. Hence ePE2
	skipping to change at page 29, line 33 ¶		skipping to change at page 29, line 33 ¶
	Special thanks to Neeraj Malhotra, Yuri Tsier for the valuable		Special thanks to Neeraj Malhotra, Yuri Tsier for the valuable
	help		help
	Special thanks to Bruno Decraene for the valuable comments		Special thanks to Bruno Decraene for the valuable comments
	This document was prepared using 2-Word-v2.0.template.dot.		This document was prepared using 2-Word-v2.0.template.dot.
	Authors' Addresses		Authors' Addresses
	Ahmed Bashandy		Ahmed Bashandy
	Cisco Systems		Arrcus
	170 West Tasman Dr, San Jose, CA 95134, USA
	Email: abashandy.ietf@gmail.com		Email: abashandy.ietf@gmail.com
	Clarence Filsfils		Clarence Filsfils
	Cisco Systems		Cisco Systems
	Brussels, Belgium		Brussels, Belgium
	Email: cfilsfil@cisco.com		Email: cfilsfil@cisco.com
	Prodosh Mohapatra		Prodosh Mohapatra
	Sproute Networks		Sproute Networks
	Email: mpradosh@yahoo.com		Email: mpradosh@yahoo.com
End of changes. 19 change blocks.
	35 lines changed or deleted		41 lines changed or added
This html diff was produced by rfcdiff 1.47. The latest version is available from http://tools.ietf.org/tools/rfcdiff/