Information processing apparatus, summarizing method and summarizing program

An information processing apparatus retains topology information indicating how all nodes are connected in a predetermined target area within a network divided into plural areas. The information processing apparatus includes an ingress/egress determining unit that determines, by referring to connected area information indicative of which area an area border node is connected to, an ingress-node group and an egress-node group, a disjoint determining unit that determines, by referring to the topology information, whether two or more disjoint routes from a node(s) of the ingress-node group to reach a node(s) of the egress-node group are present, a summarized-information generating unit that generates summarized information indicating a route from the adjacent area through the target area to the other adjacent area according to determination result by the disjoint determining unit, and a summarized-information reporting unit that reports the summarized information to another area.

CROSS-REFERENCE TO RELATED APPLICATION

This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2008-078524, filed on Mar. 25, 2008, the entire contents of which are incorporated herein by reference.

FIELD

The embodiments discussed herein are directed to an information processing apparatus, summarizing method, and summarizing program that summarizes a target area in a network divided into a plurality of areas.

BACKGROUND

Conventionally, in communications performed via a backbone network, a communication apparatus in the network relays data, messages, and others (for example, refer to Japanese Patent Application Laid-open No. 2004-343199).

The communication apparatus uses a predetermined communication protocol. In particular, a communication apparatus using Open Shortest Path First (OSPF) broadcasts, within the network, link information indicative of a link between apparatuses and link state between apparatuses.

This communication apparatus receives the link information to generate topology information indicative of how all communication apparatuses are connected with each other in the network.

Each communication apparatus refers to the topology information to search for a route to an arbitrary destination, for example.

Meanwhile, as the network grows bigger, the link information to be broadcasted further increases, resulting in overgrown topology information retained in each communication apparatus.

To address this problem, a technique has been developed in which the network is divided into a plurality of areas and the broadcast destination of the link information from each communication apparatus is restricted within an area.

Specifically, a node selected from an area or, for example, a totally different server, summarizes link information within the area. Then, the communication apparatus, which summarizes the information representatively, broadcasts resulting summarized information to another area.

Examples of summarizing techniques include a node abstraction technique of abstracting areas into a single node (refer to “OSPFv2 Routing Protocols Extensions for ASON Routing”, Dimitri Papadimitriou, URL that includes “tools.ietf.org/html/draft-ietf-ccamp-gmpls-ason-routing-ospf-03”.) and a link abstraction technique of abstracting links among apparatuses within an area into links only between area border nodes each serving as an entrance to its own area and area border nodes each serving as an exit to another area.

In the techniques mentioned above, each representative communication apparatus receives and retains summarized information generated in another area.

By referring to the summarized information, it is possible to know how the areas are connected to each other to construct the network, whereby it is possible to search for an approximate route to relay to an arbitrary destination, with the knowledge of which areas to pass through.

However, the summarized information does not include detailed information about links between the apparatuses within each area. Therefore, whether the routes found as a result of the search are redundant cannot be known.

Therefore, redundant routes to an arbitrary destination cannot be set based on the summarized information.

Moreover, it is impossible to find redundant routes to an arbitrary destination and to find a maximum reservable bandwidth of the set redundant routes based on the summarized information.

SUMMARY

According to an aspect of an embodiment, an information processing apparatus retains topology information indicating how all nodes are connected to configure a network, in a predetermined target area within a network that is divided into a plurality of areas, and the information processing apparatus includes an ingress/egress determining unit that determines, by referring to a storage unit having stored therein connected area information indicative of which area the node at a border with another area is connected to, an ingress-node group of ingress nodes each serving as an entrance to the target area from an adjacent area and an egress-node group of egress nodes each serving as an exit from the target area to another adjacent area, a disjoint determining unit that determines, by referring to the topology information, whether two or more disjoint routes from one or more node of the ingress-node group to reach one or more node of the egress-node group are present, a summarized-information generating unit that performs a process of generating summarized information indicating a route from the adjacent area through the target area to the other adjacent area as a route from an ingress abstract node obtained by abstracting the ingress-node group to an egress abstract node obtained by abstracting the egress-node group according to a result of determination by the disjoint determining unit, and a summarized-information reporting unit that reports the summarized information generated by the summarized-information generating unit to another area.

