Routing Algorithms

 The main function of network layer is routing packets from the source machine to the
destination machine.
 The algorithms that choose the routes and the data structures that they use are a major area of
network layer design.
 The routing algorithm is that part of the network layer software responsible for deciding which
output line an incoming packet should be transmitted on.
 There are two processes inside router:
1. One of them handles each packet as it arrives, looking up the outgoing line to
use for it in the routing table. This process is forwarding.
2. The other process is responsible for filling in and updating the routing tables.
That is where the routing algorithm comes into play. This process is routing.
 When new connections are established, certain properties are desirable in a routing algorithm:
1) Correctness
2) Simplicity
3) Robustness
4) Stability
5) Fairness
6) Optimality
 Routing algorithms can be grouped into two major classes:
1) Nonadaptive
2) Adaptive
 Nonadaptive algorithm do not base their routing decisions on measurements or estimates of
the current traffic and topology. This procedure is sometimes called static routing.
 Adaptive algorithm change their routing decisions to reflect changes in the topology, and
usually the traffic as well.

The Optimality Principle

 One can make a general statement about optimal routes without regard to network topology or
traffic.
 This statement is known as the optimality principle.
 It states that if router J is on the optimal path from router I to router K, then the optimal path
from J to K also falls along the same route.
 As a direct consequence of the optimality principle, we can see that the set of optimal routes
from all sources to a given destination form a tree rooted at the destination.
 Such a tree is called a sink tree
 The goal of all routing algorithms is to discover and use the sink trees for all routers
 (a) A subnet. (b) A sink tree for router B.

Shortest Path Routing

 The idea is to build a graph of the subnet, with each node of the graph representing a router and
each arc of the graph representing a communication line or link.
 To choose a route between a given pair of routers, the algorithm just finds the shortest path
between them on the graph.
 Many other metrics besides hops and physical distance are also possible.
 For example, each arc could be labeled with the mean queuing and transmission delay for some
standard test packet as determined by hourly test runs.
 With this graph labeling, the shortest path is the fastest path rather than the path with the
fewest arcs or kilometers.
 In the general case, the labels on the arcs could be computed as a function of the distance,
bandwidth, average traffic, communication cost, mean queue length, measured delay, and other
factors
 By changing the weighting function, the algorithm would then compute the “shortest” path
measured according to any one of a number of criteria or to a combination of criteria.

The first five steps used in computing the shortest path from A to D. The arrows indicate the working
node.
Flooding

 Another static algorithm is flooding, in which every incoming packet is sent out on every
outgoing line except the one it arrived on.
 Flooding obviously generates vast numbers of duplicate packets, in fact, an infinite number
unless some measures are taken to damp the process.
 One such measure is to have a hop counter contained in the header of each packet, which is
decremented at each hop, with the packet being discarded when the counter reaches zero.
 Ideally, the hop counter should be initialized to the length of the path from source to
destination.
 Selective flooding , the routers do not send every incoming packet out on every line, only on
those lines that are going approximately in the right direction.
 Flooding is not practical in most applications.

Distance Vector Routing

 Distance Vector Routing is dynamic routing algorithm.

 Distance Vector Routing algorithms operate by having each router maintain a table (i.e., a
vector) giving the best known distance to each destination and which line to use to get there.
 These tables are updated by exchanging information with the neighbors.
 As an example, assume that delay is used as a metric and that the router knows the delay to
each of its neighbors.
 Once every T msec each router sends to each neighbor a list of its estimated delays to each
destination.
 It also receives a similar list from each neighbor.

The Count-to-Infinity Problem

 Slow Convergence to the correct answer.

 Good news Propagate fast
 Bad news Propagate slowly:
 The core of the problem is that when X tells Y that I has a path somewhere, Y has no
way of knowing whether it itself is on the path.

Link State Routing

 Two primary problems caused distance vector routing’s demise.

1. First, since the delay metric was queue length, it did not take line bandwidth into account
when choosing routes.
2. Second, the algorithm often took too long to converge (the count-to-infinity problem)
 Link State Routing is also dynamic routing algorithm.
  Each router must do the following:
