按每流排队的物理队列动态共享装置

摘要

本发明属于计算机网络中业务流管理技术领域，其特征在于，它含有：该装置含有：物理存储器件RAM，以及集成在FPGA/ASIC上的写入模块、调度模块、RAM管理模块、动态共享列表、动态共享模块；其中，物理存储器件RAM，用于缓存数据分组和每个数据块的下一指针；将数据分组写入RAM对应的地址中；调度模块，按照设定的调度方式在处于活跃状态的流中进行调度；RAM管理模块，按照设定的方式对数据分组在RAM中存储的数据结构进行管理；动态共享列表维护活跃流和物理队列间的映射关系；动态共享提供快速的查找机制，插入机制，和删除机制。该装置降低了所需要的物理队列，实现了按流排队。

说明书

技术领域

本发明是一种实现线速对业务流进行按每流排队(per-flow queueing)的物理队列动态共享装置，可以应用于高速宽带网络转发设备中以实现服务质量(QoS)保证，属于计算机网络领域。

背景技术

通过在路由器、交换机等计算机网络转发设备中采用按每流排队(per-flow queuing)的方式进行缓存管理，可以严格保证不同业务流之间的服务质量(Quality of Service，QoS)。传统意义上，按照每流排队需要物理隔离不同的流进行管理，也就是说要为每个流单独维护一个物理队列。通过网络测量等手段发现，高速宽带网络中(如2.5Gbps，10Gbps带宽的网络)可以同时共存百万个以上的不同的活跃业务流，从而需要为每流排队的管理方式维护上百万个物理队列，而这将使得管理单元占用过多的资源和耗费过多的处理时间，使得难以实现。因此，尽管按每流排队的缓存管理方式可以提供QoS保证，但是传统的观念却被认为不具有可扩展性而无法在高速宽带网络中实现。

尽管高速宽带中可以共存百万个以上的不同的活跃业务流，但是通过对真实的网络数据仿真试验，发现任何一个时刻长度不为空的队列数目其实不超过几百或几千的数量级。直观的解释：每一个数据包在路由器等转发设备中存储的时间很短(ms级，甚至ns级)，而当同一流分组之间到达的间隔大于这个数量级时，会出现队列暂时为空的情况。本发明基于这一事实，提出一种可扩展装置，在物理上只维护少量队列(如，小于1k个队列)，通过对于队列的动态共享的方式，保证在任何时刻，不同的活跃业务流在转发设备中能够分配到单独的队列，避免一个队列中存在多个流，从而实现按每流排队，保证服务质量。

发明内容

每流排队存储管理系统中，为了确定需要预留多少资源，可以通过以下方法测量链路上传输的流的数量：1)流分类根据数据分组头部中的5元组来对分组进行分类，不同的数据分组归属不同的流；2)判断是否为正在传输中的流。当一个流的首个数据分组达到时，认为流开始传输；为检测流的传输是否结束，设置τ超时时间。如果τ时间内该流无数据分组到达，则认为流的传输过程结束。测量时设置τ为60秒甚至更长。测量结果表明通过节点的流的数量可达到几十万甚至上百万个。基于该结果，如果每流排队系统为每个流维护一个队列，则队列的数目也将达到几十万甚至上百万个，使每流排队的存储管理在高速路由器中变得难以实现。然而事实上，在流传输的过程中，某些时刻一些流对应的队列并没有存储数据分组，此时虽然它们的传输并未结束，但是在这些时刻，数据分组存储系统没有必要为其保存队列。实验和建模的结果表明，实际被占用的队列数远远小于同时进行传输的流的数量。基于此，数据分组存储系统中只需实现少量的队列，而通过动态物理队列的方式，达到每流排队的目的。