According to another aspect of an embodiment, an information processing apparatus retains topology information indicating how all nodes are connected, in a predetermined target area within a network that is divided into a plurality of areas, and the information processing apparatus includes an ingress/egress determining unit that determines, by referring to a storage unit having stored therein connected area information indicative of which area the node at a border with another area is connected to, an ingress-node group of ingress nodes each serving as an entrance to the target area from an adjacent area and an egress-node group of egress nodes each serving as an exit from the target area to another adjacent area, a disjoint determining unit that determines, by referring to the topology information, whether two or more disjoint routes from a virtual start-point node through any node of the ingress-node group and any node of the egress-node group to reach a virtual end-point node are present, a summarized-information generating unit that performs a process of generating summarized information indicating a route from the adjacent area through the target area to the other adjacent area as a route from an ingress abstract node obtained by abstracting the ingress-node group to an egress abstract node obtained by abstracting the egress-node group according to a result of determination by the disjoint determining unit, and a summarized-information reporting unit that reports the summarized information generated by the summarized-information generating unit to another area.

According to still another aspect of an embodiment, a method is for summarizing a target area within a network that is divided into a plurality of areas, and the method includes firstly determining, by referring to a storage unit having stored therein connected area information indicative of which area a node at a border with another area is connected to, an ingress-node group of ingress nodes each serving as an entrance to the target area from an adjacent area, and an egress-node group of egress nodes each serving as an exit from the target area to another adjacent area, secondly determining, by referring to topology information of the target area, whether two or more disjoint routes from one or more node of the ingress-node group to reach one or more node of the egress-node group are present, performing a process of generating summarized information indicating a route from the adjacent area through the target area to the other adjacent area as a route from an ingress abstract node obtained by abstracting the ingress-node group to an egress abstract node obtained by abstracting the egress-node group according to a result of determination in the secondly determining, and reporting the summarized information generated in the performing to another area.

According to still another aspect of an embodiment, a computer program product causes a computer to perform the method according to the embodiment as described above.

Additional objects and advantages of the invention (embodiment) will be set forth in part in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The object and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims.

DESCRIPTION OF EMBODIMENTS

With reference to the attached drawings, exemplary embodiments of a data relaying apparatus are explained in detail below as an information processing apparatus according to the present invention.

[a] First Embodiment

With reference toFIG. 1, a data relaying apparatus according to a first embodiment is explained schematically. The data relaying apparatus implements Generalized Multi-Protocol Label Switching (GMPLS). This data relaying apparatus is located in one area of a network which is divided into plural areas. Further, the data relaying apparatus forms a network with nodes including other data relaying apparatuses similarly implementing GMPLS.

For example, as depicted inFIG. 1, six data relaying apparatuses (N1to N6represent apparatus IDs (identifications)) are placed in an area2. The data relaying apparatus according to the first embodiment corresponds to an area border node placed at a border between different areas.

Conventionally, each data relaying apparatus exchanges a predetermined control message with other apparatuses to know a link state between apparatuses within the area.

Specifically, the data relaying apparatus broadcasts within the area, a link-information reporting message which includes information indicative of links between the apparatuses and other information.

As depicted inFIG. 1, for example, N1transmits the link-information reporting message (MSG1) to N3and N4that are connected to N1.

When N3and N4receive the link-information reporting message from outside for the first time, they transfer the link-information reporting message to another adjacent data relaying apparatus.

As a result, as depicted in a lower part ofFIG. 1, each data relaying apparatus knows the link state between the apparatuses within the same area.

In the present embodiment, when there are two or more disjoint routes that can connect one area (e.g., area1) via an adjacent area (e.g., area2) to another area (e.g., area3), an area border node of the adjacent area (area2) generates summarized information in which links between the apparatuses within its own area are summarized, and then reports the summarized information to the other area (area1or area3).

In each area, an area border node generates summarized information in the same manner, and reports the summarized information to another area.

