用于检测网络中状态改变的系统及方法

摘要

本发明涉及用于检测网络中状态改变的系统及方法。用于节点网络中可伸缩状态改变检测的系统及方法包括将节点坐标位置嵌入到虚拟地图环境中。节点的集群用代表节点来代表，以形成节点及集群的层次结构，其中代表节点的状态改变意味着集群的节点中的状态改变。通过有选择地监视代表节点的状态改变，代表节点产生对网络进行可伸缩监视的能力。

权利要求

1.一种用于节点网络中的可伸缩状态改变检测的方法，包括步骤：将节点坐标位置嵌入到分层布置的虚拟地图环境中；

用代表节点代表节点集群，以形成节点及集群的层次结构，其中代表节点的状态改变意味着集群的节点中的状态改变；以及有选择地监视代表节点的状态改变，使得代表节点产生对网络进行可伸缩监视的能力，其中包括步骤：计算代表节点的新虚拟坐标；

将计算的新虚拟坐标与旧虚拟坐标相比较；以及如果代表节点的坐标改变超过阈值，则确定代表节点的状态已改变。

2.根据权利要求1中所述的方法，其中节点及集群的层次结构包括节点组的多层结构。

3.根据权利要求1中所述的方法，其中有选择地监视的步骤包括在多个不同的集群层次上监视代表节点，以提供网络的可伸缩监视。

4.根据权利要求1中所述的方法，进一步包括在虚拟坐标地图中更新虚拟坐标，以确定网络中的节点的状态改变的步骤。

5.根据权利要求4中所述的方法，进一步包括通过细分集群或节点组来调查在哪里已发生改变的步骤。

6.根据权利要求5中所述的方法，进一步包括确定被细分的集群的质心，并且如果集群的状态已改变，则进一步细分该集群的步骤。

7.根据权利要求1中所述的方法，其中有选择地监视的步骤包括确定已改变状态的所识别节点。

8.根据权利要求7中所述的方法，其中确定已改变状态的所识别节点的步骤包括如果连接节点的区段的被监视特性已改变，则列出被影响的节点。

9.根据权利要求8中所述的方法，进一步包括将被影响的节点与已改变状态的节点相比较以确定对状态改变负责的候选对象的步骤。

10.根据权利要求1中所述的方法，其中被监视的状态改变包括延迟改变、距离改变、安全、分组损失率及/或活动性改变。

11.根据权利要求1中所述的方法，其中嵌入坐标位置的步骤包括计算虚拟地图环境中的距离。

12.一种用于节点网络中可伸缩状态改变检测的方法，包括步骤：确定虚拟地图环境中的参考位置；

基于虚拟地图环境中的参考位置确定节点坐标位置；

基于虚拟地图环境中的位置将节点组成集群；

用代表节点代表节点集群，其中代表节点的状态改变意味着集群的节点中的状态改变；以及监视该代表节点的状态改变，其中包括步骤：

计算代表节点的新虚拟坐标；

将计算的新虚拟坐标与旧虚拟坐标相比较；以及如果代表节点的坐标改变超过阈值，则确定代表节点的状态已改变。

13.根据权利要求12中所述的方法，其中代表节点集群的步骤包括创建节点集群及子集群的层次结构。

14.根据权利要求13中所述的方法，其中监视的步骤包括在多个不同集群层次上监视代表节点以提供网络的可伸缩监视。

15.根据权利要求12中所述的方法，进一步包括在虚拟坐标地图中更新虚拟坐标，以确定网络中的节点的状态改变的步骤。

16.根据权利要求15中所述的方法，进一步包括通过细分集群来调查在哪里已发生改变的步骤。

17.根据权利要求16中所述的方法，进一步包括确定被细分的集群的质心，并且如果集群的状态已改变，则进一步细分该集群的步骤。

18.根据权利要求12中所述的方法，其中监视的步骤包括确定已改变状态的所识别节点。

19.根据权利要求18中所述的方法，其中确定已改变状态的所识别节点的步骤包括如果区段的被监视特性已改变，则列出被影响的节点。