本发明提出一种可适用于高速宽带网络的可线速实现按每流排队的可扩展的装置，通过动态共享的机制，在少量物理队列中实现大量业务流的按每流排队，保证在任何时刻同一物理队列中不会缓存不同的业务流。定义两种流的状态：1)活跃状态。当一个流在物理队列中存储有分组，则认为该流处于活跃状态；2)静默状态。当一个流在网络转发设备中存储的所有分组都已经被转发，在没有属于该流的新的分组到达之前，认为该流处于静默状态。只有当一个流活跃时才占用一个物理队列，相应地可以建立其流号(即当前活跃的流)f_n和物理队列PQ_q间的映射关系f_n→PQ_q，集合{f_n→PQ_q}称为活跃流映射。当流从活跃变为静默的时候，需要将其对应的流号到物理队列的映射从活跃流映射中删除，并释放对应的物理队列；当流从静默变为活跃时，需要为其分配一个新的物理队列，在活跃流列表中添加其流号到物理队列的映射。

本发明装置的系统结构图如图1共存流数目随时间的变化曲线，其中实线是OC-192的曲线，虚线是OC-48的曲线。

图2占用物理队列数目随时间的变化曲线，其中下三角标记曲线是OC-192的曲线，上三角标记曲线是OC-48的曲线。

图3利用链表结构组织动态共享列表的子表时的操作复杂度，其中下三角标记曲线是OC-192的曲线，上三角标记曲线是OC-48的曲线；(a)图表示查找已存在活跃流的情况，(b)图是插入一个新的活跃流到物理队列映射的情况。

图4利用分查找树组织动态共享列表的子表时的操作复杂度，其中下三角标记曲线是OC-192的曲线，上三角标记曲线是OC-48的曲线；(a)图表示查找已存在活跃流的情况，(b)图是插入一个新的活跃流到物理队列映射的情况。

图5动态共享管理模块返回业务流对应物理队列的平均时间，其中上三角标记曲线是动态共享子表采用链表的组织方式时的情况，正方形标记曲线是动态共享子表采用二分查找树的组织方式时的情况；(a)图表示OC-48情况，(b)图是OC-192的情况。

图6利用二分查找树组织动态共享列表的子表时，动态共享管理模块返回业务流对应物理队列的平均时间的累积分布函数。

图7所示，其中，

RAM是存储数据分组的物理存储器件；

RAM管理模块对数据分组在RAM中存储的数据结构进行管理，包括，存储器的划分，空闲块的分配回收，向写入模块提供空闲块写入地址，向调度模块提供被调度队列的队头元素的地址。

动态共享列表是用来进行存储和维护活跃流映射关系f_n→PQ_q。

动态共享模块1)根据写入模块提供的流号f_n，根据动态共享列表里存在的信息判断当前是否存在物理队列对应流f_n，存在则返回其对应的物理队列号PQ_q；否则返回一个空闲队列号给写入模块，并在动态共享列表为其添加一条新的映射关系。2)在收到调度模块返回的某一物理队列变空的消息后，从动态共享列表里删除该物理队列对应的映射表项。

写入模块负责到达分组的写入。首先向动态共享模块请求当前到达分组所在流的对应物理队列，然后根据动态共享模块返回的结果，从RAM管理模块得到该物理队列的队尾写入地址，并将数据分组写入RAM对应的地址中。

调度模块负责数据分组的调度。先根据调度算法得到应该获得调度的物理队列，然后从RAM管理模块获取物理队列队头的读出地址，并将其从RAM中读出。当物理队列经过调度变空时，调度模块通知动态共享模块从动态共享列表中删除该物理队列对应的映射表项。

本发明的处理流程可以如下概括为：

分组到达时  根据其流号f_n查找动态共享列表；  如果 不存在f_n对应的物理队列       分配一个物理队列PQ_q并将该分组写入；       在动态共享列表添加一条f_n→PQ_q的映射  否则       将分组写入f_n对应的物理队列分组离开时  从物理队列PQ_q调度走一个分组；  如果  物理队列PQ_q变空      在动态共享列表删除一条f_n→PQ_q的映射

本发明解决如何使链路中(尤其是主干网中)数以百万计的业务流共享网络转发设备中有限的物理队列资源，实现按每流排队，其挑战主要在于：

