CN1564989A - Mac地址高速搜索引擎 - Google Patents

Abstract

本发明公开了一种用于在计算机网络系统中存储和搜索计算机节点地址的装置和方法。在一个实施例中，装置包括一个例如为转接器(115)的数据帧转发装置。该转接器(115)包括两个MAC地址表：主MAC地址表(220a)和副MAC地址表(220b)，这两个地址表都用来储存和搜索MAC地址。主MAC地址表(220a)中存储着一些记录，这些记录中包含MAC地址的压缩值。这些记录被储存在一些存储单元中，这些存储单元用MAC地址的压缩值或散列值作为搜索索引。为了能解决由于不同的MAC地址压缩成同一数值而产生的搜索冲突问题，主地址表(220a)中的每个记录都与由副地址表(220b)中的记录组成的一个链串相链接。副地址表(220b)的每一记录中都存储着完整的MAC地址。每个由副地址表(220b)中记录组成的链串都包含一些属于同一散列族的MAC地址。

Description

MAC地址高速搜索引擎

关于版权和商业登记的声明

本专利文件所公开的内容中包含一部分由版权保护的资料。本专利文件表示和/或描述的主题可能是属于编写者的商业登记/或者可能成为编写者的商业登记。如同在专利商标局显示的文档和记录那样，该版权和商业登记的所有人并不反对任何人对该专利公开的内容进行复制，但无论如何也保留所有的版权和商业登记权。

技术领域

本发明涉及计算机网络技术。更具体来讲，本发明涉及在计算机网络中对数据帧和计算机地址进行搜索和转发。

背景技术

一个计算机网络通常包括一组相互连接的计算机装置，这些计算机装置保持通讯链结从而可共享某些资源，其中的共享资源例如为存储设备、外围设备、应用程序、输出装置等。在一个局域网(LAN)中的计算机装置通常通过电缆连接线相互直接连接在一起。出于组网方面的原因，网络中的几个计算机装置可被连接到一个中央连接点上，此处的中央连接点被称为网络集线器。一个集线器通常具有多个端口，每一个端口都与一个或多个装置通信连接，其中的装置例如为一个网络节点、一个转接器(switch)或一个中继器。在本文中，词语“网络节点”指代网络中可以同其它计算机通信的任何装置。集线器从某个端口接收一个源节点发送来的输入信号，并通过一个或多个其它端口将此输入信号发送向某个目的节点。

中继器是一种非常简单的集线器。中继器通过将多个子网合并成一个更大的子网而扩展了网络的范围。中继器增大了网络信号的强度，从而可在更长的距离上发送和接收信号，而不会使信号的品质降低。例如，由于信号从信号源要经电缆传输一段距离才能到达中继器，所以信号的质量会变差。中继器在其内部对减弱的信号进行还原，并将信号通过所有的端口转发出去。这就意味着中继器根本不对数据执行任何处理，而只是接收输入信号并对信号进行重整后立即将它们从所有的端口(除了原始端口之外)发送出去。也就是说，该中继器并不对信号的目的地址进行任何分析，而只是盲目地将信号从所有端口发送出去。

由于中继器将所有的输入信号从每一个端口都发送出去，所以会显著地增大网络的通信量。对于通信量相对较低的网络这还不是一个问题。但是，在通信量相对较高的网络中，通信量小的增加都会显著降低网络的性能。

转接器和网桥是形式更为复杂的集线器，它们克服了中继器所涉及到的那些缺点。与中继器不同，转接器和网桥具有数据帧转发逻辑电路，并在将一个输入信号传输出去之前对信号执行基本的过滤功能。中继器只是简单地将所有的信号从每一个端口转发出去，而转接器和网桥则只转发那些必要的信号，并根据信号的目的地址只将信号发送向适当的端口。

按照以太网的标准，信号是以数据帧的形式在网络中从源节点传送到目的节点的。一个数据帧通常是由几个信息字段组成的，其中包括两个代表数据帧的媒介访问控制(MAC)目的地址以及MAC源地址的字段。MAC源地址指明数据帧的源节点，而MAC目的地址指明数据帧的目的节点。网络中的各个节点都用唯一的一个MAC地址标记，MAC地址是一个48比特长(6个字节)的字符串。六字节长的设备标识号实现了约32太拉(248)个可能的互异MAC地址。

