Subject: Re: [Idr] BGP 1771 follow-on draft : Scalability,etc

From: Curtis Villamizar <[email-masked]>
Date: Tue, 01 Mar 2005 13:23:56 -0500

In message <[email-masked]>
Erblichs writes:

	Group, here are a few suggestions to this document
	that deal with scalability and minimizing convergence
	timeframes.

	6.5 Hold Timer Expired error Handling
	--------------------------------------

	A) If a situation occurs that prevents the
	reception of a KEEPALIVE at Router-B from
	Router-A, delayed or retransmitted by IP/TCP
	for UPDATES will keep the connection open...

		AND

	B) With the current situation to decrease bandwidth
	the non-transmiting of KEEPALIVES will have no
	effect as long as UPDATES are sent within the HOLD
	Timer interval

		AND
	
	C) KEEPALIVES that are incorrectly configured will
	seem to keep a connection alive as long as UPDATES
	are recieved from the same neighbor

		AND

	D) If a NOTIFICATION is recieved, since the connection
	is closed after sending it, the reciept of this forces
	the connection to stay open HOLD TIME interval longer
	without the connection being 2-way.

	Thus with the proper handling of KEEPALIVES specified
	lower in this set of suggestions, only the KEEPALIVE
	is needed to be processed to keep the connection open.

The receipt of either a KEEPALIVE or an UPDATE already resets the
keepalive timer.

	TCP / BGP Interactions
	----------------------
	Even though BGP uses TCP as its transport protocol,
	the formation of large BGP protocol packets that are
	multiple MTU sizes will force IP to fragment it into
	multiple MTU sized packets. The loss of just one
	fragment will cause the entire original large packet
	to be resent. Each fragment will be handled and
	routed independently. The over-head of fragmenting
	and then re-assembling of the packet will also
	delay reception of the packet at the BGP destination,
	due to the fact that all the fragments must be
	recieved before being handed to BGP.

Apparently you don't know how TCP works.  Only the missing TCP segment
is retransmitted if fast-retransmit and fast-recovery are implemented
(every modern TCP implementation).

TCP does not use IP fragmentation.

	Default TCP behaviour is to initially probe for bandwidth
	availablity, during what is known as slow start. This
	initial slow-start is normally set at 4 MTUs/segments.If a
	burst of TCP data is required that is greater than what
	is the current window transmit capability, the transmitter
	will wait for acknowledgements or a large timeout
	before transmitting additional data. These acknowledgements
	will come in approximate 1 round-trip time frame. 

	This situation also
	occurs after idle times, which prevents burst of data.

This is correct but we don't need a TCP tutorial in every protocol
spec that uses TCP.

	Lastly, current TCP implimentations will back-off window
	sizes, if the current applications are not using the max
	size of the transmit window. Thus is known as application
	versus network bandwidth limited.

	Thus, in some/many environments, the limiting of the size of
	a packet to within the MTU size and sending multiple full
	 header packets versus sending 1 large packet os preferable.
	This almost gurantees that packets are recieved within
	1 round trip time verus 5 or more RTTs for large fragmentated
	packets.

You need to study up a little more carefully on how TCP works.  TCP
does not use IP fragmentation.

	Neighbor Scalability
	--------------------
	(ex:Update message storm)
	Under some environments,  KEEPALIVE messages can be recieved
	and not processed within Hold Timer intervals. If these
	messages are not handled in such a way that they are
	guranteed to be processed before the timer expires,
	the neighbor adjacency will normally be dropped. One possible
	suggestion is to mark the input control packet queue
	as to the current end of the queue when the timer expires,
	and to process to that mark before processing the
	functions that deal with this timer.

	If the queue is being filled and KEEPALIVES are being dropped
	due tail-drops, then their is a small chance that a UPDATE
	from the same BGP-router as the KEEPALIVE would be present.

