[go: up one dir, main page]

WO2004071032A1 - マルチキャスト転送経路設定方法、及びそれを実現するためのマルチキャストラベルスイッチング方法 - Google Patents

マルチキャスト転送経路設定方法、及びそれを実現するためのマルチキャストラベルスイッチング方法 Download PDF

Info

Publication number
WO2004071032A1
WO2004071032A1 PCT/JP2004/001246 JP2004001246W WO2004071032A1 WO 2004071032 A1 WO2004071032 A1 WO 2004071032A1 JP 2004001246 W JP2004001246 W JP 2004001246W WO 2004071032 A1 WO2004071032 A1 WO 2004071032A1
Authority
WO
WIPO (PCT)
Prior art keywords
path
route
multicast
delay
calculation
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2004/001246
Other languages
English (en)
French (fr)
Inventor
Seisho Yasukawa
Koji Sugisono
Masanori Uga
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NTT Inc
Original Assignee
Nippon Telegraph and Telephone Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Nippon Telegraph and Telephone Corp filed Critical Nippon Telegraph and Telephone Corp
Priority to EP20040708880 priority Critical patent/EP1592183A4/en
Priority to US10/522,713 priority patent/US7583601B2/en
Priority to JP2005504888A priority patent/JP3900195B2/ja
Publication of WO2004071032A1 publication Critical patent/WO2004071032A1/ja
Anticipated expiration legal-status Critical
Priority to US12/237,912 priority patent/US7792099B2/en
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/48—Routing tree calculation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H04L45/121—Shortest path evaluation by minimising delays
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/16—Multipoint routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/50—Routing or path finding of packets in data switching networks using label swapping, e.g. multi-protocol label switch [MPLS]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/70—Routing based on monitoring results

