JPH02190060A - Preset bypass system for packet exchange network - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] [Summary] Consisting of a plurality of stations that exchange packet data,
In a packet switching network that has multiple routes to a destination station that accommodates a destination terminal, each station on the route selects one of the multiple routes for each packet and transfers the packet to the destination station. Regarding the route determination power formula, and more specifically, regarding the advance detour method when a large number of packets are concentrated on one route, when route selection is performed using the fixed detour method in a packet switching network, when abnormal traffic concentration occurs, With the aim of realizing a detour operation with little impact on the other route, each station on the route contains route information for determining the route to the destination station, and transmission information for each route. storage means for storing detour setting information for setting whether or not to perform a detour when the number of request packets exceeds a predetermined threshold corresponding to each route before overflow; A first process of selecting a route by referring to the route information on the storage means corresponding to the destination station, and determining the number of transmission request packets corresponding to each selected route corresponding to the route. If the predetermined threshold is exceeded, the first process is repeated only for the transmission request packet corresponding to the destination station whose detour presence/absence setting information on the storage means indicates that there is a detour, and a second route is selected. and a step of transmitting each of the transmission request packets to each route selected by the first process after the number of transmission request packets corresponding to the route no longer exceeds the predetermined threshold corresponding to the route. and a control means for performing the processing in step 3.

[Industrial application field]

The present invention is a packet switching network that is composed of a plurality of stations that exchange packet data and has a plurality of routes to a destination station accommodating a destination terminal, and each station on the route sends a packet to the plurality of routes for each packet. The present invention relates to a route determination method for selecting one route and transferring the packet to its destination station, and more specifically relates to a pre-detour method when a large number of packets are concentrated on one route.

[Conventional technology]

In a packet switching network composed of multiple packet switches, the packet switch (
It has multiple packet transfer routes (hereinafter referred to as routes) to the destination station (hereinafter referred to as destination stations), and all packet exchanges 4m (hereinafter simply referred to as stations) on the relevant routes transfer the packets to the multiple routes for each packet. A method is adopted in which the packet is transferred to the destination station by selecting one of the routes and transferring the packet.

FIG. 6 shows the configuration of a -11u packet switching network.

In the same figure, for example, when transferring a packet from terminal 2X to terminal 2y, station I, one way 31 - station It one way 3d
- Station ID, station IA one way 3. - Station 1m → Route 36 - Station I
D, or station I^ one way 3c-station 1c one way 3f-station ID
A representative route selection is considered as follows.

In a packet-switched network like the one above, one
Conventionally, as a method for determining routes, each station has a table in which multiple routes to each destination station are stored in order of priority (for example, order of distance), and according to this priority order,
As shown in Figure 7, first select one route.
l) If the route is usable (packets can be sent), send packets to the route (Figures 32-33),
If the route in question is unavailable (packets cannot be sent), a fixed detour method is generally adopted in which the route with the next highest priority is selected and the same procedure as above is repeated (Figure 32-31). has been done.

That is, in FIG. 6, for example, when the station IA receives a packet from the terminal 2X, it first selects, for example, 3□ as the route with the highest (Z) priority, and if this route 31 is available, it selects the corresponding route. The station LE sends a packet to the route
forward the packet to.

Also, route 3. If the route is unavailable, the next route is
h is set to 55 ftJ', and if the route 3b is available, the packet is sent to that route and transferred to the station 1B. Thereafter, the same operation is repeated at the lower station that received the packet, and finally the packet is transferred to the station ID.

In the above-mentioned fixed detour method, the conditions for determining that the route is unusable, that is, route detour conditions, include exceeding the queue length of packets waiting to be transmitted due to abnormal concentration of traffic. In other words, each station stores received packets in the memory of the packet switch and makes each packet wait (packets in such a waiting state are called queues), and then stores them in each transmission waiting queue depending on the network traffic state. In this case, if queues for the same route are concentrated and the number of queues exceeds a certain number and the queue length exceeds, all packets related to that route are sent to the next priority route. I am detouring to.

For example, in FIG. 6, if station IA receives a large number of packets whose destinations are, for example, terminals not particularly shown that are accommodated in station 1n and station IE, from a plurality of terminals (not particularly shown) accommodated in the same station. , those packets are temporarily stored as transmission waiting queues in station IA, and route 3. is assigned as the first route corresponding to each of these queues. is selected, the queue length exceeds for that route.

Therefore, these routes 3. All packets relating to the route will be diverted to the next priority route, for example route 3c.

[Problem to be solved by the invention]

