CN107395457B

CN107395457B - 基于排队模型的空间dtn网络链路可用带宽估计方法及系统

Info

Publication number: CN107395457B
Application number: CN201710601063.6A
Authority: CN
Inventors: 杨志华; 廖小丽; 李悦
Original assignee: Harbin Institute of Technology Shenzhen
Current assignee: Harbin Institute of Technology Shenzhen
Priority date: 2017-07-21
Filing date: 2017-07-21
Publication date: 2020-12-22
Anticipated expiration: 2037-07-21
Also published as: CN107395457A

Abstract

本发明公开了一种基于排队模型的空间DTN网络链路可用带宽估计方法及系统，本发明通过在空间DTN网络链路上发送探测包收集时延信息，分析bundle的传输过程和交付时延，并应用排队论知识对bundle的到达离开过程建立M/D/1排队模型，推导出bundle的逗留时间和网络流量的关系式，对空间DTN网络中链路可用带宽进行估计。最后，采用蒙特卡罗方法在MATLAB平台上进行仿真实验。实验结果表明，本发明提出的算法能够较准确的估计出空间DTN网络中链路的可用带宽，为QoS服务提供数据指导。

Description

基于排队模型的空间DTN网络链路可用带宽估计方法及系统

技术领域

本发明涉及空间DTN网络技术领域，尤其涉及一种基于排队模型的空间 DTN网络链路可用带宽估计方法及系统。

背景技术

在空间网络中，由于节点的运动，网络拓扑结构动态变化，且具有长时延、高误码率和间歇性连接等特性，因此，传统的基于端到端连接的TCP/IP 协议在空间网络数据传输服务中无法表现出优良的性能。为克服这一问题，空间网络采用容断网络架构(DTN,Disruption-tolerant Networking Architecture) 进行数据传输。DTN通过在传输层或其他底层上引入覆盖层(Bundle Layer, BP)为潜在的异构网络提供数据传输服务，BP层通过汇聚层适配器 (Convergence Layer Adapters,CLAs)接入下层协议，其主要协议包括覆盖层的BP协议及汇聚层的LTP协议。DTN采用存储-转发机制对数据进行逐跳转发，以解决空间网络中链路间歇性连接问题，保证数据的可靠传输。当进行数据传输时，应用数据单元将作为负载封装到BP层的bundle中传输至汇聚层，然后作为一个LTP块被划分为多个segments。这些segments经底层协议处理后将以链路帧的形式发送到下一跳节点协议栈。在这一传输过程中，底层协议的检测功能和LTP的快速自动重传机制确保了bundle的可靠交付。经过逐跳的转发，bundle将被目的节点接收，随后，其所携带的应用数据将被恢复并交付给对应的上层应用。

对于可用带宽的测量，关于TCP/IP网络，有很多关于可用带宽测量的研究，主要可分两类：一是主动测量，二是被动测量。主动测量是通过向网络发送探测数据包，收集相关的信息来推测带宽的情况；被动测量，不向网络发送探测包，而是通过设置监听点监听网络中的流量来测量网络的带宽。

其中，主动测量又可分为包间隔模型(PGM)、包速率模型(PRM)和网络流量模型三种。PGM模型的测量前提是已知待测链路的容量C，然后源端以一定格式向接收端发送多个探测包对，利用探测包对的输入和输出间隔数据估计网络的可用带宽，基于PGM模型的测量方法有Spruce、IGI和基于前两者的各种改进办法。PRM模型是利用自导拥塞思想进行可用带宽测量，即通过调整探测包的发送速率找到时延响应曲线的转折点来估计可用带宽，由PRM模型得到的测量方法有Pathload、Pathchirp、TOPP和相应的各种改进的方法。而网络流量模型是通过建立网络流量模型来估计的，但是建立准确的网络流量具有很大的难度，现今有基于网络流量模型的测量技术利用多分形小波模型MWM(Multiracial WaveletModel)能很好地反映出流量分形特性的特点，通过流量模型来估算在一定的时间范围内路径中的背景流量，以此得到可用带宽。

对于空间网络中可用带宽估计的研究很少，这些研究也是利用主动探测的方法根据包间隔或者探测包的时延统计信息进行可用带宽的估计的。据调研显示，还没有针对空间DTN网络中可用带宽估计的研究。

