Subject: Re: About OSPF route flapping

From: Erblichs <[email-masked]>
Date: Wed, 4 Jan 2006 17:55:52 -0800

Group,

	yes, its verbose...

	Sorry, a week later.. Let me generalize the problem, which
	I think hasn't been said yet. In essense, find a cost that
	you can throttle some data thru that link. This is a
	dynamic load balancer based on path cost and only the
	link flap originator and the local routers next to the
	originator need this change.. :-)

	First, I see route flapping as a origination / destination
	sort of a problem. I believe that OSPF has a unique way
	of easily dealing with link unstability that should be
	independent on link type or anything else. This is link
	cost. So bear with me, why you disagree that this can't
	be fixed this way.

	My first question is the determination of a link failure?
	If it is due to hello broadcasts, then the router dead
	value should limit the amount of flapping at the other
	side of the link. If the route flap is identified at the
	origination by repeated sending of LSAs (ex:router), then
	only full neighbors need any type of work, IMO.

	If at the origination a "link" is decidely unstable, is
	their any disagreement that when the link comes up, the
	originator SHOULD advertise the link with an additionaly
	unstable penalty cost? It keeps the link available for
	no alternative routes versus doing nothing..

	However, this assumes that the originator is keeping
	some sort of link down/up/down/up history...

	Based on my experiences the penalty
	should be multiplicative in nature, so once it has
	reached a level of unstability, no routing changes
	really take place. No alternative routing will always
	and can always use the unstable link.

	Additionally, if the nbr at the other side of the
	unstable link sees excessive "router" LSAs, then
	his return cost SHOULD also add this unstable penalty
	cost.

	Also, this nbr at the other end of the adj, could
	slowly form the full adj AND only after local adj
	formation is complete, it COULD then forward the
	appropriate LSA control packets.

	BGP and OSPF are different.. BGP has TCP handshaking that
	must proceed any data transfers. It also has TCP to
	"limit" data transfer bandwidth based on percieved link
	congestion. TCP will slowly increase the available bandwidth
	each time a connection is lost and thus will effectively
	already dampen the connection as each time the link is
	dropped the link will move back into slow start. Since
	BGP will broadcast its entire routing table, the freq of
	routing table changes should be minimized. BGP also has
	the abiltiy to withdraw the link, and their link flapping
	algorithm effectively does that.

	BGP does have a local preference value and I would think
	that could be adjusted in some instances based on link
	instabliity.

	To minimize the amount of SPF/SPT work, these unstable
	routes should have secondary branches that can be
	used when they are unstable. these should be able to
	generate quick calculations.

	Mitchell Erblich
	PS: Also inline comments..
	--------------------------------

Yasuhiro Ohara wrote:
> 
> Hi Erblichs,
> 
> Here I try to respond your requests by describing my opinion
> beside what manav have told already.
> 
> Please see inline.
> 
> From: Erblichs <[email-masked]>
> Subject: Re: About OSPF route flapping
> Date: Tue, 20 Dec 2005 15:02:53 -0800
> Message-ID: <[email-masked]>
> 
> erblichs> Yasu,
> erblichs>
> erblichs>       I think I read this paper before and wanted to ask
> erblichs>       you and the group a few questions. Why are you suggesting
> erblichs>       black-holing routes and not suggesting a SIMPLER approach?
> 
> We were not suggesting black-holing, we suggest to apply BGP flap
> dampening also to OSPF events. Black-holing in the experiment
> just happened because of time lag between result of OSPF computation
> and the actual link state, and it is regarded as a bad phenomenon.
> 
> Black-holing is bad because it keep us from using alternative routes.
> We applied flap dampening so that there would be no black-holing.

	I still think that will be the result with no alternative
	routing when the link is unstable until a certain amount
	of time has PASSED and it has been stable for awhile.
> 
> erblichs>       My suggested simpler approach is #4.
> erblichs>
> erblichs>       0) Are't you effectively black-holing the route
> erblichs>          and the routers behind the "flapping link"?
> 
> Please see above. Black-holing was the bad situation resulted from
> the flapping route.

	But you can't use the link after it has become stable until
	some time has passed!!!!
