JP2000201182A - Routing device and routing method - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To achieve high-speed and highly reliable packet transfer. SOLUTION: It is periodically distributed throughout the network,
When congestion occurs in an arbitrary interface based on link state information held by each node in synchronization and interface information managed locally by each node, a rerouting path is adaptively set to avoid the interface.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention is used for a routing algorithm mounted on each node (router) in an IP network. INDUSTRIAL APPLICABILITY The present invention is used in a routing algorithm that enables high-speed and highly reliable packet transfer by adaptively changing a route under a dynamically fluctuating traffic environment and performing routing while avoiding a congestion point. In particular, the present invention relates to a scalable packet transfer technique for performing routing while setting up multipaths and distributing load while avoiding congestion points in a large-scale IP network having a hierarchical network.

[0002]

2. Description of the Related Art Routing algorithms widely used at present in the Internet world are roughly classified into two types of protocols. One of them is called a link state type protocol, and OSPF is a typical example. In this routing protocol,
It is necessary that each node distributes link state information (link cost) to an adjacent node in synchronization with the entire network (data held by each node in the network completely matches).

At this time, each node in the network calculates a network topology based on the distributed link state information, and all nodes in the network share the same effective graph reflecting the network topology. Each node calculates the shortest route to the destination by searching for a route that achieves the minimum metric (distance) based on the route information, and determines the next hop node for each destination. In this process, the next hop node forwarded by each node exists on the shortest route even if packets are transferred hop-by-hop in order for each router to calculate the shortest route using a completely synchronized effective graph. I do. Therefore, it is possible to transfer a packet to a destination using the same shortest route.

[0004] A second typical routing protocol is a path vector type routing protocol. B
GP is a typical example. In the path vector type routing protocol, each node in the network notifies the adjacent node of the transfer cost to the adjacent node.
The notified adjacent node adds the transfer cost to its own adjacent node, and notifies the next adjacent node of the total hop cost. When this operation is performed on the entire network, each node can determine a hop cost to an arbitrary destination and an adjacent next hop node address.

[0005]

The link state type algorithm that determines a routing path based on link state information is based on the premise that the effective graphs held by each router are synchronized. Therefore, when the shortest route is calculated based on the effective graph in which the routers are not synchronized, there is a problem that the shortest route calculated between the nodes does not match and a loop is formed at the time of packet transfer.

On the other hand, in order to perform high-throughput and high-reliability routing, adaptive routing that avoids dynamically changing congestion points in a network is required. For this reason, it is desirable that each node calculates a routing route by reflecting a traffic situation that fluctuates locally and dynamically in the network in a metric distributed in synchronization with the network.

However, when the network scale becomes large, the metric distribution period becomes longer than the traffic fluctuation period. Therefore, a metric reflecting the traffic load that fluctuates dynamically between the routers is calculated and distributed in synchronization with the entire network. It becomes impossible to do. Therefore, it is difficult to search for the adaptive shortest route corresponding to the load. Furthermore, since this algorithm calculates the shortest route from the minimum metric route based on the metric information reflecting the hop cost between each node, the calculated route from any node to the destination node is only the minimum cost route. Become. Therefore, since routing is performed using only one packet transfer route irrespective of the load state of the network, there is a problem that it is not possible to realize multipath routing in consideration of load distribution reflecting network resources.

[0008] Further, even in a path vector type routing protocol, when determining a routing path, it is assumed that transfer costs are distributed in synchronization with the entire network. Similarly, there is a problem that adaptive routing that avoids a locally generated congestion point cannot be realized.

Furthermore, even when a path vector type routing protocol is used, it is difficult to perform routing in consideration of the traffic situation in the AS when performing routing between ASs, so that a fixed route is selected between hierarchical networks. And doing routing. For this reason, when congestion occurs in the AS in the route, a detour route cannot be dynamically set, and there is a problem that packet discards frequently occur at a traffic concentration point and the throughput characteristic of the entire network is significantly deteriorated.

Therefore, there is a need for a scalable routing algorithm capable of adaptively setting a detour route under a heavy load in a hierarchical large-scale IP network and executing load distribution of the entire network under a multipath environment.

