cs398 Lecture Notes Spring 2000 Week 11, Thursday These are the notes for the fictitious lecture I didn't get to deliver on Thursday. They include the exam solutions and the second half of the discussion of end-to-end protocols. Exam solutions -------------- (4 points) What is the approximate bandwidth of this link? You may assume that the one-way transmission time is one half of the measured round trip time. The slope of this line shows the number of additional milliseconds per byte, on the margin. Inverting the slope yields the bandwidth in Bytes/ms, which can be converted to 1.6 Mbps. In fact, this data does not come from a single link, but from the first six hops of a path. (4 points) Why does IP use a simple checksum for error detection rather than the more powerful CRC? Because IP operations are usually implemented in software, unlike the lower-level protocols we have seen, which are usually implemented in hardware. A checksum is easier to implement in software that CRC. (4 points) What is the maximum number of interfaces (hosts) in the world at any given time that have Class C addresses? There are 2^21 Class C networks, each of which can have approximately 2^8 = 256 hosts. The total number of interfaces is roughly 2^29. Actually, host numbers 0 and 255 are forbidden, so the real number is about 1% smaller. (4 points) Under ATMARP, how does the ARP server learn the physical network addresses of the hosts in its subnet? At boot time, each host opens a virtual circuit to the ARP server. That's how the server learns the network and physical addresses of each host in its subnet. (4 points) Why is it possible for a manufacturer to give an interface a unique network address, but not possible for the manufacturer to give it an IP address at the same time? IP addresses contain the address of the network to which the host is connnected. There is no way the manufacturer can know what network a given card will be connected to. On the other hand, physical addresses only need to be globally unique; they don't have to be hierarchically aggregatable. (4 points) The ttl field of an IP header is supposed to limit the number of hops the packet can traverse, but there are circumstances in which a packet will traverse more than the specified number of hops. Explain one such circumstance at an appropriate level of detail. If the packet goes through a tunnel, it will be wrapped up inside another IP packet. While it is wrapped up, the ttl of the wrapper packet is decremented, but the ttl of the inner packet is not. (4 points) Use Dijkstra's algorithm to find the shortest route between B and the other nodes in this graph. You may draw your answer neatly on the graph. In OSPF, why do the update packets have to have sequence numbers? The receiver needs to know whether it has seen an update packet before so that (1) it knows whether to update its routing tables, and (2) it knows whether to forward/broadcast the packet to its other neighbors. Does the revised ARPANET routing metric (the third version we looked at) take into account the latency and bandwidth of the links? If so, how? If not, why not? The "squashing" functions that map utilization to cost take into account the type of the link, which includes information about its latency and bandwidth. *IPv6 (4 points) IPv6 addresses are so big that it is often possible to use the network address of an interface as the host part of its IP address. What effect does this design have on ARP? On any network that implements this policy, ARP is unnecessary, since you can generate a physical address just by stripping the header of the IPv6 address. (4 points) What does it mean to say that a set of addresses is ``aggregatable''? It means that if two addresses share a common prefix, they must share a common route. If this is true for multiple prefix sizes (as in CIDR) then we would say the addresses are _hierarchically_ aggregatable. (4 points) IPv6 addresses are 4 times bigger than IPv4 addresses, but an IPv6 header is only twice as big as an IPv4 header. Why? IPv6 deliberately leaves out some features of IPv4 in order to reduce the size of the headers (example: checksum) Also, it moves some features out of the header and into extension headers (examples: options, fragmentation info). *Switches (4 points) Suppose that we are using a shared-media switch to implement an 8x8 switch for OC3 links, which have a bandwidth of 155 Mbps. How fast does the memory bus have to run? 8 * 155 Mbps = 1240 Mbps = 1.24 Gbps (4 points) Assuming that the memory bus is fast enough to keep up with the links, what other part of the system is likely to limit the performance of the switch? The control logic. (4 points) Which traffic pattern would allow this switch to achieve better throughput, lots of small packets or lots of large packets? Why? Lots of small packets would require more work for the control logic (probably dominated by allocating and deallocating buffers). So large packets would yield the best throughput. Remember, throughput is measured in bits per second, like bandwidth, but it is not the same thing as bandwidth. In the context of a switch, the throughput depends on the number of packets per second that can be switched and also on the size of those packets. (4 points) Let's say we replace this switch with a banyan switch. How fast would the connections between the switching elements inside the banyan have to run? The interconnect only has to run as fast as the links, 155 Mbps. (4 points) What traffic pattern would tend to make the performance of the banyan network pessimal? All the incoming traffic going to the same output port. That causes contention at the output port and also in the switching elements. (4 points) What conditions are necessary in order to guarantee that there will be no collisions inside a banyan network? Two requirements: the packets must be presented in ascending order, and the also must all be destined for different ports. Connection ---------- Passive open: socket listen (anyone) Active open: socket connect (name other party) Three way handshake 1) SYN (starting sequence number) 2) SYN (starting sequence number), ACK (next expected number) 3) ACK (next expected number) Why not start with sequence number 0? State transition diagrams are an important tool for software design. Study this one carefully. Work through the examples. See how many bugs you would not have thought of if you didn't use this diagram. (paragraph on the top of page 383) Sliding Window -------------- Sender: last byte acked, last byte sent, last byte written Receiver: last byte read, next byte expected, last byte received Receiver throttles the sender by advertising a window that is no larger than the amount of data it has buffer space for. Sender is allowed to send Advertised window - unacknowledged bytes in flight When receiver advertises 0 window length, sender must stop. But only ACKs contain window advertisements. (So how do we get started again?) (What is the underlying design principle here?) (Can anyone think of a reason for it?) Wraparound ---------- Have to make sure we don't send 4 billion segments in less than 120 seconds (what's 120 seconds?) OC12 can easily do this. Ouch! (Are they neglecting headers?) Anyway, we can fix the problem by using the timestamp field as additional sequence number high-order bits. One of the problems for next time addresses this. Advertised window ----------------- 16-bit advertised window only allows 64 KB in flight. Can't keep even moderate pipes full! Transcontinental T3 has delay-bandwidth = 549 KB (What's the solution?) (What else have we seen that looks like this?) Adaptive retransmission ----------------------- Why is it important to get this right? 1) Delays indicate contention. If you retranmit whenever there is a delay, you are contributing unnecessary additional load at the worst time. 2) Timeouts are used for congestion control (Chapter 6). Important not to overreact. How to choose retranmit time adaptively 1) running average of RTT newAvg = alpha * oldAvg + (1 - alpha) * sampleRTT This is a standard technique for running averages. alpha -> 0 means use the more recent sample alpha -> 1 means we ignore new data Something like 0.825 works well. Why? Timeout = 2 * newAvg (What's the factor of 2 for?) 2) Karn/Partidge Apparently you can get you name on something just by suggestion that when you have to do a retransmit, you don't count it as a sample. 3) Jacobson/Karels Deviation matters! If all measured RTTs are the same, then there is no reason for the arbitrary factor of 2. If the deviation is high, you might want to wait extra long. Estimate cumulative deviation along with cumulative average. (There are lots of hackish ways to do this approximately) timeout = average + phi * deviation Phi is something like 4 Record boundaries ----------------- Apparently TCP supports some ways of telling the receiver where the breaks are in the data, but I don't think anyone uses them because they are not provided by the API, at least not in a very friendly way. Besides, its easy to put this info into the data stream itself. The next message is 25 bytes long. Here is the next message. The next message is 8 bytes long. Bite me. Taxonomy of end-to-end protocols -------------------------------- byte-stream vs. request-reply reliable vs. unreliable What are the cons of byte-stream? 1) setup-breakdown overhead (matters more for short transactions) this topic will be back when we talk about HTTP 2) no record boundaries (but we just said that it's easy to do this at the application level -- in fact, the Java socket API does it for you, I think) What are the advantages? 1) no upper bound on message size (do we buy this? -- see page 396) 2) setup gives the reciever a chance to reject before the sender sends data (do you get the sense this section is really desperate?) Rate control versus window control -- more foreshadowing of Chapter 6.