Methods and apparatus for content delivery via application level multicast with minimum communication delay

• US 20050201405A1
• Filed: 03/13/2004
• Published: 09/15/2005
• Est. Priority Date: 03/13/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation, ServiceNow Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Liu, Zhen, Zhang, Li, Riabov, Anton
• Granted Patent: US 7,593,353 B2
• Time in Patent Office: Days
• US Class Current: 370/432
• CPC Class Codes: H04L 12/1881 with schedule organisation, e.g. priority, sequence management
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A method for constructing an overlay multicast tree to deliver data from a source to an identified group of nodes is provided in which a plurality of nodes are identified and mapped into multidimensional Euclidean space. A geometric region is constructing having a size that is the minimum size necessary to contain the source and all the nodes. Once constructed, a tree is created beginning at the source and including all of the nodes within the geometric region.

Claims

1. A method for constructing an overlay multicast tree to deliver data from a source to an identified group of nodes, the method comprising:

identifying a plurality of nodes;

mapping the nodes into multidimensional space;

constructing a geometric region comprising a size that is the minimum size necessary to contain the source and all the nodes;

creating a tree beginning at the source and including all of the nodes within the geometric region.

2. The method of claim 1, wherein the step of constructing a geometric region comprises constructing a circular region.

3. The method of claim 1, wherein the step of mapping the nodes into multidimensional space comprises mapping the nodes into multidimensional Euclidean space.

4. The method of claim 1, further comprising creating a grid within the geometric region.

5. The method of claim 4, wherein the step of creating a grid comprises creating a grid comprising a plurality of cells such that all of the cells comprise a substantially equivalent amount of area.

6. The method of claim 5, wherein the step of creating a tree comprises selecting a representative node for each cell containing at least one node and connecting first to the representative nodes.

7. The method of claim 6, wherein the representative node is selected to be the node within each cell that is closest to the source.

9. The method of claim 7, further comprising, for cells containing three or more nodes one of which is the representative node, selecting a second node in the same cell to connect to additional nodes in the cell and selecting a third node in the cell to connect to the representative nodes in at least two cells in an outer ring.

10. The method of claim 6, further comprising connecting additional nodes within each cell.

11. The method of claim 10, wherein the step of connecting to additional points within each cell comprises using a constant factor approximation algorithm.

12. The method of claim 4, wherein the step of constructing a geometric region comprises constructing a circular region and the step of constructing a grid comprises constructing a polar grid comprising a plurality of cells having substantially equal areas.

13. The method of claim 12, wherein the step of constructing a polar grid comprises dividing the circle into a plurality of rings by constructing a sequence of circles of decreasing radius concentric with the source such that each subsequent circle divides substantially in half an area bounded by a next largest circle, and placing a number of the cells into each one of the plurality of rings such that the number of cells per ring doubles with each ring moving radially outward from the source.

14. The method of claim 12, wherein the step of dividing the circle into a plurality of rings comprises dividing the circle into the maximum number of rings such that there is at least one node in each cell except for cells disposed in an outermost ring.

15. The method of claim 1, wherein the step of creating a tree comprises using an out-degree less than two for each node in the tree.

8. The method of clam 7, further comprising, for cells containing two nodes one of which is the representative node, connecting the representative node to a second node in the same cell and using the second node to connect to the representative nodes in at least two cells in an outer ring.

16. A computer readable medium containing a computer executable code that when read by a computer causes the computer to perform a method for constructing an overlay multicast tree to deliver data from a source to an identified group of nodes, the method comprising:

identifying a plurality of nodes;

mapping the nodes into multidimensional space;

constructing a geometric region comprising a size that is the minimum size necessary to contain the source and all the nodes;

creating a tree beginning at the source and including all of the nodes within the geometric region.

17. The computer readable medium of claim 16, wherein the step of constructing a geometric region comprises constructing a circular region.

18. The computer readable medium of claim 16, wherein the step of mapping the nodes into multidimensional space comprises mapping the nodes into multidimensional Euclidean space.

19. The computer readable medium of claim 16, further comprising creating a grid within the geometric region.

20. The computer readable medium of claim 19, wherein the step of creating a grid comprises creating a grid comprising a plurality of cells such that all of the cells comprise a substantially equivalent amount of area.

21. The computer readable medium of claim 20, wherein the step of creating a tree comprises selecting a representative node for each cell containing at least one node and connecting first to the representative nodes.

22. The computer readable medium of claim 21, wherein the representative node is selected to be the node within each cell that is closest to the source.

24. The computer readable medium of claim 22, further comprising, for cells containing three or more nodes one of which is the representative node, selecting a second node in the same cell to connect to additional nodes in the cell and selecting a third node in the cell to connect to the representative nodes in at least two cells in an outer ring.

25. The computer readable medium of claim 21, further comprising connecting additional nodes within each cell.

26. The computer readable medium of claim 25, wherein the step of connecting to additional points within each cell comprises using a constant factor approximation algorithm.

27. The computer readable medium of claim 19, wherein the step of constructing a geometric region comprises constructing a circular region and the step of constructing a grid comprises constructing a polar grid comprising a plurality of cells having substantially equal areas.

28. The computer readable medium of claim 27, wherein the step of constructing a polar grid comprises dividing the circle into a plurality of rings by constructing a sequence of circles of decreasing radius concentric with the source such that each subsequent circle divides substantially in half an area bounded by a next largest circle, and placing a number of the cells into each one of the plurality of rings such that the number of cells per ring doubles with each ring moving radially outward from the source.

29. The computer readable medium of claim 27, wherein the step of dividing the circle into a plurality of rings comprises dividing the circle into the maximum number of rings such that there is at least one node in each cell except for cells disposed in an outermost ring.

30. The computer readable medium of claim 16, wherein the step of creating a tree comprises using an out-degree less than two for each node in the tree.

23. The computer readable medium of clam 22, further comprising, for cells containing two nodes one of which is the representative node, connecting the representative node to a second node in the same cell and using the second node to connect to the representative nodes in at least two cells in an outer ring.

31. An overlay network comprising:

a source having an out-degree of no more than ten; and

a plurality of nodes in communication with the source, each node comprising an out-degree of no more than ten.

32. The network of claim 31, wherein the source and the nodes each have an out-degree of no more than two.

33. The network of claim 31, wherein the source and nodes are mapped into a geometric region in multidimensional space, the geometric region having a minimum size necessary to contain the source and the nodes.

34. The network of claim 33, wherein the multidimensional space is multidimensional Euclidean space.

35. The network of claim 33, wherein the geometric region comprises a circle having a radius equal to a distance between the source and a node located a farthest distance from the source.

36. The network of claim 33, wherein the geometric region comprises a sphere having a radius equal to a distance between the source and a node located a farthest distance from the source.