CRC-based framing
Encyclopedia
The concept of CRC-based framing was developed by StrataCom
, Inc. in order to improve the efficiency of a pre-standard Asynchronous Transfer Mode
(ATM) link protocol. This technology was ultimately used in the principal link protocols of ATM itself and was one of the most significant developments of StrataCom. An advanced version of CRC-based framing was used in the ITU
-T SG15 G.7041 Generic Framing Procedure
(GFP), which itself is used in several packet link protocols.
(CRC), which is present in ATM and other similar protocols, to provide framing on the link with no additional overhead. In ATM, this field is known as the Header Error Control/Check (HEC) field. The header CRC/HEC is needed for another purpose within an ATM system, to improve the robustness in cell delivery. Using this same CRC/HEC field for the second purpose of link framing provided a significant improvement in link efficiency over what other methods of framing, because no additional bits were required for this second purpose.
A receiver utilizing CRC-based framing bit-shifts along the received bit stream until it finds a bit position where the header CRC is correct for a number of times. The receiver then declares that it has found the frame. A hysteresis function is applied to keep the receiver in lock in the presence of a moderate error rate.
In links where there is already a byte lock mechanism present such as within an E-carrier
or SDH
frame, the receiver need only byte-shift (rather than of bit-shifting) along the receive data stream to find lock.
-T SG15 G.7041 GFP
links where it is known as Length/HEC-based framing. An offset to the next valid header is present in a fixed position relative to the CRC/HEC. The receiver looks for a position in the receive data stream following the rules that the header CRC/HEC is correct and the byte offset correctly points to the next valid header CRC/HEC.
. The IPX used 24 byte
cells instead of ATM's 53 byte cells, and the field definitions were slightly different, but the basic idea of using short, fixed length cells was identical. StrataCom's first product had T1 (1.544 Mbit/s) based links which included a 5 bit header CRC, similar to ATM's 8 bit header CRC.
T1
is a time-division multiplexing
(TDM) protocol with 24 byte payloads carried in a 193 bit frame. The first bit of each frame carries one bit out of a special pattern. A receiver finds this special pattern by sequentially looking for the bit position in the receive data where a bit from this pattern shows up every 193rd byte. It was convenient for StrataCom to make the length of one cell equal to the length of one T1 frame
because a useful T1 framer Integrated Circuit
from Rockwell
was on the market. This device found the 193 bit long TDM frame and put out the 24 bytes in a form that could be used effectively.
When it came time to produce a Europe
an product, the benefit of using 24 byte frames became a liability. The European T-carrier
(E1) format has a 32 byte frame of which 30 bytes could carry data. The development team's first proposal used the HDLC protocol to encapsulate a sequence of 24 byte cells into a byte stream collected from the 30 byte E1 payloads. This was highly inefficient because HDLC has a heavy and data-dependent overhead. This factor may have ruined the economics of product for the European market. In the design review, everyone was lamenting what a bad solution HDLC was for the problem. Brian Holden, who was one of the reviewers present, then uttered the sentence "Why don't you just frame on the CRC?". Everyone in the room went "Oh!" as the lightbulb flashed on. Participating in this design review and uttering this one high-value sentence was Brian's only involvement in this E1 project and the consequent development of CRC-based framing.
The project team went on to base the framing of the E1 project on the CRC. A circuit was designed which examined the incoming byte stream emerging from the E1 framer device and found a byte position for which the header CRC value was consistently correct. The developers Rick Enns and Paul O'Hare properly got the patent
for the development as Brian Holden did just utter the one sentence.
This team also went on to create a more error tolerant form of the technique.
A related technique was patented in 1984.
That technique uses the CRC to find the start of 50 bit frames composed of a 36 bit data payload, a 13 bit CRC, and a single 1 bit start-of-frame indicator.
StrataCom
StrataCom, Inc. was founded in Cupertino, California, USA, in January 1986 by 26 former employees of the failing Packet Technologies, Inc. StrataCom produced the first commercial cell switch, also known as a fast-packet switch. Its product was the working proof of the technology which became...
, Inc. in order to improve the efficiency of a pre-standard Asynchronous Transfer Mode
Asynchronous Transfer Mode
Asynchronous Transfer Mode is a standard switching technique designed to unify telecommunication and computer networks. It uses asynchronous time-division multiplexing, and it encodes data into small, fixed-sized cells. This differs from approaches such as the Internet Protocol or Ethernet that...
(ATM) link protocol. This technology was ultimately used in the principal link protocols of ATM itself and was one of the most significant developments of StrataCom. An advanced version of CRC-based framing was used in the ITU
Itu
Itu is an old and historic municipality in the state of São Paulo in Brazil. The population in 2009 was 157,384 and the area is 641.68 km². The elevation is 583 m. This place name comes from the Tupi language, meaning big waterfall. Itu is linked with the highway numbered the SP-75 and are flowed...
-T SG15 G.7041 Generic Framing Procedure
Generic Framing Procedure
Generic Framing Procedure is a multiplexing technique defined by ITU-T G.7041. This allows mapping of variable length, higher-layer client signals over a circuit switched transport network like OTN, SDH/SONET or PDH...
(GFP), which itself is used in several packet link protocols.
Overview of CRC-based framing
The method of CRC-Based framing re-uses the header cyclic redundancy checkCyclic redundancy check
A cyclic redundancy check is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data...
(CRC), which is present in ATM and other similar protocols, to provide framing on the link with no additional overhead. In ATM, this field is known as the Header Error Control/Check (HEC) field. The header CRC/HEC is needed for another purpose within an ATM system, to improve the robustness in cell delivery. Using this same CRC/HEC field for the second purpose of link framing provided a significant improvement in link efficiency over what other methods of framing, because no additional bits were required for this second purpose.
A receiver utilizing CRC-based framing bit-shifts along the received bit stream until it finds a bit position where the header CRC is correct for a number of times. The receiver then declares that it has found the frame. A hysteresis function is applied to keep the receiver in lock in the presence of a moderate error rate.
In links where there is already a byte lock mechanism present such as within an E-carrier
E-carrier
In digital telecommunications, where a single physical wire pair can be used to carry many simultaneous voice conversations by time-division multiplexing, worldwide standards have been created and deployed...
or SDH
Synchronous optical networking
Synchronous Optical Networking and Synchronous Digital Hierarchy are standardized multiplexing protocols that transfer multiple digital bit streams over optical fiber using lasers or highly coherent light from light-emitting diodes . At low transmission rates data can also be transferred via an...
frame, the receiver need only byte-shift (rather than of bit-shifting) along the receive data stream to find lock.
Length/HEC-Based Framing
An advanced, variable frame size version of CRC-Based framing is used in ITUItu
Itu is an old and historic municipality in the state of São Paulo in Brazil. The population in 2009 was 157,384 and the area is 641.68 km². The elevation is 583 m. This place name comes from the Tupi language, meaning big waterfall. Itu is linked with the highway numbered the SP-75 and are flowed...
-T SG15 G.7041 GFP
Generic Framing Procedure
Generic Framing Procedure is a multiplexing technique defined by ITU-T G.7041. This allows mapping of variable length, higher-layer client signals over a circuit switched transport network like OTN, SDH/SONET or PDH...
links where it is known as Length/HEC-based framing. An offset to the next valid header is present in a fixed position relative to the CRC/HEC. The receiver looks for a position in the receive data stream following the rules that the header CRC/HEC is correct and the byte offset correctly points to the next valid header CRC/HEC.
Invention of CRC-based framing
The story behind the invention of CRC-based framing is as follows: StrataCom produced the first (pre-standard) ATM commercial product, the IPXIPX
Internetwork Packet Exchange is the OSI-model Network layer protocol in the IPX/SPX protocol stack.The IPX/SPXM protocol stack is supported by Novell's NetWare network operating system. Because of Netware's popularity through the late 1980s into the mid 1990s, IPX became a popular internetworking...
. The IPX used 24 byte
Byte
The byte is a unit of digital information in computing and telecommunications that most commonly consists of eight bits. Historically, a byte was the number of bits used to encode a single character of text in a computer and for this reason it is the basic addressable element in many computer...
cells instead of ATM's 53 byte cells, and the field definitions were slightly different, but the basic idea of using short, fixed length cells was identical. StrataCom's first product had T1 (1.544 Mbit/s) based links which included a 5 bit header CRC, similar to ATM's 8 bit header CRC.
T1
T-carrier
In telecommunications, T-carrier, sometimes abbreviated as T-CXR, is the generic designator for any of several digitally multiplexed telecommunications carrier systems originally developed by Bell Labs and used in North America, Japan, and South Korea....
is a time-division multiplexing
Time-division multiplexing
Time-division multiplexing is a type of digital multiplexing in which two or more bit streams or signals are transferred apparently simultaneously as sub-channels in one communication channel, but are physically taking turns on the channel. The time domain is divided into several recurrent...
(TDM) protocol with 24 byte payloads carried in a 193 bit frame. The first bit of each frame carries one bit out of a special pattern. A receiver finds this special pattern by sequentially looking for the bit position in the receive data where a bit from this pattern shows up every 193rd byte. It was convenient for StrataCom to make the length of one cell equal to the length of one T1 frame
because a useful T1 framer Integrated Circuit
Integrated circuit
An integrated circuit or monolithic integrated circuit is an electronic circuit manufactured by the patterned diffusion of trace elements into the surface of a thin substrate of semiconductor material...
from Rockwell
Rockwell
- People :* Dick Rockwell, an American comic strip and comic book artist, nephew of Norman Rockwell* Francis W. Rockwell, a United States Congressman from Massachusetts* Francis W...
was on the market. This device found the 193 bit long TDM frame and put out the 24 bytes in a form that could be used effectively.
When it came time to produce a Europe
Europe
Europe is, by convention, one of the world's seven continents. Comprising the westernmost peninsula of Eurasia, Europe is generally 'divided' from Asia to its east by the watershed divides of the Ural and Caucasus Mountains, the Ural River, the Caspian and Black Seas, and the waterways connecting...
an product, the benefit of using 24 byte frames became a liability. The European T-carrier
T-carrier
In telecommunications, T-carrier, sometimes abbreviated as T-CXR, is the generic designator for any of several digitally multiplexed telecommunications carrier systems originally developed by Bell Labs and used in North America, Japan, and South Korea....
(E1) format has a 32 byte frame of which 30 bytes could carry data. The development team's first proposal used the HDLC protocol to encapsulate a sequence of 24 byte cells into a byte stream collected from the 30 byte E1 payloads. This was highly inefficient because HDLC has a heavy and data-dependent overhead. This factor may have ruined the economics of product for the European market. In the design review, everyone was lamenting what a bad solution HDLC was for the problem. Brian Holden, who was one of the reviewers present, then uttered the sentence "Why don't you just frame on the CRC?". Everyone in the room went "Oh!" as the lightbulb flashed on. Participating in this design review and uttering this one high-value sentence was Brian's only involvement in this E1 project and the consequent development of CRC-based framing.
The project team went on to base the framing of the E1 project on the CRC. A circuit was designed which examined the incoming byte stream emerging from the E1 framer device and found a byte position for which the header CRC value was consistently correct. The developers Rick Enns and Paul O'Hare properly got the patent
Patent
A patent is a form of intellectual property. It consists of a set of exclusive rights granted by a sovereign state to an inventor or their assignee for a limited period of time in exchange for the public disclosure of an invention....
for the development as Brian Holden did just utter the one sentence.
This team also went on to create a more error tolerant form of the technique.
A related technique was patented in 1984.
That technique uses the CRC to find the start of 50 bit frames composed of a 36 bit data payload, a 13 bit CRC, and a single 1 bit start-of-frame indicator.