Chapter 2: Links

Part A: The Bit Level: Encoding, Framing, and Error Detection

This chapter covers a wide variety of material, nominally united bythe common thread of  applicability to direct links not involvingswitching or routing. Some sections are very link-specific  (2.6 onEthernet, for example, or 2.3 on encoding) while some are very generalsections (2.5, on the sliding window algorithm, applies almost completelyto the general switched-network case). The first four sections are decidedly more nuts-and-bolts (or perhaps even mundane) and are treated in this unit; this unit may be deferred temporarily without loss of continuity.

The other two sections, 2.5 on reliable transmission and 2.6 on Ethernet, are the most important of the chapter. They are treated in a separate unit, 2B.

Section 2.1

General stuff, and a discussion about what kinds of links you can buy from the phone company.We will come back to these various named "bit pipes" later, when estimating, for example, round-trip times and bandwidth for Internet connections.
 

Section 2.2 - Encoding

Encoding. You can't just encode your data by having 0's be off and 1'sbe on (an encoding that, although not used directly, does have a name:NRZ). The problem is that, first, long strings of 0's would look like the signal is simply "off".Second, the receiver is likely to lose count when receiving long stringsof either 0's or 1's; there is nothing to separate out one bit from the one that follows it excepttiming, and timing can slip. This latter problem is discussed in the textas clock recovery. There is also the issue of baseline wander, the variation in signal strength.

So this section goes on to discuss some variations. The two in commonuse are Manchester encoding, which sticks in an extra clock bit betweeneach pair of data bits, and 4B/5B. Note that the table given in the textfor 4B/5B is completely arbitrary, but is fixed by convention. Note also that all these clock bits cost something; in the case of Manchester encoding, it means that the effective bitrate for data transmission is only half of the underlying frequency at which the system operates.

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 fromManchester 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 typesof links the packets are simply run together. The PPP case is the situationeveryone uses if they use a dialup connection to the Internet.

The section deals with byte-oriented protocols (where the data bytealignment remains intact, and we simply insert extra "marker" bytes), andbit-oriented protocols (where what gets inserted are extra bits, whichmore or less implies dedicated hardware at each end to convert back tobytes), 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 itgets changed as it's transmitted; some sequences cannot appear as transmissions.)

How does SONET deal with the problem of clock recovery?

Compare and contrast the following strategies for framing: (for Ethernet, peek ahead or look at the hint). For which of these strategies is the frame enlarged somewhat upon transmission? 
How could 4B/5B be used to solve the framing problem? (Hint: there are more usable 4b/5b codes than the sixteen needed for data)

Exercises

6    BISYNC
8    sonet

Section 2.4 - Error-detecting codes

This is another technical (notoriously technical!) section. The most basic error-detection strategy is to use a paritybit. The drawback to it is that it detects only one-bit errors; if a burstof a large number of errors occurs, then the odds that the parity bit endsup correct by chance alone (and thus that an error is transmitted undetected) is around 50%. When most errors are "individual"errors, and most packets have at most a single error, parity can work quitewell. But errors often occur in "bursts".

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

Although it isn't entirely clear from this section, the standard engineering approach to dealing with a "lossy" link is to add error-correcting codes, so that a packet transmission can recover from losses without retransmission. This has the effect of raising the reliability of the link (often by a large amount), at the expense of transmitting slightly more bits.

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