KR100204476B1 - A method of optimal route setting in atm networks - Google Patents

Abstract

The present invention relates to a method for optimal path selection in an ATM network. The present invention, when receiving a call setup request message including the class and the destination from the source, the first step of searching for all routes connectable to the destination; A second step of calculating, for all the paths searched, the number of calls each path can accommodate to the class of a class having a higher bandwidth than the required class; A third step of calculating the number of calls that can accommodate the required class as much as possible in the remaining bandwidth after allocating the call by one higher class in the second step; A fourth step of selecting a path having a maximum number of calls by comparing the number of calls of each class obtained in the third step, and selecting a path having the maximum number of arcs obtained in the second step if there are a plurality of paths having the maximum number; And a fifth step of updating the remaining bandwidth of the selected path and setting up a call to the selected path.

Therefore, the present invention is effective in utilizing network resources more efficiently by reducing the rejection rate of a call of a large bandwidth class.

Description

A method of setting optimally a route in a ATM network

1 is a diagram illustrating a general ATM network structure.

2 is a flowchart illustrating a routing method in a general ATM network.

3 is a flowchart illustrating a path establishment method in an ATM network according to the present invention.

4 is a diagram illustrating a routing system in a general ATM network.

The present invention relates to a method for finding and establishing an optimal path in an ATM network. In particular, the present invention relates to searching for the remaining bandwidth of all connectable paths when setting up a call so as to reduce the rejection rate of a large bandwidth call by a predetermined algorithm. The present invention relates to a method for searching for an optimal path.

With the rapid development of information society, B-ISDN emerged as the next-generation communication network due to the increase of user's communication service demand. In B-ISDN, asynchronous so as to accommodate various narrow and wide bandwidth services regardless of band and speed The ATM mode, which is a delivery mode, is used as a basic delivery means.

Here, Asynchronous Transfor Mode (ATM) refers to high-speed transmission in asynchronous manner by dividing information to be transmitted into fixed short packet units called cells.

In general, services provided by ATM networks are classified into several classes having the same characteristics, and each class has a different bandwidth requirement.

Therefore, the routing algorithm in a multi-class switching system such as an ATM network must not only efficiently share network resources in order to improve network efficiency, but also inter-call interference with other classes, that is, use situations of other classes. This should reduce as much as possible the impact of the rejection rate of the current class.

In order to satisfy the above demands, the conventional ATM network selects a path that is randomly possible, selects a path with the least load (that is, a path with the highest remaining bandwidth), and sets a path according to a predetermined pattern. Has been considered, and the method of selecting a path with the least load among them has been most commonly used.

For example, when Host A requests a connection to Host B in an ATM network, as shown in FIG. 1, the switching node ㉮ to which Host A is joined attempts to call the switching node 호스트 to which Host B is subscribed. do.

In this case, there are three paths that can be connected between the switching node and the switching node.The remaining bandwidth of path 1 is 11Mbps, the remaining bandwidth of path 2 is 16Mbps, the remaining bandwidth of path 3 is 20Mbps, the remaining bandwidth of path 2 is 16Mbps, Assume that the remaining bandwidth of path 3 is 20 Mbps. Also assume that Class 1 is a service that requires 1Mbps, Class 2 is 3Mbps, and Class 3 is 6Mbps.

2 is a flowchart illustrating a route setting method in a general ATM network. Referring to FIG.

When a request for a class 2 (required bandwidth: 3 Mbps) call is received from the host A to the switching node S (S1), the switching node S searches for all paths that can be connected to the switching node S (S2), and then the search. Path 3 (the remaining bandwidth: 20 Mbps) having the largest residual bandwidth among the selected paths 1, 2, and 3 is selected (S3), and the remaining bandwidth of the path 3 is updated to 17 Mbps (20 Mbps-3 Mbps = 17 Mbps) (S4). After the call is set to the selected route 3 (S5), the call setup message is transmitted to the switching node (S6).

