cs398 Lecture Notes Spring 2000 Week 9, Thursday For today you should have read Sections 4.2 and 4.3 and answered questions 12, 14 and 15. You should also have solved the recurrence relation that was in notes14.txt Quiz today! For next time, please download, print and read the fine paper "End to End routing behavior in the Internet" by Vern Paxson. It appeared in IEEE/ACM Transactions on Networking, Vol.5, No.5, pp. 601-615, October 1997. You can get it from http://rocky.colby.edu/cs398/handouts/ Distance vector routing (RIP) ----------------------------- Everyone knows who their neighbors are and their cost, which is one. Distance to non-neighbors is initially infinity. Periodically, everyone sends that information to their neighbors, who update their own table. Eventually, the system converges (everyone has a consistent view of the topology and knows the shortest distance to everyone). Updates are periodic (seconds to minutes) and triggered (tell your neighbors if something changes). How might a node detect that one of its neighbors (or the intervening link) has failed? What does it do in that case? In the graph on page 284, if E goes down, A sends messages to everyone. If B gets the message before C, and C sends an update to B before B gets the message from A, all heck breaks loose. Link state routing (OSPF) ------------------------- Instead of everyone telling the neighbors everything they know, everyone tells everyone only what they know well! Then everyone has global information and they can use global algorithm to find minimal paths. Problem: how can you multicast when you have not yet got routes established? Answer: reliable flooding. 1) send to all your neighbors. 2) they send to all of theirs, and so on. 3) packets have sequence numbers, so you only pass on new ones. 4) every connection is reliable (uses ACKS) Total amount of traffic is more, per update, but updates need to happen less often, since convergence is fast and reliable. Once hosts have global info, they use Dijkstra's shortest path algorithm. Downside: 1) amount of info stored at each router is large Example: graph on page 296, starting from B Proof of correctness. Ultimately, neither of these algorithms scales well, which is why we need Section 4.3: Global Internet. Metrics ------- So far, we have been using costs = 1, which means we are choosing the shortest path in number of hops, but that is not necessarily best. Neither is the first draft of ARPANET 1) cost = queue length 2) cost = average delay of the last few packets delay = latency + transmit time + (depart - arrival) latency, in this context, means the fixed part of the time it takes to send a packet, regardless of size transmit time is the variable part of the time it takes to send a packer, depending on size (depart - arrival) is usually queue delay, but also includes timeouts and resend times Latency and transmit time are static, (depart - arrival) is updated periodically (presumably when we recompute routes). I assume that transmit time is based on some average packet size. 3) total hack! What is instability? On one level is means that routes are changing more than you want. The more interesting meaning is that routes oscillate forever and never converge. COMPRESS effect of queue delays to reduce the appeal of long paths SMOOTH by replacying delay with utilization, and averaging over a longer period of time, and bounding rate of change over time. This supposedly reduces instability. SIMPLIFY STATIC INFO instead of latency and transmit time, just look at the type of the link -- in other words, the precomputed functions on page 303 take into account the link characteristics. Empricial Internet Behavior --------------------------- The box on page 304 describes an interesting phenomenon. Although the Internet is made up of deterministic, man-made pieces, the system as a whole cannot be understood using the conventional tools of reductionism. It is best treated as a complex system, which means 1) it is made up of multiple components 2) the interactions of those components contribute something essential to the behavior of the system, making it impossible to understand the system by looking at the parts in isolation. complex != complicated complex means made up of multiple components, not monolothic therefore, you either are or aren't; there's no "so complex..." complicated has an underlying element of human confusion, which comes in degrees, as in "the system is so complicated that we can't make good predictions about it" Alternatively, "the system is complex, so the best way to make predictions about it is to model the components and also the interactions among the components." Let's read Paxson's paper! Let's skip routing for mobile hosts Global Internet --------------- Two problems 1) routing algorithms don't scale up to 10,000 networks routers might have 10,000 entries! 2) address allocation is getting tight Subnetting ---------- You might have noticed that I have been vague for the last week about what I mean by a network. Is it a single Ethernet on a campus or is it the whole campus. The answer is that from the point of view of a router that is off campus, the entire Colby campus is one network. So all traffic headed for Colby is going to go to the same place, which is fine becauce 1) there is only one way to get here anyway, and 2) even if there were more than one way, any will do. Once the packet gets onto campus, OUR routers use additional bits of the "host" part of the address to forward the packet to the right subnet (which usually corresponds to a physical network). We can use as many bits as we want, even non-contiguous bits (although the latter is a bad idea). The subnet mask indicates which bits it is. Only the routers (and host) in our domain need to know which part of our IP addresses idenifies the subnet. Why do hosts have to know the subnet mask? Can have more than one physical network per subnet! (we saw this in Chapter 3 -- bridges forward from one physical network to another) Can have more than one subnet per physical network! (this just means that hosts that are actually on the same network will think they are not and send packets through the router when they don't have to) There are several good things about subnetting, but the biggest benefit is that it greatly reduces the amount of information off-campus routers need to have about our network. CIDR ---- Classless interdomain routing. We have already blurred the line between the network part of an IP address and the host part. CIDR does the same thing, except in the other direction. If you (a router) use only a prefix of the network part, and ignore the low order bits, you are effectively aggregating a bunch of networks. Anything that starts with 137.0011 is going to the same place. If you hand out IP addresses in clever ways, you can make this work. For example, give a set of contiguous, power-of-two addresses to a network servive provider and let them hand out network addresses to customers. For the point-of-view of other networks, you can send packets for any of MCIs customers to the same place. This is sometimes called supernetting, since you are taking a bunch of network and treating them as one big unit. CIDR prefixes can be any length. Routers match IP addresses with entries in the forwarding table by choosing the longest prefix match. There might be something like: For example, maybe Denmark is one big supernet, but it includes networks in Denmark but also in Greenland. A router in Reykjavik might have entries that say... Anything going to Denmark, send it here. Except things in Greenland (a Danish colony), which go somewhere else. BGP --- That's still not good enough. Even with CIDR, there are still something like 50,000 prefixes out there that every router would have to know (and that was a couple of years ago). 1) the world is broken into AUTONOMOUS SYSTEMS. Forget about getting packets to the right network; just get them to the right AS. 2) most AS don't participate in interdomain routing, so that simplifies the routing process if not the forwarding process (we can assign a unique ID to all the transit AS) 3) forget about minimal paths, just try to get a loop-free path 4) appoint only one router in each AS to participate in routing -- the speaker 5) when you advertise a path, advertise the complete path so that someone deciding whether to use it can check for loops. 6) withing each AS, aggregating works well because finding a good path means finding the right border router, and there usually aren't that many per AS Injection --------- In a stub AS, all the routers know that the border router is the default router. (I don't understand why the book indicates that this information is injected by the border router into the intradomain routing process.) In a multihomed AS, is it actually useful for the border routers to advertise routes (with local costs) to the other routers in the domain, so that internal routers can choose the best border router for a given destination from a given place in the AS. In a transit AS, you might want to use IBGP, which uses BGP to identify the best border router and intradomain routing to get there. Next time: IPv6!