draft-ietf-idr-bgp-analysis-06.txt		draft-ietf-idr-bgp-analysis-07.txt
	INTERNET-DRAFT D. Meyer		INTERNET-DRAFT D. Meyer
	draft-ietf-idr-bgp-analysis-06.txt K. Patel		draft-ietf-idr-bgp-analysis-07.txt K. Patel
	Category Informational		Category Informational
	Expires: February 2005 August 2004		Expires: June 2005 December 2004
	BGP-4 Protocol Analysis		BGP-4 Protocol Analysis
	<draft-ietf-idr-bgp-analysis-06.txt>		<draft-ietf-idr-bgp-analysis-07.txt>
	Status of this Memo		Status of this Memo
	Status of this Memo		Status of this Memo
	This document is an Internet-Draft and is subject to all		This document is an Internet-Draft and is subject to all
	provisions of section 3 of RFC 3667. By submitting this		provisions of section 3 of RFC 3667. By submitting this
	Internet-Draft, each author represents that any applicable patent		Internet-Draft, each author represents that any applicable patent
	or other IPR claims of which he or she is aware have been or will		or other IPR claims of which he or she is aware have been or will
	be disclosed, and any of which he or she become aware will be		be disclosed, and any of which he or she become aware will be
	disclosed, in accordance with RFC 3668.		disclosed, in accordance with RFC 3668.
	Internet-Drafts are working documents of the Internet Engineering		Internet-Drafts are working documents of the Internet
	Task Force (IETF), its areas, and its working groups. Note that		Engineering Task Force (IETF), its areas, and its working
	other groups may also distribute working documents as		groups. Note that other groups may also distribute working
	Internet-Drafts.		documents as Internet-Drafts.
	Internet-Drafts are draft documents valid for a maximum of six		Internet-Drafts are draft documents valid for a maximum of six
	months and may be updated, replaced, or obsoleted by other		months and may be updated, replaced, or obsoleted by other
	documents at any time. It is inappropriate to use		documents at any time. It is inappropriate to use
	Internet-Drafts as reference material or to cite them other than		Internet-Drafts as reference material or to cite them other
	as "work in progress."		than as "work in 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/1id-abstracts.txt.
	The list of Internet-Draft Shadow Directories can be accessed at		The list of Internet-Draft Shadow Directories can be accessed
	http://www.ietf.org/shadow.html.		at http://www.ietf.org/shadow.html.
	This document is a product of the IDR Working Group WG. Comments should be		This document is a product of the IDR Working Group
	addressed to the authors, or the mailing list at idr@ietf.org.		WG. Comments should be addressed to the authors, or the
			mailing list at idr@ietf.org.
	Copyright Notice		Copyright Notice
	Copyright (C) The Internet Society (2004). All Rights Reserved.		Copyright (C) The Internet Society (2004). All Rights Reserved.
	Abstract		Abstract
	The purpose of this report is to document how the requirements for		The purpose of this report is to document how the requirements for
	advancing a routing protocol from Draft Standard to full Standard		advancing a routing protocol from Draft Standard to full Standard
	have been satisfied by Border Gateway Protocol version 4 (BGP-4).		have been satisfied by Border Gateway Protocol version 4 (BGP-4).
	This report satisfies the requirement for "the second report", as		This report satisfies the requirement for "the second report", as
	described in Section 6.0 of [RFC1264]. In order to fulfill the		described in Section 6.0 of [RFC1264]. In order to fulfill the
	requirement, this report augments [RFC1774] and summarizes the key		requirement, this report augments [RFC1774] and summarizes the key
	features of BGP-4 protocol, and analyzes the protocol with respect to		features of BGP-4 protocol, and analyzes the protocol with respect
	scaling and performance.		to scaling and performance.
	Table of Contents		Table of Contents
	1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4		1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
	2. Key Features and algorithms of the BGP protocol. . . . . . . . 4		2. Key Features and algorithms of the BGP protocol. . . . . . . . 4
	2.1. Key Features. . . . . . . . . . . . . . . . . . . . . . . . 4		2.1. Key Features. . . . . . . . . . . . . . . . . . . . . . . . 4
	2.2. BGP Algorithms. . . . . . . . . . . . . . . . . . . . . . . 5		2.2. BGP Algorithms. . . . . . . . . . . . . . . . . . . . . . . 5
	2.3. BGP Finite State Machine (FSM). . . . . . . . . . . . . . . 6		2.3. BGP Finite State Machine (FSM). . . . . . . . . . . . . . . 6
	3. BGP Capabilities . . . . . . . . . . . . . . . . . . . . . . . 7		3. BGP Capabilities . . . . . . . . . . . . . . . . . . . . . . . 7
	4. BGP Persistent Peer Oscillations . . . . . . . . . . . . . . . 7		4. BGP Persistent Peer Oscillations . . . . . . . . . . . . . . . 7
	skipping to change at page 4, line 16		skipping to change at page 4, line 16
	BGP-4 is an inter-autonomous system routing protocol designed for		BGP-4 is an inter-autonomous system routing protocol designed for
	TCP/IP internets. Version 1 of the BGP-4 protocol was published in		TCP/IP internets. Version 1 of the BGP-4 protocol was published in
	[RFC1105]. Since then BGP versions 2, 3, and 4 have been developed.		[RFC1105]. Since then BGP versions 2, 3, and 4 have been developed.
	Version 2 was documented in [RFC1163]. Version 3 is documented in		Version 2 was documented in [RFC1163]. Version 3 is documented in
	[RFC1267]. Version 4 is documented in the [BGP4] (version 4 of BGP		[RFC1267]. Version 4 is documented in the [BGP4] (version 4 of BGP
	will hereafter be referred to as BGP). The changes between versions		will hereafter be referred to as BGP). The changes between versions
	are explained in Appendix A of [BGP4]. Possible applications of BGP		are explained in Appendix A of [BGP4]. Possible applications of BGP
	in the Internet are documented in [RFC1772].		in the Internet are documented in [RFC1772].
	BGP introduced support for Classless InterDomain Routing [CIDR].		BGP introduced support for Classless Inter-Domain Routing
	Since earlier versions of BGP lacked the support for CIDR, they are		[RFC1519]. Since earlier versions of BGP lacked the support
	considered obsolete and unusable in today's Internet.		for CIDR, they are considered obsolete and unusable in
			today's Internet.
	2. Key Features and algorithms of the BGP protocol		2. Key Features and algorithms of the BGP protocol
	This section summarizes the key features and algorithms of the BGP		This section summarizes the key features and algorithms of the
	protocol. BGP is an inter-autonomous system routing protocol; it is		BGP protocol. BGP is an inter-autonomous system routing
	designed to be used between multiple autonomous systems. BGP assumes		protocol; it is designed to be used between multiple
	that routing within an autonomous system is done by an intra-		autonomous systems. BGP assumes that routing within an
	autonomous system routing protocol. BGP also assumes that data		autonomous system is done by an intra-autonomous system
	packets are routed from source towards destination independent of the		routing protocol. BGP also assumes that data packets are
	source. BGP does not make any assumptions about intra-autonomous		routed from source towards destination independent of the
	system routing protocols deployed within the various autonomous		source. BGP does not make any assumptions about
	systems. Specifically, BGP does not require all autonomous systems to		intra-autonomous system routing protocols deployed within the
	run the same intra-autonomous system routing protocol (i.e., interior		various autonomous systems. Specifically, BGP does not require
	gateway protocol or IGP).		all autonomous systems to run the same intra-autonomous system
			routing protocol (i.e., interior gateway protocol or IGP).
	Finally, note that BGP is a real inter-autonomous system routing		Finally, note that BGP is a real inter-autonomous system
	protocol, and as such it imposes no constraints on the underlying		routing protocol, and as such it imposes no constraints on the
	interconnect topology of the autonomous systems. The information		underlying interconnect topology of the autonomous
	exchanged via BGP is sufficient to construct a graph of autonomous		systems. The information exchanged via BGP is sufficient to
	systems connectivity from which routing loops may be pruned and many		construct a graph of autonomous systems connectivity from
	routing policy decisions at the autonomous system level may be		which routing loops may be pruned and many routing policy
	enforced.		decisions at the autonomous system level may be enforced.
	2.1. Key Features		2.1. Key Features
	The key features of the protocol are the notion of path attributes		The key features of the protocol are the notion of path
	and aggregation of network layer reachability information (NLRI).		attributes and aggregation of Network Layer Reachability
			Information (NLRI).
	Path attributes provide BGP with flexibility and extensibility. Path		Path attributes provide BGP with flexibility and
	attributes are partitioned into well-known and optional. The		extensibility. Path attributes are partitioned into well-known
	provision for optional attributes allows experimentation that may		and optional. The provision for optional attributes allows
	involve a group of BGP routers without affecting the rest of the		experimentation that may involve a group of BGP routers
	Internet. New optional attributes can be added to the protocol in		without affecting the rest of the Internet. New optional
	much the same way that new options are added to, say, the Telnet		attributes can be added to the protocol in much the same way
	protocol [RFC854].		that new options are added to, say, the Telnet protocol [RFC854].
	One of the most important path attributes is the Autonomous System		One of the most important path attributes is the Autonomous
	Path, or AS_PATH. As the reachability information traverses the		System Path, or AS_PATH. As the reachability information
	Internet, this (AS_PATH) information is augmented by the list of		traverses the Internet, this (AS_PATH) information is
	autonomous systems that have been traversed thus far, forming the		augmented by the list of autonomous systems that have been
	AS_PATH. The AS_PATH allows straightforward suppression of the		traversed thus far, forming the AS_PATH. The AS_PATH allows
	looping of routing information. In addition, the AS_PATH serves as a		straightforward suppression of the looping of routing
	powerful and versatile mechanism for policy-based routing.		information. In addition, the AS_PATH serves as a powerful and
			versatile mechanism for policy-based routing.
	BGP enhances the AS_PATH attribute to include sets of autonomous		BGP enhances the AS_PATH attribute to include sets of autonomous
	systems as well as lists via the AS_SET attribute. This extended		systems as well as lists via the AS_SET attribute. This extended
	format allows generated aggregate routes to carry path information		format allows generated aggregate routes to carry path information
	from the more specific routes used to generate the aggregate. It		from the more specific routes used to generate the aggregate. It
	should be noted however, that as of this writing, AS_SETs are rarely		should be noted however, that as of this writing, AS_SETs are
	used in the Internet [ROUTEVIEWS].		rarely used in the Internet [ROUTEVIEWS].
	2.2. BGP Algorithms		2.2. BGP Algorithms
	BGP uses an algorithm that is neither a pure distance vector		BGP uses an algorithm that is neither a pure distance vector
	algorithm or a pure link state algorithm. It is instead a modified		algorithm or a pure link state algorithm. It is instead a
	distance vector algorithm referred to as a "Path Vector" algorithm		modified distance vector algorithm referred to as a "Path
	that uses path information to avoid traditional distance vector		Vector" algorithm that uses path information to avoid
	problems. Each route within BGP pairs destination with path		traditional distance vector problems. Each route within BGP
	information to that destination. Path information (also known as		pairs destination with path information to that
	AS_PATH information) is stored within the AS_PATH attribute in BGP.		destination. Path information (also known as AS_PATH
	The path information assist BGP in detecting AS loops thereby		information) is stored within the AS_PATH attribute in
	allowing BGP speakers select loop free routes.		BGP. The path information assists BGP in detecting AS loops
			thereby allowing BGP speakers select loop free routes.
	BGP uses an incremental update strategy in order to conserve		BGP uses an incremental update strategy in order to conserve
	bandwidth and processing power. That is, after initial exchange of		bandwidth and processing power. That is, after initial
	complete routing information, a pair of BGP routers exchanges only		exchange of complete routing information, a pair of BGP
	changes to that information. Such an incremental update design		routers exchanges only changes to that information. Such an
	requires reliable transport between a pair of BGP routers to function		incremental update design requires reliable transport between
	correctly. BGP solves this problem by using TCP for reliable		a pair of BGP routers to function correctly. BGP solves this
	transport. TCP further assist BGP in limiting congestion to the		problem by using TCP for reliable transport.
	advertised window limits.
	In addition to incremental updates, BGP has added the concept of		In addition to incremental updates, BGP has added the concept
	route aggregation so that information about groups of destinations		of route aggregation so that information about groups of
			destinations
	that use hierarchical address assignment (e.g., CIDR) may be		that use hierarchical address assignment (e.g., CIDR) may be
	aggregated and sent as a single Network Layer Reachability (NLRI).		aggregated and sent as a single Network Layer Reachability
			(NLRI).
	Finally, note that BGP is a self-contained protocol. That is, BGP		Finally, note that BGP is a self-contained protocol. That is,
	specifies how routing information is exchanged both between BGP		BGP specifies how routing information is exchanged both
	speakers in different autonomous systems, and between BGP speakers		between BGP speakers in different autonomous systems, and
	within a single autonomous system.		between BGP speakers within a single autonomous system.
	2.3. BGP Finite State Machine (FSM)		2.3. BGP Finite State Machine (FSM)
	The BGP FSM is a set of rules that are applied to a BGP speaker's set		The BGP FSM is a set of rules that are applied to a BGP
	of configured peers for the BGP operation. A BGP implementation		speaker's set of configured peers for the BGP operation. A BGP
	requires that a BGP speaker must connect to and listen on TCP port		implementation requires that a BGP speaker must connect to and
	179 for accepting any new BGP connections from its peers. The BGP		listen on TCP port 179 for accepting any new BGP connections
	Finite State Machine, or FSM, must be initiated and maintained for		from its peers. The BGP Finite State Machine, or FSM, must be
	each new incoming and outgoing peer connections. However, in steady		initiated and maintained for each new incoming and outgoing
	state operation, there will be only one BGP FSM per connection per		peer connections. However, in steady state operation, there
	peer.		will be only one BGP FSM per connection per peer.
	There may exist a temporary period where in a BGP peer may have		There may be a short period during which a BGP peer may have
	separate incoming and outgoing connections resulting into two		separate incoming and outgoing connections resulting in the
	different BGP FSMs for a peer (instead of one). This can be resolved		creation of two different BGP FSMs relating to a peer (instead
	following BGP connection collision rules defined in the [BGP4].		of one). This can be resolved by following the BGP connection
			collision rules defined in the [BGP4] specification.
	Following are different states of BGP FSM for its peers:		The BGP FSM has the following states associated with each of its
			peers:
	IDLE: State when BGP peer refuses any incoming		IDLE: State when BGP peer refuses any incoming
	connections.		connections.
	CONNECT: State in which BGP peer is waiting for		CONNECT: State in which BGP peer is waiting for
	its TCP connection to be completed.		its TCP connection to be completed.
	ACTIVE: State in which BGP peer is trying to acquire a		ACTIVE: State in which BGP peer is trying to acquire a
	peer by listening and accepting TCP connection.		peer by listening and accepting TCP connection.
	OPENSENT: BGP peer is waiting for OPEN message from its		OPENSENT: BGP peer is waiting for OPEN message from its
	peer.		peer.
	OPENCONFIRM: BGP peer is waiting for KEEPALIVE or NOTIFICATION		OPENCONFIRM: BGP peer is waiting for KEEPALIVE or NOTIFICATION
	message from its peer.		message from its peer.
	ESTABLISHED: BGP peer connection is established and exchanges		ESTABLISHED: BGP peer connection is established and exchanges
	UPDATE, NOTIFICATION, and KEEPALIVE messages with		UPDATE, NOTIFICATION, and KEEPALIVE messages with
	its peer.		its peer.
	There are different BGP events that operate on above mentioned states		There are an number of BGP events that operate on above
	of BGP FSM for BGP peers. These BGP events are either mandatory or		mentioned states of the BGP FSM for BGP peers. Support of
	optional. They are triggered by the protocol logic as part of the BGP		these BGP events are either mandatory or optional. They are
	or using an operator intervention via a configuration interface to		triggered by the protocol logic as part of the BGP or using an
	the BGP protocol.		operator intervention via a configuration interface to the BGP
			protocol.
	These BGP events are of following types: Optional events linked to		These BGP events are of following types: Optional events
	Optional Session attributes, Administrative Events, Timer Events,		linked to Optional Session attributes, Administrative Events,
	TCP Connection based Events, and BGP Message-based Events. Both,		Timer Events, TCP Connection based Events, and BGP
	the FSM and the BGP events are explained in details in [BGP4].		Message-based Events. Both the FSM and the BGP events are
			explained in detail in [BGP4].
	3. BGP Capabilities		3. BGP Capabilities
	The BGP Capability mechanism [RFC2842] provides an easy and flexible		The BGP Capability mechanism [RFC2842] provides an easy and flexible
	way to introduce new features within the protocol. In particular, the		way to introduce new features within the protocol. In particular, the
	BGP capability mechanism allows a BGP speaker to advertise to its		BGP capability mechanism allows a BGP speaker to advertise to its
	peers during startup various optional features supported by the		peers during startup various optional features supported by the
	speaker (and receive similar information from the peers). This allows		speaker (and receive similar information from the peers). This allows
	the base BGP protocol to contain only essential functionality, while		the base BGP protocol to contain only essential functionality, while
	at the same time providing a flexible mechanism for signaling		at the same time providing a flexible mechanism for signaling
	protocol extensions.		protocol extensions.
	4. BGP Persistent Peer Oscillations		4. BGP Persistent Peer Oscillations
	Ideally, whenever a BGP speaker detects an error in any peer		Whenever a BGP speaker detects an error in any peer connection, it
	connection, it shuts down the peer and changes its FSM state to IDLE.		shuts down the peer and changes its FSM state to IDLE. BGP speaker
	BGP speaker requires a Start event to re-initiate its idle peer		requires a Start event to re-initiate its idle peer connection. If
	connection. If the error remains persistent and BGP speaker generates		the error remains persistent and BGP speaker generates Start event
	Start event automatically then it may result in persistent peer		automatically then it may result in persistent peer flapping.
	flapping. However, although peer oscillation is found to be wide-		However, although peer oscillation is found to be wide-spread in BGP
	spread in BGP implementations, methods for preventing persistent peer		implementations, methods for preventing persistent peer oscillations
	oscillations are outside the scope of base BGP protocol		are outside the scope of base BGP protocol specification.
	specification.
	5. Implementation Guidelines		5. Implementation Guidelines
	A robust BGP implementation is work conserving. This means that if		A robust BGP implementation is work conserving. This means that if
	the number of prefixes is bound, arbitrarily high levels of route		the number of prefixes is bounded, arbitrarily high levels of route
	change can be tolerated with bounded impact on route convergence for		change can be tolerated with bounded impact on route convergence for
	occasional changes in generally stable routes.		occasional changes in generally stable routes.
	A robust implementation of BGP should have the following		A robust implementation of BGP should have the following
	characteristics:		characteristics:
	1. It is able to operate in almost arbitrarily high levels		1. It is able to operate in almost arbitrarily high levels
	of route flap without loosing peerings (failing to send		of route flap without losing peerings (failing to send
	keepalives) or loosing other protocol adjacencies as a		keepalives) or loosing other protocol adjacencies as a
	result of BGP load.		result of BGP load.
	2. Instability of a subset of routes should not affect the		2. Instability of a subset of routes should not affect the
	route advertisements or forwarding associated with the set		route advertisements or forwarding associated with the set
	of stable routes.		of stable routes.
	3. High levels of instability and peers of different CPU speed		3. High levels of instability and peers of different CPU speed
	or load resulting in faster or slower processing of routes		or load resulting in faster or slower processing of routes
	should not cause instability and should have a bounded		should not cause instability and should have a bounded
	skipping to change at page 8, line 42		skipping to change at page 9, line 4
	6.1. Link bandwidth and CPU utilization		6.1. Link bandwidth and CPU utilization
	Immediately after the initial BGP connection setup, BGP peers		Immediately after the initial BGP connection setup, BGP peers
	exchange complete set of routing information. If we denote the total		exchange complete set of routing information. If we denote the total
	number of routes in the Internet by N, the total path attributes (for		number of routes in the Internet by N, the total path attributes (for
	all N routes) received from a peer as A, and assume that the networks		all N routes) received from a peer as A, and assume that the networks
	are uniformly distributed among the autonomous systems, then the		are uniformly distributed among the autonomous systems, then the
	worst case amount of bandwidth consumed during the initial exchange		worst case amount of bandwidth consumed during the initial exchange
	between a pair of BGP speakers (P) is		between a pair of BGP speakers (P) is
	BW = O((N + A) * P)		BW = O((N + A) * P)
	BGP-4 was created specifically to reduce the size of the set of NLRI
	entries which have to be carried and exchanged by border routers.		BGP-4 was created specifically to reduce the size of the set
	The aggregation scheme, defined in [CIDR],describes the provider-		of NLRI entries which have to be carried and exchanged by
	based aggregation scheme in use in today's Internet.		border routers. The aggregation scheme, defined in [RFC1519],
			describes the provider-based aggregation scheme in use in
			today's Internet.
	Due to the advantages of advertising a few large aggregate blocks		Due to the advantages of advertising a few large aggregate blocks
	instead of many smaller class-based individual networks, it is		instead of many smaller class-based individual networks, it is
	difficult to estimate the actual reduction in bandwidth and		difficult to estimate the actual reduction in bandwidth and
	processing that BGP-4 has provided over BGP-3. If we simply		processing that BGP-4 has provided over BGP-3. If we simply
	enumerate all aggregate blocks into their individual class-based		enumerate all aggregate blocks into their individual class-based
	networks, we would not take into account "dead" space that has been		networks, we would not take into account "dead" space that has been
	reserved for future expansion. The best metric for determining the		reserved for future expansion. The best metric for determining the
	success of BGP's aggregation is to sample the number NLRI entries in		success of BGP's aggregation is to sample the number NLRI entries in
	the globally connected Internet today and compare it to projected		the globally connected Internet today and compare it to projected
	growth rates before BGP was deployed.		growth rates before BGP was deployed.
	At the time of this writing, the full set of exterior routes carried		At the time of this writing, the full set of exterior routes carried
	by BGP is approximately 134,000 network entries [ROUTEVIEWS].		by BGP is approximately 134,000 network entries [ROUTEVIEWS].
	6.1.1. CPU utilization		6.1.1. CPU utilization
	An important and fundamental feature of BGP is that BGP's CPU		An important and fundamental feature of BGP is that BGP's CPU
	utilization depends only on the stability of its network which		utilization depends only on the stability of its network which
	relates to BGP in terms of BGP UPDATE message announcments. If the		relates to BGP in terms of BGP UPDATE message announcements. If the
	BGP network is stable: all the BGP routers within its network are in		BGP network is stable: all the BGP routers within its network are in
	the steady state; then the only link bandwidth and router CPU cycles		the steady state; then the only link bandwidth and router CPU cycles
	consumed by BGP are due to the exchange of the BGP KEEPALIVE		consumed by BGP are due to the exchange of the BGP KEEPALIVE
	messages. The KEEPALIVE messages are exchanged only between peers.		messages. The KEEPALIVE messages are exchanged only between peers.
	The suggested frequency of the exchange is 30 seconds. The KEEPALIVE		The suggested frequency of the exchange is 30 seconds. The KEEPALIVE
	messages are quite short (19 octets), and require virtually no		messages are quite short (19 octets), and require virtually no
	processing. As a result, the bandwidth consumed by the KEEPALIVE		processing. As a result, the bandwidth consumed by the KEEPALIVE
	messages is about 5 bits/sec. Operational experience confirms that		messages is about 5 bits/sec. Operational experience confirms that
	the overhead (in terms of bandwidth and CPU) associated with the		the overhead (in terms of bandwidth and CPU) associated with the
	KEEPALIVE messages should be viewed as negligible.		KEEPALIVE messages should be viewed as negligible.
	During the periods of network instability, BGP routers within the		During periods of network instability, BGP routers within the network
	network are generating routing updates that are exchanged using the		are generating routing updates that are exchanged using the BGP
	BGP UPDATE messages. The greatest overhead per UPDATE message occurs		UPDATE messages. The greatest overhead per UPDATE message occurs
	when each UPDATE message contains only a single network. It should be		when each UPDATE message contains only a single network. It should be
	pointed out that in practice routing changes exhibit strong locality		pointed out that in practice routing changes exhibit strong locality
	with respect to the route attributes. That is, routes that change		with respect to the route attributes. That is, routes that change
	are likely to have common route attributes. In this case, multiple		are likely to have common route attributes. In this case, multiple
	networks can be grouped into a single UPDATE message, thus		networks can be grouped into a single UPDATE message, thus
	significantly reducing the amount of bandwidth required (see also		significantly reducing the amount of bandwidth required (see also
	Appendix F.1 of [BGP4]).		Appendix F.1 of [BGP4]).
	6.1.2. Memory requirements		6.1.2. Memory requirements
	skipping to change at page 10, line 31		skipping to change at page 10, line 32
	number of networks in the Internet will grow much faster than the		number of networks in the Internet will grow much faster than the
	average number of peers per router. As a result, BGP's memory		average number of peers per router. As a result, BGP's memory
	scaling properties are linearly related to the total number of		scaling properties are linearly related to the total number of
	networks in the Internet.		networks in the Internet.
	The following table illustrates typical memory requirements of a		The following table illustrates typical memory requirements of a
	router running BGP. We denote average number of routes advertised by		router running BGP. We denote average number of routes advertised by
	each peer as N, the total number of unique AS paths as A, the mean AS		each peer as N, the total number of unique AS paths as A, the mean AS
	distance of the Internet as M (distance at the level of an autonomous		distance of the Internet as M (distance at the level of an autonomous
	system, expressed in terms of the number of autonomous systems),		system, expressed in terms of the number of autonomous systems),
	number of bytes required to store a network as R, and number of bytes		number of octets required to store a network as R, and number of
	required to store one AS in an AS path as P. It is assumed that each		bytes required to store one AS in an AS path as P. It is assumed
	network is encoded as four bytes, each AS is encoded as two bytes,		that each network is encoded as four bytes, each AS is encoded as two
	and each networks is reachable via some fraction of all of the peers		bytes, and each networks is reachable via some fraction of all of the
	(# BGP peers/per net). For purposes of the estimates here, we will		peers (# BGP peers/per net). For purposes of the estimates here, we
	calculate MR = (((N * R) + (M * A) * P) * S).		will calculate MR = (((N * R) + (M * A) * P) * S).
	# Networks Mean AS Distance # AS's # BGP peers/per net Memory Req		# Networks Mean AS Distance # AS's # BGP peers/per net Memory Req
	(N) (M) (A) (P) (MR)		(N) (M) (A) (P) (MR)
	---------- ---------------- ------ ------------------- --------------		---------- ---------------- ------ ------------------- --------------
	100,000 20 3,000 20 10,400,000		100,000 20 3,000 20 10,400,000
	100,000 20 15,000 20 20,000,000		100,000 20 15,000 20 20,000,000
	120,000 10 15,000 100 78,000,000		120,000 10 15,000 100 78,000,000
	140,000 15 20,000 100 116,000,000		140,000 15 20,000 100 116,000,000
	In analyzing BGP's memory requirements, we focus on the size of the		In analyzing BGP's memory requirements, we focus on the size of the
	BGP RIB table (and ignoring implementation details). In particular,		BGP RIB table (ignoring implementation details). In particular, we
	we derive upper bounds for the size of the BGP RIB table. For		derive upper bounds for the size of the BGP RIB table. For example,
	example, at the time of this writing, the BGP RIB tables of a typical		at the time of this writing, the BGP RIB tables of a typical backbone
	backbone router carry on the order of 120,000 entries. Given this		router carry on the order of 120,000 entries. Given this number, one
	number, one might ask whether it would be possible to have a		might ask whether it would be possible to have a functional router
	functional router with a table that will have 1,000,000 entries.		with a table that will have 1,000,000 entries. Clearly the answer to
	Clearly the answer to this question is more related to how BGP is		this question is more related to how BGP is implemented. A robust BGP
	implemented. A robust BGP implementation with a reasonable CPU and		implementation with a reasonable CPU and memory should not have
	memory should not have issues scaling to such limits.		issues scaling to such limits.
	7. BGP Policy Expressiveness and its Implications		7. BGP Policy Expressiveness and its Implications
	BGP is unique among deployed IP routing protocols in that routing is		BGP is unique among deployed IP routing protocols in that routing is
	determined using semantically rich routing policies. Although		determined using semantically rich routing policies. Although
	routing policies are usually the first thing that comes to a network		routing policies are usually the first thing that comes to a network
	operator's mind concerning BGP, it is important to note that the		operator's mind concerning BGP, it is important to note that the
	languages and techniques for specifying BGP routing policies are not		languages and techniques for specifying BGP routing policies are not
	actually a part of the protocol specification ([RFC2622] for an		actually a part of the protocol specification ([RFC2622] for an
	example of such a policy language). In addition, the BGP		example of such a policy language). In addition, the BGP
	specification contains few restrictions, either explicitly or		specification contains few restrictions, either explicitly or
	implicitly, on routing policy languages. These languages have		implicitly, on routing policy languages. These languages have
	typically been developed by vendors and have evolved through		typically been developed by vendors and have evolved through
	interactions with network engineers in an environment lacking vendor-		interactions with network engineers in an environment lacking
	independent standards.		vendor-independent standards.
	The complexity of typical BGP configurations, at least in provider		The complexity of typical BGP configurations, at least in provider
	networks, has been steadily increasing. Router vendors typically		networks, has been steadily increasing. Router vendors typically
	provided hundreds of special commands for use in the configuration of		provide hundreds of special commands for use in the configuration of
	BGP, and this command set is continually expanding. For example, BGP		BGP, and this command set is continually expanding. For example, BGP
	communities [RFC1997] allow policy writers to selectively attach tags		communities [RFC1997] allow policy writers to selectively attach tags
	to routes and use these to signal policy information to other BGP-		to routes and use these to signal policy information to other
	speaking routers. Many providers allow customers, and sometimes		BGP-speaking routers. Many providers allow customers, and
	peers, to send communities that determine the scope and preference of		sometimes peers, to send communities that determine the scope
	their routes. These developments have more and more given the task		and preference of their routes. These developments have
	of writing BGP configurations aspects associated with open-ended		increasingly given the task of writing BGP configurations
	programming. This has allowed network operators to encode complex		aspects associated with open-ended programming. This has
	policies in order to address many unforeseen situations, and has		allowed network operators to encode complex policies in order
	opened the door for a great deal of creativity and experimentation in		to address many unforeseen situations, and has opened the door
	routing policies. This policy flexibility is one of the main reasons		for a great deal of creativity and experimentation in routing
			policies. This policy flexibility is one of the main reasons
	why BGP is so well suited to the commercial environment of the		why BGP is so well suited to the commercial environment of the
	current Internet.		current Internet.
	However, this rich policy expressiveness has come with a cost that is		However, this rich policy expressiveness has come with a cost
	often not recognized. In particular, it is possible to construct		that is often not recognized. In particular, it is possible
	locally defined routing policies that can lead to unexpected global		to construct locally defined routing policies that can lead to
	routing anomalies such as (unintended) nondeterminism and to protocol		unexpected global routing anomalies such as (unintended)
	divergence. If the interacting policies causing such anomalies are		non-determinism and to protocol divergence. If the
	defined in different autonomous systems, then these problems can be		interacting policies causing such anomalies are defined in
	very difficult to debug and correct. In the following sections, we		different autonomous systems, then these problems can be very
	describe two such cases relating to the existence (or lack thereof)		difficult to debug and correct. In the following sections, we
	of stable routings.		describe two such cases relating to the existence (or lack
			thereof) of stable routings.
	7.1. Existence of Unique Stable Routings		7.1. Existence of Unique Stable Routings
	One can easily construct sets of policies for which BGP can not		One can easily construct sets of policies for which BGP can not
	guarantee that stable routings are unique. This can be illustrated		guarantee that stable routings are unique. This can be illustrated
	by the following simple example. Consider the example of four		by the following simple example. Consider the example of four
	Autonomous Systems, AS1, AS2, AS3, and AS4. AS1 and AS2 are peers,		Autonomous Systems, AS1, AS2, AS3, and AS4. AS1 and AS2 are peers,
	and they provide transit for AS3 and AS4 respectively, Suppose		and they provide transit for AS3 and AS4 respectively, Suppose
	further that AS3 provides transit for AS4 (in this case AS3 is a		further that AS3 provides transit for AS4 (in this case AS3 is a
	customer of AS1, and AS4 is a multihomed customer of both AS3 and		customer of AS1, and AS4 is a multihomed customer of both AS3 and
	skipping to change at page 13, line 45		skipping to change at page 13, line 45
	of signaling information within and between autonomous systems than		of signaling information within and between autonomous systems than
	is possible with [RFC1997] communities. At the same time,		is possible with [RFC1997] communities. At the same time,
	applications of communities by network operators are evolving to		applications of communities by network operators are evolving to
	address complex issues of inter-domain traffic engineering.		address complex issues of inter-domain traffic engineering.
	7.2. Existence of Stable Routings		7.2. Existence of Stable Routings
	One can also construct a set of policies for which BGP can not		One can also construct a set of policies for which BGP can not
	guarantee that a stable routing exists (or worse, that a stable		guarantee that a stable routing exists (or worse, that a stable
	routing will ever be found). For example, [RFC3345] documents		routing will ever be found). For example, [RFC3345] documents
	several scenarios that lead to route oscillations associated with the		several scenarios that lead to route oscillations associated
	use of the Multi-Exit Discriminator or MED, attribute. Route		with the use of the Multi-Exit Discriminator or MED,
			attribute. Route
	oscillation will happen in BGP when a set of policies has no		oscillation will happen in BGP when a set of policies has no
	solution. That is, when there is no stable routing that satisfies		solution. That is, when there is no stable routing that satisfies
	the constraints imposed by policy, then BGP has no choice by to keep		the constraints imposed by policy, then BGP has no choice by to keep
	trying. In addition, BGP configurations can have a stable routing,		trying. In addition, BGP configurations can have a stable routing,
	yet the protocol may not be able to find it; BGP can "get trapped"		yet the protocol may not be able to find it; BGP can "get trapped"
	down a blind alley that has no solution.		down a blind alley that has no solution.
	Protocol divergence is not, however, a problem associated solely with		Protocol divergence is not, however, a problem associated solely with
	use of the MED attribute. This potential exists in BGP even without		use of the MED attribute. This potential exists in BGP even without
	the use of the MED attribute. Hence, like the unintended		the use of the MED attribute. Hence, like the unintended
	nondeterminism described in the previous section, this type of		nondeterminism described in the previous section, this type of
	protocol divergence is an unintended consequence of the unconstrained		protocol divergence is an unintended consequence of the unconstrained
	nature of BGP policy languages.		nature of BGP policy languages.
	8. Applicability		8. Applicability
	In this section we answer the question of which environments is BGP		In this section we identify the environments for which BGP well
	well suited, and for which environments it is not suitable. This		suited, and for which environments it is not suitable. This question
	question is partially answered in Section 2 of BGP [BGP4], which		is partially answered in Section 2 of BGP [BGP4], which states:
	states:
	"To characterize the set of policy decisions that can be enforced		"To characterize the set of policy decisions that can be
	using BGP, one must focus on the rule that an AS advertises to its		enforced using BGP, one must focus on the rule that an AS
	neighbor ASs only those routes that it itself uses. This rule		advertises to its neighbor ASs only those routes that it
	reflects the "hop-by-hop" routing paradigm generally used		itself uses. This rule reflects the "hop-by-hop" routing
	throughout the current Internet. Note that some policies cannot		paradigm generally used throughout the current Internet.
	be supported by the "hop-by-hop" routing paradigm and thus require		Note that some policies cannot be supported by the
	techniques such as source routing to enforce. For example, BGP		"hop-by-hop" routing paradigm and thus require techniques
	does not enable one AS to send traffic to a neighbor AS intending		such as source routing to enforce. For example, BGP does
	that the traffic take a different route from that taken by traffic		not enable one AS to send traffic to a neighbor AS
	originating in the neighbor AS. On the other hand, BGP can		intending that the traffic take a different route from
	support any policy conforming to the "hop-by-hop" routing		that taken by traffic originating in the neighbor AS. On
	paradigm. Since the current Internet uses only the "hop-by-hop"		the other hand, BGP can support any policy conforming to
	routing paradigm and since BGP can support any policy that		the "hop-by-hop" routing paradigm. Since the current
	conforms to that paradigm, BGP is highly applicable as an inter-AS		Internet uses only the "hop-by-hop" routing paradigm and
	routing protocol for the current Internet."		since BGP can support any policy that conforms to that
			paradigm, BGP is highly applicable as an inter-AS routing
			protocol for the current Internet."
	One of the important points here is that the BGP protocol contains		One of the important points here is that the BGP protocol contains
	only the functionality that is essential, while at the same time		only the functionality that is essential, while at the same time
	providing a flexible mechanism within the protocol that allow us to		providing a flexible mechanism within the protocol that allows us to
	extend its functionality. For example, BGP capabilities provide an		extend its functionality. For example, BGP capabilities provide an
	easy and flexible way to introduce new features within the protocol.		easy and flexible way to introduce new features within the protocol.
	Finally, since BGP was designed with flexibility and extensibility in		Finally, since BGP was designed with flexibility and
	mind, new and/or evolving requirements can be addressed via existing		extensibility in mind, new and/or evolving requirements can be
	mechanisms.		addressed via existing mechanisms.
	To summarize, BGP is well suitable as an inter-autonomous system		To summarize, BGP is well suited as an inter-autonomous system
	routing protocol for any internet that is based on IP [RFC791] as the		routing protocol for any internet that is based on IP [RFC791]
	internet protocol and "hop-by-hop" routing paradigm.		as the internet protocol and "hop-by-hop" routing paradigm.
	9. Acknowledgments		9. Acknowledgments
	We would like to thank Paul Traina for authoring previous versions of		We would like to thank Paul Traina for authoring previous
	this document. Tim Griffin, Randy Presuhn, Curtis Villamizar and		versions of this document. Elwyn Davies, Tim Griffin, Randy
	Atanu Ghosh also provided many insightful comments on earlier		Presuhn, Curtis Villamizar and Atanu Ghosh also provided many
	versions of this document.		insightful comments on earlier versions of this document.
	10. Security Considerations		10. Security Considerations
	BGP provides flexible mechanisms with varying levels of complexity		BGP provides flexible mechanisms with varying levels of complexity
	for security purposes. BGP sessions are authenticated using BGP		for security purposes. BGP sessions are authenticated using BGP
	session addresses and the assigned AS number. Since BGP sessions use		session addresses and the assigned AS number. Since BGP
	TCP (and IP) for reliable transport, BGP sessions are further		sessions use TCP (and IP) for reliable transport, BGP sessions
	authenticated and secured by any authentication and security		are further authenticated and secured by any authentication
	mechanisms used by TCP and IP.		and security mechanisms used by TCP and IP.
	BGP uses TCP MD5 option for validating data and protecting against		BGP uses TCP MD5 option for validating data and protecting against
	spoofing of TCP segments exhanged between its sessions. The usage of		spoofing of TCP segments exchanged between its sessions. The usage
	TCP MD5 option for BGP is described at length in [RFC 2385]. The TCP		of TCP MD5 option for BGP is described at length in [RFC 2385]. The
	MD5 Key management is discussed in [RFC 3562]. BGP data encryption is		TCP MD5 Key management is discussed in [RFC 3562]. BGP data
	provided using IPsec mechanism which encrypts the IP payload data		encryption is provided using IPsec mechanism which encrypts the IP
	(including TCP and BGP data). The IPsec mechanism can be used in		payload data (including TCP and BGP data). The IPsec mechanism can
	both, the transport mode as well as the tunnel mode. The IPsec		be used in both, the transport mode as well as the tunnel mode. The
	mechanism is described in [RFC 2406]. Both, the TCP MD5 option and		IPsec mechanism is described in [RFC 2406]. Both, the TCP MD5 option
	the IPsec mechanism are not widely deployed security mechanisms for		and the IPsec mechanism are not widely deployed security mechanisms
	BGP in today's Internet and hence it is difficult to guage their real		for BGP in today's Internet and hence it is difficult to gauge their
	performance impact when using with BGP. However, since both the		real performance impact when using with BGP. However, since both the
	mechanisms are TCP and IP based security mechanisms, the Link		mechanisms are TCP and IP based security mechanisms, the Link
	Bandwidth, CPU utilization and router memory consumed by BGP protocol		Bandwidth, CPU utilization and router memory consumed by BGP protocol
	using it would be same as any other TCP and IP based protocols.		using it would be same as any other TCP and IP based protocols.
	BGP uses IP TTL value to protect its EBGP sessions from any TCP (or		BGP uses IP TTL value to protect its External BGP (EBGP) sessions
	IP) based CPU intensive attacks. It is a simple mechanism which		from any TCP (or IP) based CPU intensive attacks. It is a simple
	suggests the use of filtering BGP (TCP) segments using the IP TTL		mechanism which suggests the use of filtering BGP (TCP) segments
	value carried within the IP header of BGP (TCP) segments exchanged		using the IP TTL value carried within the IP header of BGP (TCP)
	between the EBGP sessions. The BGP TTL mechanism is described in		segments exchanged between the EBGP sessions. The BGP TTL mechanism
	[BTSH]. Usage of [BTSH] impacts performance in a similar way as using		is described in [RFC3682]. Usage of [RFC3682] impacts performance in
	any ACL policies for BGP.		a similar way as using any ACL policies for BGP.
	Such flexible TCP and IP based security mechanisms, allow BGP to		Such flexible TCP and IP based security mechanisms, allow BGP to
	prevent insertion/deletion/modification of BGP data, any snooping of		prevent insertion/deletion/modification of BGP data, any snooping of
	the data, session stealing, etc. However, BGP is vulnerable to the		the data, session stealing, etc. However, BGP is vulnerable to the
	same security attacks that are present in TCP. The [BGP-VUL]		same security attacks that are present in TCP. The [BGP-VUL]
	explains in depth about the BGP security vulneribility. At the time		explains in depth about the BGP security vulnerability. At the time
	of this writing, several efforts are underway for creating and		of this writing, several efforts are underway for creating and
	defining an appropriate security infrastructure within the BGP		defining an appropriate security infrastructure within the BGP
	protocol to provide authentication and security for its routing		protocol to provide authentication and security for its routing
	information; some of which include [SBGP] and [SOBGP].		information; some of which include [SBGP] and [SOBGP].
	11. IANA Considerations		11. IANA Considerations
	This document presents an analysis of the BGP protocol and hence		This document presents an analysis of the BGP protocol and hence
	presents no new IANA considerations.		presents no new IANA considerations.
	12. References		12. References
	12.1. Normative References		12.1. Normative References
	[BGP4] Rekhter, Y., T. Li., and S. Hares, Editors, "A		[BGP4] Rekhter, Y., T. Li., and S. Hares, Editors, "A
	Border Gateway Protocol 4 (BGP-4)",		Border Gateway Protocol 4 (BGP-4)",
	draft-ietf-idr-bgp4-20.txt. Work in progress.		draft-ietf-idr-bgp4-2.txt. Work in progress.
	[CIDR] Fuller, V., Li, T., Yu, J., and K. Varadhan,		[RFC1519] Fuller, V., Li, T., Yu, J., and K. Varadhan,
	"Classless Inter-Domain Routing (CIDR): an Address		"Classless Inter-Domain Routing (CIDR): an Address
	Assignment and Aggregation Strategy", RFC 1519,		Assignment and Aggregation Strategy", RFC 1519,
	September, 1993.		September, 1993.
	[RFC791] "INTERNET PROTOCOL", DARPA INTERNET PROGRAM		[RFC791] "INTERNET PROTOCOL", DARPA INTERNET PROGRAM
	PROTOCOL SPECIFICATION, RFC 791, September,		PROTOCOL SPECIFICATION, RFC 791, September,
	1981.		1981.
	[RFC1997] Chandra. R, and T. Li, "BGP Communities		[RFC1997] Chandra. R, and T. Li, "BGP Communities
	Attribute", RFC 1997, August, 1996.		Attribute", RFC 1997, August, 1996.
			[RFC2385] Heffernan, A., "Protection of BGP Sessions via
			the TCP MD5 Signature Option", RFC 2385,
			August, 1998.
	[RFC2842] Chandra, R. and J. Scudder, "Capabilities		[RFC2842] Chandra, R. and J. Scudder, "Capabilities
	Advertisement with BGP-4", RFC 2842, May 2000.		Advertisement with BGP-4", RFC 2842, May 2000.
	[RFC3345] McPherson, D., Gill, V., Walton, D., and		[RFC3345] McPherson, D., Gill, V., Walton, D., and
	A. Retana, "Border Gateway Protocol (BGP) Persistent		A. Retana, "Border Gateway Protocol (BGP) Persistent
	Route Oscillation Condition", RFC 3345,		Route Oscillation Condition", RFC 3345,
	August, 2002.		August, 2002.
	[BTSH] Gill, V., Heasley, J., and D. Meyer, "The BGP TTL
	Security Hack (BTSH)", draft-gill-btsh-02.txt.
	Work in progress.
	[RFC2385] Heffernan, A., "Protection of BGP Sessions via
	the TCP MD5 Signature Option", RFC 2385,
	August, 1998.
	[RFC3562] Leech, M., "Key Management Considerations for		[RFC3562] Leech, M., "Key Management Considerations for
	the TCP MD5 Signature Option", RFC 3562,		the TCP MD5 Signature Option", RFC 3562,
	July, 2003.		July, 2003.
	[soBGP] White, R., "Architecture and Deployment Considerations for		[RFC3682] Gill, V., Heasley, J., and D. Meyer, "The
	Secure Origin BGP (soBGP)", Internet-Draft, Work in Progress.		Generalized TTL Security Mechanism (GTSM)", RFC
			3682, February, 2004.
			[SOBGP] White, R., "Architecture and Deployment
			Considerations for Secure Origin BGP (soBGP)",
			draft-white-sobgp-architecture-00.txt. Work in
			Progress.
	[BGP_VULN] Murphy, S., "BGP Security Vulnerabilities Analysis",		[BGP_VULN] Murphy, S., "BGP Security Vulnerabilities Analysis",
	draft-ietf-idr-bgp-vuln-00.txt. work in progress		draft-ietf-idr-bgp-vuln-01.txt. Work in progress
	[SBGP] Lynn, C., Mikkelson, J., and K. Seo, "Secure BGP S-BGP",		[SBGP] Lynn, C., Mikkelson, J., and K. Seo, "Secure BGP S-BGP",
	Internet-Draft, Work in Progress.		Internet-Draft, Work in Progress.
	12.2. Informative References		12.2. Informative References
	[RFC854] Postel, J. and J. Reynolds, "TELNET PROTOCOL		[RFC854] Postel, J. and J. Reynolds, "TELNET PROTOCOL
	SPECIFICATION", RFC 854, May, 1983.		SPECIFICATION", RFC 854, May, 1983.
	[RFC1105] Lougheed, K., and Y. Rekhter, "Border Gateway		[RFC1105] Lougheed, K., and Y. Rekhter, "Border Gateway
End of changes.
This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/