CEN 4500C Fundamentals of Computer Communication Networks

Last modified 1/30/95.

Framing and Synchronization

Synchronization - bits, words and frames

• Data Rate Measures
  • We will be considering various measures of data rate throughout. The raw data rate (the number of bits that the transmitter can per second without formatting) is only the starting point. There may be overhead for synchronization, for framing, for error checking, for headers and trailers, for retransmissions, etc.
  • Utilization may mean more than one thing. When dealing with network monitoring and management, it refers to the fraction of the resource actually used (for useful data and for overhead, retransmissions, etc.). In this context, utilization refers to the fraction of the channel that is available for actual data transmission to the next higher layer. It is the ratio of data bits per protocol data unit (PDU) to the total size of the PDU, including synchronization, headers, etc. Equivalently, it is the ratio of the time spent actually sending useful data to the time it takes to transfer that data and its attendant overhead.
  • The effective data rate at a layer is the net data rate available to the next higher layer. Generally this is the utilization times the raw data rate.
• Bit synchronization
  • Asynchronous communication (word-oriented)
  • In asynchronous communication, small, fixed-length words (usually 5 to 9 bits long) are transferred without any clock line or clock recovery from the signal itself. Each word has a start bit (a 0) before the first data bit of the word and a stop bit (a 1) after the last data bit of the word. The receiver's local clock is started when the receiver detects the 1-0 transition of the start bit, and the line is sampled in the center of the fixed bit intervals (a bit interval is the inverse of the data rate). The sender output the bit at the agreed-upon rate, holding the line in the appropriate state for one bit interval for each bit, but using its own local clock to determine the length of these bit intervals. The receiver's clock and the sender's clock may not run at the same speed, so that there is a relative clock drift (this may be caused by variations in the crystals used, temperature, voltage, etc.). If the receiver's clock drifts too much relative to the sender's clock, then the bits may be sampled while the line is in transition from one state to another, causing the receiver to misinterpret the received data. Data must be sent in multiples of the data length of the word, and the two or more bits of synchronization overhead compared to the relatively short data length causes the effective data rate to be rather low.
  • Synchronous communication (bit-oriented)
  • Timing is recovered from the signal itself (by the carrier if the signal is analog, or by regular transitions in the data signal or by a separate clock line if the signal is digital). Scrambling is often used to insure frequent transitions needed. The data transmitted may be of any bit length, but is often constrained by the frame transfer protocol (datalink or MAC protocol).
• Frame synchronization
  • Character-oriented
  • Character-oriented framing assumes that character synchronization has already been achieved by the hardware. The sender uses special characters to indicate the start and end of frames, and may also use them to indicate header boundaries and to assist the receiver gain character synchronization. Frames must be of an integral character length. Data transparency must be preserved by use of character stuffing (see below). Most commonly, a DLE (datalink escape) character is used to signal that the next character is a control character, with DLE SOH (start of header) used to indicate the start of the frame (it starts with a header), DLE STX (start of text) used to indicate the end of the header and start of the data portion, and DLE ETX (end of text) used to indicate the end of the frame.
  • Bit-oriented
  • Bit-oriented framing only assumes that bit synchronization has been achieved by the underlying hardware, and the incoming bit stream is scanned at all possible bit positions for special patterns generated by the sender. The sender uses a special pattern (a flag pattern) to delimit frames (one flag at each end), and has to provide for data transparency by use of bit stuffing (see below). A commonly used flag pattern is HDLC's 01111110 flag.
• Data Transparency - Stuffing
  • Character stuffing
  • When a DLE character occurs in the header or the data portion of a frame, the sender must somehow let the receiver know that it is not intended to signal a control character. The sender does this by inserting an extra DLE character after the one occuring inside the frame, so that when the receiver sees two DLEs in a row, it knows to delete one and interpret the other as header or data. This is similar to the practice in FORTRAN of doubling the double quotes if one appears in a string. Note that since the receiver has character synchronization, it will not mistake a DLE pattern that crosses a byte boundary as a DLE signal.
  • Bit stuffing
  • If the flag pattern appears anywhere in the header or data of a frame, then the receiver may prematurely detect the start or end of the received frame. To combat this, the sender makes sure that the frame body it sends has no flags in it at any position (note that since there is no character synchronization, the flag pattern can start at any bit location within the stream). It does this by bit-stuffing, inserting an extra bit in any pattern that is beginning to look like a flag. In HDLC, whenever 5 consecutive 1'a are encountered in the data, a 0 is inserted after the 5th 1, regardless of the next bit in the data. On the receiving end, the bit stream is piped through a shift register as the receiver looks for the flag pattern. If 5 consecutive 1's followed by a 0 is seen, then the 0 is dropped before sending the data on (the receiver destuffs the stream). If 6 1's and a 0 is seen, it is a flag and either the current frame is ended or a new frame is started, depending on the current state of the receiver. If more than 6 consecutive 1's are seen, then the receiver has detected an invalid pattern, and usually the current frame, if any, is discarded.

In addition to receiving the data in logical units called frames, the receiver should have some way of determining if the data has been corrupted or not. If it has been corrupted, it is desirable not only to realize that, but to make an attempt to obtain the correct data. This process is called error correction, and is the subject of the next page.