《一种基于端到端测量构造网络性能拓扑的方法.doc》由会员分享，可在线阅读，更多相关《一种基于端到端测量构造网络性能拓扑的方法.doc（8页珍藏版）》请在三一文库上搜索。
1、一种基于端到端测量构造网络性能拓扑的方法中图法分类号：TP393.06文献标识码：A 传统的分布式计算平台(如集群)具有高性能网络连接和可靠性保证。而在异构、层次性的大规模分布式网络中，网络性能成为分布式应用的一个重要瓶颈。分布式应用系统，通常具有特殊的通信模式，其性能在很大程度上依赖于网络的结构特性。因此，对于分布式应用，不仅需要获得节点对之间的带宽、时延、丢包率等性能参数，还需要知道各个节点之间的相互连接关系。获得这些信息，可以预测节点集合之间的通信性能，使得应用在调度决策中不会作出错误的决定，如将通信频繁地应用部署到节点之间网络性能良好的节点集合中去，优化服务的部署。常用的网络拓扑测量方
2、法是分析来自网络内部资源的数据(BGP路由表、ICMP), 生成网络拓扑或性能的报告1。这种方法是基于路由器或路由器协作的,它适合于在大时间尺度上进行宏观分析,但不适合小时间粒度的场合。目前端到端拓扑探测的研究2主要针对连接一个发送者与多个接收者之间的树型拓扑，利用终端节点之间性能相关性(时延/丢包相关性)来推测与某种性能(如时延、丢包率)相关的逻辑拓扑。本文的目的在于通过端到端的测量方法探测对分布式应用产生重要影响的网络性能拓扑结构。 1 性能拓扑结构探测 分布式应用所需要的网络信息主要突出以下两点：性能测量值，如带宽、时延和丢包率（端到端的），反映分布式应用通信效率问题;拓扑结构，能够展示
3、资源之间的相互连接关系，也能够反映出数据传输是否具有共享路径的问题。 网络性能划分方法的一个基本原则是，要使划分到同一个集合中的边缘节点具有相同的特性，包括集合成员之间的带宽特性一致和集合成员对外带宽特性一致。与此同时，集合成员之间的连接关系也必须进行探测，因为在多数据传输时，共享路径也明显影响着应用系统的性能。 利用端到端的网络测量探测性能拓扑结构是较为实用的方法。端到端的性能测量可以使用现有的各种成熟的测量方法和测量工具，而不需要特殊的配置和权限。文献3中研究各种性能测量工具时显示，选择正确测量工具有利于提高测量精度；文献4的研究也指出在应用层能够对有效带宽进行准确建模。 网络性能的分布通
4、常具有相对集中性。各个学校、部门等内部网络性能相对较高（如带宽、丢包率、时延），而区域与区域之间的网络性能相对较差。网络性能也往往具有相关性，如端到端时延等于各路径时延之和,是随路径单调递增(至少不减)的函数。在本文中，首先利用对瓶颈带宽的测量高效地将一个一般网络划分成若干个子集合,并且满足某些最优目标,如测量点最少；然后再通过性能相关性探测各个子集合，构造出完整网络性能拓扑结构。 1.1 测量瓶颈链路分组划分 尽早自动对集合进行划分，有利于减少测量次数提高探测准确度。当一个集合外节点与集合内节点之间带宽性能小于集合内带宽性能时，就可以将这个节点排出划分到该集合之内；当一个集合外节点与某一个集
5、合内节点之间的带宽性能大于集合内带宽性能时，就可以将该集合内节点脱离该集合。 网络测量工作组织5(Network Measurements Working Group，NMWG)参考文档显示，端到端网络带宽相关的几个常用特性为吞吐量、批量数据传输能力、带宽容量和有效带宽。从这些特性中派生出两个最常用的网络特性，即瓶颈带宽和带宽利用率。瓶颈带宽与端到端带宽容量是等价的，而带宽利用率为已用带宽与带宽容量的比值。它们之间的关系进一步表示如下：设H为路径P上的跳数(链路数)，Ci为链路i的带宽容量，C0为发送者的传输能力，那么该路径的带宽容量为 批量数据传输能力(Bulk-Transfer Capab
6、ility，BTC)为网络在一定时间内，持续TCP传输的吞吐量。实验显示，BTC测量结果会比实际有效带宽高出20%30%。但是，BTC反映的是应用在实际运行过程中所能获得的最大带宽，它能够最大程度地反映分布式应用在实际运行过程中网络的性能情况。利用端到端的分布式测量判断多条路径中存在瓶颈带宽6。具体过程如图1所示，三个节点由路由器相连，选择其中两个（S1，S2）为数据源，一个数据接收者D。两个数据源到数据接收者的路径上存在共享路径。在测量和推论中使用如下两个规则： 规则1 如果S1D路径上的带宽大于S2D路径上的带宽，S2D之间的瓶颈链路必须在非共享部分。 规则2 两条路径的带宽相同。最大的可
7、能性就是瓶颈链路存在于它们的共享路径部分。注意到，这种规则可能会得出错误的结论。如果两者的瓶颈链路存在于非共享部分且相等，那么测量出来的结果也会一样。此时，可以重新选择数据源和数据接收者，并使用规则1和规则2进行判断。 采用分布式动态机制，节点可以任意加入或退出分布式系统。对于每一个节点，其初始带宽门限值为0，并属于只含有节点本身的集合。随着各个节点之间的动态发现和两两调度测量，每一个节点能够独立进行分组划分。如下算法详细地说明了在进行带宽测量之后分组划分的情况。 1.2 分析性能相关性拓扑探测 测量瓶颈链路不可以将带宽性能相同的节点排出集合。如图2所示，若A，B与C节点之间的带宽相同，将可能
8、存在两种组合情况，或者成为A，B的兄弟节点，或者与A，B父节点结合。因此，在带宽性能相同的集合中，需要进一步分析。利用网络性能相关性，可以判断出哪些节点之间存在高度联系，共享同一个路由节点。 该性质可以分析潜在的拓扑结构。如图2所示，对于任何节点iR/A,B相关系数A,B将会大于i,A。说明在逻辑拓扑结构中，A和B节点具有同一个父节点。利用这一性质，就可以采用自底向上的合并算法分析出完整的拓扑结构2。对发送者S，设LS为相关接收者按各自测得的丢包率从大到小排序。通常的想法是，若两个接收者共享的路径越多，相应的丢包率也就接近，这两个接收者就应该属于同一个父节点。这种推测，假设了各个路径丢包率是接
9、近的。若r1-r2具有高的丢包率，那么就可以明显看出A和B之间具有相同的较高的丢包率；若r1-r2具有较低的丢包率，而r1-C之间的丢包率又较高，那么得出的结论可能就是A，C之间的丢包率与A，B之间的丢包率相同。 对于每一个边缘节点都存在从该节点角度出发的一个树型结构。若节点之间的路由对称，那么可以认为不同节点看到的拓扑结构等价。假设在一定时间内，各条路径上的丢包率存在空间独立性，那么在同一拓扑结构下，可以得出不同角度的性能分布情况。 不同接收者之间因为有共享路径而存在相关性，而相关性的大小取决于实际路径的具体情况，具有随机性。事实上，上述测量只有S到r1这段路径被三个接收者所共享，若r1到C
10、之间的丢包率较高，就只能显示出相对较低的相关性。反过来，若以C作为发送者，那么C与r1之间这段路径的丢包率就可以表示S，A和B三者之间较高的相关性。 如图3所示，各个路径标注了相应的丢包率，对于各个节点，可以用各条路径丢包率乘积表示其丢包率（为表示方便，乘积越小最终丢包率越大）。从每一个节点的角度出发，得出不同性能视图。从图3(d)可以看出，以C节点为根节点，其他节点所得出的丢包率最大，表示其他节点之间存在一条相关性较大的路径，因此首先将C节点单独划分出来。 2 试验 这一节，用OMNeT+7模拟工具，实现以上拓扑探测方法。在试验中，探测流量由边缘节点发出。与此同时随机产生流量（FTP，Tel
11、net）造成排队时延模拟实际环境。为了分析本文中所使用方法的效率，模拟了在不同节点个数条件下性能拓扑发现的情况，统计其测量次数，以及测量时相互干扰的程度。结果显示，优先进行分组划分能够在很大程度上减少测量次数，单一化第二步进行相关性测量节点集合的性能参数，提高测量准确度。但是，利用测量瓶颈带宽排出非集合节点算法中，非集合节点被排出的先后具有随机性。因为在实际分布式应用系统中，节点加入或离开是动态的，对于每一个节点它所发现的相邻节点先后存在任意性。图4显示了生成树型拓扑结构时性能参数值的相关性情况。若发送数据包增加，相应接收者的丢包样例数也相应增加，意味着不同接收者之间代表共享路径的相关性逼近它
12、的真实值。同时也显示出，不同节点数情况下，随着丢包样例的增加，探测到真实网络拓扑结构的概率是收敛的。图5为利用OMNeT+工具生成的拓扑结构。 3 结论 网络性能往往是分布式应用的一个重要瓶颈。不但节点之间带宽、时延、丢包率等单一的性能值对应用产生影响，全局网络性能分布对应用的优化部署，性能预测也起到重要作用。考虑到实际测量中所用到具体测量技术及效率问题，本文提出以瓶颈带宽进行集合划分以及网络性能相关性对节点树型结构划分结合使用的方法，尽早排出非集合节点，减少了测量次数；利用网络性能相关性，可以对网络内部结构进一步划分，降低对网络性能的消耗。 如何有效地利用两种划分方法在实际操作过程中还存在一定问题。性能相关性拓扑划分是在节点之间有效带宽性能稳定的前提条件下的进一步划分。如何准确地判断网络稳定性，及时进行下一步划分操作问题还有待进一步研究。 本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。