时延计时设备、管理多个时延的方法及延迟多个数据包的装置

摘要

本发明公开了一种对多个时延进行计时的时延计时设备(1)，包括时延时钟(2)，时延时钟(2)包括多个时钟存储器(3、3a、3b、3c)，其中，所述多个时钟存储器(3、3a、3b、3c、3d)与时延时钟值的多个位位置相对应；时延存储器(4)，用于存储所述多个时延(5、5a、5b、5c、5d、5e、5-i)；时延逻辑单元(6)，用于通过将新时延(5、5a、5b、5c、5d、5e、5-i)存储到所述时延存储器(4)来添加所述新时延，并通过以下方法对所述新时延(5、5a、5b、5c、5d、5e、5-i)进行计时：将所述新时延(5、5a、5b、5c、5d、5e、5-i)耦合到与所述新时延(5、5a、5b、5c、5d、5e、5-i)的时延值的非零最高位位置相对应的时钟存储器(3、3a、3b、3c)，然后根据所述新时延(5、5a、5b、5c、5d、5e、5-i)的时延值将所述新时延耦合到与所述时延值的下一个次高位位置相对应的时钟存储器(3、3a、3b、3c)，并在所述新时延到期时生成时延信号(19)。本发明进一步公开了一种方法和装置。

说明书

技术领域

本发明总体上涉及电子设备中的时钟或计时器，尤其是针对数据网络，更具体地涉 及对多个时延(a plurality of delays)进行计时的时延计时器(delay timer)、管理多个时 延的方法以及延迟多个数据包(delaying a plurality of data packets)的装置。

背景技术

现代电子设备中，时钟或定时器用于完成各种任务。例如，现代数据网络中，数据 整形(data shaping)需要时钟或计时器。数据整形需平滑流量突发，以控制和限定接收 单元处的数据包队列以及执行服务提供商和客户之间的合约。

在流量整形应用(traffic shaping applications)中测量到来的流量(incoming traffic)， 一旦超过为数据流量定义的一定限度，便阻留或延迟到来的流量以在最小突发量下保持 稳定的数据速率。这种流量整形器(traffic shaper)通过使用计时器对各个单一的数据包 的时延进行计时，或对一个数据包流队列中的时延进行计时，管理数据包的时延。当计 时器显示时延已到期时，便将相应流量从延迟的数据包队列中传输出去。

极高带宽应用中的流量整形器可在任何给定的时间延迟数以百万计的数据包或流队 列。

将硬件计时器用于所有延迟的数据包或流队列可实现对较少时延的管理。但是，对 于数以百万计的时延，计数器的数量及如触发电路(flip flops)等集成电路的量(the  amount of integrated circuitry)将显著增加。这将增加能耗和设备成本，从而导致这种流量 整形器经济效益不佳。

因此，对于大量时延，已开发出对这些时延进行计时的方法，包括处理器和用于存 储所述时延的数据存储器。在这种流量整形器中，时延值(delay value)存储在存储器 中，该时延值不断递减，直至为0。如果时延值达到0，则该时延到期，进而传输数据包 或允许流队列发送流量。在这种流量整形器中，时延值每一次递减时，都需要对该存储 器进行读写访问，然后进行与0相比较的操作。如果时延值的范围为0到1000，在最坏 的情况下，需针对每个时延对该存储器进行1000次读写访问。这样，当用于大量数据包 或流队列时，就会产生性能瓶颈。

因此开发出用于减少管理时延而需要的计算量的方法。一种方法包括计算时延值的 多个单一的位及其对应的速率(counting the single digits of a delay value with their  corresponding rate)。例如，值为987的时延可计数为9个百位步(hundreds-steps)、8个 十位步(tens-steps)和7个个位步(ones-steps)。这样，所需计算量减少到所述时延值的 多个位的总和。但是，根据定时器的个数和数以百万计的时延的时延值范围，该处理仍 可能达到较高值，从而引发性能问题。

发明内容

本发明的目的在于提供用于有效管理多个数据包的时延的方法。

根据本发明第一方面，本发明上述目的由对多个时延进行计时的时延计时设备来实 现。所述时延计时设备包括：包括多个时钟存储器(a number of clock memories)的时延 时钟(delay clock)，其中，所述多个时钟存储器与时延时钟值(delay clock value)的多 个位位置(digit positions)相对应；时延存储器，用于存储所述多个时延；时延逻辑单元 (delay logic unit)，用于通过将新时延存储到所述时延存储器来添加所述新时延，并通过 以下方法对所述新时延进行计时：将所述新时延耦合到与所述新时延的时延值的非零最 高位位置(most significant digit position)相对应的时钟存储器，然后根据所述新时延的时 延值将所述新时延耦合到与所述时延值的下一个次高位位置(next less significant digit  position)相对应的时钟存储器，并在所述时延到期时生成时延信号(delay signal)。本发 明提供一种时延计时器，能够对时延进行计时，且只需要经过少量计算。为了对时延进 行计时，在最坏的情况下，所述时延计时器需在该单一时延上针对时延值的每一位运行 一次。例如，在一个较佳实施例中，如果所述时延以个位为0的时延时钟值结束，如 220，所述时延计时器只需要在所述时延上针对百位和十位运行。这样，所述时延计时器 仅需在所述时延上运行两次，便可对所述时延进行计时。进一步地，本发明提供一种时 延计时器，可在需要时仅通过添加或移除时钟存储器，便能适应不同的时延时钟值规 格。