In this state, if there is a call setup request of class 3 (6 Mbps) with a larger bandwidth than class 2, path 3 is allocated with the largest remaining bandwidth of 17 Mbps. Can hold up to)

However, if a path other than path 3 is allocated to the class 2 path allocation, the class 3 can fully use the remaining bandwidth of 20 Mbps. Can hold up to)

Therefore, the conventional minimum load selection method results in a reduction in the number of class 3 calls that can accommodate a class 3 call from three to two, thereby increasing the probability that the call request of the class 3 is rejected. That is, the conventional minimum load selection method has a relatively good rejection characteristics and traffic characteristics, but there is a problem that a call with a large band is deprived of a call access opportunity relatively than a call with a small band.

Accordingly, the present invention has been made to solve the above problems, and when the call request, the ATM to search for the remaining bandwidth of all paths that can be connected between the two hosts to reduce the rejection rate of a large band call according to a predetermined algorithm. The purpose is to provide a routing method in the network.

According to the method of the present invention for achieving the above-described rule, in an ATM network having a plurality of nodes interposed between a source and a destination, if the source requests a connection with a destination in a predetermined class, the ATM network receives the destination from the private source. An ATM network configured to set an optimal route in consideration of bandwidth of each route, comprising: a first step of searching for all routes connectable to the destination upon receiving a call setup request message including a class and a destination from a source; A second step of calculating, for all the paths searched, the number of calls that each path can accommodate the call of a class having a higher bandwidth than the required class; For all the searched paths, a path having a maximum number of calls is selected by allocating a call of one class higher class in the second step and comparing the number of calls that can accommodate the required class to the remaining bandwidth. A fourth step of selecting a path having the maximum number of arcs obtained in the second step if there are a plurality of phosphorus paths; And a fifth step of updating the remaining bandwidth of the selected path and setting up a call to the selected path.

That is, when a call request is generated from a host, the present invention searches for all paths that can be connected to the destination, and, after receiving the call of the class having a larger bandwidth than the corresponding class, for all the found paths, The number of arcs of the corresponding class that can be accommodated as much as possible is calculated, and a path having the maximum calculated number is selected.

Therefore, by setting up a call on the selected path and transmitting a call setup message to a destination node, the rejection rate of a call of a class having a relatively high required bandwidth can be reduced, thereby making more efficient use of network resources.

Hereinafter, an embodiment of the present invention will be described in detail with reference to the accompanying example drawings.

3 is a flowchart illustrating a method for selecting an optimal path in an ATM network according to the present invention, the method comprising: a tenth step (S10) of receiving a call establishment request message; A 20th step (S20) of searching for all routes connectable to the destination; A step (S30) of calculating the number of calls of the corresponding class that can accommodate the remaining bandwidth as much as possible after accepting the call of the class having a larger bandwidth than the corresponding class for all the found paths; A 40th step (S40) of selecting a path having the maximum number calculated; A fifty step (S60) of updating a remaining bandwidth of the selected path (S50); And a seventy step (S70) of transmitting a call setup message to a destination node according to the call setup.

Here, the thirty-third step (S30) may include a thirty-first step (S31) for calculating a quotient of all the paths by dividing the remaining bandwidth by the required bandwidth of the corresponding class; A 32nd step (S32) of calculating a quotient by dividing the remaining bandwidth by the required bandwidth of the class one step larger than the corresponding class; And a thirty-third step of multiplying the requested bandwidth of the one-level larger class by the value calculated in the thirty-second step (S32), subtracting the multiplied value from the remaining bandwidth, and dividing by the requested bandwidth of the corresponding class to calculate a quotient. (S33).

