CN1195363C - Method for evaluating route performances of quality of service based on linear structure - Google Patents

Abstract

The quality of service routing performance evaluation method based on linear structure belongs to the technical field of Internet routing performance evaluation, and is characterized in that: it is a basic linear energy function g (e)=∑ ^k _l=1 (a _l W _l (e)) and the Internet The multi-metric path problem can be transformed into a method that can use the Dijkstra algorithm to calculate the minimum energy path problem, where e is the link, l is the serial number of the k-weight measure, 1≤l≤k, a _l ∈ [0, 1] is the and chain The path e has nothing to do with coefficients and satisfies ∑ ^k _l=1 a _l =1; it first randomly selects source and destination node pairs (s, t) on the topological graph, and then from s to t according to the path linear energy function is equal to each The principle of the sum of the linear energy functions of the link uses the Dijkstra algorithm to establish a path with the minimum energy value, and then uses the metric value of the path as the constraint c of the node pair (s, t)’s QoS request, so as to ensure that the simulated A quality of service request for has a feasible path. Experimental results show that this evaluation method can not only represent the real application business, but also reflect the routing performance well.

Description

Quality of Service Routing Performance Evaluation Method Based on Linear Construction

technical field

A quality of service routing performance evaluation method based on a linear structure belongs to the technical field of Internet routing performance evaluation, and in particular relates to a quality of service routing evaluation method with multiple quality of service parameters as constraint conditions.

Background technique

There are two common methods for evaluating the performance of Quality-of-service (QoS) routing algorithms. (1) Competition rate: the ratio of the number of requests that the algorithm can find feasible paths to the number of requests that have feasible paths; (2) Routing success rate: the ratio of the number of requests that the algorithm can find feasible paths to the total number of simulated requests.

The difference between these two evaluation methods lies in whether the QoS request as the denominator must have a feasible path. These two methods have a common defect: the calculation result largely depends on the qualification condition of the generated QoS request, that is, the distribution of QoS constraints. Moreover, for large-scale network topology graphs, since it is difficult to judge whether a QoS request has a feasible path, the routing success rate has been widely used. However, the routing success rate depends on the constraints of the QoS request to a greater extent. Different documents use different generation methods, which leads to the loss of the evaluation significance of the absolute value of the routing success rate. It is only meaningful in the relative comparison of the same batch of data. , so the performance evaluation data given by different literatures cannot be directly compared.

Contents of the invention

The purpose of the present invention is to provide a linear structure-based QoS routing performance evaluation method.

The method that the present invention proposes is characterized in that: it first associates a group of k weights (w ₁ (e), w ₂ (e), ... , w _k (e)), that is, the quality of service measure w(e) of link e, and then based on the linear function of the link $g\left(e\right)={\mathrm{\Σ}}_{l=1}^k\left(a_l{w}_l\left(e\right)\right)$ Transform the multi-metric path problem of the Internet into a single metric that can be calculated by the Dijkstra algorithm, that is, a path problem with the minimum energy value, where 1 is the serial number of the k-weight metric, 1≤l≤k, a _l ∈ [0, 1] is a coefficient independent of link e and satisfies ${\mathrm{\Σ}}_{l=1}^k{a}_l=1$ ; It first randomly selects the source node and destination node pair (s, t) on the network topology graph, and then uses Dijkstra The algorithm establishes the path with the minimum energy value, and then uses the metric value of this path as the constraint condition c of the node pair (s, t)'s QoS request, so as to ensure that the simulated QoS request has a feasible path. The steps are as follows:

(1) use a computer to input the Internet topology graph G with k weight values (w ₁ (e), w ₂ (e), ..., w _k (e)) for each link;

(2) Randomly generate the source node s and target node t of the service quality request, and ensure that the minimum number of hops between (s, t) (that is, the number of nodes passed from s to t) is not less than 3;

(3) For all l=1, 2, ..., k, generate a uniformly distributed random number b _l ~uniform(0, 1) in the [0, 1] interval (that is, a uniform distribution in the [0, 1] interval) , and then order $a_l=b_l/{\mathrm{\Σ}}_{l=1}^k{b}_l;$

(4) Calculate the energy value of each link $g\left(e\right)={\mathrm{\Σ}}_{l=1}^k\left(a_l{w}_l\left(e\right)\right);$

(5) According to the above-mentioned energy value, take s as the tree root to calculate the shortest path tree (Shortestpath tree, SPT) with the energy value g(e) as the evaluation standard;

(6) Based on the path from s to t along the SPT, calculate each metric value of the path.

The experiment proves that this performance evaluation method can not only simulate the service quality request with practical significance, but also the simulated request has a feasible path, so it can extend the performance index routing success rate that can only be used for relative evaluation to absolute index competition At the same time, this method is easier to distinguish the performance surprises between different algorithms than other methods.

