CN1306773C

CN1306773C - 使用缓存来维护分组顺序的方法和系统

Info

Publication number: CN1306773C
Application number: CNB2004100381029A
Authority: CN
Inventors: 阿洛科·库马尔; 拉杰·亚瓦特卡尔
Original assignee: Intel Corp
Current assignee: Intel Corp
Priority date: 2003-05-28
Filing date: 2004-04-28
Publication date: 2007-03-21
Anticipated expiration: 2024-04-28
Also published as: ATE373369T1; EP1629644B1; TWI269163B; CN1574785A; EP1629644A1; TW200500858A; WO2004107684A1; DE602004008911D1; DE602004008911T2; US20040240472A1

Abstract

本发明描述了一种使用缓存来维护分组顺序的方法和系统。在接收元件处接收作为序列一部分的多个分组。由一个或多个处理模块对这些分组进行处理。然后，重排序元件将所述序列的多个分组排序，以确保将这些分组以与其被接收到时相同的顺序发送。当在重排序元件处接收到序列的分组时，重排序元件判断所接收的分组是不是序列中要被发送的下一分组。如果是，则发送该分组。如果不是，则当所述分组能装入本地存储器时，重排序元件将所述分组存储在所述本地存储器中。否则，将所述分组存储在非本地存储器中。当所存储的分组是序列中要被发送的下一分组时，将所存储的分组取回并发送。

Description

使用缓存来维护分组顺序的方法和系统

技术领域

本发明的实施例涉及分组排序领域，更具体地涉及使用缓存来维护分组顺序。

背景技术

在某些系统中，分组排序标准要求一个流的多个分组以与其到达系统相同的顺序离开该系统。一种可能的解决方案是使用异步插入，同步去除(Asynchronous Insert，Synchronous Remove，AISR)数组。当接收到每个分组时，都给其分配一个序号。该序号可以是对到达系统的所有分组全局地维护的，或者可以是对每个端口或每个流而分开地维护的。

所维护的AISR数组是共享存储器(例如SRAM)，并由分组序号进行索引。对于每个流，都有一个单独的AISR数组。当分组处理流水线完成了对特定分组的处理时，该流水线将该分组传递到下一阶段，或重排序模块。重排序模块用AISR数组来存储乱序分组，并按所分配的序号的顺序来挑选分组。

这种设置的一个问题在于，当流中的下一分组还未准备好被处理时，系统必须继续轮询(poll)AISR列表。还存在存储器访问所带来的延迟，所述存储器访问是按所需顺序在流中对准备好并等候处理的分组进行取回所需的访问。

发明内容

综上，本发明的目的在于提供使用缓存来维护分组顺序的方法、装置和系统。

本发明所提供的方法包括在重排序元件处接收分组，该分组是要被按顺序发送至下一网络目的地的分组序列的一部分，所述方法还包括判断所接收的分组是不是所述序列中要被发送的下一分组，如果是，则发送所接收的分组，而如果不是，则：判断所接收的分组是否能装入本地缓存存储器中；如果所接收的分组能装入所述本地缓存存储器中，则将所接收的分组存储在所述本地缓存存储器中；如果所接收的分组不能装入所述本地缓存存储器中，则将所接收的分组存储在非本地存储器中。并且，当所存储的分组是序列中要被发送的下一分组时，将所存储的分组取回并发送。

本发明所提供的装置包括：处理模块，对从网络接收到的一个序列的多个分组进行处理；重排序元件，其耦合到所述处理模块，在向下一网络目的地发送之前对所述序列的多个分组进行重排列；本地缓存存储器，其耦合到所述重排序元件，存储一个或多个用于将分组重排序的数组；以及非本地存储器，其耦合到所述重排序元件，存储一个或多个用于在所述本地缓存存储器装满时将分组重排序的数组。

本发明所提供的系统包括：交换结构和网络处理器，所述网络处理器经由交换结构接口而耦合到所述交换结构，所述网络处理器包括：处理模块，对从网络接收到的一个序列的多个分组进行处理；重排序元件，其耦合到所述处理模块，在向下一网络目的地发送之前对所述序列的多个分组进行重排列；本地缓存存储器，其耦合到所述重排序元件，存储一个或多个用于将分组重排序的数组；以及静态随机访问存储器，其耦合到所述重排序元件，存储一个或多个用于在所述本地缓存存储器装满时将分组重排序的数组。

综上，本发明实现了使用缓存来有效地维护分组顺序的方法、装置和系统。

附图说明

