JPH0556080A - Packet relay device - Google Patents

Abstract

(57) [Summary] [Objective] In a packet relay device having a distributed dynamic route selection function based on the Bellman-ford algorithm in a packet-switched communication network between heterogeneous networks, the network topology information is added to the route information and the route is added. By making a selection, it is intended to suppress the leakage of incorrect route selection information. A structure in which network tree topology information composed of optimum path information is added to a conventional format of a packet format transmitted and received dynamically by a route control means of a packet relay device by an addition module 1 for adding topology information. By doing so, when a route change occurs, the route control module 2 uses this as a judgment material and surely updates the old route information without updating the new route information with the old route information. It is possible to reliably transmit to all network systems.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a packet relay device in a packet switching communication network between heterogeneous networks.

[0002]

2. Description of the Related Art In recent years, a packet switching communication system between heterogeneous networks used in a computer network is mainly based on a dynamic route control. Above all, the route control in a small scale network is Bellman-for.
Those based on the d algorithm are widely used. With respect to this conventional example, first, a method in which a packet relay device relays packets between different networks will be described.

FIG. 8 shows an example of a packet switching communication network.
11 to 114 are packet relay devices, 21 to 24 are networks, and 31 to 34 are terminals. The packet relay device 111 is connected to the network 21 and the network 22,
The packet relay device 112 is connected to the networks 21 and 23, and the packet relay device 113 is connected to the network 2
2 and the network 23, and the packet relay device 114 is connected to the networks 23 and 24. The terminal 31 is on the network 21, the terminal 32 is on the network 22, the terminal 33 is on the network 23, and the terminal 3 is
4 is connected to the network 24. The terminals and packet relay devices connected to the same network are
It has a function of transmitting and receiving packets to and from each other.

Here, if the terminal 31 tries to transmit a packet to the terminal 34, each packet is sent from the terminal 31 to the packet relay device 112, and the packet relay device 112 sends this packet to the packet relay device 114 through the network 23. It can be considered that the packet relay device 114 sends the packet to the terminal 34 as an example. The path of such a packet is hereinafter referred to as a path. In order to select the route as described above in a distributed processing manner, each of the terminals 31 to 34 and each of the packet relay apparatuses 111 to 114 has to select which terminal or packet relay apparatus should relay the transmitted packet. I have to do it. Therefore, first, a unique address is assigned to each interface of each device connected to the network of the packet switching communication network in advance.

This address is composed of a network ID and a host ID, and it can be seen from the address which network the hardware interface is connected to. Each terminal 31 to 3
4. Each of the packet relay devices 111 to 114 holds a table in which the final destination address is associated with the relay destination address of the same network to be transmitted to the final destination address for the above route selection. .. This table is called a routing table.

For example, when the terminal 31 tries to send a packet to the terminal 32, the terminal 31 looks up the table of FIG.
1 to the hardware interface. The packet relay apparatus 111 determines that the address is its own direct connection network from the table of FIG. 9B, and transmits the packet to the terminal 32.

A distributed optimal route selection system using the Bellman-ford algorithm dynamically creates a routing table for a network of packet relay devices connected to a network to be route-controlled by software, that is, a network. It is a system that automatically creates a routing table in response to system changes. For this purpose, each packet relay device exchanges route information with each other on a regular basis, and each determines an optimum route based on an algorithm described later, and creates a routing table.

As a method of determining the route as optimum, a numerical value called a cost is given to each network, and a route that minimizes the total cost of networks appearing in the route and the number of metrics is determined as the optimum. Is taking. In the example of FIG. 8 described above, for example, the cost 21 is assigned to the network 21, the cost 1 is assigned to the network 22,
If the network 23 is given the cost 3 and the network 24 is given the cost 1, the optimum route of the packet relay device 114 to the network 21 is the network 21, the packet relay device 112, the network 23, and the packet relay device 1.
With a route of 14, the number of metrics is 4.

