19-11-2012, 11:56 AM
Routing
Routing.ppt (Size: 474 KB / Downloads: 24)
Routing in Circuit Switched Network
Many connections will need paths through more than one switch
Need to find a route
Efficiency
Resilience
Public telephone switches are a tree structure
Static routing uses the same approach all the time
Dynamic routing allows for changes in routing depending on traffic
Uses a peer structure for nodes
Alternate Routing
Possible routes between end offices predefined
Originating switch selects appropriate route
Routes listed in preference order
Different sets of routes may be used at different times
Routing in Packet Switched Network
Complex, crucial aspect of packet switched networks
Characteristics required
Correctness
Simplicity
Robustness
Stability
Fairness
Optimality
Efficiency
Decision Time and Place
Time
Packet or virtual circuit basis
Place
Distributed
Made by each node
Centralized
Source
Network Information Source and Update Timing
Routing decisions usually based on knowledge of network (not always)
Distributed routing
Nodes use local knowledge
May collect info from adjacent nodes
May collect info from all nodes on a potential route
Central routing
Collect info from all nodes
Update timing
When is network info held by nodes updated
Fixed - never updated
Adaptive - regular updates
Fixed Routing
Single permanent route for each source to destination pair
Determine routes using a least cost algorithm (appendix 10A)
Route fixed, at least until a change in network topology
Flooding
No network info required
Packet sent by node to every neighbor
Incoming packets retransmitted on every link except incoming link
Eventually a number of copies will arrive at destination
Each packet is uniquely numbered so duplicates can be discarded
Nodes can remember packets already forwarded to keep network load in bounds
Can include a hop count in packets