KR100231714B1 - Path Calculation Algorithm with multiple Quality of Service Constraints - Google Patents

Abstract

The present invention relates to a method for calculating a path of a call requiring multiple quality of service in a system including a source routing function such as a link state protocol. The present invention partially optimizes a selected parameter by allowing a user priority of selecting a parameter required for shortest path selection. As a path is provided and the service quality check is performed on the paths calculated so far during the path selection process, if the path that satisfies the requested quality of service is found, the path calculation is immediately terminated. Although not optimized for the parameters used in the selection, it provides a partially optimized path and guarantees fast path calculation time, and if there is a path in the network that satisfies multiple quality of service, one path must be performed through one algorithm. To find It is possible to select some optimized paths for specific parameters by reflecting the user's preferences, and by checking the service quality satisfaction check in parallel with the path selection work, even though there is an appropriate path that satisfies multiple service quality. It prevents the error of not finding the path, and makes it possible to find the path with only one algorithm.

Description

Path Calculation Algorithm with multiple Quality of Service Constraints}

The present invention relates to a quality of service routing method for selecting an appropriate path that guarantees all of the multiple quality of service in a system including a link state protocol which is a class of routing protocols.

The routing algorithms developed or proposed to date are largely divided into two categories.

One is to give a weight value for each of several quality of service, generate one value, and then generate the shortest path based on this value, and then check whether the requested quality of service is satisfied for the obtained path; The other method is to select one of the quality of service and then select the shortest path thereof to check whether the requested quality of service for the selected path is satisfied.

Common to both methods is that the shortest path is selected based on one parameter value, that is, a newly generated value or a selected value, and then the quality of service is checked for the selected path.

However, the first method has a disadvantage in that there is no appropriate policy or guideline in determining the weight value, and the selected path is too sensitive to one value generated with the weight value.

In addition, if both methods do not satisfy the requested quality of service, the same algorithm must be repeated several times by blocking the previously selected path and repeating the same algorithm again or reselecting the parameter to be used for shortest path selection. There is this.

In the worst case, this may result in the path not being found despite the proper path.

In order to solve the above disadvantages, the present invention makes it possible to find a path by performing a single algorithm when there is an appropriate path for a path request requiring multiple quality of service, and also fixes a parameter necessary for selecting the shortest path. The purpose is to provide a better quality of service by allowing a user to prioritize the selection of parameters, rather than selecting them arbitrarily or arbitrarily.

1 is a functional structural diagram of a system having a routing function of the present invention;

2 is a detailed structural diagram of a routing function unit of a system having a routing function of the present invention;

3 is a flowchart of a method for calculating a route requiring multiple quality of service to which the present invention is applied.

<Description of the symbols for the main parts of the drawings>

101: system management function 102: signal function / data processing unit

103: routing function unit 104: media control function unit

105: physical layer function unit 201: routing protocol

202: topology database 203: path calculation algorithm

In order to achieve the above object, the present invention is characterized by consisting of the process of selecting one parameter required for the shortest path selection from among several quality of service, and the process of selecting the shortest path for the selected parameters while satisfying all the quality of service at the same time do.

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

1 is a functional structural diagram of a system having a routing function of the present invention, a system management function 101 for performing functions related to overall system operation, a signal function for setting and releasing data channels or transmitting / receiving user data / A data processing unit 102, a routing function 103 for exchanging topology information with systems including other routing functions in the network, and a media control function 104 configured differently according to the characteristics of the physical network medium actually used. And a physical medium function 105 that performs the functions of physical, electrical, and optical characteristics, which are hardware control functions, as the lowest level among the functions on the protocol.

The system function management unit 101 performs functions related to overall system operation, and performs local management functions such as an operator interface, configuration management, and fault management, and a network management agent function. Some functions of the system configuration are performed in cooperation with the signal function / data processing unit 102 and the routing function unit 103.

The signal function / data processing unit 102 may be configured differently according to the characteristics of the network to which the present invention is applied. When the signal function / data processor 102 is applied to a non-connected network, the data function does not need a signal function because no preset operation of the data channel is required. The function of the processor is used, and in the case of a connected network, the signal function processor is used.

The routing function 103 exchanges topology information with systems including other routing functions in the network, which are used to find a path for signaling messages or user data to proceed, and for signaling and requesting such a path request and response. Interoperate with the data processing unit 102.