在本发明第一方面提供的所述时延计时设备的第一可能实现方式中，每个时钟存储 器包括为所述时延计时设备使用的数字系统中的每位(every digit)提供的至少一个存储 块(memory block)；所述时延时钟包括为每个时钟存储器提供的一个指针，所述指针用 于指向存储块，所述存储块表示在指示相应的时钟存储器的位位置的实际时延时钟值 (actual delay clock value)。在相应的最优实现方式中，使用指针表示所述实际时延时钟 值，则通过增加单个指针的值，便可计算出所述时延时钟值，且不需要进行复杂的计 算。进一步地，本发明提供的时延计时器可使用任何适用于某个执行环境的数字系统。 在最优实现方式中，如果所述时延计时器使用十进制数字系统，所述时钟存储器中需要 有至少10个存储块。因此，在最优实现方式中，如果所述时延计时器使用十六进制数字 系统，所述时钟存储器中需要有至少16个存储块。在最优实现方式中，对于八进制数字 系统，所述时钟存储器中需要有至少8个存储块。

在本发明第一方面提供的时延计时设备的第一可能实现方式的第二可能实现方式 中，所述时延计时器的基本时间间隔(basic time interval)表示与所述时延时钟的最低位 位置(the least significant digit position)的一个位增量(one digit increment)相对应的时 步(time step)，所述时延时钟包括时钟逻辑单元，其中，所述时钟逻辑单元用于在每个 基本时间间隔后对指向所述时延时钟的最低位位置的指针进行增量，所述时钟逻辑单元 还用于在指向所述数字系统中最高位(the highest digit)的存储块的指针被增量时，重设 每个指针，使其指向所述数字系统中最低位的存储块，所述时钟逻辑单元还用于同时对 指向下一个更高位位置(the next more significant digit position)的指针进行增量，使其指 向下一个存储块，从而提供一种可以通过很少计算量进行管理的时延时钟。仅对指针进 行“+1”的操作，便可更新实际时延时钟值，而且使用简单的“if”从句，便可检查是否 需要重设指针，无需进行复杂的运算。

在本发明第一方面提供的时延计时设备的第一或第二实现方式的第三可能实现方式 中，所述时延逻辑单元进一步用于通过将存储的新时延耦合到指示所述存储新时延的时 延值的非零最高位位置的时钟存储器，添加所述新时延，其中，所述存储的新时延与所 述时钟存储器的存储块相关联，所述存储块是在添加所述存储的新时延时相应指针所指 向的位置上的存储块，所述相应指针被增量，增量为所述存储的新时延的时延值的非零 最高位位置表示的步数加上所述存储的新时延的时延值的多个次高位位置上的多个位与 所述实际时延时钟值的多个次高位位置上的多个位之和的进位(carryover)。通过将新时 延与相应时钟存储器的存储块相关联，可提供一种管理时延的有效方式。识别是否必须 在特定的时延时钟周期再次对所述时延进行处理时，不需要将所有时延都与所述实际时 延时钟值进行比较，只需要处理与所述时钟存储器的指针实际指向的时钟存储器的存储 块相关联的时延。

在本发明第一方面提供的时延计时设备的第一、第二或第三实现方式的第四可能实 现方式中，所述时延逻辑单元用于，当指向与时延瞬时关联的时钟存储器的指针到达与 所述时延相关联的所述时钟存储器的所述存储块时，将所述时延耦合到指示所述时延值 的下一个次高位的时钟存储器；所述时延逻辑单元还用于将所述时延耦合到指示所述时 延值的下一个次高位的时钟存储器的存储块，所述存储块是指耦合所述时延时相应指针 所指向的存储块，所述相应指针被增量，增量为所述时延的时延值的下一个次高位位置 表示的步数加上所述时延的时延值中比所述下一个次高位位置更低的多个位位置上的多 个位与所述实际时延时钟值中比所述下一个次高位位置更低的多个位位置上的多个位之 和的进位，这样，提供了有效的方法，用于在时钟存储器的指针指向时延耦合到的存储 块时对所述时延进行处理。

