Data pattern analysis using optimized deterministic finite automaton

Techniques for data pattern analysis using deterministic finite automaton are described herein. In one embodiment, a number of transitions from a current node to one or more subsequent nodes representing one or more sequences of data patterns is determined, where each of the current node and subsequent nodes is associated with a deterministic finite automaton (DFA) state. A data structure is dynamically allocated for each of the subsequent nodes for storing information associated with each of the subsequent nodes, where data structures for the subsequent nodes are allocated in an array maintained by a data structure corresponding to the current node if the number of transitions is greater than a predetermined threshold. Other methods and apparatuses are also described.

FIELD OF THE INVENTION

The present invention relates generally to data pattern analysis. More particularly, this invention relates to data pattern analysis using deterministic finite automaton.

BACKGROUND

Deterministic finite automaton (DFA) or deterministic finite state machine is a set of states tied together by a set of transitions, where transitions specify movement from one state to another based on some input. Thus, a deterministic finite automaton at a given state and for a given input has only one transition to a next state. Examples of such deterministic finite automaton may be designed in hardware or software to produce results based on the state and any input. Some applications for deterministic finite automaton are used in electronic systems, such as network equipment and computer operated systems, to control and run processes.

To increase the speed at which a deterministic finite automaton operates on an electronic system current systems load an array into memory for each state of the deterministic finite automaton. Each array contains information on the current state and defines what the next state will be given a certain input. As the number of states and transitions between states of a deterministic finite automaton increases the size of the array also increases. This creates the need for large amounts of memory necessary to store the information needed to execute a deterministic finite automaton. As the memory demands increase so does the cost of implementing a deterministic finite automaton.

SUMMARY OF THE DESCRIPTION

Techniques for data pattern analysis using deterministic finite automaton are described herein. In one embodiment, a number of transitions from a current node to one or more subsequent nodes representing one or more sequences of data patterns is determined, where each of the current node and subsequent nodes is associated with a deterministic finite automaton (DFA) state. A data structure is dynamically allocated for each of the subsequent nodes for storing information associated with each of the subsequent nodes, where data structures for the subsequent nodes are allocated in an array maintained by a data structure corresponding to the current node if the number of transitions is greater than a predetermined threshold.

DETAILED DESCRIPTION

Recently, DFA states have been widely used in identifying certain data patterns of data traffics such as, for example, antivirus, anti-spyware and/or content filtering processes in a network environment. Each DFA state is associated with a data structure to store certain information regarding to a respective DFA state such as target or matched data, link references to other data structures of other DFA states. The data structures of DFA states that represent certain data pattern may be referenced one another. A first data structure may reference a second data structure either including the whole second data structure (e.g., an array) or alternatively, a link referenced to an address of the second data structure (e.g., a linked-list structure). As described above, if the first data structure contains the entire second data structure, processing logic can access from the first data structure to the second data structure faster, but it requires more memory to retain the second data structure. In a linked-list manner, it takes less memory; however, it accesses slower.

According to certain embodiments of the invention, dependent upon certain data patterns being examined, data structures for the DFA states may be allocated in an array manner, a linked-list manner, or a combination of both, to optimize the memory usage (e.g., a hybrid approach). For example, given the fact that some states do not necessarily have all 256 transitions (e.g., standard 256 ACSII codes representing 256 characters) associated with them and some do, for certain states with more than or equal to a certain threshold, most or all transitions are allocated as pointers in a dynamic array. For states which have transitions fewer than certain threshold, the transitions may be allocated in a linked-list manner in which each state requires only two pointers, one referencing to its parent and the other one referencing to its child. Alternatively, for a given state of a sequence of state representing a data sequence, based on a relationship between the given state and its top parent state (e.g., root state), a data structure for the given state may be allocated in a data array or in a linked-list manner. For example, if a given node is within a predetermined distance from its root node, the data structure corresponding to the given node may be allocated in an array; otherwise, the data structure may be allocated in a linked-list manner. The distance threshold may be user configurable and/or specified in the data structure of the root node. Other configurations may exist.