You need to study up a more carefully on how TCP and BGP work.

	Neighbor Flapping
	------------------
	Under some circumstances including short Hold Timers,
	neighbors may be repeatedly dropped. Any updates/routes/etc
	could/SHOULD be placed on a delay queue. A interval
	timer should be set to X and to not exceeed 2x the max
	time frame between past flaps of the neighbor. After
	this timer / time interval has passed, it is less likely 
	to flap in the near time frame.

Bad idea.

> Mitchell Erblich

Curtis

_______________________________________________
Idr mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/idr

---

From: Erblichs <[email-masked]>
Date: Tue, 01 Mar 2005 12:36:51 -0800

Group,

	I am splitting my email because of the multiple
	items being discussed.

	1) 6.5 allows KEEEPALIVES, UPDATES, and NOTIFICATIONS
	   to keep a conection alive.

	    I agree ONLY the KEEPALIVES should have this
	    functionality!!!!

	   1a) When NOTIFICATIONS are sent, the sender closes the
	   connection (at one end) after it is sent
	   as specified in 4.5.

	   Why would the other side that was about to recieve
	   the NOTIFICATION keep the other side of the
	   connection open for another HOLD TIME????

	    1b) UPDATES keep a connection open.. WHY??

	    If one end wants to make sure that a UPDATE
	    is recieved before HOLD TIME expires, then
	    send it before the HOLD TIME expires, TCP will 
	    attempt to deliver it..

	   If these are added to keep adj/peer relationships
	   during UPDATE storms, and I am probably sure they
	   are, then .....

	   a) Prioritize KEEPALIVES and insert them at the head
	      of the BGP control queue

			and/or

	   b) Create a 2nd input queue for KEEPALIVES and
	      possibly other infrequent hi-prioity packets.
	      This will not fill this input queue and cause
	      tail-drops

			and/or

	   c) Implement RED (Random Early Discard) and drop
	      without/acks the UPDATE pkts..

			and/or

	   d) Delay processing the HOLD TIMER (rare event)
	      and process the items in the input queue looking
	      for KEEPALIVES..

	  Thus, improper configuration of the value of HOLD
	  TIME will not keep the connection open AS LONG AS
	  UPDATES or NOTIFICATIONS are sent. Or other strange
	  behaviours because KEEPALIVES are no longer being
	  sent or recieved.

	   Mitchell Erblich
	-------------------------------

---

From: Curtis Villamizar <[email-masked]>
Date: Tue, 01 Mar 2005 21:24:51 -0500

> 	    I agree ONLY the KEEPALIVES should have this

You assert that only the keepalives should have this functionality.
Otherwise, who are you agreeing with?

> 	   connection open for another HOLD TIME????

That is when a CEASE NOTIFICATION is sent.  Some BGP extensions have
defined NOTIFICATION that do not close the connection.

> 	    send it before the HOLD TIME expires, TCP will 

That is because if you are getting UPDATE, or any other packet for
that matter, the connection is known to be alive.

> 	   a) Prioritize KEEPALIVES and insert them at the head

The UPDATEs and the KEEPALIVEs are on the BGP input stream which is a
TCP stream.  The BGP packets are read in order.  If BGP is bogged
down, the router is busy with AdjIn processing and may not get to the
KEEPALIVE in time on a given connection.

> 	      This will not fill this input queue and cause

There is no such thing as tail-drops on a TCP stream.  TCP provides a
guaranteed in order delivery.

> 	      without/acks the UPDATE pkts..

When TCP gets bogged down the sender packs all packets into full size
segments.  The back of one UPDATE, a KEEPALIVE, and the front of
another UPDATE are likely to be in one IP packet.  There is no way for
RED to inspect the payload to determine that there is a KEEPALIVE in
there and even if it could, TCP delivers in order packets to the
application.

> 	      and process the items in the input queue looking

That is called AdjIn processing, and the point of allowing UPDATEs to
refresh the HOLD TIMER is that if you are so busy churning through
UPDATE packets you know the TCP connection is live so why bother
looking for a KEEPALIVE to tell you that.

> 	  behaviours because KEEPALIVES are no longer being

