\chapter{Routing of circuits\label{chap:CircuitRouting}}

\section{Introduction}

\subsection{Organization of the chapter}

\section{Background and previous work}

\section{}

\section{Conclusions and summary of contributions}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Discussion with Frank Kelly}
\begin{itemize}
\item Bistability is likely to occur where the difference between the shortest path and the next shortest path is relatively large (e.g. in meshes where the SP is of length one, and the next SP is of length 2)
\item if several SPs of same or similar length exist, then there is little/no bistability
\item if there is bistability (hysteresis), the we can solve it by eliminating/rerouting the ccts along very long routes (those taking many resources that might be needed by other more direct flows). We can also solve it by using shadow proices that prevent ccts from being established along long routes, even if there are enough resources currently
\item If we use shadow prices, we have to tackle issues with fairness (long flows have to be able to make it).
\item one can use off-line, centralized algorithms to set shadow price budgets fairly, but on-line, distribued algorithms to calculate prices and do the routing.
\item For diversity routing, optimal algorithms are NP hard, but heuristics are P hard, and good enough
\item for diversity routing, sometimes the fate sharing between elements is not well known, so the graph is inaccurate (e.g. 2 routers sharing the same power line, but no one told you about it), and there is little need in being optimal, if your information is not that accurate.
\end{itemize}

\section{Introduction}

This section discuses some general issues concerning the routing of circuits in a network and proposes different routing mechanisms that can be used in conjuction with TCP switching

Routing is as an important problem in a communications network as switching. By definition switching just forwards information inside a network node, from the input port to a given output port. But, which output port? This is determined by the routing mechanism. By composing several switched segments inside network nodes, the routing mechanism defines a path or route that goes from the source of the information flow to its destination. In a sense, switching provides the forwarding, whereas routing provides the steering.

A routing algorithm performs two main functions: one is to compute the path or route between different source-destination pairs, the other is to look up the corresponding route (or output port) whenever a circuit request or a packet arrives. A difference between routing circuits and packets is when the routing lookup is taken. With circuits a route lookup only needs to be done when the circuit is established. In packet switching a route lookup the route lookup is performed for every packet arrival. Because a circuit usually carries the same amount of information as several packets, routing occur more frequently in packet switching. Techniques like MPLS or VCs (such as ATM) speed the route lookup of packets by performing a fixed length match on a local address space, rather than a variable-length match on a global address space.  

In the rest of this chapter I will focus only in the route computation problem.


The routing of circuits and packets is very similar, as in both cases it just defines a path or route for the information flow. However there is a major difference in the switching that requires special attention. In circuit switching, resources are assigned in exclusivity to flows. If there are too many flows, we will run out of resources, mainly bandwidth in the outgoing link. As a result, the information flow cannot make progress and it is therefore blocked. On the other hand if there are too many packets arriving at a node, the excess is buffered locally, in the hope that the oversubscription rapidly disappears. However if this oversubscription lasts for a long time, those excess packets will eventually be dropped. With packets there is no blocking, but rather some potential packet drops.

A bad routing algorithm will overload certain parts of the network, and it will have different effects on packets or circuits. Under overload, packets are delayed, and even dropped, because of queueing, whereas circuits are blocked (until bandwidth becomes available) or even dropped, if they have too wait for too long.

A good routing algorithm for packets is such that it achieves high throughput for a given average packet delay. In the case of circuits, a good algorithm produces a low circuit blocking probability.

In theory each packet in a flow could be following a different path, we just need to make a different routing decision at any node of the network for each of them. In practice packets follow a single precomputed path, more specifically the shortest path to the destination, because computing the full path is very costly, where as looking up a cached version of the decision is not.

There have been proposals to have several paths of equal or similar cost to the destination, so that these paths can be load balanced and then the capacity to the destination is increased {\bf [check with Sundar]}.

Routing algorithms can be static, if routes remain fixed regardless of the network conditions, or adaptive, if routes change as the load changes. Static routing algorithms do not behave well under diverse traffic patterns because they may concentrate traffic in certain parts of the network. An adaptive algorithm can distribute the load more evenly, improving the total throughput.

The most common routing algorithms in the Internet create paths that follow the shortest-path tree to the destination. This tree is calculated either the Bellman-Ford algorithm, like RIP \cite{RIP}, or Dijkstra's algorithm, like OSPF \cite{OSPF}. An overviewof both algorithmscan be found in \cite{BertsekasGallager92}.


There are several ways of dealing with blocking XXXX

The goal of a routing algorithm for a CS'ed core is to:
-achieve the maximum throughput through the network
-be compatible with IP routing protocols used at the edges (we want to simulate IP routing inside the circuit switched cloud)

IP routing protocols such as OSPF use hop-by-hop routing, with some network topology information which might be stale.

All circuits are unidirectional and independent routing decision are made for each direction. In the case of a bi-directional communication, two independent, uni-directional circuits are created.

I have studied a set of traceroutes from NLANR [ref]. They are traceroutes performed every 10 minutes between different universities and research institutions [XXX results and what is a traceroute XXX]
\section{Control traffic}

In TCP Switching, control information (routing information, network status, alarms, etc.) uses packet switching to communicate. Keeping a circuit between every pair of nodes is very expensive. Because IP is the most common protocol based on packets, I propose using it. 

This is also used in the phone system by the Intelligent Network in the form of the SS7 protocol [ref].

\section{Centralized routing}

One way of finding the maximum flow through a network is to write the problem as a linear program. This is a centralized routing algorithm that requires the knowledge of the state of all links in the network, as well as the flow demand between source-destination pairs. 

Given a graph $G$ composed of nodes interconnected through edges or links, we can write the multicommodity maximum flow problem as a linear problem. In the set of nodes we have a subset of sources $\mathcal{S} = \{ s \}$ and a subset of destinations $\mathcal{T} = \{ t \}$. Each source-destination pair has a demand of $F_{s,t}$. With this variables the resulting problem is like this:


