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

• US 7,853,615 B2
• Filed: 09/03/2004
• Issued: 12/14/2010
• Est. Priority Date: 09/03/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Popescu, George V., Liu, Zhen
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): Uddin; Mohammed R
• Application Number:
  US10/933,800
• Publication Number:
  US 20060053163A1
• Time in Patent Office: 2,293 Days
• Field of Search: 709/227, 709/230, 707/103, 707/791, 707/793, 707/798
• US Class Current: 707/791
• 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 dynamically partitioning a hierarchical space of objects representing a dynamic set of participants in a distributed interactive application for managing state updates of said objects, said method comprising:

partitioning an application space at any point of time into communication cells according to a current state of said application space, the application space comprising an N-dimensional virtual attribute space containing 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, wherein N≧

3, wherein said application space is spanned by coordinates representing said attribute values, wherein said application space is partially replicated in each of a plurality of clients, each of which controls a limited number of static and dynamic objects in the application space;

grouping the plurality of clients into the communication cells;

indexing the communication cells based on the set of attributes of objects sharing a communication interest at that time;

constructing a hierarchical index by sequential insertion of the communication cells; and

disseminating state updates to subsets of clients according to their communication interests, wherein a state update is generated for each modification of the attributes.

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 managing the hierarchical index.

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

5. The method of claim 4, 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 corresponding to each of the M clusters, and

(c) splitting a node into M nodes; and

propagating part (c) down the hierarchical index.

6. The method of claim 4, 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.

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

8. The method of claim 7, wherein dynamically 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.

9. A method of dynamically partitioning an application space into a hierarchical structure for managing state updates of a dynamic set of objects, the application space comprising an N-dimensional virtual attribute space containing said set of objects and its associated states, wherein N≧

3, wherein said application space is spanned by coordinates representing attribute values of said objects, the objects representing participants in a distributed interactive application, the method comprising;

mapping the application space at any point of time into hierarchical hyperrectangular cells of variable sizes according to a current state of said application space; and

exporting the application space into the hierarchical hyperrectangular cells;

wherein said hierarchical structure comprises leaf nodes storing lists of objects whose communication interest are included in the associated partition cell and non-leaf nodes associated with domains of the application space;

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

wherein each of the hierarchical hyperrectangular cells is associated with a domain defined by a numerical attribute and a non-numerical attribute of an object at that time.

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 hyperrectangular cells with corresponding range values,

the list comprising unique cell identifications corresponding with the hyperrectangular 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 computer-readable hardware medium having instructions stored thereon for execution by a computer processor to perform a method of dynamically partitioning a hierarchical space of objects representing a dynamic set of participants in a distributed interactive application for managing state updates of said objects, said method comprising:

partitioning an application space at any point of time into communication cells according to a current state of said application space, the application space comprising an N-dimensional virtual attribute space containing 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, wherein N≧

3, wherein said application space is spanned by coordinates representing said attribute values, wherein said application space is partially replicated in each of a plurality of clients, each of which controls a limited number of static and dynamic objects in the application space;

indexing the communication cells based on the set of attributes of the objects at that time;

constructing a hierarchical index by sequential insertion of the communication cells; and

dynamically modifying the hierarchical index, including 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.

17. A computer-readable hardware medium having instructions stored thereon for execution by a computer processor to perform a method of dynamically partitioning an application space into a hierarchical structure for managing state updates of a dynamic set of objects, the application space comprising an N-dimensional virtual attribute space containing said set of objects and its associated states, wherein N≧

3, wherein said application space is spanned by coordinates representing attribute values of said objects, the objects representing participants in a distributed interactive application, the method comprising;

mapping the application space at any point of time into hierarchical hyperrectangular cells of variable sizes according to a current state of said application space; and

exporting the application space into the hierarchical hyperrectangular cells;

wherein said hierarchical structure comprises leaf nodes storing lists of objects whose communication interest are included in the associated partition cell and non-leaf nodes associated with domains of the application space;

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

wherein each of the hierarchical hyperrectangular cells is associated with a domain defined by a numerical attribute and a non-numerical attribute of an object at that time.