It appears to me that you don't sufficiently understand how TCP and
BGP work which is not uncommon so don't feel bad.  This wouldn't be
the first time that someone who did not understand TCP got on the IDR
list and told us how to fix perceived problems in the BGP/TCP
interaction.  Last time it had to do with connection establishment.
If you have limited implementation experience, you really should start
with a question on the IDR list verifying with people who have worked
on deployed BGP implementations whether a specific issue exists before
asserting that it does.

At least you dropped the fragmentation argument.  Thanks.

I'll let someone else on the list give a third opinion at this point
if you insist on persisting with this.

Curtis

---

From: Erblichs <[email-masked]>
Date: Wed, 02 Mar 2005 16:52:00 -0800

Group and negative commentor,

	It is so interesting that the comments seem to
	be directed to the person, than about the
	ideas / suggestions.
	
	For those who read this (A) email, some of you
	may wonder, why suggest this change? After I
	try to be short and to the point, I will then
	address a few of the negative comments..

	A) If according to this draft that Updates
	reset the HOLD TIME interval, should this
	be an issue?

	Yes.  Lets pick a number. Say 100,000 UPDATES
	msgs per hour are recieved as a Murphy's example. 
	For each UPDATE
	recieved and processed we need to minimally
	lookup, reset, and possibly adjust the position
	of the timer item.  In this example, it will occur
	100,000 times per hour. The KEEPALIVE is a
	relatively constant infrequent message that
	should infrequently reset our HOLD TIMES. Thus,
	why spend a limited number of cycles doing
	something that can be done with less overhead.

	B) FIRST....
	If AdjIn RIB processing, etc, takes multiple
	seconds that equals or can be close to HOLD
	TIME, then their is something significantly
	broken with the implimentation.

	C) a, b, c, are frequently used in all routing
	protocols for KEEPALIVES, hellos, etc to
	make sure that the adj/peer relationship does
	not fail entirely due to a UPDATE/LSA storm.

	D) d assumes that UPDATES from one specific
	nbr/ peer are not normally sent within short 
	time intevals (hold times) and thus the
	likelyhood of finding them in the input queue
	is slight. In addition from above, why spend
	extra code doing something that doesn't
	need to be done? Since we need to process
	these messages anyway, why not process to
	a valid KEEPALIVE or mark? We are only delaying
	the teardown of the nbr/peer. It might delay
	it by 1ms or less, where our hold times are
	in secs. This should be perfectly acceptable.
	Also, d does not suggest that the normal 
	processing of packets on BGPs input queue should
	stop.
	
	E) Tail-drop is a packet behaviour that we only
	drop packets when the packet queue is FULL. 
	TCP can not prevent a queue 
	from becoming full. It can only advertise 
	what should be an acceptable window of bytes
	for the other nbr/peer/endpoint to transmit.

> guaranteed in order delivery.

	Then you need to read "End-to-End Packet Dynamics, by
	Paxson. It talks about ooo segments / packets..

	Yes, order out-of-order (ooo) packets / segments
	will NOT be recieved by the BGP application, except
	urgent data... But at the routing layer (ex:IP)
	their is no gurantee of ordered data to be recieved
	in the order it was transmitted. AND it does not
	guranantee delivery, it just makes best repeatted
	best attempts of delivery. 
	
	F) RED, Random early Discard, assumes that one
	wants to make sure that space is available
	within the input queue for the most important
	packets. The issue is not whether msg types
	can be combined; it is whether the inqueue
	msg contains a KEEPALIVE msg type. The reason
	to RED a packet is to make sure that enough
	queue space is allocated to not just one
	connection, but to all connections. If the
	BGP speaker is only concerned with one connection,
	then a RED allows a resend interval to pass
	before re-reciveing the packet.

	If we could gurantee that no-KEEPALIVES could
	be "lost" or delayed beyond HOLD TIME, the
	implementor could minimally send KEEPALIVES
	AND their would be NO NEED to suppliment the
	connection liveliness with other packets from
	the peer/nbr.

	Group, I don't expect that a thru d be incoporated
	into the draft due to the fact that a-d are
	implimentation specifics. However, it is reasonable
	to SUGGEST due to a-d that the inclusion of
	only KEEPALIVES be used to sustain a peer/nbr
	relationship.

	G)
	1a) reply..

	LASTLY, with the 26th revision of the BGP draft,
	 it does not separate out various classifications
	of NOTIFICATIONS. For those reviewers who seem NOT
	to read the draft, here is a quote from 4.5. 
	
	"A NOTIFCATION mesage is sent when an error condition
	is detected. The BGP Connection is closed immediately
	after sending it."

	This either validates the "1a" section or suggests
	a re-wording of 4.5 in the draft to incorporate
	this discreptancy and incorporate the extensions.

	Since, IMO NOTIFCATIONS are a infrequent recv'd msg
	type, the reset of the HOLD TIME SHOULD have minimal 
	extra work-load associated with it. With the same
	thought, the infrequentness of the reception of this
	msg type, should have minimal KEEPALIVE benefit.

	Enough said...

	Mitchell Erblich
	---------------------

