基于哈希表和TCAM表的MAC地址硬件学习方法及系统

摘要

本发明公开了一种基于哈希表和TCAM表的MAC地址硬件学习方法及系统，涉及MAC地址学习领域，本发明在没有MAC地址冲突的时候，使用哈希表来存储学习到的MAC地址，哈希表硬件上用SRAM或者DRAM来实现；存在MAC地址冲突时，使用TCAM表来缓存冲突的MAC地址，TCAM表硬件上采用TCAM存储器来实现，由于TCAM硬件上是并行查找，一次搜索即可定位空闲表项，而且TCAM的表项个数就是实际能缓存的冲突的MAC地址个数。本发明在通用的可编程交换芯片上实现，不需专用硬件电路的支持，学习速率较高，占用的内存资源较少，采用通用的算法，应用灵活，能实现冲突概率完全可控。

说明书

技术领域

本发明涉及MAC（Media Access Control，媒体访问控制）地址 学习领域，特别是涉及一种基于HASH（哈希）表和TCAM（Ternary  Content Addressable Memory，三态内容寻址存储器）表的MAC地址 硬件学习方法及系统。

背景技术

随着经济全球化的发展，越来越多的企业分布范围日益扩大，迫 切需要电信运营商提供链路连接，以便将企业各分支机构囊括进来， 组成企业内部的专用网络。在这样的市场需求下，VPLS（Virtual  Private Lan Service，虚拟专用局域网业务）技术应运而生，VPLS技 术结合了以太网技术和MPLS（Multi-Protocol Label Switching，多协 议标签交换）技术的优势，通过运营商提供的IP（Internet Protocol， 网际协议）/MPLS网络连接地域上隔离的多个由以太网构成的LAN （Local Area Network，局域网），实现了对传统LAN功能的仿真， 使它们像一个LAN那样工作。

VPLS通过查找对应VSI（Virtual Switch Instance，虚拟转发实例） 的MAC地址转发表，来指导用户报文的转发，而MAC地址转发表 是通过MAC地址学习功能创建的。因此，MAC地址学习功能是实 现VPLS的关键因素。

MAC地址学习的2个触发条件是：

（1）某个VSI收到源MAC是未知单播地址时；

（2）某个VSI收到一个已知的源MAC地址，但是对应的转发 表项需要更新，例如：接收VP（Virtual Port，VSI中的虚拟交换端口） 发生了变化。

在MAC地址学习中地址冲突是不可避免的问题，原因是MAC 地址有48bit，而VSI根据设备容量的不同取值一般大于10bit（即最 少支持1k个VSI）。理论上如果要避免MAC地址冲突，则需要穷举 所有MAC地址组合情况，至少需要2^58=256P（计算机存储单位， 1Peta=1024T）个表项，显然不可能用硬件来缓存如此大数量级的表 项。

目前解决MAC地址冲突的方法有以下三种：

（1）依赖主控CPU（Central Processing Unit，中央处理器）来 协助解决地址冲突：一种MAC地址软件学习方法，即在主控CPU 上通过实现“冲突链表”算法来解决地址冲突问题。由于主控CPU 通常用来运行复杂的路由协议，本身负担已经较重，因此，非常浪费 宝贵的主控CPU处理资源，而且与MAC地址硬件学习方法相比， 该MAC地址软件学习方法的学习速率比较低。

（2）单哈希表缓存冲突方法：一种MAC地址硬件学习方法， 使用一个哈希表来缓存MAC地址冲突，即通过扩大哈希表的容量， 以降低冲突产生的概率，是一种最简单、最常见的缓存冲突方法。

哈希算法将任意长度的二进制值映射为固定长度的较小二进制 值，以实现数据的压缩，并通过将原始数据打散和离散，以抑制映射 后产生的数据冲突。常用的哈希算法有MD2（Message Digest  Algorithm2，消息摘要算法第二版）、MD5（Message Digest Algorithm 5，消息摘要算法第五版）、CRC（Cyclic Redundancy Check，循环冗 余校验）32等。实际应用中常采用CRC32来作为哈希算法。以64K 地址表为例，将VSI和源MAC用CRC32算法计算出32bit的哈希散 列值，并将32bit结果的高、低16bit异或之后截取低16bit（2^16=64K） 作为索引值，去索引RAM中的表项。如果两个MAC地址16bit离散 值相同，则其中一个MAC地址无法被缓存；此时，只能期望两个 MAC地址CRC32Hash值的bit17不同，并将表项容量由64k扩展 128k，以此来进一步缓解冲突。