FIG. 1is a block diagram illustrating an example of a network configuration according to one embodiment. Referring toFIG. 1, in one embodiment, the network configuration100includes a network access device104providing network access services for one or more network nodes106-107over a first network105which may be a local area network (LAN). In order to access remote nodes101-102(e.g., Web servers or peer nodes) over a second network103(e.g., an external network), each of the nodes106-107has to go through the network access device104and optionally, a network service provider (e.g., an Internet service provider or ISP) in order to access remote nodes101-102.

In one embodiment, the connection between the network access device104and the network103may be a wired connection. Alternatively, such a connection may be a wireless connection; for example, a satellite or an IEEE 802.1x compatible connection. The network103may be a wide area network (WAN), such as, for example, the Internet. The network105may be a home network using an IEEE 802.1x compatible protocol. Alternatively, the network105may be a local network within an organization (e.g., an Intranet). The network105may be a wired or wireless network, or a combination of both, using a variety of network protocols, such as, Ethernet and/or IEEE 802.1x compatible protocols, such as, for example, Wi-Fi and/or Bluetooth protocols. Wireless connections may include both RF and non-RF links, for example, an IR link. Wired connections may include both electrical and non-electrical links, for example, fiber optic links.

According to one embodiment, network access device104(e.g., gateway device) includes packet inspection logic108which may be implemented as part of an antivirus/spyware and/or content filtering function of the network access device104. Packet inspection logic108may inspect incoming and/or outgoing data packets to detect certain data patterns which may be used to identify certain offensive data such as viruses or certain offensive content. The packet inspection logic108may use multiple DFA states to identify the data patterns, where each DFA is associated with a data structure (e.g., DFA data structures109) to store certain state information of the respective DFA state. According to one embodiment, the DFA data structures109may be allocated dependent upon the specific transitions from one DFA state to another DFA state of a data pattern. The data structures of the child nodes may be allocated in a dynamic array fashion, a linked-list manner, or a combination of both. For example, for certain states with more than or equal to a certain threshold, most or all transitions are allocated as pointers in a dynamic array. For states which have transitions fewer than certain threshold, the transitions may be allocated in a linked-list manner in which each state requires only two pointers, one referencing to its parent and the other one referencing to its child. Furthermore, a data structure for a given node may be allocated in an array or in a linked-list manner dependent upon its relationship (e.g., distance from the root node) with respect to its top parent node or root node. As a result, memory usage for the DFA data structures may be optimized without compromising the performance of content scanning.

FIG. 2Ais a state diagram illustrating an exemplary DFA according to one embodiment of the invention. In this example, an IPS (intrusion detection/prevention system) is programmed to detect and to prevent a pattern of “0111” to pass through. The DFA200shown inFIG. 2Acorresponds to this pattern. Processing logic may use the DFA200to perform pattern matching on a number of packets to determine whether the packets contain the pattern “0111”. Furthermore, to simplify the illustration, it is assumed in this example that each packet contains only one digit. However, it should be appreciated that the concept is applicable to scenarios where a packet contains more than one digit and/or alphabetic letters.

Referring toFIG. 2A, the DFA200includes 5 states211-219. The states211-219in the DFA200may be referred to as nodes. Pattern matching begins at the initial state211. If a packet received contains a “1”, processing logic remains in the initial state211. If the packet contains a “0”, which corresponds to the first digit in the predetermined pattern, processing logic transitions to the A state213. If processing logic receives a “0” subsequently, processing logic remains in the A state213. If processing logic receives a “1”, which corresponds to the second digit in the predetermined pattern, then processing logic transitions into the B state215. From the B state215, processing logic may transition back to the A state213if the next packet received contains a “0”. If the next packet received contains a “1”, which corresponds to the third digit in the predetermined pattern, then processing logic transitions to the C state217.

From the C state217, processing logic may transition back to the A state213if the next packet received contains a “0”. If the next packet received contains a “1”, which corresponds to the last digit in the predetermined pattern, then processing logic transitions to the final state219. When processing logic reaches the final state219, processing logic knows that the packets received so far contains the predetermined pattern. Hence, processing logic may perform the appropriate operations in response to receiving the predetermined pattern, such as block the packet of the predetermined pattern last received and issuing an alarm to alert system administrators. To keep track of which state of the DFA processing logic is in, processing logic may use a logical pointer to point to the current state of the DFA. For example, a logical pointer221inFIG. 2Apoints at state B215to indicate that state B215is the current state of the pattern matching.

