Data processing: measuring – calibrating – or testing – Testing system – Including specific communication means
Reexamination Certificate
2001-08-30
2003-11-25
Hoff, Marc S. (Department: 2857)
Data processing: measuring, calibrating, or testing
Testing system
Including specific communication means
C702S122000, C702S123000, C702S182000, C702S188000, C709S241000, C709S241000, C709S201000, C714S039000, C714S047300, C714S781000, C370S395310, C370S395320
Reexamination Certificate
active
06654701
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of computer technology. More specifically, the invention relates to a method and apparatus for measuring protocol performance in a data communication network.
Portions of the disclosure of this patent document contain material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office file or records, but otherwise reserves all copyrights whatsoever.
BACKGROUND
In order to transmit data from one computer to another the data may be sent across computer networks. So that each computer connected to the network can send and receive data from other computers on the network, each of the interconnected computers is typically configured to understand one or more common protocols. Each protocol defines a format for encapsulating data and transmitting that data across the network. Protocols designed to send data across packet switched networks (e.g., the Internet) typically divide the data that is to be transmitted into sets of packets. Each packet is then sent through the network to the indicated destination. The path that each packet takes may vary, but in every instance the packet data will be sent through network equipment such as a router, switch, hub, and/or any other type of network node.
The performance of the network is dependent upon how quickly the packet data is transmitted through such network equipment. Modern network equipment is designed to move packet data through the network at rates that exceed the connection speed. If, for example, a router is connected to a Gigabit Ethernet network, that router must be capable of moving data at speeds that do not lead to bottlenecking. If a certain device is not able to operate on the packet data at such rates, the network becomes bottlenecked and the overall data transfer rate associated with the entire network can decrease. Therefore, a constant concern network engineers have is whether, or not, the equipment being connected to the network can adequately handle the data speeds of the network. When the routing hardware is efficient, the network itself is efficient.
To address this concern, network engineers and others responsible for ensuring the network remains efficient use devices that can test the speed of the routers and other such pieces of hardware utilized to control packet flow. Such test devices are generally referred to as network test devices. A problem encountered by such test devices is that to effectively measure the performance of protocol data, the test equipment itself must be able to keep up with the transmission speeds of the routing hardware and the data line. In order to assess the behavior of the network for each of the connections, the test equipment must be able to perform a lookup operation to associate each packet with a particular connection. The test equipment must be able to perform this required connection lookup processing for each packet at any given transmission speed. Current performance testing systems have a limited capacity for performing this connection lookup and for processing protocol data when the network speed exceeds one Gigabit per second.
Thus, there is a need for improving the efficiency of connection lookup operations while placing one or more network devices under test.
SUMMARY OF THE INVENTION
An embodiment of the invention provides a mechanism for measuring the performance characteristics of data sent across any communication path configured to carry data between two or more computational devices (e.g., local area networks, wide area network, virtual private networks, wireless networks, or any other type of interconnect mechanism). In a test environment, processing speed is a critical part of producing test equipment that can process network protocol data in real-time. Embodiments of the invention provide network test equipment with a methodology for performing enough lookup processing operations to keep up with the real time frame rates of a gigabit Ethernet network.
This is accomplished in accordance with one embodiment of the invention by improving the performance of the connection lookup processor in test devices. The lookup processor initiates processing when it obtains connection data (e.g., TCP) from a request FIFO. Once the lookup processor receives an incoming datagram containing connection data (e.g., TCP or any other type of datagram to be evaluated), the processor determines a connection index that corresponds to the connection represented by the datagram. Each connection is uniquely identified by the source and destination information associated with the datagram. For instance, each incoming connection may be uniquely identified by examining the source address, destination address, source port, and destination port associated with the connection. Once the connection data is obtained, that data is utilized to perform a lookup operation. During the lookup operation a hashing operation is performed on the connection data and the connection data is associated with an index or hash vector used to find the table of state information for the connection. In accordance with one embodiment of the invention, the lookup operation is performed using an SDRAM memory configured as a chained hash table, using a polynomial hashing algorithm.
Because the lookup processing is performed in a performance measurement system, the hashing algorithm that is selected must be capable of performing enough lookup processing operations to keep up with the frame rates of a Gigabit per second or above Ethernet network. Therefore, the invention contemplates the use of a polynomial hashing algorithm that seeks to distribute the incoming keys as evenly as possible over the range of possible hash function values. The degree of the polynomial used by the hashing algorithm at step
302
is chosen in one embodiment of the invention to give the desired range of hash vectors. Thus, the depth of the linked lists associated with the chained hash table is minimized and the efficiency associated with lookup processing is increased. When the system embodying the invention is configured to handle at least 2 million connections, the chained hash table has an unallocated size capable of storing 2097152 Keys. A suitable hashing polynomial would be 19
th
degree; this produces 524288 distinct hash vectors.
When polynomial hashing is utilized the key to be hashed (e.g., a 96-bit key) is passed through a polynomial division operation. The remainder from the division operation becomes the value of the hash function utilized for the table lookup. The performance of the hashing algorithm is dependent upon the hashing polynomial that is selected. For instance some polynomials perform better than others. The degree of the polynomial that is selected depends upon how many bits are desired in the hash value itself. For a CRC polynomial of order N, the number of unique hash values possible is 2
N
. In one embodiment of the invention, the polynomial order is approximately ¼ the size of the number of lookups desired. For example, for 2 million connections the maximum size of the lookup table is 2,097,152 (2
21
) therefore the polynomial that would maximize efficiency in one embodiment of the invention would be a polynomial of size 2
19
. For a polynomial to be utilized in a hash function, the polynomial should be primitive. For degree 19, there are at least 11 primitive polynomials. In one embodiment of the invention polynomial 7 is viewed as the most effective polynomial. However, other polynomial hashing algorithms can be incorporated into embodiments of the invention and utilized during lookup processing.
REFERENCES:
patent: 4588985 (1986-05-01), Carter et al.
patent: 4853928 (1989-08-01), Williams
patent: 5838919 (1998-11-01), Schwaller et al.
patent: 5881237 (1999-03-01), Schwaller et al.
patent: 5937165 (1999-08-01), Schwaller et al.
patent: 6034958 (2000-03-01), Wicklund
patent: 6061725 (2000-05-01), S
Desta Elias
Hoff Marc S.
Spirent Communications
The Hecker Law Group
LandOfFree
Method and apparatus for measuring protocol performance in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for measuring protocol performance in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for measuring protocol performance in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3165679