基于输入交叉点缓存快速分组交换网络的流量控制方法

摘要

一种基于输入交叉点缓存快速分组交换网络的流量控制方法，操作方法是：每个输入端的输入数据包按照目的端地址被实时写入对应的输出虚拟队列VOQ；该输入端的输出调度模块根据调度规则从VOQ中实时读取数据包，并写入交换开关中的交叉点缓存器CP；然后，输出端的输出调度模块根据调度规则实时读取并发送与其对应的CP中的数据包，CP在其缓存的数据包发生变化时，向对应的输入端和输出端实时发送状态更新信息；输出端与输入端分别根据该状态更新信息，实时更新自身存储的状态值；同时，输入端和输出端的各自输出调度模块分别根据该更新后的状态值对数据包进行调度，完成相应数据包的传输。

说明书

技术领域

本发明涉及一种基于输入交叉点缓存快速分组交换网络的流量控制方法， 属于快速分组交换的技术领域。

背景技术

传统分组交换技术是在20世纪60年代末至70年代初研制成功的。当时所 用的传输媒质主要是铜线（包括同轴电缆和双绞线电缆），传输速率低，传输误 码率高，因而网络性能的瓶颈是传输链路，而不是交换机。

经过数十年的发展，链路的主要传输媒质已经变为光纤，其传输速率高达 几Gbits，传输误码率低到10^-9以下。网络性能的瓶颈不再是传输链路，而是节 点的交换机。这就驱使人们去研究快速分组交换技术。

快速分组交换的基本思路是简化分组交换机的协议处理，将复杂性推向网 络终端系统。实现快速分组交换的具体技术措施有如下几种：

（1）取消链路层的差错控制和流量控制，通过端到端的差错控制来解决极 少发生的差错。

（2）采用硬件实现分组转发和并行处理技术。

（3）采用固定长度的小分组。因为缩短分组长度有利于减小分组转发的时 延，尽管这样处理会引起单位时间内到达的分组数的增加，但是，其优点还是 主要的。采用固定长度的分组有利于分组交换机的硬件设计，便于安排从不同 的端口输入分组，并实行并行交换。

快速分组交换采用的交换网络的结构和数据包缓存器的设置是不可分割 的。设置缓存器的主要目的是解决输出冲突问题。快速分组交换的整个交换系 统由输入端、输出端和交换开关组成。

基于纵横式交换矩阵crossbar的交换网络结构组成按照缓存器的设置主要 分为：输入缓存IQ（Input Queued）、输出缓存OQ（Output Queued）、输入 输出缓存CIOQ（Combined Input and Output Queued）、交叉点缓存CQ（Crosspoint  Queued）和输入交叉点缓存CICQ（Combined Input and Crosspoint Queued）等。 其中，基于crossbar的输入交叉点缓存交换网络为现有技术。本发明流量控制 方法就是在基于crossbar的输入交叉点缓存交换网络的结构基础上提出的。

参见图1，介绍一种基于crossbar的输入交叉点缓存交换网络的结构组成： 该交换网络在输入端和交换开关的交叉点都设有缓存器。在每个输入端都设有 N个输出虚拟队列，分别对应的不同输出端，用于缓存发往相应输出端的数据 包。输入端的每个输出虚拟队列VOQ与各个交叉点缓存器CP是一一对应的。 例如，输入端1接收到发往输出端1的数据包，将其缓存于输出虚拟队列 VOQ11，通过输出调度模块1将该数据包写入与VOQ11对应的交叉点缓存器 CP11。再由输出端1中的输出调度模块将CP11中的数据包读取并发送。

图1所示的基于crossbar的输入交叉点缓存交换网络，也是本发明流量控 制方法的应用场景或基础。下面简要说明该分组交换网络的结构组成，其设有： 多个输入端、多个输出端和交换开关。其中：

N个输入端，用于完成输入数据包的缓存和数据包的输出调度。每个输入 端设有：N个输出虚拟队列VOQ，用于缓存输入数据包。一个输出调度模块， 用于接收交换开关发来的交叉点缓存器的状态信息，并根据输入端的输出虚拟 队列的缓存状态信息和交叉点缓存器的状态信息完成输入端输出虚拟队列的数 据包输出调度。

一个交换开关，用于完成数据包的缓存和交换。其中包括：交叉点缓存器， 用于缓存数据包，并监视各个交叉点缓存器的占用状态，向输入端和输出端分 别发送交叉点缓存状态更新信息；交换网络连接线，用于分别连接交叉点缓存 器和输入端与输出端。

