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