当一个转接器或网桥接收到一个输入数据帧时，转接器或网桥就检查数据帧的目的地址。转接器在其内部存储器中记载了一个关于以往数据帧的数据库。通过利用该数据库(本文称其为地址表)，转接器就可以跟踪转接器的各个端口分别对应的是哪些MAC地址。在接收到数据帧的情况下，转接器查询所说的数据库并确定出是哪个端口与该特定MAC地址相对应。然后，转接器将该数据帧转发向该正确的端口。转接器的工作基本上是检查其对以往数据帧的内部储存记录，并确定出是否将该数据帧转发向其它的端口、或者是滤掉该数据帧。

转接器将一个数据帧转发向正确端口的速度取决于几个因素，这些因素包括：数据帧查询地址表所用的时间；找出数据帧的目的地址所用的时间；以及将数据帧从正确的端口(一个或多个)输出的时间。理想的情况：一个地址表应当具有足够的空间来存储每一个可能的6字节长MAC地址。在此情况下，地址表就包括了一个表目数组，该数组是由所有可能地址的完整列表以及与各个地址对应的端口组成的。这样，在收到一个MAC地址之后，转接器就可以快速地搜索过地址表，确定出应当经那个合适的端口向该MAC地址转发。

但是，如上所述，在这样的地址表中必须要存储约32太拉(248)个可能的MAC地址。在实际工作中，从经济性的角度考虑，拥有一个存储量足以容纳所有六字节MAC地址的数据表的存储器是不现实的。减小地址表所需存储量的一种方法是将地址表中储存的地址变为压缩格式或散列格式。但是，由于一个或多个不同的地址会映射于同一个散列值，所以这会导致在搜索过程中产生冲突。

因而，现有技术中需要一种快速而有效的方法来保存计算机地址转发表。

发明内容

本发明公开了一种用于在计算机网络系统中存储和搜索计算机节点地址的装置和方法。在存储和搜索MAC地址的示例性上下文环境中，所说网络系统被描述成一个以太网系统。该系统包括一个例如为转接器的数据帧转发装置。该转接器包括两个MAC地址表：主MAC地址表和副MAC地址表，这两个地址表都用来储存和搜索MAC地址。

主MAC地址表最好是被存放在转接器的一个外部存储器中，而副MAC地址表则最好是被存储在转接器的一个内部存储器中。主地址表最好是按照外存储器的总线宽度而对数据表目的字长敏感的，且相比于副地址表而具有较低的访问速度和较大的容量。为了提高副地址表的搜索速度，构建了一个在某一带宽上运行的检索模块，其中的带宽对于副地址表所在的存储器而言是优化的。

在本发明的一个方面，主MAC地址表所存储的记录中包含MAC地址。这些记录被储存在一些存储单元中，这些存储单元用MAC地址的压缩值或散列值作为搜索索引。为了能解决由于不同的MAC地址与同一个散列值对应而产生的搜索冲突问题，主地址表中的每个记录都与由副地址表中的记录组成的一个散列族链串相链接。副地址表中的每一记录散列族链串都包含一些MAC地址，这些地址属于同一散列族、或者是被压缩成同一数值的一些MAC地址。

从下文的具体描述，本领域技术人员可对本发明系统的其它目的和优点、以及其应用和工作原理有更为清楚的认识。

附图说明

从下文对本发明优选实施例的描述，本发明其它的目的、对这些目的产生影响的其它特征、以及这些特征所带有的优点将变得到显见，其中的优选实施例表示在附图中，图中用同样的数字标号指代所有的对应部件，对优选实施例的理解应结合下文的附图，在附图中：

图1示意地表示了一个网络系统；

图2是一个示意图，表示了网络系统中的一个转接器器件；

图3表示了一主地址表和一副地址表的优选实施形式；

图4表示了地址存储记录的几个散列族链串；

图5A是一个流程图，描述了为副地址表分配资源的过程；

图5B表示了副地址表的一个第一示例，该副地址表已根据图5A中的过程分配好了；

图5C表示了副地址表的一个第二示例，该副地址表也已根据图5A所示的过程进行了分配；

图6是一个流程图，其表示了转接器器件的数据帧转发机理；以及

图7A-7D是几个流程图，表示了用于对主、副地址表进行搜索和填充的方法。

借助于下文的详细描述，就可以对本发明这些实施例、以及其它的实施例有更好的理解，在下文的描述中，介绍了一个说明性的实施例。

具体实施方式

贯穿下文的描述，附图中所示的优选实施方式和示例应当被看作是示范性的，而不对本发明的装置和方法产生任何的限定作用。

