TECHNIQUE FOR DETERMINING A POINT-TO-MULTIPOINT TREE LINKING A ROOT NODE TO A PLURALITY OF LEAF NODES

• US 20110044352A1
• Filed: 03/03/2009
• Published: 02/24/2011
• Est. Priority Date: 03/04/2008
• Status: Abandoned Application

• Current Assignee: Orange S.A.
• Original Assignee: Orange S.A.
• Inventors: Chaitou, Mohamad, Le Roux, Jean-Louis
• Application Number:
  US12/920,337
• Publication Number:
  US 20110044352A1
• Time in Patent Office: Days
• US Class Current: 370/408
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A method is provided for determining a point-to-multipoint tree connecting a root node to a plurality of leaf nodes (some nodes in different domains) used by a path calculation entity associated with a current domain. The method comprises receiving from at least one other path calculation entity associated with a downstream domain at least one message including a first set of identifiers including at least one identifier of a bunch of branches comprising at least one branch and a respective cost associated with said bunch, the bunch comprising at least one branch enabling connection to leaf nodes in downstream domains, and determining at least one new bunch of branches comprising at least one branch as a function of said at least one first set received, said new bunch of branches having a minimum cost and making it possible also to contact the leaf nodes of the current domain.

Claims

1. A method of determining a point-to-multipoint tree connecting a root node to a plurality of leaf nodes, at least some of the nodes being in different domains, executed by a path calculation entity associated with a domain known as the current domain, said method comprising steps of:

receiving from at least one other path calculation entity associated with a domain downstream of the current domain at least one message comprising a first set of identifiers comprising at least one identifier of a bunch of branches comprising at least one branch and a respective cost associated with said bunch, the bunch comprising at least one branch making it possible to connect to leaf nodes in downstream domains; and

determining at least one new bunch of branches comprising at least one branch as a function of said at least one first set received, said new bunch of branches having a minimum cost and making it possible to connect also to the leaf nodes of the current domain if necessary.

2. The method according to claim 1, wherein the number of new bunches is limited to a predetermined number during the step of determining at least one new bunch.

3. The method according to claim 1, wherein the new bunch is limited to one branch during the step of determining at least one new bunch.

4. The method according to claim 1, wherein the step of receiving at least one message comprising a first set of identifiers comprising at least one identifier of a bunch of branches comprising at least one branch and a respective cost associated with said bunch and of determining at least one new bunch of branches including at least one branch and then the step of sending a message comprising a second set of identifiers of the determined new bunch or bunches and a respective cost associated with said new bunch are executed successively from the downstream end to the upstream end by path calculation entities to a path calculation entity associated with the upstream domain comprising the root node.

5. The method according to claim 1, further comprising a step of sending a request to determine a point-to-multipoint tree to path calculation entities associated with domains downstream of the current domain before the receiving step.

9. A computer program comprising instructions for executing the method according to claim 1, for determining a point-to-multipoint tree connecting a root node to a plurality of leaf nodes, at least some of the nodes being in different domains, when the program is executed by a processor.

6. A path calculation entity associated with a domain, called the current domain, for determining a point-to-multipoint tree connecting a root node to a plurality of leaf nodes, at least some of the nodes being in different domains, said entity comprising means for:

receiving at least one message comprising a first set of identifiers comprising at least one identifier of a bunch of branches comprising at least one branch and a respective cost associated with said bunch from at least one other path calculation entity associated with a domain downstream of the current domain, the bunch of branches comprising at least one branch making it possible to connect to leaf nodes in downstream domains; and

determining at least one new bunch of branches comprising at least one branch as a function of said at least one first set received, said new bunch of branches having a minimum cost and making it possible to connect to the leaf nodes of the current domain, if necessary.

7. A system comprising a plurality of path calculation entities according to claim 6.

8. A node of a communications network comprising a path calculation entity according to claim 6.

10. A signal sent by a path calculation entity associated with a domain, said signal bearing a message comprising a set of identifiers comprising at least one identifier of a bunch of branches comprising at least one branch and a respective cost associated with said bunch, the bunch of branches comprising at least one branch making it possible to connect to leaf nodes in domains downstream of the domain and in said domain, if necessary.