Therefore, each area border node can know the link relation of each area, and is capable of searching for an approximate route for the destination, with the knowledge of which areas to pass through. Further, the area border node can know whether the obtained route has redundancy or not.

Next, the configuration of the area border node is explained.FIG. 2is a block diagram of a configuration of the data relaying apparatus according to the first embodiment.

As depicted inFIG. 2, a data relaying apparatus10includes a data transmitting and receiving unit20, a main controlling unit30, a topology storage unit40, a connected area information storage unit50, an ingress/egress specifying unit60, a summarized-information generating unit70, a summarized-information reporting unit80, and a summarized-information storage unit90.

The data transmitting and receiving unit20performs a process to transmit and receive a link-information reporting message and live data. On receiving data, the data transmitting and receiving unit20determines the type of the received data. Based on a result of determination, the data transmitting and receiving unit20determines the destination of the data output.

The main controlling unit30is a controlling unit that controls the entire data relaying apparatus10, and includes a data relaying unit31, a connected-area reporting unit32, and a generation controlling unit33.

The data relaying unit31performs a process regarding a link-information reporting message and live data. Specifically, the data relaying unit31generates a link-information reporting message, and transmits the generated link-information reporting message via the data transmitting and receiving unit20to another data relaying apparatus connected to its own data relaying apparatus10. Further, the data relaying unit31stores information included in a received link-information reporting message in the topology storage unit40, or transfers the information to another data relaying apparatus.

Here, as depicted inFIG. 3, the data relaying unit31includes in a link-information reporting message, information such as an apparatus ID of a transmission source, an apparatus ID of a link source, an ID of an I/F (interface) used by the apparatus of the link source, an apparatus ID of the link destination, and an ID of an I/F used by the apparatus of the link source. In the first embodiment, the apparatus ID of the link source and its I/F ID and the apparatus ID of the link destination and its I/F ID represent one link between apparatuses. Here, the apparatus ID of the transmission source and the apparatus ID of the link source correspond to the apparatus ID of the data relaying apparatus10in which the data relaying unit31itself is included.

When relaying a message or data upon receiving, for example, live data, from the data transmitting and receiving unit20, the data relaying unit31refers to the topology storage unit40, and determines a relay destination based on the link states among the apparatuses within the area. Then, the data relaying unit31transmits the received message or data via the data transmitting and receiving unit20.

The topology storage unit40stores the information prepared by the data relaying unit31. Specifically, as depicted inFIG. 4, the topology storage unit40stores information including apparatus IDs and I/F IDs that indicates links between the apparatuses.

For example, as depicted inFIG. 4, in the topology storage unit40, information including an apparatus ID “N1” and its I/F ID “A1” and an apparatus ID “N3” and its I/F ID “A2” represents one link between apparatuses.

The connected-area reporting unit32generates a connected-area reporting message which includes, for example, the area ID of the area to which its own apparatus is connected, and broadcasts the message within the area. Further, the connected-area reporting unit32stores information included in a received connected-area reporting message in the connected area information storage unit50, or transfers the information to another data relaying apparatus.

For example, as depicted inFIG. 5, the connected-area reporting unit32generates a connected-area reporting message including the apparatus ID of the transmission source and the area IDs.

As a result, the connected area information storage unit50stores the information generated by the connected-area reporting unit32. Specifically, as depicted inFIG. 6, the connected area information storage unit50stores the apparatus IDs and the area IDs in association with each other.

Here, the connected area information storage unit50may store the information in any manner. For example, an administrator may input the information in advance so that the connected area information storage unit50holds the information on receiving the input.

The generation controlling unit33controls whether to perform a summarized-information generating process in its own apparatus or not. Specifically, the generation controlling unit33refers to the information included in the received connected-area reporting message to determine whether the transmission source of the message is connected to the same area to which its own apparatus is connected.

As a result of determination, if the transmission source is connected to the same area, the generation controlling unit33compares the apparatus ID of its own apparatus and the apparatus ID of the transmission source to determine whether to perform a summarized-information generating process in it own apparatus or not.

For example, if the value of the apparatus ID of its own apparatus is a maximum among values of apparatus IDs of all area border nodes, the generation controlling unit33instructs the ingress/egress specifying unit60to start the summarized-information generating process.