---

From: Andrew Lee <[email-masked]>
Date: Wed, 02 Mar 2005 22:31:20 -0500

> 	address a few of the negative comments..

I think that is a fair thing to wonder about an aspect of the protocol that has 
been very stable.

> 	reset the HOLD TIME interval, should this

I don't believe so.
> 	something that can be done with less overhead.

100k UPDATEs per hour, even in the worst case of having 1 UPDATE per message 
(as you can have multiple UPDATEs per message), would only be 28 per second. 
As a worst case scenario, this isn't that big a deal.

> 	broken with the implimentation.

Don't consider it broken, just consider it a Murphy's example.

> 	not fail entirely due to a UPDATE/LSA storm.

Not all protocols can or should behave the same.  BGP serves a different 
function than OSPF and has different constraints.  Your suggestions of b and c 
confuse me as I was under the impression we were trying to *simplify* the work 
done by the router.  How are b and c less complex than simply counting UPDATES 
as KEEPALIVES?  As far as a goes, what is the mechanism that a router would use 
to move a KEEPALIVE to the head of the queue?  If the router has already 
inspected a packet enough to know that it is a KEEPALIVE, why do any further 
processing?  Again, how is this simplifying the process?

> 	processing of packets on BGPs input queue should

The purpose of a KEEPALIVE is to let a peer know that a session is active when 
the session would otherwise be idle.  I don't see any benefit in trying to 
approach this problem from the other end and try to define the usefulness of 
KEEPALIVEs for a session that is not idle.

> 	for the other nbr/peer/endpoint to transmit.

What queue are you referring to?  Interface queues?  Internal queues for 
packets awaiting processing time?

This discussion may be academically interesting, but surely you can understand 
our lack of enthusiasm at changing a mechanism that is well understood by both 
vendors and researchers to one that at first and second glance could lead to 
unnecessary session resets.

---

From: Erblichs <[email-masked]>
Date: Thu, 03 Mar 2005 12:18:38 -0800

Andrew and group,

	It is common for some Preprocessing of packets for 
	validation before being placed on the BGP queue(s). A
	check for a valid msg type is required anyway. It is
	just the additional separation of msg types so they
	can be handled as a group if wanted.  Maybe
	NOTIFICATIONS can be handled urgently if wanted, ..
	The original "1d" does nothing as long as a peer's
	HOLD TIME doesn't expire.

