论文部分内容阅读
网络演算(Network Calculus)是近二十年来受到广泛关注的计算机网络性能分析新理论,它主要有两个分支:确定性网络演算(Deterministic NetworkCalculus,DNC)和随机网络演算(Stochastic Network Calculus,SNC)。DNC的理论和应用研究已经基本成熟,但其分析能力有限。SNC是DNC的随机扩展。它可以有效弥补DNC的理论不足,但其理论和应用研究相对滞后。当前,SNC已经成为计算机网络性能分析理论的一个研究热点。本文针对当前SNC理论研究的困难和实际应用的问题展开深入研究,从代数基础上解决了当前SNC的主要理论困难,大大简化了SNC的理论复杂度,显著提高了SNC性能分析的精度,有效促进了SNC在各个性能分析领域的广泛应用。研究内容大体可以分为两大部分:SNC理论研究部分和SNC应用研究部分。关于SNC的理论研究,主要的研究内容有三个方面:(1)从代数基础的角度分析当前SNC的理论困难并提出有效的解决途径当前,SNC主要以最小加代数为理论基础。由于在最小加代数中进行概率运算存在很大的理论困难,SNC至今仍没有一个大家普遍接受的理论体系。本文从代数基础的角度深入分析当前SNC的理论困难,发现在SNC中概率运算与最小加代数从根本上是不协调的。因而,我们转换思路,尝试构造不基于最小加代数的SNC,并通过SNC的性能分析定理初步论证了思路的可行性。这部分研究工作澄清了当前SNC理论困难的根源,开创了网络演算理论研究的一个全新思路。(2)从公理化的角度研究替换DNC的代数基础并提出性能演算公理系统我们希望构建一个不基于最小加代数的网络演算理论,以解决当前SNC的理论困难,因而我们需要研究如何替换最小加代数在网络演算中的基础作用。本文采用公理化的方法来研究网络演算的性能分析基本定理,并总结提出了一套性能演算公理。基于性能演算公理,我们构建了一个不基于最小加代数的确定性网络演算理论(Non Min-Plus DNC, NMP-DNC)。这个研究工作论证了性能演算公理可以很好地替换最小加代数在网络演算中的基础作用。(3)通过公理化方法研究构建不基于最小加代数的随机网络演算理论这部分研究内容是本文最核心最具原创性的内容。为了解决当前SNC的主要理论困难,我们构建了一个不基于最小加代数的随机网络演算理论(NonMin-Plus SNC, NMP-SNC)。NMP-SNC是由NMP-DNC进行随机扩展得到,其中主要有两大步骤:1)对NMP-DNC中的基本概念进行随机扩展,得到NMP-SNC中的基本概念;2)基于NMP-SNC的基本概念和性能演算公理推导NMP-SNC的性能分析基本定理。为了说明NMP-SNC相对于当前SNC的改进,我们通过一个具体的网络实例将NMP-SNC的分析结果与当前SNC的分析结果进行了详细比较。结果显示,NMP-SNC可以很大程度地简化SNC的理论复杂性,显著提高性能分析结果的精度。这部分研究工作展示了NMP-SNC可以从代数基础上解决当前SNC所面临的主要理论困难,对SNC的理论研究是一个很大的推动。关于SNC的应用研究,主要的研究内容有两个方面:(4)研究SNC应用的共性问题:模型曲线的选择和理论分析的极限网络演算的两个基本概念是到达曲线和服务曲线。SNC应用的一个主要问题就是这两个模型曲线的选择问题。我们提出了一个统一的分析框架来指导模型曲线的选择。SNC应用的另一个主要问题是理论分析的极限问题,即SNC能否与DNC一样可以得到与实际性能足够接近的分析结果。我们研究发现SNC的分析结果与实际性能之间总存在一个难以逾越的差距。这部分研究工作系统讨论了SNC应用的共性问题,同时也提出了相应的解决方案和SNC的应用指导原则。(5)研究网络演算理论在无线网络编码性能分析中的应用问题网络编码是近十年发展起来的一项网络通信新技术。在网络编码中,网络节点可以把不同的数据流编码在一起再同时发送出去。为了使用网络演算来分析无线网络编码的性能,我们主要研究解决了以下三个具体的应用问题:1)当数据流被编码在一起时,如何辨识原始未编码的数据流;2)如何为无线网络中的广播信道建模,以计算节点提供的服务曲线;3)当网络节点可以执行编码操作时,如何计算节点为各个数据流提供的服务能力。基于网络演算,我们详细分析了无线网络编码的性能影响因素,并提出了无线网络编码的改进方案。这部分研究工作将网络演算成功应用于无线网络编码的性能分析,拓展了网络演算的应用领域。综上所述,本文首先针对当前SNC的理论困难,提出了一个公理化的解决方案,构建了一个简洁好用的SNC理论体系(NMP-SNC)。NMP-SNC从代数基础上解决了当前SNC的理论困难,大大简化了SNC的理论复杂度,显著提高了SNC性能分析的精度。基于上述理论研究成果,本文再通过具体的实例分析,研究了SNC应用的共性问题,提出了SNC的应用指导原则,并将网络演算成功应用于无线网络编码的性能分析领域,有效促进了网络演算理论的广泛应用。