Re: Re: BGP path hunting, MRAI timer and Path Length Damping

On Thu, 12 Jul 2007, Tony Li wrote:

> We could try, but I'm not sure that we can maintain
that information 
> accurately.  Specifically, when would we ever fill in
the field with "path 
> hunting"?

Hmm, Jakob might be right...

We don't need to maintain 'path hunting' state, we need to
maintain 
"where in the network did the withdraw start?". If
we do that, then 
we can detect subsets of the topology that must be as dead
as the 
path the withdraw is for. E.g., Geoff's example:

  http:/
/www.potaroo.net/ispcol/2007-06/fig1.jpg

5 could easily note that, given the withdrawal by 2 of 2_1,
its other 
paths of 3_2_1 and 4_3_2_1 all go through 2 - and just
avoid/defer 
picking those as new best-paths.

This doesn't work if the failure is once (or more) removed,
or for 
more complex cycles, e.g.:

          |
          |
      5---6-
     /   /  
  1-2-3-4  9  E
  |      /  /
  |   7--8  /
  A--B--C--D

6 has:

   1_2_5
   1_2_3_4
   1_2_7_8_9
   1_A_B_C_D_E

If 1-2 fails, then 6 should get successive withdraws. It
can't 
immediately tell where the failure occured. On the second
withdraw, 
it could, by comparison, note that 1_2 is common, and
theorise that 
the other paths with 1_2 in the path have a higher
probability of 
imminent withdrawal than the 1_A_B_C_D_E path.

That's still heuristics though, and a more complicated
version of 3.4 
'path length damping' from your stability draft.

However, we could allow 6 to determine with /certainty/, if
we had 
some kind of transitive Withdraw-Originater-AS attribute.
With such:

- 1_2 fails
- 2 starts sending withdraws to 5, 3 and 7, each marked
with
   some "AS2 started this.."
- 6 receives a withdraw (from 5, 4 or 9, matters not which)
- 6 starts best-path selection, taking the
withdraw-originator into
   account
     - each path containing AS2 it can discount
     - leaving it to pick 1_A_B_C_D_E


I.e. use the AS_PATH to do what it's there for - detect
cycles ;). 
(just on the withdraw side). ;)

(there'd be some additional details to take care of in the
above 
scheme obviously..)

regards,
-- 
Paul Jakma	paulclubi.ie	pauljakma.org	Key ID: 64A2FF6A
Fortune:
Bad cafeteria food landed all the sysadmins in the
hospital.

_______________________________________________
Idr mailing list
Idrietf.org
https://ww
w1.ietf.org/mailman/listinfo/idr

Paul Jakma wrote:
> On Thu, 12 Jul 2007, Tony Li wrote:
> 
>> We could try, but I'm not sure that we can maintain
that information 
>> accurately.  Specifically, when would we ever fill
in the field with 
>> "path hunting"?
> 
> Hmm, Jakob might be right...
> 
> We don't need to maintain 'path hunting' state, we need
to maintain 
> "where in the network did the withdraw
start?". If we do that, then we 
> can detect subsets of the topology that must be as dead
as the path the 
> withdraw is for. E.g., Geoff's example:
> 
>  http:/
/www.potaroo.net/ispcol/2007-06/fig1.jpg
> 
> 5 could easily note that, given the withdrawal by 2 of
2_1, its other 
> paths of 3_2_1 and 4_3_2_1 all go through 2 - and just
avoid/defer 
> picking those as new best-paths.

defer, not avoid - it may be that AS2 may have withdrawn the
routing due 
to a policy change with respect to AS5 rather than the
commencement of a 
path exploration leading to withdrawal.

There have been a number of proposals I've seen in the
literature on 
this topic that attempt to address Jakob's desire to
explicitly mark the 
"path exploration" phase. The "this is a
withdrawal at origin" flag 
appears to be a common thread, where a withdrawal is
intended to be 
marked with a flag that says "this origin is pulling
this prefix, don't 
listen to path exploration updates as all hope is already
lost!" In 
response to this flag a bgp speak upon receiving such a
flagged 
withdrawal would not advertise any withdrawal-triggered
updates. 
Variants of this propose a flag to say "this AS path
pair of origin and 
nexthop is dead - no not use any adj-rib entry that includes
this path 
pair for this prefix"

This explicit flagging would be more effective than
attempting to second 
guess what is a path exploration update sequence, but there
are likely 
some further considerations with the approach of explicit
flagging of 
such events.

- Its a change to all BGP deployments to be effective, not
just a local 
change to the way in which updates are interpreted. By no
means a major 
concern, but it does imply some morphing of the BGP spec to
apply some 
transitive attribute to withdrawals that are essentially not
in the spec 
at the moment.

- While there are relatively simple topologies where this
information of 
"complete withdrawal at source" is accessible,
more complex topologies 
are tougher for a BGP speaker to determine whether to set
such a flag or 
not. If thats the case then such explicit flagging of
withdrawal "type" 
would only be present some of the time, leaving the issue of
passive 
detection and damping of path exploration updates as one
that would have 
some leverage in reducing the BGP update load.

I suspect that there is still a valid case for the passive
detection of 
path exploration update detection using the relatively
simple heuristic 
of detecting sequences of update messages where the common 
characteristic is a) closely coupled in time, b) refer to
the same 
prefix, c) refer to the same origin AS, and d) contain AS
path vectors 
of increasing length.

