A Machine Learning Approach to Routing

Asaf Valadarsky1 Michael Schapira1 Dafna Shahaf1 Aviv Tamar2

ABSTRACT Unfortunately, in general, routing configurations optimized

Recently, much attention has been devoted to the question with respect to specific traffic conditions can fail miserably
of whether/when traditional network protocol design, which in achieving good performance even under not-too-different
relies on the application of algorithmic insights by human ex- traffic conditions. In addition, optimizing worst-case perfor-
perts, can be replaced by a data-driven (i.e., machine learning) mance across a broad range of considered traffic scenarios
approach. We explore this question in the context of the ar- might come at the expense of being far from the achievable
guably most fundamental networking task: routing. Can ideas optimum for the actual traffic conditions.
and techniques from machine learning (ML) be leveraged to Intuitively, ML suggests a third option: leveraging infor-
automatically generate “good” routing configurations? We fo- mation about past traffic conditions to learn good routing
cus on the classical setting of intradomain traffic engineering. configurations for future conditions. While the exact future
We observe that this context poses significant challenges for traffic demands are unknown to the decision maker in advance,
data-driven protocol design. Our preliminary results regard- a realistic assumption is that the history of traffic demands
ing the power of data-driven routing suggest that applying contains some information regarding the future (e.g., changes
ML (specifically, deep reinforcement learning) to this context in traffic across times of day, the skewness of traffic, whether
yields high performance and is a promising direction for fur- certain end-hosts communicate often, etc.). Hence, a natural
ther research. We outline a research agenda for ML-guided approach is to continuously observe traffic demands and adapt
routing. routing with respect to (implicit or explicit) predictions about
the future.
1. INTRODUCTION Intradomain traffic engineering (TE) as a case study. We
initiate the study of ML-guided routing by examining the
Applying machine learning (ML) to computational chal-
classical environment of intradomain TE [15, 16, 17, 24,
lenges is prevalent in numerous areas in computer science
50, 29, 10]–the optimization of routing within a single, self-
(AI, computer vision, graphics, NLP, comp-bio, and beyond).
administered network. We leave the investigation of data-
Computer networking, in contrast, has largely withstood the
driven routing in other contexts to future research (Section 7).
ML tide until recently. Recent advances suggest that this
We present a model for data-driven (intradomain) rout-
might be changing [23, 33, 32].
ing that builds on the rich body of literature on intradomain
We ask whether data-driven protocol design [23] can im-
TE [15, 16, 17, 24, 50, 29, 10] and (multicommodity [43, 22,
prove upon today’s approaches in the context of routing, i.e.,
7, 10, 29, 16, 5]) flow optimization. We investigate, within
the selection of paths for traffic within a network, or across
this model, the application of different ML paradigms and
networks.
machinery.
Why apply machine learning to routing? Routing is, ar- In our investigation of ML-guided intradomain TE we grap-
guably, the most fundamental networking task and, conse- ple with two main questions: (1) How should routing be
quently, has been extensively researched in a broad variety formulated as an ML problem? and (2) What are suitable
of contexts (data centers, WANs, ISP networks, interdomain representations for the inputs and outputs of learning in this
routing with BGP, wireless networks, and more). Tradition- domain? We next expand on each of these challenges, which
ally, route-optimization contends with uncertainty about fu- also pertain to data-driven routing in other contexts.
ture traffic conditions in one of two manners: (1) optimizing
Learn future traffic demands or learn routing configura-
routing configurations with respect to previously observed
tions? Supervised learning or reinforcement learning? A
traffic conditions, with the hope that these configurations fare
natural approach to ML-based routing is the following: ob-
well also with respect to the future, or (2) optimizing with
serve past traffic demands, apply ML to explicitly predict the
respect to a range of feasible traffic scenarios, in hope of
upcoming traffic demands, and optimize routing with respect
providing high performance across the entire range [16, 10,
to the predicted demands. In ML terms, this is a supervised
29, 7].
learning task [39]. bors. Thus, a routing strategy specifies, for each vertex v and
We evaluate several supervised learning schemes for pre- source-destination pair (s, t) a mapping from v’s neighbors
dicting traffic demands. Our preliminary results are discour- to values in the interval [0, 1], Rv,(s,t) : Γ(v) → [0, 1], such
aging, indicating that supervised learning might be ineffective that Rv,(s,t) (u) is the fraction of traffic from s to t travers-
if the traffic conditions do not exhibit very high regularity. ing v that v forwards to its neighbor
P u. We require that for
We next turn our attention to a different approach: reinforce- every s, t ∈ V and v 6= t, u∈Γ(v) Rv,(s,t) (u) = 1 (no
ment learning [45]. Now, instead of explicitly learning future traffic is blackholed
P at a non-destination), and also for every
traffic demands and optimizing with respect to these, the goal s, t ∈ V , u∈Γ(v) Rt,(s,t) (u) = 0 (all traffic to a destination
is to learn a good mapping from the observed history of traffic is absorbed at that destination).
demands to routing configurations. Our preliminary results Induced flows of traffic. A demand matrix (DM) D is a
suggest that this approach is more promising, yet realizing it n × n matrix whose (i, j)’th entry Di,j specifies the traffic
requires care, as discussed next. demand between source i and destination j. Observe that
What should the output of the learning scheme be? The any demand matrix D and routing strategy R induce a flow
intradomain routing context poses significant challenges to of traffic in the network, as explained next. Traffic from
the application of reinforcement learning. A key challenge is every source s to destination t is split amongst s’s neighbors
that the natural “output” of a routing scheme is a collection of according to Rs,(s,t) . Similarly, traffic from s to t traversing
rules specifying how traffic is forwarded from each source to a neighbor of s, v, is split amongst v’s neighbors according
each destination. This output’s naive representation involves to Rv,(s,t) , etc.
a very large set of parameters (as opposed to, e.g., selecting How good is a traffic flow? We adopt the classical objective
a single action from a fairly small set [32, 33]). Our initial function of minimizing link (over)utilization [16, 10, 7, 29].
results indicate that this can render learning slow and ineffec- The link utilization under a specific multicommodity flow f is
tive. We hence devise methods for constraining the size of the maxe∈E c(e)fe
, where fe is the total amount of flow traversing
output without losing “too much” in terms of routing expres- edge e under flow f . Our formulation can easily be extended
siveness. We leverage ideas from the literature on hop-by-hop to other multicommodity-flow-based objective functions. We
traffic engineering [35, 50, 16] to efficiently learn, via deep leave the evaluation of other objectives (e.g., flow-completion
reinforcement learning, good routing configurations. Our pre- time, latency) to future research (Section 7).
liminary findings suggest that this is a promising direction for We point out that for any given demand matrix, computing
improving upon today’s intradomain TE. a multicommodity flow f that minimizes link utilization can
Outlining a research agenda for data-driven routing. We be executed in a computationally-efficient manner via linear
believe that our investigation below but scratched the surface programming [22, 7, 16]. Our focus, in contrast, is on the
of data-driven routing. We leave the reader with many interest- realistic scenario in which the DM is not known beforehand.
ing research questions, including (1) extending our approach Routing future traffic demands. Time is divided into
to other routing contexts, (2) examining other performance consecutive intervals, called “epochs”, of length δt (δt is
metrics, (3) identifying better supervised learning approaches determined by the network operator). At the beginning of
to traffic-demand estimation, (4) scaling reinforcement learn- each epoch t, the routing strategy Rt for that epoch is decided.
ing in this context, and beyond. We discuss this research Rt can depend only on the history of past traffic patterns and
agenda in Section 7. routing strategies (from epochs 1, . . . , t − 1).
We make two simplifying assumptions: (1) the demand
2. DATA-DRIVEN ROUTING MODEL matrix is fixed throughout each time epoch, and (2) demand
In our framework, a decision maker (network operator / matrices can be inferred after the fact (e.g., via network mea-
automated system) repeatedly selects routing configurations. surements). We leave the investigation of data-driven routing
Traffic conditions vary and routing decisions are oblivious to under more complex traffic patterns (e.g., IP flows enter and
future traffic demands. Our focus is on the conventional opti- leave within each epoch) and of information-constrained rout-
mization objective of minimizing link over-utilization (a.k.a. ing decisions (e.g., only partial information about past traffic
minimizing congestion) from traffic engineering literature [16, demands) to the future.
7, 10, 29]. After selecting the routing strategy Rt for epoch t, the
demand matrix for epoch t, and the associated cost, in terms
Network. We model the network as a capacitated directed
of maximum link-utilization, are revealed. The objective of
graph G = (V, E, c), where V and E are the vertex and edge
the decision maker is to select routing strategies in a manner
sets, respectively, and c : E → R+ assigns a capacity to each
that consistently results in low link over-utilization.
edge. Let n denote the number of vertices in V and Γ(v)
denote vertex v’s neighboring vertices in G.
Routing. A routing strategy R for the network specifies, 3. WHAT TO LEARN?
for each source vertex s and destination vertex t how traf- Our underlying assumption is the existence of some regular-
fic from s to t that traverses v is split between v’s neigh- ity in the DMs, and the purpose of the investigation below is
 (a) Cyclic gravity DM sequences (sparsity (b) Averaged bimodal DM sequences (spar- (c) Randomly drawn gravity DM sequences
p = 0.3) sity p = 1) (sparsity p = 0.3)