单哈希桶缓存冲突方法通过扩展离散值bit数的方法来降低冲突 概率，每增加1bit离散值，需要将冲突表容量扩展一倍，因此对冲突 表资源浪费很大。而且，由于这种办法完全依赖离散值进行表项的定 位，不管如何扩容表项，始终无法缓存离散值完全相同的多个MAC 地址。另外，当MAC地址样本发生变化时，并不能保证系统设计时 所允许的冲突概率。

（3）多桶缓存冲突方法：一种MAC地址硬件学习方法，该方 法使用多个桶来缓解冲突，在一些ASIC（Application Specific  Integrated Circuit，专用集成电路）芯片上实现，即采用硬件电路模拟 多个冲突桶，每个冲突桶具备一定缓存冲突的能力。仍以64k地址表 项为例，用CRC32算法离散MAC地址，并取32bit Hash值的低16bit 作为离散结果，首先使用16bit离散值的低13bit（2^13=8K）去定位 8K个冲突桶，每个冲突桶中有8个冲突表项；然后在当前定位的冲 突桶中，去搜索8个冲突表项中空闲的表项，如果有空闲表项则放入 空表项中；如果没有，则无法缓存冲突。

多桶缓存冲突方法很大程度上解决了单哈希桶无法缓存离散值 相同的MAC地址的问题，而且硬件资源的利用效率也比较高，但是， 该方法需要大量冲突桶协同工作，需要专用的硬件电路的支持，而且 每个冲突桶中空闲表项的搜索方法需要专用的硬件电路来实现搜索 算法，由于其实现的算法并未公开，因此应用不灵活；另外，由于该 方法只利用当前冲突桶中空闲表项资源来缓存冲突，因此，只能缓存 最多8个离散值相同的MAC地址，对更多离散值相同的恶劣情况其 缓存冲突的能力有限。

发明内容

本发明的目的是为了克服上述背景技术的不足，提供一种基于 哈希表和TCAM表的MAC地址硬件学习方法及系统，在通用的可 编程交换芯片上实现，不需专用硬件电路的支持，学习速率较高；占 用的内存资源较少，采用通用的算法，应用灵活，能实现冲突概率完 全可控。

本发明提供的基于哈希表和TCAM表的MAC地址硬件学习方 法，包括以下步骤：

S1、以报文所属的虚拟转发实例号和源MAC地址计算哈希值， 并以哈希值为索引搜索哈希表；

S2、组织搜索TCAM表项的键值：虚拟转发实例号为报文所属 的虚拟转发实例号；MAC地址为报文的源MAC地址；表项满标志 置1，表示在已经学习到的TCAM表项中进行搜索；

S3、判断TCAM表项数据中有效标志是否置位，如果置位，则 转到S4；否则，转到S6；

S4、比较TCAM表项数据中虚拟交换端口是否等于报文接收虚 拟交换端口，如果是，则表项不需要更新，转到S15；否则，表示 TCAM表项需要更新，转到S5；

S5、更新当前TCAM表项数据中虚拟交换端口为报文实际接收 虚拟交换端口，转到S15；

S6、判断哈希表中数据有效标志是否置位，如果置位，则转到 S8；否则，转到S7；

S7、将报文源MAC地址、报文所属虚拟转发实例号和报文接收 的虚拟交换端口存储到当前哈希表项中，表项有效标志置1，转到 S15；

S8、比较哈希表中虚拟转发实例号和MAC地址是否和报文所属 的虚拟转发实例号及源MAC地址相匹配，如果匹配，则表示当前地 址已经在哈希表中学到过，转到S9；否则，转到S11；

S9、比较当前哈希表中虚拟交换端口是否等于报文实际接收虚拟 交换端口，如果相等，则哈希表项不需要更新，转到S15；否则，转 到S10；

