CMPE 150 Winter 2009 Lecture 11 Februaryy 12 2009 P E Mantey CMPE 150 Introduction to Computer Networks Instructor Patrick Mantey mantey soe ucsc edu htt http www soe ucsc edu mantey d t Office Engr 2 Room 595J Office hours Tues 3 5 PM Mon 5 6 PM TA Anselm Kia akia soe ucsc edu Web site http www soe ucsc edu classes cmpe150 Winter09 Text Tannenbaum Computer p Networks 4th edition available in bookstore etc Syllabus Today s Agenda Routing continued Distance Vector Protocol Link State Routing Network Layer Hierarchical Routing g Broadcast Routing Spanning Tree Routing Congestion Control Quality of Service Internetworking Reading Assignment Today y Chapter p 5 sections 5 2 4 8 continued 5 3 5 4 1 5 4 3 Tuesday Tannenbaum Chapter5 section 5 5 5 6 Internet Protocol 5 6 Internet Layering Level 4 Application Layer rlogin ftp SMTP POP3 IMAP HTTP Transport Layer a k a Host to Host Level 3 Level 2 TCP UDP ARP ICMP etc Network Layer a k a a k a Internet IP Data Link Layer MAC sub layer Level 1 a k a a k a Network Interface or Network Access Layer Physical Layer Level 5 Distance Vector protocol Initialize routing table with local links Flood routing table to all routers Do Compute local routing table from graph Wait for update or link cost change or timer Update network graph If link cost change Flood updated link to all routers Else if timer expired Flood routing table to all routers Forever Distance Vector Routing a A subnet s bnet b Input Inp t ffrom om A A I I H H K K and the ne new routing table for J Distance Vector Routing 1 Each router keeps routing table or routing vector giving best known distance to each destination and the corresponding outgoing interface Routing tables are updated by exchanging routing information with neighbors Implements distributed version of Bellman Ford Aka Ford Fulkerson Timer based refresh vs neighbor tables Distance Vector 2 Routing table at each router One entry per participating router router Each entry contains outgoing interface and distance to corresponding destination Metric number of hops delay queue length Each router knows distance to its neighbors neighbors Old ARPANET algorithm DV where costt metric t i iis outgoing t i link li k queue length Also used in RIP Routing Updates Every T interval routers exchange routing updates R i update Routing d from f router X consists i off a vector with all destinations and the corresponding distance from X to them When router Y receives an update from X it can estimate its distance to router Z through X as Dyz Dyx Dxz Router Y receives update from all its neighbors discards its RT and builds a new one Distance Vector Example 3 2 5 2 1 3 1 2 1 3 1 6 9 4 7 5 2 N d Di Node Distance t Next N t 1 0 2 3 4 5 6 Node Distance Next 1 0 2 3 2 5 2 3 4 5 6 1 6 8 4 3 3 T T0 T T T T2 2 3 0 3 2 3 5 3 7 4 5 4 0 2 1 3 2 T T1 2 0 1 3 Distance Vector Example 3 2 5 2 1 3 1 2 1 3 1 6 9 4 7 5 2 N d Di Node Distance t Next N t 1 0 2 3 2 3 2 4 4 5 6 1 2 4 4 4 4 Node Distance Next 1 0 2 3 2 5 2 3 4 5 6 1 6 8 4 3 3 T T0 T T T T2 2 3 0 3 2 3 5 3 7 4 5 4 0 2 1 3 2 T T1 2 0 1 3 Problems Routing loops 2 Slow convergence 3 Counting to infinity 3 infinity 1 Bellman Ford overview Network represented by graph G V E V contains vertices i j E contains t i edges d i j i j Algorithm data structures s s sou source ce vertex e e dij cost of the edge i j dij if i j E Dhi cost of the shortest path with h hops from s to i Bellman Ford algorithm Dhs 0 for all h D0i for all i V i s h 0 Do h h 1 Dhj Min Dh 1i dij for all j V j s Until Dhi Dh 1i for all i V Bellman Ford illustrated B 2 2 2 6 E 1 E A 0 E 4 A 0 E4 E 4 2 D 12 F 6 A 0 H 8 H 10 C 9 E 4 A0 A 0 H 88 C 9 E 4 G 5 D 12 F 6 G 5 G B 2 D 10 F 6 D F F G 6 B 2 H 10 C 9 E 4 G 5 D H C 9 G 5 B 2 A0 A 0 3 F 2 F 4 G 6 B 2 A 0 3 2 C 9 B 2 C 7 D 10 F 6 H 8 Count to Infinity 1 A Initially A down A comes up B infinity 1 1 1 1 C D E infinity infinity infinity infinity infinity infinity 2 infinity infinity 2 3 infinity y 2 3 4 Good news propagates faster faster after 1 exchange after 2 exchanges after 3 exchanges g after 4 exchanges Count to Infinity 2 A Initially all up A goes down B C 1 3 3 5 5 7 7 2 2 4 4 6 6 8 D 3 3 3 5 5 7 7 infinity E 4 4 4 4 6 6 8 But bad news propagate slower after 1 exchange g after 2 exchanges after 3 exchanges after 4 exchanges after 5 exchanges after 6 exchanges Count to Infinity 3 Gradually routers work their way up to infinity infinity Number of exchanges g depends p on how large is infinity To reduce number of exchanges exchanges if metric is number of hops i fi it infinity maximum i path 1 th 1 Solution Routing loops Path vector record actual path used in the DV Previous hop p tracing g records preceding p g router Count to infinity Split horizon router doesn t report true route to next hop of the previous route p Poison reverse router infinity to next hop of previous route Split horizon with poison reverse prevent loops involving two routers Triggered updates if the metric for a route is changed send an update d t iimmediately di t l In the absence of other updates this solves the problem in reality other updates will keep hope alive RFC1058 is a good reference for these issues Split Horizon Tries to make bad news spread faster A node reports p infinityy as distance to node X on link packets to X are sent on Example in the first exchange C tells D its di t distance to t A but b t tells t ll B its it distance di t …
View Full Document
Unlocking...