在本发明第一方面提供的时延计时设备的第一至第四任一种实现方式的第五可能实 现方式中，所述时延逻辑单元用于，在指向所述时延时钟的最低位位置的指针到达与相 应时延相关联的存储块时，指示所述时延到期。

在本发明第一方面提供的时延计时设备的第二至第六任一种实现方式的第六可能实 现方式中，每个时钟存储器包括一个附加存储块，所述附加存储块位于指示所述数字系 统的最高位的存储块之后；所述时钟逻辑单元还用于在指向所述附加存储块的指针被增 量时，重设每个指针，使其指向所述数字系统中最低位的存储块；所述时钟逻辑单元还 用于同时对指向下一个更高位位置的指针进行增量，使其指向下一个存储块；所述时延 逻辑单元还用于，在将时延耦合到存储块时，通过所述附加存储块补偿小于所述时延时 钟的基本时间间隔的系统时间间隔(system clock intervals)。这样，提供了方法，用于补 偿比嵌入了所述时延计时器的集成电路的一个时钟周期持续更长时间的基本时间间隔。

在本发明第一方面提供的时延计时设备的第一至第六任一种实现方式的第七可能实 现方式中，与一个存储块相关联的所述多个时延被组织在链表中，所述存储块包括指向 所述链表中第一元素的指针和/或指向所述链表中最后一个元素的指针，时延包括时延时 间值(delay time value)和/或时延时间余数(delay time remainder)以及指向所述链表中 下一个时延(next delay)的时延指针(delay pointer)。链表可用于管理对象列表，即对时 延进行有效地管理，将时延从所述链表中移除或添加到所述链表中。

在本发明第一方面提供的时延计时设备的第一至第七任一种实现方式的第八可能实 现方式中，所述时延计时设备包括可编程逻辑设备和/或处理器和/或专用集成电路和/或计 算机程序产品。通过提供不同电子装置形式的时延计时器，所述时延计时器可适用于各 种不同的使用场景。

根据本发明第二方面，本发明上述目的也可由一种对多个时延进行计时的方法实 现，所述方法包括以下步骤：

根据本发明第一方面或本发明第一方面提供的时延计时设备的第一至第八任一种实 现方式，提供时延计时设备；

将时延存储到时延存储器；

将所述新时延耦合到指示所述新时延的时延值的非零最高位位置的时钟存储器；然 后根据所述新时延的时延值，将所述新时延耦合到与所述时延值的下一个次高位位置相 对应的时钟存储器；当所述新时延到期时，生成时延信号。

在本发明第二方面提供的对多个时延进行计时的方法的第一实现方式中，所述方法 包括以下步骤：

为时钟存储器中所述时延计时设备使用的数字系统中的每位提供至少一个存储块；

为每个时钟存储器提供一个指针；

使所述指针指向存储块，所述存储块表示在指示相应的时钟存储器的位位置的实际 时延时钟值。

在本发明第二方面提供的对多个时延进行计时的方法的第一实现方式的第二实现方 式中，所述时延计时器的基本时间间隔表示与所述时延时钟的最低位位置的一个位增量 相对应的时步，且所述方法包括以下步骤：

在每个基本时间间隔后对指向所述时延时钟的最低位位置的指针进行增量；

当指向所述数字系统中最高位的存储块的指针被增量时，重设每个指针，使其指向 所述数字系统中最低位的存储块，同时进一步对指向下一个更高位位置的指针进行增 量，使其指向下一个存储块。

在本发明第二方面提供的对多个时延进行计时的方法的第一或第二实现方式的第三 实现方式中，可通过以下方法添加新时延：将所述存储的新时延耦合到指示所述存储的 新时延的时延值的非零最高位位置的时钟存储器；将所述存储的新时延耦合到所述时钟 存储器的存储块，所述存储块是在添加所述存储的新时延时相应指针所指向的位置上的 存储块，所述相应指针被增量，增量为所述存储的新时延的时延值的非零最高位位置表 示的步数加上所述存储的新时延的时延值的多个次高位位置上的多个位与所述实际时延 时钟值的多个次高位位置上的多个位之和的进位。

在本发明第二方面提供的对多个时延进行计时的方法的第一、第二或第三实现方式 的第四实现方式中，当指向与时延瞬时关联的时钟存储器的指针到达与所述时延相关联 的所述时钟存储器的存储块时，时延与指示该时延值的下一个次高位位置的时钟存储器 相关联；所述时延与所述指示所述时延值的下一个次高位的时钟存储器的存储块相关 联，所述存储块是指耦合所述时延时相应指针所指向的存储块，所述相应指针被增量， 增量为所述时延的时延值的下一个次高位位置表示的步数加上所述时延的时延值中比所 述下一个次高位位置更低的多个位位置上的多个位与所述实际时延时钟值中比所述下一 个次高位位置更低的多个位位置上的多个位之和的进位。

