CN103281256A - Network tomography-based end-to-end path packet loss rate detection method - Google Patents

Abstract

Translated fromChinese

本发明提供基于网络层析的端到端路径丢包率探测方法，所述方法包括S1：对网络中路径丢包率和链路丢包率的关系进行建模，得到Gx=b；S2：对路由矩阵G进行筛选，得到初始路径集合G_inde，在筛选过程中探测到G_inde的路径丢包率；S3：判断G_inde是否为极大线性无关路径集合，若不是，则继续执行步骤S4；若是，则设G_inde为集合G₁，并跳转步骤S5；S4：利用路径选择算法对G_inde继续进行筛选；S5：获取所述极集合G₁中的路径丢包率，并计算剩余路径丢包率。本发明提出一种基于网络层析的端到端路径丢包率探测方法，通过获得网络拓扑将路径丢包率与链路丢包率进行建模，且支持UDP的网络环境，对网络造成的负载较小，且得到的探测路径数量明显降低。

The present invention provides an end-to-end path packet loss rate detection method based on network tomography. The method includes S1: modeling the relationship between the path packet loss rate and link packet loss rate in the network to obtain Gx=b; S2: Screen the routing matrix G to obtain the initial path set G_inde , and detect the path packet loss rate of G_inde during the screening process; S3: judge whether G_inde is a maximum linearly independent path set, if not, proceed to step S4 ; If yes, set G_inde as set G₁ , and jump to step S5; S4: Use the path selection algorithm to continue screening G_inde ; S5: Obtain the packet loss rate of the path in the extreme set G₁ , and calculate the remaining Path packet loss rate. The present invention proposes an end-to-end path packet loss rate detection method based on network tomography. By obtaining the network topology, the path packet loss rate and link packet loss rate are modeled, and the UDP network environment is supported, causing damage to the network. The load is small and the resulting number of probing paths is significantly reduced.

Description

The end-to-end path packet loss detection method of chromatography Network Based

Technical field

The present invention relates to technical field of the computer network, particularly a kind of end-to-end path packet loss detection method of chromatography Network Based.

Background technology

Along with Internet fast development, people improve constantly the degree of dependence of network service, and the performance of network is also had higher requirement.Network performance measurement is basis and the checking means of carrying out network traffics, topology, behavior modeling analysis.How to use lower cost, the operation conditions that measures whole network exactly becomes the focus of more and more researcher's researchs.

Network tomography is to survey by the probe to end-to-end transmission, obtains structure and the performance information of network internal.The network tomography technology can be under the situation that does not have the internal network node cooperation, by initiatively sending probe and inferring large scale network link level qos parameter and topological structure according to statistical method.The packet loss Detection Techniques are the awareness network behaviors, carry out network control, eliminate network bottleneck, improve basis and the important step of network performance, so have very important meaning as one of them branch.

Transmit in the process of information at IP network, congested being difficult to avoided, and the congested network that may cause can't normally provide service, thereby causes economic loss and potential safety hazard.Network end-to-end path packet loss and network link packet loss can reflect operation conditions and the Congestion Level SPCC of network, are the important indicators of network performance, therefore how to obtain the focus that path and link packet drop rate become numerous researcher's researchs rapidly and accurately.The detection problem of primary study end-to-end path packet loss herein.

The path monitoring method of network can be divided into initiatively measurement and passive measurement according to the mode of measuring.The passive measurement technology is only obtained the network performance situation by the method that catches the available data bag that tested network transmits, and its performance index that can analyze out can be subjected to the influence of monitoring range.Initiatively measuring is present emerging network measure mode, and it is measured the transmission situation that wraps in the network by the particular data packet, the record that initiatively send and obtains network performance data, have higher flexibility, but this method need take certain Internet resources.In order to save the Internet resources expense, existing network monitoring method based on initiatively measurement has mainly adopted following measure: 1) optimize and dispose watch-dog, to reduce hardware spending; 2) select the to try one's best quantity of few measuring route; 3) reduce overlapping measurement, to reduce link load as far as possible.

