1 of 39

1

Routing

Distance Vector and Link State Algorithms

krraju.in

2 of 39

Why routing is necessary in switched networks?
What is good routing?
What are different approaches to routing?
What are the routing characteristics and how to achieve them?
Different routing strategies.
Compare and contrast Dijkstra’s and Bellman-Ford algorithms

2

What you’ll learn

Network layer: Network Layer Services, IPV4 Address, Subnetting, Super-netting, Classless addressing, Internet Protocol (IP, ARP, DHCP, ICMP), IPV6 Address format, Routing algorithms:Distance vector, Link state, Network Address Translation (NAT).

Unit-4

krraju.in

3 of 39

Why Routing?

In a large telephone network, when a call is placed, the network must devise a route (path) through the network from calling subscriber to called subscriber that passes through a number of switches and trunks.

3

B

D

C

E

A

F

krraju.in

4 of 39

What is Routing?

The determination of a path that a data unit will traverse from source to destination.

Data unit may be a frame, packet, or a message.

4

B

D

C

E

A

F

krraju.in

5 of 39

Flow Control

Regulation of the rate of data transmission

Objectives

Strike a good compromise between throttling users and keeping average delay per message at a reasonable level.
Maintain fairness for all users in the offered traffic that is prevented from entering the network.

As the routing algorithm is more successful in keeping delay low, the flow control algorithm allows more traffic into the network

5

Flow Control

Routing

Offered Load

Rejected Load

Delay

Throughput

krraju.in

6 of 39

Good routing

to increase throughput for the same value of average delay per packet

under high offered load conditions

to decrease average delay per packet

under low offered load conditions

6

Throughput

Delay

Poor routing

Good routing

krraju.in

7 of 39

Approaches

Static routing:

The route can not be altered depending on current traffic conditions.

Dynamic routing:

Routing decisions are influenced by current traffic conditions.

More flexible:

More alternative routes are available.

More complex:

Architecture does not provide a natural path or set of paths based on hierarchical structure.

7

krraju.in

8 of 39

8

	Static Routing	Dynamic Routing
Path Selection	One preconfigured to destination	Multiple available routes to destination
Route updates	Administrator must reconfigure to make route changes	Algorithms automatically update with preferred route changes
Routing Tables	Smaller routing table with only one entry for each destination	Routers send out entire routing tables to identify route availability
Protocols and Algorithms	Does not use protocols or algorithms for preconfigured route	Distance vector algorithms (RIP, IGRP) and link state algorithms (OSPF, IS-IS) adjust routes
Computation and Bandwidth	Requires less computation and bandwidth	Requires more computation and bandwidth
Security	Better security	Less security
Use Cases	Used in smaller networks with fewer routers and unchanging network architecture	Used in larger networks and in networks that change frequently

krraju.in

9 of 39

Approaches (Circuit switching networks)

Fixed routing:

Single permanent route configured for each source-destination pair

Routes are fixed and may change when topology changes (not so often). No dynamic updates

Alternate routing:

Possible routes to be used are predetermined.
Fixed alternate routing: Only one routing sequence (sequence in which the routes in the set are tried) defined for each source-destination pair.
Dynamic alternate routing: Different set of pre planned routes is used for different time periods, to take advantage of the differing traffic patterns in different time zones and at different times of day.

9

krraju.in

10 of 39

Routing Characteristics

Strategies (Packet switched networks)

Correctness
Simplicity
Robustness
Stability
Fairness
Optimality
Efficiency

Requirements

Efficiency
Resilience

10

krraju.in

11 of 39

Elements of routing techniques

Performance criteria

Number of hops
Cost
Delay
Throughput

Decision time

Packet (datagram)
Session (virtual circuit)

Decision place

Each node (distributed)
Central node (centralized)
Originating node (source)

Network information source

None
Local
Adjacent node
Nodes along route
All nodes

Network information update timing

Continuous
Periodic
Major load changes
Topology change

11

krraju.in

12 of 39

Fixed Routing

Single permanent route is configured for each source-destination pair of nodes in the network.
A central routing matrix is created and stored at network control center.
For each source-destination pair of nodes, the matrix shows the identity of the next node on the route.

12

krraju.in

13 of 39

Routing Table

One routing table is needed for each router
One entry for each destination network

Not for each destination host
Once datagram reaches router attached to destination network, that router can deliver to host

Each entry shows next node on the route to destination

Not whole route

Routing tables may also exist in hosts

If multiple routers attached to network, host needs table saying which to use
If the attached network has single router, then not needed

All traffic must go through that router (called the gateway)

13

krraju.in

14 of 39

Routers and Networks (Sample configuration)

Link costs are at the output of the links
There is no cost of getting data from the network

For example, the cost of the path X-A-F-Y is 1+1+4=6

14

B

D

C

E

A

F

G

H

Net 1

Host X

Net 2

Host Y

Net 3

Net 4

Net 5

10

1

5

2

9

7

3

1

9

1

8

6

2

3

1

4

1

	A	B	C	D	E	F	G	H	X