1) Discover its neighbors, learn their network address.
2) Measure the delay or cost to each of its neighbors.
3) Construct a packet telling all it has just learned.
4) Send this packet to all other routers.
5) Compute the shortest path to every other router

 Complete topology and all delays are experimentally measured and distributed to every router.
 Dijkstra’s algorithm can be run to find the shortest path to every other router.

Learning about the Neighbors

 “HELLO” packed send on each point-to-point line from a booted router.

 Router on the other end must reply by sending its globally unique “name”.
 Example of routers connected by a LAN.

(a) Nine routers and a LAN. (b) A graph model of (a).

 When two or more routers are connected by a LAN, the situation is slightly more complicated.
 LAN to which three routers, A, C, and F, are directly connected.
 Each of these routers is connected to one or more additional routers.
 One way to model the LAN is to consider it as a node itself. Fig(b).
 Here we have introduced a new, artificial node, N, to which A, C, and F are connected.
 The fact that it is possible to go from A to C on the LAN is represented by the path ANC here.

Measuring Line Cost

 It is required by the Link State Routing algorithm that each router not have a reasonable
estimate of the delay/cost to each of its neighbors.
 Send “ECHO” packet (ping) that the other side is required to send back immediately.
1. Measure Round Trip time; Divide by 2 to get an estimate.
2. More accurate estimate by repeating the process several times and by averaging
estimates.
 3. Assumes symmetric delay.
 Channel Load Issue when Measuring Delay
 To factor the load in: round trip timer must be started when the ECHO packed is
queued.
 To ignore the load: round trip timer must be started when ECHO packed reaches front
of the queue.

Building Link State Packets

 Packet Format:
 Identity of Sender
 Sequence Number
 Age
 List of Neighbors
 Corresponding Delay

(a) A subnet. (b) The link state packets for this subnet.

 Building the link state packets is easy.

 The hard part is determining when to build them.
Distributing the Link State Packets

 Distributing Link State Packets Reliably is tricky:

 As the packets are distributed and installed, the routers getting the first ones will change
their routes before other routers in the network update their routing tables.

 Different Routers may be using different versions of the topology (inconsistencies,

loops, unreachable machines, etc.)
 Basic Algorithm: Flooding
 Sequence Number (incremented for each new packet sent) is used to keep the flood in
check.
 Routers keep track of all the source router packets they have been sent to.
 New link state packets is checked against the track list:
 1. If new/unseen (based on the sequence number) then it is broadcasted to all
neighboring routers with exception of the sender.
2. If duplicate, it is disregarded.
3. If sequence number is lower than the highest one in the track list, it is rejected.
 Problems with basic algorithm:
1. Sequence Number wrap around.
 Make a long precision number (e.g., 32-bit)
2. Crash of a router: losing track of sequence number.
3. Corruption of sequence number.
 Solution: Include Age of each packet.
 Decrement this value once per second.
 When zero, this state information is disregarded.
 Normally a new packed is send every 10 sec.
 Router information times out when:
1. Router is down, or
2. A Number of (e.g., 6) consecutive packets have been lost.
Computing the New Routes

 Once a router has accumulated a full set of link state packets, it can construct the entire subnet
graph because every link is represented.
 Every link is, in fact, represented twice, once for each direction.

Hierarchical Routing

 Large Networks:
 Proportionally large routing tables are required for each router
 More CPU time is needed to scan them
 More bandwidth is needed to send status reports.
 At certain point network may grow so large where it is no longer feasible for every
router to have an entry for every other router.
 Solution: Routing has to be done hierarchically.
 Routers divided in Regions (as in telephone network):
 Each router knows how to route packets to destinations within its own region.
 However, router does not have any information regarding the topology of the network
of other regions.
 When different networks are interconnected they are regarded as a separate region in order to
free the routers in one network from having to know the topological structure of the other
ones.
 Huge networks will require more than two-level hierarchy.
 How many hierarchical levels are optimal.
 Kamoun and Kleinrock (1979): optimal number for an N router subnet is ln(N), requiring total
of e*ln(N) entries per router.
Broadcast Routing

 Sending a packed to all destinations simultaneously is called Broadcasting.

 Direct Method: Source sends a distinct packet to each destination routers in the subnet:
