法律状态公告日
法律状态信息
法律状态
2012-06-13
未缴年费专利权终止 IPC(主分类):H04L12/26 授权公告日:20081126 终止日期:20110405 申请日:20040405
专利权的终止
2008-11-26
授权
授权
2005-03-09
实质审查的生效
实质审查的生效
2005-01-12
公开
公开
技术领域
本发明涉及一种基于模糊数学质量评估模型的网络瓶颈链路评判检测方法,确切地说,涉及一种根据网络测量获得的多项性能因素对网络链路的性能恶化程度进行综合评定,并据此检测确定网络中的瓶颈链路的方法,以便为网络扩容和维护提供重要依据,属于网络测量及网络性能评估技术领域。
背景技术
网络中的瓶颈链路是指网络中严重影响业务质量的链路。比如对于IP电话业务而言,具有较大的时延抖动、较大时延、较高丢包率、较小带宽的链路常常是严重影响IP电话质量的链路。
瓶颈链路严重影响网络的整体性能。对于网络的监测和管理人员来说,只有找到网络中的瓶颈所在,才能采取相应的措施(比如扩容),才能有效地优化网络的运行状况,改进业务的质量。因此,瓶颈链路检测对于网络运行维护和扩容意义重大。瓶颈链路可能是一段物理链路,也可能是一段逻辑链路(一段或几段连续的不分叉的物理链路)。
链路性能的主要指标包括链路丢包率、排队时延、链路带宽(链路带宽、可用带宽)、时延抖动等。所以,首先要通过一定的方法获知网络中每个链路的各项性能,之后,才能够根据每个链路的各项性能因素的指标来判定哪些链路是网络的瓶颈。
目前,获取链路性能的方法主要有两种:第一种是基于路由器获得链路性能,如果具有网络管理权限(比如运营商),能够得到路由器内部信息,就可以直接从路由器获得每个链路的性能,即包括丢包率、平均排队时延等网管信息。第二种是基于端到端的网络性能测量,如果不是网络管理人员,通常不能从路由器中直接获得网络中各个链路的性能信息。只能在网络的边缘进行端到端的性能测量,再根据测量结果应用某种算法来推测网络内部各个链路的信息。图1中的测量主机1~6就是在网络边缘设置的一些测量结点,再在各个测量结点之间发送一定数量的探测数据包获得端到端的各种性能测量数据,如丢包率、时延、带宽等,然后根据端到端的路径性能和链路性能的关系,利用一定的推测算法,可以推测得到图1所示网络中的每个链路1~9的性能(如丢包率、时延分布、端到端路径上的可用带宽等)。获得这些链路性能之后,再按照一定的评估模型(即设定时延、丢包等各个因素对于性能恶化程度评判的影响),评判网络中各个链路的性能恶化程度,最后根据评判结果确定网络中的瓶颈链路。
当前,对于网络瓶颈链路的评判检测大多是依据链路的某种单一性能因素。实际上,链路性能有多种参数,不同应用对于各种性能因素的要求是不同的,比如IP电话对于时延抖动和时延非常敏感,而视频业务对于带宽的要求高,因此应根据实际应用的需求,根据链路的多种性能因素对网络的链路性能恶化程度给予综合评价检测才是最合理的。然而,至今还没有一种方法是如此处理的。
下面简要说明现有的两种瓶颈链路的检测方法:
(1)基于时延分布的瓶颈链路检测方法:由于网络性能恶化常常意味着在瓶颈链路(或区域)出现较大时延,因此文章《Unicast Inference Of Network LinkDelay Distributions From Edge Measurements》(Proc.IEEE Int.Conf.Acoust.,Speech,and Signal Processing)提出了将端到端的时延推测结果——链路时延分布用于检测瓶颈链路。这种基于链路时延分布判定瓶颈链路的方法中,将“瓶颈”定义为“链路时延超过某一门限的概率大于某指定值的事件”。
例如图2中,设定各个链路带宽为1Mbps,传播时延50ms,链路3的流量负荷被设置为高于其他链路。求得各链路时延分布后,定义瓶颈链路的判别标准为“链路时延超过0.005s的概率最少为0.5”,即利用公式P(Xj≥0.005s)≥0.5,分别将各个链路的时延代入该公式进行计算(公式中P表示概率,Xj代表链路j的时延,图2的例子中j=1,..,4)。下表给出了根据上述公式进行瓶颈链路检测的计算结果,则链路3被检测为瓶颈链路:
这种方法的前提是“网络性能恶化常常意味着在瓶颈链路(或区域)出现较大时延”。但是,这个结论并不一定成立,即未必大时延的链路就是网络的瓶颈链路。实际上,它忽略了其它性能对性能恶化评判的影响,虽然其余链路的时延都比链路3小,但是其中有的链路的其它性能因素的指标可能比链路3还要差,比如丢包率远远超过链路3。如果综合考虑这些性能因素,链路3并非性能最差的链路,这样就造成的瓶颈链路的误判。因此,只根据链路时延一种性能来判定瓶颈链路是片面的、不准确的。
(2)基于带宽的瓶颈链路检测:由于网络中带宽小的链路常常造成网络的瓶颈,文章《Using pathchar to estimate Internet link characteristics》(ACMSIGCOMM′99)和《A tool for Measuring Bottleneck Link Bandwidth》(USITS’01)都提出了由端结点通过发送测量数据包对路径上的各段链路带宽进行推测的方法:先得到各段链路的带宽,再找到该路径上带宽比较小的链路,并认为其是网络的瓶颈。同样地,带宽小的链路也不一定是网络的瓶颈链路。因为带宽最小的链路上的网络流量不一定大,其可用带宽(即未被背景流量占用的剩余带宽)不一定小;而带宽较大的链路也可能其可用带宽比较小,具有较大的丢包率和时延,性能恶化比较严重。因此,单纯依据链路带宽一个性能来检测网络中的瓶颈链路也不合理。
总之,现有瓶颈链路检测技术的主要缺陷是没有综合考虑实际业务的性能需求,而是片面地凭借链路的某一种性能因素进行评判,常常导致瓶颈链路的误判。实际上,“瓶颈链路”本身不是一个确定的概念,而是一个与许多性能因素(比如丢包率、排队时延、时延抖动、可用带宽等)有关的模糊概念;而且,在不同应用场合,瓶颈链路的含义也各不相同,即在不同的应用场合中瓶颈链路的判定标准也不同。例如,对于IP电话业务比较关心链路的排队时延和时延抖动,此时有较大时延和时延抖动的链路就是网络瓶颈。而文件传输协议(FTP,File Transfer Protocol)应用比较关心链路的带宽,这时带宽小的链路可能被认为是瓶颈链路。因此,需要综合考虑实际业务的性能需求,通过多种性能因素对网络链路性能恶化程度进行综合评定,并最终确定瓶颈链路。
发明内容
本发明的目的是提供一种基于模糊数学质量评估模型的网络瓶颈链路评判检测方法,该方法综合考虑了“瓶颈链路”在不同应用场合下的不确定性,以及它与多种性能因素有关的模糊性,根据不同应用场合下的多个不同性能因素进行链路评判与检测,使检测所得的瓶颈链路更切合网络和应用的实际情况。
本发明的目的是这样实现的:一种基于模糊数学质量评估模型的网络瓶颈链路评判检测方法,其特征在于:包括下述步骤:
(1)根据网络链路的性能因素和业务评价的需求,建立链路性能恶化程度的模糊数学评估模型;
(2)依据链路性能恶化程度的模糊数学评估模型,综合考虑网络的每个链路的各个性能因素,确定其性能恶化等级;
(3)确定性能严重恶化的等级,选出性能恶化严重的链路作为网络中的瓶颈链路,完成网络瓶颈链路的检测。
所述步骤(1)包括下述初始化操作:至少建立三个集合,确定该三个集合中分别包含的元素,并设定性能恶化程度的量化标准及其隶属函数,作为性能恶化程度的模糊数学评估模型。
所述三个集合分别是:
待评价的链路集合X={x1,x2,x3...},其中x为待评价的各个链路;
影响链路性能恶化程度评价的各个性能因素的集合U={u1,u2,...,un},其中u为影响性能恶化程度评价的各个不同性能因素,n为该性能因素集合中的元素数目;
链路的性能恶化等级集合V={v1,v2,...,vm},其中vi为第i个性能恶化等级,i=1,2,...,m,m为性能恶化等级集合的元素数目。
所述步骤(1)建立链路性能恶化程度的模糊数学评估模型,进一步包括下列操作:
(11)先为反映链路性能恶化程度的各个性能因素分别建立各自的量化标准,以表示其对链路性能恶化程度的影响;然后将各个性能因素的量化标准用一个n行m列的量化标准矩阵aij表示,其中i=1,2,...,n,n为影响性能恶化程度评价的性能因素集合中的元素数目;j=1,2,...,m,m为性能恶化等级集合中的元素数目;
(12)根据每个性能因素的量化标准确立其隶属函数,以便综合考虑各种因素对性能恶化程度的影响,建立性能恶化程度的模糊数学评估模型。
所述量化标准矩阵aij中的元素采用区间量化方式表达时,该量化标准中各个性能因素指标数值都处于各个性能恶化等级的两个边界数值范围之内,即不同性能恶化等级的链路中的各个性能因素的指标数值是用区间范围表示。
所述量化标准矩阵aij中的元素采用一般量化方式表达时,该量化标准中各个性能因素指标数值都处于各个性能恶化等级的一个边界数值范围内,即不同性能恶化等级的链路中的各个性能因素的指标数值是用大于等于或小于等于一个设定数值表示。
所述隶属函数在评判过程中用于计算各个性能因素对于各个性能恶化等级的隶属程度的模糊关系,它是根据量化标准中的各个性能因素的指标处于各个不同性能恶化等级而构造的;链路x的隶属函数的计算公式为:μij(x)(i=1,...,n;j=1,...,m),其中,μij(x)是从第i个性能因素角度看,链路x属于性能恶化等级j的概率,n为影响性能恶化程度评价的性能因素集合的元素数目,m为性能恶化等级集合中的元素数目。
当采用区间量化方式时,所述隶属函数有下述两种表达方式:
如果第i个性能因素指标的量化区间为[ai0,ai1),[ai1,ai2),...,[aim-1,aim],且ai0<ai1<...<aim,i∈{1,2,...,n},所述隶属函数μij(x)如下述各式所示,其中i=1,2,...,n,n为影响性能恶化程度评价的性能因素集合中的元素数目;j=1,2,...,m,m为性能恶化等级集合中的元素数目;
如果第i个性能因素指标的量化区间为[ai0,ai1),[ai1,ai2),...,[aim-1,aim],且ai0>ai1>...>aim,i∈{1,2,...,n},所述隶属函数μij(x)如下述各式所示,其中i=1,2,...,n,n为影响性能恶化程度评价的性能因素集合中的元素数目;j=1,2,...,m,m为性能恶化等级集合中的元素数目;
所述步骤(2)进一步包括下列操作步骤:
(21)确定待评价的每个链路的各个性能因素的测量值;
(22)根据性能恶化评估模型中的隶属函数公式,确定每个链路对于每一个性能因素属于各个性能恶化等级的隶属程度,然后构造每个链路的各个性能因素属于各个性能恶化等级的模糊关系矩阵;
(23)确定各个性能因素在性能恶化评判过程中的重要程度——权重;
(24)根据每个性能因素的权重综合考虑各个性能因素的影响,求得每个链路对于各个性能恶化等级的综合隶属程度及其最终所属的性能恶化等级。
本发明是一种基于模糊数学质量评估模型的网络瓶颈链路评判检测方法,其特点和效果简述如下:
首先,本发明不同于现有的网络瓶颈链路检测方法,它不是只根据某一个性能因素(例如带宽或时延等)就判定某一链路是否属于瓶颈链路或评价性能恶化的等级,而是综合考虑链路的各种性能参数对于判定链路性能恶化程度的影响。也就是本发明根据链路的实际情况,在链路的性能恶化程度评估模型中建立一个包含多个不同性能因素的集合U,并引入模糊数学的质量评估模型有效地综合考虑各种性能因素的影响。
此外,考虑到不同的应用场合,对于瓶颈链路的评价标准会有所不同,本发明提出一种具有较强适应性的网络瓶颈链路评价方法:在不同应用场景下,用户可以根据实际情况提出特定的评价标准。性能恶化程度评估模型中影响评价的性能因素集合U、性能恶化等级集合V、量化标准、隶属函数和权重分配都可以根据应用场合的不同而改变,使得网络瓶颈链路的评判和检测结果能够真正反映和符合当前应用场景下的“瓶颈链路”。
附图说明
图1(A)、(B)分别是基于端到端的因特网路径性能测量示意图和网络内部各条链路性能推测示意图。
图2是现有技术中根据链路时延进行瓶颈链路检测的举例拓扑示意图。
图3是本发明基于模糊数学质量评估模型的网络瓶颈链路评判检测方法的总流程图。
图4是本发明方法中依据链路性能恶化程度的模糊数学评估模型,综合考虑网络的每个链路的各个性能因素,确定其性能恶化等级的流程图。
图5是应用本发明方法评判和检测一个树形拓扑网络的实施例图。
图6是采用本发明方法对图5的网络进行评判和检测,并标志了其中瓶颈链路的树形拓扑网络的实施例图。
具体实施方式
众所周知,对于一个给定网络找出其瓶颈,即性能严重恶化的区域或者链路,对于网络的管理和规划相当必要。例如在网络扩容时,就能够优先考虑针对这些严重性能恶化的链路。遗憾的是,现有的网络瓶颈链路评价方法仅仅片面地只是考虑链路的单一性能来进行评判和检测,因此不能获得很好的检测结果。实际上,“瓶颈”或“性能恶化”,往往不是局限于链路的一种性能,而是链路的多种性能的综合体现;而且,所谓“性能恶化”不是一个确定的概念,在各个不同应用场合下都用同一标准来评判瓶颈链路是不科学的。因此,本发明提出一种基于模糊数学质量评估模型的网络瓶颈链路评判检测方法,将链路的多种性能因素都作为瓶颈链路的判定标准,并考虑到在不同应用场合下,链路的不同性能对于传输所产生的影响和重要性也有所不同,使瓶颈链路的评判更加合理。
本发明引入模糊数学理论中的质量评估模型,综合分析各个性能因素对瓶颈链路评价的影响。也就是利用质量评估模型,综合考虑端到端网络测量或者从路由器得到的多种链路性能(如丢包率、时延、时延抖动等),并根据用户在当前应用场景下的瓶颈链路评价标准,进行瓶颈链路的评判与检测。
本发明的网络瓶颈链路的评判和检测方法,主要是评判链路的性能恶化程度和在此基础上检测网络中的瓶颈链路。其主要过程是:先评判网络中的各个链路的性能恶化程度,进而根据各个链路的性能恶化程度,选出其中性能恶化严重的链路作为网络中的瓶颈链路,从而完成网络中瓶颈链路的检测。
其中,评判网络中的各个链路的性能恶化程度主要分为两个步骤:第一,建立链路的性能恶化程度评估模型;第二,按照评估模型,对于网络中的链路进行性能恶化程度的综合评价,再根据评价结果,确定其性能恶化等级。
因此,本发明基于模糊数学质量评估模型的网络瓶颈链路的评判检测方法主要包括三个步骤(参见图3):
(1)根据网络链路的性能因素和业务评价的需求,建立链路性能恶化程度的模糊数学评估模型;
(2)依据链路性能恶化程度的模糊数学评估模型,综合考虑网络的每个链路的各个性能因素,确定其性能恶化等级;
(3)确定性能严重恶化的等级,选出性能恶化严重的链路作为网络中的瓶颈链路,完成网络瓶颈链路的检测。
下面对上述瓶颈链路的评判检测过程的三个步骤分别进行详细描述。
在步骤(1)中,建立链路的性能恶化程度评估模型时,需要考虑的因素有:
评价对象是什么?即确定待评价的链路集合;评价因素有哪些?各个因素在评价中的重要程度如何?即依据哪些性能因素来评价链路性能恶化程度,其中哪些因素相对更重要些,哪些因素的影响相对次要些;评价结果如何表示?评价的具体方法?即评价结果是用若干个等级分别表示链路的性能恶化的不同程度,以及确定评价的具体计算方法。
将上述几方面内容具体化,就可以定义本发明瓶颈链路评判检测方法。
首先,链路的性能恶化程度评估模型至少包括以下三个集合:
待评价的链路集合X={x1,x2,x3...},其中x为待评价的各个链路;
影响链路性能恶化程度评价的性能因素集合U={u1,u2,...,un},其中u为影响性能恶化程度评价的各个不同性能因素,n为该性能因素集合中的元素数目。例如,对于IP电话业务来说,具有较大的时延抖动、时延、较大丢包率和带宽较窄的链路是相对性能恶化的链路,可以定义评判性能因素集合为U={时延抖动,时延,丢包率,链路带宽},其中n=4。此外,还要确定各个性能因素对于性能恶化评判的重要程度。比如对于IP电话业务来说,时延抖动和时延对于业务质量的影响较大,而丢包率对于业务质量的影响较小,这样就可以给时延抖动和时延的权重较高,使得它们对评判结果的影响更大一些,而给予丢包率的权重小一些,使其对评判结果的影响小一些。
性能恶化等级集合V={v1,v2,...,vm}为各种性能恶化等级的集合,其中vi为第i个性能恶化等级(i=1,2,...,m),m为性能恶化等级集合的元素数目。例如V={轻度性能恶化,中度性能恶化,重度性能恶化},定义了三个性能恶化等级。
在步骤(2)中具体描述了性能恶化程度评价过程,就是如何根据链路的性能恶化程度评估模型、各链路的性能测量指标值及其权重确定在链路集合中哪些链路是瓶颈链路,这里涉及到量化标准和隶属函数。因为,要综合考虑决定链路性能恶化程度的性能因素集合中多种不同性能对于性能恶化程度的评价的影响,需要先通过量化标准定义每种性能因素对于链路性能恶化程度的影响,然后,再采用一定方法将这些不同性能因素对性能恶化程度的影响结合起来。下面分别详细说明之:
本发明定义的量化标准就是根据每个链路x的性能因素的测量指标值yi在什么区间范围,确定该链路x属于什么性能恶化等级。比如性能参数位于ai0~ai1,ai1~ai2,...,aim-1~aim区间内,则定义该链路x分别属于性能恶化等级1,2,...,m。由于存在多个(例如n个)性能因素,因此n个性能因素的量化标准可以采用量化标准矩阵来表示。具体地说,量化标准矩阵的第i行(其中i=1,2,...n)表示:如果第i个性能因素的测量指标值yi在ai0~ai1范围内,则就该性能因素而言,链路属于性能恶化等级v1;如果第i个因素的测量指标值yi在ai1~ai2范围内,则就该性能因素而言,链路属于性能恶化等级v2,以此类推。
确定了量化标准后,就可以根据量化标准构造各个性能因素相对于各个性能恶化等级的隶属函数μij(x)(i=1,...,n;j=1,...,m)(μij(x)是从第i个性能因素角度看,链路x属于性能恶化等级j的概率,n为影响性能恶化程度评价的性能因素集合的元素数目,m为性能恶化等级集合中的元素数目),以便在评判过程中计算模糊关系矩阵时应用该隶属函数。隶属函数的确定,实际上反映了性能恶化程度评判的模糊性——链路上的各个性能因素的测量值对于各个性能恶化等级的隶属程度(即属于某个性能恶化等级的概率)并不是绝对的,而是相对的。本发明就是利用各种性能因素的测量值对于各性能恶化等级的隶属程度的模糊性或不确定性,结合各个性能因素的权重以及后面描述的评价过程,把各个性能因素对于性能恶化等级评价的影响有效地结合起来。
隶属函数:μij(x)(i=1,...,n;j=1,...,m)是按下述方式建立的:
①如果量化标准矩阵的第i行为ai0<ai1<...<aim的情况(其中i∈{1,2,...,n}),则定义隶属函数μij(x)为:
公式组(1)
②如果量化标准矩阵的第i行为ai0>ai1>...>aim的情况(其中i∈{1,2,...,n}),则定义隶属函数μij(x)为:
公式组(2)
以上为通常情况下的隶属函数构造方法,也可以根据实际情况构造其它种类的隶属函数。
参见图4,本发明进行链路性能恶化程度的评价过程就是按照性能恶化程度评估模型对网络中的各个待评价链路进行性能恶化程度的评价,包括下述步骤:
(21)确定待评价链路各个性能因素的测量值:
对于每一个待评价对象链路xk(k=1,2,...,N,其中N为集合X中的元素数目,即待评价的链路总数),根据链路性能测量结果给出一个测定值向量:Yk=(y1,y2,...,yn),其中yi为性能因素ui的测量值(i=1,2,...,n,n为影响性能恶化程度评价的性能因素集合的元素数目)。例如,如果设定性能因素u1为链路丢包率,则y1为测得的链路xk的具体丢包率值。
(22)根据隶属函数公式,分别对每一个性能因素计算链路属于各个性能恶化等级的概率,即隶属度。具体方法是:将待评价链路xk对于每一个因素ui的测量指标yi带入隶属函数公式,求得rij=μij(yi)(i=1,...,n;j=1,...,m),其中,rij的含义是就性能因素ui来说,该链路属于性能恶化等级vj的概率,n为影响性能恶化程度评价的性能因素集合中的元素个数,m为性能恶化等级集合的元素个数。然后根据隶属程度rij构造该链路xk的各个性能因素映射到各性能恶化等级的模糊关系矩阵Rk=(rij)m×n,其中rij是矩阵Rk第i行第j列的元素。
(23)确定各个性能因素在性能恶化评判过程中的重要程度——权重:以向量A表示各性能因素在性能恶化评判中的重要程度,A=(a1,a2,...,an),
(24)根据每个性能因素的权重综合考虑各个性能因素的影响,求得每个链路对于各个性能恶化等级的综合隶属程度(即概率),并确定该链路最终所属的性能恶化等级。
根据公式
本发明的步骤(3)是:确定性能严重恶化等级,选出性能恶化严重的链路作为网络的瓶颈链路。
按照上述步骤(1)和(2)对待评价链路集合X中的所有链路逐一进行性能恶化等级的评价之后,再根据链路的性能恶化程度评估模型定义的指标,用户可以定义出其认为属于性能严重恶化等级集合SV,该性能严重恶化等级集合是原有性能恶化等级集合V的一部分(SV∈V),即从性能恶化等级集合中确定哪些性能恶化等级是性能严重恶化等级。然后,就可以选出属于性能严重恶化等级集合SV的链路,即严重性能恶化的链路,它们被认为是网络中的瓶颈链路,这样就完成了瓶颈链路的检测。
参见图5和图6,下面结合图5和图6的一个实施例进一步说明本发明如何定义和建立链路的性能恶化程度评估模型,以及进行瓶颈链路评判和检测的过程:
待评价链路集合X={x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11}(其中链路xk是图中结点由k的父结点到结点k的链路(k=1,...,11),例如链路x1指结点0到结点1的链路);
影响链路性能恶化程度评价的性能因素集合U={丢包率,时延均值}(其中性能因素数目n=2);
性能恶化等级集合V={v1,v2,v3,v4,v5},(其中性能恶化等级数目m=5)vi为性能恶化等级(i=1,...,5);
量化标准(采用区间量化方式):
隶属函数的确定采用公式组(1)所示的隶属函数形式;
性能恶化程度评价过程中(24)操作为
设定各因素的权重为:A={0.6,0.4},即丢包率占60%,时延占40%;
各链路的测量值向量为: Y1=(0.005,0.2);
Y2=(0.01,90); Y3=(0.15,150);
Y4=(0.001,7); Y5=(0.0006,1.8);
Y6=(0.0001,0.05); Y7=(0.009,18);
Y8=(0.012,209); Y9=(0.0045,20);
Y10=(0.008,45); Y11=(0.0024,75);
将上述链路性能测量值带入瓶颈链路评判检测方法,性能恶化程度判定结果为:
注:表中加下划线的项为向量Bk中的最大项(k=1,...,11)。
在将待检测链路集合X中的所有链路都进行了性能恶化等级的评判之后,如果定义属于性能恶化等级4和5的链路为性能恶化比较严重的链路,也就是网络的瓶颈,就可以根据上表中经链路性能恶化评判算法所得的各个链路所属的性能恶化等级,选出链路x2,x3,x8为瓶颈链路(在上表中用*标出)。这样就完成了上述网络中瓶颈链路的检测。相应地,可以在网络逻辑拓扑图中以粗虚线标记出这些严重性能恶化的瓶颈链路(参见图6),作为直观的网络瓶颈链路的评判检测的结果显示。
机译: 基于离群模型的基于视觉描述符的视频质量评估
机译: 基于链路质量的接收机侧评估的动态分集的设备和方法
机译: 基于链路质量的接收机侧评估的动态分集的设备和方法