US 5,691,997 AGrant
Encoder for Use in Asynchronous Transfer Mode Systems
Issue Date:1997-11-25
•11 Claims
•4 Drawing Sheets
Abstract
A destination station receives from a network a data packet that is transmitted as a plurality of cells and separately encodes each of the received cells, to produce associated, individual c-bit partial CRC remainders, where c is the number of bits in the CRC remainder associated with the packet. These partial CRC remainders correspond to the respective contributions that the cells make to the packet CRC pattern. The encoder appends the partial CRC remainders to the cells, and the station then stores them in an associated memory and links the individual cells to previously stored cells from the same packet with pointers. Once all the cells of a packet are encoded and stored, the destination station retrieves appended partial CRC remainders from the memory, and provides the remainders to a partial CRC encoder. The encoder manipulates the partial remainders and produces a packet CRC remainder. If the CRC packet is error-free, this packet CRC remainder matches the predetermined CRC pattern associated with the CRC code.
Metadata
Assignee
- Cisco Systems, Inc.
Inventor
- Stanley A. Lackey, Jr.
Application Information
Application Number:US 5354536
Filing Date:1995-09-28
Priority Date:1995-09-28
Art Unit:236
Classifications
IPC:
G06F 1110
Field of Search:
37137037.1;53395;473
Patent Drawings (4 sheets)
Description
Field of the Invention
This invention relates generally to communications systems and, more particularly, to asynchronous transfer mode systems.
Background of the Invention
In asynchronous transfer mode (ATM) systems a source station separates a multiple byte data packet into a plurality of fixed-length cells.
Each cell contains a 5-byte header that includes routing and other information, and a payload of up to 48 data bytes. Padding is appended, as necessary, to ensure that the payload of each cell is 48 bytes in length. These cells, in turn, are assembled into multiple-cell frames, which are transmitted over a network to a designated destination station.
The destination station accumulates the cells, or more specifically data bytes included therein, and reassembles them into the respective data packets. Before sending a data packet to an end user, the destination station performs an error detection operation, to determine if the packet is error free. If the packet contains errors, the destination station typically refrains from sending the packet to the end user.
An ATM adaptation layer (AAL) is responsible for segmenting the data packets into the cells at the source station and reassembling the cells into the packet at the destination station. One version of AAL, referred to as AAL 5, includes in the last cell of a data packet a multiple-bit CRC remainder, which is produced at the source station by encoding the packet data bytes in accordance with a CRC code. Using the AAL 5 protocol, the destination station determines if the packet contains errors by encoding the received data bytes and the CRC remainder, in accordance with the CRC code, and comparing the result to a predetermined constant, or CRC pattern. If the two match, the destination station determines that the packet is error-free. Conversely, if the two do not match, the station determines that the packet contains errors.
Each data packet is encoded at the source station by (i) selectively combining the first data byte of the packet with the contents of a register that has been set to an initial condition, (ii) using the result of the encoding to update the register, (iii) encoding a next byte by selectively combining it with the contents of the updated register, (iv) updating the register with the results of the encoding, and so forth, until all of the data bytes in the packet have been encoded. After the last data byte is encoded, the 1s complement of the contents of the register are appended to the packet as the CRC remainder, the packet is segmented into the fixed-sized cells, and the cells typically are packed into frames for transmission to the designated destination station.
Generally, the cells are transmitted as part of a stream of traffic over the network, such that the cells associated with an individual data packet are spread out, with cells from other data packets in between them. In one implementation, the cells are packed into frames, with the cells from other packets packed in between them. This means that the destination station typically receives, in any one transmission, portions of multiple data packets. In the time it takes the station to receive a complete data packet, it may receive portions of thousands of packets. Accordingly, the destination station must coordinate and control the error detecting operations for all of these data packets.
In known prior systems, the destination stations use one of two methods to control the error detecting operations. Using a first method, the destination station stores the received cells in an associated memory, with the cells associated with a particular packet "linked" to each other. When the last cell of a packet is received, the station retrieves the cells from the memory, reassembles the packet and encodes the data and the included CRC remainder to reproduce the CRC pattern. The station then compares the reproduced pattern to the actual pattern and determines if the packet is error free.
These retrieval and encoding operations take a relatively long time, particularly if the data packets are large. Accordingly, there can be an unacceptably long delay between the time the complete packet is received by the destination station and the time that the packet is forwarded from that station to an end user. Also, the associated memory must include extra storage locations, to hold various complete data packets until they can be checked for errors by the station.
Using the alternative method, the destination station encodes the cells as the cells are received. To do this the CRC encoder must maintain thousands of running CRC accumulations, one for each partially-received packet, because there is not enough time as the cells are received for the encoder to (i) retrieve the appropriate CRC accumulation from an associated memory, (ii) use the retrieved accumulation to update the encoder's register, and (iii) encode the cell. The encoder must thus include buffers with sufficient space, associated addressing circuitry and so forth, to manipulate the thousands of CRC accumulations. This increases the complexity of the encoders.
Summary of the Invention
The invention is an encoder that, as cells are received, separately encodes them, to produce associated, individual multiple-bit partial CRC remainders. These remainders correspond to the respective contributions that the cells make to the packet CRC pattern. The encoder appends the partial CRC remainders to the cells, and the station then stores them in an associated memory and links them to previously stored cells from the same packet. Once all the cells of a packet are encoded and stored, the destination station retrieves the partial CRC remainders from the memory, and provides them to a partial CRC encoder. The encoder manipulates the partial remainders and produces a packet CRC pattern. If the CRC packet is error-free, its data pattern matches the predetermined CRC pattern associated with the CRC code.
More specifically, the CRC encoder in the destination station encodes a received cell in accordance with the CRC code, and appends the result to the cell as the partial CRC remainder. As discussed above, the cell, with its appended partial CRC remainder, is stored in the associated memory and linked to any previously received cells that are associated with the same data packet. The encoder thereafter encodes the succeeding cells, as they are received, and appends the results to the cells as the partial CRC remainders. Each of these cells is stored in the memory, linked to the previously recorded cells of the same packet.
When all the cells of one of the packets have been encoded and stored, the station verifies the packet by retrieving the partial remainders from the memory. The encoder then, as discussed above, manipulates the retrieved remainders, and reproduces the packet CRC pattern. The manipulation operations are discussed in more detail below. If the CRC verifies that the packet is error-free, the entire packet is then retrieved from memory and forwarded to an end user.
The encoder can quickly encode the partial CRC remainders to determine if the associated packet is error-free, since this encoding requires manipulation of only the relatively small number of bits in the partial remainders. It can thus perform the encoding in the short period of time between the receipt of successive transmission bursts, and the station can essentially transmit the packet to the end user as soon as it is received. This is in contrast to known prior systems that, after the packet is received, retrieve and encode the entire packet, that is, encode all of the data bytes in all of the cells in one encoding operation. This not only delays the forwarding of the packet to the end user, it also consumes memory resources since the entire packet must be read back before the CRC can be used to verify that the packet is error-free.
In contrast to the known prior encoders that maintain running CRC accumulations of encoded cells, and thus, must include sufficient on-chip buffer space, the partial-remainder encoder stores the encoded cells and the partial CRC remainders in an associated memory. This reduces the complexity of the encoder, by eliminating from it both the buffer space and the associated buffer control circuitry.
Brief Description of the Drawings
The above and further advantages of the invention may be better understood by referring to the following description in conjunction with the accompanying drawings, in which:
FIG. 1 is a functional block diagram of a source station;
FIG. 2 is an illustration of a cell and a frame;
FIG. 3 is a functional block diagram of a destination station that is constructed in accordance with the invention; and
FIG. 4 is a functional block diagram of an encoder that is included in the destination station of FIG. 2.
Detailed Description of Illustrative Embodiments
Section 1 discusses the encoding operations of a source station operating in accordance with AAL5. Section 2 discusses, in terms of a specific example in AAL5, the CRC verification operation of a destination station that is constructed in accordance with the current invention. Section 3 discusses in general terms the CRC verification operations of the destination station.
1. Source Station Encoding
Referring to FIG. 1, a source station 10 receiving data from, for example, a peripheral device (not shown), supplies a data packet to a CRC encoder 12. The CRC encoder 12, operating in a conventional manner, initializes, or sets, a "c"-bit checksum register 14 to a "seed" value, where c, which is the number of bits in the CRC remainder, equals 32 for AAL5. The encoder 12 then combines, that is, XOR's, the first data byte of the packet with the contents of a register 14, using XOR gates 16. The result of the encoding of the first data byte is then used to update the register 14. The first data byte is also provided to a cell processor 18.
The encoder 12 encodes the second data byte of the data packet in the same manner, by combining it with the contents of the updated register 14, and again updating the register 14 with the result. This data byte is similarly provided to the cell processor 18. The encoder repeats these encoding and updating operations with the next data byte, and so forth, until all the data bytes in the packet have been encoded. The contents of the register 14, are then supplied to the cell processor 18, as the packet CRC remainder, or checksum.
Referring also to FIG. 2, the cell processor 18 segments the data into cells 30. It first separates the data into groups of "n" bytes and appends to each group an appropriate b-byte header 34 that contains routing and other information, where in AAL5 n=48 and b=5. The processor 18 includes the 32-bit CRC remainder as the last 4 bytes of the last cell. As necessary, padding is included in one or more of the cells, to ensure that each cell has a payload 32 of 48 bytes.
The cell processor 18 supplies the cells to a frame processor 20. The frame processor 20 separates these cells and, as appropriate, the cells of other packets into groups of "f" cells. It appends header and control information 38 to the groups to form for each group a frame 36. The source station 10 then transmits the frames 36 over a network (not shown) to a designated destination station 40 (FIG. 3).
2. Destination Station Encoding Using Partial CRC Remainders
Referring now to FIG. 3, a destination station 40 receives the frames 36 (FIG. 2) from the network (not shown) and supplies them to a frame processor 20. The frame processor 20, in turn, supplies the cells that are included in the frame to the cell processor 18, and the cell processor 18 supplies the data bytes included therein to a destination CRC encoder 42.
The destination CRC encoder 42 encodes each cell separately to form, for each, a 32-bit partial CRC remainder. The encoder 42, which operates in essentially the same manner as the source CRC encoder 12, encodes each received cell as if the cell contained the first 48 data bytes of the associated data packet. It thus (i) combines the first data byte of the received cell with the contents of an initialized register 14; (ii) updates the register 14 with the result of the encoding; (iii) encodes a next data byte by combining it with the updated contents of the register 14; (iv) updates the register 14 with the result of the encoding; and (v) repeats iii and iv for each of the remaining data bytes in the cell. After the last data byte in the cell is encoded, the contents of the register 14 are appended to the cell as the partial CRC remainder.
The station 40 provides the cell and the appended partial CRC remainder to an associated memory 46. The memory 46 stores the cell as part of a linked list, which associates the cell with the preceding cells of the same packet. Each received cell, as it is received, is thus fully encoded, and need not be again encoded during packet reassembly operations.
The encoder 42 re-initializes the register 14, and encodes a next received cell to produce a next partial CRC remainder, and so forth. Each cell and its appended partial CRC remainder are stored in the memory 46, as discussed above, and linked to the previous cells in the associated packet. The encoder can thus individually encode the cells of thousands of packets as the cells are received, without having to retrieve data from the memory 46 or maintain thousands of running CRC accumulations, as is required in known prior systems.
When the last cell of a data packet and its partial CRC remainder are stored in the memory, a reassembly processor 48 in the destination station 40 verifies the packet CRC by retrieving, in order from the memory, the appended partial CRC remainders. As the partial CRC remainders are retrieved, the processor sends them to a partial CRC encoder 50. The encoder 50 manipulates, or encodes them, in accordance with update expressions that, as discussed in more detail below, are associated with the CRC code but are not the same expressions that are used by the source station 10 (FIG. 1) to encode the data.
The destination station 40 then compares, in compare circuit 56, the result of the encoding operation to the CRC pattern. If the compare circuit 56 determines that the two match, the destination station treats the reassembled packet as error-free and sends the data in the corresponding cells to an end user. Otherwise, the destination station determines that the packet contains errors and, as appropriate, sends to the source station a request that the station re-transmit the packet. The partial CRC encoder 50 is discussed in more detail with reference to FIG. 4 below.
3. Encoding Using Partial CRC Remainders--In General
In known prior systems, the CRC verification of a received packet is performed by encoding the entire packet to produce a CRC remainder, R(x), in accordance with the following expression:
where i is the length of the packet in bits, L(x) is the seed value that is used to initialize the CRC register, c is the number of bits in the CRC remainder, F(x) is a polynomial of order x.sup.i-1 with coefficients that are equal to the bits of the packet--modulo 2, and G(x) is the CRC generator polynomial. The terms x.sup.d are displacement values. For example, x.sup.i displaces the seed value, L(x), such that it is combined with the first data byte of the packet.
In cell-based systems, the packet is received as n cells, and ##EQU1## where a is the length of the data in a cell in bits, f.sub.k (x) is a polynomial of order x.sup.a-1 with coefficients that are equal to the bits of a cell--modulo 2, and n is the number of cells in the packet. Substituting into formula 1, the CRC remainder for a full packet of n cells is: ##EQU2##
As discussed above with reference to FIG. 3, a partial remainder is determined for each cell by treating the bits of the cell as the bits of the packet. Thus, by definition, the partial CRC remainder, r.sub.k (x), for each cell is:
Note that this is the same as formula 1, with a seed value of L(x)=0.
Substituting into equation 3, ##EQU3##
By defining an expression T(x) as
where c is again the number of bits in the CRC remainder, and substituting this into equation 4, ##EQU4## and R(x) can be reconstructed from the partial CRC remainders r.sub.k (x) by initializing the CRC register to R(x)=L(x) and determining for k=1 to n-1:
where "*" again represents XOR'ing.
Since T(x) is a constant, the expression H(T(x)R(x)) reduces, in a station performing the calculations using the CRC of AAL5, to a set of equations set forth in Table 2 below, and discussed below in Section 4.
The same result can be obtained by multiplying the partial results with the associated displacements by defining U(x).tbd.x.sup.a mod.G(x) and setting W(x)=L(x). Then, for k=n-1 to 1:
as a final computation
4. Encoding Using Partial CRC Remainders--In AAL5
Referring again to FIG. 2, a source station 10 in a conventional manner encodes the data bytes of a data packet in accordance with the polynomial
to produce a 32-bit packet CRC remainder. To start the encoding, the register 14, which is a 32-bit register, is initialized to all ones, or in hexadecimal notation to a value of FFFFFFFF. The contents of the register 14 are hereinafter denoted R31:0!, with the numerals in brackets representing the individual bits.
The encoder 12 encodes the first data byte D.sub.1 7:0! by combining it with, that is, XOR'ing it to, R31:23!, to produce a checksum byte B7:0!. It then combines this checksum byte with the contents of the register to produce an update checksum U31:0! in accordance with the following table, in which "*" represents XOR'ing:
The update checksum U31:0! is then used to update the register 14 to R31:0!=U31:0! before the second data byte is encoded.
The encoder next combines the second data byte D.sub.2 7:0! with R31:24! to produce an associated checksum byte B7:0! and this byte is combined with the contents of the register 14 in accordance with Table 1 above. The register 14 is again updated with the update checksum U31:0! produced by this encoding, and a next data byte D.sub.i is encoded in the same manner until all the data bytes in the packet have been encoded and a last update checksum U.sub.L 31:0! has been produced. This last checksum is supplied to the cell processor 18 as the packet CRC remainder.
The cell processor 18 groups the data into 48-byte segments and appends to each segment a 5-byte header, to form a plurality of cells. These cells are then transmitted to the destination station.
In the implementation of the destination station discussed below with reference to FIGS. 3 and 4, a seed value, L(x)=FFFFFFFF, is used to initialize the register 14 each time a cell is encoded to form a partial CRC remainder. Using this implementation, each cell is thus encoded as if it is the first cell of a packet. When the partial remainders are later iteratively combined to form the packet CRC remainder, the intermediate results are complemented to compensate for the inclusion of the seed value in second, third, . . . nth cells of the packet.
Referring now to FIGS. 3 and 4, the destination station receives the cells, each of which contain a portion of the data bytes associated with a particular data pocket. The station applies the cells to the destination CRC encoder 42 and encodes each cell individually by initializing the register 14, combining the first data byte of a cell, D.sub.1, 7:0! with the contents of the register R31:24! to produce a checksum byte B.sub.1, 7:0! and combining the checksum byte with the contents of the register R31:0! in accordance with Table 1 above. The encoder 42 uses the results of the encoding to update the register 14 and similarly encodes the remaining 47 bytes of the cell payload. The contents of the register 14 are then appended to the cell as a 32-bit partial CRC remainder, PR31:0!, and the station stores the cell and appended remainder in the memory 46.
When all the cells associated with a particular packet are encoded, the station retrieves from the memory 46 the appended partial CRC remainders PR.sub.i 31:0! and provides them to the partial CRC encoder 50. The encoder 50 takes the complement of the first partial CRC remainder PR.sub.1 31:0!, to ensure that the contribution of the seed value is not removed from this cell by the complementing of the results of the encoding, and uses the result as the initial contents of an updated partial remainder register 62. It uses the second partial CRC remainder PR.sub.2 31:0! as the initial contents of the partial remainder register 60, and it then combines the contents of the two registers 60 and 62 in XOR gates 64 in accordance with the expressions in Table 2 below:
where UP ! denotes the contents of the updated partial remainder register 62, PR ! denotes the contents of the partial remainder register 60, "*" denotes XOR'ing, and ()* denotes taking the complement.
The result of the encoding, UP31:0!, is used to update the updated partial remainder register 62. The encoder uses the next partial remainder, PR.sub.i 31:0!, as the new contents of the partial remainder register 60, and again combines the contents of the two registers in XOR gates 64. The result of the encoding, UP.sub.i 31:0!, is again used to update the register 62. The encoder continues to encode the retrieved partial CRC remainders and update the register 62, until it encodes the last partial CRC remainder, PR.sub.L 31:0!. The result UP.sub.L 31:0!, is the CRC remainder associated with the received packet. If the packet is error-free, this remainder is the same as a predetermined CRC pattern.
A numerical example involving a 221-byte data packet is attached as Appendix A.
The exemplary embodiment is described in terms of AAL5 protocol in which cells arrive at a destination station in order. With known prior encoding systems, the in-order delivery is essential to the CRC remainder calculations, since they accumulate the CRC remainder over the entire data packet. In the current system, which encodes each cell individually, the order of arrival of the cells is not critical, as long as the cells can be reassembled in the proper order, such reassembly ensures that the partial CRC remainders will also be in order. Thus the current system can, without modification, be used in connectionless networks.
The foregoing description has been limited to a specific embodiment of this invention. It will be apparent, however, that variations and modifications may be made to the invention, with the attainment of some or all of its advantages. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.
Claims
What is claimed is:
1. A system for determining if a data packet received in the form of cells contains errors, the system including: A. a first encoder for encoding the data included in a received cell in accordance with a cyclic redundancy check code to produce an associated partial remainder; B. means for appending the partial remainder to the received cell; C. storage means for storing the cell and the appended partial remainder, the storage means linking the cell by pointers to previously stored cells associated with the same data packet; D. means for determining if a cell is the last cell of a packet; E. means for retrieving the stored partial remainders associated with the cells of a selected data packet once the last cell of the selected packet has been encoded by the first encoder; and F. a second encoder for manipulating the partial remainders associated with the cells to produce a packet remainder; G. comparison means for comparing the packet remainder with a predetermined pattern, the comparison means determining that the data packet is error-free if the remainder and the pattern match.
2. The system of claim 1 further including means for retrieving the stored cells, said means retrieving the cells if the comparison means determines that the data within the cells is error-free.
3. The system of claim 1, wherein the first encoder encodes the cells by initializing the encoder for each cell to an initial value that is associated with an initial encoding of the first byte of the data packet at a source station.
4. The system of claim 3, wherein the second encoder manipulates the partial CRC remainders in accordance with Table 2, in which UP ! denotes an updated CRC partial remainder, PR ! denotes a partial remainder associated with a cell, and "*" denotes XOR'ing.
5. A communication system including: A. a source station for transmitting data, the source station including: i. a source station encoder for encoding a data packet and segmenting the data packet into fixed-sized cells, the encoder appending the result of the encoding to the packet before segmenting the packet, ii. means for transmitting the cells; and B. a destination station for receiving transmitted cells, the destination station including: i. a first encoder for encoding the data included in a received cell in accordance with a cyclic redundancy check code to produce an associated partial remainder; ii. means for appending the partial remainder to the received cell; iii. storage means for storing the cell and the appended partial remainder, the storage means linking the cell by pointers to previously stored cells associated with the same data packet; iv. means for determining if a cell is the last cell of a packet; v. means for retrieving the stored partial remainders associated with the cells belonging to a selected data packet once the last cell of the selected packet has been encoded by the first encoder; vi. a second encoder for manipulating the partial remainders associated with the retrieved cells to produce a packet remainder; and vii. comparison means for comparing the packet remainder with a predetermined pattern, the comparison means determining that the data packet is error-free if the remainder and the pattern match.
6. The system of claim 5, wherein the first encoder encodes the cells by initializing the encoder for each cell to an initial value that is associated with an initial encoding of the first byte of the data packet at the source station.
7. The system of claim 6, wherein the second encoder manipulates the partial CRC remainders in accordance with Table 2, in which UP ! denotes an updated CRC partial remainder, PR ! denotes a partial remainder associated with a cell, and "*" denotes XOR'ing.
8. A system for determining if a data packet received in the form of cells contains errors, the system including: A. a first encoder for encoding the data included in a received cell in accordance with a cyclic redundancy check code to produce an associated partial remainder; B. storage means for storing the cell and the partial remainder, the storage means linking the cell and the partial remainder by pointers to previously stored cells and partial remainders associated with the same data packet; D. means for determining if a cell is the last cell of a packet; E. means for retrieving the stored partial remainders associated with the cells of a selected data packet once the last cell of the selected packet has been encoded by the first encoder; and F. a second encoder for manipulating the partial remainders associated with the cells to produce a packet remainder; G. comparison means for comparing the packet remainder with a predetermined pattern, the comparison means determining that the data packet is error-free if the remainder and the pattern match.
9. The system of claim 8 further including means for retrieving the stored cells, said means retrieving the cells if the comparison means determines that the data within the cells are error-free.
10. The system of claim 8, wherein the first encoder encodes the cells by initializing the encoder for each cell to an initial value that is associated with an initial encoding of the first byte of the data packet at a source station.
11. The system of claim 10, wherein the second encoder manipulates the partial CRC remainders in accordance with Table 2, in which UP ! denotes an updated CRC partial remainder, PR ! denotes a partial remainder associated with a cell, and "*" denotes XOR'ing.