Apparatus and method for operating on data in a data communications system

• US 6,438,678 B1
• Filed: 08/11/1998
• Issued: 08/20/2002
• Est. Priority Date: 06/15/1998
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bahr, Raymond G., Cashman, John D., Ye, Wei, Riley, Paul M., Osler, Bruce P., Grummer, Grant
• Primary Examiner(s): Courtenay, III, St. John
• Application Number:
  US09/132,621
• Time in Patent Office: 1,470 Days
• Field of Search: 709/230, 709/247, 709/250, 709/253, 709/310, 710/105, 710/106, 712/28-39
• US Class Current: 712/34
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30072 to perform conditional operations, e.g. using predicates or guards
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: H04L 69/12 Protocol engines
• CPC Class Codes: H04L 69/18 Multiprotocol handlers, e.g. single devices capable of handling multiple protocols
• CPC Class Codes: H04L 69/324 in the data link layer [OSI layer 2], e.g. HDLC
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A programmable data communications device is provided to process multiple streams of data according to multiple protocols. The device is equipped with a co-processor including multiple, programmable processors allowing data to be operated on by multiple protocols. The programmable processors within the co-processor include extended instruction sets including instructions providing the operations of zero stuffing, CRC computation, partial compare, conditional move, and trie traversal. These instructions allow the processor(s) of the co-processor to more efficiently execute programs implementing data communications protocols. Since each processor is programmable, protocols standards which change may be accommodated. A network device equipped with the co-processor can handle multiple simultaneous streams of data and can implement multiple protocols on each data stream. The protocols can execute within the co-processor either independently of each other, or in conjunction with each other.

Claims

1. An apparatus comprising:

a programmable processor for executing multiple protocols;

a memory system coupled to the programmable processor;

a programming/control interface coupled to the memory system and to the programmable processor, the programming interface accepting a communications program downloaded into the memory system from a host computer,

the programmable processor executing multiple protocols including the communications program that is downloaded.

2. The apparatus of claim 1, in which the programmable processor includes:

a first programmable processor unit and

a second programmable processor unit; and

wherein the memory system includes;

a first local memory unit coupled to the first programmable processor;

a second local memory unit coupled to the second programmable processor;

a bus system coupled to the first and second programmable processor units and the first and second local memory units, the bus system having a data interface capable of being connected to the host computer for transferring data between the host system and the first and second programmable processor units and the first and second local memory units; and

wherein the first and second programmable processor units include an extended instruction set allowing the first and second programmable processor units to be programmed with instructions to concurrently execute multiple protocols independent of each other, or allowing the first and second programmable processor units to be programmed with instructions to concurrently execute multiple protocols in conjunction with each other.

3. The apparatus of claim 2, wherein the protocol executed by the first programmable processor unit is an encryption protocol to encrypt data and the protocol executed by the second programmable processor unit is a decryption protocol to decrypt data.

4. The apparatus of claim 2, wherein the protocol executed by the first programmable processor unit is an encryption protocol to encrypt data and the protocol executed by the second programmable processor unit is a compression protocol to compress data.

5. The apparatus of claim 2, wherein the protocol executed by the first programmable processor unit is an compression protocol to compress data and the protocol executed by the second programmable processor unit is an decompression protocol to decompress data.

6. The apparatus of claim 2, wherein the protocol executed by the first programmable processor unit is an decryption protocol to decrypt data and the protocol executed by the second programmable processor unit is an decompression protocol to decompress data.

7. The apparatus of claim 2, wherein the first and second programmable processor units are each programmed to execute at least one protocol selected from the protocol group consisting of:

encryption, decryption, compression, decompression, HDLC framing, point-to-point protocol, serial line interface protocol, MNP5-Microcom network protocol, V.42bis.

8. The apparatus of claim 1, wherein the programmable processor unit includes:

a) an input interface for loading the communications programs from the memory system and for loading communications data;

b) a first unit including processor instruction logic circuits for executing first portions of the communications programs;

c) a second unit including extension processor instruction logic circuits for executing second portion of the communications programs and for processing at least one portion of the communications data; and

d) an output interface for storing results of the processing.

9. The apparatus of claim 1, wherein the first and second programmable processor units are 32-bit RISC processors.