Specifically, with reference toFIG. 1, of four area border nodes, the generation controlling unit33in N1refers to the connected-area reporting message received from N2to determine that N2is connected to an area1, to which its own apparatus is also connected.

The generation controlling unit33of N1then compares the apparatus ID “N2” of the transmission source and the apparatus ID “N1” of its own apparatus. Since “N1” is smaller than “N2”, the generation controlling unit33cancels an instruction for starting the summarized-information generating process.

Here, it is sufficient if the summarized information is generated in one apparatus among the area border nodes (apparatuses) connected to the same area. Therefore, for example, the generation controlling unit33may make an instruction to start the summarized-information generating process when the value of the apparatus ID of its own apparatus is a minimum.

Alternatively, the generating controlling unit33may control the operation of summarized-information generating process by allowing the summarized-information generating unit70to perform the process or prohibiting the summarized-information generating unit70from performing the process.

In this manner, inFIG. 1, N2and N6generate summarized information of the area2, for example. Specifically, N2generates summarized information of the area2indicative of routes from the area1via the area2to an area3, whilst N6generates summarized information of the area2indicative of routes from the area3via the area2to the area1.

The ingress/egress specifying unit60specifies an ingress border node serving as an entrance to its own area and an egress border node serving as an exit from its own area.

Specifically, upon receiving an instruction from the generation controlling unit33, the ingress/egress specifying unit60refers to the connected area information storage unit50.

The ingress/egress specifying unit60then selects an ingress border node connected to the same area to which its own apparatus is connected and an egress border node connected to another area, and gives an instruction on the selected nodes to the summarized-information generating unit70.

When there are a plurality of combinations of an ingress border node and an egress border node, the ingress/egress specifying unit60gives an instruction on each combination to the summarized-information generating unit70.

The summarized-information generating unit70is a processing unit that generates summarized information in which links between the apparatuses in the area are summarized, and includes a disjoint determining unit71.

Specifically, when the summarized-information generating unit70receives the instruction on the ingress border node and the egress border node from the ingress/egress specifying unit60, the disjoint determining unit71determines whether there are two or more disjoint routes from the ingress border node to the egress border node.

A manner of determination by the disjoint determining unit71is explained with reference toFIGS. 7 and 8. First, as depicted inFIG. 7, the disjoint determining unit.71refers to the topology storage unit40to know the link state between the apparatuses in its own area, to virtually set a start-point node and an end-point node.

Furthermore, the disjoint determining unit71generates a virtual link state between the apparatuses, where the start-point node is connected to each ingress border node and the end-point node is connected to each egress border node.

Then, the disjoint determining unit71determines whether there are two or more disjoint routes from the start-point node to the end-point node.

Here, disjoint of each route may be determined based on link-disjoint or node-disjoint.

Whether the disjoint determining unit71determines based on link-disjoint or node-disjoint is set in advance. For example, the disjoint determining unit71determines whether there are two or more routes from the start-point node to the end-point node that do not pass thorough the same link.

The link-disjoint routes may be determined based on, for example, Edge-Disjoint Shortest Pair algorithm.

Alternatively, the disjoint determining unit71may determine whether there are two or more routes that do not pass through the same node, not the same link.

In this case, the Vertex-Disjoint Shortest Pair algorithm can be used, for example.

Two types of determination results are explained below, assuming various link states among apparatuses. As depicted inFIG. 8, in a topology1, there are no two or more routes not passing through the same link, and no two or more routes not passing through the same node. Note that passing through the area is allowed.

In a topology2, there are two or more routes not passing through the same link, but there are two or more routes not passing through the same node.

In a topology3, there are two or more routes not passing through the same link, and there are two or more routes not passing through the same node.

As a result of determination by the disjoint determining unit71, if there are two or more disjoint routes, the summarized-information generating unit70treats the ingress border nodes as one abstract node and the egress border nodes as one abstract node, and gives predetermined identification information to each abstract node separately.

