Chapter 8: Packet Switching
Raj Jain
Professor of CIS
The Ohio State University
Columbus, OH 43210
Jain@[Link]
[Link]
The Ohio State University Raj Jain
8-1
Overview
Circuit, datagram, virtual circuit switching
Routing algorithms
ARPAnet routing
The Ohio State University Raj Jain
8-2
Datagram vs Virtual Circuit
Connectionless vs connection-oriented
The Ohio State University Fig 8.4 Raj Jain
8-3
Circuit vs Datagram vs VC
Circuit Switching Datagram Virtual Circuit
Dedicated transmission path No dedicated path No dedicated path , Shared path
Continuous transmission of data Bursty Bursty
No buffering required Buffers required Buffers required
Path fixed at connection setup Different packets may take different Path fixed at connection setup
paths
Call setup delay Queueing delays Call setup + queueing delays
Overload blocks new calls Overload increases queueing delays Overload may block new calls. May
increase queueing delays
Source and destination have the Source and destination may have Source and destination may have
same speed different speed different speed
Bandwidth is reserved. Unused Bandwidth is dynamically shared Bandwidth is reserved as well as
bandwidth is wasted among users dynamically shared
No overhead bits after call setup Overhead bits in each packet Less overhead bits in each packet
Switches keep state Switches donot keep state Switches keep state
No or negligible loss Loss possible Loss possible
On link failure Connection continues VC broken
The Ohio State University Table 8.1 Raj Jain
8-4
External vs Internal VC
External: End-to-end (Transport layer)
Internal: On the path (Network layer)
On the path
(Internal)
Datagram Virtual Ckt
No connection
End-to-end
UDP/IP
(External)
(Datagram)
Connection SNA
TCP/IP
(VC) TYMNET
The Ohio State University Raj Jain
8-5
Routing
The Ohio State University Fig 8.8 Raj Jain
8-6
Rooting or Routing
Rooting is what fans do at football games, what
pics do for truffles under oak trees in the
Vaucluse, and what nursery workers intent on
propagation do to cuttings from plants.
Routing is how one creates a beveled edge on a
table top or sends a corps of infanctrymen into
full scale, disorganized retreat
Ref: Piscitello and Chapin, p413
The Ohio State University Raj Jain
8-7
Routeing or Routing
Routeing: British
Routing: American
Since Oxford English Dictionary is much
heavier than any other dictionary of American
English, British English generally prevalis in
the documents produced by ISO and CCITT;
wherefore, most of the international standards
for routing standards use the routeing spelling.
Ref: Piscitello and Chapin, p413
The Ohio State University Raj Jain
8-8
Routing Techniques Elements
Performance criterion: Hops, Distance, Speed,
Delay, Cost
Decision time: Packet, session
Decision place: Distributed, centralized, Source
Network information source: None, local, adjacent
nodes, nodes along route, all nodes
Routing strategy: Fixed, adaptive, random, flooding
Adaptive routing update time: Continuous, periodic,
topology change, major load change
The Ohio State University Raj Jain
8-9
Dijkstras Algorithm
Goal: Find the least cost paths from a given node to all other
nodes in the network
Notation:
dij = Link cost from i to j if i and j are connected
Dn = Total path cost from s to n
M = Set of nodes so far for which the least cost path is known
Method:
Initialize: M={s}, Dn = dsn
Find node w M, whose Dn is minimum
Update Dn
The Ohio State University Raj Jain
8-10
Example
The Ohio State University Raj Jain
8-11
Example (Cont)
M D2 Path D3 Path D4 Path D5 Path D6 Path
1 {1} 2 1-2 5 1-3 1 1-4 - -
2 {1,4} 2 1-2 4 1-4-3 1 1-4 2 1-4-5 -
3 {1,2,4} 2 1-2 4 1-4-3 1 1-4 2 1-4-5 -
4 {1,2,4,5} 2 1-2 3 1-4-5-3 1 1-4 2 1-4-5 4 1-4-5-6
5 {1,2,3,4,5} 2 1-2 3 1-4-5-3 1 1-4 2 1-4-5 4 1-4-5-6
6 {1,2,3,4,5,6} 2 1-2 3 1-4-5-3 1 1-4 2 1-4-5 4 1-4-5-6
The Ohio State University Table 8.4a Raj Jain
8-12
Dijkstra's routing algorithm
Apply to the following network and compute
paths from node 1.3 2
2 3 6
1 1
1 4
4 1
1 4 5
M D2 Path D3 Path D4 Path D5 Path D6 Path
The Ohio State University Raj Jain
8-13
Dijkstra's routing algorithm
Apply to the following network and compute
paths from node 1.
3 2
2 3 6
1 1
1 4
4 1
1 4 5
M D2 Path D3 Path D4 Path D5 Path D6 Path
1 {1} 1 1-2 - 4 1-4 - -
2 {1,2} 1 1-2 4 1-2-3 4 1-4
3 {1,2,3} 1 1-2 4 1-2-3 4 1-4 2 1-2-5 6 1-2-3-6
4 {1,2,3,5} 1 1-2 4 1-2-3 3 1-2-5-1 2 1-2-5 6 1-2-3-6
5 {1,2,3,4,5} 1 1-2 4 1-2-3 3 1-2-5-1 2 1-2-5 6 1-2-3-6
6 {1,2,3,4,5,6} 1 1-2 4 1-2-3 3 1-2-5-1 2 1-2-5 6 1-2-3-6
The Ohio State University Raj Jain
8-14
Bellman-Ford Algorithm
Notation:
h = Number of hops being considered
D(h)n = Cost of h-hop path from s to n
Method: Find all nodes 1 hop away
Find all nodes 2 hops away
Find all nodes 3 hops away
Initialize: D(h)n = for all n s; D(h)n = 0 for all h
Find jth node for which h+1 hops cost is minimum
D(h+1)n = minj [D(h)j +Djn]
The Ohio State University Raj Jain
8-15
Example
The Ohio State University
Fig 8.9b Raj Jain
8-16
Example (Cont)
(h) (h) (h) (h) (h)
h D Path D Path D Path D Path D Path
2 3 4 5 6
0 - - - - -
1 2 1-2 5 1-3 1 1-4 - -
2 2 1-2 4 1-4-3 1 1-4 2 1-4-5 10 1-3-6
3 2 1-2 3 1-5-4-3 1 1-4 2 1-4-5 4 1-4-5-6
4 2 1-2 3 1-5-4-3 1 1-4 2 1-4-5 4 1-4-5-6
The Ohio State University Table 8.4b Raj Jain
8-17
Flooding
Uses all possible paths
Uses minimum hop path Used for source routing
The Ohio State University Fig 8.11b Raj Jain
8-18
ARPAnet Routing (1969-78)
Features: Cost=Queue length,
Each node sends a vector of costs (to all nodes) to neighbors.
Distance vector
Each node computes new cost vectors based on the new info
using Bellman-Ford algorithm
The Ohio State University Fig 8.13 Raj Jain
8-19
ARPAnet Routing (1979-86)
Problem with earlier algorithm: Thrashing (packets went to
areas of low queue length rather than the destination), Speed
not considered
Solution: Cost=Measured delay over 10 seconds
Each node floods a vector of cost to neighbors.
Link-state. Converges faster after topology changes.
Each node computes new cost vectors based on the new info
using Dijkstras algorithm
The Ohio State University Fig 8.14 Raj Jain
8-20
ARPAnet Routing (1987+)
Problem with 2nd Method: Correlation between delays
reported and those experienced later : High in light loads, low
during heavy loads Oscillations under heavy loads
Unused capacity at some links, over-utilization of others,
More variance in delay more frequent updates More overhead
The Ohio State University Fig 8.15 Raj Jain
8-21
Routing Algorithm
Delay is averanged over 10 s
Link utilization = r = 2(s-t)/(s-2t)
where t=measured delay,
s=service time per packet (600 bit times)
Exponentially weighted average utilization
U(n+1) = U(n)+(1-)r(n+1)
=0.5 U(n)+0.5 r(n+1) with = 0.5
Link cost = fn(U)
The Ohio State University Fig 8.16 Raj Jain
8-22
Summary
Connection-oriented and Connectionless
Routing: Least-cost, Flooding, Adaptive
Dijkstras and Bellman-Ford algorithms
ARPAnet
The Ohio State University Raj Jain
8-23
Homework
Excercise 8.4 (in b assume a unidirectional
single loop), 8.10, 8.15
Due: Next class
The Ohio State University Raj Jain
8-24