Hello everyone, my name is Thomas and I will
explain you XBGP, a new way to add flexibility
inside a routing protocol. So why is it needed to
bring programmability to a routing protocol?
Imagine yourself as being a maintainer of an
autonomous system. The current best practice
today is to have routers from different vendors.
But the problem is that you don't have a unified
interface to configure your routers. And the
second problem is that if you would like to add
a new functionality inside your network, then all
the routers must implement the functionality.
But all other routers do not implement the same
set of functionality and this is a problem.
And the other problem is that if you would like
to add a new functionality which is not
standardized
or implemented to the routers, then you need to
pass through a standardization step by the IETF.
In average for BGP, it takes 3.5 years. On the
slide, you can see the standardization delay of
all BGP features. So we measure the time since it
is released as a draft to the moment it is
released as an RFC. This is not an isolated case,
other routing protocols suffer from the same
delay, but studies have shown that this is also
the case for other RFCs. Next, you need to
implement your feature to the operating system
vendors and finally the routers must be updated.
But if you are a small network such as Belknet,
you cannot easily influence step 1 and step 2
because you don't have enough impact to actually
convince router vendors and the IETF from your
new feature. Because of those problems, we
introduced XBGP that is designed to bring
back innovation to the network operator. We would
like to open the BGP box so that the network
operator can actually modify the protocol. I will
explain you how XBGP works in practice.
We start from BGP which is considered as the
black box. You can configure BGP with multiple
interfaces, for example CLI, Netconf, or SNMP to
make some monitoring. So those are the main
interfaces to configure, but you don't have any
way to modify the protocol new as being a network
operator. XBGP will open the lid and will expose
the protocol and the protocol memory. Inside the
protocol you can add a new state, you can modify
existing states, and also you can modify the
transition between two states. Concerning the
protocol memory, you can access to the routing
table, you can also access to other internal data
structures. Now, the operator, thanks to the
interface of XBGP, can now add extension code to
their router. So they write the extension code
once, it will compile to a bytecode, and this
bytecode will be executed to all the routers
which are XBGP compatible. Now, actually, XBGP is
added on the top of operating system vendors. Now,
the routers can be seen as a kernel where you can
actually run some extension which is a
modification to your BGP protocol. Now, I will
explain you how XBGP works inside BGP, but before
I will take an example of a new feature which is
not standardized by the ITF and not implemented
inside any operating system. So what we would
like is to add the geographical localization of
the router who received the BGP update to make
some, for example, filtering or some analysis.
This information about the geographical localization
will be added to the BGP update
that will be spread to other routers of your
network, and so that other routers can use your
functionality that you have implemented. And then,
in order to not spoil the other neighbor,
you will remove your geographical localization
from the BGP update. If you would like to add
this new feature inside the BGP protocol, then
you need to think about how BGP implementation
works. Normally, all the BGP implementation
follows the RFC 4271, and inside the RFC 4271,
it explains the BGP workflow. First, you have BGP
messages that come from your peers. It will pass
to the Hedge Ribbon, then inside the import
filter. When it passes the import filter, it goes
to the
local rib. All the acceptable routes inside the
local rib will be taken to the BGP process to
take only one best route that will be pushed to
the forwarding table of the routers, and then
putting inside the export filter to check whether
or not the route can be exported to other
neighbors.
And if it is the case, it will be stored to the Hedge
Ribbon, and finally, the message will be
generated. If I take back my geographical localization
extension, you need to modify
multiple steps of the BGP protocol, and those are
represented by the blue arrows.
With XBGP, it is possible to modify the protocol
thanks to the introduction of insertion points.
Insertion points are a way to execute arbitrary
code, and so if I take up my geographical
localization, it is composed of multiple subparts,
and those subparts will be added to the right
insertion point. But that's not all, because our
extension must talk to the protocol memory to
retrieve the geographical localization, and this
is done via the XBGP API. And this is something
that makes the interaction between the plugin and
the protocol memory. Now I will explain you
the XBGP API. This is a way to communicate with
the BGP implementation, and all the extension
code or plugins must use this API to retrieve or
send some protocol memory. Why? First, because
it ensures the isolation of the plugin and the BGP
implementation, and second, it is a unified way
to
access the memory. Remember that XBGP must
support multiple BGP implementations. The XBGP
API
contains multiple functions, such as functions to
send and read BGP messages, also functions to get
or set some memory inside the protocol memory.
For example, for the geographical localization,
you must access to the geographical localization
of the router, then you use a getter function.
You have also functions to access to the routing
table and other utility functions to manipulate
the memory or doing simple math functions. So now
we have the big picture of XBGP, and I will show
you some use cases that you can do with XBGP. But
before, you need to adapt some BGP implementations
to make them XBGP compliant. We have frouting and
burn in our case. In the slide, I've put an array
with all the lines of code that you need to
modify or add to make the BGP implementation XBGP
compatible. The first use case is a simple one,
this is the monitoring, and what we would like
to do is to monitor the length of the ISPath.
Actually, it is difficult to achieve it with
traditional interface, but with XBGP, you have an
interface that is easier. Why we would like to
monitor the ISPath? For example, you would like
to monitor it to filter out large ISPath or make
analysis afterwards. So now I will explain you a
complete example of C code that represents the
XBGP expansion. First, you need to retrieve the
data from the host implementation. This is known
through get_arc() function. So this is a function
of the API. Then you will do your computation.
So here you will pass the ISPath attribute and
count the number of autonomous systems contained
inside the path. And then you will use another
function to actually log the number of AS you
computed. This extension code will be added to
the import filters. The second use case is
related to
the use of BGP inside datacenter. In datacenter,
you use BGP to make your internal routing. All
the best practice concerning the use of BGP in a
datacenter is stated in RFC 7938. Inside this
document, there is a constraint. You don't have
any zigzag path. So for example, to go from level
2 to level 0, you must go to level 1 and level 0.
But you cannot make some zigzag path between
level
2 and level 1, for example. And to avoid this zigzag
path, you must have the same autonomous
system number for all routers of the same level.
So here, level 0, all routers have the AS1 number.
But these constraints make debugging difficult.
If you would like to check where the routes are
sourced from, you cannot because all the paths
have the same autonomous system for the same
level.
And so you cannot decide if the packet goes
through the left part of the datacenter or the
right part.
But now, with XBGP, you can get rid of this
constraint and put a different autonomous
system number for the routers of the same level.
To do so, you must first design your XBGP
extension
and pass them a datacenter topology configuration.
So that you can actually check if there is any
zigzag path to your datacenter. This extension
will also be put on the insertion point related
to the import filters. The third use case is
related to the route selection. So in this slide,
we consider a stub network to the source network
connected to several transit, transit 1 and
transit
2. And to reach the network destination, XBGP
must advertise a route to the source. The source
will directly receive the green route via transit
1 and another one from transit 2. According to
the
local transit 2 policy, it will either announce
the blue or the yellow path. Maybe transit 2
choose the path for its security properties, but
the source prefers the path with a lower latency.
And so the ranking of the source and the transit
does not match. XBGP can solve the problem to
execute a plugin that will choose the route on
the edge router of transit 2 according to the
source ranking network. And so transit 2 choose
the route the source prefers. This path selection
service will be added to the decision process
insertion point. The last use case is about
detecting BGP zombies. If you know a prefix P,
then your router will announce that it can reach
in the prefix P. And the other router will do the
same by advertising to the neighbor the prefix P.
And so all the routers can reach P. But now
consider prefix P is no longer reachable. So
the router will send a withdrawal to the neighbor,
but for whatever reason, due to a software bug or
misconfiguration, the router cannot process the
withdrawal. And so it fails to send a withdrawal
to the other neighbor. The upstream router will
still have the prefix P in their forwarding table.
This is something we don't want because it may
lead to some black hole or traffic. And this is
a BGP zombie. This is a route that is still in
the theme of some routers, but no longer reachable
anymore. With XBGP, you can actually detect those
BGP zombie routes. You need to write a plugin
that
will analyze the routing table and flag all the
routes that are older than the given threshold.
Then for all those prefix, it will ask to the
upstream router to confirm if the route is still
valid or not. There are some mechanisms in BGP
such as graceful restart that can actually
reload all the entire routing table of the
neighbor. But since BGP zombie is concerning
a small fraction of prefix, according to some
measurements inside the internet, it is not
really necessary to reload all the entire routing
table. So we designed a prototype
that only asks for those BGP zombies that we
detected.
This extension code will be added to the
background task insertion pod, which acts like a
front job.
For each unit of time, you will execute this
plugin. So now we've seen some use cases that
you can do with XBGP, but the code that is
executed is untrusted. And we can ask the
following question, could it break XBGP? Well, we
need to have an automated way to verify some
properties before injecting it to the routers.
With XBGP, we make the following approach.
First, you start from the extension source code
that you will annotate, then it will be passed
to the software verification tools. And if the
verification tool says, okay, the code can be
trusted, it will be compiled to the bytecode and
then injected to the protocol. Now I will explain
you some properties that we defined that all the
plugins must satisfy before being injected to the
routers. The first one is the termination
properties. We do not want that a need-fill-it
loop, for
example, breaks the protocol. Another property is
related to the memory isolation of the plugin.
All plugins must not modify memory that are not
authorized to modify. We also restrict some
API functions to some extension code. For example,
for the monitoring, they do not have the right to
modify the protocol. Finally, we use CR, another
verification tool, to verify properties related
to the BGP syntax. As an example, we will verify
the syntax of the geographic coordinate extension.
So this geographic coordinate extension is
defined on a graph and it must follow
the format specified on this graph. And those
properties I've defined on the slide are those
that must be followed by the plugin. We write all
the properties and we annotate the plugin.
And then this annotated plugin will be passed to
the verification tool server that will say yes or
no. And if it says yes, then we are guaranteed
that all execution of the plugin will satisfy
the constraint. To conclude, with XBGP, you can
make XBGP implementation truly extensible.
If you want more details, you can read the paper
related to this presentation. We have also a
website that connects all the source code of XBGP.
We designed a methodology for BGP, but
the methodology could be also applied to other
routing protocols. Thank you.