20.根据权利要求19中所述的方法，进一步地包括将被影响的节点与已改变状态的节点相比较以确定对状态改变负责的候选对象的步骤。

21.根据权利要求12中所述的方法，其中被监视的状态改变包括延迟改变、距离改变、安全、分组损失率及/或活动性改变。

22.根据权利要求12中所述的方法，其中确定节点坐标位置的步骤包括计算虚拟地图环境中的距离。

23.一种用于监视网络中状态改变的系统，包括：被连接到网络并与网络交互以从网络收集虚拟坐标信息的服务器；

存储在与服务器相关的存储器中的虚拟地图，该虚拟地图包括节点及代表节点的虚拟坐标，代表节点代表网络中的节点组；以及定期测试地图中的虚拟坐标以检测节点或节点组中的或之间的状态改变的定期监视模块，虚拟坐标表示网络的被监视特性，其中定期监视模块比较新虚拟坐标与旧的虚拟坐标以确定状态改变是否已发生。

24.根据权利要求23中所述的系统，其中定期监视模块在多个不同集群层次上监视代表节点以提供网络的可伸缩监视。

25.根据权利要求23中所述的系统，其中被监视的状态改变包括延迟改变、距离改变及/或业务改变。

26.一种用于节点网络中可伸缩状态改变检测的方法，包括步骤：将节点坐标位置嵌入到分层布置的虚拟地图环境中；

用代表虚拟地图表示节点集群以形成表示节点的集群及子集群的虚拟地图的层次结构，使得代表虚拟地图的状态改变意味着集群或子集群的节点中的状态改变；以及有选择地监视代表虚拟地图的状态改变，使得代表虚拟地图产生对网络进行可伸缩监视的能力，其中包括步骤：计算代表节点的新虚拟坐标，其中代表节点代表节点集群或子集群；

将计算的新虚拟坐标与旧虚拟坐标相比较；以及如果代表节点的坐标改变超过阈值，则确定代表节点的状态已改变。

说明书

技术领域

本发明涉及用于利用可伸缩的端到端方案迅速检测网络异常或网络延迟的较大改变的可伸缩分层系统及方法。

背景技术

用户或网络操作员通常想要连续监视网络的不同部分的状态以迅速检测异常。当前网际路由协议进行链路状态监视并调整路由表以绕过故障链路。然而，由于BGP(边界网关协议)策略路由，远程网络的路由变更信息通常不传播给互联网的其他部分。对于像覆盖网络或p2p(端到端)网络的一些应用，节点数量非常大并且广泛分布。因此，迅速知道远程节点周围的网络状态是相当困难的。
一种直接的方式是连续地监视有关的节点。然而，如果有关节点的数量较大，则监视过程不是可伸缩的。

发明内容

本发明的实施例包括利用基于虚拟坐标的地图嵌入处理以使监视网络更加可伸缩并能够处理网络改变的动态特性的分层方法。分层方案被包括进来，该方案旨在通过将分层地图嵌入与详细拓扑结构感知探测(detailed topology aware probing)相结合来确定网络中的延迟异常，并通过虚拟坐标方案有选择地诊断网络延迟异常。针对描述虚拟坐标的属性的改变的选择性诊断也被包括进来。
用于节点网络中可伸缩状态改变检测的系统及方法包括将节点坐标位置嵌入到虚拟地图环境中。节点集群由代表节点来代表，以形成节点及集群的层次结构，其中代表节点的状态改变意味着该集群的节点的状态改变。通过有选择地监视代表节点的状态改变，代表节点产生对网络进行可伸缩监视的能力。
用于节点网络中可伸缩状态改变检测的系统/方法包括在虚拟地图环境中确定参考位置并且基于虚拟地图环境中的参考位置确定节点坐标位置。基于虚拟地图环境中的位置执行节点的集群化。节点集群用领导节点(leader node)代表，其中领导节点的状态改变意味着该集群的节点的状态改变。监视领导节点的状态改变。
用于节点网络中可伸缩状态改变检测的另一个系统/方法包括将节点坐标位置嵌入到虚拟地图环境中，并且用代表虚拟地图表示节点集群，以形成代表节点的集群及子集群的虚拟地图的层次结构，以使代表虚拟地图的状态改变意味着集群或子集群的节点的状态改变。有选择地监视代表虚拟地图的状态改变，以使代表虚拟地图产生对网络进行可伸缩监视的能力。
用于监视网络中状态改变的系统包括连接到网络并与网络进行交互以从网络收集虚拟坐标信息的服务器。虚拟地图被存储在与服务器相关的存储器中。虚拟地图包括节点及代表节点的虚拟坐标，所述代表节点代表网络中的节点组。监视模块定期更新地图中的虚拟坐标以检测节点或节点组中的或之间的状态改变。虚拟坐标表示网络的被监视特性。
结合附图阅读，通过下面说明性的实施例的详细描述将明白这些及其他目的、特性和优点。