图1示意地表示了一个局域网(LAN)100，其包括多个计算机节点。这些计算机节点总体上用数字标号105指代，且各个节点用数字标号105带上一个字母后缀来表示。在LAN100中还连接了其它的附加设备，例如为打印机、扫描仪、复印机以及诸如多功能外围设备(MFPs)和传真设备等其它装置。根据本文公开的内容，尽管本文描述的原理同样适用于其它类型的网络拓扑结构，但在此处，LAN100被描述成处于以太网布局的环境中。该LAN100还可以包括一个或多个信号转发装置—例如为路由器、中继器等。

每个计算机节点105都向心地连接到一个转接器115上。该转接器115具有多个端口120a-120d(总称为端口120)。转接器115被设计成通过第一端口120接收一个或多个输入数据帧，之后再从一个或多个其它端口将各个数据帧传送出去，这样，数据帧就可以到达其预期的目的地。转接器115包括一个搜索模块，该模块检查数据帧的MAC目的地址并将数据帧转发到正确的端口120，这些内容将在下文作详细的描述。搜索模块最好是用软件指令执行的，这些软件指令储存在转接器115的存储器中。可以理解：此处所述的搜索、转发功能并不限定于由转接器来实现，而是可以由任何合适的网络设备来完成，只要其能执行地址搜索和数据帧转发的逻辑运算即可。

图2示意地表示了应用本发明一种实施方式的转接器115。如上所述，转接器115包括一组典型的端口120，这些端口120与一个或多个计算机节点105(见图1)保持通讯连接。虽然图中所示的转接器115只具有四个端口，但可以理解端口120的数目是可以改变的。如上所述，转接器115具有一个存储器，该存储器中存储了一个搜索模块210，此搜索模块被设置成用于检查和处理输入数据帧的MAC源地址和/或目的地址，以确定出要使该数据帧到达其预期目的地址应当将其转发至哪一个或哪几个端口120。

参见图2，转接器115在其存储器中存放和保存这一主MAC地址表220a，该地址表用于存放MAC地址以及相关的端口标号。转接器115还在存储器中存储保存着一个副MAC地址表220b，此地址表与主MAC地址表220a相链接，并与主地址表协同使用。副MAC地址表220b也用于存储MAC地址以及相关的端口标号。主、副MAC地址表220最好都具有特定的格式，这些内容将在下文详细描述。此处所述的地址表220被用于存储MAC地址，但可以理解：该地址表220也可以用来存储其它格式的网络节点地址。

参见图3，图中表示了主MAC地址表220a的一种优选格式。该主MAC地址表220a是一种数据结构，该数据结构包括多个主记录305，这些主记录以数组的形式排列，从而使得地址表220a中的某个主记录305a后面跟着另一个记录305b，并依次类推。每个主记录305都包括一个用于存储MAC地址(或者是压缩格式、或者是原始格式)的地址字段；一个端口字段，用于存储与该MAC地址相关的端口标号；以及一个链接字段，用于存储一个散列族链接索引，该索引指向副MAC地址表220b中一个对应副记录330的位置，或者是指向一个空链接，这些内容在下文有进一步的描述。每个主记录305中还可以包含与MAC地址有关的其它信息。

主MAC地址表220a最好是用MAC地址的散列转换函数值作为索引，其中的MAC地址被存储在主MAC地址表220a中。在一个优选实施例中，对存储的所有MAC地址都执行一个散列函数运算，且各个MAC地址的散列值被作为存放该MAC地址的那一具体主记录305的定位索引。这样，各个主记录305中的内容就可以通过一个指向该具体主记录305存储位置的主索引进行访问。在这样的情况情况下，主索引的值等于存储在该主记录305中的MAC地址的散列值。

可能出现这样的情况：几个不同的MAC地址可能会映射向同一个散列值，从而，就会有几个MAC地址映射向主MAC地址表220a中的同一个主记录305。这几个映射向同一散列值的MAC地址在本文中称为“属于同一散列族”。因而，例如如果MAC地址100和200都映射向同一散列值，则地址100和200就属于同一散列族。在对主MAC地址表进行索引的过程中，由于两个不同的MAC地址具有相同的主索引值，所以这种情况就会导致冲突情况的产生。产生冲突情况的可能性大小是散列算法以及在散列运算过程中MAC地址压缩量的函数。数据压缩量越大，发生冲突的可能性就越小。尽管压缩宽度可以是小于原始宽度的任何值，但在一个实施例中，MAC地址被散列运算转换成16比特的位宽度。对于压缩成16比特宽度的情况，有65536个可能的散列族。