10. A network device used for processing data communications comprising:

an input interface receiving data;

an output interface for transmitting data;

a memory for storing data;

a system bus coupling the input interface, the output interface, and the memory;

a central processing unit coupled to the system bus, the central processing unit controlling the receipt of data by the input interface and storing the data in the memory;

a co-processor coupled to the system bus, the co-processor having an internal programmable processor unit programmed to execute multiple protocols, the coprocessor;

(i) retrieving the data from the memory upon an indication from the central processing unit,

(ii) executing the multiple protocols on the data for which the internal programmable processor unit is programmed;

(iii) returning the data to the memory for transmission from the output interface of the network device.

11. The network device of claim 10, wherein the co-processor includes first and second programmable processor units each including an extension instruction set allowing the first and second programmable processor units to be programmed with instructions to concurrently execute protocols to encrypt and decrypt and compress and decompress data independent of each other.

12. The network device of claim 10, wherein the co-processor includes first and second programmable processor units each including an extension instruction set allowing the first and second programmable processor units to be programmed with instructions to concurrently execute protocols to encrypt and decrypt and compress and decompress data in conjunction with each other.

13. The network device of claim 11, wherein the co-processor includes first and second programmable processor units each including an extension instruction set allowing the first and second programmable processor units to be programmed with instructions to concurrently execute protocols to encrypt and decrypt and compress and decompress data in conjunction with each other.

14. The network device of claim 10, wherein the co-processor further includes first and second programmable processor units each comprising:

a) an input interface for loading communications programs and communications data;

b) a first unit including processor instruction logic circuits for executing first portions of the communications programs;

c) a second unit including extension processor instruction logic circuits for executing second portion of the communications programs and for processing at least one portion of the communications data; and

d) an output interface for storing results of the processing.

15. The network device of claim 14 wherein the extension processor instruction logic circuits execute stuffing and unstuffing instructions.

16. The network device of claim 14 wherein the extension processor instruction logic circuits execute multiple compare instructions.

17. The network device of claim 14 wherein the extension processor instruction logic circuits execute trie-traversal instructions.

18. The network device of claim 14 wherein the extension processor instruction logic circuits execute CRC calculation instructions.

19. A method for processing data in a network device, the method comprising the steps of:

programming a co-processor in the network device with a plurality of communications program;

accepting communications data into the network device via an input interface;

transferring the communications data into the co-processor;

executing at least one of the plurality of communications programs within the co-processor to operate on the communications data;

transferring the communication data from the co-processor.

20. The method of claim 19, wherein the executing step includes the steps of:

executing a first communications program selected from the plurality of communication programs to perform a first protocol operation on the communication data;

maintaining the communications data within the co-processor after the executing a first communications program step; and

executing a second communication program selected from the plurality of communications program to perform a second protocol operation on the communications data.

21. A processor comprising:

an input interface loading communications programs and communications data;

a first unit including processor instruction logic circuits executing first portions of the communications programs;

a second unit including extension processor instruction logic circuits executing second portion of the communications programs and processing at least one portion of the communications data; and

an output interface storing results of the processing.

22. The processor of claim 21, wherein the processor is a RISC microprocessor.

23. The processor of claim 21, wherein the communications programs include:

compression/decompression protocols.

24. The processor of claim 21, wherein the communications programs include:

encryption/decryption protocols.

25. The processor of claim 21, wherein the extension processor instruction logic circuits include:

a zero stuffing instruction logic circuit including;

an input logic device which accepts the communications data;

a detecting logic device which detects a predetermined sequence of bits within the communications data;

an insertion logic device which inserts a modifier into the communications data creating a modified data; and

an output logic device which stores the modified data in a predefined location.

26. The processor of claim 25, wherein:

the insertion logic device creates overflow data; and

the output logic device stores the overflow data in a second predefined location and maintains overflow state information.

27. The processor of claim 25, wherein:

the predetermined sequence of bits is a continuous series of five one bits; and

the modifier is a single zero bit.

28. The processor of claim 25, wherein:

the zero stuffing instruction logic circuit further includes a means for activating the zero stuffing instruction logic circuit a plurality of times;

upon each activation the insertion logic device produces an overflow; and