This metric calculation is performed by Bellman-
Distributed processing is performed in the distributed optimal route selection system using the ford algorithm. For example, in the above example,
Since the packet relay apparatus 112 sets the cost value of its own direct connection network before the packet switching communication network operates, it can determine that the cost of the network 21 is 1, that is, the metric number of the network 21 is 1. This information plus the cost of the packet relay device 112 direct connection network 23 that is going to send this information is sent to the packet relay device 114. Therefore, the packet relay device 114 receives the metric number of this route to the network 21 as 4. ..

By the way, in addition to the above-mentioned routes to the network 21, the network 21 and the packet relay device 11
1, the network 22, the packet relay device 113, the network 23, and the packet relay device 114 also exist, but the metric number of this route is 5 when similarly calculated in a distributed manner. Therefore, the optimum route of the packet relay device 114 to the network 21 is determined to be the route to be sent to the packet relay device 112 having the metric number 4.

Such an operation is performed on all the networks forming the packet switching communication network. The information periodically transmitted to each other is the destination network address and the metric number, which are mutually transmitted to the packet relay devices connected to the same network called neighbors. Hereinafter, a combination of information such as exchanged network addresses and the number of metrics is referred to as a route information unit in the case of describing the related art.

Although the basic operation has been described above, the operation of the distributed optimal route selection system using the Bellman-ford algorithm is summarized as follows. First, a cost is set for each network, and first, for each network, start with an initial value that it is unreachable except for direct connection networks, and each packet relay device has a set of each network address and metric in the routing table, that is, route information Take the units for all networks, add to the metric numbers the cost of the direct connect network sending them, and send them in a packet to all direct connect networks. This transmission is repeated periodically, but the interval is not specified.

The receiving side selects the route information unit having the smallest metric number for each network among the route information units in the packet transmitted from each neighbor as the optimum route. Actually, the selection is realized by comparing the optimum route information unit possessed by each packet relay device with the route information unit sent every time a packet arrives. However, as an exception, if the packet relay device that sent the packet has sent the route information unit that has been selected as the optimum route up to that point, that is, if it is the next hop, the minimum distance is not required. This is selected as the optimum route.

In order to select all routes from the next hop, the maximum value of the metric number is put in the route information unit in order to convey unreachability in the distributed optimal route selection system using the Bellman-ford algorithm. This is because the existing route disappears because the existing route is not updated, that is, the routing table is not changed only by the minimum metric selection method. In the route selection, the adjacent packet relay device to be relayed to send the packet to the network address of the optimum route is the packet relay device that has sent the optimum route information unit.

Hereinafter, the interface means a connection between the packet relay devices. For example, the packet relay device 112 and the packet relay device 113, the packet relay device 112 and the packet relay device 114, and the set of the packet relay device 113 and the packet relay device 114 in FIG. Interface.

As described above, the maximum metric number is defined as the metric number, and it is considered that the packet relay device having this route information unit cannot transmit to the network address of the route information unit having a metric value exceeding or equal to this value. Be done. By transmitting this value to the neighboring packet relay device, each packet relay device notifies other packet relay devices that its own interface has gone down, in other words, that route information cannot be exchanged. The route information unit having the maximum metric number is deleted by the timeout of the timer having a constant timeout value. The distributed optimal route selection system using the Bellman-ford algorithm is constructed by the above technique.

However, the optimal route selection system using the Bellman-ford algorithm is, in theory,
It only guarantees that the optimum route can be selected by each packet relay device by exchanging the route information a finite number of times, and because it is especially distributed, the packet relay devices cannot be synchronized and the network topology and route information are generated. Depending on the timing, there may be a problem that the convergence is delayed.

