Routing device

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Technical field to which the invention belongs]

The present invention is used for communication performed via a plurality of communication nodes constituting a communication network. The present invention is used to select the shortest route in the communication network. In particular, the present invention relates to a technique for selecting the shortest route that bypasses an unusable route.

【0002】

[Conventional technology]

In order to communicate via the communication network, it is necessary to select a route between the transmitting end and the receiving end. Information transfer methods include circuit switching and packet switching (datagram). In the case of circuit switching, the route is selected by using the destination address notified by the line setting signal at the time of line setting. In the case of packet switching, the route is selected using the destination address in the header of the packet. Even in the case of packet switching, when a virtual line (virtual circuit) is set without using a datagram, the route is selected at the time of line setting.

【0003】

Both circuit switching and packet switching are roughly classified into two methods according to the timing of route selection. One is a method of selecting a route hop-by-hop, and the other is a method of specifying a route to a destination address at the transmitting end edge node of the communication network. Here, hop-by-hop is a method of sending a setup message for connection connection to a communication node, and the communication node sequentially selects the next route having a margin in the band described in the setup message. Further, the edge node refers to a communication node at the transmitting end or the receiving end.

【0004】

The latter method is called source routing, and in order to do this, it is premised that the transmitting edge node knows the topology of the communication network. Here, the relay method by source routing is a method of relaying via a bridge, a LAN, or the like indicated by the routing information following the source address. The edge node at the transmitting end selects the shortest route to the destination based on the topology information of the communication network and sets the route.

【0005】

A typical example of source routing is PNNI (Private Network-Network Interface), which was specified by the ATM forum. In addition, the header format has been determined so that source routing is possible even with IPv6, which is the standard for the next-generation Internet protocol (reference name is RFC1883). In addition, the burst circuit switching network invented by the applicants of the present application also performs source routing at the edge node at the transmitting end (Japanese Patent Application No. 9-334444, unpublished at the time of filing the application of the present application).

【0006】

[Problems to be Solved by the Invention]

As already explained, the transmitting edge node needs to know the topology of the communication network when performing source routing. However, communication may not be possible if the edge node routes with the old topology information before the link failure occurs and the information is propagated to the edge node. Also, if a link on the route is being used by another user, you must wait until the link becomes available.

【0007】

In such a case, in order to continue the communication, it is conceivable to calculate the detour route at the communication node in the middle of the route. The conventional problems will be described with reference to FIGS. 5 to 9. FIG. 5 is a diagram showing a conventional detour selection method. FIG. 6 is a diagram showing an example of a communication network. FIG. 7 is a diagram showing an example of a communication network in which a failure has occurred. FIG. 8 is a diagram showing an example of another communication network. FIG. 9 is a diagram showing an example of another communication network in which a failure has occurred.

【0008】

In FIG. 5, the communication node B is on the shortest path from the communication node A to C. In the figure, only communication nodes A, B, and C are shown, but other communication nodes are not shown. Here, the shortest path from the communication node B to the communication node C forms a part of the shortest path from the communication node A to C. Here, if the link from the communication node B to the communication node C cannot be used, the communication node B may calculate the second shortest path between the communication nodes B and C and select the route. .. However, with this method, a closed route may be created as shown below, and the desired destination address may not be reached.

【0009】

FIG. 6 is a network consisting of communication node A to communication node L and link 1 to link 16. Considering the route selection from the communication node A to the communication node E, assuming that the length of each link is the same, the shortest route is ABCDE. Communication node A, which is the transmitting edge node, selects this shortest path and starts communication. Here, as shown in FIG. 7, when the link 3 connecting the communication node B and the communication node C cannot be used due to congestion or failure, the communication node B is the shortest path to the communication node E. Cannot be used, so reselect BFGDE, which is the second shortest path from communication node B to communication node E.

【0010】

Next, when the communication node F is reached, if the link 8 connecting the communication node F and the communication node G cannot be used, the communication node F is the second shortest path from the communication node F to the communication node E. Reselect FHBCDE. However, since the link 3 connecting the communication node B and the communication node C cannot be used, when returning to the communication node B, the route to the communication node F is selected again, and a closed route is created.