1)从高速网络转发设备处理时间的尺度上来看，在高速网络转发设备中缓存的业务流是随机变化的，因此需要及时响应当前活跃流的变化。本发明提供了有效的机制维护和更新活跃流和物理队列之间的映射关系。

2)在高速网络中，数据分组之间到达的间隔很小，因此需要快速的查找机制定位到达分组所应存入的物理队列。本发明提供了快速算法查找活跃流和物理队列之间的映射关系。

3)存储器带宽和容量是高速网络转发设备的潜在瓶颈之一，RAM的管理对于存储器带宽和容量的影响巨大。本发明了采用高效的数据结构和控制方式维护RAM的管理。

本发明的特征在于，该装置含有：物理存储器件RAM，以及集成在FPGA/ASIC上的写入模块、调度模块、RAM管理模块、动态共享列表、动态共享模块；其中，

物理存储器件RAM，用于缓存数据分组和每个数据块的下一指针，采用SRAM，DRAM或者其他物理存储设备中的任何一种；

写入模块，设有活跃流的到达分组输入端，当前到达分组所在流的对应物理队列输入端，与动态共享模块的相应输出端相连，用于把所述物理队列写入物理存储器件RAM中的空闲块的队尾写入地址输入端，与RAM管理模块相应输出端相连；还设有，所述对应物理队列的请求信号输出端，与动态共享模块的相应输入端相连；所述对应物理队列的队尾写入地址请求信号输出端，与RAM管理模块相应输入端相连；数据分组输出端，与物理存储器件RAM的相应输入端相连；所述写入模块先向动态共享模块请求当前到达分组所在流的对应物理队列，然后根据动态共享模块返回的结果，从RAM管理模块得到该物理队列的队尾写入地址，并将数据分组写入RAM对应的地址中；

调度模块，用于数据分组的调度，设有：当前应该获得调度的物理队列输入端，与动态共享模块的相应输出端相连；所述物理队列队头读出地址输入端与RAM管理模块相应输出端相连；与所述物理队列队头读出地址对应的物理队列读入端与物理存储器件RAM的相应读出端相连；还设有：活跃流输出端，分别为向动态共享模块、RAM管理模块、物理存储器件RAM发出的请求信号输出端，其中包括向动态共享模块发出的，请求从动态共享列表中删除经过调度已经变空的物理队列所对应的映射表象请求信号；该调度模块按照设定的调度方式在处于活跃状态的流中进行调度，得到应该获得调度的物理队列，然后从RAM管理模块获取物理队列队头的读出地址，并将其从物理存储器件RAM中读出对应的数据分组；所属活跃状态是指一个流的对应的物理队列中存储有数据分组；

RAM管理模块，在与物理存储器件RAM、写入模块、调度模块分别相连的同时，按照设定的方式对数据分组在RAM中存储的数据结构进行管理，包括，存储器的划分，空闲块的分配回收，向写入模块提供空闲块写入地址，向调度模块提供被调度队列的队头元素的地址；

动态共享列表维护活跃流A和物理队列PQ之间一对一的映射关系，A和PQ中的元素的个数相同；

动态共享模块与动态共享列表互连；该模块提供快速的查找机制，负责从动态共享列表中找到活跃流对应的物理队列；还提供快速的插入机制，当新到达一个活跃流的分组时，负责插入一条新的活跃流到物理队列的映射到动态共享列表中；此外还提供快速的删除机制，当一个流所分配的物理队列变空时，负责在动态共享列表中删除一条活跃流到物理队列的映射。

所述的调度模块按照轮转的方式在一个以上的活跃的物理队列中进行调度。

所述的RAM管理模块把RAM存储空间和分成大小固定的存储块，其大小等于一个数据传输单元的大小。

所述的RAM管理模块采用栈结构方式实现空闲存储块的分配和回收；空闲块栈则在数据分组离开并归还空闲块后，栈顶指针向上移动，而当数据分组到达，分配了空闲块，空闲块栈顶指针向下移动。