参照以下用来说明本发明实施例的说明书和附图，可以最好地理解本发明。在附图中：

图1是一个框图，示出了包含本发明的系统的一般实施例。

图2是一个流程图，示出了本发明实施例的方法。

图3是一个框图，示出了一个合适的计算环境，在该环境中可以实施本发明的某些方面。

具体实施方式

以下描述了使用缓存来维护分组顺序的系统和方法的实施例。在以下描述中，阐述了许多具体细节。然而应该理解到，没有这些具体细节也可以实施本发明。在其它情况下，没有详细示出公知的电路、结构和技术，以免妨碍对此描述的理解。

在整个本说明书中所提到的“一个实施例”或“实施例”的意思是，所描述的与本发明有关的特定特征、结构或特性包括在本发明的至少一个实施例中。从而，在整个本说明书中多处出现的说法“在一个实施例中”或“在实施例中”不一定都指同一实施例。此外，所述的特定特征、结构或特性可以用任何合适的方式结合在一个或多个实施例中。

参照图1，该框图示出了本发明一个实施例的网络处理器100。本领域普通技术人员将会意识到，网络处理器100可以包括比图1中所示的更多的组件。然而，不需要为了将实施本发明的说明性实施例公开而示出所有这些一般的传统组件。在一个实施例中，将网络处理器经由交换接口耦合到交换结构(switch fabric)。

网络处理器100包括从网络接收分组的接收元件102。所接收的分组可以是分组序列的一部分。网络处理器100包括一个或多个处理模块104。这些处理模块对接收到的分组进行处理。某些处理模块可能按适当的顺序来处理一个序列的多个分组，而其它处理模块可能乱序地处理这些分组。

处理分组之后，重排序元件106将属于一个序列的多个分组按适当的顺序排序。当重排序元件106从处理模块接收到分组时，其判断接收到的分组是不是序列中要被发送的下一分组。如果是，则发送元件108将所述分组发送或排队准备发送。如果不是，则重排序元件106判断所述分组是否能装入本地缓存存储器110中。如果是，则将所述分组存储在本地缓存存储器110中。否则，将所述分组存储在非本地存储器112中。在一个实施例中，非本地存储器112是静态随机访问存储器(SRAM)。在一个实施例中，网络处理器包括耦合到处理模块以存储数据的动态随机访问存储器(DRAM)。

当所存储的分组是序列中要被发送的下一分组时，该分组由重排序元件106从存储器中取回，并由发送元件108发送。当重排序元件106从本地缓存存储器110中取回要被发送的分组时，重排序元件106将存储在非本地存储器112中的分组拷贝到本地缓存存储器110中。

在一个实施例中，当属于一个序列的每个分组进入接收元件102时，都给了该分组一个序号，以便标记该分组，用于重排序。在处理模块104处理分组之后，重排序元件106将这些分组插入数组中。在一个实施例中，所述数组是异步插入，同步去除(AISR)数组。分组插入数组中的位置是基于分组序号的。例如，将序列中的第一个分组插入数组中的第一个位置，将序列中的第二个分组插入数组中的第二个位置，等等。重排序元件106按顺序从数组中取回分组，而发送元件108将分组发送给下一个网络目的地。

在一个实施例中，分组排序的实现假定存储器中的AISR数组足够大，使得序号通常不应循环，并且新的分组不应因此而覆写旧的但仍有效的分组。然而，如果发生了这样的情况，则重排序元件不应进行无限长的等待。因此，在一个实施例中，分组所携带的序号所具有的位(bit)数比存储器中用来表示最大序号的位数(max_seq_num)更多。这将会允许识别AISR数组中的任何循环。如果一个分组到达，使得其序号大于或等于(expected_seq_num+max_seq_num)(expected_seq_num是所预期的序号)，则重排序元件停止接受任何新分组。同时，如果存在具有expected_seq_num的分组，则其将被处理或被假定为丢弃，然后将会增加expected_seq_num。继续此过程，直到已到达的分组能装入AISR数组中。此后，重排序元件将会开始接受新的分组。应该注意的是，实践中不应出现此状态，存储器中的最大序号应该足够大以使得这种情况不会出现。

在一个实施例中，如果在分组处理期间丢弃了一个分组，则将通知发送给重排序元件。此通知可以是所述分组的一个桩(stub)。在一个实施例中，如果在分组处理期间生成了新的分组，则可以对该新分组进行标记，以向重排序元件表明不需要对该新分组进行排序。在一个实施例中，如果在分组处理期间生成了新的分组，则该新分组与生成该新分组时所依据的那个分组共享同一序号。所述分组将会具有共享的数据结构，以表明该序号的拷贝数。重排序元件将会进行如下假定，即，仅当序号具有多个拷贝的分组的所有拷贝都到达时，所述分组才到达。