【0011】

FIG. 8 is another example, in which the communication node G, the link 8 and the link 9 are removed from the network of FIG. In this example, as shown in FIG. 9, when it is found that the link 3 cannot be used on the communication node B, the route to the communication node F is selected, but the communication node F knows that the link 3 cannot be used. Otherwise, the second shortest path, FHB, will be selected and a closed path will be created as shown in Fig. 9. The reason why such a closed route is created is that the communication node that selects the route does not know the state other than the link directly connected to the communication node.

【0012】

The applicant of the present application, in accordance with Japanese Patent Application No. 10-112347 (unpublished at the time of filing the application of the present application, hereinafter referred to as the prior application), each communication node notifies each other of the availability of the link due to congestion or failure of the link. We have proposed a route selection device that virtually reproduces the topology of the communication network and selects the shortest route according to the topology of this virtually reproduced communication network for the communication node at the transmitting end. We have decided to make a more detailed proposal on a technique for avoiding the occurrence of the closed route when the communication node at the transmitting end selects the shortest route without knowing the occurrence of the above.

【0013】

The present invention has been made in such a background, and it is an object of the present invention even within the signal propagation delay time from the time when the link is congested or the failure occurs until the information is transmitted between the communication nodes. An object of the present invention is to provide a route selection device capable of selecting a route to a destination.

【0014】

[Means for solving problems]

According to the present invention, the availability status of a link is notified to each other between the nodes, and when the link becomes unusable due to congestion or failure, this is reflected in the topology information of the network of each node. When creating the route information, the edge node on the transmitting side constructs a virtual network by removing the link from the topology information of the network and calculates the shortest route.

【0015】

In addition, since the route of temporary interruption may be calculated until the information that the link becomes unavailable is transmitted to the edge node, in preparation for that case, the same applies to the node in the middle of the route. Create a virtual network and recalculate the shortest path to the destination. When it learns that a link on that path is unavailable, the node configures a virtual network by removing the link from the network topology information, and from that virtual network between the sender and the receiver. Of the route information, all the nodes sandwiched from the sender to the link and the links directly connected to those nodes are removed. In the virtual network thus created, the shortest path from the node immediately before the disabled link to the destination is calculated. Of the route information between the sender and the receiver in the route information, the route information from the node immediately before the disabled link to the destination is replaced with the newly calculated route information, and the route selection is continued. I will go.

【0016】

That is, the present invention is a route selection device, which includes a plurality of communication nodes and a plurality of links connecting the plurality of communication nodes to each other, and the communication node can use the links connected to itself. According to the means for determining the state regardless of the presence or absence of communication, the means for mutually notifying the determination result of the determination means among the plurality of communication nodes, and the availability status notified by the means for notifying each other. A means for virtually reproducing the topology of the communication network, and a communication node at the transmitting end is a means for selecting a route from the transmitting end to the receiving end on the communication network virtually reproduced by the reproducing means. It is a route selection device including a means for generating designated route information written in a packet to be transferred according to the information of the route selected by the selection means.

【0017】

Here, a feature of the present invention is that the means for virtually reproducing the topology of the communication network is a communication node that has passed a packet to be transferred that arrives at the own communication node and a link that directly connects to the communication node. And, including a topology update means that virtually reproduces the topology of the communication network from which congestion or failure links have been removed, the specified route information of packets arriving at the own communication node to be transferred is updated according to the update result of this topology update means. It is in a place equipped with means to do so.

【0018】

The means for virtually reproducing the topology of the communication network may be configured to include a means for updating the topology each time the availability state of the link is changed, or the topology of the communication network may be virtually reproduced. By configuring the means to periodically update the topology regardless of the change in the availability state of the link, the topology of the virtually reproduced communication network is made the same as the actual communication network. be able to.

【0019】

The means for selecting the route can select the shortest route by including means for selecting the route in order from the route having the smallest number of relay communication nodes.

【0020】

BEST MODE FOR CARRYING OUT THE INVENTION

Embodiments of the invention will be described with reference to FIGS. 1 and 2. FIG. 1 is a block configuration diagram of a main part of the route selection device according to the embodiment of the present invention. FIG. 2 is a diagram showing a failure example of a communication network for explaining the first embodiment of the present invention.