In addition, the media control unit 104 is configured differently according to the characteristics of the physical network medium actually used, Ethernet media control function (Medium Access Control, hereinafter referred to as MAC) when the physical network is Ethernet (Ethernet) Is used, and when an Asynchronous Transfer Mode (hereinafter referred to as ATM) network is used, an ATM medium control function, for example, ATM, ATM Adaptation Layer (hereinafter referred to as AAL) is used.

Other media control functions such as token ring can also be used.

The physical layer function unit 105 is the lowest level among the functions on the protocol and performs functions such as physical, electrical, or optical characteristics, which are hardware control functions.

This function also applies other functions according to the physical network characteristics used.

2 is a detailed structural diagram of a routing function unit of a system having a routing function of the present invention. The routing protocol 201, which is a link state protocol that dynamically operates among various known protocols and is highly scalable, includes all topology information generated by itself and other The topology database 202 maintains and manages topology information generated by all nodes, and a path calculation algorithm 203 performs a function of finding an appropriate path that satisfies all quality of service.

The routing protocol 201 of FIG. 2 refers to a link state protocol that is dynamically extensible and highly scalable among various well-known protocols.

This is a function of exchanging topology information with systems having other routing functions in a network. First, topology information about itself is generated, stored in the topology database 202, and distributed to other nodes.

It also compares topology information received from other nodes with information in its database and, if the received information is new or not in the database, all other adjacent nodes except the node that updated the topology database and sent the information. To redistribute them

The topology database 202 is a function for maintaining and managing all topology information generated by itself and topology information generated by all other nodes in the network. When all nodes in the network are synchronized by the routing protocol 201, all nodes are synchronized. They maintain the same topology database, which is used by the path calculation algorithm 203.

The path calculation algorithm 203 performs a function of finding an appropriate path according to its own needs or upon request of a path satisfying the multiple quality of service from the signal function / data processing unit 102 of FIG.

3 is a flowchart illustrating a route calculation method requiring multiple quality of service to which the present invention is applied.

First, when receiving a path request for a specific destination address together with a parameter requiring a single or multiple quality of service from a signaling function or data processing unit (S1), it is determined using a topology database whether a destination node including the received destination address exists. (S2).

If the destination node is not found as a result of the determination, a path calculation failure error is notified (S3), and if the destination node exists, the service node satisfies this for non-additive quality of service. Find and remove all links in the network that are not allowed (S4).

This is a method for improving the efficiency of the subsequent routing calculation algorithm. For each of the nodes excluding the set of nodes incorporated so far by the path calculation algorithm in the destination node existence determination step (S2) and the set of all nodes in the network. It may be placed anywhere between the steps of calculating the quality value and assigning it to C (n).

Next, it is determined whether a routing parameter value is included in the path request S1 for a specific destination address together with a parameter requiring a single or multiple quality of service from a signal function or a data processor (S5).

If the routing parameter value is not included as a result of the determination, a value automatically assigned by the system as a routing parameter for shortest path selection, for example, a manager's preference value for the link is assigned (S6), and the routing parameter value is included. Is used as a parameter for shortest path selection. However, the routing parameter selected here assumes that the smaller the value, the better the path.

In order to calculate the path, initialization of the following four parameters N, s, d, and M is required (S7).

N is a set of all nodes in the network, s is an originating node, i.e., a node performing route calculation, d is a called node, i. It represents the set of nodes incorporated so far by the algorithm and has the originating node {s} as the initial value.

From the originating node s defined in the initializing step S7 of the four parameters, a value of quality of service (1 (s, n)) is calculated for each n of nodes except N to M, and C (n). (S8).

C (n) contains items according to the type of quality of service, where s and n nodes are assigned to ∞ values for all items, and s and n nodes are adjacent to adjacent links. Assign each quality of service value to

If all items of the C (d) value, that is, the quality of service are compared with the quality of service requested in the route request step (S1) for the destination address (S9), and all are satisfied, the route calculated so far is delivered (S10). As a result of the determination, if the value of C (d) does not satisfy the requested quality of service, the value of C (d) is set to ∞ (S11), and N, which is a set of all nodes in the network, is compared with M (S12).