The present invention has been made in view of such a background, and provides a routing apparatus and a routing method capable of executing adaptive routing while avoiding a congestion point that dynamically fluctuates in a network. The purpose is to do. An object of the present invention is to provide a routing device and a routing method capable of executing loop-free routing. An object of the present invention is to provide a routing device and a routing method that can achieve load distribution and execute routing in a multipath environment. An object of the present invention is to provide a routing device and a routing method that enable loop-free multipath routing while avoiding a congestion point even in a hierarchical IP network. An object of the present invention is to provide a routing device and a routing method that can realize high-throughput and highly reliable packet transfer in a large-scale hierarchically complex IP network.

[0012]

SUMMARY OF THE INVENTION The present invention is directed to an arbitrary network based on link state information which is periodically distributed to the entire network and held by each node in synchronization and interface information which each node locally manages. The main feature is that when congestion occurs in an interface, a rerouting path can be set adaptively avoiding the interface.

[0013] The prior art is that a loop-free rerouting path can be set even when routing is performed adaptively based on local information, that packet transfer can be performed while performing load distribution in a multipath environment, and that hierarchization is performed. The difference is that loop-free adaptive multipath routing that avoids congestion points can be performed even within a restricted IP network.

That is, a first aspect of the present invention is a routing device, which manages global IP addresses distributed synchronously in a network and node topology information describing a positional relationship between nodes, and is managed for each node. It is characterized by comprising means for setting a rerouting path avoiding a congestion point to an arbitrary destination in a loop-free manner in accordance with local congestion information reflecting a traffic load transferred through an interface in a node.

Preferably, the means for setting loop-free includes means for holding routing vector information indicating the direction of a loop-free rerouting path.
This makes it possible to avoid setting a rerouting path that may form a loop.

Further, it is desirable to have means for setting a rerouting route in the order of the route having the minimum metric among the loop-free rerouting routes.

Further, means for holding information on the traffic load of the minimum metric path and a plurality of other rerouting paths, and while performing load distribution in the network to the destination according to the information held in the holding means. It is desirable to have means for performing routing. As a result, the probability of occurrence of congestion can be reduced.

At this time, the means for executing the routing includes means for updating the information on the traffic load with a transfer cost reflecting the traffic load actually transferred at every fixed period smaller than the link state exchange period. It is desirable. As a result, it is possible to execute routing while performing load distribution according to the latest traffic load information.

Further, it is desirable to have an inter-layer routing executing means for executing a routing while setting a multi-path in a loop-free manner over a layer in the layered IP network and performing load distribution. Thus, the routing algorithm of the routing device of the present invention can be used even in a hierarchical IP network.

At this time, it is preferable that the inter-layer routing executing means includes a representative node that manages information on the traffic load and the congestion of the own layer and the layers higher or lower than the own layer and executes the routing. With this representative node, the routing algorithm of the routing device of the present invention can be used between layers.

A second aspect of the present invention is a routing method, which comprises a global IP address synchronously distributed in a network, node topology information describing a positional relationship between nodes, and node topology information managed for each node. A rerouting path that avoids a congestion point is set to any destination in a loop-free manner in accordance with local congestion information that reflects the traffic load transferred through the interface.

At this time, it is desirable to set the rerouting path to an arbitrary destination in a loop-free manner according to the routing vector information indicating the direction of the loop-free rerouting path. Further, it is desirable to set the rerouting route in the order of the route having the minimum metric among the loop-free rerouting paths.

It is desirable to execute the routing while distributing the load in the network to the target destination according to the information on the traffic load of the minimum metric path and a plurality of other rerouting paths. At this time, it is desirable to update the traffic load information with a transfer cost reflecting a traffic load actually transferred at every fixed period smaller than the link state exchange period.

It is also possible to set up a multi-path in a loop-free manner across layers in a layered IP network and execute routing while performing load distribution. At this time, it is desirable to execute the routing by managing the information of the traffic load and the congestion of the own layer and the layers higher or lower than the own layer.

[0025]

Embodiments of the present invention will be described with reference to FIG. FIG. 1 is a diagram showing a routing image including a block diagram of a main part of the routing device of the present invention.

The present invention is a routing device 10,
Global IP distributed synchronously within the network
A rerouting path that avoids congestion points according to node topology information that describes the positional relationship between addresses and nodes, and local congestion information that is managed for each node and reflects the traffic load transferred through the interface within the node, at any destination And a routing unit 20 that is a means for setting a loop-free operation.