附图说明

本申请将参考以下附图在下面优选实施例的描述中提供细节，其中：
图1是示出被分配给虚拟地图的地标位置的示意图；
图2是根据一个实施例，示出用于监视网络改变的方法的方框/流程图；
图3是根据更详细的实施例，示出用于监视网络改变的方法的方框/流程图；
图4是示出相对于虚拟地图中的地标位置所确定的节点或主机位置的示意图；
图5是根据本发明的一个方面，示出为节点组所选择的代表或领导节点的示意图；
图6是示出被细分以确定其中异常可能已发生的位置的节点集群的示意图；
图7是示出确定其中异常可能已发生的段位置的示意图；
图8是根据本发明的说明性实施例，示出用于监视网络的系统的方框图。

具体实施方式

本发明的示范性实施例提供可伸缩自适应网络监视系统及方法。目标节点被分组成若干集群。集群中的节点优选地在一个紧密区域中。换言之，节点的网络状态改变意味着其他节点的网络状态改变。然而，很难弄清楚哪些节点接近哪些节点。
采用了虚拟坐标系统，其中在因特网或其他网络中选择一组强制回应命令发出点(ping points)、地标节点或其他参考位置。测量从参考位置到目标节点的距离。基于从参考位置到目标节点的网络距离，以通过欧几里得空间中的几何距离估计网络距离的方式，在2或3维欧几里得空间中针对每个目标节点计算一组虚拟坐标。因为虚拟坐标系统提供了估计主机之间的距离的方法，可应用集群形成算法，例如K-均值(K-mean)来分组目标节点。接下来，从每个集群中选择节点，并且仅监视被选定的节点。监视包括地标节点定期测量从其本身到选定节点的距离。之后，计算选定节点的新虚拟坐标。
如果选定节点的位置发生改变从而超过阈值，则该节点周围的网络状态很可能也已改变。节点属于的组被进一步地调查。然而，不必监视该组中所有节点。通过应用一些集群形成算法，该组可被细分成若干子组，然后针对每个子组选择质心(centroid)或代表节点。质心的网络状态可被再次获得。如果一些质心已改变其位置，则子组可被进一步地细分。
网络状态改变的节点可以被识别。该组节点可被称为已识别节点。然而，实际上可能不知道网络的有问题地区。为得到更详细信息，可使用踪迹路径(traceroute)数据，假定可得到从地标节点到所有目标节点的踪迹路径数据。
收集踪迹路径数据中涉及的区段集合。区段是一组连续的链路，在其上没有附连分支。然后，针对每个区段，可迭代执行下面的步骤。
选择一个区段，并且如果该区段已增加了其延迟，则列出所有将受该区段的延迟增加的影响的目标节点。如果选定的目标节点的集合是已识别节点的子集，该区段则是导致网络状态改变的可能候选对象。如果该集合是已识别节点的超集，则该区段不会是有问题的节点。可针对其他区段执行该迭代序列。
按以上步骤选定的区段集合包括可能已导致问题的候选对象。在选定的区段集合中，选择最小区段子集。该最小区段子集被认为已导致已识别节点的网络改变。该算法中的一个探索是网络改变的原因应该尽可能小。为找出该集合，可使用直接的指数时间算法，例如仅尝试所选区段的每个子集来检查是否该子集导致已识别节点的网络状态改变。
本发明的实施例可以采取完全硬件实施例、完全软件实施例或硬件和软件元素两者都包括的实施例的形式。在最优实施例中，本发明被以软件方式实现，其包括但不局限于固件、常驻软件、微代码等等。
更进一步地，本发明可以采取从计算机可用的或计算机可读的介质可获得的计算机程序产品的形式，该计算机可用的或计算机可读的介质提供程序代码以便由计算机或任何指令执行系统使用或与之结合使用。出于这里的说明的目的，计算机可用的或计算机可读的介质可以是任何装置，其可以包含存储、传送、传播或传输程序以便由指令执行系统、装置或设备使用或与之结合使用。介质可以是电子的、磁性的、光学的、电磁的、红外线的或半导体系统(或装置或设备)或传播介质。计算机可读的介质的例子包括半导体或固态存储器、磁带、可折卸计算机软盘、随机存取存储器(RAM)、只读存储器(ROM)、硬磁盘以及光盘。光盘的当前例子包括高密度盘-只读存储器(CD-ROM)、高密度盘-读/写(CD-R/W)以及DVD。
适用于存储及/或执行程序代码的数据处理系统可包括直接或通过系统总线间接地连接到存储器单元的至少一个处理器。存储器单元可包括程序代码的实际执行期间所采用的本地存储器、成批存储设备以及高速缓冲存储器，其提供至少一些程序代码的暂时存储以减少执行期间从成批存储设备取出代码的次数。输入/输出或I/O设备(包括但不限于键盘、显示器、定位设备等等)可被直接或者通过中间的I/O控制器连接到系统。
网络适配器也可被连接到系统以使数据处理系统能够通过中间私人或公共网络变为连接到其他数据处理系统或远程打印机或存储设备。调制解调器、电缆调制解调器以及以太网卡只是若干当前可用类型的网络适配器。
现在参考附图，其中同样的数字代表相同的或类似的元素，并且最初参考图1，根据本发明的实施例说明性地示出了可伸缩网络距离地图服务。网络10可包括因特网、有线网、电话网、局域网、广域网或任何其他分布式网络。网络10包括多个节点。这些节点当中，可定义地标或测量点22。
每个节点被分配了在虚拟地图30中代表其位置的一组坐标24。坐标(例如，(x，y)坐标)反映相对于地图30中的其他节点的一个或多个特性(例如，延迟、距离、业务拥塞、分组损失率、活动性、安全性等等)。例如，x，y可以是位置；x可以是延迟而y是业务测量，等等。以所期望的特性的相对顺序保持有效的方式确定被分配的坐标24。例如，可以考虑一组节点间的往返时间(RTT)度量。每个节点22被分配了虚拟地图30中欧几里得空间坐标，使得两个坐标之间的欧几里德距离提供两个相应节点之间的RTT。该过程可被定义为“地图嵌入”过程。本发明利用地图嵌入过程来可伸缩地确定网络中节点之间的例如延迟改变、距离或其他特性。
可以有任何数量的地标或其他参考位置22；然而三个良好分布的地标可给出优选的结果。采用地标22来提供参考，可对照地标22来限定其他节点在虚拟坐标地图中的坐标。
参考图2，根据本发明的一般实施例，示出了地图嵌入过程。在方框102中，在N个节点的大集合当中，只有一些节点M(其中M＜＜N)被选为领导节点。这M个节点的集合包括被用于地图嵌入过程的集群领导。如果需要，也可选择单一节点。在多分辨率方案中，可建立多级集群或节点组。针对节点的每个分层，只有代表或领导节点(或其虚拟地图)需要被监视。
在方框104中，利用期间间隔，这些M节点被嵌入到地图中以确定这些节点的坐标。
如果坐标存在改变(超出指定阈值)，则在方框106中，将节点标记成检测已改变的坐标的候选节点。现在，在方框108中，更详细的过程(利用踪迹路径或其他软件算法)被用来检测该节点集合当中何处网络延迟已改变。
参考图3及4，更详细地示例说明利用地标节点的地图嵌入过程。在地标节点已被选定、加到虚拟地图中并且针对地标节点，例如L1、L2、L3(如参考图1及2所描述)确定坐标之后，在方框202中，相对一组地标节点22测量每个节点或主机节点20，例如测量RTT。图4示出了计算虚拟地图30中地标22的坐标24之间距离的节点或主机节点20。一旦确定相对这些地标22的RTT，在方框204中，坐标(x，y)25被分配给节点20，使得欧几里得距离保持有关的度量。在方框206中，可采用集群形成算法来确定哪些节点一起组成集群以及为每个集群35定义领导节点33(见图5)。
参考图5，节点20可被分组成节点集群35。可采用集群形成算法来确定哪些节点一起组成集群。优选地，集群35中节点20在区域中彼此“接近”。换言之，节点的网络状态改变意味着其他节点的网络状态改变。当难以确定哪些节点彼此“接近”时，采用虚拟坐标系统30(图4)，其中在网络10中选择强制回应命令发出点(ping point)集合(地标22)。从地标22到已经确定的目标节点20的距离可被用来将节点分组成集群35，虽然可采用其他标准。每个集群35将定义其自己的领导节点33，其为集群35的节点的代表。
再次参考图3，在方框206中，在一个实施例中，基于从地标22到目标节点20的网络距离，以通过欧几里得空间中的几何距离估计网络距离的方式，针对每个目标节点计算2(或3)维欧几里得空间中的一组虚拟坐标。因为虚拟坐标系统提供了估计主机(20)间的距离的方法，可应用诸如K-均值(K-mean)的集群形成算法来组合目标节点。
在方框214中，选择并监视来自每个集群的节点(例如，领导节点33)。在一个实施例中，只有选定节点被监视。监视假定地标节点定期测量从其本身到选定节点的距离。之后，在方框216中计算选定节点的新虚拟坐标。
在方框218中，新虚拟坐标与旧虚拟坐标相比较，并且如果选定节点的位置发生改变从而超过阈值，则该节点周围的网络状态很可能也已改变。在方框220中，因为系统可能没有监视组中的所有节点，已发生超过阈值的改变的组被进一步地调查以确定何处已发生改变。
在方框222中，通过应用一个或多个集群形成算法，组被细分成若干子组。在方框224中，针对每个子组选择或计算质心，并且针对质心再次检查网络状态(方框208)。如果一些质心已改变其位置，则在方框226中，子组被进一步地细分。
参考图6，监视领导节点(或虚拟地图)，直到遇到超过阈值的改变。如果这样的问题存在，则集群形成程序细分集群(或集群的虚拟地图)35成子集群(或子集群的虚拟地图)40及42。针对每个子集群40及42确定质心45及47并执行监视以进一步地识别哪个子集群已遇到改变。每个子集群40及42然后可以被进一步地细分成子子集群50，如此类推，直到已识别出状态改变。
通过提供节点的集群化及解除集群，提供了用于监视网络的分层系统，其完全可伸缩成任何规模的网络或任何数量的节点。如果一切顺利进行，则可以在高层次上监视系统，或在故障点中在非常低的层次上，或以任何粒度组合来进行监视。
也应该理解，虚拟地图可以以和节点相同的分层方式来布置。这样，可以监视集群的虚拟地图，并且如果发生改变，则通过下降虚拟地图的层次，直到问题可以被识别并解决，问题可以被放大。虚拟地图可被如此处所描述地用于监视网络的节点代替。
在一个实施例中，利用分层布置的虚拟地图可进行节点网络中的可伸缩状态改变检测。节点坐标位置被嵌入到虚拟地图环境中。节点集群可由代表虚拟地图表示，以形成表示节点的集群及子集群的虚拟地图层次结构，使得代表虚拟地图的状态改变意味着集群或子集群的节点中的状态改变。有选择地监视代表虚拟地图的状态改变，并且代表虚拟地图产生对网络进行可伸缩监视的能力。
再次参考图3，在方框228中，网络状态改变的节点可以被识别。该组节点可被称作已识别节点。然而，没有明确地知道实际成为问题部分网络的区域。为得到更详细的信息，可使用踪迹路径数据或其他数据，假定可得到从地标到所有目标节点的踪迹路径数据。在方框230中，踪迹路径数据中涉及的区段集合得到收集。区段是一组连续的链路，在其上没有附连分支。然后，对于每个区段，在检测算法中执行并迭代下面步骤。
在方框232中，选择一个区段。在方框234中，如果该区段已改变其延迟或其他被监视特性已改变，则列出所有会受区段的延迟增加的影响的目标节点。在方框236中，如果选定的目标节点的集合是已识别节点的子集，则该区段是导致网络状态改变的可能候选对象。在方框238中，如果该集合是已识别节点的超集，则该区段不可能是有问题的节点。针对其他区段执行迭代。
选定区段的集合包括可能已导致问题的候选对象。在选定区段集合当中，优选地选择最小区段子集。该最小区段子集可被断定为已导致已识别节点的网络改变。该算法中的一个探索包括网络改变的原因应该尽可能小。为找出集合，可使用直接的指数时间算法，例如仅尝试所选区段的每个子集来检查是否该子集导致已识别节点的网络状态改变。
参考图7，其中示例性示出了表明节点20之间的区段60的区段地图。每个区段60可具有针对具体区段所计算或测量的时间或其他特性。利用如上所述的区段分析可以比较这些特性。
区段或节点可以被预先表征。一个可能的方案会是在受控环境或模型中设置节点，并且随着各种延迟的引入，观察所报告的结果以及探测业务。通过利用根据本发明的工具使延迟改变与引入的探测业务相关来分析输出。
参考图8，根据本发明的一个实施例，说明性地示出了用于映射以及监视网络的系统300。服务器310被连接到网络305。网络305包括地标322，其可包括网络305中的节点或其他识别标志。地标322给主机节点或节点320提供测量信息。除地标322之外或代替地标322，也可采用其他参考。基于层次结构的层次或系统已设置的方式，节点320可包括一个或多个领导节点、节点的集群及/或单一节点。地标322提供了参考，其中相对该参考确定节点320的虚拟坐标。
距离或其他信息被输入给服务器310，其处理该信息以将坐标分配给节点320。该信息被存储在数据库或库312中以建立用于分类和关联(集群)主机节点320的虚拟地图环境。库312也存储用于执行在监视网络时所用的多个服务的模块。例如，分别连同其各自的应用编程接口314、316、318及319，说明性地示出距离估计模块330、搜索模块332、服务器选择模块334及定期监视模块336。可增加及提供其他模块以代替或补充说明性地示出的模块。
基于网络节点的虚拟坐标，距离估计模块330执行距离计算。搜索模块332允许针对特定的节点、硬件、性能信息或其他标准进行网络搜索。搜索模块332允许系统查找已遭遇特定的改变或特定值的改变的节点或区段。服务器选择模块334允许确定领导节点或质心来给提供特征节点/服务器以进行监视，而不是监视网络的所有节点。定期监视模块336寻找旧的及新虚拟坐标之间的状态改变。定期测试状态的这些更新并与阈值相比较以确定问题是否存在。其他模块可被增加或替代那些图8中示出的模块。监视模块发送信息或测量请求给特定的主机节点320(主机IP)，并且节点响应以虚拟地图中所接收及更新的信息。
本系统及方法可被作为网络的监视服务提供。分层(集群的层次)允许系统不考虑节点数量而容易地被伸缩为大、小网络。可通过购买运行本发明的方法的程序存储设备来提供该服务。
已描述了利用虚拟坐标映射来检测状态改变的系统及方法的最优实施例(本意是说明性的而非限制性的)，注意到，根据以上教导，本领域技术人员可做出修改及变化。因此可以理解，在所揭示的由附加权利要求概述的本发明范围及精神内的具体实施例中可做出改变。利用由专利法要求的细节及特性，从而已描述了本发明的方面，在附加的权利要求中阐述了由专利特许证所要求及期望保护的方面。