一种支持网络编码的无源光网络吞吐量提高方法

技术领域

本发明涉及一种支持网络编码的无源光网络吞吐量提高方法，属于光纤接入网络领 域。

背景技术

现今，随着网络运营商光纤到户架构的广泛部署，无源光网络成为了构建下一代光纤 接入网络以满足用户各种高带宽应用的关键基础设施。

无源光网络通过光分裂器将一个光线路终端连接至多个光网络单元，实现点到多点的 连接。基于这样的结构，无源光网络上光网络单元之间的通信实现方式是：首先源光网络 单元通过共享的上行带宽将数据传输至光线路终端，接着再由光线路终端将收到的数据广 播至所有的光网络单元，最后目的光网络单元接收所收到的数据，而其它光网络单元则将 收到的数据丢弃。

由于各种实际应用，如p2p文件共享、蜂窝网络和智能电网等的逐步出现，光网络单 元之间的通信量日益增多。为了有效的提高无源光网络上的吞吐量，基于网络编码技术的 光网络单元之间的通信方式得到了人们的普遍青睐。

在网络编码方式下，如图1所示，光线路终端不再是简单的转发数据，而是将从两个 互为目的光网络单元的源光网络单元发出的数据包进行编码后发送。源光网络单元在收到 编码包后可以利用自己产生的数据包去解码编码包，进而获得数据。通过一次编码包的传 输代替原来的两次原始数据包的传输，可以有效的提高系统吞吐量。但由于这种方式需要 等待编码条件的形成(也即须有两个光网络单元向彼此发送数据时才可以进行编码)，系 统吞吐量的提升会受到一定的限制。为了突破吞吐量提升的瓶颈，需要对光网络单元内部 的数据进行整体调度，尽可能多的产生可编码的数据流，从而提高基于网络编码技术的无 源光网络上的吞吐量。

发明内容

针对上述技术问题，本发明所要解决的技术问题是提供一种支持网络编码的无源光网 络吞吐量提高方法，针对光网络单元内部的待传送数据分布情况进行整体调度，使得各个 光网络单元传递至光线路终端处的数据能够尽可能多的被编码，进而实现无源光网络吞吐 量增益的最大化。

本发明为了解决上述技术问题采用以下技术方案：本发明设计了一种支持网络编码的 无源光网络吞吐量提高方法，其中，无源光网络包括光分裂器、光线路终端和N个光网络 单元，N≥2，光线路终端经光分裂器分别与各个光网络单元相连接；所述无源光网络吞 吐量提高方法在一个上行数据传输周期开始时执行，包括如下步骤：

步骤001.分别针对N个光网络单元中的各个光网络单元，统计光网络单元所对应的 各个待选目的光网络单元，以及分别对应于各个待选目的光网络单元的待传送数据流的数 据大小，作为光网络单元的待传送数据分布情况，发送至光线路终端；其中，各个光网络 单元所分别对应各待选目的光网络单元的待传送数据流的数据大小均大于0；

步骤002.光线路终端针对来自N个光网络单元的待传送数据分布情况进行分析，判 断是否满足各个光网络单元所对应待选目的光网络单元数目均为N-1，且各待选目的光网 络单元的待传送数据流的数据大小均大于等于W_max，是则进入步骤003；否则判断是否满 足各个光网络单元分别所对应的各待选目的光网络单元均为其相邻光网络单元，是则进入 步骤004，否则进入步骤005；其中，W_max为无源光网络中预设的光网络单元在一个上行 数据传输周期中的最大数据传输量；

步骤003.光线路终端将N个光网络单元两两组合构成光网络单元对，然后各对光网 络单元中的两个光网络单元在上行数据传输周期中彼此相互传递大小为W_max的数据流汇 总至光线路终端，光线路终端再针对各对数据流进行网络编码后传回至对应的光网络单 元，实现无源光网络吞吐量增益的最大化；

步骤004.光线路终端基于解决二分图上最大带权匹配问题的Kuhn-Munkras算法， 针对N个光网络单元进行调度，在各个光网络单元分别所对应的待选目的光网络单元中， 调度确定各个光网络单元分别唯一对应的目的光网络单元，然后配对的各对光网络单元在 上行数据传输周期中互传数据以形成网络编码数据流，实现无源光网络吞吐量增益的最大 化；