Existing network measuring system is divided into two classes: a class is general measuring system, and a class is only to measure the system of time delay.The former can measure a lot of performances of network, but when n terminal, needs O (n²) the measurement complexity.And latter's one side measurement result is accurate inadequately; On the other hand, even this latency measurement system can measure the result, still can not provide the guess value of accurate percent of pass and mortality ratio.

In the network with n terminal, the definition path is the connection of terminal room, and link is the connection between the point-to-point, and the path is exactly a series of link set.Just exist O (n at n terminal room so²) path of number.And the existing technical problem that will solve is: wish path subclass of trying one's best little of monitoring, thereby can infer packet loss and the time delay that all paths of residue.

The method of available technology adopting has: adopt multicast detection or uni-cast probe, in order to solve the limited problem of multicast detection application environment, can adopt uni-cast probe; Perhaps place monitor in initial logic topological tree inside, and collect all observed data of initial logic tree, set up the packet loss sequence of the leaf node of every subtree correspondence then, thereby infer the packet loss that its inner every link; Perhaps use topology and the packet loss of every detective path of unicast packet detection network, and carry out modeling according to the packet loss in the topological sum path of described network, utilize Non-Linear Programming to calculate link packet drop rate according to the model of building.

Yet prior art has the shortcoming that detectivity is low, complexity is high and cost on network communication is big.

Summary of the invention

(1) technical problem of Xie Jueing

The technical problem that the present invention solves is that the more excellent path of few distribution of how selecting to try one's best is surveyed, and obtains the calculated value of network packet loss rate accurately.

(2) technical scheme

The invention provides a kind of end-to-end path packet loss detection method of chromatography Network Based, described method comprises:

S1: the relation to path packet loss and link packet drop rate in the network is carried out modeling, obtains Gx=b, and wherein, G is route matrix, and x is the logarithm of every link percent of pass, and b is the logarithm of every paths percent of pass;

S2: G screens to the route matrix, obtains initial path set G_Inde, in screening process, detect described initial path set G_IndeThe path packet loss;

S3: judge described initial path set G_IndeWhether be very big linear independence set of paths, if not, execution in step S4 then continued; If then establish described initial path set G_IndeBe set G₁, and jump procedure S5;

S4: utilize routing algorithm that initial path is gathered G_IndeProceed screening;

S5: in step S2, survey the described initial path set G that obtains_IndeThe path packet loss in obtain described set G₁In the path packet loss, and calculate the residual paths packet loss; Described residual paths is that described route matrix G filters out described set G₁Remaining path, back.

Preferably, among the step S1 percent of pass be 1 with the difference of packet loss.

Preferably, among the step S2 described route matrix G screened specifically and comprises:

S21: described route matrix G is divided into groups according to the path node j that sets out, and the row of the path of each grouping in described route matrix G number is recorded in S set_jIn;

S22: extract S set_jIn first data m, the path that obtains the capable correspondence of matrix m is vectorial u, judge described vectorial u whether with G_IndeIn SYSTEM OF LINEAR VECTOR irrelevant, if linear independence, jump procedure S23 then is if linear correlation then deposits the number of going m in set T_j

S23: survey the path percent of pass of described vectorial u correspondence, and judge whether the path percent of pass of described vectorial u correspondence is 1, if 1, then with S set_jIn data m from S set_jMiddle deletion, and upgrade described route matrix G, and then upgrade G_IndeIf be not 1, then the path with described vectorial u correspondence joins G_IndeIn.

Preferably, judge the described vectorial u first time and G_IndeIn vector whether during linear independence, establish G_IndeBe null matrix.

Preferably, the described route matrix G of described renewal specifically comprises: be 1 column vector deletion with the value of the capable correspondence of m among the described route matrix G.

Preferably, the G that finally obtains among the determining step S23_IndeOrder whether equal to upgrade the way of escape by the order of matrix G, if unequal, then will gather T_jAssignment is to S set_j, jump procedure S22; If equate, then continue step S3.

Preferably, routing algorithm is specially described in the step S4:

S41: get initial path set G_IndeFirst row be made as v, calculate R₁=orth (G₁^Τ)^Τv^ΤAnd R₂=‖ v ‖²-‖ R₁‖², wherein, T represents transposition, || || expression delivery, G₁Be very big linear independence set of paths;

