Essay about Dijkstra ' s Algorithm and Arpanet Routing Chow

Submitted By akshaykitswgl
Words: 1445
Pages: 6

Datagram vs. Virtual Circuit
In a virtual circuit network
Session Routing
A

In a datagram network
A
B
C
D

A3
A2
D3

B1

E

E

D1 A1
C1
D2
Mi: ith datagram sent by Host M.

B
C
D

All packets of the same virtual circuit travel along the same path.
Two packets of the same user pair can travel along different routes.
Packet sequencing is guaranteed.
The packets can arrive out of sequence. Packets contain short VC Id. (VCI).
Packets contain full Src, Dst addresses. Each VC occupies routing table entries.
Each host occupies routine table entries. Requires VC setup. First packet has
Requires no connection setup. large delay. chow CS522 F96-Routing-12/3/96–Page 1-

Virtual Circuit and Datagram Implementation
Internal Operation
Datagram

Datagram

Victual Circuit

UDP over IP
(packet)

IP over ATM

External Service Virtual Circuit TCP over IP
TYMNET, SNA over ATM
(message, packet) (Virtual and explicit route)

chow

CS522 F96-Routing-12/3/96–Page 2-

Routing Algorithm l l

Select routes for various origin-destination (OD) pairs via shortest or optimization calculation (accommodate more OD pairs).
Delivery of messages to the correct destination once routes are selected.
→ Use routing tables.

Performance Measures Affected By Routing
Delay
5 pkts/s
5 pkts/s 5 pkts/s Throughput
(to 6)

(to 6)

2

1

3

4

6

(to 6)
2

1
5

Destination

All links have C=10 pkts/s.
If all traffic is via (4,6), congestion occurs.
Via (1,3,6) and (2,5,6), the delay is small. chow 15 pkts/s
(to 6)

3

4

6

5

Destination

All links have C=10 pkts/s.
Traffic can be accommodated by multi-path routing.
What is the max. throughput from nodes 1and 2 to 6?
How about the worst case?
CS522 F96-Routing-12/3/96–Page 3-

Classification of Routing Algorithms l l

Centralized (all routing decisions at a single node) or Distributed (computation of routes shared by nodes)
Static (routes are fixed for each OD pair regardless of traffic pattern) or Adaptive (responsive to traffic pattern)

Desirable Properties of Routing Algorithms l l l l l l

correctness simplicity robustness stability fairness conflicts optimality
A

B

C

X

X’
A’

chow

B’

C’
CS522 F96-Routing-12/3/96–Page 4-

(Routing) Optimal Principle

A subnet l l

chow

sink tree for router B

If router J is on the optimal path from route I to route K, then the optimal path from J to K also falls along the same route.
The optimal routes to a router form a sink tree.

CS522 F96-Routing-12/3/96–Page 5-

Dijkstra’s Shortest Path Algorithm [DIJK59]
Find the shortest paths form a given source node to all other nodes by developing paths in order of increasing path length.
Let the set of nodes in a network be N.
1. start with a source node S in node set M. Let the nodes not in M be M’.
2. Let L with the set of links connecting M and M’. l Among the nodes in M’ connected to M via L, find the node, n, with the lowest path cost to s. Move n to M. (Use hopcount, nodeId for tie breaker.) l Update the cost from s to other nodes in M’ taking into consideration of the new path via n.
3. Repeat step 2 until M=N.

chow

CS522 F96-Routing-12/3/96–Page 6-

Computing Shortest Path

chow

CS522 F96-Routing-12/3/96–Page 7-

Routing Strategies l l

chow

Fixed routing
Network Operation Center (NOC) collects information from individual nodes
NOC carries out the least cost routing algorithms.
NOC distributed the routing information to individual nodes.
The above steps are carried out periodically.
Flooding
A node sends/relays a message along all its outgoing links.
Rely on hop counts or time-stamps to terminate the flooding.
Disadvantage: a lot of redundant msgs, waste bandwidth.
Advantage: does not require NOC, reliable, message may arrive via a minimum hop route.

CS522 F96-Routing-12/3/96–Page 8-

Routing in ARPANET (old version)
Use distributed, shortest path, and adaptive routing algorithm.
Periodically, each IMP calculates delay to other IMPs, exchanges delay vectors with their neighbors, based on the delay vectors…