每个主记录305都可以与副MAC地址表220b中的一个对应副记录330相链接。如果是相链接的，一个主记录305最好是与一由一个或多个副记录330组成的链串相链接，其中的这些副记录330中存储着属于同一散列族的MAC地址，主记录305中存储的MAC地址也属于该散列族。因而，属于同一散列族的MAC地址就被存储在由主、副记录305、330相互链接成的同一散列族链串中。在本文的应用中，词语“散列族链串”指代由至少一个主地址和可能的一个或多个副记录组成的链接串，其中所有相链接记录中存储的地址都属于同一散列族。在该散列族链串中的第一副记录330的存储位置被链串中主记录305的散列族链接字段指明。如果在主记录305中的MAC地址属于一个只包括一个记录的散列族链串，则主记录305就最好是与一个空指针相链接。

主MAC地址表220a的大小最好能至少存储与散列族同等数目的主记录305。在一个实施例中，主MAC地址表220a被设计成存储了至少64k(65536)个主记录305。主MAC地址表最好是存放在转接器115的一个外存储器中。各个主记录305的大小或宽度最好被定为小于或等于外存储器的总线宽度。

图3还示意了主MAC地址表220a和副MAC地址表220b的一种优选格式。副MAC地址表是由一种数据结构组成的，该数据结构包括多个以数组形式排列的副记录330。每个副记录330包括一个用于存储MAC地址的地址字段；一个用于存储与该MAC地址相关的端口标号的端口字段；以及一个散列族链接字段，在该链接字段中存放了一个散列族链接，该散列族链接指明了存储同一族MAC地址的另一个副记录330的位置。在初始阶段，散列族链接字段中是一个空指针。另外，各个散列族链串中的最后一个副记录330最好是与一个空指针相关联，以表明此处是该散列族链串的结束。

副MAC地址表220b最好是放在转接器115的一个内部存储器中。同时，该副MAC地址表220b最好小于主MAC地址表220a。在一个实施例中，该副MAC地址表220b的大小可存储2048个副记录330。

图3表示了主MAC地址表220a和副MAC地址表220b的示例性实施方式，图中这两个地址表都至少部分地被填上了数据。在主MAC地址表220a中，把MAC地址100、200、300、400分别填在主记录305a-305d中。对于副MAC地址表220b，分别将MAC地址A、B、C、D、E、F填充在副记录330a-330g中。副记录330a-330g的索引值分别为1-7。

假设MAC地址100、A、B和C属于同一散列族；MAC地址200、D和E属于同一散列族；MAC地址300、F和G属于同一族；MAC地址400自己为一个散列族。因而，如图4所示，在示例的地址表220a和220b中就有四个独立的散列族链串。

参见图4，第一散列族链串403是由主记录305a和副记录330a、330b和330c串联组成的。如图3所示，在主记录305a中的散列族链接字段中记载了对应副记录330a的索引(1)，该副记录330a是链串中的下一个记录。在该链串中向前推进，副记录330a中的散列族链接字段中包含了副记录330b的索引号(2)。类似地，副记录330b的散列族链接字段中记载了副记录330c的索引(3)—即该散列族链串中的下一个(也是最后一个)记录。最后，副记录330c的散列族链接字段中存放了一个空指针，这代表副记录330c是该散列族链串403的最后一个记录。

类似地，如图4所示，一个第二散列族链串407是由主记录305b和副记录330d和330e组成的，这几个记录以串联关系链接。如图3所示，主记录305b和副记录330d、330e的散列族链接字段中都包含了指向散列族链串407中下一个记录的索引。副记录330e作为链串中最后一个记录而被链接向一个空指针。

如图4所示，主记录305c和副记录330f、330g一起也构成了一个第三散列族链串409。第四散列族链串411仅包括记录305d，该记录305d如其散列族链接字段(图3)中的空值所指示的那样，也被链接向一个空指针。

图5A是一个流程图，表示了为副MAC地址表220b分配资源的过程。在一个起始步骤503中，在转接器115内部存储器中形成一列未被填充的副记录。最好是，该阵列中至少有一个记录被预留为空记录。在一个优选实施例中，用作为一个空指针。在随后的下一个步骤507中，将所有副记录以串联关系链接，从而形成一个资源分配链串，该链串是由链成一串的所有副记录组成的。资源分配链串中的第一个记录被称为起始记录，分配链串中的最后一个记录(不包括空记录)被称为末尾记录。

在步骤509中，转接器115记下资源分配链串的起始记录和末尾记录的存储地址。可以理解，资源分配链串的起始记录和末尾记录的地址是可以随副MAC地址表220b的填充和保持而被改变的。转接器115最好能跟踪此地址改变，从而能始终更新资源分配链串的起始记录和末尾记录的地址。

