cs398 Lecture Notes Spring 2000 Week 9, Tuesday For today, you should have read Sections 4.1 and 4.2 and written answers for questions 2, 3, 6, 8 and 9 on pages 354-355. For next time, read Sections 4.2 and 4.3 and answer questions 12, 14 and 15. Also, answer the question that appears below in the recurrence relation section. We will have a quiz on Thursday, probably on the topic of something in Section 4.2, but possibily including material from Section 4.3. Wednesday: cs fete! Recurrence relations -------------------- In the spirit of Math-on-demand, here's a few tips about recurrence relations. See Sedgewick, pages 76-78. Problem for next time: Given the following recurrence relation: f(n) = a f(n/2) + b lg n f(1) = f1 Assume that there is a solution of the form: f(n) = c n lg n + d lg n + en Find a general solution by plugging the assumed solution into the recurrence and solving for c, d and e in terms of a, b, and f1. Is there some condition on a, b, and f1 that is required in order for this functional form to solve the recurrence relation? ARP --- Translate the IP address and encapsulate the IP packet One possibility is to use physical addresses as the host part of the IP address, but that's not generally possible. Instead, each host maintains a table. 1) updated dynamically 2) entries time out after about 15 minutes 3) if you don't know, broadcast If you get an ARP query, you (incidentally) find out the physical address of the sender. 1) if the sender is already in your table, refresh 2) if the sender is asking about you, reply, and also add an entry to your table (on the assumption that you will need it soon) 3) otherwise, do nothing ATMARP ------ Divide net into subnets. Each subnet gets an ARP server. Each node configured with physical address of ARP server. Everyone has a VC to the ARP server. Everyone registers with the ARP server when they create their VC. Server answers all ARP queries. DHCP ---- Dynamic host configuration protocol Can't allocate IP addresses at manufacture time. (Why not?) Have to configure upon installation on a network. In addition to their own IP addresses, hosts need to be configured with the IP address of a default server. Administrator can assign addresses and configure manually. Alternative: 1) create a DHCP server somewhere on the network (in this case, think campus-wide) 2) on startup, host broadcasts DHCPDISCOVER on its subnet if DHCP server is on the subnet, it replies otherwise, a DHCP relay on the subnet relays (by unicast) the message to the DHCP server (it knows the IP address) 3) DHCP might have a table of static IP addresses, in which case it will look up the physical address of the sender otherwise it will choose an IP address dynamically from the range of available addresses This makes things more manageable, mostly. Problem: IP address of a given host changes more often than might be desireable, especially if this host provides a service of some kind (like web pages) There might be bad interactions with DNS, about which more later. ICMP ---- Internet Control Message Protocol Something goes wrong, routers (or recipients) can send messages back to sender 1) host unreachable! 2) reassembly failed! 3) ttl = 0, time expired! 4) checksum failed! Quick note: both DHCP and ICMP use UDP, which is a protocol that runs on top of IP, so we are getting just a little ahead of ourselves, but that's ok. Virtual private networks ------------------------ You might not want everyone to be able to send packets to you from a shared link. On nets that support VC, this is easy to do. You just configure your router to refuse to create VCs from addresses you don't like. Tunnel ------ In IP land (no virtual circuits), we can get some of the same behavior with tunnels. Tunnel entrance takes incoming packets, encapsulates them and sends them to the other end. Tunnel exit unwraps the packets and delivers them locally. Tunnel exit can restrict access to local network by refusing to unpack packet from undesireables, or packets that aren't wrapped at all. Benefits: 1) privacy, security 2) multicast: multicast packet travels through non-multicast intermediate network incognito 3) non-IP protocols over IP (similar to above) Downside: 1) space overhead, time on router overhead 2) management 3) confounds path discovery, since intermediate routers don't decrement ttl of inner packet Section 4.2 ----------- Routing... See the table on page 266. How did it get built? Building the table is routing. When you hear routing, think, "building routes," which means "building routing tables." You can't route a packet. You can forward a packet using a routing table that got built by the routing mechanism. (What information is in the forwarding table that is often not in the routing table?) (Why might/should be routing table and the forwarding table be different data structures?) Fundamental problem with decentralized algorithms -- possibility of inconsistent state... I think you have the fastest route to the dest; you think I do. We keep handing the packet back and forth. Best we can promise is that this situation will resolve itself in a reasonable amount of time. 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. (What is the error in the book?) Link state (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 Ultimately, neither of these algorithms scales well, which is why we need Section 4.3: Global Internet.