As described above, when the route is changed due to the disconnection of the network or the failure of the packet relay device, the route information unit to the unreachable network is transmitted with the metric number as the maximum metric number, and the other metric number is transmitted. Since the route information unit of the packet relay device is updated, the adjacent packet relay device to which the new route information has not been transmitted has not yet failed in the route information unit in the updated packet relay device. , A route information unit with a metric smaller than the maximum metric may be rewritten by the optimal route selection algorithm. As a result, the new information of route loss is lost and old information that does not match the current situation remains. This state is repeated until the cost is added to the number of metrics and the maximum number of metrics is reached,
Causes slow convergence.

The conventional technique has dealt with this problem by adding the following two auxiliary functions. Split horizon is one of the technologies. In the own packet relay device, for the next hop of the route information unit for a certain network address selected for the optimum route selection, the route information unit is not transmitted, or the metric number is transmitted as the maximum metric number. is there. 10, 11, and 12 are examples of slow convergence solved by the split horizon. 1
11, 112 and 113 are packet relay devices, 21 is a network, and solid lines drawn between the packet relay devices are interfaces. In this example, the packet relay device 112 is the next hop of the packet relay device 113 as shown in FIG. 10, but before the packet relay device 112 transmits the down of the network 21 to the packet relay device 113, as shown in FIG. Since the packet relay device 113 has transmitted its own route information to the packet relay device 112, the old network information held by the packet relay device 113 updates the down information.

FIG. 12 shows a state in which the packet relay device 112 has rewritten the packet relay device 113 with old route information. Such a state is repeated until the number of metrics of the route information unit reaches the maximum number of metrics. If the split horizon is used, the next hop is not updated, so such a failure cannot occur. As a result, even if the above-mentioned failure occurs, the route information units will not reciprocate and select each other. However, split horizon alone cannot suppress slow convergence for all cases.

As such an example, a second example of slow convergence is given in FIGS. 13, 14 and 15. 111, 112, 11
3, 114 and 115 are packet relay devices, 21 is a network, and a solid line drawn between the packet relay devices indicates an interface. In the state of FIG. 13, the next hop of the packet relay device 115 is the packet relay device 113.
Therefore, the old information of the packet relay device 115 cannot be transmitted to the packet relay device 113. However, as shown in FIG.
Since it is not the next hop for 5, it will be updated. Thereafter, such update is repeated in the order of the packet relay device 115, the packet relay device 114, the packet relay device 112, and the packet relay device 113. FIG. 15 shows where the packet relay device 114 has rewritten the packet relay device 112.

As a technique for this, there is a technique called trigger update. This means that when a change occurs in the route in the own packet relay device, only the changed route information unit is immediately transmitted to the neighboring packet relay device. This reduces the timing at which the old route information unit rewrites the new route information unit. In this way, it is possible to suppress the problems of the slow convergence 2 type.

[0023]

In the trigger update of the auxiliary function described in the above-mentioned prior art, once the network topology is changed, each packet relay device begins to randomly generate a great amount of route information packets, and each network repeats. Increase the load on. The change in the network topology generally means that the system consisting of networks that exchange packets with each other is in an unstable state, and it is not desirable to increase the load on each network in such a state.

The present invention provides a packet relay apparatus which solves the problem of overload, reliably discards the old route control information solved by the conventional technique, and converges the optimum route selection to a steady state as quickly as possible. The purpose is to provide.

[0025]

In order to solve the above problems, a packet transfer apparatus according to the present invention comprises an interface unit for a plurality of networks, a packet relay unit between the networks, and a route control unit for selecting a packet route. And the route control means has an addition means for adding topology information indicating a connection state between networks.

[0026]

Since the topology information is added to the route control information by the addition unit in the route control unit, the route control unit can judge the reliable and unreliable route information when the route information is changed. Therefore, it is possible to deal with a situation that causes a slow convergence problem. Also, when trigger update is used, the broadcast that is immediately issued when there is a route change is not generated, so the network load that occurs in an unstable network system where the route change occurs by this unnecessary broadcast amount Can be reduced.

