Massachusetts Institute of TechnologyDepartment of Electrical Engineering and Computer Science6.829 Fall 2005 Problem Set 2 September 22, 2005This problem set has 3 questions, most with multiple parts. Answer them as clearly and concisely aspossible. You may discuss ideas with others in the class, but your solutions and presentation mustbe your own (for each such discussion, please mention whom you collaborated with). Do not lookat anyone else’s solutions or copy them from anywhere (in particular, “bibles” are not allowed).Turn in your solutions on Thursday, September 29, 2005 in class.1 Route reflectionThe Border Gateway Protocol (BGP) has two modes of operation. eBGP runs between the border(or egress) routers of ASes to exchange reachability information between ASes. iBGP runs withinan AS to disseminate the information about external destinations (learned through eBGP) amongstrouters within an AS.We define two correctness properties that are desirable in any intra-AS route dissemination mech-anism.P1 Complete visibility: The dissemination of information amongst the routers is “complete”in the sense that, for every external destination, each router picks1the same route that itwould have picked had it seen the best routes from each eBGP router in the AS.P2 Loop-free forwarding: After the dissemination of eBGP learned routes, the resulting routes(and the subsequent forwarding paths of packets sent along those routes) picked by all routersare free of forwarding loops.1. To solve the intra-AS route dissemination problem, the designers of BGP proposed the useof a “full mesh” iBGP configuration. Here, each eBGP router in the AS establishes BGPsessions with all the other routers (both eBGP routers and internal routers) in the network.Show that the full mesh iBGP configuration always satisfies P1 and P2. (Assume there areno link or router failures in the network. Also assume that the underlying IGP implementsshortest path routing. )2. The full mesh iBGP does not scale well because it requires a quadratic number of iBGPsessions. Route reflection improves the scalability of intra-AS route dissemination. Refer L4notes for information on how route reflection works.iBGP configurations with route reflectors do not necessarily satisfy P1 and P2. Consider theiBGP configuration shown in Figure 1. R1 and R2 are route reflectors and are iBGP peers ofeach other. C1 and C2 are route reflector clients of R1 and R2 respectively. The IGP costsof the network are marked on the links in the figure. Two routes to an external destinationd, which are equally good with respect to the local preference, AS path length and MED1Figure 1: iBGP configuration with route reflectorsattributes, arrive at the routers R1 and R2. Under this situation, show that the given iBGPconfiguration violates properties P1 and P2.3. Suppose the route reflectors R1 and R2 are modified so that they forward not just theirbest route but all the routes they hear to (and from) their clients. Show that, under thismodification, this iBGP configuration satisfies the properties P1 and P2.4. Consider an iBGP configuration which has the following property:2For every router A andevery egress router B, one of the following conditions always holds (a) A is a route reflectorand B is a client of A. (b) B is a route reflector and A is a client of B (c) A and B are normaliBGP peers (d) there exists a route reflector R on the shortest path between A and B suchthat both A and B are clients of R. Show that such an iBGP configuration satisfies P1 andP2.2 Understanding BGP using table dumpsFor this question, you will need to download the Routeviews routing table from http://nms.csail.mit.edu/6.829/ps/ps2/oix-full-snapshot-2005-09-20-2200.dat.gzThis file contains a Cisco BGP-4 routing table snapshot, taken at Oregon Route Views (http://www.routeviews.org/) on September 20, 2005. If you are curious about what other snapshotslook like, you can find daily snapshots at http://archive.routeviews.org/. You can also find thepeering structure of the Routeview router at http://www.routeviews.org/peers/route-views.oregon-ix.net.txt.1. To start with, find the routing table entry for the MIT network (which corresponds to theprefix 18.0.0.0/8).(a) From the routing table file, what is the AS number for MIT?(b) What is the IP address of the best next hop from this router to MIT? How does thisrouter know how to reach that next hop IP address?1Refer to L4 notes for details on the BGP route selection process.2Do not worry about how the iBGP should be configured so that this property is satisfied.2(c) How many AS’s must a packet traverse between the time it leaves the router and thetime that it arrives at MIT?(d) Use traceroute now to trace the route from MIT to the router that took the snapshot.Is the current route from MIT to the router the same as the reverse route in the tracedata?(e) On September 20, 2005 the AS path to route-views.oregon-ix.net from MIT was10578 11537 4600 3582. Why is this path not simply the reverse of the path advertisedby MIT to Routeviews? Why does this traceroute (which was run at the same time),not match the AS path?traceroute to route-views.oregon-ix.net (128.223.60.103), 30 hops max, 38 byte packets1 legacy31.default.csail.mit.edu (18.31.0.1) [AS3] 0.430 ms 0.371 ms 0.370 ms2 kalgan.trantor.csail.mit.edu (128.30.0.245) [AS40] 0.401 ms 0.408 ms 0.400 ms3 B24-RTR-2-CSAIL.MIT.EDU (18.4.7.1) 7.190 ms [AS3] 0.830 ms 1.092 ms4 EXTERNAL-RTR-1-BACKBONE.MIT.EDU (18.168.0.18) [AS3] 3.714 ms 0.942 ms 0.764 ms5 EXTERNAL-RTR-2-BACKBONE.MIT.EDU (18.168.0.27) [AS3] 0.829 ms 0.692 ms 0.755 ms6 nox230gw1-Vl-526-NoX-MIT.nox.org (192.5.89.89) [(null)] 5.305 ms 0.783 ms 0.609 ms7 nox230gw1-PEER-NoX-NOX-192-5-89-10.nox.org (192.5.89.10) [(null)] 6.119 ms 9.434 ms 6.083 ms8 chinng-nycmng.abilene.ucaid.edu (198.32.8.82) [(null)] 26.016 ms 39.404 ms 26.142 ms9 iplsng-chinng.abilene.ucaid.edu (198.32.8.77) [(null)] 270.931 ms 281.590 ms *10 kscyng-iplsng.abilene.ucaid.edu (198.32.8.81) [(null)] 50.490 ms 39.170 ms 39.077 ms11 dnvrng-kscyng.abilene.ucaid.edu (198.32.8.13) [(null)] 49.970 ms 49.781 ms 49.803 ms12 snvang-dnvrng.abilene.ucaid.edu (198.32.8.1) [(null)] 74.424 ms 74.614 ms 74.453 ms13 pos-1-0.core0.eug.oregon-gigapop.net (198.32.163.17) [AS4600] 86.717 ms 86.726 ms 86.792 ms14 uo-0.eug.oregon-gigapop.net (198.32.163.147) 89.333 ms [AS4600] 110.026 ms 102.835 ms15 ge-5-1.uonet1-gw.uoregon.edu (128.223.2.1) [AS3582] 87.760 ms 86.942 ms