Figure 1: Representative Results for Supervised Learning (using NAR-NN with k = 10 and q = 5)

exploring how such regularity can be inferred and leveraged in which communication end-points are divided into small
to optimize routing. We consider two different manifesta- flows (mice) and large flows (elephants). We also consider
tions of regularity— embedding deterministic regularity into “sparsifications” of gravity/bimodal DMs generated by select-
the DM sequence and drawing DMs from a fixed probabil- ing, uniformly at random, a p-fraction of the communicating
ity distribution—and two high-level learning approaches— pairs, for some choice of p ∈ [0, 1], and removing the traffic
supervised learning and reinforcement learning. demands of all other pairs from consideration. We refer to p
as the sparsity of the DM.
3.1 Supervised Learning Approach Our experiments require generating sequences of DMs,
specifying a DM for each time epoch. We examine two
Since for a given demand matrix (DM), an optimal routing
classes of DM sequences:
strategy is efficiently computable, a natural approach is to
repeatedly try to predict (i.e., learn) the next DM and then Class I: DM sequences in which the next DM is determin-
compute an optimal routing strategy for that DM. In ML istically derived from past DMs. One example for such a
terms, this is a supervised learning problem. DM sequence is “a cycle of DMs”, in which the DM in each
epoch belongs to a fixed set of q DMs, D(0) , . . . , D(q−1) such
Supervised learning. A supervised learning task involves
that if D(j) is the DM in epoch t − 1 then D(j+1 modulo q)
a sample space X and a labeling space Y. An algorithm A
is the DM in epoch t. D(0) , . . . , D(q−1) in our experiments
for the task is a function mapping values in X to labels in
are sparsified (for varied values of p) gravity/bimodal DMs
Y. Given a set of samples and their true labels {(xi , yi )} ∈
(for varied values for parameters of the bimodal model). Cy-
X × Y, the goal is to identify a mapping that produces correct
cles of DMs might capture, e.g., the scenario that the traffic
labels for new samples, drawn from the same distribution as
demands at a certain time of day are rather similar across
the data. How good/bad a mapping fares is quantified in terms
days. See discussion of such temporal consistencies in ISP
of a loss function L : Y × Y → R. Intuitively, for any pair
networks in [17]. Another example of a DM sequence that,
of labels (y1 , y2 ), L(y1 , y2 ) represents the cost of predicting,
though more artificial, also exhibits high regularity (and so is
for a given sample, the label y2 instead of the correct label y1 .
interesting to study) is when each DM is the average of the
See [39] for a detailed exposition of supervised learning.
previous q DMs (for some fixed q > 0). Our experiments
We consider the following supervised learning approach
evaluate supervised learning schemes on DM cycles of sizes
to routing: the learning algorithm observes the history of
q = 5, 10, 15, 20, and DM sequences in which each DM is
DMs up to the current epoch, and predicts the DM for the
the average over the previous q = 5, 10, 15, 20 DMs.
upcoming epoch. This prediction is then used to generate an
optimal routing strategy with respect to the predicted DM. Class II: DM sequences in which each DM is independent
When is employing this scheme a good idea? To answer this of the previous DMs. The DM for each epoch is now drawn
question, we evaluate several supervised learning schemes independently from a fixed probability distribution over DMs,
for predicting the next DM on different traffic patterns. namely sparsified gravity/bimodal DMs. We point out that
such traffic patterns are commonly used in evaluations of
Generating DM sequences for our experiments. We next
data center architectures and protocols [25, 4, 19, 51] as
discuss how traffic patterns are generated in our experiments.
traffic in data centers is often viewed as highly skewed and
We consider two standard schemes for generating DMs: the
unpredictable [20, 18].
(deterministic) gravity model [40] and the (probabilistic) bi-
modal model [34]. Intuitively, the former captures scenarios Supervised learning schemes. Following the recent suc-
in which communication between end-points is proportional cesses of deep neural networks (DNNs) [28, 38, 41]), we
to their outgoing bandwidths and the latter captures scenarios evaluate 3 different DNN architectures. The input to all three
architectures is the k most recent observed DMs and the out- framework, an agent repeatedly interacts with an environment.
put is a DM. We examine different values of k (5, 10, and Time is divided into discrete time slots t = 1, 2, 3, .... At the
20). We use the Frobenius (or l2 ) norm [21] to quantify the beginning of each time slot t, the agent observes the current
quality of an output with respect to the actual DM. The three state st−1 of the environment and selects an action at from
architectures differ in the structure of the neural network in- a fixed set of actions. Once the agent chooses action at , the
terconnecting the input layer (representing k-long histories state of the environment changes to st and the agent receives
of DMs) and output layer (representing the next DM). We a reward rt (a numerical value) signifying how good/bad
evaluate (1) FCN, a 3-layered fully-connected network, (2) the action he took was. The goal of the agent is to learn a
CNN, a 4-layered convolutional neural-network [30], and (3) mapping π from the set of possible states S to the space of
NAR-NN, a nonlinear auto-regressive model [11], realized via actions A (i.e., π : S → A) that fares well with respect to
a 4-layered neural network that, for input demand matrices thePobjective of maximizing the expected discounted reward
D(1) , . . . , D(k) , learns a k-vector α =
P(α1 , . . . , αk ) and an E[ t γ t rt ] for a predetermined γ > 0, called the discount
n × n matrix β, and outputs the DM i αi D(i) + β. factor. See [45] for a detailed exposition of reinforcement
Evaluation framework. We experiment with gravity and learning.
bimodal DMs of various sizes (9×9, 12×12, 23×23, 30×30, Routing via reinforcement learning. Routing-strategy se-
50 × 50, and 100 × 100) under various choices of sparsity lection can be cast as a reinforcement learning task as follows.
levels p = 0.3, 0.6, 0.9, 1 and of values of per vertex outgoing At the beginning of each time epoch t, the operator/system
bandwidths (ranging from 10’s of MB to 10’s of GB). We (agent) decides on a routing strategy Rt for that epoch based
consider various DM sequence lengths for training and testing on the routing strategies and DMs in the most recent k time
the model (ranging from a few 10’s to few 100’s of DMs). We epochs, which constitute the observed state of the environ-
generate, for each choice of parameter assignment to q, p, k ment at that point. Then, the state changes as the DM for
(t)
and sequence length, a training set of 10 DM sequences and a epoch t, D(t) , is revealed and the reward r(t) = − OPu T (t) is
test set of 3 DM sequences. We define a learning epoch as a received, where u(t) is the max-link-utilization under Rt for
full traversal of the training set. We train each neural network D(t) , and OP T (t) is the optimal max-link-utilization with
for 2000 learning epochs. respect to D(t) (r(t) thus captures the ratio between achieved
Results. Our experimental results (for the test DM se- performance and optimal performance). The goal is to learn
quences) show that for DM sequences that exhibit determinis- a mapping from k-long histories of DMs to routing strategies
tic regularity, namely, cycles of DMs and “averaged DMs”, that maximizes the expected discounted reward, as formu-
only the NAR-NN performs fairly well and only for specific lated above. We explore the power of this approach in the
relations between the examined history (k) and the size of following sections.
the cycle / number of DMs averaged over (q). Specifically,
when q ≤ k, NAR-NN well-approximates the next DM for 4. REPRESENTING THE OUTPUT
cycles of DMs, and performs well on averaged DMs. NAR- In contrast to other recent applications of ML to network-
NN continues to perform reasonably well on averaged DMs ing [32, 33], learning routing strategies involves generating
when q > k, but fails on cycles of DMs for q > k. All neural networks with very large output layers (containing, e.g.,
3 architectures failed to approximate the next DM for ran- thousands of output nodes even for a communication network
domly generated DMs (which is not surprising, as there are of but tens of vertices). Consider, e.g., the representation of a
no temporal correlations between DMs in the sequence). routing strategy described in Section 2. This representation
We present representative results for NAR-NN on a network involves |V |2 · |E| variables, where |V | and |E| are the sizes
G with 30 vertices. We plot the loss, in terms of distance of of the network graph’s vertex set and edge set, respectively.
the predicted DM from the actual DM (y-axis), over the num- We show below that even for constrained routing strategies
ber of learning epochs (x-axis). Figure 1b and Figure 1a show of much smaller sizes, a (“vanilla”) reinforcement learning
that the model succeeds in learning the next DM when using approach for predicting the complete routing strategy fails to
the averaged and cyclic DM sequence generation. Figure 1c attain good performance within reasonable time.
demonstrates failure in learning the next DM when drawn We restrict our attention to destination-based routing strate-
from a probability distribution. We leave the investigation gies, i.e., routing strategies in which the splitting ratios at
of whether better supervised learning of traffic demands is each vertex u with respect to any destination d are the same
feasible for the future (see Section 7). across all possible sources s. Observe that any such rout-
3.2 Reinforcement Learning Approach ing strategy RS can be represented by |V | · |E| values (i.e.,
|V | times smaller than unconstrained routing strategies). We
Next, instead of learning the next DM and optimizing the employ the continuous-control reinforcement-learning algo-
routing strategy with respect to that DM, our goal is to di- rithm, TRPO [41], applied to a 3-layered fully-connected
rectly learn a good mapping from observed DMs to routing neural network, to learn the mapping π from k-long histories
strategies. of DMs to a routing strategy RS. The real-valued outputs
Reinforcement learning. In the reinforcement learning generated by the deep neural network are turned into per ver-
tex traffic-splitting ratios by applying, for each vertex in the
communication network u, the softmax function [9] to the
outputs corresponding to u’s outgoing edges.
Evaluation. We adapt the open-source implementation of
TRPO [41] provided by OpenAI [13] to the task of learning
routing-strategies. We begin our evaluation with a seemingly
easy target: learning the splitting ratios for a 12-vertices,
32-edges network (taken from [26]), and (sparsified) gravity
DMs. We train a 3-layered fully-connected network over 7
sequences of gravity DMs of length 60 and evaluate (test) the
neural network on 3 such sequences. We repeat this process
(a) Congestion ratio for sparse (p = 0.3) grav-
for sparsity levels 0.3, 0.6, and 0.9. We use k = 10 (the ity DM sequences
length of the history of past DMs received as input). We
compute the optimal congestion using the CPLEX [2] LP
solver.
The training phase involves generating, from every se-
quence of DMs of length 60, 50 sequences of 10 consecutive
DMs (representing ten-long histories of DMs), by grouping
DMs 1 − 10, 2 − 11, etc. Training the neural network on each
of these “histories of DMs” involves evaluating the neural
network 30 times in parallel (and so 1, 500 iterations per DM
sequence and 10, 500 overall). We refer to one execution of
this process as a “learning epoch”.
Our results (omitted due to space constraints) suggest that
this approach leads to slow and ineffective learning; e.g., even (b) Congestion ratio for non-sparse (p = 1.0)
after more than 700 learning epochs, the produced routing bimodal DM sequences with 40% elephant flows
strategies were still over 9x away from the optimum, in terms
Figure 2: Representative Results for sof tmin-Routing
of max-link-utilization. As shown below, routing strategies
that fare significantly better can be generated much quicker.
We hypothesize that the large number of output parameters v. Let SPw (v, u, d) denote this length. Given a set of such
renders efficient learning very challenging. We thus seek a per-neighbor distances for a vertex u, the sof tmin function
class of routing policies that can be more concisely repre- can be applied to generate a probability distribution across
sented yet is still rich enough to attain high performance. these neighbors, which can be interpreted as u’s splitting
ratios for traffic destined for d. We refer to this scheme as
5. LEARNING SOFTMIN ROUTING “softmin-routing”. The higher the choice of γ to plug into the
We explore the following approach: instead of learning softmin function the closer the resulting routing scheme is to
splitting ratios directly, learn per-edge weights, and then use shortest path routing. We set γ = 2 in our experiments.
these weights to generate a routing strategy. Under this ap- Our reinforcement learning scheme maps k-long histories
proach, the output of the neural network is of size |E| (as of DMs to per-edge link weights. The reward is computed by
opposed to |V |2 × |E| and |V | × |E| for unrestricted and turning these weights into traffic splitting ratios and comput-
destination-based routing policies, respectively). ing the max-link-utilization of the resulting routing strategy
Generating forwarding rules from link weights is a classical with respect to the next DM. We realize this learning scheme
approach to routing [16, 50, 35]. We resort to the following via a 3-layers fully-connected network.
approach: We benchmark our results against three alternative non-ML-
The sof tminγ value for a vector of r coordinates α = based approaches to computing routing strategies: (1) P rev:
(α1 , α2 , . . . , αr ), for γ > 0, is the vector (also of r coor- optimizing softmin routing with respect to the most recent
−γαi
dinates) sof tminγ (α)i = Pre e−γαi , i ∈ 1, . . . , r. Ob- DM, (2) Avgk , optimizing softmin routing with respect to the
i=1
serve that sof tmin(α) can be regarded as a probability dis- k most recent DMs, and (3) Oblivious, the optimal oblivious
tribution (as the sum of all coordinates necessarily equals routing scheme [7] (which does not depend on the history of
1). DMs at all). 1
Consider a specific assignment of per-edge weights w = 1
Observe that both P rev and Avgk optimize softmin routing, as
{we }e∈E , a specific edge (u, v) ∈ E, and a specific traffic opposed to applying the optimal multicommodity flow computed for
destination d. Observe that, when viewing weights as dis- the input DM(s) to route the next DM. The reason is that the latter
option is not well defined (and, in particular, some of the end-points
tances, w determines the length of the shortest path from communicating in the next DM might not communicate at all in
vertex u to vertex d that goes through u’s immediate neighbor the input DM). We point out that in our experimentation softmin
Evaluation. We consider a communication network with learns a mapping from packet headers to outgoing ports. This
12 vertices and 32 edges. We use the adaptation of [13] dis- involves routers constantly exchanging information, at per
cussed in Section 4 to train a 3-layered fully-connected neural packet resolution, about their latencies with respect to differ-
network to generate the weights for softmin routing. We train ent destinations. We believe that operating at per packet level,
the neural network on 7 sequences of gravity and bimodal and in a decentralized fashion, poses significant challenges in
DMs of length 60 each, and tested on 3 such sequences. For terms of scalability and communication overhead.
gravity DM, the above process is repeated per sparsity levels
0.3, 0.6, and 0.9. For bimodal DMs the sparsity level is p = 1 7. CONCLUSION
and the percentage of large (elephant) flows amongst the com- We initiated the study of data-driven routing and presented
municating pairs is varied: 20/40/60% of all pairs. We set preliminary results for the context of intradomain traffic engi-
k = 10 and compute the optimal flow via the CPLEX [2] LP neering. Our preliminary results from experimentation with
solver. deep reinforcement learning show that extracting information
We show in Figure 2a representative results for gravity from the history of traffic scenarios to generate good routing
DMs and in Figure 2b representative results for bimodal based with respect to future traffic scenarios is an interesting ap-
DMs. The figures plot the ratio between the performance of proach. We view our results as a first step towards realizing a
the resulting routing strategies (for the test DM sequences), in much broad research agenda.
terms of averaged max-link-utilization (congestion), and the
optimum congestion. Interestingly, oblivious routing outper- Other routing domains. Optimizing routing is a keystone
forms the other two baselines. Observe that sof tmin-routing of networking research, investigated in a broad variety of
gets very close to oblivious routing’s performance for gravity contexts, including legacy IP networks [16], data centers [3],
DM sequences (and could perhaps outperform it with more private backbone networks [24], interdomain routing with
training), and significantly outperforms oblivious routing for BGP, overlay networks [6], publish-subscribe networks [14],
bimodal DM sequences. and more. Applying a data-driven routing approach to other
settings is an important research direction.
6. RELATED WORK Other objective functions. Our focus in this study was on
the classical objective of minimizing max-link-utiliziation.
Traffic engineering Traffic engineering (TE) is fundamental
Examining other well-studied multicommodity-flow-based
to networking, and hence vastly researched. Results on TE
objectives, e.g., maximizing overall goodput, is of great in-
range from routing in legacy, OSPF/ECMP networks [16,
terest, as is investigating performance metrics that relate to
10] to datacenter networks [3] and backbone networks [24].
latency, flow-completion-time, etc.
Softmin routing is inspired by the literature on TE via hop-by-
hop routing in IP networks e.g., PEFT [50] and HALO [35]. Predicting traffic-demands. Our preliminary results sug-
We find softmin routing especially convenient to use as it gest that well-predicting traffic conditions can, in general, be
involves fairly simple splitting traffic across next-hops, while very challenging. This motivates further research on super-
still achieving high performance. vised learning approaches to this challenge.
Reinforcement learning. Machine learning via deep-neural Better ML-guided intradomain traffic engineering. Our
networks has proven extremely useful in executing many dif- investigation of the application of ML to intradomain TE
ferent tasks: machine translation [8], image recognition [28], is only a first step in this direction. Important questions
and more. Specifically, reinforcement learning has been ap- remain regarding (1) the scalability of ML approaches in this
plied to playing computer games [37] and beating world- context, (2) the environments in which ML-guided routing
champions in strategic board games [44], robotics [27], 3D- outperforms traditional routing, and the causes for this, and (3)
locomotion tasks [41], and beyond. The development and the “right” choice of the duration of the time epoch be to strike
optimization of reinforcement learning algorithms is thus the the right balance between routing stability and reactiveness
subject of much attention. Our algorithms rely on utilizing to traffic changes.
TRPO [41]. We leave the evaluation of other reinforcement- Better experimental and empirical evaluations. Our ex-
learning algorithms [36, 49, 42] to future research. periments involved fairly small networks and synthetically-
ML applications to networking. Machine learning has generated traffic demands. Evaluating routing solutions in
been applied to various networking contexts including con- more realistic scenarios is important.
gestion control [48, 12], network bottleneck detection [46],
and optimizing datacetner power consumption [1], resource Acknowledgements
allocation [32], and bitrate selection for video streaming [33]. We thank Marco Chiesa for providing us with the code needed
Q-routing [31] applies Q-learning [47] to the network rout- to evaluate the oblivious routing scheme. We also thank the
ing context. Under Q-routing [31], each router individually anonymous HotNets reviewers for valuable feedback.
routing is consistently within at most 5% of the optimum traffic flow
with respect to any input DM and so very closely approximates this
strategy.
8. REFERENCES Agile Reconfigurable Datacenter Interconnect.
SIGCOMM, 2016.
[1] DeepMind AI Reduces Google Data Centre Cooling [19] D. Halperin, S. Kandula, J. Padhye, P. Bahl, and
Bill by 40%. [Link] D. Wetherall. Augmenting data center networks with
multi-gigabit wireless links. SIGCOMM, 2011.
[2] IBM ILOG CPLEX Optimizer.
[Link] [20] N. Hamedazimi, Z. Qazi, H. Gupta, V. Sekar, S. R. Das,
commerce/optimization/ J. P. Longtin, H. Shah, and A. Tanwer. Firefly: A
cplex-optimizer/[Link]. reconfigurable wireless data center fabric using
free-space optics. SIGCOMM, 2014.
[3] M. Al-Fares, S. Radhakrishnan, B. Raghavan,
N. Huang, and A. Vahdat. Hedera: Dynamic flow [21] K. Janocha and W. M. Czarnecki. On loss functions for
scheduling for data center networks. In NSDI, 2010. deep neural networks in classification. CoRR, 2017.
[4] M. Alizadeh, A. Greenberg, D. A. Maltz, J. Padhye, [22] W. S. Jewell. Multi-commodity Network Solutions.
P. Patel, B. Prabhakar, S. Sengupta, and M. Sridharan. 1966.
Data Center TCP (DCTCP). ACM SIGCOMM, 2010. [23] J. Jiang, V. Sekar, I. Stoica, and H. Zhang. Unleashing
[5] M. Allalouf and Y. Shavitt. Maximum flow routing with the potential of data-driven networking. COMSNETS,
weighted max-min fairness. In Quality of Service in the 2017.
Emerging Networking Panorama. [24] S. Kandula, D. Katabi, B. Davie, and A. Charny.
[6] D. Andersen, H. Balakrishnan, F. Kaashoek, and Walking the tightrope: Responsive yet stable traffic
R. Morris. Resilient overlay networks. 2001. engineering. 2005.
[7] Y. Azar, E. Cohen, A. Fiat, H. Kaplan, and H. Racke. [25] S. Kassing, A. Valadarsky, G. Shahaf, M. Schapira, and
Optimal oblivious routing in polynomial time. STOC, A. Singla. Augmenting data center networks with
2003. multi-gigabit wireless links. SIGCOMM, 2011.
[8] D. Bahdanau, K. Cho, and Y. Bengio. Neural machine [26] S. Knight, H. Nguyen, N. Falkner, R. Bowden, and
translation by jointly learning to align and translate. M. Roughan. The internet topology zoo. IEEE Journal
arXiv, 2014. on Selected Areas in Communications, 2011.
[9] C. M. Bishop. Pattern Recognition and Machine [27] J. Kober, J. A. Bagnell, and J. Peters. Reinforcement
Learning (Information Science and Statistics). Springer, learning in robotics: A survey. The International
2006. Journal of Robotics Research, 2013.
[10] M. Chiesa, G. Rétvári, and M. Schapira. Lying your [28] A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet
way to better traffic engineering. CoNEXT, 2016. classification with deep convolutional neural networks.
In NIPS, 2012.
[11] T. W. S. Chow and C. T. Leung. Nonlinear
autoregressive integrated neural network model for [29] P. Kumar, Y. Yuan, C. Yu, N. Foster, R. D. Kleinberg,
short-term load forecasting. IEE Proceedings - and R. Soulé. Kulfi: Robust traffic engineering using
Generation, Transmission and Distribution, 1996. semi-oblivious routing. CoRR, 2016.
[12] M. Dong, Q. Li, D. Zarchy, P. B. Godfrey, and [30] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner.
M. Schapira. PCC: Re-architecting congestion control Gradient-based learning applied to document
for consistent high performance. NSDI, 2015. recognition. Proceedings of the IEEE, 1998.
[13] Y. Duan, X. Chen, R. Houthooft, J. Schulman, and [31] M. Majer, C. Bobda, A. Ahmadinia, and J. Teich.
P. Abbeel. Benchmarking deep reinforcement learning Packet routing in dynamically changing networks on
for continuous control. ICML, 2016. chip. In Proceedings of the 19th IEEE International
Parallel and Distributed Processing Symposium
[14] P. T. Eugster, P. A. Felber, R. Guerraoui, and A.-M.
(IPDPS’05) - Workshop 3 - Volume 04, IPDPS ’05,
Kermarrec. The many faces of publish/subscribe. ACM
pages 154.2–, Washington, DC, USA, 2005. IEEE
Comput. Surv., 2003.
Computer Society.
[15] B. Fortz, J. Rexford, and M. Thorup. Traffic
[32] H. Mao, M. Alizadeh, I. Menache, and S. Kandula.
engineering with traditional ip routing protocols. Comm.
Resource management with deep reinforcement
Mag., 2002.
learning. HotNets, 2016.
[16] B. Fortz and M. Thorup. Increasing internet capacity
[33] H. Mao, R. Netravali, and M. Alizadeh. Neural adaptive
using local search. Computational Optimization and
bitrate streaming with pensive. SIGCOMM, 2017.
Applications, 2004.
[34] A. Medina, N. Taft, K. Salamatian, S. Bhattacharyya,
[17] B. Fortz and M. Thorup. Optimizing ospf/is-is weights
and C. Diot. Traffic matrix estimation: Existing
in a changing world. IEEE [Link]. A. Commun., 2006.
techniques and new directions. 2002.
[18] M. Ghodbadi, R. Mahajan, A. Phanishayee,
[35] N. Michael and A. Tang. Halo: Hop-by-hop adaptive
H. Rastegarfar, P.-A. Blanche, M. Glick, D. Kilper,
link-state optimal routing. IEEE/ACM Transactions on
J. Kulkarni, G. Ranade, and N. Devanur. ProjecToR:
 Networking, 2015. Flexible wireless links for data centers. SIGCOMM,