【0021】

As shown in FIG. 2, the present invention includes a plurality of communication nodes A to L and a plurality of links 1 to 16 for interconnecting the plurality of communication nodes A to L, and the communication nodes A to L are provided. , The usability determination unit 21, which is a means for determining the usability status of the link connected to itself regardless of the presence or absence of communication, and the determination result of this usability determination unit 21 are mutually determined between a plurality of communication nodes A to L. The availability notification unit 22, which is a means for notifying each other, and the virtual communication network configuration unit 23, which is a means for virtually reproducing the topology of the communication network according to the availability status notified by the availability notification unit 22. The communication node A at the transmission end is provided with a route selection unit 24, which is a means for selecting a route from the transmission end to the reception end on the communication network virtually reproduced by the virtual communication network configuration unit 23, and a route selection unit. It is a route selection device including a designated route information generation unit 25 which is a means for generating designated route information written in a packet to be transferred according to the route information selected by the unit 24.

【0022】

Here, the feature of the present invention is that the virtual communication network configuration unit 23 determines the communication node through which the packet to be transferred that arrives at the own communication node has passed so far, the link directly connected to the communication node, and the congestion or failure link. The topology of the removed communication network is virtually reproduced, and the designated route information generation unit 25 updates the designated route information of the packet to be transferred that arrives at the own communication node according to the update result of the virtual communication network configuration unit 23. There is.

【0023】

In the embodiment of the present invention, the virtual communication network configuration unit 23 updates the topology of links 1 to 16 each time the availability status is changed. As another example, the topology may be updated periodically regardless of the change in the availability status of links 1 to 16. The route selection unit 24 selects routes in ascending order of the number of relay communication nodes.

【0024】

Further, packet communication is performed by the communication device 30. At this time, the availability information of the link is input from the communication device 30 to the availability determination unit 21. Further, the destination information of the packet to be transferred is input from the communication device 30 to the route selection unit 24. Further, the availability notification information from the availability notification unit 22 to the other communication node is transferred to the other communication node via the communication device 30. After the route selection unit 24 selects a route according to the destination information of the packet to be forwarded, the designated route information generation unit 25 generates the designated route information according to the selected route and inputs it to the communication device 30. The communication device 30 forwards the packet to be forwarded according to the input designated route information. In addition, this designated route information is also forwarded as header information of the packet to be forwarded.

【0025】

[Example]

(First Example) The first embodiment of the present invention will be described with reference to FIGS. 2 and 3. FIG. 3 is a diagram for explaining the first embodiment of the present invention. In FIG. 2, in the communication network of FIG. 6, when the link 3 between the communication node B and the communication node C and the link 8 between the communication node F and the communication node G become unavailable, from the communication node A Suppose you want to select a route to communication node E.

【0026】

First, as normal operation, the fact that link 3 and link 8 have become unusable is reflected in the network topology information of each communication node by notifying each other of each other. To propagate the disabled information of the link to all the nodes in the network, see section 5.3 (pp418-433) in Data Networks (2nd ed., Prentice Hall, 1992) by D. Bertsekas and R. Gallagar et al. ), Etc. can be used.

【0027】

To explain this method very simply, when a failure occurs in an adjacent link of a communication node, the communication node puts the link number in a message and broadcasts to a link other than the failed link. .. The communication node adjacent to the communication node that received the message broadcasts the message to a link other than the link that received the message. At this time, in order to prevent duplicate messages notifying the same information, a message number is assigned to the message, the message is identified, and if the message has already been received, it is not broadcast to other communication nodes. In this way, the information of the fault link is propagated in the communication network.

【0028】

Based on the information that the link is unusable obtained in this way, node A is based on the topology information of the virtual communication network in which link 3 and link 8 are removed from the topology information of the complete communication network. Calculate the shortest route from node A to node E. At node A, ABHIJKLDE is created as route information and route selection is performed. This allows the shortest route to be selected without using the disabled links.

【0029】

Next, after link 3 and link 8 become unavailable, communication node A selects ABCDE as the shortest path to communication node E before this information is propagated to communication node A. This case will be described.

