Routing in packet switching networksSlide 2Criteria for a good routing algorithmClassification of routing algorithmsRouting tablesSlide 6Slide 7Slide 8Slide 9Hierarchical routingSlide 11IP hierarchical addressingHow to compute routes dynamicallyDistance vector routingLink state routingSlide 16Bellman-Ford algorithmSlide 18BackSlide 20Slide 21Slide 22Slide 23Slide 24Slide 25Distributed implementation of Bellman-Ford algorithmDistributed implementation of Bellman-Ford algorithm(cont.)Slide 28Slide 29Some solutions to counting to infinity problemSlide 31Dijkstra’s algorithm & link state routingSlide 33Slide 34Slide 35Comparison of distance vector and link state routingsOther routing approaches --floodingOther routing approaches –source routingATM virtual-circuit networksTraffic management and QoSApproaches to traffic managementRandom Early Detection (RED)Congestion control in packet switching networksSlide 44Approaches to congestion controlSlide 46Traffic policing vs. traffic shapingSlide 48Slide 49End-to-end vs. hop-by-hopImplicit vs. explicit feedbackClose-loop control—TCP congestion control1Routing in packet switching networks•Routing is a key function: determine a (best) path from any source to any destination•There exist multiple paths •Which path is best?•Depend on objective:–Minimize number of hops–Minimize end-to-end delay–Maximize available bandwidth•Must have global knowledge about network state to perform this task2123456ABSwitch or routerHostFigure 7.23An example of a packet-switch networkPaths: 1-3-6, 1-4-3-6, 1-2-5-6, …3Criteria for a good routing algorithm1. Correctness: correct route and accurate delivery of packets2. robustness: adaptive to changes of network topology and varying traffic load3. Cleverness: ability to detour congestion links and determine the connectivity of the network.4. Efficiency: rapid finding of the route and minimization of control messages.4Classification of routing algorithms•Static vs. dynamic:–Static: manually compute routes, simple, but not scalable and dynamic–Dynamic: automatic route computation, adaptive to dynamics of network but complicated•Centralized vs. distributed–Centralized: a center entity computes all routes and load the routes into all routers, but not scalable–Distributed: routers exchange topology information and perform own computation of routes, but inconsistent and loop routes.•In datagram, routing is based on packet by packet but in VC, routing is executed during setup5Routing tables•Store routing information, being looked up to forward packets•Different networks have different routing tables–Datagram: destination address + next hop–VC: incoming VCI + out-going VCI + out-going port #6123456ABCD15237185423652Figure 7.24Virtual-circuit packet switchingLink 1—3 is shared by connection 1 and 2Link 3—4 is shared by connection 2 and 3Therefore the connection is called virtual-circuit.Three connections: 1. Solid line: A 1 3 6 B with local VCIs 1,2,7,82. Dotted line: A …1…3…4 …5… D with local VCIs 5,3,4,5,23. Dashed line: C --- 2--- 4--- 3--- 6 B with local VCIs 6,3,2,1,5Reasons using local VCIs rather than global VCIs:1. searching for an available VCI is easier because of local uniqueness2. More available local VCIs, so there can have more connections7Incoming Outgoingnode VC node VC A 1 3 2 A 5 3 3 3 2 A 1 3 3 A 5Incoming Outgoingnode VC node VC 1 2 6 7 1 3 4 4 4 2 6 1 6 7 1 2 6 1 4 2 4 4 1 3Incoming Outgoingnode VC node VC 3 7 B 8 3 1 B 5 B 5 3 1 B 8 3 7Incoming Outgoingnode VC node VC C 6 4 3 4 3 C 6Incoming Outgoingnode VC node VC 2 3 3 2 3 4 5 5 3 2 2 3 5 5 3 4Incoming Outgoingnode VC node VC 4 5 D 2 D 2 4 5Node 1Node 2Node 3Node 4Node 6Node 5Figure 7.25Routing table for virtual-circuit packet switching network.8123456ABSwitch or routerHostFigure 7.23An example of a datagram packet-switch networkPaths: 1-3-6, 1-4-3-6, 1-2-5-6, …9 2 2 3 3 4 4 5 2 6 3Node 1Node 2Node 3Node 4Node 6Node 5 1 1 2 4 4 4 5 6 6 6 1 3 2 5 3 3 4 3 5 5Destination Next node 1 1 3 1 4 4 5 5 6 5 1 4 2 2 3 4 4 4 6 6 1 1 2 2 3 3 5 5 6 3Destination Next nodeDestination Next nodeDestination Next nodeDestination Next nodeDestination Next nodeFigure 7.26Routing table for datagram packet switching network10Hierarchical routing•Size of routing tables will become extremely large when network increases•Solution is: the hosts close to each other are assigned network addresses with the same prefixes. In a remote routing table, all these hosts are treated as one address, just one entry in the routing table. (only in the local routing table, these hosts are treated separately).•All packets towards to these hosts are forwarded to this area from remote area based on remote routing table and further forwards to the specific host based on local routing table. •Therefore hierarchical addressing.110000 0001 0010 00110100 0101 0110 01111100 1101 1110 11111000 1001 1010 1011R1R21254300 1 01 3 10 2 11 300 3 01 4 10 3 11 5(a)0000 0111 1010 11010001 0100 1011 11100010 0101 1000 11110011 0110 1001 1100R1R2125430000 1 0111 1 1010 1 … …0001 4 0100 4