在本发明第二方面提供的对多个时延进行计时的方法的第一至第四任一种实现方式 的第五实现方式中，当指向所述时延时钟的最低位位置的指针到达与相应时延相关联的 存储块时，指示所述时延到期。

在本发明第二方面提供的对多个时延进行计时的方法的第一至第五任一种实现方式 的第六实现方式中，所述方法包括以下步骤：

在每个时钟存储器中提供一个附加存储块，所述附加存储块位于指示所述数字系统 的最高位的存储块之后；

当指向所述附加存储块的指针被增量时，重设每个指针，使其指向所述数字系统中 最低位的存储块，同时对指向下一个更高位位置的指针进行增量，使其指向下一个存储 块；

将时延耦合到存储块时，通过所述附加存储块补偿小于所述时延时钟的基本时间间 隔的系统时钟间隔。

在本发明第二方面提供的对多个时延进行计时的方法的第一至第六任一种实现方式 的第七实现方式中，所述方法包括以下步骤：

与一个存储块相关联的所述多个时延被组织在链表中；

提供指向所述链表中第一元素的指针和/或指向所述链表中最后一个元素的指针；

在每个时延中提供时延时间值和/或时延时间余数以及指向所述链表中下一个时延的 时延指针。

根据本发明第三方面，本发明上述目的也可由一种延迟多个数据包的装置实现，所 述装置包括如本发明第一方面提供的第一至第八任一种实现方式所述的至少一个时延计 时设备，至少一个数据接口，所述数据接口用于接收和传输数据包，以及至少一个处理 单元，所述处理单元用于通过所述时延计时设备延迟接收到的数据包。本发明提供的装 置能够通过本发明提供的时延计时器处理数字数据。因此，本发明提供的装置能够有效 延迟数字数据，例如，在数据网络中高效进行流量整形。

在本发明第三方面提供的对多个时延进行计时的装置的第一可能实现方式中，所述 装置包括网桥(network bridge)。

在本发明第三方面提供的对多个时延进行计时的装置的第一可能实现方式中，所述 装置包括网络交换机(network switch)。

在本发明第三方面提供的对多个时延进行计时的装置的第一可能实现方式中，所述 装置包括网络路由器(network router)。

上述技术可以通过硬件、软件、固件或它们的结合实现。通过软件实现时，所述技 术可部分由包括程序代码的计算机可读介质来实现，所述程序代码包含在需要执行时执 行此处描述的一种或多种方法的指令。

附图说明

下面结合附图描述本发明提供的对多个时延进行计时的时延计时设备、对多个时延 进行计时的方法和延迟多个数据包的装置的实现方式。

图1示出了本发明第一方面提供的时延计时设备的第一可能实现方式的框图；

图2示出了本发明第二方面提供的对多个时延进行计时的方法的一种可能实现方式 的流程图；

图3示出了本发明第三方面提供的延迟多个数据包的装置的一种可能实现方式的框 图；

图4示出了根据本发明第一方面中所述时延计时设备的第八实现方式提供的时延计 时设备的第二可能实现方式的框图；

图5示出了连续三个时间点上四个时钟存储器的状态的框图；

图6示出了时钟存储器和链表的框图。

具体实施方式

图1示出了本发明第一方面提供的时延计时设备1的第一可能实现方式的框图。

图1所示的时延计时设备1包括时延时钟2。所述时延时钟2包括时钟存储器3。图 1明确示出表示时钟存储器3的块3，并通过多个点示出其他可能的时钟存储器3a、3b和 3c。所述时延时钟2包括为时延时钟值的每位提供的一个时钟存储器3、3a、3b、3c或 3d。如本说明书所指，所述时延时钟值并不是实际时延时钟值，而是所述时延时钟用于 计数的最大值。例如，如果所述时延时钟值包括四位，可使所述时延时钟从时延时钟值 0000计数到时延时钟值9999，则所述时延时钟包括对应于所述时延时钟值的千位的第一 时钟存储器、对应于所述时延时钟值的百位的第二时钟存储器、对应于所述时延时钟值 的十位的第三时钟存储器和对应于所述时延时钟值的个位的第四时钟存储器。相反，所 述实际时延时钟值是特定时间点上时延时钟的瞬间时延时钟值。

所述时延计时设备1还包括时延存储器4，所述时延存储器4包括已存储的时延5– 5e和5-i。进一步，图1通过三个点示出可能的时延5–5e和5-i。所述时延时钟2和所述 时延存储器4均被耦合到时延逻辑单元6，所述时延逻辑单元6用于将新时延5–5e和5- i存储到所述时延存储器4中，并将所述新时延5–5e和5-i耦合到相应的时钟存储器3、 3a、3b、3c和3d。

