Method and system for network load balancing with a compound data structure

• US 7,146,354 B1
• Filed: 06/19/2000
• Issued: 12/05/2006
• Est. Priority Date: 06/18/1999
• Status: Expired due to Term

• Current Assignee: F5 Networks, Inc. (F5 Incorporated)
• Original Assignee: F5 Networks, Inc. (F5 Incorporated)
• Inventors: Skene, Bryan D., Tennican, Scott P.
• Primary Examiner(s): LEROUX, ETIENNE PIERRE
• Application Number:
  US09/596,796
• Time in Patent Office: 2,360 Days
• Field of Search: 707/1, 707/3, 707/103.R, 707/5, 707/102, 707/4, 707/2, 707/100, 709/206, 370/393, 382/178, 715/536, 718/104
• US Class Current: 1/1
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 61/25 of the same type
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

The invention provides for employing a complex data structure to optimize the retrieval of data from a data store over a network. The complex data structure includes two separate sub-data structures (Trie and List) that separately reference the same data objects in a data store. The complex data structure employs a functional interface to determine which data structure matches a particular function request for data. A Trie sub-data structure is used to fulfill a single data object request. The List sub-data structure is employed with function requests related to several data objects. Each data object is associated with a parent object that includes a list of every reference to the data object in both the Trie and List sub-data structures. When a data object is subsequently deleted, the parent object list is employed to automatically delete every reference to the deleted data object in both the Trie and List sub-data structures. A collector object is a type of data object that is associated with a member object and which includes a list of other related data/collector objects. When data associated with the collector object is requested, other data associated with the other data/collector objects on the member object list are automatically retrieved. The complex data structure can also use a Hash sub-data structure to retrieve single data objects.

Claims

1. A method for managing network address translation (NAT) connections over a network, comprising:

storing a plurality of NAT connection data in a data store;

for each stored NAT connection datum, assigning each of a plurality of different data structure types to the same stored NAT connection datum, wherein each of the plurality of different data structure types are based on at least one of an IP address or a port number;

receiving a request for a NAT connection datum, wherein the request includes an IP address and port number;

automatically determining one of the plurality of different data structure types best suited to the NAT connection datum; and

employing the determined data structure type to retrieve the requested NAT connection datum.

2. The method of claim 1, further comprising:

identifying a key in the request for the NAT connection datum;

dividing the key into segments; and

employing each segment to search one of the plurality of different data structure types to locate the requested NAT connection datum.

3. A server array controller for managing network connections between a client and a plurality of servers, comprising:

a storage component that stores a plurality of connection data objects in a data store;

a first object retrieval component that is configured to employ a first data structure type to retrieve each of the plurality of connection data objects from the data store;

a second object retrieval component that is configured to employ a second data structure type to retrieve each of the plurality of connection data objects from the data store, wherein the second data structure type is different from the first data structure type;

an interface component that;

receives a first request for a connection data object;

in response to the first request performing actions, including;

determining one of the first object retrieval component or the second object retrieval component for retrieval of the connection data object based on the first request, and

employing the determined object retrieval component to retrieve the connection data object.

4. The server array controller of claim 3, wherein the determination of one of the first object retrieval component or the second object retrieval component in response to the first request is based on a number of connection data objects requested by the first request.

5. The server array controller of claim 3, wherein the determination of one of the first object retrieval component or the second object retrieval component in response to the first request is based on whether the first request includes a key identifying the connection data object.

6. The server array controller of claim 3, wherein the first data structure type is a trie data structure and the second data structure type is a list structure.

7. A server array controller for managing network connections between a client and a plurality of servers, comprising:

first data retrieval means for retrieving each of the plurality of connection data objects by employing a trie data structure type;

second data retrieval means for retrieving each of the plurality of connection data objects by employing a data structure type that is different from the trie data structure type;

storage means for storing a plurality of connection data objects, each of the plurality of connection data objects being accessible by each of the first data retrieval means and the second data retrieval means; and

third data retrieval means for retrieving each of the plurality of connection data objects by selecting one of the first data retrieval means or second data retrieval means based on a request for a connection data object.