Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-10-06
2002-05-14
Shah, Sanjiv (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06389419
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to intercepting and processing packets that are related to a connection. More specifically, finding a connection object containing information related to the connection by looking once in a hash table that contains entries for packets sent in both directions between two parties is described.
BACKGROUND OF THE INVENTION
Various network appliances are used in networks to intercept packets and process packets. These appliances include load balancers, network address translation (NAT) devices, proxies, firewalls, and packet monitors. These devices monitor or modify packets on a network. In many cases, packets belonging to different connections are treated differently. Often, packets corresponding to different flows in the same connection are handled differently.
Instructions for handling packets in different flows are stored by the network appliance for the purpose of determining how to handle incoming packets. These instructions must be accessed quickly so that packet processing is not unduly delayed.
FIG. 1A
is a block diagram illustrating a network that includes a client
102
, a network appliance
104
, and a set of servers
106
. For the purpose of this illustration, network appliance
104
will be described as a NAT device that translates the destination address of certain packets sent from the client to a global IP address assigned to the group of servers. Network appliance
104
translates the global IP address used by the client to the local IP address of one of the servers selected to handle the connection with the client. The client IP address and port are referred to as the foreign IP address and port.
The network appliance modifies certain packets or records certain packets that belong to certain connections. A connection is made up of two flows, one in each direction between two parties. In general, a source address and port number, a destination address and port number, and a protocol define a flow. The source and destination addresses and ports are reversed for flows in opposite directions. For the purpose of illustration, this specification describes an example using only addresses as flow identifiers. It should be noted, whenever only an address is mentioned as an identifier, that an address and port may also be used and that a protocol may be added in some embodiments as well.
In the example shown in
FIG. 1A
, each connection is defined by a client IP address and port, a local IP address and port corresponding to the server selected to handle the connection, and a global IP address and port that corresponds to the IP address and port specified by the client for the connection. Packets passing through the network appliance are handled differently depending on whether they are a part of the flow from the client to the server or the flow from the server to the client. Therefore, network appliance
104
must, for each packet received, find a connection object that corresponds to the connection to which the packet belongs and also determine whether the packet is an incoming or an outgoing packet. For the purpose of this description, the terms incoming and outgoing are defined with reference to the server.
FIG. 1B
is a block diagram illustrating the components of a typical network appliance. A processor
110
is connected to a memory
112
and several inbound/outbound interfaces that allow the network appliance to send and receive packets.
FIG. 1B
shows an inbound interface
114
and an outbound interface
116
. Each of the interfaces are intended to represent a large number of interfaces. In some embodiments, the inbound/outbound interfaces are distinguished by whether they are on the client side or the server side. The network appliance may be implemented on any suitable general purpose computer architecture, including a machine running UNIX or Microsoft Windows.
FIG. 2A
is a chart illustrating which address is included as the source and destination address for inbound and outbound packets. For an inbound packet, the foreign address is the source address and the global address is the destination address. For an outbound packet, the foreign address is the destination address and the local address is the source address. The foreign address is included in both inbound and outbound packets as either the source address or the destination address. As a result, a connection object that corresponds to a packet can be located by hashing only the foreign address included in the connection object. A match in the hash table that corresponds to the connection object can be located by first searching using the source address of the packet and then searching using the destination address of the packet. If the connection object is found using the source address of the packet, then the packet is an inbound packet that includes the foreign address of the connection as its source address. If the search using the packet destination address locates the connection object, then the packet is an outbound packet and the foreign address of the connection is the destination address of the outbound packet. Thus, two lookups are required at most to locate a hash table entry that corresponds to the correct connection object.
FIG. 2B
is a flowchart illustrating a process for creating a new entry in a hash table for a new connection object. The process starts at
220
. In a step
222
, the foreign IP address of the connection objects is hashed. Next, in a step
224
, the hash is used to index into the hash table. In a step
226
, the pointer from the hash table is copied into the new connection object. Then, in a step
228
, a pointer to the new connection object is written into the hash table. The process ends at
230
.
FIG. 2C
is a flow chart illustrating a process for searching for a connection object when a packet is received. The process starts at
240
. In a step
242
, the packet source IP address is hashed. Then, in a step
244
, the hash list is checked to see if the source IP address hash is included in the list. If the source IP address hash is found, then in step
246
, it is determined that the packet is an inbound packet. In a step
247
, the connection object is retrieved and the process ends at
254
.
If, in step
244
, the source IP address hash is not found, then control is transferred to a step
248
. In step
248
, the packet destination IP address is hashed and the hash list is checked again. If the destination IP address hash is not found, then control is transferred to a step
250
and it is determined that no connection object exists. If the destination IP address hash is found, then control is transferred to a step
252
and it is determined that the packet is an outbound packet. Control is then transferred to step
247
and the connection object is retrieved. Thus, the connection object is retrieved and it is determined whether the packet is an inbound packet or an outbound packet.
FIG. 2D
is a block diagram illustrating a hash table and several connection objects which may be searched using the hash table. Hash table
266
includes a hash
268
. Hash
268
includes a pointer to a connection object
272
. Connection object
272
points to connection object
274
, which points to connection object
276
. The pointer to connection object
272
was entered in the hash table using a process such as is described in FIG.
2
B. The foreign IP address in connection object
272
, as well as connection objects
274
and
276
hashes to hash
268
. Connection object
276
is the last connection object in the hash chain and so it contains a null pointer.
FIG. 2E
is a block diagram illustrating hash table
266
just before connection object
272
is inserted in the hash table. Hash
268
includes a pointer labeled “A” that points to connection object
274
. Connection object
274
includes a pointer labeled “B” that points to connection object
276
. Connection object
272
is inserted by copying pointer A into connection object
272
and then overwriting pointer A in hash table
266
with a pointer to connecti
LeBlanc William M.
Wong Bruce F.
Cisco Technology Inc.
Shah Sanjiv
Van Pelt & Yi LLP
LandOfFree
Storing and retrieving connection information using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Storing and retrieving connection information using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Storing and retrieving connection information using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2878133