One advantage of using the DFA to perform pattern matching on packets is to eliminate the need to reassemble the packets because processing logic can walk through the DFA as each packet is received and examined. If processing logic reaches a final state, there is a match between the pattern contained in the packets received so far and the predetermined pattern. As mentioned above, a pattern is typically broken up into a number of segments and each segment is transmitted using a packet. Using the DFA, processing logic may not have to reassemble the packets in order to find out what the pattern contained in the packets is in order to match the pattern against a predetermined pattern. Processing logic may perform pattern matching on a packet-by-packet basis as each of the packets is received without reassembling the packets. Therefore, processing logic does not have to store the packets for reassembling the packets. Instead, processing logic may simply store a pointer to keep track of the current state in the DFA.

The concept described above may be expanded to signature detection. A signature is a collection of multiple patterns. To keep track of which pattern within a signature is being matched, processing logic may use a tree structure, where each node within the tree structure corresponds to a pattern and each pattern is represented using a DFA. Alternatively, a single DFA may represent multiple patterns, an example of which is discussed below with reference toFIG. 2B. Processing logic may use a pointer to point at the node corresponding to the pattern that is currently being matched.

In some embodiments, multiple patterns in a signature are matched sequentially. That is, once a first pattern is matched, processing logic goes on to try to match a second pattern. However, processing logic may continue looking for the first pattern in the incoming data packets because the first pattern may repeat before the second pattern arrives. In some embodiments, processing logic has to take into consideration of additional rules besides matching individual patterns of a signature. For example, a first pattern may have to be at least x bytes away from the second pattern, where x is a predetermined number. Alternatively, two patterns of the signature may have to be separated from each other by y bytes or less, where y is a predetermined number.

FIG. 2Bis a state diagram illustrating an exemplary DFA according to an alternative embodiment of the invention. In this example, an IPS is programmed to detect a pattern of “CAT” and a pattern of “CACHE.” Both patterns may be part of a signature. To simplify the illustration, it is assumed in this example that each packet contains only one alphabetic letter. However, it should be appreciated that the concept is applicable to scenarios where a packet contains one or more alphabetic letters and/or one or more numeric digits.

The DFA250includes six states251-257. Pattern matching begins at the initial state251. If a packet received contains a “C,” which is the first letter of both “CAT” and “CACHE,” processing logic transitions to the state252. If the packet received contains any other alphabet, processing logic remains in the initial state251. From state252, if processing logic receives a “C,” then processing logic remains in state252. If processing logic receives an “A,” then processing logic transitions to state253. If processing logic receives any alphabet other than “A” or “C,” processing logic returns to the initial state251.

From state253, if processing logic receives a “C,” then processing logic transitions to state254because “C” is the third letter in the pattern “CACHE.” If processing logic receives a “T,” then processing logic transitions to the final state257because the pattern “CAT” is matched. If processing logic receives any alphabet other than “T” or “C,” processing logic returns to the initial state251. From state254, if processing logic receives a “C,” then processing logic transitions back to state253. If processing logic receives an “H,” then processing logic transitions to state255. If processing logic receives any alphabet other than “H” or “C,” processing logic returns to the initial state251.

From state255, if processing logic receives a “C,” then processing logic transitions back to state252. If processing logic receives an “E,” then processing logic transitions to the final state256because the pattern matches “CACHE.” If processing logic receives any alphabet other than “E” or “C,” processing logic returns to the initial state251. As discussed above, when processing logic reaches a final state (e.g., state256and state257), processing logic knows that the packets received so far contains at least one of the predetermined patterns. Hence, processing logic may perform the appropriate operations in response to receiving the predetermined pattern, such as blocking the packet of the predetermined pattern last received and issuing an alarm to alert system administrators. Furthermore, to keep track of which state of the DFA250processing logic is in, processing logic may use a logical pointer to point to the current state of the DFA250. Further detailed information concerning the above packet scanning techniques can be found in a co-pending U.S. patent application Ser. No. 11/112,252, entitled “Method and Apparatus for Identifying Data Patterns in a File,” filed Apr. 21, 2005, which has been assigned to a common assignee of this application, and which is incorporated by reference herein in its entirety.

