JP4678689B2 - Inter-domain path quality class assignment method, program, and storage medium thereof - Google Patents

Description

  The present invention relates to an inter-domain path quality class assigning method, a program, and a storage medium thereof, and more particularly, to satisfy an end-to-end quality required for an inter-domain path while reducing a minimum cost inter-domain path. The present invention relates to an interdomain path quality class assignment method that can be set, a program, and a storage medium thereof.

  A large-scale network is configured by connecting a plurality of networks (hereinafter referred to as a domain) whose protocols or network managers are different from each other.

In such a large-scale network, when setting up an inter-domain path with end-to-end required quality values, there is a technology that reduces the resource consumption of the path within its own domain where each domain constitutes an inter-domain path. It is disclosed in Non-Patent Document 1. Here, the lowest quality class is assigned to the path within the own domain within a range in which the path quality required between the own domain and the destination domain is satisfied at least in the path within the own domain.
R. Zhang and J.-P. Vasseur, Ed., "MPLS Inter-Autonomous System (AS) Traffic Engineering (TE) Requirements," IETF RFC4216, Nov. 2005.

  In the above prior art, each domain assigns the lowest quality class to its own intra-domain path as long as the required path quality to the destination domain is satisfied by its own intra-domain path. If the number of downstream domains is large or the quality class that can be assigned in the downstream domain is low, the end-to-end of the inter-domain path is likely to fail to satisfy the required quality. The path setup request loss rate increases.

  The object of the present invention is to solve the above-mentioned problems of the prior art, and to satisfy the end-to-end quality required for the inter-domain path, while setting the minimum cost inter-domain path quality. To provide a class assignment method, a program, and a storage medium thereof.

  In order to achieve the above-described object, the present invention determines a quality class to be assigned to an intra-domain path constituting an inter-domain path in response to an inter-domain path setting request passing through a plurality of domains including the own domain. The domain-to-domain path quality class assigning method is targeted, and each domain includes the following procedure.

  That is, the number of downstream domains from the own domain of the inter-domain path to the predetermined destination domain, the procedure for setting the quality value Q that the inter-domain path should satisfy between the own domain and the destination domain, and the number of downstream domains For each N and quality value Q, solve the mathematical model that minimizes the sum of the amount of resources used in all transit domains from the local domain to the destination domain, and the quality that can be assigned to each intra-domain path by the downstream domain including the local domain A procedure for calculating class candidates, a procedure for receiving an inter-domain path setting request and obtaining information about the number N of downstream domains and the quality value Q in the inter-domain path, and corresponding to the number N of downstream domains and the quality value Q The procedure for selecting a quality class candidate and the assignment to the intra-domain path constituting the inter-domain path from the quality class candidates. A procedure for determining the quality class that, characterized in that it comprises a procedure for transferring the inter-domain path setting request updated based on the quality class assigned to the own intradomain path downstream domain.

  According to the present invention, it is possible to reduce the rate of loss of request for setting an inter-domain path through which each domain passes through its own domain while satisfying the end-to-end quality required for the inter-domain path.

  DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, the best embodiment of the present invention will be described in detail with reference to the drawings. FIG. 1 is a diagram schematically showing the configuration of the main part of an inter-domain network to which the quality class assignment method of the present invention is applied. A plurality of networks (domains) having different protocols and network administrators are shown in FIG. Are connected to each other via a border router BR installed at the border of the network, and a policy server PS is connected to each border router BR. Here, taking the inter-domain path Pad with the end node a of the domain A as the source and the end node d of the domain D as the destination, the quality to the path within the own domain that constitutes the inter-domain path Pad in each domain The class assignment method will be described.

  FIG. 2 is a flowchart showing the procedure of the quality class assignment method in the present embodiment. The policy server PS connected to the border router BR of each domain A, B, C, D through the inter-domain path Pad is autonomous. Is executed automatically.

  In this embodiment, the number of downstream domains from the own domain to the destination domain on the inter-domain path so that the optimal quality class for the path within the own domain can be immediately determined when an inter-domain path setup request is detected in each domain. Quality that can be assigned to the path within the own domain for each quality value that the inter-domain path should satisfy between the own domain and the called domain (including the own domain and the called domain). Class candidates are registered in advance in each policy server PS (step S1), and when the inter-domain path setting request arrives thereafter, the quality class candidates are determined based on the number of downstream domains and the quality value of the requested path. Extract from PS and select the best quality class for the domain from the quality class candidates in an autonomous and distributed manner. Assign to paths (steps S2 to S5).

  Hereinafter, the operation of the present embodiment will be described in detail along the flowchart of FIG. In step S1, in each domain, a quality class candidate that minimizes the total amount of resources used in all the transit domains from the own domain to the destination domain is calculated for each quality value that the number of downstream domains and the interdomain path should satisfy. Registered in the policy server PS.

  Here, the number of downstream domains from the local domain to the destination domain (including the local domain and the destination domain) is N, and the inter-domain path should be satisfied between the local domain and the destination domain (including the local domain and the destination domain) Let Q be the quality value (quantized and expressed as an integer value). Also, C is the number of quality classes that can be set for each domain, qj is the path quality value in its own domain (quantized and expressed as an integer value) corresponding to quality class j, and rj is the resource usage of the path belonging to quality class j And