如前所述，目前已有技术都是针对TCP/IP网络进行研究的。而TCP/IP 协议和DTN中BP/LTP协议有着很大的区别：一两者的传输机制不一样， BP/LTP是逐跳转发的，不同于TCP/IP的端到端传输；二两者的应用场景不一样。将已有技术直接应用于DTN网络测量结果准确性会下降，况且现有可用带宽测量技术本身也存在一些问题：

1.主动测量

主动测量要向网络中发送探测包，这会增加网络潜在的负载，影响测量结果的准确性。其中，基于PGM模型和PRM模型的技术较为成熟，它们有三个共同的前提：一是待测链路上所有路由节点都是先进先出；二是网络中的业务流量处于稳定状态；三是业务流量的平均速率变化较慢，在一个测量周期保持恒定。然而，网络中的流量并不总是处于稳定状态，具有突发性。另外，对于PGM模型，当包对在同一队列排队时，输入包间隔才能很好的反映网络中业务流量的情况，当包对不在同一队列排队时，就可能出现输出包间隔被压缩/拉长等失真情况，进而导致估计结果偏小/大。对于PRM模型，由于其在测量过程中需要不断调整探测包的发送速率去逼近，这会引入大量的探测包，且探测时间较长，进而会对网络造成拥塞。而对于基于网络流量模型的技术，最大的难点就在于建立准确的数学模型去描述网络流量的特性。

2.被动测量

被动测量，不需要向网络中引入探测流量，因此不会增加网络的负载，但是由于其在监听时可能涉及比较敏感的用户信息，会影响到用户信息的安全性和保密性。为了安全和保密的需要，一般网络服务提供商不会允许在网络内部随便设监测点，因此其使用范围受限。

发明内容

本发明提供一种可准确估计空间DTN网络中链路可用带宽的基于排队模型的空间DTN网络链路可用带宽估计方法及系统。

为实现上述目的，本发明提供的一种基于排队模型的空间DTN网络链路可用带宽估计方法，包括以下步骤：

在空间DTN网络链路上发送探测包收集时延信息；

根据收集的时延信息，以及预先创建的排队模型估计所述空间DTN网络链路的可用带宽，其中，所述排队模型包括利用排队论分析推导得到的网络流量和bundle交付时延的关系。

其中，所述在空间DTN网络链路上发送探测包收集时延信息的步骤之后还包括：

根据收集的时延信息，分析bundle的传输过程和交付时延，并应用排队论知识对bundle的到达离开过程建立M/D/1排队模型，推导出bundle的逗留时间和网络流量的关系式。

其中，所述根据收集的时延信息，以及预先创建的排队模型估计所述空间DTN网络链路的可用带宽的步骤包括：

根据收集的时延信息以及预先创建的排队模型估计所述空间DTN网络链路的网络流量；

根据估计的网络流量以及预设的可用带宽估计算法计算得到所述空间 DTN网络链路的可用带宽。

其中，所述在空间DTN网络链路上发送探测包收集时延信息的步骤包括：

通过随机填充比特生成长度为L_b的探测bundle序列；

在空间DTN网络链路上以包间隔为g_i发送探测bundle，即发送速率为 R_s＝L_b/g_i；发送节点收到来自下一节点的确认信息，则根据确认信息计算相应的bundle交付时延和传播时延，得到交付时延集合{T_B(i)}和传播时延集合 {T_pro(i)}，并求平均得到avg_T_B和avg_T_pro，同时统计P_seg。

其中，所述方法还包括：

对所述可用带宽估计算法进行仿真验证。

本发明还提出一种基于排队模型的空间DTN网络链路可用带宽估计系统，其特征在于，包括存储器、处理器以及存储在所述存储器上的计算机程序，所述计算机程序被所述处理器运行时实现如如上所述的方法的步骤。

本发明的有益效果为：

本发明通过在空间DTN网络链路上发送探测包收集时延信息，分析 bundle的传输过程和交付时延，并应用排队论知识对bundle的到达离开过程建立M/D/1排队模型，推导出bundle的逗留时间和网络流量的关系式，对空间DTN网络中链路可用带宽进行估计。最后，采用蒙特卡罗方法在MATLAB 平台上进行仿真实验。实验结果表明，本发明提出的算法能够较准确的估计出空间DTN网络中链路的可用带宽，为QoS服务提供数据指导。

