Subject: [savi] Does the improvement to IGP algorithms solve the false positive of uRPF?

From: Bingyang LIU <[email-masked]>
Date: Fri, 6 Jan 2012 23:50:57 -0500

Hi all,

In IETF82, there was a discussion about SAVI beyond the first hop,
especially the problems of uRPF. In the intra-domain scenario, asymmetric
routing and fast reroute can cause the false positive of uRPF.

A possible solution is to improve the IGP algorithm (link-state and
distance-vector), so that the routers can better exchange and have
sufficient information to enforce uRPF without false positive.

However, in case of static routing configured on some routers, better
exchanging link-state or distance-vector information couldn't help with the
correctness of uRPF. So essentially, what we should do is to exchange the
route decision that has already been made on each router, so that each
router has full information to enforce uRPF correctly.

In another dimension, the information should be updated frequently,
otherwise, fast re-route may cause the information on some routers
incomplete.

best
Bingyang
-- 
Bingyang Liu
Network Architecture Lab, Network Center,Tsinghua Univ.
Beijing, China
Home Page: http://netarchlab.tsinghua.edu.cn/~liuby

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sat, 07 Jan 2012 00:55:16 -0500

Attempting to improve the convergence times of routing protocols seems 
to me to be clearly out of scope for SAVI.

Yours,
Joel

On 1/6/2012 11:50 PM, Bingyang LIU wrote:
> especially the problems of uRPF. In the intra-domain scenario,
> asymmetric routing and fast reroute can cause the false positive of uRPF.
>
>
> exchanging link-state or distance-vector information couldn't help with
> the correctness of uRPF. So essentially, what we should do is to
> exchange the route decision that has already been made on each router,
> so that each router has full information to enforce uRPF correctly.
>
> _______________________________________________
> savi mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/savi

---

From: Bingyang LIU <[email-masked]>
Date: Sat, 7 Jan 2012 01:17:21 -0500

yes, but should we improve or extend the IGPs to make uRPF work better? Or
we need some other methods for intra-domain anti-spoofing?

On Sat, Jan 7, 2012 at 12:55 AM, Joel M. Halpern <[email-masked]>wrote:

> Attempting to improve the convergence times of routing protocols seems to
> me to be clearly out of scope for SAVI.
>
> Yours,
> Joel
>
>
>> Home Page: http://netarchlab.tsinghua.**edu.cn/~liuby<http://netarchlab.tsinghua.edu.cn/~liuby>
>>
>>
>> ______________________________**_________________
>> savi mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/**listinfo/savi<https://www.ietf.org/mailman/listinfo/savi>
>>
>

---

From: Fred Baker <[email-masked]>
Date: Fri, 6 Jan 2012 22:23:26 -0800

On Jan 6, 2012, at 8:50 PM, Bingyang LIU wrote:

> A possible solution is to improve the IGP algorithm (link-state and distance-vector), so that the routers can better exchange and have sufficient information to enforce uRPF without false positive. 

Agree with Joel on the scope.

That said, on the topic, I'll say what I said in the SAVI meeting at IETF 82.

With an SPF protocol, you have complete information within the area. It is as a result possible to do a reverse SPF - do an SPF calculation, but instead of using the metric going "away" from me, us the metric going "towards" me. Having done that, you know how to do uRPF for the prefixes in the area.

In a Bellman-Ford protocol, or if there is static routing, by definition there is information you don't know and can't calculate. If you don't know something, you can't make accurate predictions based on the knowledge. You can't get there from here.

Now I'll point out something that I didn't say.

One of the issues Jun Bi raised was that in ECMP implementations there is usually some upper bound on the number of routes the implementation will actually use. We might have 25 equally good ways to get from here to there; if the table structure limits us to using 8, we will use 8 of them. Same is true on the uRPF: if there are 25 ways that a packet with a given source prefix can get to me but my table structure only allows me to represent 8, I can only verify 8.

I'm all for improving anti-spoofing. This working group isn't chartered to work on it, and if it is chartered, there are known limits on the solutions that can be developed. Frankly, I would suggest that the work, if it is done, be done in the routing area.

---

From: Bingyang LIU <[email-masked]>
Date: Sat, 7 Jan 2012 01:42:29 -0500

Hi Fred,

Thanks for replying, and I agree with you that there can be limits on the
solutions. Also I think the improvement you suggested for SPF is practical.
What I'm wandering is that, can we do more and better than that? For
example, should there be some "best practice" or guidelines for
implementing anti-spoofing in the intra-domain scenario, especially when
static routing and fast re-route exist?

thanks
Bingyang

On Sat, Jan 7, 2012 at 1:23 AM, Fred Baker <[email-masked]> wrote:

> With an SPF protocol, you have complete information within the area. It is
> as a result possible to do a reverse SPF - do an SPF calculation, but
> instead of using the metric going "away" from me, us the metric going
> "towards" me. Having done that, you know how to do uRPF for the prefixes in
> the area.
>
> In a Bellman-Ford protocol, or if there is static routing, by definition
> there is information you don't know and can't calculate. If you don't know
> something, you can't make accurate predictions based on the knowledge. You
> can't get there from here.
>
> One of the issues Jun Bi raised was that in ECMP implementations there is
> usually some upper bound on the number of routes the implementation will
> actually use. We might have 25 equally good ways to get from here to there;
> if the table structure limits us to using 8, we will use 8 of them. Same is
> true on the uRPF: if there are 25 ways that a packet with a given source
> prefix can get to me but my table structure only allows me to represent 8,
> I can only verify 8.
>
> I'm all for improving anti-spoofing. This working group isn't chartered to
> work on it, and if it is chartered, there are known limits on the solutions
> that can be developed. Frankly, I would suggest that the work, if it is
> done, be done in the routing area.

---

From: "Jun Bi" <[email-masked]>
Date: Sun, 8 Jan 2012 19:01:13 +0800

Hi all,

I think there might be two ways to resolve problems:
1 One way is to try to resolve part of the problem without changing existing routing protocols (revising the algorithm of generating filtering rules should be permitted), this approach should be certainly within SAVI WG scope, like we discussed just after SAVI meeting at IETF82, having some delayed timer to trigger filtering to handle the delay of coverage. Certainly this approach has its limitation (because we limited the solution scope), but it still can improve. 
2 Another way is to resolve (more completely) by revising routing protocol, certainly needs to collaborate with routing area.

Anyway, clearly stating the problem should be a good staring point to figure out which detail solution is good for resolving which detail piece of problem, and analyzing the benefit and limitation of each piece of solution. This discussion would be worthy the SAVI meeting at IETF83.

Thanks,
Jun Bi

From: Bingyang LIU 
Sent: Saturday, January 07, 2012 2:42 PM
To: Fred Baker 
Cc: [email-masked] 
Subject: Re: [savi] Does the improvement to IGP algorithms solve the false positive of uRPF?

Hi Fred,  

Thanks for replying, and I agree with you that there can be limits on the solutions. Also I think the improvement you suggested for SPF is practical. What I'm wandering is that, can we do more and better than that? For example, should there be some "best practice" or guidelines for implementing anti-spoofing in the intra-domain scenario, especially when static routing and fast re-route exist? 

thanks
Bingyang

--------------------------------------------------------------------------------
_______________________________________________
savi mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/savi