Storing and retrieving connection information using bidirectional hashing of connection identifiers

• US 6,389,419 B1
• Filed: 10/06/1999
• Issued: 05/14/2002
• Est. Priority Date: 10/06/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Wong, Bruce F., LeBlanc, William M.
• Primary Examiner(s): Shah, Sanjiv
• Application Number:
  US09/413,743
• Time in Patent Office: 951 Days
• Field of Search: 707/7, 707/2, 707/10, 707/104, 709/238, 711/108, 370/469, 370/255, 365/230.01
• US Class Current: 709/245
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 69/12 Protocol engines
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A network appliance is configured to store and retrieve instructions for handling a packet corresponding to a connection. The network appliance includes a connection storing processor configured to hash an incoming flow identifier for incoming packets to obtain an incoming hash; to hash an outgoing flow identifier for outgoing packets to obtain an outgoing hash; to insert an incoming entry corresponding to the incoming hash in a bidirectional hash table; and to insert an outgoing entry corresponding to the outgoing hash in a bidirectional hash table. A connection finding processor is configured to hash a packet identifier to obtain a packet hash; and to determine a matching entry in the bidirectional hash table that corresponds to the packet hash. A memory is configured to store the bidirectional hash table.

Claims

1. A method of storing and retrieving instructions for handling a packet corresponding to a connection comprising:

hashing an incoming flow identifier for incoming packets to obtain an incoming hash;

hashing an outgoing flow identifier for outgoing packets to obtain an outgoing hash;

inserting an incoming entry corresponding to the incoming hash in a bidirectional hash table;

inserting an outgoing entry corresponding to the outgoing hash in the bidirectional hash table;

hashing a packet identifier to obtain a packet hash; and

determining a matching entry in the bidirectional hash table that corresponds to the packet hash.

2. A method as recited in claim 1 wherein the flow identifiers contain IP addresses.

3. A method as recited in claim 1 wherein the flow identifiers contain IP addresses and port numbers.

4. A method as recited in claim 1 wherein the incoming flow identifier includes a foreign address and a global address.

5. A method as recited in claim 1 wherein the incoming flow identifier includes a foreign address, a foreign port, a global address and a global port.

6. A method as recited in claim 1 wherein the incoming flow identifier includes a foreign address, a foreign port, a global address a global port and a protocol.

7. A method as recited in claim 1 wherein the outgoing flow identifier includes a local address and a foreign address.

8. A method as recited in claim 1 wherein the outgoing flow identifier includes a local address, a local port, a foreign address and a foreign port.

9. A method as recited in claim 1 wherein the outgoing flow identifier includes a local address, a local port, a foreign address, a foreign port and a protocol.

10. A method as recited in claim 1 wherein the matching entry points to a memory location that indicates whether the matching entry was inserted as an incoming entry or an outgoing entry.

11. A method as recited in claim 10 wherein the memory location is part of an inbound/outbound object that points to a connection object.

12. A method as recited in claim 11 further including determining a memory offset based on whether the memory location indicates that the matching entry was inserted as an incoming entry or an outgoing entry for the purpose of reading data from the connection object.

13. A method as recited in claim 10 wherein the memory location is part of a connection object.

14. A computer readable medium as recited in claim 1 wherein the flow identifiers contain IP addresses.

15. A computer readable medium as recited in claim 1 wherein the flow identifiers contain IP addresses and port numbers.

16. A computer readable medium as recited in claim 1 wherein the incoming flow identifier includes a foreign address and a global address.

17. A computer readable medium as recited in claim 1 wherein the incoming flow identifier includes a foreign address, a foreign port, a global address and a global port.

18. A computer readable medium as recited in claim 1 wherein the incoming flow identifier includes a foreign address, a foreign port, a global address a global port and a protocol.

19. A computer readable medium as recited in claim 1 wherein the outgoing flow identifier includes a local address and a foreign address.

20. A computer readable medium as recited in claim 1 wherein the outgoing flow identifier includes a local address, a local port, a foreign address and a foreign port.

21. A computer readable medium as recited in claim 1 wherein the outgoing flow identifier includes a local address, a local port, a foreign address a foreign port and a protocol.

22. A computer readable medium as recited in claim 1 wherein the matching entry points to a memory location that indicates whether the matching entry was inserted as an incoming entry or an outgoing entry.

23. A computer readable medium as recited in claim 22 wherein the memory location is part of an inbound/outbound object that points to a connection object.

24. A computer readable medium as recited in claim 22 wherein the memory location is part of a connection object.

25. A computer readable medium as recited in claim 22 further including determining a memory offset based on whether the memory location indicates that the matching entry was inserted as an incoming entry or an outgoing entry for the purpose of reading data from the connection object.

26. A network appliance configured to store and retrieve instructions for handling a packet corresponding to a connection comprising:

a connection storing processor configured to;

hash an incoming flow identifier for incoming packets to obtain an incoming hash;

hash an outgoing flow identifier for outgoing packets to obtain an outgoing hash;

insert an incoming entry corresponding to the incoming hash in a bi-directional hash table; and

insert an outgoing entry corresponding to the outgoing hash in a bi-directional hash table;

a connection finding processor configured to;

hash a packet identifier to obtain a packet hash; and

determine a matching entry in the bi-directional hash table that corresponds to the packet hash; and

a memory configured to store the bi-directional hash table.

27. A network appliance as recited in claim 26 wherein the connection storing processor and the connection finding processor are implemented on the same processor.

28. A network appliance as recited in claim 26 wherein the flow identifiers contain IP addresses.

29. A network appliance as recited in claim 26 wherein the flow identifiers contain IP addresses and port numbers.

30. A network appliance as recited in claim 26 wherein the incoming flow identifier includes a foreign address and a global address.

31. A network appliance as recited in claim 26 wherein the incoming flow identifier includes a foreign address, a foreign port, a global address and a global port.

32. A network appliance as recited in claim 26 wherein the incoming flow identifier includes a foreign address, a foreign port, a global address a global port and a protocol.

33. A network appliance as recited in claim 26 wherein the outgoing flow identifier includes a local address and a foreign address.

34. A network appliance as recited in claim 26 wherein the outgoing flow identifier includes a local address, a local port, a foreign address and a foreign port.

35. A network appliance as recited in claim 26 wherein the outgoing flow identifier includes a local address, a local port, a foreign address a foreign port and a protocol.

36. A network appliance as recited in claim 26 wherein the matching entry points to a memory location that indicates whether the matching entry was inserted as an incoming entry or an outgoing entry.

37. A network appliance as recited in claim 36 wherein the memory location is part of an inbound/outbound object that points to a connection object.

38. A network appliance as recited in claim 36 wherein the memory location is part of a connection object.

39. A network appliance as recited in claim 38 further including determining a memory offset based on whether the memory location indicates that the matching entry was inserted as an incoming entry or an outgoing entry for the purpose of reading data from the connection object.

40. A computer readable medium including program code for storing and retrieving information for handling a packet corresponding to a connection, the program code comprising instructions for.

hashing an incoming flow identifier for incoming packets to obtain an incoming hash;

hashing an outgoing flow identifier for outgoing packets to obtain an outgoing hash;

inserting an incoming entry corresponding to the incoming hash in a bi-directional hash table;

inserting an outgoing entry corresponding to the outgoing hash in a bi-directional hash table;

hashing a packet identifier to obtain a packet hash; and

determining a matching entry in the bidirectional hash table that corresponds to the packet hash.