As described above, each DFA state is associated with a data structure for storing state information for the respective DFA state. Each data structure is dynamically allocated from a parent state dependent upon a specific data pattern at the point in time. For example, referring toFIG. 2B, at node or state253, a next state could be state254or state257dependent upon a specific data pattern. As a result, a DFA data structure associated with a child node of node253may be in a dynamic array manner or in a linked list manner based on certain rules, which may be configured by a network administrator or predetermined policies.

FIG. 3is a state diagram illustrating an example of DFA states which may represent a data pattern. Referring toFIG. 3, in this example, a parent node301has two child nodes302-303, each corresponding to a transition from node301. Node302includes child nodes304-306, each corresponding to a transition from node302, while node302itself is a child node to node301. Node303includes only one child node307forming a single node chain having nodes308and309.

According to one embodiment, for a given node, if a number of transitions from this given node to child nodes of this given node is greater than or equal to a predetermined threshold, the data structures for the child nodes are allocated in an array do that the data structures of the child nodes can be directly accessed from the data structure of the given node (e.g., parent node). In this configuration, if number of the transitions is relatively large, that means the child nodes or DFA states are frequently accessed from the parent node (e.g., commonly used data patterns). As a result, it is desirable that the data structures for all child nodes are maintained and directly accessed from the parent node for the purposes of performance, even though this configuration requires more memory (e.g., contiguous or continuous) for the data structures.

Referring back toFIG. 3, given node302, it is assumed that the number of transitions from node302to nodes304-306is greater than or equal to a predetermined threshold (e.g., 3 in this example). Thus, from the data structure associated with node302, data structures for nodes304-306are allocated in an array (e.g., a continued block of memory) which can be directly and quickly accessed from node302, as shown inFIG. 4A. In this situation, the benefit of higher performance outweighs the detriment of requiring a larger memory block. If, however, the number of transitions is less than a certain threshold, the data structures of the child nodes may be allocated in a linked-list configuration as shown in FIG.4B, where each data structure includes a first reference pointer linked with a data structure of its immediate parent node and a second reference pointer linked with a data structure of one its immediate child node in a chain fashion. In a linked-list configuration a parent node has to walk through one child node at a time in order to access to all of its child nodes. In this way, a smaller continued or contiguous block of memory is needed; however, it may take a longer time to access all the child nodes. Since there are fewer child nodes, memory usage may be reduced and the performance drawback may be minimized.

According to another embodiment, for a given node, if there is only one immediate child node (e.g., the whole data sequence is a single child chain where a node has only zero or one child node), a data structure of the top parent node of the chain may include most or all necessary information for the child nodes in the chain, optionally in a compressed manner, to further reduce memory usage without significantly compromising the performance. In this example as shown inFIG. 3, data structures for states or nodes303, and307-309may be allocated in a compressed form within the data structure corresponding their root parent node301. Examples of pseudo code in C/C++ representing the data structures are shown inFIGS. 6A-6B.

Furthermore, according to further embodiment, for a given state of a sequence of state representing a data sequence, based on a relationship between the given state and its top parent state (e.g., root state), a data structure for the given state may be allocated in a data array or in a linked-list manner. For example, if a given node is within a predetermined distance from its root node, the data structure corresponding to the given node may be allocated in an array; otherwise, the data structure may be allocated in a linked-list manner. The distance threshold may be user configurable and/or specified in the data structure of the root node.

Referring back toFIG. 3, for example, it is assumed that a data structure for any node within a three node distance from its root parent node will be allocated in an array; otherwise the data structure will be allocated in a linked-list manner. Thus, in this example as shown inFIG. 3, data structures for nodes303and307-308may be allocated in an array within the data structure for the root node301, while the data structure for node309may be allocated in a separate data structure accessible from the data structure corresponding to node308via a linked-list manner. Note that the configurations of data structures described above may be allocated in a mixed or combined manner. Thus, data structures for a particular sequence may be allocated in an array in part and in a linked-list manner in part.