S42: judge R₂Whether be 0, if be not 0, then v, continue step S43 if satisfying linear independence; If 0, jump procedure S44 then;

S43: v is joined G₁In, and judge whether v is G₁Last column, if, then with G₁Return, otherwise execution in step S44;

S44: initial path is gathered G_IndeThe next line assignment give v, execution in step S41.

Preferably, G among the step S41₁Initial value be null matrix.

Preferably, calculating the residual paths packet loss among the step S5 specifically comprises:

S51: establishing the residual paths matrix is G_Rem, with G_RemWith described very big linear independence set of paths G₁Recombinate, obtain the matrix of recombinating$G_{\mathrm{final}}=\left[\begin{array}{c}{G}_1\\ G_{\mathrm{rem}}\end{array}\right];$

S52: to reorganization matrix G_FinalCarry out elementary rank transformation, then residual paths percent of pass logarithm is reorganization matrix G_FinalCarry out matrix and described very big linear independence set of paths G that elementary rank transformation obtains₁In path percent of pass logarithm long-pending.

Three) beneficial effect

The present invention proposes a kind of end-to-end path packet loss detection method of chromatography Network Based, by obtaining network topology path packet loss and link packet drop rate are carried out modeling, and support the network environment of UDP, less to the load that network causes, and the detective path quantity that obtains obviously reduces.

Description of drawings

Fig. 1 is method flow diagram provided by the invention;

Fig. 2 is network topology structure figure in the embodiment of the invention.

Embodiment

Below in conjunction with the accompanying drawing in the embodiment of the invention, the technical scheme in the embodiment of the invention is clearly and completely described.

Embodiment 1:

The invention provides a kind of end-to-end path packet loss detection method of chromatography Network Based, this method flow diagram as shown in Figure 1, described method comprises:

S1: the relation to path packet loss and link packet drop rate in the network is carried out modeling, obtains Gx=b, and wherein, G is route matrix, and x is the logarithm of every link percent of pass, and b is the logarithm of every paths percent of pass;

By surveying the packet loss of topological and every the detective path that obtains network, set up algebraic equation Gx=b.G is route matrix, a line display one paths among the G, and a link, G are shown in a tabulation_IkBe the element of the capable k row of the i of matrix, value is 0 or 1, works as G_IkRepresented that path i did not comprise link k at=0 o'clock, work as G_Ik=1 expression path i comprises link k.

Among the step S1 percent of pass be 1 with the difference of packet loss.

S2: G screens to the route matrix, obtains initial path set G_Inde, in screening process, detect described initial path set G_IndeThe path packet loss;

Among the step S2 described route matrix G screened specifically and comprises:

S21: described route matrix G is divided into groups according to the path node j that sets out, and the row of the path of each grouping in described route matrix G number is recorded in S set_jIn;

S22: extract S set_jIn data m, the path that obtains the capable correspondence of matrix m is vectorial u, judge described vectorial u whether with G_IndeIn SYSTEM OF LINEAR VECTOR irrelevant, if linear independence, if jump procedure S23 then is linear correlation, then with the capable set T that deposits in of m_j

S23: survey the path percent of pass of described vectorial u correspondence, and judge whether the path percent of pass of described vectorial u correspondence is 1, if 1, then with S set_jIn m capable of S set_jMiddle deletion, and upgrade described route matrix G, and then upgrade G_IndeIf be not 1, then the path with described vectorial u correspondence joins G_IndeIn.

Judge the described vectorial u first time and G_IndeIn vector whether during linear independence, establish G_IndeBe null matrix.Form by a series of 0,1 among the route matrix G, then upgrade described route matrix G and specifically comprise: be 1 column vector deletion with the value of the capable correspondence of m among the described route matrix G.The G that finally obtains among the determining step S23_IndeOrder whether equal to upgrade the way of escape by the order of matrix G, if unequal, then will gather T_jAssignment is to S set_j, jump procedure S22; If equate, then continue step S3.

S3: judge described initial path set G_IndeWhether be very big linear independence set of paths if not, then continue execution in step S4; If then establish described initial path set G_IndeBe set G₁, and jump procedure S5;