Then, the summarized-information generating unit70summarizes the links between the apparatuses in the area, assuming that the abstract nodes are linked to each other, thereby generating summarized information including the identification information. Then, the summarized information is stored in the summarized-information storage unit90, and is output to the summarized-information reporting unit80.

Meanwhile, the summarized information is generated in each area by a representative area border node.

For example, as depicted inFIG. 9, in an area8, summarized information of the area8indicative of routes from the area7via the area8to an area9is generated by N8. In the area9, summarized information indicative of routes from the area8via the area9to an area10is generated by N12.

Here, N8generates summarized information using predetermined identification information given to an abstract node “H1” obtained by abstracting N7and N8, which are ingress border nodes, into one and an abstract node “H2” obtained by abstracting N11and N12, which are egress border nodes, into one.

Also, N12generates summarized information using predetermined identification information given to an abstract node “H3” obtained by abstracting N11and N12, which are ingress border nodes, into one and an abstract node “H4” obtained by abstracting N14and N15, which are egress border nodes, into one.

These pieces of summarized information are broadcasted to another area by the summarized-information reporting unit80, which will be explained further below. With the reported summarized information, the representative area border node knows the link relation in the area.

Therefore, it is desirable that the representative area border node associate these pieces of summarized information with each other.

In other words, desirably the identification information given to H2by N8is made identical to the identification information given to H3by N12.

These pieces of identification information may be made identical based on identification information defined by a table set in advance by the administrator.

Specifically, as depicted inFIG. 10, the table associates the area ID of an area to which the area border node is connected with the identification information set separately for each area.

When N8refers to the table, N8knows that the egress border node is connected to the area9. Then, N8gives identification information “900” to H3.

In the same manner, on referring to the table, N12knows that the ingress border node is connected to the area8. Then, N12gives identification information “900” to H4.

In this manner, the same identification information can be given to corresponding abstract nodes more immediately in comparison with a technique explained later, according to which area IDs are combined.

In the alternative technique of making these pieces of identification information identical, the identification information may be generated by combining the area ID of its own area and the area ID of the connecting area together.

Specifically, as depicted inFIG. 11, when the area ID has 16 bits, identification information of 32 bits is provided. Note that the number of bits of the area ID is not restricted to 16 bits.

Here, the abstract node obtained by abstracting the ingress border nodes is provided with 32-bit identification information with its upper 16 bits representing the area ID of the connecting area and its lower 16 bits representing the area ID of its own area.

On the other hand, the abstract node obtained by abstracting the egress border nodes is provided with 32-bit identification information with its upper 16 bits representing the area ID of its own area and its lower 16 bits representing the area ID of the connecting area.

For example, N8provides H2with identification information “89”. In the similar manner, N12provides H3with identification information “89”.

In this manner, the identification information can be made identical without the need of setting and storing the table in advance and providing an additional storage unit, which is required in the technique mentioned earlier.

Returning to the explanation of the configuration, the summarized-information reporting unit80reports the summarized information generated by the summarized-information generating unit70to another area.

Specifically, upon receiving the summarized information from the summarized-information generating unit70, the summarized-information reporting unit80generates an abstract-link-information reporting message including the summarized information, and broadcasts the abstract-link-information reporting message via the data transmitting and receiving unit20.

Here, as depicted inFIG. 12, the summarized-information reporting unit80includes in the abstract-link-information reporting message, information such as the apparatus ID of the transmission source, the ID of the abstract node obtained by abstracting the ingress border nodes, and the ID of the abstract node obtained by abstracting the egress border nodes. In the first embodiment, the IDs of the two abstract nodes represent one link (abstract link) between the abstract nodes. Note that the apparatus ID of the transmission source is the apparatus ID of its own apparatus.

The summarized-information storage unit90receives from the summarized-information generating unit70the summarized information generated by its own apparatus, receives from the data transmitting and receiving unit20the summarized information transmitted from the area border node of another area, and then stores these pieces of summarized information therein.

The data relaying unit31of the main controlling unit30refers to the topology storage unit40and also the summarized-information storage unit90to search for a route to the data destination.