N个输出端，根据交换网络发过来的交叉点缓存状态信息完成数据包的输出 调度，从交叉点缓存器中读取数据包，并向外转发。每个输出端都设有N个输 出虚拟队列与交换开关中的交叉点缓存器一一对应，且输出端的每个输出虚拟队 列中的数据包通过输出调度模块被写入交换开关中对应的交叉点缓存器。例如， 输入端1中的输出虚拟队列VOQ11对应的交换开关中的交叉点缓存器为CP11。

因为数据包都是等长的，因此，下述四个时间的时长相等：即输入端接收 一个数据包的时间、输入端向交叉点缓存器写入一个数据包的时间、输出端向 外发送一个数据包的时间、以及输出端从交叉点缓存器读取一个数据包的时间， 四者数值相同，且被称为一个时间槽。输入端通过输出调度模块在一个时间槽 只能向交叉点缓存器写入一个数据包，同样地，输出端在一个时隙也只能从交 叉点缓存读取一个数据包。

下面介绍快速分组交换的流量控制的发展现状：

快速分组交换的流量控制的目的是企图减少、甚至避免交换过程中丢失数 据包。目前采用的流量控制方法通常是基于输入输出缓存的交换网络，采用端 到端的流量控制方法，也就是通过在输入端与输出端之间传递流量控制信息来 进行输入端和输出端的数据包调度，从而减少或避免交换过程中丢失数据包。

目前，现有技术的流量控制方法主要有两种：

第一种方法（参见图2所示）：输出端根据输出端缓存器的状态独立决策， 向输入端发送流量控制信息，当输出端队列中的数据包数量超过设定的某个阈 值时，向输出端发送流量关闭或者减小数据流流量的流量控制信息，输入端收 到流量控制信息后，关闭或者减小流量控制信息指示的相应的数据流。相反地， 当输出端队列中的数据包数量设定的另一个阈值时，向输出端发送流量开启或 者增加数据流流量的流量控制信息，输入端收到流量控制信息后，开启或者增 加流量控制信息指示的相应的数据流。

第二种方法（参见图3所示）：是一种基于信任的流量控制方法，输入端向 输出端发送缓存状态信息，输出端根据输入端和输出端的缓存状态向输入端发 送流量控制令牌，输入端在获得令牌以后才能发送数据包。

当前的流量控制基本上都是基于输入输出缓存交换网络提出相应的流量控 制方法。迄今为止，尚未发现有专用于基于输入交叉点缓存交换网络的流量控 制方法。

发明内容

有鉴于此，本发明的目的是在现有的基于输入交叉点缓存快速分组交换网 络基础上，提供一种基于输入交叉点缓存快速分组交换网络的流量控制方法， 该方法能够减少甚至避免在快速分组交换过程中因为拥塞导致的数据包丢失。

为了达到上述目的，本发明提供了一种基于输入交叉点缓存快速分组交换 网络的流量控制方法，其特征在于：所述方法包括下列操作步骤：

（1）每个输入端的输入数据包按照目的端口地址被实时写入对应的输出虚 拟队列VOQ，等待被该输入端的输出调度模块读取；

（2）输入端的输出调度模块根据调度规则对输出虚拟队列VOQ中的数据包 进行调度，并从VOQ中实时读取数据包，再写入交换开关中的交叉点缓存器；

（3）输出端的输出调度模块根据调度规则实时读取并发送与其对应的交叉 点缓存器中的数据包；

（4）交叉点缓存器实时监测自身缓存的数据包数量，一旦发现该数据包数 量发生变化，立即向对应的输入端和输出端分别发送相应的缓存状态更新信息；

（5）输出端与输入端分别实时接收交叉点缓存器发送来的缓存状态更新信 息，并把与该缓存状态信息相对应的自身存储的状态值更新为接收到的缓存状 态更新信息中的当前缓存状态值；

（6）输入端和输出端的输出调度模块分别根据各自更新后的自身存储的状 态值对数据包进行调度，完成相应数据包的传输。

当前的流量控制方法都是在输入输出缓存交换网络的基础上提出的，本发 明流量控制方法的基础是输入交叉点缓存快速分组交换网络，是一种创新的流 量控制方法。本发明基于当前普遍应用的基于输入交叉点缓存快速分组交换网 络的流量控制方法优点是：操作步骤简单、实用，能够有效降低数据包的丢失 率，提高交换网络中交叉点缓存器的利用率，有利于推广普及。

附图说明

图1是本发明方法的应用场景：输入交叉点缓存快速分组交换网络的结构 组成及其操作方法示意图。

图2是第一种基于输入输出缓存的交换网络的流量控制方法示意图。

图3是第二种基于输入输出缓存的交换网络的流量控制方法示意图。

图4（A）、（B）是本发明网络中输入端的两个缓存状态存储器示意图。

