(solution) A Case Study in Network Architecture Tradeoffs Nikolai Matni

(solution) A Case Study in Network Architecture Tradeoffs Nikolai Matni

I need help with Case Study Analysis supposed to be due yesterday at 11:59 P. M.  I really need your help with it. 

The topic is as follow and the document on the case study analysis based is attached. 

“A Case Study in Network Architecture Tradeoffs”

A Case Study in Network Architecture Tradeoffs?
Nikolai Matni Ao Tang John C. Doyle California Institute of
Technology
1200 E California Blvd
Pasadena, California Cornell University
337 Frank H. T. Rhodes Hall
Ithaca, NY California Institute of
Technology
1200 E California Blvd
Pasadena, California [email protected] [email protected] [email protected] ABSTRACT Categories and Subject Descriptors Software de?ned networking (SDN) establishes a separation
between the control plane and the data plane, allowing network intelligence and state to be centralized ? in this way the
underlying network infrastructure is hidden from the applications. This is in stark contrast to existing distributed networking architectures, in which the control and data planes
are vertically combined, and network intelligence and state,
as well as applications, are distributed throughout the network. It is also conceivable that some elements of network
functionality be implemented in a centralized manner via
SDN, and that other components be implemented in a distributed manner. Further, distributed implementations can
have varying levels of decentralization, ranging from myopic
(in which local algorithms use only local information) to
coordinated (in which local algorithms use both local and
shared information). In this way, myopic distributed architectures and fully centralized architectures lie at the two
extremes of a broader hybrid software de?ned networking
(HySDN) design space.
Using admission control as a case study, we leverage recent developments in distributed optimal control to provide
network designers with tools to quantitatively compare different architectures, allowing them to explore the relevant
HySDN design space in a principled manner. In particular, we assume that routing is done at a slower timescale,
and seek to stabilize the network around a desirable operating point despite physical communication delays imposed by
the network and rapidly varying tra?c demand. We show
that there exist scenarios for which one architecture allows
for fundamentally better performance than another, thus
highlighting the usefulness of the approach proposed in this
paper. C.2.1 [Network Architecture and Design]: Miscellaneous; C.4 [Performance of Systems]: Miscellaneous. ?N. Matni & J. C. Doyle were in part supported by the
AFOSR and the Institute for Collaborative Biotechnologies
through grant W911NF-09-0001 from the U.S. Army Research O?ce. A. Tang was in part supported by the ONR
under grant N00014-12-1- 1055.
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are not
made or distributed for pro?t or commercial advantage and that copies bear
this notice and the full citation on the ?rst page. Copyrights for components
of this work owned by others than ACM must be honored. Abstracting with
credit is permitted. To copy otherwise, or republish, to post on servers or to
redistribute to lists, requires prior speci?c permission and/or a fee. Request
permissions from [email protected]
SOSR2015, June 17 – 18, 2015, Santa Clara, CA, USA
c 2015 ACM ISBN 978-1-4503-3451-8/15/06 …$15.00
DOI: http://dx.doi.org/10.1145/2774993.2775011. General Terms
Design, Theory, Performance 1. INTRODUCTION A common challenge that arises in the design of networks
is that of achieving globally optimal behavior subject to the
latency, scalability and implementation requirements of the
system. Many system properties and protocols ? such as network throughput, resource allocation and congestion avoidance ? are inherently global in scope, and hence bene?t from
centralized solutions implemented through Software De?ned
Networking (SDN) (e.g., [3, 4, 9]). However, such centralized solutions are not always desirable due to latency and
scalability constraints ? in particular the delay inherent in
communicating the global state of the network, solving a
global optimization problem and redistributing the solution
to the network, can often negate the bene?ts achieved from
this holistic strategy. In these cases, distributed networking
solutions can be preferable (e.g., [1]).
Traditionally, there has been very little in the way of theoretical tools at the disposal of network designers to quantitatively compare di?erent architectures. Because of this,
the appropriateness of an architectural decision could only
be con?rmed once a suitable algorithm had been prototyped
and validated via experiment. This process is time consuming and expensive, and even worse, can be inconclusive. In
particular, if an algorithm performs poorly, it is not clear
if this poor performance is due to an inherent limitation of
the chosen architecture, or simply due to a poorly designed
algorithm, making it very di?cult to quantitatively compare
network architectures.
In this paper, we argue that due to both the increased
?exibility a?orded to network designers by SDN and to recent advances in distributed optimal control, the gap between theory and practice has closed signi?cantly. Although
the gap has not yet completely closed, we show that in the
context of certain network applications, existing theory can
indeed be used to quantitatively compare the fundamental performance limits of di?erent network architectures. In
particular, we leverage the fact that new theory can now
explicitly take into account the e?ect of communication delays inherent to coordinating control actions in a networked
setting. Towards this end, we de?ne the broader Hybrid Software
De?ned Networking (HySDN) design space (§2) of network
architectures, and argue that an important metric in determining the appropriateness of an architecture is the optimal
performance achievable by any algorithm implemented on
that architecture. This additional metric can then be used
by a network designer to quantify the performance tradeo?s
associated with using a simpler or more complex architecture, allowing for more informed decisions about architecture early in the design process.
We further explain how recent advances in distributed
optimal control theory allow us to apply this approach to
a class of network control problems in which the objective is to regulate network state around a pre-speci?ed desired set-point. In §3, we illustrate the usefulness of this
approach with an admission control case study. Perhaps
surprisingly, we show that for two nearly identical routing
topologies, there can be signi?cant di?erences in the performance achievable by centralized and distributed network
architectures.
We emphasize that we are not arguing that a speci?c implementation, algorithm or architecture is best suited for a
given application ? rather, we are illustrating the usefulness
of a methodology that allows network designers to make
quantitative decisions about architectural choices early in
the design process. We are also not proposing that this
method replace the important steps of simulation, prototyping and experiments, but rather as a complement to it.
Indeed, in order to achieve theoretical tractability, simplifying assumptions such as linearized ?ow models, constant
delays, reliable control packet communication and negligible
computation time are made ? the validity of these assumptions can only be con?rmed through experiments. We do
however believe that the proposed tools can help network designers streamline the prototyping process by allowing them
to narrow down the range of potential architectures that
need to be explored. 2. ARCHITECTURAL TRADEOFFS Completely distributed network architectures, in
which local algorithms take local actions using only locally
available information, and centralized network architectures,
in which a centralized algorithm takes global action using
global information, can be viewed as lying at the extremes
of a much richer design space. It is possible to build a network architecture in which certain network logic elements
are implemented in a centralized fashion via SDN, and in
which other network logic elements are implemented in a
distributed fashion. Further, distributed architectures can
have varying levels of decentralization, ranging from completely distributed (as described above), or myopic, architectures to coordinated distributed architectures, in which
local algorithms take local actions using both locally available information and shared subsets of global state information. We call this broad space of architectures the Hybrid
Software De?ned Networking (HySDN) design space (illustrated in Figure 1), as its constituent architectures are naturally viewed as hybrids of distributed and software de?ned
networks.
The question then becomes how to explore this even larger
design space in a systematic way. As we have already alluded to, there are inherent tradeo?s associated with any architecture: algorithms running on centralized architectures typically achieve better steady state performance, but often
react with higher latency than those implemented on a distributed architecture ? conversely distributed algorithms are
often simpler to implement but can lead to less predictable
steady state performance.
We pause here to recognize that network architectures and
algorithms are judged by many di?erent metrics, including
but not limited to performance, scalability, ease of deployment and troubleshooting, and ?exibility. We argue that
as much as possible, each of these di?erent metrics should
be traded o? against each other in a quantitative way ? for
example, it is important for a network designer to be able
to quantify the performance degradation su?ered by using a
network architecture or algorithm that is simpler to deploy
and troubleshoot. Our approach to exploring these tradeo?s
is simple: we compare network architectures by comparing
the optimal performance achievable by any algorithm implemented using them. This approach allows for a network
designer to compare fundamental limits of achievable performance across di?erent architectures. The approach also
allows for the comparison of the performance of more scalable, ?exible, or easier to deploy algorithms implemented
using a given network architecture to that network architecture?s best possible performance, allowing for a quanti?able
tradeo? between these metrics of interest.
In order to make the discussion concrete, we focus on algorithms that can be viewed as controllers that aim to keep the
state of the network as close to a nominal operating point as
possible, while exchanging and collecting information subject to the communication delays imposed by the network.
For example, in §3, we consider admission control algorithms
that aim to keep the link ?ow rates at a user-speci?ed setpoint while minimizing the admission bu?er size, despite
physically imposed communication delays and rapidly varying source rates. In particular, we are not addressing the
problem of determining what nominal operating point the
controllers should attempt to bring the network state to ?
we aim to extend our analysis to such problems in future
work. We recognize that this measure of performance is not
standard in the networking community, but note that it is a
natural one to consider when explicitly taking into account
rapidly varying and unpredictable source rates.
By restricting ourselves to problems of this nature, we
can leverage recent results in distributed optimal control
theory to classify those architectures for which the optimal algorithm and achievable performance can be computed
e?ciently.1 It is well known that the optimal centralized
controller, delayed or not, can be computed e?ciently via
convex optimization [13]. Further, it is known that myopic
distributed optimal controllers are in general NP-hard to
compute [12, 8]. Up until recently however, it was unclear if
and when coordinated distributed optimal controllers could
be speci?ed as the solution to a convex optimization problem.
The challenge inherent in optimizing distributed control
algorithms is that control actions (e.g., local admission control decisions) can potentially serve two purposes: actions
taken by local controllers can be used to both control the
state of the system in a manner consistent with performance
1
Throughout this discussion, we assume that the dynamics
of the network are linear around a neighborhood of the nominal operating point. This assumption holds true for many
commonly used network ?ow models [5, 2]. Centralized'Applica1on'Plane'
Centralized'
Centralized'
Applica1on'
Applica1on' Centralized'
Applica1on' Centralized'
Applica1on' Applica1on'Controller'Plane'Interface''
Control'Plane' Applica/on'Plane'
Centralized'
Centralized'
Applica/on'
Applica/on' Network'Opera1ng'System' Centralized'
Applica/on' Centralized'
Applica/on' Applica/on'Controller'Plane'Interface''
Control'Plane' Applica3ons$ Applica3ons$
OS$
Data$
Forwarding$$ OS$
Data$
Forwarding$$ Applica3ons$ Data'Controller'Plane'Interface'' Network'Opera/ng'System' Data'Plane' Applica3ons$
OS$
Data$
Forwarding$$ OS$
Data$
Forwarding$$ (a) Distributed Networking Dist.'App'
Local'OS'
Data' Dist.'App'
Local'OS'
Data'
Dist.'App'
Local'OS'
Data' Data'Controller'Plane'Interface''
Dist.'App'
Local'OS'
Data' Data'Plane' Data'
Forwarding'' Data'
Forwarding'' Data'
Forwarding''
Data'
Forwarding'' (b) Hybrid Software De?ned Networking (c) Centralized Software De?ned Networking Figure 1: The Hybrid Software De?ned Networking Design space, ranging from distributed (Fig 1a) to centralized (Fig 1c)
network protocols. objectives, and to signal to other local controllers, allowing
for implicit communication and coordination. Intuitively, it
is this attempt to both control the system and to implicitly communicate that makes the problem di?cult to solve
computationally. However, if local controllers are able to
coordinate their actions via explicit communication, rather
than by implicit signaling through the system, then the optimal controller synthesis problem becomes computationally
tractable [11, 10]. Further it is not di?cult to argue that
distributed controllers using explicit communication to coordinate will outperform those relying on implicit signaling through the system. Removing the incentive to signal
through the system can be done in a network control setting
by giving control dedicated packets, i.e., packets containing
the information exchanged between local algorithms, priority in the network.2
These theoretical developments thus provide the necessary tools to explore a much larger section of the HySDN
design space in a principled manner. We propose leveraging these results to compare the performance achievable by
algorithms implemented on four di?erent classes of architectures, described below:
1. The GOD architecture: in order to quantify the
fundamental limits on achievable performance, we propose computing the optimal controller implemented
using the Globally Optimal Delay-free (GOD) architecture. This architecture assumes instantaneous communication to and from a central decision maker ?
although not possible to implement, the performance
achieved by this architecture cannot be beaten, and
as such represents the standard against which other
architectures should be compared.
2. The centralized architecture: this architecture corresponds to the SDN approach, in which a centralized
decision maker collects global information, computes
2 Speci?cally, if local controllers can communicate with each
other as quickly as the e?ect of their actions propagate
through the network, then the resulting optimal control
problem is convex. By giving such communication packets
priority in the network and ensuring that they are routed
along suitably de?ned shortest paths, this property is guaranteed to be satis?ed [10]. a global control action to be taken, and broadcasts it
to the network. Although global in scope, the latency
of algorithms implemented using this architecture is
determined by the communication delays inherent in
collecting the global network state and broadcasting
global actions.
3. The coordinated architecture: this architecture is
distributed, but allows for su?cient coordination between local controllers so that the optimal control law
can be computed e?ciently [11, 10]. This architecture
takes both rapid action based on timely local information, and slower scale action based on global but
delayed shared information, and can thus be viewed as
an intermediate between centralized and myopic architectures.
4. The myopic architecture: this architecture is one
in which local controllers take action based on local
information. Although the optimal controller cannot
be computed, the performance achieved by any myopic controller can be compared with the performance
achieved by an optimal coordinated controller, thus
providing a bound on the performance di?erence between the two architectures.
It should be noted that the coordinated architecture will
always perform at least as well as the myopic and centralized
architectures, as any algorithm implemented on the latter
architectures can also be implemented on the former. It is
clear why this holds for myopic algorithms, but it is worth
emphasizing why this holds for centralized algorithms. This
is true because the delays faced by a coordinated distributed
algorithm in collecting and sharing state information are also
faced by a centralized algorithm. Whereas a centralized algorithm waits until the global state has been collected and
processed to react to make changes to the system, a coordinated distributed algorithm takes both local timely actions
based on local information and delayed actions based on
shared information.
What we seek to understand is how large of a gap in performance exists between these di?erent architectures. By
computing the performance of each of these architectures,
the network designer can then quantify tradeo?s in implementation complexity and performance in a computationally e?cient and inexpensive manner. We demonstrate the usefulness of this approach on an admission control case study
in the next section. 3. Noisy source
xs (t) = x? (t) + s (t)
s ADMISSION CONTROL DESIGN In this section we pose an admission control problem, de?ne the relevant HySDN design space and show that it can
be explored in a principled and quantitative manner using
tools from distributed optimal control theory. We discuss
the problem at a conceptual level in this section, and refer
the interested reader to [7] for the technical details. 3.1 Figure 3: Diagram of an edge admission controller. Ingoing ?ows
f 1 (t)
f 2 (t)
f 3 (t) Problem We consider the following admission control task: given
a set of source-destination pairs (s, d), a set of desired ?ow
rates f ,(s,d) on each link for said source-destination pairs,
and a ?xed routing strategy that achieves these ?ow rates,
design an admission control policy that maintains the link
?ow rates f ,(s,d) (t) as close as possible to f ,(s,d) while minimizing the amount of data stored in each of the admission
control bu?ers, despite ?uctuations in the source rates xs (t).
The architectural decision that the network designer is
faced with is whether to implement the admission control
policy in a myopic, coordinated, or centralized manner ?
representative examples of these possible architectures are
illustrated in Figure 2 for the case of three sources. In the
myopic distributed architecture, local admission controllers
AC1, AC2 and AC3 have policies that depend solely on their
local information ? in what follows, we de?ne the local information available to a local algorithm for the speci?c case
studies that we consider. In the coordinated distributed architecture, the local admission controllers take action based
on both locally available information and on information
shared amongst themselves ? this shared information is delayed, as it must be communicated across the network and is
therefore subject to propagation delays. Finally, in the centralized architecture, a central decision maker collects the
admission control bu?er and link ?ow rate states subject to
appropriate delays, determines a global admission control
strategy to be implemented and broadcasts it to the local
AC controllers ? this strategy also su?ers from delay due to
the need to collect global state information and to broadcast
the global policy to each AC controller.
As mentioned in the previous section, we know a priori
that the coordinated distributed optimal control architecture will perform no worse than either the myopic or centralized architecture. Conversely, the myopic and centralized schemes are signi?cantly easier to deploy, and the centralized scheme is signi?cantly easier to troubleshoot. Thus,
in quantifying the gaps in performance between the centralized, myopic and distributed architectures, the network
designer is able to make an informed decision as to whether
the added complexity of the coordinated distributed scheme
is warranted.
As described in §2, our approach to exploring the HySDN
design space is to compute optimal admission controllers implemented on each of these di?erent architectures. In particular we compute admission controllers that minimize a
performance metric of the form
N f
t=1 ,(s,d) ,(s,d) (t) ?f 2
,(s,d) + ? A(t) 2 ,
2 (1) Admission
Control
Bu?er
Admitted ?ow
as (t)
As (t) Admission
Control
Bu?er Admitted
a1 (t) ?ows
a2 (t)
As (t)
a3 (t) Figure 4: Diagram of an internal admission controller. where A(t) is a vector containing the size of the admission
control bu?ers and N is the optimization horizon. Thus the
controllers aim to minimize a weighted sum of ?ow rate deviations and admission queue lengths over time, where ? > 0
determines the relative weighting assigned to each of these
two terms in the ?nal cost. By solving the corresponding
optimal control problems, we obtain two parameters: an
optimal cost and an admission control policy that achieves
it. These optimal costs thus serve as a quantitative measure
of the performance of a given architecture, as by de?nition,
they correspond to the best performance achievable by any
admission control policy implemented on that architecture. 3.2 Case Study We consider a simple routing topology overlaid onto the
abilene network, and two di?erent admission control scenarios: one in which only edge admission control is allowed (cf.
Figure 3) and one in which edge and internal admission control is allowed (cf. Figure 4). We model the dynamics of the
system using a ?ow based model and solve the optimal control problem with the cost (1) taken to be the in?nite horizon
LQG cost using the methods described in [13] and [6] ? we
refer the reader to [7] for the technical details. Intuitively,
this cost measures the amount of ?energy? transferred from
the source rate deviations to the ?ow rate deviations and
bu?er sizes. We assume that the nominal source rates xs (t)
and the nominal ?ow rates f ,(s,d) are all equal to 1 (this
is without loss of generality through appropriate normalization of units), and empirically choose ? = 50 based on the
observed responses of the synthesized controllers.
We compute three optimal controllers for each of the scenarios considered: a coordinated distributed optimal controller in which local admission controllers are able to exchange information via the network in order to coordinate
their actions, as illustrated in the middle pane of Figure
2, a centralized optimal controller subject to the delays induced by collecting global state information and broadcasting a global control action, and the GOD controller. We also
compare the performance of these controllers with the performance achieved by the best myopic distributed controller
we are able to compute via non-linear optimization (recall
that optimal myopic controllers are in general computationally intractable to compute). Noisy&
Src&1& AC1& AC2& AC3& AC1& AC2& AC3&
Flow&3&
Flow&2& Flow&1& Flow&3& Flow&2& Flow&1& Flow&3& Flow&2& Flow&1& Network& Network& Network& Myopic&Distributed& Coordinated&Distributed& Info&3& AC3& Info&2& AC2& Noisy&
Src&3& Admission&Controller& Info&1& AC1& Info&3& Noisy&
Src&3& Info&2& Noisy&
Src&2& Info&1& Noisy&
Src&1& Info&3& Noisy&
Src&3& Info&2& Noisy&
Src&2& Info&1& Noisy&
Src&1& Noisy&
Src&2& Centralized& Figure 2: The HySDN design space for an admission control problem with three sources. Blue arrows denote the ?ow of tra?c,
whereas dashed black lines denote the ?ow of admission control related information. Note that the dotted lines correspond to
virtual connections, and can be implemented using either control dedicated communication links, or using control dedicated
t…