[0027]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS A packet relay device that solves the above problems will be described below with reference to the drawings. FIG. 1 is a block diagram of a packet relay device. As components, 1 is an addition module for processing a route control packet with topology information added, 2 is a route control module for controlling the routing table of the own packet relay device from the route information with topology information added, and the route control means is It is composed of an additional module 1 and a route control module 2. Three
Is a routing table, 4 is a packet transmission / reception module of its own packet relay device, and 5 is a packet relay module. The packet relay means is composed of a packet transmitting / receiving module 4 and a packet relay module 5. Reference numerals 6 and 7 denote network interfaces as interface means, and 8 and 9 denote physical networks.
The number of network interfaces 6 and 7 may be any number as long as it is two or more.

Next, the operation will be described. If a packet is input from the network interface and is not a packet addressed to the own packet relay device, this packet is processed by the packet relay module 5.
The packet relay module 5 routes according to the routing table 3. When a packet addressed to the own packet relay device is input to the network interface, the packet transmission / reception module 4 of the own packet relay device
Is processed by. This is a module used for transmitting and receiving the routing control information packet of the additional module 1 which processes the routing control packet to which the topology information is added.

The additional module 1 for processing the route control packet to which the topology information is added removes split horizon and trigger update from the technique described in the prior art, and will be described in the following items (1) and (2). It consists of adding a method. This corresponds to "addition means for adding topology information indicating the connection state between networks" described in the claims.

The route control module 2 for controlling the routing table of the own packet relay device from the route information added with the topology information has the following techniques (3) and (4) in the technique described in the prior art. It is configured by adding. The technique added to the conventional technique will be described below.

(1) Packet configuration format The packet configuration format is as shown in FIG.
What is referred to herein as a route information unit is an extension of the route information unit described in the prior art, as shown below. Each network route information unit is composed of five components: an interface ID, an interface down flag, an interface up flag, a pointer indicating the depth of the tree, and a network information unit.

Next, these format components will be described. First, the interface ID has only to be a unique number for each interface. For example, in the case of TCP / IP, the output Internet address may be used. This is the case in the present embodiment. This is used to determine the output source of the route information unit.

The interface down flag indicates that the own interface is disconnected, and the interface up flag indicates that the interface is restarted or started. It is set up by a packet relay device directly connected to the corresponding interface and transmitted to all neighboring packet relay devices.

An integer value is written in the pointer indicating the depth of the tree, and is used to describe the shape of the network connection as a tree topology from the packet format.

Further, the network information unit is composed of two constituent elements which have been included in the conventional route information unit, that is, a network address and a metric number.

The addition of the pointer indicating the depth of the tree in the above format to the route information unit in this way will be described as a format in which the tree topology information can be added to the route information unit.

Before that, some terms will be explained.
Topology here means an event that can be abstracted into a figure composed of points and lines. In the case of the present invention, each packet relay device is regarded as a point, and more specifically, a network, more specifically, an interface is regarded as a line, and is used as a means for abstractly expressing the connection condition and the route between the network and the packet relay device. On the other hand, the tree topology means a topology having no ring structure. The purpose of this format is to describe this tree topology in the packet.

In the tree topology, a branch separated from a certain point does not intersect with another branch again, so that a certain reference point, one point on the tree topology that has been constructed starting from the certain reference point, and the tree topology are still formed. If all the points which are not incorporated and are connected to the points by lines can be expressed, it is possible to describe the tree topology by recursively repeating this expression. In the tree topology description method to be described here, a reference point is set at a certain point called the root, the description of the tree topology is started from this point, and the pointer indicating the depth of the tree and the position of the route information unit on the packet By expressing the connection of the relay devices repeatedly, the tree topology composed of the optimum route information is expressed.

More specifically, the packet relay device indicated by the interface ID of the route information unit whose pointer indicating the depth of the tree has a value of x searches for the direction of the beginning of the packet from the position within the packet. The value of the pointer indicating the depth of the tree first appearing in (3) indicates that the interface ID is directly connected through the network of the route information unit of x-1. By this representation method, each path information unit is uniquely incorporated in the tree topology.

Using the example of FIG. 3, let's describe the tree topology according to the above format. 11 to 15
Indicates a packet relay device, and 21 to 25 networks. If the starting point of this figure is described in the packet relay device 11 according to the packet format, it can be written as follows.

(P11, 1, N21) (P12, 2, N)
22) (P13, 3, N25) (P12, 2, N23)
(P14, 3, N24) However, P11, P12, P1
3 and P14 are packet relay devices 11 and 1
Interface ID of 2, 13, 14 and N2
The ones labeled 1, N22, N23, N24, N25 are networks 21, 22, 23, 24, 25. What is enclosed in open parentheses and closing parentheses is the route information unit, and the first item in both parentheses is the interface ID.
Indicates. Here, instead of the interface ID, it means a packet relay device having the interface ID at the output Internet address. The second term in both brackets means a pointer indicating the depth of the tree. As a result, this number is the number of packet relay devices that pass through before reaching the network address of the route information unit + 1
Equivalent to. The third item in the brackets is the network information unit connected to the interface ID of the route information unit. The interface down flag and interface up flag in the route information unit are
Since it is not relevant here, it is omitted.

A tree topology is constructed from the packet information. The route is the packet relay device 11, and the network 21 is connected to this. Looking at the second route information unit, the value of the pointer indicating the depth of the tree is 2, and it is confirmed that the packet relay device 12 is connected to the packet relay device 11 through the network 21 of the first route information unit. Show. Looking at the third route information unit, the value of the pointer indicating the depth of the tree is 3, which indicates that it is connected to the packet relay device 12 through the network 22 of the second route information unit. Looking at the fourth route information unit, the value of the pointer indicating the depth of the tree is 2, which indicates that the packet relay device 12 is connected through the network 21 of the first route information unit. Looking at the fifth route information unit, the value of the pointer indicating the depth of the tree is 3, which indicates that the packet relay device 12 is connected through the network 23 of the fourth route information unit. The structure thus constructed is the tree topology itself of FIG.

(2) Packet Configuration Procedure Each packet relay device always selects and holds the route information unit sent for each interface by the optimum route algorithm. The interface into which each route information unit has entered is recorded as the next hop. Hereinafter, the procedure for forming the output packet will be described step by step (each step is indicated by step) with reference to FIG. (Step 1) Each packet relay device holds the route information unit sent for each interface. Here, the information includes only those which have already been selected as the optimum route by the optimum route selection algorithm. (Step 2) The value of the pointer indicating the depth of the tree of all the route information units is incremented by 1. (Step 3) The packet relay device is configured to configure the route information unit of the network, which has received each interface information, by inputting the address of the port to be output in its interface ID and 1 in the pointer indicating the depth of the tree. Connect before. (Step 4) The interface information received from the same network is integrated under the same one route information unit, and each interface information is collected to form a packet. However, if the constructed packet exceeds the maximum packet length of the transmission path, the packet header is divided into serial numbers and transmitted.

As described above, when the route information unit is selected as the optimum route, as described later, when the route information unit is to be deleted, when the route information unit is deleted, the entire partial tree having the route information unit as the root is deleted. Therefore, the value of the pointer indicating the depth of the tree is such that the format that can form the tree topology is maintained as the input packet. The operation of adding 1 to the pointers indicating the depths of all trees does not impair the configuration of the tree topology, and therefore the tree topology is not changed by the processing of step2. Furthermore, step3
Then, by adding the route information unit of the directly connected network, the tree topology unique to the packet relay device is added. In addition, to combine the route information unit branches received from the same network in step 4, the value of the pointer indicating the depth of the tree is 2
The value of the pointer indicating the depth of the tree is 1, that is, the connection between this network relay information unit and the packet relay apparatus direct connection network is guaranteed.

