JP3553398B2 - Routing apparatus and routing method - Google Patents

Description

[0001]
TECHNICAL FIELD OF THE INVENTION
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 in 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 performing multipath setting and load distribution by avoiding congestion points in a large-scale IP network having a hierarchical network.
[0002]
[Prior art]
Currently, routing algorithms widely used in the world of the Internet 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 match).
[0003]
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 transferred by each node exists on the shortest route even if the router transfers packets hop-by-hop in order to calculate the shortest route using the effective graph completely synchronized by each router I do. Therefore, it is possible to transfer the packet to the destination using the same shortest route.
[0004]
The second typical routing protocol is a path vector type routing protocol. BGP 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]
[Problems to be solved by the invention]
A link-state algorithm that determines a routing path based on link-state information is based on the premise that valid graphs held by each router are synchronized. Therefore, if 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.
[0006]
On the other hand, in order to perform high-throughput and highly-reliable 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 path by reflecting a traffic situation that fluctuates locally and dynamically in the network in a metric distributed in synchronization with the network.
[0007]
However, as the network scale increases, the metric distribution period becomes larger than the traffic fluctuation period.Therefore, it is not possible to calculate a metric that reflects the traffic load that fluctuates dynamically between each router and distribute it in synchronization with the entire network. Impossible. 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 that is aware of load distribution reflecting resources in the network.
[0008]
Also, in the path vector type routing protocol, when determining the routing path, it is assumed that the transfer cost is distributed in synchronization with the entire network. There is a problem that adaptive routing that avoids a congestion point that has occurred temporarily cannot be realized.
[0009]
Further, 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 and routed between hierarchical networks. It is carried out. 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 discard frequently occurs at a traffic concentration point and the throughput characteristic of the entire network is significantly deteriorated.
[0010]
Therefore, there is a need for a scalable routing algorithm that can adaptively set a detour route under a heavy load in a hierarchical large-scale IP network and execute load distribution of the entire network under a multipath environment.
[0011]
The present invention has been made in such a background, and provides a routing apparatus and a routing method capable of executing adaptive routing while avoiding a congestion point which dynamically fluctuates in a network. Aim. 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 apparatus 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 capable of realizing high-throughput and highly reliable packet transfer in a large-scale hierarchically complex IP network.
[0012]
[Means for Solving the Problems]
The present invention provides a method for distributing data when a congestion occurs in an arbitrary interface based on link state information that is periodically distributed to the entire network and is held by each node in synchronization and interface information that each node locally manages. The main feature is that a rerouting path can be set adaptively avoiding the interface.
[0013]
The conventional technology 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 hierarchical IP is used. The difference is that loop-free adaptive multipath routing that avoids congestion points is possible even in a network.
[0014]
That is, a first aspect of the present invention is a routing device, which is a global IP address distributed synchronously in a network, node topology information describing a positional relationship between nodes, and node topology information 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.
[0015]
Preferably, the means for setting loop-free includes means for holding routing vector information indicating a direction of a loop-free rerouting path. This makes it possible to avoid setting a rerouting path that may form a loop.
[0016]
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 paths.
[0017]
Further, means for holding information on the traffic load of the minimum metric path and a plurality of other rerouting paths, and executing routing while performing load distribution in the network to the destination according to the information held in the holding means. It is desirable to provide a means for performing this. As a result, the probability of occurrence of congestion can be reduced.
[0018]
At this time, it is preferable that the means for executing the routing includes means for updating the information on the traffic load with a transfer cost reflecting a traffic load actually transferred at every fixed period smaller than a link state exchange period. . As a result, it is possible to execute routing while performing load distribution according to the latest traffic load information.
[0019]
Further, it is preferable to include 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. Thus, the routing algorithm of the routing device of the present invention can be used even in a hierarchical IP network.
[0020]
At this time, it is preferable that the inter-layer routing executing means includes a representative node that manages information on traffic load and congestion of the own layer and layers higher or lower than the own layer and executes routing. With this representative node, the routing algorithm of the routing device of the present invention can be used between layers.
[0021]
A second aspect of the present invention is a routing method, comprising: a global IP address distributed synchronously in a network; node topology information describing a positional relationship between nodes; A rerouting path avoiding a congestion point is set in a loop-free manner for an arbitrary destination in accordance with local congestion information reflecting the traffic load to be transferred.
[0022]
At this time, it is desirable to set a rerouting path to an arbitrary destination in a loop-free manner according to 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.
[0023]
It is desirable to execute routing 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. At this time, it is desirable to update the traffic load information with a transfer cost reflecting a traffic load to be actually transferred at every fixed period smaller than the link state exchange period.
[0024]
Routing can be executed while setting a multipath in a loop-free manner across the layers in the layered IP network and distributing the load. 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]
BEST MODE FOR CARRYING OUT THE INVENTION
An embodiment 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.
[0026]
The present invention relates to a routing device 10, which is a global IP address synchronously distributed in a network, node topology information describing the positional relationship between nodes, and traffic managed for each node and transferred through an interface in the node. A routing unit 20 is provided, which is a 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 load.
[0027]
The routing unit 20 holds routing vector information indicating the direction of a loop-free rerouting path. In addition, rerouting routes are set in the order of the route having the minimum metric among the 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.
[0028]
In addition, the routing device 10 of the present invention performs routing while setting up a multipath in a loop-free manner and performing load distribution across layers in a hierarchical IP network. At this time, there is provided a representative node that executes routing by managing information of traffic load and congestion of the own layer and layers higher or lower than the own layer by the routing unit 20.
[0029]
【Example】
The proposed AMR (Adaptive Multipath Routing) algorithm performs routing using an interface cost dsk (ρ) that can be locally managed 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
dsk (ρ) = dsk (0) + IF (ρ)
Given by Here, dsk (0) is the next hop cost 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.
[0030]
FIG. 2 is a diagram showing the interface cost (IF-cost). When the horizontal axis represents the load ρ and the vertical axis represents the interface cost dsk (ρ), IF (ρ) is 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). Each node calculates the shortest cost by using the cost function dsk (ρ) reflecting the congestion information up to the next hop and the cost function Dkj from the next hop to the destination which is distributed in advance in synchronization with the network. Execute.
[0031]
FOR ALL POSSIBLE ROUTE
CALCULATE IF COST
IFC [k] ← dsk (ρ) + Dkj
SELECT k THAT MINIMIZE IF COST
Next hop ← k
FIG. 1 shows a routing image using this routing algorithm. 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 is possible over the entire network.
(Loop-free routing)
In the routing algorithm of the present invention, in order for each node to perform routing while avoiding congestion in an autonomous decentralized manner based on local interface costs, a packet which aims at the same destination after passing through a plurality of nodes having congestion points is looped. The possibility exists to form FIG. 3 shows an example in which congestion occurs in 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 in a sufficiently long cycle, and represents a direction vector allowed at the time of routing in the network for each destination.
[0032]
Therefore, if a reroute route is set in a direction that matches this routing vector when congestion is avoided, it is possible to guarantee that a loop will not be formed. This direction vector is calculated using Dijkstra's algorithm in the backward direction, which detects the shortest route reaching 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. The numbers described between the nodes A, B, C, S, E, F, G, and J in FIG. 4 indicate metrics that reflect the transfer cost between the nodes. Symbols P1, P2, P3, P4, and P5 indicate paths from the node J to each node in ascending metric order.
[0033]
For example, there are three types of loop-free routes from node A to destination J: 1) A → B → E → J, 2) A → B → J, 3) A → C → J Is shown. 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.
[0034]
FIG. 4 also shows flag information up to the destination J held by the nodes A and B. In setting the flag value, flag ← 0 is set when the packet transfer route matches the routing vector, and flag ← ∞ is set when the packet transfer route and the routing vector do not match. For example, the flag information held by the node A is set as A → S: ∞ because there is a possibility that a loop may be formed up to A → B: 0, A → C: 0, and S up to the adjacent nodes B and C. As described above, if the calculation method using Dijkstra in the reverse direction is used, adjacent nodes constituting the shortest hop node are sequentially determined starting from an arbitrary destination J, and thus it is guaranteed that no loop is formed in the network vector. .
[0035]
If the Dijkstra method in the reverse direction is used, the same algorithm is used for searching for the shortest path. Therefore, the shortest route candidate to the destination J is always included and calculated. The shortest path from the 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 cost between the nodes. Symbols P1, P2, P3, P4, P5, and P6 indicate paths 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.
[0036]
As a result, 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 is rerouted according to the route having the minimum metric cost. Even if rerouting is performed, 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 the AS (Autonomous System: 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) a routing vector for setting a shortest route from its own node and (2) an adjacent node to each destination and (3) a detour to a destination. Is stored in the routing unit 20 described with reference to FIG. Further, a database may be provided, and the calculation result of the routing vector may be stored in this database, and the result may be distributed to each node or transferred to each node according to a request from each node. The following algorithm Describes the link information calculated by each node.
[0037]
Next, processing when a packet arrives at a node on which the algorithm of the present invention is implemented is described in Algorithm 2. FIG. 6 shows a conceptual diagram of a packet flow described below and in a node. When the packet arrives at the node, the destination node in the same AS for arriving at the destination host from the IP address in the packet header is determined. At this time, since the algorithm of the present invention selects a multi-route path that can reach the destination 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 packet is transferred by multipath so that the load distribution reflecting the transfer cost can be achieved.
[0038]
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 within Δ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, the transfer route 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 forwarding. 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)
2. SELECT OPTIMAL ROUTE
FOR EACH PACKET COMINGING
(ADRESS RESOLUTION)
Dcs ID ← Address Resolution (IP Address)
(SELECT PATH AMONG POSSIBLE PATHS)
SP ← Select Path (Possible Path [])
(DISTRIBUTE PACKET)
Distribute Packet (SP)
(SELECT POSSIBLE PATH)
AFTER SEVERAL INTERVAL OBSERVATION
FOR ALL DESTINATION
Default Route ← Shortest-Path (Source
i → Destination j)
Select Route ← Select Min Route (j)
IF Select Route EQUAL TO Default Route
Next hop ← Default Route
Delete Extra-Route (Possible Path [])
ELSE IF Select Route DIFFER FROM Default Route
Next hop ← Multi Route
Add Next-Route (Possible Path [])
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 k THAT MINIMIZE ROUTE COST
Min hop ← k
By using such a mechanism, the algorithm of the present invention transfers packets while performing load sharing by multi-routes while avoiding congestion points in the network. For this reason, low-loss and low-delay routing with high throughput 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 network has three hierarchical structures, Level1 to Level3.
[0039]
In the Level 3 hierarchy, a network in which four nodes 1.0.0 to 4.0.0 are interconnected. Under this hierarchy, there are nodes at level 2 and nodes (1.1.0 to 1.3.0) to (4.1.0 to 4.4.0), respectively. Configure the network shown. Similarly, there is a level 1 node under the 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. The representative router holds the routing information of the level 3 hierarchy and performs the level 3 routing process.
[0040]
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 of the k + 1-th and k-th layers and performs the routing process of the k + 1-th and k-th layers. Nodes other than the representative node manage routing information only in the k-th hierarchy and are in charge of only routing processing closed in the k-th 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 the routing processing of the upper layer.
[0041]
FIG. 8 shows a hierarchical IP network. In the example of FIG. 8, in order to perform the routing of the level k, the nodes (1.2.0, 1.3.0), (2.2.0, 2.3.0), (3.1. 0) and (4.1.0, 4.3.0) are selected as the representative nodes. 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. In addition, 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.
[0042]
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 representative 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 forwards the packet to node 2.3.0 using the shortest path. At this time, since the interface of the node 2.3.0 is congested, the node 2.3.0 uses the level k routing information and passes through the node 2.2.0 to the node 4.0. Forward a portion of the traffic to 0. Node 4.1.0 is transferred to node 3.0.0 via node 4.3.0 based on level k routing information, and node 3.1.0 transfers to 3.2.0. . Since such a transfer protocol is used, the proposed protocol enables multi-path routing in a hierarchical IP network.
[0043]
【The invention's effect】
As described above, according to the present invention, adaptive loop-free routing that avoids congestion points that occur dynamically and fluctuate in a network can be executed. In this process, routing can be performed in a multipath environment to achieve load distribution. Further, the control method proposed in the routing algorithm of the present invention has a scalability to the network hierarchy, and thus enables a loop-free multipath routing avoiding a congestion point even in a hierarchical IP network. Become. As a result, by using the present routing algorithm, high-throughput and highly reliable packet transfer can be realized in a large-scale hierarchically complex IP network.
[Brief description of the drawings]
FIG. 1 is a diagram showing a routing image including a main block 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 a shortest route in a 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]
10 Routing device
20 routing section
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 nodes
P1, P2, P3, P4, P5, P6 path

