
\documentclass[11pt]{article}

\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0.5in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{8.5in}
\setlength{\parindent}{0in}
\setlength{\parskip}{0.1in}


\usepackage{times}  
\usepackage{psfig}  
\usepackage{fancyheadings}  

\pagestyle{fancy}
\cfoot{Routing: \thepage}   

\begin{document}

\title{Least-Cost Routing in Packet-Switched Networks}

\author{Norman Matloff \\
Dept. of Computer Science \\
University of California at Davis}                      

\date{June 4, 1998}

\maketitle


\section{Overview}

The question of {\bf routing} in a packet-switched network concerns
which path a packet will take to get from a given source to a given
destination.

Any individual node in a network will be connected to at least one,
sometimes several, {\bf ports}.  Typically the node will not worry
about the complete path on which a given packet will travel after it
leaves the node.  Instead, the node will simply decide which node the
packet will go to next, i.e. which output port to put the packet on.

Choosing the proper route can make a big difference in the time it
takes a packet to get to its destination.  The program {\bf traceroute}
can be used (as a first approximation, at least) to investigate 
bottlenecks.\footnote{This program is available from the Internet,
say from

ftp://ftp.umiacs.umd.edu/pub/SUGstuff

Note, though, that most of these tools are runnable only via root
privileges.  They do not (as far as I know) present any security
risks, but they use the SOCK\_RAW protocol in TCP/IP, which requires
root access.  If you have a Linux system and a SLIP or PPP account,
you may wish to experiment with them.}  Here is a sample output
from the program:

\begin{verbatim}
heather:NetworkInfo/Tools/TraceRoute% traceroute nbc.com
traceroute to nbc.com (192.35.39.100), 30 hops max, 40 byte packets
 1  ph-254-subnet56.cs.ucdavis.edu (128.120.56.254)  *  0 ms  4 ms
 2  eu2-gw.ucdavis.edu (128.120.66.254)  4 ms  16 ms  8 ms
 3  telcofddi-gw.ucdavis.edu (128.120.128.27)  4 ms  4 ms  4 ms
 4  barrn-gw.ucdavis.edu (128.120.250.1)  4 ms  4 ms  8 ms
 5  paloalto-cr2.bbnplanet.net (131.119.2.37)  55 ms  31 ms  51 ms
 6  paloalto-mci.bbnplanet.net (131.119.0.202)  35 ms  20 ms  16 ms
 7  borderx1-hssi2-0.SanFrancisco.mci.net (204.70.158.101)  12 ms  23 ms  16 ms
 8  core2-fddi-0.SanFrancisco.mci.net (204.70.158.49)  16 ms  16 ms  12 ms
 9  core2.WestOrange.mci.net (204.70.4.185)  78 ms  133 ms  86 ms
10  core1-hssi-4.NewYork.mci.net (204.70.1.97)  82 ms  82 ms  78 ms
11  border2-fddi-0.NewYork.mci.net (204.70.3.18)  86 ms  82 ms  113 ms
12  jvncnet-ges-ds3.NewYork.mci.net (204.70.45.10)  82 ms  109 ms  98 ms
13  130.94.40.252 (130.94.40.252)  86 ms  82 ms  86 ms
14  ge-gateway.jvnc.net (130.94.12.114)  98 ms  98 ms  86 ms
15  peacock.nbc.com (192.35.39.100)  90 ms  90 ms *
\end{verbatim}

Here we see the path taken from my UCD machine to NBC's Internet node,
comprising 15 hops.  The first four hops are to UCD machines, ending up
at UCD's gateway to BARRNET (hop 5); the latter was (at the time I
obtained this output) a network involving a number of sites in the
greater San Francisco Bay region.  Note the hops through MCI machines.
It is now commonplace to go through private networks, as the original
backbone of the Internet, NFSNet, was replaced by private arrangements a
couple of years ago.  The {\bf traceroute} program sends three separate
messages to each hop, reporting the round-trip transit time for each in
milliseconds.  (An asterisk indicates that the program timed-out before
receiving a response from the given node.)