However, in the conventional fixed detour method described above, all packets that arrive on the route after the queue length exceeds are diverted to the next priority route, so a large number of packets flow into the next priority route. This results in an impact on the traffic that is originally being transferred on that route.

If such an event continues for a long time, excess traffic will be transferred to the next priority route, which will not only increase the delay time of traffic on the related route but also have a negative impact on the traffic of the entire network. This has the problem that it becomes a problem.

An object of the present invention is to realize a detour operation that has less influence on the other route when abnormal traffic is concentrated when a fixed detour method is used to select a route in a packet-switched network.

[Means to solve the problem]

FIG. 1 is a block diagram of the present invention. As shown in the figure, the present invention is a packet switching network that is composed of a plurality of stations that exchange packet data and has a plurality of routes to a destination station that accommodates a destination terminal, and each station on the route A packet transfer method is assumed in which one of the plurality of routes is selected for each route and the packet is transferred to its destination station.

Then, each station 4-14j, 4i, 4, . 4
．． It has the following means in the same direction. In addition, in FIG. 1, station 4. Shown only inside.

First, the storage means 6 stores, for each destination station, route information 7 that determines the route to the destination station, and a predetermined threshold corresponding to each route before the number of packets requested to be transmitted for each route overflows. This means stores detour setting information 8 for setting whether or not to take a detour when the detour is exceeded.

Next, the control means 5 selects a route to the destination station of each transmission request packet 10 by referring to the route information 7 on the storage means 6 corresponding to the destination station; If the number of transmission request packets corresponding to each selected route 9 exceeds the predetermined threshold corresponding to the route, the detour presence/absence setting information 8 on the storage means 6 indicates that there is a detour for the route. a second process for selecting another route by repeating the first process only for the transmission request packet corresponding to the destination station;
a third process of sending each of the transmission request packets to the route after the number of transmission request packets corresponding to each route selected by the first process no longer exceeds the predetermined threshold corresponding to the route; It is a means to do this.

[For production]

For example, station 4. In the storage means 6, for example, destination stations 4. ．． 4. 7. Route information for determining the route to each destination station for each destination station. ．． 7. etc. are memorized.

