MidwayTE: Traffic Engineering with Segment Routing in SDN based WANs
George~Trimponias
Yan~Xiao
Hong~Xu
Xiaorui~Wu
and~Yanhui~Geng% <-this % stops a space \thanks{The work was supported in part by contract research between City University of Hong Kong and Huawei. The corresponding author is Hong Xu.
Segment routing is an emerging technology to simplify traffic engineering implementation in WANs. It expresses an end-to-end logical path as a sequence of segments, each of which is represented by a middlepoint. % Since a segment can be used for many logical paths, segment routing can dramatically reduce the number of flow entries needed for a SDN based WAN. In this paper, we arguably conduct the first systematic study of traffic engineering with segment routing in SDN based WANs. We first provide a theoretical characterization of the problem. We show that for general segment routing, where flows can take any path that goes through a middlepoint, the resulting traffic engineering is NP-hard. We then consider segment routing with shortest paths only, and prove that the traffic engineering problem can now be solved in (weakly) polynomial time when the number of middlepoints per path is fixed and not part of the input. Our results thus explain, for the first time, the underlying reason why existing work only focuses on segment routing with shortest paths. In the second part of the paper, we study practical traffic engineering using shortest path based segment routing. We note that existing methods work by taking each node as a candidate middlepoint. This requires solving a large-scale linear program which is prohibitively slow. We thus propose to select just a few important nodes as middlepoints for all traffic. We use node centrality concepts from graph theory, notably group shortest path centrality, for middlepoint selection. Our performance evaluation using realistic topologies and traffic traces shows that a small percentage of the most central nodes can achieve good results with orders of magnitude lower runtime. % low link utilizations while vastly reducing the network management complexity. % We propose MidwayTE, a novel TE architecture with segment routing in SDN based WANs. % Our main idea is to select just a few important nodes as middlepoints for {\em all traffic of the network, based on various centrality definitions from graph theory. This greatly reduces the complexity of middlepoint selection. % We provide a comprehensive theoretical study of network flow centrality for middlepoint selection, and prove important hardness results. % We then explore alternative path- and degree- based centrality definitions. % We formulate and study the MidwayTE problem with candidate middlepoints as a LP. % We conduct comprehensive performance evaluation of MidwayTE with realistic topologies and demands. Our results show that only a small percentage of the most central nodes can achieve low link utilizations while vastly reducing the network management complexity. % We make several technique contributions including we used the shortest path centrality to make middle point selection, formulate the traffic engineering optimization under new constraint that limit the maximum number of used middle points to further reduce the packet header overhead and present two concrete algorithms to solve the optimization problem. Extensive experiments could demonstrate that both schemes performance well in practice. % Segment routing is emerging network technology standardized by the IETF to benefit the traffic engineering and simplify the configuration in software-defined networks. It leverages the source routing paradigm, where the source calculates the path, breaks path up as segment and embeds the segments into packet header. To control the traffic in a more efficient way, these packets can be steered through middle points. We proposed
abstract.tex
%!TEX root = main.tex

\begin{abstract}

Segment routing is an emerging technology to simplify traffic engineering implementation in WANs. It expresses an end-to-end logical path as a sequence of segments, each of which is represented by a middlepoint. 
% Since a segment can be used for many logical paths, segment routing can dramatically reduce the number of flow entries needed for a SDN based WAN.
In this paper, we arguably conduct the first systematic study of traffic engineering with segment routing in SDN based WANs.
We first provide a theoretical characterization of the problem. We show that for general segment routing, where flows can take any path that goes through a middlepoint, the resulting traffic engineering is NP-hard. We then consider segment routing with shortest paths only, and prove that the traffic engineering problem can now be solved in (weakly) polynomial time when the number of middlepoints per path is fixed and not part of the input. Our results thus explain, for the first time, the underlying reason why existing work only focuses on segment routing with shortest paths.
In the second part of the paper, we study practical traffic engineering using shortest path based segment routing.
We note that existing methods work by taking each node as a candidate middlepoint. This requires solving a large-scale linear program which is prohibitively slow.  
We thus propose to select just a few important nodes as middlepoints for all traffic.
We use node centrality concepts from graph theory, notably group shortest path centrality, for middlepoint selection.
Our performance evaluation using realistic topologies and traffic traces shows that a small percentage of the most central nodes can achieve good results with orders of magnitude lower runtime.  

% low link utilizations while vastly reducing the network management complexity.

% We propose MidwayTE, a novel TE architecture with segment routing in SDN based WANs.
% Our main idea is to select just a few important nodes as middlepoints for {\em all} traffic of the network, based on various centrality definitions from graph theory. This greatly reduces the complexity of middlepoint selection.
% We provide a comprehensive theoretical study of network flow centrality for middlepoint selection, and prove important hardness results.
% We then explore alternative path- and degree- based centrality definitions.
% We formulate and study the MidwayTE problem with candidate middlepoints as a LP.
% We conduct comprehensive performance evaluation of MidwayTE with realistic topologies and demands. Our results show that only a small percentage of the most central nodes can achieve low link utilizations while vastly reducing the network management complexity.

% We make several technique contributions including we used the shortest path centrality to make middle point selection, formulate the traffic engineering optimization under new constraint that limit the maximum number of used middle points to further reduce the packet header overhead and  present two concrete algorithms to solve the optimization problem. Extensive experiments could demonstrate that both schemes performance well in practice.

% Segment routing is emerging network technology standardized by the IETF to benefit the traffic engineering and simplify the configuration in software-defined networks.  It leverages the source routing paradigm, where the source calculates the path, breaks path up as segment and embeds the segments into packet header.  To control the traffic in a more efficient way, these packets can be steered through middle points. We proposed

\end{abstract}

algorithm.tex
\section{Picking the Optimal Split Ratios}\label{sec:analysis}
\subsection{Optimal solution}
As the advanced setting does not affect the optimization complexity, we take the basic one as an example. 
The optimization problem is a mixed integer problem, which is NP-hard. However, it can be relaxed to a linear program.   Algorithm \ref{alg1} shows the  algorithm explaining the optimal solution.

Before analyzing the performance of Algorithm \ref{alg1}, we introduce some necessary notations.
When the candidate middle point set is not too large, we can exhaustedly select the combination of $k$ middle points out of  $M$, which is $C_M^k$ kinds of combinations. A generic $k$ middle points set is named  as $m_k$ and $u_m$ denotes the set of unused middle points under the constraint that $m_k\cup{u_k}=M$ and $m_k\cap{u_k}=\varnothing$.

Note that  in the Algorithm \ref{alg1}, a specific path $p$ has a binary value and the default value of $p$  is 0, which means unavailable.  $p=1$ denotes  the path is available. It is not necessary to ensure every middle point is used, since the number of used middle points can be less than $k$. We use $P_m$ to denote  the path set that  uses middle point $m_k$ and disjoint with the set $u_m$ as available. 
 
The objective function is as simple as an LP problem when we only split flows to the available paths.
Therefore, we can get the optimal solution after every  $k$ middle point combination is considered.

\renewcommand{\algorithmicrequire}{ \textbf{Input:}} %Use Input in the format of Algorithm  
\renewcommand{\algorithmicensure}{ \textbf{Output:}} %UseOutput in the format of Algorithm  

\begin{algorithm}[H]   
\caption{An optimal solution}   
\label{alg1}   
\begin{algorithmic}[1] 
\REQUIRE ~~\\ 
The network topology $G(V, E)$; The candidate middle point set $M$; The maximum number of used middle point $k$.
 \\
\ENSURE ~~\\ 
The split ratio  $x_{f,p}$;    
\WHILE{not all the $k$ middle point set is selected}  
 \STATE  Select a new $k$ middle point set, named it as $M_k$;

  \FOR{$p$ in $P_m$}
  \STATE  $p=1$; 
  
\ENDFOR  

\STATE Solve the minimize max utilization problem by split the flow to the available paths and get the $ \theta_{M_k}$

\ENDWHILE

\STATE Select the $M_k$ with minimum $ \theta_{M_k}$.


\end{algorithmic}  
\end{algorithm}  
\subsection{ Fast heuristic approach}

To quickly solve the optimization problem, we  propose a heuristic approach to greedily select the middle points.

As the statement is Algorithm \ref{alg2}, starting from an empty or partial solution (have selected some middle points but the number of used middle point is less than $k$), the heuristic approach expands the next middle point by greedily selecting the middle point that locally optimizes the objective function  most without violating any constraint.
Assume the current  used middle point set is $m_c$ and  $m_e$ be the middle points need to be explored.
$|m_c|$ is the current number of used middle point. By default,  $m_c$ is empty and $m_e=M$.
When we select a middle point, we make the paths that pass through the middle point in $m_c$ but not $m_e$ as available. 
The heuristic locally optimizes the expansion of middle point but does not provide any guarantee on the global optimality of the the objective function.  
\renewcommand{\algorithmicrequire}{ \textbf{Input:}} %Use Input in the format of Algorithm  
\renewcommand{\algorithmicensure}{ \textbf{Output:}} %UseOutput in the format of Algorithm  


\begin{algorithm}[H]   
\caption{A fast heuristic approach}   
\label{alg2}   
\begin{algorithmic}[1] 
\REQUIRE ~~\\ 
The network topology $G(V, E)$; The candidate middle point set $M$; The maximum number of used middle point $k$.
 \\
\ENSURE ~~\\ 
The split ratio  $x_{f,p}$;    
The number of used middle points  $y$.
\WHILE{ $|m_c| \leq k  $  \& add a middle point can reduce the max utilization}  
 \STATE  Expand the middle point $m$ from $m_e$    to $m_c$  with biggest reduction to max utilization. 
\STATE$|m_c|$ +=1.
\ENDWHILE

\STATE Output The split ratio  $x_{f,p}$;    
The number of used middle points  $y$.


\end{algorithmic}  
\end{algorithm}  



appendices.tex
%!TEX root = main.tex
\appendices

\section{Flow centralities }
\label{sec:appendix}


\subsection{Preliminaries}
\label{sec:flow-centrality}
The original flow centrality by Freeman et al. \cite{fbw1991} defines the flow centrality of a node $w\in V$ in a flow network $G=(V,E,c)$ as: \begin{equation}
\label{eq:trad-flow-centr}
\gamma(w)=\sum\limits_{s,t\in V|s\neq v\neq t}\frac{\nu_{max}^w(s,t)}{\nu_{max}(s,t)},
\end{equation}
where $\nu_{max}(s,t)$ the maximum flow in the single-commodity flow network with commodity $s$-$t$, and $\nu_{max}^w(s,t)$ the maximum flow through node $w$ in the single-commodity flow network with commodity $s$-$t$. Thus, the flow centrality of node $w$ represents the percentage of the maximum flow that can go through $w$ for a demand chosen uniformly at random.

For multi-commodity networks with $L$ commodities as described in Section \ref{sec:TE-prelim}, we can provide an alternative definition of flow centrality as follows: 
\begin{equation}
\label{eq:new-flow-centr}
\widetilde{\gamma}(w)=\frac{\nu_{max}^w(\bm{s},\bm{t})}{\nu_{max}(\bm{s},\bm{t})},
\end{equation}
which denotes the percentage of the maximum multi-commodity flow $\nu_{max}^w(\bm{s},\bm{t})$ that can go through node $w$ to the maximum multi-commodity flow.

The basic difference in the two definitions is that the former considers equiprobably all possible source-destination pairs, while the latter focuses on the actual commodities in the flow network. Thus, the former is based on the single-commodity formulation, and the latter on the multi-commodity one. 


\subsection{Hardness of Flow Centralities}


\begin{corollary}
Given a flow network $G=(V,E,c)$ and a node $w\in V$, it is NP-hard to compute flow centrality $\gamma(w)$ as in Equation \eqref{eq:trad-flow-centr}.
Furthermore, it is NP-hard to compute the flow centrality $\widetilde{\gamma}(w)$ of Equation \eqref{eq:new-flow-centr}.
\end{corollary}
\begin{proof}
The first statement is straightforward, since it uses $\nu_{max}^w(s,t)$ which is NP-hard by Proposition \ref{prop:NPhardness}.
For the second statement, note that $\widetilde{\gamma}(w)$ is a fraction of two terms. The denominator is the maximum multi-commodity flow $\nu_{max}$ which can be computed in strongly polynomial time \cite{Tardos1986}. If $\widetilde{\gamma}(w)$ could also be computed in polynomial time, then we could simply compute $\nu_{max}^w$ in polynomial time as the product of $\widetilde{\gamma}(w)$ and $\nu_{max}$, which is a contradiction since by Proposition \ref{prop:NPhardness}, it is NP-hard to compute $\nu_{max}^w$.
\end{proof}


\subsection{Group flow centrality}

In this section, we introduce the concept of multi-commodity group flow centrality, which can be seen as generalization of the flow centrality $\widetilde{\gamma}$ that we defined in Equation~\eqref{eq:new-flow-centr}.

\begin{definition}
The group multi-commodity maximum flow $\mathcal{GF}:2^V\rightarrow\mathbb{R}_{\geq 0}$ in a multi-commodity flow network is a function which, for any group of nodes $C\subseteq V$ of nodes, returns the maximum multi-commodity flow  $\mathcal{GF}(C)$ that can go through any node in $C$.

Furthermore, we call the maximum group flow that uses at most $N$ nodes as the $N$-group maximum flow.
\end{definition}

The group flow centrality for directed graphs is obviously NP-hard as a generalization of the $\widetilde{\gamma}$ flow centrality which is also NP-hard by Proposition~\ref{prop:NPhardness}. It is however possible to show NP-hardness by reduction from the maximum coverage problem, even for just one commodity. This is very important to also acquire approximability, as we discuss later.

\begin{proposition}
\label{group-NPhard}
The $N$-group maximum single-commodity flow is NP-hard.
\end{proposition}
\begin{proof}
We prove NP-hardness by reduction from the maximum coverage problem (MCP) \cite{nwf1978}, which is well-known to be NP-hard. In particular, assume a set $S$ of $m$ items $I=i_1,\dots,i_m$ and $n$ sets $S_1,\dots,S_n$ containing elements in $I$. Given a positive integer $N\leq n$, the MCP tries to select $N$ sets among $S_1,\dots,S_n$ such that the maximum number of elements are covered, i.e. the union of the selected sets has maximal size.
We can reduce the MCP to the $N$-group maximum multi-commodity flow by constructing a directed graph $G=(V,E)$ as follows. $V$ contains two dedicated nodes $s$ and $t$, one node $u_j$ for each item $i_j$ that appears in $I$, and one node $v_k$ for each set $S_k$. We then add one edge $(s,u_j)$ from $s$ to every node $u_j$, one edge $(v_k,t)$ from each node $v_k$ to $t$, and finally an edge $(u_j,v_k)$, if and only if set $S_k$ contains item $i_j$. We consider that each edge of the form $(s,u_j)$ has a capacity of 1, while all other edges have infinite capacity. Finally, the demand has an upper bound of $m$.

We now prove that the maximum coverage problem has a value equal to $C_{max}$, if and only if the $N$-group maximum flow has a value of $C_{max}$. Assume first that the MCP has a value of $C_{max}$. We can then construct a corresponding flow in $G$ in the following manner. First, we send one unit of flow from $s$ to node $u_j$ if and only if item $i_j$ is covered. Let $V_1\subseteq V$ be the subset of nodes $u_j$ where a unit of flow was sent from $s$. For each $u_j\in U$ we subsequently send one unit of flow to exactly one of the nodes $v_k$ that $u_j$ connects to, chosen uniformly at random. Let $V_2\subseteq V$ be the subset of nodes $v_k$ which receive flow from any node in $V_1$. We complete the construction by sending $l$ units of flow from every $v_k\in V_2$ to $t$, where $l$ is the number of nodes in $V_1$ that send a unit of flow to $v_k$. Now, the constructed flow is valid since it is easy to verify that it respects all capacity and conservation constraints. Based on that flow, we can also form a $N$-group flow. Indeed, by definition the MCP contains at most $N$ sets $S_i$, so there can be at most $N$ nodes of the form $v_k$ participating in the flow. Since the entire flow has to pass through these nodes, we can then claim that the above flow is a $N$-group flow passing through (at most) $N$ nodes of the form $v_k$. So, the $N$-group flow is at least $C_{max}$.

Furthermore, we can argue that that the $N$-group maximum flow cannot be greater than $C_{max}$. Indeed, if that were not the case, then that would imply that there is another group of $N$ nodes that can accept an even larger flow. Without loss of generality, we may assume that these nodes belong to $V$ only, since we can trivially replace any node in $U$ by any node in $V$ that it connects to and achieve a flow that is at least as large the original one. The key observation is that the group flow of $N$ nodes in $V$ has a value $C$, if and only if the coverage of the respective sets has a size of $C$. So, if there existed a group maximum flow with a greater value than $C_{max}$, then that would imply the existence of a maximum coverage of a value greater than $C_{max}$, which is a contradiction. 

The reverse direction can be proven similarly.
\end{proof}

The previous result immediately implies that the $N$-group multi-commodity flow is also NP-hard. It is interesting that the proof of Proposition \ref{group-NPhard} does not rely at all on the theory that we developed to show that the individual flow centrality is NP-hard in Proposition~\ref{prop:NPhardness}. It is well-known that the MCP cannot achieve a better approximation ratio than $O(1-\frac{1}{e})$, unless P=NP. We show below that this is also the case for the group multi-commodity flow by using results from submodular function maximization \cite{nwf1978,f1998}.

\begin{definition}
Consider a finite set of elements $U$ and a function $g:2^U\rightarrow\mathbb{R}_{\geq 0}$. We call $g$ monotone if adding an element to a set $S\in 2^U$ cannot cause the function to decrease, i.e., $g(S\cup\{v\})\geq g(S)$ for all $v\in U$ and $S\in 2^U$. Furthermore, we call $g$ submodular if the marginal gain from adding an element to a set $S$ is at least as high as the marginal gain from adding the same element to a superset of $S$, i.e., $g(S\cup\{v\})-g(S)\geq g(T\cup\{v\})-g(T)$ for all $v\in U$ and pairs of set $S\subseteq T$.
\end{definition}

\begin{lemma}
\label{monot_submod}
The function $\mathcal{GF}:2^{V-\{s,t\}}\rightarrow\mathbb{R}_{\geq 0}$ is (1) monotone, and (2) submodular.
\end{lemma}
\begin{proof}
For monotonicity, note that adding a node can never decrease the maximum group flow, since an additional node can never decrease the number of available paths to route the flow; in particular, adding a node $v\neq s,t$ to a set $S$ can either increase the number of available paths to route the flow, or leave the number of paths unchanged, if all paths that go through $v$ already go through nodes in $S$.

It is also simple to prove submodularity by noticing that the augmenting $s$-$w$-$t$ algorithm can pick the augmenting paths arbitrarily. For $T\cup\{v\}$, we can then first saturate paths through $S$, then through $T-S$, and finally through $v$. For $S\cup\{v\}$, we can then first saturate paths through $S$, and finally through $v$. Since paths through $T-S$ may overlap with paths through $v$, it is straightforward that the marginal gain from adding $v$ in the former case can never exceed the marginal gain from the latter.
\end{proof}

%For submodularity, note that the maximum value of the group maximum flow is equal to the minimum capacity of any $s$-$\mathcal{W}$-$t$ cut. Now, the trick is to notice that we n

%For submodularity, note that adding a node $v$ to a superset $T\superseteq S$ can lead to at most as many new paths to route the flow compared to adding the same node $v$ to $S$. Note that 

\begin{proposition}
\label{greedy}
Consider the greedy algorithm that each time picks the node in $V-\{s,t\}$ that maximizes the marginal utility to add to the group set. Let $S^*$ be the subset of size $k$ of $V-\{s,t\}$ that maximizes the group $\mathcal{GF}$. Then the set $S^g$ that the greedy selects satisfies the property that $\mathcal{GF}(S^g)\geq (1-\frac{1}{e})\cdot\mathcal{GF}(S^*)$, i.e., $S^*$ provides a $(1-\frac{1}{e})$- approximation. Furthermore, unless P=NP, no polynomial algorithm can achieve a $(1-\frac{1}{e}+o(1))$- approximation ratio.% for $\mathcal{GF}$.
\end{proposition}
\begin{proof}
$\mathcal{GF}$ is a non-negative monotone submodular function. The approximation ratio for the greedy algorithm then follows directly from submodular function maximization \cite{nwf1978}. The impossibility result on the approximation ratio follows from \cite{f1998}.
\end{proof}

However, note that applying the greedy algorithm by Nem-hauser et al. \cite{nwf1978} to approximate the maximal group flow is NP-hard, since even computing the maximum $s$-$w$-$t$ node is NP-hard by Proposition \ref{group-NPhard}. So, the greedy algorithm will also be NP-hard.



For the undirected group flow centrality, we can get a similar result as in Proposition~\ref{greedy}. The main difference is that in the undirected case a $s$-$w$-$t$ path consists of undirected rather than directed edges. In terms of computational complexity, note that now each step of the greedy algorithm runs in (weakly) polynomial time (see Appendix~\ref{sec:undirected}), so the time complexity for the greedy algorithm will be (weakly) polynomial, as opposed to the directed case where it is NP-hard. In fact, a strongly polynomial algorithm may also be possible, in a similar spirit to the results in \cite{Tardos1986}.



\section{The undirected case}
\label{sec:undirected}

We demonstrate a very interesting dichotomy between the cases of a directed and undirected graph. In particular, we show that the maximum multi-commodity $\bm{s}$-$w$-$\bm{t}$ flow in a undirected graph can be computed in polynomial time. Note that the main difference between the directed and the undirected flow is that the directed assumes separate capacities for each direction $(u,v)$ and $(v,u)$ whereas the undirected assumes a single capacity for the undirected edge $e$ which can be arbitrarily allocated in both directions, which upper bounds the \textit{total} flow that we can send in both directions (but not in any individual direction).

\begin{proposition}
The maximum multi-commodity flow $\nu_{max}^w$ in any undirected graph $G=(V,E)$, $w\in V$, can be computed exactly in (weakly) polynomial time.
\end{proposition}
\begin{proof}
Assume a multi-commodity undirected graph $G=(V,E)$ with $L$ commodities of the form $(s_i,t_i)$. For simplicity, we assume infinite maximum demands $D_i$ so that the demand constraint becomes redundant. We construct a directed graph $G'=(V',E')$ from $G$ as follows. We first replace each undirected edge $(u,v)\in E$ by two directed edges $(u,v)$ and $(v,u)$ edges. The capacities on the two directed edges are equal to the original capacity $c(e)$ of the undirected edge. We next introduce $L$ new nodes $z_1,\dots,z_L$ (one for each commodity), and for each $z_i$ we add the two directed edges $(s_i,z_i)$ and $(t_i,z_i)$. Finally, we introduce a node $z$ and $L$ directed edges $(z_i,z)$ from each $z_i$ to $z$. Thus, we have that $V'=V\cup\{z_1,\dots,z_L,z\}$ and $E'=E_G\cup(\cup_{i}\{(s_i,z_i),(t_i,z_i),(z_i,z)\})$, where $E_G$ are the edges that we got by replacing each undirected edge in $E$ by two directed edges.  The capacities of the newly constructed edges of the form $(s_i,z_i),(t_i,z_i),(z_i,z)$ are infinite. 

Next, we claim that the maximum flow in $G$ can be computed by considering the following arc-based linear program:
\begin{align}
\text{maximize } & \mathcal{V}=\sum_{i=1}^L\sum_{e\in {w}^{+}}f_i(e)\notag\\
\text{subject to } & \sum_{i=1}^L f_i(e)\leq c(e), \forall e\in E'\label{c1}\\
& \sum_{e\in u^+}f_i(e)=\sum_{e\in u^-}f_i(e), \forall i, \forall u\in V', w\neq u\neq z\label{c2}\\
& f_i(u,v) + f_i(v,u) \leq c(e), \forall i, \forall e=(u,v)\in E\label{sum}\\
& f_i(e)\geq 0, \forall e\in E', \forall i\in\{1,\dots,L\}\label{c3}\\
& f_j(s_i,z_i) = 0, \forall i,j\in\{1,\dots,L\}\text{ with } i\neq j\label{before-last}\\
& f_i(s_i,z_i) = f_i(t_i,z_i), \forall i\in\{1,\dots,L\}\label{last}
\end{align}

The above LP computes the maximum flow from $w$ to $z$, where the total flow is composed of $L$ separate sub-flows, one for each commodity. The sub-flow for commodity $i$ can be sent from $w$ to $z_i$ through either $s_i$ or $t_i$. Constraints~\eqref{c1},~\eqref{c2},~\eqref{c3} are the link capacity, node conservation and positive flow constraints, respectively. Constraint \eqref{sum} is necessary to  make sure that the sum of flow units in each of the two directed edges does not exceed the capacity of the original undirected edge. Constraint \eqref{before-last} implies that node $z_i$ can only receive flow from commodity $i$. Constraint \eqref{last} is especially important because it ensures that the sub-flow for commodity $i$ sent through $s_i$ is the same as the one sent through $t_i$.

Now, we establish the equivalence between the original problem and the above LP by showing that (i) $2\cdot \nu_{max}^w\leq \mathcal{V}^*$, and (ii) $\mathcal{V}^*\leq 2\cdot \nu_{max}^w$. We start with (i). Assume any maximum flow through $w$ with value $\nu_{max}^w$ in $G$. We first construct the corresponding flow in $G'$. We note that the flow in $G$ consists of $L$ sub-flows, one for each commodity $i$, that send flow from $s_i$ to $t_i$ through $s_i$-$w$-$t_i$ paths. The idea is then to reverse the direction of each sub-flow in the part from $s_i$ to $w_i$, so that it now sends to the opposite direction. We then send $\nu(f_i)$ units of flow from $s_i$ to $z_i$, $\nu(f_i)$ units of flow from $t_i$ to $z_i$, and $2\cdot \nu(f_i)$ units of flow from $z_i$ to $z$. Note that that is a valid flow since it respects all constraints in the LP, and it has a value $2\cdot(\nu(f_1)+\cdots+\nu(f_L))=2\cdot\nu_{max}^w$. But then the maximum flow will be at least as large, hence $2\cdot \nu_{max}^w\leq \mathcal{V}^*$.

For the reverse direction (ii), assume a maximum flow in $G'$. Then for each commodity $i$ half units are sent from $w$ to $s_i$ and half from $w$ to $t_i$ (and subsequently $z_i$ and $z$) due to constraint \eqref{last}. Again, the idea is to reverse the flow $f_i$ in all paths from $w$ to $s_i$. For each edge of $G$ we then send on each direction as many units of flow as we send in $G'$ (after reversing the direction from $w$ to $s_i$). The key is that in graph $G'$ the same amount of flow is sent from $w$ to $s_i$ and $w$ to $t_i$, which implies that the constructed flow in $G$ will respect all capacity and conservation constraints, including for node $w$. The value of the flow in $G$ is half that in $G'$, thus for the maximum flow on $G$ we will trivially have that $\mathcal{V}^*\leq 2\cdot \nu_{max}^w$.

Since the constraints of the LP have a size that is polynomial in $V$ and $E$, and LP runs has a (weakly) polynomial complexity in terms of the LP size \cite{K1980,K1984}, we immediately deduce that computing the maximum $\bm{s}$-$w$-$\bm{t}$ flow in an undirected graph $G=(V,E)$ can be solved in (weakly) polynomial time, which concludes the proof.
\end{proof}
backgd.tex
%!TEX root = main.tex
\section{A Primer on Segment Routing }
\label{sec:bg}
% \subsection{Traffic Engineering}
We start by introducing segment routing and the benefit of applying it to TE. We next explain related work on segment routing.



% \subsection{Segment routing}
% \label{sec:sr}

Segment routing \cite{segment1, segment2, segment3} is a recently proposed architecture based on source routing that facilitates packet forwarding via a series of segments. It can be directly applied to MPLS and IPv6.
The key idea is that the ingress switch can break up the end-to-end logical path into segments, and specify this logical path as a series of {\em middlepoints} to traverse.
Figure~\ref{SR} illustrates an example of segment routing. The ingress switch S embeds a stack of segment labels (MPLS labels for example) into the packet header to specify the entire path. Note here each label just represents a middlepoint in the network, i.e. we consider node segments here \cite{segment1, segment2, segment3}. The top label is the active label that instructs packet forwarding. Then the packet is sent to the next label M$_1$ along the shortest path(s). ECMP is used if there are multiple shortest paths. When the packet reaches M$_1$, the top label M${_1}$ is popped and the packet is routed to the next label M$_2$. Finally, all the labels are popped and the packet arrives at the egress switch D.

% Generally, a segment is an MPLS label
% where has three operations: push, pop and continue.  The segment has different types and in this paper we introduce the node segment as node segments can be used to describe paths in network topology.   Node segment contains the unique Node-SID, which identify the next router and  a list of node segments defines the path from ingress to egress. Note that between two segments, the segment routing  explores the Equal-Cost Multi-Paths (ECMP).

\begin{figure}[H]
\begin{center}
\includegraphics [scale = 0.6]{figures/sr.pdf}
% \vspace{-4mm}
\caption{A segment routing example from S to D through middlepoints M$_1$ and M$_2$.}
\label{SR}
\end{center}
\vspace{-4mm}
\end{figure}

One key advantage of segment routing is that it can greatly reduce routing cost in terms of number of flow table entries required. To see this, consider the next example shown in Figure~\ref{fig:showcase}. Three {\em demands}\footnote{When it is clear from the context, we use the terms {\em commodities}, {\em demands}, and {\em flows} interchangeably.}, which refer to the aggregated flows between a unique ingress-egress switch pair, are routed through three paths P1, P2, and P3 to their respective destinations. With tunnel-based forwarding in SDN \cite{JKMO13,HKMZ13}, each intermediate switch needs to store flow entries for each demand, and in total 12 entries are needed as shown in Table~\ref{table:rules}. Now if segment routing is applied with node E as the middlepoint, the three paths can be represented using just two labels each as in Figure~\ref{fig:showcase}, and switches C and D only need to have one entry in order to forward to the middlepoint E. The total number of entries is reduced to only 8, with 33.3\% saving.

\begin{figure}[htp]
\centering
\includegraphics[width=0.9\linewidth]{figures/showcase.pdf}
% \vspace{-4mm}
\caption{An example where segment routing saves flow table entries. }
\label{fig:showcase}
% \vspace{-3mm}
\end{figure}

\begin{table}[h]
\centering
\label{table:rules}
\resizebox{0.7\columnwidth}{!}{%
\begin{tabular}{|c|c|c|}
\hline
Node & w.o. segment routing  & w. segment routing \\ \hline
A & 2 & 2 \\ \hline
B & 1 & 1 \\ \hline
C & 3 & 1 \\ \hline
D & 3 & 1 \\ \hline
E & 3 & 3 \\ \hline
\end{tabular}
}
\vspace{2mm}
\caption{Number of flow table entries for the example in Fig.~\ref{fig:showcase}. }
\end{table}


% \subsection{Prior work }
% \label{sec:related_SR}
% We briefly review prior work in segment routing.
Given the potential of segment routing, some recent work has started to investigate how to apply it in TE.
% Segment routing is a relative new technology and only has a limited number of research work.
In \cite{bhatia2015optimized},  the authors propose solutions for determining the optimal TE with segment routing and ECMP. In their scheme, they regard all nodes except for the source and the destination as candidate middlepoints, and split flows across exactly one middlepoint. Although they limit the number of middlepoints to one for each logical path, since they consider all the intermediate nodes for one demand, the search space for middlepoints is very large. The algorithm thus cannot scale to handle medium to large scale networks.
% For a large network with many demands, many nodes are selected as middlepoints to route them which still incurs significant overhead in terms of flow entries on the switches.
Hartert et al. \cite{hartert2015solving,HVSB15} studied a similar TE problem with segment routing under a constraint programming framework. Their middlepoint selection method also takes every node as a potential candidate on a per-demand basis, and they have to resort to heuristics to reduce the run time of the algorithm.

The exploration of segment routing in TE has been ad-hoc so far.
Existing work uses heuristics \cite{HVSB15} or some special for of segment routing \cite{bhatia2015optimized} without theoretical justification.
We are thus motivated to conduct a systematic study of segment routing in TE, including the theoretical characterization of the hardness results of various forms of segment routing, and practical algorithms of solving the problems.

Given our focus on TE, in the next section we review the two common types of TE formulations. We subsequently reveal an interesting connection between them, which we utilize later in the proof of several hardness results.

% This motivates us to consider a different approach to middlepoint selection. Instead of taking every node as a candidate middlepoint, we strive to identify a very small number of nodes that are essential to the connectivity of the network topology as the middlepoints. The key intuition is that, similar to social networks, some nodes in a WAN are inherently more important and they serve naturally as middlepoints to perform segment routing.
% We further constrain TE to use only the selected middlepoints for routing {\em all} of the demands. Therefore, middlepoint selection only needs to run once for all, and the number of flow entries can also be greatly reduced.


%{\color{red} need a better connection here}
%Next we present our analysis of applying centrality in graph theory to middlepoint selection in WANs.

%The remainder of the paper is organized as follows. Section \ref{sec:TE} reviews the two major types of TE and reveals their connection. Section \ref{sec:theory} discusses the hardness of general segment routing. Section \ref{sec:opt} investigates shortest-path based segment routing and proves hardness when cycles are not allowed. Section \ref{sec:2pass} discusses practical middlepoint selection based on graph-theoretic centrality. Section \ref{sec:evaluation} contains the experimental evaluation. Section \ref{sec:related} discusses the related work, and section \ref{sec:conclusion} concludes the paper.

% Our scheme is different, since we select the middle point first and only route the flows to the selected middle points. For each source- destination demand, we limited the number of used middle point and for all the demands we further limit the number of used middle point by $k$.


  % The works in \cite{hartert2015declarative} further explore the works in \cite{hartert2015solving} and present program intra-domain forwarding in carrier-grade networks based on segment routing.





conclusion.tex
\section{Conclusion}
\label{sec:conclusion}

We have conducted the first systematic study of traffic engineering with segment routing in SDN based WANs. We showed that TE for the general segment routing is NP-hard, while segment routing with shortest paths is polynomial when the number of middlepoints per logical path is fixed and not part of the input. We also studied practical TE with shortest path based segment routing, and proposed to select just a few important nodes for all network traffic using graph theoretic centrality concepts. Our performance evaluation demonstrated that just a small percentage of powerful nodes can achieve good results at very low time complexities.

%We have proposed MidwayTE, a novel TE architecture with segment routing in SDN based WANs, which selects only few central switches as middlepoints to route the entire network traffic. To define node centrality, we employ several concepts from graph theory. Furthermore, we theoretically investigate flow centralities and acyclic segment routing, and provide several hardness results. Our experimental evaluation with realistic topologies and demands demonstrates that just a small percentage of powerful nodes can vastly simplify network management by orders of magnitude, while achieving low running times and satisfactory link utilizations.

evaluation.tex
%!TEX root = main.tex

\section{Evaluation}
\label{sec:evaluation}

In this section, we conduct trace-driven simulations to evaluate the performance of centrality based middlepoint selection methods.
The experiments are designed to answer the following important questions:
\begin{itemize}[noitemsep]
\item What is the best parameter setting for centrality based middlepoint selection? Specially, how many middlepoints per commodity, and how many middlepoints in total should we use?
\item How does our centrality based approach compare to existing work, in terms of both performance and complexity?
\item How do various centrality definitions perform against each other?
\end{itemize}

\subsection{Methodology}
\label{sec:methodology}

We use two network topologies from the dataset provided by DEFO (Declarative and Expressive Forwarding Optimizer) \cite{defo} which is used in \cite{HVSB15}. %The average node degree of topologies are about 4 or 5.
One is a synthetic network with 100 nodes ({\tt synth100} in the dataset), and the other is a real network with 161 nodes ({\tt rf3257} in the dataset). Table~\ref{table:dataset} provides more details about the networks.
The DEFO dataset also contains information of commodity flows (simply referred to as flows hereafter) for these topologies. For the real 161-node topology the flows are provided by the ISP \cite{HVSB15}. For the synthetic topology the demand matrices are computed using the approach in \cite{M05}. As explained in \cite{HVSB15}, this approach uses a gravity model fed with i.i.d. exponential random variables. It produces realistic demand matrices as shown in \cite{M05,HVSB15}.
\begin{table}[!h]
\centering
\resizebox{0.8\columnwidth}{!}{%
\begin{tabular}{|l|l|l|l|l|}
\hline
Type&ID&\# nodes&\# links&\# flows\\ \hline
% Synthetic&synth50&50&276&2449 \\ \hline
Synthetic&{\tt synth100} &100&572&9817 \\ \hline
Real&{\tt rf3257} &161&656&25486 \\ \hline
\end{tabular}
}
\vspace{3mm}
\caption{Dataset Summary.}
\label{table:dataset}
% \vspace{-3mm}
\end{table}

We perform simulations on servers each with a 2.2~GHz 64-bit 8-Core Xeon processor and 128~GB memory. We use the {\tt cvxpy} \cite{cvxpy} modeling language with the {ECOS solver} \cite{D13} to solve the LPs.
Our evaluation compares the following schemes:
\begin{itemize}[noitemsep]
\item {\em Baseline}: Traditional approach of applying segment routing studied in Sec.~IV of \cite{bhatia2015optimized}. Specifically, the TE problem assumes that every node is a candidate of middlepoint, and exactly one middlepoint is used for each flow. Only shortest paths are used for segment routing.
\item {\em Random}: Our approach where a total of $K$  middlepoints are randomly selected and used in TE problems \temf~and \telu.
\item {\em Shortest-path centrality (SP)}: Our approach where middlepoints are selected using shortest-path centrality as explained in \cref{sec:2pass} for TE.
\item {\em Group shortest-path centrality (GSP)}: Our approach where middlepoints are selected using group shortest-path centrality.
\item {\em Degree centrality (Degree)}: Our approach where middlepoints are selected using degree centrality.
\end{itemize}


\subsection{Microscopic Performance }
\label{sec:microscopic}

First we aim to understand the microscopic performance of our centrality based approach.
There are two key parameters affecting our approach in general: the number of middlepoints per flow $M$, and the total number of available middlepoints for all flows $K$. Their effects need to be thoroughly understood before we compare our approach to existing methods.

\noindent{\bf Number of middlepoints per flow $M$}:
We begin by trying to answer how many middlepoints should be used for each flow. Note that there is an inherent tradeoff: more middlepoints per flow leads to more flexibility in constructing the paths and balancing the traffic, and thus better performance. On the other hand it also means more overhead in terms of higher complexity of the TE algorithms.

To demonstrate this tradeoff, we use \telu~and compute the maximum link utilization with our centrality based middlepoint selection when the number of middlepoints per flow $M$ is equal to 1 or 2. We use the {\tt synth100} network with 100 nodes. We choose 1000 flows for the topology randomly for ten times and report the average. We apply {\em GSP} to select the middlepoints, and vary the total number of available middlepoints $K$ from 2 to 6. For a given $K$, the flows are identical for different values of $M$.
Note we also experiment with \temf~and the 161-node network; the results are qualitatively similar and omitted here for space.

\begin{figure}[thb]
\centering
\begin{minipage}{0.48\linewidth}
\includegraphics[width=\linewidth]{figures/ul_path_k100}
      \caption{Maximum link utilization of the 100-node network with 1000 flows and varying $M$.}
      \label{fig:ul_path_k100}
      \end{minipage}
   %
\begin{minipage}{0.48\linewidth}
   \includegraphics[width=1\linewidth]{figures/M2_LPtime_100}
      \caption{LP solving time of \telu~on the 100-node network with 1000 flows and varying $M$.}
      \label{fig:time_path_k100}
      \end{minipage}
% \vspace{-3mm}
\end{figure}

Fig.~\ref{fig:ul_path_k100} and Fig.~\ref{fig:time_path_k100} depict the results. We find that interestingly, the maximum link utilizations for $M=1$ and $M=2$ are quite similar. Yet the time of solving the TE with $M=2$ is much higher than $M=1$ as shown in Fig.~\ref{fig:time_path_k100} (a difference of almost 20x) when $K=6$). Given that the middlepoints are central, there is indeed a low probability that a bottleneck link exists between two middlepoints. Hence, maximum link utilization is largely determined by the bottleneck links between either the source and the middlepoint, or between the middlepoint and the destination. Therefore we conclude that 1 middlepoint per flow is good enough for performance, and use that throughout the remainder of the experiments.


\noindent{\bf Number of total middlepoints $K$}:
We next run experiments to verify that just a few central middlepoints are sufficient to achieve satisfactory TE performance.
% If more middlepoints are selected as candidates for TE, the link utilization will also decrease. Yet more middlepoints also means the centrality algorithms need to run longer. Thus we design some experiments to verify this.
We vary the total number of middlepoints $K$ from 1 to 6 for \telu~and from 1 to 8 for \temf. The middlepoints are selected using {\em Random}, {\em SP}, {\em GSP}, and {\em Degree} as explained in \cref{sec:methodology}.
We use both the 100-node and 161-node networks, and randomly choose 1000 flows and 2000 flows respectively for 10 runs. We report the average and standard deviation results.
Since {\em Random} is non-deterministic, we randomly select 5 sets of middlepoints for each of the 10 flow sets, resulting in 50 runs in total for {\rm Random}.
For \temf, in order to make the results more readable, we scale the traffic volumes by 10 times for 100-node topology and 40 times for 161-node topology, respectively.


We depict the results in Fig.~\ref{fig:ul_middle_points100}--Fig.~\ref{fig:161_multi40_2000_middle}.
As expected, more available middlepoints improve TE performance.
For \telu, when there is only one available middlepoint for the network, every flow has to be routed through it, which severely limits the path choice and the maximum link utilization is way above 1 for {\em Random} and over 1 for the other schemes. With two middlepoints the maximum link utilization is dramatically reduced by over 50\% for most schemes as seen in Fig.~\ref{fig:ul_middle_points100} and Fig~\ref{fig:ul_middle_points161}.
The same can be observed for \temf~in Fig.~\ref{fig:100_multi10_1000_middle} and Fig.~\ref{fig:161_multi40_2000_middle}.
The demand satisfaction ratio is improved by around a factor of 2 when $K$ increases to 2.


\begin{figure}[h]
\centering
\begin{minipage}{0.49\linewidth}
   \includegraphics[width=\linewidth]{figures/ul_middle_points100}
      \caption{100-node network with 1000 flows of \telu.}
      \label{fig:ul_middle_points100}
\end{minipage}
\begin{minipage}{0.49\linewidth}
\includegraphics[width=\linewidth]{figures/ul_middle_points161}
   % where an filename suffix will be assumed under latex, and a
   % .pdf suffix will be assumed for pdflatex %
   %\subsection{Sequential Hypothesis Testing}
      \caption{161-node network with 2000 flows of \telu.}
      \label{fig:ul_middle_points161}
\end{minipage}
% \vspace{-3mm}
\end{figure}

\begin{figure}[h]
\centering
\begin{minipage}{0.49\linewidth}
   \includegraphics[width=\linewidth]{figures/100_multi10_1000_middle}
   % where an filename suffix will be assumed under latex, and a
   % .pdf suffix will be assumed for pdflatex %
   %\subsection{Sequential Hypothesis Testing}
      \caption{100-node network with 1000 flows of \temf.} \label{fig:100_multi10_1000_middle}
\end{minipage}
%
\begin{minipage}{0.49\linewidth}
\includegraphics[width=\linewidth]{figures/161_multi40_2000_middle}
   % where an filename suffix will be assumed under latex, and a
   % .pdf suffix will be assumed for pdflatex %
   %\subsection{Sequential Hypothesis Testing}
      \caption{161-node network with 2000 flows of \temf.} \label{fig:161_multi40_2000_middle}
\end{minipage}
\vspace{-3mm}
\end{figure}

Another important observation is that the TE performance exhibits diminishing marginal gains as $K$ increases.
For \telu, when more than 4 middlepoints are used, very limited gains are observed ($<$10\%) in Fig.~\ref{fig:ul_middle_points100} and Fig.~\ref{fig:ul_middle_points161}.
For \temf, beyond 7 middlepoints there is little demand satisfaction improvement especially for {\em GSP} in Fig.~\ref{fig:100_multi10_1000_middle} and Fig.~\ref{fig:161_multi40_2000_middle}.
On the other hand the runtime of the TE algorithms increases dramatically due to the growing size of the LP problems. Take the 161-node network for instance. The LP time for \telu~increases by $\sim$50\% when $K$ increases from 4 to 6 as shown in Table~\ref{table:time_lu}, and from 6 to 8 for \temf~as in Table~\ref{table:time_mf}.

\begin{table}[!h]
\centering
\resizebox{0.8\columnwidth}{!}{%
\begin{tabular}{|l|c|c|c|c|c|c|}
\hline
\backslashbox{Scheme}{$K$}&1&2&3&4&5&6 \\ \hline
% Synthetic&synth50&50&276&2449 \\ \hline
Random&11.25&24.21&36.50&51.29&66.00&81.48 \\ \hline
SP&9.79&19.56&29.35&38.31&46.27&54.25 \\ \hline
Degree&8.92&17.83&28.49&42.98&55.45&64.96 \\ \hline
GSP&9.75&19.54&29.30&39.64&54.85&70.81 \\ \hline
\end{tabular}
}
\vspace{3mm}
\caption{Average LP time (seconds) of 161-node network with 2000 flows of \telu.}
\vspace{-3mm}
\label{table:time_lu}
\end{table}

\begin{table}[!h]
\centering
\resizebox{0.98\columnwidth}{!}{%
\begin{tabular}{|l|c|c|c|c|c|c|c|c|}
\hline
\backslashbox{Scheme}{$K$}&1&2&3&4&5&6&7&8 \\ \hline
% Synthetic&synth50&50&276&2449 \\ \hline
Random&12.10&23.87&32.78&45.91&60.04&76.43&100.02&110.00 \\ \hline
SP&10.63&19.49&26.46&35.66&43.36&53.80&72.30&82.26 \\ \hline
Degree&9.92&17.68&26.25&41.21&52.52&60.47&78.97&86.62 \\ \hline
GSP&10.42&20.00&26.83&38.35&52.79&67.49&81.44&91.88 \\ \hline
\end{tabular}
}
\vspace{3mm}
\caption{Average LP time (seconds) of 161-node network with 2000 flows of \temf.}
\label{table:time_mf}
\vspace{-3mm}
\end{table}

Based on the above results, we conclude that 4 middlepoints for \telu   ~and 7 middlepoints for \temf~are the sweetspots of the tradeoff between performance and complexity. We thus use these settings in the rest of the experiments.
% Thus all middlepoint selection algorithms output 4 nodes. Note that this holds for all three networks we considered with different scales.
This confirms the intuition behind our centrality based approach, namely, that it suffices to just use a small fraction of nodes as middlepoints (2.48\%--7\% of nodes) to achieve satisfactory performance.


\subsection{Comparison with Baseline}
\label{sec:vsTE}

Our motivation of using centrality based middlepoint selection is to reduce the high complexity of existing approaches, which takes  all nodes in the network as middlepoints \cite{bhatia2015optimized} as discussed in \cref{sec:intro}.
% This means that for 100-node topology for example, there are 98 candidate middlepoints for each demand.
We now compare our approach against {\em Baseline} to validate its effectiveness in this regard. The experiments here are performed on the 100-node topology for both TE formulations.
The maximum link utilization and LP time of \telu~are shown in Fig.~\ref{fig:baseline_LU_util} and Fig.~\ref{fig:baseline_LU_LP}, respectively. The demand satisfaction ratio and corresponding LP time are depicted in Fig.~\ref{fig:baseline_MF_per} and Fig.~\ref{fig:baseline_MF_LP}, respectively, for \temf.
We scale the demands of flows by a factor of 2 for \telu~and a factor of 40 for \temf.

% But it needs nearly three hours for LP time. So we just run from 500 to 700 demands to make sure the LP time is less than 1000 seconds.

\begin{figure}[h]
\centering
\begin{minipage}{0.49\linewidth}
   \includegraphics[width=\linewidth]{figures/baseline_LU_util}
      \caption{Performance of \telu~with different centralities and {\em Baseline}.} \label{fig:baseline_LU_util}
\end{minipage}
%
\begin{minipage}{0.49\linewidth}
\includegraphics[width=\linewidth]{figures/baseline_LU_LP}
      \caption{LP time of \telu~with different centralities and {\em Baseline}. Note the log scale of the y-axis.} \label{fig:baseline_LU_LP}
\end{minipage}
\vspace{-3mm}
\end{figure}

\begin{figure}[h]
\centering
\begin{minipage}{0.49\linewidth}
   \includegraphics[width=\linewidth]{figures/baseline_MF_per}
      \caption{Performance of \temf~between different centralities and {\em Baseline}.} \label{fig:baseline_MF_per}
\end{minipage}
%
\begin{minipage}{0.49\linewidth}
\includegraphics[width=\linewidth]{figures/baseline_MF_LP}
      \caption{LP time of \temf~between different centralities and {\em Baseline}. Note the log scale of the y-axis.} \label{fig:baseline_MF_LP}
\end{minipage}
% \vspace{-3mm}
\end{figure}

Notice that with {\em Baseline}, the TE problems have much more variables and constraints due to the large number of middlepoints. As a result, our machines can only solve \telu~with $\sim$400 flows, and \temf~with $\sim$1500 flows.
{For problems beyond these scales the solver reports error messages.}
Recall that with centrality based middlepoint selection the solver can easily handle problems with 3000 flows even for the bigger 161-node topology as we will show in \cref{sec:whichcentrality}. In addition, solving \temf~with {\em Baseline} and 1500 flows takes more than three hours, far exceeding the time scale (5--10 min) at which TE is performed in practice \cite{JKMO13,HKMZ13,HVSB15}. Thus we only run {\em Baseline} with up to 700 flows for \temf~to make sure the LP time is less than 1000 seconds.

As shown in Fig.~\ref{fig:baseline_LU_util}, the maximum link utilization of our approach is about 4--5 times that of {\em Baseline}, whereas the LP time of {\em Baseline} is at least 40 times worse than any centrality based approach shown in Fig.~\ref{fig:baseline_LU_LP}.
For \temf, the demand satisfaction ratio of {\em Baseline} is about 1.5 times of ours in Fig.~\ref{fig:baseline_MF_per} but the LP time is about 60 times higher than ours as in Fig.~\ref{fig:baseline_MF_LP}.


Indeed we observe that our centrality based approach sacrifices performance in order to reduce the complexity of TE.
We argue that this is a sensible tradeoff to make in most cases, especially for data center backbone WANs that use \temf~with very short time periods of 5--10 min \cite{JKMO13,HKMZ13,HVSB15}. Centrality based approach can support much larger topologies and much more flows with orders of magnitude smaller runtime. One can also increase $K$ to obtain better performance if necessary.  


\subsection{Comparison of Various Centralities}
\label{sec:whichcentrality}

We now wish to understand the relative performance of various centralities in realistic settings.
We use both the 100-node and 161-node topologies with $M=1$. Total number of middlepoints $K$ is set to 4 for \telu~and 7 for \temf~based on our previous experiments.
We vary the number of flows and for a given number of flows randomly draw flows 15 times from the traces.
For {\em Random} we perform 5 independent random selections of middlepoints for a given set of flows, resulting in 75 runs in total. For each run we compute the respective performance metrics and report the average and standard deviation.
In order to make the results more readable we scale the demands by 10 for 100-node topology and 40 for 161-node topology, respectively for \temf.

% In this section we first investigate the four centralities without using weights, and later focus on their weighted versions for completeness.

\begin{figure}[htpb]
\centering
\begin{minipage}{0.49\linewidth}
   \includegraphics[width=1\linewidth]{figures/ul_demands100}
      \caption{Performance of \telu~on the 100-node network with various centralities. $M$=1 and $K$=4.}
      \label{fig:ul_demands100}
\end{minipage}
%
\begin{minipage}{0.49\linewidth}
\includegraphics[width=1\linewidth]{figures/ul_demands161}
      \caption{Performance of \telu~on the 161-node network with various centralities. $M$=1 and $K$=4.}
      \label{fig:ul_demands161}
\end{minipage}
% \vspace{-3mm}
\end{figure}

\begin{figure}[htpb]
\centering
\begin{minipage}{0.49\linewidth}
   \includegraphics[width=1\linewidth]{figures/mf_100}
      \caption{Performance of \temf~on the 100-node network with various centralities. $M$=1 and $K$=7.}
      \label{fig:mf_100}
\end{minipage}
%
\begin{minipage}{0.49\linewidth}
\includegraphics[width=1\linewidth]{figures/mf_161}
      \caption{Performance of \temf~on the 161-node network with various centralities. $M$=1 and $K$=7. }
      \label{fig:mf_161}
\end{minipage}
% \vspace{-3mm}
\end{figure}

% \noindent{\bf Centralities without weights. }
Fig.~\ref{fig:ul_demands100} and Fig.~\ref{fig:ul_demands161} depict the results for \telu, and Fig.~\ref{fig:mf_100} and Fig.~\ref{fig:mf_161} for \temf.
We can make several interesting observations.
First, for the 100-node network {\em SP} and {\em GSP} perform the best under all settings in Fig.~\ref{fig:ul_demands100}. In contrast, for the 161-node topology in Fig.~\ref{fig:ul_demands161} {\em GSP} and {\em Degree} perform the best. When considering \temf, Fig.~\ref{fig:mf_100} shows that {\em GSP} and {\em Degree} perform better in the 100-node topology, while in the 161-node topology {\em GSP} performs best in Fig.~\ref{fig:mf_161}.
Thus, middlepoints chosen by group shortest path centrality consistently outperform those selected by other centralities in terms of TE performance.

The main advantage of {\em GSP} is that it selects a set of middlepoints whose combined power is strong. In particular, {\em SP} may select nodes that are individually strong but cover the same set of shortest paths; thus, when combined together these nodes result in poor performance since they share the same shortest paths and are unable to spread out the traffic. This is the reason why {\em GSP} performs consistently well, while the performance of {\em SP} can fluctuate from very strong as in Fig.~\ref{fig:ul_demands100} to very poor and even worse than {\em Random} as in Fig.~\ref{fig:ul_demands161}.

Second, {\em Random} performs the worst in Fig.~\ref{fig:ul_demands100}, Fig.~\ref{fig:mf_100}, and Fig.~\ref{fig:mf_161}, and it also performs badly in the 161-node network in Fig.~\ref{fig:ul_demands161}. This confirms our premise that centrality based middlepoint selection generally outperforms a naive random selection scheme. Indeed, {\em Random} does not utilize any topological information from the network. Further, {\em Random} fluctuates wildly, which makes it ill-fitted for practical use. As seen from the figures, {\em Random} has the largest standard deviations among all.


Third, we observe that the performance of {\em SP} can be worse than {\em Random} sometimes in Fig.~\ref{fig:ul_demands161}. Indeed, {\em SP} just greedily selects the top-$K$ shortest-path central nodes, even though in reality these nodes may share several shortest paths.
{\em Random}, on the other hand, can do better than {\em SP} in certain settings since it has a lower probability of choosing overlapping shortest paths.  

Another aspect of performance is the runtime of the TE LPs.
Table~\ref{table:LP_time_lu_161} and Table~\ref{table:LP_time_mf_161} show the average runtimes for \telu~and \temf~respectively.
 % as well as the total time including both middlepoint selection and solving the LP for the 161-node real network.
{\em Random} consistently has the worst results. %followed by {\em Degree}.
{\em SP} takes the least time but the difference between {\em SP}, {\em GSP}, and {\em Degree} is little.
All of the schemes can finish within 100 seconds even with 2000 flows, which demonstrates that centrality based segment routing can be practically used in large-scale networks.


%\begin{table}[!h]
%\centering
%\resizebox{0.98\columnwidth}{!}{%
%\begin{tabular}{|l|c|c|c|c|c|c|c|}
%\hline
%\backslashbox{Scheme}{\# demands}&500&750&1000&1250&1500&1750&2000 \\ \hline
%% Synthetic&synth50&50&276&2449 \\ \hline
%Random&11.52&17.49&23.78&30.23&37.32&43.59&51.92 \\ \hline
%SP&7.84&12.21&16.54&21.86&27.20&32.86&37.36 \\ \hline
%Degree&9.06&15.59&19.40&25.49&30.43&36.18&42.27 \\ \hline
%GSP&8.12&13.05&16.98&22.60&28.68&33.27&38.87 \\ \hline
%\end{tabular}
%}
%\vspace{3mm}
%\caption{Average LP time (seconds) of 161-node network of \telu.}
%\label{table:LP_time_lu_161}
%\vspace{-3mm}
%\end{table}
%
%
%\begin{table}[!h]
%\centering
%\resizebox{0.98\columnwidth}{!}{%
%\begin{tabular}{|l|c|c|c|c|c|c|c|}
%\hline
%\backslashbox{Scheme}{\# demands}&500&750&1000&1250&1500&1750&2000 \\ \hline
%% Synthetic&synth50&50&276&2449 \\ \hline
%Random&17.99&29.86&42.68&55.26&69.15&81.62&96.97 \\ \hline
%SP&12.87&20.56&29.42&39.44&49.55&58.83&70.53 \\ \hline
%Degree&14.08&23.11&34.41&43.81&53.79&64.79&76.04 \\ \hline
%GSP&14.34&22.56&32.15&43.27&54.37&66.32&79.54 \\ \hline
%\end{tabular}
%}
%\vspace{3mm}
%\caption{Average LP time (seconds) of 161-node network of \temf.}
%\label{table:LP_time_mf_161}
%\vspace{-3mm}
%\end{table}


\begin{table}[!h]
\centering
\resizebox{0.98\columnwidth}{!}{%
\begin{tabular}{|l|c|c|c|c|c|c|c|}
\hline
\backslashbox{Scheme}{\# flows}&1500&1750&2000&2250&2500&2750&3000 \\ \hline
% Synthetic&synth50&50&276&2449 \\ \hline
Random&37.54&44.76&53.07&60.70&68.18&78.52&88.00 \\ \hline
SP&28.16&32.61&38.92&44.42&50.93&56.65&62.14 \\ \hline
Degree&30.81&35.75&41.40&47.68&54.56&61.99&68.01 \\ \hline
GSP&27.48&33.75&38.49&45.44&50.56&57.38&62.64 \\ \hline
\end{tabular}
}
\vspace{3mm}
\caption{Average LP time (seconds) of 161-node network with \telu.}
\label{table:LP_time_lu_161}
\vspace{-4mm}
\end{table}


\begin{table}[!h]
\centering
\resizebox{0.98\columnwidth}{!}{%
\begin{tabular}{|l|c|c|c|c|c|c|c|}
\hline
\backslashbox{Scheme}{\# flows}&1500&1750&2000&2250&2500&2750&3000 \\ \hline
% Synthetic&synth50&50&276&2449 \\ \hline
Random&69.15&81.62&96.97&115.41&137.69&153.45&176.62 \\ \hline
SP&49.55&58.83&70.53&79.87&93.67&107.57&122.04 \\ \hline
Degree&53.79&64.79&76.04&90.49&102.63&112.53&129.58 \\ \hline
GSP&54.37&66.32&79.54&94.04&108.38&125.80&140.17 \\ \hline
\end{tabular}
}
\vspace{4mm}
\caption{Average LP time (seconds) of 161-node network with \temf.}
\label{table:LP_time_mf_161}
\vspace{-3mm}
\end{table}

The reason that {\em Random} has the longest runtime is that it selects nodes that are not central with possibly many distinct paths and links. This leads to more active optimization variables and constraints for the same LP, thus longer runtime. By the same token, the reason that {\em SP} has the lowest runtime is that it selects top-$K$ central nodes with many overlapping shortest paths. This results in fewer active links being used for routing, and thus fewer active optimization variables and constraints in the LP. 

% \draft{(because of \temf, how to modify this part?)}To better understand this result, we recall that the LP consists of the objective \eqref{obj} and the constraints \eqref{con:capacity}--\eqref{con:flow}. \eqref{obj}, \eqref{con:nonnegative}
%  and \eqref{con:flow} are the same for all methods. However, the capacity constraint \eqref{con:capacity} depends on the tunnels and segments, which in turn depend on the actual middlepoints. Interestingly, {\em SP} and {\em GSP} lead to capacity constraints with fewer decision variables $x_{i,t}$ with non-zero coefficients. Equivalently, each edge capacity constraint in {\em SP} and {\em GSP} has on average fewer active decision variables $x_{i,t}$ than random or degree. The reason is that by definition {\em SP}  or {\em GSP}  middlepoints have the property that, for a randomly picked source-destination pair, a high percentage of shortest paths from the source to the destination go through the middlepoints. As a result, when we send traffic from a source to a destination through a middlepoint the resulting segment will generally use few links. This is not the case with degree, and even more so with random, where middlepoints may participate in only few shortest paths. Then segments for random or degree contain more links on average leading, in turn, to more active decision variables per link capacity constraint. More active decision variables also implies higher density of the LP constraint matrix, which makes the LP computation more costly.

% To verify that this is indeed the case, we use the setting in Table~\ref{table:LP_time_lu_161}, and for each number of demands we compute the average number of active decision variables of each method. We then compute the Pearson's correlation coefficient between this quantity and the LP runtime, and take the average over all numbers of demands. The average correlation coefficient stands at 92.26\%, implying that the constraint density is strongly correlated in the LP time.

To summarize, based on the above experimental results and analysis, we find that {\em GSP} consistently delivers the best TE performance with the least LP time among all centralities we considered.
% time-saving middlepoint selection method to be used with TE.


\subsection{Comparison of Weighted Centralities}
\label{sec:eva_weighted}


The centralities we have studied so far only considered the connectivity of the network topology.
As discuss in \cref{sec:2pass}, it is also possible to take into account the link capacity information by adding weights to links and using weighted versions of centralities.

\begin{figure}[htpb]
\centering
\begin{minipage}{0.49\linewidth}
   \includegraphics[width=1\linewidth]{figures/weighted_ul_100}
      \caption{100-node network when $M$=1 and $K$=4 based on weighted centrality for \telu.}
      \label{fig:weighted_ul_100}
\end{minipage}
%
\begin{minipage}{0.49\linewidth}
\includegraphics[width=1\linewidth]{figures/weighted_ul_161}
      \caption{161-node network when $M$=1 and $K$=4 based on weighted centrality for \telu.}
      \label{fig:weighted_ul_161}
\end{minipage}
% \vspace{-3mm}
\end{figure}



\begin{figure}[htpb]
\centering
\begin{minipage}{0.49\linewidth}
   \includegraphics[width=1\linewidth]{figures/weighted_mf_100}
      \caption{100-node network when $M$=1 and $K$=7 based on weighted centrality for \temf.}
      \label{fig:weighted_mf_100}
\end{minipage}
%
\begin{minipage}{0.49\linewidth}
\includegraphics[width=1\linewidth]{figures/weighted_mf_161}
      \caption{161-node network when $M$=1 and $K$=7 based on weighted centrality for \temf.}
      \label{fig:weighted_mf_161}
\end{minipage}
% \vspace{-3mm}
\end{figure}


We also carry out experiments to compare the performance of weighted {\em SP}, weighted {\em degree}, and weighted {\em GSP} centralities against {\em GSP}, the best centrality without using weights for middlepoint selection. Weighted here means that the three centrality based approaches are weighted by the capacity of each edge.
Fig.~\ref{fig:weighted_ul_100} and Fig.~\ref{fig:weighted_ul_161} show the performance comparison with \telu, while Fig.~\ref{fig:weighted_mf_100} and Fig.~\ref{fig:weighted_mf_161} show the comparison with \temf. For the 161-node topology, we observe that {\em GSP} and weighted {\em GSP} are always the best. In the 100-node topology, {\em GSP} is sometimes worse than weighted {\em Degree} and weighted {\em GSP} although the differences are very small. Therefore, {\em GSP} without weights is still the most effective and robust middlepoint selection method in all settings. 
% Using link capacities does not improve the TE performance significantly. 

experiment.tex
\section{Experimental Evaluation} \label{sec:exp}

We performed experiments to evaluate the performance of optimal solution as well as the heuristic approach with a MacBook Pro 
configured with 2.6 GHz Intel CPU and 16GB of memory, using Python 2.7.11.  The optimization problem in Section \ref{formu} was solved using  CVX Solver to get the optimal traffic split values.
The experiments are measured on two public synthetic topologies one with 50 nodes and 276 edges while the other with 100 nodes and  572 edges. The  topologies are generated using the Delaunay's triangulation algorithm \cite{Igen, defo}. 
We sample demands with different source and destination and the number of demands falls in the range from 10-200. 
The results showed below are the average results from different demands.  We scale up all the demands by 10 times to consider the critical situations. Loop paths are removed in our experiments.


We compared with the following schemes:

\begin{itemize}
\item MP(Multiple path routing) The routing scheme splitting the flow through multiple paths by minimizing max utilization. Note that since this scheme has minor limitations about paths, so they can split flows to more paths and could achieve better load balance.
\item 2SR(Traffic Aware 2-Segment Routing) We implemented the Traffic aware 2-segment routing scheme with the identical setting to our scheme.
\end{itemize}

In the first experiments, we mainly focus on the performance of our optimal solution and heuristic approach. We fix the variable of the maximum number of used middle points falls in the range from 1 to 8. 
As shown in Fig.\ref{local_optimal},  the minimum max link utilization of optimal solution is always less than or equal to the local heuristic approach. As the number of used middle points increase, the link utilization of of both scheme are in a decrease trend.

\begin{figure}[!tb] 
\begin{center}
\includegraphics [scale = 0.6]{figures/local_optimal.pdf}
\caption{The performances of local heuristic approach and optimal solution}
\label{local_optimal} 
\end{center}
\vspace*{-0.25in}
\end{figure}

We now look at the influence of  $path_k$. As discussed, $path_k$ means the maximum number of used middle points for each path. We limit the number of used middle point for each path to reduce the overhead of packet header.
When the number of $path_k$ is one, only the paths using one of the $k$ selected middle points can be available. Not surprisingly, base on this strict limitation, the link utilization is quit poor. However, when the $path_k$ is equal to 2, much more paths can be used and further increase the number of $path_k$ does not reduce the link utilization. We set the $path_k= 2$ for the rest of the experiments.   

\begin{figure*}[!tb] 
\begin{center}
\includegraphics [scale = 0.45]{figures/path_k.pdf}
\caption{The local heuristic approach and optimal solution}
\label{local_optimal} 
\end{center}
\vspace*{-0.25in}
\end{figure*}


\begin{figure*}[!tb] 
\begin{center}
\includegraphics [scale = 0.45]{figures/comparison100nodes.pdf}
\caption{The local heuristic approach and optimal solution}
\label{local_optimal} 
\end{center}
\vspace*{-0.25in}
\end{figure*}

intro.tex
%!TEX root = main.tex
\section{Introduction}
\label{sec:intro}

% TE is an important task and is done mostly in SDN now
Traffic engineering (TE) is an important task for network operators to improve network efficiency and application performance. TE is commonly exercised in a wide range of networks, from carrier networks \cite{HVSB15,FT00} to data center backbones \cite{JKMO13,HKMZ13}. Increasingly, TE is implemented using SDN (Software Defined Networking) given its flexibility. Notable examples include Google's B4 \cite{JKMO13} and Microsoft's SWAN \cite{HKMZ13}. 
% Usually some tunneling protocol is used: the controller
% establishes multiple tunnels (i.e. network paths) between
% an ingress-egress switch pair, and configures splitting weights at
% the ingress switch. 

% The ingress switch then uses hashing based
% multipath forwarding such as ECMP to send flows [6, 7, 9]. 

% TE involves high cost in terms of the routing table entries for SDN switches. 
Implementing TE in the data plane requires a large number of flow table entries on switches. This is because each switch on the path needs to have an entry for a demand, i.e. ingress-egress switch pair, to forward its traffic to the next hop, and for a large-scale network there can be many demands. Commodity switches, on the other hand, have very limited capacity for flow entries (usually 1-2 thousands of entries \cite{CMTY11,KPK15}) due to the expensive TCAM (Ternary Content Aware Memory) hardware needed \cite{CMTY11,CLNR14,MPEK16}. The use of wildcarding could reduce the number of flow entries, but it is often undesirable as it reduces the ability to implement demand-level policies and monitoring. 
% Moreover, it is very slow to update an entry on an Openflow switch ($\sim$10ms) \cite{CMTY11}, making it even more difficult and error-prone to implement hundreds or thousands of TE rule changes every 5 or 10 minutes. 
Therefore it has become a major challenge to practically implement TE on commodity SDN switches. 

% existing approaches to reduce routing table entires; move this to related work
% segment routing as a good candidate developed earlier

Segment routing \cite{segment1, segment2, segment3} is a recently proposed routing architecture to tackle this challenge. 
Its key idea is to perform routing based on a sequence of logical segments formed by some {\em middlepoints} between the ingress and egress nodes. A segment is the logical pipe between two middlepoints that may include multiple physical paths spanning multiple hops, and ECMP is used to load balance traffic among these paths.  
Now with segment routing instead of end-to-end paths, intermediate switches only need to know how to reach middlepoints in order to forward packets. They no longer need to maintain per-demand routing information which scales quadratically with the number of nodes.
Thus segment routing has the potential to greatly reduce the overhead and cost of TE \cite{bhatia2015optimized,HVSB15}. 

% challenge: how to pick the middlepoints and how to use them for TE?
Segment routing has been explored with TE in some existing work. For example Bhatia et al. \cite{bhatia2015optimized} apply 2-segment routing to TE, where any logical path contains only one middlepoint and thus two segments. Hartert et al. \cite{HVSB15} propose some heuristics to solve various TE problems with segment routing. 
% Aubry et al. \cite{aubry2016scmon} applies segment routing to network monitoring and measurement. 
There lacks a thorough exploration and understanding of applying segment routing to TE, particularly the hardness of the resulting TE problem, and the development of practical TE algorithms with segment routing.  
% To utilize segment routing in TE, two fundamental questions must be addressed: first, which middlepoint(s) should be used to route the demands, and second, how the routing should be done across these segments? Clearly performance is maximized when the two are jointly considered, which is impossible to solve for however due to the exponentially many possibilities of combinations of segments as paths. Several recent works have started to tackle this problem \cite{bhatia2015optimized,HVSB15}. The general approach is to consider, for each demand, the joint problem of middlepoint selection and TE optimization, and iteratively optimize the objective. 
% This approach still suffers from high complexity largely due to the combinatorial nature of per-demand based middlepoint selection, because every node is a potential candidate of middlepoint. Indeed Hartert et al. prove that middlepoint selection is NP-hard even if there are only link capacity constraints \cite{HVSB15}. Thus greedy heuristics are usually adopted to derive a solution.  


In this paper, we conduct arguably the first systematic study of TE with segment routing in SDN based WANs.
We first focus on the theoretical aspects of TE with segment routing. We consider two common types of TE: $TE_{MF}$ that maximizes total throughput based on multi-commodity flow, and $TE_{LU}$ that minimizes the maximum link utilization. $TE_{MF}$ is mostly for data center backbone WANs \cite{JKMO13,HKMZ13}, and $TE_{LU}$ mostly for carrier networks \cite{HVSB15,FT00}. 

We provide new hardness results for TE with segment routing in directed networks. With general segment routing where traffic can take any path that goes through a middlepoint, we prove that it is NP-hard to decide if the maximum flow through just one given middlepoint is greater than 0 (\cref{sec:theory}). Thus $TE_{MF}$ is NP-hard. Due to the connection between the decision version of maximum flow and $TE_{LU}$, this also proves that $TE_{LU}$ given a single fixed middlepoint is NP-hard.   
We then study a restricted form of segment routing that uses only shortest paths between two segments in \cref{sec:opt}, and prove that both TE problems now can be solved in (weakly) polynomial time as an LP when the number of middlepoints per path is fixed and not part of the input. Our results thus provide a theoretical foundation for existing work that focuses on shortest path based segment routing \cite{bhatia2015optimized,HVSB15}. 
Interestingly, imposing acyclic end-to-end paths renders TE NP-hard.

% In this paper, we propose a novel TE architecture called MidwayTE that addresses the complexity and scalability challenges of applying segment routing in SDN based WANs. MidwayTE is motivated by two key novel ideas. First, given the complexity of per-demand middlepoint selection, we propose to select a common set of middlepoints to be used for all demands. Then the TE problem only involves these candidate middlepoints. Effectively, we significantly reduce the search space for middlepoints in order to reduce the complexity. Second, inspired by results from social networking research \cite{Newman2010,b87,b2005}, we apply graph centrality to middlepoint selection, and aim to select a small fraction of nodes that are topologically crucial to the network by various definitions.

Given our theoretical results, we next focus on the practical problem of how to choose a small but representative set of middlepoints in order to solve TE with shortest path based segment routing (\cref{sec:2pass}). 
Existing approaches \cite{bhatia2015optimized} assume that for each demand, every node in the network is potentially a middlepoint candidate, and formulate it as part of the TE problem. This causes the TE to be of a very large scale, which makes it computationally expensive to solve for practical purposes. 
As we show in \cref{sec:vsTE}, it cannot be solved by the {ECOS solver} \cite{D13} after three hours on a medium topology with 100 nodes and 1500 commodity flows, while in practice TE often needs to be re-computed at the granularity of 10 minutes \cite{JKMO13,HVSB15,HKMZ13,LKMZ14}. 
% Some other work relies on heuristics to do middlepoint selection \cite{HVSB15} 

Thus we propose to apply the centrality concept from graph theory and network analysis  \cite{Newman2010} to select a few middlepoints to route all traffic in the network. 
Centrality was first developed in social network analysis \cite{F1977,b87} to determine the most influential nodes in a social graph. 
In the context of routing, centrality can be naturally viewed in terms of the node importance when routing the demands along the admissible paths. 
We explore several centrality definitions based on the network topology only, such as shortest-path, group shortest-path, and degree centralities, and apply them to middlepoint selection in networks. We also introduce weighted variants that additionally take into account the link capacities.

We conduct comprehensive performance evaluation of centrality based middlepoint selection using real topologies and traffic traces. Our results demonstrate that only a small percentage of around 2.5\%--7\% of the most central nodes can achieve good TE performance with orders of magnitude lower runtime. Using centrality based middlepoint selection methods, one can solve TE problems with up to 3000 flows on a 161-node topology in less than 3 minutes. We also observe that group shortest-path consistently outperforms other centralities for middlepoint selection, and may be used as the sole solution in practice for simplicity.  

Finally, we comment that our work is of independent theoretical interest for two reasons. First, our theoretical analysis for $TE_{MF}$ can be used to prove that the flow centralities, first introduced in 1991 by Freeman, Borgatti, and White \cite{fbw1991}, are NP-hard to compute in directed graphs, thus restricting their practical applicability. Second, we show a profound dichotomy between directed and undirected networks: TE and flow centralities are NP-hard to compute in the former, but they are (at least) weakly polynomial in the latter. These results are included in Appendices at the end.


% Concretely, centrality is a fundamental concept in graph theory and network analysis that aims at identifying the most significant vertices within a graph \cite{Newman2010}. It was first developed in social network analysis \cite{F1977,b87} to determine the most influential nodes in a social graph. However, the notion of centrality has been expanded to a wide range of domains \cite{Newman2010}. How to exactly define the node significance depends on the application scenario, which has led to a variety of different definitions \cite{b2005}.

% In the context of routing, centrality can be naturally viewed in terms of the node importance when routing the demands along the admissible paths. For instance, in a multi-commodity network with several demands and link capacity constraints, centrality can be defined in terms of the maximum amount of network flow that can go through the node \cite{fbw1991}. In a network where routing only occurs along shortest paths, it is possible to view a node as central if several shortest paths go through it \cite{F1977}. In general, centrality indices in routing applications are better described in terms of the paths along which demands can be routed.

% As we earlier explained, our goal is to exploit the centrality information to identify a set of most central nodes that we can subsequently use as middlepoints in segment routing. The idea is that even a small percentage of the nodes can vastly simplify the routing process by only minimally impacting performance.

% Our work makes several fundamental contributions, many of which are of independent theoretical interest. We summarize them as follows: 
% \begin{itemize}[noitemsep]
% \item We thoroughly analyze the complexity of network flow centrality, which is a standard centrality measure in the literature for flow networks \cite{fbw1991} developed in the early 90's. We prove a deep dichotomy between the cases of directed and undirected graphs: computing flow centrality is NP-hard for the former but polynomial for the latter. We also prove that group flow centrality is NP-hard but approximable within a $1-\frac{1}{e}$ ratio with a greedy algorithm by using results from submodular function maximization.
% \item Motivated by the hardness of flow centrality, we explore several alternative centrality definitions based only on the network topology, such as shortest-path, degree, and group shortest-path centralities, and apply them to middlepoint selection in networks.
% \item We formulate the MidwayTE problem with candidate middlepoints as a LP that can be solved in polynomial time. We also establish hardness results for various acyclic versions of segment routing. 
% \item We conduct a comprehensive performance evaluation of MidwayTE with realistic topologies and demands. Our results demonstrate, among others, that only a small percentage of around 2.5\%--8\% of the most central nodes can achieve satisfactory link utilizations while vastly reducing the network management complexity.
% \end{itemize}



 

main.tex
\documentclass[journal,letterpaper,twoside]{IEEEtran}
% \documentclass{sig-alternate-05-2015}
% Add the compsocconf option for Computer Society conferences.
%
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:
% \documentclass[conference]{../sty/IEEEtran}

\usepackage{multirow}
\usepackage{bm}
\usepackage{graphicx,cite}
% \usepackage[font=footnotesize]{caption}
% \usepackage[font=footnotesize]{subcaption}
\usepackage[T1]{fontenc}
\renewcommand{\ttdefault}{txtt}
\usepackage{comment}
\usepackage{diagbox}
% \usepackage{slashbox}
% Some very useful LaTeX packages include:
% (uncomment the ones you want to load)


% *** MISC UTILITY PACKAGES ***
%
%\usepackage{ifpdf}
% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
% compilation based on whether the output is pdf or dvi.
% usage:
% \ifpdf
%   % pdf code
% \else
%   % dvi code
% \fi
% The latest version of ifpdf.sty can be obtained from:
% http://www.ctan.org/tex-archive/macros/latex/contrib/oberdiek/
% Also, note that IEEEtran.cls V1.7 and later provides a builtin
% \ifCLASSINFOpdf conditional that works the same way.
% When switching from latex to pdflatex and vice-versa, the compiler may
% have to be run twice to clear warning/error messages.
\usepackage{float}
% *** CITATION PACKAGES ***
%
\usepackage{cite}
% cite.sty was written by Donald Arseneau
% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
% \cite{} output to follow that of IEEE. Loading the cite package will
% result in citation numbers being automatically sorted and properly
% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
% \cite will automatically add leading space, if needed. Use cite.sty's
% noadjust option (cite.sty V3.8 and later) if you want to turn this off.
% cite.sty is already installed on most LaTeX systems. Be sure and use
% version 4.0 (2003-05-27) and later if using hyperref.sty. cite.sty does
% not currently provide for hyperlinked citations.
% The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/cite/
% The documentation is contained in the cite.sty file itself.
\usepackage{amsmath, amssymb,amsthm}
%\usepackage{euscript}
\usepackage[ansinew]{inputenc}

\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}

\usepackage{setspace}
\usepackage{graphics}


%\usepackage[numbers]{natbib}
%\bibliographystyle{IEEEtranN}
%\bibliographystyle{IEEEtran}


% *** MATH PACKAGES ***
%

% A popular package from the American Mathematical Society that provides
% many useful and powerful commands for dealing with mathematics. If using
% it, be sure to load this package with the cmex10 option to ensure that
% only type 1 fonts will utilized at all point sizes. Without this option,
% it is possible that some math symbols, particularly those within
% footnotes, will be rendered in bitmap form which will result in a
% document that can not be IEEE Xplore compliant!
%
% Also, note that the amsmath package sets \interdisplaylinepenalty to 10000
% thus preventing page breaks from occurring within multiline equations. Use:
%\interdisplaylinepenalty=2500
% after loading amsmath to restore such page breaks as IEEEtran.cls normally
% does. amsmath.sty is already installed on most LaTeX systems. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/




% *** SPECIALIZED LIST PACKAGES ***
%

\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{array}
\usepackage{longtable,enumitem}



% *** ALIGNMENT PACKAGES ***
%
%\usepackage{array}
% Frank Mittelbach's and David Carlisle's array.sty patches and improves
% the standard LaTeX2e array and tabular environments to provide better
% appearance and additional user controls. As the default LaTeX2e table
% generation code is lacking to the point of almost being broken with
% respect to the quality of the end results, all users are strongly
% advised to use an enhanced (at the very least that provided by array.sty)
% set of table tools. array.sty is already installed on most systems. The
% latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/tools/


%\usepackage{mdwmath}
%\usepackage{mdwtab}
% Also highly recommended is Mark Wooding's extremely powerful MDW tools,
% especially mdwmath.sty and mdwtab.sty which are used to format equations
% and tables, respectively. The MDWtools set is already installed on most
% LaTeX systems. The lastest version and documentation is available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/mdwtools/


% IEEEtran contains the IEEEeqnarray family of commands that can be used to
% generate multiline equations as well as matrices, tables, etc., of high
% quality.


%\usepackage{eqparbox}
% Also of notable interest is Scott Pakin's eqparbox package for creating
% (automatically sized) equal width boxes - aka "natural width parboxes".
% Available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/eqparbox/
\usepackage{listings}
\usepackage{color}
\usepackage{csquotes}




% *** SUBFIGURE PACKAGES ***
%\usepackage[tight,footnotesize]{subfigure}
% subfigure.sty was written by Steven Douglas Cochran. This package makes it
% easy to put subfigures in your figures. e.g., "Figure 1a and 1b". For IEEE
% work, it is a good idea to load it with the tight package option to reduce
% the amount of white space around the subfigures. subfigure.sty is already
% installed on most LaTeX systems. The latest version and documentation can
% be obtained at:
% http://www.ctan.org/tex-archive/obsolete/macros/latex/contrib/subfigure/
% subfigure.sty has been superceeded by subfig.sty.

\usepackage[caption=false,font=footnotesize]{subfig}
%\usepackage{subfig}
%\usepackage{caption}
%\usepackage[caption=false]{caption}
%\usepackage[font=footnotesize]{subfig}
% subfig.sty, also written by Steven Douglas Cochran, is the modern
% replacement for subfigure.sty. However, subfig.sty requires and
% automatically loads Axel Sommerfeldt's caption.sty which will override
% IEEEtran.cls handling of captions and this will result in nonIEEE style
% figure/table captions. To prevent this problem, be sure and preload
% caption.sty with its "caption=false" package option. This is will preserve
% IEEEtran.cls handing of captions. Version 1.3 (2005/06/28) and later
% (recommended due to many improvements over 1.2) of subfig.sty supports
% the caption=false option directly:
%\usepackage[caption=false,font=footnotesize]{subfig}
%
% The latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/
% The latest version and documentation of caption.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/caption/




\usepackage[hyphens]{url}
\usepackage[colorlinks=true,linkcolor=black,citecolor=black,urlcolor=black]{hyperref}
% create fancy cross-section references
\usepackage{cleveref}
\crefname{section}{\S}{\S\S}
\Crefname{section}{\S}{\S\S}
\crefformat{section}{\S#2#1#3}
\hypersetup{colorlinks={true},linkcolor={blue},citecolor=blue}

\newcommand{\draft}[1]{{\color{blue} #1}}
\newcommand{\telu}{$TE_{LU}$}
\newcommand{\temf}{$TE_{MF}$}

% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.
% (Unless specifically asked to do so by the journal or conference you plan
% to submit to, of course. )


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


\begin{document}




%
% paper title
% can use linebreaks \\ within to get better formatting as desired

% Copyright
% \setcopyright{acmcopyright}
%\setcopyright{acmlicensed}
%\setcopyright{rightsretained}
%\setcopyright{usgov}
%\setcopyright{usgovmixed}
%\setcopyright{cagov}
%\setcopyright{cagovmixed}


% DOI
% \doi{10.475/123_4}

% ISBN
% \isbn{123-4567-24-567/08/06}

%Conference
% \conferenceinfo{SIGMETRICS '17}{June 5--9, 2016, Champaign-Urbana, IL, USA}

% \acmPrice{\$15.00}

%
% --- Author Metadata here ---
% \conferenceinfo{WOODSTOCK}{'97 El Paso, Texas USA}
%\CopyrightYear{2007} % Allows default copyright year (20XX) to be over-ridden - IF NEED BE.
%\crdata{0-12345-67-8/90/01}  % Allows default copyright data (0-89791-88-6/97/05) to be over-ridden - IF NEED BE.
% --- End of Author Metadata ---

\title{On Traffic Engineering with Segment Routing \\in SDN based WANs }
% \title{MidwayTE: Traffic Engineering with Segment Routing in SDN based WANs }

% author names and affiliations
% use a multiple column layout for up to two different
% affiliations
\author{George~Trimponias,
        Yan~Xiao,
        Hong~Xu,
        Xiaorui~Wu,
        and~Yanhui~Geng% <-this % stops a space
\thanks{The work was supported in part by contract research between City University of Hong Kong and Huawei. The corresponding author is Hong Xu.}
\thanks{G. Trimponias and Y. Geng are with Huawei Noah's Ark Lab, Hong Kong, China (email: \href{mailto:g.trimponias@huawei.com}{g.trimponias@huawei.com}, \href{mailto:geng.yanhui@huawei.com}{geng.yanhui@huawei.com}). }% <-this % stops a space
\thanks{Y. Xiao, H. Xu and X. Wu are with Department of Computer Science, City University of Hong Kong, Hong Kong, China (email: \href{mailto:yanxiao6-c@my.cityu.edu.hk}{yanxiao6-c@my.cityu.edu.hk}, \href{mailto:henry.xu@cityu.edu.hk}{henry.xu@cityu.edu.hk}, \href{mailto:xiaoruiwu3-c@my.cityu.edu.hk}{xiaoruiwu3-c@my.cityu.edu.hk}).}% <-this % stops a space
}

% The paper headers
\markboth{IEEE/ACM TRANSACTIONS ON NETWORKING}%
{Trimponias et al.: On Traffic Engineering with Segment Routing in SDN based WANs}





% make the title area
\maketitle

\input{abstract}
\begin{IEEEkeywords}
Segment Routing, Traffic Engineering, Graph Centrality, Software Defined Networking
\end{IEEEkeywords}

% \keywords{Segment Routing, Traffic Engineering, Software Defined Networking, Source Routing, Graph Centrality}





\input{intro}
\input{backgd}
\input{te}
\input{theory}
\input{opt}
\input{selection}
% \input{algorithm}
\input{evaluation}
\input{related}
\input{conclusion}


%\color{black}
% conference papers do not normally have an appendix


% use section* for acknowledgement
%\section*{Acknowledgment}
%This research is supported by Hong Kong RGC grant HKU 716712E.

% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
% adjust value as needed - may need to be readjusted if
% the document is modified later
%\IEEEtriggeratref{8}
% The "triggered" command can be changed if desired:
%\IEEEtriggercmd{\enlargethispage{-5in}}

% references section

% can use a bibliography generated by BibTeX as a .bbl file
% BibTeX documentation can be easily obtained at:
% http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/
% The IEEEtran BibTeX style support page is at:
% http://www.michaelshell.org/tex/ieeetran/bibtex/
%\begin{spacing}{0.9}
\bibliographystyle{IEEEtranS}
% argument is your BibTeX string definitions and bibliography database(s)
\bibliography{bib/reference}

\begin{IEEEbiographynophoto}{George Trimponias} received his PhD from the Department of Computer Science and Engineering at the Hong Kong University of Science  and Technology. Prior to that he obtained a five-year diploma in Electrical and Computer Engineering from the National Technical University of Athens, Greece. He is currently a Researcher at Huawei Noah's Ark Lab in Hong Kong. His research interests include machine learning, combinatorial optimization, and game theory.
\end{IEEEbiographynophoto}

\begin{IEEEbiographynophoto}{Yan Xiao}
received the B.Eng. and M.Eng. degrees in College of Computer and Information from Hohai University, Nanjing, China, in 2013 and 2016, respectively. She is currently a Ph.D. student in Department of Computer Science, City University of Hong Kong. Her research interests include data mining, big data, deep learning based software engineering, and graph theory.
\end{IEEEbiographynophoto}

\begin{IEEEbiographynophoto}{Hong Xu}
received the B.Eng. degree from the Department of Information Engineering, The Chinese University of Hong Kong, in 2007, and the M.A.Sc. and Ph.D. degrees from the Department of Electrical and Computer Engineering, University of Toronto. He joined the Department of Computer Science, City University of Hong Kong in 2013, where he is currently an assistant professor. His research interests include data center networking, SDN, NFV, and cloud computing. He was the recipient of an Early Career Scheme Grant from the Research Grants Council of Hong Kong in 2014. He also received the best paper awards from IEEE ICNP 2015 and ACM CoNEXT Student Workshop 2014. He is a member of ACM and IEEE.
\end{IEEEbiographynophoto}

\begin{IEEEbiographynophoto}{Xiaorui Wu}
received his B.S. degree in Electrical Information Engineering from University of Electronic Science and Technology of China in 2016. He is currently a first-year PhD student in Department of Computer Science, City University of Hong Kong. His research interests include computer networking, machine learning, and big data systems. He is a student member of the IEEE.
\end{IEEEbiographynophoto}

\begin{IEEEbiographynophoto}{Yanhui Geng}
is a senior researcher and project manager at Huawei Noah's Ark Lab (Hong Kong). He received his B.Eng. and M.Eng. in Electronic Engineering and Information Science from the University of Science and Technology of China (USTC) in 2002 and 2005, respectively. He obtained his Ph.D. degree in Electrical and Electronic Engineering from the University of Hong Kong (HKU) in 2009. Before joining Huawei, he was a Post-Doctoral Research Fellow at HKU from 2009 to 2012, and was a Senior Engineer at the Hong Kong Applied Science and Technology Research Institute (ASTRI) from 2012 to 2013. His research interests include performance modeling and analysis of communication networks, SDN, machine learning, big data analytics, cloud computing, and indoor positioning technology. He has filed 15 patents related to communication networks. He has 26 technical publications on international journals and conferences including ACM SIGCOMM, IEEE/ACM Transactions on Networking, IEEE INFOCOM, ICNP, ICDCS, ICDM, etc. and his work on information quality received the IEEE ICC 2010 Best Paper Award.
\end{IEEEbiographynophoto}

\clearpage
\input{appendices}



% that's all folks
\end{document}








opt.tex
%!TEX root = main.tex
\section{Segment Routing with Shortest Paths}
\label{sec:opt} 

Given the NP-hardness of applying general segment routing in TE, here we consider TE with shortest path based segment routing. That is, now traffic is routed only along the shortest paths for a given segment. 
In this sense, our results provide for the first time theoretical foundation for existing work that focuses on shortest path based segment routing \cite{bhatia2015optimized,HVSB15}. 
% In Section \ref{sec:model} we formulate the traffic engineering problem with segment routing using ECMP, whereas in Section \ref{sec:SRhardness} we discuss hardness results for acyclic segment routing.

\subsection{Network model and TE}
\label{sec:model}

%\draft{is there a way to simplify this and make all the notations coherent with the ones in \cref{sec:TE}? also do we need Table 2?}

%Our network is a directed graph $G=(V,E)$, where $E$ represents the set of directed links between switches.
%Each link $e\in E$ has a capacity $C_e$. 
%Let $F$ denote the set of flows, where each flow $f \in F$ is the aggregated traffic from an ingress to an egress switch.
%The demand of $f$ in a TE interval $D_f$ is given.

Assume there are in total $K$ middle points available. Each end-to-end path can use up to $M\leq K$ of these middle points. For a segment $s\in S$ between an ingress node and a middlepoint, two middlepoints, or a middlepoint and an egress node, there are multiple paths in general. We assume, for simplicity, that routing is done by ECMP over all shortest paths of a segment. This is consistent with prior work \cite{bhatia2015optimized}. We use  $T_i$ to denote the complete set of logical tunnels formed by segments in $S$ that can be used for commodity $i$, with up to $M$ middle points. A tunnel involves only ingress/egress switch, and the intermediate middlepoints. This can be constructed offline efficiently. 

Let $G_{t,s}$ denote if a tunnel $t$ uses segment $s$ or not, %$H_{s,p}$ denote if segment $s$ uses shortest path $p$ or not,
and $I_{p,e}$ denote if path $p$ uses link $e$ or not. Furthermore, let $\hat{P}_s$ be the set of all shortest paths for segment $s$,
% We use $P_f$ to denote the set of disjoint  paths corresponding to  flow $f$ where the paths in $P_f$ have the same source and destination with $f$. 
and $f_{i}(t)$ represent the flow in tunnel $t$ for commodity $i$. The split ratio  $x_{i,t}$ for $i$ on tunnel $t$ is defined as the ratio $x_{i,t}=\frac{f_i(t)}{\sum_{t \in T_i}f_{i}(t)}$.
% If  $ x_{f,p}=0$ means flow $f$ does not reroute through path $p$.
%Table~\ref{table:notation1} summarizes the key notations.  


%\begin{table}%[H]
%\centering
%\label{table:notation1}
%\resizebox{\columnwidth}{!}{%
%\begin{tabular}{|l|l|l|}
%\hline
%\multirow{12}{*}{TE Input}     
%                               & $E$         %& Set of directed links in the network    %\\ \cline{2-3} 
%                               & $C_e$       %& Capacity of link $e$                    %\\ \cline{2-3} 
%                               & $F$         %& Set of flows     \\ \cline{2-3} 
%                               & $D_f$       %& Bandwidth demand of flow $f$   \\ %\cline{2-3} 
%                               & $K$         %& Number of available middle points \\ %\cline{2-3} 
%                               & $M$         %& Maximum number of middle points in an %end-to-end path \\ \cline{2-3} 
%                               & $S_t$        %& Set of segments for tunnel $t$  \\ %\cline{2-3} 
%                               & $T_f$       %& Set of possible tunnels for routing $f$ %\\ \cline{2-3}                           
%                               & $P_s$       %& Set of shortest paths for segment $s$ \\ %\cline{2-3}                           
%%                               & $G_{t,s}%$   & Binary variable to see if $t$ uses %segment $s$ or not \\ \cline{2-3} 
%%                               & $H_{s,p}%$   & Binary variable to see if $s$ uses %shortest path $p$ or not \\ \cline{2-3} 
%                               & $I_{p,e}$   %& Binary variable to see if $p$ uses link %$e$ or not \\ \hline
%\multirow{1}{*}{TE  Output} 
%                             
%                              &  $x_{f,t}$ %& The split ratio on tunnel $t\in T_f$ for %flow $f$ \\ \hline
%\end{tabular}
%}
%\vspace{2mm}
%\caption{ Key notations}
%\vspace{-2mm}
%\end{table}

The $TE_{LU}$ problem with segment routing can be formulated similar to Section~\ref{sec:TE-LU}, where the set of paths $\mathcal{P}_i$ for commodity $i$ is now replaced by the set of logical tunnels $T_i$: 
%\begin{align}%G_{t,s} H_{s,p}
%\min      & \quad\quad \theta \label{obj} %\\  
%\text{s.t. }& \sum_{f \in F} \sum_{t \in %T_f}\sum_{s\in S_t} \sum_{p\in P_s} x_{f,t}D_f\frac{I_{p,e}}{\lvert P_s \rvert}    \leq \theta\cdot C_e ,\forall e \in E,  \label{con:capacity} \\
%&  0 \leq x_{f,t}\leq 1 ,\forall  f  \in F,  t \in T_f, \label{con:nonnegative} \\
%& \sum_{t \in T_f}x_{f,t} = 1, \forall  f  \in F. \label{con:flow}
%\end{align}
\begin{align}%G_{t,s} H_{s,p}
\min      & \quad\quad \theta \label{obj} \\  
\text{s.t. }& \sum_{i=1}^{L} \sum_{t \in T_i}\sum_{s\in S_t}\sum_{p\in \hat{P}_s} f_{i}(t)\frac{I_{p,e}}{\lvert \hat{P}_s \rvert}    \leq \theta\cdot c(e) ,\forall e \in E,  \label{con:capacity} \\
&  0 \leq f_{i}(t) ,\forall  i  \in \{1,\dots,L\},  t \in T_i, \label{con:nonnegative} \\
& \sum_{t \in T_i}f_{i}(t) \geq D_i, \forall  i  \in \{1,\dots,L\}. \label{con:flow}
\end{align}
%The objective is again to minimize the maximum link utilization $\theta$ across the network.
The capacity constraint \eqref{con:capacity} indicates that the total traffic routed to link $e$ from across all flows, tunnels, segments, and shortest paths, cannot exceed $\theta$ times the link capacity. Since ECMP is used for routing within any segment $s$, each shortest path $p$ of segment $s$ receives flow equal to $f_{i}(t)/\lvert \hat{P}_s \rvert$. 
%Constraint \eqref{con:flow} ensures that the entire demand for $f$ is routed.

Regarding the TE asymptotic complexity, we have the following result when $M$ is fixed and not part of the input:

\begin{proposition}
\label{prop:te-sp-lu}
For fixed $M$ with respect to the input graph $G$, the $TE_{LU}$ problem described by Equations \eqref{obj}-\eqref{con:flow} can be solved in (weakly) polynomial time.
\end{proposition}
\begin{proof}
The number of commodities $L$ cannot exceed $|V|\cdot(|V|-1)$, and the number $|T_i|$ of tunnels per commodity $i$ is upper bounded by ${{K}\choose{0}}+\cdots+{{K}\choose{M}}$, where $K\leq|V|$. For fixed $M$ w.r.t. the input graph $G$, $|T_i|$ has polynomial size w.r.t the graph. Finally, the number $S_t$ of segments per tunnel cannot exceed $K+1\leq|V|+1$, since a tunnel can use at most all $K$ middlepoints. For the inner sum $\sum_{p\in \hat{P}_s} \frac{I_{p,e}}{\lvert \hat{P}_s \rvert}$, note that it basically denotes the percentage of shortest paths for segment $s$ that use link $e$. However, this can be computed in polynomial time, e.g. by using the techniques in \cite{B2001}.

Thus, we have proved that for fixed $M$, the LP has a polynomial number of variables, and a polynomial number of constraints whose coefficients can be computed in polynomial time. The proposition then immediately follows by standard results in linear programming \cite{K1984,K1980}.
\end{proof}

Given that the $TE_{MF}$ formulation is very similar, we can similarly prove that is can also be solved in (weakly) polynomial time for segment routing with shortest paths.

Finally, we observe that the TE problem is naturally related to the shortest path centrality that we discussed in Section \ref{sec:2pass}. Indeed, the inner part $\sum_{p\in \hat{P}_s} \frac{I_{p,e}}{\lvert \hat{P}_s \rvert}$ of constraint \eqref{con:capacity} precisely describes the percentage of shortest paths for segment $s$ that use a specific edge, and note that we do that for all possible segments. Even though shortest path centrality refers to a node rather than an edge and equally takes into account all possible source-destination pairs, constraint \eqref{con:capacity} reveals interesting connections between the popular centrality metric and the segment routing problem.

\subsection{Hardness of Acyclic Segment Routing}
\label{sec:SRhardness}
So far, we have focused on segment routing where routing on a segment is based on ECMP. 
One challenge is that this generally produces source destination paths with edge repetitions, i.e., walks. Even in the case of just one middle point per path, it is possible that a (simple) shortest path from the source $s$ to a middle point $M$ shares an edge $e$ with a shortest path from $M$ to the destination $d$. So, even though the paths for any given segment are simple, the resulting $s$-$d$ path may not even be a path. This may reduce the performance of segment routing, because it increases the link load on the reused edges and may lead to higher link utilization.

%A natural question would then be to consider segment routing using only paths or even simple paths from any source to any destination. %Note that for now we do not just assume shortest paths between the segment endpoints but the set of all possible simple paths. 
%The next result answers this negatively. %for directed graphs.

%\begin{proposition}
%\label{prop:SRpathNP-hard}
%Segment routing in a directed graph using only paths or simple paths is NP-hard, even for just one demand and only one middle point per path.
%\end{proposition}
%\begin{proof}
%Assume a directed graph $G=(V,E)$, two distinct nodes $s,t$ in $V$, and a node $s\neq M\neq t$ in $V$. Consider we do segment routing from $s$ to $t$ using $M$ as a middle point. We can easily show that the problem is NP-hard by a reduction from Lemmas \ref{lemma:exists-path-NPhard} and \ref{lemma:exists-simple-path-NPhard}.

%Indeed, assume we want to determine whether there is a simple path from $s$ to $t$ through $M$ in graph $G$. We can reduce this problem to segment routing traffic engineering with simple paths as follows. We associate with each edge in $G$ a positive capacity, and a positive demand $D>0$ from $s$ to $t$. We then argue that segment routing with simple paths between any segment endpoints accepts a positive solution $\theta^{*}>0$, if and only if there is a simple path from $s$ to $t$ through $M$.

%Indeed, if there is a simple path from $s$ to $t$, then there will be always a positive solution to the optimization problem that (at least) uses that path (since all capacities are non-zero). Conversely, if there is no simple path, then the problem is infeasible and accepts no solution at all.

%We can similarly prove that segment routing with paths is NP-hard by a reduction from Lemma \ref{lemma:exists-path-NPhard}.
%\end{proof}

%The above result assumes that routing on any given segment can use any (simple) path connecting the segment endpoints. 
In that case a natural question arises:
what if we consider segment routing with shortest paths for segments, under the condition that the resulting walk from the source to the destination is a path or even a simple path? As our subsequent analysis shows, traffic engineering will become NP-hard, even for just one commodity. To prove this fact, we first introduce the following fundamental result due to Eilam-Tzoreff \cite{t1998}.

\begin{theorem}[NP-hardness of $k$DSP \cite{t1998}]
\label{theorem:kDSP}
Given a graph $G=(V,E)$ and $k$ pairs of distinct vertices $(u_i,v_i)$, $1\leq i\leq k$, the $k$DSP problem of computing $k$ pairwise disjoint shortest paths $P_i$ between $u_i$ and $v_i$ is NP-complete, when $k$ is part of the input. This result holds for all four versions of the $k$DSP problem, namely, node or edge-disjoint paths for directed or undirected graphs.
\end{theorem}

\begin{proposition}
\label{prop:SRshortestpathNP-hard}
The $TE_{MF}$ and $TE_{LU}$ problems in a directed or undirected graph with $K$ middle points $(1)$ using only shortest path segment routing and $(2)$ only allowing paths or simple paths from a source to a destination, are NP-hard, even for just one commodity, when $K$ is part of the input.
\end{proposition}

\begin{proof}[Proof sketch]
We can show the statement by making similar arguments as for general segment routing TE in Section \ref{sec:theory}. For $TE_{MF}$, the idea is to first show that we can solve $k$DSP if and only if we can solve the corresponding $TE_{MF}$ formulation. 

Indeed, assume a directed or undirected graph $G=(V,E)$, two distinct nodes $s,t$ in $V$, and $K$ distinct nodes $s\neq M_i\neq t$ in $V$, $1\leq i\leq K$. Consider we do segment routing from $s$ to $t$ using nodes $M_i$ as our $K$ middle points. We will show that the the $TE_{MF}$ problem is NP-hard by a reduction from the $k$DSP problem.

Concretely, assume for instance the $k$DSP node-disjoint problem in Theorem \ref{theorem:kDSP}. We construct a new graph $G'$ as follows. For each $i$, $1\leq i\leq K-1$, we introduce a new node $M_i$ along with the two (directed or undirected) edges $e^i_{in}=(v_i,M_i)$ and $e^i_{out}=(M_i, u_{i+1})$. Moreover, we associate each edge in $G'$ with a positive capacity, and we assume the single commodity $(s,t)=(u_1,v_K)$ with a positive demand $D>0$. We now argue that there are $K$ node-disjoint shortest paths between $u_i$ and $v_i$, if and only if $TE_{MF}$) with the single commodity $(s,t)$ and the $K-1$ middle points $M_1,\dots,M_{K-1}$ accepts a positive solution (maximum flow).

But this can be proven using very similar techniques as in Section \ref{sec:SRhardness}. The only difference is that the minimum edge cut in this case corresponds to the minimum sum of edge capacities whose removal results in no path (or simple path) using shortest paths from the source to the destination through the middle points.

Finally, NP-hardness for $TE_{LU}$ then follows immediately by Lemma \ref{lemma:connection}, in a similar spirit as Corollary \ref{corollary:NP-hard-TE-LU}.
\end{proof}

%\begin{proof}
%Assume a directed or undirected graph $G=(V,E)$, two distinct nodes $s,t$ in $V$, and $K$ distinct nodes $s\neq M_i\neq t$ in $V$, $1\leq i\leq K$. Consider we do segment routing from $s$ to $t$ using nodes $M_i$ as our $K$ middle points. We will show that the the segment routing optimization problem described by formulation (\ref{obj})-(\ref{con:flow}) is NP-hard by a reduction from the $k$DSP problem.


%Indeed, assume for instance the $k$DSP node-disjoint problem in Theorem \ref{theorem:kDSP}. We construct a new graph $G'$ as follows. For each $i$, $1\leq i\leq K-1$, we introduce a new node $M_i$ along with the two (directed or undirected) edges $e^i_{in}=(v_i,M_i)$ and $e^i_{out}=(M_i, u_{i+1})$. Moreover, we associate each edge in $G'$ with a positive capacity, and we assume the single commodity $(s,t)$=$(u_1,v_K)$ with a positive demand $D>0$. We now argue that there are $K$ node-disjoint shortest paths between $u_i$ and $v_i$, if and only if the optimization problem (\ref{obj})-(\ref{con:flow}) with the single commodity $(s,t)$ and the $K-1$ middle points $M_1,\dots,M_{K-1}$ accepts a positive solution $\theta^{*}>0$.

%Indeed, if there are $K$ node-disjoint shortest paths between $u_i$ and $v_i$, then there will be always a positive solution to the optimization problem that uses those paths (since all capacities are non-zero). Conversely, if there no such $K$ paths exist, then the problem is clearly infeasible and accepts no solution.

%\end{proof}

Interestingly, Proposition \ref{prop:SRshortestpathNP-hard} is general and holds for both directed and undirected graphs. We emphasize however that it assumes that the number of middle points $K$ is part of the input. For $k=2$, \cite{t1998} provides a polynomial algorithm for the undirected case of $k$DSP, whereas the complexity for the directed case when $k=2$ remains open.

related.tex
%!TEX root = main.tex
\section{Related Work}
\label{sec:related}

% \subsection{Reducing flow entries}

% There has been some work on reducing the flow entries in TCAM.
% The common approach is to compress the effective TCAM size required in conventional IP routers by prefix aggregation and expansion techniques, such as in \cite{RM04,L02,RMB05}. 
% In the context of SDN, 
% DevoFlow \cite{CMTY11} introduces new mechanisms for elephant flow detection and flow management with aggressive use of wild-carded OpenFlow rules. 
% Banerjee et al. \cite{BK14} propose to replace the flow entries with two layers of simpler and shorter tags to save flow table entries. 
% Cohen et al. \cite{CLNR14} consider the limited TCAM size as constraints of the TE optimization, and present approximation algorithms for the NP-hard problem. 
% Moln\'{a}r et al. \cite{MPEK16} use flow table decomposition to reduce TCAM cost.
% Note that these approaches strive to compress the rules installed in TCAM, while we focus on actually reducing the number of forwarding rules in the first place by using segment routing. 
	

% \subsection{Segment routing}
% We briefly review prior work in segment routing.

% Segment routing is a relative new technology and only has a limited number of research work. 
% In \cite{bhatia2015optimized},  the authors proposed solutions for determining the optimal allocation in ECMP aware traffic engineering.  In their scheme, they regard all the nodes except the source and destination as the candidate intermediate point and split flows across exactly one intermediate node. Although they limit the number of segment as two for one path, since they consider all the candidate intermediate points, for one s-d demand, many intermediate node will be used and for all the demands even more nodes are involved as the intermediate node, which will be a overhead of the border network(e.g. ingress node). 
% Our scheme is different, since we select the middle point first and only route the flows to the selected middle points. For each source- destination demand, we limited the number of used middle point and for all the demands we further limit the number of used middle point by $k$.



We now review related work on segment routing other than those discussed already in \cref{sec:bg}. Segment routing is a relatively new concept with limited prior work. 
Aubry et al. \cite{aubry2016scmon} propose to use segment routing for continuous monitoring of the data plane of the network with a single box. Segment routing is used to force probe packets to traverse specific paths. Giorgetti et al. \cite{giorgetti2015path} propose algorithms for segment routing label stack computation that guarantee minimum label stack depth.

TE has been extensively studied in carrier networks \cite{EJLW01,KKDC05,WXQY06,FT00,HBCR07,HVSB15}, and has also attracted much attention recently in data center backbone WANs \cite{JKMO13,HKMZ13,LKMZ14,GHCR13} with software defined networking \cite{FRZ13}. End-to-end paths are usually used while we study segment routing here in TE. 

Finally, we note that graph centralities have been applied to routing in some specific SDN problems, such as in service chain embedding \cite{Lukovszki2015} and incremental SDN deployment \cite{Lukovszki2016,Levin2014}. In a service chain \cite{Lukovszki2015}, traffic needs to be steered through a set of waypoints, with the goal of admitting a maximum number of routes. In the context of hybrid and incremental SDN deployment \cite{Levin2014}, a set of middleboxes need to be deployed in order to serve a maximal number of flows, respecting flow rule constraints.
Solutions to these problems are based on degree centralities, and there exist greedy approximation algorithms exploiting submodularity as well \cite{Lukovszki2016}. Contrary to these works, our paper focuses on the theoretical fundamentals of TE using segment routing and on graph-theoretic practical middlepoint selection.
selection.tex
%!TEX root = main.tex
\section{Centrality Based Middlepoint Selection}
\label{sec:2pass}

The previous sections investigated the fundamentals of segment routing, and showed that the TE for unrestricted segment routing is NP-hard. On the other hand, Proposition \ref{prop:te-sp-lu} suggests that if we only allow a fixed number $M$ of middlepoints per path, then TE with shortest paths is (weakly) polynomially computable.

One approach would then be to consider all nodes as candidate middlepoints, i.e. $K=|V|$. However, that results in very large TE programs that are costly to solve. An alternative is to just consider a small number of middlepoints such that $K\ll|V|$, that would still produce good output for the TE. Given that this is generally NP-hard \cite{HVSB15}, in this section we discuss practical middlepoint selection based on alternative centrality measures with polynomial complexity. Note that these centralities are \textit{structural} metrics that look at the graph structure, i.e., the connections among the various nodes. However, they generally do not take into account the flow network and its flow conservation and capacity constraints, which was the case with the NP-hard flow centralities in Appendix~\ref{sec:appendix}.

{\bf Shortest-path centrality.}
We start with \textit{shortest-path} centrality, which characterizes the power of a node in terms of the number of shortest paths that go through that node for a randomly picked source-destination pair. Concretely, assume a directed graph $G=(V,E)$. The shortest-path betweenness centrality of a node $v\in V$ \cite{F1977} is defined as:
\begin{equation}
\delta(v) = \sum_{s,t\in V|s\neq v\neq t}\frac{\sigma_{st}(v)}{\sigma_{st}},
\end{equation}
where $\sigma_{st}(v)$ is the number of shortest paths from $s$ to $t$ that go through $v$, and $\sigma_{st}$ the total number of shortest paths from $s$ to $t$. Calculating the shortest path centrality of all vertices in a graph requires $\Theta({|V|}^3)$ time and $\Theta({|V|}^2)$ space. This can be achieved by augmenting the Floyd-Warshall algorithm for the all-pairs shortest-paths problem with path counting. Brande's algorithm improves these bounds by only using $O(|V|+|E|)$ space and running in $O(|V|+|E|)$ and $O(|V|\cdot|E|+{|V|}^2\log|V|)$ time on unweighted and weighted networks, respectively \cite{B2001}.

{\bf Group shortest-path centrality.}
As opposed to the aforementioned \textit{individual} centrality, the \textit{group} shortest-path betweenness centrality of a group of nodes $C\subseteq V$ refers to the combined centrality of the group \cite{eb1999}. It is defined as:
\begin{equation}
\delta_{\mathcal{G}}(C)(v) = \sum_{s,t\in V|s\neq v\neq t}\frac{\sigma_{st}(C)}{\sigma_{st}},
\end{equation}
where $\sigma_{st}(C)$ the number of shortest paths that go through \textit{any node} in $C$.
Group betweenness centrality can be approximated within a factor $1-\frac{1}{e}$ to the optimal using a greedy incremental algorithm \cite{depz2009}. Brandes' algorithm for computing the betweenness centrality of all vertices can be modified to compute the group betweenness centrality of one group of nodes with the same asymptotic running time \cite{pyeb2009}.

{\bf Degree centrality.}
A simple alternative to the family of shortest path centralities is \textit{degree} centrality. The degree centrality of a node $v\in V$ is defined as the average of its in-degree and its out-degree:
\begin{equation}
d(v) = \frac{|v^+|+|v^-|}{2}
\end{equation}
Degree centrality captures a node's power by its number of neighbors; the higher that number, the better connected the node and the larger its centrality. Despite its simplicity, degree centrality can capture to a good extent a node's structural importance.

{\bf Weighted centralities.}
All aforementioned centralities only employ the graph connectivity information, and treat all links equally. However, in practice links are further characterized by their capacity. We can thus define variants of the previous centralities that additionally take into account the link capacity information. A simple approach is to associate each edge with the non-negative cost $\frac{1}{c(e)}$. This is based on the observation that the higher the capacity, the lower the cost of the link since it can accommodate larger flows. The shortest path centrality variants are simple to define, if we note that the cost of a path is the sum of the costs of its constituent links, and the shortest path refers to the path with the minimum cost among all paths. In a similar spirit, we can define the weighted degree of any node as the sum of the costs of the edges that are incident to the node. Intuitively, we expect that the weighted variants should perform better since they take into account both the connectivity and the capacity information. Section~\ref{sec:eva_weighted} empirically confirms our intuition.

%Finally, note that all aforementioned centralities can accept a weighted variant, where each edge is characterized by a non-negative weight. A common approach is to associate each edge with a unit cost, so that a shortest path minimizes the number of hops from the source to the destination. One shortcoming with this definition is that if edge capacities differ dramatically, then the number of hops may not represent well how good a path is. For this reason, an alternative cost function is $\frac{1}{c_e}$, where $c_e$ the edge capacity. The idea is that the higher the capacity, the lower the cost of the link since it can accommodate a larger flow. In the special case where all link capacities are identical, the two definitions are equivalent up to the multiplicative constant $\frac{1}{c_e}$.
te.tex
%!TEX root = main.tex

\section{Background on Traffic Engineering}
\label{sec:TE}
In our work, we focus on two common types of traffic engineering, depending on the objective criterion.  The first type maximizes the total throughput subject to the capacity and maximum demand constraints. Since it can be formulated as a maximum flow problem, we call it $TE_{MF}$. The second type minimizes the maximum link utilization, which acts as the system bottleneck. For this reason, we call it $TE_{LU}$. 

% In the remainder of this section, we review the two TE types, and reveal an interesting connection between them.

%{\color{red} probably need to say why this section is necessary. also shorten the discussion, reviewers should be familiar with most of the materials here already}

\subsection{Preliminaries}
\label{sec:TE-prelim}
Assume a directed graph $G=(V,E)$, where $V$ is the set of nodes and $E$ the set of directed edges. Given a node $v\in V$, $v^+$ denotes the set of outgoing edges of node $v$, i.e., the subset of edges in $E$ of the form $(v,u)$, $u\in V$. Similarly, the set $v^-$ denotes the set of incoming edges of $v$ of the form $(u,v)$, $u\in N$. The out-degree of $v$ is defined as the cardinality $|v^+|$, whereas the in-degree is defined as the cardinality $|v^-|$.

A \textit{flow network} $G=(V,E,c)$ is defined as a directed graph $G=(V,E)$, together with a non-negative function $c:V\times V\rightarrow\mathbb{R}_{\geq 0}$ that assigns to each edge $e\in E$ a non-negative capacity $c(e)$. If $(u,v)\not\in E$, then we define $c(u,v)=0$.

A \textit{walk} in a directed graph is an alternating sequence of vertices and edges, $v_0$, $e_0$, $v_1$, $\dots$, $v_{k-1}$, $e_{k-1}$, $v_k$, which begins and ends with vertices and has the property that each $e_i$ is an edge from $v_i$ to $v_{i+1}$. A \textit{path} is a walk where all edges are distinct. A \textit{simple path} is a path where all vertices are distinct. The term $u$-$v$ path (resp., simple path) refers to any valid path (resp., simple path) from $u$ to $v$.

In flow networks, we usually distinguish between single-commodity and multi-commodity flows. For single-commodity flow, we consider a single commodity that consists of a source $s\in V$ and a sink $t\in V$, where $s\neq t$. %Our goal is to compute the maximum flow from $s$ to $t$ in the underlying flow network. 
For multi-commodity flows, we assume $L$ commodities of the form $(s_i,t_i)$, where $s_i,t_i\in V, s_i\neq t_i$. Each commodity $i$ is associated with a non-negative demand $D_i\geq0$. For convenience, we also use the notation $\bm{s}=(s_1,\dots,s_L)$ and $\bm{t}=(t_1,\dots,t_L)$, and write $(\bm{s},\bm{t})$ to denote the corresponding multi-commodity network. 
% the following is only for TE_MF
% Our goal is to maximize the sum of flow units that we send from sources $s_i$ to their corresponding sinks $t_i$.

\subsection{TE Type 1: $TE_{MF}$}
\label{sec:TE-MCF}
\begin{comment}
Since the single-commodity flow is a special case of the more general multi-commodity flow, we provide next several formulations for the latter. First, the maximum multi-commodity flow can be formulated as the following LP:

{\color{red} if the arc based formulation is not essential, can we just start with path-based formulation? it's quite well understood in TE literature}

\[
\begin{aligned}
\text{maximize}\qquad & \nu=\sum_{i=1}^L\sum_{e\in {s_i}^{+}}f_i(e)\\
\text{subject to }\qquad & \sum_{i=1}^L f_i(e)\leq c(e), \forall e\in E\\
& \sum_{e\in {s_i}^{+}}f_i(e)\leq D_i\\
& f_i(e)\geq 0, \forall e\in E, \forall i\in\{1,\dots,L\}\\
& \sum_{e\in u^+}f_i(e)=\sum_{e\in u^-}f_i(e), \forall i, \forall u, s_i\neq u\neq t_i\\
\end{aligned}
\]
\end{comment}

Let $\mathcal{P}_i$ be the set of all $s_i$-$t_i$ paths, and $\mathcal{P}_{i,e}$ the set of all $s_i$-$t_i$ paths that go through edge $e$. Then the maximum multi-commodity flow program can be expressed by the following path-based formulation:

\begin{align}
\text{maximize}\qquad & \nu=\sum_{i=1}^L\sum_{p\in \mathcal{P}_i}f_i(p)\label{TE-MCF-obj}\\
\text{subject to }\qquad & \sum_{i=1}^L\sum_{p\in \mathcal{P}_{i,e}} f_i(p)\leq c(e), \forall e\in E\label{TE-MCF-first-constraint}\\
& \sum_{p\in \mathcal{P}_i}f_i(p)\leq D_i\label{TE-MCF-second-constraint}\\
& f_i(p)\geq 0, \forall i\in\{1,\dots,L\}, \forall p\in \mathcal{P}_i\label{TE-MCF-last-constraint}
\end{align}
\begin{comment}
% In the above arc-based formulation, we divide the total flow into $k$ sub-flows, one for each commodity. The flow of commodity $i$ along edge $(u,v)$ is $f_i(u,v)$. The first constraint is a capacity constraint that the sum of all sub-flows on any edge cannot exceed the edge capacity. The second constraint imposes that the flow should be non-negative. The third constraint is a conservation constraint that ensures that each sub-flow is conserved in all nodes other than its source and its sink. For any valid flow $f$, the value of a flow $\nu(f)$ is defined as the total sum of units that all sub-flows $f_i$ send. The maximum flow is then simply defined as $\nu_{max}$. Note also that the multi-commodity flow formulation can also include upper (or lower) bounds for the demands of the commodities, which are easily expressed as linear constraints.
\end{comment}
% In the above formulation, we divide the total flow into $L$ sub-flows, one for each commodity. 
The commodity flow $i$ along path $p\in\mathcal{P}_i$ is $f_i(p)$. Constraint \eqref{TE-MCF-first-constraint} is a capacity constraint that the sum of all sub-flows on any edge cannot exceed the edge capacity. Constraint \eqref{TE-MCF-second-constraint} simply describes the maximum demand $D_i$ for commodity $i$. Finally, constraint \eqref{TE-MCF-last-constraint} simply imposes that the flow should be non-negative. For any valid flow $f$, the value of a flow $\nu(f)$ is defined as the total sum of units that all sub-flows $f_i$ send. The maximum flow is then simply defined as $\nu_{max}$.
$TE_{MF}$ is mostly used in data center backbone WANs \cite{JKMO13,HKMZ13}, where traffic is elastic and the main objective is to fully utilize the expansive WAN links.


Note that even though the single-commodity maximum flow accepts various combinatorial algorithms \cite{amo1993}, e.g., Ford-Fulkerson or Edmonds-Karp, there is to date no combinatorial algorithm for the maximum multi-commodity flow even though the problem is known to be strongly polynomial due to Tardos \cite{Tardos1986}. Furthermore, even though single-commodity networks always accept an integer maximum flow, this is not always the case with multi-commodity networks; in fact, the decision problem of integral multi-commodity flow is NP-complete even if the number of commodities is two, for both the directed and undirected cases \cite{eis1975}.

%Besides the path-based formulation, the maximum multi-commodity flow problem also accepts an arc-based formulation.
%The path formulation implicitly incorporates the node conservation constraints into the paths, so we do not need to list them explicitly as we did in the edge formulation. 
%The latter is more compact and can be represented in polynomial space, whereas the former can take space exponential to the input graph, since there can be exponentially many paths between two nodes.

\subsection{TE Type 2: $TE_{LU}$}
\label{sec:TE-LU}

$TE_{LU}$ is mostly used in carrier networks \cite{HVSB15,FT00}, where traffic demands are given and inelastic, and the main objective thus is to control the congestion or link utilization in order to ensure the smooth operation of the network. 
The general form for this type of TE is:
\begin{align}
\text{minimize}\qquad & \theta\label{TE-LU-obj}\\
\text{subject to }\qquad & \sum_{i=1}^L\sum_{p\in \mathcal{P}_{i,e}} f_i(p)\leq \theta\cdot c(e), \forall e\in E\label{TE-LU-first-constraint}\\
& \sum_{p\in \mathcal{P}_i}f_i(p)\geq D_i\label{TE-LU-second-constraint}\\
& f_i(p)\geq 0, \forall i\in\{1,\dots,L\}, \forall p\in \mathcal{P}_i\label{TE-LU-last-constraint}
\end{align}

The variable $\theta$ in the objective function \eqref{TE-LU-obj} refers to the maximum link utilization, which must be minimized. Constraint \eqref{TE-LU-first-constraint} ensures that $\theta$ will be at least as large as the maximum link utilization; constraint \eqref{TE-LU-second-constraint} ensures that each demand is satisfied; and the last constraint \eqref{TE-LU-last-constraint} is similar to $TE_{MF}$ in Section~\ref{sec:TE-MCF}.

\subsection{An Interesting Connection}
\label{sec:connection}
Having introduced the two types of TE, a natural question is to ask whether they are related. To answer this question, we introduce the following \textit{decision version} of the maximum multi-commodity flow problem.

\begin{definition}\label{def:decision}[Decision version of maximum flow (DMF)]
Given a flow network $G=(V,E,c)$ with a set of $L$ commodities $(\bm{s},\bm{t})$, each associated with a non-negative maximum demand $D_i\geq0$, decide whether the maximum multi-commodity flow has a value of at least $\sum\limits_{i=1}^L{D_i}$.
\end{definition}

Note that is the answer to the decision problem DMF is a ``yes'', then by constraint \eqref{TE-MCF-second-constraint} the maximum flow has to be exactly equal to $\sum\limits_{i=1}^L{D_i}$. If the answer is no, then the maximum flow is strictly less than $\sum\limits_{i=1}^L{D_i}$.

%Note that the optimization version of the maximum flow with demands is at least as hard as without, since the latter is a special case of the former when the maximum demand for any commodity is unbounded (infinite).

%Note that the above TE has a general form. If for instance our goal is not to achieve a flow of value at least $\mathcal{V}^*$ but rather satisfy all demands, then we could simply set $V^*=\sum\limits_{i=1}^L D_i$, which is a special case of the above TE.

We are now ready to establish the following result that reveals the relationship between the two types of TE:

\begin{lemma}\label{lemma:connection}
DMF accepts a ``yes'' answer, if and only if the system \eqref{TE-LU-obj}--\eqref{TE-LU-last-constraint} for $TE_{LU}$ accepts a solution $\theta^*\leq1$.
\end{lemma}
\begin{proof}
Assume that DMF accepts a ``yes'' answer. Then there is a flow that respects constraints \eqref{TE-MCF-first-constraint}--\eqref{TE-MCF-last-constraint}. That flow will then trivially satisfy constraints \eqref{TE-MCF-first-constraint}--\eqref{TE-MCF-last-constraint} with $\theta=1$. Since the objective criterion of $TE_{LU}$ minimizes over $\theta$, the optimal solution to the TE program \eqref{TE-LU-obj}--\eqref{TE-LU-last-constraint} will accept an optimal solution $\theta^*\leq 1$.

For the reverse direction, assume that the system \eqref{TE-LU-obj}--\eqref{TE-LU-last-constraint} accepts a solution $\theta^*\leq1$. Then constraint \eqref{TE-LU-first-constraint} implies that the capacity constraints are satisfied for each edge, thus the corresponding flow is a valid flow for system \eqref{TE-MCF-obj}--\eqref{TE-MCF-last-constraint} with value $\sum\limits_{i=1}^L{D_i}$. The maximum flow has then trivially a value of at least $\sum\limits_{i=1}^L{D_i}$.
\end{proof}

Lemma~\ref{lemma:connection} shows that solving $TE_{LU}$ immediately generates a ``yes'' or ``no'' answer to the DMF. Thus, the TE naturally encompasses the general DMF problem of Definition~\ref{def:decision}. This also suggests that hardness results on the DMF (Proposition~\ref{prop:NPhardness}) immediately imply hardness for $TE_{LU}$. We describe this in more detail in the next section. %For instance, selecting the middlepoint that minimizes link utilization while ensuring that the total flow is at least $\mathcal{V}^*$ is NP-hard.
%\begin{corollary}
%Given a flow network $G$=$(V,E,c)$ with commodity $(s,t)$ and a node $w\neq s,t$, it is NP-hard to solve the following TE problem:
%\begin{align*}
%\min\qquad & \theta\\
%\text{subject to }\qquad & \sum_{i=1}^L\sum_{p\in %\mathcal{P}_{i,e}^w} f_i(p)\leq \theta\cdot c(e), \forall e\in E\\
%& \sum_{i=1}^L\sum_{p\in \mathcal{P}_i^w}f_i(p)\geq0\\
%& f_i(p)\geq 0, \forall i\in\{1,\dots,L\}, \forall p\in \mathcal{P}_i^w
%\end{align*}
%\end{corollary}
%\begin{proof}
%As in Lemma \ref{connection}, we can show that the decision problem in Proposition \ref{prop:NPhardness} accepts a ``yes'' answer if and only if the above TE accepts a solution $\theta^*\leq1$. NP-hardness then follows directly from Proposition \ref{prop:NPhardness}.
%\end{proof}

%\draft{This needs to be fixed. It doesn't belong here.}
To conclude this section, notice that even though we assumed a directed network throughout Section~\ref{sec:TE}, it is possible to extend the definitions to undirected graphs as well. The main difference is that an undirected edge is associated with a capacity, and flow can travel in both directions of a link, under the constraint that the sum of the flow value in the two edge directions does not exceed the capacity. Despite the innocuous difference, our analysis in Appendix~\ref{sec:undirected} uncovers a profound dichotomy between the two cases with regard to maximum flow.
theory.tex
%!TEX root = main.tex

\section{Hardness of General Segment Routing}
% \section{Hardness of Flow Centrality}
\label{sec:theory}

In this section, we present the first part of our theoretical investigation. We study the general form of applying segment routing to TE, where traffic can take any path that goes through a middlepoint. We prove an important new result that it is NP-hard to decide if the maximum flow through just one given middlepoint is greater than 0. 
Due to the connection between the decision version of maximum flow and $TE_{LU}$, this also means that $TE_{LU}$ given a single fixed middlepoint is already NP-hard. This then motivates us to consider using segment routing with shortest paths only in the next section.

% In this section, we investigate network flow centrality, which characterizes the node importance by the maximum amount of flow that can go through that node. Network flow centrality was originally introduced by Freeman, Borgatti and White for flow networks \cite{fbw1991}. Sec.~\ref{sec:preliminaries} reviews several key concepts from multi-commodity flow networks and maximum flow. Sec.~\ref{sec:flow-centrality} introduces the flow centrality by Freeman et al. \cite{fbw1991}, and proposes a new flow centrality better suited for multi-commodity flow networks. Sec.~\ref{sec:directed} analyzes the computational complexity of flow centrality for directed graphs, and Sec.~\ref{sec:undirected} for undirected graphs.

\subsection{Hardness of $TE_{MF}$}
\label{sec:directed}
% \subsubsection{Individual flow centrality}

The maximum multi-commodity flow $f_{max}$ with value $\nu_{max}$ refers to the total flow over all possible paths that each commodity accepts. Assume instead that we focus on the maximum flow that can go through a specific network node, e.g., $w\neq s,t$. Let $\mathcal{P}_i^w$ be the set of all $s_i$-$w$-$t_i$ paths (i.e. $s_i$-$t_i$ paths that go through $w$), and $\mathcal{P}_{i,e}^w$ the set of all $s_i$-$w$-$t_i$ paths that also go through edge $e$. The path-based formulation then is:
\[
\begin{aligned}
\text{maximize}\qquad & \nu^w=\sum_{i=1}^L\sum_{p\in \mathcal{P}_i^w} f_i(p)\\
\text{subject to }\qquad & \sum_{i=1}^L\sum_{p\in \mathcal{P}_{i,e}^w} f_i(p)\leq c(e), \forall e\in E\\
& f_i(p)\geq 0, \forall i\in\{1,\dots,L\}, \forall p\in \mathcal{P}_i^w\\
\end{aligned}
\]
We denote the maximum flow through any node $w$ as the \textit{maximum} $w$-\textit{flow} $f_{max}^w$ and denote its value by $\nu_{max}^w$. Alternatively, we use the notation $s$-$w$-$t$ flow for single-commodity networks (or $\bm{s}$-$w$-$\bm{t}$ for multi-commodity networks). Similarly, for single-commodity flows we also write $\nu_{max}^w(s,t)$ (or $\nu_{max}^w(\bm{s},\bm{t})$ for multi-commodity networks) for the value of the maximum $w$-flow.

Note that in the single-commodity case we always assume that $w\neq s,t$, even if not explicitly stated. Indeed, if either $w=s$ or $w=t$ then $\nu_{max}=\nu_{max}^w$. In this case, the problem is strongly polynomial and accepts combinatorial algorithms such as the Ford-Fulkerson algorithm.


A central result in graph theory that we will be using throughout the paper is the two node-disjoint path (2DP) problem due to Fortune, Hopcroft and Wyllie \cite{fhw1980}.
\begin{theorem}[NP-hardness of 2DP \cite{fhw1980}]
\label{theorem:2node-disjoint}
Assume a directed graph $G=(V,E)$ and four distinct vertices $u_1,u_2,$ $v_1,v_2\in V$. It is NP-hard to decide whether there are two node-disjoint paths in $G$ from $u_1$ to $u_2$ and from $v_1$ to $v_2$.
\end{theorem}

%Note that Theorem \ref{theorem:2node-disjoint} can be equivalently stated in terms of three \textit{distinct} nodes $s,t,w$, where it is NP-hard to decide whether there are two node-disjoint paths from $s$ to $w$ and from $w$ to $t$, excluding the common node $w$. Indeed, assume that we augment the graph $G$ of Theorem \ref{theorem:2node-disjoint} with a new node $z$ and the two directed edges $(v_1,z)$ and $(z,u_2)$. Then it is simple to see that there are two disjoint paths from $u_1$ to $z$ and from $z$ to $v_2$ (excluding $z$), if and only if there are two node-disjoint paths from $u_1$ to $v_1$ and from $u_2$ to $v_2$.

We are now ready to provide two lemmas.

\begin{lemma}
\label{lemma:exists-simple-path-NPhard}
Computing whether there is a simple $s$-$w$-$t$ path in a directed graph $G=(V,E)$, where $w,s,t\in V$ and  $w\neq s, t$, is NP-hard.
\end{lemma}
\begin{proof}
Finding whether there is a simple $s$-$t$ path that goes through a node $w$ is equivalent to determining whether there are two node-disjoint paths from $s$ to $w$ and from $w$ to $t$ (excluding of course node $w$). We prove that the latter problem is NP-hard by a reduction from the NP-hard 2DP problem.

Assume a directed graph $G=(V,E)$ and nodes $u_1,u_2$,$v_1$,$v_2$ $\in V$. We introduce a new node $w$ and create the new edges $e_1=(u_2,w)$ and $e_2=(w,v_1)$. We now argue that there are two node-disjoint paths from $u_1$ to $u_2$ and from $v_1$ to $v_2$, if and only if there is a simple $u_1$-$w$-$v_2$ path. 

Indeed, if the former condition is satisfied, then we can know for sure that the path from $u_1$ to $u_2$ cannot go through node $w$ through edge $e_1$ since otherwise that path would also have to use node $v_1$ after $w$ since $u_2$ is the end node. Similarly we can argue that the path from $v_1$ to $v_2$ cannot go through node $w$ through edge $e_2$. But then we can form a new path from $u_1$ to $v_2$ by concatenating the path $u_1$ to $u_2$, edge $e_1$, edge $e_2$, and finally the path from $v_1$ to $v_2$. This path does not repeat any node since the node disjoint paths from $u_1$ to $u_2$ and from $v_1$ to $v_2$ do not contain $w$, hence it is a simple path. For the reverse direction, we just note that if there exists a simple $u_1$-$w$-$v_2$ path, then this path will necessarily contain edges $e_1$ and $e_2$. By removing these two edges, we get two node-disjoint paths, one from $u_1$ to $u_2$ and another from $v_1$ to $v_2$, since the $u_1$-$w$-$v_2$ path is simple.
\end{proof}

\begin{lemma}
\label{lemma:exists-path-NPhard}
Computing whether there is a $s$-$w$-$t$ path in a directed graph $G=(V,E)$, where $w,s,t\in V$ and $w\neq s, t$, is NP-hard.
\end{lemma}
\begin{proof}
Finding whether there is a $s$-$t$ path that goes through a node $w$ is equivalent to determining whether there are two edge-disjoint paths from $s$ to $w$ and from $w$ to $t$. We now argue that the latter problem is NP-hard by a reduction from the 2DP problem.

Indeed, assume any graph $G=(V,E)$, and three distinct nodes $s,t,w\in V$. We construct a new graph $G'=(V',E')$ from $G=(V,E)$ in the following manner. For each node $v\in V$ we introduce two nodes $v_{in},v_{out}\in V'$. For each edge $e=(u,v)\in E$, we introduce an edge $e'=(u_{out},v_{in})\in E'$. Moreover, $E'$ contains an edge $e'=(v_{in},v_{out})$ connecting each pair of nodes $v_{in},v_{out}$ in $G'$ that we constructed above. We now make the statement that there are two edge-disjoint paths in graph $G'$ from $s_{out}$ to $w_{in}$ and from $w_{out}$ to $t$, if and only if there are two node-disjoint paths in $G$ from $s$ to $w$ and from $w$ to $t$.

Indeed, consider first any two node-disjoint paths in $G$, namely, $s, u_1,\dots,u_l,w$ and $w,v_1,\dots,v_m,t$, where all intermediate nodes $u_i$ and $v_j$ are distinct. Then it is easy to see that the paths $s_{out},$ $u_{1,in},$ $u_{1,out},$ $\dots,$ $u_{l,in},$ $u_{l,out},$ $w_{in}$ and $w_{out},$ $v_{1,in},$ $v_{1,out},$ $\dots,$ $v_{m,in},$ $v_{m,out},$ $t_{in}$ in $G'$ are : (1) valid since they use existing edges in $G'$, and (2) edge-disjoint since the set of nodes on the first path is disjoint to the set of nodes in the second. For the reverse direction, consider two edge-disjoint paths in $G'$ from $s_{out}$ to $w_{in}$ and from $w_{out}$ to $t$. We then argue that these paths necessarily have the above form $s_{out},$ $u_{1,in},$ $u_{1,out},$ $\dots,$ $u_{l,in},$ $u_{l,out},$ $w_{in}$ and $w_{out},$ $v_{1,in},$ $v_{1,out},$ $\dots,$ $v_{m,in},$ $v_{m,out},$ $t_{in}$. The reason is that any pair of nodes $(v_{in},v_{out})$ can only be reached from other nodes in $V'$ via $v_{in}$ and can only reach other nodes in $V'$ via $v_{out}$. So, a path will necessarily consist of consecutive pairs of nodes of the form $(v_{in},v_{out})$ (with the exception of the two endpoints). Furthermore, any such pair $(v_{in},v_{out})$ can (1) appear at most once on either path, and (2) cannot appear on both paths. The reason is that going from $v_{in}$ to $v_{out}$ requires edge $v_{in},v_{out}$, but the two paths are edge-disjoint. But then it holds that the paths $s, u_1,\dots,u_l,w$ and $w,v_1,\dots,v_m,t$ in $G$ are both valid and node-disjoint. This completes the proof.
\end{proof}

We next provide definitions and results for the maximum $w$-flow that are reminiscent of results in traditional single-commodity maximum flow. One significant difference is that the \textit{cut} is now defined as a collection of edges rather than a collection of nodes. We focus first on the $s$-$w$-$t$ flow in single-commodity networks.

\begin{definition}
A $s$-$w$-$t$ edge-cut is a subset of edges $\mathcal{C}^w\subseteq E$ such that removing the edges in $\mathcal{C}^w$ from the graph results in no $s$-$w$-$t$ paths, i.e., there are no $s$-$w$-$t$ paths in the graph $G'=(V,E-\mathcal{C}^w)$. The value $c(\mathcal{C}^w)$ of the edge-cut is defined as the sum of the capacities of all edges in $\mathcal{C}^w$.
\end{definition}

\begin{lemma}
\label{anyf_anyc}
Let $f^w$ be any $s$-$w$-$t$ flow, and $\mathcal{C}^w$ any $s$-$w$-$t$ cut. Then $\nu^w(f^w)\leq c(\mathcal{C}^w)$.
\end{lemma}
\begin{proof}
First, note that the flow $f^w$ is the sum of individual flows, each going through a distinct $s$-$w$-$t$ path $p$. Each of these individual flows must go through at least some edge in $e\in\mathcal{C}^w$, otherwise there would be a $s$-$w$-$t$ path in the graph $G'=(V,E-E')$. So, let $\mathcal{F}_e$ be the set of flows that go through $e$. Then we have:
\begin{align}
\sum_{e\in\mathcal{C}^w}\nu^w(\mathcal{F}_e) &\leq \sum_{e\in\mathcal{C}^w}c(e) \Leftrightarrow \notag \\
\sum_{e\in\mathcal{C}^w}\nu^w(\mathcal{F}_e) &\leq c(\mathcal{C}^w) \Leftrightarrow \notag \\
\nu^w(f^w) &\leq c(\mathcal{C}^w)
\end{align}
Note that $\sum_{e\in\mathcal{C}^w}\nu^w(\mathcal{F}_e)$ $\leq$ $\nu^w(f)$, since we argued that the path for each individual flow must go through at least one edge in $\mathcal{C}^w$.
\end{proof}

\begin{lemma}
\label{maxc_minc}
Given a flow network $G=(V,E,c)$ and three distinct nodes $s,w,t$, the maximum value of any $s$-$w$-$t$ flow is equal to the minimum capacity of any $s$-$w$-$t$ edge-cut.
\end{lemma}
\begin{proof}
Consider a variation of the well-known Ford-Ful-kerson algorithm for (single-commodity) maximum flow \cite{ps1982}, where at each round the algorithm picks a $s$-$w$-$t$ path rather than just a $s$-$t$ path. The augmenting $s$-$w$-$t$ path algorithm terminates, if and only if there is an $s$-$w$-$t$ edge-cut in the graph where each edge $e\in\mathcal{C}^w$ is saturated. Next, note that the total flow comprised of all individual path flows must be at least as large as the capacity of that edge-cut. But since by Lemma \ref{anyf_anyc} the value of any flow can be at most as large as the value of any $s$-$w$-$t$ edge-cut, it must necessarily hold that the flow that the augmenting path algorithm returns is maximal and equal to the capacity of the minimum $s$-$w$-$t$ edge-cut.
\end{proof}

\begin{corollary}
\label{integrality}
For integral capacities, there is a maximum $s$-$w$-$t$ flow that is integral.
\end{corollary}
\begin{proof}
Note that by Lemma \ref{maxc_minc} the augmenting $s$-$w$-$t$ path algorithm returns a maximal flow and, furthermore, at each step the flow on any edge is integral. Thus, there must be a maximal flow whose value on any edge is integral.
\end{proof}

We are now ready to prove that the decision problem of whether the maximum flow through any specific node is greater than 0 is NP-hard under integral demands.
\begin{proposition}
\label{prop:NPhardness}
Given a multi-commodity flow network $G=(V,E,c)$, it is NP-hard to even decide whether $\nu_{max}^w(\bm{s},\bm{t})>0$.
\end{proposition}
\begin{proof}
We show that even the single-commodity version of our problem is NP-hard. Since the single-commodity case can be seen as a special case of the multi-commodity problem, our result immediately implies hardness for the multi-commodity maximum flow as well. Our strategy will be to reduce the $s$-$w$-$t$ path problem in Lemma \ref{lemma:exists-path-NPhard} to the single-commodity maximum flow problem with integral demands.

Indeed, consider a directed graph $G=(V,E)$ and three distinct nodes $s,t,w\in V$. We construct a flow-network $G'$ from $G$ in the following manner. We consider one commodity from $s$ to $t$, and we further assume that each edge $e\in E$ has a capacity of 1.  We then argue that there is a path from $s$ to $t$ through $w$, if and only if the maximum flow through $w$ in $G'$ is greater than 0.

First, assume there is a path $p=(s,e_1,\dots,e_m,t)$, so that every edge $e_i$ in the path appears only once and node $w$ appears in the path. It is then possible to send one unit of flow from $s$ to $t$, given the unit capacities. Thus, the maximum multi-commodity flow will be at least 1, and thus for sure greater than 0. For the reverse direction, assume there is a maximum flow greater than 0 in $G'$. Since we only have one commodity, it follows that there has to be a maximum flow where the flow value on every edge is integral. Moreover, note that each edge can be used at most once in that flow due to its unit capacity. Now, consider any path $p_{(s,w)}$ that carries flow from $s$ to $w$, and any path $p_{(w,d)}$ that carries flow from $w$ to $d$. Since each edge is used at most once, this means that the path $p_{(s,w)}\cup p_{(w,d)}$ has the properties: (1) it goes from $s$ to $d$ through $w$, and (2) it visits any edge at most once. Thus, there must be a path from $s$ to $t$ through $w$.
\end{proof}


\begin{corollary}\label{corollary:cut-hardness}
Given a flow network $G=(V,E,c)$ with a single commodity $(s,t)$ and a node $w\in V$, it is NP-hard to compute the minimum $s$-$w$-$t$ cut $\mathcal{C}^w$.
\end{corollary}
\begin{proof}
We can show that even for single commodity-networks the problem is NP-hard. Indeed, by Lemma \ref{maxc_minc} we know that the maximum value of any $s$-$w$-$t$ flow is equal to the minimum capacity of any $s$-$w$-$t$ edge-cut. But since by Proposition \ref{prop:NPhardness} it is NP-hard to compute the maximum $s$-$w$-$t$ flow, it must also be NP-hard to compute the value of the minimum $s$-$w$-$t$ cut.
\end{proof}

Perhaps unexpectedly, the above hardness results do not hold when the underlying graph is undirected. Appendix \ref{sec:undirected} discusses this dichotomy in detail.


\subsection{Hardness of $TE_{LU}$}
\label{sec:hardness_TE}


For the flow network $G$ with the $L$ commodities, we define the $TE_{LU}$ in the following manner:
\begin{align}
\min\qquad & \theta\label{TE2-LU-obj}\\
\text{subject to }\qquad & \sum_{i=1}^L\sum_{p\in \mathcal{P}_{i,e}^w} f_i(p)\leq \theta\cdot c(e), \forall e\in E\label{TE2-LU-first-constraint}\\
& \sum_{i=1}^L\sum_{p\in \mathcal{P}_i^w}f_i(p)\geq0\label{TE2-LU-second-constraint}\\
& f_i(p)\geq 0, \forall i\in\{1,\dots,L\}, \forall p\in \mathcal{P}_i^w\label{TE2-LU-last-constraint}
\end{align}

Lemma \ref{lemma:connection} shows that solving the $TE_{LU}$ immediately generates a ``yes'' or ``no'' answer to the corresponding DMF. Thus, the hardness results on the DMF (Proposition \ref{prop:NPhardness}) immediately imply hardness for the corresponding TE: %For instance, selecting the middlepoint that minimizes link utilization while ensuring that the total flow is at least $\mathcal{V}^*$ is NP-hard.
\begin{corollary}
\label{corollary:NP-hard-TE-LU}
It is NP-hard to solve the $TE_{LU}$ \eqref{TE2-LU-obj}--\eqref{TE2-LU-last-constraint}.
\end{corollary}


main.bbl
% Generated by IEEEtranS.bst, version: 1.13 (2008/09/30)
\begin{thebibliography}{10}
\providecommand{\url}[1]{#1}
\csname url@samestyle\endcsname
\providecommand{\newblock}{\relax}
\providecommand{\bibinfo}[2]{#2}
\providecommand{\BIBentrySTDinterwordspacing}{\spaceskip=0pt\relax}
\providecommand{\BIBentryALTinterwordstretchfactor}{4}
\providecommand{\BIBentryALTinterwordspacing}{\spaceskip=\fontdimen2\font plus
\BIBentryALTinterwordstretchfactor\fontdimen3\font minus
  \fontdimen4\font\relax}
\providecommand{\BIBforeignlanguage}[2]{{%
\expandafter\ifx\csname l@#1\endcsname\relax
\typeout{** WARNING: IEEEtranS.bst: No hyphenation pattern has been}%
\typeout{** loaded for the language `#1'. Using the pattern for}%
\typeout{** the default language instead.}%
\else
\language=\csname l@#1\endcsname
\fi
#2}}
\providecommand{\BIBdecl}{\relax}
\BIBdecl

\bibitem{cvxpy}
\url{http://www.cvxpy.org/en/latest/}.

\bibitem{defo}
``Declarative and expressive forwarding optimizer,''
  \url{http://sites.uclouvain.be/defo/}, October 2016.

\bibitem{amo1993}
R.~K. Ahuja, T.~L. Magnanti, and J.~B. Orlin, \emph{Network Flows: Theory,
  Algorithms, and Applications}.\hskip 1em plus 0.5em minus 0.4em\relax
  Prentice-Hall, Inc., 1993.

\bibitem{aubry2016scmon}
F.~Aubry, D.~Lebrun, S.~Vissicchio, M.~T. Khong, Y.~Deville, and
  O.~Bonaventure, ``{SCMon: Leveraging Segment Routing to Improve Network
  Monitoring},'' in \emph{Proc.~IEEE INFOCOM}, 2016.

\bibitem{bhatia2015optimized}
R.~Bhatia, F.~Hao, M.~Kodialam, and T.~V. Lakshman, ``{Optimized Network
  Traffic Engineering using Segment Routing},'' in \emph{Proc.~IEEE INFOCOM},
  2015.

\bibitem{b87}
P.~Bonacich, ``{Power and Centrality: A Family of Measures},'' \emph{American
  Journal of Sociology}, vol.~92, no.~5, pp. 1170--1182, 1987.

\bibitem{B2001}
U.~Brandes, ``A faster algorithm for betweenness centrality,'' \emph{Journal of
  Mathematical Sociology}, vol.~25, pp. 163--177, 2001.

\bibitem{CLNR14}
R.~Cohen, L.~Lewin-Eytan, J.~S. Naor, and D.~Raz, ``{On the effect of
  forwarding table size on SDN network utilization},'' in \emph{Proc.~IEEE
  INFOCOM}, 2014.

\bibitem{CMTY11}
A.~R. Curtis, J.~C. Mogul, J.~Tourrilhes, P.~Yalagandula, P.~Sharma, and
  S.~Banerjee, ``Devoflow: {Scaling} flow management for high-performance
  networks,'' in \emph{Proc.~ACM SIGCOMM}, 2011.

\bibitem{depz2009}
S.~Dolev, Y.~Elovici, R.~Puzis, and P.~Zilberman, ``Incremental deployment of
  network monitors based on group betweenness centrality,'' \emph{Inf. Process.
  Lett.}, vol. 109, no.~20, pp. 1172--1176, 2009.

\bibitem{D13}
A.~Domahidi, E.~Chu, and S.~Boyd, ``{{ECOS}: {A}n {SOCP} solver for embedded
  systems},'' in \emph{Proc.~European Control Conference (ECC)}, 2013.

\bibitem{t1998}
T.~Eilam-Tzoreff, ``The disjoint shortest paths problem,'' \emph{Discrete Appl.
  Math.}, vol.~85, no.~2, pp. 113--138, 1998.

\bibitem{EJLW01}
A.~Elwalid, C.~Jin, S.~Low, and I.~Widjaja, ``{MATE: MPLS Adaptive Traffic
  Engineering},'' in \emph{Proc.~IEEE INFOCOM}, 2001.

\bibitem{eis1975}
S.~Even, A.~Itai, and A.~Shamir, ``On the complexity of time table and
  multi-commodity flow problems,'' in \emph{Proceedings of the 16th Annual
  Symposium on Foundations of Computer Science}, 1975, pp. 184--193.

\bibitem{eb1999}
M.~G. Everett and S.~P. Borgatti, ``The centrality of groups and classes,''
  \emph{The Journal of Mathematical Sociology}, vol.~23, no.~3, pp. 181--201,
  1999.

\bibitem{FRZ13}
N.~Feamster, J.~Rexford, and E.~Zegura, ``The road to {SDN: An} intellectual
  history of programmable networks,'' \emph{ACM Queue}, vol.~11, no.~12, pp.
  20:20--20:40, December 2013.

\bibitem{f1998}
U.~Feige, ``A threshold of ln n for approximating set cover,'' \emph{Journal of
  ACM}, vol.~45, no.~4, pp. 634--652, 1998.

\bibitem{segment3}
C.~Filsfils, S.~Previdi, A.~Bashandy, and Decraene, ``Segment routing with mpls
  data plane,'' \emph{Internet Engineering Task Force, Internet Draft (Work in
  Progress) draft-ietf-spring-segment-routing-mpls-00}, 2014.

\bibitem{segment2}
C.~Filsfils, P.~Francois, and Previdi, ``Segment routing use cases,'' 2013.

\bibitem{segment1}
C.~Filsfils, N.~K. Nainar, and Pignataro, ``{The Segment Routing
  Architecture},'' in \emph{Proc.~IEEE Globecom}, 2015.

\bibitem{fhw1980}
S.~Fortune, J.~Hopcroft, and J.~Wyllie, ``The directed subgraph homeomorphism
  problem,'' \emph{Theoretical Computer Science}, vol.~10, no.~2, pp. 111--121,
  1980.

\bibitem{FT00}
B.~Fortz and M.~Thorup, ``Internet traffic engineering by optimizing {OSPF}
  weights,'' in \emph{Proc.~IEEE INFOCOM}, 2000.

\bibitem{fbw1991}
L.~C. Freeman, S.~P. Borgatti, and D.~R. White, ``{Centrality in valued graphs:
  A measure of betweenness based on network flow},'' \emph{Social Networks},
  vol.~13, no.~2, pp. 141--154, 1991.

\bibitem{F1977}
L.~C. Freeman, ``{A Set of Measures of Centrality Based on Betweenness},''
  \emph{Sociometry}, vol.~40, no.~1, pp. 35--41, 1977.

\bibitem{GHCR13}
A.~Ghosh, S.~Ha, E.~Crabbe, and J.~Rexford, ``Scalable multi-class traffic
  management in data center backbone networks,'' 2013.

\bibitem{giorgetti2015path}
A.~Giorgetti, P.~Castoldi, F.~Cugini, J.~Nijhof, F.~Lazzeri, and G.~Bruno,
  ``Path encoding in segment routing,'' in \emph{Proc.~IEEE Globecom}, 2015.

\bibitem{hartert2015solving}
R.~Hartert, P.~Schaus, S.~Vissicchio, and O.~Bonaventure, ``{Solving Segment
  Routing Problems with Hybrid Constraint Programming Techniques},'' in
  \emph{International Conference on Principles and Practice of Constraint
  Programming}, 2015.

\bibitem{HVSB15}
R.~Hartert, S.~Vissicchio, P.~Schaus, O.~Bonaventure, C.~Filsfils, T.~Telkamp,
  and P.~Francois, ``{A Declarative and Expressive Approach to Control
  Forwarding Paths in Carrier-Grade Networks},'' in \emph{Proc.~ACM SIGCOMM},
  2015.

\bibitem{HBCR07}
J.~He, M.~Bresler, M.~Chiang, and J.~Rexford, ``Towards robust multi-layer
  traffic engineering: Optimization of congestion control and routing,''
  vol.~25, no.~5, pp. 868--880, June 2007.

\bibitem{HKMZ13}
C.-Y. Hong, S.~Kandula, R.~Mahajan, M.~Zhang, V.~Gill, M.~Nanduri, and
  R.~Wattenhofer, ``Achieving high utilization with software-driven {WAN},'' in
  \emph{Proc.~ACM SIGCOMM}, 2013.

\bibitem{JKMO13}
S.~Jain, A.~Kumar, S.~Mandal, J.~Ong, L.~Poutievski, A.~Singh, S.~Venkata,
  J.~Wanderer, J.~Zhou, M.~Zhu, J.~Zolla, U.~H\"{o}lzle, S.~Stuart, and
  A.~Vahdat, ``{B4}: Experience with a globally-deployed software defined
  {WAN},'' in \emph{Proc.~ACM SIGCOMM}, 2013.

\bibitem{KKDC05}
S.~Kandula, D.~Katabi, B.~Davie, and A.~Charny, ``{Walking the Tightrope:
  Responsive Yet Stable Traffic Engineering},'' in \emph{Proc.~ACM SIGCOMM},
  2005.

\bibitem{K1984}
N.~Karmarkar, ``A new polynomial-time algorithm for linear programming,'' in
  \emph{Proc.~ACM STOC}, 1984.

\bibitem{K1980}
L.~Khachiyan, ``Polynomial algorithms in linear programming,'' \emph{USSR
  Computational Mathematics and Mathematical Physics}, vol.~20, no.~1, pp.
  53--72, 1980.

\bibitem{KPK15}
M.~Ku{\'z}niar, P.~Pere{\v{s}}{\'\i}ni, and D.~Kosti{\'c}, ``{What you need to
  know about SDN flow tables},'' in \emph{Proc.~PAM}, 2015.

\bibitem{Levin2014}
D.~Levin, M.~Canini, S.~Schmid, F.~Schaffert, and A.~Feldmann, ``Panopticon:
  Reaping the benefits of incremental sdn deployment in enterprise networks,''
  in \emph{2014 USENIX Annual Technical Conference (USENIX ATC 14)}, 2014, pp.
  333--345.

\bibitem{LKMZ14}
H.~H. Liu, S.~Kandula, R.~Mahajan, M.~Zhang, and D.~Gelernter, ``Traffic
  engineering with forward fault correction,'' in \emph{Proc.~ACM SIGCOMM},
  2014.

\bibitem{Lukovszki2016}
T.~Lukovszki, M.~Rost, and S.~Schmid, ``It's a match!: Near-optimal and
  incremental middlebox deployment,'' \emph{SIGCOMM Comput. Commun. Rev.},
  vol.~46, no.~1, pp. 30--36, 2016.

\bibitem{Lukovszki2015}
T.~Lukovszki and S.~Schmid, ``Online admission control and embedding of service
  chains,'' in \emph{Post-Proceedings of the 22Nd International Colloquium on
  Structural Information and Communication Complexity - Volume 9439}, ser.
  SIROCCO 2015, 2015, pp. 104--118.

\bibitem{MPEK16}
L.~Moln\'{a}r, G.~Pongr\'{a}cz, G.~Enyedi, Z.~L. Kis, L.~Csikor, F.~Juh\'{a}sz,
  A.~K\H{o}r\"{o}si, and G.~R{\'e}tv\'{a}ri, ``{Dataplane Specialization for
  High-performance OpenFlow Software Switching},'' in \emph{Proc.~ACM SIGCOMM},
  2016.

\bibitem{nwf1978}
G.~L. Nemhauser, L.~A. Wolsey, and M.~L. Fisher, ``An analysis of
  approximations for maximizing submodular set functions---i,''
  \emph{Mathematical Programming}, vol.~14, no.~1, pp. 265--294, 1978.

\bibitem{Newman2010}
M.~Newman, \emph{Networks: An Introduction}.\hskip 1em plus 0.5em minus
  0.4em\relax Oxford University Press, Inc., 2010.

\bibitem{ps1982}
C.~H. Papadimitriou and K.~Steiglitz, \emph{Combinatorial Optimization:
  Algorithms and Complexity}.\hskip 1em plus 0.5em minus 0.4em\relax
  Prentice-Hall, Inc., 1982.

\bibitem{pyeb2009}
R.~Puzis, D.~Yagil, Y.~Elovici, and D.~Braha, ``Collaborative attack on
  internet users' anonymity,'' \emph{Internet Research}, vol.~19, pp. 60--77,
  2009.

\bibitem{M05}
M.~Roughan, ``{Simplifying the synthesis of Internet traffic matrices},''
  \emph{ACM CCR}, vol.~35, no.~5, pp. 93--96, 2005.

\bibitem{Tardos1986}
E.~Tardos, ``A strongly polynomial algorithm to solve combinatorial linear
  programs,'' \emph{Oper. Res.}, vol.~34, no.~2, pp. 250--256, 1986.

\bibitem{WXQY06}
H.~Wang, H.~Xie, L.~Qiu, Y.~R. Yang, Y.~Zhang, and A.~Greenberg, ``{{COPE:}
  Traffic Engineering in Dynamic Networks},'' in \emph{Proc.~ACM SIGCOMM},
  2006.

\end{thebibliography}
