Abstract:
Packet switching node in a communication system includes apparatus for receiving incoming information packets or frames which contain header portions with formatting control blocks. Information in the frame&#39;s header contains frame alteration commands for modifying the information in the frame. The modifications include adding new information, deleting information, and overlaying information. Decoders and control devices in an alteration engine interpret the commands and apply the modifications to the frame data. Common and standard data patterns are stored for insertion or overlaying to conserve data packet space.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
   This patent application is related to U.S. patent application by Calvignac et al., Ser. No. 09/792,557 for STORING FRAME MODIFICATION INFORMATION IN MEMORY, filed Feb. 23, 2001. 
   BACKGROUND OF THE INVENTION 
   1. Field of the Invention 
   1. This invention relates to network communication systems. More particularly, it relates to modification of frames (message packets) in nodes forming a path from sender to receiver. 
   2. Description of the Related Art 
   Packet switching networks operate by relaying data along a series of nodes from a sending node to a final receiving node. These nodes or points are often computers programmed to process the frames, forwarding them to other nodes if necessary according to routing information in the frame. 
   Communications among computers and networks operate at ever-increasing speeds. There are also a number of differing protocols, often requiring changes to formats along the communication paths. Protocols dictate the format of header information which includes source and destination addresses and data which can include digitized voice data. The information transmitted in packets or frames is usually of predetermined sizes although there is flexibility in the dimensions of message frames. Frame alterations or modifications sometimes need to be changed, added to, or deleted from frame headers. The changes can be implemented in hardware but hardwired modification circuits are not as versatile as software implementations which can be more easily changed albeit slower in operation. A hybrid system uses a combination of hardware, universal in nature, and software for control. 
   There are several known systems for processing frames in a network structure. The simplest might be merely to transmit the information to the next terminal. More adaptable systems may use frame alteration at each node for more efficient transmission through the network 
   BRIEF SUMMARY OF THE INVENTION 
   In accordance with the invention, a packet switching node in a communication system includes apparatus for receiving incoming information packets or frames. A processor controls frame alteration commands for modifying the information in the frame. The modifications include adding new information, deleting information, and overlaying information. Decoders and control devices in an alteration engine interpret the commands and apply the modifications to the frame data. Common or often used data patterns can be stored in alteration arrays for insertion into a data frame, precluding the necessity of using packet data space. 

   
     BRIEF DESCRIPTION OF THE DRAWING 
     The invention is described in detail by referring to the various figures which illustrate specific embodiments of the invention, and wherein like numerals refer to like elements. 
       FIG. 1  is an illustration of an frame alteration control block format. 
       FIG. 2  is an example of a use of the format. 
       FIG. 3  is a flowchart showing a manner of operation for one embodiment of the invention. 
       FIG. 4  is a block diagram of an apparatus for practicing the invention. 
       FIG. 5  is a block diagram of a frame alteration unit. 
       FIG. 6  is an illustration of an unaltered frame and the resulting altered frame. 
       FIG. 7  is a logic diagram of an alteration engine according to the invention. 
       FIG. 8  is a logic diagram for supplying a new byte to an output frame. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   The following explanation discloses a preferred mode of practicing the invention but other implementations are possible given the teachings of the invention. 
   U.S. patent application Ser. No. 09/792,557 for STORING FRAME MODIFICATION INFORMATION IN MEMORY, described in more detail in the Cross Reference section of this application, is incorporated herein by reference. This invention is relates particularly to the frame alteration LOGIC  212  as shown in  FIG. 2  thereof. 
   As frames arrive from the network, they are stored in a memory. An area is reserved in memory immediately preceding the frame&#39;s data for storage of one or more frame alteration control blocks. During frame processing, software executed by a processor writes the frame alteration commands into the frame alteration control blocks. The frame is then queued for transmission onto the network by placing it in a port queue. Hardware apparatus then services the port queue by reading the frame alteration control blocks, applying the requested alterations to the frame data and transmitting the modified frame onto the network. 
     FIG. 1  shows a 128-bit (quadword) frame alteration control block. In  FIG. 1 , a one-bit bottom-of-stack field  11  specifies the frame is the bottom of stack if set to 1. The first frame alteration control blocks in a list of multiple frame alteration control blocks will have the first bit set to 0. The bottom-of-stack bit is then set to 1 in the frame alteration control block immediately preceding the first quadword of the packet data. 
   A three-bit field  12  indicates the type of frame access control block. More than one type can be defined, each containing frame alteration commands that are specific to a particular scenario. Some frame access control block types may be optimized for Ethernet frame alteration and others, for Packet-over-Sonet frame alteration. The system uses the frame alteration control block type field  12  to determine how to parse information in the Frame Alteration Commands field  17 . 
   A four-bit displacement field  15  is used only in the bottom-of-stack frame alteration control block to define the offset to the first valid packet data byte in the first quadword of the packet data. This field is required as the starting byte position to skip over unused bytes in the first quadword of the packet data. 
   Bits  8  through  127  of the quadwords in the frame alteration control block stack contain the frame alteration commands  17 . These are the commands to be applied to a packet as it is transmitted. The frame alteration commands are specific to the frame alteration control block type. 
     FIG. 2  shows an example of an frame alteration control block stack with two quadwords of a data packet. The bottom-of-stack field  201  of the first frame alteration control block is set to 0 as are those of the following two quadwords. The bottom-of-stack field  202  of the fourth quadword is set to 1 since it is at the bottom of the stack. The displacement field  203  of the fourth quadword points to the beginning of the packet data in the following quadword or buffer. 
   The flowchart of  FIG. 3  illustrates an example of a frame alteration procedure where the changes are to insert, to overlay, or to delete data within the frame. A terminal block  301  starts the procedure. A process block  302  fetches the frame alteration control block from a memory device storing the frame to be altered and parses it into the frame alteration control block portion and the data portion. The frame alteration control block commands are stored in hardware registers by a process block  303 . In a process block  305 , the input data pointer is set to the value of the DISP field of the frame to skip the unused bytes in order to locate the beginning of the data in the input frame and the pointer to the output data bytes is set to zero. The first input byte is read from the input frame by an input/output block  315 . 
   A decision block  306  determines whether the current input byte is to be deleted. This is accomplished by testing the contents of the input data pointer against the OFFSET field in the frame alteration control block for equality. If the frame alteration control block command specifies that the current data byte is to be deleted, the input data byte pointer is incremented by a process block  307 . No further is action is performed and the present data byte is not written to the output as part of the altered frame. The process then continues at a decision block  318  which determines whether the last input data byte has been read from the frame alteration control block storage memory, i.e., whether the end of the input frame has been reached. If so, the process is exited at a terminal block  319 . 
   If the end of the frame has not been reached, the process continues at the input/output block  315  to read the next input data byte. 
   If the frame alteration control block command is not a delete instruction, the process continues from the decision block  306  to a decision block  308  to determine whether the frame alteration control block command is an insert instruction. If so, the replacement byte is read from the appropriate frame alteration control block field or the alteration array  511  ( FIG. 5 ) and written as the output byte by a process block  316  Next, the output data pointer is incremented by a process block  317 . The end-of-frame test is then performed at the decision block  318  as previously described. 
   If the frame alteration control block command is not an insert instruction, the process continues from the decision block  308  to a decision block  311  to determine whether it is an overlay instruction. If so, then the new (overlaying) byte is read from the frame alteration control block data field and the input data pointer is incremented in a process block  310 . The overlaying byte is then written as the output byte. 
   If the frame alteration control block command is neither a delete, an insert, nor an overlay instruction, then the byte read from the input frame is written as the output byte after incrementing the input data pointer at the process block  310 . 
   Adding other frame alteration control block commands is within the skill of the art given the present explanation. For example, bytes can be incremented, decremented, inverted, and otherwise modified as desired. 
   In  FIG. 4 , a data flow controller  401  is coupled to a processor  403  for generating the frame alteration commands based on the protocol of the network. In the data flow controller  401 , a receive interface  405  transfers a frame from the network to a memory interface  407  for storage in a memory. 
   The memory interface  407  extracts the frame header from the memory  415  and transfers it to the processor  403  via a control interface  409 . The processor  403  generates the frame alteration commands contained in the header and returns frame alteration control blocks to the memory  415  via the control interface  409  and memory interface  407 . The frame alteration control blocks are stored in the memory  415  immediately preceding the beginning of the frame data. 
   Next, the data flow controller  401  reads the frame alteration control block and data from the memory  415  under the control of a transmit controller  411  and transfers them to a read unit  417 . The frame alteration control block and data are transferred to a frame alteration unit  419  which applies the alterations according to the contents of the frame alteration control blocks. The output frame data is then moved to a transmit unit  421  which transmits them to the network. 
   Details of the frame alteration unit  419  are shown in  FIG. 5 . A frame parser  501  separates the frame alteration control blocks and frame data. Unaltered and unaligned frame data are sent a data aligner  503  which realigns the data to even 16-byte boundaries since the unaltered frame data may not be so aligned. This was accomplished by setting data pointers as shown in the process block  305  of  FIG. 3 . The aligned data is then applied to an alteration engine  505 . 
   The frame alteration control blocks are applied from the frame parser  501  to an frame alteration control block decoder  507 . The frame alteration control block decoder  507  interprets the frame alteration control block bits and moves the frame alteration commands to a frame alteration controller  509 . The frame alteration controller  509  disassembles the frame alteration commands from the frame alteration control block decoder  507  into basic instructions which are coupled to the alteration engine. 
   An alteration array  511  is an optional storage device that supplies frequently used data patterns to be inserted or overlay data in the input frame under alteration. When a frame alteration command is decoded that designates one of the patterns is to be inserted or to overlay frame data, the designated configuration is extracted from the alteration array  511  by the frame alteration controller  509  and moved to the alteration engine  505 . 
   The described operations accomplish the frame alterations in the alteration engine  505  by using the instruction to insert, to delete, to overlay, to increment, plus others as needed to assemble altered data frames which are then applied to the transmit unit  421  of  FIG. 4 . The process for executing the instructions were described above with reference to  FIG. 3 . 
     FIG. 6  shows an example of a frame alteration.  FIG. 6A  illustrates an exemplary input frame with its accompanying frame alteration control block and  FIG. 6B  illustrates a resulting altered output frame. This example inserts four bytes of data from the frame alteration control block (top row of  FIG. 6A ) at a 50-byte data offset specified by bits  16  to  31  of the frame alteration control block. 
   The BOS (bottom-of-stack bit  0 ) is set to 1 to indicate that this is the only frame alteration control block in the stack. The frame alteration control block TYPE (bits  1 - 3 ) identifies the format of bits  8 - 127 . The DISP field (displacement bits  4 - 7 ) specifies where the data begins. The CMD (command field bits  8 - 15 ) is a unique code which in this example indicates that there is 4-byte data field to be inserted at a point in the data field specified-by the OFFSET (bits  16 - 31 ). The data to be inserted is the field comprising bits  32 - 63 . 
     FIG. 6B  shows the altered frame as transmitted. The data is aligned on even numbered 16-byte data fields and the inserted data is shown at the 50th byte, i.e., byte 48 plus 16 bits (two bytes). 
   A hardware implementation of the alteration engine  505  in  FIG. 5  is shown in  FIG. 7 . Bytes from the unaltered input frame are stored in a register  709 . Bytes from the frame alteration control block field to be inserted or overlaid are stored in a register  707 . Each successive byte is stored by a timing signal CLK. 
   The command in the frame alteration control block CMD field is gated to a decoder  701  to be executed. In the example under consideration, the instructions are overlay (OV), insert (IN), and delete (DE). The OV and IN output signals from the decoder  701  are applied to input terminals of an OR gate  715 . The output signal from the OR gate  715  is applied to an input terminal of an AND gate  717 . 
   The other input signal to the AND gate  717  is from a flip-flop  741  which is set by a comparator  711  when the READ ADDRESS is equal to the OFFSET field of the frame alteration control block. The flip-flop  741  is reset by an EOF signal indicating that the end of the data to be inserted or overlaid has been reached. This permits the INPUT PTR counter  703  to continue to advance and to address the next input data bytes from the input frame&#39;s data field. The DISP field contents of the frame alteration control block are set into a counter INPUT PTR  703  by an initialization signal INIT and is incremented by successive CLK timing signals when the command being executed is not an INSERT instruction by means of an AND gate  737  and an INVERTER  739 . When the instruction is an INSERT, the inverter  739  inhibits the AND gate  737 . The INPUT PTR counter  703  keeps track of the next byte to be read from the unaltered input frame&#39;s data field so its output signals also supply the read address of the bytes. 
   The other input to the comparator  711  is an offset register  705  which is loaded by the INIT signal and stores the contents of the OFFSET field of the frame alteration control block. The comparator  711  supplies an output signal when the read address from the INPUT PTR  703  equals the OFFSET value, causing the flip-flop  741  to be set at the next CLK signal. The output signal from the flip-flop  741  enables the AND gate  717  when bytes are to be overlaid or inserted during execution of an overlay or insert instruction from the decoder  701  as indicated by the output signal from the OR gate  715 . 
   When the AND gate  717  is enabled, the new byte is passed by an AND gate  723  to an OR gate  724 . When the AND gate  717  is disabled, either because the OFFSET address has not been reached or the command being executed is neither an overlay or insert instruction, an inverter  719  enables an AND gate  721  to pass the current input byte from the register  709  to the OR gate  724 . 
   The byte from the OR gate  724  is coupled to an AND gate  731  to be gated as the output byte at the next CLK signal if the command is not a delete instruction (DE from the decoder  701 ). The CLK signal is applied to an AND gate  729  except when inhibited by the output from an INVERTER  727  when the command being executed is a DELETE instruction. When the output signal from the AND gate  729  gates the output byte at the AND gate  731 , it also increments an OUTPUT PTR counter  735 . 
   Some data patterns are common and often repeated. For example, converting from one protocol to another usually necessitates that fixed patterns be inserted or overlaid on part of the frame data.  FIG. 8  is a block diagram showing details within the frame alteration controller  509  in  FIG. 5  for providing the new byte to the NEW register  707  of  FIG. 7 . 
   Data to be inserted from the FACB header is coupled to one input of an AND gate  801 . A pattern identifier, which can be an address supplied by a frame alteration command, reads a desired data pattern from the alteration array  511  to an input of an AND gate  803 . Source control signals from a frame alteration command and decoded by the FACB decoder  507  enables one of the AND gates  801  or  803  if a new byte is to be supplied to the alteration engine. The output from an enabled AND gate is applied to an OR gate  807  to supply the new byte. 
   The contents of the alteration array  511  can be dynamic. That is, its contents can be altered under software control to enable the logic to handle a wide variety of protocols and standard data patterns. 
   The operation of the read unit of  FIG. 5  as well as the interfaces are well known in the art and need not be explained in detail for an understanding of the invention or how to make and to use it. 
   While the invention has been particularly shown and described with reference to a preferred embodiment thereof, it will be understood by those skilled in the art that various changes and modifications in form and details may be made therein without departing from the spirit and scope of the invention according to the following claims.