JP2005094137A - Multicast transfer path setting method and apparatus - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a technology capable of attaining active / standby switching in a midway node so as to reduce a switching time. <P>SOLUTION: A multicast transfer path setting method calculates a main transfer path respectively tying a given start point and a plurality of end points, calculates a standby transfer path to all links on the main transfer path, measures a traffic state by each link and by each traveling direction of data distributed to each link to calculate the main transfer path, and calculates and obtains the standby transfer path by each link on the calculated main transfer path. <P>COPYRIGHT: (C)2005,JPO&NCIPI

Description

  The present invention is used for multicast transfer for delivering moving images and audio to a specific number of users over a computer network. In particular, it relates to a countermeasure against a failure in a multicast main transfer path (hereinafter referred to as a main transfer path).

  Multicast forwarding, which distributes video and audio to a large number of users over a computer network, has attracted attention. In this transfer method, information is copied at a portion where the route is divided among routes connecting the start point of the route and one or more selected end points, and the information is delivered to each end point. When information is delivered using a unicast transfer that transfers one-to-one with the start point to a specific number of end points, it is necessary to prepare information for the start point as many as the end points. Therefore, the amount of information in the network is reduced by using multicast transfer.

  In multicast transfer, a specific number of end points are managed in a management unit called a multicast group, and one transfer path is set for the multicast group. This transfer path is set so as to connect all the end points belonging to the multicast group from the start point. In the case of a link failure on the route, in the case of unicast transfer, since it is a one-to-one transfer, there is little influence on the end point that information is not received, but in the case of multicast transfer, it is a one-to-multiple transfer. The number of endpoints affected by one link failure may increase.

  An example is shown in FIG. In this example, in the case of unicast transfer, only one recipient can no longer receive information, but in the case of multicast transfer, there are 6 end points. Therefore, it is more important to have a multicast preliminary transfer path (hereinafter referred to as a preliminary transfer path) in multicast transfer than unicast transfer.

