CS551Unicast RoutingBill Chenghttp://merlot.usc.edu/cs551-f121 Computer Communications - CSCI 551 Copyright © William C. ChengRouting: process by which the forwarding table is builtand maintained:the forwarding tableForwarding: the process of moving packets from input tooutput based on:2Forwarding V.S. Routing Computer Communications - CSCI 551 Copyright © William C. Chengone or more routing protocolsprocedures (algorithms) to convert routing info toforwarding tableinformation in the packet destination IP addressTo forward unicast packets a router uses: 3Forwarding Examples Computer Communications - CSCI 551 Copyright © William C. Chenglongest matching prefix in forwarding tablesource + destination IP address and incoming interfaceTo forward multicast packets: longest and exact match algorithms4A Router And Its Components Computer Communications - CSCI 551 Copyright © William C. Chengline cardline cardline cardline cardline cardrouteprocessorinterconnect(backplane, crossbar, etc.)Cisco 7xxx Routerstatic: topologyRouting algorithms view the network as a graph5Factors Affecting Routing Computer Communications - CSCI 551 Copyright © William C. ChengProblem: find lowest cost path between two nodesFactorsdynamic: loadpolicy3ABC DEF1162194DV: Distance-vector protocols6Two Main Approaches Computer Communications - CSCI 551 Copyright © William C. ChengLS: Link state protocolsyou tell your neighbors what you know about everyoneyou tell everyone about your neighborsadaptiveEmployed in the early Arpanet7Distance Vector Protocols Computer Communications - CSCI 551 Copyright © William C. ChengDistributed next hop computationvector of distances to destinationsUnit of information exchangeDistributed Bellman-Ford AlgorithmAsynchronous, iterativeD X(Y,Z) : distance to Y via Z in node X’s distance table (Z isX’s direct neighbor)8Distance Vector Computer Communications - CSCI 551 Copyright © William C. Chengc(X,Z) : cost from X to X’s direct neighbor ZD X(Y,Z) = c(X,Z) + minw{D Z(Y,w)}where w is a direct neighbor of Zeach router advertises its current vector to allneighboring routersSend step:upon receiving vectors from each of its neighbors, routercomputes its own distance to each neighborReceive step:each router starts with a vector of distances to all directlyattached networksStart Conditions:9Distributed Bellman-Ford Computer Communications - CSCI 551 Copyright © William C. Chengthen, for every network X, router finds that neighbor whois closer to X than to any other neighborrouter updates its cost to X. After doing this for all X,router goes to send step if routing information haschanged10Example - Initial Distances Computer Communications - CSCI 551 Copyright © William C. ChengInfo atnodeA B C D E0 7 ~ ~ 17 0 1 ~ 8~ 1 0 2 ~~ ~ 2 0 21 8 ~ 2 0ABCDEAEBDC128 27111Example - Initial Distances Computer Communications - CSCI 551 Copyright © William C. ChengInfo atnodeA B C D E0 7 ~ ~ 17 0 1 ~ 8~ 1 0 2 ~~ ~ 2 0 21 8 ~ 2 0ABCDEAEBDC128 271c(D,E) = 212E Receives D’s Routes Computer Communications - CSCI 551 Copyright © William C. ChengInfo atnodeA B C D E0 7 ~ ~ 17 0 1 ~ 8~ 1 0 2 ~~ ~ 2 0 21 8 ~ 2 0ABCDEAEBDC128 27113E Updates Cost to C Computer Communications - CSCI 551 Copyright © William C. ChengInfo atnodeA B C D E0 7 ~ ~ 17 0 1 ~ 8~ 1 0 2 ~~ ~ 2 0 21 84 2 0ABCDEAEBDC128 271c(A,B) = 714A Receives B’s Routes Computer Communications - CSCI 551 Copyright © William C. ChengInfo atnodeA B C D E0 7 ~ ~ 17 0 1 ~ 8~ 1 0 2 ~~ ~ 2 0 21 84 2 0ABCDEAEBDC128 27115A Updates Cost to C Computer Communications - CSCI 551 Copyright © William C. ChengInfo atnodeA B C D E0 78 ~ 17 0 1 ~ 8~ 1 0 2 ~~ ~ 2 0 21 8 4 2 0ABCDEAEBDC128 271c(A,E) = 116A Receives E’s Routes Computer Communications - CSCI 551 Copyright © William C. ChengInfo atnodeA B C D E0 78 ~ 17 0 1 ~ 8~ 1 0 2 ~~ ~ 2 0 21 8 4 2 0ABCDEAEBDC128 27117A Updates Cost to C & D Computer Communications - CSCI 551 Copyright © William C. ChengInfo atnodeA B C D E0 75 3 17 0 1 ~ 8~ 1 0 2 ~~ ~ 2 0 21 8 4 2 0ABCDEAEBDC128 27118Final Distances Computer Communications - CSCI 551 Copyright © William C. ChengInfo atnodeA B C D E06 5 3 16 0 1 3 551 0 2 43 32 0 215 4 2 0ABCDEAEBDC128 27119View From a Node Computer Communications - CSCI 551 Copyright © William C. ChengInfo atnodeA B C D E0 6 5 3 16 0 1 3 55 1 0 2 43 3 2 0 21 5 4 2 0ABCDEABDC128 271EdestA B D1 14 57 856 9 44 11 2ABCDNext hopE’s routing table:20Final Distances After Link Failure Computer Communications - CSCI 551 Copyright © William C. ChengInfo atnodeA B C D E0 6 5 3 16 0 1 3 55 1 0 2 43 3 2 0 21 5 4 2 0ABCDEABDC128 271EdestA B D1 14 57 856 9 44 11 2ABCDNext hopE’s routing table:21Final Distances After Link Failure (Cont...) Computer Communications - CSCI 551 Copyright © William C. ChengInfo atnodeA B C D E0 6 5 3 16 0 1 3 55 1 0 2 43 3 2 0 21 5 4 2 0ABCDEABDC128 271EdestA B D1 14 57 856 9 44 11 2ABCDNext hopE’s routing table:destA B D115 58 8 59 9 411 11 2ABCDNext hopE’s routing table:Info atnodeA B C D E07 8 10 17 0 1 3 881 0 2 9103 2 0 111 8 9 11 0ABCDEABDC128 271E22Final Distances After Link Failure (Cont...) Computer Communications - CSCI 551 Copyright © William C. ChengdestAC13A31Cnp23The Bouncing Effect(a.k.a. Count to Infinity Problem) Computer Communications - CSCI 551 Copyright © William C. ChengA BC1150destBC12B5150CnpdestAB5051A21BnpdestAB5051A21Bnp5024The Bouncing Effect(a.k.a. Count to Infinity Problem) Computer Communications - CSCI 551 Copyright © William C. ChengA BC11destBC12B5150CnpdestAC13A31CnpdestBC12B5150CnpdestAC13A31Cnp25B Sends Routes to CC Updates Distance to A Computer Communications - CSCI 551 Copyright © William C. ChengA BC150destAB5051A21Bnp4destBC12B5150Cnp26C Sends Routes to BB Updates Distance to A Computer Communications - CSCI 551 Copyright © William C. ChengA BC150destAC13A31Cnp5destAB5051A21Bnp4destBC12B5150CnpdestAC13A31Cnp527B Sends Routes to CC Updates Distance to A Computer Communications - CSCI 551 Copyright © William C. ChengA BC150destAB5051A21Bnp4 6destBC12B5150CnpdestAC13A31Cnp5destAB5051A21Bnp4 628C Sends Routes to BB Updates Distance to A Computer Communications - CSCI 551 Copyright © William C. ChengA BC150This is known as the count to infinity problem7B’s metric increasesObservation 1:29How Are These Loops Caused? Computer Communications - CSCI 551 Copyright © William C. ChengC picks B as next hop to AObservation 2:But, the implicit path from C to A includes itself!in our example, B delays advertising routeIf
View Full Document
Unlocking...