Figure 1: A shared resource
This chapter is a précis of Chapter 7 of Doug Comer's book [Comer 2004] . It introduces the concept of packets and explains how a sender and receiver co-ordinate the transfer of a packet.
Computer networks do not dedicate a single wire to each pair of communicating computers. Instead, the computers share the underlying hardware facilities. Although it is economic to share facilities, it can cause delays when the network is being heavily used. To avoid long delays, network technologies limit the amount of data that a computer can transmit on each turn. This is called packet switching, and the unit of data that can be transfered is called a packet.
Both LANs and WANs use packet switching. Figure 1 illustrates a shared communication channel.
If A was allowed to send to B a 5 MB file (typical large data file) over the communication channel running at 56 kbps (typical long-distance network), then the transfer will take approximately 12 minutes. This is how long C and D wait to use the channel.
In contrast, consider the situation where transfers take place using 1,000 byte packets. A sends its first packet to B - the transfer takes 143 ms. C or D (or even B) can now transmit. There are no long delays.
Conceptually, a network that permits sources to take turns to access a communication channel is providing a form of time-division multiplexing, as illustrated in Figure 2.
In (a) computer 1 uses the channel, and then in (b) computer 2 uses the channel. Dividing the data into small packets allows all sources to receive prompt service.
In most packet switching networks, transfers occur quickly. A typical LAN can transfer a thousand packets between two computers every second. To a human, events that require thousandths of a second appear instantaneous. For example, several people can use computers connected to a single network without perceiving any delay. The network hardware handles the sharing of the network automatically. It does not require any computation or co-ordination. A computer generates a packet at any time. When the packet is ready, the computer's interface hardware waits its turn before transmitting the packet.
The term packet switching is a generic term for the concept of dividing the data into small blocks for transmission. For a specific hardware technology, the term frame is used to describe the specific format to be used.
Suppose one host needs to send a block of data to another host using the RS-232 character transmission mechanism - this does not include a mechanism for the sender to signal the end of a block. The sender and receiver must agree on the mechanism. Figure 3 illustrates a scheme where the ASCII characters soh (start of header) and eot (end of transmission) are used to delimit the frame.
The mechanism is simple and unambiguous. The only disadvantage is the overhead of generating two additional characters per block of data.
The sender and receiver have agreed to use the characters soh and eot to delimit the frame. Therefore these characters cannot appear as data within the block. A technique called byte stuffing resolves this problem by allocating a third character to mark occurrences of reserved characters in the data. The ASCII character esc is usually used, as illustrated in Figure 4.
For each occurence of a character in the left column, the sender transmits the two characters in the right column. Figure 5 illustrates a complete data block.
In (a) we have a data block containing the special framing characters. In (b) we have the complete frame after byte stuffing. In most communication systems, the characters x, y, and z in the above figure are soh, eot, and esc respectively.
Electro-magnetic interference can introduce unwanted electrical currents into the electronic components or wires used for communication. Severe interference (e.g. lightning) can cause permanent damage to network equipment. More often, interference changes the electrical signal without damaging the equipment. This can cause the receiver to misinterpret one or more bits of data. Lost, changed, or spuriously appearing bits, collectively called transmission errors, account for extra complexity required in computer networks.
RS-232 circuits can use a parity bit to ensure that each character arrives intact. The sender computes an additional bit based on the seven ASCII data bits and transmits this as an eighth bit. The receiver performs the same computation and verifies that the parity bits agree. The computation is chosen so that a one-bit alteration can be detected.
Parity can be even or odd; for even (odd) parity the sender sets the parity bit so that the total number of 1 bits is even (odd).
Many computer networks send a checksum along with each packet to help the receiver detect errors. To compute a checksum, the sender treats the data as a sequence of binary integers and computes their sum, as illustrated in Figure 6.
Each pair of characters is treated as a 16-bit integer. If the sum overflows 16 bits, the carry bits are added to the total. The advantage of such checksums is the size and ease of computation. Addition requires very little computation and the cost of sending an additional 16-bits is negligible.
However, checksums do not detect all common errors, as illustrated in Figure 7.
A transmission error has reversed the second bit in each of the four data items, yet the checksums are identical.
It is possible to detect more errors without increasing the amount of additional information in the packet using a Cyclic Redundency Check (CRC) technique. Moreover, the hardware necessary to generate them is very simple. The two necessary components are an exclusive or (XOR) unit and a shift register. Figure 8 illustrates the XOR hardware and truth table.
In (a), we have the diagram for the hardware which computes the XOR. In (b), we have the output value for each of the four combinations of input values. The second component, a shift register, holds a fixed number of bits and each time a new bit enters (on the right) the contents of the register shift left and the leftmost bit becomes the output. This is illustrated in Figure 9.
In (a) we have the position before the shift and in (b) the position after the shift. The shift register can be initialised by setting all bits to zero.
Figure 10 illustrates how three XOR units and three shift registers can be combined to form a 16-bit CRC. The hardware is inexpensive and easy to construct.
Output from the leftmost shift register goes to the three XOR units simultaneously. To compute a CRC, the shift registers are intialised to zero, and the bits of the message are shifted in one at a time. After an entire message has been shifted into the unit, the shift registers contain the 16-bit CRC for the message. The receiver uses identical hardware to calculate a CRC to verify that it agrees with the sender's CRC.
To simplify checking, a small modification is made to the above algorithm. When computing the CRC, the sender appends an additional sixteen zeros to the message. Mathematically, the sixteen zeros cause the resulting CRC to be an inverse. This is useful for the receiver, who computes the CRC over the incoming message and the incoming CRC. If all bits are correctly received, the computed value will be zero.
The mathematics of CRCs are too complex to be covered here (see [Tanenbaum 2003] , pp. 196-200 for further details). The 16-bit CRC used above will detect all single-bit errors, all double-bit errors, all errors containing an odd number of bits, and all burst errors of length 16 or less (first and last bits are one), as well as a number of additional errors. Detecting burst errors is important, as electrical interference (lightning, and other sparks) often produces burst errors.
Networks usually handle error detection at the frame level. The sender computes a checksum or CRC and transmits this with each frame. The receiver performs the same calculation and uses the result to validate the incoming frame. A simple frame format is illustrated in Figure 11.
The modified frame format includes a 16-bit CRC. Different standards define whether the CRC is computed over the original message or the stuffed frame.
Error correction can be used on simplex channels, where retransmission cannot be requested, but most often error detection followed by retransmission is preferred because it is more efficient.
A simple method for correcting single bit errors is to transmit each bit three times.
0 -> 0001 -> 111
If 001, 010, or 100
is received, the original message was 0. If
110, 101, or 011 is
received, the original message was 1.
It is possible to do better than this. Hamming codes (see [Tanenbaum 2003] , pp. 193-194 for further details) are used to correct single bit errors (8 data bits require 4 extra bits to be transmitted).
| Last modified: Thu Nov 24 10:40:13 2005 |