S4: utilize routing algorithm that initial path is gathered G_IndeProceed screening;

Routing algorithm is specially following steps described in the step S4:

S41: get initial path set G_IndeFirst row be made as v, calculate R₁=orth (G₁^Τ)^Τv^ΤAnd R₂=‖ v ‖²-‖ R₁‖², wherein, T represents transposition, || || expression delivery, G₁Be very big linear independence set of paths;

S42: judge R₂Whether be 0, if be not 0, then v, continue step S33 if satisfying linear independence; If 0, jump procedure S44 then;

S43: v is joined G₁In, and judge whether v is G₁Last column, if, then with G₁Return, otherwise execution in step S44;

S44: initial path is gathered G_IndeThe next line assignment give v, execution in step S41.

G among the step S41₁Initial value be null matrix.

S5: in step S2, survey the described initial path set G that obtains_IndeThe path packet loss in obtain described set G₁In the path packet loss, and calculate the residual paths packet loss; Described residual paths is that described route matrix G filters out described set G₁Remaining path, back.

Calculating the residual paths packet loss among the step S5 specifically comprises:

S51: establishing the residual paths matrix is G_Rem, with G_RemWith described very big linear independence set of paths G₁Recombinate, obtain the matrix of recombinating$G_{\mathrm{final}}=\left[\begin{array}{c}{G}_1\\ G_{\mathrm{rem}}\end{array}\right];$

S52: to reorganization matrix G_FinalCarry out elementary rank transformation, then the residual paths packet loss is reorganization matrix G_FinalCarry out matrix and described very big linear independence set of paths G that elementary rank transformation obtains₁In the path packet loss long-pending.

Embodiment 2:

Part topological structure with a practical IP network is that example is showed path of the present invention packet loss detection method below.Exist service end to end in this topological structure between any two main frames.e₁-e₆Represent and have a data harvester in the link network in the network, the data message that exists in real-time monitoring and the collection network.This topological structure as shown in Figure 2.

The end-to-end path packet loss detection method implementation step that the present invention proposes a kind of chromatography Network Based is as follows:

101) read network topology and detection information, concrete steps comprise:

Be that end of probe is carried out the traceroute(Internet mutually with 3 main frames in scheming earlier) obtain network topology, it is as follows to obtain route topological:

$G=\left[\begin{array}{cccccc}1& 0& 0& 0& 0& 1\\ 1& 0& 0& 0& 1& 0\\ 0& 0& 1& 1& 0& 0\\ 0& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 0\\ 0& 1& 0& 0& 0& 1\end{array}\right]$

Each line display one paths is respectively A → B, A → C, B → A, B → C, C → A, C → B; A link is shown in each tabulation, respectively the e in the corresponding diagram₁To e₆And their opposite direction (from left to right).

102) route matrix G is handled, survey while screening, obtain initial path set G_Inde:

$G_{\mathrm{inde}}=\left[\begin{array}{ccc}0& 1& 1\\ 0& 1& 0\\ 1& 0& 1\end{array}\right]\stackrel{\‾}{b}=\ln \left[\begin{array}{c}0.9310\\ 0.9800\\ 0.9500\end{array}\right].$

103) judge G_IndeBe very big linear independence set of paths, then G₁=G_Inde, obtain initial path set G_IndeThe logarithm of path percent of pass be

104) according to the packet loss of the very big linear independence set of paths reasoning residual paths that obtains, according to G₁Obtain G_FinalAs follows:

$G_{\mathrm{final}}=\left[\begin{array}{ccc}0& 1& 1\\ 0& 1& 0\\ 1& 0& 1\\ 0& 0& 0\\ 0& 0& 0\\ 1& 0& 0\end{array}\right]$

To G_FinalCarry out elementary rank transformation and obtain its row simplest formula G_sFor:

$G_s=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\\ 0& 0& 0\\ -1& 1& 1\end{array}\right]$

ThenThe value that obtains b is:

$b=\ln \left[\begin{array}{c}0.9310\\ 0.9800\\ 0.9500\\ 1.0000\\ 1.0000\\ 1.0000\end{array}\right]$