在步骤511中，资源分配链串的末尾记录被链接向空记录。然后，该资源分配过程就结束了。

在图5B中表示了副地址表220b的一个示例，该地址表是根据上述的资源分配过程进行配置的。图5B表示了一个示例性的副地址表220b，该地址表具有六个副记录，这六个记录用0到5六个数字指代。索引号为0的副记录被预留为空记录。起始记录是索引号为1的副记录，末尾记录是索引号为5的副记录，从而，资源分配链串是由1到5号副记录顺次链接成的。末尾记录被链接向空记录。

可以理解：资源分配链串中的副记录并不需要保持顺序的次序。例如，图5C表示了一个资源分配链串，它是由几个副记录以1、4、5、2和3的次序组成的。在该示例中，记录1为起始记录，记录3为末尾记录。

图6是一个流程图，表示了转接器115的数据帧转发机理。在第一个步骤605中，转接器115从某一特定端口120接收一个输入数据帧。然后，转接器115检查该数据帧的源地址段，以获得该数据帧起源节点的MAC地址的信息(步骤610)。

在步骤615中，转接器115求助于搜索模块210来查询MAC地址表220，并确定出该源地址是否在地址表中(步骤620)。该源地址首先被执行散列运算以获得主搜索索引，该索引用于访问主MAC地址表220a中的一个主记录305。此间的搜索过程在下文将参照图7A-7D作详细描述。

如果该源地址不在MAC地址表220中，则地址表220就用与该MAC源地址相关的信息填充(步骤625)。该信息最好包括：(1)数据帧的源地址；(2)与该源地址对应的端口号；以及(3)任何其它的相关信息：例如该源地址的时龄(age)。例如，假定节点105a(见图1)的MAC地址是100。如果输入数据帧是从节点105a发送来的，则转接器115就将MAC地址100、以及端口120a的标号填入MAC地址表220。以这样的方式，转接器就“记住”了该MAC地址以及对应的端口。

某个特定源地址未在地址表220中出现的原因是不同的。例如，可能是因为转接器115新装到网络中、发信设备是新装到网络中的、或者是该发信设备在最近的时期内保持静默(也就是说该发信设备最近没有发送过数据帧)。

转接器15可利用MAC地址的时龄项作为定期保持MAC地址表大小的措施。例如，如果MAC地址表目的时龄项超过一个设定的时间限度，则转接器就将该表目从MAC地址表中删去。由于只需对很少的表目进行检查，所以将节省存储空间，且可提高访问速度。

如果搜索模块210发现源地址实际上在MAC地址表220中是存在的，则转接器115就从数据帧获得其MAC目的地址(步骤630)。然后转接器115求助于搜索模块210，按照下文中结合图5所描述的方法对MAC地址表220进行查询(步骤635)。然后，根据该MAC目的地址是否存在于MAC地址表220中，数据帧被从合适的端口120(一个或多个)转发出去、或者是按照普通的方式抛弃该数据帧。

例如，如果在MAC地址表220中没有发现该MAC地址，则转接器115就将该数据帧向所有的端口转发，以确保该数据帧能最终到达其接收者处。如果该MAC目的地址在MAC地址表220中被找到了，则转接器115就从该地址表220获取了此目的地址的详细信息，这些信息包括该MAC目的地址与哪一个端口相关联。然后，转接器115从该合适的端口120将数据帧转发出去。

如果该与MAC目的地址相关联的端口与接收到数据帧的端口是同一端口，则转接器115就最好是滤掉该数据帧(即丢弃该数据帧)。该数据帧被丢弃的原因是源节点和目的节点都位于LAN中的同一共享子网内。这样，该数据帧无须经过转接器115就已能被传送到目的地址。

图7A到图7C是几个流程图，表示了搜索模块查询MAC地址表220、以及通过MAC地址表220来“学习”MAC地址信息的过程。转接器115最好包括能执行上述过程的硬件和或软件。参见图7A，在第一个步骤705中，搜索模块210从一个数据帧获得一个MAC地址(“输入地址”)。在以太网标准的环境中，一个示例的数据帧包括几个字段，这些字段包括数据帧的目的地址字段以及源地址字段。该搜索模块210获取MAC地址的方式是公知的。

在步骤710中，搜索模块210对输入的MAC地址执行散列运算，以产生一个主索引。搜索模块最好是将该MAC输入地址散列成一个宽度小于48比特位MAC地址全字长的数据。MAC输入地址可用一个散列函数进行散列运算，其中的散列函数用MAC输入地址的数值输出一个压缩后或散列后的数值。

