Subject: [RRG] getting rid of longest match

From: Iljitsch van Beijnum <[email-masked]>
Date: Mon, 25 Feb 2008 22:17:49 +0100

Hi,

After yesterday's YouTube/Pakistan Telecom debacle, I was thinking,  
not for the first time, that the longest match first rule is more  
trouble than it's worth.

I think it would probably be possible to get rid of it, although that  
would be a it tricky. The only place you really need overlapping  
prefixes in the table is your own BGP aggregate vs internal more  
specifics. But that should be solvable.

Question for the hardware people: would this help with FIB lookups?

It would certainly end this whole deaggregation for traffic  
engineering business. Although if not done carefully it could mean  
that everything goes to maximum deaggregation at once, which wouldn't  
be good. The right way to do it would be to have a fixed prefix length  
for parts of the address space. This would work especially well in IPv6.

--
to unsubscribe send a message to [email-masked] with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg

---

From: Tony Li <[email-masked]>
Date: Mon, 25 Feb 2008 14:28:43 -0800

On Feb 25, 2008, at 1:17 PM, Iljitsch van Beijnum wrote:

> I think it would probably be possible to get rid of it, although  
> that would be a it tricky. The only place you really need  
> overlapping prefixes in the table is your own BGP aggregate vs  
> internal more specifics. But that should be solvable.
>

Possibly.  It very much depends on what alternate algorithm you use  
to resolve overlap.

Tony

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Mon, 25 Feb 2008 23:33:47 +0100

> Possibly.  It very much depends on what alternate algorithm you use  

What I'm thinking is that for any given part of the address space,  
there would be a fixed prefix length. So for 192.0.0.0/8 /24, for  
64.0.0.0/8 /20, for 17.0.0.0/8 /8... So in theory, there would be no  
overlap. There could still be if the filters weren't set up properly,  
which would probably have to resolved when translating the RIB into  
the FIB.

---

From: Scott Brim <[email-masked]>
Date: Mon, 25 Feb 2008 14:43:11 -0800

On 2/25/08 2:33 PM, Iljitsch van Beijnum allegedly wrote:
>> Possibly.  It very much depends on what alternate algorithm you use to 
>> resolve overlap.
> 
> What I'm thinking is that for any given part of the address space, there 
> would be a fixed prefix length. So for 192.0.0.0/8 /24, for 64.0.0.0/8 
> /20, for 17.0.0.0/8 /8... So in theory, there would be no overlap. There 
> could still be if the filters weren't set up properly, which would 
> probably have to resolved when translating the RIB into the FIB.

Isn't this just what we did pre-CIDR?

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 26 Feb 2008 00:06:22 +0100

On 25 feb 2008, at 23:43, Scott Brim wrote:

>> 64.0.0.0/8 /20, for 17.0.0.0/8 /8... So in theory, there would be  
>> no overlap. There could still be if the filters weren't set up  
>> properly, which would probably have to resolved when translating  
>> the RIB into the FIB.

> Isn't this just what we did pre-CIDR?

Yes, except that it wouldn't be hardcoded into the IP stack but  
enforced through filters. So it could be /24 for 193.0.0.0/9 and /19  
for 193.128.0.0/9.

The issue with overlap is: which one do you choose? Longest match says  
the smallest block is the good one, but I don't think YouTube  
appreciated that logic yesterday. If we ditch longest match we need  
another rule. Allowing only one prefix size for a certain address  
range is one way to resolve this, but others are also possible. For  
instance, S-BGP or soBGP-like security mechanisms.

---

From: Danny McPherson <[email-masked]>
Date: Mon, 25 Feb 2008 19:04:09 -0700

On Feb 25, 2008, at 4:06 PM, Iljitsch van Beijnum wrote:
> The issue with overlap is: which one do you choose? Longest match  
> says the smallest block is the good one, but I don't think YouTube  

Or we just need those 'filters' you're referring to above, and leave the
protocols as is...

-danny

---

From: Tony Li <[email-masked]>
Date: Mon, 25 Feb 2008 18:06:09 -0800

On Feb 25, 2008, at 3:06 PM, Iljitsch van Beijnum wrote:

>>> What I'm thinking is that for any given part of the address  
>>> space, there would be a fixed prefix length. So for 192.0.0.0/8 / 
>>> 24, for 64.0.0.0/8 /20, for 17.0.0.0/8 /8... So in theory, there  
>>> would be no overlap. There could still be if the filters weren't  
>>> set up properly, which would probably have to resolved when  
>>> translating the RIB into the FIB.
>
> enforced through filters. So it could be /24 for 193.0.0.0/9 and / 
> 19 for 193.128.0.0/9.
>

If I understand this proposal, then for any given prefix, the entire  
net would agree on a prefix length and only propagate paths for this  
prefix length.  This would imply that there would actually be no  
required hardware change, as all of this filtering could (and should)  
happen during BGP processing (specifically during UPDATE parsing) and  
prior to RIB insertion and thus prior to the FIB insertion.

Thus, from a hardware perspective, this is largely a NOP.

Note that this could somewhat decrease the complexities of future  
hardware designs.  Since we now guarantee that there are no  
overlapping prefixes, the table now effectively forms a tree of  
variable prefix lengths, but now the first match found in the tree  
suffices.  In the grand scheme of things I would judge this not to  
have a significant impact, but it is arguably simpler.

