04-network Layer-03 By Apcoms

CPS 422 Computer Networks

Flooding ‰A static routing algorithm ‰Every incoming packet is sent out on every outgoing line except the one it arrived on ‰Generates vast numbers of duplicate packets ‰Some measure has to be taken to damp the process ‰Hop counts in the packet is one way of reducing the number of duplicate packets generation ‰At every hop the hop count is decremented and the packet forwarded only if hop count > 0 ‰Value of hop count determines the diameter of flooding

NETWORK LAYER

Faisal Amjad CPS 422

Flooding

Faisal Amjad CPS 422

Flooding

‰Alternative technique to contain the flooding is to keep track of packets already flooded ‰Sequence numbers used for this purpose ‰One method is to keep a list of all seen packets ‰Requires very large lists ‰Another method is to keep one counter with value ‘k’ representing all packets with sequence numbers <= k ‰This will require only one comparison for each incoming packet ‰If its sequence number is > k flood it otherwise discard it

‰Flooding is not practical in most applications ‰Due to its robustness, it has some uses ‰Military applications in which a number of routers may be blown to bits ‰Distributed applications may require concurrent updation of all databases ‰As a metric against which other routing protocols can be compared, after all among all the routes flooding takes it also takes the shortest path and hence will have minimum delay (ignoring all the overhead generated by the flooding process)

Faisal Amjad CPS 422

Dynamic Routing Algorithms

Faisal Amjad CPS 422

Distance Vector Routing

‰Modern computer Networks generally use dynamic routing algorithms rather than static ones ‰As studied earlier, dynamic routing algorithms base their routing decisions on current network conditions ‰Most popular dynamic routing algorithms are o Distance vector (DV) routing and o Link State (LS) routing

Faisal Amjad CPS 422

‰Also called distributed ‘Bellman-Ford’ routing algorithm and Ford-Fulkerson routing algorithm ‰Each router maintains a table (a ‘vector’) giving the best known distance to each destination and which line to use to get to it ‰The tables are updated by exchanging information with the neighbors ‰The ‘distance’ is a metric which can be number of hops, packet delay, total number of packets queued along the path etc. Faisal Amjad CPS 422

1

Distance Vector Routing - Operation

Distance Vector Routing - Operation

‰Each router maintains a ‘routing table’ indexed by one entry per router in the subnet ‰Each routing table entry contains two parts o The preferred outgoing line to use for that destination o Estimated time or ‘distance’ to that destination

‰If ‘delay’ is used as a metric, it is calculated by a special ECHO packet which is time stamped by the recipient and sent back ‰The delay is then computed from the time stamp Faisal Amjad CPS 422

‰ Assume delay is used as a metric and a router knows the delay to each of its neighbors ‰ Once every T msec each router sends to its neighbors, a list of its estimated delays to all the destinations ‰ Hence every router receives such lists regarding every other router in the subnet ‰ Assume one of these tables (distance vector) has arrived at router Y, from a neighbor X, with Xi msec being X’s estimate of how long it takes to get to router i from router X ‰ The recipient (Y) of this distance vector also knows that it takes m msec to get to X fro Y ‰ It means that it would take Xi + m msec to get to router I from router Y Faisal Amjad CPS 422

Distance Vector Routing - Operation ‰By performing these calculations for each of the router in the subnet, a router can find out which estimate seems the best and use that estimate along with the corresponding line in its new routing table ‰Old routing table is not used in the calculations

Xi m sec

i

m msec X

Y

Xi + m msec

Faisal Amjad CPS 422

Distance Vector – Routing Table Calculation To

New estimated delay Line

A

I

H

K

A

0

24

20

21

8

A

B

12

36

31

28

20

A

C

25

18

19

36

28

I

D

40

27

8

24

20

H

E

14

7

30

22

17

I

F

23

20

19

40

30

I

G

18

31

6

31

18

H

H

17

20

0

19

12

H

I

21

0

14

22

10

I

J

9

11

7

10

0

-

K

24

22

22

0

6

K

15

K

L

29

33

9

9

JA delay is 8

JI delay is 10

JH delay is 12

JK delay is 6

New vectors received from J’s neighbors

A

E

I

B

C

F

G

J

K

D

H

Faisal Amjad CPS 422

Distance Vector Routing – Reaction to Topology Changes

‰A ‘good’ news is propagated quickly ‰A serious drawback of the algorithm while propagating ‘bad’ news ‰Consider a linear subnet with five nodes where the number of hops is considered to be the delay metric

L

New routing table for J

Faisal Amjad CPS 422

Faisal Amjad CPS 422

2

Distance Vector Routing – Reaction to BAD news Distance Vector Routing – Reaction to GOOD news

A

B

C

D

E

∞ 1

∞ ∞

1

2

∞ ∞ ∞

1

2

3

∞ ∞ ∞ ∞

1

2

3

4

The Count to Infinity Problem B

C

D

E

Initially

1

2

3

4

Initially

After 1 exchange

3

2

3

4

After 1 exchange

After 2 exchanges

3

4

3

4

After 2 exchanges

After 3 exchanges

5

4

5

4

After 3 exchanges

After 4 exchanges

5

6

5

6

After 4 exchanges

∞

∞

∞

∞

A

Faisal Amjad CPS 422

The Split Horizon Hack

Faisal Amjad CPS 422

The Split Horizon Hack

‰Split horizon Hack is a remedy for the count to infinity problem ‰Although it also ‘fails’ in certain conditions ‰It changes the way routers announce connectivity to their neighbors ‰In split horizon hack, distance to a node X is not reported on the line on which packets for X are sent ‰In simple words, if a node is towards node X’s ‘left’, then X will not announce its reachability towards left hand side

Announcement of distance vector regarding A Infinity

Actual A

C

B

D

‰ C has to send a distance vector to be sent regarding A ‰ It tells D and E, the ‘truth’ about its distance to A, but tells B that the distance to A is infinity ‰ Suppose that now A goes down ‰ On the first exchange of distance vectors, B discovers that the direct line to A is gone and C has an infinite distance to A. Hence B also makes the distance to A as infinity

Faisal Amjad CPS 422

The Split Horizon Hack

E

Faisal Amjad CPS 422

B

A

Announcement of distance vector regarding A Infinity

Actual A

B

C

D

C

E

‰On the next exchange C discovers that now both of its neighbors have an infinite distance to A ‰It also sets the distance to A as infinity ‰In this manner the news regarding a fault travels one hop at a time ‰Split horizon hack fails in situations where there are loops in a network Faisal Amjad CPS 422

D

‰A announces its distance regarding D to B but not to C (according to split horizon hack) ‰Similarly, B announces its distance regarding D to A but not to C (according to split horizon hack) ‰When line CD breaks both A and B think they can reach D through the other path (not through C) ‰They both count to infinity (their distance regarding D) and the problem persists

Faisal Amjad CPS 422

3

‰It seems (According to book) that Distance Vector Routing algorithm is a total failure, but it is not ‰It has been implemented for routing in Ad hoc networks after some modifications (called Ad hoc On-demand Distance Vector (AODV) routing protocol)

Faisal Amjad CPS 422

4