所述的空闲块的分配与回收，当数据分组到达时，RAM管理模块从栈顶取出空闲块地址分配空闲块，将数据分组存入；当数据分组离开时，占用的存储块变为空闲块，RAM管理模块又将其地址写入栈结构，收回空闲块。

所述的RAM管理模块采用链表方式实现物理队列的管理，对于每一个物理队列，维护一个头部指针，指向物理队列的头部；维护一个尾部指针，指向物理队列的尾部；物理队列的每个数据块中保存一个下一指针，指向下一个数据块。

所述的RAM管理模块在写入模块写入一个新的数据块时更新队尾指针，在调度模块调度走一个数据块时更新队头指针。

所述的动态共享列表包括一个直接寻址存储表和一系列动态共享子表；该直接寻址存储表的每一个位置包括一个比特的标识位和一个指向子表的指针；其中，标识位为“1”，当某一位置存在子表，并且指向子表的指针有效的；标识位为“0”，当某一位置不存在子表，并且指向子表的指针为空指针。

所述的直接寻址存储表的位置，由到达分组的流号经过一次哈希函数之后的值确定；其中，哈希函数包括是MD-5或SHA-1等任意均匀哈希函数。

所述的动态共享子表可以用链表的方式进行组织。

所述的动态共享子表可以用二分查找树的的方式进行组织。

所述的动态共享子表可以用平衡二分查找树的的方式进行组织。

所述的动态共享模块的查找机制，指的是，先根据到达分组的流号经过哈希函数确定要查找的动态共享子表，再在相应的动态共享子表进行查找。

所述的在相应的动态共享子表进行查找的机制，针对权利要求0所述的链表组织方式，采用线型表顺序查找的方式进行。

所述的在相应的动态共享子表进行查找的机制，当采用二分查找树或者二分平衡查找树时，先比较要查找的流号值和根结点上存储的流号的值的大小，大于则转向右子树，小于则转向左子树，再比较子树根结点上存储的流号的值，依此类推，直到找到要找的流号。

所述的动态共享模块的插入机制，先根据分组流号经过哈希函数的值确定要插入的动态共享子表，再将要插入的节点插入到相应的动态共享子表。

所述的将要插入的节点插入到相应的动态共享子表机制，当采用链表组织方式时，采用线型表顺序插入的方式在动态共享子表的链表的尾部插入。

所述的将要插入的节点插入到相应的动态共享子表机制，当采用二分查找树的组织方式时，先比较要插入表项中的流号值和根结点上存储的流号的值的大小，大于则转向右子树，小于则转向左子树，再比较子树根结点上存储的流号的值，依此类推，直到找到叶子结点，如果要插入表项中的流号值大于叶子结点上存储的流号的值，则插入在右孩子，否则插入在左孩子。

所述的将要插入的节点插入到相应的动态共享子表机制，当采用的平衡二分查找树的组织方式时，先按照二分查找树组织方式下的方式插入要插入的子表表项，然后再调整二分查找树，使之每一个节点的左右子树的深度差不超过1。

所述的动态共享模块的删除机制，先根据分组流号经过一次哈希函数的值确定要删除的节点所在的动态共享子表，再在相应的动态共享子表进行删除。

所述的公台共享模块对相应的动态共享子表进行删除的机制，当采用链表组织方式时，用线性表顺序查找方式找到要删除的节点，然后删除。

所述的动态共享模块在相应的动态共享子表进行删除的机制，当采用二分查找树的组织方式时，先以二分查找树的查找方式找到要删除的节点，然后对其进行删除；其中，当删除的节点是叶子结点时，只需将其父节点指向NULL空指针；当删除的节点只有一个左(或右)孩子节点时，用其父节点直接指向要删除节点的左(或右)孩子；当删除的节点既有左孩子又有右孩子时，将删除的节点的右子树作为其左子树中值最大的节点的右子树，然后将调整后的左子树作为其父节点的子树。

