Method and system for dynamically managing data structures to optimize computer network performance

• US 6,732,116 B2
• Filed: 06/21/2001
• Issued: 05/04/2004
• Est. Priority Date: 06/21/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Banerjee, Dwip N., Marquardt, David
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US09/886,194
• Publication Number:
  US 20030009482A1
• Time in Patent Office: 1,048 Days
• Field of Search: 707/102
• US Class Current: 707/800
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method and system for providing and dynamically managing the size of a storage space containing data structures depending on a current network load. The present invention expands the size of a storage space when the amount of data therein is large, thereby reducing the time spent searching for values within the data structure. When the amount of data within the storage space is small, the present invention contracts the size of the storage space to reduce the memory needed to maintain the storage space. In this manner, the present invention dynamically adjusts the size of the storage space in response to changing network loads to ensure that network performance remains optimized.

Claims

1. A method of managing storage space used for storing data items on a storage device of a computer network, comprising:

storing the data items within a storage space having an initial size;

defining a threshold number of data items to be stored in the storage space;

varying the initial size of the storage space when the number of data items is greater than or less than the threshold number of data items; and

maintaining variance of the size of the storage space during varying transfer loads of the data items within the computer network.

2. The method as set forth in claim 1, wherein the size of the storage space is expanded if the number of data items is greater than the threshold number of data items.

3. The method as set forth in claim 1, wherein the size of the storage space is contracted if the number of data items is less than the threshold number of data items.

4. The method as set forth in claim 1, wherein the storage space is divided into a plurality of cells.

5. The method as set forth in claim 4, wherein the threshold number of data items is the maximum number of data items that each of the plurality of cells may contain.

6. The method as set forth in claim 4, wherein the storage space is expanded one cell at a time.

7. The method as set forth in claim 4, wherein if one or more of the plurality of cells contains enough storage space to store data items in a particular cell, the data items are stored in the one or more of the plurality of cells and the particular cell is removed.

8. The method as set forth in claim 7, further comprising:

determining that a linked list of data items in a particular cell is greater than the threshold number of data items; and

adding a new cell to the hash table.

9. The method as set forth in claim 7, further comprising:

determining that a linked list of data items in a particular cell is less than the threshold number of data items; and

deleting the particular cell.

10. The method as set forth in claim 1, wherein the storage space is a hash table having plurality of cells and at least one of the plurality of cells contains a linked list of data items.

11. A computer-readable medium having computer-executable instructions thereon for performing the method as set forth in claim 1.

12. A method for managing a data structure having data items stored therein, comprising:

separating the data structure into a number of cells;

defining a threshold number of data items;

determining whether the number of cells should be changed based on a comparison between the threshold number and a number of data items stored within each cell; and

maintaining the comparison between the threshold number and the number of data items stored within each cell during varying transfer loads of the data items within a computer network.

13. The method as set forth in claim 12, further comprising:

determining that the number of data items in a cell is greater than the threshold number of data items; and

increasing the number of cells.

14. The method as set forth in claim 12, further comprising:

determining that the number of data items in a cell is less than the threshold number of data items; and

decreasing the number of cells.

15. The method as set forth in claim 12, wherein the number of data items within a cell are contained in a linked list.

16. The method as set forth in claim 15, further comprising adding a new cell if the number of data items in the linked list is greater than the threshold number of data items.

17. The method as set forth in claim 15, further comprising deleting an existing cell if the number of data items in the linked list of the existing cell is less than the threshold number of data items.

18. The method as set forth in claim 15, further comprising:

rearranging the data items between linked lists in the number of cells based on the comparison;

determining that the number of data items in a linked list of a first cell is greater than the threshold number of data items; and

adding one of the data items in the linked list of the first cell to another linked list in a second cell such that the number of data items in the linked list of the second cell is not greater than the threshold number of data items.

19. The method as set forth in claim 15, further comprising:

rearranging the data items between linked lists in the number of cells based on the comparison;

determining that the number of data items in a linked list of a first cell is less than the threshold number of data items;

adding the number data items in the linked list of the first cell to another linked list in a second cell; and

deleting the first cell.

20. In a computer system having a processor for processing data items, a memory containing a data structure having a size for storing data items, and a display for displaying processed data items to a user, a data structure management system for managing the data items stored within the data structure, comprising:

a dynamic data structure management module that defines a threshold number of data items to be stored in the data structure and expands the size of the data structure when the number of data items is greater than the threshold number and contracts the size of the data structure when the number of data items is less than the threshold number; and

a maintain module that maintains variance of the size of the data structure during varying transfer loads of the data items within the computer system.