S10、更新当前哈希表项中的虚拟转发端口号为报文实际接收虚 拟端口号，转到S15；

S11、产生哈希冲突，组织搜索TCAM表项的键值以寻找空闲 TCAM表项缓存冲突：键值中虚拟转发实例号为0，MAC地址为0， 表项满标志为0，表示在空闲TCAM表项中进行搜索；

S12、判断TCAM数据中有效标志是否置位，如果置位，表示找 到第一个空闲表项，转到S14；否则，转到S13；

S13、TCAM存储器没有空闲表项，放弃学习，转到S15；

S14、将MAC地址缓存到当前空闲TCAM表项中：键值的虚拟 转发实例号填写为报文所属虚拟转发实例号，掩码置1；MAC地址 填写为报文的源MAC地址，掩码置1；表项满标志置1，掩码置1； 数据中虚拟交换端口填写为报文实际接收虚拟交换端口，转到S15；

S15、MAC地址硬件学习流程结束。

在上述技术方案的基础上，步骤S1之前还包括表项初始化的步 骤：判断初始化表项索引是否大于表项最大值，如果是，则返回异常； 否则，判断初始化表项索引值是否位于哈希表索引范围内，如果是， 则初始化哈希表，直接用初始化索引值定位哈希表项，并将表项内容 全部清0；否则，判断初始化表项索引是否为TCAM最后一项，如果 是，则初始化最后一个TCAM表项，键值中所有字段均初始化为0， 掩码为0，数据中的所有字段均赋值为0，表示该表项为TCAM最后 一个表项；否则，将键值中表项满标志清0，掩码置1，表示当前表 项初始状态为空，键值中其余字段清0，掩码清0，数据中表项有效 标志置1，其余字段清0，表示该表项不是最后一个表项，初始化结 束。

在上述技术方案的基础上，步骤S15之后还包括老化的步骤： 判断老化表项索引是否大于表项最大值，如果是，则返回异常；否则， 判断老化表项索引值是否位于哈希表索引范围内，如果是，则老化哈 希表，直接用初始化索引值定位哈希表项，并将表项内容全部清0； 否则，判断老化表项索引是否为TCAM最后一项，如果是，则表示 TCAM最后一项是一个匹配任意键值的表项，结束老化；否则，将键 值中表项满标志清0，掩码置1，其余字段清0，掩码清0，将表项状 态置为空，数据中表项有效标志置1，其余字段清0，表示该表项不 是最后一个表项，老化结束。

在上述技术方案的基础上，所述哈希表存储在SRAM或者 DRAM中。

在上述技术方案的基础上，所述TCAM表项存储在TCAM存 储器中。

本发明还提供一种基于哈希表和TCAM表的MAC地址硬件学 习系统，包括搜索单元、TCAM表项判断单元、哈希表判断单元、哈 希表比较单元和哈希冲突处理单元，其中：

所述搜索单元，用于：以报文所属的虚拟转发实例号和源MAC 地址计算哈希值，并以哈希值为索引搜索哈希表；组织搜索TCAM 表项的键值：虚拟转发实例号为报文所属的虚拟转发实例号；MAC 地址为报文的源MAC地址；表项满标志置1，表示在已经学习到的 TCAM表项中进行搜索；

所述TCAM表项判断单元，用于：判断TCAM表项数据中有效 标志是否置位，如果置位，则比较TCAM表项数据中虚拟交换端口 是否等于报文接收虚拟交换端口，如果是，则不更新表项；否则，更 新当前TCAM表项数据中虚拟交换端口为报文实际接收虚拟交换端 口；如果没有置位，产生哈希表判断触发信号，并发送到哈希表判断 单元；

所述哈希表判断单元，用于：收到哈希表判断触发信号时，判断 哈希表中数据有效标志是否置位，如果没有置位，将报文源MAC地 址、报文所属虚拟转发实例号和报文接收的虚拟交换端口存储到当前 哈希表项中，表项有效标志置1；如果置位，产生比较触发信号，并 发送到哈希表比较单元；