所述的动态共享模块在相应的动态共享子表进行删除的机制，当采用二分查找树的组织方式时，先以二分查找树的删除方式删除要删除的节点，然后再调整二分查找树，使之每一个节点的左右子树的深度差不超过1。

所述的动态共享列表可以用内容寻址存储器CAM代替。

所述装置按以下步骤实现物理队列的共享：

步骤1：当有一个数据分组进入写入模块，写入模块用数据分组的流号向动态共享模块请求相应的物理队列；

步骤2：动态共享模块从动态共享列表查找相应流号所对应的表项，若存在则返回物理队列写入地址给写入模块；否则，分配一个新的物理队列给该流，返回物理队列号给写入模块，并在动态共享列表写入这条新的表项；

步骤3：写入模块得知相应物理队列写入地址之后，向RAM管理模块获得一个空闲块写入RAM，RAM管理模块更新该物理队列的尾指针和空闲块栈顶指针：

步骤4：调度模块根据调度算法调度各个物理队列，向RAM管理模块询问当前被调度队列的队头指针，从RAM中读出；同时RAM管理模块回收此数据块加入空闲块栈，修改空闲块栈顶指针，并修改相应物理队列的队头指针；

步骤5：当当前被调度队列变为空时，调度模块通知动态共享模块，删除其在动态共享管理列表上表项。

本发明提出的可扩展的装置，通过动态共享的机制，在只提供少量物理队列资源的情况下，仍能保证在任何时刻同一物理队列中不会缓存不同的业务流，从而实现了高速宽带网络的可线速实现按每流排队。试验结果表明，60％的情况下，一个时钟周期就可以返回结果，完成队列共享；在90％的情况下，可以保证2个时钟周期返回结果，完成队列共享。

实验验证

为验证本发明的装置方案，本发明进行了相关的实验，实验选取两段来自NLANR(http://pma.nlanr.net/Special/)的实际网络业务流量数据：1)OC-48：链路容量为2.5Gbps。2)OC-192：链路容量为10Gbps。其中，同时传输的流的数目如图1所示，OC-48上统计的流数在300,000上下波动，OC-192统计得到的流数在360,000上下波动。

仿真按分组的到达时刻将其存入不同的队列进行排队，调度在被占用的物理队列间公平地分配带宽，采用轮询方式，每个物理队列每次得到调度后转发固定长度的字节(1500字节)，然后轮询至下一个物理队列。实验统计的性能参数如下：

1)平均速率。某个时间段内通过节点的数据量和时间长度的比值，用表示；

2)共存的流数。对流设置τ时间的超时，对正在传输的流数进行统计，用N_s(τ)表示；

3)活跃流数，某个时刻占用队列进行排队的流的数量，即被占用的队列的数量，用N_a表示。

统计过程每25ns对N_a和N_s(τ)进行一次采样，相应地得出某个时间段(例如1秒或者10分钟)内的Max{N_a}和Max{N_s(τ)}。系统的负载L定义为真实业务流量的平均速率和出口带宽的比值，由于真实业务流量的平均速率无法改变，只能通过改变出口带宽来调整仿真的负载L以统计不同负载情况下的性能参数。如图2所示，为系统负载L设定为0.97时，物理队列占用随时间变化的情况。从图中可以看出，OC-48统计得到的流数最大仅为89，OC-192最大仅为406。将图2和图1中的原始共存流的数目比较，通过本发明的装置，使得需要设定的物理队列的数量大大减小。

通过哈希函数将动态共享列表分成多个子表的情况如下表所示。

子表数目测试项目  OC-48    OC-19264个子表平均子表条目数  2.1    2.97最坏子表条目数  13    17子表条目超过1的概率  0.343    0.722子表条目超过2的概率  0.177    0.495256个子表平均子表条目数  1.24    1.4最坏子表条目数  8    9子表条目超过1的概率  0.31    0.146子表条目超过2的概率  0.007    0.031024个子表平均子表条目数  1.06    1.1最坏子表条目数  5    6子表条目超过1的概率  0.003    0.017

