测量协同问题研究--完全分布式的解决方案

摘要

精确性是网络测量的一个关键问题.一个测量节点对测量任务的并发执行通常会影响测量结果的精确性,测量任务的互斥执行可以降低或消除这种影响.同时,单向测量需要两个节点协作进行,因此随机产生的测量任务可能会产生冲突,从而导致进程死锁、测量效率低下等一系列问题.我们称该类问题为测量协同问题(MCP).MCP是一类特殊的分布式资源分配问题,它的特殊性主要在于:(1)资源之间协商该被哪个进程(任务)使用;(2)如果任务的资源需求得不到满足,则该任务将被放弃执行.作者提出了测量协同问题完全分布式的算法--CDA,证明了CDA的存活性和正确性,并分析了消息复杂度、空间复杂度和收敛时间.模拟实验表明,CDA具有良好的处理冲突任务的能力,使得CDA在任务并发性较强时仍然具有较好的任务执行能力.