图5是本发明网络中输出端缓存状态存储器示意图。

图6是本发明流量控制方法的操作步骤流程图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面结合附图对本发明作 进一步的详细描述。

参见图1和图6，介绍本发明基于输入交叉点缓存快速分组交换网络的 流量控制方法的下列具体操作步骤：

步骤1，每个输入端的输入数据包按照目的端口地址被实时写入对应的输出 虚拟队列VOQ，等待被该输入端的输出调度模块读取。

步骤2，输入端的输出调度模块根据调度规则对输出虚拟队列VOQ中的数 据包进行调度，并从VOQ中实时读取数据包，再写入交换开关中的交叉点缓存器。该步骤包括下述操作内容：

（21）每个输入端i的输出调度模块都设有两个存储器：一个为输出虚拟队 列状态存储器（参见图4（A）所示），用于存储该输入端的各个VOQ_ij的状态值， 即其已占用的缓存量h_j；而每个输出虚拟队列缓存器的缓存资源总量H_j是已知 的；另一个为输入端交叉点缓存状态存储器（参见图4（B）所示），用于存储 与该输入端对应的每个交叉点缓存器CP_ij的状态值，即其已占用的缓存量q_j，而 每个交叉点缓存器CP_ij的缓存资源总量Q_j是已知的；则输入端i中各个VOQ_ij的缓 存器的占用比例与输入端i对应的各个CP_ij的占用比例式中， 自然数i是输入端的序号，自然数j是输入端i中的VOQ和与该VOQ对应的交叉点 缓存器CP的序号，i和j的最大值均为N。

（22）输出调度模块根据步骤（21）中的两个存储器存储的状态值和设定 调度规则对数据包进行调度，并将其写入交换开关中的交叉点缓存器CP_ij。

该步骤的调度规则是：输入端i的输出调度模块首先检查其输入端交叉点缓 存状态存储器，并判断各个CP是否已经存满；

若CP_ij已满，即其对应的状态值q_j等于其缓存资源总量Q_j，则输入端i的输 出调度模块就暂停读取VOQ_ij中数据包；

若CP_ij不满，即其对应的状态值q_j小于其缓存资源总量Q_j，则输入端i的输 出调度模块就继续读取VOQ_ij中数据包；

然后，输入端i的输出调度模块检查每个VOQ缓存器的占用比例η_j，从未被 暂停读取的VOQ中选择占用比例最大的VOQ，从中读取数据包，并写入交换开 关中的交叉点缓存器。

步骤3，输出端的输出调度模块根据调度规则实时读取并发送与其对应的 交叉点缓存器中的数据包。该步骤包括下述操作内容：因每个输出端k都设有 输出端交叉点缓存状态存储器（参见图5所示），，用于存储该输出端k对应的 各个交叉点缓存器CP_bk的状态值，即其已占用的缓存量m_b；而每个交叉点缓存 器CP_bk的缓存资源总量M_b是已知的，故每个交叉点缓存器CP_bk的占用比例 式中，自然数k和b分别是输出端序号和该输出端ｋ所对应的交叉点 缓存器的序号，k和b的最大值均为N；然后，该输出端ｋ的输出调度模块选 择占用比例最大的CP中的数据包读取并发送。

步骤4，交叉点缓存器实时监测自身缓存的数据包数量，一旦发现该数据包 数量有变化，立即向对应的输入端和输出端分别发送相应的缓存状态更新信息。

该步骤包括下述操作内容：交换开关中设置的N×N个交叉点缓存器各自分 别实时监测自身缓存的数据包数量是否有变化，即其自身缓存资源的使用情况。 一旦发现数量发生变化，该交叉点缓存器立即向其对应的输入端和输出端分别 发送其缓存器的状态更新信息；若没有发现数量变化，就不发送状态更新信息。

步骤5，输出端与输入端分别实时接收交叉点缓存器发送来的缓存状态更 新信息，并把与该缓存状态信息相对应的自身存储的状态值更新为接收到的缓 存状态更新信息中的当前缓存状态值。

参见图1左下侧的框图：交叉点缓存器的状态更新信息包括两个字段：交叉 点缓存器序号及其当前缓存状态值。其中，交叉点缓存器序号是每个交叉点缓 存器的唯一标识，以供输入端和输出端区分该状态更新信息来自哪个交叉点缓 存器，当前缓存状态值是该交叉点缓存器被占用的缓存量。

步骤6，输入端和输出端的输出调度模块分别根据各自更新后的自身存储 的状态值对数据包进行调度，完成相应数据包的传输。

本发明已经进行了多次实施试验，实验的结果是成功的，实现了发明目的。