CMPE 150 Introduction to Computer Networks Dr Chane L Fullmer chane cse ucsc edu Spring 2003 UCSC cmpe150 1 Homework Assignments Homework assignment 3 Chapter Four Due by May 22 Spring 2003 UCSC cmpe150 2 Thursday s Lecture Guest lecturer Dr Soumya Roy On Demand Link State Routing in Ad Hoc Networks Will speak on IP multicasting and related issues Yes his lecture will be on the exam Spring 2003 UCSC cmpe150 3 CMPE 150 Introduction to Computer Networks Set 12 Internet Routing Spring 2003 UCSC cmpe150 4 Internet Routing Protocols Intra domain routing RIP OSPF EIGRP Single path routing protocols static link costs Performance shortest path Inter domain routing Border Gateway Protocol BGP Single path Policy based Spring 2003 UCSC cmpe150 5 RIP v1 Based on DBF Used in small internets Problems Counting to infinity and looping single path routing link cost should be 1 or infinity Update specifies only a destination network and a distance to it hence no variable subnet masks are allowed in local internet and a static subnetting convention must be used for all routers Router sends its routing table to its neighbors every 30 sec or when it must update its routing table Runs on top of UDP Spring 2003 UCSC cmpe150 6 RIPv2 Adds the next hop to a destination and subnet mask in each update Variable subnets are allowed Performance does not improve much Spring 2003 UCSC cmpe150 7 OSPF Open Shortest Path First Dijkstra s SPF used to compute shortest paths locally based on topology map Flooding is used to disseminate topology maps Sequence numbers and age fields are used to validate link state updates Runs on top of IP and implements its own reliable transmission of link state updates Designated routers are used to reduce overhead within a LAN and areas connected by a backbone are used to reduce overhead across LANs HELLOs used to identify neighbors Spring 2003 UCSC cmpe150 8 OSPF A1 R R R A2 R R R R R R R backbone A3 not allowed A4 Areas must be connected by a connected backbone area 0 Spring 2003 UCSC cmpe150 9 OSPF A1 internal router R R R A2 R R Spring 2003 R R To other domains EA1 EA2 EAn R boundary router backbone router R area border router A3 UCSC A4 cmpe150 10 OSPF Areas need unique IDS an IP address Zero or more address ranges can be reached in an area Different types of routers have different views of topology End result is a hybrid of link state and distance information Spring 2003 UCSC cmpe150 11 Topology Information at Backbone Router R A2 A1 R EA1 R R EA2 EAn A3 Spring 2003 UCSC A4 cmpe150 12 Topology Information at Area Border Router A1 R R A2 R R R EA1 R R R EA2 EAn A3 Spring 2003 R UCSC A4 cmpe150 13 Topology Information at Internal Router A1 A2 R R EA1 R EA2 EAn UCSC R A4 A3 Spring 2003 R cmpe150 14 OSPF R R R R In a broadcast LAN designated router eliminates too many link state updates LSUs HELLOs and topology updates sent unicast to designated router which keeps all routers in LAN updated Spring 2003 UCSC cmpe150 15 Inter AS routing in the Internet BGP R4 R5 R3 BGP AS1 AS2 RIP intra AS routing OSPF intra AS routing BGP R2 R1 AS3 OSPF intra AS routing Figure 4 5 2 new2 BGP use for inter domain routing Spring 2003 UCSC cmpe150 16 BGP BGP Border Gateway Protocol the de facto standard for Internet inter AS routing Path Vector protocol Similar to Distance Vector protocol Each Border Gateway broadcast to neighbors peers entire path i e sequence of AS s to destination BGP routes to networks ASs not individual hosts e g Gateway X may send its path to dest Z Path X Z X Y1 Y2 Y3 Z Spring 2003 UCSC cmpe150 17 BGP Gateway X send its path to peer gateway W W may or may not select path offered by X cost policy don t route via competitors AS loop prevention reasons If W selects path advertised by X then Path W Z w Path X Z Note X can control incoming traffic by controlling its route advertisements to peers e g do not want to route traffic to Z do not advertise any routes to Z Spring 2003 UCSC cmpe150 18 Controlling Who Routes to You legend B W provider network X A Do not allow C customer network Y Figure 4 5 BGPnew a simple BGP scenario A B C are provider networks X W Y are customer of provider networks X is dual homed attached to two networks X does not want to route from B via X to C so X will not advertise to B a route to C Spring 2003 UCSC cmpe150 19 Controlling Who Routes to You legend B W provider network X A customer network C Y Figure 4 5 BGPnew A advertises to B thea simple pathBGP AWscenario B advertises to X the path BAW Should B advertise to C the path BAW No B gets no revenue for routing CBAW since neither W nor C are B s customers B wants to force C to route to W via A B wants to route only to from its customers Spring 2003 UCSC cmpe150 20 BGP Operation Receiving and filtering route advertisements from directly attached neighbor s Route selection To route to destination X which path of several advertised will be taken Sending route advertisements to neighbors Spring 2003 UCSC cmpe150 21 BGP Messages BGP messages exchanged using TCP BGP messages OPEN opens TCP connection to peer and authenticates sender UPDATE advertises new path or withdraws old KEEPALIVE keeps connection alive in absence of UPDATES also ACKs OPEN request NOTIFICATION reports errors in previous msg also used to close connection Spring 2003 UCSC cmpe150 22 Differences between Intra and Inter AS routing Policy Inter AS admin wants control over how its traffic routed who routes through its net Intra AS single administration so no policy decisions needed usually changing with traffic engineering Scale Hierarchical routing saves table size reduced update traffic Performance Intra AS can focus on performance Inter AS policy dominates over performance Spring 2003 UCSC cmpe150 23 Supporting Mobility in Routing Host moves and new connections are established Host moves and same IP address must be used Use DHCP to obtain a temporary new IP address Use mobile IP Hosts and routers move within the same domain I e ad hoc wireless nets Use ad hoc routing protocol Spring 2003 UCSC cmpe150 24 Routing in Ad Hoc Networks The problem addressed is host and router mobility IETF MANET Working Group is defining which approach to evolve into a standard Proposals On demand routing approaches DSR AODV TORA and many others Table driven and hybrid approaches STAR and approaches based on topology broadcast Spring 2003 UCSC cmpe150 25 On Demand Routing Routers maintain routing table entries for only those destinations that they need to reach
View Full Document
Unlocking...