1. Wasteful of the bandwidth.
2. It requires source to have a list of all destinations.
3. In practice this may be the only feasible solution.
 Flooding:
1. Ordinarily ill suited for point-to-point communication:
 Generates to many packets, and
 Consumes to much bandwidth.
 Multi-destination Routing
1. Each packets contains:
 A list of designations, or
 A bit map indicating the desired destinations.
2. When packet arrives at a router:
 The router checks all the destinations to determine the set of output lines
that will be needed.
 Generates a new copy of the packed for each output line to be used and
includes in each packet only those destinations that are to use the line.
 After a sufficient number of hops, each packed will carry only one
destination and can be treated as normal packet.
3. Multi-destination routing is like separately addressed packets, except that when
several packets must follow the same rout, one of them pays full fare and the
rest ride free.
 Spanning Tree:
 It is a subset of the subnet that includes all routers but contains no loops.
 Each router knows which of its lines belong to the spanning tree, it can copy an
incoming broadcast packet onto all the spanning tree lines except the one it arrived on.
1. Makes excellent use of bandwidth (generates absolute minimum number of
packets necessary to do the job)
2. Must have knowledge of some spanning tree for the method to be applicable.
 Information available in some instances (e.g., link state routing)
 Information not available (e.g., distance vector routing)
 Reverse Path Forwarding:
 Router checks if the broadcast packet arrived on the line that is normally used for
sending packets to the source of the broadcast.
 If so, there is excellent chance that the broadcast packet itself followed the best route
from the router and is therefore the first copy to arrive at the router. The router forwards
copies of it onto all lines except the one it arrived on.
  If the broadcast packet arrived on a line other than the preferred one for reaching the
source, the packet is discarded as a likely duplicate.
 Advantages:
1. Efficient and easy to implement Algorithm
2. It does not require routers to know about spanning trees.
3. Does not have the overhead of destination list or bit map in each broadcast
packet (as multi-destination addressing).
4. It does not require any special mechanism to stop the process as flooding does

Multicast Routing

 Application that require separate processes (i.e., each from separate location) access and ability
to work on the same data.
 Small group can use point-to-point messaging to accomplish this task.
 Broadcasting can be used but communicating with 1000 “interested” machines out of
million-node network is inefficient.
 Need a mechanism that would send messages to well-defined groups that are numerically large
in size but small compared to the network as a whole.
 Sending a message to a such a group is called multicasting.
 Corresponding routing algorithm is called multicast routing.
 Requirements:
 Create and Destroy Groups
 Nodes should be able to Join and Leave Groups, etc.
 Group Management.
 When a process joins a group it informs its host.
 Routers must know which of their hosts belong to which group.
 Host must inform their routers about changes in group membership, or
 Routers must query their hosts periodically.
 Information shared with Neighboring Routers (propagation of information through the
subnet).
Tree Pruning

 Link State Routing – each router is aware of the complete topology, including which hosts
belong to which groups.
 Pruning starting from leaf-node up toward root node.
 Distance Vector Routing – Basic pruning algorithm is based on reverse path forwarding.
 Router with no hosts interested in a particular group and no connections to other routers
responds with PRUNE message to a multicast message.
 Also when a router with no group members among its hosts receives a multicast
message it too will respond with a PRUNE message effectively recursively pruning the
subnet.
 Potential Problem is that it scales poorly to large networks.
  Core-Based Trees – an alternative algorithm:
 Uses one spanning tree per group,
 Root (core) node near the middle of the group.
 Host sends multicast message to core node; which in turn sends the message along the
spanning tree.
 Tree will not be optimal for every source,
 Reduction is storage from m trees to one tree per group.

Routing for Mobile Hosts

 Increasing number of users of Portable Computers and Personal Computer Devices. They
require access to:
 E-mail
 File System, etc.
 In order to route a packet to a mobile host, the network first has to find it.
 World Model of communication network:
 WAN consisting of routers and hosts,
 LAN’s connected to WAN, and
 MAN’s connected to WAN.

 Stationary Hosts - Hosts that never move.

 Migratory Hosts - Stationary hosts who move from one fixed site to another from time to time