Currently, methods such as Non-Patent Documents 1 to 3 are disclosed as algorithms for obtaining a backup transfer path with respect to a main transfer path instead of a backup transfer path for a link. These methods are algorithms for obtaining the main transfer route and the backup transfer route at the same time. In particular, the method introduced in Non-Patent Document 1 reduces the bandwidth used by the main transfer route and the backup transfer route. Is aimed at.
M. Kodialem and T. Lakshman. Dynamicrouting of bandwidth guaranteed multicasts with failure backup. In Proceedingsof IEEE INFOCOM, June 2002. Alon Itai and Michael Rodeh. The multi-tree approach to reliability in distributed networks. In IEEE Symposium on Foundations of Computer Science, pages 137-147, 1984. M.M_edard, S.Finn, R.Barry, andR.Gallager.Redundant trees for preplanned recovery in arbitraryvertex-redundant or edge-redundant graphs.IEEE/ACM Transaction on Networking, 7 (5): 641-652,1999. V. Kompella et al., “Multicast routing for multimedia communication,” IEEE / ACM Transactions on Networking, Volume: 1 Issue: 3, pp.286-292, June 1993. Q. Zhu, et al., “A source-based algorithm fordelay-constrained minimum-cost multicasting,” Proc in IEEE INFOCOM '95, vol. 1, pp. 377-385, 1995. EWDjikstra, “A note on two problems in connection with graphs,” Numerische Mathematik, vol.1, pp.269-271, 1959.

  Here, the techniques introduced in the above Non-Patent Documents 1 to 3 have a problem that switching takes time because failure cannot be transmitted unless the failure is transmitted to the start node. If switching takes time, the time during which information does not reach the recipient becomes longer.

  The present invention has been carried out against such a background, and by preparing a standby transfer path for each link on the main multicast transfer path instead of the starting point, it is possible to perform active backup switching at an intermediate node, The purpose is to shorten the switching time.

  A first aspect of the present invention is a multicast transfer route setting method, and the feature of the present invention is applied to a multicast network composed of a plurality of nodes each provided with a multicast transfer device. A step of calculating a main transfer route connecting a start point and a plurality of end points by a multicast transfer route calculation device; a step of setting the calculated main transfer route by a multicast transfer route setting device; and the multicast transfer route calculation device A step of calculating a spare transfer route for each of all the links on the obtained main transfer route and a step of setting the calculated all spare transfer routes by a multicast transfer route setting device are performed (claims). 1).

  In this way, by calculating the backup transfer path for all the links of the main transfer path, when a failure occurs in the middle of the main transfer path, even if the failure does not propagate to the start node, You can switch to the transfer path.

  The multicast transfer route setting device makes a request for calculating the main transfer route and the backup transfer route to the multicast transfer route calculation device, and the multicast transfer route calculation device that has received the calculation request is based on the calculation request. The step of calculating the main transfer route and the backup transfer route, the step of notifying the multicast transfer route setting device of the calculation result, and the calculation result received by the multicast transfer route setting device that has received the notification And a step of setting a transfer path and a backup transfer path.

  Thereby, a multicast transfer route setting device and a multicast transfer route calculation device can be individually installed, and a single multicast transfer route calculation device can correspond to a plurality of multicast transfer route setting devices.

  A step of measuring the state of traffic flowing on a link in the multicast network, a step of notifying the multicast transfer route calculation device of the measurement result, and the multicast transfer route calculation device And calculating a main transfer path and a backup transfer path based on the measured result.

  As a result, route calculation reflecting the traffic situation of the network can be performed.

  Further, when the multicast transfer apparatus measures the state of traffic flowing on a link in the multicast network, the step of measuring the traffic state for each link and for each traveling direction when data flows on the link; (Claim 4).

  This makes it possible to perform route calculation reflecting the traffic situation for each link. Furthermore, since the route calculation reflecting the traffic situation can be performed for each traveling direction when data flows even in the same link, the actual traffic situation of the network can be accurately reflected.

  Further, the multicast transfer path calculation device includes a step of calculating and determining the main transfer path based on the measurement result, and a step of calculating and determining a backup transfer path for each link on the calculated main transfer path. (Claim 5).

  By calculating the backup transfer path in units of links in this way, backup transfer paths can be set for all the links in the backup transfer path.

  In addition, the multicast transfer route calculation device may include the main transfer route including a start point of the main transfer route by removing the link when calculating the preliminary transfer route for each link on the route from the obtained main transfer route. A step of dividing the path tree into two partial path trees that do not include the start point, a temporary start point that connects all the nodes included in the partial path tree including the start point, and the other part that does not include the start point The shortest path from the temporary start point to the temporary end point, excluding all nodes other than the temporary end point itself and links connected to that node from the other partial path trees that do not include the start point as the temporary end point. On the basis of the measurement result, and when the shortest route is obtained, the step of setting the obtained shortest route as a spare transfer route for the corresponding link, and finding the shortest route If not, the node adjacent to the downstream of the tree viewed from the top of the other partial path tree that does not include the start point is set as a temporary end point, and the node other than the temporary end point in the other partial path tree that does not include the start point and its node Steps for finding the shortest route from the temporary start point to the temporary end point, and if the shortest route has not yet been found by this step, The shortest point from the temporary start point to the new temporary end point except for all the nodes other than the new temporary end point and links connected to the node among the other partial path trees not including the start point as the temporary end point It is possible to execute the step of repeatedly obtaining the route until the shortest route is obtained (Claim 6).

  Thereby, the shortest route of the backup transfer route can be calculated efficiently.

  When there are a plurality of adjacent nodes of the tree viewed from other partial path trees not including the start point, and a plurality of shortest paths from the temporary start point to the plurality of nodes are obtained, A step of adopting a route having a low cost among the routes as a backup transfer route can be executed.

  As a result, a low-cost route can be used as a backup transfer route, and network operation can be performed efficiently. Here, the “low cost route” is, for example, a route with a short distance. The distance here is not limited to a physical distance, but can also be defined by the size of the band and the communication quality. In addition, the present invention does not limit the definition of cost.

  In addition, it is possible to execute a step of ending the calculation of the spare transfer path when the spare transfer path is obtained for all the links on the obtained main transfer path.

  A second aspect of the present invention is a multicast transfer path calculation device, and the feature of the present invention is applied to a multicast network composed of a plurality of nodes each provided with a multicast transfer device. There is a means for calculating a main transfer path connecting a start point and a plurality of end points, and a means for calculating backup transfer paths for all links on the main transfer path obtained by the calculation means. (Claim 9).

  The means for calculating may comprise means for calculating a main transfer path and a backup transfer path based on a measurement result of a state of traffic flowing on a link in the multicast network.

  The measurement result is a measurement result obtained by measuring a traffic state for each link and for each traveling direction when data flows through the link, and the means for calculating is based on the measurement result for each link. In addition, it is possible to provide means for calculating a backup transfer path for the main transfer path for each traveling direction when data flows through the link.

  Further, the calculating means removes the link from the obtained main transfer path when calculating the spare transfer path for each link on the path, thereby subtracting the main transfer path from the partial path tree including the start point of the main transfer path and A means for dividing into two other partial path trees not including the start point and a temporary start point connecting all nodes included in the partial path tree including the start point are created, and the other partial path trees not including the start point are generated. The measurement of the shortest path from the temporary start point to the temporary end point, excluding all nodes other than the temporary end point itself and links connected to that node from the other partial path trees that do not include the start point. Means to obtain based on the result, means to make the obtained shortest path a spare transfer route for the corresponding link when the shortest route is obtained, and not to include the start point when the shortest route is not obtained The downstream adjacent node of the tree seen from the vertex of the outer partial path tree is a temporary end point, and all of the other partial path trees not including the start point except the temporary end point and the links connected to the node are excluded. Means for obtaining the shortest route from the temporary start point to the temporary end point, and if the shortest route is not yet obtained by this means, the adjacent node of the previous temporary end point is set as a new temporary end point, and the start point is not included. Steps for obtaining a shortest path from the temporary start point to the new temporary end point by excluding all nodes other than the new temporary end point and links connected to the node from the partial path tree other than are obtained until the shortest path is obtained. Repetitive means (claim 12).

  When there are a plurality of adjacent nodes of the tree viewed from other partial path trees not including the start point, and a plurality of shortest paths from the temporary start point to the plurality of nodes are obtained, It is possible to provide means for adopting a low-cost route among the routes as the backup transfer route.

  A third aspect of the present invention is a program, and the feature of the present invention is that the information processing apparatus is configured by a plurality of nodes each provided with a multicast forwarding apparatus by being installed in the information processing apparatus. Applied to a given multicast network, a function for calculating a main transfer path connecting a given start point and a plurality of end points, and a spare transfer path for all links on the main transfer path obtained by this function And a function corresponding to a multicast forwarding path calculation device having a function for calculating the (Claim 14).

  Further, as the calculation function, a function of calculating the main transfer path and the backup transfer path based on the measurement result of the state of traffic flowing on the link in the multicast network can be realized.

  The measurement result is a measurement result obtained by measuring a traffic state for each link and for each traveling direction when data flows through the link, and as a function to calculate, for each link based on the measurement result, In addition, it is possible to realize a function of calculating a backup transfer path for the main transfer path for each traveling direction when data flows through the link.

  Further, as the function to calculate, when calculating the spare transfer route for each link on the route from the obtained main transfer route, by removing this link, the main transfer route is changed to a partial route tree including the start point of the main transfer route and Create a temporary start point connecting all the nodes included in the partial path tree including the start point and the function of dividing into two other partial path trees that do not include the start point, and other partial path trees that do not include the start point The measurement of the shortest path from the temporary start point to the temporary end point, excluding all nodes other than the temporary end point itself and links connected to that node from the other partial path trees that do not include the start point. The function to be obtained based on the result, the function to make the obtained shortest path as a spare transfer path for the corresponding link when the shortest path is found, and the start point not to be found when the shortest path is not found The downstream adjacent nodes of the tree seen from the vertices of the partial path tree other than the above are used as temporary end points, and all of the other partial path trees not including the start point other than the temporary end points and links connected to the nodes are excluded. A function for obtaining the shortest route from the temporary start point to the temporary end point, and if the shortest route is not yet obtained by this function, the adjacent node of the previous temporary end point is set as a new temporary end point and does not include the start point The shortest path is obtained in the step of obtaining the shortest path from the temporary start point to the new temporary end point by excluding all nodes other than the new temporary end point and links connected to the node from the other partial path trees. And the function of repeatedly performing the process can be realized (claim 17).

  When there are a plurality of adjacent nodes of the tree viewed from other partial path trees not including the start point, and a plurality of shortest paths from the temporary start point to the plurality of nodes are obtained, It is possible to realize a function of adopting a low-cost route as a backup transfer route among the routes (claim 18).

  A fourth aspect of the present invention is the information processing apparatus-readable recording medium on which the program of the present invention is recorded (claim 19). By recording the program of the present invention on the recording medium of the present invention, the information processing apparatus can install the program of the present invention using this recording medium. Alternatively, the program of the present invention can be directly installed on the information processing apparatus via a network from a server holding the program of the present invention.

  As a result, when data transfer is performed by multicast transfer using a general-purpose information processing device, it is possible to switch to a backup transfer path at a faulty neighboring node by having a backup link for each link at the time of link failure. Therefore, it is possible to realize a multicast transfer route calculation device that can realize high-speed switching.

  According to the present invention, when performing data transfer by multicast transfer, by having a spare link for each link at the time of a link failure, it becomes possible to switch to a spare transfer path in a neighboring node where the failure occurs, thereby realizing high-speed switching. it can.

  Hereinafter, a multicast transfer route setting method according to an embodiment of the present invention will be described with reference to the drawings.

  FIG. 1 is a diagram for explaining the outline of the present invention. The present invention is a multicast transfer route setting method for setting backup transfer routes for all links on a main transfer route. The multicast network is composed of a plurality of nodes provided with a multicast transfer route setting device, and a multicast transfer route calculation device or a multicast transfer route setting device is provided in any one of the nodes. (Claim 1).

  Then, the multicast transfer device in the network collects network measurement information indicating the data transfer delay generated in each link in each direction of data flow (1), and the multicast transfer device is a multicast transfer route calculation device or a multicast transfer route. The network measurement information is notified to the setting device (2). When the necessity of setting the transfer path of data to be transferred by multicast occurs, the setting of the main transfer path and the backup transfer path of the data is executed by the multicast transfer path setting device and the multicast transfer route calculation device according to the processing described later. (Claims 3 and 4).

  In the present invention, the multicast transfer device has a function of collecting network measurement information of data transferred between nodes, the multicast transfer route calculation device has a function of calculating a main transfer route and a backup transfer route, The multicast transfer path setting device has a function of setting a main transfer path and a backup transfer path. In addition, one node may have the functions of a plurality of the above-described devices.

  Here, when the multicast transfer route setting device and the multicast transfer route calculation device are different devices, the multicast transfer route setting device requests the multicast transfer route calculation device to calculate the main transfer route and the backup transfer route (billing). Item 2). When the multicast transfer route setting device and the multicast transfer route calculation device are the same device, the multicast transfer route setting device instructs its route calculation module to perform main transfer route calculation and backup transfer route calculation.

  Then, the route calculation module of the multicast transfer route setting device or the multicast transfer route calculation device calculates the main transfer route and the backup transfer route based on the collected information (5). Then, the calculation result is notified to the route setting module of the multicast transfer route setting device (6), and the multicast transfer route setting device that has received the calculation result sets the main transfer route and the backup transfer route of the data.

