search

osrg / gobgp

BGP implemented in the Go Programming Language
https://osrg.github.io/gobgp/
Apache License 2.0
3.62k stars 688 forks source link

global rib <ip> longer-prefixes functionality #1006

Closed benagricola closed 8 years ago

benagricola commented 8 years ago

I've been testing out the 'longer-prefixes' route lookup today to implement a feature on my app that looks for more specific routes, but I've found some weirdness with how I was expecting the functionality to work and how it actually works in practice.

Taking an example from JunOS for example, the use of 'orlonger' on a routing policy prefix-list would mean the following:

1.2.0.0/19 orlonger would encompass:

And so on. Essentially any query for 1.2.0.0/19 orlonger would return any subnet range which fits wholly inside the given search, if specified as a min and max integer.

I've tested this in GoBGP in the following manner, by adding the below routes to the global rib:

    Network             Next Hop             AS_PATH              Age        Attrs
*>  1.2.0.0/19          1.1.1.2              xxxxx               00:06:32   [{Origin: i} {Communities: xxxxx:100}]
*>  1.2.0.0/20          1.1.1.2              xxxxx               00:06:44   [{Origin: i} {Communities: xxxxx:100}]
*>  1.2.0.0/21          1.1.1.2              xxxxx               00:06:48   [{Origin: i} {Communities: xxxxx:100}]
*>  1.2.0.0/22          1.1.1.2              xxxxx               00:07:45   [{Origin: i} {Communities: xxxxx:100}]
*>  1.2.2.0/23          1.1.1.1              xxxxx               01:41:22   [{Origin: ?} {Communities: xxxxx:100}]

I then proceed to query for all routes longer than 1.2.0.0/19:

$../gobgp -p 50051 global rib 1.2.0.0/19 longer-prefixes
    Network             Next Hop             AS_PATH              Age        Attrs
*>  1.2.0.0/19          1.1.1.2              xxxxx               00:15:16   [{Origin: i} {Communities: xxxxx:100}]
*>  1.2.0.0/20          1.1.1.2              xxxxx               00:15:28   [{Origin: i} {Communities: xxxxx:100}]
*>  1.2.0.0/21          1.1.1.2              xxxxx               00:15:32   [{Origin: i} {Communities: xxxxx:100}]
*>  1.2.0.0/22          1.1.1.2              xxxxx               00:16:29   [{Origin: i} {Communities: xxxxx:100}]

Expected behaviour would be seeing routes for 1.2.2.0/23 returned as well, since this is entirely contained within 1.2.0.0/19, but this is not the case.

From what I can ascertain from the code, the 'longer-prefixes' functionality basically takes the given address and increments the mask by 1 until reaching /32 (or IPv6 equivalent), and then does a lookup directly on the routing table - this does not work for routes which don't exactly match the original masked network that was provided (i.e. in the example, the route NLRI actually matches 1.2.0.0/<mask> exactly).

As far as I can tell, these searches are simply made against a map of <ip/mask>: destination, in GetDestination() which means a proper prefix search in this manner cannot be done.

Is the more correct way to do this to load the destinations map into a radix trie, like GetSortedDestinations() does, and then do a WalkPrefix over the trie?

I'm going to test this for my own sanity, but are there any performance implications here given that the routes appear not to be stored in a radix trie by default and must be loaded before each query?

benagricola commented 8 years ago

cd7bf4e37d1bb69d8f4dd19df7017a6e7cd48c3d contains a test implementation of WalkPrefix based searching for longer-prefixes and an implementation of shorter-prefixes using the inverse of the old longer-prefixes implementation.

This works for shorter-prefixes because we can remove more specific data from the search prefix using masking, but not for longer-prefixes because we can't add unknown data when searching for more specifics.

Any issues with the code as-is or suggestions for performance improvements?

Results of the above modifications:

$ ./gobgp/gobgp global rib
    Network             Next Hop             AS_PATH              Age        Attrs
*>  1.2.0.0/19          1.1.1.2                                   00:13:33   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.0.0/20          1.1.1.2                                   00:13:33   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.0.0/21          1.1.1.2                                   00:13:33   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.0.0/22          1.1.1.2                                   00:13:33   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.2.0/23          1.1.1.1                                   00:13:33   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.3.0/24          1.1.1.1                                   00:13:33   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]

More specific matches:

$ ./gobgp/gobgp global rib 1.2.0.0/19 longer-prefixes
    Network             Next Hop             AS_PATH              Age        Attrs
*>  1.2.0.0/19          1.1.1.2                                   00:00:12   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.0.0/20          1.1.1.2                                   00:00:12   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.0.0/21          1.1.1.2                                   00:00:12   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.0.0/22          1.1.1.2                                   00:00:12   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.2.0/23          1.1.1.1                                   00:00:12   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.3.0/24          1.1.1.1                                   00:00:12   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]

$ ./gobgp/gobgp global rib 1.2.0.0/20 longer-prefixes
    Network             Next Hop             AS_PATH              Age        Attrs
*>  1.2.0.0/20          1.1.1.2                                   00:00:17   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.0.0/21          1.1.1.2                                   00:00:17   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.0.0/22          1.1.1.2                                   00:00:17   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.2.0/23          1.1.1.1                                   00:00:17   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.3.0/24          1.1.1.1                                   00:00:17   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]

$ ./gobgp/gobgp global rib 1.2.0.0/21 longer-prefixes
    Network             Next Hop             AS_PATH              Age        Attrs
*>  1.2.0.0/21          1.1.1.2                                   00:00:19   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.0.0/22          1.1.1.2                                   00:00:19   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.2.0/23          1.1.1.1                                   00:00:19   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.3.0/24          1.1.1.1                                   00:00:19   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]

$ ./gobgp/gobgp global rib 1.2.0.0/22 longer-prefixes
    Network             Next Hop             AS_PATH              Age        Attrs
*>  1.2.0.0/22          1.1.1.2                                   00:00:21   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.2.0/23          1.1.1.1                                   00:00:21   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.3.0/24          1.1.1.1                                   00:00:21   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]

$ ./gobgp/gobgp global rib 1.2.0.0/23 longer-prefixes
Network not in table

$ ./gobgp/gobgp global rib 1.2.2.0/23 longer-prefixes
    Network             Next Hop             AS_PATH              Age        Attrs
*>  1.2.2.0/23          1.1.1.1                                   00:00:34   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
*>  1.2.3.0/24          1.1.1.1                                   00:00:34   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]

$ ./gobgp/gobgp global rib 1.2.3.0/24 longer-prefixes
    Network             Next Hop             AS_PATH              Age        Attrs
*>  1.2.3.0/24          1.1.1.1                                   00:00:50   [{Origin: i} {LocalPref: 80} {Communities: 24916:100}]
ishidawataru commented 8 years ago

@benagricola Nice! LGTM. thanks for your work. Could you gofmt server.go? Also, it might be better to split the commit into two(fix longer-prefixes, add shorter-prefixes)

benagricola commented 8 years ago

@ishidawataru Cheers! I'll gofmt, split these and submit as separate PR's when I'm back at work :)

fujita commented 8 years ago

The issue was resolved, right? If not, please reopen it.