6.826—Principles of Computer Systems 1999 Handout 23. Networks — Links and Switches 1 23. Networks — Links and Switches This handout presents the basic ideas for transmitting digital data over links, and for connecting links with switches so that data can pass from lots of sources to lots of destinations. You may wish to read chapter 7 of Hennessy and Patterson for a somewhat different treatment, more focused on interconnecting the components of a multiprocessor computer. 1 Links A link is an unreliable FIFO channel. As we mentioned earlier, it is an abstraction of a point-to-point wire or of a simple broadcast LAN. It is unreliable because noise or other physical problems can corrupt messages. There are many kinds of physical links, with cost and performance that vary based on length, number of drops, and bandwidth. Here are some current examples. Bandwidth is in bytes/second2, and the “+” signs mean that software latency must be added. The nature of the messages reflects the origins of the link. Computer people prefer variable-size packets, which are good for bursty traffic. Communications people prefer bits or bytes, which are good for fixed-bandwidth voice traffic and minimize the latency and buffering added by collecting voice samples into a message. A physical link can be unidirectional (‘simplex’) or bidirectional (‘duplex’). A duplex link may operate in both directions at the same time (‘full-duplex’), or in one direction at a time (‘half-duplex’). A pair of simplex links running in opposite directions forms a full-duplex link. So does a half-duplex link in which the time to reverse direction is negligible, but in this case the peak full-duplex bandwidth is half the half-duplex bandwidth. If most of the traffic goes in one direction, however, the usable bandwidth of a half-duplex link may be nearly the same as that of a full-duplex link. To increase the bandwidth of a link, run several copies of it in parallel. This goes by different names; ‘space division multiplexing’ and ‘striping’ are two of them. Common examples are: Parallel busses, as in the first five lines of the table. Switched networks: the telephone system and switched LANs. Multiple disks, each holding part of a data block, that can transfer in parallel. Cellular telephony, using spatial separation to reuse the same frequencies. In the latter two cases there must be physical switches to connect the parallel links. Another use for multiple links is fault tolerance, discussed earlier. 1 My thanks to Alex Shvartsman for some of the figures in this handout. 2 Beware: communications people usually quote bits/sec. 6.826—Principles of Computer Systems 1999 Handout 23. Networks — Links and Switches 2 Medium Link Bandwidth Latency Width Message Alpha chip on-chip bus 4 GB/s 2 ns 64 8 bytes PC board RAMbus 0.5 GB/s 150 ns 8 packet, < 100 B PCI I/O bus 133 MB/s 250 ns 32 packet Wires HIPPI3 100 MB/s 100 ns 32 packet Fibre channel4 100 MB/s 250 ns 1 packet IEEE 13945 50 MB/s 250 ns 1 packet SSA6 20 MB/s 500 ns 1 packet SCSI 20 MB/s 500 ns 16 packet USB 1.5 MB/s 5 µs 1 ? LAN FDDI 12.5 MB/s 20 + µs 1 packet, 20-4500 B Gigabit Ethernet 125 MB/s 1 + µs 1 packet, 64-1500 B Fast Ethernet7 12.5 MB/s 10 + µs 1 packet, 64-1500 B Ethernet 1.25 MB/s 100 + µs 1 packet, 64-1500 B Wireless WaveLAN .25 MB/s 100 + µs 1 packet, < 1500 B Fiber (Sonet) OC-48 300 MB/s 5 µs/km 1 1 byte or 1 cell Coax cable T3 6 MB/s 5 µs/km 1 1 byte Copper pair T1 0.2 MB/s 5 µs/km 1 1 byte Copper pair ISDN 16 KB/s 5 µs/km 1 1 byte Broadcast CAP 16 3 MB/s 3 µs/km 6 MHz 1 byte or 1 cell Flow control Many links do not have a fixed bandwidth that is known to the sender, because the link is being shared (that is, there is multiplexing inside the link) or because the receiver can’t always accept data. In particular, fixed bandwidth is bad when traffic is bursty, because it will be either too small or too large. If the sender doesn’t know the link bandwidth or can’t be trusted to stay below it, some kind of flow control is necessary to match the flow of traffic to the link’s or the receiver’s capacity. A link can provide this in two ways, by contention or by scheduling. In this case these general strategies take the form of backoff or backpressure. Backoff In backoff the link drops excess traffic and signals ‘trouble’ to the sender, either explicitly or by failing to return an acknowledgment. The sender responds by waiting for a while and then retransmitting. The sender increases the wait by some factor (say 2) after every trouble signal and decreases it with each trouble-free send. This is called ‘exponential backoff'; when the 3 D. Tolmie and J. Renwick, HIPPI: Simple yields success. IEEE Network 7, 1 (Jan. 1993), pp 28-32. 4 M. Sachs and A. Varman, Fibre channel and related standards. IEEE Communications 34, 8 (Aug. 1996), pp 40-49. 5 G. Hoffman and D. Moore, IEEE 1394: A ubiquitous bus. Digest of Papers, IEEE COMPCON ’95, 1995, pp 334-338. 6 http://www.ssaia.org 7 M. Molle and G. Watson, 100Base-T/IEEE 802.12/Packet switching. IEEE Communications 34, 8 (Aug. 1996), pp 63-73.6.826—Principles of Computer Systems 1999 Handout 23. Networks — Links and Switches 3 increasing factor is 2, it is ‘binary exponential backoff’. It is used in the Ethernet8 and in TCP9, and is analyzed in some detail in a later section. Exponential backoff works because it adjusts the rate of sending so that most packets get through. If every sender does this, then every sender’s delay will jiggle around the value at which the network is just managing to carry all the traffic. This is because a wait that is too short will overload the network, some packets will be lost, and the sender will increase the wait. On the other hand, a wait that is too long will always succeed, and the sender will decrease it. Of course these statements are probabilistic: sometimes a conservative sender will lose a packet because someone else overloaded the network. The precise details of how the wait should be lengthened (backed off) and shortened depend on the properties of the channel. If the ‘trouble’ signal comes back very quickly and the cost of trouble is small, senders can shorten their waits aggressively; this happens in the Ethernet, where collisions are detected in at most