FIG. 5Ais a flow diagram illustrating a process for data pattern analysis according to one embodiment of the invention. Note that process500may be performed by processing logic which may include hardware, software, or a combination of both. For example, process500may be performed by a network access device such as network access device104ofFIG. 1. Referring toFIG. 5A, at block501, for given a current node of multiple nodes representing one or more data patterns, where each node corresponding to a DFA state, processing logic determines a number of transitions from the current node to one or more immediate child nodes. If the number of transitions is greater than or equal to a predetermined threshold or alternatively, if a child node is within a predetermined distance from the root node, at block502, data structures for the child nodes are allocated in an array (e.g., continuous block of memory) that are directly accessible from the current node. In this way, the data structures of the child nodes can be quickly accessed, but it requires more memory at block504. Otherwise, at block503, each data structure corresponding to an immediate child node is allocated in a linked-list manner, where the current node has to “walk” through intermediate nodes in order to reach a node down at the bottom of the linked-list. In this way, it requires less memory, but the performance (e.g., speed) to access these data structures would be reduced at block504. Other operations may also be performed.

FIG. 5Bis a flow diagram illustrating a process for data pattern analysis according to an alternative embodiment of the invention. Note that process550may be performed by processing logic which may include hardware, software, or a combination of both. For example, process550may be performed by a network access device such as network access device104ofFIG. 1. Referring toFIG. 5B, at block551, for given a current node of multiple nodes representing one or more data patterns, where each node corresponding to a DFA state, processing logic determines whether the child nodes are in a single node chain (e.g., each node in the chain only has one immediate child node). If so, at block552, a single data structure is allocated for the entire chain. In one embodiment, the single data structure is allocated for the most top parent node of the chain. The data members of the single data structure are used to store all necessary information for each child node in the chain, optionally in a compressed form, which can be directly accessed during data pattern analysis at block554. Otherwise, at block553, the data structures for the child nodes may be allocated dependent upon other factors such as those shown inFIG. 5A. Other operations may also be performed.

FIG. 6Ais pseudo code representing a data structure used in a data pattern analysis according to one embodiment. Referring toFIG. 6A, data structure600may be allocated to a parent node of a sequence of data pattern. As described above, data structure600representing a parent node may need to access a data structure of a child node in a form dependent upon a specific configuration of a data pattern. For example, as described above, if the number of transitions from a parent node exceeds a predetermined threshold, the data structures of all child nodes are allocated in an array as data member601directly accessed by data structure600. In this situation, the benefit of higher performance justifies a larger memory block.

Otherwise, if the number of transitions from a parent node is below a predetermined threshold, the data structures of all child nodes are allocated in a linked-list manner as data member602in which a parent node associated with data structure600has to “walk” through each data structure one at a time. Although it may take longer time to walk through, a smaller memory block is needed. Since the number of transitions is relatively small, the balance of memory usage and performance is achieved.

In a special situation in which the sequence of data pattern is a single node chain, as described above, a single data structure is allocated for all child nodes in a compressed form as data member603(with a data structure example as shown inFIG. 6B). That is, in this situation, only one data structure accessed from the parent node is needed to represent all child nodes. Since each child node can only have up to two transitions, either to an immediate parent node or to an immediate child node, a single data structure is sufficient to cover all necessary information associated with each child node in the chain.

In addition, according to certain embodiments, data structure600includes data member604to store an entry point to a data structure of a right sibling (e.g., a horizontal sibling as shown inFIG. 3). Data member605is used to store an entry point to each transition state (also referred to as a fail state) when a current state fails to match a target data. Data member606is used to store an entry point of a function or routine to which processing logic will call when the current state matches the target data. Data member606may contain additional information about what exactly was matched by the entire sequence, such as, for example, a pattern ID and/or a function pointer to call when the match occurs, etc. Data member607is used to store the number of child nodes with respect to the current node as a parent node. For example, child count607may be used to determine whether certain child nodes should be allocated in an array or in a linked-list manner. Alternatively, the distance of a particular child node with respect to its root node can be used to determine whether the data structure for the node should be allocated in an array or in a linked-list manner. Data member608is used to store an ASCII content of the current node.