步骤005.光线路终端基于最大边带权独立集算法，针对N个光网络单元进行调度， 在各个光网络单元分别所对应的待选目的光网络单元中，调度确定各个光网络单元分别唯 一对应的目的光网络单元，然后配对的各对光网络单元在上行数据传输周期中互传数据以 形成网络编码数据流，实现无源光网络吞吐量增益的最大化。

作为本发明的一种优选技术方案：所述无源光网络中，分别针对N个光网络单元中的 各个光网络单元，设置与之对应的N-1个数据缓冲区，用于存储该光网络单元分别向其余 N-1个光网络单元传输的待传送数据流；所述步骤001具体包括如下步骤：

步骤00101.分别针对N个光网络单元中的每个光网络单元，将光网络单元所对应的 N-1个数据缓冲区中，数据大小大于0的各个待传送数据流所对应的各个光网络单元，作 为该光网络单元的待选目的光网络单元；

步骤00102.分别针对N个光网络单元中的各个光网络单元，统计光网络单元所对应 的各个待选目的光网络单元，以及分别对应于各个待选目的光网络单元的待传送数据流的 数据大小，作为光网络单元的待传送数据分布情况，发送至光线路终端。

作为本发明的一种优选技术方案：所述步骤003包括如下步骤：

步骤00301.判断无源光网络中光网络单元的个数N是否为偶数，是则进入步骤 00302，否则进入步骤00303；

步骤00302.光线路终端针对N个光网络单元，任意调度组成对光网络单元，然后 各对光网络单元中的两个光网络单元在上行数据传输周期中彼此相互传递大小为W_max的 数据流汇总至光线路终端，光线路终端再针对各对数据流进行网络编码后传回至对应的光 网络单元，实现无源光网络吞吐量增益的最大化；

步骤00303.光线路终端针对N个光网络单元，任意调度组成对光网络单元， 并余留一个光网络单元，该光网络单元可以从其待选目的光网络单元中任选一个，并向其 发送数据，以避免轮空，然后各对光网络单元中的两个光网络单元在上行数据传输周期中 彼此相互传递大小为W_max的数据流汇总至光线路终端，光线路终端再针对各对数据流进行 网络编码后传回至对应的光网络单元，实现无源光网络吞吐量增益的最大化。

作为本发明的一种优选技术方案：所述步骤004包括如下步骤：

步骤00401.构建一个带权二分图BG＝(X,E,Y)，其中，X＝{u_i}和Y＝{v_i}均为顶点 集合，分别包括N个顶点，各顶点集合分别与无源光网络的顶点相对应，其中各顶点集合 中的各个顶点分别代表无源光网络N个顶点中的一个光网络单元，1≤i≤N；

步骤00402.根据各个光网络单元分别所对应的各待选目的光网络单元均为其相邻光 网络单元，获得彼此互有待传送数据流的各对互传光网络单元，在X顶点集合和Y顶点集 合之间连接各对互传光网络单元中两个光网络单元所对应的顶点，作为顶点之间的边，获 得边集合$E=\{e_i,e_j^{*}\},$其中e_i＝(u_2i-1,v_2i)，$1\le i\le \frac{N}{2},$$e_j^{*}=(v_{2j},u_{2j+1}),$$1\le j<\frac{N}{2};$同时，获 得并在顶点之间的边上标记所连接两顶点对应两个光网络单元之间，进行互传数据以形成 网络编码数据流所带来的吞吐量增益；

步骤00403.光线路终端基于解决二分图上最大带权匹配问题的Kuhn-Munkras算 法，求出带权二分图BG上的一个最大匹配集；

步骤00404.光线路终端根据得到的最大匹配集，调度该匹配集中每一条边的两个顶点所 分别对应的两个光网络单元，在上行数据传输周期中彼此相互传递数据以形成网络编码数 据流，实现无源光网络吞吐量增益的最大化；而对于没有配对成功的光网络单元，可从其 待选目的光网络单元中任选一个，并向其发送数据，以避免轮空。

作为本发明的一种优选技术方案：所述步骤005包括如下步骤：