从表中可以看出，经过哈希函数之后，每个子表的平均长度小于3。尽管最坏情况下子表的长度仍然可能达到10以上，但是，子表条目超过1或者2的概率就已经很小了。同时增加子表的数目，也可以极大地减小子表的长度。

图3和图4分别是利用链表和二分查找树组织动态共享列表的子表时的操作复杂度。两个图中的(a)是子表中已经存在该活跃流时的查找周期和子表数目的关系，而(b)是一个新的活跃流到达时的查找周期和子表数目的关系(需要插入新的表项)。从图中可以看出，随着子表数目的增加，查找的开销减小，当子表数目大于64时，就(a)(b)中显示的操作开销都在1.5个时钟以下。

图5是动态共享管理模块向写入模块返回业务流对应物理队列的平均时间。(a)(b)分别是针对OC-48和OC-192的实际业务流量时的平均时间开销。其中包括了一个周期的计算hash函数的时间开销。从图中可以看出，随着子表数目的增加，时间的开销减小，当子表数目大于256时，就(a)(b)中显示的操作开销都在2个时钟以下。

图6是存在256个子表并采用二分查找树组织子表结构时，时间开销的累计概率函数。从图中可以看出，60％的情况下，一个时钟周期就可以返回结果，在90％的情况下，可以保证2个时钟周期返回结果。

附图说明

图1共存流数目随时间的变化曲线，其中实线是OC-192的曲线，虚线是OC-48的曲线。

图2占用物理队列数目随时间的变化曲线，其中下三角标记曲线是OC-192的曲线，上三角标记曲线是OC-48的曲线。

图3利用链表结构组织动态共享列表的子表时的操作复杂度，其中下三角标记曲线是OC-192的曲线，上三角标记曲线是OC-48的曲线；(a)图表示查找已存在活跃流的情况，(b)图是插入一个新的活跃流到物理队列映射的情况。

图4利用二分查找树组织动态共享列表的子表时的操作复杂度，其中下三角标记曲线是OC-192的曲线，上三角标记曲线是OC-48的曲线；(a)图表示查找已存在活跃流的情况，(b)图是插入一个新的活跃流到物理队列映射的情况。

图5动态共享管理模块返回业务流对应物理队列的平均时间，其中上三角标记曲线是动态共享子表采用链表的组织方式时的情况，正方形标记曲线是动态共享子表采用二分查找树的组织方式时的情况；(a)图表示OC-48情况，(b)图是OC-192的情况。

图6利用二分查找树组织动态共享列表的子表时，动态共享管理模块返回业务流对应物理队列的平均时间的累积分布函数。

图7系统结构图。

图8块存储方式下队列结构的实现。

图9利用哈希函数分割动态共享列表。

图10利用链表结构组织利用哈希函数分割后的动态共享列表的子表。

图11利用二分查找树组织动态共享列表的子表的例子。

图12在二分查找树组织的动态共享列表的子表中插入一个表项的例子。

图13在二分查找树组织的动态共享列表的子表中删除一个表项的例子，其中(a)是删除74的例子，(b)是删除12的例子，(c)是删除66的例子。

具体实施方式

实施例1

写入模块负责到达分组的写入。首先向动态共享模块请求当前到达分流的对应物理队列，然后根据动态共享模块返回的结果，从RAM管理模块得到该物理队列的队尾写入地址，并将数据分组写入RAM对应的地址中。

为方便管理，RAM管理模块通常把数据分组存储空间分成大小固定的存储块。但是，网络上传输的是变长的数据分组，因此需要把分组切割成大小固定的单元，称为数据单元(DataUnit，简称DU)，这些DU在离开转发设备之前被重新组装成原始的变长数据分组。存储器RAM被分成的存储块的大小和DU的相同，因此一个DU正好占用一个存储块。

