JP5071245B2 - Packet switching apparatus and program - Google Patents

Description

  The present invention relates to a packet route control technique in a packet network.

  In a packet network composed of packet switching devices called routers and switches, switching devices usually exchange route information to create a route table, thereby determining the interface to which received packets should be sent. (See, for example, Non-Patent Documents 1 and 2.)

  In addition, in order to perform more detailed route control according to the traffic situation of the network, instead of determining the interface to be sent only with the destination address of the packet, it is a flow unit, that is, for example, the destination address of the packet, the destination port number There has been proposed a flow routing for determining an interface to be transmitted by a combination of a transmission source address and a transmission source port number (for example, see Non-Patent Document 3).

J. et al. Moy, “OSPF Version 2”, RFC 2328, April 1998 R. Callon, “Use of OSI IS-IS for Routing in TCP / IP and Dual Environments”, RFC 1195, December 1990. Dr. Lawrence G. Roberts, “The Next Generation of IP-Flow Routing”, [online], July 29, 2003, Caspian Networks, [May 13, 2008 search], Internet <URL: http: // www. packet. cc / files / FlowPaper / NextGeneration of IP-FlowRouting. htm>

  For example, in the configuration shown in FIG. 1, the total cost to the network 6 is 10 for the route passing through the link 12 and 40 for the route passing through the link 13 when viewed from the switching device 1. The switching apparatus 1 sends a packet addressed to the network 6 to the link 12, that is, to the interface (IF) b.

  Here, when the packet addressed to the network 6 received by the switching device 1 exceeds the bandwidth of the link 12, the switching device 1 normally discards the portion of the packet that exceeds the bandwidth of the link 12. In order to avoid discarding the packet as much as possible, the use of another route can be considered, but if a packet is transmitted to a route with the lowest cost, the occurrence of a loop packet, that is, two or more switching devices There is a possibility that the packet will be forwarded in order. Loop packets are discarded when their maximum transfer hop count is exceeded, but in this case, it is advantageous to simply use the network bandwidth wastefully and immediately discard it in the switching equipment as before. . However, there is a route that does not generate loop packets. If the route does not generate loop packets, discarding packets can be suppressed by sending packets to this route instead of discarding them in the switching equipment. become.

  Accordingly, an object of the present invention is to provide a packet switching apparatus that reduces the number of packets discarded compared to the prior art and suppresses the generation of loop packets, and a program that causes a computer to function as the switching apparatus. .

According to the packet switching apparatus of the present invention,
Means for exchanging route information with another switching device to create a route table, and means for determining an interface to be used for transmitting packets belonging to the flow based on the route table when a new flow occurs. And the means for creating the route table includes: an optimum route based on a route selection criterion determined in advance from a route to the destination network, and another route located next to the route other than the optimum route. A route that does not include the device itself is determined as an optimum route in the route selection criterion from the switching device to the destination network, and an interface corresponding to the obtained route is an interface capable of transmitting a packet to the destination network. A route table is created.

According to another embodiment of the exchange device of the present invention,
Means for measuring the amount of traffic transmitted to each interface; and means for determining whether each interface is in a congested state based on the measured traffic amount and a threshold value. The determining means preferably determines an interface to be used for transmitting a packet belonging to a new flow from an interface that is not in a congested state.

According to another embodiment of the exchange device of the present invention,
A packet switching device for exchanging route information with other switching devices to create a route table, and when a new flow occurs, it is used to transmit packets belonging to that flow based on the route table A means for determining an interface; a means for measuring the traffic volume transmitted to each interface; and a means for determining whether each interface is in a congested state based on the measured traffic volume and a threshold. The means for creating the route table provides a link corresponding to the interface to an optimum route according to a predetermined route selection criterion to each destination network as seen from each switching device when the interface becomes congested. Change the cost value of the link corresponding to the interface so that it will not be included. Or the deletion of a link corresponding to the interface notifies the other switching device, the cost value of the changed or, and updates the routing table as the link is deleted.