附图说明

图1是本发明基于排队模型的空间DTN网络链路可用带宽估计方法流程示意图；

图2a是空间DTN网络中的单跳链路示意图；

图2b是单跳链路上bundle的传输过程示意图；

图3是Bundle在DTN节点中的排队过程示意图；

图4是本发明探测过程示意图；

图5是Bundle基本块的格式与bundle处理控制标识符结构示意图；

图6是网络流量的估计值和仿真值的比较及相应的估计误差示意图；

图7是网络流量/可用带宽的估计值和仿真值的比较示意图；

图8是不同条件下的仿真结果示意图。

本发明目的的实现、功能特点及优点将结合实施例，参照附图做进一步说明。

具体实施方式

应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

本发明考虑到：空间网络具有长时延、高误码率和间歇性连接等特性，这给可用带宽的估计带来了极大的挑战。而据前期调研显示，当前的研究都是关于TCP/IP网络中可用带宽的估计，其中极少是关注于空间(卫星)网络的。为了实现空间DTN网络中链路可用带宽的估计，本发明分析了bundle 的传输过程和交付时延，并应用了排队论知识对bundle的到达离开过程建立 M/D/1排队模型，推导出bundle的逗留时间和网络流量的关系式。最后，采用蒙特卡罗方法在MATLAB平台上进行仿真实验。实验结果表明，本发明提出的算法能够较准确的估计出空间DTN网络中链路的可用带宽，为QoS服务提供数据指导。

具体地，如图1所示，本发明提出一种基于排队模型的空间DTN网络链路可用带宽估计方法，包括：

步骤S1，在空间DTN网络链路上发送探测包收集时延信息；

本发明中，根据收集的时延信息，分析bundle的传输过程和交付时延，并应用排队论知识对bundle的到达离开过程建立M/D/1排队模型，推导出 bundle的逗留时间和网络流量的关系式。

其中，在空间DTN网络链路上发送探测包收集时延信息包括：

通过随机填充比特生成长度为L_b的探测bundle序列；

后续，即可根据上述参数估计所述空间DTN网络链路的可用带宽。

步骤S2，根据收集的时延信息，以及预先创建的排队模型估计所述空间DTN网络链路的可用带宽，其中，所述排队模型包括利用排队论分析推导得到的网络流量和bundle交付时延的关系。

具体地，根据收集的时延信息以及预先创建的排队模型估计所述空间 DTN网络链路的网络流量；

进一步地，本发明所述方法还包括：

步骤S3，对所述可用带宽估计算法进行仿真验证。

本发明通过上述方案，在空间DTN网络链路上发送探测包收集时延信息，分析bundle的传输过程和交付时延，并应用排队论知识对bundle的到达离开过程建立M/D/1排队模型，推导出bundle的逗留时间和网络流量的关系式，对空间DTN网络中链路可用带宽进行估计。最后，采用蒙特卡罗方法在 MATLAB平台上进行仿真实验。实验结果表明，本发明提出的算法能够较准确的估计出空间DTN网络中链路的可用带宽，为QoS服务提供数据指导。

以下对本发明实施例方案进行详细阐述：

1、数学建模

本发明是研究空间DTN网络中链路可用带宽的估计。这里，可用带宽的含义和大多数研究中的含义一样，指在不影响链路中当前业务流量(也称为网络流量，networktraffic)的情况下链路还能提供的最大传输速率。可用带宽的大小主要受链路容量和时变的网络流量的影响，对于于一条链路的可用带宽可表示为：

ab＝(1-u)·R＝R-NTraffic (1)

其中，R表示链路容量，u∈[0,1]表示在一段时间内的链路平均利用率，而NTraffic指在一段时间内链路中的平均网络流量。因此，链路可用带宽估计的问题可以转换为链路中网络流量的估计。又在空间DTN网络中链路上的网络流量大小情况在一定程度上体现为bundle交付时延的变化，故本发明将利用排队论来研究网络流量和bundle交付时延的关系，进而提出可用带宽估计算法。如图2a所示，为空间DTN网络中的单跳链路(图中束层就是覆盖层)。于BP/LTP协议，托管传输机制使得bundle在束层排队，且会在节点的永久性存储空间中保存相应bundle的副本直到该bundle被成功传输至下一个节点。一个bundle向下传输时会在LTP层被分成多个segments，又LTP协议的快速自动重传机制决定了bundle的服务过程。下面，将分别讨论bundle的交付时延和bundle在束层的排队过程。