[36] V. Mnih, A. P. Badia, M. Mirza, A. Graves, T. Lillicrap, 2012.
T. Harley, D. Silver, and K. Kavukcuoglu.
Asynchronous methods for deep reinforcement learning.
ICML, 2016.
[37] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves,
I. Antonoglou, D. Wierstra, and M. A. Riedmiller.
Playing atari with deep reinforcement learning. CoRR,
2013.
[38] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu,
J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller,
A. K. Fidjeland, G. Ostrovski, et al. Human-level
control through deep reinforcement learning. Nature,
2015.
[39] M. Mohri, A. Rostamizadeh, and A. Talwalkar.
Foundations of Machine Learning. The MIT Press,
2012.
[40] M. Roughan, A. Greenberg, C. Kalmanek,
M. Rumsewicz, J. Yates, and Y. Zhang. Experience in
measuring backbone traffic variability: Models, metrics,
measurements and meaning. IMW, 2002.
[41] J. Schulman, S. Levine, P. Abbeel, M. Jordan, and
P. Moritz. Trust region policy optimization. ICML,
2015.
[42] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and
O. Klimov. Proximal Policy Optimization Algorithms.
ArXiv e-prints, 2017.
[43] F. Shahrokhi and D. W. Matula. The maximum
concurrent flow problem. J. ACM, 1990.
[44] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre,
G. van den Driessche, J. Schrittwieser, I. Antonoglou,
V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe,
J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap,
M. Leach, K. Kavukcuoglu, T. Graepel, and
D. Hassabis. Mastering the game of Go with deep
neural networks and tree search. Nature, 2016.
[45] R. S. Sutton and A. G. Barto. Reinforcement learning:
An introduction. MIT press Cambridge, 1998.
[46] H. Wang and B. Li. Lube: Mitigating bottlenecks in
wide area data analytics. HotCloud, 2017.
[47] C. J. Watkins and P. Dayan. Q-learning. Machine
Learning, 1992.
[48] K. Winstein and H. Balakrishnan. Tcp ex machina:
Computer-generated congestion control. SIGCOMM,
2013.
[49] Y. Wu, E. Mansimov, S. Liao, R. B. Grosse, and J. Ba.
Scalable trust-region method for deep reinforcement
learning using kronecker-factored approximation. ArXiv
e-prints, 2017.
[50] D. Xu, M. Chiang, and J. Rexford. Link-state routing
with hop-by-hop forwarding can achieve optimal traffic
engineering. INFOCOM, 2008.
[51] X. Zhou, Z. Zhang, Y. Zhu, Y. Li, S. Kumar, A. Vahdat,
B. Y. Zhao, and H. Zheng. Mirror mirror on the ceiling: