Configuring direction-based core based tree (CBT) for CBT-based overlay multicast

• US 20040196795A1
• Filed: 03/16/2004
• Published: 10/07/2004
• Est. Priority Date: 03/28/2003
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Yang, Ki-Seon
• Granted Patent: US 7,450,526 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/488 using root node determination

Abstract

A method of configuring a direction-based Core Based Tree (CBT) for a CBT-based overly multicast includes: requesting and receiving an arbitrary terminal node which intends to subscribe to the CBT of information on a child node pre-subscribed to a core node; calculating a direction between the arbitrary terminal node receiving the child node information from the core node and each of the received child nodes, to transmit information to the core node on the child node of the core node having a minimum resultant value along with a subscription request message; receiving the subscription request message transmitted from the terminal node and the child node information from the core node, and comparing a resultant direction calculation value of the corresponding child node and terminal node with a resultant direction calculation value between the pre-subscribed child nodes and allowing the terminal node to subscribe to a child node or a parent node of the corresponding child node to configure the CBT in response thereto; and, periodically transmitting and receiving a hello packet between the core node and the terminal node, and among the parent, child and brother nodes so that a state of the corresponding node is confirmed and to reconfigure the configured CBT in response to the confirmed state.

Claims

1. A method of configuring a direction-based Core Based Tree (CBT) for a CBT-based overlay multicast, the method comprising:

requesting and receiving information on child nodes pre-subscribed to a core node at an arbitrary terminal node to be subscribed to the CBT;

calculating a direction between the terminal node and each of the child nodes and transmitting information on the child node having a minimum resultant value to the core node along with a subscription request message; and

comparing the calculated direction between a corresponding child node and the terminal node with the calculated direction between child nodes pre-subscribed to the core node at the core node and subscribing the terminal node to either the child node or a parent node of the corresponding child node in accordance with the comparison to configure the CBT.

2. The method according to claim 1, further comprising periodically transmitting and receiving a hello packet at the core node and the terminal node to and from the parent node, the child node and a brother node to confirm a state of the corresponding node and reconfiguring the configured CBT in response to the confirmed state of the corresponding node.

3. The method according to claim 1, wherein calculating the direction comprises using internal and external angles and a height of a triangle having respective distances between the core node and two arbitrary nodes adjacent to the core as respective sides of the triangle.

4. The method according to claim 3, wherein calculating the direction comprises using the formula:

direction=(α

+β

)*y

wherein the triangle has nodes a1, C0 and a2, C0 being a core node, and al and a2 being arbitrary nodes, C0 and a2 forming a bottom side of the triangle, “

α

”

being an internal angle formed by a side C0a1 and a side C0a2 of the triangle;

“

β

”

being an external angle formed by the side C0a1 and a side a1a2 of the triangle, “

y”

being a height of the triangle, and “

direction”

being the calculated direction.

5. The method according to claim 1, wherein calculating the direction further comprises determining that the child node having a minimum resultant value and the terminal node have a same forwarding direction of packets from the core node, the terminal node being determined to be either a child node or a parent node of the corresponding child node

6. The method according to claim 1, wherein:

when the resultant value of calculating the direction between the corresponding child node and the terminal node is smaller than the resultant value of calculating the direction between the pre-subscribed child nodes at the core node, the terminal node is subscribed to the child node of the core node and a message is transmitted to the pre-subscribed child node to re-subscribe to the child node of the terminal node; and

the pre-subscribed child node withdraws from the core node and subscribes to the child node of the terminal node in response to the message.

7. A program storage device, readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method of configuring a direction-based Core Based Tree (CBT) for a CBT-based overlay multicast, the method comprising:

requesting and receiving information on child nodes pre-subscribed to a core node at an arbitrary terminal node to be subscribed to the CBT;

calculating a direction between the terminal node and each of the child nodes and transmitting information on the child node having a minimum resultant value to the core node along with a subscription request message; and

comparing the calculated direction between a corresponding child node and the terminal node with the calculated direction between child nodes pre-subscribed to the core node at the core node and subscribing the terminal node to either the child node or a parent node of the corresponding child node in accordance with the comparison to configure the CBT.

8. The program storage device according to claim 7, the method further comprising periodically transmitting and receiving a hello packet at the core node and the terminal node to and from the parent node, the child node and a brother node to confirm a state of the corresponding node and reconfiguring the configured CBT in response to the confirmed state of the corresponding node.

9. The program storage device according to claim 7, wherein calculating the direction comprises using internal and external angles and a height of a triangle having respective distances between the core node and two arbitrary nodes adjacent to the core as respective sides of the triangle.

10. The program storage device according to claim 9, wherein calculating the direction comprises using the formula:

direction=(α

+β

)*y

wherein the triangle has nodes a1, C0 and a2, C0 being a core node, and al and a2 being arbitrary nodes, C0 and a2 forming a bottom side of the triangle, “

α

”

being an internal angle formed by a side C0a1 and a side C0a2 of the triangle;

“

β

”

being an external angle formed by the side C0a1 and a side a1a2 of the triangle, “

y”

being a height of the triangle, and “

direction”

being the calculated direction.

11. The program storage device according to claim 7, wherein calculating the direction further comprises determining that the child node having a minimum resultant value and the terminal node have a same forwarding direction of packets from the core node, the terminal node being determined to be either a child node or a parent node of the corresponding child node.

12. The program storage device according to claim 7, wherein:

when the resultant value of calculating the direction between the corresponding child node and the terminal node is smaller than the resultant value of calculating the direction between the pre-subscribed child nodes at the core node, the terminal node is subscribed to the child node of the core node and a message is transmitted to the pre-subscribed child node to re-subscribe to the child node of the terminal node; and

the pre-subscribed child node withdraw from the core node and subscribes to the child node of the terminal node in response to the message.