By constructing the packet by these processes, the route information packet is transmitted by configuring the optimum route information unit to each network of the source packet relay device in a tree topology.

(3) Interface Down Flag and Interface Up Flag Rule The interface down flag and the interface up flag will be described below. If this flag is not present, a timer that causes the deletion of the route information unit from the routing table always occurs before the interface goes down and comes up, and routing cannot be performed during that time. Attaching the down flag has almost the same meaning as using the maximum number of metrics, but attaching the up flag makes it sensitive to the situation where the interface up information flows again after the down flag is established. it can.

There are the following two conditions for establishing the down flag. One of them is when the timer of the interface of the local packet relay device times out. That is, when the condition of interface down in the conventional technology is satisfied. The other is when the down flag is set on the route information unit of the input packet and is updated in accordance with the following item (4) "update rule in each packet relay device".

The conditions for establishing the up flag are as follows.
On the street. One of them is when the interface is up again, or when it is first launched. The other is when the up flag is set on the route information unit of the input packet and is updated according to the following item (4) "update rule in each packet relay device".

There are the following three conditions for clearing the down flag. First, the route information unit having each down flag is deleted together with the subtree having the route information unit at the root when the timer of the route information unit times out. This time-out value is the same value as when the route information unit having the maximum metric value in the prior art is deleted.

The second is when the up flag is set in the route information unit having the same network information unit as the one in which the down flag of the input packet is set, and the third is when the route information unit higher in the tree is down. When the flag is established, this down flag is cleared.

There are the following three conditions for clearing the up flag. First, the route information unit with the up flag runs a timer from when the up flag is set, and clears the up flag with a time-out value for setting the down flag of the direct connection network.

Second, the route information unit having the same network information unit as the up flag of the input packet has a down flag, and the fourth) item "update rule in each packet relay device" shown below is set. In the third case, the up flag is cleared when the down flag is established in the upper path information unit in the tree.

In the above-mentioned clear rule, when the route information unit with the down flag or the up flag is updated with exactly the same information, the value of each timer is not reset. The down flag and the up flag are set and cleared according to the conditions of the above flags.

(4) Update Rule in Each Packet Relay Device The route information unit selection algorithm will be described below. FIG. 5 shows a flowchart of this algorithm. Each step of this flowchart will be described. (Step 11) The process for the incoming route information input packet is started by first searching for the interface ID of the own packet relay device. If a route information unit having such an interface ID exists, all the route information units corresponding to the tree having the route information unit as a root, that is, the branches, are discarded. (Step 12) Next, the route information unit with the down flag is searched from the route of the input packet in ascending order of the pointer value indicating the depth of the tree, and if found, the route from the own packet relay device to the route information unit is found. , The down flag of its own packet relay device is set when it matches with the optimum route so far. Then, other route information units on the branch having this route information unit as a root are discarded. (Step 13) After that, the optimal route information is selected for each route information unit in the ascending order of the optimal route information held for each interface and the value of the pointer indicating the depth of the tree from the route of the input packet. When one is selected from the other in each selection and is discarded, each route information unit on the subtree when it is set as the root is discarded. The processing is different when the down flag is set in the route information unit held by the packet relay device. At this time, if the interface IDs are different, the packet route information unit is unconditionally selected. When the interface IDs are the same, the packet route information unit is selected only when the up flag is set, and when not, the route information unit on the packet is discarded. If the down flag is not set, the route selection described in the related art is performed.

The above items (1), (2), and (3)
The embodiment is constructed by adding the provisions of the item (4) and the item (4) instead of the split horizon trigger update of the prior art.

The operation of this embodiment with respect to the slow convergence example 1 and the slow convergence example 2 described in the prior art will be described with reference to the drawings. FIG. 6 describes the slow convergence example 1 described in the prior art. 1 in this figure
1 to 13 are packet relay devices, and 21 is a network. Packet relay device 12 and packet relay device 13
, There is information on the network 21 in the route information units held by the packet relay devices, respectively. However, in the packet relay device 13, since it is written that the information of the network 21 comes from the interface ID of the packet relay device 12, even if the information is transmitted to the packet relay device 12, the above (4) According to the update rule described in Section), if the interface directly connected to the local packet relay device exists in the input packet, the route information unit on the subtree having the route information unit as the route is discarded. Information is discarded.