In the above-described function of collecting network measurement information, OSPF-TE (Open Shortest Path First-Traffic Engineering) and IS-IS-TE (Intermediate) have been proposed.
Network measurement information is collected by expanding and using a route calculation protocol equipped with a function for exchanging network measurement information between adjacent nodes such as System-Intermediate System-Traffic Engineering).

  In addition, the multicast transfer path calculation device has a function of receiving network measurement information from the multicast transfer device, a packet transfer function of transmitting calculation results of the main transfer path and the backup transfer path, and calculation of the main transfer path and the backup transfer path. Programs that implement the algorithms used, network measurement information, main transfer path and backup transfer path calculation programs, storage media that store main transfer paths and backup transfer path calculation results, and main transfer paths and backup transfer path calculations And a path calculation function to be executed.

  The main transfer path calculation program used in the present invention uses a program in which a known algorithm is installed. Another object of the spare transfer path program used in the present invention is to calculate a spare transfer path for each link on the determined main transfer path.

  When calculating the preliminary transfer route of the link on the route from the obtained main transfer route, the corresponding link is excluded, so that the main transfer route is changed to the partial route tree including the start point of the main transfer route and the other partial routes not including the start point. Create a temporary start point that connects to all nodes included in the partial path tree that includes the start point, sets the vertices of other partial path trees that do not include the start point as temporary end points, and does not include the start point Except for all nodes other than the temporary end point in the partial path tree and all links connected to the node, the shortest path from the temporary start point to the temporary end point is determined by a known shortest path algorithm based on the measurement result. Ask.

  If the shortest route is obtained, the obtained shortest route is set as a preliminary transfer route for the corresponding link. If the shortest route is not obtained, the tree is viewed from the top of the other partial route tree not including the start point. The shortest distance from the temporary start point to the temporary end point, excluding all nodes other than the temporary end point and the links connected to the node among the other partial path trees not including the start point as the temporary end point The route is obtained by a known shortest route algorithm.

  If the shortest path cannot be obtained, the adjacent node of the temporary end point is set as the temporary end point, and is connected to the node other than the temporary end point in the other partial path tree that does not include the start point and the node. The shortest path from the temporary start point to the temporary end point is obtained by removing all links. This is repeated until one shortest path is obtained (claim 6).

  At this time, when there are a plurality of adjacent nodes of the tree viewed from other partial path trees not including the start point, and a plurality of shortest paths from the temporary start point to the plurality of nodes are determined, the plurality of the determined nodes are determined. Among the shortest routes, a route having a low cost is adopted as a backup transfer route. The calculation of the spare transfer path is terminated when the spare transfer path is obtained for all the links on the obtained main transfer path.

  Next, a multicast transfer route calculation device and a multicast transfer route setting device necessary for realizing the multicast transfer route setting method of the present invention will be described. FIG. 2 is a diagram showing a configuration of a multicast transfer route calculation apparatus (claim 9). The multicast transfer path calculation apparatus shown in FIG. 2 calculates an information management unit 20 that manages network measurement information related to delays and costs that occur in nodes in the network and links that connect the nodes, and a main transfer path and a backup transfer path. The path calculation unit 30 and the packet processing unit 40 that processes packets to be transmitted and received are configured. The packet processing unit 40 of the multicast transfer route calculation device receives the network measurement information and the route calculation request managed by the information management unit 20, and the calculation result of the main transfer route and the backup transfer route calculated by the route calculation unit 30. Transmission to the multicast transfer route setting device.

  In addition, the information management unit 20 of the multicast transfer path calculation device obtains the routing protocol module 21 for processing the information exchange protocol used in the routing protocol such as OSPF and IS-IS used for collecting the traffic state information and the protocol. And a measurement information storage unit 22 for managing network measurement information such as topology delay and cost of the received network. The route calculation unit 30 includes a route calculation processing module 31 that calculates a main transfer route and a backup transfer route, and a calculation result storage unit 32 that stores a calculation result.

  The packet processing unit 40 also determines the type of the packet that has arrived, transfers the packet or sends the packet to the information management unit, a packet transfer table storage unit 42 that records the packet transfer destination, a network And an interface 43.

  FIG. 3 is a diagram showing the configuration of the multicast transfer path setting device. The multicast transfer path setting device shown in FIG. 3 includes an information management unit 50 that manages information about delays and costs that occur in nodes and links in the network, and a measurement unit 60 that measures delays and costs that occur due to its own processing. And a route setting protocol processing unit 70 for setting a route when a new data flow occurs, and a packet processing unit 80 for processing an incoming packet.

  The basic configuration of the information management unit 50 is the same as that of the information management unit 20 of the multicast transfer path calculation device, and includes a routing protocol module 51 and a measurement information storage unit 52. The measurement unit 60 also includes a measurement module that measures information such as the state of the network interface 83 provided in the packet processing unit 80 and the processing delay of each node on the network.

  Further, the packet processing unit 80 determines the type of the packet that has arrived, transfers the packet, determines whether to determine a new route setting, and a packet transfer table that records the transfer destination of the packet A storage unit 82 and a network interface 83 are provided. In addition, the multicast transfer route setting device includes a route calculation unit 90. The route calculation unit 90 calculates a main transfer route and a backup transfer route, and a calculation result storage unit 92 that stores a calculation result. And. When the multicast transfer route setting device performs calculation of the main transfer route and the backup transfer route, the route calculation unit 90 performs the same processing as the multicast transfer route calculation device.

  The route setting protocol processing unit 70 receives a request for setting a main transfer route and a backup transfer route from the packet processing unit 80, and transmits the route setting request to the multicast transfer route calculating device. Further, the route setting protocol processing unit 70 sets a main transfer route for data transfer and a spare transfer route for handling a link failure according to the calculation result of the main transfer route and the backup transfer route received from the multicast transfer route calculation device. It has the function to do.

  When the multicast transfer route calculation device and the multicast transfer route setting device are the same node, the node includes the processing units of the multicast transfer route calculation device and the multicast transfer route setting device, and each of the processing units described above Perform the following process. When the function of the multicast transfer apparatus is provided in the same node, the route setting protocol processing unit 70 requests a route calculation to an adjacent node.

  Next, operations of the multicast transfer route calculation device, the multicast transfer route setting device, and the multicast transfer device will be described. A node having the function of a multicast transfer device in the network always exchanges network measurement information representing the network topology, delay and cost between adjacent nodes. Each node stores the network measurement information obtained by the exchange process.

  The network measurement information exchanged by a node includes not only network measurement information measured by the own node but also network measurement information measured by other nodes held by the own node. With these exchange 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 route setting device that newly sets the main transfer route and the backup transfer route makes a route calculation request to the node having the function of the multicast transfer route calculation device.

  At this time, the node having the function of the multicast transfer route calculation device is the network measurement information related to the traffic such as the topology and delay in the network managed by the information management unit 20, and the end point sent from the node that requested the route calculation. Based on the information, the main transfer path and its backup transfer path are calculated (claim 10). At this time, the network measurement information is a measurement result obtained by measuring the traffic state for each link and for each traveling direction when data flows through the link, and for each link based on the measurement result, A backup transfer path for the main transfer path is calculated for each traveling direction when data flows on the link.

  FIG. 4 is a flowchart showing a process for calculating a preliminary transfer route in the multicast transfer route calculating apparatus. First, the multicast transfer route calculation device accepts a main route calculation and a backup transfer route calculation request from a node having the function of the multicast transfer route setting device. At this time, the multicast transfer path calculation device accepts data transfer end point information from the multicast transfer path setting device. Then, the route calculation unit 30 of the multicast transfer route calculation apparatus reads the network measurement information indicating the network topology and traffic state recorded in the measurement information storage unit 22 of the information management unit 20 (step S1).

  Then, the route calculation processing module 31 uses the network measurement information to calculate a main transfer route having a minimum sum of costs from the start point to the end point of data transfer using a known main transfer route algorithm (step S2). ). At this time, the route calculation processing module 31 calculates the main transfer route having the minimum cost sum to all nodes at the end point of data transfer, starting from the node that sent the route calculation request. As an algorithm for obtaining the main transfer path, for example, an algorithm known from Non-Patent Document 4 or 5 is used.

  Next, the route calculation processing module 31 of the multicast transfer route calculation device obtains a spare transfer route for each link on the main transfer route obtained in step S2 for all links. A preliminary transfer path for a certain link on the main transfer path is obtained in steps S3 to S9. Since the preliminary transfer path is obtained for all links, steps S3 to S9 are performed for all links.

  When finding a preliminary transfer path of a link by paying attention to a link on the main transfer path, the focused link is deleted from the main transfer path, and the main transfer path is changed to a partial path tree including the start point of the main transfer path and the start point. Is divided into two other partial path trees that do not include (step S3). A temporary start point connecting all nodes included in the partial path tree including the start point is created (step S4). The vertex of the partial path tree not including the start point is set as a temporary end point (step S5). The shortest path from the temporary start point to the temporary end point is obtained by excluding all nodes other than the temporary end point and the links connected to the node from the partial path tree not including the start point (step S7). When obtaining the shortest path in step S7, for example, a known algorithm is used according to Non-Patent Document 6.

  If the shortest path is obtained in step S7 (step S8), the calculation of the spare transfer path for the focused link is terminated (step S9). If the shortest path cannot be obtained in step S7 (step S8), the downstream adjacent node of the temporary end point tree is set as the temporary start point (step S6). However, when there are a plurality of downstream adjacent nodes of the temporary end point tree, steps S6 to S7 are repeated for each downstream adjacent node as temporary end points one by one (claim 12).

  At this time, when there are a plurality of adjacent nodes of the tree viewed from other partial path trees not including the start point, and a plurality of shortest paths from the temporary start point to the plurality of nodes are determined, Among the shortest routes, the route with the lowest cost is adopted as the backup transfer route.

  Finally, the route calculation processing module 31 returns the result of the preliminary transfer route obtained by the calculation in this way to the node that issued the route calculation request via the packet processing unit 40.

  In the present embodiment, OSPF-TE is used when the multicast transfer apparatus collects network measurement information such as delay. OSPF-TE is a transfer protocol in which traffic information in the network such as a delay is stored in OSPF topology information exchange information which is a unicast routing protocol.