Definitions

  • the present invention relates to a multicast transfer path setting method, a multicast transfer path calculation device, a storage medium storing a multicast transfer path calculation program and a multicast transfer path calculation program, and in particular, to a plurality of storage mediums each provided with a multicast transfer apparatus.
  • a multicast transfer path that connects a given start point and a plurality of end points is calculated by a multicast transfer path calculator, and the calculated multicast transfer path is set by a multicast path setting apparatus.
  • the present invention relates to a multicast transfer path setting method, a multicast transfer path calculation device, a multicast transfer path calculation program, and a storage medium storing a multicast transfer path calculation program.
  • the present invention also relates to a multicast label switching method, and particularly to an efficient multicast distribution (transfer) from a multicast source node to a multicast leaf node group in the multicast communication path setting technique in a multicast communication network.
  • a multicast label switching method that enables
  • the present invention also relates to a multicast label switching method that applies a multicast label switching method to a VPN (Virtual Private Network) service, and relates to a VPN using MPLS (Multiprotocol Label Switching).
  • VPN Virtual Private Network
  • MPLS Multiprotocol Label Switching
  • multicast label switching communication that efficiently sets the optimal multicast label switching path in the provider network according to the conditions of the VPN site accommodated by each PE router About the method.
  • Background art Multicast communication which sends video and audio to a specified number of users over a computer network, is attracting attention.
  • information is copied in the portion where the route is divided among the routes connecting the start point of the route and one or more selected end points, and the information is delivered to each end point.
  • One-to-one communication between a specified number of end points and start points When information is delivered using unicast communication, it is necessary to prepare information for the start points by the number of end points. Therefore, using multicast communication reduces the amount of information in the network.
  • multicast communication a specified number of end points are managed in a management unit called a multicast group, and one transfer route is set for the multicast group. This transfer route is set so as to connect from the start point to all end points belonging to the multicast group.
  • a user who wants to obtain information transferred to a certain multicast group obtains information by joining the multicast group. Therefore, the transfer route changes according to the user's participation status.
  • start point, end point, and branch point of the route that exist in the calculated route connect between two points of the same type or two points of different types, and use the start point, end point, and route as the intermediate point of the route. From the routes that do not include branch points, select the route with the highest cost between the two points and delete it. '
  • T1 is a partial path tree including the starting point
  • T2 is another partial path tree.
  • this technique performs the calculation on the assumption that the uplink delay and the downlink delay are the same. Normally, the delay incurred on a link in a network depends on the direction. In order to extend the conventional technology to handle such situations, the following actions are required.
  • MPLS multiprotocol labeling / switching
  • MPLS can be used as a technique for setting a multicast transfer path based on the path setting calculated by the multicast communication path setting technique. For example, there is one that sets a point-to-multipoint label switching path by MPLS and performs label switching transfer (for example, see Reference 3).
  • FIG. 23 there is a technique shown in FIG. 23 as a technique for enabling multicast transfer within a VPN using MPLS.
  • a PIM (Protocol Independent Multicast) instance in a VPN site is distinguished from a PIM instance in a provider network.
  • the PE router has a VRF table for handling PIM instances for each VPN site to be accommodated.
  • the provider network has a pIM instance common to the provider network (for example, see Reference 4).
  • the conventional technology of setting a multicast distribution path using MPLS is a technique that sets a label-switching path of point-to-manole point by MPLS and is capable of performing label switching transfer. Since the label switching path is a one-layer point-to-multipoint label switching path, all the input traffic that is label-switched using the label switching path is transferred to the same destination. In other words, labels are transferred to all leaf nodes that make up the label switching path.
  • Fig. 24 shows the problem of this technology.
  • a first-layer multicast LSP (Labe 1 Switched Path) is set in the provider edge routers PE 2, 3, and 4 from the provider edge router PE # 1.
  • the traffic of the customer edge norators CE # A1, B1, and C1 accommodated by the provider edge router PE # 1 is changed to the viewing state of each group under the provider edge router PE # 2, 3, and 4. Regardless, they are transferred with the same topology. This is not desirable from the viewpoint of network transfer efficiency because it is equivalent to transferring multicast traffic to unnecessary points. For example, there is no receiver in the C1 group under the provider edge router PE # 2, but the distribution of the traffic in the C1 group causes excessive use of network resources.
  • the technology for implementing multicast forwarding on MPLS VPN requires implementation of the PIM-SM multicast routing protocol in the provider network.
  • PIM instances in the VPN site are distinguished from PIM instances in the provider network.
  • the PE router has a VRF table that handles PIM instances for each VPN site to be accommodated.
  • the provider network has a PIM instance common to the provider network.
  • a multicast distribution path is formed between PE routers of the provider network for each VPN site using a rendezvous point.
  • a multicast route of VPN # A and VPN # B is set.
  • PIM-SM Protocol Independent Multicast Sparse Mode
  • IP multicast routing protocol which requires a rendezvous point when realizing multicast distribution, so a single rendezvous point is required. Failure point due to failure point and lack of reliability.
  • a multicast distribution route is set in the provider network, but a path setting that ensures QoS (Quality of Service) is established. Since it is not possible to set a path according to the situation, there arises a problem that strict QoS guarantee and traffic engineering cannot be realized at the end-to-end of the network.
  • PIM-SM requests the P router (provider router) in the provider network to handle the multicast state ((S, G), (*, G)). Since the multicast state is frequently changed on the route, the frequent state change is frequently requested of the high-speed P router of the provider core, and there is a problem that the entire network does not scale.
  • the present invention has been made in view of the above points, and realizes an improvement in the calculation speed of a multicast transfer path, and reduces the cost of the entire path when a delay value incurred between a start point and an end point is limited. It is an object of the present invention to provide a multicast transfer path setting method, a multicast transfer path calculation device, a multicast transfer path calculation program, and a storage medium storing the multicast transfer path calculation program.
  • Another object of the present invention is to provide a multicast label switching method that enables multicast distribution for each sub-leaf group forming a different subset of leaf nodes in a multicast label switching path.
  • a further object of the present invention is to provide a multicast label switching method for realizing an optimum multicast distribution according to a traffic pattern in a virtual closed network while setting a shared multicast path between provider edge routers in the virtual closed network. It is to provide.
  • a method for setting a multicast transfer route is a method for setting a multicast transfer path in a multicast network including a plurality of nodes each provided with a multicast transfer device. And a plurality of end points, each of which is calculated by a multicast transfer path calculation device, and the calculated multicast route is set by the multicast transfer path setting device.
  • the multicast transfer route setting device measures the traffic status for each link in the multicast network and for each direction in which data flows on the link, and transmits the measurement result to the multicast transfer route calculation device, so that the multicast transfer route setting device performs the multicast transfer. Request route calculation, The multicast transfer path calculation device,
  • the maximum delay is compared with a predetermined delay condition. If the delay condition is not met, the delay condition is reset. If a condition that matches the shortest path is found, the calculated shortest In the route, any two nodes of three different types, a start point, an end point, and a branch point of the route, or two nodes of the same type are end points, and the three types of nodes are included in the middle.
  • a route with the highest cost between the two nodes at both ends is searched for from any arbitrary partial route group, the searched route is deleted from the shortest route, and the multicast transfer route is divided into two route trees.
  • the calculated route is set as a complementary route of the route to be deleted to connect the two route trees, and the calculated result is notified to the multicast transfer route setting device,
  • the multicast transfer path setting device
  • a measurement result receiving means for receiving a traffic state measurement result in the multicast network
  • Measurement information storage means for storing the received measurement results
  • a measurement result storage means for storing the measurement result in the measurement information storage means
  • a path calculation means for reading a measurement result from the measurement information storage means and performing a path calculation based on the measurement result
  • the route calculation means is:
  • a shortest path delay calculating means for calculating a shortest path relating to a delay connecting a start point and a plurality of end points, simultaneously calculating a delay from any node on the path to each end point, and recording the calculated value in a storage medium;
  • the maximum delay is compared with a predetermined delay condition. If the maximum delay is not met, the delay condition is reset. If a condition that matches the shortest path is found, the shortest path calculation means According to the calculated shortest path, any two nodes of three different types, namely, a start point, an end point, and a branch point of the path, or two nodes of the same type, as end points, and the 3
  • a maximum cost route search means for searching for a route having the highest cost between the two nodes at both ends from an arbitrary partial route group including a type of node, and deleting the searched route from the shortest route, and performing multicast transfer.
  • Path tree dividing means for dividing the path into two path trees,
  • supplementary path calculation means for setting a separately calculated path as a supplementary path of the path to be deleted in order to connect the two path trees.
  • a multicast transfer path calculation program includes a multicast transfer path that is executed by a computer that calculates a multicast transfer path based on a measurement result of traffic generated on a link in a received multicast network.
  • the maximum delay is compared with a predetermined delay condition, and if the delay condition is not met, the delay condition is reset, and a condition matching the shortest path is found.
  • the shortest path calculated by the means, three different types of the starting point, the ending point, and the branch point of the path, two nodes of the same type, or two nodes of the same type, as the end points, and searches the cost largest path between said three nodes included not from any part path group two ends of the node, the retrieved pathway deleted from the shortest route, the multicast transfer route 2
  • This is a supplementary path calculation step that divides the path into two path trees and sets the separately calculated path as the complement path of the path to be deleted in order to connect the two path trees.
  • the shape of the partial tree whose root is the end point of the path to be deleted among the subtrees of the shortest path is described. It is possible to create a multicast transfer path without any changes. Furthermore, in the present invention, by selecting a complementary route according to a selection criterion that is effective in reducing the cost of the entire tree, a multicast that employs the shortest route between a start point and an end point, which has conventionally been widely used, as a transfer route It is more effective in reducing the cost of a route than a transfer route calculation device.
  • the present invention it is possible to easily calculate the transfer route only by using the function of collecting network measurement information indicating the traffic state in the existing network. Then, it is easy for the multicast transfer route calculation device to acquire the network measurement information, and there is no need to develop a new protocol to collect the network measurement information necessary for the transfer route calculation.
  • a multicast label switching method is a multicast label switching method for setting a label switching path for multicast distribution from a multicast source node to a multicast leaf group node in a multicast communication network.
  • a first-level label is assigned to each subgroup.
  • Hierarchical label switching A plurality of second-level label switching paths that constitute a part of a path of a hierarchical path are set, and a hierarchical first-layer label switching path and a second-level label switching path are used.
  • the input label edge router assigns and assigns traffic having a destination address addressed to the destination leaf group corresponding to the label of the second hierarchy to the corresponding hierarchical label,
  • the transit label switch router labels / resists packets according to the first and second layer label pairs
  • the relay node is used for the point-to-multipoint label switching path. If it is specified as a branch node, the input label pair is replaced with output labels corresponding to multiple output branches, and copied for each output branch.
  • the output label edge router switches the input hierarchical label bucket to the output line while removing the label while determining the group of the hierarchical label, and the leaf group of the first hierarchy in the LSP of the point '2' Of the nodes, the second layer points that form a part of the first layer of the second layer that constitutes different destination subgroups
  • the second layer points that use the 'two' multipoint LSPs Label switching of traffic is performed for each subgroup of the second layer while sharing the same label switching path.
  • a shared multicast label switching path is set in a first layer label using a hierarchical label, and a portion addressed to a subgroup is set in a lower layer.
  • the feature is that multiple multicast label switching paths are set, and the relay node determines the hierarchical label and performs label switching for the entire hierarchical label.
  • the conventional technology is that multicast forwarding is performed to all leaves in the same topology even if the hierarchical labeling technology is provided at the time of multicast transfer. If there is a hierarchical label, only the first layer is used. It is used as label switching information, and differs greatly in that labels at the second level and below are copied without changing the label value at the branch point.
  • the present invention relates to the point that the first layer label is used for the VPN multicast in the same manner as the RFC 2547bis architecture, and is used for a shared point for connecting between PE routers for a label switch of a multi-point label switch path.
  • the main features are that the second-layer labels are used for label switches for VPN sites accommodated by PE routers, and the third layer is used for label switches for distinguishing traffic classes within VPN sites.
  • the conventional technology is that a shared multicast travel switching path is used to efficiently set up a multicast distribution path in the provider network, and the set multicast distribution path is optimized for the traffic conditions in the VPN site. Since multicast transmission is possible on the distribution route, unnecessary multicast The difference is that efficient network operation can be performed without generating one traffic.
  • FIG. 1 is a diagram for explaining the principle of the present invention.
  • FIG. 2 is a principle configuration diagram of the present invention.
  • FIG. 3 is a diagram for describing an outline of an embodiment of the present invention.
  • FIG. 4 is a configuration diagram of a multicast transfer path calculation device according to an embodiment of the present invention.
  • FIG. 5 is a configuration diagram of a multicast transfer path setting device according to an embodiment of the present invention.
  • FIG. 6 is a flowchart of a transfer path calculation algorithm according to the embodiment of the present invention.
  • FIG. 7 is an example of a target network according to an embodiment of the present invention.
  • FIG. 8 is a diagram showing a minimum delay path among paths connecting the start point and each end point of data transfer according to one embodiment of the present invention.
  • FIG. 9 is a diagram showing calculation of a route to be deleted according to an embodiment of the present invention.
  • FIG. 10 is a diagram showing a partial route created after the maximum cost route is deleted according to one embodiment of the present invention.
  • F IG. 11 is a complementary path calculation topology according to an embodiment of the present invention.
  • FIG. 12 is a diagram showing a result of a supplementary path calculation according to an embodiment of the present invention.
  • FIG. 13 is a diagram showing a route calculation result according to one embodiment of the present invention.
  • FIG. 14 is an optimum multicast distribution pattern between PE routers in consideration of the connection VPN site (CE) in the first embodiment of the present invention.
  • F IG. 15 is multicast signaling between optimal PE routers in consideration of the connection VPN site (CE) in the first embodiment of the present invention.
  • F IG. 16 is a hierarchically specified one-specified syndanering that realizes an optimal multicast distribution connection between PE routers in consideration of the connection VPN site (CE) in the first embodiment of the present invention.
  • FIG. 17 is an example of a multicast distribution path in the first embodiment of the present invention.
  • FIG. 18 is a sub-array of VPN #A in the first embodiment of the present invention.
  • F IG. 19 is an MPLS label exchange table designated by hierarchically designated signaling for realizing an optimal multicast distribution connection between PE routers in the first embodiment of the present invention.
  • FIG. 20 is a diagram showing an optimal multicast distribution path setting method in consideration of a distribution pattern of a multicast source in a site according to the first embodiment of the present invention.
  • FIG. 21 is a diagram for explaining a multicast distribution path exchange mechanism between PEs in the first embodiment of the present invention.
  • FIG. 22 is a VPN model to which the present invention is applied.
  • F IG. 23 is a VPN model (Rosen) in the conventional technology.
  • F IG.24 is a conventional multicast connection pattern between PE routers and a multicast transfer pattern to the CE in the VPN site.
  • FIG. 1 is a diagram for explaining the principle of the present invention.
  • the present invention provides a multicast network comprising a plurality of nodes each provided with a multicast transfer device, wherein a multicast transfer route connecting a given start point and a plurality of end points is calculated by the multicast transfer route calculation device, and the calculation is performed.
  • This is a multicast transfer path setting method in which the multicast transfer path set by the multicast path setting device is set. See Fig. 1 for each The steps will be described.
  • the multicast transfer device measures the traffic state for each link in the multicast network and for each direction in which data flows on the link (Step 1). Then, by transmitting the measurement result to the multicast transfer route calculation device, the multicast transfer route calculation device is requested to calculate the multicast transfer route (step 2).
  • the multicast transfer route calculation device calculates the shortest route connecting the start point and a plurality of end points (Step 3). The delay from the node card to each end point is calculated (step 4), and the calculated value is recorded in the storage medium (step 5). Thereafter, the multicast transfer path calculation device calculates the maximum delay when data flows on the calculated shortest path (step 6), and compares the calculated maximum delay with a delay condition given in advance (step 7). . If the predetermined delay condition is not met, reset the delay condition.
  • any two nodes of three different types, the start point, the end point, and the branch point of the path, or two nodes of the same type in the calculated shortest path is searched from an arbitrary partial route group that does not include the three types of nodes, with the node as an end point (step 8).
  • the route is deleted from the shortest route (Step 9), and the multicast transfer route is divided into two route trees (Step 10).
  • the route calculated separately is set as a supplementary route of the route to be deleted to connect the two route trees (step 11), and the calculation result is notified to the multicast transfer route setting device (step 12). ).
  • the multicast transfer path setting device sets a multicast transfer path according to the received calculation result (step 13).
  • FIG. 2 is a principle configuration diagram of the present invention.
  • a multicast transfer path calculation device in a multicast network has the following means: measurement result receiving means 130 for receiving a measurement result of a traffic state in a multicast network, measurement information for storing the received measurement result Storage means 1 1 2, Measurement result storage means 1 1 1, Measurement results stored in measurement information storage means 1 1 2, Measurement results Is read from the measurement information storage means 1 1 2 and the path is calculated based on the measurement result.
  • the route calculation means 120 further has the following means: calculate the shortest route connecting the start point and a plurality of end points, simultaneously calculate the delay from any node on the route to each end point, and calculate the calculated value.
  • maximum delay calculation means 1 2 1 2 to calculate the maximum delay when data flows on the calculated shortest path 1 2 1 2 Compared with the given delay condition, if the delay condition is not met, reset the delay condition.
  • the shortest path calculation means 1 2 1 In the shortest path calculated in 1, any two nodes of three different types, a start point, an end point, and a branch point of the route, or two nodes of the same type are set as end points, and in the middle, the 3 Two from both ends from any partial path group not including node of type Maximum cost route search means 1 2 1 3 to search for the route with the highest cost between the nodes, and a route tree split to delete the searched route from the shortest route and divide the multicast transfer route into two route trees Means 1 2 14 and supplementary path calculation means 1 2 15 for setting the separately calculated path as a supplementary path of the path to be deleted in order to connect the two path trees.
  • FIG. 3 is a diagram for explaining an outline of an embodiment of the present invention. Note that the numbers in 0 in the figure correspond to the numbers in the following description.
  • the present invention is a method for setting a multicast transfer route in a multicast network in a case where an upper limit exists in a delay value incurred when a transfer is performed from a start point to an end point.
  • the multicast network is composed of a plurality of nodes provided with a multicast transfer device 300, and a multicast transfer path calculation device 100 or a multicast transfer device is connected to any one of the nodes.
  • a route setting device 200 is provided.
  • the multicast transfer device 300 in the network collects network measurement information, such as data transfer delays occurring in each link, for each direction of data flow (1), and the multicast transfer device 300 performs multicast transfer.
  • Network measurement information is sent to the route calculation device 100 and the multicast transfer route setting device 200. Notification (2). Then, when the necessity of setting the transfer route of the data to be transferred by the multicast arises, the setting of the data route is performed by the multicast transfer route setting device 200 and the multicast transfer route calculation device 100 according to the processing described later. Is executed.
  • the multicast transfer device 300 has a function of collecting network measurement information of data transferred between nodes, and the multicast transfer route calculation device 100 has a function of calculating a transfer route.
  • the multicast transfer path setting device 200 has a function of setting a transfer path. Further, one node may have the functions of a plurality of the above-described devices.
  • the multicast transfer route setting device 200 transfers the data to the multicast transfer route calculation device 100.
  • Request route calculation (3) The multicast transfer route calculation device 100 instructs its own route calculation module to calculate a route (4).
  • the multicast transfer route setting device 200 instructs its own route calculation module to calculate a route (4 ). Then, the route calculation module of the multicast transfer route setting device 200 or the multicast transfer route calculation device 100 calculates the transfer route based on the collected information (5).
  • the calculation result is notified to the route setting module of the multicast transfer route setting device 200 (6), and the multicast transfer route setting device 200 receiving the calculation result sets the multicast transfer route of the data.
  • the functions for collecting network measurement information described above include OSPF—TE (Open Shortest Path First-Traffic Engineering), IS—IS—TE (Intermediate System- Network measurement information is collected by extending and using a route calculation protocol that has the function of exchanging network measurement information between adjacent nodes such as Intermediate System-Traffic Engineering).
  • the multicast transfer path calculation device 100 is used for a function of receiving network measurement information from the multicast transmission device 300, a bucket transfer function for transmitting a calculation result of a power transfer route, and a route calculation.
  • a program that implements the algorithm It is composed of a storage medium for storing rams, network measurement information, route calculation programs and route calculation results, and a route calculation function for executing route calculation.
  • the route calculation program used in the present invention has a function of calculating the shortest route from the start point of the transfer route to each end point, and a function of calculating the shortest route from the point on the route calculated in the procedure of performing the shortest route. A function to calculate the shortest delay until the end of the route that constitutes the shortest route.
  • the route start point has the function of selecting the node with the lowest cost among arbitrary nodes constituting the subtree of the shortest route including the start point of the deleted route.
  • the shape of the subtree whose root is the end point of the path to be deleted among the subtrees of the shortest path is changed It is possible to create a multicast transfer path without having to do this.
  • a multicast that employs the shortest route between a start point and an end point, which has conventionally been widely used, as a transfer route It is more effective in reducing the cost of a route than a transfer route calculation device. Also, in the present invention, it is possible to easily calculate the transfer route only by using the function of collecting network measurement information indicating the traffic state in the existing network. Then, it is easy for the multicast transfer path calculator 100 to acquire the network measurement information, and it is not necessary to develop a new protocol to collect the network measurement information necessary for the transfer path calculation. There is an advantage that.
  • FIG. 4 shows the configuration of the multicast transfer path calculation device 100 in the embodiment of the present invention.
  • the multicast transfer path calculation device 100 shown in FIG. Information management unit 110, which manages network measurement information related to delays and costs generated by nodes in the network and links connecting each node, route calculation unit 120, which calculates transfer routes, and packets to be transmitted and received It is composed of a packet processing unit 130 for processing.
  • the packet processing unit 130 of the multicast transfer route calculation device 100 receives network measurement information and a route calculation request managed by the information management unit 110, and receives the transfer route calculated by the route calculation unit 120. Is transmitted to the multicast transmission path setting device 200.
  • the information management unit 111 is a routing protocol module 111 that processes the protocol, and the measurement information storage unit 111 that manages network measurement information such as network topology, delay, and cost obtained by the protocol. And 2.
  • the route calculation unit 120 includes a route calculation module 122 that calculates a transfer route, and a calculation result storage unit 122 that stores a calculation result.
  • the bucket processing unit 130 determines the type of the arriving bucket, and transfers the packet, or records the packet processing module 131, which sends the packet to the information management unit 110, and the packet transfer destination. It has a transfer table storage unit 132 and one or more network interfaces 133.
  • FIG. 5 shows the configuration of a multicast transfer path setting device according to an embodiment of the present invention.
  • a multicast transfer path setting device 200 stores information on delay / cost information generated by nodes / links in a network, and information / delay / cost generated by its own processing. It is composed of a measuring unit 220 for measuring, a route setting protocol processing unit 230 for setting a route when a new data packet is generated, and a packet processing unit 240 for processing an arriving bucket. .
  • the basic configuration of the information management unit 210 is the same as that of the information management unit 110 of the multicast transfer path calculation device 100, and includes a routing protocol module 211 and a measurement information storage unit 212. ing.
  • the measuring unit 220 is a network interface provided in the packet processing unit 240. It is equipped with a measurement module that measures information such as the status of the ace 243 (described later) and the processing delay of each node on the network.
  • the packet processing unit 240 determines the type of the arriving packet, transfers the packet, and determines a new route setting.
  • the packet processing module 241 determines the destination of the packet. It has a transfer table storage unit 242 and a network interface 243.
  • the multicast transfer route setting device 200 includes a route calculation unit 250.
  • the route calculation unit 250 includes a calculation processing module 251, which calculates a transfer route, and a calculation, which stores a calculation result. And a result storage unit 25 2.
  • the route calculation unit 250 performs the same processing as that of the multicast transfer route calculation device 100.
  • the route setting protocol processing unit 230 receives the route setting request from the packet processing unit 240, and performs a process of transmitting the route setting request to the multicast transfer route calculation device 100. Further, the route setting protocol processing unit 230 has a function of setting a transfer route for data transfer in accordance with the calculation result of the transfer route received from the multicast transfer route calculation device 100.
  • the node includes the multicast transfer route calculation device 100 and the multicast transfer route setting device 200 And performs the above-described processing.
  • the route setting protocol processing unit 230 requests a route calculation to an adjacent node.
  • a node having the function of the multicast transfer device 300 in the network always exchanges network measurement information indicating network topology ⁇ delay ⁇ cost between adjacent nodes. Then, each node stores the network measurement information obtained by the exchange process.
  • the network measurement information exchanged by the node is the network measured by the next node. It includes not only the measurement information but also the network measurement information held by the own node and measured by other nodes. By these switching operations, each node holds network measurement information such as connection information and delays at all nodes in the network. Then, the node having the function of the multicast transfer path setting device 200 that newly sets the transfer route requests the node having the function of the multicast transfer path calculation device 100 to perform the route calculation. At this time, the node having the function of the multicast transfer route calculation device 100 sends network measurement information on traffic such as topology / delay in the network managed by the information management unit 110 and a route calculation request. The transfer route is calculated based on the information of the end point sent from the selected node.
  • FIG. 6 is a flowchart of a transfer path calculation algorithm according to the embodiment of the present invention.
  • the route calculation request from the node having the function of the multicast transfer route setting device 200 is received by the multicast transfer route calculation device 100.
  • the multicast transfer route calculation device 100 also receives information on the end point of the data transfer from the multicast transfer route setting device 200.
  • the route calculation unit 120 of the multicast transfer route calculation device 100 changes the topology of the network, which is recorded in the measurement information storage unit 112 (database) of the information management unit 110, into the network indicating the traffic state.
  • the measurement information is read (step 101).
  • the route calculation module 122 uses the network measurement information to calculate the minimum delay route with the smallest delay between the start point and the end point of the data transfer (step 102). At this time, the route calculation module 122 calculates the minimum delay route from the node that transmitted the route calculation request to the node at the end of data transfer. The Dijkstra algorithm is used to calculate the minimum delay path. From this, the minimum delay route to the node that issued the route calculation request and each end point is calculated.
  • the route calculation module 122 of the multicast transfer route calculation device 100 determines the start point and each end point of the nodes constituting the minimum delay route from the start point to the end point obtained in step 102.
  • a search is made for a partial route that is sandwiched between any one of the branch points of the route and that does not include the above-mentioned three types of nodes in the middle (step 103).
  • the cost of the link constituting the partial route is the lowest. Is selected, and this is deleted from the aforementioned minimum delay path.
  • information on the end point of the route to be deleted is recorded in the calculation result storage unit 122 (step 104).
  • the aforementioned minimum delay path is divided into two partial paths.
  • the route calculation module 122 of the multicast transfer route calculation device 100 determines the pseudo start point and the start point of the minimum delay route among the above-described divided partial routes from the pseudo start point.
  • the link connected to all nodes included in the included partial path and the link are added to the network topology recorded in the measurement information storage unit 112 of the information management unit 110.
  • the links and nodes passing through the partial path not including the starting point, and all the links connected to the node are deleted from the above-mentioned topology.
  • the node serving as the starting point of the above-described partial path to be deleted and the link connecting the node and a node that does not constitute a partial path are not to be deleted from the network topology (step 1). 0 5).
  • a route connecting the pseudo starting point and the starting point of the minimum delay path and connecting the starting points of the partial paths is searched.
  • an algorithm called k-th shortest path algorithm which calculates the path that realizes the kth smallest delay from the path that achieves the minimum delay, is applied to search for the path.
  • This type of algorithm searches for the k-th smallest route and then for the k-th smallest route. Therefore, it is possible to set an upper limit of the allowable delay and execute the algorithm until all the routes that fall below the upper limit are found.
  • the route searched in this way is a candidate for a route that complements the deleted route (step 106).
  • the route calculation module 1 2 1 of the multicast transfer route calculation device 100 calculates the total sum of the costs of the links constituting the route among the routes searched by the k-th shortest path algorithm. And select the route with the lowest cost. The selected route is selected as a new route to complement the deleted route (step 107).
  • the route calculation module 122 of the multicast transfer route calculation device 100 determines that the operations from step 103 to step 107 described above are the same as the route to be deleted and the selected supplementary route. Judge whether it will be. In the case of the same route, the route with the next highest cost is searched, and in all the searched routes, the complementary route is the same as the searched route. Repeat until one path is reached (step 108).
  • OSPF-TE is used when the multicast transfer device 300 collects network measurement information such as delay.
  • OSPF—TE is a communication protocol that stores network information such as delays in the topology information exchange information of OSPF, which is a routing protocol of multicast.
  • a multicast MPLS (Multi Protocol Label Switching) protocol which is an extension of RSVP—Resource Reservation Protocol-Traffic Engineering (TE) for performing explicit routing.
  • Use Multicast MPLS adds an information element that can store the tree topology to the message that generates the LSP (Label Switched Path) for the RSVP—TE used in normal MPLS, and follows the topology information. It is a technology that can establish Point-to-Multipoint LSP.
  • FIG. 7 shows a multicast network according to an embodiment of the present invention.
  • 200 indicates the start point of the data transfer path, and 1 to 3 indicate the end points of the data transfer.
  • a to I are intermediate nodes between the start point and the end point, and have the function of the multicast transfer apparatus 300.
  • the multicast transfer route setting device 200, nodes A to I, and the end nodes 1 to 3 are connected by a communication cape link (link) to form a multicast network.
  • Each link has two characteristics: delay, cost, and level. It has been recognized that the link delay and cost characteristics have different delay and cost characteristics depending on the direction in which data enters the link. In this case, when data moves rightward (from D to E), as in link D—E, the delay characteristic is 1 and the cost characteristic is 10 and moves in the opposite direction (from E to D).
  • the multicast transfer path setting device 200 transfers the data to the end points 1 to 3 based on the result calculated by the multicast transfer path calculation apparatus 100, starting from itself.
  • the network measurement information indicating the delay occurring in the link between the nodes is collected by each node using the OSPF-TE described above. Then, the network measurement information is notified to the multicast transfer path calculation device 100 in advance.
  • FIG.8 shows the minimum delay path among the paths connecting the start point and the end points of the data transfer according to the embodiment of the present invention.
  • the multicast transfer route calculation device 100 Upon receiving the route calculation request from the multicast transfer route setting device 200, the multicast transfer route calculation device 100 first starts from the multicast transfer route setting device 200, which is the starting point, to each of the end points 1 to 3. Calculate the minimum delay path. At this time, the multicast transfer path calculation device 100 uses Dijkstra's algorithm as the calculation algorithm of the minimum delay path. Dijkstra's algorithm is commonly used as an algorithm for calculating the minimum delay path.
  • the minimum delay route from the start point 200 calculated by the multicast transfer route calculation device 100 to the end points 2, 2, 3 is as follows:
  • Multicast transfer route setting device 200 ⁇ Node B ⁇ Node D ⁇ Node ⁇ No 1 G ⁇ End point 2,
  • Multicast transfer route setting device 200 Node B ⁇ Node D ⁇ Node ⁇ No — G ⁇ Node H ⁇ End point 3
  • the maximum value of the delay incurred between the start point and the end point is the delay incurred on the route connecting the start point 200 and the end point 3. Since the value is 6, this satisfies the condition for the delay upper limit.
  • FIG. 9 is a diagram showing calculation of a path to be deleted according to an embodiment of the present invention.
  • both ends are either the start point, the end point, or the branch point of the route, and the intermediate nodes of the route include the start point, the end point, and the branch point of the route.
  • the applicable route is
  • FIG.9 shows the search result of the route, and deletes the selected partial route from the route selected as the minimum delay route. As a result, the minimum delay path is split into two.
  • 40 be a partial route including the starting point
  • 50 be a route not including the starting point. This is shown in FIG.10.
  • the supplementary route is defined as a partial route 50 among the routes starting from an arbitrary point included in the partial route 40 and ending with the end point of the deleted route, that is, the starting point of the partial route 50.
  • the one that does not intersect with the point to which it belongs and that has the smallest sum of the cost characteristics held by the links that make up the route is selected. The calculation method is described below.
  • the topology of the network used for the calculation uses the network to be calculated with the following modifications.
  • a pseudo starting point 70 is prepared, and links are opened from the pseudo starting point 70 to all nodes belonging to the partial path 40.
  • the link excluding the link constituting the partial path 50 and the starting point G of the partial path 50, and all the links connected to the node are removed.
  • a topology as shown in FIG. 11 is completed.
  • the path connecting the pseudo starting point 70 and the starting point G of the partial path 50 is calculated using the k-th shortest path algorithm.
  • the k-th shortest path algorithm is an algorithm used to search the kth shortest path counting from the path with the smallest delay, and algorithms for searching such paths have already been proposed.
  • delay and cost can be considered as characteristic values used in the calculation. If the characteristic value used in the calculation is a delay, the k-th shortest path algorithm is applied recursively while the delay incurred between the start point and each end point falls below a given upper limit. That is, after calculating the k-th shortest path, the k-th shortest path is searched using the calculation result.
  • the one with the smallest sum of the cost characteristics held by the links constituting the route for each link is selected as the supplementary route.
  • the calculation is terminated when the discovered delay holding the k-th lowest cost for the first time falls below the upper limit of the delay incurred between the start point and each end point, and at that time
  • the route excluding the pseudo starting point calculated in is selected as the supplementary route.
  • FIG.12 shows the calculation results in this example.
  • the path with the lowest cost is the pseudo starting point 70 ⁇ Node B ⁇ Node D ⁇ No KF ⁇ Node E ⁇ No KG Therefore, excluding the pseudo starting point 70,
  • Node B ⁇ No KD ⁇ No KF ⁇ No KE ⁇ No KG is selected as the supplementary route.
  • the delay value generated from the node G recorded at the start point G of the partial path 50 to each end point downstream of the node G is used.
  • the delay from the start point of each new partial route 50 to each end point after the recalculation of the partial route 50 is calculated. It had to be calculated.
  • the calculation time is reduced.
  • the maximum delay between the start point and the end point realized when the supplementary route is connected is 7 that is incurred on the route connecting the start point 200 and the end point 3.
  • the delay condition is satisfied because there is a condition that the maximum delay allowed by the route is 7.
  • a route that satisfies the above conditions is set as a supplementary route, and is adopted as a route connecting the partial route 40 and the partial route 50.
  • the termination condition of the algorithm will be described. If the supplementary route is the same as the deleted route, or if the route has a longer delay than the deleted route, the deleted route becomes the supplementary route and the algorithm ends. If they are different, mark the supplementary path, and both ends are either the start point, end point, or the branch point of the path, and the intermediate node of the path does not include the start point, end point, and the branch point of the path Of which The route with the highest cost other than the marked route is selected, and after deletion, the complementary route is found. This operation is repeated until all the paths are marked. In this way, a calculation result as shown in FIG. 13 is calculated.
  • the above-described multicast transfer route calculation device and multicast transfer route setting device have a computer system inside.
  • the above-described process is stored in a computer-readable storage medium in the form of a program, and the above-described process is performed when the computer reads and executes the program.
  • the computer-readable storage medium refers to a magnetic disk, a magneto-optical disk, a CD-ROM, a DV-ROM, a semiconductor memory, or the like.
  • the computer program may be distributed to a computer via a communication line, and the computer that has received the distribution may execute the program.
  • the constructed program when stored in a portable storage medium such as a hard disk, a flexible disk, and a CD-ROM connected to a computer that operates as a multicast transfer path calculation device, the present invention may be implemented. Alternatively, it can be installed on the CPU.
  • the present invention by using a system having a route calculation node having a route calculation algorithm in consideration of an upper limit value of a delay generated between a start point and an end point, the start point and each end point
  • a route calculation node having a route calculation algorithm in consideration of an upper limit value of a delay generated between a start point and an end point
  • FIG. 14 shows a pattern of multicast distribution between optimal provider edge (PE) routers in consideration of a connection VPN site (CE) according to an embodiment of the present invention.
  • provider edge routers PE # 1, PE # 2, PE # 3, and PE # 4 and a provider (p) router that connects them to the PE router exist in the provider network.
  • PE # 1 contains CE # A1 belonging to VPN # A, CE # B1 belonging to VPN # B, and CE # C1 belonging to VPN # C.
  • PE # 2 contains CE # A2 belonging to VPN # A and CE # B2 belonging to VPN # B.
  • PE # 3 accommodates CE # A3 belonging to VPN # A, CE # B3 belonging to VPN # B, and CE # C3 belonging to VPN # C.
  • PE # 4 accommodates CE # B4 belonging to VPN # B and CE # C4 belonging to VPN # C.
  • Point # 1 Point # 2 Multipoint LSP (Label Switched Path) that is shared by all traffic to Point # 2, # 3 and # 4 is set.
  • Point # 2 Multipoint LSP Label Switched Path
  • the path indicated by the clay pipe mark in the figure corresponds to the LSP.
  • multicast label switching between PE routers considering the site connection relationship for each VPN according to the VPN site accommodated in the PE router You need a route.
  • VPN # A only sites under PE # 2 and PE # 3 are accommodated, so PE # 1 is the source and PE # 2 and 3 are the multicast sublabels of the leaves. It is desirable that a switching path be set.
  • the multicast distribution route indicated by the arrow corresponds to the multicast sublabel switching route.
  • the dashed-line arrow VP N # C corresponds to the solid-line arrow.
  • the label switching path of the second layer is a part of the label switching path of the first layer.
  • Fig. 15 shows the signaling mechanism for setting the multicast labeling switching path of Fig. 14.
  • the multicast label signaling is set, for example, by extending the existing RSVP-TE (Resource Reservation Protocol-Traffic Engineing) mechanism by multicast.
  • the multicast distribution circuit set as shown in FIG. 15 is specified by the TERO (Tree Replica Route Object) of the path message.
  • the specific format is shown in FIG. 16 corresponding to the network topology.
  • a two-layer multicast label switching path is set in order to set an optimum multicast distribution path between PE routers. Therefore, two layers of TERO indicating the setting route of the multicast label switching path to be set are prepared.
  • the multicast label switching path connecting PE # 1 (A) on the first layer to PE # 2 (D), PE # 3 (E), and PE # 4 (G) is specified.
  • TERO is defined as ⁇ A (0), B (1), C (2), D (3), E (3), F (2), G (3) ⁇ .
  • This specification method is specified by the Depth First Order algorithm. The number within 0 attached to each node indicates the distance (hop count) of the source node PE # 1 (A) force.
  • the multicast distribution path has a connection configuration as shown in FIG. Since the Depth First Order algorithm first specifies the path in the depth direction, the specification of TERO is ⁇ A (0), B (1), C (2), D (3), E (3), F (2), G (3) ⁇ . Furthermore, a multicast LSP for each VPN is set under the multicast LSP of the first layer.
  • a Path message is transmitted to the leaf node as shown in FIG.
  • a Hierarchical label is assigned from a downstream by a Resv message.
  • Fig. 19 shows the label conversion table and the hierarchical labels used in the link that are set for each node in this operation. For example, at node PE # 3 (E), all TEROs in the second layer including VP N # A, B, and C arrive, so A (101, 30), B (101 , 25), and C (101, 5).
  • PE # 2 does not reach the TERO of the second layer including VPN # A and B, so no label for VPN # C is given and A (1,1), B (1, 25) and C (l, .Nul 1).
  • the transfer function of the label packet transmitted from the BC to the CD / CE link is set to the table.
  • the label for the CD link for VPN # C is not assigned to the link of node C of F IG. 19, so one label (101, 5) is set for the CE link only. Les ,.
  • VPN # A and B the label packet arriving from BC is subjected to necessary label exchange and branched to CD and CE, but the label packet of VPN # C is not transferred to CD and the label is only sent to CE. It is switching. This operation continues at the hop pie hop to the sending node ⁇ , and a label switching path hierarchized for each VPN is formed. In this way, the packet input to node A is provided with a layered label for each VPN, label-switched with the layered label at the relay node, and multicast-distributed to the leaf nodes.
  • FIG.20 has multicast sources M # A, M # B, and M # C in VPN # B under PE # 1 and has different multicast distribution patterns (upper left of FIG. 20) Assume the case. In this case, M # A, M # B, and M # C are distributed to all PE routers accommodating VPN # B, PE # 2, PE # 3, and PE # 4 on the label switch route of two layers. Network efficiency is not good. For example, it is also multicast-distributed to PE # 4 that does not receive M # A.
  • this label is a multicast source group that belongs to the same topology B topology in the same VPN site.
  • An arbitrary distribution pattern can be realized by using such an inductive hierarchical mechanism.
  • the three-layer label switching technology described in the above embodiment is effective.
  • the multicast distribution path information accommodated in each VPN is exchanged between the PE routers by a normal unicast route exchange. Needs to be replaced in the same way as in.
  • An example is shown in FIG. As shown in the figure, route exchange is possible with MP-BGP defined by rfc 2547 bis.
  • another PE router distributes a multicast distribution path in a VPN site accommodated in PE 1 to PE 1.
  • the multicast route MG # of VPN # A and the multicast route MG # ⁇ of VPN # B are distributed to PE 1 using MP-BGP. are doing.
  • a one-way route exchange example is shown.However, by performing bidirectional full-mesh route exchange between PE routers, each PE router becomes a multicast route within the VPN site accommodated by the opposite PE router. Can all be grasped.
  • Fig. 22 shows a VPN model to which the present invention is applied. By applying this model, VP N Site Anime One The PIM-SM multicast of the application can also be transferred via VPN.
  • the multicast label switching method and the VPN multicast label switching method of the present invention it is possible to reduce the transfer cost of the entire multicast distribution path and to perform multicast distribution with the optimal topology for the destination receiving group.
  • a transfer network and VPN network can be built.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Description