Description of drawings

Figure 1. Flow chart of performance evaluation method

Figure 2. Examples of instructions for use of performance evaluation methods

Figure 3. Examples of application results of performance evaluation methods

Detailed ways

For the convenience of description, we first give the directed graph model and several definitions.

Use a directed graph G(V, E) to represent a network, where V is a node set, and an element v∈V is called a vertex (node) of the graph G; E is an arc set, and the element e _ij ∈ E is recorded as e=v _i →v _j is called an edge of graph G. In QoSR, a set of mutually independent weights (w ₁ (e), w ₂ (e), ..., w _k (e)) associated with each link e is called the QoS measure of link e, abbreviated as w(e). Where w _l (e) ∈ R ⁺ is the measure of path constraint type, for 1≤l≤k. That is to say, for the path p=v ₀ →v ₁ →…→v _n , the weight $w_l\left(p\right)={\mathrm{\Σ}}_{i=1}^{\mathrm{no}}{w}_l(v_{i-1}\&Right\; Arrow;v_l)$ Additivity is satisfied.

Definition 1: Multiple constraint paths

For a given directed graph G(V, E), it contains source node s, target node t and k≥2 weight value w _k (e)∈R ⁺ , and constraint vector c=(c ₁ , c ₂ , ..., c _k ), the path p from s to t is called multi-constrained path, if w _l (p)≤c _l , for 1≤l≤k, it is abbreviated as w(p)≤c. □

Both w(e) and c here are k-dimensional vectors. For a given QoS request and its constraint c, the main task of QoSR is to find a path p that meets the requirements in the current network state, so that w(p)≤c.

1. Linear energy function

Dijkstra gave an algorithm for calculating the shortest path tree SPT (Shortest Path Tree) under a single metric, and has a low algorithm complexity. However, the QoSR (QoS Routing) problem involving multiple restricted quality of service involves considering multiple metrics at the same time, so the problem becomes NP-complete (that is, polynomial time unsolvable) complexity and the original algorithm cannot be used. One possible solution is to convert multiple metrics into a single metric.

Definition 2: Linear energy function g _a

Let the linear function $g_a\left(e\right)={\mathrm{\Σ}}_{l=1}^k{a}_l{w}_l$ is the energy function of link e, and represents the cost value of e. where a _l ∈ [0, 1] is a coefficient that has nothing to do with e (l = 1, 2, ..., k), and ${\mathrm{\Σ}}_{l=1}^k{a}_l=1$ , and the vector a=(a ₁ , a ₂ ,..., a _k ) satisfying this condition is called the energy coefficient. □

Based on such a linear energy function, we transform the original multiple constrained path problem into a minimum energy path problem. Each coefficient of the energy function indicates the relative importance of the metric it corresponds to compared to other metrics in computing the "best path".

Theorem 1: Using Dijkstra algorithm with the goal of minimizing g _a (e), a minimum energy tree T(g _a ) with node s as the root can be established, satisfying the path from s to any node t along T(g _a ) p _T has g _a (p _T )=min _{p(s, t)∈G} g _a (p(s, t)).

Proof: Since g _a (e) is a linear function, it satisfies $g_a({\mathrm{<figure-callout\; id="1"\; label="e"\; filenames="C0215992900082.png"\; state="\{\{state\}\}">e</figure-callout>}}_1+e_2)={\mathrm{\&Sigma;}}_{l=1}^k{a}_1{w}_1({\mathrm{<figure-callout\; id="1"\; label="e"\; filenames="C0215992900082.png"\; state="\{\{state\}\}">e</figure-callout>}}_1+e_2)$ $={\mathrm{\&Sigma;}}_{l=1}^k{a}_l{w}_l\left(e_1\right)+{\mathrm{\&Sigma;}}_{l=1}^k{a}_l{w}_l\left(e_2\right)=g_a\left(e_1\right)+g_a\left(e_2\right)$ . Therefore, we can first calculate the energy value g _a (e) of each link, then use the single weight g _a (e) as the key to replace the link cost in the original Dijkstra algorithm, and then use the original algorithm to establish SPT. Since the original algorithm can guarantee that the path from s to any node along the SPT has the minimum cost, the algorithm with g _a (e) as the key guarantees that p _T is the path with the minimum energy from s to t, namely

g _a (p _T )=min _p(s,t)∈G g _a (p(s,t)). □

Taking the energy coefficient a satisfying Definition 2 as an independent variable, we denote the minimum energy tree T(g _a ) as T _a , and denote the path p _T from s to t along T(g _a ) as p _a .