所述哈希表比较单元，用于：收到比较触发信号时，比较哈希表 中虚拟转发实例号和MAC地址是否和报文所属的虚拟转发实例号及 MAC地址相匹配，如果匹配，则表示当前地址已经在哈希表中学到 过，比较当前哈希表中虚拟交换端口是否等于报文实际接收虚拟交换 端口，如果相等，则结束学习；否则，更新当前哈希表项中的虚拟转 发端口号为报文实际接收虚拟端口号，结束学习；如果不匹配，产生 哈希冲突处理触发信号，并发送到哈希冲突处理单元；

所述哈希冲突处理单元，用于：收到哈希冲突处理触发信号时， 组织搜索TCAM表项的键值以寻找空闲TCAM表项缓存冲突：键值 中虚拟转发实例号为0，MAC地址为0，表项满标志为0，表示在空 闲TCAM表项中进行搜索；再判断TCAM数据中有效标志是否置位， 如果置位，表示找到第一个空闲表项，将MAC地址缓存到当前空闲 TCAM表项中：键值的虚拟转发实例号填写为报文所属虚拟转发实例 号，掩码置1，MAC地址填写为报文的源MAC地址，掩码置1，表 项满标志置1，掩码置1，数据中虚拟交换端口填写为报文实际接收 虚拟交换端口，结束学习；如果没有置位，表示TCAM存储器没有 空闲表项，放弃学习。

在上述技术方案的基础上，还包括初始化单元，用于：判断初 始化表项索引是否大于表项最大值，如果是，则返回异常；否则，判 断初始化表项索引值是否位于哈希表索引范围内，如果是，则初始化 哈希表，直接用初始化索引值定位哈希表项，并将表项内容全部清0； 否则，判断初始化表项索引是否为TCAM最后一项，如果是，则初 始化最后一个TCAM表项，键值中所有字段均初始化为0，掩码为0， 数据中的所有字段均赋值为0，表示该表项为TCAM最后一个表项； 否则，将键值中表项满标志清0，掩码置1，表示当前表项初始状态 为空，键值中其余字段清0，掩码清0，数据中表项有效标志置1， 其余字段清0，表示该表项不是最后一个表项，初始化结束。

在上述技术方案的基础上，还包括老化单元，用于：判断老化 表项索引是否大于表项最大值，如果是，则返回异常；否则，判断老 化表项索引值是否位于哈希表索引范围内，如果是，则老化哈希表， 直接用初始化索引值定位哈希表项，并将表项内容全部清0；否则， 判断老化表项索引是否为TCAM最后一项，如果是，则表示TCAM 最后一项是一个匹配任意键值的表项，结束老化；否则，将键值中表 项满标志清0，掩码置1，其余字段清0，掩码清0，将表项状态置为 空，数据中表项有效标志置1，其余字段清0，表示该表项不是最后 一个表项，老化结束。

在上述技术方案的基础上，所述哈希表存储在SRAM或者 DRAM中。

在上述技术方案的基础上，所述TCAM表项存储在TCAM存 储器中。

与现有技术相比，本发明的优点如下：

（1）本发明的MAC地址硬件学习方法，完全在交换芯片上实 现，不需要依赖任何主控CPU的协助，学习速率比较高。

（2）本发明在没有MAC地址冲突的时候，使用哈希表来存储 学习到的MAC地址，哈希表硬件上用SRAM或者DRAM来实现， 容量和带宽上可以做得比较大，首选哈希表来存放地址表项，能充分 利用RAM大容量硬件资源的优势。存在MAC地址冲突时，使用 TCAM表来缓存冲突的MAC地址，TCAM表硬件上采用TCAM存 储器来实现，由于TCAM硬件上是并行查找，一次搜索即可定位空 闲表项，而且TCAM的表项个数就是实际能缓存的冲突的MAC地 址个数，因此，不仅能充分利用TCAM快速并行查找的优势，而且 能实现冲突概率完全可控，此外，由于不用哈希表来缓存冲突的MAC 地址，因此占用的内存资源较少。

（3）本发明在通用的可编程交换芯片上即可实现，不需要专用 硬件电路的支持，采用通用的算法，应用十分灵活。

（4）本发明使用TCAM表来缓存冲突的MAC地址，能缓存的 冲突的MAC地址总量为开辟的TCAM总量减1，冲突概率可控，能 缓存的冲突的MAC地址的个数是确定不变的，不会随着MAC地址 样本的变化而变化，缓存冲突的MAC地址的能力有保障，即使在冲 突最恶劣的情况下，TCAM表仍然能缓存几乎所有的MAC地址冲突。