{\bf
One way of putting it:

Objective function:
\[ max{\sum_{s \in \mathcal{S}} \sum_{t \in \mathcal{T}} \sum_{k \in N(s)} f_{s,k}^{s,t} - f_{k,s}^{s,t} }\]  \label{eq:RoutingILPobjective}

subject to:

demand constraints: \[ \sum_{k \in N(s)} f_{s,k}^{s,t} - f_{k,s}^{s,t} \leq F_{s,t} \ \ \  \forall s \in \mathcal{S}, t \in \mathcal{T}  \]

flow conservation: \[\sum_{v \in N(u)} f_{u,v}^{s,t} = \sum_{v \in N(u)} f_{v,u}^{s,t} \ \ \  \forall u \not\in {s,t} , s \in \mathcal{S}, t \in \mathcal{T} \]

capacity constraints: \[\sum_{s \in \mathcal{S}} \sum_{t \in \mathcal{T}} f_{u,v}^{s,t} \leq C(u,v) \ \ \  \forall u,v  \]

integrity and non-negativity constraints: \[f_{u,v}^{s,t} \in \mathcal{Z}^+ \cup \{0\} \]


where $N(u)$ is the set of adjacencies to node $u$, $ f_{u,v}^{s,t}$ is the circuit between source $s$ and sink $t$ that flows along the link $(u,v)$, and $C(u,v)$ is the capacity of such link.

We have $|S|x|T|$ demand constraints, $(N-2)x|S|x|T|$ conservation constraints, $|E|$ capacity constraints, $|S|x|T|x|E|$ non-negativity constraints. The worst complexity for the problem occurs when we have a mesh and all nodes are sources and sinks. In this case the number of variables is $N^4$, which means that a network of just 100 nodes has already 10\^8 variables. 
}

Objective function:
$max{\sum^{I}_{i=1} \sum^{J}_{j=1} \sum^{K_{i,j}}_{k=1} f_{k}(s_i,t_j)}$ \label{eq:RoutingILPobjective2}

subject to:
flow constraints: $\sum^{K_{i,j}}_{k=1}f_{k}(s_i,t_j) \leq F_{i,j}   \forall i,j$

flow conservation: $\sum_{v} f(u,v) = 0   \forall u \not\in \mathcal{S}, \mathcal{T}$

capacity constraints: $f (u,v) \leq C(u,v)   \forall u,v $

where $f_{k}(s_i,t_j)$ is the k-th circuit between source $s_i$ and sink $t_j$, $R_{i,j,k}=\{(s_i,n_1), (n_1,n_2), ..., (n_{m_{i,j,k}}, t_j)\}$ is the route taken by the circuit, i.e. the set of links that is passes through, 
$f(u,v) = \sum_{k,i,j : (u,v) \in R_{i,j,k}}f_{k}(s_i,t_j) $ is the total flow along the link between $u$ and $v$, and $C(u,v)$ is the capacity of such link.

This centralized linear program is in fact an integer program, because circuits do not have arbitrary bandwidths, but their capacity is rather a multiple of the minimum circuit granularity. If we write all link capacities as multiples of the circuit granularity, all solutions have to be integer numbers. This type of integer problems is well known to be NP-complete [ref], which makes it non-scaleable. One way of getting an approximate solution is to solve the linear program, which can be solved in polynomial time, and then round down the solution to the closest feasible circuit capacity. {\bf XXXX even this solution is not guaranteed to be close to the real one. As an example, consider $N$ sources on one side of a core link of capacity $C$, and $N$ destinations on the other size. If all source-destination pairs are active, we have $N^2$ flows, all wanting to share the core link. The linear program would yield a solution with a maximum total flow of $f_{LP} = (C/N^2)*N^2$, which approximated would be $f_{approx} = \lfloor{(C/N^2)/c_{g}}\rfloor*c_{g}*N^2$. If the circuit granularity, $c_{g}$, is bigger than the share of the link bandwidth, $C/N^2$, then the approximate solution is a zero flow. By contrast the solution to the integer program is $f_{IP} = \lfloor{C/c_{g}}\rfloor*c_{g}$, where only $\lfloor{C/c_{g}}$ flows out of the $N^2$ are active.}

In our linear program we have a linear target function and a convex feasible region (i.e. the constraint set). We can then apply techniques for convex optimization to find the optimum flow allocation. {\bf need to check}

In convex optimization, one fast way of descending towards the optimal solution is to go along the feasible direction with the steepest gradient of the target function. See chapter 5 in \cite{BertsekasGallager92} for more details.

Even the linear program, with solutions in the domain of real numbers, is very complex, and takes a lot of time to solve for large topologies. Furthermore the flow demands are continuously changing and it takes time for network information to propagate, which makes this centralized approach better suited for network capacity planning and network engineering than for network control.
 
It is impractical to gather information about the current utilization of all links in a large network. Even if the overhead was not prohibitive, the delay in transferring all link utilization to the central node can make the information obsolete. Stale information can cause oscillations in the network, as it represents a long feedback loop in the control mechanism. 


\section{Distributed routing}

In a dynamic and complex environment like the core of the Internet, a distributed routing mechanism is better suited, as it will react to sudden changes faster. The packet switched part of the network already uses such a distributed algorithm, so it is possible to make the routing of circuits and packets compatible, where the two are working on the same objective.

Following the model used in the Internet for intra-domain routing [ref OSPF, IS-IS, RIP], I propose a distributed routing algorithm that works on accurate local information, i.e. the loads of the links that are directly attached to the link, as well as with remote information that is possibly stale, such as the network topology. The routing is done hop-by-hop, meaning that at each hop a new routing decision is taken independently of the decisions that were taken in the upstream nodes.