在图1所示的时延计时设备1的第一实现方式的第一可能实施例中，所述时延计时 设备1由一种计算机程序产品来实现，所述计算机程序产品用于根据图1所示的时延计 时设备1的第一实现方式提供所述时延计时设备1的功能。在这种实施例中，所述时钟 存储器3、3a、3b、3c和3d以及所述时延存储器4可包含在如运行Windows或Linux等 操作系统的个人计算机等装置的主存储器或RAM存储器中。所述时延逻辑单元的功能被 嵌入到所述个人计算机执行的可执行计算机指令中。

在图1所示的时延计时设备1的第一实现方式的第二可能实施例中，所述时延计时 设备由一种专用集成电路来实现，所述专用集成电路用于根据图1所示的时延计时设备1 的第一实现方式提供所述时延计时设备的功能。在这种实施例中，所述时钟存储器3、 3a、3b、3c和3d以及所述时延存储器4可包含在如直接耦合到所述时延时钟逻辑6的 DRAM存储设备中，所述时延时钟逻辑6直接包含在嵌入到所述专用集成电路的集成逻 辑电路中。

在图1所示的时延计时设备1的第一实现方式的第三可能实施例中，所述时延逻辑 单元6用于分析新时延，如时延5–5e和5-i中的一个，以识别出所述新时延的时延值中 的非零最高位，其中，所述时延逻辑单元6从所述时延值中序数为0的最低位开始计 数。

例如，如果所述时延计时设备使用4个十进制位计数所述时延时间，若新时延的时 延值为985，则所述时延值的非零最高位为第二位，即十进制数字“9”。所述时延逻辑 单元6识别出所述时延值的非零最高位的位置后，会将所述新时延与所述第二时钟存储 器相关联，其中，所述第二时钟存储器与所述时延时钟值的第二位相关联。

图2示出了本发明第二方面提供的对多个时延进行计时的方法的一种可能实现方式 的流程图。

在第一步骤S1中，提供时延计时设备1。所述时延计时设备1根据本发明第一方面 中第一至第八任一种实现方式来实现。

在第二步骤S2中，将新时延5存储到时延存储器4。

在第三步骤S3中，将所述新时延耦合到时钟存储器，所述时钟存储器指示所述新时 延的时延值的非零最高位位置。

进一步地，在第四步骤S4中，根据所述新时延的时延值将所述时延耦合到与所述时 延值的下一个次高位位置相对应的时钟存储器。

最后，在第五步骤S5中，当所述新时延到期时，生成时延信号。

图3示出了本发明第三方面提供的延迟多个数据包的装置10的一种可能实现方式的 框图。

图3中的装置10包括根据本发明第一方面中第一至第八任一种实现方式提供的时延 计时设备1。所述装置10还包括数据接口11。所述时延计时设备1和所述数据接口11均 被耦合到处理单元12，所述处理单元12用于通过所述时延计时设备1延迟通过所述数据 接口11接收到的数据包。

在图3所示的本发明第三方面提供的装置10的第一可能实施例中，所述装置10包 含在嵌入式计算机中。在这种实施例中，所述时延计时设备1包含在由所述嵌入式计算 机的操作系统执行的计算机程序产品中。

在图3所示的本发明第三方面提供的装置10的第二可能实施例中，所述装置包括网 桥，所述数据接口11包括以太网接口。

在图3所示的本发明第三方面提供的装置10的第三可能实施例中，所述装置包括网 络交换机。

在第四可能实施例中，图3所示的本发明第三方面提供的装置10包括网络路由器。

在图3所示的本发明第三方面提供的装置10的第五可能实施例中，所述数据接口11 包括令牌环接口11、FDDI接口11、无线接口11或它们的组合。

在图3所示的本发明第三方面提供的装置10的第六可能实施例中，所述装置10可 作为如计算机程序产品被嵌入到网络服务器中。

图4示出了根据本发明第一方面中所述时延计时设备的第八实现方式提供的时延计 时设备1的第二可能实现方式的框图。

不同于图1中的时延计时设备1，在图4中的时延计时设备1中，所述时延时钟2包 括3a、3b和3c三个时钟存储器，每个时钟存储器具有11个存储块13-i，前10个存储块 中的每个存储块13-i对应十进制数字0–9中的一个数字，第11个存储块13-i是附加存 储块。所述第一时钟存储器3a对应十进制数值的百位。所述第二时钟存储器3b对应十进 制数值的十位。最后，所述第三时钟存储器3c对应十进制数值的个位。

所述时延时钟2还包括时钟逻辑单元14与15a、15b和15c三个指针。所述第一指针 15a指向所述第一时钟存储器3a的第一存储块13-i，其中，所述第一时钟存储器3a对应 实际时延时钟值的百位，所述第一存储块13-i对应十进制数字0。所述第二指针15b指向 所述第二时钟存储器3b的第十存储块13-i，其中，所述第二时钟存储器3b对应所述实际 时延时钟值的十位，所述第十存储块13-i对应十进制数字9。最后，所述第三指针15c指 向所述第三时钟存储器3c的第三存储块13-i，其中，所述第三时钟存储器3c对应所述实 际时延时钟值的个位，所述第三存储块13-i对应十进制数字2。在此星座图中，所述指针 15a–15c描绘了实际时延时钟值92。

