\section{Routing}

% -----------------------------------------------------------------
\begin{slide}{}

   \begin{sitem}
   \item Forwarding versus Routing
      \begin{sitem}
         \item forwarding: to select an output port based on destination
	       address and routing table
         \item routing: process by which routing table is built
      \end{sitem}   

      \item Network as a Graph

      \pichere{graph_route.eps,height=2in}

      \item Problem:  Find the lowest cost path between any two nodes

      \item Factors:
      \begin{sitem}
         \item Static: topology
         \item Dynamic: load
      \end{sitem}
   \end{sitem}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Distance Vector}

   \begin{sitem}
      \item Each node maintains a set of triples:
      \begin{quote}
      {\tt (Destination, Cost, NextHop)}
      \end{quote}

      \item Each node sends updates to (and receives updates from) its
                directly connected neightbors
      \begin{sitem}
         \item periodically (on the order of several seconds)
         \item whenever its table changes (called {\it triggered} update)
      \end{sitem}

      \item Each update is a list of pairs:
      \begin{quote}
         {\tt (Destination, Cost)}
      \end{quote}

      \item Update local table if receive a ``better'' route
      \begin{sitem}
         \item smaller cost
         \item came from next-hop
      \end{sitem}

      \item Refresh existing routes; delete if they time out
   \end{sitem}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

\begin{verbatim}
void
mergeRoute (Route *new)
{
   int i;

   for (i = 0; i < numRoutes; ++i) 
   {
      if (new->Dest == rt[i].Dest) 
      {
         if (new->Cost + 1 < rt[i].Cost) 
            break;
         else if (new->NextHop == rt[i].NextHop)
            break;
         else
            return;
      }
   rt[i] = *new;
   rt[i].TTL = MAX_TTL;
   ++rt[i].Cost;
   if (i == numRoutes) 
      ++numRoutes;
}
\end{verbatim}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Example}

   \pichere{dvroute.eps,height=3in}

   Routing table at node B

      \begin{center}
      \begin{tabular}{|c|c|c|}
      \hline
      Destination & Cost & NextHop \\ \hline
      A & 1 & A \\ 
      C & 1 & C \\ 
      D & 2 & C \\ 
      E & 2 & A \\ 
      F & 2 & A \\ 
      G & 3 & A \\
      \hline
      \end{tabular}
      \end{center}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Routing Loops}

   \begin{sitem}
      \item Example 1
      \begin{sitem}
         \item F detects that link to G has failed
         \item F sets distance to G to infinity and sends update to A
         \item A sets distance to G to infinity since it uses F to reach G
         \item A receives periodic update from C with 2-hop path to G
         \item A sets distance to G to 3 and sends update to F
         \item F decides it can reach G in 4 hops via A
      \end{sitem}

      \item Example 2
      \begin{sitem}
         \item Link from A to E fails
         \item A advertises distance of infinity to E
         \item B and C advertise a distance of 2 to E
         \item B decides it can reach E in 3 hops; advertises this to A 
         \item A decides it can reach E in 4 hops; advertises this to C
         \item C decides that it can reach E in 5 hops...... 
      \end{sitem} 

      \item Heuristics to break routing loops
      \begin{sitem}
         \item set infinity to 16
         \item split horizon
         \item split horizon with poison reverse
      \end{sitem}
   \end{sitem}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Link State}

   Strategy: Send to all nodes (not just neighbors) information about directly
   connected links (not entire routing table).

   \begin{sitem}
      \item Link State Packet (LSP)
      \begin{sitem}
         \item id of the node that created the LSP
         \item cost of link to each directly connected neighbor
         \item sequence number (SEQNO)
         \item time-to-live (TTL) for this packet
      \end{sitem}

      \item Reliable Flooding
      \begin{sitem}
         \item store most recent LSP from each node
         \item forward LSP to all nodes but one that sent it
         \item generate new LSP periodically; increment SEQNO
         \item start SEQNO at 0 when reboot
         \item decrement TTL of each stored LSP; discard when TTL=0
      \end{sitem}
   \end{sitem}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Route Calculation (in theory)}

   \begin{sitem}
      \item Dijkstra's shortest path algorithm
      \item $N$ denotes set of nodes in the graph
      \item $l(i,j)$ denotes non-negative cost (weight) for edge $(i,j)$
      \item $s \in N$ denotes this node
      \item $M$ denotes the set of nodes incorporated so far
      \item $C(n)$ denotes cost of the path from $s$ to node $n$

