Subject: grow: The impact of BGP extensions

From: Pedro Roque Marques <[email-masked]>
Date: Thu, 4 Mar 2004 01:13:34 -0800 (PST)

Given the present debate regarding RIFT, and BGP implementations in
particular, i'd like to contribute my personal impressions on the
subject.

Althought i recognise that the topic is highly subjective, the
following is an attempt to analyse subcomponents of a BGP
implementation, as i see the problem. 

Roughly, one can attempt to decompose a BGP implementation in the
following parts:

1. Configuration management and UI.
2. Session state machine and adjacency maintenance (keepalives).
3. Input processing (message decoding).
4. Route resolution (i.e. IGP metric determination).
5. Loc-Rib handling (path selection; instalation of routes in
forwarding tables).
6. Generation of UPDATEs (i.e. database synchronization between
peers).
7. Infrastructure glue that links the protocol implementation to the
rest of the system. (e.g.: TCP sockets, interface up/down, regex and
policy libraries, synchronization w/ other components).

Of all these items, the last one tends to be the one that is harder to
discuss in terms of complexity, as it differs quite significantly
between implementations. In contrast w/ the other parts which have its
functionality more or less dictated by the protocol specification, the
tasks performed by this "infrastructure glue" module are determined by
system design which is less standard by definition.

Thus, i would like to leave this bit out of this analysis, which is
intended to be implementation independent. But not without noting that
this is quite often one of the most challenging areas to maintain, in
order to fix problems or expand functionality. The main reason being
that it is often very hard to track dependencies between different
applications (protocols) that use a given infrastructure functionality
that is being changed.

Having identified 6 areas lets attempt to analyse them in terms
of complexity, reliability and impact of protocol extensions.

1. Configuration management and UI.

I'm quite lost as what to say about this area of functionality other
than the fact that it is a "pain". Maybe the fact that it is dull and
repetitive leads developers to turn off their brains and go into
zombie mode. Otherwise how to explain that the least technically
demanding part of the code accounts for probably more than 1/2 of the
regressions ?

Actually, i'm being factitious.

The typical problem w/ configuration changes is that one is changing
the state of a given "engine" (i.e. other modules of the code) while
that engine is running. The typical problem w/ UI commands is that one
is attempting to examine a given state that is changing as the command
executes, as UI commands typically suspend themselfs between runs.

It boils down to synchronization being one of the most difficult
problems in software engineering. We will return to that topic latter.

Fortunatly, problems in this area are very often reproducible and most
are caught in verification before a given software image ships.  They
are also the easiest to provide "workarounds" for, as in: "don't touch
the red button", in case the problem makes it out to the field.

When it comes down to a discussion of protocol extensions, we need to
decompose our analysis further in two parts:
a) risk of regressions for existing functionality.
b) risk of getting the new knob right at first pass.

My humble opinion is that both are reasonably low.

Again, it is hard to provide either facts or a reasoning to sustain my
thesis. But the risk of regressions mostly depends on how orthogonal
the new functionality is to the existing one. In the area of
config/ui, these are typically quite orthogonal.

2. Session state machine and adjacency maintenance.

This is probably the most stable part of a BGP implementation. It is
also the simplest module in terms of complexity.

In terms of protocols extensions the only effects tend to be in terms
of capabilities advertised/received in OPEN messages. Which is
typically easy to extend w/o affecting existing code.

3. Input processing.

This is another area of low complexity. It typically consists of
checking the validity of the received message and storing received
attributes in a database.

SAFI specific attributes are typically decoded by SAFI specific code
which is quite orthogonal to other SAFIs. Protocol extensions are
usually handled w/o interference to existing code, given a code base
that is structured to deal w/ multiple SAFIs.

4. Route resolution.

This is an area that tends to differ quite significantly between the
implementations that i'm familiar with.

While BGP nexthop resolution needs to be extended when a new type of
next-hop is introduced, only 2 address families exist currently (ipv4,
ipv6).

There is typically much more work in this area to deal w/ either
implementation deficiencies or to add more functionality in order to
influence forwarding decisions than related to protocol extensions.

5. Loc-Rib handling

A Loc-RIB gives semantics to a given SAFI. While for the rest of BGP
processing an NLRI can be treated as an opaque bitstring, once
installed in the Loc-RIB an NLRI as specific meaning.

That said, the interface that a RIB presents to the SAFI-independent
part of BGP can be uniform. Given that a SAFI corresponds to a RIB,
semantics can be added modularly to the code that supports that RIB.

This module itself is non-trivial in complexity, essentially given
that it interfaces w/ the rest of the system, and has to deal w/
things such as synchronization with the forwarding table.

In terms of protocol extensions, the risk depends a lot on how well
the infrastructure is prepared to segregate SAFI-independent from
SAFI-specific functionality.

It is possible to do a reasonable job at the latter task, given the
problem definition.

6. Generation of UPDATEs

This is by far the most complex and challenging piece of a BGP
implementation.

The subtasks involved:
a) detecting routes for which best-path as changed.
b) running export policy to calculate atributes to advertise
c) generating updates given that different memebers in a peer group
may be flow controlled.
d) updating the internal state that keeps track of which
groups/members have seen a particular update.

Essentially, this is a synchronization problem, where one part, the
sender must obey the flow control from the receiver and keep track of
which state has been advertised into the TCP session. 

The really scary part, when it comes to update generation, is that
quite often bugs are not reproducible. Or when they are it is
very hard to do so and very hard to debug.

There have been bugs in this area of the code, that cause
updates/withdrawls to be missed, shipping for years in popular
implementations, before they are detected.

The good news is that there is no good reason for this module of code
to understand the structure of a given NLRI, althought b) is typically
SAFI dependent. The bad news is that it is still hard to get right,
regardless.

Most changes in this area come from the need to enhance performance
and fix implementation issues that affect all SAFIs.

Do performance/scalability requirements increase w/ protocol
extensions ? Certainly. But the impact to existing applications should
be positive rather than negative, minus the fact that performance
enhancements do certainly affect stability until they mature.

But it seems to me that those requirements would increase regardless
of protocol extensions.

Summary

My personal opinion is that the RIFT discussion is totally inverted:
It is not current engineering problems that should drive the
applicability of a given system. Requirements should drive
engineering. Unless one intends to make the point that it is not
possible to engineer a system that meets the requirements.

However, given that i'm in the minority opinion on that point, i hope
that the decomposition above can serve as a starting point to those
intended on analysing the problem.

  Pedro.
_________________________________________________________________
web user interface: http://darkwing.uoregon.edu/~llynch/grow.html
web archive:        http://darkwing.uoregon.edu/~llynch/grow/