the overflow is accepted by the input logic device upon subsequent activation of the zero stuffing instruction logic circuit.

29. The processor of claim 21, wherein the extension processor instruction logic circuits include:

a zero unstuffing instruction logic circuit including;

an input logic device which accepts the communications data;

a detecting logic device which detects a first predetermined sequence of bits within the communications data;

a removal logic device which removes a stuffed bit from the communications data creating modified data; and

an output logic device which stores the modified data in a predefined location.

30. The processor of claim 29, wherein:

the output logic device maintains borrow state and error state information.

31. The processor of claim 29, wherein:

the first predetermined sequence of bits is a continuous series of five one bits followed by a zero bit; and

the stuffed bit is a single zero bit.

32. The processor of claim 29, wherein:

the zero unstuffing instruction logic circuit further includes a means for activating the zero unstuffing instruction logic circuit a plurality of times;

upon each execution the removal logic device modifies a borrow result; and

the borrow result is accepted by the input logic device upon subsequent execution of the zero unstuffing instruction logic circuit.

33. The processor of claim 21, wherein the extension processor instruction logic circuits include:

a partial subtraction and conditional move instruction logic circuit including;

an input logic device which accepts a first communications data, a second communications data and a third communications data;

a comparing logic device which performs a comparison between the first communications data and the third communications data, if the comparison results in the first communications data being equal to the third communications data then a down traversal state is set, if the comparison results in the first communications data being greater than the third communications data then the second communications data is copied into a predefined location and no state is set, if the comparison results in the first communications data being less than the third communications data then an insertion state is set and the first communications data is inserted into a trie data structure; and

an output logic device which stores the third communications state in a predefined location, stores the first communications data into the trie data structure and maintains the down traversal state and the insertion state information.

34. The processor of claim 21, wherein the extension processor instruction logic circuits include:

a partial compare and conditional move instruction logic circuit including;

an input logic device which accepts a first communications data and a second communications data;

a comparing logic device which performs a comparison between the first communications data and the second communications data, if the comparison results in the first communications data being equal to the second communications data then a terminate traversal state is set, if the comparison results in the first communications data being not equal to the second communications data then the first communications data is copied to a predefined location and no state is set; and

an output logic device which stores the first communications data in a predefined location and maintains the terminate traversal state information.

35. The processor of claim 21, wherein the extension processor instruction logic circuits include:

a multiple compare instruction logic circuit including;

an input logic device which accepts a first communications data, a second communications data and a third communications data;

a first comparing logic device which performs a comparison between the first communications data and a series of predefined characters in the third communications data, if the comparison results in the first communications data being equal to any character in the series of predefined characters then a character match state is set;

a second comparing logic device which performs a comparison between the first communications data and a predefined boundary, if the first communications data is within the predefined boundary then a character boundary state is set; and

an output logic device which maintains the character match state and the character boundary state information.

36. The processor of claim 35, wherein the predefined boundary is the range of 8-bit characters from 0x00 to 0x1F.

37. The processor of claim 21, wherein the extension processor instruction logic circuits include:

a CRC instruction logic circuit including;

an input logic device which accepts a first communications data, a second communications data and a third communications data;

a calculating logic device which computes a CRC value based upon the polynomial defined in the first communications data, the current state of the CRC calculation stored in the second communications data and a third communications data containing a portion of a message upon which to calculate a CRC; and

an output logic device which stores the CRC value in a predefined location.

38. The processor of claim 37, wherein:

the CRC instruction logic circuit further includes a means for activating the CRC instruction logic circuit a plurality of times;

upon each execution the calculating logic device produces a partial CRC value; and

the partial CRC value is accepted by the input logic device upon subsequent execution of the instruction.

39. A data processing method comprising the steps of:

a) loading communications programs and communications data via an input interface;

b) executing a first portion of the communications programs via a first unit including processor instruction logic circuits;

c) executing a second portion of the communications programs via a second unit including extension processor instruction logic circuits;

d) processing at least one portion of the communications data; and

e) storing results of the processing via an output interface.

40. The method of claim 39, wherein the executing a second portion step includes a step of zero stuffing, further comprising the steps of:

a) accepting the communications data;