Claims (12)

Node topology information describing the global IP address and node location relationship distributed synchronously in the network, and local congestion information reflecting the traffic load managed for each node and transferred through the interface within the node Therefore, a means for setting a rerouting path avoiding the congestion point to an arbitrary destination in a loop-free manner is provided .
The routing device, wherein the means for setting a loop free includes a means for setting a routing path according to routing vector information indicating a direction of a loop free rerouting path . 2. The routing apparatus according to claim 1, further comprising means for setting a rerouting route in an order of a route having a minimum metric among loop-free rerouting paths . Means for holding information on the traffic load of the minimum metric path and a plurality of other rerouting paths, and means for executing routing while performing load distribution in a network to a target destination according to the information held in the holding means routing apparatus according to claim 1, further comprising a. 4. The routing according to claim 3, wherein the means for executing the routing includes means for updating the information on the traffic load with a transfer cost reflecting a traffic load actually transferred at every fixed period smaller than a link state exchange period. apparatus. Routing apparatus according to claim 1, further comprising a hierarchy between routing execution means sets the multipath performs routing while load balancing loop access across inter-hierarchy in hierarchical IP network. 6. The routing device according to claim 5, 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. Node topology information describing the global IP address and node location relationship distributed synchronously in the network, and local congestion information reflecting the traffic load managed for each node and transferred through the interface within the node Therefore, a rerouting path avoiding a congestion point is set to an arbitrary destination, and the rerouting path is set to be loop-free according to routing vector information indicating a direction of the loop-free rerouting path . 8. The routing method according to claim 7, wherein rerouting routes are set in order of a path having the minimum metric among loop-free rerouting paths . 8. The routing method according to claim 7 , wherein the routing is performed 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 . 10. The routing method according to claim 9 , 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 . 8. The routing method according to claim 7 , wherein the routing is performed while setting a multipath in a loop-free manner across the layers in the layered IP network and performing load distribution . 12. The routing method according to claim 11, wherein the routing is performed by managing information on the traffic load and congestion of the own layer and a layer higher or lower than the own layer .

Images