A set of interconnected networks, i.e. an {\bf internet} (as opposed
to {\it the} Internet, a worldwide interconnection of networks),
is viewed as a set of {\bf links}.  These may be point-to-point
links such as phone lines, or simply a LAN through which a routed
message will pass.

We will discuss {\bf least-cost} routing algorithms.  The term ``cost,''
though, is an abstraction which could have various definitions.  We
define a cost according to the goal we have.  If for instance we wish
to find a path from a given source to a given destination which has
the least number of ``hops'' (i.e. least number of links traversed),
then we assign a ``cost'' of 1 to each link.  If we wish to minimize
overall queueing delay, we could define the cost of a link to be the
current length of the queue for that link.  In this case, our routing 
strategy will be {\bf dynamic}, meaning that we will frequently 
update the routes as conditions change.

\section{Routing Tables}

A {\bf router} is a machine that, as its name implies, routes packets through
the Internet.  It may be an ordinary workstation or PC, or it could be a
computer, say produced by Cisco, whose hardware and software are
developed specifically for fast routing.  A router would typically
be attached to two Ethernets, serving as a gateway between them and,
in conjunction with further routers attached to these networks, a
gateway to other Ethernets and eventually all of the Internet.

Say machine X, on an Ethernet connected to the Internet, has gotten a
message ready to send, say to machine Y.  The TCP/IP software will first
put the message in a TCP or UDP packet (typically by calling a socket
function), which will in turn encapsulate the packet in an IP wrapping,
which will in turn have an Ethernet frame wrapped around it.  The system
on X will maintain a {\bf routing table}, showing the addresses of all
routers on this Ethernet.  The software will check its routing table,
and send the packet to a router, say R, on that Ethernet (so the Ethernet
address in this packet will be that of the router).\footnote{Of course,
the node in question may itself be a router, in which case this step is
skipped.} 

When this Ethernet frame passes by R on the Ethernet cable, R will
notice
that this frame belongs to it, and thus will copy it from the cable.
The coding within the Ethernet header in the frame will indicate
that the contents are an IP packet, so the IP driver will be called
(and the Ethernet header, having finished its job, will be removed).
R will notice that the IP address here is not that of R itself, and
thus realize that the packet should be routed.

R will then check to see whether the destination machine, Y, is on any
of the Ethernets to which the router is attached.  If so, the router
will send the packet directly to Y; otherwise, the router will send the
packet to another router on one of the Ethernets to which the router is
attached.  In the latter case, again the choice of router will be made
according to the routing table at that node.

On Unix systems, the command ``netstat -r'' will display the routing
table for that machine.  Here is an example:\footnote{From {\it TCP/IP:
Architecture, Protocols and Implementation}, by Sidnie Feit,
McGraw-Hill, 1993, p.141.}

\begin{verbatim}
Destination       Gateway      Flags    Refcnt  Use    Interface
127.0.0.1         127.0.0.1    UH       1       422    lo0
128.36.16.0       128.36.12.1  UG       0       65     le0
192.35.89.0       128.36.12.5  UG       2       201    le0
default           128.36.12.1  UG       0       0      le0
\end{verbatim}

The first line, for IP address 127.0.0.1, is not a ``real'' IP
address; it is the {\bf loopback} address for testing network
software.

The second line is for a {\bf subnet}, consisting of all nodes with IP
address of the form 128.36.16,x.  The table says that any packet with
destination address in that form should be routed through the router at
128.36.12.1.  The packet will be sent to that router via the Ethernet
card at port le0.\footnote{This is a port in the input/output sense,
i.e.  an I/O/address, not in the sense of TCP/UDP sockets.}  If this
machine had a second Ethernet card, attached to another Ethernet
(e.g. if this machine were itself a router), it would be named port
le1, and so on.

The third line is for the Class C network consisting of all nodes whose
address is of the form 192.35.89.x.  Packets destined for that network
should be routed through the router at 128.36.12.5.

\section{Least-Cost Paths}

The routing tables throughout the Internet attempt to forward packets
only paths which have minimum ``cost,'' where that could be defined in
terms of the bits-per-second ratings of various links, the number of
hops, the estimated queuing times on the links, and so on.

