Source: http://www.google.ca/patents/US20040218536
Timestamp: 2017-11-21 15:57:11
Document Index: 78287702

Matched Legal Cases: ['art 11', 'art 12', 'art 13', 'art 11', 'art 12', 'art 13', 'art 13', 'art 21', 'art 22', 'art 23', 'art 24', 'art 21', 'art 22', 'art 23', 'art 24']

Patent US20040218536 - Multicast communication path calculation method and multicast communication ... - Google Patents
A multicast communication path calculation method is disclosed which includes the steps of: obtaining minimum delay paths from a source node to each destination node; selecting, as candidate nodes of a rendezvous point node, nodes on one of the obtained minimum delay paths; for each candidate node, calculating...http://www.google.ca/patents/US20040218536?utm_source=gb-gplus-sharePatent US20040218536 - Multicast communication path calculation method and multicast communication path calculation apparatus
Publication number US20040218536 A1
Application number US 10/731,156
Also published as CN1514603A, CN100442750C, DE60303763D1, DE60303763T2, DE60320104D1, DE60320104T2, EP1429500A1, EP1429500B1, EP1515495A2, EP1515495A3, EP1515495B1, US7652998, US7693074, US20080013465
Publication number 10731156, 731156, US 2004/0218536 A1, US 2004/218536 A1, US 20040218536 A1, US 20040218536A1, US 2004218536 A1, US 2004218536A1, US-A1-20040218536, US-A1-2004218536, US2004/0218536A1, US2004/218536A1, US20040218536 A1, US20040218536A1, US2004218536 A1, US2004218536A1
Inventors Seisho Yasukawa, Koji Sugisono, Masanori Uga
Patent Citations (8), Referenced by (118), Classifications (22), Legal Events (3)
US 20040218536 A1
1. A multicast communication path calculation method for obtaining multicast paths from a given source node to a plurality of destination nodes in a network including a plurality of nodes, the method comprising the steps of:
obtaining minimum delay paths from the source node to each of the destination nodes by using topology information and delay information of the network;
for each of the candidate nodes, calculating minimum delay paths from the candidate node to each of the destination nodes, and obtaining a difference between the maximum value and the minimum value among delays of the calculated minimum delay paths;
3. A multicast communication path setting method, wherein a multicast communication path calculation apparatus calculates multicast paths from a given source node to a plurality of destination nodes in a network including a plurality of nodes, and a multicast communication path setting apparatus establishes the calculated multicast paths on the network, wherein the multicast communication path setting apparatus sends a request to calculate the multicast paths to the multicast communication path calculation apparatus, and the multicast communication path calculation apparatus calculates the multicast paths according to the request by using a method comprising the steps of:
a part for obtaining minimum delay paths from the source node to each of the destination nodes by using topology information and delay information of the network;
a part for selecting, as candidate nodes of a rendezvous point node, nodes on one of the obtained minimum delay paths;
a part for calculating, for each of the candidate nodes, minimum delay paths from the candidate node to each of the destination nodes, and obtaining, for each of the candidate nodes, a difference between the maximum value and the minimum value among delays of the calculated minimum delay paths;
a part for selecting, as the rendezvous point node, the candidate node for which the difference is smallest among the differences for all of the candidate nodes; and
a part for outputting results comprising, as the multicast paths, a minimum delay path from the source node to the rendezvous point node and minimum delay paths from the rendezvous point node to each of the destination nodes.
8. The multicast communication path calculation apparatus as claimed in claim 5, further comprising a part for including the output results in a multicast path setting control message, and sending the multicast path setting control message over the multicast paths indicated by the output results.
10. A computer program for causing a multicast communication path calculation apparatus to calculate multicast paths from a given source node to a plurality of destination nodes in a network including a plurality of nodes, the computer program comprising:
program code means for obtaining minimum delay paths from the source node to each of the destination nodes by using topology information and delay information of the network;
program code means for selecting, as candidate nodes of a rendezvous point node, nodes on one of the obtained minimum delay paths;
program code means for calculating, for each of the candidate nodes, minimum delay paths from the candidate node to each of the destination nodes, and obtaining, for each of the candidate nodes, a difference between the maximum value and the minimum value among delays of the calculated minimum delay paths;
program code means for selecting, as the rendezvous point node, the candidate node for which the difference is smallest among the differences for each of the candidate nodes; and
program code means for outputting results comprising, as the multicast paths, a minimum delay path from the source node to the rendezvous point node and minimum delay paths from the rendezvous point node to each of the destination nodes.
11. The computer program as claimed in claim 10, wherein the minimum delay path on which the candidate nodes exist is one having maximum delay among minimum delay paths from the source node to each of the destination nodes.
12. A computer readable medium storing program code for causing a multicast communication path calculation apparatus to calculate multicast paths from a given source node to a plurality of destination nodes in a network including a plurality of nodes, the computer readable medium comprising:
program code means for selecting, as the rendezvous point node, the candidate node for which the difference is smallest among the differences for all of the candidate nodes; and
13. The computer readable medium as claimed in claim 12, wherein the minimum delay path on which the candidate nodes exist is one having maximum delay among minimum delay paths from the source node to each of the destination nodes.
14. A multicast communication path calculation method for obtaining multicast paths from a given source node to a plurality of destination nodes in a network including a plurality of nodes, the method comprising the steps of:
selecting the destination nodes from the first distance subgraph, obtaining a second distance subgraph in which each edge is a shortest path between two of the destination nodes, and establishing a first minimal spanning tree of the second distance subgraph;
15. A multicast communication path setting method, wherein a multicast communication path calculation apparatus calculates multicast paths from a given source node to a plurality of destination nodes in a network including a plurality of nodes, and a multicast communication path setting apparatus establishes the calculated multicast paths on the network, wherein the multicast communication path setting apparatus sends a request to calculate the multicast paths to the multicast communication path calculation apparatus, and the multicast communication path calculation apparatus calculates the multicast paths according to the request by using a method comprising the steps of:
reading a distance graph including topology and cost of the network;
obtaining the multicast paths by connecting the tree and the source node at the rendezvous point node, and outputting results comprising the multicast paths,
16. The multicast communication path setting method as claimed in claim 15, wherein each of the nodes in the network measures traffic state of the network and sends the measurement results to the multicast communication path calculation apparatus, and
17. A multicast communication path calculation apparatus for obtaining multicast paths from a given source node to a plurality of destination nodes in a network including a plurality of nodes, the apparatus comprising:
18. The multicast communication path calculation apparatus as claimed in claim 17, further comprising:
19. The multicast communication path calculation apparatus as claimed in claim 17, further comprising a part for including the output results in a multicast path setting control message, and sending the multicast path setting control message over the multicast paths indicated by the output results.
20. The multicast communication path calculation apparatus as claimed in claim 17, further comprising:
21. A computer program for causing a multicast communication path calculation apparatus to calculate multicast paths from a given source node to a plurality of destination nodes in a network including a plurality of nodes, the computer program comprising:
program code means for receiving a distance graph including topology and cost of the network;
program code means for establishing a first distance subgraph in which the source node is deleted from the received distance graph;
program code means for selecting the destination nodes from the first distance subgraph, obtaining a second distance subgraph in which each edge is a shortest path between two of the destination nodes, and establishing a first minimal spanning tree of the second distance subgraph;
program code means for establishing a subgraph of the first minimal spanning tree by including intermediate nodes in each of the edges of the first minimal spanning tree, and establishing a second minimal spanning tree of the subgraph;
program code means for deleting unnecessary edges from the second minimal spanning tree so that a tree including the destination nodes is established;
program code means for, assuming that nodes that form the tree are candidate nodes of a rendezvous point node, obtaining, for each of the candidate nodes, a difference between the maximum distance and the minimum distance among distances between the candidate node and each of the destination nodes, and selecting, as the rendezvous point node, the candidate node for which the difference is smallest; and
program code means for obtaining the multicast paths by connecting the tree and the source node at the rendezvous point node, and outputting the multicast paths.
22. A computer readable medium storing program code for causing a multicast communication path calculation apparatus to calculate multicast paths from a given source node to a plurality of destination nodes in a network including a plurality of nodes, the computer readable medium comprising:
program code means for selecting the destination nodes from the first distance subgraph, and obtaining a second distance subgraph in which each edge is a shortest path between two of the destination nodes, and establishing a first minimal spanning tree of the second distance subgraph;
Document 1: G, Rouskas, et.al., “Multicast Routing With End-to-End Delay and Delay Variation Constraints”, IEEE Journal on Selected Areas in Communication, Vol 15, NO. 3, April 1997.
First, each minimum delay path between a source node and each destination node is calculated, and a delay w of a path that has maximum delay among the minimum delay paths is checked. Assuming that
is delay variation acceptable by an application (this parameter means that the difference of the maximum end-to-end delay and the minimum end-to-end delay among the paths from the source node to all the destination nodes has to be kept within
), paths which satisfy di≦w−
are adopted in which di indicates a delay between the source node and the destination node i. As for a path that is not adopted, a path that satisfies the condition is searched for by using an algorithm for searching for a k-th shortest path. Then, the searched path is adopted. Assuming that the number of the destination nodes is m and the number of nodes in the network is n, then the computation time complexity of this method is O(kmn3).
Although to obtain the ideal solution of the Steiner problem is NP hard, a calculation method for heuristically deriving an approximated solution is proposed as KMB communication method (refer to document 3: L. Kou, G. Markowsky, and L. Berman, “A Fast Algorithm for Steiner Tree,” Acta Informatica 15, 1981, pp.141-145.).
[0041]FIG. 1 is a figure for explaining the outline of the first embodiment;
[0042]FIG. 2 is a block diagram of a multicast communication path calculation apparatus according to the first embodiment;
[0043]FIG. 3 shows a configuration example of a path calculation module 121 of the first embodiment;
[0044]FIG. 4 shows a configuration of a multicast communication path setting apparatus according to the first embodiment;
[0045]FIG. 5 is a flowchart showing processes for calculating paths in the multicast communication path calculation apparatus according to the first embodiment;
[0046]FIG. 6 shows an example of a multicast network according to the first embodiment;
[0047]FIG. 7 shows minimum delay paths from a source node to each destination node;
[0048]FIG. 8 shows paths connecting multicast communication path setting apparatus 20, nodes A, C, E, G, I and destination node 3;
[0049]FIG. 9 shows a minimum delay path from the multicast communication path setting apparatus 20 to the node E and minimum delay paths from the node E to each destination node 1-5;
[0050]FIG. 10 shows an outline of the procedure for multicast communication path calculation according to the second embodiment;
[0051]FIG. 11 shows a configuration of a path calculation module of the multicast communication path calculation apparatus according to the second embodiment;
[0052]FIG. 12 is a flowchart of the multicast communication path calculation method according to the second embodiment;
[0053]FIG. 13 shows an example of a network graph to which the procedure of the second embodiment is applied;
[0054]FIG. 14 shows a network graph in which the source node is excluded;
[0055]FIG. 15 shows a shortest path graph among destination nodes;
[0056]FIG. 16 is a minimal spanning tree obtained from the shortest path graph among destination nodes;
[0057]FIG. 17 shows an intermediate result for constructing a minimal spanning tree considering intermediate nodes;
[0058]FIG. 18 shows a subgraph that forms a minimal spanning tree considering intermediate nodes;
[0059]FIG. 19 shows minimal spanning tree of the subgraph;
[0060]FIG. 20 is a minimal tree including destination nodes;
[0061]FIG. 21 shows multicast paths from the source node to each destination node in which a rendezvous point node is provided;
[0062]FIG. 22 shows a configuration example of a multicast communication path calculation system according to the second embodiment;
[0063]FIG. 23 shows a network for evaluating the multicast communication path calculation system according to the second embodiment;
[0064]FIG. 24 shows a performance evaluation graph of multicast communication path cost;
[0065]FIG. 25 shows a performance evaluation graph of transfer delay variation.
[0068]FIG. 1 is a figure for explaining the outline of the first embodiment. A multicast network of the first embodiment includes a plurality of nodes each including a multicast transfer apparatus. A multicast communication path calculation apparatus is provided in a node, and a multicast communication path setting apparatus is provided in a node. The multicast communication path calculation apparatus may be separate from the nodes that form the multicast network. In addition, the multicast communication path calculation apparatus and the multicast communication path setting apparatus may be included in one node.
[0077]FIG. 2 is a block diagram of the multicast communication path calculation apparatus. In FIG. 2, the symbol 10 shows the multicast communication path calculation apparatus. The multicast communication path calculation apparatus 10 includes an information management part 11, a path calculation part 12 and a packet process part 13. The information management part 11 is for managing network measurement information on delay or cost arising in each node and each link between nodes in the network. The path calculation part 12 is for calculating multicast paths. The packet process part 13 is for processing packets to be sent or received. In addition, the packet process part 13 receives the network measurement information and a path calculation request, and sends calculation result to the multicast communication path setting apparatus.
[0080]FIG. 3 shows an example of a configuration of the path calculation module 121 of this embodiment. Functions of each part of the path calculation module 121 can be realized by hardware such as CPU and memory, and software.
[0083]FIG. 4 shows a configuration of the multicast communication path setting apparatus. In this figure, the symbol 20 shows the multicast communication path setting apparatus. The multicast communication path setting apparatus 20 includes an information management part 21, a measurement part 22, a path setting protocol process part 23 and a packet process part 24. The information management part 21 manages information of delay or cost that arises in nodes and links in the network. The measurement part 22 measures delay or cost arises in itself. The path setting protocol process part 23 performs path setting when new data flow arises, for example. The packet process part 24 processes arriving packets.
[0091]FIG. 5 is a flowchart showing processes for calculating multicast paths in the multicast communication path calculation apparatus 10.
[0097]FIG. 6 shows a multicast network. In this figure, symbols 1-5 show destination nodes. A-I indicate nodes existing between the source node and the destination nodes, and each node includes the capability of the multicast transfer apparatus. A multicast network is formed by the multicast communication path setting apparatus 20 (source node), the nodes A-I, and destination nodes 1-5 that are connected by communication lines. Each number shown on each link indicates a delay (cost) of the link.
[0099]FIG. 7 shows minimum delay paths from the source node to each destination node.
[0103]FIG. 8 shows the minimum delay path connecting the source node, nodes A, C, E, G, I and destination node 3. In the following, the minimum delay path is called as a rendezvous point candidate path. In addition, the nodes A, C, E, G and I are called candidate nodes.
[0112]FIG. 10 shows an outline of the procedure of the multicast communication path calculation method according to the second embodiment.
[0118]FIG. 11 shows a configuration of a path calculation module of the multicast communication path calculation apparatus according to the second embodiment of the present invention.
[0134]FIG. 12 is a flowchart of the multicast communication path calculation method according to the second embodiment.
[0144]FIG. 13 shows a network formed by 10 nodes from V0 to V9. Each node is connected by a link, and the number on each link shows a transfer cost. For example, since 1 is assigned to the link between the node V0 and the node V1, the transfer cost for transferring data from the node V0 to the node V1 is 1.
RP·V1=1,
RP·V2=3,
RP·V3=3,
RP·V4=2,
[0158]FIG. 22 shows a configuration example of a multicast communication path calculation system according to the second embodiment. That is, the system can be configured not only as shown in FIG. 1 but also as shown in FIG. 22. The system shown in FIG. 22 performs the above-mentioned multicast calculation procedure.
[0161]FIG. 23 shows a network for evaluating the multicast communication path calculation system. As shown in the figure, by setting a random graph including 400 nodes and bandwidth for each link, a multicast tree including 40 destination nodes are constructed. FIG. 24 shows a performance evaluation graph of multicast paths, and FIG. 25 shows a performance evaluation graph of delay variation. As shown in the evaluation result, although transfer cost increases slightly according to the method of the present invention compared with the KMB communication method, delay variation of the whole tree can be suppressed according to the method of the present invention.
US6088333 * 14 Nov 1997 11 Jul 2000 Electronics And Telecommunications Research Institute Multicast routing method using path overlapping efficiency in VP-based on ATM networks
US6778531 * 29 Sep 2000 17 Aug 2004 Lucent Technologies Inc. Multicast routing with service-level guarantees between ingress egress-points in a packet network
US7403479 * 7 Oct 2004 22 Jul 2008 International Business Machines Corporation Optimization of network adapter utilization in EtherChannel environment
US7558219 * 26 Aug 2005 7 Jul 2009 Juniper Networks, Inc. Multicast trees for virtual private local area network (LAN) service multicast
US7583601 * 6 Feb 2004 1 Sep 2009 Nippon Telegraph And Telephone Corporation Multicast transfer route setting method, and multicast label switching method for implementing former method
US7684420 * 30 Aug 2006 23 Mar 2010 Huawei Technologies Co., Ltd. Method for implementing cross-domain constraint routing
US7876755 17 Sep 2008 25 Jan 2011 Huawei Technologies Co., Ltd. Method and system for improving quality of communication based on label distribution protocol
US7941485 * 20 Nov 2006 10 May 2011 Hitachi, Ltd. Measurement system, management device and processing distribution method using the system
US7995569 * 23 Jan 2006 9 Aug 2011 Nortel Networks Limited Virtual routers for GMPLS networks
US8248952 2 Jun 2008 21 Aug 2012 International Business Machines Corporation Optimization of network adapter utilization in EtherChannel environment
US8611254 * 31 Oct 2006 17 Dec 2013 Hewlett-Packard Development Company, L.P. Systems and methods for configuring a network for multicasting
US8774180 * 29 Dec 2011 8 Jul 2014 Cisco Technology, Inc. Transporting multicast over MPLS backbone using virtual interfaces to perform reverse-path forwarding checks
US8855021 * 17 Apr 2009 7 Oct 2014 Canon Kabushiki Kaisha Video delivery apparatus and method
US8934486 16 Mar 2006 13 Jan 2015 Cisco Technology, Inc. System and method for implementing multicast over a label-switched core network
US9191269 * 6 Sep 2012 17 Nov 2015 Verizon Patent And Licensing Inc. Method and system for providing latency detection based on automated latency measurements of communication network paths
US20060077950 * 7 Oct 2004 13 Apr 2006 International Business Machines Corporation Optimization of network adapter utilization in etherchannel environment
US20060146716 * 30 Dec 2004 6 Jul 2006 Lun Desmond S Minimum-cost routing with network coding
US20060221981 * 23 Jan 2006 5 Oct 2006 Nortel Networks Limited Virtual routers for GMPLS networks
US20070182584 * 20 Nov 2006 9 Aug 2007 Hitachi, Ltd. Measurement system, management device and processing distribution method using the same
US20070217415 * 16 Mar 2006 20 Sep 2007 Ijsbrand Wijnands System and method for implementing multicast over a label-switched core network
US20070237097 * 29 Mar 2006 11 Oct 2007 Maharana Rohit K Method and apparatus for generating a degree-constrained minimum spanning tree
US20080101361 * 31 Oct 2006 1 May 2008 Jeremy Brown Systems and methods for configuring a network for multicasting
US20080198751 * 30 Aug 2006 21 Aug 2008 Fenglin Li Method for implementing cross-domain constraint routing
US20090028148 * 17 Sep 2008 29 Jan 2009 Huawei Technologies Co., Ltd. Method And System For Improving Quality Of Communication Based On Label Distribution Protocol
US20090162075 * 26 Aug 2008 25 Jun 2009 Fujitsu Limited Transmission system and transmission method
US20090276822 * 17 Apr 2009 5 Nov 2009 Canon Kabushiki Kaisha Video delivery apparatus and method
US20120163373 * 29 Dec 2011 28 Jun 2012 Alton Lo Transporting multicast over mpls backbone using virtual interfaces to perform reverse-path forwarding checks
US20140068106 * 6 Sep 2012 6 Mar 2014 Verizon Patent And Licensing Inc. Method and system for providing latency detection based on automated latency measurements of communication network paths
US20150128271 * 21 May 2013 7 May 2015 Electronics And Telecommunications Research Institute Apparatus and method for collecting network data traffic
WO2007021269A1 * 15 Aug 2005 22 Feb 2007 Mitsubishi Electric Research Laboratories Method, apparatus and system for multicast communication in a wireless multi-hop network
WO2007117821A2 * 12 Mar 2007 18 Oct 2007 Motorola, Inc. Method and apparatus for generating a degree-constrained minimum spanning tree
WO2007117821A3 * 12 Mar 2007 16 Apr 2009 Motorola Inc Method and apparatus for generating a degree-constrained minimum spanning tree
International Classification H04L12/24, H04L12/751, H04L12/753, H04L12/727, H04L12/721, H04L12/761, H04L12/18
Cooperative Classification H04L41/12, H04L45/48, H04L45/02, H04L45/124, H04L45/121, H04L45/16, H04L12/1877
European Classification H04L45/48, H04L45/02, H04L41/12, H04L45/121, H04L45/16, H04L45/124, H04L12/18R2
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:YASUKAWA, SEISHO;SUGISONO, KOJI;UGA, MASANORI;REEL/FRAME:015310/0938