The routing unit 20 holds routing vector information indicating the direction of a loop-free rerouting path. In addition, rerouting paths are set in the order of paths having the minimum metric among loop-free rerouting paths. Further, the routing unit 20 holds information on the traffic load of the minimum metric path and a plurality of other rerouting paths, and executes routing while performing load distribution in the network to the destination according to the held information. . At this time, the routing unit 20 updates the traffic load information with a transfer cost that reflects the traffic load that is actually transferred, at regular intervals smaller than the link state exchange period.

Further, the routing device 10 of the present invention
Routing is performed while setting a multipath in a loop-free manner across the layers in the layered IP network and performing load distribution. At this time, there is provided a representative node that manages the information of the traffic load and the congestion of the own layer and the layers higher or lower than the own layer by the routing unit 20 and executes the routing.

[0029]

DESCRIPTION OF THE PREFERRED EMBODIMENTS AMR (Adaptive Multipath Routin)
g) The algorithm performs routing using an interface cost dsk (ρ) that can be managed locally by each node and a shortest route cost Dkj that is managed synchronously by the entire network. The interface cost managed by each node is given by dsk (ρ) = dsk (0) + IF (ρ). Here, dsk (0) is the next hop cost that is distributed in advance synchronously throughout the network when link state information is exchanged, and represents the link cost from the node s to the next hop node k when the load is low.

FIG. 2 shows the interface cost (IF-co
FIG. 5B is a diagram showing the load (ρ) on the horizontal axis and the interface cost dsk (ρ) on the vertical axis, and IF (ρ)
Represents the interface cost up to the next hop node managed by the node s, and is a function of the load flowing into the interface as shown in FIG. This cost diverges to infinity at high load (ρ> ρth). Cost function ds reflecting such congestion information up to the next hop
Each node calculates the shortest cost using k (ρ) and a cost function Dkj from the next hop to the destination, which is distributed in advance in synchronization with the network, and executes routing.

FOR ALL POSSIBLE RO
UTE CALCULATE IF COST IFC [k] ← dsk (ρ) + Dkj SELECT k THAT MINIMIZE IF
COST Next hop ← k A routing image using this routing algorithm is shown in FIG. FIG. 1 is an example of routing from a source node S to a destination node J. The shortest route calculated based on the metric distributed in synchronization with the network is S → A → B → E → J. However, congestion occurs in the interface BE of the node B, and some traffic is transferred to the node B. 1 to J and an example in which congestion occurs in the interface AB of the node A and a part of the traffic is detoured from A to C to J. As described above, since each node calculates the local IF cost and adaptively sets a detour when congestion occurs, high-throughput and highly-reliable routing can be performed in the entire network. (Loop-free routing) In the routing algorithm of the present invention, each node passes through a plurality of nodes having congestion points in order to perform routing while avoiding congestion in an autonomous and distributed manner based on local interface costs, and then the same destination There is a possibility that a packet destined to form a loop. FIG. 3 shows an example in which congestion occurs on the link connected to the nodes C and F, and the packet of the destination J forms a loop A → C → F → S in order to avoid this congestion point. In order to prevent the formation of such a routing loop, in the algorithm of the present invention, each node in the network calculates a routing vector in synchronization. The routing vector is calculated from link state information provided in synchronization with the entire network at a sufficiently long period, and represents a direction vector allowed at the time of routing in the network for each destination.

Therefore, if a reroute route is set in a direction corresponding to the routing vector when congestion is avoided, it is possible to guarantee that no loop is formed. This direction vector is calculated by using Dijkstra's algorithm in the backward direction that detects the shortest route that reaches the J starting from an arbitrary destination J. FIG. 4 shows a routing vector calculated using this calculation method. In this example, a routing vector for the destination J is shown. Each node holds this information synchronously. FIG.
, The numbers described between the nodes A, B, C, S, E, F, G, and J indicate metrics reflecting the transfer cost between the nodes. Further, reference numerals P1, P2, P3, P4,
P5 indicates a path from the node J to each node in ascending metric order.

For example, a loop-free route from node A to destination J is 1) A → B → E → J, 2) A →
B → J, 3) A → C → J indicate that there are three types of routes. In addition, each node sets a routing flag to an adjacent node in order to independently describe a routing vector calculated by this calculation method at each node.