In the QoSR routing performance evaluation, we noticed that even for the same network and QoS request source-destination pair set {(s, t)}, as long as the generation of its constraints follows different distributions or different ranges, the performance of the algorithm It will also be very different, which is the main reason why the data given by the algorithm evaluation of different literatures cannot be compared. However, because the Internet lacks a typical structure and lacks sufficient understanding of the constraints of future QoS requests, it is difficult to give a reasonable model and distribution. In practice, many QoS services have different degrees of concern for various metrics on the path. For example, in order to improve the performance of file transfer, it is generally considered that the loss rate is several times more important than the delay. Based on this idea, on the basis of normalized link metrics, we design a weight ratio simulation method to generate its constraints for the QoS request of a given source-destination pair (s, t). The flow chart of this method is shown in Figure 1 shows.

When generating QoS constraints for each source-destination pair (s, t), firstly take a random number b _l ～uniform[0, 1] (that is, a uniform distribution in the interval [0, 1]), and then make $a_l=b_l/{\mathrm{\&Sigma;}}_{l=1}^k{b}_l$ , where a _l is the concern coefficient, indicating the degree of concern of the QoS service to w _l . Thus using the linear energy function described above $g\left(e\right)={\mathrm{\&Sigma;}}_{l=1}^k\left(a_l{w}_l\left(e\right)\right)$ , calculate the energy value of each link. Then use the Dijkstra algorithm to calculate the path p(s, t) with the minimum energy value from s to t (Theorem 1), and finally let the metric w(p(s, t)) corresponding to the path be the corresponding QoS request The constraint condition of (s, t), that is, c(s, t)=w(p(s, t)). Since the QoS request constructed in this way must have a feasible path, the "routing success rate" can be extended to the evaluation of the absolute performance of the algorithm.

For example, in the network shown in Figure 2.a, the source-destination pair (s, t) is randomly selected, and constraints are generated for it. Taking random numbers b ₀ =0, b ₁ =1, the concerned coefficients a ₀ =0, a ₁ =1, so the linear energy function g(e)=w ₁ (e). When using Dijkstra's algorithm, the goal of optimization is to minimize g(e)=w ₁ (e). For example, when calculating the connection status of node c, it is found that the path g(sac)=7 and g(sbc)=10, so the path p(s, t) with the minimum energy value from s to t is calculated as (sacdt) , the energy value is 9, as shown in Figure 2.b. The metric value of this path is (16, 9), so the simulation generates a QoS service with constraint condition (16, 9) from s to t. Clearly, the path (sacdt) satisfies this constraint.

Furthermore, different care coefficients may result in different constraints. For example, if random numbers b ₀ =1 and b ₁ =0 are taken, then the coefficients of interest are a ₀ =1 and a ₁ =0, so the linear energy function g(e)=w ₀ (e). Using the Dijkstra algorithm to calculate the path p(s, t) with the minimum energy value from s to t is (sbcdt), and the energy value is 12, as shown in Figure 2.c. The metric value of the path is (12, 12), so it is equivalent to generating a QoS service with the constraint condition (12, 12) from s to t, and the service has at least one feasible path, ie (sbcdt).

At present, we have applied this routing performance evaluation method to practice, using Pentium III 933MHz CPU and 256MB memory, the experimental results are shown in Figure 3, where the abscissa indicates the number of network measurements, and the ordinate indicates the routing success rate , the number of network nodes are 50, 100, 200 and 500 respectively. The graphical results show that using different algorithms or algorithm configurations, under this performance evaluation method, the algorithm performance can be more clearly reflected. Because the network based on the quality of service is the inevitable direction of the development of the Internet, and the routers in the network need to use the QoSR algorithm in order to provide QoS support, so the performance evaluation method of the QoSR algorithm will also be widely used in practice.

It can be seen that the present invention has achieved the intended purpose.

Claims (1)

1. based on the service quality routing performance evaluation method of lineament, it is characterized in that it contains successively and has the following steps:

(1) use a computer the input every link have k severe value (w ₁(e), w ₂(e) ..., w _k(e)) the Internet topological diagram G;

(2) produce source node s, the destination node t of quality of service request at random, and guarantee (s, t) minimum hop count between is not less than 3;

(3) to all l=1,2 ..., k is at the equally distributed random number b of [0,1] interval generation _l～uniform (0,1), order then

$a_l=b_l/{\mathrm{\&Sigma;}}_{l=1}^k{b}_l;$

(4) energy value of every link of calculating $g\left(e\right)={\mathrm{\&Sigma;}}_{l=1}^k\left(a_l{w}_l\left(e\right)\right);$

(5), be that tree root calculating is the shortest path tree of evaluation criterion with energy value g (e) with s according to above-mentioned energy value;

(6) to arrive the path of t along this shortest path tree from s, calculate each metric in this path.

Images