DOC PREVIEW
MIT 6 263 - Internet Routing

This preview shows page 1-2-3-4-26-27-28-53-54-55-56 out of 56 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 56 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

BooksLecture 3: Internet Routing (The real picture) (Notes. Also you can find the material in P&D 4.2 except 4.2.5, 4.3.1, 4.3.2, IP Addresses & IP HeaderForwardingPicture of the InternetTwo Main Approaches to Intra-domain Routing Distributed Bellman-Ford AlgorithmDistributed Bellman-Ford AlgorithmDistributed Bellman-Ford AlgorithmDistributed Bellman-Ford AlgorithmFormallyA Problem with Bellman-FordA Problem with Bellman-FordHow are These Loops Caused?Counting to Infinity Problem SolutionsTwo Main Approaches to Intra-domain Routing Link StateDijkstra’s Shortest Path First AlgorithmInter-Domain Routing & BGPPicture of the InternetInternet HierarchyAS Numbers (ASNs)A Logical View of the InternetInter-AS Relationship: Transit vs. PeeringPolicy Impact on RoutingCustomer-Provider HierarchyThe Peering RelationshipPeering Provides ShortcutsPolicy-Based RoutingBGP: Distance Vector with PathBGP Operations (Simplified) Four Types of BGP MessagesImplementing Customer/Provider and Peer/Peer relationships using BGPImporting RoutesExporting RoutesImport Routes Export Routes An instance of the Stable Paths Problem (SPP)An SPP may have multiple solutions BAD GADGET : No Stable SolutionKnown ResultsTwo Types of BGP Neighbor RelationshipsiBGPInternal BGP (iBGP)We learned6.263 Data Communication NetworksDina [email protected]/~dinaLecture 3: Internet Routing(some slides are taken from I. Stoica and N. Mckewon & T. Griffin)2BooksText Book Data Communication Networks, by DimitriBetsekas and Robert GallagerRecommended Computer Networks - A Systems Approach, by Larry L. Peterson and Bruce S. Davie, 3rdedition.3Lecture 3: Internet Routing (The real picture) (Notes. Also you can find the material in P&D 4.2 except 4.2.5, 4.3.1, 4.3.2, 4.3.3. For algs., see B&G-5.2.3)Lecture 1: Taxonomy of Networks(Mainly notes. Reading: P&D 3.1 pp. 164-180 )Lecture 2: Routing AlgorithmsBertsekas and Gallager4IP Addresses & IP Header¾ IP address: e.g., 18.26.0.1¾ IP prefix: • e.g., 18/8 contains 224addresses• e.g, 18.26/16 or 18.26.0/24ECNversionheaderlengthDS total length (in bytes)Identification Fragment offsetsource IP addressdestination IP addressoptions (0 to 40 bytes)payload4 bytestime-to-live (TTL) protocol header checksumbit # 0 15 23 248317160MFDF5Forwarding What’s the difference between routing and forwarding?¾ Routing is finding the path¾ Forwarding is the action of sending the packet to the next-hop toward its destination  Each router has a forwarding table¾ Forwarding tables are created by a routing protocol Forwarding:¾ When a packet arrives, • router looks up the dst. IP in the forwarding table• finds nexthop• queues packet to be sent on the interface connected to nexthop Forwarding needs to be fast18.2/1619.26/165.1.1/24137/818/8Dest. AddrR2R1R3R2R1Next-hop18.2/165.1.1/2419.26/1618/8137/8R2R3R1Router6Picture of the Internet Internet: A collection of Autonomous Systems (ASes)¾ E.g., MIT network, AT&T, Quest, Sprint, … Routing is hierarchical¾ Intra-Domain Routing inside an AS¾ Inter-Domain Routing between ASesAS-1AS-2AS-3Interior routerBorder router7Two Main Approaches to Intra-domain Routing  Distance Vector Protocols¾ E.g., RIP¾ Based on Distributed Bellman-Ford Algorithm¾ Periodically, each node tells its neighbors about its shortest route to all other nodes in the network  Link State Protocols¾ E.g., OSPF¾ Based on Dijkstra Algorithm¾ Periodically, each node tells all nodes about its neighbors (it floods that information)8Distance Vector: Control Traffic When the routing table of a node changes, the node sends its table to its neighbors A node updates its table with information received from its neighborsHost AHost BHost EHost DHost CN1N2N3N4N5N7N69Distributed Bellman-Ford AlgorithmR5R3R7R8R6R4R2R1Example: Compute routes to R81142422323∞∞∞∞∞∞∞Initial State: All routers except R8 set their route length to ∞. R8 sets its route length to 0.010Distributed Bellman-Ford AlgorithmR5R3R7R8R6R4R2R11122323424∞∞∞R1InfR2InfR34, R8R4InfR52, R8R62, R8R73, R84232Example: Compute routes to R8 Every T seconds, each router tells its neighbors its lowest-cost to R8 When a router receives a message from neighbor j, it updates its path cost as: If (j is my current nexthop) then cost= j’s cost to R8 + cost of the link to j else cost =min(current cost, j’s cost to R8 + cost of the link to j)Note, routing tables at each router have both the next-hop and the costIterative step:11Distributed Bellman-Ford AlgorithmR5R3R7R8R6R4R2R11122323424R16, R3R24, R5R34, R8R46, R7R52, R8R62, R8R73, R84232646Example: Compute routes to R8Repeat until no costs change12Distributed Bellman-Ford AlgorithmR5R3R7R8R6R4R2R11122323424R16, R3R24, R5R34, R8R46, R7R52, R8R62, R8R73, R84232646R5R3R7R8R6R4R2R11422232R16, R3R24, R5R34, R8R45, R2R52, R8R62, R8R73, R84232645SolutionExample: Compute routes to R813Formally7 loop:8 wait (link cost update or update message)9 if (c(A,V) changes by d) 10 for all destinations Y through V do11 D(A,Y) = D(A,Y) + d12 else if (update D(V, Y) received from V) 13 for all destinations Y do14 if (destination Y through V)15 D(A,Y) = c(A,V) + D(V, Y);16 else17 D(A, Y) = min(D(A, Y), c(A, V) + D(V, Y));18 if (there is a new minimum for destination Y)19 send D(A, Y) to all neighbors 20 forever1 Initialization:2 for all neighbors V do3 if V adjacent to A4 D(A, V) = c(A,V); 5 else6 D(A, V) = ∞; At router A, assume c(A,V) is the cost of the edge A-V and D(A,V) is the cost of the path from A to V14A Problem with Bellman-FordR4R3R2R1111Consider the calculation of distances to R4:“Bad news travels slowly”3211, R42,R33,R20R3R2R1TimeX3,R22,R33,R2R3ÆR4fails15A Problem with Bellman-FordR4R3R2R111Consider the calculation of distances to R4:“Bad news travels slowly”……5,R24,R35,R23211, R42,R33,R20R3R2R1Time……“Counting to infinity”3,R22,R33,R2R3ÆR4fails3,R24,R33,R216How are These Loops Caused? Observation 1:¾ R3’s metric increases Observation 2:¾ R2 picks R3 as next hop to R4; But, the implicit pathfrom R2 to R4 includes R3!17Counting to Infinity ProblemSolutions1. Set infinity = “some small integer” (e.g. 200). Stop when count = 200.2. Split Horizon: Because R2received lowest cost path from R3, it does not advertise cost to R33. Split-horizon with poison reverse: R2advertises infinity


View Full Document

MIT 6 263 - Internet Routing

Download Internet Routing
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Internet Routing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Internet Routing 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?