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 a grid comprising a plurality of cells;
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; 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.
-
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 a grid comprising a plurality of cells; 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; 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, 8, 9, 10, 11, 12, 13)
-
-
7. The method of clam 6, 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.
-
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 region geometric region; 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 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; 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; constructing a polar grid comprising a plurality of cells by dividing the circular region 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; creating a tree beginning at the source and including all of the nodes within the geometric 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