Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-06-21
2004-05-04
Amsbury, Wayne (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06732116
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates in general to computer data structures and more particularly to a method and a system for dynamically managing data structures in a computer network environment to optimize performance.
2. Related Art
Computer networks are widespread and vitally important to many types of enterprises including businesses, universities and government. In general, a computer network is two or more computers (or associated devices) that are connected by communication facilities. A computer network may include a server, which is a computer that provides shared resources to users of the network, and a client, which is a computer that accesses the shared network resources provided by the server using the communication facilities. For example, the Internet (via the World Wide Web (WWW)) is a public wide-area network (WAN) environment that enables remote clients to request and receive data located on a server.
Activity on a computer network is a dynamic process. At any given time, the number of network devices (such as client machines) connected to the network and the amount of data flowing through the network varies. For example, an Internet Web server may have a high network load during evening hours when people are not at work but may have a low network load during the middle of the day. In this situation, a high network load means that a network is handling a large number of client requests while a low network load means that the network is handling only a few client requests.
Even though network activity is dynamic, data structures associated with the network typically are static or fixed. A data structure is a mechanism for organizing and grouping related pieces of data. A fixed data structure is one where the size of the structure does not vary. Several types of data structures are available, such as data files, data arrays, data trees, data tables and hash tables. Some of these data structures may be used in a network to store network connection information. This connection information includes a list of which clients are connected to the network and the client addresses. Whenever the server needs to know the address of a client the server can access this information stored in the data structure.
Ordinarily, a hash table has individual cells with each cell identified by a rows and columns. Ideally, only a single piece of data (such as a single client address) is stored a cell of the hash table. However, because of the finite size of the hash table, two or more pieces of data frequently are located in the same cell. Thus, two or more client addresses may be stored in a single cell of the hash table.
A mechanism called a “linked list” is used whenever two or more pieces of data are contained in a single cell of the hash table. A linked list (or a data chain) is a list of the pieces of data contained in that cell. Whenever an application is searching for a particular piece of data within a cell containing multiple pieces of data, the search starts at the top of the linked list and continues down the list until the desired piece of data is found.
Current data structure management techniques choose the size of the hash table by taking into account the balance between the cost of using a great deal of memory and the time required to search through long linked lists. Specifically, if a small amount of data is anticipated then the size of the hash table should be fixed at a small value to save valuable memory. On the other hand, if a large amount of data is anticipated then the size of the hash table should be fixed at a large value to reduce the amount of time spent searching through long linked lists for a desired piece of data. As a compromise, current data structure management techniques usually fix the hash table size at a reasonably large value to accommodate the largest amount data anticipated.
One problem, however, with fixing the hash table size at a large value is that performance of the network is optimized only when there are large amounts of data in the hash table, i.e., at high network loads. At lower network loads, maintaining this large hash table size wastes memory. At the other extreme, if the hash table size is fixed at a small value then a great deal of time is spent searching through a long linked list for a desired piece of data. Both of these situations are adverse to performance of the network.
Therefore, what is needed is a method and system for dynamically managing data structures so that the size of the data structure varies depending on the amount of data therein. Moreover, what is needed is a method and system for dynamically managing data structures that provides a uniform data distribution across the data structure and reduce the time spend searching linked lists of the data structure. What is also needed is method and system for dynamically maintaining these conditions over varying network loads to deliver optimal network performance over a wide range of network loads.
SUMMARY OF THE INVENTION
To overcome the limitations in the prior art as described above and other limitations that will become apparent upon reading and understanding the present specification, the present invention includes a method and a system for managing a storage space for data in a computer network. A storage area is provided that is used to store the data. The storage space has a size and is divided into cells. The present invention expands the size of a storage area used to store network data during heavy network loads. This may be achieved, for example, by adding a cell to the storage space. Conversely, the storage space is contracted during periods of light network use. This may be achieved, for example, by removing a cell from the storage space. To determine when to contract or expand the storage space, a threshold value is defined that represents the amount of data that can be stored in each cell. If the amount of data stored in a cell is greater than a threshold value, the size of the storage space is increased. On the other hand, if the amount of data stored in a cell is less than a threshold value, the size of the storage space is decreased.
Each cell of the storage space can contain a linked list that link multiple data items. Expanding the size of the storage space reduces the amount of time spent searching a linked list for a desired data items. Contracting the size of the storage space reduces the amount of memory required to store the data. In this manner, the present invention is capable of dynamically adapting the size of the storage space to changing amounts of data and ensures that network performance is constantly optimized.
The method of the present invention includes managing storage space for data in a computer network by providing a base storage space having a base size. An amount of data within the storage space is compared to a threshold value and the size is changed in response to the comparison. Thus, the size is increased when the amount of data is greater than the threshold value and decreased when the amount of data is less than the threshold value. The present invention also includes a dynamic data structure management module that changes and dynamically manages the size of the storage space in accordance with the method of the present invention.
Other aspects and advantages of the present invention as well as a more complete understanding thereof will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention. Moreover, it is intended that the scope of the invention be limited by the claims and not by the preceding summary or the following detailed description.
REFERENCES:
patent: 4636946 (1987-01-01), Hartung et al.
patent: 5287499 (1994-02-01), Nemes
patent: 5542066 (1996-07-01), Mattson et al.
patent: 5592432 (1997-01-01), Vishlitzky et al.
patent: 5751993 (1998-05-01), Ofek et al.
patent: 6067547 (2000-05-01), Douceur
patent: 6067608 (2000-05-01), Perry
patent: 628
Banerjee Dwip N.
Marquardt David
DeFrank Edmond A.
International Business Machines - Corporation
Tyson Thomas E.
LandOfFree
Method and system for dynamically managing data structures... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for dynamically managing data structures..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for dynamically managing data structures... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3261329