CN110011924B - 一种清除缓存拥塞的方法与装置 - Google Patents

Abstract

一种清除缓存拥塞的方法与装置，通过设置回收门限，并在报文入队过程中根据入队顺序生成排序链表，在缓存使用量达到回收门限后，触发地址快速回收机制。本发明所提供的地址快速回收机制通过查找排序链表，从最老（即在缓存中最久）的报文开始，快速把占用缓存最长时间的地址先行回收，从而保证非拥塞队列的QoS性能。在回收地址时，以同一队列号下若干报文所组成的缓存分区chunk为单位进行丢弃，可迅速清除占据缓存空间的无用报文，从而进一步保障正常报文的入队与出队秩序。

Description

一种清除缓存拥塞的方法与装置

技术领域

本发明涉及数据通信领域，尤其涉及一种针对报文队列的缓存方法与装置。

背景技术

持续增长的因特网业务，让数据通信领域对数据产品的QoS性能提出了越来越高的要求。目前，各数据产品的缓存容量有限，缓存很容易被拥塞队列堆满，导致QoS性能不达标。

当前针对缓存，普遍采用的管理方式是：在报文进入缓存时，根据拥塞等级(高低优先级)以及队列号入队，当报文入队后，等待令牌，在分发令牌时优先满足高优先级报文的需求。这样，缓存中的高优先级报文在获得令牌后，就可以快速出队。但是，这种管理机制下，如果高优先级一直有报文，令牌就会一直分配给高优先级。这样导致的结果是：低优先级进入缓存后，由于高优先级始终占用令牌，而低优先级报文始终缺少令牌，因而低优先级报文始终不能出队，需要一直在缓存中占用缓存空间。长时间下去，低优先级占用的缓存越来越大，这样会导致缓存爆掉或者高优先级也不能入队，影响高优先级的流量，导致QoS性能不足。

针对该问题，目前通常的解决方式是：对一直在缓存中始终未出队的报文进行老化或清空，即，将该队列的报文全部丢弃。老化和清空这两种方式都可以将占据在缓存中的报文出队，但这两种方式存在的劣势在于：老化和清空均需要该队列的缓存达到一定的门限后才能进行老化或清空，每次老化或清空一个报文，缓存回收的速度比较慢。

为了解决上述问题，目前急需一种能够及时回收缓存的方法，能够快速把长时间占用缓存的地址回收，从而保证非拥塞队列的QoS性能。

发明内容

为了解决现有技术存在的不足，本发明的目的在于提供一种清除缓存拥塞的方法及装置。

首先，为实现上述目的，提出一种清除缓存拥塞的方法，包括以下步骤：第一步，接收报文，并依据报文的队列号或优先级调用对应的缓存分区存储所述报文；以排序链表存储调用所述各个缓存分区的先后顺序；

第二步，在缓存的深度大于回收门限时，按照所述排序链表中存储的调用所述各个缓存分区的先后顺序查找出队异常的缓存分区，清空出队异常的所述缓存分区，删除所述排序链表中存储的对应缓存分区；

第三步，依次循环所述第一步至所述第二步，直至无新报文入队。

进一步，上述的方法在所述第二步中判断所述缓存分区发生出队异常的依据包括：所述缓存分区无队列号或无优先级，或，所述缓存分区所对应的队列号或优先级无授权，或，所述缓存分区所对应的报文未进入出队链表。

进一步，上述的方法在所述第二步中出队步骤具体包括：

在缓存的深度不大于所述回收门限时，按照所述排序链表的顺序将缓存分区移入出队链表，并在获得授权后，将所述出队链中对应的报文出队。

具体的，上述的方法在所述第一步中，存储所述报文的步骤具体包括：依据所述报文的队列号或优先级调用对应的缓存分区；

若报文所属队列号或优先级下的缓存分区未填满，则将所述报文顺序存储至未填满的所述缓存分区；

若报文所属队列号或优先级下的缓存分区已填满，则建立新的缓存分区存储顺序所述报文。

具体而言，上述的方法中的所述排序链表采用双链表结构。

其次，为实现上述目的，还提出一种清除缓存拥塞的装置，包括依次连接的入队模块、缓存模块以及出队模块，其特征在于，还包括链表管理模块：所述链表管理模块的输入端同时连接所述入队模块和所述缓存模块，所述链表管理模块的控制端连接所述出队模块；