Assuming additive quality such as delay and discard rate, the mathematical model of the following constraints (1), decision variable (2) and objective function (3) is solved by integer programming, etc. At least one quality class selected is registered as a quality class candidate that can be assigned to the path within the own domain in association with the number N of downstream domains and the quality value Q.

  Here, xi, j of decision variable (2) is a binary having a value of “1” when quality class j is selected in the i-th downstream domain from its own domain, and a value of “0” when not selected. Is a variable. Therefore, the constraint condition (1) is that the sum of the path quality values qj corresponding to the quality class j selected in each downstream domain on the path is the quality value Q that the path should satisfy between its own domain and the destination domain. Is satisfied (≦ Q). The objective function (3) represents minimizing the total amount of resource usage in all transit domains from the own domain to the destination domain.

  FIG. 3 is a flowchart showing a procedure for calculating quality class candidates in step S1.

  In step S101, the number N of downstream domains (N is equal to or less than the total number of domains) and the quality value Q are set. In step S102, the above-described mathematical model is solved for the number N of downstream domains and the quality value Q, and the quality class that can be assigned to the path in the own domain is assigned a quality class selected in at least one of the downstream domains. It registers with the policy server PS as a class candidate.

  If the required quality value up to the destination domain cannot be satisfied even if the highest quality class is selected in all the downstream domains, there is no solution for the above mathematical model, and in this case, there is no assigned quality class candidate. The path setup request is considered a loss.

  In step S103, the mathematical model solution described above is repeated for all downstream domain numbers N and quality values Q. However, if the quality value Q is a discrete value instead of a continuous real number corresponding to each quality class j, the possible quality value Q can be a discrete value. Only the value less than the required quality value of the inter-domain path between two ends and the required quality value minus the integer multiple including zero of the greatest common divisor of the own domain path quality value corresponding to all quality classes) The amount of calculation can be reduced by calculating.

  FIG. 4 shows an example of a mathematical model solution when the quality class number C is “5” and the downstream domain number N is “4” at a predetermined quality value Q. FIG. Quality class candidate allocation information to be stored in advance in the policy server PS in correspondence with the solution is shown.

  In FIG. 4, the quality class of the 0th downstream domain, that is, the intra-domain path of its own domain is “1”, the quality class of the intra-domain path of the first downstream domain (domain B in FIG. 1) is “3”, 2 The quality class of the intra-domain path of the third downstream domain (domain C in FIG. 1) is set to “2”, and the quality class of the intra-domain path of the third downstream domain (domain D in FIG. 1) is set to “1”. This means that the total amount of resource usage in the four downstream domains can be minimized while satisfying the predetermined quality value Q.

  However, if the addition type quality is assumed, the combination of the downstream domain and its quality class is arbitrary, so the quality class candidate allocation information held in the policy server PS is as shown in FIG. This assigns quality class 1 to any two of the four downstream domains, assigns quality class 2 to any one of the four downstream domains, and assigns quality class 3 to any one of the four downstream domains By not assigning the quality classes 0 and 4 to any of the downstream domains, it means that the sum of the resource usage in the four downstream domains can be minimized while satisfying the predetermined quality value Q.

  Returning to FIG. 2, when the arrival of the inter-domain path setting request is detected in step S <b> 2 thereafter in each domain, in step S <b> 3, the own domain is determined based on the path setting information registered in the inter-domain path setting request. The number N of downstream domains from the destination domain to the destination domain and the quality value Q that the interdomain path should satisfy between the own domain and the destination domain are recognized.

  The number N of downstream domains can be recognized based on, for example, the destination domain registered in the inter-domain path setting request and the inter-domain route information managed in the own domain. The quality value Q indicates that each domain relaying the inter-domain path setting request registers the quality class assigned in its own domain in the inter-domain path setting request, and each downstream domain that has received this inter-domain path setting request This can be determined by subtracting the quality value corresponding to the quality class assigned in each upstream domain from the quality value to be satisfied between the originating domain and the terminating domain.

  In step S4, quality class candidates corresponding to the number N of downstream domains and the quality value Q are searched from the policy server PS. In step S5, the quality class to be assigned to the path within the own domain is determined from the searched quality class candidates. In the present embodiment, the quality class is determined based on one of the following three methods.

  FIG. 6 is a flowchart showing the procedure of the first quality class determination method, and the lowest quality class among the quality class candidates is always assigned to the path within the own domain.

  In step S501, it is determined whether or not the quality class candidate selected according to the number N of downstream domains and the quality value Q is registered in the policy server PS. If already registered, the process proceeds to step S502. In step S502, it is determined whether or not a free resource amount corresponding to the lowest quality class (quality class 1 in the example of FIG. 5) among the quality class candidates can be secured in the domain, and if it can be secured, the process proceeds to step S503. . In step S503, the lowest quality class is assigned to the path within the own domain.

  On the other hand, in step S502, if the free resource amount corresponding to the lowest quality class among the quality class candidates cannot be secured in the own domain, the process proceeds to step S504. In step S504, regardless of the quality class candidate, it is determined whether or not there is a quality class that can be allocated within the free resource amount range. If there is a quality class that can be allocated, the process proceeds to step S505. In step S505, the highest quality class among the assignable quality classes is assigned to the path within the own domain.

  If it is determined in step S501 that the quality class candidate is not registered, or if it is determined in step S504 that there is no quality class that can be allocated within the free resource amount range, the current path setting request is lost. The

  FIG. 7 is a flowchart showing the procedure of the second quality class determination method, in which any of the quality class candidates is assigned to the number of assigned quality class candidates to the downstream domain (including its own domain) in the mathematical model. It is assigned to the path in its own domain with a corresponding probability.

  In step S511, it is determined whether or not a quality class candidate corresponding to the number of downstream domains N and quality value Q is registered in the policy server PS. If already registered, the process proceeds to step S512. In step S512, one quality class is selected from the quality class candidates with a probability corresponding to the number of assigned quality class candidates to the downstream domain based on the mathematical model.

  That is, if the quality class candidates are as shown in FIG. 5 and two quality classes 1, one quality class 2, and one quality class 3 are assigned to the downstream domain, the probability that the quality class 1 is 50% The quality classes 2 and 3 are all assigned with a probability of 25%.

  In step S513, it is determined whether or not the free resource amount Mi in the domain is equal to or larger than the predetermined resource amount Mj. If Mi ≧ Mj, the process proceeds to step S514. The resource amount Mj corresponds to the resource amount consumed in the quality class selected in step S512. In step S514, the quality class selected in step S512 is assigned to the intra-domain path.

  On the other hand, if it is determined in step S513 that the free resource amount Mi in the own domain is less than the resource amount Mj, the process proceeds to step S515. In step S515, as in step S504, regardless of the quality class candidate, the presence / absence of a quality class that can be allocated within the free resource amount is determined. If there is a quality class that can be allocated, the process proceeds to step S516. In step S516, as in step S505, the highest quality class among the assignable quality classes is assigned to the path within the own domain.

  FIG. 8 is a flowchart showing the procedure of the third quality class determination method, which is a combination of the first and second methods described above.

  In step S521, it is determined whether or not a quality class candidate corresponding to the number N of downstream domains and the quality value Q is registered in the policy server PS. If already registered, the process proceeds to step S522. In step S522, it is determined whether or not the free resource amount Mi in the domain is greater than or equal to a predetermined reference value Mref. If Mi ≧ Mref, the process proceeds to step S523.

  In step S523, one quality class is selected from the quality class candidates with a probability corresponding to the number of assigned quality class candidates to the downstream domain based on the mathematical model. In step S524, it is determined whether or not the free resource amount Mi in the domain is greater than or equal to the predetermined resource amount Mj. If Mi ≧ Mj, the process proceeds to step S525, and if Mi <Mj, the process proceeds to step S528. The resource amount Mj corresponds to the resource amount consumed in the quality class selected in step S523. In step S525, the quality class selected in step S523 is assigned to the own-domain path.