1.1Bundle的交付时延

Bundle在单跳链路上的传输过程如图2b所示。一般地，bundle的交付时延TB可表示为：

T_B＝TBD+TTF+T_queue+T_random (2)

其中，TBD表示bundle正确且完整地传输到下一跳节点的时间，如图 2b中所示，bundle在LTP层被分封为多个segment，则其第一个segment到最后一个segment均被正确传输至下一节点时表示一个bundle被正确传输至下一跳节点。LTP协议的自动快速重传机制使得在传输过程中出现差错的 segment会被快速恢复。那么，TBD可表示为所有segment成功传输到下一节点的平均传输时间加上传播时延，即

E(N)表示一个segment传输成功的平均传输次数。令P_seg表示segment 的丢包率时，E(N)可表示为：

其中P_seg＝1-(1-P_e)^Lseg+Lshead。对于公式(2)中的TTF表示最终的确认信息的传输时间，表示为：

公式(3-5)中主要参数的定义如表1所示。

表格1.参数定义

此外，公式(2)中的T_queue指bundle在队列里等待的时间，即排队时延，其主要取决于bundle的到达速率和链路容量。T_random为随机延时由网络环境中的随机扰动引起。将式子(3)、式子(4)和式子(5)代入式子(2)得

1.2 Bundle的排队模型

根据bundle交付时延的分析可知，bundle的交付时延中包含排队时延 Tqueue，且排队时延主要由bundle的到达速率和链路的容量决定。在DTN协议栈中，由于BP/LTP协议的传输机制，到达的bundle在束层排队等待接受服务，bundle离开队列接受服务的同时也会将其副本保存在节点的永久性存储空间，直到收到来自下一个节点保管确认才将其从永久性存储空间释放。而bundle接受服务的过程主要由LTP层决定(LTP协议实现可靠传输)。图3示意了bundle到达和离去的过程。

为了更好的描述bundle的排队过程，本发明做如下两点假设：

1)假设所有bundle优先级一致，bundle大小一致，且排队规则为先进先出FIFO，则当bundle到达队列时，如果队列为空，bundle将无需等待直接接受服务，否则，bundle在队列中等待其前面的bundle离开队列，这个时间称为排队时延或等待时间；

2)为了不是一般性，假设bundle的到达过程服从参数为λ的泊松分布。另外，在一个观测周期(秒级)内空间链路的变化很小，bundle的接受服务的时间可以认为是一常数τ。因此，这里将bundle的排队过程用M/D/1模型来描述。

根据排队论知识，对于M/D/1排队模型，其在系统的逗留时间的概率密度函数的拉普拉斯变换为：

w(s)＝(1-ρ)·s·B(s)/(s-λ+λ·B(s)) (7)

其中ρ＝λ·τ,B(s)是服务时间概率密度函数的拉普拉斯变换。这里，服务时间为一常数τ，则

对式(8)进行二阶泰勒展开，并代入式(7)得

根据最大似然估计，可得λ的似然函数为

其中

表示逗留时间序列{t_i}的平均值。又令dL(λ)/dλ＝0,可得λ的估计值关于

和τ的表达式为：

同样的，可得

关于λ和τ的表达式为：

根据上面的分析，得到了一个时间段内bundle的平均逗留时间的数学表达式。由此，可以建立一段时间内bundle平均交付时延关于平均网络流量的关系。假设一段时间内，成功传输n个bundle，那么根据式(6)和式(12) 有：

其中

表示随机扰动时延和模型误差。

2.算法设计

本发明提出了基于主动测量的链路可用带宽估计算法，即通过向网络中引入合适的探测包序列以收集链路相关信息，然后根据式(13)和(11)去估计网络流量，最后通过式(1)得到链路可用带宽的估计。图4为探测包探测过程示意图，探测时为了尽可能不影响原来网络流量的泊松性质，引入的探测包序列为确定性的。下面，将给出探测包的格式设计和算法具体描述以及相关伪代码。