In addition, the 40th step S40 may include: a 41st step S41 of selecting a path having a maximum value calculated in the 33rd step S33; Determining whether there are a plurality of paths selected in the forty-first step (S41), and if not, the forty-second step (S42); A 43rd step (43) of selecting a path having a maximum value calculated in the 32nd step (S32) if a plurality of results are determined in the 42nd step (S42); A 44th step S44 of determining whether there are a plurality of paths selected in the 43rd step S43, and branching to the 50th step S50 if there are not a plurality of paths; And if the result of the determination in the 44th step is plural, the 45th step S45 of selecting a path having the maximum value calculated in the 31st step S31 and branching to the 50th step S50.

Next, the operation and operation of the present invention configured as described above will be described.

4 is a block diagram of a routing system in a general ATM network. The routing system in an ATM network includes: a cell receiver 1 for determining whether an ATM cell received from a host is a call establishment request message; When a call setup request message is input to the message processing unit 2 which receives the call setup request message, analyzes and processes the output call setup message, sets an optimum path by accessing the message 3, and then outputs a control signal. A processor 4; A switching unit (5) which performs a switching operation according to the control signal and exchanges user cells input from the cell receiving unit (1); It consists of a call setup message input from the message processing unit 2 and a cell transmitter 6 for transmitting the user cell input from the switching unit 5 to another node, the operation and the first and third degrees and The flow is as follows.

When host A requests a class B call establishment to host B, as shown in FIG. 1, the switching node " to which host A is subscribed attempts a call to the switching node " to which host B is subscribed.

That is, when a call setup request message is input from the host A to the switching node 를 via the cell receiver 1, the cell receiver 1 transmits the call setup request message to the message processor 2 (S10).

The message processing unit 2 extracts information related to signaling processing such as a destination address and a bandwidth from the input call establishment request message, and based on the extracted information, the processor 4 stores the memory 3 according to the flow of FIG. We will create a table to select the best path.

That is, the memory 3 stores all the information regarding the path setting. Once the call setting request message is input to the message processing unit 2, the processor 4 can read the destination address and connect with the destination. All paths are searched through the memory 3 (S20).

In this case, assume that there are three connectable paths between Node㉮ and Node㉯, that the remaining bandwidth of Path 1 is 11Mbps, the remaining bandwidth of Path 2 is 16Mbps, and the remaining bandwidth of Path 3 is 20Mbps. Also assume that class 1 is a service that requires 1Mbps, class 2 is 3Mbps, and class 3 is 6Mbps.

Accordingly, for all the paths 1, 2, and 3 found, the processor 4 accommodates the class 2 call, which is one step higher in bandwidth than the class 1, and then selects the class 1 that can accommodate the remaining bandwidth. The number of calls is calculated (S30).

The processor 4 compares the values calculated for the paths 1, 2, and 3 respectively, selects a path having the maximum value (S40), and then updates the remaining bandwidth of the selected path to the memory 3. Save (S50).

Accordingly, the message processing unit 2 sets up a call in the selected path (S60), transfers a call setup message to the cell transmitter 6, and transmits the call setup message to a destination node (S60). S70).

When the call setup process ends, the processor 4 informs the switching unit 5 of the selected path through a control signal, so that the switching unit 5 determines a user cell which is subsequently input from the cell receiver 1. Cell switching is performed through the path to the cell transmitter 6.

Accordingly, the cell transmitter 6 delivers the input user cell to the destination node.

Looking at one embodiment of the 30 th and 40 th steps S30 and S40 according to the present invention in detail, when the exchange node 교환 receives a call setup request message from the host A, the processor 4 performs a predetermined algorithm. Create a table as shown in Table 1.

That is, the switching node ㉮ updates the table shown in Table 1 every time a call is connected or released and stores it in the memory 3.

Where j = path, γ = remaining bandwidth of path j, b = the required bandwidth of class l, and M = the class whose bandwidth is one step larger than the corresponding class l that can best accommodate path j (l + 1) Number of arcs, M = Number of calls in class (l + 1) that is one step higher in bandwidth than the corresponding class l, M = Let's define the number of calls of class l that can accommodate the maximum of the remaining bands after the maximum number of arcs (l + 1) of the class bandwidth (l + 1).