明 細 書 マルチキャスト転送経路設定方法、 及びそれを実現するためのマルチキャストラ ベルスイッチング方法 技術分野
本発明は、 マルチキャスト転送経路設定方法及びマルチキャスト転送経路計算 装置及びマルチキャスト転送経路計算プログラム及びマルチキャスト転送経路計 算プログラムを格納した記憶媒体に係り、 特に、 マルチキャスト転送装置がそれ ぞれ設けられた複数のノードにより構成されるマルチキャストネットワークにお いて、 与えられた始点と複数の終点とをそれぞれ結ぶマルチキャスト転送経路を マルチキャスト転送経路計算装置により計算し、 計算されたマルチキャスト転送 経路をマルチキャスト経路設定装置が設定するマルチキャスト転送経路設定方法 及びマルチキャスト転送経路計算装置及びマルチキャスト転送経路計算プロダラ ム及ぴマルチキャスト転送経路計算プログラムを格納した記憶媒体に関する。 また、 本発明は、 マルチキャストラベルスィツチング方法に係り、 特に、 マル チキャスト通信ネットワークにおいて、 上記マルチキャスト通信経路設定技術に おけるマルチキャストソースノードからマルチキャストリーフノードグループま での、 効率的なマルチキャスト配信 （転送） を可能とするマルチキャストラベル スィツチング方法に関する。
また、 本発明は、 マルチキャストラベルスイッチング方法を V P N (仮想閉域 網） サービスに適用したマノレチキャストラベルスィツチング方法に係り、 MP L S (マルチプロトコ/レラベノレスイッチング Multi protocol Label Switching) を 用いた V P N内で、 P E (プロバイダエッジ） ルータ間に効率的に、 各 P Eルー タが収容する V P Nサイトの条件に応じてプロパイダネットワーク内に最適なマ ルチキャストラベルスィツチング経路を設定するマルチキャストラベルスィツチ ング通信方法に関する。 背景技術 コンピュータネットワーク上で、 動画や音声を特定多数のユーザに酉己送するマ ルチキャスト通信が注目を集めている。 この通信方式は、 経路の始点と選択され た 1つ以上の終点を結ぶ経路のうち、 経路が分力れる部分において情報をコピー し、 各終点へと情報を配送する。 特定多数の終点と始点とを 1対 1で通信を行う ュニキャスト通信を用いて情報を配送した場合、 終点の数だけ始点は情報を用意 する必要がある。 よって、 マルチキャスト通信を用いることにより、 ネットヮー ク内の情報量は減少する。 マルチキャスト通信では特定多数の終点をマルチキヤ ストグループと呼ばれる管理単位で管理し、 マルチキャストグループに対して 1 つの転送経路が設定される。 この転送経路は始点からマルチキャストグループに 属する全ての終点を接続するように設定される。 また、 あるマルチキャストグル ープへと転送される情報を取得したいユーザは、 マルチキャストグループに参加 することで情報を取得する。 このため、 ユーザの参加状況に応じて転送経路は変 化する。
マルチキャスト通信を用いるアプリケーションとして、 テレビ会議やオンライ ンゲーム、 映画やテレビ等の動画配送があげられる。 このうち、 テレビ会議では データ転送遅延が重要な性能項目となる。 通常行われる会話では、 音声が相手に 届くまでの遅延が 1 0 0 m s以下である場合、 違和感なく会話ができることが分 かっている。 このため、 これらのアプリケーションを使用してサービスを提供す る際、 顧客が満足するサービスを提供するためには、 ある一定値以下の遅延を実 現することが重要となる。 このようなサービスを提供する手段として、 始点から 終点までのデータの転送経路を選択する際、 アプリケーションが要求する遅延条 件を満たす経路を選択する方法が存在する。
また、 マルチキャスト通信における経路計算において、 経路全体のコストを小 さくすることが、 ネットワーク管理者の作業の軽減や経^ ¾用者が支払う経路使 用料の観点から要求される。 このため、 テレビ会議などのサービスを実現する際 には、 遅延条件を満たしつつ、 経路全体のコストを小さくすることを目的とした アルゴリズムが要求される。 このような経路選択アルゴリズムを Delay constrai ned multicast algorithmと呼ぶ。 近年、 このような遅延に厳しいアプリケーシ ョンを するために、 Delav constrained multicast algorithmの実現方法に 注目が集まっている （例えば、 下記文献 1、 文献 2参照)。
現在提案されている方式のうち、 遅延条件を満たすコストの小さい経路を計算 することで経路全体のコストを削減するという観点で優れている方式がある。 こ の方式は以下のような手続を実行する。
① 始点と各終点を結ぶ最短経路を計算する。
② 計算された経路の中に存在する、 始点、 終点、 経路の分岐点のうち、 同種 の 2点間、 もしくは異種の 2点間を接続し、 経路の中間点として始点、 終点、 経 路の分岐点を含まない経路の中で、 最も 2点間のコストが大きいものを選択し、 削除する。 '
③ 削除した結果、 2分割された経路木 T 1と T 2が生成される。 ここで、 T 1は始点を含む部分経路木、 T 2はそれ以外の部分経路木とする。
④ 2つの経路木に属する任意の点を端点とし、 始点、 終点間で被る遅延が予 め提示してある条件を満たす経路を削除した経路の補完経路として計算し、 その うち最もコストの小さいものを経路木に追加する。
⑤ 続いて、 次にコストの大きい項目②記載の経路を探索する。
⑥ すべての経路の補完経路を探索し終わるまで②〜⑤の手続を繰り返す。 この技術をテレビ会議などのサービス実現時に適用することで、 ある上限値以 下の転送遅延を実現する転送経路を計算することが可能となる （例えば、 文献 2 参照)。
これら背景技術は以下の文献に記載されている。
(文献 1 )
V. Kompella他、 "Multicast routing for multimedia communication, " IE EE/ACM Transactions on Networking, Volume: 1 Issue: 3， pp. 286-292， J une 1993
(文献 2 )
Q. Zhu,他、 "A source-based algorithm for delay-constrained minimum- cost multicasting," proc in IEEE INFOCOM '95, vol. 1， p. 377-385, 1995 しかしながら、 上記の遅延条件を満たすコストの小さい経路を計算することで 経路全体のコストの削減を図る技術では、 以下のような問題がある。 当該技術で は、 計算に必要な時間が大きいことが報告されている。
また、 当該技術は、 リンクの上りと下りの遅延が同じであるとの想定のもとに 計算を実行する。 通常、 ネットワーク内のリンクで被る遅延は方向によって異な る。 従来技術をこのような状況に対応できるように拡張するには、 次のような動 作が必要となる。
(1) 補完経路 卩時に補完経路の終点 （部分木 Τ 2内に存在する） 力 Τ 2に存在する終点までの経路の再計算を実行。
(2) 再計算結果に対し、 始点ー終点間で被る遅延値を計算し、 遅延条件を 満たすことを確認。 条件を満たさな ヽ場合次にコストの小さレヽ経路を選択し、 (1) の処理を行う。
また、 再計算の実施に伴い、 変更前の経路では、 遅延条件を満たしていない終 点が変更後条件を満たさなくなるという事例が多く発生することが予想される。 この事態による経路の再計算などの問題が生じるため、 より計算時間が大きくな ることが予想される。
迅速なサービスの «を実現するためには、 経路設定を短時間で行うことが求 められる。 しかし、 上記の従来の方式を採用した場合、 経路計算に多くの時間を 消費するため、 サービス開時間に遅延が生じる。
一方、 上記マルチキャスト通信経路設定技術により計算された経路設定に基づ きマルチキャスト転送経路を設定する技術として、 MPLS (マルチプロトコル ラベ^/スイッチング）を用いることができる。例えば、 MPLSによるポイント · ツー ·マルチポィント （point-to-multipoint) のラベルスィツチング経路を設定 し、 ラベルスイッチング転送するものがある （例えば、 文献 3参照)。
また、 MP LSを用いた VP N内でマルチキャスト転送を可能にする技術とし て、 F IG. 23に示すような技術がある。 同図に示す例では、 VPNサイト内 の P I M (Protocol Independent Multicast)ィンスタンスとプロパイダネットヮ ーク内の P IMインスタンスを区別する。 PEルータには、 収容する VPNサイ ト毎に P IMインスタンスをハンドリングする VRFテーブルを具備する。 さら に、 プロバイダネットワーク側にはプロバイダネットワーク共通の p IMインス タンスを具備する （例えば、 文献 4参照)。 これら背景技術は以下の文献に記載されている。
(文献 3 )
http：〃 w w.ietf.org/internet-draft draft-yasukawa-mpls-rsvp-nmlticast-Ol.txt (Extended RSVP-TE for Multicast LSP Tunnels) IETF
(文献 4 )
http：〃 www.ietf.org/internet-draft/draft-rosen-vpn-mcast-04.txt
(Multicast in MPLS BGP VPNs) IETF
しかしながら、 従来の MP L Sを用いてマルチキャスト配信経路を設定する技 術は、 MP L Sによるポィント ·ツー 'マノレチポィントのラベルスィツチング経 路を設定し、 ラベルスイッチング転送することは可能である力 設定されるラベ ルスィツチング経路は、 一階層のポィント 'ツー ·マルチポィントのラベルスィ ツチング経路であるため、 当該ラベルスィツチング経路を用いてラベルスィツチ される入力トラヒックは、 全て同一の宛先に転送される。 つまり、 ラベルスイツ チング経路を構成する全リーフノードまでラベル転送される。 F I G. 2 4に当 該技術の問題を示す。 同図の例では、 プロバイダェッジルータ P E # 1よりプロ バイダェッジルータ p E # 2， 3， 4に第一階層のマルチキヤスト L S P (Labe 1 Switched Path) が設定されている。 このため、 プロバイダエッジルータ P E # 1が収容するカスタマエッジノレータ C E # A 1， B 1 , C 1のトラヒックは、 プロバイダェッジルータ P E # 2， 3 , 4配下の各ブループの視聴状態に関わら ず同一のトポロジで転送されてしまう。 これは、 ネットワークの転送効率の観点 力 ら考えると、 不要なポイントにマルチキャストトラヒックを転送することに相 当するので望ましくない。 例えば、 プロバイダエッジルータ P E # 2配下には C 1グループの受信者が存在しないが、 C 1グループのトラヒックを配信すること により、 ネットワークリソースの過剰利用を引き起こしている。
このように、 当該技術を用いたラベルスィツチングは、 ポイント 'ツー 'マル チポイントと同一の転送トポロジのラベル転送を実現する。 このため、 設定した ポィン.ト ·ツー ·マノレチポィントのラベルスィツチ L S Pを共有し、 ラベルスィ ツチ L S Pを構成するリーフノードグループの部^^合であるサブグループにマ ルチキャスト配信しょうとすると、 サブグループを構成するリーフノード以外に もマルチキャストラベル転送されてしまい、 部分マルチキャスト転送できない問 題が生じる。
さらに、 MP L Sの V P N上でマルチキャスト転送を実現する技術では、 プロ バイダネットワーク内に P IM—SMマルチキャストルーティングプロトコルの 実装を要求する。 F IG. 23に示す VPNマルチキャスト技術では、 VPNサ ィト内の P IMインスタンスとプロパイダネットワーク内の P IMインスタンス を区別する。 PEルータには、 収容する VPNサイト毎に P IMインスタンスを ハンドリングする VRFテーブルを具備する。
さらに、 プロバイダネットワーク側には、 プロバイダネットワーク共通の P I Mインスタンスを具備する。 このとき、 プロバイダネットワークの PEルータ間 に V P Nサイト毎にマルチキャスト配信経路を、 ランデブーボイントを用いて形 成する。 F IG. 23の例では、 VPN#AとVPN#Bのマルチキャスト経路 が設定されている。 P IM-SM (Protocol Independent Multicast Sparse M ode)は広く知られているように、 I Pマルチキャストルーティングプロトコルで あり、マノレチキャスト配信を実現する場合にランデブーボイントを要求するため、 ランデブ一ボイントが単一障害ボイントとなり信頼性に欠ける点、 さらに、 I P マノレチキャストノレーティングプロトコノレであるため、 プロバイダネットワークに マルチキャスト配信経路を設定するものの、 Qo S (Quality of Service) を確 保したパスの設定、 トラヒックに応じたパス経路設定ができないため、 ネットヮ ークのエンド'エンドで厳密な Qo S保証、 トラヒックエンジニアリングが実現 できない問題が生じる。
さらに、 プロパイダネットワーク内の Pルータ （プロバイダルータ） にマルチ キャスト状態 （（S， G)， （*， G)) のハンドリングを要求する、 P IM—SM はマルチキャストトラヒックの視聴状態に応じてマルチキャストの経路上でマル チキャスト状態を頻繁に変更するため、 プロバイダコアの高速 Pルータにこのよ うな頻繁な状態変化を高頻度で要求するため、 ネットワーク全体としてスケール しない課題がある。
さらに、 VPN毎マルチキャスト経路を設定するため、 プロバイダネットヮー ク内のマルチキャストコネクション数が増大する問題、 さらに、 マルチキャスト コネクション内でのトラヒック酉 S信パターンを制御できないため、 V P Nサイト 内に複数のマルチキャストトラヒックが存在する場合には、 不要なトラヒックを 受信者がいない V P Nサイトにも配送してしまう問題がある。 発明の開示
本発明は、 上記の点に鑑みなされたもので、 マルチキャスト転送経路の計算速 度の向上を実現し、 始点と終点の間で被る遅延値に制限値が生じるときの経路全 体のコストの削減を実現できる、 マルチキャスト転送経路設定方法及ぴマルチキ ヤスト転送経路計算装置及びマルチキャスト転送経路計算プログラム及びマルチ キャスト転送経路計算プログラムを格納した記憶媒体を«することを目的とす る。
また、 本発明は、 マルチキャストラベ スイッチング経路内のリーフノードの 異なる部分集合を構成するサブリーフグループ毎にマルチキャスト配信が可能に なる、 マルチキャストラベルスイッチング方法を提供することを目的とする。 さらなる本発明の目的は、 仮想閉域網内でプロバイダエッジルータ間に共有マ ルチキャスト経路を設定しながらも、 仮想閉域網内のトラヒックパターンに応じ て最適なマルチキャスト配信を実現するマルチキャストラベルスィツチング方法 を提供することである。
上記目的のうち、 少なくとも一つを達成するため、 本発明の一態様によるマノレ チキャスト転送経路設定方法は、 マルチキャスト転送装置がそれぞれ設けられた 複数のノードにより構成されるマルチキャストネットワークにおいて、 与えられ た始点と複数の終点とをそれぞれ結ぶマルチキャスト転送経路をマルチキャスト 転送経路計算装置により計算し、 計算されたマルチキャスト 経路をマルチキ ヤスト経路設定装置が設定するマルチキャスト転送経路設定方法において、 マルチキャスト転送装置が、
マルチキャストネットワーク内のリンク毎に、 かつ該リンクにデータが流れる 際の進行方向毎にトラヒックの状態を計測し、 計測結果をマルチキャスト転送経 路計算装置に送信することでマルチキャスト転送経路設定装置はマルチキャスト 転送経路の計算依頼を行レ、、 マルチキャスト転送経路計算装置が、
計算依頼として取得した計測結果に基づいて、 始点と複数の終点を結ぶ遅延に 関する最短経路を計算し、 同時に、 最短経路上の任意のノードから各終点までの 遅延を計算し、 計算した値を記憶媒体に記録し、
計算された最短経路上をデータが流れるときの最大遅延を計算し、
最大遅延を予め与えられた遅延条件と比較し、 もし該遅延条件に合わない場合 には、 該遅延条件を再設定し、 最短経路に合致する条件が見つかった場合には、 計算された該最短経路にぉ ヽて、 始点と終点と経路の分岐点との 3種類の異なる 種類のいずれか 2つのノード、 もしくは同種の 2つのノードを端点とし、 かつ途 中に、 該 3種類のノードを含まない任意の部分経路群から両端の 2つのノード間 のコストが最も大きい経路を検索し、 検索された該経路を該最短経路から削除し て、 マルチキャスト転送経路を 2つの経路木に分割し、 別に計算された経路を該 2つの経路木を結ぶために削除対象となった経路の補完経路として設定し、 計算した計算結果をマルチキャスト転送経路設定装置に通知し、
マルチキャスト転送経路設定装置が、
受け付けた計算結果に従い、 マルチキャスト転送経路を設定する。
本発明の別の態様によるマルチキャストネットワークにおけるマノレチキャスト 転送経路計算装置は、
マルチキャストネットワークにおけるトラヒック状態の計測結果を受信する計 測結果受信手段と、
受信した計測結果を記憶する計測情報記憶手段と、
計測結果を計測情報記憶手段に格納する計測結果格納手段と、
計測結果を計測情報記憶手段から読み取り、 該計測結果に基づいて経路計算を 行う経路計算手段と、 を有し、
経路計算手段は、
始点と複数の終点を結ぶ遅延に関する最短経路を計算し、 同時に、 経路上の任 意のノードから各終点までの遅延を計算し、 計算した値を記憶媒体に記録する最 短経路遅延計算手段と、
計算された最短経路上をデータが流れるときの最大遅延を計算する最大遅延計 算手段と、
最大遅延を予め与えられた遅延条件と比較し、該遅延条件に合わない場合には、 該遅延条件を再設定し、 該最短経路に合致する条件が見つかった場合には、 最短 経路計算手段で計算された該最短経路にぉレヽて、 始点と終点と経路の分岐点との 3種類の異なる種類のいずれか 2つのノード、 もしくは同種の 2つのノードを端 点とし、 かつ途中に、 該 3種類のノードを含まなレヽ任意の部分経路群から両端の 2つのノード間のコストが最も大きい経路を検索する最大コスト経路検索手段と、 検索された経路を該最短経路から削除して、 マルチキャスト転送経路を 2つの 経路木に分割する経路木分割手段と、
別に計算された経路を該 2つの経路木を結ぶために削除対象となった経路の補 完経路として設定する補完経路計算手段と、 を有する。
本発明のさらに別の態様によるマルチキヤスト転送経路計算プログラムは、 受 信したマルチキャストネットワーク内のリンク上で発生するトラヒックの計測結 果に基づいてマルチキャスト転送経路を計算するコンピュータに実行させるマル チキャスト転送経路計算プログラムであって、
始点と複数の終点を結ぶ遅延に関する最短経路を計算し、 同時に、 経路上の任 意のノードから各終点までの遅延を計算し、 計算した値を記憶媒体に記録する最 短経路延計算ステップと、
計算された最短経路上をデータが流れるときの最大遅延を計算する最大遅延計 算ステップと、
最大遅延を予め与えられた遅延条件と比較し、該遅延条件に合わなレヽ場合には、 該遅延条件を再設定し、 該最短経路に合致する条件が見つかった ¾ ^には、 最短 経路計算手段で計算された該最短経路にぉレヽて、 始点と終点と経路の分岐点との 3種類の異なる種類の 、ずれか 2つのノード、 もしくは同種の 2つのノードを端 点とし、 かつ途中に、 該 3種類のノードを含まない任意の部分経路群から両端の 2つのノード間のコストが最も大きい経路を検索し、 検索された該経路を該最短 経路から削除して、 マルチキャスト転送経路を 2つの経路木に分割し、 別に計算 された経路を該 2つの経路木を結ぶために削除対象となった経路の補完経路とし て設定する補完経路計算ステップと力らなる。 上記のように、 本発明では、 補完経路の終点を削除対象の経路の終点に固定す ることで、 最短経路の部分木のうち削除対象の経路の終点を根とする部分木の形 状を変更することなく、 マルチキャスト転送経路を作成することが可能である。 さらに、 本発明では、 補完経路を木全体のコスト削減に有効である選択基準に 従い選択することで、 従来広く用いられている始点と終点間の最短経路を転送経 路に採用していたマルチキャスト転送経路計算装置に比べて、 経路のコスト削減 に有効である。 また、 本発明では、 既存のネットワーク内のトラヒック状態を示 すネットワーク計測情報の収集機能を利用するだけで、 容易に転送経路の計算を することが可能となる。 そして、 ネットワーク計測情報をマルチキャスト転送経 路計算装置が取得することは容易であり、 転送経路計算のために必要なネットヮ ーク計測情報を収集するために新たなプロトコルの開発を必要としないという利
^；がある。
本発明のさらに別の態様によるマルチキャストラベルスイッチング方法は、 マ ルチキャスト通信ネットワークにおいて、 マルチキャストソースノードからマル チキャストリーフのグループノードにマルチキャスト配信用のラベルスィッチン グ経路を設定するマルチキャストラベルスィツチング方法において、
ソースノードから全てのリーフノードにポイント ·ツー.マルチポイント の最 上位階層のラベルスィツチ経路を設定し、
設定されたボイント .ツー.マルチボイント のラベルスィツチング経路のリ一 フノードグループより任意の宛先リーフノードを抽出した複数のサブグループに 対して、 該サブグループ毎に第二階層のラベルで第一階層のラベルスィツチング 経路の部分ッリ一を構成する複数の第二階層のラベルスィツチング経路を設定し、 階層化された第一階層のラベルスィツチング経路と第二のラベルスィツチング 経路を用いて、 ラベルスィツチングするときに入力側のラベルエッジルータが第 二階層のラベルに対応した宛先リーフグループ宛の宛先ァドレスを持つトラヒッ クを対応する階層化ラベルに割り当て、 付与し、
中継ラベルスィッチルータは、 第一階層、 第二階層のラベルペアに応じて、 パ ケットをラベ/レスィツチし、
中継ノ一ドが、 ポイント 'ツー ·マルチポィント ラベルスィツチング経路の分 岐ノードとして指定される場合には、 入力ラベルペアを複数の出力分岐に対応す る出力ラベルに置き換え、 出力分岐毎にコピーし、
出力ラベルエッジルータは、 入力された階層化ラベルバケツトを階層ラベルの グループを判定しながら、 ラベル除去しながら出力ラインにスィツチングし、 ポイント 'ツー ·マノレチポィント の L S P内に、 第一階層のリーフグループノ 一ドのうち、 異なる宛先サブグループを構成する複数の第二階層の第一階層の部 分ッリ一を構成する第二階層のボイント 'ツー'マルチボイント の L S Pを用い て、 第一階層のラベルスイッチング経路を共有しながら、 第二階層のサブグルー プ毎にトラヒックをラベルスイッチングする。
上記のように、 本発明は、 マルチキャストラベルスィツチング経路を設定する ときに、 階層化ラベルを用いて、 第一階層ラベルで共有マルチキャストラベルス イッチング経路を設定し、 下位階層でサブグループ宛の部分マルチキャストラべ ルスイッチング経路を複数設定する点、 さらに、 中継ノードが階層化ラベルを判 定して、 階層化ラベル全体でラベルスイッチングする点を特徴とする。 従来の技 術では、 マルチキャスト転送時には、 階層化ラベルの技術が具備されても、 同一 トポロジですベてのリーフにマルチキャスト転送されてしまう点、 階層化ラベル があった場合には、 第一階層のみラベルスイッチング情報として利用され、 第二 階層以下のラベルは分岐ポィントでラベル値を変更することなしに、 コピーされ てしまう点において大きく異なる。
また、 本発明は、 V P Nマルチキャストに関しては、 第一階層ラベルを RFC2 547bisアーキテクチャと同様に P Eルータ間を接続するための共有ポィント ·ッ 一 .マルチポィントのラベルスィツチパスのラベルスィツチ用に利用する点、 第 二階層のラベルを P Eルータが収容する V P Nサイト用のラベルスィツチに利用 する点、 第三階層を V P Nサイト内のトラヒッククラスを区別するためのラベル スィッチに利用する点を主要な特徴とする。 従来の技術とは、 共有マルチキャス トラベルスイッチングパスを用いることでプロバイダネットワーク内に効率的に マルチキャスト配信経路を設定している点、 さらに設定マルチキャスト配信経路 により V P Nサイト内のトラヒック条件に合わせて最適な配信経路でマルチキヤ スト転送が可能なため、 プロバイダネットワーク内に不要なマルチキャストコピ 一トラヒックを発生することなく効率的なネットワーク運用が可能な点が異なる。 このように、 本発明では、 個々のマルチキャストトラヒックの宛先グループ、 Q o S要求条件に応じて最適な共有マルチキャスト通信経路を設定することが可 能となる。 さらに、 ネットワーク全体で帯域を有効活用できるので高性能なマル チキャスト配信ネットワーク、 VP Nネットワークを構築することが可能となる。 本発明のその他の目的、 特徴、 長所は、 図面を参照して以下の詳細な説明を読 めば明らかとなるであろう。 図面の簡単な説明
F I G. 1は、 本発明の原理を説明するための図である。
F IG. 2は、 本発明の原理構成図である。
F I G.3は、本発明の一実施の形態における概要を説明するための図である。 F I G. 4は、 本発明の一実施の形態におけるマルチキャスト転送経路計算装 置の構成図である。
F I G. 5は、 本発明の一実施の形態におけるマルチキャスト転送経路設定装 置の構成図である。
F I G. 6は、 本発明の一実施の形態における転送経路計算アルゴリズムのフ ローチャートである。
F I G. 7は、 本発明の一実施例の対象ネットワークの一例である。
F I G. 8は、 本発明の一実施例のデータ転送の始点と各終点を結ぶ経路のう ち遅延最小経路を示す図である。
F IG. 9は、 本発明の一実施例の削除対象経路計算を示す図である。
F IG. 10は、 本発明の一実施例のコスト最大経路削除後に作成される部分 経路を示す図である。
F IG. 11は、 本発明の一実施例の補完経路計算用トポロジである。
F IG. 12は、 本発明の一実施例の補完経路計算結果を示す図である。
F I G. 13は、 本発明の一実施例の経路計算結果を示す図である。
F I G. 14は、本発明の第 1の実施の形態における接続 VP Nサイト （CE) を考慮した最適 P Eルータ間マルチキャスト配信パターンである。 F IG. 15は、本発明の第 1の実施の形態における接続 VPNサイト （CE) を考慮した最適 PEルータ間マルチキャストシグナリングである。
F IG. 16は、本発明の第 1の実施の形態における接続 VP Nサイト （CE) を考慮した最適 P Eルータ間マルチキャスト配信接続を実現する階層化ッリ一指 定シンダナリングである。
F IG. 17は、 本発明の第 1の実施の形態におけるマルチキャスト配信経路 の例である。
F IG. 18は、 本発明の第 1の実施の形態における V P N # Aのサブッリ一 である。
F IG. 19は、 本発明の第 1の実施の形態における最適 P Eルータ間マルチ キャスト配信接続を実現する階層化ッリ一指定シグナリングで指定される MP L Sラベル交換テーブルである。
F IG. 20は、 本発明の第 1の実施の形態におけるサイト内のマルチキャス トソースの配信パターンを考慮した最適マルチキャスト配信経路設定法を示す図 である。
F IG. 21は、 本発明の第 1の実施の形態における P E間のマルチキャスト 配信経路交換メカニズムを説明するための図である。
F IG. 22は、 本発明を適用した V P Nモデルである。
F IG. 23は、 従来の技術における VPNモデル （Rosen) である。
F IG. 24は、 従来の PEルータ間のマルチキャストコネクションと VPN サイト内 CEへのマルチキャスト転送パターンである。 発明を実施するための最良の形態
F I G. 1は、 本発明の原理を説明するための図である。
本発明は、 マルチキャスト転送装置がそれぞれ設けられた複数のノードにより 構成されるマルチキャストネットワークにおいて、 与えられた始点と複数の終点 とをそれぞれ結ぶマルチキャスト転送経路をマルチキャスト転送経路計算装置に より計算し、 計算されたマルチキャスト転送経路をマルチキャスト経路設定装置 が設定するマルチキャスト転送経路設定方法である。 F IG. 1を参照して、 各 ステップについて説明する。
マルチキャスト転送装置は、 マルチキャストネットワーク内のリンク毎に、 力、 っ該リンクにデータが流れる際の進行方向毎にトラヒックの状態を計測する （ス テツプ 1 )。そして、計測結果をマルチキャスト転送経路計算装置に送信すること により、 マルチキャスト転送経路計算装置にマルチキャスト転送経路の計算依頼 を行う （ステップ 2 )。
マルチキャスト転送経路計算装置は、 マルチキャスト転送装置から計算依頼と して取得した計測結果に基づレ、て、始点と複数の終点を結ぶ最短経路を計算し（ス テツプ 3 )、最短経路上の任意のノードカゝら各終点までの遅延を計算し（ステップ 4 )、 計算した値を記憶媒体に記録する （ステップ 5 )。 マルチキャスト転送経路 計算装置は、 その後、 計算された最短経路上をデータが流れるときの最大遅延を 計算し（ステップ 6 )、計算した最大遅延を予め与えられた遅延条件と比較する（ス テツプ 7)。 もし予め与えられた遅延条件に合わない場合には、該遅延条件を再設 定する。 もし最短経路に合致する条件が見つかった場合には、 計算された最短経 路において、 始点と終点と経路の分岐点との 3種類の異なる種類のいずれか 2つ のノード、 もしくは同種の 2つのノードを端点とし、 かつ途中に、 該 3種類のノ 一ドを含まない任意の部分経路群から両端の 2つのノード間のコストが最も大き い経路を検索し （ステップ 8 )、検索された該経路を該最短経路から削除して （ス テツプ 9 )、マルチキャスト転送経路を 2つの経路木に分割する（ステップ 1 0 )。 そして別に計算された経路を該 2つの経路木を結ぶために削除対象となった経路 の補完経路として設定し（ステップ 1 1 )、計算結果をマルチキャスト転送経路設 定装置に通知する （ステップ 1 2 )。
マルチキャスト転送経路設定装置は、 受け付けた計算結果に従い、 マルチキヤ スト転送経路を設定する （ステップ 1 3 )。
F I G. 2は、 本発明の原理構成図である。 本発明に係る、 マルチキャストネ ットワークにおけるマルチキャスト転送経路計算装置は、 以下の手段を有する： マルチキャストネットワークにおけるトラヒック状態の計測結果を受信する計測 結果受信手段 1 3 0、 受信した計測結果を記憶する計測情報記憶手段 1 1 2、 計 測結果を計測情報記憶手段 1 1 2に格納する計測結果格納手段 1 1 1、 計測結果 を計測情報記憶手段 1 1 2力 ら読み取り、 該計測結果に基づいて経路計算を行う 経路計算手段 1 2 0ο
経路計算手段 1 2 0は、 さらに以下の手段を有する：始点と複数の終点を結ぶ 最短経路を計算し、 同時に、 経路上の任意のノードから各終点までの遅延を計算 し、 計算した値を記憶媒体 1 2 2に記録する最短経路遅延計算手段 1 2 1 1、 計 算された最短経路上をデータが流れるときの最大遅延を計算する最大遅延計算手 段 1 2 1 2、 最大遅延を予め与えられた遅延条件と比較し、 該遅延条件に合わな い^には、 該遅延条件を再設定し、 該最短経路に合致する条件が見つかった場 合には、 最短経路計算手段 1 2 1 1で計算された該最短経路において、 始点と終 点と経路の分岐点との 3種類の異なる種類のいずれか 2つのノード、 もしくは同 種の 2つのノードを端点とし、 かつ途中に、 該 3種類のノードを含まない任意の 部分経路群から両端の 2つのノード間のコストが最も大きい経路を検索する最大 コスト経路検索手段 1 2 1 3、 検索された経路を該最短経路から削除して、 マル チキャスト転送経路を 2つの経路木に分割する経路木分割手段 1 2 1 4、 及ぴ別 に計算された経路を該 2つの経路木を結ぶために削除対象となった経路の補完経 路として設定する補完経路計算手段 1 2 1 5。
以下、 図面と共に本発明の実施の形態を説明する。
F I G. 3は、本発明の一実施の形態における概要を説明するための図である。 なお、 同図中の 0 内の番号と以下の説明の番号は対応するものとする。
本発明は、 始点から終点まで転送される際に被る遅延値に上限値が存在する場 合のマルチキャストネットワーク内のマルチキャスト転送経路設定方法である。 そして、 当該マルチキャストネットワークは、 マルチキャスト転送装置 3 0 0が 設けられた複数のノードにより構成されており、 また、 各ノードのいずれかのノ 一ドにマルチキャスト転送経路計算装置 1 0 0または、 マルチキャスト転送経路 設定装置 2 0 0が設けられている。
そして、 ネットワーク内のマルチキャスト転送装置 3 0 0力 各リンクで発生 するデータ転送遅延などを示すネットワーク計測情報をデータが流れる方向毎に 収集し （1 )、 そして、 マルチキャスト転送装置 3 0 0がマルチキャスト転送経路 計算装置 1 0 0やマルチキャスト転送経路設定装置 2 0 0にネットワーク計測情 報を通知する （2 )。そして、マルチキャストにより転送するデータの転送経路の 設定の必然性が生じたときに、 マルチキャスト転送経路設定装置 2 0 0とマルチ キャスト転送経路計算装置 1 0 0によって後述する処理に従い、 データの 経 路の設定が実行される。
本発明においては、 マルチキャスト転送装置 3 0 0は、 ノード間で転送される データのネットワーク計測情報を収集する機能を有し、 マルチキャスト転送経路 計算装置 1 0 0は、 転送経路を計算する機能を有し、 マルチキャスト転送経路設 定装置 2 0 0は、 転送経路を設定する機能を有する。 また、 1つのノードが複数 の上述した装置の機能を有している場合もある。
ここで、 マルチキャスト転送経路設定装置 2 0 0とマルチキャスト転送経路計 算装置 1 0 0が異なる装置である場合には、 マルチキャスト転送経路設定装置 2 0 0がマルチキャスト転送経路計算装置 1 0 0への転送経路計算を依頼する（3 )。 マルチキャスト転送経路計算装置 1 0 0は、 自身の経路計算モジュールに経路計 算を指示する （4 )。 また、マルチキャスト転送経路設定装置2 0 0とマルチキヤ スト転送経路計算装置 1 0 0が同一装置である場合、 マルチキャスト転送経路設 定装置 2 0 0が自身の経路計算モジュールに経路計算を指示する （4 )。 そして、 マルチキャスト転送経路設定装置 2 0 0もしくは、 マルチキャスト転送経路計算 装置 1 0 0の経路計算モジュールが、 収集した情報をもとに転送経路を計算する ( 5 )。そして計算結果は、マルチキャスト転送経路設定装置 2 0 0の経路設定モ ジュールに通知され（6 )、当該計算結果を受信したマルチキャスト転送経路設定 装置 2 0 0がデータのマルチキャスト転送経路を設定する。 なお、 上述のネット ワーク計測情報を収集する機能にぉレ、ては、 すでに提案されてレ、る O S P F— T E (Open Shortest Path First-Traffic Engineering) や、 I S— I S— T E (I ntermediate System-Intermediate System-Traffic Engineering) などの隣接 ノード間でのネットワーク計測情報を交換する機能が備わった経路計算プロトコ ルを拡張して用いることにより、 ネットワーク計測情報を収集する。
また、 マルチキャスト転送経路計算装置 1 0 0は、 マルチキャスト^ ¾装置 3 0 0からネットワーク計測情報を受信する機能と、 力つ転送経路の計算結果を送 信するバケツト転送機能と、 経路計算に使用するアルゴリズムを実現するプログ ラム、 ネットワーク計測情報や経路計算プログラムや経路計算結果を保存する記 憶媒体と、 並びに、 経路計算を実行する経路計算機能とにより構成される。 また、 本発明で使用する経路計算プログラムは、 転送経路の始点から各終点ま での最短経路を計算する機能と、 最短経路の経路を行う手順の中で計算される経 路上の点から各終点までの最短遅延を計算する機能と、 最短経路を構成する経路 のうち、始点、終点、経路の分岐点のいずれかを端点とし、経路の中間点に始点、 終点、 経路の分岐点を含まない一続きの経路から最大のコストを有する経路を検 索する機能と、 検索結果となる経路を削除し、 削除された経路を補完する経路と して、 経路の終点が削除された経路の終点であり、 経路の始点が、 削除された経 路の始点を含む最短経路の部分木を構成する任意のノードのうち最もコストの小 さいものを選択する機能を有する。
上記の機能により、 本発明では、 補完経路の終点を削除対象の経路の終点に固 定することで、 最短経路の部分木のうち削除対象の経路の終点を根とする部分木 の形状を変更することなく、 マルチキャスト転送経路を作成することが可能であ る。
さらに、 本発明では、 補完経路を木全体のコスト削減に有効である選択基準に 従い選択することで、 従来広く用いられている始点と終点間の最短経路を転送経 路に採用していたマルチキャスト転送経路計算装置に比べて、 経路のコスト削減 に有効である。 また、 本発明では、 既存のネットワーク内のトラヒック状態を示 すネットワーク計測情報の収集機能を利用するだけで、 容易に転送経路の計算を することが可能となる。 そして、 ネットワーク計測情報をマルチキャスト転送経 路計算装置 1 0 0が取得することは容易であり、 転送経路計算のために必要なネ ットワーク計測情報を収集するために新たなプロトコルの開発を必要としないと いう利点がある。
次に、 本発明のマルチキャスト転送経路設定方式を実現するために必要なマル チキャスト転送経路計算装置 1 0 0とマルチキャスト転送経路設定装置 2 0 0に ついて説明する。
F I G. 4は、 本努明の一実施の形態におけるマルチキャスト転送経路計算装 置 1 0 0の構成を示す。 同図に示すマルチキャスト転送経路計算装置 1 0 0は、 ネットワーク内のノードや各ノードをつなぐリンクで発生する遅延ゃコストに関 するネットワーク計測情報を管理する情報管理部 1 1 0と、 転送経路を計算する 経路計算部 1 2 0と、 送受信するパケットを処理するパケット処理部 1 3 0より 構成される。 そして、 マルチキャスト転送経路計算装置 1 0 0のパケット処理部 1 3 0力 情報管理部 1 1 0で管理されるネットワーク計測情報や経路計算依頼 の受信や、 経路計算部 1 2 0が計算した転送経路の計算結果のマルチキャスト転 送経路設定装置 2 0 0への送信を行う。
, 情報管理部 1 1 0は、 プロトコルを処理するルーティングプロトコルモジユー ル 1 1 1と、 そのプロトコルによって得られたネットワークのトポロジゃ遅延、 コストなどのネットワーク計測情報を管理する計測情報記憶部 1 1 2とを備えて いる。
また、経路計算部 1 2 0は、転送経路を計算する経路計算モジュール 1 2 1と、 計算結果を記憶する計算結果記憶部 1 2 2とを備えている。
また、 バケツト処理部 1 3 0は、 到着したバケツトの種別を判断し、 そのパケ ットを転送、 または情報管理部 1 1 0に送るバケツト処理モジュール 1 3 1とパ ケット転送先を記録するバケツト転送テーブル記憶部 1 3 2と、 一または複数の ネットワークインタフェース 1 3 3とを備えている。
F I G. 5は、 本発明の一実施の形態におけるマルチキャスト転送経路設定装 置の構成を示す。
同図において、 マルチキャスト転送経路設定装置 2 0 0は、 ネットワーク内の ノードゃリンクで発生する遅延ゃコストに関する情報を管理する情報管理部 2 1 0と、 自身の処理により発生する遅延ゃコストなどを測定する測定部 2 2 0と、 新たなデータフ口一が発生したときに経路設定を行う経路設定用プロトコル処理 部 2 3 0と、 到着したバケツトを処理するパケット処理部 2 4 0により構成され る。
そして、 情報管理部 2 1 0の基本構成は、 マルチキャスト転送経路計算装置 1 0 0の情報管理部 1 1 0と同様であり、 ルーチングプロトコルモジュール 2 1 1 と、 計測情報記憶部 2 1 2を備えている。
また、 測定部 2 2 0は、 パケット処理部 2 4 0が備えるネットワークインタフ エース 2 4 3 (後述する） の状態や、 ネットワーク上の各ノードの処理の遅延な どの情報を測定する測定モジュールを備えている。
パケット処理部 2 4 0は、 到着したパケットの種別を判断し、 パケットの転送 を行い、 また、 新規の経路設定の決定を判断するバケツト処理モジュール 2 4 1 と、 パケットの転送先を記録するパケット転送テーブル記憶部 2 4 2と、 ネット ワークインタフェース 2 4 3を備えている。
また、 マルチキャスト転送経路設定装置 2 0 0は、 経路計算部 2 5 0を備えて おり、 経路計算部 2 5 0は、 転送経路を計算する計算処理モジュール 2 5 1と、 計算結果を記憶する計算結果記憶部 2 5 2とを備えている。 なお、 転送経路の計 算をマルチキヤスト転送経路設定装置 2 0 0が行う場合には、 この経路計算部 2 5 0がマルチキャスト転送経路計算装置 1 0 0と同様の処理を行う。
経路設定用プロトコル処理部 2 3 0は、 パケット処理部 2 4 0から経路設定依 頼を受信し、 その経路設定依頼のマルチキャスト転送経路計算装置 1 0 0への送 信処理を行う。 また、 経路設定用プロトコル処理部 2 3 0は、 マルチキャスト転 送経路計算装置 1 0 0から受信した転送経路の計算結果に従ってデータ転送のた めの転送経路を設定する機能を有する。
なお、 マルチキャスト転送経路計算装置 1 0 0とマルチキャスト転送経路設定 装置 2 0 0が同一ノードである場合には、 そのノードは、 マルチキャスト転送経 路計算装置 1 0 0とマルチキャスト転送経路設定装置 2 0 0の各処理部を有し、 上述の各処理を行う。 また、 マルチキャスト転送装置 3 0 0の機能が同一のノー ドに備えられる場合には、 経路設定用プロトコル処理部 2 3 0は、 隣接するノー ドに対して経路計算依頼を行う。
次に、 上記のマルチキャスト転送経路計算装置 1 0 0、 マルチキャスト転送経 路設定装置 2 0 0、 マルチキャスト転送装置 3 0 0の動作を説明する。
ネットワーク内のマルチキャスト転送装置 3 0 0の機能を有するノードは、 常 にネットワークのトポロジゃ遅延ゃコストを表すネットワーク計測情報を隣接ノ ード間で交換する。 そして、 各ノードは、 その交換処理によって得られたネット ワーク計測情報を記憶する。
ノードが交換するネットワーク計測情報は、 次ノードで計測したネットワーク 計測情報のみならず、 自ノードが保持する他ノ一ドが計測したネットワーク計測 情報も含む。 これらの交換動作により、 各ノードは、 ネットワーク内の全ノード における接続情報や遅延などのネットワーク計測情報を保持する。 そして、 新た に転送経路を設定するマルチキャスト転送経路設定装置 2 0 0の機能を有するノ ードは、 マルチキャスト転送経路計算装置 1 0 0の機能を有するノードに経路計 算依頼をする。 このとき、 マルチキャスト転送経路計算装置 1 0 0の機能を有す るノードは、 情報管理部 1 1 0で管理されているネットワーク内のトポロジゃ遅 延などトラヒックに関するネットワーク計測情報と、 経路計算依頼をしたノード から送られてきた終点の情報に基づレヽて転送経路を計算する。
F I G. 6は、 本発明の一実施の形態における転送経路計算アルゴリズムのフ ローチャートである。
まず、 マルチキャスト転送経路設定装置 2 0 0の機能を有するノードからの経 路計算依頼をマルチキャスト転送経路計算装置 1 0 0が受け付ける。 このとき、 マルチキャスト転送経路計算装置 1 0 0は、 マルチキャスト転送経路設定装置 2 0 0からデータ転送の終点の情報も受け付ける。 すると、 マルチキャスト転送経 路計算装置 1 0 0の経路計算部 1 2 0が情報管理部 1 1 0の計測情報記憶部 1 1 2 (データベース） に記録されているネットワークのトポロジゃトラヒック状態 を示すネットワーク計測情報を読み取る （ステップ 1 0 1 )。
そして、 経路計算モジュール 1 2 1がネットワーク計測情報を用いて、 データ 転送の始点と終点までの遅延が最も小さい遅延最小経路を計算する （ステップ 1 0 2 )。 このとき、経路計算モジュール 1 2 1は、経路計算依頼を送信したノード を始点とし、 データ転送の終点のノードまでの遅延最小経路を計算する。 なお、 遅延最小経路の計算には、 ダイクストラのアルゴリズムを用いる。 これより、 経 路計算依頼を発行したノードと各終点までの遅延最小経路が算出される。
次に、マルチキャスト転送経路計算装置 1 0 0の経路計算モジュール 1 2 1は、 ステップ 1 0 2で求めた始点から終点までの遅延最小経路を構成するノードのう ち、 始点と、 各終点と、 経路の分岐点と、 のいずれかに挟まれ、 かつ途中に前述 の 3種類のノ一ドを含まなレ、部分経路を検索する （ステップ 1 0 3 )。
そして、 計算された部分経路のうち、 部分経路を構成するリンクのコストが最 も大きい経路を選択し、 これを前述の遅延最小経路から削除する。 このとき、 削 除対象となる経路の終点の情報を計算結果記憶部 1 2 2に記録する （ステップ 1 0 4 )。 このとき、前述の遅延最小経路は 2つの部分経路に分割される。 次に、 マ ルチキャスト転送経路計算装置 1 0 0の経路計算モジュール 1 2 1は、 擬似的な 始点と、 擬似的な始点から前述の分割された部分経路のうち、 遅延最小経路の始 点を含む部分経路に含まれるすべてのノードへとつながるリンクと、 を情報管理 部 1 1 0の計測情報記憶部 1 1 2に記録されているネットワークのトポロジに追 加する。 この後、 前述の分割された部分経路のうち、 始点を含まない部分経路が 通過するリンクとノード、 並びに当該ノ一ドに接続されるすべてのリンクを前述 のトポロジから削除する。 伹し、 削除対象となる前述の部分経路の始点となるノ ード、 並びに、 当該ノードと部分経路を構成しないノードを結ぶリンクは、 ネッ トワークトポロジからの削除対象としないものとする （ステップ 1 0 5 )。
次に、 擬似的な始点と遅延最小経路の始点を含まなレ、部分経路の始点を結ぶ経 路を検索する。 このとき、経路の検索のために、 k-th shortest path algorithm と呼ばれる、 最小遅延を実現する経路から数えて k番目に小さい遅延を実現する 経路を計算するアルゴリズムを適用する。 この種類のアルゴリズムは、 k一 1番 目に小さい経路を検索した後、 k番目に小さい経路の検索を行う。 よって、 許容 する遅延の上限値を設け、 上限値を下回る経路が全て発見されるまで該当アルゴ リズムを実行することが可能となる。 このようにして検索された経路は削除され た経路を補完する経路の候補となる （ステップ 1 0 6 )。
次に、マルチキャスト転送経路計算装置 1 0 0の経路計算モジュール 1 2 1は、 k-th shortest path algorithmによって検索された経路のうち、 経路を構成する リンクが保持するコストの経路全体の総和を計算し、 最もコストが小さい経路を 選択する。 選択された経路は削除された経路を補完するために新たに経路として 選択される （ステップ 1 0 7 )。
最後に、 マルチキャスト転送経路計算装置 1 0 0の経路計算モジュール 1 2 1 は、 上記のステップ 1 0 3からステップ 1 0 7までの動作を削除対象の経路と選 択された補完経路が同一経路となるか判断する。 同一経路となる場合、 次にコス トの大きい経路を探索し、 すべての探索経路において、 補完経路が探索経路と同 一経路となるまで繰り返す （ステップ 1 0 8 )。
このようにして計算した結果を、 経路計算モジュール 1 2 1は、 バケツト処理 部 1 3 0を介して経路計算依頼を発行したノ一ドに返送する （ステップ 1 0 9 )。 なお、 本実施の形態では、 マルチキャスト転送装置 3 0 0が遅延などのネット ワーク計測情報を収集する際には、 O S P F— T Eを用いる。 O S P F— T Eは、 ュニキャストのルーチングプロトコルである O S P Fのトポロジ情報交換情報に 遅延などのネットワーク内のトラヒック情報を格納した通信プロトコルである。 また、 本実施の形態では、 データの転送を設定するプロトコルとして、 明示的 な経路指定を実施する R S V P— T E (Resource Reservation Protocol-Traffic Engineering) を拡張したマルチキャスト MP L S (Multi Protocol Label Swit ching) プロトコルを使用する。マルチキャスト MP L Sは、通常の MP L Sで用 いられる R S V P— T Eに対して、 L S P (Label Switched Path) を生成する メッセージ中にツリートポロジを格納できる情報要素を追加し、 そのトポロジ情 報に沿って、 Point-to-Multipoint L S Pを確立することができる技術である。 以下、 図面と共に本発明の実施例を説明する。
F I G. 7は、 本発明の一実施例のマルチキャストネットワークを示す。
同図において、 2 0 0はデータ転送経路の始点を示し、 ①〜③はデータ転送の 終点を示す。 また、 A〜Iは始点と終点との間の中間ノードであり、 マルチキヤ スト転送装置 3 0 0の機能を有している。 なお、 マルチキャスト転送経路設定装 置 2 0 0、 ノード A〜I、 終点①〜③の各ノードが通信ケープノレ （リンク） によ り接続されてマルチキャストネットワークを構成している。そして、各リンクは、 遅延とコストとレヽぅ 2つの特性を持っている。リンクの遅延特性とコスト特性は、 データがリンクに進入する際の進入方向によって、 異なる遅延特性とコスト特性 を有することが認められている。 この場合、 リンク D— Eのようにデータが右方 向 （Dから Eへ） に移動するときは、 遅延特性が 1でコスト特性が 1 0であり、 逆方向 （Eから Dへ） に移動するときは遅延特性が 1でコスト特性が 1となるリ ンクが存在する。 そして、 マルチキャスト転送経路設定装置 2 0 0は、 マルチキ ヤスト転送経路計算装置 1 0 0が計算した結果に基づいて、 自らを始点として終 点①〜終点③に対してデータを転送する。 なお、 各ノード間のリンクで発生する遅延を示すネットワーク計測情報は、 前 述の O S P F— T Eを用いて各ノードが収集する。 そして、 当該ネットワーク計 測情報が予めマルチキャスト転送経路計算装置 1 0 0に通知される。
マルチキャスト転送経路設定装置 2 0 0が遅延の上限値が 7である経路を計算 する例を示す。
F I G. 8は、 本発明の一実施例のデータ転送の始点と各終点を結ぶ経路のう ち遅延最小経路を示す。
マルチキャスト転送経路計算装置 1 0 0は、 マルチキャスト転送経路設定装置 2 0 0からの経路計算依頼を受けると、 まず、 始点となるマルチキャスト転送経 路設定装置 2 0 0から各終点①〜終点③までの遅延最小経路を計算する。この時、 マルチキャスト転送経路計算装置 1 0 0は、 遅延最小経路の計算アルゴリズムと してダイクストラのアルゴリズムを用いる。 ダイクストラのアルゴリズムは、 遅 延最小経路を計算するアルゴリズムとしては一般的によく使用される。 なお、 マ ルチキャスト転送経路計算装置 1 0 0が計算した始点 2 0 0から終点①、 ②、 ③ までの各遅延最小経路は、
•マルチキャスト転送経路設定装置 2 0 0→ノード B→終点①、
•マルチキャスト転送経路設定装置 2 0 0→ノード B→ノード D→ノード Ε ノ 一 G→終点②、
■マルチキャスト転送経路設定装置 2 0 0→ノード B→ノード D→ノード Ε ノ — G→ノード H→終点③
である。 このとき、 始点→終点間で被る遅延の最大値は始点 2 0 0と終点③を結 ぶ経路上で被る遅延であり、 その値は 6であるため、 遅延上限値に関する条件を 満たす。
F I G. 9は、 本発明の一実施例の削除対象経路計算を示す図である。
次に、 遅延最小経路を分割した部分経路のうち、 両端が始点、 終点、 経路の分 岐点のいずれかのノードであり、 かつ、 経路の中間ノードに始点、 終点、 経路の 分岐点を含まない経路を検索する。 該当する経路は、
'始点2 0 0→ノード8 (部分経路 3 1 )
.ノー B→終点① （部分経路 3 2 ) 'ノード B→ノード D→ノード Ε—ノ一 KG (部分経路 3 3 )
•ノード G→終点② （部分経路 3 4 )
-ノ一ド G ノ一ド H→終点③ （部分経路 3 5 )
である。 このような経路のうち、 経路を構成するリンクが持つコスト特性の総和 が最も大きい経路を選択する。 始点 2 0 0→ノード B (部分経路 3 1 ) のコスト は 1、ノード B→終点①（部分経路 3 2 ) のコストは 1、ノード B→ノード G (部 分経路 3 3 ) のコストは 1 2、ノード G→終点②（部分経路 3 4 ) のコストは 1、 ノード G→終点③ （部分経路 3 5 ) のコストは 2であるため、 選択される経路は ノード B→ノード G (部分経路 3 3 ) となる。 F I G. 9は経路の検索結果を示 しており、 選択された部分経路を遅延最小経路として選択された経路から削除す る。 その結果、 遅延最小経路は 2つに分割される。 ここで、 始点を含む部分経路 を 4 0、 含まない経路を 5 0とする。 この様子を F I G. 1 0に示す。
次に、 2つの部分経路 4 0、 5 0を結ぶ補完経路を検索する。 このとき、 補完 経路は、 部分経路 4 0に含まれる任意の点を始点とし、 削除経路の終点、 すなわ ち部分経路 5 0の始点を終点とするような経路のうち、 部分経路 5 0に属する点 と途中で交わらず、 経路を構成するリンクが保持するコスト特性の総和が最も小 さいものを選択する。 この計算法を以下に示す。
計算に使用するネットワークのトポロジは、 計算対象のネットワークに以下の ような修正を加えたものを使用する。 まず、 擬似的な始点 7 0を用意し、 擬似的 な始点 7 0から部分経路 4 0に属するすべてのノードに対しリンクを ϋ¾口する。 次に、 部分経路 5 0を構成するリンクと部分経路 5 0の始点 Gを除いたノード、 並びに、 当該ノードに接続するすべてのリンクを除去する。 この結果、 F I G. 1 1に示すようなトポロジが完成する。
このトポロジに対し、 擬似始点 7 0と部分経路 5 0の始点 Gを結ぶ経路を、 k- th shortest path algorithmを用レ、て計算する。 k-th shortest path algorithm とは、 遅延最小経路から数えて k番目に短レヽ経路を探索するときに使用されるァ ルゴリズムであり、 このような経路を探索するアルゴリズムはすでに提案されて いる。 k-th shortest path algorithmの適用に際し、 計算に使用される特性値と しては遅延とコストが考えられる。 計算に使用する特性値が遅延である場合、 始点と各終点の間に被る遅延が与え られた上限値を下回る間 k-th shortest path algorithmを漸化的に適用する。即 ち、 k一 1番目に短い経路を計算した後、 計算結果を用いて k番目に短い経路を 検索する。 これらの経路のうち、 経路を構成するリンクが保持するコスト特性の 各リンクに対する総和が最も小さいものを補完経路として選択する。
計算に使用する特性値がコストである場合、 発見された k番目に小さいコスト を保持する経路を始点と各終点の間で被る遅延の上限値を初めて下回ったときに 計算を終了し、 その時点で計算された擬似始点を除く経路を補完経路として選択 する。 F I G. 1 2に本実施例における計算結果を示す。 擬似始点 7 0と部分経 路 5 0の始点であるノード Gを結ぶ経路のうち、 最もコストの小さい経路は、 擬似始点 7 0→ノード B→ノード D→ノー KF→ノード E→ノー KG であるため、 擬似始点 7 0を除いた、
ノード B→ノー KD→ノー KF→ノー KE→ノー KG を補完経路として選択する。
遅延の上限値の評価には、 部分経路 5 0の始点 Gで記録されているノード Gか らノード Gの下流に存在する各終点までに発生する遅延値を使用する。 従来の方 式では、 部分経路 5 0のトポロジが補完経路の計算の際に変化するため、 部分経 路 5 0の再計算の後、 新たな部分経路 5 0の始点から各終点までの遅延を計算す る必要があった。本発明では、この作業を省くことで、計算時間を短縮している。 遅延の最大値を評価した結果、 補完経路接続時に実現される始点→終点間の最大 遅延は始点 2 0 0と終点③を結ぶ経路上で被る遅延 7となる。 経路が許容する最 大遅延が 7という条件があるため、 この場合遅延条件を満たす。 上記の条件を満 たす経路を補完経路とし、 部分経路 4 0と部分経路 5 0を結ぶ経路として採用す る。
ここで、 アルゴリズムの終了条件について説明する。 補完経路が削除された経 路と同じ場合、 もしくは、 削除された経路より遅延が大きい経路である場合、 削 除された経路が補完経路となり、 アルゴリズムを終了する。 もし、 異なる場合、 補完経路に印を付け、 両端が始点、 終点、 経路の分岐点のいずれかのノードであ り、 つ、経路の中間ノードに始点、終点、経路の分岐点を含まない経路のうち、 印を付けた経路以外でコストが最も大きい経路を選択し、 削除の後、 補完経路を 見つける。 この動作をすベての経路に印が付けられるまで繰り返す。 このように して F I G. 1 3に示すような計算結果が算出される。
なお、 上述のマルチキャスト転送経路計算装置やマルチキャスト転送経路設定 装置は内部にコンピュータシステムを有している。 そして、 上述した処理の過程 は、プログラムの形式でコンピュータ読み取り可能な記憶媒体に記憶されており、 このプログラムをコンピュータが読み出して実行することによって、 上記の処理 が行われる。ここで、コンピュータ読み取り可能な記憶媒体とは、磁気ディスク、 光磁気ディスク、 C D— R OM、 D VD - R OM,半導体メモリ等を指す。また、 このコンピュータプログラムを通信回線によってコンピュータに配信し、 この配 信を受けたコンピュータが当該プログラムを実行するようにしてもよい。 また、 構築されたプログラムを、 マルチキャスト転送経路計算装置として動作するコン ピュータに接続されるハードディスクや、 フレキシブルディスク、 C D— R OM 等の可搬記憶媒体に格納しておき、 本発明を実施する際に、 C P Uにインスト一 ルすることも可能である。
上述のように、 本発明によれば、 始点と終点間で発生する遅延の上限値を考慮 した経路計算アルゴリズムを備えた経路計算用ノードを有するシステムを用いる ことで、 マルチキャスト通信において始点と各終点の間で発生する遅延に上限が 存在するようなアプリケーションを提供する際に、 遅延条件を満たしつつ経路全 体のコストの削減を実現することが可能となる。
また、 経路計算の時間を従来方式と比較して短縮することによって、 サービス を提供するために必要な時間を短縮することが可能となる。 これにより、 ユーザ に対し、 迅速にサービスを提供することが可能となる。
このようなマルチキャスト通信経路設定技術によるマルチキャスト配信 (転送） を実現する手段として、 マルチキャストラベルスィツチング方法を利用したネッ トワークがある。 以下、 図面と共にマルチキャストラベルスイッチング方法に関 する本発明の実施の形態を説明する。
最初に、 マルチキャストラベルスィツチングの通信経路設定方式とパケット転 送メカニズムについて説明する。 F IG. 14は、 本発明の一実施の形態における接続 VPNサイト （CE) を 考慮した最適プロバイダエッジ （PE) ルータ間マルチキャスト配信のパターン を示す。 同図の例では、 プロバイダネットワーク内に、 プロバイダエッジルータ PE#1, PE#2， PE#3， P E # 4と、 それらと P Eルータ間を接続する プロバイダ （p) ルータが存在する。
PE#1には、 VPN#Aに所属する CE#A1と、 VPN#Bに属する CE #B1と、 VPN#Cに属する CE#C 1とが収容されている。 さらに、 PE# 2には、 VPN#Aに属する CE#A2と、 V P N # Bに属する C E # B 2とが 収容される。 また、 PE#3には、 VPN#Aに属する CE#A3と、 VPN# Bに属する CE#B 3と、 VPN#Cに属する CE#C3とが収容される。また、 PE#4には、 VPN#Bに属する CE#B 4と、 V P N # Cに属する C E # C 4とが収容される。
このネットワークで PE# 1から他の PEルータに送信されるマルチキャスト トラヒックの最適な配信パターンを考察する。 プロパイダネットワークの見地か らは、 PEルータ間に複数のマルチキャストラベルスイッチングを設定すること は、 ラベルの有効利用、 転送リソースの観点から望ましくない。 そこで PE# 1 から、 PE#2， 3， 4にすベてのトラヒックで共有されるポイント 'ツー ·マ ルチポィントの L S P (Label Switched Path) を設定する。
この例では、 同図中の土管のマークで図示されたパスが LSPに対応する。 こ のとき、 各 PEルータに収容される VPNサイト情報を考慮すると、 PEルータ に収容される VP Nサイトに応じて VP N毎のサイト接続関係を考慮した PEル ータ間のマルチキャストラベルスィツチング経路が必要になる。例えば、 F I G. 14の例では、 VPN#Aについては、 PE#2， P E # 3配下のみサイトが収 容されるため、 PE# 1がソース、 PE#2， 3がリーフのマルチキャストサブ ラベルスィツチング経路が設定されることが望ましい。 F IG. 14の例では、 の矢印で示されるマルチキャスト配信経路がこのマルチキャストサブラベル スイッチング経路に対応する。 以下 VPN#Bについては、 一点鎖線の矢印 VP N#Cについては、 実線の矢印が対応する。
この例でもわかるように、 プロバイダネットワークのリソースを有効活用し、 004/001246
28 かつ収容される VPNサイトに応じた PEルータ間の最適マルチキャスト配信を 実現するためには、 2階層のポィント ·ツー'マルチポィントのラベルスィツチ ングパスの設定が有効である。 さらに、 第二階層目のラベルスイッチングパスは 第一階層のラベルスイツチングパスの部 合になっていることに注意されたい。
F I G. 14のマルチキャストラべノレスィツチングパスを設定するシダナリン グメカニズムを F I G. 15に示す。 マルチキャストラベルシグナリングは、 例 えば、 既存の R S V P— T E (Resource Reservation Protocol-Traffic Enginee ring) メカニズムをマルチキャスト拡張して設定される。 F IG. 15に示すよ うに設定するマルチキャスト配信回路は、 pathメッセージの TERO (Tree Ex plicit Route Object) により規定される。 その具体的なフォーマツトをネットヮ ークトポロジに対応させて F I G. 16に示す。
前述したように、 本発明では、 PEルータ間に最適なマルチキャスト配信経路 を設定するために 2階層のマルチキャストラベルスィツチングパスを設定する。 そのため設定するマルチキャストラベルスィツチングパスの設定経路を示す TE ROを 2階層分用意する。 F IG. 16の例では、 第一階層の PE# 1 (A) か ら PE#2 (D)， PE#3 (E)， PE#4 (G) に接続するマルチキャストラ ベルスイツング経路を規定する。 TEROは、 {A (0)， B (1)， C (2)， D (3)， E (3), F (2)， G (3)} で規定される。 この規定方法は、 Depth Fi rst Orderアルゴリズムにより規定される。各ノードに付随する 0内の数値は、 ソースノード PE#1 (A) 力 の距離 （ホップ数） を示す。
F IG. 15の例では、 F IG. 17に示すような接続構成のマルチキャスト 配信経路となっている。 Depth First Orderアルゴリズムでは初めに深さ方向に パスを指定していくので、 TEROの指定は、 {A (0)， B (1)， C (2), D (3)， E (3)， F (2)， G (3)} となっている。 さらに、 この第一階層のマ ルチキャスト LSPの配下に VPN毎のマルチキャスト LS Pを設定する。 VP N#Aのサブツリーは PE# 1 (A) より PE#2 (D)、 PE#3 (E) のサブ ツリーで F I G.18のような構成なので、第二階層の VPN# Aの TEROは、 TERO= {A (0)， B (1)， C (2)， D (3), E (3)}、
VPN#Cの TEROは、 TERO= {A (0)， B (1)， C (2), E (3)， F (2)， G (3)} となる。 この TERO情報により、 F IG. 15に示すように Pathメッセージがリー フノードまで伝達される。 リーフノードまで Pathメッセージが伝達されると、 R esvメッセージにより下流から階層化ラベルがアサインされる。
F IG. 19にこの動作で各ノードに設定される、 ラベル変換テーブルとリン クで使用される階層化ラベルを示す。 例えば、 ノード PE#3 (E) では、 VP N#A， B， Cを含む第二階層の TEROが全て到達するので、 CE間のリンク で VPN毎に A (101， 30)， B (101, 25)， C (101， 5) のラベ ルが付与される。
さらに PE#2では、 VPN#A， Bを含む第二階層の TEROし力到達しな いので、 VPN#C用のラベルは付与されることなく、 リンク CD間では A (1， 1)， B (1， 25)， C (l，.Nu l 1) となる。 この情報がノード Cに到達し て、 BCから入力したラベノレパケットの CD, CEリンクへの転送関^ [系がテープ ルに設定される。 F IG. 19のノード Cのリンクで VPN#C用の CDリンク へのラベルが付与されないので、 CEリンクのみの （101， 5) の一^つのラベ ルが設定されていることに注意されたレ、。
こうして VPN#A， Bでは、 BCから到達したラベルパケットは必要なラベ ル交換が実施されて CD, CEに分岐されるが、 VPN#Cのラベルパケットは CDに転送されず、 CEのみにラベルスイッチングされていく。 この操作がホッ プパイホップに送信ノード Α·まで継続し、 VPN毎に階層化されたラベルスイツ チング経路が形成される。 こうして、 ノード Aに入力されたパケットは、 VPN 毎に階層化ラベルを付与されて中継ノードで階層化ラベルでラベルスィツチング されてリーフノードまでマルチキャスト配信される。
但し、 上記のメカニズムだけでは VPN内のマルチキャストトラヒックに対し て最適なマルチキャスト経路配信が実現できな ヽ。 F IG. 20に P E # 1配下 の VPN#B内にマルチキャストソース M#A， M#B， M#Cが存在して、 そ れぞれ異なるマルチキャスト分配パターン （F IG. 20左上） を持つ場合を想 定する。 この場合、 2階層のラベルスィッチ経路では VPN#Bが収容される全 ての PEルータ、 PE#2， PE#3， PE#4に M#A， M#B， M#Cが配 信されてしまうので、 ネットワーク効率が良くない。 例えば、 M#Aを受信しな い PE# 4にもマルチキャスト配信されてしまう。
このような無駄なマルチキャスト配信を防止するために、 更に第三階層目のラ ベルを付^することも可能である。 この例では、 このラベルは、 同一 VPNサイ ト内の同一分酉 Bトポロジに属するマルチキャストソ^"スグループということにな る。
このような帰納的な階層化メカニズムを用いることで任意の配信パターンを実 現できる。
次に、 上記の実施の形態のマルチキャストラベルスイッチングを具備した VP
VPN内でマルチキャストトラヒックを最適なトポロジで配信するために、 上 記の実施の形態で説明した 3階層のラベルスィツチング技術が有効である。 このとき、 上記の実施の形態のメカニズムを用いて VP Nサイト間を閉域接続 するためには、 各 VP N内に収容されるマルチキャスト配信経路情報を、 PEル ータ間で通常のュニキャスト経路交換と同様に交換する必要が生じる。 その例を F I G. 21に示す。 同図に示すように、 r f c 2547 b i sで規定されてい る MP— B G Pで経路交換が可能である。 F I G. 21の例では、 P E 1にその 他の PEルータが自身の収容する VP Nサイト内のマルチキャスト配信経路を配 信する例を示す。
例えば、 PE#4は、 VPN#A、 Bを収容しているので、 VPN#Aのマル チキャスト経路 MG #ひと、 VPN#Bのマルチキャスト経路 MG # βを PE 1 に MP— BGPを用いて配信している。 この例では、 一方向の経路交換例を示し ているが、 PEルータ間で双方向にフルメッシュで経路交換することで、 各 PE ルータは対向する PEルータが収容する VP Nサイト内のマルチキャスト経路を 全て把握可能となる。
このようにして、 マルチキャストラベルスィツチング経路設定者である送信ノ 一ドが対向する P E内のマルチキャスト経路を意識した階層型のボイント 'ッ 一-マルチポイントの LSPを設定可能となる。 F I G. 22に本発明を適用し た V P Nモデルを示す。 本モデルを適用することにより、 VP Nサイトアニメ一 ションの P I M—SMのマルチキャストも V P N転送可能となる。
上述のように、 本発明のマルチキャストラベルスィツチング方法及び V P Nマ ルチキャストラベルスィツチング方法によれば、 マルチキャスト配信経路全体の 転送コストを抑えながら、 宛先受信グループに最適なトポロジでマルチキャスト 配信可能なマルチキャスト転送網、 V P N網が構築できる。
そのため、 効率的で高性能なマルチキャスト配信ネットワークを構築できる。 本発明は上記の実施の形態に限定されるものではなく、 本発明の技術的範囲を 逸脱することなく、 様々なバリエーションゃ変更が可能である。

