TERMINAL AND N-TREE CONSTRUCTING METHOD

• US 20110002333A1
• Filed: 12/26/2008
• Published: 01/06/2011
• Est. Priority Date: 02/08/2008
• Status: Active Grant

• Current Assignee: Panasonic Corporation (Panasonic Holdings Corporation)
• Original Assignee: Panasonic Corporation (Panasonic Holdings Corporation)
• Inventors: Karuppiah, Ettikan Kandasamy, Lim, Boon Ping, Nam, Thoai, Yap, Kok Hoong, Muramoto, Eiichi, Tan, Pek Yew
• Granted Patent: US 8,520,556 B2
• Time in Patent Office: Days
• US Class Current: 370/390
• CPC Class Codes: H04L 12/1836 with heterogeneous network architecture
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• CPC Class Codes: H04L 43/0864 Round trip delays
• 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/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A terminal apparatus is provided that minimizes traffic congestion by reducing end-to-end delay and maximizes the bandwidth available in shared N-tree ALM nodes. In this terminal apparatus, an optimal stream path information table (204) stores N-tree session information for all nodes. A server forwarding table (202) stores bandwidth-fair ALM route information for all nodes in a specific N-tree session. An ALM forwarding table constructor (218) updates M-tree session information stored in an optimal stream path information table (204) using network metrics and heuristic rules stored in a heuristic rule database (206), executes ALM_N-tree algorithm using updated N-tree session information, and thereby generates bandwidth-fair ALM route information.

Claims

1. A terminal apparatus for setting up a packet transmission route between nodes in multipoint-to-multipoint communication, the terminal apparatus comprising:

a metric collector that, using address information which specifies members participating in the multipoint-to-multipoint communication, measures a bandwidth of a link and a round trip time between the members, and stores measurement results in a metric database;

an application layer multicasting table constructor that, using the measurement results, forms a packet transmission path (N-tree) between the members, such that a bandwidth is equal, and stores the packet transmission path in a server forwarding table;

an application layer multicasting forwarding table distributor that converts the packet transmission route set up by the application layer multicasting forwarding table constructor into information that can be represented as a combination of an incoming port number, a destination address and a destination port number, and reports the information to the members.

2. The terminal apparatus according to claim 1, wherein, in the course of formation of the N-trees, the application layer multicasting forwarding table constructor stores N-tree session information related to conditions of trees for all nodes in a connected state.

3. The terminal apparatus according to claim 1, wherein, during an execution of an N-tree algorithm, the application layer multicasting forwarding table constructor:

orders all members in a N-tree session based on a specific heuristic rule stored in a heuristic rule database and prepares an ordered list;

selects members that have not established links to all the other nodes in the N-tree from a member of the highest order in the ordered list and prepares a rule-based ordered list by ordering the selected members;

forms a pair of nodes by selecting a member from the highest order in the rule-based ordered list and a member from the initial list satisfying a specific heuristic rule stored in the heuristic rule database, orders the pair of nodes and prepares a rule pair node ordered list; and

selects members fulfilling an additional rule stored in the heuristic rule database from a pair node of a highest order in the rule pair node ordered list and forms the N-trees.

4. The terminal apparatus according to claim 3, wherein, upon forming the pair nodes, the application layer multicasting forwarding table constructor selects a link having a smallest latency between pair nodes among all links in the N-tree session.

5. The terminal apparatus according to claim 3, wherein the application layer multicasting forwarding table constructor moves links between pair nodes in order to minimize a height of the N trees.

6. The terminal apparatus according to claim 3, wherein the application layer multicasting forwarding table constructor selects a heuristic rule from the heuristic rule database, executes the selected heuristic rule based on the optimal stream path information table, and updates the server forwarding table.

7. The terminal apparatus according to claim 3, wherein the application layer multicasting forwarding table constructor selects individual nodes from the optimal stream path information table and constructs the server forwarding table for all streams passing the selected nodes.

8. The terminal apparatus according to claim 3, wherein the heuristic rules stored in the heuristic rule database comprises the rules:

(a) a node should first use a bandwidth of the node to upload streams of the node rather than carry streams of other nodes, to make possible the N-trees with little latency;

(b) if a selection is to be made between nodes, a node with a greatest number of remaining slots is selected;

(c) if a selection is to be made between links, a link with a greatest remaining slot capacity is selected; and

(d) in rule (c), if there are links having the same number of remaining slots, a link that produces a shortest end-to-end latency in the N-trees is selected.

9. An N-tree construction method comprising the steps of:

(a) ordering application layer multicasting members in an initial list with reference to metric collector information and group membership information for all nodes;

(b) ordering the members of the initial list in an ordered list based on a first heuristic rule, for all nodes in the N-tree;

(c) selecting members from the ordered list fulfilling a link connection status with respect to other nodes in the N-trees based on a second heuristic rule and ordering the members in a rule-based ordered list for each N tree;

(d) selecting, from the members of the rule-based ordered list and the members in the initial list, two members having a logical connection satisfying a third heuristic rule as pair nodes and ordering the pair nodes in the rule-based pair list;

(e) selecting, from node pairs in the rule-based pair list, selecting members satisfying a fourth heuristic rule;

(f) forming an N-tree of a root node selected from the initial list, for all receiving nodes in a group based on a fifth heuristic rule;

(g) assuring connecting all links between nodes of a specific N-tree;

(h) assuring all nodes in the specific N-tree based on nodes of the initial list included in a N-tree configuration; and

(i) assuring all N trees based on the nodes of the initial list included in a plurality of N-tree configurations.

10. The N-tree construction method according to claim 9, further comprising the step of (j) optimizing the N-trees by moving links and reordering links.

11. The N-tree construction method according to claim 9, wherein the step of optimizing the N-trees comprises the steps of:

reordering N-tree links by, when there is a link between two nodes having an unused bandwidth or slot, moving the link to a different node such that a sixth heuristic rule is still valid; and

moving the N-tree links, if there are two or more logical links between two same nodes and a first link has more intermediate nodes than a second link, such that a seventh heuristic rule is satisfied and the former link is replaced with the latter link to have a shorter N-tree.

12. The N-tree construction method according to claim 9, further comprising the step of (k) updating the optimal stream path information table and the server bandwidth-fair forwarding table with constructed N-tree information.