Next, a flow of the process by the data relaying apparatus10according to the first embodiment is explained.FIG. 13is a flowchart for explaining a process operation from generation to reporting of summarized information. The process operation illustrated inFIG. 13is performed when the generation controlling unit33instructs the ingress/egress specifying unit60to start the process.

First, the ingress/egress specifying unit60specifies ingress border nodes and egress border nodes (step S110).

The disjoint determining unit71of the summarized-information generating unit70then determines, for each specified ingress border node and egress border node, whether there are two or more disjoint routes from the ingress border node to the egress border node (step S120).

If it is determined that two or more routes are present (“Yes” at step S120), the summarized-information generating unit70generates summarized information (step S130).

The summarized-information reporting unit80reports the summarized information to another area (step S140), and the process ends.

As has been explained above, according to the first embodiment, depending on the determination result of the disjoint determining unit71, whether to generate summarized information is determined. The summarized information is generated only when two or more disjoint routes are present. Therefore, a route obtained as a result of search by using the summarized information always has redundancy.

[b] Second Embodiment

In the first embodiment, it is set in advance whether the determination on disjoint of two or more routes is based on node-disjoint or link-disjoint.

In a second embodiment, unlike the first embodiment, the disjoint is determined based both on node-disjoint and link-disjoint. Furthermore, in the second embodiment, a data relaying apparatus generates summarized information including information indicative of one of node-disjoint and link-disjoint, in addition to the predetermined identification information given to each abstract node.

FIG. 14is a block diagram of a configuration of a data relaying apparatus10A according to the second embodiment. As depicted inFIG. 14, unlike the first embodiment, a summarized-information generating unit70A of the second embodiment includes a node-disjoint determining unit72, a link-disjoint determining unit73, and a route searching unit74. Here, similar components to those in the first embodiment are not explained herein. In the following, only the summarized-information generating unit70A and a summarized-information reporting unit80A are explained.

Specifically, when the summarized-information generating unit70A accepts an instruction on the ingress border nodes and the egress border nodes from the ingress/egress specifying unit60, the node-disjoint determining unit72first determines whether two or more routes from the ingress border node to the egress border node not passing through the same node are present.

If it is determined that two or more such routes are present, the summarized-information generating unit70A takes the ingress border nodes as one abstract node and the egress border nodes as one abstract node, and provides predetermined identification information for each abstract node separately.

Then, the links among the apparatus within the area are summarized assuming that the abstract nodes are coupled, and summarized information including the identification information and protection attribute information indicative of node-disjoint is generated. Here, two or more routes that are node-disjoint are also link-disjoint.

On the other hand, if it is determined as a result of determination as to node-disjoint that two or more such routes are not present, the link-disjoint determining unit73of the summarized-information generating unit70A determines whether two or more routes from an ingress border node to an egress border node not passing through the same link are present.

If it is determined that two or more such routes are present, the summarized-information generating unit70A provides predetermined identification information for each abstract node separately in a manner similar to that explained above, and generates summarized information including the identification information and protection attribute information indicative of link-disjoint.

On the other hand, if it is determined as a result of determination as to link-disjoint that two or more such routes are not present, the route searching unit74of the summarized-information generating unit70A then searches for a route from the ingress border node to the egress border node.

If it is determined as a result of search that such a route is present, the summarized-information generating unit70A provides predetermined identification information for each abstract node separately in a manner similar to that explained above, and generates summarized information including the identification information and protection attribute information indicating that passing through the area is allowed.

After generating summarized information based on the determination by any relevant one(s) of the node-disjoint determining unit72and the link-disjoint determining unit73or the search by the route searching unit74, the summarized-information generating unit70A stores the summarized information in the summarized-information storage unit90and outputs the summarized information to the summarized-information reporting unit80A.

The summarized-information reporting unit80A reports the summarized information generated by the summarized information generating unit70A to another area.

Specifically, upon receiving the summarized information from the summarized-information generating unit70A, the summarized-information reporting unit80A generates an abstract-link-information reporting message including the summarized information, and then broadcasts the abstract-link-information reporting message via the data transmitting and receiving unit20.