附图说明

图1是本发明实施例中表项初始化的流程图。

图2是本发明实施例中基于哈希表和TCAM表的MAC地址硬 件学习方法的流程图。

图3是本发明实施例中老化的流程图。

具体实施方式

下面结合附图及具体实施例对本发明作进一步的详细描述。

TCAM是一种三态内容寻址存储器，TCAM中每个bit数据有三 种状态：除了普通的“0”和“1”之外，还有一个“don’t care”（即 不用匹配该bit）状态，所以称之为“三态”。“三态”的功能通过掩 码来实现，即掩码为0，表示“dont’t care”给定的键值；掩码为1， 表示需要精确匹配给定的键值。TCAM的这种特性使其既能完成精确 匹配，也能完成模糊匹配。TCAM的另一个特点就是“并行查找”， 即给定一个键值，则TCAM会同时匹配所有的硬件表项，并且返回 地址索引值最小的那一条表项索引。

本发明实施例采用RAM存放哈希表，作为MAC地址学习的主 存储器，结合TCAM存储器“三态存储”和“并行查找”的特点， 来缓存冲突的MAC地址。在功能划分上，哈希表作为MAC地址的 主存储器，而TCAM表负责完成缓存地址冲突的核心功能。哈希表 和TCAM表互相配合共同完成MAC地址学习的功能，其实现上需 要初始化、地址的学习和地址的老化三者的密切配合才能实现。

哈希表存储在SRAM或者DRAM中，TCAM表项存储在TCAM 存储器中。

参见表1所示，哈希表的数据结构包括虚拟转发实例（Vsi）、 Mac地址、表项有效标志（Valid）和虚拟交换端口（Vp）。

表1、哈希表的数据结构定义表

成员1 成员2 成员3 成员4 虚拟转发实例（Vsi） Mac地址 表项有效标志（Valid） 虚拟交换端口（Vp）

参见表2所示，TCAM表项的数据结构包括键值（Key）和数据 （Data），键值（Key）包括虚拟转发实例（Vsi）、Mac地址和表项满 标志（FlagFull），数据（Data）包括表项有效标志（Valid）和虚拟交 换端口（Vp）。

表2、TCAM表项的数据结构定义表

参见图1所示，本发明实施例中表项初始化的流程如下：

步骤101、判断初始化表项索引是否大于表项最大值，如果是， 则转到步骤102；否则，转到步骤103；

步骤102、初始化表项索引范围超过表项最大值，返回异常，转 到步骤108；

步骤103、判断初始化表项索引值是否位于哈希表索引范围内， 如果是，则转到步骤104；否则，转到步骤105；

步骤104、初始化哈希表，直接用初始化索引值定位哈希表项， 并将表项内容全部清0，转到步骤108；

步骤105、判断初始化表项索引是否为TCAM最后一项，如果是， 则转到步骤106；否则，转到步骤107；

步骤106、初始化最后一个TCAM表项，键值中所有字段均初始 化为0，掩码为0，即该表项是一个“catch all”（匹配任意键值）的 表项；数据中的所有字段均赋值为0，表示该表项为TCAM最后一个 表项，不能用来缓存地址冲突，TCAM最后一个表项的作用是：（1） 当业务转发查找到该表项时，可判断整个TCAM表项中没有缓存该 MAC地址，因而需要继续搜索哈希表以指导业务转发；（2）当MAC 地址学习搜索空闲表项时查找到该表项，则表示TCAM冲突缓存已 满，无法再缓存冲突的MAC地址了；因此实际能缓存的冲突总量是 TCAM表项总数减1，转到步骤108；

步骤107、将键值中表项满标志清0，掩码置1（表示当前表项 初始状态为空），键值中其余字段清0，掩码清0，数据中表项有效标 志置1，其余字段清0，表示该表项不是最后一个表项，可以用来缓 存冲突的MAC地址，转到步骤108；

步骤108、表项初始化的流程结束。