所述链表管理模块用于：根据所述入队模块中报文的队列号或优先级调用所述缓存模块中的缓存分区存储所述报文，并按照入队的顺序更新排序链表；按照所述排序链表的顺序，查找所述出队模块中所述缓存分区的状态，控制所述缓存模块释放出队异常的所述缓存分区并删除所述排序链表中对应的节点。

进一步，上述装置中，所述链表管理模块中的排序链表为双链表结构，新入队报文的所对应的缓存分区更新至所述排序链表的尾部。

具体的，上述装置中，所述缓存模块以固定大小分为多组存储单元；

所述每个缓存分区均包含有地址连续的N组存储单元，N≥1，每个缓存分区至少可存储一个报文；

每个队列号或优先级均对应至少一个所述缓存分区。

进一步，上述装置中，所述出队模块包括丢弃链表和出队链表；

所述出队链表用于存储所述排序链表中最接近链表头且获得授权的所述缓存分区，提取所述缓存模块中该缓存分区所对应的报文并出队；

所述丢弃链表用于在所述缓存模块的深度达到回收门限时，存储所述排序链表中最接近链表头而出队异常的缓存分区，提取所述缓存模块中该缓存分区所对应的报文并丢弃。

有益效果

本发明，通过设置回收门限，当缓存使用量达到回收门限后，触发地址快速回收机制：首先通过查找排序链表，从最老(即在缓存中最久)的一组报文(即通过队列号、优先级区分的一类存储于同一块缓存分区内的若干报文)开始回收，保证快速把占用缓存最长时间的地址先行回收，从而保证非拥塞队列的QoS性能。

进一步，为保证缓存利用率的均衡性，本发明在到达回收门限时，可通过查找出队链表的方式，保证出队速率与入队速率一致，即报文一个一个入队，获得权限的报文一个一个出队。但对于需要丢弃长期占用缓存资源的报文时，本发明这是通过查找报文所对应的队列号或优先级，直接舍弃该队列号或优先级下整个缓存分区中的全部报文。因此，可迅速丢弃无用报文，有效保证缓存的利用率。

同时，本发明在分配缓存分区的阶段，会预先判断报文所述队列号或优先级号下的缓存分区是否已满，仅在一个缓存分区完全填满报文的情况下，才会再分配新的缓存分区。通过这样的方式减少报文入队时申请缓存的频率，进一步提高缓存的利用率。

再进一步，本发明中的排序链表采用的是双链表的结构，这样直接删除中间节点后依旧能够迅速确定后续节点所对应的先后顺序。排序链表中，将新入队报文的缓存分区更新至排序链表的尾部，由此，直接通过排序链表就可方便地获得占用缓存资源最久的报文，将其舍弃。

本发明的其它特征和优点将在随后的说明书中阐述，并且，部分地从说明书中变得显而易见，或者通过实施本发明而了解。

附图说明

附图用来提供对本发明的进一步理解，并且构成说明书的一部分，并与本发明的实施例一起，用于解释本发明，并不构成对本发明的限制。在附图中：

图1为根据本发明的减少缓存拥塞的方法的流程图；

图2为根据本发明的减少缓存拥塞的装置的框图。

具体实施方式

以下结合附图对本发明的优选实施例进行说明，应当理解，此处所描述的优选实施例仅用于说明和解释本发明，并不用于限定本发明。

图1为根据本发明的一种清除缓存拥塞的方法，包括以下步骤：

第一步，接收报文，并依据报文的队列号或优先级调用对应的缓存分区存储所述报文；同时，以排序链表存储调用所述各个缓存分区的先后顺序；(这步为后面实现地址快速回收机制的基础)；

第二步，在缓存的深度大于回收门限时，通过丢弃链表执行地址快速回收机制：按照所述排序链表的顺序(即，所述排序链表中存储的各个缓存分区的顺序)查找出队异常的缓存分区移入丢弃链表，清空出队异常的所述缓存分区，同时删除所述排序链表中存储的对应缓存分区；(这样，以删除长期出队异常的一组报文后可实现对缓存深度的更新，后面的报文可及时进入并使用缓存资源)；同时，在缓存的深度不大于回收门限时，执行出队步骤：按照所述排序链表的顺序将缓存分区移入出队链表，并在获得授权后，将所述出队链中对应的报文按照RR规则或SP规则出队，同时删除所述排序链表中存储的对应缓存分区；第三步，依次循环所述第一步至所述第二步，直至无新报文入队。

