Hierarchical space partitioning for scalable data dissemination in large-scale distributed interactive applications

• US 20060053163A1
• Filed: 09/03/2004
• Published: 03/09/2006
• Est. Priority Date: 09/03/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Liu, Zhen, Popescu, George V.
• Granted Patent: US 7,853,615 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: A63F 2300/534 for network load management, e.g. bandwidth optimization, latency reduction
• CPC Class Codes: H04L 67/131 Protocols for games, networked simulations or virtual reality

Abstract

We present exemplary methods involving hierarchical indexing of an application space, and exemplary techniques for scalable management of shared application state update distribution. The application space is partially replicated at each individual client who controls a limited number of static and dynamic objects of the application space. State updates are generated for each modification of objects'"'"' dynamic attributes. Multiple dynamic objects may change state simultaneously, requiring dissemination of the state updates to non-overlapping groups of clients. A client'"'"'s communication interest is described using multiple dynamic attributes. The communication interest space is represented as an N-dimensional attribute space with coordinates spanning the set of dynamic object attributes contained in the communication interest space. We provide a method for partitioning the application space, creation of communication interest cells and hierarchical indexing of the communication interest space. In addition we provide methods for the creation and dynamic modification of the hierarchical index.

Claims

1. A method of partitioning a hierarchical space, comprising:

partitioning an application space into communication cells, the application space comprising a set of objects and its associated states, and each of the set of objects comprising a set of attributes and a set of methods for modifying the set of attributes;

indexing the communication cells based on the set of attributes; and

constructing a hierarchical index by sequential insertion of the communication cells.

2. The method of claim 1, wherein constructing a hierarchical index by sequential insertion of the communication cells, comprises:

inserting the set of objects sequentially into a set of nodes;

adding a child node into the set of nodes; and

splitting the set of nodes based on a node fanout condition.

3. The method of claim 1, further comprising modifying the hierarchical index.

4. The method of claim 3, wherein modifying the hierarchical index, comprises

locating a cell identification in the communication cells corresponding to an attribute in the set of attributes included in a state update message sent by an object identified by a object identification;

searching for the object identification in a current subscription list of the cell identification;

if the object identification is not found in the step of searching, then

(a) inserting the object identified by the object identification into the current subscription list of the cell identification, and

(b) searching for the object identification in the hierarchical index, and, if the object identification is found in a previous subscription list, removing the object identification from the previous subscription list; and

sending the state update message to all objects identified in the subscription list of the cell identification.

5. The method of claim 1, further comprising managing the hierarchical index.

6. The method of claim 5, wherein managing the hierarchical index comprises periodically traversing the hierarchical index by performing node splitting and node merging.

7. The method of claim 6, wherein performing node splitting, comprises while a split condition is true,

(a) clustering the communication cells into M clusters such that an objective is minimized,

(b) constructing new communication cells (<

attribute range>

, <

activity>

) corresponding to each of the M clusters, and

(c) splitting a node into M nodes; and

propagating part (c) down the hierarchical index.

8. The method of claim 6, wherein performing node merging, comprises:

while a merge condition is true,

(a) finding a first node and a second node with maximum overlap among child nodes of a p_node,

(b) merging the first node and the second node by reinserting the communication cells of the first node into the second node, wherein the first node has a smaller degree than the second node, and

propagating part (b) up the hierarchical index.

9. A method of partitioning an application space into a hierarchical structure, the application space comprising a set of objects and its associated states, the method comprising:

mapping the application space into hierarchical rectangular cells of variable sizes; and

exporting the application space into the hierarchical rectangular cells;

wherein the step of mapping satisfies an application-dependent constraint; and

wherein each of the hierarchical rectangular cells is associated with a domain defined by a numerical attribute and a non-numerical attribute.

10. The method of claim 9, wherein the application-dependent constraint comprises a constraint that the application space be partitioned into equally-spaced grids in a virtual networked simulation.

11. The method of claim 9, wherein the application-dependent constraint comprises a geometrical constraint.

12. The method of claim 9, wherein the numerical attribute comprises a position of at least one object in the set of objects.

13. The method of claim 9, wherein the non-numerical attribute comprises an object type of at least one object in the set of objects.

14. The method of claim 9, further comprising creating a partition file, the partition file comprising a list of the rectangular cells with corresponding range values, the list comprising unique cell identifications corresponding with the rectangular cells, the range values comprising intervals of numerical values of the numerical attributes and the non-numeric attributes associated with the corresponding partition cells.

15. The method of claim 14, wherein the partition file is exported to an XML document.

16. A machine-readable medium having instructions stored thereon for execution by a processor to perform a method of partitioning a hierarchical space, the method comprising:

partitioning an application space into communication cells, the application space comprising a set of objects and its associated states, and each of the set of objects comprising a set of attributes and a set of methods for modifying the set of attributes;

indexing the communication cells based on the set of attributes; and

constructing a hierarchical index by sequential insertion of the communication cells.

17. A machine-readable medium having instructions stored thereon for execution by a processor to perform a method of partitioning an application space into a hierarchical structure, the application space comprising a set of objects and its associated states, the method comprising:

mapping the application space into hierarchical rectangular cells of variable sizes; and

exporting the application space into the hierarchical rectangular cells;

wherein the step of mapping satisfies an application-dependent constraint; and

wherein each of the hierarchical rectangular cells is associated with a domain defined by a numerical attribute and a non-numerical attribute.