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?
- Ethernet (there is a "gap" of idle time, 9.6µsec, between each
pair of consecutive packets)
- Byte-oriented (eg bisync)
- Bit-oriented
- Sonet
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