具体的，上述的方法在所述第二步中判断所述缓存分区发生出队异常的依据包括：所述缓存分区无队列号或无优先级，或，所述缓存分区所对应的队列号或优先级无授权，或，所述缓存分区所对应的报文未进入出队链表。若该队列号没有授权，则不满足出队条件，所以不能存在出队链表中，无法出队，只有满足条件后，才能重新加入出队链表。若队列为空，说明没有报文了，就更不应该存在于出队链表中。为了保证缓存利用率的均衡性，当达到回收门限后，要保证入队速率和出队速率一致，报文一个个的入，对出队来说，正常报文是一个个出，对于要丢弃的报文是chunk形式丢，可以多丢几个报文，保证缓存的利用率。

进一步，为减少报文入队时申请缓存的频率，上述的方法在所述第二步中，存储所述报文的步骤具体包括：

为每一个队列号或优先级对应至少一个缓存分区；

若报文所属队列号或优先级下的缓存分区(chunk)未填满，则将所述报文接着之前的报文顺序存储至该缓存分区内空闲的存储单元(block)中。只有在该缓存分区完全被占用的状况下，才需为新报文分配新的缓存分区，并顺序存储所述报文。这样，每个缓存分区可存储一个或多个报文(具体的报文的数量与报文实际的长度有关)，在丢弃该chunk时，可及时丢弃若干条报文，以此实现缓存地址的快速回收。

具体的，上述的方法在报文获得授权时，将所述出队链表中对应的报文按照RR规则或SP规则出队。其中，RR规则，表示按照队列号依次出队。SP规则则按照队列号的优先级进行出队：若有高优先级队列有报文，先高优先出队，否则低优先级报文出队)。出队时利用出队链表执行出队过程。所述出队链表是按照队列号进行划分的，在没收到反压的情况下，各队列之间的出队链表按照所述的RR规则或SP规则进行出队。当该队列号没有报文或没授权时，则该队列的出队链表删除。

具体而言，上述的方法中的所述排序链表采用双链表结构，如此，可方便地在中间删除节点的条件下，保证先到的排在最前面。

其次，参照图2，为实现上述目的，还提出一种清除缓存拥塞的装置，包括依次连接的入队模块、缓存模块以及出队模块，其特征在于，还包括链表管理模块：

所述链表管理模块的输入端同时连接所述入队模块和所述缓存模块，所述链表管理模块的控制端连接所述出队模块。

所述链表管理模块用于在缓存模块中寻找到最长时间未出队的报文：根据所述入队模块中报文的队列号或优先级调用所述缓存模块中的缓存分区存储所述报文，并按照入队的顺序更新排序链表；按照所述排序链表的顺序，查找所述出队模块中所述缓存分区的状态，控制所述缓存模块释放出队异常的所述缓存分区(与出队过程相对)并删除所述排序链表中对应的节点。

所述入队模块：对入队报文提取队列号和拥塞等级(即高低优先级)。

缓存模块：根据队列号以及链表申请和删除情况管理缓存的深度。在设置回收门限(管理缓存的深度)时，需考虑高优先级的流量，保证非拥塞不受影响。

出队模块：将正常报文和丢弃的报文进行出队，当正常报文不出队时，丢弃的报文才可以出队。

进一步，上述装置中，所述链表管理模块中的排序链表为双链表结构，新入队报文的缓存分区更新至所述排序链表的尾部。

具体的，上述装置中，所述缓存模块以固定大小(例如，256bit)分为多组存储单元；

所述每个缓存分区均包含有地址连续的N组存储单元，N≥1(本实施例N取8)，报文以存储单元block为单位进行存储，因此每个缓存分区至少可存储一个报文；

每个队列号或优先级均对应至少一个所述缓存分区chunk，出队异常进行丢弃时以缓存分区(chunk)为单位，一次丢弃同一缓存分区其中的若干报文，因而回收效率更高。

进一步，上述装置中，所述出队模块包括丢弃链表和出队链表；

所述出队链表用于存储所述排序链表中最接近链表头且获得授权的队列号或优先级所对应的缓存分区，提取所述缓存模块中该缓存分区所对应的报文并出队；所述丢弃链表用于在所述缓存模块的深度达到回收门限时，存储所述排序链表中最接近链表头而出队异常(不在所述出队链表中)的缓存分区，提取所述缓存模块中该缓存分区所对应的报文并丢弃。