步骤00501.构建一个无向带权图G，其中包括N个顶点，各个顶点分别代表一个光 网络单元；

步骤00502.针对各个光网络单元分别所对应的各个待选目的光网络单元，获得彼此 互有待传送数据流的各对互传光网络单元，并且在无向带权图G中分别连接各对互传光网 络单元中两个光网络单元所对应的顶点，同时，获得并在顶点连线上标记所连接两顶点对 应两个光网络单元之间，进行互传数据以形成网络编码数据流所带来的吞吐量增益；

步骤00503.光线路终端基于最大边带权独立集算法，求出无向带权图G上的一个最 大边带权独立集；

步骤00504.光线路终端根据得到的最大边带权独立集，调度该独立集中每一条边的 两个顶点所分别对应的两个光网络单元，在上行数据传输周期中彼此相互传递数据以形成 网络编码数据流，实现无源光网络吞吐量增益的最大化；而对于没有配对成功的光网络单 元，可从其待选目的光网络单元中任选一个，并向其发送数据，以避免轮空。

本发明所述一种支持网络编码的无源光网络吞吐量提高方法采用以上技术方案与现 有技术相比，具有以下技术效果：本发明设计的支持网络编码的无源光网络吞吐量提高方 法，根据光网络单元内部的待传送数据分布情况，提出了光线路终端上的数据传输调度策 略，该策略分别制定了三种不同数据分布情况下的具体调度方法，相较于传统的被动等待 模式，即每个光网络单元独立的进行内部调度，而光线路终端只能被动等待编码流的形成， 本发明设计的技术方案提出了光网络单元整体调度方案，通过主动促成编码流的形成，进 而能够显著提高无源光网络上的吞吐量，实现无源光网络吞吐量增益的最大化，对提升接 入网络的终端用户体验具有重要意义。

附图说明

图1是基于网络编码的光网络单元之间的通信示意图；

图2是本发明设计支持网络编码的无源光网络吞吐量提高方法与随机调度策略的吞吐量增 益对比示意图。

具体实施方式

下面结合说明书附图针对本发明的具体实施方式作进一步详细的说明。

本发明所设计支持网络编码的无源光网络吞吐量提高方法，为了实现无源光网络吞吐 量增益的最大化，所设计执行的调度方法，分为两个实施阶段：第一阶段，在一个上行传 输周期开始时，每个光网络单元先将自身内部的待传送数据分布情况，即需要传送至其它 光网络单元的待传送数据流汇报给光线路终端；第二阶段，光线路终端基于收到的所有光 网络单元汇报的信息做出整体调度，决定在该上行传输周期内每个光网络单元应该向哪个 目的光网络单元发送数据，以最大化可编码的数据包数目(在一个上行传输周期内，每个 光网络单元只能向一个目的光网络单元发送数据，每个光网络单元可以接收多个光网络单 元发送的数据)，进而提高无源光网络上的吞吐量增益。

本发明所设计的支持网络编码的无源光网络吞吐量提高方法，其中，无源光网络包括 光分裂器、光线路终端和N个光网络单元，N≥2，光线路终端经光分裂器分别与各个光 网络单元相连接，并且在无源光网络中，分别针对N个光网络单元中的各个光网络单元， 设置与之对应的N-1个数据缓冲区，用于存储该光网络单元分别向其余N-1个光网络单 元传输的待传送数据流；在实际应用过程当中，所述无源光网络吞吐量提高方法在一个上 行数据传输周期开始时执行，包括如下步骤：

步骤001.分别针对N个光网络单元中的各个光网络单元，统计光网络单元所对应的 各个待选目的光网络单元，以及分别对应于各个待选目的光网络单元的待传送数据流的数 据大小，作为光网络单元的待传送数据分布情况，发送至光线路终端；其中，各个光网络 单元所分别对应各待选目的光网络单元的待传送数据流的数据大小均大于0；上述步骤001 的操作具体可以分为如下两步骤：

步骤00101.分别针对N个光网络单元中的每个光网络单元，将光网络单元所对应的 N-1个数据缓冲区中，数据大小大于0的各个待传送数据流所对应的各个光网络单元，作 为该光网络单元的待选目的光网络单元。