为了说明的目的，以下是用于重排序元件的示例性伪代码：Function：receive_packet()seq_num＝Extract sequence number from the packet；if(seq_num＝＝expected_seq_num)

{

process packet；

expected_seq_num++；

clear entry corresponding to seq_num from local memory

and SRAM AISR Array；

read_from_SRAM()；

}else

{

if(seq_num＜(expected_seq_num+N))

{

store seq_num in corresponding local memory AISR

Array；

look_for_head()；

}

else

{

store seq_num in corresponding SRAM AISR Array；

if(seq_num＞max_seq_num_in_SRAM)

max_seq_num_in_SRAM＝seq_num；

look_for_head()；

}

}Function：look_for_head()if(entry at expected_seq_num is not NULL)

{

process expected_seq_num；

expected_seq_num++；

clear entry corresponding to seq_num from local memory

and SRAM AISR Array；

read_from_SRAM()；

}Function：read_from_SRAM()

{

if(expected_seq_num％B＝＝0)

{

∥perform block_read_ifnessary

if((max_seq_num_in_SRAM！＝-1)&

(max_seq_num_in_SRAM＞(expected_seq_num+N))_

block read from SRAM AISR Array from

(expected_seq_num+N)to(expected_seq_num+N

+B)；

else

max_seq_num_in_SRAM＝-1；

}

函数“receive packet”从分组处理模块接收分组，并且如果该分组是序列中要被发送的下一分组，则处理该分组。否则，如果所述分组能装入本地存储器中的AISR数组中，则将所述分组插入本地存储器中AISR数组中的适当位置。如果所述分组不能装入本地存储器中的AISR数组中，则将所述分组存储在SRAM中的AISR数组中。

函数“look for head”查找本地存储器中AISR数组的顶部(head)处的分组。如果所述分组在那里，则将该分组处理并发送。

函数“read from SRAM”从SRAM中的AISR数组中读取分组。然后，当对来自本地存储器中AISR数组的分组进行处理时，可将所读取的分组拷贝到本地存储器中。

图2示出了本发明一个实施例的方法。在200，在重排序元件处接收分组，该分组是要被发送的分组序列的一部分。在202，对接收到的分组是不是序列中要被发送的下一分组进行判断。如果是，则在204，发送所述分组。如果否，则在206，对所述分组是否能装入本地缓存存储器中进行判断。在一个实施例中，对所述分组是否能装入本地缓存存储器中的AISR数组中进行判断。如果所述分组能装入本地缓存存储器中，则在208，将所述分组存储在本地缓存存储器中。如果所述分组不能装入本地缓存存储器中，则在210，将所述分组存储在非本地存储器中。在一个实施例中，如果接收到的分组不能装入本地缓存存储器中，则将该接收到的分组存储在SRAM中。在一个实施例中，当所存储的分组被判断出是序列中要被发送的下一分组时，将该所存储的分组取回并发送。

在一个实施例中，将分组存储在本地缓存存储器中的AISR数组中。当该分组到达AISR数组顶部时，将该分组取回并发送。然后，可将非本地存储器中AISR数组顶部的分组拷贝到本地缓存存储器中的AISR数组。

图3是一个框图，示出了一个合适的计算环境，在该环境中可以实施本发明的某些方面。在一个实施例中，上述方法可以在计算机系统300上实现，计算机系统300包括组件302-312，其中包括经由总线308彼此耦合的处理器302、存储器(memory)304、输入/输出设备306、数据存储设备(data storage)312和网络接口310。这些组件执行其本领域内公知的传统功能，并设有用于实现本发明的装置。总体上，这些组件表示更广的硬件系统范畴，其包括但不限于通用计算机系统和专用分组转发设备。应该意识到，可以对计算机系统300的各种组件进行重新设置，本发明的某些实现可能既不需要也不包括以上所有组件。此外，在系统300中可以包括另外的组件，例如另外的处理器(例如数字信号处理器)、存储设备、存储器，以及网络或通信接口。

本领域技术人员将会意识到，用于实现本发明方法实施例的内容，例如计算机程序指令，可以由任何机器可读介质来提供，所述机器可读介质可以存储包含本发明的系统所可以访问的数据，作为存储器的一部分或存储器的补充，所述介质包括但不限于卡式磁带(cartridge)、磁带、闪存卡、DVD、随机访问存储器(RAM)、只读存储器(ROM)等。在这点上，所述系统被配备为用本领域内公知的方式与这种机器可读介质通信。

本领域技术人员还将会意识到，可以从任何能够存储用于实现本发明方法实施例的内容、并能够将所述内容传送给网络处理器100的外部设备，将所述内容提供给网络处理器100。例如，在本发明一个实施例中，网络处理器100可以连接到一个网络，而所述内容可以存储在该网络中的任何设备上。

虽然根据若干实施例对本发明进行了描述，但本领域普通技术人员将会认识到，本发明并不限于所描述的实施例，而是可以用所附权利要求的精神和范围之内的修改和变更来实施。从而，应将本说明书看作是说明性的，而非限制性的。

Claims

1.一种用于维护分组顺序的方法，包括：

在重排序元件处接收分组，该分组是要被按顺序发送至下一网络目的地的分组序列的一部分；

判断所接收的分组是不是所述序列中要被发送的下一分组，如果是，则发送所述所接收的分组，而如果不是，则：

判断所接收的分组是否能装入本地缓存存储器中；

如果所接收的分组能装入所述本地缓存存储器中，则将所接收的

分组存储在所述本地缓存存储器中；

如果所接收的分组不能装入所述本地缓存存储器中，则将所接收

的分组存储在非本地存储器中；并且

当所存储的分组是所述序列中要被发送的下一分组时，将所述所存储的分组取回并发送。

2.如权利要求1所述的方法，其中，“如果分组能装入本地缓存存储器中则将该分组存储在所述本地缓存存储器中”包括：如果所述分组能装入所述本地缓存存储器中的异步插入同步去除数组中，则将所述分组存储在所述本地缓存存储器中的异步插入同步去除数组中。

3.如权利要求2所述的方法，其中，“如果分组不能装入本地缓存存储器中则将该分组存储在非本地存储器中”包括：如果所述分组不能装入所述本地缓存存储器中的异步插入同步去除数组中，则将所述分组存储在非本地存储器中的异步插入同步去除数组中。

4.如权利要求3所述的方法，其中，“将分组存储在非本地存储器中的异步插入同步去除数组中”包括：如果所述分组不能装入所述本地缓存存储器中的异步插入同步去除数组中，则将所述分组存储在静态随机访问存储器中的异步插入同步去除数组中。

5.如权利要求3所述的方法，还包括：将位于所述本地缓存存储器中的异步插入同步去除数组顶部的分组取回并发送。

6.如权利要求5所述的方法，还包括：在发送了位于所述本地缓存存储器中的异步插入同步去除数组顶部的分组之后，将位于所述非本地存储器中的异步插入同步去除数组顶部的分组拷贝到所述本地缓存存储器中的异步插入同步去除数组当中。

7.一种用于维护分组顺序的装置，包括：

处理模块，对从网络接收到的一个序列的多个分组进行处理；

重排序元件，其耦合到所述处理模块，在向下一网络目的地发送之前对所述序列的多个分组进行重排列；

本地缓存存储器，其耦合到所述重排序元件，存储一个或多个用于将分组重排序的数组；以及

非本地存储器，其耦合到所述重排序元件，存储一个或多个用于在所述本地缓存存储器装满时将分组重排序的数组。

8.如权利要求7所述的装置，其中，所述非本地存储器是静态随机访问存储器。

9.如权利要求7所述的装置，其中，所述本地存储器和所述非本地存储器存储一个或多个用于将分组重排序的数组包括：所述本地存储器和所述非本地存储器存储一个或多个用于将分组重排序的异步插入同步去除数组。

10.如权利要求7所述的装置，还包括耦合到所述处理模块的接收元件，该接收元件从所述网络接收分组。

11.如权利要求7所述的装置，还包括耦合到所述重排序元件的发送元件，该发送元件将重排序后的分组发送至下一网络目的地。

12.一种系统，包括：

交换结构；以及

如权利要求10所述的装置，其经由交换结构接口而耦合到所述交换结构。

13.如权利要求12所述的系统，其中，所述网络处理器还包括耦合到所述处理模块并用于存储数据的动态随机访问存储器。

14.如权利要求12所述的系统，其中，所述网络处理器还包括耦合到所述处理模块的接收元件，该接收元件从所述网络接收分组。

15.如权利要求12所述的系统，其中，所述网络处理器耦合到所述重排序元件的发送元件，该发送元件将重排序后的分组发送至下一网络目的地。