Data and Computer Communications
Chapter 12 Routing in Switched Networks
Eighth Edition by William Stallings
Routing in Packet Switched Network
key design issue for (packet) switched networks select route across network between end nodes characteristics required:
correctness simplicity Robustness-ability of the n/w to deliver packets in face of localized failure and overloads, Stability- shift from one area to the 2nd ,cause packet to travel in loops. Fairness high priority to exchange of packets between Optimality near by stations , may unfair to station who want to communicate to distant stations. Efficiency-transmission overhead which impairs network efficency.
Performance Criteria
used
for selection of route simplest is minimum hop can be generalized as least cost Cost is inversely related to the data rate or the current queuing delay on the link. Least cost route should provide the highest throughput Least cost route should minimize delay.
Example Packet Switched Network
Decision Time and Place
time
Datagram packet routing decision individually for each packet. Virtual circuit basis-routing decision made at the time the VC is established fixed if subsequent packet using that VC follow the same route. Dynamically changing if route assigned to a particular VC changes in response to changing condition. distributed - made by each node
place
Decision Place
Which
node or nodes in the n/w are responsible for routing decesion.
distributed each node in the n/w is responsible for the routing decision.(complex but robust) Centralized routing decision made by a designated node = e,g n/w control centre.(loss of n/w control center may block operation of n/w) Source routing decision made by source station rather than by the node. User can dictate route through the n/w that meets criteria local to the user.
N/w Information Source &Update Timing
routing decisions usually based on knowledge of n/w topology, traffic load and link cost. (not always)
distributed routing
using local knowledge,(cost of outgoing link) info from adjacent nodes, (amount of congestion at the node)info from all nodes on a potential route
central routing
collect info from all nodes
issue of update timing
when is network info held by nodes updated Local information continuously updated Adjacent /all nodes fixed - never updated adaptive - regular updates
Routing Strategies - Fixed Routing
use
a single permanent route for each source to destination pair determined using a least cost algorithm route is fixed
at least until a change in network topology hence cannot respond to traffic changes No difference for datagram and virtual circuits.
advantage
is simplicity disadvantage is lack of flexibility- does not react to network congestion or failures.
Routing Strategies - Flooding
At each node, an incoming packet is retransmitted on all outgoing links except for the link on which it arrived. Eventually multiple copies arrive at destination each packet is uniquely numbered so duplicates can be discarded (VC no.,Seq no.,source node). need some way to limit incessant retransmission
nodes can remember packets already forwarded to keep network load in bounds or include a hop count in packets
Flooding Example
Properties of Flooding
all
possible routes are tried
very robust used to send emergency messages
at
least one packet will have taken minimum hop count route
can be used to set up virtual circuit route
all
nodes directly or indirectly are visited is high traffic load generated
useful to distribute information (eg. routing)
disadvantage
Routing Strategies - Random Routing
simplicity of flooding with much less load node selects one outgoing path for retransmission of incoming packet selection can be random or round robin a refinement is to select outgoing path based on probability calculation no network info needed but a random route is typically neither least cost nor minimum hop
Routing Strategies - Adaptive Routing
used by almost all packet switching networks routing decisions change as conditions on the network change due to failure or congestion requires information about the state of the network exchange between the nodes. disadvantages:
decisions more complex-process burden on n/w increases adaptive strategies depend on status information that is collected at one place but used at another. tradeoff between quality of network info and overhead, more information , more frequently exchanged, better routing decision. reacting too quickly can cause oscillation reacting too slowly means info may be irrelevant
Adaptive Routing Advantages
An adaptive routing strategy can improve performance, as seen by the network user. An adaptive routing strategy can aid in congestion Because an adaptive routing strategy tends to balance loads, it can delay the onset of severe congestion.
Classification of Adaptive Routing Startegies
based
on information sources
local (isolated)
route to outgoing link with shortest queue can include bias for each destination Rarely used - does not make use of available info
adjacent nodes
takes advantage on delay / outage info distributed or centralized
all nodes
like adjacent
Isolated Adaptive Routing
ARPANET Routing Strategies 1st Generation
1969
distributed adaptive using estimated delay
queue length used as estimate of delay
using Bellman-Ford algorithm node exchanges delay vector with neighbors update routing table based on incoming info problems:
doesn't consider line speed, just queue length queue length not a good measurement of delay responds slowly to congestion
ARPANET Routing Strategies 2nd Generation
1979
distributed adaptive using measured delay
using timestamps of arrival, departure & ACK times
recomputes average delays every 10secs any changes are flooded to all other nodes recompute routing using Dijkstras algorithm good under light and medium loads under heavy loads, little correlation between reported delays and those experienced
ARPANET Routing Strategies 3rd Generation
1987 link cost calculations changed
to damp routing oscillations and reduce routing overhead
measure average delay over last 10 secs and transform into link utilization estimate normalize this based on current value and previous results set link cost as function of average utilization
Least Cost Algorithms
basis for routing decisions
can minimize hop with each link cost 1 or have link value inversely proportional to capacity
defines cost of path between two nodes as sum of costs of links traversed
in network of nodes connected by bi-directional links where each link has a cost in each direction link costs in different directions may be different
for each pair of nodes, find path with least cost
alternatives: Dijkstra or Bellman-Ford algorithms
Dijkstras Algorithm
finds
shortest paths from given source node s to all other nodes by developing paths in order of increasing path length algorithm runs in stages (next slide)
each time adding node with next shortest path algorithm terminates when all nodes processed by algorithm (in set T)
Dijkstras Algorithm Method
Step 1 [Initialization]
T = {s} Set of nodes so far incorporated L(n) = w(s, n) for n s initial path costs to neighboring nodes are simply link costs find neighboring node not in T with least-cost path from s incorporate node into T also incorporate the edge that is incident on that node and a node in T that contributes to the path L(n) = min[L(n), L(x) + w(x, n)] for all n T if latter term is minimum, path from s to n is path from s to x concatenated with edge from x to n
Step 2 [Get Next Node]
Step 3 [Update Least-Cost Paths]
Dijkstras Algorithm Example
Dijkstras Algorithm Example
Iter T L(2) Path L(3) Path L(4) Path L(5) Path L(6 ) Path 1 {1} 2 12 5 1-3 1 14 -
2
3 4
{1,4}
{1, 2, 4} {1, 2, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5, 6}
2
2 2
12
12 12
4
4 3
1-4-3
1-4-3 1-4-53
1
1 1
14
14 14
2
2 2
1-45
1-45 1-45
1-4-56
12
1-4-53
14
1-45
1-4-56
1-2
1-4-5-3
1-4
1-45
1-4-5-6
Bellman-Ford Algorithm
find
shortest paths from given node subject to constraint that paths contain at most one link find the shortest paths with a constraint of paths of at most two links and so on
Bellman-Ford Algorithm
step 1 [Initialization]
L0(n) = , for all n s Lh(s) = 0, for all h for each successive h 0
for each n s, compute: Lh+1(n)=minj[Lh(j)+w(j,n)]
step 2 [Update]
connect n with predecessor node j that gives min eliminate any connection of n with different predecessor node formed during an earlier iteration path from s to n terminates with link from j to n
Example of Bellman-Ford Algorithm
h Lh(2)
Results of Bellman-Ford Example Path L (3) Path L (4) Path L (5) Path L (6) Path
h h h h
0 1 2 2 2 3 2 4 2
1-2 1-2 1-2 1-2
5 4 3 3
1-3 1-4-3 1-4-5-3 1-4-5-3
1 1 1 1
1-4 1-4 1-4 1-4
2 2 2
1-4-5 1-4-5 1-4-5
10 4 4
1-3-6 1-4-5-6 1-4-5-6
Comparison
results from two algorithms agree Bellman-Ford
calculation for node n needs link cost to neighbouring nodes plus total cost to each neighbour from s each node can maintain set of costs and paths for every other node can exchange information with direct neighbors can update costs and paths based on information from neighbors and knowledge of link costs each node needs complete topology must know link costs of all links in network must exchange information with all other nodes
Dijkstra
Evaluation
dependent on
processing time of algorithms amount of information required from other nodes
implementation specific both converge under static topology and costs both converge to same solution if link costs change, algs attempt to catch up if link costs depend on traffic, which depends on routes chosen, may have feedback instability
Summary
routing
in packet-switched networks routing strategies
fixed, flooding, random,adaptive
ARPAnet
examples least-cost algorithms
Dijkstra, Bellman-Ford