Source: http://www.google.com/patents/US7652998?ie=ISO-8859-1&dq=5920316
Timestamp: 2015-04-21 03:06:25
Document Index: 696659529

Matched Legal Cases: ['art 21', 'art 11', 'art 212', 'art 22', 'art 24', 'art 242', 'art 25', 'art 25', 'art 252', 'art 25', 'art 25']

Patent US7652998 - Multicast communication path calculation method and multicast communication ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsA 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.com/patents/US7652998?utm_source=gb-gplus-sharePatent US7652998 - Multicast communication path calculation method and multicast communication path calculation apparatusAdvanced Patent SearchPublication numberUS7652998 B2Publication typeGrantApplication numberUS 10/731,156Publication dateJan 26, 2010Filing dateDec 10, 2003Priority dateDec 11, 2002Fee statusPaidAlso published asCN1514603A, CN100442750C, DE60303763D1, DE60303763T2, DE60320104D1, DE60320104T2, EP1429500A1, EP1429500B1, EP1515495A2, EP1515495A3, EP1515495B1, US7693074, US20040218536, US20080013465Publication number10731156, 731156, US 7652998 B2, US 7652998B2, US-B2-7652998, US7652998 B2, US7652998B2InventorsSeisho Yasukawa, Koji Sugisono, Masanori UgaOriginal AssigneeNippon Telegraph And Telephone CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (8), Non-Patent Citations (5), Classifications (27), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetMulticast communication path calculation method and multicast communication path calculation apparatus
US 7652998 B2Abstract
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:
obtaining minimum delay paths from the source node to each of the plurality of destination nodes using topology information and delay information of the network;
selecting candidate nodes of a rendezvous point node only from nodes on one of the obtained minimum delay paths;
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 a maximum value and a minimum value among delays of the calculated minimum delay paths;
selecting, as the rendezvous point node, the candidate node for which the difference is smallest among differences for all of the candidate nodes; and
2. The multicast communication path calculation method as claimed in claim 1, 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.
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:
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
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 destination node,
4. The multicast communication path setting method as claimed in claim 3, wherein each node in the network measures traffic state of the network and sends the measurement results to the multicast communication path calculation apparatus, and
5. 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:
a part configured to obtain minimum delay paths from the source node to each of the plurality of destination nodes using topology information and delay information of the network;
a part configured to select candidate nodes of a rendezvous point node only from nodes on one of the obtained minimum delay paths;
a part configured to calculate, for each of the candidate nodes, minimum delay paths from the candidate node to each of the destination nodes, and obtain, for each of the candidate nodes, a difference between a maximum value and a minimum value among delays of the calculated minimum delay paths;
a part configured to select, 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 configured to output 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.
6. The multicast communication path calculation apparatus as claimed in claim 5, 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.
7. The multicast communication path calculation apparatus as claimed in claim 5, further comprising:
a part configured to receive the topology information and the delay information of the network; and
a part configured to store the received information in a recording medium,
8. The multicast communication path calculation apparatus as claimed in claim 5, further comprising:
a part configured to include the output results in a multicast path setting control message, and send the multicast path setting control message over the multicast paths indicated by the output results.
9. The multicast communication path calculation apparatus as claimed in claim 5, further comprising:
a part configured to receive a request to calculate the multicast paths from a multicast communication path setting apparatus; and
a part configured to send the output results to the multicast communication path setting apparatus.
10. A computer readable medium storing program code, which when executed by a computer, causes the computer perform a method of calculating multicast paths from a given source node to a plurality of destination nodes in a network including a plurality of nodes, the method comprising:
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 a maximum value and a minimum value among delays of the calculated minimum delay paths;
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 readable medium 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.
Document 2: Pi-Rong Sheu, et. al., �A Fast and Efficient Heuristic Algorithm for the Delay and Delay Variation Bound Multicast Tree Problem�, IEEEICC, 2001.
Basic structure of the information management part 21 is the same as that of the information management part 11 in the multicast communication path calculation apparatus 10, and includes a routing protocol module 211 and a measurement information storing part 212. The measurement part 22 includes a measurement module for measuring status of the network interfaces 243 and information such as delay of each node on the network. The packet process part 24 includes a packet process module 241, a packet transfer table storing part 242 for storing transfer destination of packets, and network interfaces 243. Th packet process module 241 determines types of arriving packets, transfers the packets and determines whether establishing a new path. In addition, the multicast communication path setting apparatus 20 includes a path calculation part 25. The path calculation part 25 includes a calculation process module 251 for calculating multicast paths, and a calculation result storing part 252 for storing the calculation result. In the case where the multicast communication path setting apparatus 20 performs calculation of multicast paths, the path calculation part 25 performs processes the same as those of the multicast communication path calculation apparatus 10. When the multicast communication path setting apparatus 20 does not perform calculation of multicast paths, the multicast communication path setting apparatus 20 may not include the path calculation part 25.
In the following, the procedure for calculating the multicast paths according, to this embodiment is described in detail. In this embodiment, the following information is input from the measurement result storing part, for example. The following information can be collected as the network measurement information by using the existing protocol described in the first embodiment.
(1) One directed distance graph that describes topology of the whole network: G=(V,E,d), wherein V: nodes, E: links (edges) between nodes, d: costs of links (corresponding to delay of the first embodiment)
Step 101) A subgraph G′=(V-s,E-Es,d-ds) is constructed by deleting the source node from the input graph G=(V,E,d).
RP�V1=1, RP�V2=3, RP�V3=3, RP�V4=2,
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS6088333 *Nov 14, 1997Jul 11, 2000Electronics And Telecommunications Research InstituteMulticast routing method using path overlapping efficiency in VP-based on ATM networksUS6697335 *Jul 27, 2000Feb 24, 2004Lucent Technologies Inc.Quality of service routing in information networks over paths having performance-dependent costsUS6717921 *May 17, 2000Apr 6, 2004Lucent Technologies Inc.Method for configuring a shared tree for routing traffic in a multicast conferenceUS6762997 *Mar 29, 2000Jul 13, 2004Lucent Technologies Inc.Method for finding shortest network routing paths subject to system constraintsUS6778531 *Sep 29, 2000Aug 17, 2004Lucent Technologies Inc.Multicast routing with service-level guarantees between ingress egress-points in a packet networkUS7020086 *Jun 29, 2001Mar 28, 2006Telefonaktiebolaget Lm Ericsson (Publ)Lagrange quality of service routingUS7047316 *Mar 23, 2001May 16, 2006Nec CorporationLink state routing techniquesUS20030005149 *Apr 11, 2002Jan 2, 2003Haas Zygmunt J.Independent-tree ad hoc multicast routing* Cited by examinerNon-Patent CitationsReference1G. N. Rouskas, et al., IEEE Journal on Selected Areas in Communications, vol. 15, No. 3, pp. 346-356, "Multicast Routing With End-to-End Delay and Delay Variation Constraints", Apr. 1997.2L. Berman, et al., IBM Technical Disclosure Bulletin, vol. 24, No. 5, XP-002275033, pp. 2511-2512, "Fast Algorithm for Steiner Trees", Oct. 1981.3L. Kou, et al., Acta lnformatica, vol. 15, pp. 141-145, "A Fast Algorithm for Steiner Trees", 1981.4P.-R. Sheu, et al., IEEEICC, pp. 611-618, "A Fast and Efficient Heuristic Algorithm for the Delay-and Delay Variation Bound Multicast Tree Problem", 2001.5Sun Wensheng, et al., "Routing Multipoint Connections in Computer Networks", IEEE, ISCAS '98, XP-010289723, May 31, 1998, pp. VI-494-VI-497.Classifications U.S. Classification370/238, 709/240, 370/238.1, 370/255, 370/256International ClassificationH04L12/24, H04L12/721, H04L12/751, H04L12/727, H04L12/761, H04L12/753, H04L12/18, H04L1/00Cooperative ClassificationH04L45/124, H04L12/1877, H04L45/121, H04L45/02, H04L45/16, H04L45/48, H04L41/12European ClassificationH04L45/48, H04L45/124, H04L41/12, H04L45/02, H04L12/18R2, H04L45/121, H04L45/16Legal EventsDateCodeEventDescriptionJun 26, 2013FPAYFee paymentYear of fee payment: 4May 10, 2004ASAssignmentOwner name: NIPPON TELEGRAPH AND TELEPHONE CORPORATION, JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:YASUKAWA, SEISHO;SUGISONO, KOJI;UGA, MASANORI;REEL/FRAME:015310/0938Effective date: 20040405RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services