FIG. 4 also shows the flag information up to the destination J held by the nodes A and B. In setting the flag value, flag ← 0 when the packet transfer route and the routing vector match, and flag when the packet transfer route and the routing vector do not match.
Set ← ∞. For example, the flag information held by the node A is set to A → S: ∞ because there is a possibility that A → B: 0, A → C: 0, and S may form a loop up to the adjacent nodes B and C. As described above, if the calculation method using Dijkstra in the reverse direction is used, the adjacent nodes constituting the shortest hop node starting from an arbitrary destination J are sequentially determined, so that a loop is not formed in the network vector. .

When the Dijkstra method in the reverse direction is used, the same algorithm is used to search for the shortest path. Therefore, the shortest route candidate to the destination J is always included and calculated. , The shortest path from any node S to the destination J is always included. FIG. 5 shows the result of calculation of the shortest route in the forward direction for comparison. The numbers described between nodes A, B, C, SD, E, F, G, and J in FIG. 5 indicate metrics that reflect the transfer costs between the nodes. Further, symbols P1, P2, P3, P4, P5, P6
Indicates a path from the node SD to each node in ascending metric order. The numbers in parentheses indicate the accumulated metrics from the node SD to each node. FIG. 5 also shows next hop node information used when the node SD transfers a packet destined for each destination node.

Thus, even if each node forms a detour from the shortest route using this network vector, a loop is not formed along with the detour, and the detoured adjacent node reroutes according to the route having the minimum metric cost. Therefore, even if rerouting is executed, it is guaranteed that the route is routed to the destination through a route close to the default minimum cost. (Algorithm of the Present Invention) The algorithm of the present invention is a routing algorithm based on a link state protocol. Thus, in order to keep track of the network topology within an AS (Autonomous System: range automatically routed by the same administrator), each node exchanges link state information and forms a fully synchronized effective graph between the nodes. Based on this effective graph, the algorithm of the present invention calculates (1) the routing vector for setting the shortest route from the own node and (2) the adjacent node to each destination and (3) the detour to the destination. Is stored in the routing unit 20 described with reference to FIG. In addition, a database is provided, and the calculation result of the routing vector is stored in this database, and distributed to each node,
The information may be transferred to each node according to a request from each node. The following algorithm Describes the link information calculated by each node.

Next, processing when a packet arrives at a node on which the algorithm of the present invention is implemented is described in Algorithm 2. The conceptual diagram of the packet flow in the node described below is shown in FIG.
Shown in When the packet arrives at the node, the destination node in the same AS for arriving at the destination host is determined from the IP address in the packet header. At this time, since the algorithm of the present invention selects a multi-route path that can reach the target node, a transfer path is selected from the multi-paths at a distribution ratio reflecting the transfer cost actually measured at the node (for example, for each connection) ). Thereafter, the packets are transferred by multipath so that the load distribution reflecting the transfer cost can be achieved.

In the algorithm of the present invention, multipath candidates are updated at regular intervals ΔT (<< link state exchange period) at a transfer cost reflecting the traffic load actually transferred. In the algorithm of the present invention, each interface cost in ΔT is monitored and compared with the cost of the default route. In this process, the one having the minimum cost is selected from each interface cost. If the selected interface is an interface on the default shortest path, no congestion has occurred in this interface, so packets are transferred using this interface. At this time, if there is a transfer route other than the default route, it is deleted from the transfer route candidates. When the selected interface is different from the default shortest route interface, the selected interface is added as a candidate for multi-route transfer. In this case, since congestion has occurred in the default interface according to the definition of the cost function described above, traffic is diverted from the default route at a specified distribution ratio. 1. SET DATABASE FOR ALL DESTINATIONS Calculate Shortest-Path (Source i → Destination j) Calculate Shortest-Path (Next-hop k → Destination)
j) Set Routing-Vector (j) SELECT OPTIMAL ROUTE FOR EACH PACKET COMING (ADRESS RESOLUTION) Dcs ID ← Address Resolution
(IP Address) (SELECT PATH AMONG POSSIB)
LE PATHS) SP ← Select Path (Possible P)
ath []) (DISTRIBUTE PACKET) Distribute Packet (SP) (SELECT POSSIBLE PATH) AFTER Several INTERVAL OB
SERVATION FOR ALL DESTINATION Default Route ← Shortest-Pa
th (Sourcei → Destination j) Select Route ← Select Min R
out (j) IF Select Route EQUAL TO
Default Route Next hop ← Default Route Delete Extra-Route (Possib
le Path []) ELSE IF Select
Route DIFFER FROM Default
Route Next hop ← Multi Route Add Next-Route (Possible P
ath []) Select Min Route (Possible
Path []) Select Min Route (Des ID) FOR ALL POSSIBLE ROUTE CALCULATE ROUTE COST RC [k] ← IFC [k] + flag ← djk (ρ) + Dkj + flag SELECT KMITZM
UTE COST Min hop ← k By using such a mechanism, the algorithm of the present invention transfers packets while performing load sharing by multi-route avoiding congestion points in the network. Therefore, high-throughput, low-loss, low-delay routing is possible. (Multipath Hierarchical Routing) Next, consider the case where the algorithm of the present invention is applied to a hierarchical network. FIG. 7 shows a hierarchical IP network. In this example, the networks are Level1 to Level
It has three hierarchical structures up to l3.

