\section{Bootstrapping Evolvability}
\label{sec:design}

In this section, we argue that two modifications to BGP---integrated
advertisements and pass-through modules---satisfy the requirements
derived in the previous section and would allow BGP to bootstrap
evolution.  We first describe our mechanisms, focusing on how they
enable evolvability for updating the baseline, then discuss how they
could be applied to enable evolvability for custom and exclusive
routing.


\subsection{Integrated advertisements}
\label{sec:design:integrated_advertisements}

\textit{Integrated advertisements (IAs)} transform BGP's
advertisements into containers that can compactly carry multiple
protocols in addition to the current baseline.  This allows updated
routers to use new protocols and legacy ones to fall back on the
baseline.  As more routers support the updated baseline, the current
one can be eventually replaced \textit{(UB-R2)}.  Like BGP, each IA is
associated with a destination (e.g., a prefix).  However, different
protocols encoded in an IA can name the same destination differently
(e.g., using different address types).  To combat potentially large
message sizes, control information that is the same across protocols
is shared initially and split when modified by upstream ASes.

Figure~\ref{fig:wiserIntegratedAdvertisement} shows the basic
structure of an IA, which we believe is expressive (i.e., allows a
wide range of protocols to be encoded using it) and maximizes
potential for information sharing.  It is composed of three elements.
First, paths, which are encoded as nodes and edges.  We allow for
multiple paths to allow protocols that expose more than one path per
router to express them (e.g., SCION~\cite{Zhang:2011hs}).  Nodes
determine path granularity.  For example, they could be ASes, as in
BGP, or border routers, as in SCION.  Edges specify links between
nodes.

%Protocols, such as SCION or pathlet
%routing~\cite{Godfrey:2009ds}, that use different node granularities
%must use different paths.

The second element includes path descriptors, which describe
properties of entire paths or parts of them (i.e., those of specific
nodes or edges).  Destination addresses (e.g., prefixes or content
names) are included as path-level descriptors.  Possible node-level
descriptors might include intra-domain QoS objectives or S-BGP's route
attestations~\cite{Kent:2000fl}.  Edge descriptors could include
intra-domain congestion levels or BGP's MEDs.  For accountability, we
require node descriptors to include a field that states the AS
that created the corresponding node.

The third element includes \textit{AS descriptors}, which allows ASes
to include important information about themselves (e.g., on-path or
off-path services offered).  They are also used for loop detection
across all of the protocols included in an IA.

\minorsection{How IAs can be used to encode updated baseline
  protocols} Updated baselines' and current baselines' end-to-end paths
can be an amalgamation of each others' routing decisions (necessarily
meaning they will use the same node granularity).  As such, routers
can populate an IA with a single path for both the current baseline
and any updated ones they support.  Many fields can be shared.
Protocols will use the same address type, so the destination address
can be shared across protocols as a path-level descriptor.

Assuming both our modifications are implemented,
Figure~\ref{fig:wiserIntegratedAdvertisement} shows the IA that would
be received by the source AS in the example from
Section~\ref{sec:evolvability_scenarios:baseline}.  It is the
advertisement for the lowest-cost Wiser path.  It includes two
Wiser-specific fields.  The first is the global path cost.  The second
is a normalization factor, reflecting the total cost of all paths
disseminated by the AS that created this advertisement.  The latter is
required to allow upstream Wiser-enabled routers to normalize their
intra-AS costs with the global one before adding their contribution.

\subsection{Pass-through modules}
\label{sec:design:pass_throughs}

\textit{Pass-through modules} on routers work in concert with IAs.
They pass through control information for unsupported protocols with
new IAs for paths chosen by supported ones.  This allows control
information for updated baselines to be disseminated across gulfs that
support only the baseline \textit({UB-R1}).