在这种实施例中，可如下表示实际时延时钟值386：所述第一指针15a指向所述第一 时钟存储器3a的、对应十进制数字3的第四存储块13-i；所述第二指针15b指向所述第 二时钟存储器3b的、对应十进制数字8的第九存储块13-i；所述第三指针15c指向所述 第三时钟存储器3c的、对应十进制数字6的第七存储块13-i。

图4所示的时延计时设备1与图1所示的时延计时设备1之间的不同之处还在于所 述时延存储器4包括多个链表。根据本发明的一个实施例，每个包含时延5–5e和5-i的 存储块13-i与一个链表相关联，其中，当与包含存储块13-i的时钟存储器3、3a、3b和 3c相对应的指针被增量到指向所述存储块13-i时，需要关注所述时延5–5e和5-i。因 此，链表16a和16b并不是与每个存储块都有关联。在另一实施例中，如链表16a和16b 中的一个单一链表即使为空，也与每个存储块13-i相关联。

相应地，图4中的时延存储器4包括16a和16b两个链表，用于存储多个时延，其 中，所述第一链表16a包括5a、5b和5c三个时延，所述第二链表16b包括5d和5e两个 时延。

链表式构造是用于有效地组织电子存储器中的项目。一个链表中包括至少一个第一 元素。所述第一元素包括值或净荷以及指向另一元素的指针。如果链表中没有第二元素 加入，则所述第一元素的指针不指向任何地方(空指针)。如果链表中加入了第二元素， 所述第一元素的指针更新到指向所述第二元素，所述第二元素的指针不指向任何地方。 这样，可根据链表中每个元素各自的指针对链表中的所有元素进行有效迭代，直至到达 空指针。

图4中，所述时延5a–5e分别包括时延时间余数17，又称净荷，以及指向所述链表 16a和16b中下一个时延5a–5e的时延指针18。链表16a和16b中最后一个时延的时延 指针18为空指针，不指向任何地方。

进一步地，所述第一链表16a与所述第二时钟存储器3b的、对应十进制数字1的第 二存储块13-i相关联；所述第二链表16b与所述第一时钟存储器3a的、对应十进制数字 6的第七存储块13-i相关联。因此，图4中的时延计时器1需要对5个时延进行计时。这 5个时延中，当指针15a被增量到指向所述第一时钟存储器3a的、对应十进制数字6的 第七存储块13-i时，需关注时延5d和5e。当指针15b被增量到指向所述第二时钟存储器 3b的、对应十进制数字1的第二存储块13-i时，需关注其余三个时延5a、5b和5c。

在另一个较佳实施例中，所述时延时钟2包括5个以上或以下的时延，所述时延存 储器4包括2个以上或以下的链表16a和16b。在一个较佳实施例中，对于每个存储块 13-i，即使时延5、5a、5b和5c均未与存储块13-i相关联，所述时钟存储器4也包括一 个链表。

最后，图4中的时延逻辑单元6用于通过时延信号19表示时延到期。

在根据本发明第一方面中所述时延计时设备1的第八实现方式提供的时延计时设备1 的第二可能实现方式中，所述时延计时设备1使用三个十进制数字计数实际时延时钟值 并管理所述时延5–5e和5-i。进一步地，所述时延时钟的基本时间间隔为1ms，而包含 所述时延计时设备的个人计算机运行的系统时钟为1GHz。

所述时延逻辑单元6用于通过将时延与相应时钟存储器3–3c的相应存储块13-i相 关联来添加新时延。

例如，如果重启所述时延时钟2，则所述时延时钟2从“000”开始计数。例如，如 果将值为539ms的时延5添加到所述时延时钟设备1中，所述时延逻辑单元6会将该时 延与所述第一时钟存储器3a的第六存储块13-i相关联，其中，所述第一时钟存储器3a 对应所述时延时钟值的百位，所述第六存储块13-i对应十进制数字5。进一步地，所述时 延逻辑单元计算待添加到所述时延计时器1中的时延的时延值的余数。这可通过从所述 时延值539中减去与所述时延相关联的百位值500完成，在该示例中为539–500。最 后，所述时延逻辑单元将所述时延，如5–5e和5-i中的一个，存储到所述时延存储器4 中，其中，所述时延包括带有值为39ms的余数17。例如，如果基本时间间隔为1毫 秒，所述时钟逻辑单元14会将所述第三指针15c每毫秒增量一次，将所述第二指针15b 每10毫秒增量一次，将所述第一指针15a每100毫秒增量一次。