In the Level 3 hierarchy, four nodes 1.
0.0 to 4.0.0 constitute a network connected to each other. Below this level is a level 2 node,
(1.1.0 to 1.3.0) to (4.1.0 to
44.0) and constitutes the network shown in FIG. Similarly, a node of level 1 exists under the control of level 2 and forms the network shown in FIG. In order to perform routing in the highest level 3 network, a representative router is determined in the level 2 node. This representative router holds the routing information of the level 3 hierarchy and performs the level 3 routing process.

In the example of FIG. 7, the nodes existing at the nodes 1.2.0 and 1.3.0 of the level 2 in the network 1.0.0 become the representative nodes of the level 3 and are in charge of the routing processing of the level 3. . Hereinafter, the representative router is similarly determined. In this way, the node selected as the representative node in the k-th layer manages the routing information in the k + 1-th and k-th layers and manages the k + 1,
The k-level routing process is performed. Nodes other than the representative node manage routing information only in k layers and
Responsible for only the routing process closed in the hierarchy. By performing such layering, the routing information held by each node can be compressed, and the routing processing in each layer can be speeded up. In addition, the representative routers installed in the respective layers exchange link state information between the representative routers in order to perform routing processing in the upper layer.

FIG. 8 shows a hierarchical IP network. In the example of FIG. 8, nodes of level k + 1 (1.2.0, 1.3.
0), (2.2.0, 2.3.0), (3.1.0),
(4.1.0, 4.3.0) is selected as the representative node. In each level, the inventive algorithm operates independently, and when congestion occurs in the same level, adaptively sets a multipath to avoid a congestion point. Also,
Since the representative node manages the routing of the level k, when congestion occurs in the level k, a detour is set in the level k to bypass the congestion point by multipath. At this time, if there is another representative node that can reach the destination node J in the same AS, the node is set as a detour. At this time, it is assumed that the above-described routing vector is set so that no loop is formed between the representative nodes.

The packet transfer when the node 1.1.0 aims at the node 3.2.0 will be described with reference to FIG. The node 1.1.0 determines that the destination node does not exist in the same AS from the destination of the packet, and transfers the packet to the default router 1.3.0 set by default.
Since the node 1.3.0 is a representative node, the packet is transferred to the node 2.0.0 using the routing information of the level k. Node 2.1.0 uses the shortest path to node 2.1.0.
Forward the packet to 3.0. At this time, node 2.
Since the interface of 3.0 is congested, the node 2.3.0 uses the routing information of the level k to pass a part of the traffic to the node 4.0.0 via the node 2.2.0. To transfer. The node 4.1.0 is transferred to the node 3.0.0 via the node 4.3.0 based on the routing information of the level k, and the node 3.1.0 is set to 3.0.0.
Transfer to 2.0. Since such a transfer protocol is used, the proposed protocol enables multi-path routing in a hierarchical IP network.

[0043]

As described above, according to the present invention,
Adaptive loop-free routing that avoids congestion points that dynamically fluctuate in the network can be executed. In this process, routing can be performed in a multipath environment to achieve load distribution. Furthermore, the control method proposed by the routing algorithm of the present invention has a scalability to network hierarchies, so that loop-free multipath routing that avoids congestion points can be performed even in a hierarchical IP network. Become. As a result, using this routing algorithm, a complex I
High-throughput and highly reliable packet transfer can be realized in the P network.

