Abstract:
A method of delineation of a packet-based data stream in order to identify a boundary between neighbouring packets in the data stream, wherein the data stream comprises a predetermined number of bits (N); the method comprising the steps of: processing the data stream to search for the boundary between neighbouring packets in the data stream; characterised in that the method further comprises calculating the greatest common divisor (GCD) of a bit skip integer (n) where (N) and (n) are co-primes; iteratively checking after each n bits to identify the boundary between the neighbouring packets.

Description:
FIELD OF THE INVENTION 
     This invention relates to improvements in or relating to packet based data cell delineation, particularly but not exclusively at the boundaries of ATM (asynchronous transfer mode) cell delineation. 
     BACKGROUND OF THE INVENTION 
     Software recognition of ATM cell boundaries, commonly known as ATM cell delineation, on an incoming serial data stream is a computationally intensive task. Typically a method such as that outlined in the ITU-T I.432.1 specification is required. In this multiple single bit shifts followed by a boundary check per shift are employed. The reason for delineating the cells is to allow the content of the cells to be decoded. If a given RISC processor is required to delineate a plurality of serial ATM cell streams the processing requirements for the delineation algorithm will leave little computational resource for other tasks. Furthermore, if the RISC processor is of low performance (i.e. a low number of instructions processed per second) it may not be possible to process a plurality of serial ATM cell streams on that engine. Similar problems can be encountered in any embodiment of data requiring delineation based on data integrity checking. As such the present invention is relevant to more than just ATM cell delineation. 
     US 2002/0141450 relates to a scheme for cell delineation in hardware. This method processes bytes received from the data stream in multiple parallel byte processing engines that process a first set of bytes during the first cycle and a second set of bytes during a second cycle. 
     U.S. Pat. No. 5,768,274 a shows a scheme for cell delineation in hardware. This patent discloses a cell multiplexer having time divisional multiplexed cell delineation functions. 
     US 2003/0048803 relates to another hardware method for cell delineation. This application discloses a transmission convergence sub layer circuit and operating method for an asynchronous receiver. 
     U.S. Pat. No. 6,269,096 relates to yet another hardware method of cell delineation. Here blocks are received and transmitted for ATM cell delineation. The received block has a plurality of cell delineation blocks which are selected by a bus controller in order to delineate the ATM cells. 
     None of the prior art relates to any software implementation of ATM cell delineation. Accordingly none of the prior appreciate the problems of ATM cell delineation in the software environment and certainly go nowhere to solving those problems. 
     SUMMARY OF THE INVENTION 
     The present invention provides a method and apparatus as described in the accompanying claims. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Reference will now be made by way of example to the accompanying drawings, in which: 
         FIG. 1  is a flow chart of the method of ATM cell delineation in accordance with one embodiment of the invention, given by way of example, 
         FIG. 2  is a diagram of an ATM cell to show the delineation process in accordance with one embodiment of the invention, given by way of example; 
         FIG. 3  is a diagram of a RISC Processor in accordance with one embodiment of the invention, given by way of example; 
         FIG. 4  is a schematic diagram showing the cell delineation scheme in accordance with one embodiment of the invention, given by way of example. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Referring to  FIG. 1  a flow chart of the present invention is shown. A serial data stream is received or experiences a loss in delineation  100 . This commences a check  102  for the ATM cell boundary. 
     A determination is made as to whether the boundary has been found (step  104 ). If NO; n bits are skipped (step  106 ) and a new check  102  is carried out. This continues until step  102  results in a YES. If YES; a pre synchronisation state as defined in ITU-T I.432.1 (step  108 ) is achieved. 
       FIG. 2  shows a stream of ATM cells  200 , each cell or packet is represented by a rectangle  202 . One of the cells is shown in more detail at  204 . The cell includes a header  206 , a Header Error Control (HEC) element  208  and a payload  210 . The check for the ATM boundary starts at an arbitrary offset (see  212 ) in accordance with the invention. 
     If the arbitrary offset is actually on the cell boundary the pre synchronisation state of cell delineation is arrived at immediately. However, generally the arbitrary offset will not be on the cell boundary at the first instance. Hence the next check is made n bits after the starting point. 
     A plurality of subsequent checks is then carried out until the cell boundary is found. The value of n is calculated (as will be described below) to be a specific value in order to optimise the speed in which the ATM stream is delineated. The maximum number of steps from the arbitrary offset will not exceed n, due to the algorithm used and described in greater detail below. 
     Referring now to  FIG. 3  a block diagram of a possible circuit is shown. A RISC microprocessor  300  processes an ATM data stream  302 . The RISC microcode  304  in the processor includes a ATM cell delineator microcode  306  which determines the ATM cell boundary as herein described. An ATM layer  308  can, then subsequently process the delineated ATM cells in an appropriate manner. 
     ATM cell boundaries can occur at any arbitrary bit position within an incoming serial data stream. The present invention applies an algorithm (as discussed above) to the cell delineation task. This is carried out by checking every nth bit from the start, where n is an integer; rather than checking bit by bit for the start of a cell boundary. As will be appreciated this allows the cell delineation task processing requirements to be mapped to the available cycles on any given RISC processor. This reduces the processing power required for any particular ATM data stream. As a result of the reduction in processing required for each individual serial ATM stream, the RISC processor can process a plurality of serial ATM streams and still have available processing power for other tasks. In the alternative any RISC processor with low performance could be used for delineation of a plurality of serial ATM streams thereby reducing the system cost. 
     The invention makes use of the mathematical principle of coprimality, which is applied to guarantee an ATM boundary will be found no matter what the starting position in the ATM stream. The calculation of the greatest common divisor (GCD) is exploited in order to obtain the optimal step size (ie the n value or number of bits skipped for a given RISC processor) before checking for cell delineation. In mathematics the integers a and b are said to be co-prime if they have no common factor other than 1 or −1, in other words if their greatest common divisor (GCD) is 1. The fact that two integers are co-prime can be calculated in a number of different manners, but the common manner is to use the Euclidean algorithm. 
     Referring to  FIG. 4  a bit wise example of the process is shown. The RISC processor  400  contains a 32 bit register  404 . During link establishment the RISC processor needs to find the ATM cell boundaries. In the prior art the hardware based delineation schemes then check every bit for cell delineation. The present invention solves this problem by checking bits based on an n-bit interval, by allowing a low performance RISC processor to delineate the ATM cells at high line rates. 
     An ATM cell consists of 424 bits and typically the starting bit of the data stream is called bit 0. Then the bit in the stream numbered 424×i (where i=0, 1, 2 etc) will also be an ATM boundary bit. To successfully delineate an ATM cell from an arbitrary bit position the RISC processor has to “hit” a boundary bit in a finite number of steps. By selecting n to be a length co-primal to the ATM cell length the maximum number of steps that will be needed to successfully “hit” an ATM boundary bit will be less than 424. 
     The co-primality can be achieved by calculating GCD (n, 424) if the GCD result is 1 then n is co-prime with 424. For the prior art n=1. By carefully calculating the value of n the cycle budget for the cell delineation can be matched to the RISC processor bandwidth. The number of cycles required to run the cell delineation algorithm is known, therefore the number of iterations (or steps) executed is programmable using the co-prime principle and GCD calculation. 
     For example if n=33, the cell delineation task will require only 3% of the RISC processor cycles that are required when checking bit by bit. It will be appreciated that the data size of the RISC processor is significant. For example a 16-bit machine can choose an n of 15 or 17 as 15 and 17 are both co-prime with 424. For a 32 bit machine 31 and 33 are the best options for n. It will be appreciated that for each size of machine there will be a number of different options for n. It will also be appreciated that sometimes the selection of n may be compromised to some extent in order to ease the implementation with respect to cycle budget availability. 
     Referring again to  FIG. 4 , the serial data stream  402  passes through the 32-bit register  204  of the RISC processor. As the data is passed through the RISC processor the serial data stream is checked after every n bits. The cyclic redundancy check (CRC) is calculated on each 32 bits and compared with the next eight bits of serial data in the stream  402 . A series of shifts and logical OR functions manipulate the serial data stream in order to allow cell boundary checks to be carried out after n bits. 
     As has previously been indicated this invention is not just limited to ATM cell delineation schemes but may be used in any other system where a stream of packets need to be delineated. For example, it can be used to delineate fixed-length packets in a serial data stream such as fixed-length IP packets carrying 3G voice starting at arbitrary offsets within the frame. 
     It will be appreciated that the above described invention is not limited to the specific embodiment therein, it can include a number of alternatives that fall within the scope of the invention. For example, the length and type of cell, the nature of the algorithm, the manner in which the “skipping” is determined may be other than co-primality. Similarly as has been previously described when co-primality and GCD are used the value of n can be varied in accordance with the data bus width of the RISC processor, the size of the RISC processor registers and the required operating parameters of the RISC processor in a given system.