1	D	-	-	B	D	H	B	G	-
2	D	-	B	-	D	H	-	G	B
3	D	G	-	G	-	H	-	-	B
4	-	D	A	-	-	-	D	G	A
5	F	G	H	F	H	-	H	-	A

krraju.in

15 of 39

Routing Tables

15

krraju.in

16 of 39

Fixed Routing

Advantage:

Simplicity

Disadvantage:

Lack of flexibility
No difference between routing for datagrams and virtual circuits.

It will work well in a reliable network with a stable load.

16

krraju.in

17 of 39

Flooding

No network information required
Packet sent by node to every neighbor.
An incoming packet is retransmitted on all outgoing links except incoming link.
Eventually a number of copies will arrive at destination
Each packet is uniquely numbered so duplicates can be discarded at destination

17

B

D

C

E

A

F

krraju.in

18 of 39

Flooding

18

krraju.in

19 of 39

Flooding

Advantages:

Highly robust: All possible routes are tried.

At least one packet will use minimum hop count route.

All nodes are visited.

Disadvantages:

High traffic load: Directly proportional to network connectivity.

Applications:

Military networks that are subject to extensive damage.
To set up the route for a virtual circuit.

At Least one copy of the packet uses a minimum hop route.

For sending emergency messages and to distribute useful information (e.g., routing information)

19

krraju.in

20 of 39

Selective Flooding

In this the routers do not send every incoming packet out on every line
Send only on those lines that are going approximately in the right direction.
Reduced traffic load than flooding.

20

B

D

C

E

A

F

krraju.in

21 of 39

Random Routing

Selects only one outgoing link randomly, excluding the input link.

The choosing of outgoing link may be in a round robin fashion or probability assigned to each link.

Advantage:

It requires the use of no network information.

Disadvantage:

Actual route may not be the least cost route nor the minimum-hop route.

Thus, the network must carry a higher than optimum traffic load, although not as high as for flooding.

21

B

D

C

E

A

F

B

D

C

E

A

F

krraju.in

22 of 39

Adaptive Routing

Routing decisions change as conditions on the network change.

Conditions that influence routing decisions:

Failure:

When node or link fails, it can no longer be used as part of a route.

Congestion:

When a particular portion of the network is heavily congested, it is desirable to route packets around rather than through the area of congestion.

22

krraju.in

23 of 39

Adaptive Routing

Classified on the basis of information source:

Local,
Adjacent nodes,
All nodes

Isolated adaptive
Distributed adaptive

Advantages:

Can improve performance, as seen by the network user.
Can aid in congestion control.
Because this strategy tends to balance loads, it can delay the onset of severe congestion.

23

krraju.in

24 of 39

Adaptive Routing

Disadvantages:

More complex routing decision

processing burden on network nodes increases.

Depend on the status information collected at one place but used at another.

Trade Off: Quality of information vs Amount of overhead.

An adaptive strategy may react

too quickly, causing congestion producing oscillation,
too slowly, being irrelevant.

24

krraju.in

25 of 39

Routing Algorithm

Given a set of nodes, with links connecting the nodes, a routing algorithm finds a least cost path from source to destination.

Responsible for deciding which output line an incoming packet should be transmitted on.

Non-adaptive (Static Routing)

Do not base their routing decisions on measurements or estimates of the current traffic and topology.

Adaptive (Dynamic Routing)

Change their routing decisions to reflect changes in the topology, and usually the traffic as well.

25

krraju.in

26 of 39

Routing Algorithms

Load sensitive

Link costs vary dynamically to reflect the current level of congestion in the underlying link.
If a high cost is associated with a congested link, algorithm will tend to choose routes around the congested link

e.g., Early ARPAnet routing algorithms

Load insensitive

Link’s cost does not explicitly reflect its current level of congestion.

e.g., Today’s Internet routing algorithms: RIP, OSPF and BGP.

26

krraju.in

27 of 39

Routing Algorithms

Global (centralized)

Uses complete information about connectivity and link costs about the network to calculate the least cost path.