在步骤715中，搜索模块210利用所说的主索引来定位主MAC地址表220a中的一个主记录305，并检出该主记录305。换言之，MAC输入地址的散列值被用于定位主MAC地址表220a中的一个主记录305。为了便于参照，用主记录305a作为该定位出的主记录。

然后，搜索模块210检查主记录305a，并确定出该主记录305a是空闲的还是已被填充了数据(步骤720)。如果该主记录305a是空的，则就意味着还不存在包含该输入地址的散列族链串。如果是这种情况，则搜索模块210就执行过程B(见图7B)，在该步骤中，搜索模块通过把与该MAC输入地址相关的信息填充到主记录305a，而建立了一个新散列族链串中的第一个链接。

参见图7B，在步骤725中，搜索模块210开始用该MAC地址数据来填充主记录305a。在步骤730中，搜索模块210用MAC输入地址来填充主记录305a的MAC地址字段(见图3)。在步骤735中，搜索模块用与该MAC输入地址对应的端口的标号来填充端口字段(见图3)。在步骤740中，搜索模块210将主记录305a中的链接字段(见图3)设定为空值，这样就表明该主记录305a在当前是其所属特定散列族链串中唯一的一个记录。作为备选方案，链接字段中的数值可以缺省为空值，并在发生变化之前一直保持该空值。以这样的方式，搜索模块就建立起了一个新的散列族链串，且主记录305a是该链串中的第一个(也是唯一一个)主记录305a。然后，此过程就结束了。

再返回到图7A所示的步骤720，搜索模块210可能发现主记录305a中已经填入了数据。这就意味着MAC输入地址所属的散列族链串已经存在了—尽管该链串中的链接数目是未知的。如果是这种情况，搜索模块210就执行过程C，该过程表示在图7C中。

下面参见图7C，图中所示的流程图表示了在主记录305a中已填充数据的情况下搜索模块210的工作过程。在步骤745中，搜索模块将MAC输入地址与存储在记录中的MAC地址(即从表中“提取出的地址”)进行比较，以判断这两个地址是否是相同的。如果输入的地址与提取出的地址实际上是相同的，则就找到了适配。然后，搜索模块210就从该主记录305a获取数据(见步骤747)，过程C结束。

但是，如果输入的MAC地址并不与提取出的地址匹配，则产生了一个冲突情况，过程转向步骤749。这就意味着有其它不同的MAC地址被散列编码成了同样的主索引值。换言之，同一散列族中的两个不同MAC地址都映射向该主记录305a。在步骤749中，搜索模块检查该主记录305a的链接字段，以确定该链接字段是否为空值。

如果该链接字段中的数值的确是空值，则就意味着当前主记录305a是该记录所属的散列族链串中唯一的一个记录，搜索模块210就应当在该散列族链串中再建立一个新的记录。链串中的该新记录将存储当前的MAC输入地址。

然后过程转向步骤751，在该步骤中，搜索模块210利用副地址表220b的资源分配链串(上文已结合图5A-5C进行了讨论)，以选取一个副记录用于存储此MAC输入地址，并将该副记录附加到所说的散列族链串中。被选取出的此副记录被称为“提取出的副记录”。搜索模块210最好是用资源分配链串中的起始记录作为提取出的副记录。

在步骤753中，搜索模块210将与该MAC输入地址相关的适当信息填入到该提取副记录的地址字段和端口字段中。搜索模块210还用一个空值来填充该副记录的散列族链接字段，以指示此提取副记录是该散列族链串中的最后一个链接。

然后，在步骤755中，搜索模块将主记录305a中散列族链接字段的值设置成一个指针，该指针指向提取副记录的存储位置。以这样的方式，主记录305a和提取的副记录就作为同一散列族链串中的两个记录被链接起来了。

在步骤757中，搜索模块对资源分配链串进行更新，以反映出提取的副记录已被新的数据填上了。另外，在资源分配链串中顺序的下一个副记录(在图5B中为2号副记录)被设定为新的起始副记录。之后，此过程就结束了。

再参见图7C中的步骤749，搜索模块210可能会发现主记录305a中并没有存放其所属散列族链接的末尾空值，而是存储了一个指向一副记录的指针。这就表明主记录305a已经被链接向同一散列族链串中的一个或多个副记录。如果情况是这样，搜索模块210就随后转向执行过程D，该过程将结合图7D进行描述。

