Data processor with trie traversal instruction set extension

Details Data processor with trie traversal instruction set extension Data processor with trie traversal instruction set extension

1998-11-06

2001-01-16

Donaghue, Larry D. (Department: 2783)

Electrical computers and digital processing systems: processing

Processing control

Specialized instruction processing in support of testing,...

C712S209000, C712S036000

Reexamination Certificate

active

06175915

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to data communications devices and more specifically to network devices which implement protocols to operate on data in a data communications system.
BACKGROUND OF THE INVENTION
In digital communications systems, data is routinely transmitted between many processing devices over a network. For example, in computer networks such as the Internet, data is typically sent from one computer to another through network communications devices such as modems, hubs, routers, bridges, switches and/or other computers interconnected by transmission media or data links. The data itself is stored and communicated as a series of binary digits (bits) represented by zeros and ones. During data communications, the manner in which the bits of data are specifically arranged and the order in which they are exchanged between devices is called a protocol. Protocols are usually established by industry standards. There are many different types of protocols serving different purposes, but each typically involves a sending device that arranges data in one manner, and a receiving device that detects the specific arrangement of the data in order to make use of the data upon reception.
For example, blocks of data can be reduced in size by compression protocols before transmission from a sending computer in order to conserve bandwidth. When privacy is desired, data can be altered by encryption protocols into a state that makes the data unreadable by anyone or any device not authorized to read the data. The data can travel across the network in an encrypted and compressed state until it reaches its destination. Upon receipt, the receiving computer decrypts (i.e. decodes) and decompresses the data according to these protocols into a form useable by an intended application.
In some data communications devices, the main central processing unit (CPU) of the device is responsible for performing protocols on data, such as the compression, decompression and encryption, decryption protocols noted above. In this case, the protocols are performed completely under software control by a program stored in memory. In other devices, separate dedicated hardware processors are provided to perform individual protocols. In hardware implementations, the CPU of the device merely schedules the flow of data through the device, and at the appropriate time, instructs each separate dedicated processor to perform a single respective protocol for which that dedicated processor is designed.
For instance, in a modem, as data is received from the sending application it is buffered in memory before transmission onto a computer network. The CPU in the modem assembles the data into a packet, and then compresses that packet of data. After compression, if privacy is desired, the CPU then encrypts the data packet. When the CPU has completed its task, the packet is processed further and transmitted from the modem.
An example of one type of compression/decompression protocol is called V.42bis. To compress data, V.42bis creates a dictionary of commonly occurring strings of bits in data. For a string that commonly occurs, the dictionary specifies a short replacement string which, when transmitted, takes up less space, and therefore saves network bandwidth. Compressed data according to V.42bis is stored in a data structure called a “trie”. Tries are a species of multi-way search trees, designed to represent sets of character strings. To decompress data stored in a trie, a complex series of trie traversals are required to reconstruct the original data. Prior art systems perform these trie traversals in either software or with a dedicated hardware processor, as explained above.
Other protocols exist that are used to format data during data communications in order for devices to communicate effectively and efficiently. For instance, during assembly of data packets, signaling information must be provided along with the actual message data in the packets for communications to take place. Various signaling protocols have been developed to support uniform communication of data packets.
One such widely used protocol is the High Level Data Link Control (“HDLC”) protocol, as defined in Level 2 of the Open Systems Interconnection (“OSI”) model. HDLC is a bit-oriented protocol for sending packets between devices. HDLC requires the sender to distinguish the start and end of a packet from the actual data portion of the packet. To do so, HDLC uses a flag to indicate the start and end of packets. The flag consists of a zero bit followed by six one bits and ends with a zero bit, and appears as 01111110. In HDLC, a process called “zero stuffing” can be used to distinguish the flag portion of a packet from the data portion (which may itself contain an embedded series of ones that could be mistaken for a flag). In zero stuffing, a zero bit “0” is inserted into packet data being transmitted if five continuous one bits “11111” are detected. Thus, zero stuffing converts “11111” into “111110” in the data portion of a packet, in order to distinguish the data from the beginning and end of the packet. The receiver of the “stuffed” data packet then “unstuffs” the data by removing any zero bit following five continuous one bits (i.e., 111110 becomes 11111).
Other protocols called SLIP (“Serial Line Internet Protocol”) and PPP (“Point-To-Point”) are communications protocols that allow computers to simulate a direct connection to the Internet. SLIP/PPP uses special control characters that need to be detected and/or replaced in the data stream. Creation and insertion as well as detection and replacement of the control characters in prior art SLIP/PPP protocol systems is typically done with a dedicated hardware circuit processing each packet transmitted and received.
Another process occurring in data communications is called the Cyclic Redundancy Check (“CRC”). CRC is the most common method of error detection for most data communications. A CRC value is computed for a packet, attached to that packet during transmission, and upon receipt of that packet the receiver can verify the correctness of the contents of the packet by re-calculating the CRC value using the packet data and comparing the result to the attached CRC. As with the aforementioned protocols, prior art CRC computation is performed either in dedicated hardware circuitry or in software using the CPU of the device.
SUMMARY OF THE INVENTION
Currently available data communication devices that implement protocols such as compression/decompression, encryption/decryption and so forth suffer a variety of problems. Software implementations lack execution speed due to the large number of processing cycles required when executing protocols on the CPU. A CPU executing a program to compress and encrypt data must process data fast enough to fully utilize available data communications bandwidth. Fast processors are expensive and increase the cost of data communications devices. Software implementations of protocols also require a software engineer to “design” code for the protocol, which can be an error prone task.
For example, current hardware implementations of protocols are very inflexible. If the protocol changes due to evolving standards, a new chip must be created making old devices obsolete. The inflexibility of hardware solutions leads to problems when defacto protocol standards evolve that are inconsistent with a current hardware implementation. Additionally, hardware implementations may restrict future improvements in devices containing the dedicated processors because the hardware inflexibility may no longer interface to the changing functionality of the device.
The present invention overcomes the problems associated with software and hardware protocol implementations in prior art data communications devices. For simplicity herein, a data communications device that performs a protocol is called a network device. The present invention provides a network device including a unique co-processor having a symmetrical architecture and an extended processor instruction set to prov

Affiliated with

Also associated with

Rating

Data processor with trie traversal instruction set extension does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data processor with trie traversal instruction set extension, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data processor with trie traversal instruction set extension will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2536817