Terminal and N-tree constructing method

• US 8,520,556 B2
• Filed: 12/26/2008
• Issued: 08/27/2013
• 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, Muramoto, Eiichi, Yap, Kok Hoong, Tan, Pek Yew, Nam, Thoai
• Primary Examiner(s): Phillips, Hassan
• Assistant Examiner(s): CATTUNGAL, AJAY P
• Application Number:
  US12/865,134
• Publication Number:
  US 20110002333A1
• Time in Patent Office: 1,705 Days
• Field of Search: 370/229, 370/232, 370/231, 370/260, 370/256, 370/252, 370/254, 370/389, 370/390, 370/498, 370/468
• US Class Current: 370/256
• 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 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 stores N-tree session information for all nodes. A server forwarding table stores bandwidth-fair ALM route information for all nodes in a specific N-tree session. An ALM forwarding table constructor updates N-tree session information stored in an optimal stream path information table using network metrics and heuristic rules stored in a heuristic rule database, 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 a packet transmission path 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 multicast forwarding table constructor that, using the measurement results, forms a packet transmission path (N-tree) between the members, such that bandwidths are equal, and stores the packet transmission path in a server forwarding table;

an application layer multicast forwarding table distributor that converts the packet transmission path formed by the application layer multicast forwarding table constructor into information including a combination of an incoming port number, a destination address and a destination port number, and reports the information to the members,

wherein, during an execution of an N-tree algorithm, the application layer multicast 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 ordered list satisfying the 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 satisfying an additional rule stored in the heuristic rule database from a pair of nodes of a highest order in the rule pair node ordered list, and forms the N-trees.

2. The terminal apparatus according to claim 1, wherein, upon forming the pair of nodes, the application layer multicast forwarding table constructor selects a link having a smallest latency between the pair of nodes, from all links in the N-tree session.

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

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

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

6. The terminal apparatus according to claim 1, 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.

7. An N-tree construction method comprising:

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

ordering the members of the initial list in an ordered list based on a first heuristic rule, for all nodes in N trees;

selecting members from the ordered list satisfying 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;

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 a node pair and ordering node pairs in the rule-based pair list;

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

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;

assuring connection of all links between nodes of a specific N-tree;

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

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

8. The N-tree construction method according to claim 7, further comprising optimizing the N-trees by moving links and reordering links.

9. The N-tree construction method according to claim 8, wherein the optimizing the N-trees comprises:

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.

10. The N-tree construction method according to claim 7, further comprising updating an optimal stream path information table and a server bandwidth-fair forwarding table with constructed N-tree information.