当第一指针15a被增量到指向所述第一时钟存储器3a的、对应十进制数字5的第六 存储块13-i时，所述时延逻辑单元6将所述时延与所述第二时钟存储器3b的、对应十进 制数字3的第四存储块13-i相关联，并将带有值为9的新时延余数17存储到所述时延。

因此，当所述第二指针15b被增量到指向所述第二时钟存储器3b的、对应十进制数 字3的第四存储块13-i时，所述时延逻辑单元6将所述时延与第三时钟存储器3c的、对 应十进制数字9的第十存储块13-i相关联，并将带有值为0的余数17存储到所述时延。

最后，当所述第三指针15c被增量到指向第三存储器3c的、对应十进制数字9的第 十存储块13-i时，所述时延逻辑单元6输出时延信号19，表示所述时延时间已到期。对 该时延进行计时所需的计算只包括三种，每种计算均在相应指针到达与所述时延相关联 的存储块13-i时发生。在该示例中，在输入如5–5e和5-i中的一个新时延之前，重设所 述时延时钟。在下一个以十进制呈现的示例中，添加如5–5e和5-i中的一个时延，所述 时延的时延值为995ms，而如图4中指针15a–15c所示，实际时延时钟值为“092”。 该示例也将阐明为何需要所述附加的第十一存储块13-i。

以十进制为例，如图4所示，每一个时钟存储器3a、3b和3c均包括总共10个存储 块13-i和一个附加存储块13-i，即第十一存储块13-i。

当将时延值为“995”ms的时延加入到所述时延存储器4时，所述时延与代表所述时 延时钟值的百位的第一时钟存储器3a相关联。为计算出所述新时延需要关联的存储块 13-i，所述时延逻辑单元6计算所述时延值的十位和个位与所述实际时延时钟值的十位和 个位之和，并将百进位添加到所述新时延的时延值的百位值中。在此示例中，所述时延 值的十位和个位为“95”，所述实际时延时钟值的十位和个位为“92”。两者之和等于 187。这样，添加一个进位到所述时延值的百位9。因此，所述时延值的百位为10，所述 新时延与所述第一时钟存储器3a的、对应十进制数字10的所述附加的第十一存储块13-i 相关联。所述第一指针15a实际上是指向所述第一时钟存储器3a的、对应十进制数字0 的第一存储块13-i，因此，需要所述附加的第十一存储块13-i。进一步地，将所述余数 “87”存储到所述时延存储器4中。当所述第一指针15a在1000ms后被增量到指向所述 第一时钟存储器3a的、对应十进制数字10的所述附加的第十一存储块13-i时，所述时 延与所述第二存储器3b的、对应十进制数字8的第九存储块13-i相关联。当所述第二指 针15b在另一80ms后被增量到指向所述第二时延存储器3b的、对应十进制数字8的第 九存储块13-i时，所述时延与第三时延存储器3c的、对应十进制数字7的第八存储块 13-i相关联。最后，所述第三指针15c在另一7ms后被增量到指向第三时延存储器3c 的、对应十进制数字7的第八存储块13-i。此时，将所述时延从所述时延存储器4中移 除，所述时延逻辑单元通过时延信号19表示所述时延已到期。

在根据本发明第一方面中所述时延计时设备的第八实现方式提供的时延计时设备1 的第三可能实现方式中，所述时延计时设备使用的基本时间间隔为1/10毫秒。

在根据本发明第一方面中所述时延计时设备的第八实现方式提供的时延计时设备1 的第四可能实现方式中，所述时延计时设备使用的基本时间间隔为10毫秒。

图1和4中所示的时延计时设备1还有其他可能的实现方式。例如，在另一可能的 实现方式中，所述时延计时设备使用二进制、八进制、十六进制或其他数字系统。

图5示出了连续三个时间点上四个时钟存储器的状态的框图。第一时间点是实际时 延时钟值为1092的时间点。第二时间点是所述实际时延时钟值为2000的时间点。最 后，第三时间点是所述实际时延时钟值为2080的时间点。图5示出了在所述三个时间点 上的3a、3b、3c和3d四个时钟存储器。时钟存储器3d对应时延时钟值的千位。时钟存 储器3a对应所述时延时钟值的百位。时钟存储器3b对应所述时延时钟值的十位。最后， 时钟存储器3c对应所述时延时钟值的个位。

为所述四个时钟存储器3a、3b、3c和3d中的每一个分别提供一个指针15a、15b、 15c和15d。在第一时间点上，所述指针15d指向所述时钟存储器3d的、对应十进制数字 1的第二存储块13-i。所述指针15a指向所述时钟存储器3a的、对应十进制数字0的第 一存储块13-i。所述指针15b指向所述时钟存储器3b的、对应十进制数字9的第十存储 块13-i。最后，所述指针15c指向所述时钟存储器3c的、对应十进制数字2的第三存储 块13-i。