Tony

---

From: Danny McPherson <[email-masked]>
Date: Mon, 25 Feb 2008 19:38:53 -0700

On Feb 25, 2008, at 7:06 PM, Tony Li wrote:
> required hardware change, as all of this filtering could (and  
> should) happen during BGP processing (specifically during UPDATE  
> parsing) and prior to RIB insertion and thus prior to the FIB  
> insertion.
>

Of course, this doesn't address the problem that spawned his
query, which is someone else advertising my address space.

Today this sorta happens in a reactive manner, right?  For
example:

o YouTube announces a /22
o Someone announces a /24 of that /22
o YouTube responds by announcing a /24 && /22
o YouTube still largely broken

Cisco's still announcing /24s for prefixes which this happened
to a decade ago.  The result is that things are only half broken,
not completely broken, I guess.

The problem here is simply that of a reliable authenticated
authoritative data source for who owns what - AND operators
employing that to define routing policies.  If protocols like SBGP
or soBGP want to build upon that and actually get some traction
in deployment, great, but the egg here [1] is the data source that
still doesn't exist.

[1] http://www.cnn.com/2006/TECH/science/05/26/chicken.egg/

-danny

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 26 Feb 2008 16:21:03 +1300

> [1] http://www.cnn.com/2006/TECH/science/05/26/chicken.egg/

All in all, it's hard for me to imagine a smooth path from
here to a world in which punching holes in arbitrary aggregates
isn't an unavoidable business requirement. So even if the
sort of agreement Iljitsch has in mind could be reached,
I'm certain it would contain exceptions...

   Brian

---

From: Jason Schiller <[email-masked]>
Date: Tue, 26 Feb 2008 12:02:49 -0500 (EST)

I agree with Danny.

Most large ISPs are fairly good about maintaining ALC/Prefix-lists that
only allow their customers to advertise routes for space that is correctly
swipped to them.  They know who their customer is. They know to what
company the bill is sent.  They can easily verify the name of the company
(or end user) matches the swip record for the handfull of routes the
customer advertises.

On Peering links the list is too large and changes too often, and usually
includes down stream customer ASes, and their customers and so on...  As a
result it is often difficult to validate this information and manage it.

If you want to fix this problem, ensure that all routes, the ASes that
have the right to originate those routes, and the relationship between
ASes are documented in some authoritative way, by someone who has a
relationship with the AS and can verify the accuracy before any changes
are made to the data.  

This can either be managed by the RIRs, which may be problematic due to
the excessive amount of time and cost involved in acquiring, verifying,
and keeping this data up to date, or by each and every transit provider,
which may be a problem if not all transit providers choose to set up an
Internet Routing Registry, or they do not all have the same level of
security and authentication.  

Furthermore, Not only does the information need to be accurate, but you
have to actually get the transit providers to use this information to
build ALCs/Prefix-lists on Peering points.  

__Jason

==========================================================================
Jason Schiller                                               (703)886.6648
Senior Internet Network Engineer                         fax:(703)886.0512
Public IP Global Network Engineering                       [email-masked]
UUNET / Verizon                         [email-masked]

The good news about having an email address that is twice as long is that
it increases traffic on the Internet.

---

From: [email-masked] (Sandy Murphy)
Date: Tue, 26 Feb 2008 12:37:34 -0500 (EST)

On Mon, 25 Feb 2008, Danny McPherson wrote:

> employing that to define routing policies.

And on Tue, 26 Feb 2008, Jason Schiller wrote:

>swipped to them. ...
>...
>includes down stream customer ASes, and their customers and so on...

The sidr wg is working on just such a "data source" that will provides
a strong assurance of who holds what prefixes, and therefore who is
the person to authorize origination of what prefixes.

That gives you a bit more assurance that swip for knowing what prefixes
the customer legitimately holds.  And it provides for that "and their
customer" problem, that I'm not sure gets addequately captured in
swip (does rwhois generally keep up with this as well?).

At peering points, the sidr work doesn't give you the ability to
tell if the whole AS_PATH is correct, but it would let you tell if
the peer was letting through an inappropriate origination.  And the
list could be automatically generated from the "data source" as often
as you like.  So you'd have a way to check the down stream customer ASes
and their customers and so on.

It would be really good if you thought this would be useful if you
could comment on the sidr work.

--Sandy

---

From: Per Heldal <[email-masked]>
Date: Thu, 28 Feb 2008 11:43:51 +0100

On Tue, 2008-02-26 at 00:06 +0100, Iljitsch van Beijnum wrote:
> enforced through filters. 

That  starts to sound a lot like a suggestion from Proteon related to
BGP-research in the early 90s. Their idea was that all IDRs would need
to form a "relationship" with all relevant address-authorities (now
registries) for the network within which it operates. For a DFZ-router
today that would translate into a private registry, all RIRs and IANA.
Via a simple protocol routers would be fed a list of address-blocks and
the corresponding smallest allocation block within. In today's network
that would enable dynamic rules that for example could block anything
smaller that RIR allocation-blocks globally, while permitting +n TE-bits
from neighbors. Although reasonable for recent (>2000) allocations it
may not be an answer for legacy-allocations ... and it only addresses a
small part of the problem.

//per