In the present embodiment, as a protocol for setting a data transfer route, a multicast MPLS (Multicast MPLS) (Multicast MPLS) that extends RSVP-TE (Resource Reservation Protocol-Traffic Engineering) that performs explicit route designation is used.
Protocol Label Switching) protocol is used. Multicast MPLS is an LSP (Label) compared to RSVP-TE used in normal MPLS.
This is a technique in which an information element that can store a tree topology is added to a message that generates (Switched Path), and a Point-to-Multipoint LSP can be established along the topology information.

  Next, an embodiment of a process for calculating a transfer route according to the present invention will be described. FIG. 5 shows a multicast network. In this figure, P is the start point of data transfer and is also a multicast transfer setting device. R1 to R4 are the end points of data transfer. N1 to N10 are intermediate nodes between the start point and the end point, and have the function of a multicast transfer device. The multicast transfer setting device P, the nodes N1 to N10, and the end points R1 to R4 are connected by a transfer cable (link) to form a multicast network. Each link has two characteristics, delay and cost.

  Then, the multicast transfer route setting device P transfers data to the end points R1 to R4 based on the result calculated by the multicast transfer route calculation device C.

  When receiving the route calculation request from the multicast transfer route setting device P, the multicast transfer route calculation device C calculates the main transfer route, and receives the result to calculate the backup transfer route. An example in which the multicast transfer path setting device P calculates a backup transfer path for links N1 to N9 is shown.

  First, as shown in FIG. 6, the links N1 to N9 are deleted and divided into two partial path trees including the start point of the main transfer path and other partial path trees not including the start point. Next, as shown in FIG. 7, a temporary start point that connects all the nodes included in the partial path tree including the start point is created. Next, as shown in FIG. 8, the vertex of the partial path tree that does not include the start point is used as a temporary end point, and the nodes other than the temporary end point in the partial path tree that does not include the start point and all links connected to the node are excluded. Thus, the shortest path from the temporary start point to the temporary end point is obtained. At this time, the link costs of the links connecting all the nodes included in the partial path tree including the start point from the temporary start point may be the same value or different values. However, based on the cost, for example, the shortest path is obtained using a known algorithm according to Non-Patent Document 6. In this example, as shown in FIG. 9, since the shortest path is obtained, the calculation of the spare transfer path for the links from N1 to N9 is completed, and the spare transfer path obtained is N2 → N5 → N7 → N9.

  For example, in the case of a multicast network as shown in FIG. 10, even if an attempt is made to obtain a spare transfer path for links N1 to N9, the shortest path from the temporary start point to the apex (N9) of the partial path tree not including the start point is not found. Steps S6 to S7 shown in FIG. 4 are repeated the number of downstream nodes (in this example, twice) from the downstream adjacent nodes (N10, N8) of the vertex tree as temporary end points. If the shortest route is found here, the calculation of the backup transfer route is completed. FIG. 11 shows an example in which the shortest path from the temporary start point is calculated with N10 as the temporary end point.

  The present invention can be implemented as a program that, when installed in a general-purpose information processing device, causes the information processing device to realize a function corresponding to the multicast transfer path calculation device of the present invention (claims 14 to 18). This program is recorded on a recording medium and installed in the information processing device (claim 19), or installed in the information processing device via a communication line, so that the information management unit 20, route calculation is performed in the information processing device. The function corresponding to each of the unit 30 and the packet processing unit 40 can be realized.

  According to the present invention, when performing data transfer by multicast transfer, by having a spare link for each link at the time of a link failure, it becomes possible to switch to a spare transfer path in a neighboring node where the failure occurs, thereby realizing high-speed switching. it can. Thereby, it can contribute to the service quality improvement of a network user.