Claims

請 求 の 範 囲
1 . マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成さ れるマルチキャストネットワークにおいて、 与えられた始点と複数の終点とをそ れぞれ結ぶマルチキャスト転送経路をマルチキャスト転送経路計算装置により計 算し、 計算されたマルチキャスト転送経路をマルチキャスト経路設定装置が設定 するマノレチキャスト転送経路設定方法において、
前記マルチキャスト転送装置が、 ， 前記マルチキャストネットワーク内のリンク毎に、 かつ該リンクにデータが流 れる際の進行方向毎にトラヒックの状態を計測し、 計測結果を前記マルチキャス ト転送経路計算装置に送信することでマルチキャスト転送経路の計算依頼を行い、 前記マルチキャスト転送経路計算装置が、
前記計算依頼として取得した前記計測結果に基づいて、 前記始点と前記複数の 終点を結ぶ遅延に関する最短経路を計算し、 同時に、 該最短経路上の任意のノー ドから各終点までの遅延を計算し、 計算した値を記憶媒体に記録し、
計算された前記最短経路上をデータが流れるときの最大遅延を計算し
前記最大遅延を予め与えられた遅延条件と比較し、 もし該遅延条件に合わない 場合には、 該遅延条件を再設定し、 前記最短経路に合致する条件が見つかった場 合には、 計算された該最短経路において、 始点と終点と経路の分岐点との 3種類 の異なる種類のいずれか 2つのノード、もしくは同種の 2つのノードを端点とし、 かつ途中に、 該 3種類のノ一ドを含まなレ、任意の部分経路群から両端の 2つのノ ード間のコストが最も大きい経路を検索し、 検索された該経路を該最短経路から 削除して、 マルチキャスト転送経路を 2つの経路木に分割し、 別に計算された経 路を該 2つの経路木を結ぶために削除対象となった経路の補完経路として設定し、 計算した計算結果を前記マルチキャスト転送経路設定装置に通知し、
前記マルチキャスト転送経路設定装置が、
受け付けた前記計算結果に従い、 マルチキャスト転送経路を設定することを特 徴とするマルチキャスト転送経路設定方法。
2 . 前記マルチキャスト転送経路計算装置において、 前記補完経路を計算する 際に、
前記始点と前記終点の間で被る遅延が与えられた上限を下回り、 つ、 そのよ うな経路のうち最もコストが小さレ、経路を計算するクレーム 1記載のマルチキヤ スト転送経路設定方法。
3 . 前記マルチキャスト転送経路計算装置において、 前記補完経路を計算する 際に、
計算される経路の始点を前記分割された 2つの経路木のうち、 始点を含む経路 木に属する任意のノードから選択し、 終点を前記削除対象となった経路の終点と するような経路を計算するクレーム 2記載のマルチキャスト転送経路設定方法。
4 . 前記マルチキャスト転送経路計算装置において、 前記補完経路を計算する 際に、
公知のァルゴリズムである k-th shortest pathァルゴリズムを遅延に対して適 用し、 前記遅延条件を満たす間実行するクレーム 3記載のマルチキャスト転送経 路設定方法。
5 . 前記マルチキャスト転送経路計算装置において、 前記補完経路を計算する 際に、
公知のァノレゴリズムである k-th shortest pathァノレゴリズムをコストに対して 適用し、 前記遅延条件を満たす経路を発見するまで実行するクレーム 4記載のマ ルチキャスト転送経路設定方法。
6 . 前記マルチキャスト転送経路計算装置において、 前記補完経路を計算する 際に、
計算結果が、 tfilE遅延条件に合致するか検査する際に、 計算開始時に行った最 短経路計算時に前記記憶媒体に記録された、 始点から前記補完経路の始点までの 遅延と、 前記補完経路の終点からその下流に存在する各終点までの遅延と、 を使 用するクレーム 4記載のマルチキャスト転送経路設定方法。
7. マルチキヤストネットワークにおけるマルチキヤスト転送経路計算装置で あって、
ttf!Bマルチキャストネットワークにおけるトラヒック状態の計測結果を受信す る計測結果受信手段と、
受信した前記計測結果を記憶する計測情報記憶手段と、
前記計測結果を前記計測情報記憶手段に格納する計測結果格納手段と、 前記計測結果を前記計測情報記憶手段から読み取り、 該計測結果に基づいて経 路計算を行う経路計算手段と、 を有し、
前記経路計算手段は、
始点と複数の終点を結ぶ遅延に関する最短経路を計算し、 同時に、 経路上の任 意のノードから各終点までの遅延を計算し、 計算した値を記憶媒体に記録する最 短経路遅延計算手段と、
計算された前記最短経路上をデータが流れるときの最大遅延を計算する最大遅 延計算手段と、
前記最大遅延を予め与えられた遅延条件と比較し、 該遅延条件に合わなレヽ場合 には、該遅延条件を再設定し、該最短経路に合致する条件が見つかつた場合には、 前記最短経路計算手段で計算された該最短経路にぉ 、て、 始点と終点と経路の分 岐点との 3種類の異なる種類のいずれか 2つのノード、 もしくは同種の 2つのノ 一ドを端点とし、 かつ途中に、 該 3種類のノードを含まなレ、任意の部分経路群か ら両端の 2つのノード間のコストが最も大きい経路を検索する最大コスト経路検 索手段と、
検索された該経路を該最短経路から削除して、 マルチキャスト転送経路を 2つ の経路木に分割する経路木分割手段と、
別に計算された経路を該 2つの経路木を結ぶために削除対象となった経路の補 完経路として設定する補完経路計算手段と、 を有することを特徴とするマルチキ ヤスト転送経路計算装置。
8 . 前記補完経路計算手段は、
前記始点と前記終点の間で被る遅延が与えられた上限を下回り、 かつ、 そのよ うな経路のうち最もコストが小さいものを計算する手段を含むクレーム 7記載の マルチキャスト転送経路計算装置。
9 · 前記補完経路計算手段は、
計算される経路の始点を前記経路木分割手段で分割された 2つの経路木のうち、 始点を含む経路木に属する任意のノードから選択し、 終点を前記削除対象となつ た経路の終点とするような経路を計算する手段を含むクレーム 8記載のマルチキ ヤスト転送経路計算装置。
1 0. 前記補完経路計算手段は、
公知のアルゴリズムである k-th shortest pathアルゴリズムを遅延に対して適 用し、 前記遅延条件を満たす間実行する手段を含むクレーム9記載のマルチキヤ スト転送経路計算装置。
1 1 . 前記補完経路計算手段は、
公知のアルゴリズムである k-th shortest pathアルゴリズムをコストに対して 適用し、 前記遅延条件を満たす経路を発見するまで実行する手段を含むクレーム 1 0記載のマルチキャスト転送経路計算装置。
1 2. 前記補完経路計算手段は、
計算結果が、 前記遅延条件に合致するか検査する際に、 計算開始時に行った最 短経路計算において記録された、 始点から前記補完経路の始点までの遅延と、 前 記補完経路の終点からその下流に存在する各終点までの遅延と、 を使用するクレ ーム 1 0記載のマルチキャスト転送経路計算装置。
1 3 . 前記経路計算手段の計算結果を転送経路設定用制御メッセージに記載す る手段と、 前記転送経路設定用制御メッセージを前記計算結果が示すマルチキャスト転送 経路に沿って送信する手段と、 を有するクレーム 7記載のマルチキャスト転送経
1 4. マルチキャスト転送経路設定装置からマルチキャスト転送経路の計算依 頼を受信する手段と、
前記計算結果を前記マルチキャスト転送経路設定装置へ送信する手段と、 を有 するクレーム 7記載のマルチキャスト転送経路計算装置。
1 5 . 受信したマルチキャストネットワーク内のリンク上で発生するトラヒッ クの計測結果に基づいてマルチキャスト転送経路を計算するコンピュータに実行 させるマルチキャスト転送経路計算プログラムであって、
始点と複数の終点を結ぶ遅延に関する最短経路を計算し、 同時に、 経路上の任 意のノードから各終点までの遅延を計算し、 計算した値を記憶媒体に記録する最 短経路遅延計算ステップと、
計算された前記最短経路上をデータが流れるときの最大遅延を計算する最大遅 前記最大遅延を予め与えられた遅延条件と比較し、 該遅延条件に合わな 、場合 には、該遅延条件を再設定し、該最短経路に合致する条件が見つかつた場合には、 前記最短経路計算手段で計算された該最短経路にぉ ヽて、 始点と終点と経路の分 岐点との 3種類の異なる種類のレ、ずれか 2つのノード、 もしくは同種の 2つのノ 一ドを端点とし、 かつ途中に、 該 3種類のノードを含まない任意の部分経路群か ら両端の 2つのノード間のコストが最も大きい経路を検索し、 検索された該経路 を該最短経路から削除して、 マルチキャスト転送経路を 2つの経路木に分割し、 別に計算された経路を該 2つの経路木を結ぶために削除対象となった経路の補完 経路として設定する補完経路計算ステップとからなることを特徴とするマルチキ ヤスト転送経路計算プログラム。
1 6. 前記補完経路計算ステップは、 編己始点と前記終点の間で被る遅延が与えられた上限を下回り、 カゝつ、 そのよ うな経路のうち最もコストが小さいものを計算するクレーム 1 5記載のマルチキ ヤスト転送経路計算プログラム。
1 7. 前記補完経路計算ステップは、
計算される経路の始点を前記分割された 2つの経路木のうち、 始点を含む経路 木に属する任意のノードから選択し、 終点を前記削除対象となった経路の終点と するような経路を計算するクレーム 1 6記載のマルチキャスト転送経路計算プロ グラム。
1 8 . 前記補完経路計算ステップは、
公知のアルゴリズムである k-th shortest pathアルゴリズムを遅延に対して適 用し、 前記遅延条件を満たす間実行するクレーム 1 7記載のマルチキャスト転送 経路計算プログラム。
1 9 . 前記補完経路計算ステップは、
公知のァルゴリズムである k-th shortest pathァルゴリズムをコストに対して 適用し、 前記遅延条件を満たす経路を発見するまで実行するクレーム 1 8記載の マルチキャスト転送経路計算プログラム。
2 0. 前記補完経路計算ステップは、
計算結果が、 前記遅延条件に合致する力検査する際に、 計算開始時に行った最 短経路計算において記録された、 始点から前記補完経路の始点までの遅延と、 前 記補完経路の終点からその下流に存在する各終点までの遅延と、 を使用するクレ —ム 1 8記載のマルチキャスト転送経路計算プログラム。
2 1 . 受信したマルチキャストネットワーク内のリンク上で発生するトラヒッ クの計測結果に基づいてマルチキャスト転送経路を計算するコンピュータに実行 させるマルチキャスト転送経路計算プログラムを格納するマルチキャスト転送経 路計算プログラムを格納した記憶媒体であつて、
クレーム 1 5記載のプログラムを格納したことを特徴とするマルチキャスト転 送経路計算プログラムを格納した記憶媒体。
2 2. マノレチキャスト通信ネットワークにおいて、 マノレチキャストソースノー ドからマルチキャストリーフのグノレープノードにマルチキャスト配信用のラベル スィツチング経路を設定するマルチキャストラベルスィツチング方法において、 前記ソースノードから全てのリーフノードにポイント ·ツー ·マルチポイント の最上位階層のラベルスィツチ経路を設定し、
設定されたボイント 'ツー ·マルチボイント の前記ラベルスィツチング経路の リーフノードグループより任意の宛先リーフノードを抽出した複数のサブグルー プに対して、 該サブグループ毎に第二階層のラベルで第一階層のラベルスィツチ ング経路の部分ッリ一を構成する複数の第二階層のラベルスィツチング経路を設 定し、
階層化された前記第一階層のラベルスイッチング経路と前記第二のラベルスィ ツチング経路を用いて、 ラベノレスィツチングするときに入力側のラベルエッジル ータが前記第二階層のラベルに対応した宛先リーフグループ宛の宛先ァドレスを 持つトラヒックを対応する階層化ラベルに割り当て、 付与し、
中継ラベルスィッチルータは、 第一階層、 第二階層のラベルペアに応じて、 パ 中継ノ一ド力 前記ボイント 'ツー'マルチボイント ラベルスィツチング経路 の分岐ノードとして指定される場合には、 入力ラベルペアを複数の出力分岐に対 応する出力ラベルに置き換え、 出力分岐毎にコピーし、
出力ラベルエッジルータは、 入力された階層化ラベルバケツトを階層ラベルの グ /レープを判定しながら、 ラベノレ除去しながら出力ラインにスイッチングし、 ポイント 'ツー ·マノレチポィント の L S P内の、第一階層のリーフグループノ 一ドのうち、 異なる宛先サブグループを構成する複数の第二階層の第一階層の部 分ッリ一を構成する第二階層のボイント .ツー■マルチボイント の L S Pを用い て、 第一階層のラベルスイッチング経路を共有しながら、 第二階層のサブグルー プ毎にトラヒックをラベルスィツチングすることを特徴とするマルチキャストラ ベルスィツチング方法。
2 3. 第二階層のマルチキャストラベルスイッチング経路内に、 さらに、 第二 階層のラベルスィツチング経路を構成するリーフノードの部 ϋ合を構成するリ ーフノード宛に、 該第二階層のラベルスイッチング経路の部分トポロジを構成す るサブツリーを用いて、 第三階層のラベルスイッチング経路として、 複数の第三 階層ラベルスィツチング経路を備え、
さらに、 サブグループ化が必要な場合には、 下位階層のラベルスイッチング経 路を帰納的に設定し、
帰納的に設定された階層化ラベルスイッチング経路を用いてサブグループ毎に マルチキャストラベルスイッチングを行うクレーム 2 2記載のマルチキャストラ ベルスィツチング方法。 2 4. 前記クレーム 2 2記載のマルチキャストラベルスィツチング方法を、 Μ
P L Sを用いた V Ρ Νサービスに適用する際に、
V P Nサイトを収容する全てのプロバイダネットワークのプロバイダエッジル ータ間に第一階層のポィント 'ツー'マルチポィント のマノレチキャスト L S Ρを フルメッシュで接続し、
さらに、 前記プロバイダネットワークに収容される V P Νサイト毎に対応して 第二階層のマルチキャストラベルスィツチ経路を設定し、
前記第二階層のラベルスィツチ経路を設定する場合には、 V P Nを構成するプ ロバイダエッジルータがマルチキャストラベルスィツチ経路のリーフノードを構 成するときに、 各リーフに収容される、 V P Nサイトに応じて第二階層のラベル スィツチング経路を最適な部分ッリ一トポロジに調整し、
Ifiiav p N内で前記プロバイダェッジルータ間を接続する第一階層のマルチキ ヤストッリ一内に第二階層ッリーとして構成するクレーム 2 2記載のマルチキヤ ストラべノレスィツチング方法。
2 5. V P Nサイト内に複数の異なるサイト宛先を持つマルチキャスト配信経 路が存在する場合に、
前記第二階層の下位層の第三階層にそれぞれのマルチキャスト配信経路に対応 する V P Nサイトのみを宛先リーフノードとして第二階層のマルチキャスト配信 経路の部分ッリ一経路として第三階層のマルチキャスト配信経路を設定し、 前記 V P Nの同一 V P Nに所属するトラヒックであっても、 該 V P N内でマル チキャストトラヒックの受信を希望する V P Nサイトのみにマルチキャストトラ ヒックを配信するクレーム 2 4記載のマルチキャストラベルスィツチング方法。
2 6. 通信方式をラベルスィツチルータ機能として具備し、
前記入力マルチキャス卜ラベノレスィツチルータ、 中継マルチキャストラべルス ィツチルータ、 出力マルチキャストラベルスィツチルータとして動作させるクレ ーム 2 2記載 (；
PCT/JP2004/001246 2003-02-07 2004-02-06 マルチキャスト転送経路設定方法、及びそれを実現するためのマルチキャストラベルスイッチング方法 Ceased WO2004071032A1 (ja)

Priority Applications (4)

Application Number Priority Date Filing Date Title
EP20040708880 EP1592183A4 (en) 2003-02-07 2004-02-06 MULTICAST TRANSFER ROUTINE SETTING METHOD AND MULTICAST LABEL SWITCHING METHOD FOR IMPLEMENTING THE PROCESS
US10/522,713 US7583601B2 (en) 2003-02-07 2004-02-06 Multicast transfer route setting method, and multicast label switching method for implementing former method
JP2005504888A JP3900195B2 (ja) 2003-02-07 2004-02-06 マルチキャスト転送経路設定方法、及びそれを実現するためのマルチキャストラベルスイッチング方法
US12/237,912 US7792099B2 (en) 2003-02-07 2008-09-25 Method of setting multicast transfer route and method of multicast label switching for realizing the same

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
JP2003031605 2003-02-07
JP2003-031605 2003-02-07
JP2003-038782 2003-02-17
JP2003038782 2003-02-17

Related Child Applications (2)

Application Number Title Priority Date Filing Date
US10522713 A-371-Of-International 2004-02-06
US12/237,912 Division US7792099B2 (en) 2003-02-07 2008-09-25 Method of setting multicast transfer route and method of multicast label switching for realizing the same

Publications (1)

Publication Number Publication Date
WO2004071032A1 true WO2004071032A1 (ja) 2004-08-19

Family

ID=32852693

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2004/001246 Ceased WO2004071032A1 (ja) 2003-02-07 2004-02-06 マルチキャスト転送経路設定方法、及びそれを実現するためのマルチキャストラベルスイッチング方法

Country Status (4)

Country Link
US (2) US7583601B2 (ja)
EP (1) EP1592183A4 (ja)
JP (1) JP3900195B2 (ja)
WO (1) WO2004071032A1 (ja)

Cited By (34)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2007009335A1 (en) * 2005-06-04 2007-01-25 Huawei Technologies Co., Ltd. A method for realizing the multicast service in an automatic switch optical network
WO2007020774A1 (ja) * 2005-08-19 2007-02-22 Brother Kogyo Kabushiki Kaisha 情報通信システム、情報通信方法、情報通信システムに含まれるノード装置および情報処理プログラムを記憶した記憶媒体
US7519010B1 (en) * 2004-08-30 2009-04-14 Juniper Networks, Inc. Inter-autonomous system (AS) multicast virtual private networks
US7564803B1 (en) 2005-08-29 2009-07-21 Juniper Networks, Inc. Point to multi-point label switched paths with label distribution protocol
US7602702B1 (en) 2005-02-10 2009-10-13 Juniper Networks, Inc Fast reroute of traffic associated with a point to multi-point network tunnel
KR100949323B1 (ko) * 2005-11-25 2010-03-23 지티이 코포레이션 자동 교환 광 네트워크 멀티캐스트 서비스의 루트 선택방법
US7742482B1 (en) 2006-06-30 2010-06-22 Juniper Networks, Inc. Upstream label assignment for the resource reservation protocol with traffic engineering
US7769873B1 (en) 2002-10-25 2010-08-03 Juniper Networks, Inc. Dynamically inserting filters into forwarding paths of a network device
US7839862B1 (en) 2006-06-30 2010-11-23 Juniper Networks, Inc. Upstream label assignment for the label distribution protocol
US7839850B2 (en) 2006-01-30 2010-11-23 Juniper Networks, Inc. Forming equal cost multipath multicast distribution structures
US7856509B1 (en) 2004-04-09 2010-12-21 Juniper Networks, Inc. Transparently providing layer two (L2) services across intermediate computer networks
US7929557B2 (en) 2008-11-14 2011-04-19 Juniper Networks, Inc. Summarization and longest-prefix match within MPLS networks
US7936780B1 (en) 2008-03-12 2011-05-03 Juniper Networks, Inc. Hierarchical label distribution protocol for computer networks
CN102098591A (zh) * 2009-12-11 2011-06-15 中兴通讯股份有限公司 一种ason中资源共享的方法和业务节点
US7990965B1 (en) 2005-07-28 2011-08-02 Juniper Networks, Inc. Transmission of layer two (L2) multicast traffic over multi-protocol label switching networks
US8078758B1 (en) 2003-06-05 2011-12-13 Juniper Networks, Inc. Automatic configuration of source address filters within a network device
US8125926B1 (en) 2007-10-16 2012-02-28 Juniper Networks, Inc. Inter-autonomous system (AS) virtual private local area network service (VPLS)
US8270395B2 (en) 2006-01-30 2012-09-18 Juniper Networks, Inc. Forming multicast distribution structures using exchanged multicast optimization data
US8310957B1 (en) 2010-03-09 2012-11-13 Juniper Networks, Inc. Minimum-cost spanning trees of unicast tunnels for multicast distribution
US8422514B1 (en) 2010-02-09 2013-04-16 Juniper Networks, Inc. Dynamic configuration of cross-domain pseudowires
US8462635B1 (en) 2006-06-30 2013-06-11 Juniper Networks, Inc. Resource reservation protocol with traffic engineering point to multi-point label switched path hierarchy
JP2014060483A (ja) * 2012-09-14 2014-04-03 Hitachi Kokusai Electric Inc 通信システム及びその通信方法
US8837479B1 (en) 2012-06-27 2014-09-16 Juniper Networks, Inc. Fast reroute between redundant multicast streams
US8917729B1 (en) 2008-12-10 2014-12-23 Juniper Networks, Inc. Fast reroute for multiple label switched paths sharing a single interface
US8953500B1 (en) 2013-03-29 2015-02-10 Juniper Networks, Inc. Branch node-initiated point to multi-point label switched path signaling with centralized path computation
US9049148B1 (en) 2012-09-28 2015-06-02 Juniper Networks, Inc. Dynamic forwarding plane reconfiguration in a network device
US9100213B1 (en) 2011-06-08 2015-08-04 Juniper Networks, Inc. Synchronizing VPLS gateway MAC addresses
US9166807B2 (en) 2005-07-28 2015-10-20 Juniper Networks, Inc. Transmission of layer two (L2) multicast traffic over multi-protocol label switching networks
US9246838B1 (en) 2011-05-27 2016-01-26 Juniper Networks, Inc. Label switched path setup using fast reroute bypass tunnel
US9806895B1 (en) 2015-02-27 2017-10-31 Juniper Networks, Inc. Fast reroute of redundant multicast streams
US9992096B2 (en) 2014-02-19 2018-06-05 Huawei Technologies Co., Ltd. Method and apparatus for fast protection switching in multicast
JP6437180B1 (ja) * 2017-10-02 2018-12-12 三菱電機株式会社 通信装置および通信ネットワーク
CN113472671A (zh) * 2020-03-30 2021-10-01 中国电信股份有限公司 组播路由的确定方法、装置和计算机可读存储介质
CN115516951A (zh) * 2020-04-11 2022-12-23 Lg 电子株式会社 在nr v2x中选择传输资源的方法和装置

Families Citing this family (47)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7925778B1 (en) * 2004-02-13 2011-04-12 Cisco Technology, Inc. Method and apparatus for providing multicast messages across a data communication network
JP2006060579A (ja) * 2004-08-20 2006-03-02 Fujitsu Ltd アプリケーション特性に応じて複数の経路を同時に利用する通信装置
US8619774B2 (en) * 2004-10-26 2013-12-31 Cisco Technology, Inc. Method and apparatus for providing multicast messages within a virtual private network across a data communication network
US7570649B2 (en) * 2005-02-28 2009-08-04 Alcatel Lucent Forwarding state sharing between multiple traffic paths in a communication network
US8089964B2 (en) 2005-04-05 2012-01-03 Cisco Technology, Inc. Transporting multicast over MPLS backbone using virtual interfaces to perform reverse-path forwarding checks
JP4577163B2 (ja) * 2005-09-06 2010-11-10 株式会社日立製作所 インターワーキング方法及び装置
US8243630B2 (en) * 2005-10-19 2012-08-14 Microsoft Corporation Application-level routing protocol for multiparty audio-video conferencing
US7852841B2 (en) * 2005-11-04 2010-12-14 Cisco Technology, Inc. In-band multicast signaling using LDP
US8107473B2 (en) * 2006-03-16 2012-01-31 Cisco Technology, Inc. Automation fallback to P2P LSPs for mLDP built multipoint-trees
CN100563203C (zh) * 2005-11-11 2009-11-25 华为技术有限公司 通信网络中组播树叶子节点网元信号传送的方法
JP4881610B2 (ja) * 2005-11-30 2012-02-22 株式会社日立製作所 測定システム及び管理装置及びその処理分散方法
US8560651B2 (en) * 2006-03-07 2013-10-15 Cisco Technology, Inc. Method and system for streaming user-customized information
US8934486B2 (en) * 2006-03-16 2015-01-13 Cisco Technology, Inc. System and method for implementing multicast over a label-switched core network
CN100563217C (zh) 2006-06-09 2009-11-25 华为技术有限公司 解决标签冲突的方法和系统
US7856014B2 (en) * 2006-10-27 2010-12-21 International Business Machines Corporation High capacity multicast forwarding
US8045562B2 (en) * 2006-10-31 2011-10-25 Hewlett-Packard Development Company, L.P. Estimating link interference and bandwidth
US8279753B2 (en) * 2007-01-11 2012-10-02 Oracle International Corporation Efficient determination of fast routes when voluminous data is to be sent from a single node to many destination nodes via other intermediate nodes
JP4825696B2 (ja) * 2007-01-22 2011-11-30 アラクサラネットワークス株式会社 パケット中継装置
US8432894B2 (en) * 2007-02-27 2013-04-30 Alcatel Lucent Asymmetrical forwarding in layer 3 IP VPNs
US7986692B2 (en) * 2007-03-08 2011-07-26 Motorola Solutions, Inc. System and method for transmitting call information in a communication system with long link delays
EP2135393B1 (en) * 2007-04-13 2011-04-06 Telefonaktiebolaget LM Ericsson (publ) Ethernet spanning tree provision
KR101334459B1 (ko) * 2007-06-28 2013-11-29 주식회사 케이티 멀티캐스트 ｖｐｎ망에서의 ｍｄｔ 시험 시스템 및 그 방법
US8289883B2 (en) * 2007-12-21 2012-10-16 Samsung Electronics Co., Ltd. Hybrid multicast routing protocol for wireless mesh networks
TWI350672B (en) * 2007-12-31 2011-10-11 Nat Univ Tsing Hua A matjod for constructing network application-layer multicast trees by transmiting data among network terminal equipments
JP5112229B2 (ja) * 2008-09-05 2013-01-09 株式会社エヌ・ティ・ティ・ドコモ 配信装置、端末装置及びシステム並びに方法
JP5080406B2 (ja) * 2008-09-05 2012-11-21 株式会社エヌ・ティ・ティ・ドコモ 配信装置、端末装置及びシステム並びに方法
US8289978B2 (en) * 2008-10-15 2012-10-16 At&T Intellectual Property I, Lp Broadcast interactive television system
US8391303B2 (en) * 2009-04-16 2013-03-05 Futurewei Technologies, Inc. Border gateway protocol (BGP) grouped route withdrawals
US20110188499A1 (en) * 2010-02-04 2011-08-04 Cisco Technology, Inc. Point-to-multipoint path implementation in a multicast virtual private network
US9680750B2 (en) 2010-07-06 2017-06-13 Nicira, Inc. Use of tunnels to hide network addresses
US8750164B2 (en) 2010-07-06 2014-06-10 Nicira, Inc. Hierarchical managed switch architecture
US8964528B2 (en) 2010-07-06 2015-02-24 Nicira, Inc. Method and apparatus for robust packet distribution among hierarchical managed switching elements
CN102447980B (zh) * 2010-09-30 2015-01-28 中兴通讯股份有限公司 一种路由控制方法、系统及路由计算装置
WO2012178098A1 (en) * 2011-06-22 2012-12-27 Huawei Technologies Co., Ltd. Protocol independent multicast with quality of service support
WO2013139524A1 (en) * 2012-03-19 2013-09-26 Nokia Siemens Networks Oy Data transmission mechanism with improved robustness using multiflow connection
US20140204763A1 (en) * 2013-01-24 2014-07-24 Aruba Networks, Inc. Method and System for Routing Data
CN103248571A (zh) * 2013-05-16 2013-08-14 湖北邮电规划设计有限公司 一种最优第二路由的计算方法
US9432204B2 (en) 2013-08-24 2016-08-30 Nicira, Inc. Distributed multicast by endpoints
US9602385B2 (en) 2013-12-18 2017-03-21 Nicira, Inc. Connectivity segment selection
US9602392B2 (en) 2013-12-18 2017-03-21 Nicira, Inc. Connectivity segment coloring
US9794079B2 (en) 2014-03-31 2017-10-17 Nicira, Inc. Replicating broadcast, unknown-unicast, and multicast traffic in overlay logical networks bridged with physical networks
CN105871723A (zh) * 2015-12-14 2016-08-17 乐视云计算有限公司 数据传输方法、装置及系统
US11218415B2 (en) * 2018-11-18 2022-01-04 Mellanox Technologies Tlv Ltd. Low-latency processing of multicast packets
KR102291440B1 (ko) * 2019-04-04 2021-08-18 주식회사 케이티 회선 개통 자동화 방법 및 그 장치
US10778457B1 (en) 2019-06-18 2020-09-15 Vmware, Inc. Traffic replication in overlay networks spanning multiple sites
JP7437282B2 (ja) * 2020-10-01 2024-02-22 株式会社Ｓｃｒｅｅｎホールディングス 配線データ生成装置、描画システムおよび配線データ生成方法
US11784922B2 (en) 2021-07-03 2023-10-10 Vmware, Inc. Scalable overlay multicast routing in multi-tier edge gateways

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2001156800A (ja) * 1999-11-30 2001-06-08 Nec Corp 通信コネクションマージ方式及びそれを用いるノード
JP2002176441A (ja) * 2000-12-08 2002-06-21 Fujitsu Ltd 通信装置
JP2002300169A (ja) * 2001-03-29 2002-10-11 Mitsubishi Electric Corp 無線通信装置およびパスルーティング方法

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6947434B2 (en) * 2000-11-16 2005-09-20 Telefonaktiebolaget Lm Ericsson (Publ) Subgroup multicasting in a communications network
JP2002271356A (ja) * 2001-03-12 2002-09-20 Oki Electric Ind Co Ltd ネットワーク通信システム
US6961319B2 (en) * 2001-07-16 2005-11-01 International Business Machines Corporation Methods and arrangements for distribution tree development
DE60320104T2 (de) * 2002-12-11 2009-05-14 Nippon Telegraph & Telephone Co. Verfahren und Vorrichtung zur Berechnung von Mehrfachsendungsleitwegen
US7660254B2 (en) * 2006-12-22 2010-02-09 Cisco Technology, Inc. Optimization of distributed tunnel rerouting in a computer network with coordinated head-end node path computation
US7668971B2 (en) * 2008-01-11 2010-02-23 Cisco Technology, Inc. Dynamic path computation element load balancing with backup path computation elements

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2001156800A (ja) * 1999-11-30 2001-06-08 Nec Corp 通信コネクションマージ方式及びそれを用いるノード
JP2002176441A (ja) * 2000-12-08 2002-06-21 Fujitsu Ltd 通信装置
JP2002300169A (ja) * 2001-03-29 2002-10-11 Mitsubishi Electric Corp 無線通信装置およびパスルーティング方法

Non-Patent Citations (6)

* Cited by examiner, † Cited by third party
Title
HITOSHI UTA ET AL.: "MPLS Jisso AYANE ni Okeru Packet Tenso Kiko no Sekkei Oyobi Jiso", INFORMATION PROCESSING SOCIETY OF JAPAN SYMPOSIUM SERIES, vol. 2000, no. 15, 6 December 2000 (2000-12-06), MULTIMEDIA TSUSHIN TO BUSAN SHORI WORKSHOP RONBUNSHU, pages 127 - 132, XP002903744 *
NOBUO KOHAKU ET AL.: "Takeiro Seigyo Omogata Multicast no Sekkei to Jisso ni Kansuru Kosatsu", INFORMATION PROCESSING SOCIETY OF JAPAN SYMPOSIUM SERIES, vol. 2000, no. 15, 6 December 2000 (2000-12-06), MULTIMEDIA TSUSHIN TO BUNSAN SHORI WORKSHOP RONBUNSHU, pages 175 - 180, XP002903745 *
See also references of EP1592183A4 *
YONGJUN IM ET AL.: "Multicast routing algorithms in high speed networks", PROCEEDING OF THE FIFTH IEEE COMPUTER SOCIETY WORKSHOP ON FUTURE TRENDS OF DISTRIBUTED COMPUTING SYSTEMS, August 1995 (1995-08-01), pages 495 - 501, XP002903743 *
ZHANG BAOXIAN ET AL.: "An efficient delay-constrained multicast routing algorithm", PROCEEDING OF ICCT 2000, vol. 1 & 2, 2000, pages 1244 - 1247, XP010526599 *
ZHU Q. ET AL.: "A source-based algorithm for delay-constrained minimum-cost multicasting", IEEE INFOCOM', vol. 1, 1995, pages 377 - 385, XP000580601 *

Cited By (62)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7769873B1 (en) 2002-10-25 2010-08-03 Juniper Networks, Inc. Dynamically inserting filters into forwarding paths of a network device
US8078758B1 (en) 2003-06-05 2011-12-13 Juniper Networks, Inc. Automatic configuration of source address filters within a network device
US8880727B1 (en) 2004-04-09 2014-11-04 Juniper Networks, Inc. Transparently providing layer two (L2) services across intermediate computer networks
US8151000B1 (en) 2004-04-09 2012-04-03 Juniper Networks, Inc. Transparently providing layer two (L2) services across intermediate computer networks
US7856509B1 (en) 2004-04-09 2010-12-21 Juniper Networks, Inc. Transparently providing layer two (L2) services across intermediate computer networks
US8068492B1 (en) 2004-08-30 2011-11-29 Juniper Networks, Inc. Transport of control and data traffic for multicast virtual private networks
US8121056B1 (en) 2004-08-30 2012-02-21 Juniper Networks, Inc. Aggregate multicast trees for multicast virtual private networks
US7564806B1 (en) 2004-08-30 2009-07-21 Juniper Networks, Inc. Aggregate multicast trees for multicast virtual private networks
US8625465B1 (en) 2004-08-30 2014-01-07 Juniper Networks, Inc. Auto-discovery of virtual private networks
US7570604B1 (en) 2004-08-30 2009-08-04 Juniper Networks, Inc. Multicast data trees for virtual private local area network (LAN) service multicast
US7570605B1 (en) 2004-08-30 2009-08-04 Juniper Networks, Inc. Multicast data trees for multicast virtual private networks
US7590115B1 (en) 2004-08-30 2009-09-15 Juniper Networks, Inc. Exchange of control information for virtual private local area network (LAN) service multicast
US8160076B1 (en) * 2004-08-30 2012-04-17 Juniper Networks, Inc. Auto-discovery of multicast virtual private networks
US7519010B1 (en) * 2004-08-30 2009-04-14 Juniper Networks, Inc. Inter-autonomous system (AS) multicast virtual private networks
US7558263B1 (en) 2004-08-30 2009-07-07 Juniper Networks, Inc. Reliable exchange of control information for multicast virtual private networks
US7558219B1 (en) 2004-08-30 2009-07-07 Juniper Networks, Inc. Multicast trees for virtual private local area network (LAN) service multicast
US7804790B1 (en) 2004-08-30 2010-09-28 Juniper Networks, Inc. Aggregate multicast trees for virtual private local area network (LAN) service multicast
US8111633B1 (en) 2004-08-30 2012-02-07 Juniper Networks, Inc. Multicast trees for virtual private local area network (LAN) service multicast
US7522600B1 (en) 2004-08-30 2009-04-21 Juniper Networks, Inc. Transport of control and data traffic for multicast virtual private networks
US7522599B1 (en) 2004-08-30 2009-04-21 Juniper Networks, Inc. Label switching multicast trees for multicast virtual private networks
US7990963B1 (en) 2004-08-30 2011-08-02 Juniper Networks, Inc. Exchange of control information for virtual private local area network (LAN) service multicast
US7933267B1 (en) * 2004-08-30 2011-04-26 Juniper Networks, Inc. Shared multicast trees for multicast virtual private networks
US7983261B1 (en) 2004-08-30 2011-07-19 Juniper Networks, Inc. Reliable exchange of control information for multicast virtual private networks
US7957386B1 (en) 2004-08-30 2011-06-07 Juniper Networks, Inc. Inter-autonomous system (AS) multicast virtual private networks
US7602702B1 (en) 2005-02-10 2009-10-13 Juniper Networks, Inc Fast reroute of traffic associated with a point to multi-point network tunnel
WO2007009335A1 (en) * 2005-06-04 2007-01-25 Huawei Technologies Co., Ltd. A method for realizing the multicast service in an automatic switch optical network
US7990965B1 (en) 2005-07-28 2011-08-02 Juniper Networks, Inc. Transmission of layer two (L2) multicast traffic over multi-protocol label switching networks
US9166807B2 (en) 2005-07-28 2015-10-20 Juniper Networks, Inc. Transmission of layer two (L2) multicast traffic over multi-protocol label switching networks
US8059561B2 (en) 2005-08-19 2011-11-15 Brother Kogyo Kabushiki Kaisha Information communication system, information communication method, node device included in information communication system, and recording medium having information processing program recorded on it
WO2007020774A1 (ja) * 2005-08-19 2007-02-22 Brother Kogyo Kabushiki Kaisha 情報通信システム、情報通信方法、情報通信システムに含まれるノード装置および情報処理プログラムを記憶した記憶媒体
US7940698B1 (en) 2005-08-29 2011-05-10 Juniper Networks, Inc. Point to multi-point label switched paths with label distribution protocol
US7564803B1 (en) 2005-08-29 2009-07-21 Juniper Networks, Inc. Point to multi-point label switched paths with label distribution protocol
KR100949323B1 (ko) * 2005-11-25 2010-03-23 지티이 코포레이션 자동 교환 광 네트워크 멀티캐스트 서비스의 루트 선택방법
US7839850B2 (en) 2006-01-30 2010-11-23 Juniper Networks, Inc. Forming equal cost multipath multicast distribution structures
US8270395B2 (en) 2006-01-30 2012-09-18 Juniper Networks, Inc. Forming multicast distribution structures using exchanged multicast optimization data
US7742482B1 (en) 2006-06-30 2010-06-22 Juniper Networks, Inc. Upstream label assignment for the resource reservation protocol with traffic engineering
US8488614B1 (en) 2006-06-30 2013-07-16 Juniper Networks, Inc. Upstream label assignment for the label distribution protocol
US7839862B1 (en) 2006-06-30 2010-11-23 Juniper Networks, Inc. Upstream label assignment for the label distribution protocol
US8767741B1 (en) 2006-06-30 2014-07-01 Juniper Networks, Inc. Upstream label assignment for the resource reservation protocol with traffic engineering
US8462635B1 (en) 2006-06-30 2013-06-11 Juniper Networks, Inc. Resource reservation protocol with traffic engineering point to multi-point label switched path hierarchy
US8125926B1 (en) 2007-10-16 2012-02-28 Juniper Networks, Inc. Inter-autonomous system (AS) virtual private local area network service (VPLS)
US7936780B1 (en) 2008-03-12 2011-05-03 Juniper Networks, Inc. Hierarchical label distribution protocol for computer networks
US8363667B2 (en) 2008-11-14 2013-01-29 Juniper Networks, Inc. Summarization and longest-prefix match within MPLS networks
US7929557B2 (en) 2008-11-14 2011-04-19 Juniper Networks, Inc. Summarization and longest-prefix match within MPLS networks
US8917729B1 (en) 2008-12-10 2014-12-23 Juniper Networks, Inc. Fast reroute for multiple label switched paths sharing a single interface
CN102098591A (zh) * 2009-12-11 2011-06-15 中兴通讯股份有限公司 一种ason中资源共享的方法和业务节点
US8422514B1 (en) 2010-02-09 2013-04-16 Juniper Networks, Inc. Dynamic configuration of cross-domain pseudowires
US8310957B1 (en) 2010-03-09 2012-11-13 Juniper Networks, Inc. Minimum-cost spanning trees of unicast tunnels for multicast distribution
US9246838B1 (en) 2011-05-27 2016-01-26 Juniper Networks, Inc. Label switched path setup using fast reroute bypass tunnel
US9100213B1 (en) 2011-06-08 2015-08-04 Juniper Networks, Inc. Synchronizing VPLS gateway MAC addresses
US8837479B1 (en) 2012-06-27 2014-09-16 Juniper Networks, Inc. Fast reroute between redundant multicast streams
JP2014060483A (ja) * 2012-09-14 2014-04-03 Hitachi Kokusai Electric Inc 通信システム及びその通信方法
US9049148B1 (en) 2012-09-28 2015-06-02 Juniper Networks, Inc. Dynamic forwarding plane reconfiguration in a network device
US8953500B1 (en) 2013-03-29 2015-02-10 Juniper Networks, Inc. Branch node-initiated point to multi-point label switched path signaling with centralized path computation
US9992096B2 (en) 2014-02-19 2018-06-05 Huawei Technologies Co., Ltd. Method and apparatus for fast protection switching in multicast
KR101878085B1 (ko) * 2014-02-19 2018-07-12 후아웨이 테크놀러지 컴퍼니 리미티드 멀티캐스트 고속 보호 스위칭 방법 및 디바이스
US9806895B1 (en) 2015-02-27 2017-10-31 Juniper Networks, Inc. Fast reroute of redundant multicast streams
JP6437180B1 (ja) * 2017-10-02 2018-12-12 三菱電機株式会社 通信装置および通信ネットワーク
WO2019069353A1 (ja) * 2017-10-02 2019-04-11 三菱電機株式会社 通信装置および通信ネットワーク
CN113472671A (zh) * 2020-03-30 2021-10-01 中国电信股份有限公司 组播路由的确定方法、装置和计算机可读存储介质
CN113472671B (zh) * 2020-03-30 2023-05-02 中国电信股份有限公司 组播路由的确定方法、装置和计算机可读存储介质
CN115516951A (zh) * 2020-04-11 2022-12-23 Lg 电子株式会社 在nr v2x中选择传输资源的方法和装置

Also Published As

Publication number Publication date
EP1592183A4 (en) 2010-02-24
EP1592183A1 (en) 2005-11-02
US7792099B2 (en) 2010-09-07
US20090028149A1 (en) 2009-01-29
JPWO2004071032A1 (ja) 2006-06-01
US7583601B2 (en) 2009-09-01
US20060147204A1 (en) 2006-07-06
JP3900195B2 (ja) 2007-04-04

Similar Documents

Publication Publication Date Title
WO2004071032A1 (ja) マルチキャスト転送経路設定方法、及びそれを実現するためのマルチキャストラベルスイッチング方法
KR100703499B1 (ko) 다중 프로토콜 레이블 교환 시스템에서 트래픽 엔지니어링기능을 구현하기 위한 데이터구조 및 구축 방법
CN1992676B (zh) 在通信网络中多个业务路径之间共享转发状态的方法和设备
CN101313528B (zh) 一种多域路由计算方法和系统
CN101471853B (zh) 一种路由计算方法、单元及系统
JP4612987B2 (ja) マルチプロトコルラベルスイッチングベースのポイント対マルチポイント・トラフィックルーチング方法
CN101313517A (zh) 以太网中的控制系统、数据报文传输方法和网络设备
US8295201B2 (en) System and method for providing lower-layer path validation for higher-layer autonomous systems
CN109995655A (zh) 一种实现无缝最优跨域路径的方法及装置
JP2003018191A (ja) マルチプロトコルラベルスイッチングネットワークにおけるトラフィック経路決定方法
WO2007054032A1 (fr) Procede d'emission de signal en arbre de diffusion multi-destinataire, et element de reseau noeud correspondant
WO2007079667A1 (en) A method for traffic engineering computation between the areas and a system, an equipment, a storage media thereof
JP3755527B2 (ja) マルチキャスト転送経路計算方法及びマルチキャスト転送経路計算装置並びにプログラム
WO2007019758A1 (en) A method, system and apparatus for implementing traffic engineering
CN100442758C (zh) 组播传送路径设定方法和实现该方法的组播标签交换方法
JP2004260285A (ja) 通信品質管理システムおよび方法
JP4231074B2 (ja) マルチキャストラベルスイッチング方法
CN101534203B (zh) 一种组播控制的方法、设备和系统
Wen et al. Centralized Control and Management Architecture Design for PIM-SM Based IP/MPLS Multicast Networks
Ravindran et al. Cost analysis of multicast transport architectures in multiservice networks
JP4522955B2 (ja) マルチキャストポイントツーポイント（ｍｐ２ｐ）マルチプロトコルラベルスイッチング（ｍｐｌｓ）トラヒックエンジニアリング（ｔｅ）通信システム
Li et al. Deploying bidirectional multicast shared trees in MPLS networks
Bartczak et al. Assuring quality of service for IP Multicast transmissions in ISP networks
Pedersen et al. A new approach to multicasting and QoS within an MPLS backbone
JP2003060696A (ja) ルータシステム

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 2005504888

Country of ref document: JP

AK Designated states

Kind code of ref document: A1

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BW BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE EG ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NA NI NO NZ OM PG PH PL PT RO RU SC SD SE SG SK SL SY TJ TM TN TR TT TZ UA UG US UZ VC VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): BW GH GM KE LS MW MZ SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LU MC NL PT RO SE SI SK TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
ENP Entry into the national phase

Ref document number: 2006147204

Country of ref document: US

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 10522713

Country of ref document: US

REEP Request for entry into the european phase

Ref document number: 2004708880

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 2004708880

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 2004800740X

Country of ref document: CN

WWP Wipo information: published in national office

Ref document number: 2004708880

Country of ref document: EP

WWP Wipo information: published in national office

Ref document number: 10522713

Country of ref document: US