I also suspect (but I'm not convinced as yet) that a
mechanism of 
deferral of further propagation of such detected updates
could be a 
reasonable replacement for both route flap damping and the
MRAI timer in 
BGP, given that both these mechanisms were similarly
motivated by a 
desire to suppress the update load associated with the
behaviour of 
distance vector algorithms in the face of a withdrawal. I
should add 
however that this last suspicion (of potentially using this
instead of 
MRAI and RFD) is pretty speculative, and the work I've done
recently in 
looking at this used an approach of placing this detection
on top of 
existing MRAI behaviour, so its not a case of have to use
one or the 
other - both is a possible as well.

   Geoff










_______________________________________________
Idr mailing list
Idrietf.org
https://ww
w1.ietf.org/mailman/listinfo/idr

Hi,Paul:

The question is at some AS, a withdrawal message will stop
propagating and it will be replaced by a new route
advertisement if there is an alternate route available, in
other words, the original route is withdrawn implicitly. It
is this implicit withdrawal that blurs the difference
between a withdrawal due to a real topology change (link
down etc) and a state transition due to local route-chosen
policy or reconfiguration of route policies. It is difficult
to distinghish them. As I see, only the AS adjacent to the
failed link can identify a real reason caused to its flap.

Best,
Michael 


----- Original Message ----- 
From: "Paul Jakma" <paulclubi.ie>
To: "Tony Li" <tlicisco.com>
Cc: "idr" <idrietf.org>
Sent: Friday, July 13, 2007 2:18 AM
Subject: Re: [Idr] Re: BGP path hunting, MRAI timer and Path
Length Damping


> On Thu, 12 Jul 2007, Tony Li wrote:
> 
>> We could try, but I'm not sure that we can maintain
that information 
>> accurately.  Specifically, when would we ever fill
in the field with "path 
>> hunting"?
> 
> Hmm, Jakob might be right...
> 
> We don't need to maintain 'path hunting' state, we need
to maintain 
> "where in the network did the withdraw
start?". If we do that, then 
> we can detect subsets of the topology that must be as
dead as the 
> path the withdraw is for. E.g., Geoff's example:
> 
>  http:/
/www.potaroo.net/ispcol/2007-06/fig1.jpg
> 
> 5 could easily note that, given the withdrawal by 2 of
2_1, its other 
> paths of 3_2_1 and 4_3_2_1 all go through 2 - and just
avoid/defer 
> picking those as new best-paths.
> 
> This doesn't work if the failure is once (or more)
removed, or for 
> more complex cycles, e.g.:
> 
>          |
>          |
>      5---6-
>     /   /  
>  1-2-3-4  9  E
>  |      /  /
>  |   7--8  /
>  A--B--C--D
> 
> 6 has:
> 
>   1_2_5
>   1_2_3_4
>   1_2_7_8_9
>   1_A_B_C_D_E
> 
> If 1-2 fails, then 6 should get successive withdraws.
It can't 
> immediately tell where the failure occured. On the
second withdraw, 
> it could, by comparison, note that 1_2 is common, and
theorise that 
> the other paths with 1_2 in the path have a higher
probability of 
> imminent withdrawal than the 1_A_B_C_D_E path.
> 
> That's still heuristics though, and a more complicated
version of 3.4 
> 'path length damping' from your stability draft.
> 
> However, we could allow 6 to determine with
/certainty/, if we had 
> some kind of transitive Withdraw-Originater-AS
attribute. With such:
> 
> - 1_2 fails
> - 2 starts sending withdraws to 5, 3 and 7, each marked
with
>   some "AS2 started this.."
> - 6 receives a withdraw (from 5, 4 or 9, matters not
which)
> - 6 starts best-path selection, taking the
withdraw-originator into
>   account
>     - each path containing AS2 it can discount
>     - leaving it to pick 1_A_B_C_D_E
> 
> 
> I.e. use the AS_PATH to do what it's there for - detect
cycles ;). 
> (just on the withdraw side). ;)
> 
> (there'd be some additional details to take care of in
the above 
> scheme obviously..)
> 
> regards,
> -- 
> Paul Jakma paulclubi.ie pauljakma.org Key ID: 64A2FF6A
> Fortune:
> Bad cafeteria food landed all the sysadmins in the
hospital.
> 
> _______________________________________________
> Idr mailing list
> Idrietf.org
> https://ww
w1.ietf.org/mailman/listinfo/idr
>

_______________________________________________
Idr mailing list
Idrietf.org
https://ww
w1.ietf.org/mailman/listinfo/idr

In message <Pine.LNX.4.64.0707121849170.5529localhost.localdomain>
Paul Jakma writes:
>  
>   http:/
/www.potaroo.net/ispcol/2007-06/fig1.jpg
>  
> 5 could easily note that, given the withdrawal by 2 of
2_1, its other 
> paths of 3_2_1 and 4_3_2_1 all go through 2 - and just
avoid/defer 
> picking those as new best-paths.


Ignoring the fact that this means saving AS Path information
for
withdrawn routes ...

What about if AS2 made a policy change and decided not to
announce to
AS5, rather than AS2 lost the route.  How long would you
suppress any
and all alternates that went through AS1-AS2?

Curtis

_______________________________________________
Idr mailing list
Idrietf.org
https://ww
w1.ietf.org/mailman/listinfo/idr