在数据分组存储器中，未被占用的存储块称为空闲块，RAM管理模块用栈结构来组织空闲块的地址。当数据分组到达时，RAM管理模块从栈顶取出空闲块地址分配空闲块，将数据分组存入；当数据分组离开时，占用的存储块变为空闲块，RAM管理模块又将其地址写入栈结构，收回空闲块。

RAM管理模块采用链表方式对物理队列的管理进行管理。链表中维护一个头部指针，指向物理队列链表的头部；维护一个尾部指针，指向物理队列链表的尾部。物理队列中数据存储在RAM中，在每一个数据块后面维护下一指针，指向下一个数据块。所有物理队列的头尾指针存储在RAM管理模块中，物理队列的数目不是事先固定的，物理队列是根据当前活跃流的个数动态创建和撤销。本发明使用FPGA/ASIC片内的SRAM保存物理队列头尾指针和空闲块栈，而数据分组和下一指针则存储于外部RAM存储设备中，如图8所示。

当数据分组到达或离去时，需要对指针数据进行更新，更新涉及到两个部分：1)下一指针的更新，以DU为单位。当一个DU到达时，需要完成入队操作，从空闲块栈中获取一个空闲块，将数据写入，此时把前一个DU所在的存储块的下一指针指向当前的DU存储位置；当一个DU离开时，需要完成出队操作，把空闲块加到空闲块队列末尾，更新前一个空闲块的下一指针使其指向收回的空闲块；2)头尾指针的更新。更新以数据分组为单位进行。当新的数据分组到达并存入后，队列的尾部发生变化，将尾部指针更新到新的位置；当数据分组离开时，队列的头部位置发生了改变，将头部指针更新到新的位置。空闲块栈则在数据分组离开并归还空闲块后，栈顶指针向上移动，而当数据分组到达，分配了空闲块，空闲块栈顶指针向下移动。

按流排队要求不同流之间的分组必须在每一个时刻都存储在不同的队列中，动态共享管理模块和动态共享列表的引入正是为了实现不同流能够无冲突的共享物理队列资源。本发明动态共享机制的其特点在于：

1)活跃流集合A是全体流集合F的一个子集，即AF，并且A在F内时刻变化；

2)A和物理队列PQ之间维持一个一对一的映射关系，A和PQ中的元素的个数相同，但是大大小于F中的元素个数；

3)动态共享管理提供一种快速的查找机制，负责从动态共享列表中找到活跃流对应的物理队列；

4)动态共享管理提供一种快速的插入机制，当新到达一个活跃流的分组时，负责插入一条新的活跃流到物理队列的映射；

5)动态共享管理提供一种快速的删除机制，当一个流所分配的物理队列变空时，负责删除一条活跃流到物理队列的映射。

通过TCP/IP分组头部的五源组信息(源IP地址，目的IP地址，源端口号，目的端口号，协议)可以区分不同的业务流。由于该五源组同有13bytes(以IPv4为例)，则全体流集合F最多可以包含2¹⁰⁴个元素。尽管活跃流的数目不超过1K，但是由于活跃流在最多可以包含2¹⁰⁴个元素的集合F中动态变化，使得动态共享管理具有很大的难度。我们分两步来解决动态共享的问题。首先，我们利用一个哈希函数将整个动态共享列表分成多个子表；然后我们再利用链表或者二分查找树的结构来组织子表。

利用哈希函数将整个动态共享列表分成多个子表的情况如图9所示。图中，动态共享列表是一个直接寻址存储表，其上的每一个位置对应一个子表。活跃流经过一个哈希函数h(·)之后，被哈希到相应的子表上，如h(f₇)被哈希到子表s₁上，h(f₃)和h(f₅)被哈希到子表s₂上。其中，哈希函数可以是MD-5，SHA-1等任意均匀哈希函数。