\begin{tabbing}
x \= xxx \= xxx \= xxx \= \kill
\> $M = \{s\}$\\
\> {\tt for each} $n$ {\tt in} $N - \{s\}$\\
\>\> $C(n) = l(s,n)$\\
\> {\tt while} $(N \ne M)$\\
\>\> $M = M$ {\tt union} $\{w\}$ {\tt such that} $C(w)$\\
\>\> {\tt is the minimum for all $w$ in} $(N-M)$\\
\>\> {\tt for each $n$ in} $(N-M)$\\
\>\>\> $C(n)$ = {\tt MIN}$(C(n), C(w)+l(w,n))$
\end{tabbing}
   \end{sitem}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Route Calculation (in practice)}

   \begin{sitem}
      \item Forward search algorithm
      \item Each switch maintains two lists:
      \begin{quote}
      {\tt Tentative} and {\tt Confirmed}
      \end{quote}
      \item Each list contains a set of triples:
      \begin{quote}
      {\tt (Destination, Cost, NextHop)}
      \end{quote}
   \end{sitem}

   \pichere{lsroute.eps,height=2.5in}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \begin{enumerate}
      \item Initialized {\tt Confirmed} with entry for me; cost = 0.
      \item For the node just added to {\tt Confirmed} (call it {\tt Next})
            select its LSP.
      \item For each {\tt Neighbor} of {\tt Next}, calculate the {\tt Cost}
            to reach this {\tt Neighbor} as the sum of the cost from me to
            {\tt Next} and from {\tt Next} to {\tt Neighbor}.
      \begin{enumerate}
         \item If {\tt Neighbor} is currently in neither {\tt Confirmed} or
            {\tt Tentative}, add {\tt (Neighbor, Cost, NextHop)} to
            {\tt Tentative}, where {\tt NextHop} is the direction to
            reach {\tt Next}.

         \item If {\tt Neighbor} is currently in {\tt Tentative}  and
            {\tt Cost} is less that current cost for {\tt Neighbor}, then
             replace current entry with {\tt (Neighbor, Cost, NextHop)}, 
             where {\tt NextHop} is the direction to reach {\tt Next}.
      \end{enumerate}
      \item If {\tt Tentative} is empty, stop. Otherwise, pick entry from 
            {\tt Tentative} with the lowest cost, move it to {\tt Confirmed},
            and return to step 2.
   \end{enumerate}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

\begin{center}
\begin{tabular}{ccc}
Step & {\tt Confirmed} & {\tt Tentative}\\
1. & (D,0,-)\\
\\
2. & (D,0,-) & (B,11,B) \\
   &         & (C,2,C)\\
\\
3. & (D,0,-) & (B,11,B)\\
   & (C,2,C)\\
\\
4. & (D,0,-) & (B,5,C)\\
   & (C,2,C) & (A,12,C)\\
\\
5. & (D,0,-) & (A,12,C)\\
   & (C,2,C)\\
   & (B,5,C)\\
\\
6. & (D,0,-) & (A,10,C)\\
   & (C,2,C)\\
   & (B,5,C)\\
\\
7. & (D,0,-)\\
   & (C,2,C)\\
   & (B,5,C)\\
   & (A,10,C)\\
\end{tabular}
\end{center}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Metrics}

   \begin{sitem}
      \item Original ARPANET metric
      \begin{sitem}
         \item measured number of packets enqueued on each link
         \item took neither latency or bandwidth into consideration
      \end{sitem}

      \item New ARPANET metric
      \begin{sitem}
         \item stamp each incoming packet with its arrival time ({\tt AT})
         \item record departure time ({\tt DT})
         \item when link-level ACK arrives, compute
         \begin{quote}
         {\tt Delay = (DT - AT) + Transmit + Latency}
         \end{quote}
         \item if timeout, reset {\tt DT} to departure time for retransmission
         \item link cost = average delay over some time period
      \end{sitem}
   \end{sitem}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

    \begin{sitem}
      \item Problems with ``New'' metric
      \begin{sitem}
         \item under low load, static factors dominated cost; worked OK
         \item under high load, congested links had very hight costs; 
	       packets oscillated between congested and idle links
         \item range of costs too large; prefered path of 126 lightly 
               loaded 56Kbps links to a 1-hop 9.6Kbps path
      \end{sitem}
      \item Revised ARPANET metric
      \begin{sitem}
         \item replaced delay measurement with link utilization
         \item compressed dynamic range

         \begin{sitem}
            \item highly loaded link never has a cost more than 3 times its
                  idle cost
            \item most expensive link only 7 times the cost of the least 
		  expensive
            \item high-speed satellite link more attractive than low-speed 
		  terrestrial link
            \item cost is a function of link utilization only at moderate 
		  to high loads.
         \end{sitem}
      \end{sitem}
   \end{sitem}
\end{slide}


% -----------------------------------------------------------------
\begin{slide}{}

   \pichere{metric.eps,height=4in}

\end{slide}