参见图2所示，本发明实施例提供一种基于哈希表和TCAM表 的MAC地址硬件学习方法，包括以下步骤：

步骤201、以报文所属的虚拟转发实例号和源MAC地址计算哈 希值，并以哈希值为索引搜索哈希表；

步骤202、组织搜索TCAM表项的键值：虚拟转发实例号为报文 所属的虚拟转发实例号；MAC地址为报文的源MAC地址；表项满 标志置1，表示在已经学习到的TCAM表项中进行搜索；

步骤203、判断TCAM表项数据中有效标志是否置位，如果置位， 则转到步骤204；否则，转到步骤206；

步骤204、比较TCAM表项数据中虚拟交换端口是否等于报文接 收虚拟交换端口，如果是，则表项不需要更新，转到步骤215；否则， 表示TCAM表项需要更新，转到步骤205；

步骤205、更新当前TCAM表项数据中虚拟交换端口为报文实际 接收虚拟交换端口，转到步骤215；

步骤206、判断哈希表中数据有效标志是否置位，如果置位，则 转到步骤208；否则，转到步骤207；

步骤207、将报文源MAC地址，报文所属虚拟转发实例号和报 文接收的虚拟交换端口存储到当前哈希表项中，表项有效标志置1， 转到步骤215；

步骤208、比较哈希表中虚拟转发实例号和MAC地址是否和报 文所属的虚拟转发实例号及源MAC地址相匹配，如果匹配，则表示 当前地址已经在哈希表中学到过，转到步骤209；否则，转到步骤211；

步骤209、比较当前哈希表中虚拟交换端口是否等于报文实际接 收虚拟交换端口，如果相等，则哈希表项不需要更新，转到步骤215； 否则，转到步骤210；

步骤210、更新当前哈希表项中的虚拟转发端口号为报文实际接 收虚拟端口号，转到步骤215；

步骤211、产生哈希冲突，组织搜索TCAM表项的键值以寻找空 闲TCAM表项缓存冲突：键值中虚拟转发实例号为0，MAC地址为 0，表项满标志为0，表示在空闲TCAM表项中进行搜索；

步骤212、判断TCAM数据中有效标志是否置位，如果置位，表 示找到第一个空闲表项，转到步骤214；否则，转到步骤213；

步骤213、TCAM存储器没有空闲表项可以缓存冲突，放弃学习， 转到步骤215；

步骤214、将MAC地址缓存到当前空闲TCAM表项中：键值的 虚拟转发实例号填写为报文所属虚拟转发实例号，掩码置1；MAC 地址填写为报文的源MAC地址，掩码置1；表项满标志置1，掩码 置1；数据中虚拟交换端口填写为报文实际接收虚拟交换端口，转到 步骤215；

步骤215、MAC地址硬件学习流程结束。

参见图3所示，本发明实施例中老化的流程如下：

步骤301、判断老化表项索引是否大于表项最大值，如果是，则 转到步骤302；否则，转到步骤303；

步骤302、初始化表项索引范围超过表项最大值，返回异常，转 到步骤308；

步骤303、判断老化表项索引值是否位于哈希表索引范围内，如 果是，则转到步骤304；否则，转到步骤305；

步骤304、老化哈希表，直接用初始化索引值定位哈希表项，并 将表项内容全部清0，转到步骤308；

步骤305、判断老化表项索引是否为TCAM最后一项，如果是， 则转到步骤306；否则，转到步骤307；

步骤306、TCAM最后一项是一个“catch all”（匹配任意键值） 的表项，一旦初始化则不需要对其进行操作，转到步骤308；

步骤307、将键值中表项满标志清0，掩码置1，其余字段清0， 掩码清0，将表项状态置为空，数据中表项有效标志置1，其余字段 清0，表示该表项不是最后一个表项，可以用来缓存冲突的MAC地 址，转到步骤308；

步骤308、MAC地址老化流程结束。

本发明实施例还提供一种基于哈希表和TCAM表的MAC地址 硬件学习系统，包括初始化单元、搜索单元、TCAM表项判断单元、 哈希表判断单元、哈希表比较单元、哈希冲突处理单元和老化单元， 其中：