If a call request of class 1 is received, the maximum number of calls that can be accommodated in paths 1, 2, and 3 are obtained.

Route 1, , Path 2 is 16, and path 3 is 20, respectively.

That is, for class 1, the maximum number of calls that can be accommodated in paths 1, 2, and 3 are 11, 16, and 20, respectively.

We can also find the number of class 2 arcs that can best accommodate paths 1, 2, and 3,

Route 1, , Route 2 is 5, and route 3 is 6, respectively.

That is, for class 1, the maximum number of class 2 calls that can be accommodated in paths 1, 2, and 3 is 3, 5, and 6, respectively.

In addition, if the maximum number of Class 2 calls are accommodated in Paths 1, 2, and 3, and the number of Class 1 calls that can accommodate the remaining bands is obtained,

Route 1 is Path 2 is 1 and path 3 is 2 respectively.

That is, for Class 1, after the maximum number of Class 2 calls are accommodated in Paths 1, 2, and 3, the number of Class 1 calls that can be accommodated in the remaining bands is 2, 1, and 2, respectively.

M by the same algorithm as above_jl, M_jl ^', M_jl Once the value is calculated, M along each path_jl By comparing M_jl Select the path with the largest value.

If, M_jl If two paths with the same value are selected, again M_jl ^'Compare values to M_jl ^'Select the path with the largest value. Still M_jl ^'If two paths with the same value are selected, M_jlCompare the values to select the path with the largest value.

For example, if the call was a class 1 call as described above, the values of paths 1, 2, and 3 are M._jl In comparison, of which M_jl Select paths 1 and 3 with the largest values, and again M for paths 1 and 3_jl ^'Compare the values, of which M_jl ^'Select path 3 with a large value.

Accordingly, the processor 4 stores in the memory 3 a value obtained by subtracting the required bandwidth of the corresponding class from the remaining bandwidth of the original path 3 to update the remaining bandwidth of the selected path 3.

That is, γ _j = γ _j -b _j = 20-1 = 19 (Mbps),

In the memory 3, the remaining bandwidth of path 3 is updated to 19 Mbps.

By the above algorithm, the values of Classes 2 and 3 can be obtained as shown in Table 1, so that the processor 4 selects an optimal path.

Therefore, if a call setup request message is entered, M_jl By selecting the path with the maximum value, the possibility of connecting a relatively high bandwidth call is slightly improved.

As described above, in the present invention, when a call is requested, all the paths that can be connected to the destination are searched, and after receiving the call of the class having a bandwidth greater than that of the corresponding class with respect to all the searched paths, the present invention corresponds to the remaining bandwidth. By calculating the number that can accommodate the call of the class, by setting the call to the path with the maximum number of the calculated number, and passing the call setup message to the destination node, it is possible to reduce the rejection rate of the call with a large bandwidth, The effect is to use it more efficiently.

Claims (2)

In an ATM network composed of multiple nodes between a source and a destination, if a source requests a connection with a destination in a predetermined class, the ATM network may set an optimal path in consideration of the bandwidth of each path from the source to the destination. In an ATM network, when receiving a call setup request message including a class and a destination from a source, a first step of searching for all paths connectable to the destination when receiving a call setup request message including the destination; A second step of calculating, for all the paths searched, the number of calls that each path can accommodate the call of a class having a higher bandwidth than the required class; A third step of allocating the calls of one class higher class to all the paths searched and calculating the number of calls that can accommodate the required class as much as the remaining bandwidth; A fourth step of selecting a path having the maximum number of calls by comparing the number of calls of each class obtained in the third step; And a fifth step of updating the remaining bandwidth of the selected path and setting up a call to the selected path. The method as claimed in claim 1, wherein the fourth step selects a path that can accommodate a call of a required class as much as possible from all the searched paths when the number of paths obtained in the second step is the maximum. Optimal route setting method in ATM network.