Here, as depicted inFIG. 15, in the second embodiment, in the abstract-link-information reporting message, the ID of the ingress abstract node, the ID of the egress abstract node, and the protection attribute information indicative of an attribute of the link between the abstract nodes represent one link (abstract link) between the abstract nodes.

Next, a flow of the process by the data relaying apparatus10A according to the second embodiment is explained.FIG. 16is a flowchart for explaining a process operation from generation to reporting of summarized information. The process operation illustrated inFIG. 16is performed when the generation controlling unit33instructs the ingress/egress specifying unit60to start the process.

First, the ingress/egress specifying unit60specifies ingress border nodes and egress border nodes (step S150).

The node-disjoint determining unit72of the summarized-information generating unit70A then determines, for each specified ingress border node and egress border node, whether there are two or more disjoint routes from the ingress border node to the egress border node (step S160).

If it is determined that such routes are present (“Yes” at step S160), the summarized-information generating unit70A generates summarized information including protection attribute information indicative of node-disjoint (step S170).

On the other hand, if such routes are not present (“No” at step S160), the link-disjoint determining unit73of the summarized-information generating unit70A determines whether there are two or more link-disjoint routes from the ingress border node to the egress border node (step S180).

If it is determined that such routes are present (“Yes” at step S180), the summarized-information generating unit70A generates summarized information including protection attribute information indicative of link-disjoint (step S190).

On the other hand, if such routes are not present (“No” at step S180), the route searching unit74of the summarized-information generating unit70A determines whether passing from the ingress border node to the egress border node is allowed (step S200).

If it is determined that such passing is allowed (“Yes” at step S200), the summarized-information generating unit70A generates summarized information including protection attribute information indicating that passing through the area is allowed (step S210).

Then, the summarized information is reported by the summarized-information reporting unit80A to another area (step S220), and then the process ends.

Meanwhile, since bandwidth control is performed among the data relaying apparatuses, the link-information reporting message also includes bandwidth information among the apparatuses.

Therefore, as depicted inFIG. 17, each data relaying apparatus refers to the topology storage unit having stored therein the information included in the link-information reporting message to also know the bandwidth of the links in the area.

Thus, when two or more disjoint routes are present, the summarized-information generating unit70A may generate summarized information including bandwidth information indicative of a maximum bandwidth that can be reserved by at least two routes.

For example, in an area2, two routes depicted in a left part in the middle ofFIG. 17are node-disjoint, and the bandwidth that can be reserved by these two routes is 10 megabits per second. These are the only two node-disjoint routes in the area2, and 10 megabits per second is a maximum bandwidth that can be reserved.

Also, for example, in the area2, two routes depicted in a center part in the middle ofFIG. 17are link-disjoint, and the bandwidth that can be reserved by these two routes is 30 megabits per second. Other than these two routes, there are two link-disjoint routes in the area2, but 30 megabits per second is a maximum bandwidth that can be reserved.

Here, when passing through the area2is allowed, summarized information including bandwidth information indicative of a maximum bandwidth that can be reserved by one route may be generated.

For example, in the area2, a route depicted in a right part in the middle ofFIG. 17can reserve a maximum bandwidth of 100 megabits per second.

When the routes are node-disjoint, they are also link-disjoint and allow passing through the area. Therefore, the summarized-information generating unit70A generates summarized information separately for each piece of protection attribute information.

That is, as first summarized information for the area2, the summarized-information generating unit70A generates summarized information including the identification information explained above, the protection attribute information indicative of node-disjoint, and bandwidth information indicative of, for example, 10 megabits per second.

Furthermore, as second summarized information for the area2, the summarized-information generating unit70A generates summarized information including the identification information explained above, the protection attribute information indicative of link-disjoint, and bandwidth information indicative of, for example, 30 megabits per second.

Still further, as third summarized information for the area2, the summarized-information generating unit70A generates summarized information including the identification information explained above, the protection attribute information indicating that passing through the area is allowed, and bandwidth information indicative of, for example, 100 megabits per second.

Here, as depicted inFIG. 18, in this case, in the abstract-link-information reporting message, the ID of the ingress abstract node, the ID of the egress abstract node, the protection attribute information, and the bandwidth information represent one link (abstract link) between the abstract nodes. Furthermore, even the same abstract links are distinguished by the protection attribute information.

