论文部分内容阅读
随着互联网技术的发展，许多互联网应用迫切需要优化数据传输时间，达到提高用户体验质量的目的，因此如何高效地测量参与数据传输过程的节点之间的网络延迟成为一个重要问题。分布式网络延迟测量技术通过参与节点的分布式协作获取节点间的网络延迟，具有较好的可扩展性。已有的分布式网络延迟测量技术可以分为分布式网络坐标技术和分布式网络邻近度估计技术，后者按照邻近信息的表示形式可以分为分布式分簇技术、分布式最近节点搜索技术和分布式K最近节点搜索技术。互联网节点的规模巨大、能力受限特性以及网络延迟的波动性对分布式网络延迟测量技术提出三种基本要求：（1）能够准确地测量网络延迟；（2）能够针对不同的节点规模可扩展地测量网络延迟；（3）能够以较低开销测量网络延迟。然而，已有的分布式网络延迟测量技术未能兼顾精确性、可扩展性和低开销的测量需求。本文针对互联网环境的特点，对互联网环境中分布式网络坐标技术和分布式网络邻近度估计技术进行深入研究。取得的主要研究进展如下：已有的分布式网络坐标方法坐标更新过程中不同节点的坐标误差会相互影响，导致误差累积放大效应。针对已有方法在精确性方面的不足，本文提出一种分布式相对坐标矩阵分解方法——RMF。每个节点随机初始化本节点的坐标位置，定期地随机采样一组逻辑邻居，并根据逻辑邻居的相对坐标迭代更新本节点坐标位置。RMF利用相对坐标的无误差累积优势，避免已有方法的不足，提高了网络延迟测量精确性。此外，RMF采取分布式的坐标更新过程提高可扩展性，并且通过低维度的相对坐标和适中的逻辑邻居规模降低通信开销。模拟测试和PlanetLab测试表明，相对于现有方法，RMF降低了网络延迟测量误差，而且随着节点规模的上升，RMF具有较好的可扩展性，同时在节点失效时保持稳定的精确度。已有的分布式分簇方法中簇首节点容易造成性能瓶颈，同时分簇结构受到启发式规则影响而难以精确表示节点邻近关系。针对分布式分簇方法在可扩展性和精确性方面的不足，本文提出一种分布式层次值矩阵分解方法——HPM，通过网络坐标分布式地计算互联网节点之间的层次分簇。每个节点在加入系统的时候随机初始化一个坐标位置，随后定期地随机采样一组逻辑邻居，测量与逻辑邻居在层次分簇中的层次值，然后根据逻辑邻居的坐标位置迭代地更新本节点的坐标位置。HPM通过分布式最大边际效用矩阵分解过程将坐标距离映射到最优的层次值，提高了层次分簇的精确性，而且HPM利用分布式的坐标更新方法能保持较好的可扩展性，同时利用低维度坐标和适中的逻辑邻居规模降低了通信开销。模拟测试和PlanetLab测试表明，相对于已有的层次分簇方法，HPM以较低的通信开销将分簇精确度提升2至9倍，而且随着节点规模的上升，HPM具有较高的可扩展性，同时在节点失效时保持较为稳定的分簇精确度。已有的分布式最近节点搜索方法逻辑邻居覆盖范围较窄，同时难以发现距目标节点最近的逻辑邻居，导致搜索过程陷入局部最优节点，而且随着目标节点数目的增大其搜索精确度迅速下降。针对已有方法在精确性和可扩展性方面的不足，本文提出单目标节点分布式最近节点搜索方法——HybridNN，以及多目标节点分布式最近节点搜索方法——DEB。HybridNN采取低度量模型递归地选择距目标节点更近的逻辑邻居，能够选择最近的逻辑邻居，同时通过分布式的贪心搜索过程保持了较好的可扩展性。DEB通过本文提出的多目标节点低度量模型递归地选择距多个目标节点平均延迟更小的逻辑邻居，能够在不同的目标节点数目下可扩展地发现最近的逻辑邻居。此外，本文提出了适应网络延迟空间分簇特征的逻辑邻居采样方法，显著提高逻辑邻居的覆盖范围，而且通过网络坐标降低了HybridNN和DEB的搜索开销。模拟测试和PlanetLab测试表明，相对于已有的方法，HybridNN显著降低了单目标节点搜索误差，减小了搜索开销和搜索时间；DEB显著降低了多目标节点搜索误差，缩减了搜索开销和搜索时间，同时随着目标节点数目的上升，保持了较为稳定的搜索精确度。已有的分布式最近节点搜索方法逻辑邻居覆盖范围较窄，易于陷入局部最优，随着最近节点数目的增大，其搜索精确度显著下降。针对已有的方法在精确性和可扩展性方面的不足，本文提出单目标节点分布式K最近节点搜索方法——DKNNS，以及多目标节点分布式最近节点搜索方法——KDEB。DKNNS通过单目标节点最远搜索选择距单个目标节点较远的节点开始单目标节点分布式最近节点搜索过程，在每发现一个最近节点后，回溯到搜索路径的上一跳步节点继续搜索剩余的最近节点。DKNNS提高了回溯后发现距目标节点更近的逻辑邻居的可能性，同时利用回溯过程提高了搜索可扩展性。KDEB通过多目标节点最远搜索选择距目标节点集合平均延迟较大的节点开始多目标节点分布式最近节点搜索过程，在每发现一个最近节点后，回溯到搜索路径的上一跳步节点继续搜索剩余的最近节点。KDEB提高了回溯后发现距多个目标节点平均延迟更小的逻辑邻居的可能性，而且利用回溯过程增强了搜索可扩展性。模拟测试和PlanetLab测试表明，相对于已有方法，DKNNS显著降低单目标节点最近节点搜索误差，缩减了搜索开销和搜索时间；KDEB显著降低了多目标节点最近节点搜索误差，减小了搜索开销和搜索时间；同时随着最近节点数目的增大，DKNNS和KDEB具有较为稳定的搜索精确度。