It can run at one site or replicated at multiple sites
E.g., Link-state (LS) algorithm (Dijkstra's)

Decentralized

Least cost path is calculated in an iterative distributed manner.

No node has complete information about the costs of all network links. Instead, each node begins with only the costs of its own directly attached links.
E.g., Distance Vector (DV) algorithm (Bellman-Ford)

27

krraju.in

28 of 39

Link State Algorithm

A dynamic routing algorithm (Dijkstra's algorithm) used to find the shortest path from one node to every other node in the network.

Each router shares knowledge of its neighbors with every other router in the network through flooding.

Information sharing takes place only whenever there is a change.

Convergence occurs faster than distance vector.

Link state establishes a neighbor relationship with directly connected peers and shares routing information with its neighbors only when there are changes in the network topology.

28

krraju.in

29 of 39

Distance Vector Algorithm

An asynchronous algorithm in which node x sends the copy of its distance vector to all its neighbors.
When node x receives the new distance vector from one of its neighboring vector, v, it saves the distance vector of v
Uses the Bellman-Ford equation to update its own distance vector.

29

krraju.in

30 of 39

Least Cost Path

30

Routing decision is based on some form of least cost criterion to compute optimal routes.

If the criterion is to minimize the number of hops, each link has a value of 1
Link value is

inversely proportional to the link capacity.
proportional to the current load on the link

Examples:

Dijkstra’s algorithm
Bellman-Ford algorithm

krraju.in

31 of 39

Dijkstra’s Algorithm

31

N = set of nodes in the network

s = source node

T = set of nodes so far incorporated by the algorithm

w(i,j) = link cost from node i to node j

w(i,i) = 0

w(i,j) = ∞ if the two nodes are not directly connected

w(i,j) ≥ 0 if the two nodes are directly connected

L(n) = cost of the least cost path from node s to node n that is currently known to the algorithm.

At termination, this is the cost of the least cost path in the graph from s to n

krraju.in

32 of 39

Dijkstra’s Algorithm Contd..

32

[Initialization]

T = {s} (i.e., set of nodes so far incorporated consists of only the source node)

L(n) = w(s,n) for n ≠ s (i.e., the initial path costs to neighboring nodes are simply the link costs)

2. [Get Next Node]

Find, x, the neighbouring node not in T that has the least cost path from node s and incorporate that node into T. Also incorporate the edge that is incident on that node and a node in T that contributes to the path.
Add x to T; add to T the edge that is incident on x and that contributes the least cost component to L(x), i.e., last hop in the path

krraju.in

33 of 39

Dijkstra’s Algorithm Contd..

33

3. [Update Least-Cost Paths]

L(n) = min [L(n), L(x)+w(x,n) for all n ∉ T (If the latter term is the minimum, the path from s to n is now the path from s to x concatenated with the edge from x to n)

Iteration:T	L(B):Path	L(C):Path	L(D):Path	L(E):Path	L(F):Path	Comments
1: [A]	1:A-B	∞:---	2:A-D	∞:---	∞:---
2: [A,B]	1:A-B	2:A-B-C	2:A-D	∞:---	∞:---
3: [A,B,D]	1:A-B	2:A-B-C	2:A-D	4:A-D-E	∞:---	3:A-D-C: Didn’t make it
4: [A,B,D,C]	1:A-B	2:A-B-C	2:A-D	3:A-B-C-E	∞:---	A-D-E: too long
5:[A,B,D,C,E]	1:A-B	2:A-B-C	2:A-D	3:A-B-C-E	6:A-B-C-E-F
6:[A,B,D,C,E,F]	1:A-B	2:A-B-C	2:A-D	3:A-B-C-E	6:A-B-C-E-F	Stop

A

B

C

E

D

F

1

2

3

1

2

krraju.in

34 of 39

Dijkstra’s Algorithm Contd..

34

Iteration 2

A

B

1

Iteration 3

A

B

D

1

2

Iteration 4

A

B

C

D

1

2

1

Iteration 5

A

B

C

E

D

1

2

1

Iteration 6

A

B

C

E

D

F

1

2

3

1

Iteration 1

A

B

C

E

D

F

1

2

3

1

2

krraju.in

35 of 39

Bellman-Ford Algorithm

35

s = source node

T = set of nodes so far incorporated by the algorithm

w(i,j) = link cost from node i to node j

w(i,i) = 0

w(i,j) = ∞ if the two nodes are not directly connected

w(i,j) ≥ 0 if the two nodes are directly connected

h = maximum number of links in a path at the current stage of the algorithm

Lh(n) = cost of the least cost path from node s to node n under the constraint of no more than h links.

krraju.in

36 of 39

Bellman-Ford Algorithm Contd..

36

h	L(B):Path	L(C):Path	L(D):Path	L(E):Path	L(F):Path
0	∞:---	∞:---	∞:---	∞:---	∞:---
1	1:A-B	∞:---	2:A-D	∞:---	∞:---
2	1:A-B	2:A-B-C	2:A-D	4:A-D-E	∞:---
3	1:A-B	2:A-B-C	2:A-D	3:A-B-C-E	7:A-D-E-F
4	1:A-B	2:A-B-C	2:A-D	3:A-B-C-E	6:A-B-C-E-F
5	1:A-B	2:A-B-C	2:A-D	3:A-B-C-E	6:A-B-C-E-F

A

B

C

E

D

F

1

2

3

1

2

krraju.in

37 of 39

Bellman-Ford Algorithm Contd..

37

h=0

A

B

C

E

D

F

1

2

3

1

2

h=1

A

B

C

E

D

F

1

2

3

1

2

h=2

A

B

C

E

D

F

1

2

3

1

2

h=3

A

B

C

E

D

F

1

2

3

1

2

h=4

A

B

C

E

D

F

1

2

3

1

2

h=5

A

B

C

E

D

F

1

2

3

1

2

krraju.in

38 of 39

Recap

38

krraju.in

39 of 39

Video Links

39

krraju.in