A.探测包格式设计

一个bundle至少由两个块结构组成，第一个是基本块(primary Bundle block)，且每个Bundle有且只有一个基本块；其它类型的Bundle协议块跟随在基本块之后，支持对Bundle协议的扩展，例如Bundle安全协议；序列中至多有一个载荷块。而bundle的基本块包含了bundle数据传递所需要的链路节点标识符、处理控制标识符和字典序列等重要信息。bundle基本块的结构如图5所示。

由图5可知，bundle基本块包含了bundle的绝大部分传递所需信息。特别地，Bundle的处理控制标识符描述了bundle的一般属性、服务类型和状态报告请求状态，每一比特位都约束着某些能够用来对Bundle进行的操作。图 5中也给出了bundle处理控制标识符的具体格式。一般来说，bundle的处理控制标识有20个比特位(可扩展)，其中0-6位置的比特位描述了bundle的一般属性；7-13位置的比特位表示bundle的服务类型；14-20位置的比特位为状态报告请求标识符，每一位置的比特请求不同的Bundle处理报告。而在这 20个比特位中，位置6、9-13和19-20作为保留位，因此，选择6位置的比特位作为探测包标识符，当该比特位为1时表示为探测包，否则，表示为普通的bundle。另外，对于探测包，要求位置14的比特位为1，即请求报告bundle 的接收状态，以便于收集信息。

B.算法描述

根据前面的分析，算法的核心是利用式子(13)进行链路中总流量的估计，从而得到链路可用带宽的估计。因此，算法主要分为前期和后期两部分，前期为通过发送探测包序列收集时延信息，后期是利用收集的时延信息去估计可用带宽。其中，前期具体流程为：通过随机填充比特生成长度为L_b的探测bundle序列；以包间隔为g_i发送探测bundle，即发送速率为R_s＝L_b/g_i；发送节点收到来自下一节点的确认信息，则根据确认信息计算相应的bundle交付时延和传播时延，得到交付时延集合{T_B(i)}和传播时延集合{T_pro(i)}，并求平均得到avg_T_B和avg_T_pro，同时统计P_seg。后期，则将前期所得数据代入式 (13)和式NTtraffic＝λ′·L_b-R_s求得相应的估计值。核心算法伪代码如表格II 所示。

表格II.可用带宽估计算法伪代码

3.实验结果

由于GEO卫星和地球同步运行且具有很宽的覆盖率，因此常作为骨干节点，而LEO卫星离地面较近，其运行周期短，常作为数据传输的接入节点。因此，在实验仿真中以LEO-GEO链路为例，且令LEO卫星位于500km高的轨道，倾角45°。通过STK卫星仿真工具得到LEO-GEO链路距离的时变数据，并用于仿真实验中。至于链路上的误码率，初始为1e-6，之后随距离的变化而发生相应的变化。而参数L_seg、L_shead、L_RA和R分别设置为1480bytes、20bytes、70bytes和2Mbps。

采用蒙特卡罗方法在MATLAB平台上进行仿真实验。在给定条件(a)Lb 等于30Kbytes b)逗留时间的方差为1e-4c)一次探测收集30个bundle的时延信息)下，仿真实验结果分别如图6和图7所示。图6是网络流量的估计值和仿真值的比较及相应的估计误差((1)、(2)为lambda＝5bundles/s条件下的仿真结果，(3)、(4)为lambda＝7bundles/s条件下的仿真结果)。

实验结果显示，在很大程度上运用本算法得到的估计值都很接近于仿真值。特别地，对于每一次仿真中开始几次得到的估计值均较小，这是因为在仿真生成泊松流时开始时刻的流都会较小。另外，本算法中对链路可用带宽的估计误差与网络流量的估计误差一致，如图7中(1)和(2)所示，这是由式子 (1)所致。

图7是网络流量/可用带宽的估计值和仿真值的比较。