FIG. 7 shows the slow convergence example 2 described in the prior art.
About. In this figure, 11 to 16 are packet relay devices, and 21 is a network. Each of the packet relay devices 14 and 15 has a route information unit held by the packet relay device as shown in the figure. However, the packet relay device 14 has entered through the same interface of the packet relay device 16 as the packet relay device 15, and in order to update the route information unit with the down flag, the procedure described in (4) above is performed. As described above, the information of the network 21 of the packet relay device 15 is discarded in the packet relay device 14 because it is not updated unless the information has the up flag.

The following is a summary of the entire embodiment. It is possible to add the tree topology information to the packet format of the route information according to the item (1) of the above-mentioned embodiment, and the route to which each route information unit has been transmitted according to the item (2) of the above-mentioned embodiment is set to the above-mentioned method. According to the packet format according to the item (1) of (1), each packet relay device is given an output packet configuration procedure that enables reconfiguration as a tree topology again, and the interface disconnection information as in item (3) of the above embodiment is given. By defining the conditions for sending the restart information, it becomes possible to evaluate the reliability of the interface up / down information by the optimum route tree in the item (4) of the above embodiment, and the down information is old information. It will be transmitted to the end without being harmed by the network and will be restarted by the packet relay device that declared down. To ensure that the new is is. This is
This method surely updates old information and does not use the conventional technique, which is the reason why the traffic can be reduced in order to prevent random update information.

[0059]

As is clear from the above proof, the present invention does not use a trigger update by providing the route control means for controlling the route of the packet with the addition means for adding the topology information to the route control information. It can deal with the slow convergence failure described in the prior art. Therefore, a high-speed communication can be stably performed without causing an overload on the network caused by the trigger update.

[Brief description of drawings]

FIG. 1 is a block diagram showing a packet relay device module configuration according to a first embodiment of the present invention.

FIG. 2 is a packet format configuration diagram according to the embodiment.

FIG. 3 is an example network configuration diagram in which a tree-structured network topology is described using the packet format of the same embodiment.

FIG. 4 is an explanatory diagram showing a packet configuration procedure in the packet relay device in the embodiment.

FIG. 5 is a flowchart of a route selection algorithm in the same embodiment.

FIG. 6 is an explanatory view showing a coping operation for the first example of slow convergence in the embodiment.

FIG. 7 is an explanatory diagram showing a coping operation for the second example of slow convergence in the same embodiment.

FIG. 8 is a schematic diagram illustrating a conventional technique.

FIG. 9 is an explanatory diagram of a routing table

FIG. 10 is a state diagram of a packet relay device showing Example 1 of slow convergence.

FIG. 11 is a state diagram of a packet relay device showing a first example of slow convergence.

FIG. 12 is a state diagram of a packet relay device showing a first example of slow convergence.

FIG. 13 is a state diagram of a packet relay device showing a second example of slow convergence.

FIG. 14 is a state diagram of a packet relay device showing a second example of slow convergence.

FIG. 15 is a state diagram of a packet relay device showing a second example of slow convergence.

[Explanation of symbols]

 1 additional module 2 route control module 3 routing table 4 packet transmission / reception module 5 packet relay module 6, 7 network interface 8, 9 physical network

Claims (2)

[Claims] 1. A route control system comprising: interface means for a plurality of networks; packet relay means for relaying packets between the networks via the interface means; and route control means for selecting a route of the packet. A packet relay device having means for adding topology information indicating a connection state between networks. 2. The route control means is Bellman-for
The packet relay device according to claim 1, which performs route control based on the d algorithm.