步骤00102.分别针对N个光网络单元中的各个光网络单元，统计光网络单元所对应 的各个待选目的光网络单元，以及分别对应于各个待选目的光网络单元的待传送数据流的 数据大小，作为光网络单元的待传送数据分布情况，发送至光线路终端。

步骤002.光线路终端针对来自N个光网络单元的待传送数据分布情况进行分析，判 断是否满足各个光网络单元所对应待选目的光网络单元数目均为N-1，且各待选目的光网 络单元的待传送数据流的数据大小均大于等于W_max，是则进入步骤003；否则判断是否满 足各个光网络单元分别所对应的各待选目的光网络单元均为其相邻光网络单元，是则进入 步骤004，否则进入步骤005；其中，W_max为无源光网络中预设的光网络单元在一个上行 数据传输周期中的最大数据传输量；

步骤003.光线路终端将N个光网络单元两两组合构成光网络单元对，然后各对光网 络单元中的两个光网络单元在上行数据传输周期中彼此相互传递大小为W_max的数据流汇 总至光线路终端，光线路终端再针对各对数据流进行网络编码后传回至对应的光网络单 元，实现无源光网络吞吐量增益的最大化；上述步骤003的操作具体可以分为如下步骤执 行：

步骤00301.判断无源光网络中光网络单元的个数N是否为偶数，是则进入步骤 00302，否则进入步骤00303。

步骤00302.光线路终端针对N个光网络单元，任意调度组成对光网络单元，由于 无源光网络中预设的光网络单元在一个上行数据传输周期中的最大数据传输量为W_max，因 此，所获得的各对光网络单元中的两个光网络单元，在上行数据传输周期中彼此相互传递 大小为W_max的数据流汇总至光线路终端，光线路终端再针对各对数据流进行网络编码后传 回至对应的光网络单元，实现无源光网络吞吐量增益的最大化。

步骤00303.光线路终端针对N个光网络单元，任意调度组成对光网络单元， 并余留一个光网络单元，该光网络单元可以从其待选目的光网络单元中任选一个，并向其 发送数据，以避免轮空，然后各对光网络单元中的两个光网络单元在上行数据传输周期中 彼此相互传递大小为W_max的数据流汇总至光线路终端，光线路终端再针对各对数据流进行 网络编码后传回至对应的光网络单元，实现无源光网络吞吐量增益的最大化。

步骤004.光线路终端基于解决二分图上最大带权匹配问题的Kuhn-Munkras算法 (KM)，针对N个光网络单元进行调度，在各个光网络单元分别所对应的待选目的光网络 单元中，调度确定各个光网络单元分别唯一对应的目的光网络单元，然后配对的各对光网 络单元在上行数据传输周期中互传数据以形成网络编码数据流，实现无源光网络吞吐量增 益的最大化；上述步骤004的操作具体可以分为如下步骤执行：

步骤00401.构建一个带权二分图BG＝(X,E,Y)，其中，X＝{u_i}和Y＝{v_i}均为顶点 集合，分别包括N个顶点，各顶点集合分别与无源光网络的顶点相对应，其中各顶点集合 中的各个顶点分别代表无源光网络N个顶点中的一个光网络单元，1≤i≤N。

步骤00402.根据各个光网络单元分别所对应的各待选目的光网络单元均为其相邻光 网络单元，获得彼此互有待传送数据流的各对互传光网络单元，在X顶点集合和Y顶点集 合之间连接各对互传光网络单元中两个光网络单元所对应的顶点，作为顶点之间的边，获 得边集合$E=\{e_i,e_j^{*}\}$其中e_i＝(u_2i-1,v_2i)，$1\le i\le \frac{N}{2},$$e_j^{*}=(v_{2j},u_{2j+1}),$$1\le j<\frac{N}{2};$同时，获 得并在顶点之间的边上标记所连接两顶点对应两个光网络单元之间，进行互传数据以形成 网络编码数据流所带来的吞吐量增益，这里互传数据形成网络编码数据流所带来的吞吐量 增益可以通过如下公式(1)进行获得；

R_ij＝min{W_max,r_ij,r_ji}(1)