> 
> erblichs>       1) If a link, route is flapping and it is a low traveled
> erblichs>          data link (almost a demand circuit) what is the harm
> erblichs>          if the link is periodicly down for short periods of
> erblichs>          time?
> erblichs>
> erblichs>       2) If the link is unstable because it is a "wireless"
> erblichs>          type link with large packet losses, won't you
> erblichs>          effectively isolate the wireless links if their
> erblichs>          are no alternative routes?
> 
> As manav have told, we can configure the threshold of how unstable
> for the link event to be dampend, and how quickly it starts to damp.
> What types of link should be dampened or not is beyond the scope
> of the paper, but I agree that on demand circuit we would not want
> to dampen the link event. On wireless the dampening feature might be
> useful, I guess.

	That threshold will NEVER (IMO) be perfect for all
	environments or the same environment with different
	configs. It will be either not agressive enough and
	have no effect or to be too agressive and dampen out
	things so the link is basicly unuseable..
> 
> Regardless of whether it is wireless or not, it is important
> if we have another alternative route to the same destination other
> than the flapping route. If we don't have any alternative, then
> the dampening should leave the link "up" against ordinary
> dampening method which would leave the link "down".
> In the paper we only investigate the case when we have a alternative
> route, so the dampening is made to leave the link as down.

	Agreed. But where you have two link paths, you COULD
	have balanced some of the load by link cost.  Also,
	you do nothing if their is no alternative route. Why
	do nothing? A percentage of paths will have no
	alternatives..
> 
> I think I don't understand what you've meant by "isolate",
> so please tell me if I am missing your point.

	Isolate, means to make unreachable. I just don't see
	in reality where an additional router is used for
	reliablity and if it goes down, nothing is effected.

> 
> erblichs>       3) If the link has random periods of instability isn't
> erblichs>          your dampening increasing the period that the link
> erblichs>          CAN'T be used?
> 
> Hmm I don't understand 'random periods of instability' ... What model
> are you mentioning precisely ?

	No specific model. Just random times that things fail or
	get overloaded and need a kick to get them restarted.
> 
> If the duration of previous up/down state is short enough compared to
> configured threshold settings, then the dampening function will
> increase the period that the link can't be used. Otherwise,
> when the previous down duration is long enough, and when the link event
> just occured is up, the link would be used immediately (dampening function
> does not effect).
> 
> erblichs>       3b) If the link has become stable after a period of
> erblichs>           unstability, won't you have an extended period of
> erblichs>           down time?
> 
> Yes, we will have an extended period of down time just after the
> unstability. That is from the nature of dampening algorithm.
> We will leave the link as down even if the link is up
> until the penalty of the link decreases as time passes.
> 
	Isn't this bad. the link is up and it can't be used!!!
	What happens if this unstability is caused by load. Won't
	you create in essense a thundering heard problem. This
	can only be fixed by THROTTING back!!!!!!!!!

> erblichs>       Maybe an upcoming Informational RFC if I FIND the time..
> erblichs>       4) WHY don't you just increment the cost of the link
> erblichs>          during periods of instability? Maybe, a demand
> erblichs>          type link that doesn't have to be up 100% of the time.
> erblichs>
> erblichs>          Yes, you have to increment the cost as the time of
> erblichs>          instability increases or assume an initial level of
> erblichs>          instability and as the link ages, decrease the link
> erblichs>          cost.
> erblichs>
> erblichs>          * Shouldn't this minimize any effects and supply
> erblichs>            as much activeness as possible?
> 
> I think increasing the link cost as the link's instability increases
> is not a good thing, because the OSPF cost of the link have totally
> different meaning in essence.
> 
> The OSPF's link cost have different measure compared to instability
> (flapping rate), so intuitively we can't explain what does it mean
> to reflect flapping rate to the OSPF cost. Reflecting flapping rate
> to the OSPF cost will result that, say, we will use the flapping link
> if the flapping duration is longer than every 3 second. Actual flapping
> rate (or duration) that we will shift to alternative route is decided
> by the alternative route's total OSPF link cost. Is that making any
> sense ? I don't think so.
> 
> The only benefit we get from manipulating OSPF cost would be
> in the discussion of "leave up or leave down". If we make OSPF cost
> as LsInfinity, it means that the link is up but almost down.
> Using LsInfinity is good, but about reflecting flapping rate to OSPF cost,
> I would disagree.

	Ok, its okay to disagree. Link cost is a measure of link
	speed, ISP's willingness to handle transit traffic, link
	latency, etc.

	I am just effectively adding a penalty to a cost ONLY IF
	the link is causing excessive REDs, excessive LSAs, 
	excessive SPF calcs, ..

	It still says that when I say the link is up, its up AND
	I don't have to worry if their is an alternative route
	because it is unstable or the type of link that it is..
	
	Thus, link cost gets me to use the alternative link IF
	IT EXISTS.