There are two famous classes of algorithms for finding least-cost
paths.  In both cases, we discuss how to find the least-cost path 
from a source s to a destination node n.  Let N be the set of all 
nodes, and let $c(i,j)$ be the ``cost'' (however defined) associated 
with the link from node i to node j, if there is a direct link 
between them.  If there is no link between i and j, set the cost to 
infinity.

Note that both algorithm classes operate on a {\bf distributed} basis.
This means that each node computes its own routing tables, as opposed to
the {\bf centralized} case, where one node computes the tables for all
other nodes.  Centralized routing is considered infeasible for large
networks.

\subsection{Link-State Algorithms}

The name here refers to the fact that the calculation relies on
knowledge of the ``state'' (cost) of all links in the entire network.
A well-known algorithm of this class is that of Dijkstra, used in the
ARPANET and TYMNET II networks.  It works as follows.

Let S be a subset of N; S will initially be equal to $\{ s \}$,
but we will add one node to S in each iteration.  At any
given time, for any node n we will have the least-cost path p(s,n) from 
s to n, among paths which use only nodes within the current S.  
Denote the cost of that path by m(s,n).  The algorithm terminates when 
S = N, and we have the overall least-cost path.

Here is the corresponding pseudocode:

{\samepage
\begin{verbatim}
set S to {s}, m(s,n) to infinity for all n not equal to s
do
   find the node w not in S for which m(s,w) is smallest
   add w to S
   for each n not in S
      if m(s,w)+c(w,n) < m(s,n) then
         set m(s,n) to m(s,w)+c(w,n)
         set p(s,n) to p(s,w) concatenated with the link from w to n
until S = N
\end{verbatim}
}

(In the first iteration, the third line of code will simply find the
w for which c(s,w) is minimum, since the set S will consist only of s
at that time.)

The principle drawback of this class of algorithms is that any given
source must know the entire network topology and all link costs.  These
may change:  For example, a link or node may go down, and if cost is
defined in terms of something like queue length, the cost will change
frequently.  Thus update information must be periodically transmitted
to the entire network, which itself is a problem due to the extra
traffic it generates.

\subsection{Distance Vector Algorithms}

The word ``vector'' in this name stems from the fact that instead of 
directly concerning itself with a full least-cost path to a node n, s 
will simply determine the first step of such a path, i.e. ``which 
direction to go first.''  The word ``distance'' refers to the fact
that the total cost of a path to n is often casually called the
distance between the two nodes.  

The chief advantage of the distance-vector algorithm approach is that s
does not have to know all the c(i,j) values, but rather need know only
c(s,k), for those nodes k which are immediate neighbors of s.  This will
have important practical considerations, as we will see later.

The most famous member of this algorithm class is the Bellman-Ford
algorithm, which works in the following manner.

The algorithm is again iterative.  Any given source s knows only the
costs of the links to its immediate neighbors, plus whatever new
information the neighbors have provided.  To explain the latter, suppose
k is a neighbor of s.  The node s will ask k, ``What is the path to n
which is of least cost, {\bf as far as you know}?''  For whichever
neighbor k reports the least cost (plus the cost of going to k), s will
set its own best path to n to be ``Go first to k, and then follow
directions to n from there.''  Note that the situation will be the same
at k:  It will set its best path to be of the form ``Go first to j, and
then follow directions to n from there.''

To state the algorithm more precisely, retain the notation m( ),
p( ) etc. introduced earlier, and for any nodes s and n, let f(s,n) 
be the ``first step'' from s to n, as with k above.  Here then is the 
algorithm: 

{\samepage
\begin{verbatim}
for all s 
   for all n not equal to s
      if n is an immediate neighbor of s then 
         set f(s,n) to n
         set m(s,n) to c(s,n)
      else
         set f(s,n) to "unknown"
         set m(s,n) to infinity
while (true)
   for all s
      for all neighbors k of s
         send f(s,r) and m(s,r) to k for all r
         receive f(k,r) and m(k,r) from k for all r
      for all n
         for all neighbors k of s
            if c(s,k) + m(k,n) < m(s,n) then
               set f(s,n) to k
               set m(s,n) to c(s,k) + m(k,n)
\end{verbatim}
}

Note that node s will only know the values f(s,n) and m(s,n), for
varying n.  In other words, if we were to represent f and m as
tables, node s would know only its own row in each table.

