12-03-2011, 11:15 AM
Submitted By :
Rameshwar
[attachment=10059]
Packet Switching
Transfer of information as in data packets
Different applications impose differing requirements on the transfer of information
packet-switch network
Packet Switching Operation
Routing
Data is sent in form of packets between 2 end devices
Routers are used to direct packet to its destination
Hop count - this is the number of routers a packet must travel through to get to its destination
Router as a Computer
Describe the basic purpose of a router
Computers that specialize in sending packets over the data network
They are responsible for interconnecting networks by selecting the best path for a packet to travel and forwarding packets to their destination
Routers are the network center
Routers generally have 2 connections:
• WAN connection (Connection to ISP)
• LAN connection
Routing Performance Criteria
Used for selection of route
Minimum hop
Hop count - this is the number of routers a packet must travel through to get to its destination
Least cost
Using some algorithm-Dijsktra, Bellman-Ford
Delay
Throughput
Routing Strategies
Fixed
Flooding
Random
Adaptive
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
advantage is simplicity
disadvantage is lack of flexibility
Routing Strategies
Fixed RoutingTables
Routing Strategies - Flooding
packet sent by node to every neighbor
eventually multiple copies arrive at destination
no network info required
each packet is uniquely numbered so duplicates can be discarded
Routing Strategies
Flooding Example
Routing Strategies - Random Routing
simplicity of flooding with much less load
node selects one outgoing path for retransmission of incoming packet
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 like in failure
It requires info about network
disadvantages:
decisions more complex
reacting too quickly can cause oscillation
Routing Strategies
Isolated Adaptive Routing
Link state routing
Every router maintains its page link state packet (LSP) which records the state information of links to all its neighbors.
A router floods its LSP to entire network, i.e., all routers, (whenever its page link state changes)
Routing in Packet Networks
Routing in Packet Switched Network
Complex, crucial aspect of packet switched networks
Characteristics required
Correctness
Simplicity
Robustness
Stability
Fairness
Optimality
Efficiency
Routing in packet switching networks
Routing is a key function: determine a (best) path from any source to any destination
There exist multiple paths, Which is Best?
Depend on objective:
Minimize number of hops
Maximize available bandwidth
Must have global knowledge about network state to perform this task
Least Cost Algorithms Goals
Basis for routing decisions
Can minimize hop with each page link cost 1
Can have page link value inversely proportional to capacity
Given network of nodes connected by bi-directional links
Define cost of path between two nodes as sum of costs of links traversed, least cost preferd
Link costs in different directions may be different
E.g. length of packet queue
Least Cost Algorithms
Dijkstra
Bellman-Ford
Assumption with example
Dijkstra’s Algorithm
N: set of nodes for which shortest path already found
Initialization: (Start with source node s)
N = {s}, Ds = 0, “s is distance zero from itself”
Dj=Csj for all j ¹ s, distances of directly-connected neighbors
Step A: (Find next closest node i)
Find i Ï N such that
Di = min Dj for j Ï N
Add i to N
If N contains all the nodes, stop
Step B: (update minimum costs)
For each node j Ï N
Dj = min (Dj, Di+Cij)
Go to Step A
Execution of Dijkstra’s algorithm
Shortest Paths in Dijkstra’s Algorithm
Reaction to Failure
If a page link fails,
Router sets page link distance to infinity & floods the network with an update packet
All routers immediately update their page link database & recalculate their shortest paths
Recovery very quick
But watch out for old update messages
Add time stamp or sequence # to each update message
Check whether each received update message is new
If new, add it to database and broadcast
If older, send update message on arriving link
Bellman-Ford Algorithm
Consider computations for one destination d
Initialization
Each node table has 1 row for destination d
Distance of node d to itself is zero: Dd=0
Distance of other node j to d is infinite: Dj=µ, for j¹ d
Next hop node nj = -1 to indicate not yet defined for j ¹ d
Send Step
Send new distance vector to immediate neighbors across local link
Receive Step
At node j, find the next hop that gives the minimum distance to d,
Go to send step
Problem: Bad News Travels Slowly
Split Horizon
Do not report route to a destination to the neighbor from which route was learned
Poisoned Reverse
Report route to a destination to the neighbor from which route was learned, but with infinite distance
Breaks erroneous direct loops immediately
Does not work on some indirect loops