Figure~\ref{fig:pass_through_module_design} shows a router that
includes a pass-through module.  It is similar to existing routers,
except it runs multiple \textit{decision modules} for each protocol it
supports.  Decision modules include protocol-specific path-selection
algorithms (e.g., BGP's tie-breaking logic), import/export filters,
and data structures (e.g., ADJ-RIBs).  The pass-through module assumes
responsibility for receiving IAs, interfacing with decision modules,
installing forwarding entries corresponding to their path choices, and
disseminating new IAs.

\input{fig_wiserIntegratedAdvertisement} 

\input{fig_pass_through_module_design}
\input{fig_wiser_solution}

To work, pass-through modules include the following elements and
interfaces.  Import/export filters allow implementation of global
policies (e.g., prefer paths learned through customers).  The
\textit{control interface} is used to push control information
relevant to supported protocols to their decision modules.  The
\textit{path-selection interface} allows protocols' decision modules
to return their path choices and any modified control information.
The \textit{data-plane interface} allows pass-through modules to
install forwarding choices corresponding to chosen paths. For
protocols that share the same network protocol and address types
(e.g., updated baselines), pass-through modules will only use
the most recent supported version.  

Pass-through modules store received advertisements in a database.
When creating an IA for a chosen path, they index into this database
to identify the message that advertised the path, and embellish the
message as needed with new control information.  They also add the
protocol used to choose path(s) to the relevant AS descriptor,
allowing upstream ASes to avoid paths chosen by undesired protocols.


\minorsection{How pass-throughs help with updating the baseline
  protocol} Passing through control information across gulfs allows
non-contiguous islands to use an updated baseline when routing to each
other.  Figure~\ref{fig:wiser_solution} illustrates the result if the
ASes in the scenario from
Section~\ref{sec:evolvability_scenarios:baseline} supported
pass-throughs and IAs.  The source AS is able to see Wiser's path cost
(see Figure~\ref{fig:wiserIntegratedAdvertisement}) and use it to
select the lower cost, longer path.  E1 and E2 are still at the mercy
of ASes that run only BGP, but their situation incrementally improves
as additional ASes deploy Wiser.

\subsection{Custom \& exclusive routing}
\label{sec:design:discovery}

IAs and pass-through modules enable discovery for custom routing and
in-band dissemination for exclusive routing.  For the former, IAs
could carry descriptions of the custom services offered and the extra
coordination needed to enable them within AS or node
descriptors~\textit{(CR-R3)}.  For the latter, routers could create
IAs that encode control information for both the new protocol and the
baseline protocol.  It could also specify the data-plane encapsulation
technique that must be used to forward traffic across
gulfs~\textit{(ER-R4)}.

Our modifications allow the transit AS in the example from
Section~\ref{sec:evolvability_scenarios:custom} to discover and use the
MIRO AS's alternate path as follows.  First, the MIRO AS uses
IAs to advertise a path to a service portal it
provides.  The AS descriptor includes a description of the custom
coordination required to use this service portal (e.g., a specific
protocol).  Second, the transit AS contacts the service portal to
negotiate the alternate path to the destination and the data-plane
encapsulation technique (e.g., an additional prefix) that
will be used to cross gulfs and selectively route the transit's
traffic.  Third, the transit uses the necessary encapsulation
technique to tunnel its traffic destined for the destination AS.  As an
optimization, the initial advertisement could include a list of the
most popular alternate paths the MIRO-enabled AS provides (e.g.,
alternate paths to Google, or S-BGP~\cite{Kent:2000fl} paths that
avoid North Korea).

Figure~\ref{fig:scionSolution} illustrates how IAs and pass-through
modules address the example discussed in
Section~\ref{sec:evolvability_scenarios:exclusive_routing}.  The edge
AS's border router in the SCION island creates an IA that includes
control information for both BGP and SCION.  The former includes a
single path, an IP prefix, and an AS descriptor for the edge AS.  The
latter includes two SCION paths, AS descriptors for them, and an
annotation in the edge AS's descriptor listing the encapsulation
technique needed to bridge gulfs.  In this case, it specifies that
SCION packets should be encapsulated with an IP header that lists the
prefix used in the IA as the destination.  When receiving packets, the
router at the edge of the SCION region de-encapsulates the IP header
and forwards packets using the source's path choice, specified in the
underlying SCION header.

\input{fig_scionSolution}

\subsection{Limitations}
\label{sec:design:limitations}

Our mechanisms are subject to the limitations and policies of the
baseline protocol(s) used to bridge gulfs.  For example, they allow
Wiser islands to pick the lowest-cost path from the options given, but
those options may include only high-cost paths because of ASes in BGP
gulfs' poor path choices.  Our mechanisms are also not sufficient to
enable evolvability for protocols that are not path-vector-based
(e.g., link-state).


%%% Local Variables:
%%% mode: latex
%%% TeX-master: "hotnets15_submit_evolvability"
%%% End:
