算法实现中的数据包信息交换流程

从算法分析可知，数据包交换与调度（data packet switching and sorting，DPSS）算法需要解决如下问题：

①数据包丢弃记录。在拓扑结构中，如何标识丢弃的数据包，才能确保该数据包的全局唯一性？

②数据包信息交换。什么情况下进行数据包信息交换，采用什么方式进行？

③数据包排序与编码。根据获取的缓存数据包ID，如何进行数据包的排序与编码？

本节从上述三个问题出发，详细论述基于DPSS算法的网络编码缓存策略实现过程。

3.4.2.1　数据包丢弃记录

为了确定数据包的来源，必须在X型网络结构中采用全局唯一的标识ID来表示数据包。本章采用二元组的方式进行数据包定义，形式上表现为{源ID，消息ID}，源ID表示发送节点的编号，消息ID表示为每个发送消息设置的序列号。

在编码队列缓存满的情况下，对于新获得的数据包，算法采用预丢弃但在目的节点记录该数据包ID的策略。主要思想是对于新获得的数据包，目的节点先记录该数据包ID，然后对该数据包进行丢弃处理。具体过程如下：

①假定一段时间T内，源节点SA需发送N个数据包给中继节点R，目的节点DB先后成功获得源节点SA发送的数据包P1，P2，…，PN，由于缓存的大小只有D个数据包大小，节点根据先后到达顺序将D个数据包存储在缓存内，假如缓存内存储的数据包为P1，P2，…，PD；

②在有保障的获得条件下，对于接下来获得的数据包，目的节点DB记录下这些数据包的ID，并保存在向量V中，同时对这些数据包进行丢弃处理。

3.4.2.2　数据包信息交换

数据包信息交换采用的是请求-应答方式，包括目的节点向源节点获取丢弃数据包和编码节点向目的节点获取缓存数据包信息两个过程。考虑到无线网络信号干扰的特性，节点之间的信息交互采用异步方式，节点内部的数据交互和处理采用并发方式。以目的节点向源节点获取丢弃数据包为例，具体步骤如下：

①在缓存出现空闲位置的时候，比较空闲的缓存容量Ns和丢弃数据包记录V中元素个数|V|的大小。若Ns＜|V|，则从V中选取Ns个数据包ID；否则，根据V中所有数据包ID，向源节点发起获取数据包请求。(www.xing528.com)

②源节点根据该请求，从维护的节点数据队列内取出相应的数据包集合Is，并将该集合内的数据包发给目的节点。

③目的节点将收到的数据包集合ID与请求数据包ID进行比较，确保收到的数据包和请求数据包一致；若不一致，则将不一致的数据包重新发给源节点，返回步骤①。

④目的节点将收到的数据包加入缓存内空闲位置，并进入下一轮编码数据包的接收和解码。

3.4.2.3 数据包排序与编码

编码节点R获取目的节点缓存内数据包ID，并根据获取到的数据包ID，重新组织编码队列内数据包。在本书的X型网络拓扑结构中，数据包重组与编码机制如下：

①节点R获取目的节点Di（i=1，2）中缓存队列里的数据包集合ID1，ID2。

②节点R从编码队列数据包集合R0里选出属于ID1或ID2的数据包集合R1，2。

③将R1，2内来自不同流或者源节点的数据包两两配对，将配对好的数据包从编码队列头位置开始置于队列内。若R1，2为奇数，将最后配对剩余的数据包置于配对好的数据包序列之后，并记录队列内数据包序号Rn；否则，记录插入队列内最后一个数据包序号Rn。

④将R0内剩余的数据包按照不同的来源两两组对加入编码队列内。

⑤将编码队列内序号Rn之前的数据包两两之间采用异或操作进行编码，形成新的数据包，并将其发送至目的节点。

⑥进入下一轮数据包编码。