> 
> erblichs>          * As a followup, if hellos are lost and no data
> erblichs>            is pending to be sent out (must be implimented
> erblichs>            on all sides of the link), delay dropping the
> erblichs>            adj. I am assuming that the period of hellos
> erblichs>            could be too short for short periods of high
> erblichs>            levels of traffic.
> erblichs>
> erblichs>           * Followup, if just a few LSAs have been sent out
> erblichs>             this questionable link and no hellos or acks
> erblichs>             have been returned, identify whether their are
> erblichs>             any alternatives for the queued pkts. If their
> erblichs>             is drop the link, else delay dropping the link?
> 
> Why do you consider hello events ? We should consider link up/down events
> or route appearing/disappearing events, not hello events.
> We might postpone/defer link or route events, but we will not postpone
> hello events. Further, how do you detect that a Hello packet has been
> lost ? "if hellos are lost" can be detected only by timer, and it
> should mean the link down event. So we don't need to consider about
> hello event at all.

	Congestion.. If a broadcast storm was just seen, the router
	may have delayed processing all its hello packets! Since
	we assume it is an infrequent event, we just want to make
	sure that their are no pending hellos that would have kept
	it open..
> 
> erblichs>       Thus, did BGP do the right thing? It is difficult to
> erblichs>       make a quick decision because TCP will rexmit lost or
> erblichs>       non acked pkts/segments within time. And TCP will force
> erblichs>       an initial handshake before data can be sent. Plus
> erblichs>       we are on a OSPF mail alias!
> erblichs>
> erblichs>       Mitchell Erblich
> erblichs>       ---------------------------
> 
> Detecting if the packet is lost is difficult, almost impossible.
> but BGP's flap dampening does not need to detect them.
> It detect only receiving update or withdrawal, and only dampening
> if the duration is too short or rate is too high.
> TCP is not involved if the BGP packet have already been processed.
> 
> regards,
> yasu
> 
> erblichs>
> erblichs>
> erblichs>
> erblichs>
> erblichs> Yasuhiro Ohara wrote:
> erblichs> >
> erblichs> > We once checked the relation between link flapping and
> erblichs> > OSPF fixed timer. In the paper we solved that by applying
> erblichs> > dampening function similar with BGP's.
> erblichs> >
> erblichs> > http://www.sfc.wide.ad.jp/~yasu/saint2003.pdf
> erblichs> >
> erblichs> > The experiment was done by Zebra ospf6d.
> erblichs> > Unfortunately I removed the dampening code since then,
> erblichs> > because there seemed no interest.
> erblichs> >
> erblichs> > Let me know if you want further info.
> erblichs> >
> erblichs> > regards,
> erblichs> > yasu
> erblichs> >
> erblichs> > From: Kouzengjie <[email-masked]>
> erblichs> > Subject: About OSPF route flapping
> erblichs> > Date: Thu, 24 Nov 2005 15:02:18 +0800
> erblichs> >
> erblichs> > > hi,all
> erblichs> > >     How does OSPF route flapping affect?
> erblichs> > >     Is it important?
> erblichs> > >     what is the method for solving it?
> erblichs> > >
> erblichs> > > thanks,
> erblichs> > > Kou
> erblichs> > >
> erblichs>