Further, data member609is used to indicate whether the data structures of the child nodes are allocated in an array. If so, data member601is valid; otherwise, data member602is valid. Data member610is used to indicate whether the childe nodes are in a single node chain; if so, data member603will take a precedent. Data structure600may further include certain attributes associated with the current node and/or the sequence of data pattern. For example, data member611may be used to indicate whether a particular character should be treated as a case sensitive or insensitive manner. Data member612may be used to indicate that a fail pointer from the current character points to a node with a match state, in which case, processing logic needs to follow a fail pointer and temporarily match something else while the processing logic is walking through the sequence. Note that the format of data structure600is shown for purposes of illustration only. More or fewer data members, as well as other formats, may also be implemented.

FIG. 6Bis pseudo code representing a data structure used in a data pattern analysis according to one embodiment. For example, data structure650may be used in a single node data chain (e.g., accessed from data structure600ofFIG. 6Avia data member603). Data structure650may be allocated as a single data structure to cover all child nodes in the chain, optionally in a compressed form. According to one embodiment, data member651may be used to indicate how many child nodes in the chain. Similar to data member606of data structure600, data member652may include additional information about what exactly was matched by the entire sequence, such as, for example, a pattern ID and/or a function pointer to call when the match occurs, etc. Data member653may be used to represent the ASCII content of the chain, such as, for example, data sequence of “ABCDEFGH”, etc. Data member654may be used to represent certain attributes associated with each character in the chain, such as those similar to attributes stored in data members611-612of data structure600. For example, key[0] may be used to store attributes associated with character ‘A’ of data member653. Similar to data member612of data structure600, data member655may be used to store each of the fail states. Also note that the format of data structure650is shown for purposes of illustration only. More or fewer data members, as well as other formats, may also be utilized.

FIG. 7is a diagram of a network of computer systems, which may be used with an embodiment of the invention. As shown inFIG. 7, a network700includes a number of client computer systems that are coupled together through an Internet722. It will be appreciated that the term “Internet” refers to a network of networks. Such networks may use a variety of protocols for exchange of information, such as TCP/IP, ATM, SNA, SDI. The physical connections of the Internet and the protocols and communication procedures of the Internet are well known to those in the art. It will be also appreciated that such systems may be implemented in an Intranet within an organization.

Access to the Internet722is typically provided by Internet service providers (ISPs), such as the ISP724, and the ISP726. Users on client systems, such as the client computer systems702,704,718, and720, generally obtain access to the Internet through Internet service providers, such as ISPs724and726. Access to the Internet may facilitate transfer of information (e.g., email, text files, media files, etc.) between two or more digital processing systems, such as the client computer systems702,704,718, and720and/or a Web server system728.

For example, one or more of the client computer systems702,704,718, and720and/or the Web server728may provide document presentations (e.g., a Web page) to another one or more of the client computer systems702,704,718, and720and/or Web server728. For example, in one embodiment of the invention, one or more client computer systems702,704,718, and720may request to access a document that may be stored at a remote location, such as the Web server728. In the case of remote storage, the data may be transferred as a file (e.g., download) and then displayed (e.g., in a window of a browser) after transferring the file. In another embodiment, the document presentation may be stored locally at the client computer systems702,704,718, and/or720. In the case of local storage, the client system may retrieve and display the document via an application, such as a word processing application, without requiring a network connection.

The Web server728typically includes at least one computer system to operate with one or more data communication protocols, such as the protocols of the World Wide Web and, as such, is typically coupled to the Internet722. Optionally, the Web server728may be part of an ISP which may provide access to the Internet and/or other network(s) for client computer systems. The client computer systems702,704,718, and720may each, with appropriate Web browsing software, access data, such as HTML document (e.g., Web pages), which may be provided by the Web server728.