为了进一步验证算法的可行性，本发明进行了不同条件下多次仿真实验。图8(1)为不同bundle大小条件下的多次仿真结果，其结果显示bundle较大时估计结果相对稳定些。图8(2)为逗留时间方差不同的条件下的多次仿真结果，其结果显示方差大估计结果的波动也相对大些。然而，从实验结果中，还是可以得出结论：整体来说，本算法在多种不同参数条件下都能够较为准确的估计出链路的可用带宽，且估计误差基本能控制在10％以内，即估计值＝真实值 *(1±0.1)。

由上述可知，空间网络具有长时延、高误码率和间歇性连接等特性，这给可用带宽的估计带来了极大的挑战。而据前期调研显示，当前的研究都是关于TCP/IP网络中可用带宽的估计，其中极少是关注于空间(卫星)网络的。为了实现空间DTN网络中链路可用带宽的估计，本发明分析了bundle的传输过程和交付时延，并应用了排队论知识对bundle的到达离开过程建立M/D/1 排队模型，推导出bundle的逗留时间和网络流量的关系式。最后，采用蒙特卡罗方法在MATLAB平台上进行仿真实验。实验结果表明，本发明提出的算法能够较准确的估计出空间DTN网络中链路的可用带宽。

此外，本发明还提出一种基于排队模型的空间DTN网络链路可用带宽估计系统，包括存储器、处理器以及存储在所述存储器上的计算机程序，所述计算机程序被所述处理器运行时实现如上所述的方法的步骤，在此不再赘述。

此外，本发明还提出一种计算机可读存储介质，该计算机可读存储介质存储有计算机程序，所述计算机程序被处理器运行时实现如上所述的方法的步骤，在此不再赘述。

以上所述仅为本发明的优选实施例，并非因此限制本发明的专利范围，凡是利用本发明说明书及附图内容所作的等效结构或流程变换，或直接或间接运用在其它相关的技术领域，均同理包括在本发明的专利保护范围内。

Claims

1.一种基于排队模型的空间DTN网络链路可用带宽估计方法，其特征在于，包括以下步骤：

在空间DTN网络链路上发送探测包收集时延信息；

根据收集的时延信息，以及预先创建的排队模型估计所述空间DTN网络链路的可用带宽，其中，所述排队模型包括利用排队论分析推导得到的网络流量和bundle交付时延的关系；

所述在空间DTN网络链路上发送探测包收集时延信息的步骤包括：

通过随机填充比特生成长度为L_b的探测bundle序列；

在空间DTN网络链路上以包间隔为g_i发送探测bundle，即发送速率为R_s＝L_b/g_i；发送节点收到来自下一节点的确认信息，则根据确认信息计算相应的bundle交付时延和传播时延，得到交付时延集合

和传播时延集合{T_pro(i)}，并求平均得到

和

同时统计P_seg，P_seg为一个数据片段的丢包率；

所述根据收集的时延信息，以及预先创建的排队模型估计所述空间DTN网络链路的可用带宽的步骤包括：

根据式

和式NTtraffic＝λ′·L_b-R_s求得相应的网络流量的估计值，并根据式ab＝(1-u)·R＝R-NTraffic估计链路的可用带宽；

其中，n为连续成功传输的bundle的数量，λ为bundle到达节点时所服从的泊松分布的平均速率，λ′为λ的估计值，λ的估计值关于t和τ的表达式为：

关于λ和τ的表达式为：

其中，τ为常数，定义为一个测量周期内的系统服务时间；t表示逗留时间序列{t_i}的平均值；μ为系统服务时间的倒数；L_ACK是反馈链路上的确认包的尺寸；R_s是探测bundle的发送速率，R_s＝L_b/g_i；

其中，

表示随机扰动时延和模型误差，NTraffic指在一段时间内链路中的平均网络流量，ab表示链路的可用带宽，R表示链路容量，u∈[0,1]表示在一段时间内的链路平均利用率，L_b为一个bundle的长度，也是以bundle作为单位所衡量出的链路传输容量。

2.根据权利要求1所述的基于排队模型的空间DTN网络链路可用带宽估计方法，其特征在于，所述方法还包括：

对所述可用带宽估计算法进行仿真验证。

3.一种基于排队模型的空间DTN网络链路可用带宽估计系统，其特征在于，包括存储器、处理器以及存储在所述存储器上的计算机程序，所述计算机程序被所述处理器运行时实现如权利要求1-2中任一项所述的方法的步骤。