The routing model consists in following the shortest path to the destination. Notice that this decision making does not take into account the load of the network, but just the network topology. Because of this, the shortest path between the source of the destination might not have enough capacity for the new circuit request, but another path might. In this case the circuit request encounters blocking. One option is to stop the request there, and wait for bandwidth to become available. Another option is to reject the circuit request and inform the source about it. In both cases, by restricting ourselves to the shortest path, we are not taking advantage of the bandwidth that might be available along other secondary paths, and thus the total flow of the network will be smaller than the optimum that the network can support.

For this reason, I propose the use of deflection routing. If the circuit request is blocked along the shortest path, then the circuit is deflected to a neighboring node, which will try its shortest path to the destination, unless it means returning to the node immediately upstream, in which case the circuit request gets deflected again. Deflection routing has been well known since the early days of the Internet, and it was proposed under the name of {\em hot potato} routing in \cite{baran64}.

If no deflection is possible because there is no spare bandwidth in any of the outgoing links, then there are two possibilities; one is to block the circuit request and wait for bandwidth to be liberated before the circuit source gives up, the other alternative is to backtrack the circuit request and try deflecting differently at another node upstream.

Two performance metrics can be used to test the goodness of such distributed mechanism. First, the blocking probability for a given network load indicates what is the probability of not being able to find a path to the destination. This probability should be very small except for high network loads. Second, the ratio between the maximum total flow when there is blocking to the maximum uni-commodity flow indicates how close we are to the maximum flow the network can support.

Deflection routing can show hysteresis and have several modes of operation, which are difficult to leave. For example one mode where we follow the shortest paths, and another where we follow the long paths and we consume more resources, as shown in figure \ref{fig:DeflectionHysteresis}. This hysteresis has been studied in \cite{Kelly90Bistability}. That paper recommends that the dynamic algorithm should favor short paths to avoid consuming extra resources in the network. Long routes make it difficult to select feasible paths for subsequent long-lived circuits, and also consume excess resources that would otherwise be available to the short-lived traffic

\begin{figure}[htp]
{\centering \resizebox*{0.8\columnwidth}{!}{\includegraphics[clip]{fig/DeflectionHysteresis.eps}} \par}
\caption{\label{fig:DeflectionHysteresis}Hysteresis between two stable states when using deflection routing. The configuration using the longest paths uses more resources and has a lower total troughput.}
\end{figure}


Route changes due to congestion or topology changes are more stable in circuit switched networks than in packet switched ones. When a route changes, only the new circuits will take the new path, while the old ones will remain untouched. In essence in circuit switching traffic is rerouted gradually. In contrast, in a packet switched network all traffic to the affected destination will follow the new path. These sudden traffic surges can cause congestion somewhere else in the network, and new route changes in turn. Potentially, traffic can be oscillating between two different routes without ever conversing to one of them. One way of stabilizing the routing of packets is to dampen either the calculation of link costs or the reporting of such cost. Circuit switching inherently dampens the diversion of traffic, thus slowing down changes in link costs. 

Circuit switching can still be unstable, as shown in figures 5.4.1 and 5.4.2 in \cite{BertsekasGallager92}. If circuit life times are very long, route changes will take sometime to take effect, but it will not oscillate. However, if circuit life times are short, and route updates occur infrequently, then we have a situation similar to that of packet switching, where the network reacts very quicking to route changes, becoming unstable. If one takes the circuit duration to the limit and makes it as short as a single packet, then we have a packet switched network.

{\bf the figure is for virtual circuits, but it can be extended for real circuits}

The average circuit duration in the Internet is 10 seconds, as stated in chapter \ref{chap:TCPSwitching}, where as the average packet duration is of 0.4 $\mu s$. If we update the network information every 30 s, as in OSPF {\bf need to check}, then we will need some damping in the cost calculation or reporting, but not as much as with packets. The price to pay for the routing stability is a slow down in the response to sudden network changes.

In TCP Switching, circuits can be rerouted by changing the output channel or port at any node. A new circuit will be created starting at that node, and the old circuit will timeout, as it will stop carrying traffic. Obviously this creates a glitch until the new circuit is created. One can reduce the glitch duration by diverting one packet first, then one has to wait for sometime for the new circuit to be established, aand then one can divert all traffic from the flow to the new circuit. 

Rerouting of existing circuits is needed when there is a link failure or because we want to switch one long-lived flow from a long route to a shorter one. This can reduce the hysteresis effect that was discussed shortly before. Rerouting all existing circuits simultaneously can cause oscillations in the network, and they should be staged out.

Load balancing in packet switching can cause packets to be delivered out of order, and then the destination has to reorder them. Flow control in TCP is very sensitive to out-of-order packets, as they generate duplicate acknowledgements. TCP interprets 3 consecutive duplicate acknowledgements as a congestion signal, and it throttles the throughput of the flow down.

OSPF \cite{OSPF} or IS-IS \cite{ISIS} can be used to broadcast the link costs and to compute the shortest path to all destinations, just like a router inside a packet-switched autonomous system.

This distributed algorithm is a greedy algorithm, in the sense that it always tries to use the shortest path. When being deflected the circuit tries to find another branch of the shortest-path tree that is rooted at the destination as shown in figure \ref{fig:DeflectionOnSPT}

\begin{figure}[htp]
{\centering \resizebox*{0.8\columnwidth}{!}{\includegraphics[clip]{fig/DeflectionOnSPT.eps}} \par}
\caption{\label{fig:DeflectionOnSPT}Distributed algorithm following the shortest-path tree.}
\end{figure}
\subsection{Two methods}
Below, I will describe two methods: one that uses Dijkstra to calculate routes, the other that uses Bellman-Ford to do the same. Dijkstra's algorithm is one that does a computation on the whole network topology at each single node, and so it requires that each node have a complete knowledge of the network. In contrast, Bellman-Ford's algorithm does not require this global knowledge, as the computation is done in a distributed way based on the local knowledge of the resources that are attached to the switches. Although the latter algorithm requires less information to be exchanged, it can lead to stability problems because a lot of trust is put on the computation performed by other switches. One can find more information about these two algorithms in \cite[a book]. 

