Northern Technical University

TECHNICAL ENG. COLLEGE \ MOSUL

Routing
 Northern Technical University
TECHNICAL ENG. COLLEGE \ MOSUL

What is Routing?
• Process of finding a path from a source to every distention in the
network.

• Does a shorter path exists?

• What if a link along the route goes down?

• What if you are on a mobile wireless link.

 Northern Technical University
TECHNICAL ENG. COLLEGE \ MOSUL

Basics
• A routing protocol sets up a routing table in routers.
• A routing table is the source of information that each router uses to
make routing decisions.
• Basic problem: enable network nodes to make local choices that
depend on global topology.
 Northern Technical University
TECHNICAL ENG. COLLEGE \ MOSUL

How do we make correct local decisions? (Without

having a complete global view of the network)
• Each router must know something about global state.

• The global state may be:

• Huge
• Dynamic
• Hard or costly to collect.

• A routing protocol must intelligently summarizes relevant

information.
 Northern Technical University
TECHNICAL ENG. COLLEGE \ MOSUL

Requirements:
• Minimize routing table space
• Fast to lookup
• Less information to exchange

• Minimize number and frequency of control messages

• Overhead

• Use optimal path

 Northern Technical University
TECHNICAL ENG. COLLEGE \ MOSUL

Types
• Static routing
• With static routing, the routing table entries are manually configured.

• Dynamic routing
• With dynamic routing, the route calculation is performed by a routing
protocol.
• A routing protocol implements a distributed algorithm where routers
exchange information to calculate the best possible paths between hosts.
Example of a physical network
How it looks from an IP perspective
Routing tables
Routing tables
• Whenever a host or router needs to transmit an IP datagram, it
performs a lookup in its routing table.
• The lookup uses the IP destination address of the datagram as a key
to search the routing table for a matching entry.
• The output of the routing table lookup is the IP address of a next hop
router or the name of the network interface through which the IP
datagram can be directly delivered.
• A routing table lookup does not modify the routing table.
• Routing tables are modified only by static routing configurations or
by routing protocols.
Routing tables
• The destination address in a routing table can be
• a network prefix,
• a host IP address,
• a loopback address,
• or a default route.
• Routing table entries where the destination address is a network prefix are
called network routes.
• Routing table entries where the destination address is the IP address of a
host are called host routes.
• A routing table can have a default route. This entry is used for the
forwarding decision when no other entry matches the destination IP
address.
• a routing table can have at most one default route.
Routing tables
• The router that is listed as the next hop router for the default route is called the default gateway.
• Routing tables at routers can have many thousand entries and are generally set via dynamic routing
protocols.
• Hosts, on the other end, require only a few routing table entries, which can be configured statically.
• When a router or host performs a lookup in the routing table, it searches for an entry that has the
longest match with the prefix of the destination IP address of the datagram.
• This is referred to as a longest prefix match.
• First the routing table is searched for a match on all 32 bits of the IP destination address.
• If there is no 32-bit prefix match, the routing table is searched for an entry that has a 31-bit prefix
match. Then the routing table is searched for a 30-bit prefix match, and so on.
• If there is no match with a host route or a network route, then the default route is selected
• 0.0.0.0
Two key algorithms for dynamic Routing
• Distant vector algorithm and,

• Link state algorithm.

• Both assume routers knows address of each neighbor.

• Both assume routers knows cost to reach each neighbor.

• Both allow a router to determine global router information.

• By talking to its neighbors.
Distance Vector (Basic idea)

• Nodes tells its neighbors its best estimate of distance to every other
node in the network.

• Nodes receives these distance vectors from its neighbors

• Used to update its notion of minimum distance and,
• best next hop towards each destination.
Distance Vector (Features)

• Distributed

• Adopts to traffic changes and link failures

• Suitable for networks with multiple administrative entities.

 Distance Vector (Routing)

Distance Table
1
6 B C D B A DE( . , . )
5 14 1 A
A 8 2 5 8 7 B
4 9 6 C
1 2 11 4 D
E D
2
 Distance Vector (Routing)