初始化单元，用于：判断初始化表项索引是否大于表项最大值， 如果是，则返回异常；否则，判断初始化表项索引值是否位于哈希表 索引范围内，如果是，则初始化哈希表，直接用初始化索引值定位哈 希表项，并将表项内容全部清0；否则，判断初始化表项索引是否为 TCAM最后一项，如果是，则初始化最后一个TCAM表项，键值中 所有字段均初始化为0，掩码为0，数据中的所有字段均赋值为0， 表示该表项为TCAM最后一个表项；否则，将键值中表项满标志清0， 掩码置1，表示当前表项初始状态为空，键值中其余字段清0，掩码 清0，数据中表项有效标志置1，其余字段清0，表示该表项不是最 后一个表项，初始化结束；

搜索单元，用于：以报文所属的虚拟转发实例号和源MAC地址 计算哈希值，并以哈希值为索引搜索哈希表，哈希表存储在SRAM 或者DRAM中；TCAM表项存储在TCAM存储器中，组织搜索TCAM 表项的键值：虚拟转发实例号为报文所属的虚拟转发实例号；MAC 地址为报文的源MAC地址；表项满标志置1，表示在已经学习到的 TCAM表项中进行搜索；

TCAM表项判断单元，用于：判断TCAM表项数据中有效标志 是否置位，如果置位，则比较TCAM表项数据中虚拟交换端口是否 等于报文接收虚拟交换端口，如果是，则不更新表项；否则，更新当 前TCAM表项数据中虚拟交换端口为报文实际接收虚拟交换端口； 如果没有置位，产生哈希表判断触发信号，并发送到哈希表判断单元；

哈希表判断单元，用于：收到哈希表判断触发信号时，判断哈希 表中数据有效标志是否置位，如果没有置位，将报文源MAC地址、 报文所属虚拟转发实例号和报文接收的虚拟交换端口存储到当前哈 希表项中，表项有效标志置1；如果置位，产生比较触发信号，并发 送到哈希表比较单元；

哈希表比较单元，用于：收到比较触发信号时，比较哈希表中虚 拟转发实例号和MAC地址是否和报文所属的虚拟转发实例号及 MAC地址相匹配，如果匹配，则表示当前地址已经在哈希表中学到 过，比较当前哈希表中虚拟交换端口是否等于报文实际接收虚拟交换 端口，如果相等，则结束学习；否则，更新当前哈希表项中的虚拟转 发端口号为报文实际接收虚拟端口号，结束学习；如果不匹配，产生 哈希冲突处理触发信号，并发送到哈希冲突处理单元；

哈希冲突处理单元，用于：收到哈希冲突处理触发信号时，组织 搜索TCAM表项的键值以寻找空闲TCAM表项缓存冲突：键值中虚 拟转发实例号为0，MAC地址为0，表项满标志为0，表示在空闲 TCAM表项中进行搜索；再判断TCAM数据中有效标志是否置位， 如果置位，表示找到第一个空闲表项，将MAC地址缓存到当前空闲 TCAM表项中：键值的虚拟转发实例号填写为报文所属虚拟转发实例 号，掩码置1，MAC地址填写为报文的源MAC地址，掩码置1，表 项满标志置1，掩码置1，数据中虚拟交换端口填写为报文实际接收 虚拟交换端口，结束学习；如果没有置位，表示TCAM存储器没有 空闲表项，放弃学习；

老化单元，用于：判断老化表项索引是否大于表项最大值，如果 是，则返回异常；否则，判断老化表项索引值是否位于哈希表索引范 围内，如果是，则老化哈希表，直接用初始化索引值定位哈希表项， 并将表项内容全部清0；否则，判断老化表项索引是否为TCAM最后 一项，如果是，则表示TCAM最后一项是一个匹配任意键值的表项， 结束老化；否则，将键值中表项满标志清0，掩码置1，其余字段清 0，掩码清0，将表项状态置为空，数据中表项有效标志置1，其余字 段清0，表示该表项不是最后一个表项，老化结束。

本领域的技术人员可以对本发明实施例进行各种修改和变型，倘 若这些修改和变型属在本发明权利要求及其等同技术的范围之内，则 这些修改和变型也在本发明的保护范围之内。

说明书中未详细描述的内容为本领域技术人员公知的现有技术。