Furthermore, according to another embodiment of the exchange device of the present invention,
It is preferable that the means for determining the interface continues to transmit the packet belonging to the flow that has been determined to use the interface before the interface even if the interface is in a congested state.

  A program for causing a computer to function as the exchange device is also provided.

  A route other than the optimum route to a certain destination network may cause a loop packet, but the own device is included in the optimum route from another switching device adjacent to the own device to this destination network. Since the unrouted route is a route in which no loop packet is generated, a route table including these routes is created. As a result, even if a certain interface is in a congested state, another route in which a loop packet indicated by the route table does not occur can be used, and the number of discarded packets can be suppressed. In addition, when the transmission interface becomes congested, the link corresponding to this interface is configured to update the route table in each switching device as being substantially deleted, so that the new flow is It will be sent to the optimal route at that time that does not include a link in a congested state, that is, a route in which a loop packet does not occur, thereby suppressing the number of discarded packets.

  The best mode for carrying out the present invention will be described in detail below with reference to the drawings. FIG. 1 is a configuration diagram of a network that executes path control according to the present invention. According to FIG. 1, the link 12 of the cost 10 connects the exchange device 1 and the exchange device 2, the link 13 of the cost 10 connects the exchange device 1 and the exchange device 3, and the link 34 of the cost 10 exchanges with the exchange device 3. The device 4 is connected, and the link 24 of the cost 20 connects the exchange device 2 and the exchange device 4. Further, the exchange device 1 is connected to the network 5 through a link of cost 10, the exchange device 2 is connected to the network 6, the exchange device 3 is connected to the network 7, and the exchange device 4 is connected to the network 8. The exchange device 1 is connected to the network 5 through an interface (IF) a, is connected to the link 12 through IFb, and is connected to the link 13 through IFc.

  Each switching device uses the link state type routing protocol described in Non-Patent Documents 1 and 2 to provide route information, specifically, the link connected to the own device, the cost of the link, and the connection destination. Exchange information about the interface of other exchange equipment. FIG. 2 is a route table generated by the exchange apparatus 1 when the exchange apparatus 1 is a conventional exchange apparatus. As shown in FIG. 2, the conventional switching apparatus obtains an optimum route based on a route selection criterion determined in advance for each destination network, and in this embodiment, a route with the lowest total cost of each link. The interface corresponding to the route is stored as a route table.

  FIG. 3 is a diagram showing a route table generated by the exchange apparatus 1 according to the present invention. The switching apparatus according to the present invention first obtains a route to a destination network and obtains an interface corresponding to each route by the same method as before. Among these, the interface corresponding to the optimum route based on the route selection criterion determined in advance for this destination network and its cost are set in the route table. Various known methods can be applied as the route selection criterion.

  Subsequently, for each route other than the optimum route to the destination network, the switching apparatus checks whether a loop packet has occurred. Specifically, the optimum route to this destination network is obtained from the switching device connected to the interface corresponding to the route other than the optimum route, and when the own device is included in this optimum route, the loop If a packet is generated and not included, it is determined that no loop packet is generated. When a loop packet does not occur, the interface and cost corresponding to the route are set in the route table.

  For example, in the switching apparatus 1 in FIG. 1, since a route including IFb and c is possible to the network 6 and the optimum route is IFb, IFb and its cost “10” are set in the route table. Subsequently, for the IFc that is not the optimum route, the optimum route from the switching apparatus 3 connected to the IFc to the network 6 is obtained. In this case, the optimum route is a route passing through the link 13 and the link 12, and the switching apparatus 1 is included in the route, so that it can be determined that a loop packet occurs. Therefore, the route corresponding to IFc is not set in the route table.

  Similarly, in the switching apparatus 1 of FIG. 1, since a route including IFb and c is possible to the network 8 and the optimum route is IFc, IFc and its cost “20” are set in the route table. . Subsequently, for the IFb that is not the optimum route, the optimum route from the switching apparatus 2 connected to the IFb to the network 8 is obtained. In this case, since the optimum route is a route passing through the link 24 and the switching apparatus 1 is not included in the route, it can be determined that no loop packet is generated. Therefore, IFb and its cost “30” are stored in the route table. Set.

  In addition, the switching apparatus according to the present invention monitors the amount of traffic transmitted to each interface. For example, a threshold is set in advance for each interface as a percentage of the maximum bandwidth. When the amount of traffic transmitted to an interface exceeds the threshold for this interface, this interface Is congested, that is, the link corresponding to this interface is determined to be congested. When a new flow occurs, the interface to be used for transmitting packets belonging to the newly generated flow is determined from the interfaces that are not congested among the interfaces to the destination network of this flow in the route table. The correspondence between the new flow and the determined interface is set in the transfer table. Thereafter, when the switching apparatus receives a packet belonging to this new flow, it performs transmission according to the forwarding table. In other words, the interface determined to be used for transmission of packets belonging to the flow is not changed by the subsequent change in the congestion state of the interface. This determination is preferably performed in the order of the optimum route, that is, in order from the lowest cost.

  For example, it is assumed that a new flow addressed to the network A occurs in the state having the route table shown in FIG. If IFa1 is not in a congested state when this new flow occurs, the switching apparatus determines that IFa1 is used for packets belonging to this new flow, and sets the combination of this new flow and IFa1 to the transfer table. Set to. Thereafter, when receiving a packet belonging to this new flow, the switching apparatus transmits the received packet to IFa1 according to the forwarding table even if IFa1 is congested at the time of reception. However, if another new flow for network A occurs when IFa1 is congested, the switching device belongs to this other new flow unless IFa3, which is the next lowest cost, is not congested. It is determined that IFa3 is used for the packet, and a set of another new flow and IFa3 is set in the forwarding table. Thereafter, when receiving a packet belonging to another new flow, the switching apparatus transmits the received packet to IFa3 according to the forwarding table even if IFa1 is not congested at the time of reception. Note that packets of flows that occur when all possible routes are in a congestion state are discarded.

  A flow is a unit indicating individual communication between terminals. For example, a flow is a combination of a destination address and a transmission source address or a combination of a destination address, a destination port number, a transmission source address, and a transmission source port number. It is specified.

  As described above, in the present invention, the switching device searches not only the optimum route but also an alternative route in which a loop packet does not occur in advance, creates a route table indicating both the optimum route and the alternative route, and a flow occurs. A route to be used for this flow is determined based on the congestion state of each interface at the time. This makes it possible to suppress the number of discarded packets while preventing the generation of loop packets.

  Subsequently, another embodiment of the present invention will be described. In this embodiment, the switching apparatus creates and saves the same route table as shown in FIG. 2 and saves a packet belonging to the newly generated flow based on the route table when a new flow occurs. The interface to be used is determined, and the correspondence between this new flow and the determined interface is set in the transfer table. Thereafter, when the switching apparatus receives a packet belonging to this new flow, it performs transmission according to the forwarding table. In addition, when the interface is congested, the switching apparatus according to the present embodiment supports the interface while maintaining the transmission to the interface based on the forwarding table while maintaining the transmission to the interface. The other switching apparatus is notified that the link has been deleted, causes the other switching apparatus to update the routing table, and the routing table is updated assuming that the interface in the congestion state has also been deleted. As a result, the route including the link corresponding to the interface in the congested state is not included in the optimum route to each destination network as seen from each switching device. Therefore, the new route generated after the congested state is generated. The flow will be transferred using another route that does not include this congested link, avoiding packet discard. Since all the switching devices update the route table on the assumption that the interface that has become congested has been deleted, loop packets do not occur in packet transfer using the updated route table.

  Also, when an interface that is in a congested state is no longer congested, the switching device adds this interface and updates the route table, and notifies the other switching device of the addition of this interface, so that the other switching The device also updates the route table.

  Note that when an interface becomes congested, this interface is treated as deleted, and when an interface that is in a congested state is no longer congested, this interface is not treated as an added one. It is also possible to use a form in which it is handled as if it was substantially deleted by changing. In other words, when an interface becomes congested, the cost of the interface is changed to a very large value, and the changed value is notified to other switching devices, so that each destination network seen from each switching device It is also possible to adopt a form in which the link corresponding to this interface is not included in the optimum route to In this case, when an interface that has been in a congested state is no longer in a congested state, the cost of the link corresponding to this interface is returned to the original value, and this original value is notified to other switching devices.

  Note that the above-mentioned very large value includes, for example, a value that is equal to or greater than the value obtained by multiplying the maximum cost assigned to a link in the network by the number of links in the network, or all links in the network. A value equal to or higher than the total cost can be used.

  As described above, in this embodiment, at the time of becoming congested, the flow existing in the link that has become congested is maintained on the link by the forwarding table, but is newly added to the route including this link. Update the route table as if this link was deleted, or change the cost of this link to a very large value, and at the same time, the cost of deleting or changing this link The value is notified to another switching apparatus, and the routing table is updated also in the other switching apparatus. As a result, a new flow can be caused to flow through another path that does not generate a loop packet and does not include a link in a congested state, thereby suppressing packet discard.

  FIG. 5 is a block diagram of an exchange apparatus according to the present invention. In FIG. 5, the interface 41 transmits and receives packets, and when the exchange processing unit 42 receives a packet belonging to a new flow for the first time, it refers to the route table 43 and transmits the packet belonging to this new flow. The interface 41 is determined, and the correspondence between the new flow and the determined interface 41 is set in the transfer table 46. Thereafter, when receiving a packet belonging to this flow, the exchange processing unit 42 transmits the packet from the interface 41 indicated by the transfer table 46. The traffic monitoring unit 44 monitors the traffic volume of the packet transmitted by the interface 41 and notifies the routing control unit 45 of the traffic, and the routing control unit 45 communicates with other switching devices and route information via the switching processing unit 42 and the interface 41. And the route table 43 is created.

  In the first embodiment, the routing control unit 45 creates the route table 43 shown in FIGS. 3 and 4, determines the occurrence of congestion based on the notification from the traffic monitoring unit 44, and exchanges the interface in the congestion state Notify the unit 42. When a new flow occurs, the exchange processing unit 42 determines a route, that is, an interface, for transmitting a packet belonging to the new flow, based on the route table 43 and the congestion state of the interface.

  Further, in the later embodiment, when a congested interface occurs, the routing control unit 45 assumes that the link corresponding to this interface has been deleted as described above, or the cost of this link is very high. The value is changed to a large value, and the cost after deletion or change is notified to another switching apparatus, and the route table 43 is updated. When the congested interface is no longer congested, the routing control unit 45 adds this interface, or returns the cost of this interface to the original value and updates the route table, and supports this interface. The link to be added or the original cost value of this link is notified to other switching devices.

  The exchange apparatus according to the present invention can be realized by a program that causes a computer to function as each unit in FIG. These computer programs can be stored in a computer-readable storage medium or distributed via a network.