The ISP724provides Internet connectivity to the client computer system702via a modem interface706, which may be considered as part of the client computer system702. The client computer systems702,704,718, and720may be a conventional data processing system, such as a desktop computer, a “network” computer, a handheld/portable computer, a cell phone with data processing capabilities, a Web TV system, or other types of digital processing systems (e.g., a personal digital assistant (PDA)).

Similarly, the ISP726provides Internet connectivity for the client computer systems702,704,718, and720. However, as depicted inFIG. 7, such connectivity may vary between various client computer systems, such as the client computer systems702,704,718, and720. For example, as shown inFIG. 7, the client computer system704is coupled to the ISP726through a modem interface708, while the client computer systems718and720are part of a local area network (LAN). The interfaces706and708, shown as modems706and708, respectively, may represent an analog modem, an ISDN modem, a DSL modem, a cable modem, a wireless interface, or other interface for coupling a digital processing system, such as a client computer system, to another digital processing system.

The client computer systems718and720are coupled to a LAN bus712through network interfaces714and716, respectively. The network interface714and716may be an Ethernet-type, asynchronous transfer mode (ATM), or other type of network interface. The LAN bus is also coupled to a gateway digital processing system710, which may provide firewall and other Internet-related services for a LAN. The gateway digital processing system710, in turn, is coupled to the ISP726to provide Internet connectivity to the client computer systems718and720. The gateway digital processing system710may, for example, include a conventional server computer system. Similarly, the Web server728may, for example, include a conventional server computer system.

In one embodiment, the local area network712may be local wireless network (e.g., a home network) and the gateway710may include a wireless access point (also referred to as a base station) to one or more clients718and720using a variety of wireless networking protocols; for example, the IEEE 802.xx protocols including Wi-Fi and/or Bluetooth protocols. In a further embodiment, the gateway710may access the server728via dialup network services using a modem.

FIG. 8is a block diagram of a digital processing system which may be used with one embodiment of the invention. For example, the system500shown inFIG. 8may be used as a client computer system such as clients704-705ofFIG. 7. Alternatively, the exemplary system800may be implemented as a network access device702, etc.

Note, that whileFIG. 8illustrates various components of a computer system, it is not intended to represent any particular architecture or manner of interconnecting the components, as such details are not germane to the present invention. It will also be appreciated that network computers, handheld computers, cell phones, and other data processing systems which have fewer components or perhaps more components may also be used with the present invention. The computer system ofFIG. 8may, for example, be an Apple Macintosh computer or an IBM compatible PC.

As shown inFIG. 8, the computer system800, which is a form of a data processing system, includes a bus802which is coupled to a microprocessor803and a ROM807, a volatile RAM805, and a non-volatile memory806. The microprocessor803, which may be, for example, an Intel processor or a PowerPC processor, is coupled to cache memory804as shown in the example ofFIG. 8. The bus802interconnects these various components together and also interconnects these components803,807,805, and806to a display controller and display device808, as well as to input/output (I/O) devices810, which may be mice, keyboards, modems, network interfaces, printers, and other devices which are well-known in the art.

Typically, the input/output devices810are coupled to the system through input/output controllers809. The volatile RAM805is typically implemented as dynamic RAM (DRAM) which requires power continuously in order to refresh or maintain the data in the memory. The non-volatile memory806is typically a magnetic hard drive, a magnetic optical drive, an optical drive, or a DVD RAM or other type of memory system which maintains data even after power is removed from the system. Typically, the non-volatile memory will also be a random access memory, although this is not required.

WhileFIG. 8shows that the non-volatile memory is a local device coupled directly to the rest of the components in the data processing system, it will be appreciated that the present invention may utilize a non-volatile memory which is remote from the system, such as a network storage device which is coupled to the data processing system through a network interface such as a modem or Ethernet interface. The bus802may include one or more buses connected to each other through various bridges, controllers, and/or adapters, as is well-known in the art. In one embodiment, the I/O controller809includes a USB (Universal Serial Bus) adapter for controlling USB peripherals. Alternatively, I/O controller809may include an IEEE-1394 adapter, also known as FireWire adapter, for controlling FireWire devices. Other components may also be included.