传输控制协议/网际协议(TCP/IP)在Internet中的广泛应用证明了它是一个有效的网络体系结构。但是在空间网络中，连接中断频繁发生，节点间传播延迟很长，TCP/IP并不能有效地运行[1]。延迟中断容忍网络(DTN)[2]是一种新的网络体系结构，能适应网络连接的大延迟和多中断特性，得到了广泛的研究和应用。
Licklider传输协议(LTP)[3]是一个应用于具有极长的传输延迟和频繁中断连接的传输协议，可用于空间网络相邻节点间的数据传输。其设计源于空间网络中点对点数据传输需求，可作为DTN网络的支撑协议。LTP可为上层协议提供可靠或不可靠的数据传输服务，它利用自动重传请求和选择重传实现可靠传输。LTP是一种无状态协议，通信双方不需要协商或握手的过程，通过预先保存的链路状态线索决定传输的开始或暂停。应用程序将需要传输的数据发送給LTP实体后，实体在链路可用时发送数据，链路不可用时暂停发送。
LTP协议数据单元为块，1个块由多个数据段组成。在数据段需要可靠传输时，当LTP判断数据块接收完毕后，向发送实体返回1个接收报告，确认哪些数据段已经正确收到。发送方收到接收报告后，重新发送报告中未确认的数据段。这个往返过程重复多个轮次，直到所有数据段被成功接收。
传输时延是网络数据传输的重要性能指标，协议的设计对传输延迟产生影响。传播延迟是LTP应用场景中总体传输延迟的重要组成部分，以火星探测的应用场景为例，从火星到地球的光传播延迟达8~20 min。传输轮次直接决定了整体的传播延迟，因此有必要对传输轮次深入分析。
现有的相关研究中，文[4, 5, 6]以仿真和测试的方式，考察了在不同的传输协议(包含LTP)支持下，地月通信场景中DTN的性能特性。其中，文[4, 5]测试比较了不同的传输协议、不同误码率等设置下的信道利用效率和数据传输延迟； 文[6]分析了同一链路中并发会话数量和每个会话容量对链路吞吐量的影响。文[7]分析了地月通信场景中的LTP数据块的聚合问题，考虑返回确认延迟和传输效率，提供了一种最优聚合数量计算方法。文[8]以仿真实验的方式考察了基于LTP的DTN数据传输在火星探测场景中的性能，分析了在不同的LTP数据块长度和数据段长度下的发送时间、协议开销以及内存占用问题。文[9]提供了2种选择重传协议的队列长度分析方法，可用于节点排队延迟的分析。文[10]提供了一个选择重传协议的性能界限，分析的指标为链路的吞吐量。文[11]分析了往返时间可变的无限信道中的选择重传协议的性能，考察的指标为排队延迟和发送延迟。文[12]分析了无限信道中的选择重传协议的性能，考察的指标为吞吐量。
已有的研究对LTP的评价主要针对具体的场景，采用仿真和测试的方法，形式化的分析和结论较少； 对其他选择重传协议的评价主要基于Markov假设，评价指标主要集中在节点的排队和发送等行为。现有文献没有对LTP协议以及其他选择重传协议的传输轮次和传播延迟进行形式化研究。
本文首先给出了一种传输轮次的形式化评价方法，结论包含传输轮次的分布函数、期望和方差，并给出了期望和方差的截断计算方法，然后提出了一种形式上更加简洁的轮次期望值的上下界和近似值计算方法，然后通过仿真验证了上述方法和结论的正确性。
1 传输轮次分析一次确认和传输的过程定义为一轮。每一轮的开始时刻为数据的发送开始时刻。收到返回确认后，一轮传输结束，开始下一轮数据发送。为了加速确认的过程，1个LTP数据块中可能包含多个检查点。在评价传输延迟的过程中，包含多个检查点的LTP数据块可以认为是多个数据块，针对每个数据块来评价。因此本文假设每一轮传输过程中，仅最后一个数据块被标记为检查点。
每一个数据段传输过程中都可能丢失，因此需要建立丢失事件的数学模型。独立同分布模型是性能评价中随机事件的常用模型，文[13]的研究表明： 当链路发生异常的概率较低，异常时段长度与一个数据段传输过程所需长度相比为较小值时，独立同分布模型能较好应用于数据丢失情况分析。本文假设每一个数据段的丢失事件的发生是独立同分布的。用pf表示数据段的发送成功概率，pb表示返回确认段的发送成功概率，则单轮次的成功发送概率p=pfpb。
对一个包含b个数据段的LTP数据块，计第i个数据段在第Ri个轮次成功发送并确认，所有数据段在第R个轮次后均已成功发送并确认。则Ri和R都是随机变量，且有R=max{Ri}。
1.1 分布函数对于独立的数据段i，Ri服从参数为p的几何分布，令q=1-p，有
| $ \begin{align} & P\left\{ {{R}_{i}}=n,n\in {{\mathbb{N}}_{+}} \right\}={{q}^{n-1}}p,\\ & P\left\{ {{R}_{i}}=n,n\in {{\mathbb{N}}_{+}} \right\}= \\ & 1-P\left\{ {{R}_{i}}=n,n\in {{\mathbb{N}}_{+}} \right\}=1-{{q}^{n}}. \\ \end{align} $ |
由于每个数据段的传输是独立的，因此有：
| $ \begin{align} & P\left\{ R\le n \right\}=P\left\{ \max \left( {{R}_{i}} \right)\le n \right\}= \\ & P\left\{ R\le n,i\in \left\{ 1,2,\cdots ,b \right\} \right\}= \\ & P\left\{ {{R}_{1}}\le n \right\}\times P\left\{ {{R}_{2}}\le n \right\}\times \cdots \times P\left\{ {{R}_{b}}\le n \right\}= \\ & \ \ \ \ \ \ \ \ {{\left( 1-{{q}^{n}} \right)}^{b}}. \\ \end{align} $ |
可得到传输轮次的分布函数为
| $ \begin{align} & P\left\{ R=n \right\}=P\left\{ R\le n \right\}-P\left\{ R\le n-1 \right\}= \\ & \ \ \ \ \ {{\left( 1-{{q}^{n}} \right)}^{b}}-{{\left( 1-{{q}^{n-1}} \right)}^{b}}. \\ \end{align} $ |
这里分别考察不同的b和段丢失率e下的传输轮次特性。b分别取102和104，e分别取10-2、 10-3和10-4。在6种不同的b和e的组合下，成功传输一个LTP数据块所需要的轮次R的分布函数曲线如图1所示。
|
| 图 1 不同段丢失率和块长度下的轮次分布 |
根据轮次的分布函数，可以的到轮次的期望值为
| $ \begin{align} & E\left( R \right)=\sum\limits_{n=1}^{+\infty }{nP\left\{ R=n \right\}=} \\ & \ \ \sum\limits_{n=1}^{+\infty }{n\left( {{\left( 1\text{-}{{q}^{n}} \right)}^{b}}-{{\left( 1-{{q}^{n-1}} \right)}^{b}} \right).} \\ \end{align} $ |
方差为
| $ \begin{align} & D\left( R \right)=E\left( {{R}^{2}} \right)-{{E}^{2}}\left( R \right)= \\ & \sum\limits_{n=1}^{+\infty }{{{n}^{2}}\left( {{\left( 1\text{-}{{q}^{n}} \right)}^{b}}-{{\left( 1-{{q}^{n-1}} \right)}^{b}} \right)-} \\ & {{\left( \ \sum\limits_{n=1}^{+\infty }{n\left( {{\left( 1\text{-}{{q}^{n}} \right)}^{b}}-{{\left( 1-{{q}^{n-1}} \right)}^{b}} \right)} \right)}^{2}}. \\ \end{align} $ |
以上期望和方差的表达形式均为无穷项和形式。因此需要通过有限项和值作为其近似值。从图1可以看出，分布曲线达到峰值以后迅速降低到接近零，即曲线有一个“短尾”。因此实际计算中只需要计算有限的前几项即可得较高的精确度。
这里提出一种截尾法： 记一个数据段在第n轮成功发送的概率为g(n)，求满足g(n+1)＜g(n)和 $\sum\limits_{i=n+1}^{n+l}{g\left( i \right)}/\sum\limits_{i=1}^{n}{f\left( i \right)}\le \delta $的n最小值，记为N。其中，l和δ为需要预先给出的预算的尾部长度和截尾占比。在E(R)和D(R)的计算中，截断第N项以后部分。l越大，δ越小，截得的N越大，结果越准确。
根据这种截尾法，取l=5，δ=0.001，b分别取从100 到20 000 的每一个自然数，e分别取10-2、 10-3、 10-4和10-5，E(R)和D(R)计算结果分别如图2和3所示。
|
| 图 2 不同段b和e下的E(R) |
|
| 图 3 不同段b和e下的D(R) |
节1给出了轮次的分布、期望和方差。结果中期望和方差的计算需要给出截尾长度和截尾占比，并计算不确定项的累加和。因此，使用前需要了解方法的基本过程和这2个概念的含义，过程相对较为繁琐，计算量也相对较大。本节给出一种易于快速使用的轮次期望的上下界和近似值。对于方差，通过分析图3可以看出，D(R)随b和e变化呈现周期性变化，且最大值基本确定，可以直接将0.3和0作为其方差的上下界。
以下讨论期望值的上下界，首先给出2个定理。
定理1 设X~exp(λ)，令 $Y=\left\lfloor X \right\rfloor +1$，则 Y~geo(1-e-λ)。
证明 X~exp(λ)即X为连续型随机变量，其概率密度函数为
| $ f\left( x \right)=\left\{ \begin{align} & \lambda {{e}^{-\lambda x}},x\ge 0; \\ & 0,\ \ \ \ \ \ \ x<0. \\ \end{align} \right. $ |
因此 $Y=\left\lfloor X \right\rfloor +1 $ 是离散型随机变量，其分布函数为
| $ \begin{align} & P\left( Y=k \right)=P\left( \left\lfloor X \right\rfloor +1=k \right)= \\ & \ \ P\left( k-1\le X<k \right)= \\ & \int_{k-1}^{k}{\lambda {{e}^{-\lambda x}}}dx=\left( 1-{{e}^{-\lambda }} \right){{\left( {{e}^{-\lambda }} \right)}^{k-1}}. \\ \end{align} $ |
即Y~geo(1-e-λ)。
定理2 对
| $ f\left( n \right)=\left( n+1 \right)\sum\limits_{i=1}^{n}{\left( C_{n}^{i}\frac{{{\left( -1 \right)}^{i}}}{{{\left( i+1 \right)}^{2}}} \right)},n\in {{\mathbb{N}}_{+}}, $ |
有ln(e(n+2)/2)＜f(n)＜ln(e(n+1))
证明 f(n)可整理为 $\sum\limits_{i=1}^{n}{\left( C_{n}^{i}\frac{{{\left( -1 \right)}^{i}}}{{{\left( i+1 \right)}^{2}}} \right)}$，进一步可以得到。
构造2个连续函数g1(x)=ln(e(x+2)/2)和g2(x)=ln(e(x+1))，则有g′1(x)=1/(x+2)，g′2(x)=1/(x+1) ，且f(0)=g1(0)=g2(0)=1。因此，对 $n\in {{\mathbb{N}}_{+}}$ 有
| $ \begin{align} & {{g}_{1}}\left( n \right)={{g}_{1}}\left( 0 \right)+\sum\limits_{i=0}^{n-1}{\int_{i}^{i+1}{g{{'}_{1}}}}\left( x \right)dx= \\ & \ \ \ \ {{g}_{1}}\left( 0 \right)+\sum\limits_{i=0}^{n-1}{\int_{i}^{i+1}{\frac{1}{x+2}dx<}} \\ & \ \ \ \ {{g}_{1}}\left( 0 \right)+\sum\limits_{i=0}^{n-1}{\int_{i}^{i+1}{\frac{1}{i+2}dx=}} \\ & \ \ \ \ \ \ f\left( 0 \right)+\sum\limits_{i=0}^{n-1}{\frac{1}{i+2},} \\ \end{align} $ | (1) |
| $ \begin{align} & {{g}_{\text{2}}}\left( n \right)={{g}_{\text{2}}}\left( 0 \right)+\sum\limits_{i=0}^{n-1}{\int_{i}^{i+1}{g{{'}_{\text{2}}}}}\left( x \right)dx= \\ & \ \ \ \ {{g}_{\text{2}}}\left( 0 \right)+\sum\limits_{i=0}^{n-1}{\int_{i}^{i+1}{\frac{1}{x+2}dx>}} \\ & \ \ \ \ {{g}_{2}}\left( 0 \right)+\sum\limits_{i=0}^{n-1}{\int_{i}^{i+1}{\frac{1}{i+2}dx=}} \\ & \ \ \ \ \ \ f\left( 0 \right)+\sum\limits_{i=0}^{n-1}{\frac{1}{i+2},} \\ \end{align} $ | (2) |
| $ \begin{align} & f\left( n \right)=f\left( 0 \right)+\sum\limits_{i=0}^{n-1}{\left( f\left( i+1 \right)-f\left( i \right) \right)=} \\ & \ \ \ \ \ \ f\left( 0 \right)+\sum\limits_{i=0}^{n-1}{\frac{1}{i+2}.} \\ \end{align} $ | (3) |
综合式(1)—(3)，有g1(n)＜f(n)＜g2(n)，定理2即证。
根据定理1，构造b个随机数Xi，且Xi~exp(-ln(1-p))。令X=max(Xi)，取Yi=|Xi|+1，则有Yi~geo(p)。节1的结论中有Ri~geo(p)，R=max(Ri)，因此有:
| $ \begin{align} & E\left( R \right)=E\left( \max \left( {{R}_{i}} \right) \right)=E\left( \max \left( {{Y}_{i}} \right) \right)= \\ & \ \ \ \ \ \ \ \ \ \ \ E\left( \max \right)\left( \left\lfloor {{X}_{i}} \right\rfloor +1 \right)\in \\ & \ \ \ \left( E\left( \max \left( {{X}_{i}} \right) \right),E\left( \max \left( {{X}_{i}} \right) \right)+1 \right). \\ \end{align} $ | (4) |
对X有P{X≤x}=(1-eωln(q))b，其概率密度函数为
| $ {{f}_{X}}\left( x \right)=b{{\left( 1-{{e}^{x\ln \left( q \right)}} \right)}^{b-1}}\ln \left( q \right)\left( -{{e}^{x\ln \left( q \right)}} \right). $ |
因此有：
| $ \begin{align} & \int_{0}^{+\infty }{b{{\left( 1-{{e}^{x\ln \left( q \right)}} \right)}^{b-1}}}\ln \left( q \right)\left( -{{e}^{x\ln \left( q \right)}} \right)xdx= \\ & \frac{-b}{\ln \left( q \right)}\sum\limits_{i=0}^{b-1}{C_{b-1}^{i}}{{\left( -1 \right)}^{i}}\frac{1}{{{\left( i+1 \right)}^{2}}}. \\ \end{align} $ |
根据定理2，有:
| $ \begin{align} & -ln\left( e\left( b+1 \right)/2 \right)/\ln q\le E\left( X \right)\le \\ & \ \ \ \ \ \ -\ln \left( eb \right)/\ln q. \\ \end{align} $ | (5) |
结合式(4)和(5)，可以得到一个轮次期望的上界和一个下界，形式为
| $ \begin{align} & E\left( R \right)<1-\ln \left( eb \right)/\ln q,\\ & E\left( R \right)>-\ln \left( e\left( b+1 \right)/2 \right)/\ln q. \\ \end{align} $ |
可以把其中值作为其近似值，其值为-ln(e2b(b+1)/2)/(2lnq)。
3 数值仿真计算与比较本节比较节1和2的方法以及仿真方法得到的结果。节1中的截断结果包含期望值和方差，因此本节将截断结果的期望值和方差均与仿真结果进行了比较，截断过程中取l=5，δ=0.001 。节2中的上下界法只包含期望值的分析，不包含方差分析。对截尾法和上下界法，b取从100到20 000 的每一个自然数； 对仿真法，在该范围内间隔100取值。e分别取10-2、 10-3、 10-4和10-5。
不同e下的E(R)如图4—7所示。截尾法舍弃了一部分高轮次数据，其理论值应该略小于仿真结果，但图4—7中结果与仿真结果基本相同，说明了截尾法的有效性。图4—7中的上下界有效包夹了仿真结果，另外上下界的中值较好地逼近了仿真结果。
|
| 图 4 E(R)比较(e=10-2) |
|
| 图 5 E(R)比较(e=10-3) |
|
| 图 6 E(R)比较(e=10-4) |
|
| 图 7 E(R)比较(e=10-5) |
图8为同样场景设置情况下截尾法和仿真法求得的D(R)，2种方法得到的结果也完全一致。
|
| 图 8 D(R)比较 |
本文对LTP协议数据传输所需要的轮次进行了深入的分析，提供了2种形式化的结果，结论包含轮次的期望和方差。与仿真法结果的比较证明了结论的正确性。截尾法的表达形式需要截断，适用较为复杂的问题； 上下界法为轮次期望提供了1个上下界和近似值，其结论形式非常简洁，易于使用。截尾法的结论计算过程相对复杂，计算精度较高，结论较为全面，适合任务规划和综合分析的场合； 上下界法的结论形式简单，计算量小，可以部署在航天器或地面节点上，用于网络节点的实时计算。
| [1] | 李洋. Linux安全策略与实例[M]. 北京:机械工业出版社, 2009.LI Yang. Linux Security Policy and Example[M]. Beijing:China Machine Press, 2009.(in Chinese) |
| [2] | Pfleeger C P. Security in Computing.[M]. 4th ED. Upper Saddle River, NJ, USA:Prentice Hall, 2006. |
| [3] | 范九伦, 刘宏月. 密码学基础[M]. 西安:西安电子科技大学出版社, 2008.FAN Jiulun, LIU Hongyue.Foundations of Cryptography[M]. Xi'an:Xidian University Press, 2008.(in Chinese) |
| [4] | Sabelfeld A, Myers A C. Language-based information-flow security[J]. IEEE Journal on Selected Areas in Communications, 2003, 21(1):5-19. |
| [5] | Xu W, Bhatkar S, Sekar R. Taint-enhanced policy enforcement:a practical approach to defeat a wide range of attacks[C]//15th USENIX Security Symposium. Vancouver, Canada:USENIX Association, 2006, 9. |
| [6] | Zeldovich N, Boyd-Wickizer S, Kohler E, et al. Making information flow explicit in histar[C]//Proceedings of the Symposium on Operating Systems Design and Implementation. Seattle, WA, USA:USENIX Association, 2006:263-278. |
| [7] | Efstathopoulos P, Krohn M, VanDeBogart S, et al. Labels and event processes in the asbestos operating system[C]//Proceedings of the ACM Symposium on Operating Systems Principles. Brighton, UK:ACM, 2005:17-30. |
| [8] | Yang J, Shin K G. Using hypervisor to provide data secrecy for user applications on a per-page basis[C]//Proceedings of the fourth ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments. Seattle, WA, USA:ACM, 2008:71-80. |
| [9] | Chen X, Garfinkel T, Lewis E C, et al. Overshadow:A virtualization-based approach to retrofitting protection in commodity operating systems[C]//Proceedings of the 13th International Conference on Architectural Support for Programming Languages and Operating Systems. Seattle, WA, USA:ACM, 2008:2-13. |
| [10] | Dalton M, Kannan H, Kozyrakis C. Raksha:A flexible information flow architecture for software security[C]//Proceedings of the 34th Annual International Symposium on Computer Architecture. San Diego, CA, USA:ACM, 2007:482-493. |
| [11] | Chen Y Y, Jamkhedkar P A, Lee R B. A software-hardware architecture for self-protecting data[C]//Proceedings of the 2012 ACM Conference on Computer and Communications Security. Raleigh, NC, USA:ACM, 2012:14-27. |
| [12] | Champagne D, Lee R B. Scalable architectural support for trusted software[C]//Proceedings of the 16th IEEE International Symposium on High-Performance Computer Architecture. Bangalore, India:IEEE Press, 2010:31-42. |
| [13] | McCune J M, Li Y, Qu N, et al. TrustVisor:Efficient TCB reduction and attestation[C]//Proceedings of the IEEE Security and Privacy. Oakland, CA, USA:IEEE Press, 2010:143-158. |
| [14] | Bae C S, Lange J R, Dinda P A. Enhancing virtualized application performance through dynamic adaptive paging mode selection[C]//Proceedings of the 8th ACM International Conference on Autonomic Computing. Karlsruhe, Germany:ACM, 2011:255-264. |