[Brief description of the drawings]

FIG. 1 is a diagram showing a routing image including a main block configuration diagram of a routing device of the present invention.

FIG. 2 is a diagram showing interface costs.

FIG. 3 is a diagram showing an example in which congestion occurs in a link connected to a node C and a node F, and a packet of a destination J forms a loop A → C → F → S in order to avoid this congestion point.

FIG. 4 is a diagram showing a routing vector.

FIG. 5 is a diagram showing a calculation result of the shortest route in the forward direction.

FIG. 6 is a conceptual diagram of a packet flow in a node.

FIG. 7 is a diagram showing a hierarchical IP network.

FIG. 8 is a diagram showing a hierarchical IP network.

[Explanation of symbols]

Reference Signs List 10 routing device 20 routing unit A, B, C, E, F, G, J, S, SD, 1.0.0,
2.0.0, 3.0.0, 4.0.0, 1.1.0,
1.2.0, 1.3.0, 2.1.0, 2.2.0,
2.3.0, 3.1.0, 3.2.0, 4.1.0,
4.2.0, 4.3.0, 4.4.0 Node P1, P2, P3, P4, P5, P6 Path

 ──────────────────────────────────────────────────続 き Continued on the front page F term (reference) 5K030 GA13 HC01 JL07 KA01 KA05 LB07 LC11 LE03 MA01 5K033 AA03 CB06 DA05 DB01 DB12 DB14 DB18 EA07 EB02 EC03 9A001 CC06 CC07 FF03 GG01 GG06 GG19

Claims (14)

[Claims] 1. A global IP address distributed synchronously in a network, node topology information describing a positional relationship between nodes, and a local reflecting a traffic load managed for each node and transferred through an interface in the node. Routing means for setting a rerouting path avoiding a congestion point to an arbitrary destination in a loop-free manner in accordance with appropriate congestion information. 2. The routing apparatus according to claim 1, wherein the means for setting loop-free includes means for holding routing vector information indicating a direction of a loop-free rerouting path. 3. The routing apparatus according to claim 1, further comprising: means for setting a rerouting route in a path having the minimum metric in a loop-free rerouting path. 4. A means for holding information on the traffic load of the minimum metric path and a plurality of other rerouting paths, and distributing the load in the network to the target destination according to the information held by the holding means. 2. The routing device according to claim 1, further comprising means for performing routing. 5. The means for executing the routing includes means for updating the traffic load information with a transfer cost reflecting a traffic load actually transferred at every fixed period smaller than a link state exchange period. Item 5. The routing device according to Item 4. 6. The routing apparatus according to claim 1, further comprising an inter-layer routing executing means for executing a routing while setting a multipath in a loop-free manner and performing a load distribution over the layers in the layered IP network. 7. The routing according to claim 6, wherein the inter-layer routing executing means includes a representative node that manages information on traffic load and congestion of the own layer and a layer higher or lower than the own layer and executes routing. apparatus. 8. A global IP address synchronously distributed in a network, node topology information describing a positional relationship between nodes, and a local reflecting a traffic load managed for each node and transferred through an interface in the node. A routing method characterized in that a rerouting path avoiding a congestion point is set to an arbitrary destination in a loop-free manner in accordance with various congestion information. 9. The routing method according to claim 8, wherein a rerouting path is set to an arbitrary destination in a loop-free manner according to routing vector information indicating a direction of the loop-free rerouting path. 10. The routing method according to claim 8, wherein rerouting routes are set in order of a path having the minimum metric among loop-free rerouting paths. 11. The routing method according to claim 8, wherein the routing is performed while distributing the load in the network to the target destination in accordance with the information on the traffic load of the minimum metric path and a plurality of other rerouting paths. 12. The routing method according to claim 11, wherein the information on the traffic load is updated with a transfer cost reflecting a traffic load actually transferred at every fixed period smaller than a link state exchange period. 13. The routing method according to claim 8, wherein a routing is executed while setting a multipath in a loop-free manner across the layers in the layered IP network and performing load distribution. 14. The routing method according to claim 13, wherein the routing is executed by managing the information on the traffic load and the congestion of the own layer and a layer higher or lower than the own layer.