It is a block diagram of the network which performs the route control method by this invention. It is a route table by the conventional exchange apparatus. It is a figure which shows the routing table which the exchange apparatus by this invention produces | generates. It is a figure explaining the route control method of the present invention. It is a block diagram of the exchange apparatus by this invention.

Explanation of symbols

1, 2, 3, 4, 51 Switching device 5, 6, 7, 8 Network 12, 13, 24, 34 Link 41 Interface 42 Exchange processing unit 43 Route table 44 Traffic monitoring unit 45 Routing control unit 46 Forwarding table

Claims (4)

A packet switching device,
Means for exchanging route information with another exchange device to create a route table;
Means for determining an interface to be used for transmission of a packet belonging to the flow based on a route table when a new flow occurs;
With
The means for creating the route table is based on the route to the destination network.
Find a first optimal route with predetermined route selection criteria ,
Further, the means for creating the route table obtains the optimum route to the destination network from the switching device connected to the interface corresponding to the route other than the first optimum route, based on the route selection criterion, and Find the second optimal route that does not include your device in the route ,
Creating a route table in which interfaces corresponding to the first and second optimum routes are interfaces capable of transmitting packets to the destination network;
Exchange equipment. A means of measuring the amount of traffic sent to each interface;
Means for determining whether or not each interface is in a congested state based on the measured traffic volume and a threshold value;
The means for determining the interface determines an interface to be used for transmission of a packet belonging to a new flow from an interface that is not in a congestion state.
The exchange device according to claim 1. The means for determining the interface continues transmission to the interface for packets belonging to a flow that has been determined to use the interface before the interface even if the interface is congested.
The exchange device according to claim 1 or 2 . A program for causing a computer to function as the exchange device according to any one of claims 1 to 3 .

Images