下面参见图7D，在步骤765中，搜索模块利用主记录305a中存储的散列族链接指针而检出一个副记录(“提取出的副记录”)。该提取的副记录是散列族链串中用于存储MAC输入地址的下一个记录。然后，搜索模块210读取出该提取副记录中存储的MAC地址。在步骤767中，搜索模块判断提取出的地址是否与输入的地址相一致。如果输入地址实际上与提取出的地址是相同的，则就发现了相匹配的情况。然后，搜索模块210就从提取副记录中获取数据(步骤769)，至此过程结束。

但是，如果提取出的地址与输入地址并不相符，则执行过程就转向步骤771。在步骤771中，搜索模块对已提取副记录中的散列族链接字段进行检查，并判断该链接字段是否为空值。如果该链接字段中未包含一个空值，则就意味着还有其它的副记录链接在当前的散列族链串中。如果是这样的情况，搜索模块就利用该散列族链接字段中的散列族链接指针来检出该散列族链串中的下一个副记录(步骤765)。搜索模块循环执行步骤765、767和771，直到在步骤767中找到相匹配的地址或在步骤771中找到空链接指针为止。

返回到步骤771中，如果散列族链接字段中的确包含一个空值，则就意味着所提取出的副记录即为散列族链串的最后一个记录。因而，搜索模块210就应当执行过程：在散列族链串末尾附加另一个记录，用于存储MAC输入地址。

然后，执行过程转向步骤773，在该步骤中，搜索模块210利用副地址表220b的资源分配链串选取一个新的副记录，用于附加到所说的散列族链串上。搜索模块210最好是用资源分配链串中的起始记录作为该新的副记录。

在步骤775中，搜索模块210将与输入的MAC地址相关的适当信息填入到新副记录的地址字段和端口字段中。搜索模块210还用一个空值来填充散列族链接字段，由此来指示现在提取的副记录成为了散列族链串中最后一个链接。

之后，在步骤777中，搜索模块210将散列族链串中前一个副记录(即带有空指针的那个副记录)的散列族链接字段设定为一个指针，该指针指向现在存储着MAC输入地址的新副记录的位置。以这样的方式，就用另一个记录扩展了所说的散列族链串。

在步骤779中，搜索模块210对资源分配链串进行更新，以反映出提取副记录已经被新的数据所填充。另外，在资源分配链串中该提取副记录的后序下一个副记录被设定为新的起始副记录。之后，此过程就结束了。

尽管上文对本发明的示例性实施方式进行了表示和描述，但对于本领域技术人员来说很显然的是：在不偏离本发明设计思想的前提下，对本文所描述的发明可以有多种形式的改动、变型或替换。因而所有这些改动、替换和变型都应当被看作是在本发明的范围内。

Claims (21)

1.一种用于在地址表中查询计算机地址的方法，其中所说计算机地址的字长为n比特，该方法包括步骤：

a.通过对计算机地址进行压缩而获得一个压缩后的地址值，以此产生一个搜索索引，其中该搜索索引的位长为一个第一数目，此数目小于字长n比特；

b.访问一个主地址记录表中与该计算机地址相对应的一主地址记录，对该主地址记录的访问是通过用所说的搜索索引定位出该主地址记录来实现的，其中，主地址记录中包括该计算机地址、与该计算机地址相关的端口号、以及一个链接字，该链接字标明了一个初始副地址记录在一副地址表中的位置；

c.通过如下的过程对搜索索引与主地址记录进行比较

i.对搜索索引进行解压缩而获得一个第一值；

ii.对主地址记录中存储的地址压缩值进行解压缩而获得一个第二值；

iii.将第一值与第二值进行比较；

d.如果第一值不等于第二值，则就通过链接字访问初始副地址记录，其中该初始副地址记录中包括一个未压缩的计算机地址、一个与该完整计算机地址相关的端口号；以及一个链接字，该链接字指向同一散列族中随后的一个副地址记录。

2.根据权利要求1所述的方法，其特征在于：所说主地址记录表存储在转接器的一个外部存储器中。

3.根据权利要求1所述的方法，其特征在于：对计算机地址进行压缩来生成搜索索引的步骤包括将计算机地址从48比特的字长压缩到小于48位的宽度。

4.根据权利要求1所述的方法，其特征在于：对计算机地址进行压缩来生成搜索索引的步骤包括将计算机地址从48比特的字长压缩到16比特的宽度。

5.根据权利要求1所述的方法，其特征在于还包括步骤：将第一值与副记录中的完整计算机地址进行比较。

6.根据权利要求5所述的方法，其特征在于还包括步骤：如果随后的副记录是空的，则用该计算机地址以及与该计算机地址相对应的端口号填充到该后序副记录。

