USA: +1(669)289-8683 
Sign in
50
COSC 5350 COURSE ASSIGNMENT VIII
RAINWATER NETWORKING ROUTING
NAME:___________________________________ SCORE:_______________
ATTACH SOURCE PROGRAM LISTING, INPUT DATA SET AND OUTPUT INDICATIVE
OF PROGRAM RESULTS TO THIS COURSE ASSIGNMENT.
DUE DATE: Wednesday, 24 April 2013
Using the language of your choice, write a program which implements Dijkstra’s
Shortest Path Algorithm as discussed in class. Your program should input the
network cost matrix and determine the shortest path length from each node to every
other node in the network. Use the following network to provide for input data to
your program (feel free to input additional networks for supplemental testing).
For the indicated network, your program’s output for NODE 0 might appear as
follows:
FROM NODE 0
TO NODE LENGTH PATH
1 5 0-1
2 4 0-2
3 12 0-2-4-3
4 10 0-2-4
5 11 0-3-5
6 22 0-2-4-3-6
Your program would also output the routing table for the remaining nodes in the
network. You should, of course, work independently on this program and follow the
logical design previously discussed in class. Be sure to include descriptive
documentation to your source code and practice good programming techniques.
Data and Computer Communications
Ninth Edition
by William Stallings
Unit
1
2 – Routing in Switched Data Networks
Data and Computer Communications, Ninth Edition by William Stallings, (c) Pearson Education – Prentice Hall, 2011
1
“Data and Computer Communications”, 9/e, by William Stallings, Chapter 12 “Routing in Switched Networks”.
Routing in Packet Switching Networks
key design issue for (packet) switched networks
select route across network between end nodes
characteristics required:
correctness
simplicity
robustness (delivery in face of failures and overloads)
stability (dynamic state of links)
fairness (nearby versus faraway nodes)
optimality (maximize average throughput)
efficiency (processing overhead)
2
A key design issue in switched networks, including packet-switching, frame relay, and ATM networks, and with internets, is that of routing. In general terms, the routing function seeks to design routes through the network for individual pairs of communicating end nodes such that the network is used efficiently. The primary function of a packet-switching network is to accept packets from a source station and deliver them to a destination station. To accomplish this, a path or route through the network must be determined; generally, more than one route is possible. Thus, a routing function must be performed. The requirements for this function are shown on the slide.
The first two items on the list, correctness and simplicity, are self-explanatory. Robustness has to do with the ability of the network to deliver packets via some route in the face of localized failures and overloads. The designer who seeks robustness must cope with the competing requirement for stability. Techniques that react to changing conditions have an unfortunate tendency to either react too slowly to events or to experience unstable swings from one extreme to another. A tradeoff also exists between fairness and optimality. Some performance criteria may give higher priority to the exchange of packets between nearby stations compared to an exchange between distant stations. This policy may maximize average throughput but will appear unfair to the station that primarily needs to communicate with distant stations. Finally, any routing technique involves some processing overhead at each node and often a transmission overhead as well, both of which impair network efficiency. The penalty of such overhead needs to be less than the benefit accrued based on some reasonable metric, such as increased robustness or fairness.
Performance Criteria
used for selection of route
simplest is to choose “minimum hop”
can be generalized as “least cost” routing
because actual “least cost” is more flexible (with similar computational effort) it is more common than “minimum hop”
3
The selection of a route is generally based on some performance criterion. The simplest criterion is to choose the minimum-hop route (one that passes through the least number of nodes) through the network. This is an easily measured criterion and should minimize the consumption of network resources. A generalization of the minimum-hop criterion is least-cost routing. In this case, a cost is associated with each link, and, for any pair of attached stations, the route through the network that accumulates the least cost is sought. In either the minimum-hop or least-cost approach, the algorithm for determining the optimum route for any pair of stations is relatively straightforward, and the processing time would be about the same for either computation. Because the least-cost criterion is more flexible, this is more common than the minimum-hop criterion. Several least-cost routing algorithms are in common use. These are described in Stallings DCC9e Section 12.3
Elements of Routing Techniques for Packet-Switching Networks
Stallings DCC9e Table 12.1.
4
Example of Packet Switched Network
The shortest path (fewest hops) from node 1 to node 6 is 1-3-6 (cost is 5 + 5 = 10), but least-cost path is 1-4-5-6 (cost is 1 + 1 + 2 = 4).
Costs are assigned to links to support one or more design objectives. For example, cost could be inversely related to data rate (higher data rate on a link, lower assigned cost of link) or current queuing delay on link.
5
Stallings DCC9e Figure 12.1 illustrates a network in which the two arrowed lines between a pair of nodes represent a link between these nodes, and the corresponding numbers represent the current link cost in each direction. The shortest path (fewest hops) from node 1 to node 6 is 1-3-6 (cost = 5 + 5 = 10), but the least-cost path is 1-4-5-6 (cost = 1 + 1 + 2 = 4). Costs are assigned to links to support one or more design objectives. For example, the cost could be inversely related to the data rate (i.e., the higher the data rate on a link, the lower the assigned cost of the link) or the current queuing delay on the link. In the first case, the least-cost route should provide the highest throughput. In the second case, the least-cost route should minimize delay.
Decision Time and Place
6
Routing decisions are made on the basis of some performance criterion. Two key characteristics of the decision are the time and place that the decision is made.
Decision time is determined by whether the routing decision is made on a packet or virtual circuit basis. When the internal operation of the network is datagram, a routing decision is made individually for each packet. For internal virtual circuit operation, a routing decision is made at the time the virtual circuit is established. In the simplest case, all subsequent packets using that virtual circuit follow the same route. In more sophisticated network designs, the network may dynamically change the route assigned to a particular virtual circuit in response to changing conditions (e.g., overload or failure of a portion of the network).
The term decision place refers to which node or nodes in the network are responsible for the routing decision. Most common is distributed routing, in which each node has the responsibility of selecting an output link for routing packets as they arrive. For centralized routing, the decision is made by some designated node, such as a network control center. The danger of this latter approach is that the loss of the network control center may block operation of the network. The distributed approach is perhaps more complex but is also more robust. A third alternative, used in some networks, is source routing. In this case, the routing decision is actually made by the source station rather than by a network node and is then communicated to the network. This allows the user to dictate a route through the network that meets criteria local to that user.
decision time
packet or virtual circuit basis
decision place
distributed – made by each node
fixed or dynamically changing
more complex, but also more robust
centralized – made by a designated node
source – made by source station and communicated to network
Network Information Source and Update Timing
routing decisions usually based on (static or dynamic) knowledge of network, traffic load, and link cost
distributed routing
using local knowledge, information from adjacent nodes, information from all nodes on a potential route
central routing
collect information from all nodes
7
Most routing strategies require that decisions be based on knowledge of the topology of the network, traffic load, and link cost.
With distributed routing, in which the routing decision is made by each node, the individual node may make use of only local information, such as the cost of each outgoing link. Each node might also collect information from adjacent (directly connected) nodes, such as the amount of congestion experienced at that node. Finally, there are algorithms in common use that allow the node to gain information from all nodes on any potential route of interest. In the case of centralized routing, the central node typically makes use of information obtained from all nodes.
A related concept is that of information update timing, which is a function of both the information source and the routing strategy. Clearly, if no information is used (as in flooding), there is no information to update. If only local information is used, the update is essentially continuous. For all other information source categories (adjacent nodes, all nodes), update timing depends on the routing strategy. For a fixed strategy, the information is never updated. For an adaptive strategy, information is updated from time to time to enable the routing decision to adapt to changing conditions.
As you might expect, the more information available, and the more frequently it is updated, the more likely the network is to make good routing decisions. On the other hand, the transmission of that information consumes network resources.
issue of update timing
depends on routing strategy
fixed – never updated
adaptive – regular updates to adapt to changing conditions
Routing Strategies – Fixed Routing
use a single permanent route for each source to destination pair of nodes
determined using a least cost algorithm
route is fixed
until a change in network topology
based on expected traffic or capacity
cannot be based on dynamic variable (traffic)
advantage is simplicity
disadvantage is lack of flexibility
does not react to network failure or congestion
8
A large number of routing strategies have evolved for dealing with the routing requirements of packet-switching networks, we survey four key strategies: fixed, flooding, random, and adaptive.
For fixed routing, a single, permanent route is configured for each source-destination pair of nodes in the network. Either of the least-cost routing algorithms described in Section 12.3 could be used. The routes are fixed, or at least only change when there is a change in the topology of the network. Thus, the link costs used in designing routes cannot be based on any dynamic variable such as traffic. They could, however, be based on expected traffic or capacity.
With fixed routing, there is no difference between routing for datagrams and virtual circuits. All packets from a given source to a given destination follow the same route. The advantage of fixed routing is its simplicity, and it should work well in a reliable network with a stable load. Its disadvantage is its lack of flexibility. It does not react to network congestion or failures.
Fixed Routing
Tables
Central routing matrix (perhaps stored at network control center) – for each source-destination pair, identity of next node on the route – complete routes not stored, only first node on route
From matrix, routing tables developed and stored at each node
No difference between datagram and virtual circuit
No flexibility unless refined via alternate next nodes provided
Routing Strategies – Flooding
no network information required
packet sent by node to every neighbor
eventually multiple copies arrive at destination
each packet is uniquely numbered so duplicates can be discarded
need to limit incessant retransmission of packets
nodes can remember identity of packets retransmitted
can include a hop count, such as the diameter (length of the longest minimum-hop path through the network) of the network, in packets
decrement at each node; discard packet when count reaches zero
10
Another simple routing technique is flooding. This technique requires no network information whatsoever and works as follows. A packet is sent by a source node to every one of its neighbors. At each node, an incoming packet is retransmitted on all outgoing links except for the link on which it arrived. Eventually, a number of copies of the packet will arrive at the destination. The packet must have some unique identifier (e.g., source node and sequence number, or virtual circuit number and sequence number) so that the destination knows to discard all but the first copy.
Unless something is done to stop the incessant retransmission of packets, the number of packets in circulation just from a single source packet grows without bound. One way to prevent this is for each node to remember the identity of those packets it has already retransmitted. When duplicate copies of the packet arrive, they are discarded. A simpler technique is to include a hop count field with each packet. The count can originally be set to some maximum value, such as the diameter (length of the longest minimum-hop path through the network) of the network. Each time a node passes on a packet, it decrements the count by one. When the count reaches zero, the packet is discarded.
Properties of Flooding
11
The flooding technique has three remarkable properties:
• All possible routes between source and destination are tried. Thus, no matter what link or node outages have occurred, a packet will always get through if at least one path between source and destination exists.
• Because all routes are tried, at least one copy of the packet to arrive at the destination will have used a minimum-hop route.
• All nodes that are directly or indirectly connected to the source node are visited.
Because of the first property, the flooding technique is highly robust and could be used to send emergency messages. An example application is a military network that is subject to extensive damage. Because of the second property, flooding might be used initially to set up the route for a virtual circuit. The third property suggests that flooding can be useful for the dissemination of important information to all nodes; we will see that it is used in some schemes to disseminate routing information. The principal disadvantage of flooding is the high traffic load that it generates, which is directly proportional to the connectivity of the network. Another disadvantage is that every node sees the routing data, which may create a security concern.
all possible routes are tried
highly robust
can be used to send emergency messages
at least one packet will have taken minimum hop route
nodes directly or indirectly connected to source are visited
Disadvantages:
high traffic load generated
security concerns
Flooding
Example
3 packets
9 packets
22 packets
Packet to be sent from node 1 to node 6
Note: if hop count field used in each packet, such set as diameter (length of longest minimum-hop path through the network) of network – i.e. for each pair of end systems attached to network, there is a minimum hop path – length of longest such path is diameter of network
Routing Strategies – Random Routing
simplicity of flooding with much less traffic 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 – based on data rate or fixed link costs ( e.g. Ri / Rj)
no network information (overhead) needed
random route is typically neither least cost nor minimum hop – network must carry a higher than optimum traffic load (not as high as flooding)
13
Random routing has the simplicity and robustness of flooding with far less traffic load. With random routing, a node selects only one outgoing path for retransmission of an incoming packet. The outgoing link is chosen at random, excluding the link on which the packet arrived. If all links are equally likely to be chosen, then a node may simply utilize outgoing links in a round-robin fashion.
A refinement of this technique is to assign a probability to each outgoing link and to select the link based on that probability. The probability could be based on data rate, or on fixed link costs.
Like flooding, random routing requires the use of no network information. Because the route taken is random, the actual route will typically not be the least-cost route nor the minimum-hop route. Thus, the network must carry a higher than optimum traffic load, although not nearly as high as for flooding.
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 (dynamic) information about network
Disadvantages:
decisions more complex (node processing burden)
tradeoff between quality of network information and overhead (status info collected in one place, used in another)
reacting too quickly can cause oscillation
reacting too slowly means information may be irrelevant
14
In virtually all packet-switching networks, some sort of adaptive routing technique is used. That is, the routing decisions that are made change as conditions on the network change. The principal conditions that influence routing decisions are:
• Failure: When a node or link fails, it can no longer be used as part of a route.
• Congestion: When a particular portion of the network is heavily congested, it is desirable to route packets around rather than through the area of congestion.
For adaptive routing to be possible, information about the state of the network must be exchanged among the nodes. There are several drawbacks associated with the use of adaptive routing, compared to fixed routing:
• The routing decision is more complex; therefore, the processing burden on network nodes increases.
• In most cases, adaptive strategies depend on status information that is collected at one place but used at another. There is a tradeoff here between the quality of the information and the amount of overhead. The more information that is exchanged, and the more frequently it is exchanged, the better will be the routing decisions that each node makes. On the other hand, this information is itself a load on the constituent networks, causing a performance degradation.
• An adaptive strategy may react too quickly, causing congestion-producing oscillation, or too slowly, being irrelevant.
Adaptive Routing Advantages
15
Despite these real dangers, adaptive routing strategies are by far the most prevalent, for two reasons:
• An adaptive routing strategy can improve performance, as seen by the network user.
• An adaptive routing strategy can aid in congestion control, which is discussed in Chapter 13. Because an adaptive routing strategy tends to balance loads, it can delay the onset of severe congestion.
These benefits may or may not be realized, depending on the soundness of the design and the nature of the load. By and large, adaptive routing is an extraordinarily complex task to perform properly. As demonstration of this, most major packet-switching networks, such as ARPANET and its successors, and many commercial networks, have endured at least one major overhaul of their routing strategy.
improved performance
aid in congestion control (we will see more later)
*These benefits depend on the soundness of the design and nature of the load.
Classification of Adaptive Routing Strategies
on the basis of information source
16
A convenient way to classify adaptive routing strategies is on the basis of information source: local, adjacent nodes, all nodes. An example of an adaptive routing strategy that relies only on local information is one in which a node routes each packet to the outgoing link with the shortest queue length, Q. This would have the effect of balancing the load on outgoing links. However, some outgoing links may not be headed in the correct general direction. We can improve matters by also taking into account preferred direction, much as with random routing. In this case, each link emanating from the node would have a bias Bi, for each destination i, such that lower values of Bi indicate more preferred directions. For each incoming packet headed for node i, the node would choose the outgoing link that minimizes Q + Bi. Thus a node would tend to send packets in the right direction, with a concession made to current traffic delays.
Adaptive schemes based only on local information are rarely used because they do not exploit easily available information. Strategies based on information from adjacent nodes or all nodes are commonly found. Both take advantage of information that each node has about delays and outages that it experiences. Such adaptive strategies can be either distributed or centralized. In the distributed case, each node exchanges delay information with other nodes. Based on incoming information, a node tries to estimate the delay situation throughout the network, and applies a least-cost routing algorithm. In the centralized case, each node reports its link delay status to a central node, which designs routes based on this incoming information and sends the routing information back to the nodes.
local (isolated)
route to outgoing link with shortest queue
adjacent nodes
takes advantage of delay and outage information
all nodes
like adjacent
can include bias for each destination –
rarely used – does not make use of all available information
distributed or centralized
for distributed, each node exchanges delay info
Isolated Adaptive Routing
packet arrives at node 4 from node 1 with destination node 6 – min value is on link through node 3 since Q + B6 is 4 (1 + 3)
note: (outgoing) queue lengths of receiving node
Least Cost Algorithms
for example: Dijkstra or Bellman-Ford algorithms (Floyd-Warshall all nodes)
18
Virtually all packet-switching networks and all internets base their routing decision on some form of least-cost criterion. If the criterion is to minimize the number of hops, each link has a value of 1. More typically, the link value is inversely proportional to the link capacity, proportional to the current load on the link, or some combination. In any case, these link or hop costs are used as input to a least-cost routing algorithm, which can be simply stated as:
Given a network of nodes connected by bidirectional links, where each link has a cost associated with it in each direction, define the cost of a path between two nodes as the sum of the costs of the links traversed. For each pair of nodes, find a path with the least cost.
Note that the cost of a link may differ in its two directions. This would be true, for example, if the cost of a link equaled the length of the queue of packets awaiting transmission from each of the two nodes on the link.
Most least-cost routing algorithms in use in packet-switching networks and internets are variations of one of two common algorithms, known as Dijkstra’s algorithm and the Bellman-Ford algorithm.
basis for routing decisions
minimize hop with each link cost of 1
have link value inversely proportional to capacity
defines cost of path between two nodes as sum of costs of links traversed
network of nodes connected by bi-directional links
link has a cost in each direction
for each pair of nodes, find path with least cost
link costs in different directions may be different
Least Cost Algorithms
Basis for routing decisions
Can minimize hop with each link cost 1
Can have link value inversely proportional to capacity
Given network of nodes connected by bi-directional links
Each link has a cost in each direction
Define cost of path between two nodes as sum of costs of links traversed
For each pair of nodes, find a path with the least cost
Link costs in different directions may be different
e.g. length of packet queue
Dijkstra’s Algorithm
Find shortest paths from given source node to all other nodes, by developing paths in order of increasing path length
N = set of nodes in the network
s = source node
T = set of nodes so far incorporated by the algorithm
w(i, j) = link cost from node i to node j
w(i, i) = 0
w(i, j) = if the two nodes are not directly connected
w(i, j) 0 if the two nodes are directly connected
L(n) = cost of least-cost path from node s to node n currently known
At termination, L(n) is cost of least-cost path from s to n
Dijkstra’s Algorithm Method
Step 1 [Initialization]
T = {s} Set of nodes so far incorporated consists of only source node
L(n) = w(s, n) for n ≠ s
Initial path costs to neighboring nodes are simply link costs
Step 2 [Get Next Node]
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
Step 3 [Update Least-Cost Paths]
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
Algorithm terminates when all nodes have been added to T
Dijkstra’s Algorithm Notes
At termination, value L(x) associated with each node x is cost (length) of least-cost path from s to x.
In addition, T defines least-cost path from s to each other node
One iteration of steps 2 and 3 adds one new node to T
Defines least cost path from s to that node
Example of Dijkstra’s Algorithm
1
4
5
3
6
2
Iteration T L(2) Path L(3) Path L(4) Path L(5) Path L(6) 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
25
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Set value[0] to 0, the rest of the values to
Place node 0 (the source) into class 1 , the rest into class 2
while the sink node is not in class 1 do
The last node put in class 1 is the pivotal node
for all nodes j in class 2:
if this node j is not connected to the pivotal node
then do nothing
else if the value of the pivotal node +
edge value is less than value of node j
then value of node j is assigned
the value of the pivotal node + edge value
else do nothing
end for
Add the node in class 2 with minimum value to class 1
end while
L(n) = min[L(n), L(x) + w(x, n)] for all nT
27
Dijkstra’s Algorithm
PREDECESSOR PIVOTAL NODE Class 1 =
value[0] = Class 2 =
value[1] = ∞
value[2] = ∞
value[3] = ∞
value[4] = ∞
value[5] = ∞
value[6] = ∞
28
Another Example
a
e
d
c
b
1
5
2
4
6
3
7
0
1
3
2
4
ARPANET Routing Strategies
First Generation – 1969
ARPANET – foundation of present-day Internet
Distributed adaptive routing
Estimated delay as performance criterion (distance-vector routing – Delay and Successor vectors for each node)
Node exchanges delay vector with neighbors (every 128 milliseconds)
Update routing table based on incoming info
Bellman-Ford algorithm (least-cost routing algorithm)
Doesn’t consider link speed; just uses queue length as estimator of node delay
Queue length not a good measurement of delay
Responds slowly to congestion
ARPANET Routing Strategies
Second Generation – 1979
Addressed shortcomings of first generation (i.e. in which line speed not considered – only queue length … slow response to congestion)
Used delay as performance criterion
Delay measured directly (not just as the artificial measure of queue length – using packet time-stamping – departure time minus arrival time plus transmission and propagation times – thus includes link data rate) – every 10 seconds
If significant delay changes, then flood this info out to all other nodes
(re)computation using Dijkstra’s least-cost algorithm
works good under light and medium loads
but under heavy loads, little correlation between reported delays and those experienced
ARPANET Routing Strategies
Third Generation – 1987
as network load grew, new strategy needed
Link cost calculations changed
Measure average delay over last 10 seconds – routing so that average path good instead of all routes
Normalize to value achieved on idle line (just transmission and propagation times) and based on current value versus previous results
Revised cost function keyed to utilization rather than delay
Function acts similar to delay-based metric under light loads and to capacity-based metric under heavier loads
Summary
routing in packet-switched networks
routing techniques
routing strategies
fixed, flooding, random, adaptive
least-cost algorithms
Dijkstra, Bellman-Ford
evolution of ARPANET routing strategies
32
Stallings DCC9e Chapter12 summary.
Performance Criteria
Number of hops
Cost
Delay
Throughput
Decision Time
Packet (datagram)
Session (virtual circuit)
Decision Place
Each node (distributed)
Central node (centralized)
Originating node (source)
Network Information Source
None
Local
Adjacent node
Nodes along route
All nodes
Network Information Update Timing
Continuous
Periodic
Major load change
Topology change
