\section{Deployment Models}
\label{sec:evolvability_scenarios:terminology}
\label{sec:evolvability_scenarios:assumptions}
\label{sec:terms}

% Intro: 
% Drivers/deployment scenarios

Based on a literature survey~\cite{Kent:2000fl, Mahajan:2007ws,
  LISPANewRouting:2011tf, Peter:2014jj, Xu:2006kh, Kushman:2007td,
  Subramanian:2005ce, Godfrey:2009ds, Yang:2007is, Zhang:2011hs}, we
have identified three commonly used deployment models for introducing
new protocols.  They differ in how they expect new protocols to be
used.  As such, it is the model, not individual protocols, that
dictate requirements for routing evolvability.  Multiple deployment
models may be suitable for a single protocol.  In such cases,
operators choose a model based on protocol-specific goals (e.g., do
they want the protocol to eventually replace the baseline or only be
used for select traffic?).  This section describes our models in
detail.  We first discuss the data-plane issues that can arise when
deploying multiple protocols, which our models manage differently.

\minorsection{Assumptions} At the beginning of time, we assume that
all domains, ASes for short, are using a baseline routing protocol for
inter-connectivity that is BGP-like. It is a path vector protocol in
which advertisements carry connectivity information upstream from
traffic sinks to traffic sources.  Data packets flow downstream from
sources to sinks.  Advertisements identify only one path to each sink.
The discussion below and the mechanisms presented in
Section~\ref{sec:design} are agnostic to whether ASes use distributed
control (i.e., routers choose paths) or centralized control (e.g.,
SDNs~\cite{Jain:2013un, Hong:2013tb}) and to whether ASes support
different sets of protocols on different routers.

\minorsection{Terminology} \textit{Islands} refer to a cluster of one
or more contiguous ASes that support the same set of routing
protocols.  Neighbors of islands run a different set of protocols.
\textit{Baseline ASes / Islands} refer to those that run the
baseline protocol (e.g., BGP).  \textit{Upgraded ASes / Islands}
refer to those that support the new protocol being discussed.  We
refer to the set of baseline ASes separating two upgraded islands
as \textit{gulfs}.

\subsection{Routing protocols \& the data plane}
\label{sec:evolvability_scenarios:data_plane}

The data plane or \textit{network protocol} is responsible for
enforcing routing protocols' path choices.  When multiple routing
protocols are deployed concurrently, consistency of routing decisions
becomes an issue.  If care is not taken to consistently enforce the
same routing protocol's path choices for a destination address at
every location (e.g., router or AS), the resulting end-to-end path may
not be the result of any single protocol's choices.  Also, paths
chosen by one protocol at one location may prevent data packets from
using better paths selected by a more preferred protocol at other
locations.  These issues can severely curtail new protocols' benefits.
Whether or not a protocol needs its routing decisions to be
consistently enforced informs the model to which it is best suited.

Enforcing consistency requires different mechanisms within islands and
across islands.  Our discussions assume an IP prefix as the
destination address, but are equally valid for other types (e.g.,
content names~\cite{Zhang:2014cj}).  To ensure consistency within
islands, protocols must be careful not to install conflicting entries
at different points in the path.  This requires assigning different
protocols different addresses that name the same physical
destinations.

Additionally ensuring consistency for routing decisions across islands
requires the relevant protocol's path choices to be enforced at
locations that do not support it (i.e., within gulfs).  Doing so
requires data packets to be encapsulated and tunneled, thus hiding
their within-island addresses from other protocols and islands.

We note that if routing protocols use different network protocols or
use a network protocol that supports multiple address types (e.g.,
XIA~\cite{Han:2012un}), consistency issues cannot arise.



\subsection{Model A: Updating the baseline}
\label{sec:evolvability_scenarios:baseline}

This model assumes that new protocols do not need consistency for
their routing decisions.  It is safe for end-to-end routing paths to
be an amalgamation of different protocols' individual path choices.
It is most useful for deploying critical fixes or updates to the
existing baseline protocol. Such updates disseminate extra control
information to improve path selection or the protocol itself.  Many
proposed fixes to BGP are suited for this model, including
Wiser~\cite{Mahajan:2007ws}, for fixing BGP's broken support for
traffic management, S-BGP~\cite{Kent:2000fl} for fixing BGP's
susceptibility to route hijacking, and
LISP~\cite{LISPANewRouting:2011tf} for supporting mobility.


% Data plane
\minorsection{Data-plane issues} Since consistency of routing
decisions is not an issue, there are no data-plane issues.  Protocols
deployed using this model can be leveraged to support new network
protocols, similar to IPv6 support using M-BGP~\cite{mp-bgp}.
Content-based routing~\cite{Zhang:2014cj}, which forwards traffic
based on content names, can be enabled in a similar way.

\input{fig_wiser_problem}

