Method and apparatus for measuring protocol performance in a data communication network

• US 6,654,701 B2
• Filed: 08/30/2001
• Issued: 11/25/2003
• Est. Priority Date: 08/30/2001
• Status: Expired due to Term

• Current Assignee: Spirent Communications PLC (Spirent Communications Incorporated)
• Original Assignee: Spirent Communications PLC (Spirent Communications Incorporated)
• Inventors: Hatley, Tom
• Primary Examiner(s): Hoff, Marc S.
• Assistant Examiner(s): Desta, Elias
• Application Number:
  US09/945,236
• Publication Number:
  US 20030050762A1
• Time in Patent Office: 817 Days
• Field of Search: 702/119, 702/122, 702/123, 702/182-189, 702/FOR.103, 702/104, 702/134, 702/135, 702/139, 702/170, 702/171, 709/102, 709/104, 709/107, 709/201, 709/213, 709/223-226, 709/249, 709/310, 709/312, 709/FOR.100, 709/116, 380/277, 380/278, 380/280, 380/281, 380/44, 380/45, 370/395.32, 370/395.31, 714/39, 714/47, 714/781
• US Class Current: 702/122
• CPC Class Codes: H04L 43/0888 Throughput
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

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.

Claims

1. A testing apparatus for measuring the performance of protocol data in a data communication network comprising:

a testing device comprising a lookup processor;

said lookup processor configured to obtain protocol data from a data communication network;

said protocol data comprising connection data;

said lookup processor performing a polynomial hashing operation using said connection data as a hash key to produce a hash vector;

said lookup processor initiating a search of hash vector values in a hash vector table to determine a location to store said hash key;

wherein said lookup processor is configured to obtain a stored key from a free list and link said hash vector into said stored key when value of said hash vector table is zero; and

wherein said lookup processor is configured to search for said hash vector when said value of said hash vector table is not zero.

2. The testing apparatus of claim 1 wherein said polynomial hashing operation utilizes a polynomial having an order approximately ¼

the size of the number of lookups to be performed by said lookup processor.

3. The testing apparatus of claim 1 wherein said polynomial hashing operation utilizes a polynomial of size 2¹⁹.

4. The testing apparatus of claim 1 wherein said connection data comprises source data and destination data.

5. The testing apparatus of claim 4 wherein said source data comprises a source address and source port.

6. The testing apparatus of claim 4 wherein said destination data comprises a destination address and destination port.

7. The testing apparatus of claim 1 wherein said hash vector is stored in a location associated with a matching hash vector when said search for said hash vector locates a match.

8. The testing apparatus of claim 1 wherein said hash vector table comprises a chained hash table.

9. The testing apparatus of claim 1 wherein said protocol data comprises TCP data.

10. The testing apparatus of claim 1 wherein said data communication network transports data at at least one gigabit per second.

11. A method for measuring the performance of protocol data in a data communication network comprising:

testing the performance of protocol data, said testing comprising;

obtaining protocol data comprising connection data from a data communication network;

performing a polynomial hashing operation on said connection data to produce a hash vector;

searching a hash vector table to determine a location to store said hash vector;

obtaining a stored key from a free list and linking said hash vector into said stored key when said hash vector table is zero; and

searching for said hash vector when said hash vector table is not zero.

12. The method of claim 11 wherein said polynomial hashing operation utilizes a polynomial having an order approximately ¼

the size of the number of lookups to be performed by said lookup processor.

13. The method of claim 11 wherein said polynomial hashing operation utilizes a polynomial of size 2¹⁹.

14. The method of claim 11 wherein said connection data comprises source data and destination data.

15. The method of claim 14 wherein said source data comprises a source address and source port.

16. The method of claim 14 wherein said destination data comprises a destination address and destination port.

17. The method of claim 11 wherein said hash vector is stored in a location associated with a matching hash vector when said search for said hash vector locates a match.

18. The method of claim 11 wherein said hash vector table comprises a chained hash table.

19. The method of claim 11 wherein said protocol data comprises TCP data.

20. The method of claim 11 wherein said data communication network transports data at at least one gigabit.

21. A computer program product comprising:

a computer usable medium having computer readable program code for measuring the performance of protocol data in a data communication network comprising embodied therein said computer readable program code configured to;

obtain protocol data comprising connection data from a data communication network;

execute a polynomial hashing operation on said connection data to produce a hash vector;

search a hash vector table to determine a location to store said hash vector;

obtain a stored key from a free list and link said hash vector into said stored key when said hash vector table is zero; and

search for said hash vector when said hash vector table is not zero.

22. The computer program product of claim 21 wherein said polynomial hashing operation utilizes a polynomial having an order approximately ¼

the size of the number of lookups to be performed by said computer readable program code.

23. The computer program product of claim 21 wherein said polynomial hashing operation utilizes a polynomial of size 2¹⁹.

24. The computer program product of claim 21 wherein said connection data comprises source data and destination data.

25. The computer program product of claim 24 wherein said source data comprises a source address and source port.

26. The computer program product of claim 24 wherein said destination data comprises a destination address and destination port.

27. The computer program product of claim 21 wherein said hash vector is stored in a location associated with a matching hash vector when said search for said hash vector locates a match.

28. The computer program product of claim 21 wherein said hash vector table comprises a chained hash table.

29. The computer program product of claim 21 wherein said protocol data comprises TCP data.

30. The computer program product of claim 21 wherein said data communication network transports data at at least one gigabit.

31. A system for testing the performance of TCP data in a data communication network comprising:

a data communication network configured to transport TCP data having source data and destination data;

a testing device comprising a lookup processor, said lookup processor configured to obtain said TCP data from said data communication network and execute a polynomial hashing operation using said source data and said destination data as a hash key to produce a hash vector;

said lookup processor initiating a search of a hash vector table to determine a location to store said hash vector;

said lookup processor determining if a location associated with said hash vector in said hash vector table is empty; and

said lookup processor obtaining a stored key from a free list and associating said stored key with said location in said hash vector table when said location is empty.

32. The system of claim 31 wherein said lookup processor provides a result to a results FIFO.

33. The system of claim 31 further comprising:

said lookup processor searching said hash vector table for said hash vector.

34. The system of claim 31 wherein said polynomial hashing operation utilizes a polynomial having an order approximately ¼

the size of the number of lookups to be performed by said lookup processor.

35. A method for testing the performance of TCP data in a TCP/IP network comprising:

obtaining TCP data having connection data comprising source data and destination data;

providing said connection data as a hash key to a polynomial hashing operation;

executing said polynomial hashing operation to generate a hash vector;

searching a hash vector table to determine a location to store said hash vector, wherein said searching comprises;

determining if a location associated with said hash vector in said hash vector table is empty; and

obtaining a stored key from a free list and associating said stored key with said location in said hash vector table when said location is empty.

36. The method of claim 35 further comprising:

searching said hash vector table for said hash vector.

37. The method of claim 35 wherein said polynomial hashing operation utilizes a polynomial having an order ¼

the size of the number of lookups to be performed.