本发明技术方案的优点主要体现在：通过设置回收门限，并在报文入队过程中根据入队顺序生成排序链表，在缓存使用量达到回收门限后，触发地址快速回收机制。本发明所提供的地址快速回收机制通过查找排序链表，从最老(即在缓存中最久)的报文开始，快速把占用缓存最长时间的地址先行回收，从而保证非拥塞队列的QoS性能。在回收地址时，以同一队列号下若干报文所组成的chunk(缓存分区)为单位进行丢弃，可迅速清除占据缓存空间的无用报文，从而进一步保障正常报文的入队与出队秩序。

本领域普通技术人员可以理解：以上所述仅为本发明的优选实施例而已，并不用于限制本发明，尽管参照前述实施例对本发明进行了详细的说明，对于本领域的技术人员来说，其依然可以对前述各实施例记载的技术方案进行修改，或者对其中部分技术特征进行等同替换。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims (8)

1.一种清除缓存拥塞的方法，其特征在于，步骤包括：

第一步，接收报文，并依据报文的队列号或优先级调用对应的缓存分区存储所述报文；以排序链表存储调用各个所述缓存分区的先后顺序；

第二步，在缓存的深度大于回收门限时，按照所述排序链表中存储的调用所述各个缓存分区的先后顺序查找出队异常的缓存分区，清空出队异常的所述缓存分区，删除所述排序链表中存储的对应缓存分区；

第三步，依次循环所述第一步至所述第二步，直至无新报文入队；

所述第二步中，判断所述缓存分区发生出队异常的依据包括：所述缓存分区无队列号或无优先级，或，所述缓存分区所对应的队列号或优先级无授权，或，所述缓存分区所对应的报文未进入出队链表。

2.如权利要求1所述的清除缓存拥塞的方法，其特征在于，所述第二步中的出队步骤包括：

按照所述排序链表的顺序将缓存分区移入出队链表，并在获得授权后，将所述出队链中对应的报文出队。

3.如权利要求1所述的清除缓存拥塞的方法，其特征在于，所述第一步中，存储所述报文的步骤包括：

依据所述报文的队列号或优先级调用对应的缓存分区；

若报文所属队列号或优先级下的缓存分区未填满，则将所述报文顺序存储至未填满的所述缓存分区；

若报文所属队列号或优先级下的缓存分区已填满，则建立新的缓存分区存储顺序所述报文。

4.如权利要求1至3任一所述的清除缓存拥塞的方法，其特征在于，所述排序链表为双链表结构。

5.一种清除缓存拥塞的装置，包括依次连接的入队模块、缓存模块以及出队模块，其特征在于，还包括链表管理模块；

所述链表管理模块的输入端同时连接所述入队模块和所述缓存模块，所述链表管理模块的控制端连接所述出队模块；

所述链表管理模块用于：根据所述入队模块中报文的队列号或优先级调用所述缓存模块中的缓存分区存储所述报文，并按照入队的顺序更新排序链表；按照所述排序链表的顺序，查找所述出队模块中各缓存分区的状态，控制所述缓存模块释放出队异常的所述缓存分区并删除所述排序链表中对应的节点；其中，判断所述缓存分区发生出队异常的依据包括：所述缓存分区无队列号或无优先级，或，所述缓存分区所对应的队列号或优先级无授权，或，所述缓存分区所对应的报文未进入出队链表。

6.如权利要求5所述的清除缓存拥塞的装置，其特征在于，所述链表管理模块中的排序链表为双链表结构，新入队报文所对应的缓存分区更新至所述排序链表的尾部。

7.如权利要求6所述的清除缓存拥塞的装置，其特征在于，所述缓存模块以固定大小分为多组存储单元；

每个所述缓存分区均包含有地址连续的N组存储单元，N≥1，

每个队列号或优先级均对应至少一个所述缓存分区。

8.如权利要求6所述的清除缓存拥塞的装置，其特征在于，所述出队模块包括丢弃链表和出队链表；

所述出队链表用于存储所述排序链表中最接近链表头且获得授权的所述缓存分区，提取所述缓存模块中该缓存分区所对应的报文并出队；

所述丢弃链表用于在所述缓存模块的深度达到回收门限时，存储所述排序链表中最接近链表头而出队异常的缓存分区，提取所述缓存模块中该缓存分区所对应的报文并丢弃。

Images