A flow of the process by the summarized-information generating unit70A when summarized information including bandwidth information is generated is explained.FIG. 19is a flowchart for explaining a process operation of the summarized-information generating unit70A, the process operation being performed when the summarized-information generating unit70A accepts an instruction on ingress border nodes and egress border nodes from the ingress/egress specifying unit60.

First, the summarized-information generating unit70A refers to the topology storage unit40to set a maximum bandwidth of bandwidths of links within the area as a lower-limit value (step S230), and then selects links of bandwidths equal to or larger than the lower-limit value (step S240).

The node-disjoint determining unit72of the summarized-information generating unit70A determines whether there are two or more node-disjoint routes from an ingress border node to an egress border node using only the selected links (step S250).

If it is determined that such two or more routes are present (“Yes” at step S250), the summarized-information generating unit70A generates summarized information including protection attribute information indicative of node-disjoint and bandwidth information indicative of a reservable maximum bandwidth (step S260).

On the other hand, if such routes are not present (“No” at step S250), the summarized-information generating unit70A determines whether the next largest bandwidth is present among the bandwidths of links within the area (step S270).

If the next largest bandwidth is present (“Yes” at step S270), the summarized-information generating unit70A sets the next largest bandwidth as a lower-limit value (step S280), selects links of bandwidths equal to or larger than that lower-limit value (step S240), and then the subsequent process is performed.

On the other hand, if the next largest bandwidth is not present (“No” at step S270) or after summarized information is generated (step S260), the summarized-information generating unit70A sets the maximum bandwidth among the bandwidths of the links in the area as a lower-limit value (step S290).

Based on a determination by the link-disjoint determining unit73, the summarized-information generating unit70A then performs a summarized-information generating process from steps S230to S280explained above (step S300).

In the summarized-information generating process, if the next largest bandwidth is not present or after summarized information is generated, the summarized-information generating unit70A again sets the largest bandwidth among the bandwidths of the links within the area as a lower-limit value (step S310).

Based on a determination by the route searching unit74, the summarized-information generating unit70A then performs a summarized-information generating process from steps S230to S280explained above (step S320), and the process ends.

Here, instead of generating summarized information for each piece of protection attribute information, one piece of summarized information may be generated.

In this case, the summarized information includes, for example, protection attribute information indicative of node-disjoint, bandwidth information indicative of 10 megabits per second, protection attribute information indicative of link-disjoint, bandwidth information indicative of 30 megabits per second, protection attribute information indicating that passing through the area is allowed, and bandwidth information indicative of 100 megabits per second.

As has been explained above, according to the second embodiment, even when two or more disjoint routes are present, these routes are distinguished based on node-disjoint or link-disjoint, and attribute information capable of determining the type is provided to the summarized information. With this, it is possible to determine which type each of these two or more disjoint routes belongs to.

Furthermore, according to the second embodiment, since the bandwidth information is included in the summarized information, it is possible to determine whether redundant routes to an arbitrary destination are present and, if they are present, find a reservable maximum bandwidth.

Note that each component depicted inFIGS. 2 and 14is functionally conceptual, and is not required to be physically configured as depicted.

That is, the specific form of distribution and unification of the components is not restricted to those depicted in the drawings. For example, the summarized-information generating unit70/70A and the summarized-information reporting unit80/80A may be unified. As such, all or part of the components can be configured by being functionally or physically distributed or unified by an arbitrary unit according to various loads and use states.

Furthermore, all or arbitrary part of the process function performed in each component can be achieved by a Central Processing Unit (CPU) and a program analyzed and executed on the CPU, or can be achieved as hardware with a wired logic.

The data relaying apparatus according to an embodiment reflects the determination result of the disjoint determining unit on the process of generating summarized information. For example, summarized information is generated only when redundant routes are present. Alternatively, identification information is made included in the summarized information for distinguishing between summarized information generated when redundant routes are present and summarized information generated when redundant routes are not present. Thus, it is possible to determine that all the routes obtained as a result of search by using the relevant summarized information are redundant.