Same (For each destination station 4X, 4y, etc., whether to perform a detour when the number of transmission request packets for each route 9□, 9n, etc. exceeds a predetermined threshold corresponding to each route before overflowing. The detour presence/absence setting information 8X, 8y, etc. for setting the detour information is stored.The reason why a predetermined threshold value is provided for each route is that the permissible traffic amount often differs depending on the route.

Now, station 4. For example, the transmission request packet 10. ．．
10q, 10, etc. are received, the control means 5 first processes each transmission request packet 109.10qS.
The route information 7.10 to each destination station 4X, 4, etc. on the storage means 6 corresponding to the destination station. ．． 7. etc., and performs the selection process. Direction information 7. ．． 7. For example, route numbers and the like are stored in order of priority.

Through the above process, for example, route 90 is selected for transmission request packet 10°, route 9n is selected for transmission request packet 10q, route 91 is selected for transmission request packet 10t, etc. .

Subsequently, the control means 5 performs a second process on each of the selected routes 9. ．． If the number of transmission request packets corresponding to 9n, etc. exceeds the predetermined threshold corresponding to the route, the storage means 6
The detour presence/absence setting information 8 above, . 8. The first process is repeated only for the transmission request packet corresponding to the destination station on each route indicating that there is a detour, and the other route is selected.For example, if the transmission request packet 1
02.109,...Lot etc. destination station is 4X, 4y
As a result of the first process, the route 9 toward the station 4i is
．． Consider a case where allocation is concentrated on route 91 and the number of transmission request packets corresponding to route 91 exceeds the predetermined threshold.

Here, the predetermined threshold value does not reach a value that overflows the maximum number of packets that the route can accommodate, but it is a value that is quite close to it. In this case, with respect to the destination stations 4X and 4y related to the route 91, the detour presence/absence setting information 8X, 8y, etc. in the storage means 6 is referred to, and if the information indicates that there is a detour, the corresponding action is taken. The first process is again performed on the transmission request packet related to the destination station to cause the route to be detoured.

That is, for example, when the detour presence/absence setting information 8 regarding the destination station 4 indicates that there is a detour, only the transmission request packet corresponding to the destination station 4X is routed from the route 9° to the route 9, for example.
Detour to ゜. On the other hand, if the detour presence/absence setting information 8y regarding the destination station 4y indicates no detour, the transmission request packet corresponding to the destination station 4y is routed through route 9. , as it is.

After repeating the first process and the second process and the number of transmission request packets corresponding to each route 9°, 91, etc. no longer exceeds the predetermined threshold corresponding to the multi-way route, the control means 5 As processing, each transmission request packet is sent to the corresponding route 9□
, 9n, etc.

As described above, in the present invention, when the allowable number of transmission request packets for one route is about to overflow, only the transmission request packets to the destination station determined in advance as detour setting information are detoured. let As a result, if the number of transmission request packets (sending queue) for each route is concentrated due to abnormal traffic concentration,
It becomes possible to appropriately distribute the concentration to each route, and it is also possible to avoid concentration of transmission request packets on the other route due to the detour operation.

〔Example〕

Hereinafter, the present invention will be described in detail with reference to the drawings.

First, FIG. 2 is a diagram showing the configuration of each station (packet switch) in a packet switching network according to an embodiment of the present invention.

The communication control devices 131-13o are connected to each line 12-12.
This is a line-compatible device that sends and receives data to and from the network.

The control device 11 includes a line control processing section 14, a route selection processing section 15, and a packet processing section 17, and includes a line 12+
The packets input to and output from -12n flow as shown by the dashed line 18 in FIG.

The line control processing unit 14 is a processing unit that performs transmission and reception operations of data input and output via each communication control device 131 to 13°.

The route selection processing unit 15 determines the destination station of each processing packet according to the destination corresponding route determination table described later in the storage device 16 connected to the control bag Tl1l, and determines a route that can be sent to the destination station.・Send. Furthermore, if the received packet is addressed to the local station, it is a processing unit that notifies the packet processing unit of the packet.

The packet processing unit 17 notifies the terminal accommodated by the packet processing unit 17 of the packet notified by the route selection processing unit 15. Or
Route selection processing unit 1 routes packets from terminals accommodated by the own station.
5 and notifies (requests) transmission of the packet to the destination station.

Next, FIG. 3 is a diagram showing an example of a packet switching network constructed by connecting a plurality of stations having the configuration shown in FIG. 2.

Each of the stations 18^ to 18G accommodates a plurality of terminals, although not particularly shown, and as shown in the figure, there are a plurality of routes 19. ~19c...

Next, in the case of the station 18A of FIG. 3, the storage device 16 of FIG. 2 stores a destination corresponding route determination table as shown in FIG. 4. That is, each destination station 1811 to station 18
For each G, routes for the relevant station are stored in the order of the first candidate and the second candidate. Note that destination stations marked with "*" indicate stations to be bypassed in advance, which will be described later.

The packet transfer processing in Figs. 2 to 4 above is explained in Fig. 5.
This will be explained according to the operation flowchart shown in the figure. In addition, the fifth
The operation flowchart in the figure is based on the route selection processing unit 1 in FIG.
This is realized as a control program (not specifically shown) executed by 5.

First, for example, in the station 18a, when a packet is received via the communication control devices 13+ to 137 and the line control processing section 14 shown in FIG. 2, the route selection processing section 15 shown in FIG.
Execute the operation flowchart shown in the figure.

First, in FIG. 5, a route (hereinafter referred to as an output route) to which the received packet should be output is determined. That is, the route selection processing section 15 in FIG. 2 is connected to the control device 11 in FIG.
The destination corresponding route determination table shown in FIG. 4 in the storage device 16 connected to is referred to. Then, the route corresponding to the destination station indicated by the received packet is searched and determined in the order of the first candidate and then the second candidate. For example, if the destination station of a received packet is station 18m, 18n, or 18E, then route 19. is selected. Also, station 18c, 18F or 1
8a, route 19b is normally selected. The ranking of these routes is set, for example, in descending order of line distance.

Here, when a large number of transmission request packets are received at the station 18A, after the above-mentioned route selection, these packets are accumulated as a transmission waiting queue in an area not particularly shown in the storage device of FIG. 2 on each route side. be done.

In this case, each time the route selection is performed for each packet, it is determined at 35 in FIG. 5 whether or not the packet can be transmitted for each route. If it is impossible to send a packet because each route is full or a failure has occurred, the process returns to the process shown in FIG. 5 and determines another output route for the received packet. Specifically, the second candidate route in the destination corresponding route determination table of FIG. 4 is selected.

On the other hand, if it is possible to send packets for a certain route, the process proceeds to S6 in FIG. It is determined whether or not it exceeds. Here, the pre-detour regulation value is based on the number of packets that can be tolerated by that route, but it does not reach that value.
If the number of transmission waiting queues continues to increase, there is a risk of exceeding the permissible value, and although this value differs depending on each route, it is usually set to a value of about 60 to 80% of the permissible value.

As a result of the above determination, if the number of packets waiting to be transmitted is less than the pre-detour regulation value, the process proceeds to the process shown in FIG.

On the other hand, if the number of packets waiting to be sent exceeds the advance detour regulation value, the process proceeds to S7 in FIG. 5, and the destination corresponding route determination in FIG. The table is referred to, and it is determined whether each destination station is a pre-detour target station (whether it is a station marked with "*" in FIG. 4).

If the station is not the pre-detour target station, the packet waiting to be transmitted to the destination station is sent as is to the corresponding route in S8 of FIG. On the other hand, if the station is a pre-detour target station, the outgoing route determination process of FIG. 534 is executed again for the packet waiting to be transmitted to the destination station, and another route is selected.

Now, for example, route 19. When the number of packets waiting to be sent to the destination station is concentrated and the number of packets waiting to be sent exceeds the above pre-detour regulation value, the packets waiting to be sent whose destination station is the pre-detour target station in the waiting queue (packets waiting to be sent), that is, the number of packets waiting to be sent are In FIG. 4, only packets waiting to be transmitted whose destination station is the station 18m are detoured to the second candidate route 19b. On the other hand, packets waiting to be sent that are not pre-detour target stations, that is, packets waiting to be sent whose destination station is station 18o or 18E in FIG. will be sent to. As a result, station 1
The packet destined for 8a is from station 18A → route 19h → station 18
c one way 19c-station 18. route, and station 18
Packets destined for D (station 18E) are routed from station 18^ to route 1.
9. - Station 188 - The route of station 18D (station 18E) remains.

In the above detour operation, even when traffic is concentrated on route 19b, since station 18c is the only station to be detoured in advance from FIG. will be diverted to.

With the above operation, for example, in the packet switching network shown in FIG. 3, when traffic abnormally concentrates on route 191 or route 19b, instead of detouring all packets related to that route, a predetermined advance detour is performed. By detouring only the target station, packets can be appropriately distributed and transferred between routes.

〔Effect of the invention〕

According to the present invention, when traffic is abnormally concentrated between specific stations in a packet switching network, only packets destined for the specific stations can be detoured to other routes in advance before the route overflows. This makes it possible to realize appropriate load distribution of traffic.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of the present invention; FIG. 2 is a configuration diagram of an embodiment of the present invention; FIG. 3 is a diagram showing an example of a packet switching network to which the embodiment of the present invention is applied; 4 is a configuration diagram of a destination corresponding route determination table, FIG. 5 is an operation flowchart of an embodiment of the present invention, FIG. 6 is an explanatory diagram of routes in packet exchange and switching lines, and FIG. It is an operation flowchart in a conventional example. 41. 4 Direct, 4j... Station, 4X, 4y... Destination station, 5... Control means, 6... Storage means, 7, . 7. ...Route information, 8X, 8y ...Detour setting information, 9, . 9n・
...Route, 102.109, ... IOL ... Transmission request packet. In fact, the object of the present invention is 1 and r4, 7 to table t * husband same i column = see; L r< Qnko Figure 3 Patent applicant Fujitsu Ltd. Lecture on the tape 'le of the person who cheated on f. Flowchart of the implementation sequence 1 Step 4
Yuyumi 1c O 1 Brochure Flow Chart Figure

Claims (1)

[Claims] Consisting of a plurality of stations that exchange packet data,
In a packet switching network that has multiple routes to a destination station that accommodates a destination terminal, each station on the route selects one of the multiple routes for each packet and transfers the packet to the destination station. In the transfer method, each station (4) on the route includes, for each destination station, route information that determines the route to the destination station, and information on the route before the number of packets requested to be transmitted for each route overflows. A storage means (6) for storing detour setting information for setting whether or not to perform a detour when a predetermined threshold corresponding to each route is exceeded; a first process of selecting by referring to the route information on the storage means corresponding to the destination station, and the number of transmission request packets corresponding to each selected route exceeds the predetermined threshold corresponding to the route; If the detour presence/absence setting information on the storage means indicates that there is a detour, the first process is repeated only for the transmission request packet corresponding to the destination station related to the route, and a second route is selected. and a third step of transmitting each of the transmission request packets to each route selected by the first process after the number of transmission request packets corresponding to the route no longer exceeds the predetermined threshold corresponding to the route. A pre-detour method for a packet switching network, characterized in that it has a control means (5) that performs processing.