在第二时间点上，所述指针15d指向所述时钟存储器3d的、对应十进制数字1的第 二存储块13-i。所述指针15a指向所述时钟存储器3a的、对应十进制数字10的第十一存 储块13-i。所述指针15b指向所述时钟存储器3b的、对应十进制数字0的第一存储块13- i。最后，所述指针15c指向所述时钟存储器3c的、对应十进制数字0的第一存储块13- i。

在第三时间点上，所述指针15d指向所述时钟存储器3d的、对应十进制数字1的第 二存储块13-i。所述指针15a指向所述时钟存储器3a的、对应十进制数字10的第十一存 储块13-i。所述指针15b指向所述时钟存储器3b的、对应十进制数字8的第九存储块13- i。最后，所述指针15c指向所述时钟存储器3c的、对应十进制数字0的第一存储块13- i。

在所述第一时间点和所述第二时间点之间经过908个基本时间间隔。在所述第二时 间点和所述第三时间点之间经过80个基本时间间隔。

图5示出了在所述第一时间点上添加时延的处理方式，其中，所述时延的时延值为 995。时延值1对应所述时延计时器1的基本时间间隔。在实际时延时钟值为1092的情 况下，将所述新时延添加到所述时延计时器1。为确定所述新时延需要耦合到的存储块 13-i，首先要确定所述时延值的非零最高位。时延值为995时，第三位被确定为非零最高 位。进一步地，计算所述时延值的其余位即十位和个位与所述实际时延时钟值的其余位 之和，在此示例中为95+92。两者之和等于187。由于两者之和大于99，需将进位100 与所述时延值的第一位即非零最高位的值相加，在此示例中为900+100＝1000。因此， 在所述指针15a在所述第一时间点上指向的存储块13-i之前，需为所述新时延添加10个 存储块13-i，即1000/100＝10。因此，将所述新时延耦合到所述时钟存储器3a的第十一 存储块13-i，其中，所述时钟存储器3a对应所述时延时钟值的百位。当所述时延被耦合 到所述第十一存储块13-i时，会存储带有值为87的第一余数17，且该第一余数17被耦 合到所述第十一存储块13-i。

在第二时间点上，所述指针15a被增量到指向所述时钟存储器3a的、对应十进制数 字10的第十一存储块13-i。此时，再次对带有值为87的所述第一余数17进行处理。通 过减去所述实际时延时钟值的十位和个位即80，计算出第二余数17，即87–80＝7。由 于所述第一余数的十位等于8，因此将带有值为7的所述第二余数17耦合到与所述指针 15b在第二时间点加8处所指向的位置相对应的时钟存储器13-i，在此示例中为对应十进 制数字8的第九存储块13-i。

在第三时间点上，所述指针15b被增量到指向对应十进制数字8的第九存储块13-i。 此时，再次对带有值为7的所述第二余数17进行处理。由于个位是所述时延时钟值和所 述时延值的最低位，因此不需要计算第三余数。这样，由于所述第二余数的个位等于7， 因此，将所述时延耦合到与所述指针15c在第三时间点加7处所指向的位置相对应的时钟 存储器13-i，在此示例中为对应十进制数字7的第八存储块13-i，并将余数存储为0。

在图5未示出的第四时间点上，另外7个基本时间间隔后，所述指针15c指向对应十 进制数字7的第八存储块13-i。将所述时延从所述存储块中移除，并针对所述时延生成时 延信号19。

图6示出了时钟存储器和链表的框图。在图6中，时延时钟2有3a、3b和3c三个时 钟存储器。所述时钟存储器3a、3b和3c分别包括多个存储块13-i。所述时钟存储器3a 中的最上层存储块13-i以放大的存储块13-i详细示出，所述放大的存储块13-i包括头指 针HEAD_PTR和尾指针TAIL_PTR。所述头指针HEAD_PTR指向第一链表16c的第一时 延5-i。所述尾指针TAIL_PTR指向所述第一链表16c的最后一个时延5-i。所述链表16c 包括组成一排的8个时延，其中，所述第一时延5-i指向(用箭头表示)第二时延。进一 步地，连续时延5-i中的每一个时延都指向同排中的下一个时延5-i，直至到达最后一个时 延5-i。

图6示出其他三个链表，即16d、16e和16f。第二链表16d中五个时延5的组合方 式与所述第一链表16c相同。第三链表16e中三个时延5的组合方式也与所述第一链表 16c相同。最后，第四链表16f中十一个时延5的组合方式也与所述第一链表16c相同。

所述第二链表的最后一个时延5-i以放大的时延5-i详细示出，所述放大的时延5-i包 括两个块，第一块示出了余数17，第二块示出了指向链表中下一个时延的指针18。