7.根据权利要求6所述的方法，其特征在于还包括步骤：如果随后的副记录是空的，则用随后副地址记录的位置来填充到初始副地址记录。

8.一种用于存储和查询计算机地址的单元，其中所说计算机地址的字长为n比特，该单元包括：

a.一个存储在一第一存储器中的主地址表，第一存储器的总线宽度为第一宽度，该主地址表被配置成存储一组主地址记录，每个主地址记录都包括：各自的一个地址表目，该表目的宽度为第一比特数，其小于固定的字长n；一个与该压缩地址表目相关的端口号；以及一个第一链接字，该链接字将各个主地址记录链接向一个对应的链串，该链串是由一副地址表中的几个副地址记录组成的；

b.一个存储在一第二存储器中的副地址表，第二存储器与所说第一存储器是分开的，副地址表被设置为存储一组副地址记录，每个副地址记录包括：一个完整地址的表目，该表目的宽度为第二比特数，此比特数等于固定字长n；一个与该计算机地址相关的端口号；以及一个链接字，该链接字将每个副地址记录链接向副地址表中的一个对应的副地址记录，从而形成链成一串或多串的副地址记录，其中，每个副地址记录链串中包含的完整地址表目都属于同一个散列族；

c.一个软件搜索模块，其被设计用来存储、访问主地址记录和副地址记录，其中，该软件模块将各个主地址记录存储到一个存储位置中，该存储位置是由对应压缩地址表目的数值的。

9.根据权利要求8所述的存储和查询单元，其特征在于：所说计算机地址是MAC地址。

10.根据权利要求8所述的存储和查询单元，其特征在于：第一存储器的总线宽度为16位。

11.根据权利要求8所述的存储和查询单元，其特征在于：压缩地址表目的位长等于第一存储器的总线宽度。

12.根据权利要求8所述的存储和查询单元，其特征在于：所说存储、查询单元包括一个以太网转接器。

13.根据权利要求12所述的存储和查询单元，其特征在于：第一存储器是转接器的外部存储器。

14.根据权利要求13所述的存储和查询单元，其特征在于：第二存储器是转接器的内部存储器。

15.一种可读取的计算机软件，其存储在一个计算机网络的数据帧转发装置中，该可读取的计算机软件的代码包括一组指令，这些指令指使帧转发装置在一个地址表中查询一个计算机地址，该计算机地址的字长为n，程序指令还使得装置执行如下操作：

a.通过对计算机地址进行压缩而获得一个压缩后的地址值，以此产生一个搜索索引，其中该搜索索引的位长为一个第一数目，此数目小于字长n；

b.访问一个主地址记录表中与该计算机地址相对应的一主地址记录，对该主地址记录的访问是通过用所说搜索索引定位出该主地址记录来实现的，其中，主地址记录中包括该地址的压缩值、与该计算机地址相关的端口号、以及一个链接字，该链接字将主地址链接向一个初始副地址记录，该副地址记录位于一副地址表中；

c.通过如下的过程对搜索索引与主地址记录进行比较

i.对搜索索引进行解压缩而获得一个第一值；

ii.对主地址记录中存储的地址压缩值进行解压缩而获得一个第二值；

iii.将第一值与第二值进行比较；

d.如果第一值不等于第二值，则就通过链接字访问初始副地址记录，其中该初始副地址记录中包括一个未压缩的计算机地址、一个与该完整计算机地址相关的端口号；以及一个链接字，该链接字指向同一散列族中随后的一个副地址记录。

16.根据权利要求15所述的可读取计算机软件代码，其特征在于：所说主地址记录表存储在转接器的一个外部存储器中。

17.根据权利要求15所述的可读取计算机软件代码，其特征在于还包括：一些指令，用于使装置将计算机地址从48比特的字长压缩到小于48位的宽度。

18.根据权利要求15所述的可读取计算机软件代码，其特征在于还包括：一些指令，用于使装置将计算机地址从48比特的字长压缩到16位的宽度。

19.根据权利要求15所述的可读取计算机软件代码，其特征在于还包括：一些指令，用于使装置对第一值与副记录中的完整计算机地址进行比较。

20.根据权利要求19所述的可读取计算机软件代码，其特征在于还包括：一些指令，如果随后的副记录是空的，这些指令使得装置用计算机地址以及与该计算机地址相对应的端口号填充到随后的副记录。

21.根据权利要求20所述的可读取计算机软件代码，其特征在于还包括：一些指令，如果随后的副记录是空的，这些指令使得装置用随后副地址记录的位置填充到所说的初始副地址记录。

Images