Subject: RE: [Idr] A question on longest match

From: "john smith" <[email-masked]>
Date: Wed, 02 Jun 2004 05:53:18 +0000

Thanks Howard,

My question is more specific to the paradigm of longest match.

In most cases, we have:

(Routing protocols)-->Best 
routes_based_on_metric/prefix_size/protocol_metric/foobar-->RIB-->FIB

My question specifically is that do most vendors aggregate the entries when 
they go from the RIB to the FIB?

The problem specifically cropped up when I realised that some peers were 
sending multiple /24s (even though they were contiguous) to a node I was 
working on though the next-hop was the same.

I was wondering if there is an "aggregation" performed based on next-hop 
when putting routes into the FIB.

Of course a more pragmatic approach is ofcourse to enforce aggregation 
rather than have a prefix range propogation.

However, I assume the biggest problem is the population of the FIB and hence 
the need for prefix range filtering.

Would it not be easier, for starters, to simply aggregate routes based on 
next-hop when populating the FIB?

this would not even break the longest match method used to balance links, 
but would solve the FIB explosion problem.

-John

>From: "Howard C. Berkowitz" <[email-masked]>
>To: [email-masked]
>Subject: RE: [Idr] A question on longest match
>Date: Tue, 1 Jun 2004 14:43:01 -0400
>
>At 8:19 AM +0000 6/1/04, john smith wrote:
>>Hello Big Brother,
>>
>>It is specifically releated to BGP.
>>
>>Aggregation in non DV protocols is not a possibility unless one goes 
>>across Area/Level boundarys.
>
>Maybe I'm missing something, but I wouldn't make that claim. Hierarchical 
>topology and multiple levels are not a requirement of routing protocols. 
>Many large ISPs run very big single ISIS areas. So, there very well may not 
>be Area/Level boundaries to cross.
>
>Hierarchical information hiding MAY be a useful deployment technique in LS 
>protocols to reduce the computational load of the Dijkstra algorithm, but 
>it's perfectly reasonable and plausible to build hierarchical networks in 
>protocols as simple as RIPv1 -- start with Class C (usually private space) 
>at the edge and work up, eventually going to Class B.
>
>>
>>This is due to their inherent nature of sending advertisements of "all 
>>connected networks" to "all nodes in the same level or area".
>>
>>Now you do believe aggregation is good, do you not? I am sure you do!
>>
>>Now to further that assumption, if aggregation is good, and one was to 
>>make a forwarding device which would not do Layer 3 lookup based on the 
>>bit aligned boundaries, but on ranges, would it be considered bad or good?
>>
>>Also please let me know if this is not an item to dicuss on idr, or should 
>>the be specifically targetted to the routing-discussion mailing list? In 
>>that case I shall not cc the list further on these queries.
>>
>>--
>>(&)
>>Little John.
>>
>>>From: "John Smith" <[email-masked]>
>>>To: <[email-masked]>
>>>Subject: RE: [Idr] A question on longest match
>>>Date: Tue, 1 Jun 2004 13:43:25 +0530
>>>
>>>Is your question related to BGP or is it related to general routing
>>>(networking) principles?
>>>
>>>If its the latter then you need to start with a good book on basic
>>>networking principles (unless ofcourse i am missing your point 
>>>altogether!)
>>>and if its the latter, then it doesn't make much sense to me ! Care to
>>>elaborate?
>>>
>>>--
>>>(&)
>>>Big brother John
>>>
>>>----- Original Message -----
>>>From: "john smith" <[email-masked]>
>>>To: <[email-masked]>
>>>Sent: Tuesday, June 01, 2004 1:19 PM
>>>Subject: [Idr] A question on longest match
>>>
>>>
>>>>  Hello,
>>>>
>>>>  Is there any specific reason why the BGP algorithm relies on the 
>>>>longest
>>>>  match paradigm?
>>>>
>>>>  Is there any reason why one cannot simply propogate the "range of
>>>addresses"
>>>>  and use different metrics?
>>>>  For example one could say "address numbers 100000 - 212123 are here 
>>>>and
>>>>  212124 - 312127 are there?
>>>>
>>>>  Would this not lead to considerable reduction of the size of the
>>>forwarding
>>>>  table?
>>>>
>>>>  --
>>>>  (&)
>>>>  Little John.
>>>>
>>>>  _________________________________________________________________
>>>>  Add photos to your messages with MSN 8. Get 2 months FREE*.
>>>>  http://join.msn.com/?page=features/featuredemail
>>>>
>>>>
>>>>  _______________________________________________
>>>>  Idr mailing list
>>>>  [email-masked]
>>>>  https://www1.ietf.org/mailman/listinfo/idr
>>>>
>>>
>>
>>_________________________________________________________________
>>The new MSN 8: advanced junk mail protection and 2 months FREE* 
>>http://join.msn.com/?page=features/junkmail
>>
>>
>>_______________________________________________
>>Idr mailing list
>>[email-masked]
>>https://www1.ietf.org/mailman/listinfo/idr
>
>
>_______________________________________________
>Idr mailing list
>[email-masked]
>https://www1.ietf.org/mailman/listinfo/idr

_________________________________________________________________
Tired of spam? Get advanced junk mail protection with MSN 8. 
http://join.msn.com/?page=features/junkmail

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

---

From: Curtis Villamizar <[email-masked]>
Date: Wed, 02 Jun 2004 15:34:21 -0400

> but would solve the FIB explosion problem.

Its not worth it to aggregate the FIB.  There is very little gain if
you don't aggregate over holes.

If you aggregate over holes you'd need to include more specific reject
routes.

If you aggregate the FIB and a withdraw occurs you need to add a
reject.  You then need to be concerned about aggregating the rejects
that you are adding.

Gain is small.  There is an increase in completity.

Disallowing longest to allow automatic aggregation was discussed on
BGP, BGPD, CIDR, or CIDRD more than 10 years ago.  We didn't go that
way and its way too late to turn back.

Curtis