\minorsection{Example} Figure~\ref{fig:wiser_problem} shows a scenario
in which ASes start to incrementally deploy
Wiser~\cite{Mahajan:2007ws} as an update to BGP.  Wiser fixes BGP's
broken support for inter-domain traffic management by modifying BGP's
advertisements to include a \textit{global path cost}, which is used
to inform path selection.  This field is unit-less and normalized
across neighbors.  The two ASes at the edge of the large Wiser island,
E1 and E2, use BGP to advertise paths to their neighbors in the BGP
gulf.  Lines show paths advertised and arrows show the direction of
the advertisement.

The figure illustrates two problems. First, the source, which supports
Wiser, must use BGP to select paths because it cannot see global path
costs.  As such, it will choose the shortest path (due to BGP's
decision criteria), which has the highest global path cost.  Second,
E1 and E2 are at a disadvantage because they must honor global path
costs when selecting paths, but cannot express their own costs.  They
are at the mercy of upstream ASes' routing decisions.  This may
dis-incentivize them from supporting Wiser, especially if this
requirement increases their payments to providers or peers.

\minorsection{Requirements} As the above example shows, today,
non-contiguous islands or ASes that deploy updated baseline protocols
cannot quickly leverage the improvements afforded by them.  This is
because updated baselines' extra control information cannot be
disseminated across BGP gulfs.  Thus, we end up with this requirement:

\begin{description}
\item[UB-R1] \textit{Disseminate updated baseline's additional control
    information across gulfs}.
\end{description}

Also, the update must replace the baseline eventually:

\begin{description}
\item[UB-R2] \textit{Allow the existing baseline to be eventually
    replaced}. 
\end{description}

\minorsection{Constraints} This deployment model is only useful for a
very restricted set of protocol improvements.  For example (assuming a
BGP baseline), it is limited to path-vector-based protocols.  It
assumes routing decisions need not be consistent and does not support
off-path discovery of upgraded ASes.

\subsection{Model B: Custom routing}
\label{sec:evolvability_scenarios:custom}

This model assumes that protocols deployed using it require their
routing decisions to be consistently enforced across the Internet. It
also assumes that that new protocols will be used for only select
traffic and that the baseline will be used for the rest.  New
protocols use out-of-band coordination to disseminate control
information across upgraded islands (i.e., they use paths already
established by the baseline).

In the literature, this deployment model is often used to introduce
protocols that provide value-added services, which are sold for
profit.  Examples include selling alternate paths~\cite{Xu:2006kh,
  Peter:2014jj, Kushman:2007td} and selling extra functionality on
existing paths~\cite{Peter:2014jj} (e.g., higher intra-domain or
intra-island QoS).  This deployment model can also be used to connect
non-contiguous islands running a wide variety of protocols, including
those that use different routing paradigms than the existing baseline
(e.g., pathlet routing~\cite{Godfrey:2009ds} or path-based
routing~\cite{Yang:2007is, Zhang:2011hs}).  For example, two
non-contiguous islands could use a path-based protocol deployed using
this model to explicitly coordinate the intra-island hops they will
use for important traffic.

\minorsection{Data-plane issues} Islands will run multiple
inter-domain routing protocols concurrently (e.g., the baseline and
the new protocol).  The new protocol's routing decisions must be
enforced consistently, both within islands, and across gulfs.
Assuming all routing protocols use the same network protocol and
address types, separate address ranges must be assigned to custom
protocols within islands.  Packets must be encapsulated and tunneled
across gulfs.  Otherwise, the baseline protocol may divert packets
from ever reaching an upgraded island.

%Note it is easier to avoid using conflicting routing decisions in
%upgraded islands if the baseline and custom routing protocols are
%associated with different network protocols.\footnote{Some network
%  protocols support multiple address types (e.g.,
%  XIA~\cite{Han:2012un}).  The same is true for them.}  The reason is
%that each routing protocol will have its own network protocol, and the
%version number of the network protocol will be used to direct packets
%to the right forwarding table.

%The same is true if a single network
%  protocol supports multiple address types, e.g., XIA\cite{Han:2012un}
%  or unicast versus multicast addresses in IP, each of which is
%  supported by a separate routing protocol.}

%Finally,both packets describing the coordination necessary to use the
%custom protocol and regular data packets will have to traverse gulfs
%of baseline ASes.  The former can leverage paths established by the
%baseline protocol, but data packets may be diverted from ever reaching
%the upgraded island by routing decisions made within BGP gulfs.
%Avoiding this problem requires using encapsulation to tunnel packets
%across gulfs, effectively hiding traffic destined to an upgraded
%island from the baseline.

\input{fig_MIROExample}

\minorsection{Example} Figure~\ref{fig:wiserDeployment} describes a
scenario in which a transit AS (marked T) wishes to avoid the single
poorly performing path advertised by BGP (the dashed path).  An AS
that supports MIRO~\cite{Xu:2006kh} offers alternate paths for payment
(the rightmost one).  However, the transit AS cannot discover the
MIRO-enabled AS because BGP does not allow discovery of ASes' custom
services or the extra coordination required to use them.  This lack of
discovery mechanism limits the MIRO AS's potential customers, perhaps
only to its direct neighbors.  It could use bespoke approaches for
discovery (e.g., a web site), but these may go unnoticed.