【0030】

Since communication node A does not know that link 3 and link 8 have become unusable, ABCDE is selected as the shortest path from node A to node E using the topology information of the communication network. Next, when the packet arrives at communication node B, communication node B knows that link 3 is unavailable, so it creates a virtual network image with communication node A and link 2 and link 3 removed. , Calculate the shortest path from communication node B to communication node E.

【0031】

Since BFGDE is the shortest path in the virtual network, ABFGDE, which is the original route information ABCDE in which the BCDE part is replaced with BFGDE, is used as the new route information.

【0032】

Next, as shown in FIG. 3, when the packet arrives at the communication node F, the communication node F knows that the link 8 is unavailable, so that the communication nodes A, B, links 1, 2, Create a virtual network image with 3, 7, 10 and link 8 removed, and calculate the shortest path from communication nodes F to E. Since FHIJKLDE is the shortest route in the virtual network, the route information ABFGDE at the time of arrival at the communication node F, in which the FGDE part is replaced with FHIJKLDE, is used as the new route information.

【0033】

In this way, the shortest path from the communication node A to the communication node E is selected even if the link 3 and the link 8 are unavailable and the communication node A and the communication node B do not know the information, respectively. be able to.

【0034】

(Second Example) The second embodiment of the present invention will be described with reference to FIG. FIG. 4 is a diagram for explaining a second embodiment of the present invention. In the second embodiment of the present invention, in the communication network shown in FIG. 8, the communication node A reaches the communication node E after the link 3 becomes unavailable and before this information is propagated to the communication node A. The case where ABCDE is selected as the shortest route of is described.

【0035】

Since communication node A does not know that link 3 has become unusable, ABCDE is selected as the shortest path from node A to node E using the topology information of the communication network. Next, when the packet arrives at communication node B, communication node B knows that link 3 is unavailable, so it creates a virtual network image with communication node A and link 2 and link 3 removed. , Calculate the shortest path from communication node B to communication node E.

【0036】

Since BFHIJKLDE is the shortest path in the virtual network, ABFHIJKLDE, which is the original route information ABCDE in which the BCDE part is replaced with BFHIJKLDE, is used as the new route information. After that, it will be routed according to that route.

【0037】

In this way, the shortest route from the communication node A to the communication node E can be selected even if the link 3 is unavailable and the communication node A and the communication node B do not know the information, respectively.

【0038】

(Summary of Examples) As described above, in the conventional route selection device, a closed route may be created when a link in the middle cannot be used due to congestion or failure. This happens because the communication node that selects the route does not know the state other than the link directly connected to the communication node. In the present invention, even if a link in the middle becomes unusable due to congestion or failure, a virtual communication node that has passed so far, a link related thereto, and a link that is known to be unusable are removed. By reselecting the shortest route in a typical communication network, even if the link in the middle becomes unusable due to congestion or failure, the route to the target destination is correctly selected without selecting the closed route. it can.

【0039】

[Effect of the invention]

As described above, according to the present invention, a route to a target destination is provided even within the signal propagation delay time from the time when the link is congested or the failure occurs until the information is transmitted between the communication nodes. You can choose.

[Simple explanation of drawings]

[Figure 1]

The block block diagram of the main part of the route selection apparatus of the Example of this invention.

[Figure 2]

The figure which shows the failure example of the communication network for demonstrating the 1st Embodiment of this invention.

[Fig. 3]

The figure for demonstrating 1st Embodiment of this invention.

[Fig. 4]

The figure for demonstrating the 2nd Embodiment of this invention.

[Fig. 5]

The figure which shows the conventional detour selection method.

[Fig. 6]

The figure which shows the example of a communication network.

[Fig. 7]

The figure which shows the example of the communication network in which the failure occurred.

[Fig. 8]

The figure which shows the example of another communication network.

[Fig. 9]

The figure which shows the example of another communication network in which a failure occurred.

[Explanation of symbols]

1 ~ 16 links 20 Route selection device 21 Usability judgment unit 22 Usability notification section 23 Virtual Communication Network Configuration Unit 24 Route selection section 25 Designated route information generator 30 Communication equipment A ~ L communication node