其中，R_ij表示光网络单元i与光网络单元j之间分别向彼此传递数据形成网络编码数 据流所带来的吞吐量增益，r_ij表示光网络单元i向光网络单元j传递的数据量，r_ji表示光网 络单元j向光网络单元i传递的数据量。

步骤00403.光线路终端基于解决二分图上最大带权匹配问题的Kuhn-Munkras算法 (KM)，求出带权二分图BG上的一个最大匹配集。

步骤00404.光线路终端根据得到的最大匹配集，调度该匹配集中每一条边的两个顶 点所分别对应的两个光网络单元，在上行数据传输周期中彼此相互传递数据以形成网络编 码数据流，实现无源光网络吞吐量增益的最大化，该最大化的吞吐量增益如下式(2)所 示；

$max\underset{i,j=1}{\overset{N}{\Sigma }}{c}_{ij}*c_{ji}*R_{ij}---\left(2\right)$

其中，c_ij＝1表示光线路终端调度光网络单元i向光网络单元j传递数据，反之c_ij＝0。

对于没有配对成功的光网络单元，可从其待选目的光网络单元中任选一个，并向其发 送数据，以避免轮空。

步骤005.光线路终端基于最大边带权独立集算法，针对N个光网络单元进行调度， 在各个光网络单元分别所对应的待选目的光网络单元中，调度确定各个光网络单元分别唯 一对应的目的光网络单元，然后配对的各对光网络单元在上行数据传输周期中互传数据以 形成网络编码数据流，实现无源光网络吞吐量增益的最大化；上述步骤005的操作具体可 以分为如下步骤执行：

步骤00501.构建一个无向带权图G，其中包括N个顶点，各个顶点分别代表一个光 网络单元。

步骤00502.针对各个光网络单元分别所对应的各个待选目的光网络单元，获得彼此 互有待传送数据流的各对互传光网络单元，并且在无向带权图G中分别连接各对互传光网 络单元中两个光网络单元所对应的顶点，同时，获得并在顶点连线上标记所连接两顶点对 应两个光网络单元之间，进行互传数据以形成网络编码数据流所带来的吞吐量增益，这里 互传数据以形成网络编码数据流所带来的吞吐量增益，同样可以根据上述公式(1)获得。

步骤00503.光线路终端基于最大边带权独立集算法，求出无向带权图G上的一个最 大边带权独立集。

步骤00504.光线路终端根据得到的最大边带权独立集，调度该独立集中每一条边的 两个顶点所分别对应的两个光网络单元，在上行数据传输周期中彼此相互传递数据以形成 网络编码数据流，实现无源光网络吞吐量增益的最大化，该最大化的吞吐量增益同样可以 有上述式(2)所示；对于没有配对成功的光网络单元，可从其待选目的光网络单元中任 选一个，并向其发送数据，以避免轮空。

上述技术方案所设计的支持网络编码的无源光网络吞吐量提高方法，根据光网络单元 内部的待传送数据分布情况，提出了光线路终端上的数据传输调度策略，该策略分别制定 了三种不同数据分布情况下的具体调度方法，相较于传统的被动等待模式，即每个光网络 单元独立的进行内部调度，而光线路终端只能被动等待编码流的形成，本发明设计的技术 方案提出了光网络单元整体调度方案，通过主动促成编码流的形成，进而能够显著提高无 源光网络上的吞吐量，实现无源光网络吞吐量增益的最大化，对提升接入网络的终端用户 体验具有重要意义。上述本发明所设计支持网络编码的无源光网络吞吐量提高方法，在实 际应用调度中，基于如下具体实施示例：无源光网络共包含16个光网络单元，分别到达 每个光网络单元的数据包服从泊松分布，且每个数据包的目的地均匀的分布在其它15个 光网络单元上，将吞吐量增益比定义为吞吐量增益除以网络中的负载，如图2所示，本发 明所设计调度策略所带来的网络吞吐量增益远远高于随机调度策略，且随着网络负载的增 加，这种优势愈发明显。

上面结合说明书附图针对本发明的实施方式作了详细说明，但是本发明并不限于上述 实施方式，在本领域普通技术人员所具备的知识范围内，还可以在不脱离本发明宗旨的前 提下做出各种变化。