It should be noted that in a wired environment the network topology does not vary as quickly as the link loads, and so the calculation of the primary and alternate routes can be done off-line, and the result can be kept cached at each of the switches.

\subsubsection {First method: using Dijkstra's algorithm}
The first step is to exchange the link information so that all nodes have the same view of the network topology. Then node $i$ uses the regular Dijkstra's algorithm to calculate all routes from $i$ to all other nodes, $primary_route{i,*}$. It should be noted that we obtain the complete route with its cost for all destinations, $j$.

Now, to calculate an alternate route that is link-disjoint from the primary one, $alternate_route{i,j}$, one needs to remove the links of $primary_route{i,j}$ and apply Dijkstra to calculate the route between $i$ and $j$. It may be possible that no route can be found because $i$ and $j$ became disconnected. In this case, we need to add links in $primary_route{i,j}$ until $i$ and $j$ become connected.

In the deflection algorithm that is described in Section \ref{a section}, there is a hidden cost budget that is used to make sure that the deflected route is not taking many resources from other routes that may be used by other connections. This hidden cost budget can be calculated as the cost of $alternate_route{i,j}$ multiplied by a certain factor, $1.5$.

\subsubsection{Second method: using Bellman-Ford's algorithm}
The first step is to use Bellman-Ford's algorithm to calculate the next hop and the cost of the routes among all node pairs, $primary_route{*,*}$.  The disadvantage of this method is that we do not know the exact route, only the next hop, so it is difficult to calculate the best alternate route to the primary route. The advantage is that less signaling is required, as it is proportional to the diameter of the network rather than to the number of links.

To calculate the alternate route we will use an approximate method. Node $I$ will ask all its neighbors, $n_{k}^{i}$ for their routing tables containing their cost and next hop to each destination $j$. For each destination $j$, node $i$ will then pick among the neighbors $n_{k}^{i}$ that do not have $i$ as its next hop the one with the lowest cost to $j$. That will be the $alternate_route{i,j}$.

If all neighbors have $i$ as the next hop, then we can repeat the process again by asking all neighbors of $i$ for their alternate routes and picking the one with the lowest cost that does have a different next hop than $i$. This process can be repeated until there is an $alternate_route{i,j}$.

As in the previous method, the hidden cost budget can be calculated as the cost of $alternate_route{i,j}$ multiplied by a certain factor; $1.5$ in the experiments.


\section{Routing loops}
One problem with both independent decisions made at each hop, and deflection routing is that loops can occur. Loops are bad, because they take away resources while not making forward progress towards the destination.

Packet switching deals with loops by adding a Time-To-Live (TTL) field that gets decremented at each node. A packet in a routing loop will eventually get its TTL worn out, and then it is discarded. In circuit switching, this cannot be done, because the data path does no processing on the information. However, we can use a similar technique in the control path, and use it when creating the circuits. This TTL in the circuit request will kill those requests that make little or no progress. The problem is that the TTL is slow in detecting loops, as loops will only be caught after they have reserved resources on multiple nodes.

A faster way of detecting the loops is to assign circuit a circuit identifier (ID), which will be remembered whenever we hold resources for a circuit. When a circuit request is received at a node, we just have to check whether that same circuit is already going through the node. 

When we detect a loop we can do two things; one is to splice the circuit, and continue the search where the loop was detected, the other is to backtrack the loop, and to continue the search at the first node upstream that has a link that has not been explored yet.

If so, then we can splice the circuit by releasing the loop that starts and finishes in our node, as shown in figure \ref{fig:CircuitSplicing}. If we were to deflect the routing of the circuit, then we would not use the same outgoing link as before, since it would most probably recreate the loop. As one can see, it is possible that the splicing prevents us from exploring all options, and thus the existing path to the destination is not found. 

By backtracking we are doing a search on a graph without loops, that is a tree. The tree is constructed by eliminating the links that would create a loop during the search.

\begin{figure}[htp]
{\centering \resizebox*{0.8\columnwidth}{!}{\includegraphics[clip]{fig/CircuitSplicing.eps}} \par}
\caption{\label{fig:CircuitSplicing}Splicing of a circuit loop.}
\end{figure}

This circuit ID is a global identifier that includes the packet header fields that are used by the ingress boundary router to map packets to circuits. In our case, it is the source and destination IP addresses. 

The deflection algorithm that I am proposing in effect is doing a depth-first search for a path to the destination on a graph without loops (i.e. a tree, where the source is at the root), as shown in figure \ref{fig:DepthFirstSearch}. The measure used for the depth is the shortest path tree to the destination. This method only uses local knowledge at each node and it will always find a path to the destination, if there is one. In practice, it may not find any existing path because the graph can change in the middle of the search. In this case, paths to the destination exist only temporally, and the circuit does not come to the right node at the right time.

\begin{figure}[htp]
{\centering \resizebox*{0.8\columnwidth}{!}{\includegraphics[clip]{fig/DepthFirstSearch.eps}} \par}
\caption{\label{fig:DepthFirstSearch}Depth-first search on the tree rooted at the source.}
\end{figure}

\subsection{Route field in circuit request}
An alternate way of detecting loops is to use a route field in the header request. As the circuit request moves forward, switches append their ID to the list. When a switch receives a circuit request, if it sees its ID in the request's route field it knows that there is a loop. The advantage of this approach is that the switch does not have to look up local state to determine whether there is a loop. The disadvantage is that it has to parse a route field of varying length before processing the request. Also the circuit request is not of fixed size.

\section{Diversity routing}

As we have seen in chapter \ref{chap:CSvsPS}, IP has a slow failure detection and recovery. The failure detection is often caused by a decoupling between the link layer and the IP layer in a router, by which it takes sometime for the upper layer to get notified of a link failure. This can be solved by having both layers integrated more tightly.

The slow failure recovery is due to the need both to flood the network with the new topology and to recompute routes to the destination, which takes sometime. Because the calculations do not take place at all the nodes at the same time, there are oscillations, and it takes time for the system to converge.

SONET, on the contrary, has a very fast failure recovery because it precomputes a backup path that is used in case of failure of the primary path. Also, because the network is configured in the form of counter-rotating rings, the splicing of the primary path into the backup path is done at the node that detects the failure.

In the case of TCP Switching, I propose using precomputed backup paths that are only used in the case of failure. However, a TCP Switched cloud has a mesh topology that prevents us from doing the splicing at the upstream node of the failure. Instead we have to switch from the primary circuit to the backup circuit in the only point that is common to both circuits, the ingress boundary router. 

The egress is the other node that can be common to the two circuits, but it may also be different if the destination sub-network is multi-homed. If the network is not properly designed, it may happen that the spare capacity between source and destination forces all paths to go through one intermediate node or link. A distributed routing protocol will not know that the only possible path is through that node/link, and it will deflect the backup path towards the source, which eventually will run out of options and the ingress node will notice it. In such a network diversity of routes cannot be obtained. 

One can verify that a network is k-connected (i.e. that there are k node-disjoint paths connecting every pair of nodes) by using Kleitman's algorithm \cite{BertsekasGallager92}. Its complexity is $O(k*N)$, where N is the number of nodes.

Circuits have a version number that is sent along the circuit ID. Of the two active circuits, the lower version number indicates that the circuit is a primary circuit.

Both circuits are routed in a diverse manner, i.e. we try that the two share the minimum amount of elements, ideally none except for the ingress boundary router, and perhaps the egress router, too. When we receive a circuit request with the same circuit ID, but a different version number, we tell the backup path to backtrack, so that it tries to use a different path.

I assume a 1+1 protection mechanism.

In order to speed up the notification of a circuit failure to the ingress boundary router, we should include the IP address of the ingress point in the circuit ID.  

{\bf We have a packet switched control plane}

\section{Denial of Service}
A discussion on how to avoid a denial of service by issuing numerous bogus
circuit requests needs to be done.


\section{Performance study}

If we have a single destination (or a single source), then the solution for the uni-commodity flow problem is also the solution to the multicommodity flow problem. The proposed deflection routing augments the flow from source to destination along an augmenting path, and from the Ford-Fulkerson theorem we know that such method achieves an optimal solution to the unicommodity problem. However, Ford-Fulkerson can be a slow algorithm to find the maximum uni-commodity flow, and other algorithms based on pre-flows, such as the push-relabel, are preferred.

\begin{figure}[htp]
{\centering \resizebox*{0.8\columnwidth}{!}{\includegraphics[clip]{fig/SingleDestinationProblem.eps}} \par}
\caption{\label{fig:SingleDestinationProblem}The multi-commodity flow problem for a single destination can be converted into a uni-commodity problem.}
\end{figure}

If we have multiple sources and destinations, then the solution for the unicommodity flow problem is larger or equal to that of the multi-commodity version. Figure \ref{fig:MultipleDestinationProblem} shows how the uni-commodity has a min cut in the access links, but the bottleneck link in the multi-commodity problem is the backbone link.

This is because we cannot prevent flow from going from source $s_i$ to sink $t_i$ in the uni-commodity problem.

\begin{figure}[htp]
{\centering \resizebox*{0.8\columnwidth}{!}{\includegraphics[clip]{fig/MultipleDestinationProblem.eps}} \par}
\caption{\label{fig:MultipleDestinationProblem}Comparison of the multi-commodity and uni-commodity flow problems for a multiple sources and destinations.}
\end{figure}

\section{Simulation scenario}
From "An approach to alleviate link overload 
as observed on an IP backbone", by Sundar Iyer, Supratik Bhattacharyya, Nina Taft, Christophe Diot [Infocom 2003]:
Simulations were performed using the Mars [15] routing simulator, on the Sprint US backbone network as shown in Figure 10. The network consists of 17 major PoPs. There were a total of 70 backbone routers in our simulations, and the routers within each PoP were connected in a fully meshed topology. The backbone link speeds were set to 2.5Gbit/s. The average propagation delay for inter-PoP links was set to 10ms and 1ms for
intra-PoP links in accordance with measurements done in [16]. Also the processing delay on each router was set to 1ms as reported in [17]. The buffer size on each interface was to set to 32Mb (which is the default size on the Cisco IP backbone routers) and the average packet size used in our simulations was 500 bytes. 

Generating a sound traffic matrix: Unfortunately due to the lack of measurement infrastructure we do not have an accurate model of the traffic matrix i.e. the amount of traffic which originates  in one PoP and is sunk by another PoP. One option to estimate the traffic matrix is to use techniques suggested in previous  work [18][19][20]. These methods rely on SNMP link counts as the only concrete information about the network. However we chose to use gravity models in estimating the traffic  matrix as suggested in [21]. In its simplest form (as specified  in Equation 10 in [21]) the amount of traffic sent from PoP  to PoP  , denoted by  $X_{ij}$ can be specified as: $X_{ij}=F_{i} \alpha_{ij}$

where  $F_{i}$ is amount of traffic generated by PoP   (we obtained by measurements on the access aggregate links for eachPoP), and $\alpha_{ij}$  is a fraction based on the relative capacities $C_I$ and $C_j$ (sum of the capacities of all incoming access aggregate links to a PoP) of the PoPs  $i$ and $j$ . Note that in our simulations we would like to study how the network would perform under varying link utilization. In order that we can proportionately scale the traffic matrix, we define a parameter called 'normalized  load'   on the network. The normalized load for the Sprint network   is defined as: $\lambda_{s} = 1/N \times \sum_{i=1}^{N} F_i/C_j$


\section{General points}

*In a network the maximum flow is determined by the minimum
cut (min cut-max flow theorem) [See handout\#2 from cs363 by Craig Silverstein] 

\begin{itemize}
 \item a method that can be used to determine the max flow is by adding BW along any path (augmenting paths theorem) 
 \item a better method is by adding the max BW along the shortest path (shortest augmenting paths) 
 \item even though there are other methods that are faster, this method works better with the way TCP Switching operates 
\end{itemize}

\section{classification}

\begin{itemize}
 \item Network information is: current vs. stale 
 \begin{itemize}
  \item With current  information we will always find the current shortest path, and by the  shortest agmenting path theorem we will attain the max flow of the  network. 
  \item With stale  information, we will follow an old ``static''; shortest path,  which will run out of BW faster than a dynamic shortest path. 
 \end{itemize}
 \item Routing is: hop-by-hop vs. centralized (source routing) 
 \begin{itemize}
  \item centralized routing  produces no loops 
  \item hop-by-hop routing can  produce loops 
 \end{itemize}
 \item Loops are either: ignored, avoided using TTL or detected during cct creation 
 \begin{itemize}
  \item loops waste BW, and  they never timeout (unless there is a TTL). It is like a memory leak in  WinNT 
  \item with a TTL decrease,  loops eventually timeout, since packets are removed if they loop 
  \item loops can be detected  during the creation of ccts, when a cct request arrives one can check  that no other port has such circuit. Also one can record the nodes that  the cct has visited using a special packet. 
  \item If a loop is detected  the loop can be removed and the other ccts spliced. 
 \end{itemize}
 \item If a flow is blocked, this flow can either: be rerouted, be dropped or be stopped 
 \begin{itemize}
  \item If the cct is blocked  or dropped, the max BW can be the BW of the bottleneck in the old  shortest path 
 \end{itemize}
 \item If a blocked flow is dropped or stopped, the partial cct upstream can either: be cleared immediately or left until it timesout 
 \begin{itemize}
  \item the partial cct will  consume resources. 
  \item In the case ccts are  blocked, they will be queued closer to the source, but hte Q service  policy will not be FIFO. 
 \end{itemize}
\end{itemize}

*How to implement the routing of the flow along the shortest path? 

\begin{itemize}
\item Information can be stale at the ingress, so when routing a flow we might find that the foreseen route is no longer available. 

\item We need to *If a flow gets routed, so that we get back to node that was visited before, we have a loop 

\item This can happen if the different nodes have different information 

\item To detect this when a new flow request arrives, we need to check whether the flow was present before on any of our linecards 

\item We need to eliminate the loop, since it does not do anything. So we splice the original incoming circuit with the outgoing circuit that we will create. 
\end{itemize}

\begin{itemize}
 \item we eliminate the loop by sending an explicit teardown message that will stop when received again by the node that detected the loop. 

\item In this splicing we need to be careful, since we might create a loop, and since we do not have a TTL-decrement in the circuit switches, a packet that got trapped into a circuit will prevent the loop from timing out. 
\end{itemize}

\begin{itemize}

\item One solution is to add a TTL-decrement every time we splice (or perhaps at every circuit switch) 

\item Another solution is to send a special packet that is detected by the control plane that detects whether there is a loop. This packet could be doing the TTL-decrement. 

\item We may inform of this to a monitoring and network management station *it may happen that the shortest path has run out of bandwidth, but the upstream switches still do not know of this, so we still get requests that have to be blocked. 

\item One solution is to reroute the circuit towards the upstream routers, and have the latter figure out that the flow has to be routed in a different direction through the loop detection mechanism. 

\item It may happen that the path going upstream has no spare bandwidth, too, in which case we need to send an explicit prune message to the upstream switch. *Upon the detection of a blocking downstream, (e.g. the flow comes back to us, or an explicit prune message), we need to recalculate the route. 

\item rather than relying on the regular routing tables, we need to recomputed an alternate route, since the routing tables reflect shortest-path routes that were calculated on stale information. 

\item therefore we need an explicit source routing mechanism 

\begin{itemize}
\item it can be a new type of packet 
\end{itemize}

\item it would be good if the packet that came back to us had information about the route that it took so far, that way we could know what route to remove in the calculation of the new route. 
\end{itemize}

*I propose than rather than using the first packet in a flow to create the circuit, that we use a new type of packet that: 
\begin{itemize}

\item encapsulated the first packet in the flow 

\item has a TTL (to prevent/detect loops) 

\item records the route that it follows 

\item has the option of an explicit source route 

\item has other options, such as the requested bandwidth and the timeout value that has to be used. *Additionally I propose two other control messages: 

\item a prune message, that prunes a branch of the shortest-route path 

\item an explicit circuit teardown message, used mainly to close detected loops, but it could also be used to teardown circuits that timed out. 

\begin{itemize}
\item If we use this message to teardown timed-out circuits, we could have a very precise timer at the ingress and very coarse (and long) timers at the core. 
\end{itemize}

TCP Switching *in the boundary router, the TCP Switching functions can all be contained in a line card, whereas the rest of the router is a regular router (there is no change) 

\item The circuit switched card is needed anyways 

\item An implementation where the classification is done in the ingress linecard would be more efficient, but it would require to modify the whole router. 
\end{itemize}


DOS attacks could be easily traced back to individual hosts and squelched,
maybe even automatically. With no global routing table to munge up, it
would be harder to black hole or flood.

Add in the fact that optical sniffing, while not impossible by any means
today, will increasingly become non-trivial as bandwidth increases. Which
is exactly one of the 'problems' they expect optical network to solve.


The current routing protocols in the Internet, OSPF \cite{OSPF} and IS-IS \cite{ISIS}, route the information along the shortest path to the destination. They constrain the load on the network along a small set of shortest paths, even if there are alternate parallel paths with available capacity. This limits the maximum throughput that can be attained from the network, and sometimes it can be well below the optimal maximum throughput \cite{Bertsekas91Optimization}. Intuitively it would be beneficial to spread the load uniformly over several parallel paths of similar cost, reducing the probability of saturating any given link. Both OSPF and IS-IS have been extended to split traffic uniformly among multiple equal weight paths. Multipath routing protocols that divide the load unequally among several alternate paths have been proposed in the past \cite{vutukury01mdva,vutukury99algorithm,zaumen98loopfree}.

Deflection only works if there are other links in the network that are not
overloaded.

Loop detection is easier in CS because we have to maintain local state related to the circuit. 

Deflection routing has been proposed before for telephone networks \cite{kelly91network} and data networks \cite{wang90emergencyExits}

The core of the Internet is so overprovisioned that link utilization in the core of the network is very low \cite{Odlyzko99NetsEmpty,iyer03overload}. For example the Sprint backbone is designed with the goal of keeping teh load level of every link under 50\% in the absence of link failure. The rational behind it is that when a link fails, there should be enough capacity on the backup path as to absorb all the traffic from the failed link. As a result, link overload (load > 50\%) is rare, and when it occurs, 80\% of the time it is caused by link failures. Single link failures contribute to more than 45\% of all failures \cite{iyer03overload}
 

{\bf Notes from Sigcomm}
Tim Griffin \& G Wilfong show in their SIGCOMM 02 paper ("On correctness of IBGP configuration") how having two parallel routing mechanisms, IGP and IBGP, may cause problems in the routing of the packets. The reason is that IBGP decides to send the packet through an egress of the AS, but then IGP (OSPF or IS-IS) routes it through another egress. Some topologies have loops, others have no solution, and others have two or more possible solutions.

S. B. Fredj, T. Bonald, A. Proutiere, G. Regnie, and J. W. Roberts, "Statistical Bandwidth Sharing: A Study of Congestion at Flow Level," in Proceedings of ACM SIGCOMM, Aug. 2001. They show that flow arrivals are Poisson. Other papers: Cleveland SIGMETRICS 01 (for http user flows).

\begin{itemize}

\item [ Guangzhi Li, Jennifer Yates, Dongmei Wang, and Charles Kalmanek, "Control Plane Design for Reliable Optical Networks," to appear in IEEE Communications Magazine.]

One has to make sure that failures in the control plane do not affect circuits that have already been accepted and that are processed by the data plane.

There are tradeoffs between spare capacity requirements, service interruption time and protocol complexity.

For protection/restoration after data plane failures, there are path-based schemes (using an alternate path from source to destination, it is a dedicated end-to-end protection) and link-based schemes (protection on a per-link basis, such as SONET rings). Protection reacts almost immediately and thus requires preallocated resources, whereas restoration relies on dynamic resource reservation, and it may take over an order of magnitude longer to restore the connection.

Path-based schemes can be classified as link-disjoint, node-disjoint or (shared-risk link group) SRLG-disjoint.

I propose using dynamic restoration, having the circuit reestablishment request be deflected until sufficient resources are found. Some of the problems are the lack of predictability and lack of guarantee of successful failure recovery. The advantage is that it does not reserve resources that will not be used unless there is a failure. So it is more bandwidth efficient than any protection mechanism.

\item
To increase the realibility of the network pre-computed backup routes should be available to the router, so that there is no time wasted in doing the calculation on the spot. This could lead to a suboptimal solution, but one that is faster.

\item Routing algorithm goals 
\begin{itemize}

\item Optimal routes
- Calculate and select the best routes - many methods
\item Simplicity
- Functional efficiency with low routing protocol overhead
\item Robust and stable
- Predictable and correct functionality 
in a variable environment (hardware failure, high load, topology changes)
\item Rapid convergence
- Slow route calculations cause loops 
and drops in service
\item Flexibility
- Speed + accuracy to adapt to network changes (bandwidth, delays, queues, traffic levels, etc.)
\end{itemize}

\item A large study demonstrated that up to 80% of all Internet paths could be improved by an alternate routing decision - some by a factor of two or more. Moreover, almost half of this inefficiency could be attributed to excessive propagation delays, rather than congestion, suggesting that it will not be eliminated as bandwidth becomes more plentiful. \ref{ Stefan Savage, Andy Collins, Eric Hoffman, John Snell, and Tom Anderson, "The End-to-end Effects of
Internet Path Selection", In Proceedings of the 1999 ACM SIGCOMM Conference, pages 289-299, Cambridge,
MA, September 1999.



\item In a paper in Sigcomm 01, S. B. Fredj, T. Bonald, A. Proutiere, G. Regnie, and J. W. Roberts, "Statistical Bandwidth Sharing: A Study of Congestion at Flow Level," in Proceedings of ACM SIGCOMM, Aug. 2001. The authors state that flow arrivals are Poisson.

\item Bill Cleveland in SIGMETRICS 01 also has the same result for HTTP flows.

\item 
? BGP statistics and Internet interdomain topology
• "BGP Table Data," http://bgp.potaroo.net/
• "The Skitter Project," http://www.caida.org/tools/measurement/skitter/
• S. Agarwal, L. Subramanian, J. Rexford, and R. H. Katz, "Characterizing the Internet hierarchy from multiple vantage points," IEEE Infocom, 2002, http://www.cs.berkeley.edu/~sagarwal/research/BGP-hierarchy/
? Network evolutionary dynamics
• R. Albert and A.-L. Barabasi, "Statistical mechanics of complex networks," Reviews of Modern Physics 74, 47 (2002), http://www.nd.edu/~networks/PDF/rmp.pdf
• "Study of Self-Organized Networks at Notre Dame," http://www.nd.edu/~networks/
References (contd.)
? Hierarchical routing
• L. Kleinrock and F. Kamoun, "Hierarchical routing for large networks: Performance evaluation and optimization," Computer Networks, vol. 1, pp. 155-174, 1977, http://www.cs.ucla.edu/~lk/LK/Bib/PS/paper071.pdf
• P. Tsuchiya, "The landmark hierarchy: A new hierarchy for routing in very large networks," Computer Commun. Rev., vol 18, no. 4, pp. 43-54, 1988
• J. J. Garcia-Luna-Aceves, "Routing management in very large-scale networks," Future Generation Computer Systems, North-Holland, vol. 4, no. 2, pp. 81-93, 1988
• I. Castineyra, N. Chiappa, and M. Steenstrup, "The Nimrod routing architecture," RFC 1992, August 1996, http://ana-3.lcs.mit.edu/~jnc/nimrod/docs.html
• P. Tsuchiya, "Pip," http://www.watersprings.org/pub/id/draft-tsuchiya-pip-00.ps, http://www.watersprings.org/pub/id/draft-tsuchiya-pip-overview-01.ps
• F. Kastenholz, "ISLAY,"
http://partner.unispherenetworks.com/rrg/draft-irtf-routing-islay-00.txt
References (contd.)
? Control theory and derivatives
• D. Bertsekas, Dynamic Programming and Optimal Control, Athena Scientific, 2000-2001, http://www.athenasc.com/dpbook.html
• D. Bertsekas, Nonlinear Programming, Athena Scientific, 1999, http://www.athenasc.com/nonlinbook.html
• D. Bertsekas and J. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996, http://www.athenasc.com/ndpbook.html
• J. Boyan and M. Littman. "Packet routing in dynamically changing networks: A reinforcement learning approach," Advances in Neural Information Processing Systems, vol. 6, pp. 671-678, 1993, http://www.cs.duke.edu/~mlittman/topics/routing-page.html
• D. Wolpert, K. Tumer, and J. Frank, "Using collective intelligence to route Internet traffic," Advances in Neural Information Processing Systems-11, pp. 952-958, 1998, http://ic.arc.nasa.gov/ic/projects/COIN/
References (contd.)
• Game theory
• R. La and V. Anantharam, "Optimal routing control: Game theoretic approach," IEEE Conference on Decision and Control, 1997, http://citeseer.nj.nec.com/la97optimal.html
• Y. Korilis, A. Lazar,  and A. Orda, "Achieving network optima using Stackelberg routing games," IEEE Transactions on Networking, vol. 5, no. 1, pp. 161-173, 1997, \url{http://comet.columbia.edu/~aurel/papers/networking_games/stackelberg.pdf}
? "Mobile ad-hoc networks (MANET),"
http://www.ietf.org/html.charters/manet-charter.html
• E. Royer and C.-K. Toh, "A review of current routing protocols for ad-hoc mobile wireless networks," IEEE Personal Communications Magazine, pp. 46-55, April 1999, http://alpha.ece.ucsb.edu/~eroyer/txt/review.ps
References (contd.)
? Bio-nets, adaptive routing, application routing, active networks, etc.
• G. Di Caro and M. Dorigo, "An adaptive multi-agent routing algorithm inspired by ants behavior," Proc. PART98 - Fifth Annual Australasian Conference on Parallel and Real-Time Systems, 1998, http://dsp.jpl.nasa.gov/members/payman/swarm/
• "Bio-Networking Architecture," http://netresearch.ics.uci.edu/bionet/, and related works, http://netresearch.ics.uci.edu/bionet/relatedwork/index.html; application/content/peer-to-peer routing, in particular:
• S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Schenker, "A scalable content-addressable network," Proc. of  SIGCOMM, ACM, 2001, http://citeseer.nj.nec.com/ratnasamy01scalable.html
• S. Joseph, "NeuroGrid," http://www.neurogrid.net/
• "Active Networks," http://nms.lcs.mit.edu/darpa-activenet/
References (contd.)
? Packet routing and queuing theories
• A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan, and D. Williamson, "Adversarial queuing theory," Proc. ACM Symp. on Theory of Computing, pp. 376-385, 1996, http://citeseer.nj.nec.com/472505.html
• C. Scheideler and B. Vocking, "From static to dynamic routing: Efficient transformations of store-and-forward protocols," Proc. of the 31st ACM Symp. on Theory of Computing, pp. 215-224, 1999, http://citeseer.nj.nec.com/scheideler99from.html
• B. Awerbuch, P. Berenbrink, and A. Brinkmann, Christian Scheideler, "Simple routing strategies for adversarial systems," Proc. IEEE Symp. on Foundations of Computer Science, 2001, http://citeseer.nj.nec.com/awerbuch01simple.html

References (contd.)
? Physical routing (starting points)
• D. Bertsekas, Network Optimization: Continuous and Discrete Models, Athena Scientific, 1998, http://www.athenasc.com/netbook.html
• Ball-and-string model
• G. J. Minty, "A comment on the shortest route problem," Operations Research, vol. 5, p.724, 1957
• Multicommodity flow problem
• "Multicommodity Problems," http://www.di.unipi.it/di/groups/optimize/Data/MMCF.html
• B. Awerbuch and T. Leighton, "Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks," Proc. ACM Symp. on Theory of Computing, 1994, http://citeseer.nj.nec.com/awerbuch94improved.html
• R. D. McBride, "Advances in solving the multicommodity flow problem," SIAM J. on Opt. 8(4), pp. 947-955, 1998
• T. Larsson and D. Yuan, "An augmented Lagrangian algorithm for large scale multicommodity routing," LiTH-MAT-R-2000-12, Linkopings Universitet, 2000

Off-line Configuration of a MPLS over WDM Network under Time-Varying Offered Traffic Stefano Salsano (University of Rome "Tor Vergata"), Fabio Ricciato (University of Rome "La Sapienza"), Marco Listanti (University of Rome "La Sapienza"), Angelo Belmonte (University of Rome "La Sapienza") 


Performance Analysis of Deflection Routing in Optical Burst-Switched Networks Ching-Fang Hsu (National Tsing Hua University), Te-Lung Liu (National Tsing Hua University), Nen-Fu Huang (National Tsing Hua University) 


\end{itemize}