If the comparison result is equal to N and M, i.e., if the route calculation from the originating node to all other nodes is completed but no route is found that satisfies the requested quality of service, the route calculation failure is notified (S3). If M is different, select w to have the smallest routing parameter value among items of C (w) for all nodes w except for N in M and add it to M (S13).

For each node (n) in N, except for M, the previously calculated C (n) values (S8, S14) and C (w) values plus the new 1 (w, n) (S8, S14) Are compared with respect to the routing parameters, and all items of the smaller side are assigned to C (n) (S14).

The previously calculated C (n) value and the C (w) value plus the new 1 (w, n) value are compared with respect to the routing parameter and all the smaller items are assigned to C (n) (S14). ) Means adding 1 (w, n) to the C (w) value, which means that you can actually add a value, such as a cell propagation delay value, depending on the characteristics of the quality of service. It means you can also choose.

The same applies to routing parameters.

Each item of the recalculated C (d) value is compared with the quality of service requested in the route request (S1) step for the destination address (S9), and if the value is not satisfied, the value of C (d) is set to ∞ ( S11) When the result of the comparison satisfies all of the requested quality of service, the process ends after delivering the path calculated so far (S10).

As described above, in selecting a path that satisfies the multiple quality of service of the present invention, it is possible to select some optimized paths for specific parameters by reflecting the user's preferences, and to check whether the quality of service is satisfied. In parallel with this, even though there is an appropriate path that satisfies the multiple quality of service, the error of not finding the path can be prevented and the path can be found by only one algorithm.

Claims (3)

Routing function to exchange topology information with systems including system management function that performs functions related to overall system operation, signal function / data processing unit for setting and releasing data channel or transmitting and receiving user data, and other routing functions in the network. A routing function consisting of a physical control function unit configured differently according to the characteristics of the physical network medium actually used and a physical media function unit performing physical, electrical, and optical characteristics, which are hardware control functions, which is the lowest level among the functions on a protocol. In calculating a path that guarantees the quality of service of a system having: A first process of selecting one parameter from among several quality of service, And a second process of satisfying all the quality of service while simultaneously providing a partially optimized path for the selected parameter and ensuring a fast path calculation time. The method of claim 1, wherein the first process is A first step of receiving a route request for a specific destination address together with a parameter requiring a single or multipath quality of service from a signaling function or data processing unit; A second step of determining, via a topology database, the presence of a destination node including a received destination address; A third step of notifying a path calculation failure error if the destination node is not found as a result of the determination; A fourth step of removing all the links that do not satisfy the requested value by checking all links in the network for a quality of service having no additional attribute among the requested multiple quality of service if the called node exists as a result of the determination; A fifth step of determining whether a routing parameter value is included in a route request for a specific destination address together with a parameter requiring a single or multiple quality of service from a signal function or a data processing unit after all links are removed; A sixth step of allocating a value automatically assigned by the system as a parameter for selecting the shortest path when the routing parameter value is not included as a result of the determination; And a seventh step of using the included value as a parameter for selecting the shortest path when the routing parameter value is included in the determination result. The method of claim 1, wherein the second process The set of all nodes in the network (N) for the path calculation, the set of nodes (M), the originating node (s), the destination node (d), and the shortest path nodes from the originating node, thus far incorporated by the route computation algorithm Initializing a set of nodes incorporated by a calculation algorithm; Calculating and allocating a quality of service value (C (n)) for each (n) of nodes except N and M from the originating node defined in the initializing of the four parameters; A third step of comparing the quality of service with the quality of service requested in the route request step for the destination address and delivering a route calculated to date if all are satisfied; If the quality of service value does not satisfy the requested quality of service, setting the service quality value to infinity and comparing N and M, which are sets of all nodes in the network, with a fourth step; A fifth step of notifying a path calculation failure if N and M are equal after the comparison, that is, the path calculation from the originating node to all other nodes has been completed but the requested quality of service has not been satisfied; A sixth step of selecting and adding a value having the smallest routing parameter to all nodes except N in M if N and M are the same; Comparing the previously calculated value for each node except N to M with a new 1 (w, n) plus the quality of service value of the node having the smallest routing parameter value selected in the sixth step with the routing parameter And assigning a smaller item to a quality of service value of each of the nodes.

Images