On the other hand, if it is determined in step S522 that the free resource amount Mi in the domain is less than the reference value Mref, the process proceeds to step S526. In step S526,
Similar to step S502, it is determined whether or not a free resource amount corresponding to the lowest quality class among the quality class candidates can be secured in the domain, and if it can be secured, the process proceeds to step S527. In step S527, the lowest quality class is assigned to the path within the own domain.

  In step S526, if the free resource amount corresponding to the lowest quality class in the quality class candidates cannot be secured in the domain, the process proceeds to step S528. In step S528, as in step S504, regardless of the quality class candidate, the presence / absence of a quality class that can be allocated within the free resource amount range is determined. If there is a quality class that can be allocated, the process proceeds to step S529. In step S529, as in step S505, the highest quality class among the assignable quality classes is assigned to the path within the own domain.

  As described above, when the assignment of the quality class to the path in the own domain is completed, in step S6, the path setting request is updated, and the quality class assigned to the path in the own domain is additionally registered. In step S7, the updated path setting request is transferred to the downstream domain. Thereafter, a route search is performed in the domain based on the quality class assigned to the path in the own domain, and a path in the own domain that satisfies the quality class is established in the domain.

  In each downstream domain, the own-domain path is sequentially selected based on the number N ′ of downstream domains and the quality value Q ′.

