Transcript THE NETWORK LAYER 5.2 ROUTING ALGORITHMS

THE NETWORK LAYER
5.2 ROUTING ALGORITHMS - adaptive
Distance Vector Routing (Bellman-Ford, Ford-Fulkenson). It was used in early
versions of ARPANET and in Internet (RIP), DECnet,, AppleTalk and Cisco.
• Each router maintains a table (i.e. a vector) indexed by, and containing one entry
for each router in the subnet. The entry contains the preferred outgoing line for
this destination and an estimate giving the best known distance to that
destination (# of hops, time delay, etc.).
 Once every T msec each router sends to (and receives from) each neighbor a
list of estimated distance to each destination. The router recalculates the
distances.
2
1
Stainov - DataCom
MET CS TC535
3
THE NETWORK LAYER
5.2 ROUTING ALGORITHMS - adaptive
Count-to-Infinity Problem - the distance vector routing propagates the good
news, but leisurely to the bad news.
Stainov - DataCom
MET CS TC535
4
THE NETWORK LAYER
5.2 ROUTING ALGORITHMS - adaptive
Link State Routing (Second Generation in ARPANET) - the first generation did not
consider the speed, but only the queue length, and took too long to converge.
1. Discover its neighbors and learn their network addresses.
2. Measure the delay or cost to each of its neighbors (e.g. by ECHO packets)
 measure RTT/2 and calculate only the queue delay (to avoid load oscillation) or
both, the queue delay and the communication load transformed to "link utilization".
3. Construct a packet telling all it has just learned, and send the packet to all routers.
4. Compute the shortest path to every other router.
 The complete topology and all delays are experimentally measured and distributed
to every router.
Stainov - DataCom
MET CS TC535
5
5.5 INTERNET: Subnets
a. The classic (and externally transparent) IP address:
b. Internal structuring of the IP address:
Net-ID
Net-ID
Subnet-ID
Host-ID
Host-ID
•
For example are the first 8 bits (= 1 byte) the host ID. The 3 high order bits
can be used as subnet ID. It means, 28 = 256 host addresses are divided
into 23 = 8 subnets with 25 = 32 host addresses each.
• How many bits are to be used for the subnet ID is specified by the subnet
mask.
Example: The subnet mask 255.255.255.224, of a C class address means,
that the three high order bits in the first byte are used for subnet IDs:
» 111111112 . 111111112 . 111111112 . 111000002
Stainov - DataCom
MET CS TC535
31
Internetworking
IP Routing Example
193.174.26.5
PC
Internet
destination
127.0.0.1
default
193.174.24.27
PC-4
Router1
193.174.26.3
routing to flags
127.0.0.1
H
193.174.26.178
G
193.174.26. 171
PC
Router2 193.174.26. 180
193.174.26.7
Sun
193.174.26.10
Stainov - DataCom
Modem
193.174.26.178
destination
routing to
flags
127.0.0.1
127.0.0.1
H
default
193.174.26.5
G
193.174.26.160/27 193.174.26.178
MET CS TC535
11100000 = 224 mask
PC
Modem
10100000 = 160 subnet ID
10110100 = 180 destin.
193.174.26.190
10101011 = 171 destin.
41