\minorsection{Requirements} As the above example shows, ASes or
islands supporting the new protocol must be able to both discover each
other and how to coordinate out-of-band in order to exchange relevant
control information, including protocol-specific information (e.g.,
alternate paths) and the type of encapsulation method that will be
used to route packets across gulfs.  Thus, we require:

\begin{description}
\item[CR-R3] \textit{Facilitate discovery of custom services}.  
\end{description}

\minorsection{Constraints} This model cannot be used for protocols
that aim to replace the existing baseline.  It will be difficult to
deploy a large number of custom-routing protocols that use the same
network protocol because each will have to be assigned increasingly
smaller pools of addresses.  In contrast, this model is attractive for
routing protocols that use different network protocols (or different
address types within an existing protocol), or for within-island
protocol extensions.


\subsection{Model C: Exclusive routing}
\label{sec:evolvability_scenarios:exclusive_routing}

This model involves deploying new routing protocols by completely
\emph{replacing} the baseline protocol with a new one in upgraded
islands.  So, the key difference between this and the previous model
is that the new protocol is used for \textit{all traffic} in these
islands.  Doing so is very aggressive model and likely to be only
attractive if there are strong incentives or requirements that are
impossible to meet with the baseline (e.g., high QoE for all traffic
or specific economic relationships).  As such, it is likely to be
useful only within islands.  However, multiple islands could use the
same protocol and route traffic among each other using this model.  In
such cases, this model could be used to introduce radically different
protocols that aim to eventually replace the existing baseline.

%As the number of such islands grows, this model could be us
%such cases, this model could be used to eventually replace the current
%baseline with a radically different one.

Protocols that could be introduced using this model include ones that
use very different routing paradigms than the baseline, such as
HLP~\cite{Subramanian:2005ce}, which is a hybrid
path-vector-based/link-state protocol, or path-based
ones~\cite{Godfrey:2009ds, Yang:2007is, Zhang:2011hs}.

% \minorsection{Needed data-plane support} 

\minorsection{Data-plane issues} Within islands, consistency is not an
issue because only a single routing protocol is used.  The baseline
protocol will not have alternate end-to-end paths to destinations
controlled by upgraded islands, so consistency is also a non-issue
when traversing gulfs.  However, packets that traverse gulfs still
need to be encapsulated so that they can be forwarded by both the new
protocol and the baseline protocol (see requirements below).

\input{fig_sourceControlledExample}

% \subsubsection{Evolvability requirements}
% \label{ec:evolvability_scenarios:new_paradigm:challenges}

\minorsection{Example} Figure~\ref{fig:scionDeployment} illustrates a
scenario in which BGP is being replaced by SCION~\cite{Zhang:2011hs},
a path-based protocol.  Sources can be advertised multiple
path options (exposed at the granularity of border routers).  They
pick which one they want to use by encoding the path in packet
headers, which routers key on to forward traffic.  In this case, the
rightmost SCION region in the diagram exposes two paths to the
destination.

The scenario illustrates two key problems: the SCION source in the
diagram cannot discover other SCION islands or route traffic to them.
Unlike the previous model, out-of-band coordination and tunneling
cannot be used to address this problem as it will not scale to handle
all traffic.  Also, ASes within BGP gulfs cannot route to destinations
within SCION islands.  Both problems can be addressed by
re-distributing SCION routes into BGP~\cite{Le:2007gj}.  But, BGP can
only advertise one path per router, so one of the SCION paths would be
lost.

%Second,
%one of the two path options cannot be disseminated across the gulf
%because BGP supports only one path per border router.

\minorsection{Requirements} Solving the above problems requires the
ability to disseminate new protocols' control information in-band
with the baseline protocol.  Doing so sidesteps scalability issues and
avoids redistribution issues that may result in loss of important
information.  Thus, we have:

\begin{description}
\item[ER-R4] \textit{Enable in-band dissemination of new protocols'
    control information}
\end{description}

For protocols that aim to become the new baseline protocol, UB-R2 also
applies.
\\

With in-band dissemination, paths are jointly controlled by the
baseline in gulfs and by the new protocol in upgraded islands.
Packets routed along these paths be encapsulated so that they can be
forwarded by both protocols.  For example, in the example above, to
route packets to the SCION destination, the SCION source must
encapsulate data packets so that they contain both an IP header and
their path choice within the rightmost SCION island.

%we need
%coordination between new and baseline domains: in contrast to the
%previous model, some paths will necessarily be partly controlled by
%the baseline in some islands and partly by the new protocol in others.
%This means that the old and new protocol must cooperate by exchanging
%connectivity information so that it is possible to create paths that
%include both types of domains.  In particular, the extra control
%information associated with a new protocol must be sent in-band with
%baseline advertisements; similar to the redistribution that happens
%between routing protocols in today's Internet~\cite{Le:2007gj}. Thus,
%we have:

\minorsection{Constraints} There are no limitation on the type of
protocols that can be deployed using this model.


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