通过哈希的作用，不同的流被均匀地分配到各个子表上，而且通过实验发现，每个子表上的活跃流数目很小(后面的实验验证部分会详细列举实验结果)。因此，我们可以简单使用链表结构来组织各个子表，其结构如图10所示。在动态共享列表上的每一个位置用一个比特来表示该子表是否有元素存在，1表示存在子表，并且其后用一个指针指向子表的元素；0表示无子表，并且其后跟一个null空指针。子表中的每一个元素除了指向下一元素的指针之外，包含一个流号f和一个物理队列号PQ。在每个子表上的查找，插入和删除操作可以按照线型表方式的处理。

当写入模块向动态共享模块发送一个流号为f₅的查找请求时，首先经过一次哈希运算，被哈希到子表s₂，顺序查找s₂上的表项。通过2次查找找到f₅，返回其对应的物理队列号q₈。

当写入模块向动态共享模块发送一个流号为f₆的查找请求时，首先经过一次哈希运算，被哈希到子表s₃，由于s₃上的标识为0，因此分配一个物理队列后直接在s₃插入一条表项。

当调度模块将队列q₇中的元素全部调度空时，删除子表s₂上对应的表项，此时子表s₂上表项变为<f₅，q₈>。为了使得产出操作更加简单，可以在子表的每一个表项上增加一个上一指针，指向前一条表项。

调度模块按照轮转的方式在活跃的物理队列中进行调度。例如当前活跃的物理队列为q₁和q₈，则调度模块轮流调度两个队列，当前时刻调度q₁，则下一个时刻调度q₈，依此类推。如果新插入一个队列q₅，则调度模块轮流调度这三个队列；如果随后q₁被调度空，怎调度模块轮流调度q₅和q₈二个队列。

实施例2

写入模块和实施例1的工作方式一致。

RAM管理模块和实施例1的工作方式一致。

调度模块和实施例1的工作方式一致。

动态共享列表同样先按照图9方式的哈希方式进行划分成不同的子表，每一个子表按照二分查找树的方式进行组织，以减小在子表上的时间开销。二分查找树上的每一个节点同样包含活跃流号和对应的物理队列号，一个二分查找树的例子如图11所示，为了表示方便，每一个节点上的只给出对应的流号的数值。一个二分查找树的特点在于，左子树的数值小于根结点的数值，而右子树的数值大于根结点的数值。

如果要查找二分查找树上流号为74的活跃流对应的表项，先查看根结点，74＞56，转向右子树，74＞66，转向右子树，74＜86，转向左子树，找到。

当查找的过程中没有找到所要的节点，则在叶子节点处插入新的节点，图12给出了个插入流号为30的例子。30＜56，转向左子树，30＞18，转向右子树，30＜36而且36的左子树为空，则插入30作为36的左叶子结点。

在查找二分查找树上的删除分三种情况，如图13所示。当删除的节点是叶子结点时，只需将其父节点指向NULL空指针，如图13(a)所示。当删除的节点只有一个左(或右)孩子节点时，用其父节点直接指向要删除节点的左(或右)孩子，图13(b)所示。当删除的节点既有左孩子又有右孩子时，将删除的节点的右子树作为其左子树中值最大的节点的右子树，然后将调整后的左子树作为其父节点的子树，图13(c)所示。

实施例3

写入模块和实施例1的工作方式一致。

RAM管理模块和实施例1的工作方式一致。

调度模块和实施例1的工作方式一致。

动态共享列表同样先按照图9方式的哈希方式进行划分成不同的子表，但是每一个子表按照平衡二分查找树的方式进行组织。其与二分查找树的区别在于，每一个节点的左右子树的深度差不超过1。平衡二分查找树的查找过程和实施例2中二分查找树的查找过程一致。平衡二分查找树插入一条表项时，先和实施例2中二分查找树的查找过程一致，然后再对生成二分查找树进行调整，使得其左右子树的深度差不超过1。平衡二分查找树删除一条表项时，先和实施例2中二分查找树的删除过程一致，然后再对生成二分查找树进行调整，使得其左右子树的深度差不超过1。