> packets awaiting processing.

	Internal queues for (input) packets awaiting processing.

	Depending on the implimentation, it may either
	combine msgs from different nbrs/peers or set up
	a descriptor per peer connection, or ..., and poll or
	interrupt on these descriptors for packets to be 
	recieved.

	Yes, the Murphy's example is a worst case example.
	I had to pick a large number.
	Yes, it is currently an unrealistic value for an
	hour!  However, is a one minute burst of 1,666
	unrealistic??? Isn't that 100,000 per hr?

	Their is  a rare extreme value that still
	must be handled. One must code for these rare 
	events to have a stable environment. In addition,
	we normally want to minimize the amount of work done
	frequently (assume updates at rare times are recieved
	in large numbers), if nothing else as to minimize the
	delay to finish and move on to the next task.

	We change the spec based on our ongoing knowledge
	base. That is why RFC1654 is NOT current.

	Bottom line..
	If we assume that the combined queue is full of 
	UPDATES except for a few KEEPALIVES mixed in. AND that one
	specific peer only has 1 KEEPALIVE msg towards the
	rear of the queue. 

		OR we have a large number of descriptors for a
	large number of peers/ connections.

	We have less than a sec remaining on that peer's HOLD TIME.
	Does the spec and implimentation prevent the TRANSIENT 
	loss of the adj/ nbr???

	If they don't, they SHOULD...

	Done...

	Mitchell Erblich
	--------------------

---

From: Andrew Lee <[email-masked]>
Date: Thu, 03 Mar 2005 20:41:18 -0500

Mitchell,

> 	unrealistic??? Isn't that 100,000 per hr?

I didn't say it was unrealistic.  Infact, I said 28 messages per second wasn't 
a big deal.

> 	base. That is why RFC1654 is NOT current.

No, we are changing the spec to more accurately reflect current reality.

> 	If they don't, they SHOULD...

Isn't that a good reason for UPDATEs to reset the Hold Timer, so we don't have
to wait for a KEEPALIVE if we are receiving large numbers of other messages
from a peer and therefor know its alive already?  Maybe I am missing the point
of your original proposal?  Like I said before, it seems like it is introducing
complexity in an aspect of the protocol where we want it to be as simple as
possible.

> 	Done...

You sure? ;)

---

From: Curtis Villamizar <[email-masked]>
Date: Mon, 07 Mar 2005 17:31:38 -0500

> 	If they don't, they SHOULD...

The reference used in discussions of implementation have generally
been BSD and gated since source is available for both and they are
both efficient implementations.

There is a queue of size tcp.recvspace on the receiver end and
tcp.sendspace on the sender end.  Typically its 16K-64K on each end.
Though it can be set much larger it usually is not so for the sake or
argument just consider the default settings.  A full update is 4K so
thats 4-16 full updates on either side or not more than 32 total (not
1,666).

The receiving application code (gated) does not buffer in the
application.  It processes packets as they are available on the
socket.  The sending application code also does not buffer in the
application (except to buffer half packet writes).  It does a
non-blocking write and does not attempt to write to the socket for a
BGP peer that has fallen behind, instead keeping a bit map in each
route of peers that the route update still needs to be sent to.

When the sending socket is jammed (ie: has returned EWOULDBLOCK or
EAGIAN) updates tend to be packed very full, generally to the 4K
capacity (about 500 NLRI, depending on size and number of other
attributes such as AS PATH, etc).

Since there is a maximum of 32 full size packets "in the pipe", a
keepalive is queue behind a max of 32 updates.  It could also be
behind a larger number of updates that are not as well packed.  If the
recieving end is extremely busy, it might not be able to handle the 32
or more updates, or 16K or so routes, before reaching the keepalive.
As long as it gets any sort of packet is in the socket and available
to read, the following is satisfied.

> 	Does the spec and implimentation prevent the TRANSIENT 

Updating the HOLD TIME timer is a very light weight operation with
respect to the processing that goes into handling the update itself.

So based on the experience of those who have actually written BGP code
that is deployed on high demand (service provider) networks the spec
reads the way it does.

It is possible and there is plenty of existance proof that this can be
done very efficiently.  The reference implementations are fast, use
relatively little memory, even under overloaded conditions, are work
conserving, and efficient.

If you are going to talk about nebulous "internal queues" it may be
either how you imagine things to work or some other implementation of
BGP and/or TCP.  It is possible to write highly inefficient BGP code
(and that's certainly been done before) and it is not the specs
problem if someone new has managed to do so.

So first of all - if you are talking about a specific implementation
you need to specify which one and some details on how it works since
based on your sketchy description so far it is quite different from
the reference implementation (or any major router vendor afaik).

Curtis