cs398 Lecture Notes Spring 2000 Week 8, Tuesday For today, if I remember right, you had no assignement. For next time you should start reading Chapter 4. Do a high-level skim and write an outline if you are so inclined. Also, please write answers for questions 29, 30 and 35 on page 243. Exam 2 Solutions ---------------- For all short-answer questions on this exam, please write complete, grammatically-correct, clear, concise, unambiguous English sentences. For questions with numerical answers, show your calculations and write your answers clearly and with appropriate units. *Part One: ATM (4 points) Name one advantage and one disadvantage of of fixed size packets (cells) compared to variable length packets. Advantage: easier to design _switch_ hardware better queueing behavior (less jitter) (not necessarily any decrease in _mean_ delay) Disadvantage: header overhead _might_ be larger padding overhead for small messages (4 points) Name one advantage and one disadvantage of of large cells compared to small cells. Advantage: large cells reduce per-byte header overhead Disadvantage: large cells require more padding for small messages (4 points) Give an example of an application-level requirement that might take advantage of the drop priority field in an ATM cell. Stream data is the canonical example because: 1) if a packet is late, it might as well get dropped 2) streams can usually tolerate losing some data 3) there is no need to resend a packet if it gets dropped From the network's point of view, it is less appealing to drop a packet from a file transfer, since the packet is going to get resent anyway, and probably with some additional overhead. (4 points) Name two capabilities that are provided by AAL3/4 that are not provided by AAL5. per-cell error detection multiplexing multiple flows onto a single virtual circuit *True or false (14 points) Frequency hopping makes it possible to use all of the available bandwidth by using a broad range of frequencies. False. Packets on datagram networks tend to have longer headers than packets on connection-oriented networks. True, because the addresses are globally unique. Successive packets on the same virtual circuit must follow the same path. True. The exposed node problem causes a host to refrain from sending even when it might be able to. True. In a token ring, the sender must wait until it receives an ACK before releasing the token. False. Hosts in a FDDI ring are connected by two fiber links that carry data in opposite directions at the same time. False. There are two links, but only one is used. The other is used in case of a failure. Datagram networks might yield better performance than connection-oriented networks because they can take advantage of alternate paths to the same destination. True. *Short answer questions (4 points) Imagine that two hosts are trying to send frames on an Ethernet at the same time. Host A has tried to send its frame before and suffered one collision. Host B has tried before and suffered two collisions. Assuming their frames collide again, what is the probability that Host A will ``win the faceoff'' and retry first? A is choosing from 0 1 2 3 B is chooding from 0 1 2 3 4 5 6 7 A wins 22 cleanly B wins 6 cleanly plus 4 ties Assuming that A wins at least half the ties, the chances that A ultimately wins are > 24/32 (4 points) Suppose that a local phone company offers improved-quality twisted-pair wiring with the following hypothetical characteristics: the range of frequencies that can be carried on these wires is 30 Hz to 5000 Hz, and the signal-to-noise ratio is 5000 to 1. What is the maximum capacity of a signal on these wires? C = 4970 * log2 (5001) = 61 Kbps (2 points) Regarding the previous question, which would yield greater benefit, doubling the upper bound on frequency or doubling the signal-to-noise ratio? Doubling the upper bound on frequency, since the capacity grows linearly with bandwidth and only logarithmically with signal to noise. By the way, this is one reason signal-to-noise ratios are usually expressed in logarithmic terms, a.k.a. decibels. (4 points) ICO is a network infrastructure made up of 10 satellites at an altitude of 10,355 kilometers. What is the minimum distance a signal must travel from a sender to a satellite and down to a receiver? What is the propagation time of that signal at 3 * 10^8 m/s? Ok, this is a throwback question. Transmission time = distance / propagation speed. = 20,710,000 m / 3 * 10^8 m/s = .069 s 0r 69 ms. That's getting pretty close to the threshhold where human's start to notice delays (about 100 ms). (4 points) How can virtual circuits be used to avoid the possibility of dropping packets due to congestion? What is the primary disadvantage of such a system? You can reserve buffer space and network bandwidth along the path, but the cost of doing that is relatively inefficient use of network resources, because applications seldom use the full capacity of the VC all the time. (4 points) In a similar-sized network, why would we expect VCIs to be smaller than host addresses? Under what conditions would that not be true? VCIs only have to be locally unique, so they are generally smaller than host addresses, which have to be globally unique. The only exception would be a network that expects to have more VCs per host than total number of hosts, which is unlikely. *Part Four: Ethernet Switches This figure shows a configuration of Ethernets (marked with lower case letters), hosts (upper case letters) and bridges (B1 through B6). (2 points) During the first round of the distributed MST algorithm, what triplet does B6 broadcast? (B6, 0, B6) (3 points) During the second round of the distributed MST algorithm, what triplet does B6 broadcast? (B2, 1, B6) (3 points) During the third round of the distributed MST algorithm, what triplet does B6 broadcast? (B1, 2, B6) (4 points) What is the longest path in the MST (measured in number of bridges) from one host to another? How long is the shortest path between these hosts, if you could use all ports? From F to A is 4 bridges, when it could be 1! From F to D is also 4 bridges, but the best it could be is 2. (4 points) If D sends a packet to F, which bridges learn where D is? Does Host A hear this packet? All the bridges learn except B5, which is out of the picture. A hears the message. (4 points) If C sends a packet to E, is it necessary for B2 to repeat it? Why or why not? How might B2 know whether or not to repeat it? It is not necessary for B2 to repeat it because the receipient (E) hears it at the same time B2 does. If B2 knows which port E is on, then it will know not to repeat the message. In theory, it could wait to hear an ACK before forwarding, but that would not be a good idea. (4 points) Later on, if E sends a packet to D, is it necessary for B6 to repeat it? Why or why not? How might B6 know whether or not to repeat it? Again, it is not necessary for B6 to repeat this message, and it will know that, since it knows which port D is on. (4 points) What do you think would happen to the performance of the network if we switched B1 and B6 without changing the topology? It would probably improve, since the new root would be more centrally located, reducing the length of the longest path. (4 points) If A sends a train of packets to F, is it possible for the packets to arrive out of order? If not, why not? If so, explain how. If one of the bridges goes down, the MST algorithm might discover a shorter path, allowing a later packet to overtake an earlier one. Some of you suggested that a packet might get dropped and resent, but that only causes the data to arrive out of order (from the application's point of view). It does not cause _packets_ to arrive out of order. Now, picking up where we left off in Chapter 3! Performance issues ------------------ General-purpose hardware may not be appropriate for switches 1) bandwidth limit: half the speed of the I/O bus or half the memory bandwidth, whichever is less 2) throughput limit: throughput = number of packets per second * packet size for small packets, often limited by software speed (reading headers, looking up routing table, etc.) (this is the first definition we have seen. note that it is not the same as bandwidth -- a switch that is throughput limited will not saturate the bandwidth of the outgoing links) Factors that affect throughput ------------------------------ 1) Contention a) output contention: many packets queued for the same output while outputs are idle b) internal contention: in some fabrics, packets that are destined for different ports can still contend 2) Arrival process: as the variance in interarrival times increases, the behavior of queues deteriorates (more buffer space needed, more drops, higher average delay) 3) Distribution of sizes: variability makes buffer allocation harder, also degrades queueing behavior (for the same reasons) and affects impact of per-packet overhead. Throughput depends on traffic patterns. Traffic patterns depend on aggregate behavior of many complex systems (people). Alternate architectures ----------------------- Port: present packets to the fabric maybe do VC lookup or Ethernet table lookup Then either 1) set up the fabric to switch the packet or 2) attach a little switch header that the switch uses to route the packet internally (self-routing) Fabric: get the packet to the right output port Crossbar switch --------------- Pro: Simple, no contention except for output ports. Con: They don't scale well. Every port is connected to all others. Input port closes the appropriate switches and then sends in the packet. Shared-Media Switch ------------------- Big memory, very fast (wide) bus. Controllers handle allocation and deallocation of buffers, control input multiplexer and output demultiplexer. Pro: off-the-shelf memory Con: limited by speed of control logic Buffering --------- 1) input buffering: packets arrive but might queue at the input port before being presented to the fabrics 2) output buffering: packets enter fabric even if the downstream path is congested, queue at the output ports 3) internal buffering: there are places inside the fabric where packets can queue There is analytic evidence that output buffering is better (under certain assumptions about the traffic pattern). Avoids head-of-line blocking: two packets that contend prevent a non-contending packet from entering fabric. Example: crossbar switch with output buffering only. (Makes output port complicated!) Knockout switch --------------- Full crossbar can handle the case where all input ports are sending to the output port. Assume that that is rare: choose a value l < n that is the largest number of simultaneous packets you expect to be destined for the same port. Knockout concentrator: at the input, makes sure that no more than l things are admitted at the same time (destined for the same port). Losers get recycled. Output buffer: at the output port, up to l packets get queued using a round-robin discipline. Self-routing fabrics -------------------- Many small switches in cascade. Packets forwarded from one mini-switch to the next according to self-routing header. This looks a lot like source-routing, which is feasible in this case because the input port knows the topology of the switch (and it doesn't change). Problem: somehow we have to insure that packets don't collide inside the fabric. Not obvious by looking at the source and dest ports whether two packets will collide internally. Could use internal buffering, but better to avoid. Banyan networks: "perfect shuffle" wiring pattern makes collisions impossible (?) as long as packets are presented in ascending order by output port # Batcher network: precede a Banyan network with a mergesorting network So far, we can handle any set of packets as long as no two are headed for the same output port. Sunshine switch: l parallel Banyan networks plus output ports like the ones in a Knockout switch Batcher network insures no internal contention. Trap makes sure that no more than l are headed for the same port, recycles extras. Selector insures that the l headed for the same port go on different Banyans. Yowsers!