but use the network only when they are physically connected to it.
 Roaming Hosts - Need to maintain their connections as they move around.
 Mobile Hosts - Migratory and Roaming Hosts – that is all host that are away from home and
still want to be connected.
 All hosts are assumed to have:
 A permanent home location, and
 A permanent home address:
 Used to determine their home location (analogous to telephone number; e.g., 1-
212-555-1212).
  According to the sketch in previous slide world is divided up (geographically) into small units
– areas.
 Areas are typically LANs or wireless cells.
 Each area has one or more
 Foreign agents:
o Processes that keep track of all mobile hosts visiting the area.
 Home agent:
o Keeps track of hosts whose home is in the area, but who are currently
visiting another area.

 REGISTRATION with Foreign Agent:

When a new host enters an area, either by connecting to it (e.g., plugging into LAN), or
wandering into the cell it must register itself with the foreign agent of that area.
 Registration Procedure
1. Each foreign agent broadcast a packet announcing its existence and address.
2. The mobile host registers with the foreign agent:
 Gives its home address,
 Current data link layer address, and
 Some security information.
3. The foreign agent contact the mobile host’s home agent and informs it about a
mobile host in his area. This message contains:
 The foreign agent’s network address,
 Security information
4. The home agent authenticates security information containing:
 Timestamp (to prove that it was generated within the past few seconds), etc.
 Acknowledges foreign agent by indicating to proceed if everything checks
out.
5. Foreign agent registers and informs the mobile [Link] out when done
(typically mobile hosts just turn-off their computers).

Packet Routing for Mobile Hosts

 Example: Sender wants to send a packet to a host in New York.

 Home agent does:
Routing in Ad Hoc Networks

 Ad Hoc networks refers to the extreme case of mobility where not only the hosts are mobile
but routers as well. Examples:
1. Military vehicles on a battlefield with no existing infrastructure.
2. A fleet of ships at sea.
3. Emergency workers at en earthquake that destroyed the infrastructure.
4. A gathering of people with notebook computers in an area lacking 802.11 (IEEE
Wireless LAN protocol).
 Each node consists of a router and a host – usually on the same computer.
 Networks of neighboring nodes are called ad hoc networks or MANETs (Mobile Ad hoc
NETworks).
 Ad hoc On-demand Distance Vector routing (AODV) Algorithm
 AODV takes into account limited bandwidth and low battery life of devices.
 It is a on-demand algorithm; that is it determines a route to some destination only when
there is a demand to send a packed to a destination.
 Route Discovery
 Ad-hoc network can be described by a graph of the nodes (routers + hosts).
 Two nodes are connected, if they can communicate directly using their radios.
 Scenario: A wants to send a packet to node I.
 To locate an unknown node (I), source node A constructs a special ROUTE
REQUEST packet and broadcasts it.
(a) Range of A's broadcast. (b) After B and D have received A's broadcast. (c) After C, F, and G have
received A's broadcast. (d) After E, H, and I have received A's broadcast.

 Format of ROUTE REQUEST PACKET:

 Source and Destinations Address (typically IP address).

 Request ID – local counter maintained separately by each node and incremented each
time a ROUTE REQUEST is broadcast.
 Source Address and Request ID allow nodes to discard any duplicate packets they may
receive.
 Sequence Counters – Each node also maintains a second sequence counter incremented
whenever a ROUTE REQUEST is sent . It is used to tell new routes form old routes.
 Hop Count – keeps track of how many hops the packet has made.

 Format of ROUTE REPLY PACKET:

 The Source address, Destination address, and Hop count are copied from the incoming
request, but the Destination sequence number taken from its counter in memory.
 The Hop count field is set to 0.
 The Lifetime field controls how long the route is valid.

 Route Maintenance

 In Ad-hoc networks the nodes can move or can be switched off.

 For example, Each node broadcasts a Hello message periodically. Each neighbor is
expected to respond to it.
 If no response is forthcoming, the broadcaster knows that that neighbor has moved
out of range and is no longer connected to it.
 Similarly, if it tries to send a packet to a neighbor that does not respond, it learns
that the neighbor is no longer available.