The conceptual diagram of this invention. The block diagram of the multicast transfer path | route calculation apparatus of a present Example. 1 is a configuration diagram of a multicast transfer route setting device of an embodiment. FIG. The flowchart of the transfer route calculation algorithm of a present Example. The figure which shows the example of a multicast network. The figure which shows the result divided | segmented into two partial path | route trees. The figure which shows a mode that the temporary start point was created. The figure which shows a mode that a temporary end point is produced and the shortest path | route is calculated | required. The figure which shows the obtained backup transfer path | route. The figure which shows the example of a multicast network. The figure which shows a mode that the shortest path | route is calculated | required from a temporary start point. The figure which compares a unicast transfer and a multicast transfer.

Explanation of symbols

20, 50 Information management unit 21, 51 Routing protocol module 22, 52 Measurement information storage unit 30, 90 Route calculation unit 31, 91 Route calculation processing module 32, 92 Calculation result storage unit 40, 80 Packet processing unit 41, 81 Packet transfer Processing module 42, 82 Packet transfer table storage unit 43, 83 Network interface 60 Measuring unit 70 Route setting protocol processing unit C Multicast transfer route calculation device P Multicast transfer route setting device N1 to N10 Nodes R1 to R4 End point

Claims (19)

Applied to a multicast network composed of a plurality of nodes each provided with a multicast forwarding device,
Calculating a multicast main transfer path (hereinafter referred to as a main transfer path) connecting a given start point and a plurality of end points by a multicast transfer path calculation device;
A step of the multicast transfer path setting device setting the calculated main transfer path;
Calculating a multicast preliminary transfer path (hereinafter referred to as a preliminary transfer path) for all links on the main transfer path obtained by the multicast transfer path calculation device;
And a step of setting all the calculated preliminary transfer paths by a multicast transfer path setting device. The multicast transfer route setting device making a request for calculation of a main transfer route and a backup transfer route to the multicast transfer route calculation device;
The multicast transfer path calculation device that has received this calculation request calculates the main transfer path and the backup transfer path based on the calculation request;
Notifying the multicast forwarding route setting device of the calculation result;
The multicast transfer route setting method according to claim 1, wherein the multicast transfer route setting device that has received the notification executes a step of setting a main transfer route and a backup transfer route according to the calculation result received. Measuring the state of traffic flowing on a link in the multicast network by the multicast forwarding device;
Notifying the measurement result to the multicast forwarding path calculation device;
The multicast transfer path setting method according to claim 1, wherein the multicast transfer path calculation device performs a step of calculating a main transfer path and a backup transfer path based on the notified measurement result. When measuring the state of traffic flowing on the link in the multicast network, the multicast transfer device,
The multicast transfer path setting method according to claim 3, wherein the step of measuring the traffic state is performed for each link and for each traveling direction when data flows through the link. The multicast transfer path calculation device
Calculating and obtaining the main transfer path based on the measurement result;
The multicast transfer route setting method according to claim 3 or 4, wherein the step of calculating and obtaining a spare transfer route for each link on the calculated main transfer route is executed. The multicast transfer path calculation device
When calculating the spare transfer route for each link on the route from the obtained main transfer route, by removing this link, the main transfer route is divided into a partial route tree including the start point of the main transfer route and the other points not including the start point. Dividing the partial path tree into two parts;
A temporary start point connecting all nodes included in the partial path tree including the start point is created, the vertices of the other partial path tree not including the start point are set as temporary end points, and the other partial path trees not including the start point are included. The step of obtaining the shortest path from the temporary start point to the temporary end point based on the measurement result, excluding all the nodes other than the temporary end point and the link connected to the node,
When the shortest route is obtained, a step of setting the obtained shortest route as a spare transfer route for the corresponding link;
If the shortest path cannot be obtained, the downstream adjacent node of the tree viewed from the top of the other partial path tree not including the start point is set as a temporary end point, and the temporary end point of the other partial path trees not including the start point Excluding all other nodes and links connected to the node, and obtaining a shortest path from the temporary start point to the temporary end point;
If the shortest route is not yet obtained by this step, the adjacent node of the previous temporary end point is set as a new temporary end point, and the nodes other than the new temporary end point in the other partial path trees not including the start point 6. A multicast transfer route according to claim 5, wherein the step of obtaining a shortest route from the temporary start point to the new temporary end point, excluding all links connected to the node is repeated until the shortest route is obtained. Setting method.   When there are a plurality of adjacent nodes of the tree viewed from other partial path trees not including the start point, and a plurality of shortest paths from the temporary start point to the plurality of nodes are determined, the plurality of the shortest paths determined The multicast transfer route setting method according to claim 6, wherein a step of adopting a route having a low cost as a backup transfer route is executed.   7. The multicast transfer path setting method according to claim 6, wherein a step of ending calculation of the backup transfer path is executed for the links on the determined main transfer path when the backup transfer path is determined. Applied to a multicast network composed of a plurality of nodes each provided with a multicast forwarding device,
Means for calculating a main transfer path connecting a given start point and a plurality of end points;
A multicast transfer path calculation apparatus comprising: means for calculating backup transfer paths for all links on the main transfer path obtained by the calculation means.   10. The multicast transfer path calculation device according to claim 9, wherein said calculating means includes means for calculating a main transfer path and a backup transfer path based on a measurement result of a state of traffic flowing on a link in the multicast network. The measurement result is a measurement result obtained by measuring a traffic state for each link and for each traveling direction when data flows through the link.
The multicast according to claim 10, wherein the means for calculating comprises means for calculating a spare transfer path for the main transfer path for each link based on the measurement result and for each traveling direction when data flows through the link. Transfer route calculation device. The means for calculating is
When calculating the preliminary transfer route for each link on the route from the obtained main transfer route, by removing this link, the main transfer route is divided into a partial route tree including the start point of the main transfer route and the other portion not including the start point. Means to divide the path tree into two,
A temporary start point connecting all nodes included in the partial path tree including the start point is created, the vertices of the other partial path tree not including the start point are set as temporary end points, and the other partial path trees not including the start point are included. Means for obtaining the shortest path from the temporary start point to the temporary end point based on the measurement result, excluding all of the nodes other than the temporary end point and the links connected to the node,
When the shortest route is obtained, a means for setting the obtained shortest route as a spare transfer route for the corresponding link;
If the shortest path cannot be obtained, the downstream adjacent node of the tree viewed from the top of the other partial path tree not including the start point is set as a temporary end point, and the temporary end point of the other partial path trees not including the start point Means for obtaining a shortest path from the temporary start point to the temporary end point, excluding all nodes other than and links connected to the node;
If the shortest path is not yet determined by this means, the adjacent node of the previous temporary end point is set as a new temporary end point, and the nodes other than the new temporary end point in the other partial path trees not including the start point And a means for repeating the step of obtaining the shortest route from the temporary start point to the new temporary end point except for all links connected to the node until the shortest route is obtained. Computing device.   When there are a plurality of adjacent nodes of the tree viewed from other partial path trees not including the start point, and a plurality of shortest paths from the temporary start point to the plurality of nodes are determined, the plurality of the shortest paths determined 13. The multicast transfer path calculation device according to claim 12, further comprising means for adopting a low-cost path as a backup transfer path. By installing on an information processing device,
Applied to a multicast network composed of a plurality of nodes each provided with a multicast forwarding device,
A function for calculating a main transfer path connecting a given start point and a plurality of end points;
A program characterized by realizing a function corresponding to a multicast transfer path calculation device having a function of calculating backup transfer paths for all links on the main transfer path obtained by the function of calculating.   15. The program according to claim 14, wherein the calculation function realizes a function of calculating a main transfer path and a backup transfer path based on a measurement result of a state of traffic flowing on a link in a multicast network. The measurement result is a measurement result obtained by measuring a traffic state for each link and for each traveling direction when data flows through the link.
16. The program according to claim 15, wherein the calculation function realizes a function of calculating a backup transfer path for the main transfer path for each link based on the measurement result and for each traveling direction when data flows through the link. . As the function to calculate,
When calculating the preliminary transfer route for each link on the route from the obtained main transfer route, by removing this link, the main transfer route is divided into a partial route tree including the start point of the main transfer route and the other portion not including the start point. A function that divides the path tree into two,
A temporary start point connecting all nodes included in the partial path tree including the start point is created, the vertices of the other partial path tree not including the start point are set as temporary end points, and the other partial path trees not including the start point are included. A function for obtaining the shortest path from the temporary start point to the temporary end point based on the measurement result, excluding all the nodes other than the temporary end point and the links connected to the node,
When the shortest route is found, a function that makes the found shortest route a spare transfer route for the corresponding link;
If the shortest path cannot be obtained, the downstream adjacent node of the tree viewed from the top of the other partial path tree not including the start point is set as a temporary end point, and the temporary end point of the other partial path trees not including the start point A function for obtaining the shortest path from the temporary start point to the temporary end point, excluding all other nodes and links connected to the node;
If the shortest path is not yet obtained by this function, the adjacent node of the previous temporary end point is set as a new temporary end point, and the node other than the new temporary end point among the other partial path trees not including the start point The program according to claim 16, further comprising: a function that repeats a step of obtaining a shortest path from the temporary start point to the new temporary end point except for all links connected to the node until the shortest path is obtained.   When there are a plurality of adjacent nodes of the tree viewed from other partial path trees not including the start point, and a plurality of shortest paths from the temporary start point to the plurality of nodes are determined, the plurality of the shortest paths determined 18. The program according to claim 17, which realizes a function of adopting a low-cost route as a backup transfer route.   19. A recording medium readable by the information processing apparatus, on which the program according to claim 14 is recorded.

Images