Methods and apparatus for content delivery via application level multicast with minimum communication delay
First Claim
Patent Images
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 the nodes, the geometric region comprising a grid comprising a plurality of cells arranged in concentric rings;
creating a tree beginning at the source and including all of the nodes within the geometric region by;
selecting a representative node for each cell containing at least one node and connecting first to the representative nodes;
selecting a second node in the same cell to connect to additional nodes in the cell, for cells containing three or more nodes one of which is the representative node; and
selecting a third node in the cell to connect to the representative nodes in at least two cells in an outer ring of the concentric rings; and
using the created tree as the overlay multicast tree to deliver data from the source comprising a provider of a given service to an identified group of nodes comprising subscribers having access to the given service.
1 Assignment
0 Petitions
Accused Products
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.
14 Citations
20 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 the nodes, the geometric region comprising a grid comprising a plurality of cells arranged in concentric rings; creating a tree beginning at the source and including all of the nodes within the geometric region by; selecting a representative node for each cell containing at least one node and connecting first to the representative nodes; selecting a second node in the same cell to connect to additional nodes in the cell, for cells containing three or more nodes one of which is the representative node; and selecting a third node in the cell to connect to the representative nodes in at least two cells in an outer ring of the concentric rings; and using the created tree as the overlay multicast tree to deliver data from the source comprising a provider of a given service to an identified group of nodes comprising subscribers having access to the given service. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. 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 circular geometric region comprising the mapped nodes; dividing the circular region into a plurality of rings by constructing a sequence of circles of decreasing radius concentric with the source such that each subsequent circle divides 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; creating a tree beginning at the source and including all of the nodes within the circular region; and using the created tree as the overlay multicast tree to deliver data from the source comprising a provider of a given service to an identified group of nodes comprising subscribers having access to the given service. - View Dependent Claims (15, 16, 17)
-
-
18. 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 circular region comprising the mapped nodes; constructing a polar grid comprising a plurality of cells within the circular region by dividing the circular region into a plurality of concentric rings, each ring comprising at least one of the plurality of cells and the plurality of concentric rings comprising a maximum number of rings such that there is at least one node in each cell except for cells disposed in an outermost ring of the plurality of concentric rings; creating a tree beginning at the source and including all of the nodes within the circular region; and using the created tree as the overlay multicast tree to deliver data from the source comprising a provider of a given service to an identified group of nodes comprising subscribers having access to the given service. - View Dependent Claims (19, 20)
-
Specification