b) detecting a predetermined sequence of bits within the communications data;

c) inserting a modifier into the communications data creating a modified data and an overflow data; and

d) storing the modified data in a predefined location.

41. The method of claim 40, wherein:

a) the inserting a modifier step further comprises creating an overflow data; and

b) the storing step further comprises storing the overflow data in a second predefined location and maintaining overflow state information.

42. The method of claim 40, wherein:

a) the predetermined sequence of bits detected is a continuous series of five one bits; and

b) the modifier inserted is a single zero bit.

43. The method of claim 40, including the steps of:

a) executing the step of zero stuffing a plurality of times;

b) upon each execution the inserting a modifier step produces an overflow data; and

c) the overflow data is accepted by the accepting the communications data step upon subsequent execution of the step of zero stuffing.

44. The method of claim 39, wherein the executing a second portion step includes a step of zero unstuffing, further comprising the steps of:

a) accepting the communications data;

b) detecting a first predetermined sequence of bits within the communications data;

c) removing a stuffed bit from the communications data creating a modified data; and

d) storing the modified data in a predefined location.

45. The method of claim 44, wherein:

the step of storing further comprises maintaining borrow state and error state information.

46. The method of claim 44, wherein:

a) the first predetermined sequence of bits detected is a continuous series of five one bits followed by a zero bit; and

b) the stuffed bit is a single zero bit.

47. The method of claim 44, including the steps of:

a) executing the step of zero unstuffing a plurality of times;

b) upon each execution the removing a second predetermined sequence of bits step modifies a borrow result; and

c) the borrow result is accepted by the accepting the communications data step upon a subsequent execution of the step of zero unstuffing.

48. The method of claim 39, wherein the executing a second portion step includes a step of partial subtraction and conditional moving, further comprising the steps of:

a) accepting a first communications data, a second communications data and a third communications data;

b) comparing first communications data and the third communications data, if the comparison results in the first communications data being equal to the third communications data then a down traversal state is set, if the comparison results in the first communications data being greater than the third communications data then the second communications data is copied into a predefined location and no state is set, if the comparison results in the first communications data being less than the third communications data then an insertion state is set and the first communications data is inserted into a trie data structure; and

c) storing the third communications state in a predefined location, storing the first communications data into the trie data structure and maintaining the down traversal state and the insertion state information.

49. The method of claim 39, wherein the executing a second portion step includes a step of partial compare and conditional moving, further comprising the steps of:

a) accepting a first communications data and a second communications data;

b) comparing the first communications data and the second communications data, if the comparison results in the first communications data being equal to the second data then a terminate traversal state is set, if the comparison results in the first communications data being not equal to the second data then the first communications data is copied into a predefined location and no state is set; and

c) storing the first communications state in a predefined location and maintaining the terminate traversal state information.

50. The method of claim 39, wherein the executing a second portion step includes a step of multiple comparing, further comprising the steps of:

a) accepting a first communications data, a second communications data and a third communications data;

b) comparing first communications data and a series of predefined characters in the third communications data, if the comparison results in the first communications data being equal to any character in the series of predefined characters then a character match state is set;

c) comparing first communications data and a predefined boundary, if the first communications data is within the predefined boundary then a character boundary state is set; and

d) maintaining the character match state and the character boundary state information.

51. The method of claim 50, wherein the predefined boundary compared is the range of 8-bit characters from 0x00 to 0x1F.

52. The method of claim 39, wherein the executing a second portion step includes a step of CRC computation, further comprising the steps of:

a) accepting a first communications data, a second communications data and a third communications data; and

b) calculating a CRC value based upon;

i) the polynomial defined in the first communications data;

ii) the current state of the CRC calculation stored in the second communications data; and

iii) a third communications data containing a portion of a message upon which to calculate a CRC; and

c) storing the CRC value in a predefined location.

53. The method of claim 52, including the steps of:

a) executing the step of calculating a CRC value a plurality of times;

b) upon each execution the calculating a CRC value step produces a partial CRC value; and

c) the partial CRC value is accepted by the accepting an input bit stream step upon subsequent execution of the step of calculating a CRC value.

c) the partial CRC is accepted by the accepting a first communications data step upon a subsequent execution of the step of CRC computation.