Distance Table

D B A DE( . , . )
• The routing table extracted from the 5 14 1 A
distance table 5 8 7 B
• By picking the smallest entries. 4 9 6 C
2 11 4 D
1
6 B C Routing Table
Next Hop Distance DE( . , . )
A 8 2 Direct 1 A
D 5 B
1
E D D 4 C
2
Direct 2 D
How do we compute and maintain distance
tables?

• Bellman-Ford Algorithm

• Runs at each node

• Determines least cost of path to every other node.

• Keeps track of next node on each least cost path

Algorithm at node X:

• Initialization
• For all adjacent nodes V (columns in distance table)
• Dx ( * , V ) = ∞
• Dx ( V , V ) = C ( X , V )

• Loop:
• Execute distributed topology update procedure

• Keep running loop

Topology update algorithm at node X:

• Wait (until observed link cost to a neighbor Y change or until received

a control message from neighbor W)

• Cost change to neighbor Y

• If ( C (X,Y) changed by ᵟ )
• Go to column (route via) Y and change all entries by ᵟ
• If the change also changes the cost of the least cost path to some node Z , send control
message to neighbor with my new minimum cost to Z.
Shortest path via W for some node Z has
changed

• If ( received a control message from neighbor W)

• Dx ( Z , W ) = C ( X , W ) + d ( W , Z )
• If cost of least cost path to Z has changed, send control message to neighbors
with new minimum cost to Z.
Example:
2
X Y

7 1

Z Y Dx Z X Dy Y X Dz
∞ 2 Y ∞ 2 X ∞ 7 X
7 ∞ Z 1 ∞ Z 1 ∞ Y

Control message with cost d(Z,Y)=1

 Dx(Y,Z)=C(X,Z)+d(Z,Y) = 7+1 =8

Z Y Dx Z X Dy Y X Dz
8 2 Y ∞ 2 X ∞ 7 X
7 ∞ Z 1 ∞ Z 1 ∞ Y

Cont. msg. d(Y,Z)=1

Dx(Z,Y)=C(X,Y)+d(Y,Z) = 2+1 =3

Z Y Dx • By looking at the table of node Y, what does it need to finish?

• It needs to know the cost of reaching node Z via X
8 2 Y • X has to send the direct distance to Z d(X,Z)
7 3 Z • It needs to know the cost of reaching node X via Z
• Z has to send the direct distance to X d(Z,X)
Change of minimum🡪 control message d(X,Z)=3 • The control messages will be sent as needed
• X🡪Z d(X,Z)=7
Z X Dy
• Z🡪X d(Z,X)=7
8 2 X • Dy(Z,X) = C(Y,X)+d(X,Z)=2+7=9
1 9 Z • Dy(X,Z) = C(Y,Z)+d(Z,X)=1+7=8
Dy(X,Z)=C(Y,Z)+d(Z,X)=1+3=4
Dy(Z,X)=C(Y,X)+d(X,Z)=2+3=5

Z X Dy
4 2 X
1 5 Z
Why does it work?
• Each node knows its true cost to its neighbors.

• This information is spread to its neighbors the first time it sends out
its distance vector.

• Eventually, it is incorporated into the routing tables every where in

the network.

• Complexity depending largely on topology and implementation.

DV Routing Problems:

• If link XY fails, and both X and Y set C(X,Y) to infinity and run topology
update algorithm 🡪 two types of problems:
• Slow convergence: the network eventually finds new shortest path but it
takes time.
• Count to infinity
Link State Routing
• Each router knows the entire network topology.

• Computes the shortest path by itself.

• Two key elements:

• Topology dissemination
• Computing shortest routes
Topology dissemination

• A router describes its neighbors with a Link State Packet LSP.

• This information needs to be distributed every where

• Routers store LSPs in an LSP data base
• When receiving a new LSP, forwards the LSP to every interface other than the
incoming one.
Example

LSP Created by A
2 B A
1 D A
5 C A