The value that obtains the path percent of pass after the rearrangement is 1.0000,1.0000,0.9310,0.9800,0.9500,1.0000, and is identical with actual value.

Because the order of route matrix G is 5, all are not when using our algorithm, and detective path bar number is 5, and use after our algorithm herein, by the route matrix deleted that the detective path bar number that obtains is reduced to 3, has saved communication overhead to a great extent.

Above execution mode only is used for explanation the present invention; and be not limitation of the present invention; the those of ordinary skill in relevant technologies field; under the situation that does not break away from the spirit and scope of the present invention; can also make a variety of changes and modification; therefore all technical schemes that are equal to also belong to category of the present invention, and scope of patent protection of the present invention should be defined by the claims.

Claims (9)

Translated fromChinese

1.基于网络层析的端到端路径丢包率探测方法，其特征在于，所述方法包括：1. the end-to-end path packet loss rate detection method based on network layering, it is characterized in that, described method comprises:S1：对网络中路径丢包率和链路丢包率的关系进行建模，得到Gx=b，其中，G是路由矩阵，x是每条链路通过率的对数，b是每条路径通过率的对数；S1: Model the relationship between the path packet loss rate and the link packet loss rate in the network, and get Gx=b, where G is the routing matrix, x is the logarithm of the pass rate of each link, and b is each path logarithm of pass rate;S2：对路由矩阵G进行筛选，得到初始路径集合G_inde，在筛选过程中探测到所述初始路径集合G_inde的路径丢包率；S2: Screen the routing matrix G to obtain an initial path set G_inde , and detect the path packet loss rate of the initial path set G_inde during the screening process;S3：判断所述初始路径集合G_inde是否为极大线性无关路径集合，若不是，则继续执行步骤S4；若是，则设所述初始路径集合G_inde为集合G₁，并跳转步骤S5；S3: judging whether the initial path set G_inde is a maximum linear independent path set, if not, proceed to step S4; if yes, set the initial path set G_inde as set G₁ , and skip to step S5;S4：利用路径选择算法对初始路径集合G_inde继续进行筛选；S4: Use the path selection algorithm to continue to screen the initial path set G_inde ;S5：在步骤S2中探测得到的所述初始路径集合G_inde的路径丢包率中获取所述集合G₁中的路径丢包率，并计算剩余路径丢包率；所述剩余路径为所述路由矩阵G筛选出所述集合G₁后剩余的路径。S5: Obtain the path packet loss rate in the set_G1 from the path packet loss rate of the initial path set G_inde detected in step S2, and calculate the remaining path packet loss rate; the remaining path is the The routing matrix G screens out the remaining paths after the set G₁ .2.根据权利要求1所述的方法，其特征在于，步骤S1中通过率为1与丢包率的差值。2. The method according to claim 1, characterized in that, in step S1, the pass rate is the difference between 1 and the packet loss rate.3.根据权利要求1所述的方法，其特征在于，步骤S2中对所述路由矩阵G进行筛选具体包括：3. The method according to claim 1, characterized in that, screening the routing matrix G in step S2 specifically comprises:S21：将所述路由矩阵G根据路径出发节点j进行分组，每个分组的路径在所述路由矩阵G中的行号记录在集合S_j中；S21: Group the routing matrix G according to the path starting node j, and record the row number of the path of each group in the routing matrix G in the set S_j ;S22：提取集合S_j中的第一个数据m，得到矩阵第m行对应的路径为向量u，判断所述向量u是否与G_inde中的向量线性无关，若线性无关，则跳转步骤S23，若线性相关，则将行号m存入集合T_j；S22: Extract the first data m in the set S_j , obtain the path corresponding to the mth row of the matrix as a vector u, judge whether the vector u is linearly independent from the vector in G_inde , if not, skip to step S23 , if it is linearly related, then store the row number m into the set T_j ;S23：探测所述向量u对应的路径通过率，并判断所述向量u对应的路径通过率是否为1，若为1，则将集合S_j中的数据m从集合S_j中删除，并更新所述路由矩阵G，进而更新G_inde；若不为1，则将所述向量u对应的路径加入到G_inde中。S23: Detect the pass rate of the path corresponding to the vector u, and judge whether the pass rate of the path corresponding to the vector u is 1, if it is 1, delete the data m in the set S_j from the set S_j , and update The routing matrix G further updates G_inde ; if it is not 1, the path corresponding to the vector u is added to G_inde .4.根据权利要求3所述的方法，其特征在于，判断所述向量u第一次与G_inde中的向量是否线性无关时，设G_inde为零矩阵。4. The method according to claim 3, wherein, when judging whether the vector u is linearly independent with the vector in G_inde for the first time, set G_inde to be a zero matrix.5.根据权利要求3所述的方法，其特征在于，所述更新所述路由矩阵G具体包括：将所述路由矩阵G中第m行对应的值为1的列向量删除。5. The method according to claim 3, wherein the updating the routing matrix G specifically comprises: deleting a column vector with a value of 1 corresponding to the mth row in the routing matrix G.6.根据权利要求1或3任一项所述的方法，其特征在于，判断步骤S23中最终得到的G_inde的秩是否等于更新后路由矩阵G的秩，若不相等，则将集合T_j赋值到集合S_j，跳转步骤S22；若相等，则继续步骤S3。6. according to the method described in any one of claim 1 or 3, it is characterized in that, judge whether the rank of G_inde finally obtained in step S23 is equal to the rank of routing matrix G after updating, if not equal, then set T_j Assign a value to the set S_j , jump to step S22; if they are equal, continue to step S3.7.根据权利要求1所述的方法，其特征在于，步骤S4中所述路径选择算法具体为：7. The method according to claim 1, wherein the path selection algorithm described in step S4 is specifically:S41：取初始路径集合G_inde的第一行设为v，计算R₁=orth(G₁^Τ)^Τv^T和R₂＝‖v‖²-‖R₁‖²，其中，T表示转置，||||表示取模，G₁为极大线性无关路径集合；S41: Set the first row of the initial path set G_inde as v, and calculate R₁ =orth(G₁^Τ )^Τ v^T and R₂ =‖v‖² -‖R₁ ‖² , where T represents transposition , |||| means modulus, and G₁ is a set of maximum linearly independent paths;S42：判断R₂是否为0，若不为0，则v满足线性无关，继续步骤S43；若为0，则跳转步骤S44；S42: Determine whether R₂ is 0, if not 0, then v satisfies linear independence, continue to step S43; if it is 0, then skip to step S44;S43：将v加入到G₁中，并判断v是否为G₁的最后一行，若是，则将G₁返回，否则执行步骤S44；S43: Add v to G₁ , and judge whether v is the last line of G₁ , if so, return G₁ , otherwise execute step S44;S44：将初始路径集合G_inde的下一行赋值给v，执行步骤S41。S44: assign the next row of the initial path set G_inde to v, and execute step S41.8.根据权利要求7所述的方法，其特征在于，步骤S41中G₁的初始值为零矩阵。8. The method according to claim 7, characterized in that the initial value of_G1 in step S41 is a zero matrix.9.根据权利要求1所述的方法，其特征在于，步骤S5中计算剩余路径丢包率具体包括：9. The method according to claim 1, wherein calculating the remaining path packet loss rate in step S5 specifically comprises:S51：设剩余路径矩阵为G_rem，将G_rem与所述极大线性无关路径集合G₁进行重组，得到重组矩阵$G_{\mathrm{final}}=\left[\begin{array}{c}{G}_1\\ G_{\mathrm{rem}}\end{array}\right];$S51: Set the remaining path matrix as G_rem , reorganize G_rem and the set of maximum linearly independent paths G₁ to obtain a reorganization matrix$G_{\mathrm{final}}=\left[\begin{array}{c}{G}_1\\ G_{\mathrm{rem}}\end{array}\right];$S52：对重组矩阵G_final进行初等列变换，则剩余路径通过率对数为重组矩阵G_final进行初等列变换得到的矩阵与所述极大线性无关路径集合G₁中的路径通过率对数之积。S52: Perform elementary column transformation on the reorganization matrix G_final , and the remaining path passing rate logarithm is the matrix obtained by performing elementary column transformation on the reorganization matrix G_final and the path passing rate logarithm in the maximum linearly independent path set_G1 . product.

Images