---

From: "Joel M. Halpern" <[email-masked]>
Date: Wed, 4 Jan 2006 21:02:03 -0500

Actually,
a) this is local policy and does not need standardization
b) this is not obviously the "right" thing to do.  If the link is really 
flapping badly, the local node might well decide to advertise it as down, 
on the grounds that pretending it is useful is actually misleading.  I 
could imagine an implementation offering all sorts of knobs, if people 
really want them (I hope not.)

Given that all of the routers within a domain are presumed to have the same 
policy, it seems quite sensible to declare that the router local to the 
problem is responsible for dealing with it.
There is the argument that some mechanism would allow remote routers to 
cope with dumber local routers.  That is a complication too be avoided, as 
there are many ways for a local router to misbehave.  Second guessing 
another router in the same domain is just asking for trouble.

(The MANET situations i probably even more complicated, but remote flap 
damping does not strike me as the right answer then either.)

Yours,
Joel M. Halpern

---

From: Erblichs <[email-masked]>
Date: Thu, 5 Jan 2006 01:00:11 -0800

Joel Halpern, et al,

	First, my suggestion, past experimental implimentations
	are local to the link. Link costs are two directional
	determined by the two routers on both sides of the link.
	Since link costs are additive (directional per hop)
	only those routes that potentially pass thru those links 
	will incure those costs.

	Secondary issues is the freq of changing costs that will
	generate new SPF calcs. The below suggested link cost scenario
	SHOULD minimze repeated SPF calcs.

	Second, I know of no other ideas that in the next below
	example will not decrease the up time of the link if
	link cost is not adjusted other than to do NOTHING.

	Ex: Router A's link w.x.y.z comes up and stays up for
	about 4 minutes at a time. After that 4 minute time
	period, the link goes down for 1 minute. Their are
	routes that are only accessible via this router's
	interface. It then repeats with another 4 min up time.

	Now in this example we will know that the link is
	down after the dead router timer expires (30 secs)
	for simplicity. And immediately after the link comes
	up it will send a hello without any neighbors listed.

	So, it is down for 30 secs at the end of our up time
	before we are sure that it is down.

	We could also use router LSAs used by the originator
	after the fact on the flapping interface when it is
	back up. Or...

	What do we do?

	0) Do nothing..

	A) If we follow the BGP like implimentation and allow
	   the non origination router or the origination router
	   to delay link up status notification each time, then
	   the routes that are accessible only via this "unstable"
	   link will have less up time when it is available.
	   It is that simple. Any threshold will increase the
	   link's unavailability when too agressive and will lead
	   to repeated SPF calcs when not agressive enough.Any
	   method of route-WITH-HOLDING MUST be used by all
	   routers unless it was done at the originator.

	B) IT IS Preferable having the originator increase the cost 
	   of the link to allow routes that can transit other paths, 
	   take those other routes and those that can't be forced 
	   to rexmit or be dropped when the link is down.

	   This allows that during that 30 sec period that we aren't
	   sure that the router's link is down to use alternative routes
	   when available.

	   This also allow those routes that are only accessible
	   thru this link to have 4 minutes of up connectivity
	   every 5 minute period.

	   Since the originating router can't update the link
	   cost on this link when it is down, it is prefered that
	   some history is kept and that the next time the link
	   comes up a cost increase is implimented. My assumption
	   is that a multicative increase is best while we are
	   in periods of "instability" and slowly decrease it
	   as we become more stable over time.

	   1. if the other side of the link is aware of the
	      unstability, it can boost its link cost to allow
	      other route paths to be used for some pkts 
	      and not pushed into the router's link for the 
	      30secs that it takes to determine that the link is 
	      down.

	  2) This (boost link cost) can also be done on the router's 
	     other interfaces at the time the interface is determined
	     down. We can do this because a percentage of pkt will
	     enter one interface and be directed out towards the
	     dead interface.

	  Since only the orignator's link and the nbr's link
	  make the link cost change, this change SHOULD be completely
	  transparent and only infrequent additional LSAs are
	  re-originated with different link costs.

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