It is the figure which expressed typically the structure of the network between domains to which this invention is applied. It is the flowchart which showed the procedure of the quality class allocation method in this embodiment. It is the flowchart which showed the calculation procedure of the quality class candidate. It is the figure which showed an example of the solution of a mathematical model. It is the figure which showed an example of the quality class candidate allocation information hold | maintained at policy server PS. It is the flowchart which showed the procedure of the 1st quality class determination method. It is the flowchart which showed the procedure of the 2nd quality class determination method. It is the flowchart which showed the procedure of the 3rd quality class determination method.

Explanation of symbols

A, B, C, D ... domain
a, d ... End node
PS: Policy server
BR ... Border router

Claims (6)

In the inter-domain path quality class assignment method for determining a quality class to be assigned to an intra-domain path constituting an inter-domain path in response to a request for setting an inter-domain path passing through a plurality of domains including the own domain.
Each domain
A mathematical model that minimizes the sum of the amount of resources used in all transit domains from the own domain to the destination domain for each value that the inter-domain path can take as a quality value Q to be satisfied between the own domain and the destination domain. , Solving for each possible value as the number of downstream domains N, and calculating in advance a quality class candidate that can be assigned to each intra-domain path by a downstream domain including its own domain;
Receives the inter-domain path setting request, a step of recognizing information about a downstream domain number N and the quality value Q at the interdomain paths,
A procedure for searching for quality class candidates corresponding to the number N of downstream domains and the quality value Q from the calculated quality class candidates ;
A procedure for determining a quality class to be assigned to a path within the own domain that constitutes the inter-domain path from among the searched quality class candidates;
Look including a procedure for transferring the inter-domain path setting request updated based on the quality class assigned to the own intradomain path downstream domain,
The inter-domain path setting request includes information for subtracting the quality value corresponding to the quality class assigned in each upstream domain from the quality value to be satisfied between the destination domain and the originating domain and the destination domain. Registered,
The procedure for transferring the inter-domain path setting request to the downstream domain is to send an inter-domain path setting request so that the quality class assigned to the path within the own domain is added as the quality class assigned in each upstream domain that has passed through. A method for assigning a quality class of an inter-domain path characterized by updating . The procedure for determining the quality class assigned to the intra-domain path is as follows:
A procedure for assigning the lowest quality class to a path in the own domain when the amount of free resources in the own domain is larger than the amount of resources required for the lowest quality class among the quality class candidates;
When the amount of free resources in your domain is less than the amount of resources required for the lowest quality class among the quality class candidates, select the highest quality class among the quality classes that use less than the amount of free resources. The method for assigning a quality class for an inter-domain path according to claim 1, further comprising a step of assigning to a path within the own domain.   In the procedure for determining the quality class to be assigned to the path within the own domain, one of the quality class candidates is assigned to the path within the own domain with a probability corresponding to the number of assigned quality class candidates to the downstream domain in the mathematical model. The quality class allocating method for an inter-domain path according to claim 1.   In the procedure for determining the quality class to be assigned to the path within the own domain, if the free resource amount of the own domain is equal to or greater than a predetermined reference value, one of the quality class candidates is assigned to each quality class to the downstream domain in the mathematical model. Allocate to the path in the own domain with a probability corresponding to the number of candidate allocations, and if the free resource amount in the own domain is less than the predetermined reference value, assign the lowest quality class among the quality class candidates to the path in the own domain The quality class allocating method for an inter-domain path according to claim 1.   5. An inter-domain path quality class assignment program for causing a computer to execute the quality class assignment method according to claim 1.   6. A storage medium for an inter-domain path quality class assignment program storing the quality class assignment program according to claim 5 so as to be readable by a computer.

Images