Let us examine what is happening in the {\bf while} loop.  First,
each pair of neighboring nodes exchanges information about the
best paths known to each node so far.\footnote{Though we have
shown this exchange as occurring at the beginning of an iteration,
in practice the exchange is asynchronous.}  Then each node will
update its best path to a given node if the neighbor's information 
indicates a better one.

Assume for the moment that the link costs do not change, and no nodes
or links go down.  Then after i iterations of this algorithm, each
node will know the best path of i hops or less to any other node.
Thus, this process will converge after at most D iterations, where
D is the {\bf diameter} of the network, i.e. the largest number of 
hops between any two nodes in the network.  

However, we have written the code above so that the iterating in the 
{\bf while} loop continues forever.  It is implemented this way in 
practice, since the link costs may change, and thus routes will need
to be updated.  In the Routing Information Protocol commonly used in
Internet routing, for instance, there is an information exchange
between neighbors once every 30 seconds.\footnote{Optimal paths are 
periodically computed for Dijkstra's algorithm too.  However, in that 
case there are no natural recomputation points within the code, 
whereas in the Bellman-Ford case the natural recomputation point is 
the exchange of information between neighboring nodes.}

The Bellman-Ford algorithm has its drawbacks too.  One problem is
that it reacts slowly to changes.  Say nodes u and v are i hops
apart, and that a link leading out of v changes cost.  This news
will not reach u until i iterations later.

\subsection{Hierarchical Routing}

In large networks, it is infeasible to do routing computations for
all nodes.  Instead, {\bf hierarchical routing} is used.  This means
that the network is broken up into {\bf domains}, and that all nodes
in a domain are treated as identical for routing purposes.  One node
in the domain acts as a representative for all nodes in the domain,
and it will be the only node from the domain to enter the routing 
computations.  Since the overall network will contain far fewer 
domains than nodes, the routing computation is much easier and
quicker.

This setup is natural anyway.  Consider a domain which consists of
a single Ethernet, and on which the node g is the {\bf gateway} to
the outside world.  In other words, g is the only node on this
Ethernet which is physically connected to at least one other network.
Then it is natural to choose g as the ``representative'' mentioned
above, and in fact to set things up so that any packet from other
nodes on this Ethernet which will go to the outside world will have
its routing determined by g.

\subsection{Example:  Open Shortest Path First (OSPF) Routing Protocol}

A routing program runs on an {\bf autonomous system} (AS), meaning an
internet.\footnote{Spelled with `i', not `I', meaning a set of interconnected
networks but not ``the'' entire worldwide Internet.}  The same routing
policy runs on all nodes in the AS.
 
OSPF has become the most popular routing protocol on the Internet
today, offered both in public-domain form and also by virtually every
router vendor.  It uses the link-state approach, on a hierarchical basis.

An AS using OSPF will be divided into {\bf areas}.  An area consists of
a set of networks (say Ethernets), routers and possibly point-to-point
links.  The AS will also have a {\bf backbone} network, called Area 0,
through which all \underline{inter}area traffic will be
routed.\footnote{\underline{Intra}area traffic, by definition, will stay
within the given area.}

Within a given area, all routers know the entire topology and set of
link costs of that area, including links to the backbone.  All routers
within the area compute the Shortest Path First routes between any
pair of nodes within the area.  Thus all routing tables within an area
will be identical.  Whenever a link goes down or conditions
change on a link, that information is sent to all routers in the area,
in packets called {\bf link state advertisements}, so that the routers
can update their routing tables accordingly.\footnote{Actually, a
technique called {\bf flooding} is used to send out the information
concerning the change.  Each node tells all its neighbor about this
news.  Of course, this is overdoing it---a node will often receive
the same message multiple times---but at least the news gets out
quickly, and things are set up so that a node won't send a message
out again after receiving it back from someone else.}  Since the
news of the change is propagated only through the given area, the
update is quick.

Note that any area must have at least one router which is also
part of Area 0.  Since the latter has full information on Area 0
and thus knows which routers in Area 0 are connected to the
destination area, the packet can be properly forwarded to its
destination.

\end{document}


