Chapter 2: Links

This chapter also covers a wide variety of material, nominally united by the common thread of  applicability to direct links not involving switching or routing. Some sections are very link-specific  (2.6 on Ethernet, for example, or 2.3 on encoding) while some are very general sections (2.5, on the sliding window algorithm, applies almost completely to the general switched-network case).

The most important sections are 2.5 on reliable transmission, and 2.6 on Ethernet.

Section 2.1

General stuff, and a discussion about what kinds of links you can buy from the phone company.
 

Section 2.2 - Encoding

Encoding. You can't just encode your data by having 0's be off and 1's be on (an encoding that, although not used directly, does have a name: NRZ). First, long strings of 0's then look like the signal is simply "off". Second, the receiver is likely to lose count when receiving long strings of either 0's or 1's; there is nothing to separate out the bits except timing, and timing can slip. This latter problem is discussed in the text as clock recovery. There is also the issue of baseline wander.

So this section goes on to discuss some variations. The two in common use are Manchester encoding, which sticks in an extra clock bit between each pair of data bits, and 4B/5B. Note that the table given in the text for 4B/5B is completely arbitrary, but is fixed by convention.

This section can be deferred, if desired.

Study questions:

Explain why encoding is also a problem if you are writing a stream of data as a sequence of 0's and 1's to a magnetic storage medium (eg a disk drive).
In what sense is Manchester encoding "inefficient"? In switching from Manchester to 4B/5B, what improves?

Exercises

1    basic encodings
2    4b/5b encoding

Section 2.3 - Framing

Framing is the issue of deciding when a packet stops and the next one starts. On Ethernet, there is simply a gap between every pair of consecutive packets, during which the line is completely idle. However, on many other types of links the packets are simply run together. The PPP case is the situation everyone uses if they use a dialup connection to the Internet.
This section can also be deferred.

The section deals with byte-oriented protocols (where the data byte alignment remains intact, and we simply insert extra "marker" bytes), and bit-oriented protocols (where what gets inserted are extra bits, which more or less implies dedicated hardware at each end to convert back to bytes), and SONET. Note that SONET is both a framing and an encoding mechanism.

Study questions:

For the byte-oriented and bit-oriented protocols, what sequences can not appear transmitted on the link? (That is, any data can be sent, but it gets changed as it's transmitted; some sequences cannot appear as transmissions.)
How does SONET deal with the problem of clock recovery?

Exercises

6    BISYNC
8    sonet

Section 2.4 - Error-detecting codes

Another technical (notoriously technical!) section that can be deferred for a while. The most basic error-detection strategy is to use a parity bit. The drawback to it is that it detects only one-bit errors; if a burst of a large number of errors occurs, then the odds that the parity ends up correct by chance alone is around 50%. When most errors are "individual" errors, and most packets have at most a single error, parity can work quite well. But errors often occur in "bursts".

The text discusses three main strategies: two-dimensional parity, the internet checksum algorithm, and CRC. All of these deal well with "burst" errors, where large numbers of bits are subject to corruption, as well as "individual" errors. The nice thing about two-dimensional parity is that it extends to a simple form of error-correcting code.

Study questions:

What is the CRC remainder if the generator is 1101 and the message is 1001 1101 101?

Exercises

10    2-D parity undetected errors
11    2-D parity error correction (our only example of an error-correcting code)
12    Internet checksum

Section 2.5 - Reliable transmission

This is the heart of any reliable transport mechanism, including TCP. The simplest strategy, of alternating exchange of data and ACK, is called stop-and-wait here. To avoid excessive waiting for ACKs, the sliding window algorithm is usually employed. There is a subtle assumption in this chapter that we're doing transport only over a single link, which generally implies that delivered packets cannot arrive out of order. Links essentially never reorder packets. However, reordering is possible (in fact, common) once switches and routers are introduced. The only place this matters, though, is in how many bits of the sequence number are actually transmitted; everything works out fine if, for the time being, you just imagine that sequence numbers are infinite-precision (that is, they never wrap around).

The text includes some code implementing the sliding window algorithm; you may skip this part.

Study questions:

See the exercises

Exercises:

22    relatively simple stop-and-wait variation
23    Sorcerer's Apprentice bug
27, 28, 29    three variations on the relationship between SWS, RWS, and MaxSeqNum
30    Timeline of sliding windows through a router

Section 2.6 - Ethernet

This is the basic LAN mechanism. The original model of Ethernet was that a bunch of stations were all connected along a single piece of coaxial cable. Nowadays the use of hubs provides almost infinite branching, and there are no longer any "taps" allowed along twisted-pair Ethernet cable. However, the original mechanism still works in more or less the same way. At the physical layer, every packet is broadcast, and is seen by every other host's network adaptor (also called network interface). The network adaptor interrupts the host CPU and delivers the packet whenever one of the conditions on page 121 applies.

One important consequence is that Ethernet supports true broadcast, where one node can send a message to every other.

Another important issue for Ethernet is that the underlying unsynchronized transmission strategy allows collisions to occur, and these must then be dealt with. This is discussed in the text in the section Transmitter Algorithm.

Further information can be found at my Ethernet page.

Study questions:

What is a realistic utilization rate for a busy Ethernet?
What happens as the desired sending rate climbs above the effective bandwidth available?

Exercises

33    The need for an Ethernet length field
37    Ethernet "capture effect"; kind of long but illustrates an important failure of "fairness"
39    Ethernet timeline
42    A different Ethernet timeline
44    Estimate of the usable fraction of Ethernet bandwidth

Section 2.7 - Token Ring

You need only read the beginning of the chapter here (up to the beginning of subsection 2.7.1), to understand how token ring mechanisms (there are several) work, and why they provide fairer and more efficient use of the LAN as utilization approaches 100%, than Ethernet. However, this improvement is nowadays generally regarded as irrelevant. For "legacy" LANs, 10 Mbps Ethernet had more effective bandwidth than the then-available 4Mbps IBM token ring. Nowadays, 100 Mbps Ethernet or 1 Gbps Ethernet is usually a cheaper upgrade alternative than some comparable ring protocol.

Study question:

Why does token ring guarantee round-robin service to the stations waiting to transmit (that is, they take turns, cyclically)?
Does token ring support true broadcast?