一种基于HASH进行标签映射的交叉方法

摘要

本发明涉及一种基于HASH进行标签映射的交叉方法，步骤如下：步骤1，生成一张MAC地址和所有ENTRY的HASH关系对应表，所有ENTRY的初始状态都为空闲态；步骤2，为每条新业务分配一个空闲的ENTRY：并选择ENTRY内容中对应的单播或组播MAC地址做为业务的映射地址；分配后，该ENTRY的状态变为使用态；步骤3，TUNNEL MAP芯片使用分配的MAC地址进行标签映射，MAC交叉芯片也用该MAC地址设置L2地址表；步骤4，当交叉业务被删除时，ENTRY被释放且状态重新赋值为空闲态。本发明所述方法，彻底解决因HASH冲突而引起的交叉限制，交叉条目数完全等于MAC表的物理容量；交叉配置所对应的MAC表物理位置已提前算出，易于错误定位。

权利要求

1.一种基于HASH进行标签映射的交叉方法，其特征在于，包括以下步骤：步骤1，生成一张MAC地址和所有ENTRY的HASH关系对应表，所有ENTRY的初始状态都为空闲态；

步骤2，为每条新业务分配一个空闲的ENTRY：

对于每一条新配置的交叉业务，从HASH关系对应表中申请一个空闲的未使用的ENTRY，若新配置的交叉业务的交叉属性是单播交叉，则选择ENTRY内容中对应的单播MAC地址做为业务的映射地址；

若新配置的交叉业务的交叉属性是组播交叉，则选择ENTRY内容中对应的组播MAC地址做为映射地址；

分配后，该ENTRY的状态变为使用态；

步骤3，使用分配的MAC地址进行映射配置：

TUNNEL MAP芯片使用分配的MAC地址进行标签映射，MAC交叉芯片也用该MAC地址设置L2地址表；

由于新分配的MAC地址总能对应交叉芯片MAC表里的一个已知位置的但未使用的ENTRY，所以对于每条新交叉业务，MAC交叉芯片将不再出现MAC表的HASH冲突问题；

步骤4，业务删除，释放ENTRY：

一个ENTRY只能被分配一次，直到对应的交叉业务被删除，才能重新被分配；

当交叉业务被删除时，ENTRY被释放，且被释放的ENTRY状态将重新赋值为空闲态。

2.如权利要求1所述的基于HASH进行标签映射的交叉方法，其特征在于：步骤1中生成一张MAC地址和所有ENTRY的HASH关系对应表时，若HASH算法为直接索引算法，且算法使用MAC地址的低位进行索引，HASH关系对应表的生成方法如下：MAC地址为48BIT，表示为BIT1～BIT48，值范围为[0，2^48-1]；

若BIT8＝0，则MAC为单播地址；若BIT8＝1，且所有BIT不全为1，则MAC地址为组播地址；

设BUCKET个数为4K，4K＝2^12，则索引BUCKET的位数需要12BIT，设每BUCKET有8个ENTRY，8＝2^3，则索引对应BUCKET里的8个ENTRY位置需要3BIT，使用数组MAC_UC[4K][8]存储对应的单播MAC地址，使用数组MAC_MC[4K][8]存储对应的组播MAC地址，由于算法使用MAC地址的低位进行索引，即MAC高位不参与HASH算法，高位可以都为

0，所以MAC地址的取值为：

MAC_UC[B_NUM][E_MUM]＝(E_NUM＜＜12)|(B_NUM)；

MAC_MC[B_NUM][E_NUM]＝(0X01＜＜40)|(E_NUM＜＜12)|(B_NUM)；

其中对应BUCKET存储个数值B_NUM为12BIT，值范围为[0，4095]；

对应BUCKET的ENTRY存储个数值E_NUM为3BIT，值范围为[0，7]；

得出单播MAC数组MAC_UC[X][Y]和组播MAC数组MAC_MC[X][Y]，即得出了一张MAC地址和ENTRY的HASH关系对应表，每个ENTRY将对应一个单播地址和一个组播地址。

3.如权利要求1所述的基于HASH进行标签映射的交叉方法，其特征在于：步骤1中生成一张MAC地址和所有ENTRY的HASH关系对应表时，若HASH算法为间接索引算法，设HASH算法为CRC-32校验，取校验值的低位进行HASH，a)计算的CRC多项式为：

G(x)＝X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1b)计算的过程为：

设BUCKET个数为4K，4K＝2^12，则索引BUCKET的位数需要12BIT，设每BUCKET有8个ENTRY，对于同一个BUCKET，需要找出8个HASH值相同的MAC地址来对应其包含的8个ENTRY，首先，进行单播MAC地址的查找：

数组MAC_UC[4K][8]用于存储相同BUCKET的单播MAC值，数组COUNT_UC[4K]用于累计每个BUCKET存储的单播个数，变量TOTAL_UC用于累计当前已得的单播MAC值总数，所有数组和变量的初始值都为0，当TOTAL_UC＝4K*8＝32K时，单播MAC地址查找将终止；

将MAC地址从小到大依次进行CRC-32的计算，MAC地址的取值范围为[0，2^48-1]内的单播地址；

若某个单播地址MAC_UC_N的CRC值的低12位为对应BUCKET存储个数值B_NUM，其对应BUCKET的ENTRY存储个数值E_NUM＝COUNT_UC[B_NUM]，则将MAC_UC_N存储于MAC_UC[B_NUM][E_NUM]位置，然后将COUNT_UC[B_NUM]加一，TOTAL_UC加一；

当NUM＝COUNT_UC[B_NUM]值＝8时，表示对应B_NUM位置的BUCKET已经装满8个ENTRY的单播MAC地址，则该BUCKET无需再存储，直接进行下一个单播MAC的CRC计算；

当TOTAL_UC＝32K时，表示单播地址已经存满，则单播查找终止，继续进行组播查找；

接下来，进行组播MAC地址的查找，进行组播MAC地址的查找与进行单播MAC地址的查找同理，数组MAC_MC[4K][8]用于存储相同BUCKET的组播MAC值，数组COUNT_MC[4K]用于累计每个BUCKET存储的组播个数，变量TOTAL_MC用于累计当前已得的组播MAC值总数，所有数组和变量的初始值都为0，当TOTAL_MC＝4K*8＝32K时，组播MAC地址查找将终止；

将MAC地址从小到大依次进行CRC-32的计算，MAC地址的取值范围为[0，2^48-1]内的组播地址；

若某个组播地址MAC_MC_N的CRC值的低12位为B_NUM，其对应BUCKET的ENTRY存储个数值E_NUM＝COUNT_MC[B_NUM]，则将MAC_MC_N存储于MAC_MC[B_NUM][E_NUM]位置，然后将COUNT_MC[B_NUM]加一，TOTAL_MC加一；

当NUM＝COUNT_MC[B_NUM]值＝8时，表示对应B_NUM位置的BUCKET已经装满8个ENTRY的组播MAC地址，则该BUCKET无需再存储，直接进行下一个组播MAC的CRC计算；

当TOTAL_MC＝32K时，表示组播地址已经存满，则组播查找终止；

得出单播MAC数组MAC_UC[X][Y]和组播MAC数组MAC_MC[X][Y]，即得出了一张MAC地址和ENTRY的HASH关系对应表，每个ENTRY将对应一个单播地址和一个组播地址。

说明书

一种基于HASH进行标签映射的交叉方法

技术领域

[0001] 本发明涉及T-MPLS(传送多协议标签交换)技术及其交叉实现方法，具体说是一种基于HASH进行标签映射的交叉方法。

背景技术

[0002] T-MPLS是ITU-T(国际电信联盟)标准化的一种分组传送网技术，其解决传统SDH(同步数字体系)在以分组交换为主的网络环境中暴露出效率低下的缺点。T-MPLS具有面向连接的数据转发机制、多业务承载、较强的网络扩展性、丰富的OAM(操作，维护，管理)、严格的QoS(服务质量)机制以及50ms的网络保护等技术特征。

[0003] T-MPLS是MPLS(多协议标签交换)的一个子集，在业务封装模式上，它定义了层次化的封装模型。它先将每条业务封装进不同的PW(伪线)里得到PW数据包，再将PW数据包封装进不同的TUNNEL(隧道)里得到两层标签的MPLS包，然后将该MPLS包送到MPLS网络进行转发，MPLS网络根据MPLS包携带的TUNNEL标签进行转发，在中间节点可以进行TUNNEL标签交换。

[0004] 在业务的保护方式上，ITU-T定义了T-MPLS环网保护标准G.8132和线性保护标准G.8131。

[0005] 为了实现各种业务保护，一般的系统都要构造一个TUNNEL层面的CROSS(交叉)矩阵实现TUNNEL交叉。所说的TUNNEL交叉就是将含有某种TUNNEL标签的MPLS包转发到指定的一个或多个出口，即实现“INPORT+TUNNEL--＞OUTPORT LIST”的功能。对于TUNNEL层面的CROSS交叉矩阵而言，其入接口和出接口的包都是基于以太网的两层标签(TUNNEL+PW)的MPLS包，基于以太网的两层标签(TUNNEL+PW)的MPLS包格式如下：

[0006]DMAC SMAC 0X8847 TUNNEL PW CUSTOM DATA CRC

[0007] 其中各字段含义如下：

[0008] DMAC：目标MAC地址；

[0009] SMAC：源MAC地址；

[0010] 0X8847：MPLS包的以太网类型值；

[0011] TUNNEL：隧道标签值；

[0012] PW：伪线标签值；

[0013] CUSTOM DATA：客户数据内容；

[0014] CRC：循环冗余校验。

[0015] 为了实现大容量的TUNNEL层面的CROSS交叉矩阵，所述大容量是指交叉条目＞＝4K*N(N＞＝1)。根据目前的芯片技术情况，使用标签映射是其中的一种实现方法。图1即为标签映射的业务交叉模型。

[0016] 1)如图1所示，其业务转发过程为：

[0017] 步骤1，分支芯片T(即图1中的T1、T2、……、Tn)对客户业务进行封装处理，在入接口处形成两层标签的MPLS包，所说的两层标签为TUNNEL+PW标签；

[0018] 步骤2，TUNNEL MAP芯片(即图1中的MAP_1、MAP_2、……、MAP_n)接收两层标签的MPLS包后，用其具有的TUNNEL映射为DMAC的功能，对两层标签的MPLS包进行标签映射；

[0019] 步骤3，DMAC交叉芯片接收进行标签映射后的MPLS包，用其具有的L2MAC表的单播和组播资源，根据相应的交叉配置进行转发设置；

[0020] 步骤4，最后，出接口的分支芯片T再将MPLS包转发到相应的网络上；

[0021] 上述入接口的分支芯片T和对称的出接口的分支芯片T是同一个芯片。

[0022] 2)步骤2中所述的对两层标签的MPLS包进行标签映射是指：

[0023] 利用基于以太网的MPLS包的DMAC域进行标签映射，进行映射后MPLS包头的DMAC值将会发生改变，由于MPLS包头的DMAC和SMAC域只是为了形成以太网包格式而增加的，一般都不存在任何具体意义，所以DMAC域的改变不会对后续的包处理产生任何影响。

[0024] 图1中，大容量的DMAC交叉芯片缺乏TUNNEL交叉资源，但是却有丰富的L2MAC表的单播和组播资源，这个MAC表资源就是实现标签映射的媒介。大容量的DMAC交叉芯片可实现单播和组播，其中：

[0025] L2单播条目的内容为：DMAC--＞OUTPORT；

[0026] L2组播条目的内容为：DMAC--＞OUTPORT LIST；

[0027] 小容量的TUNNEL MAP芯片拥有丰富的TUNNEL交叉资源，并且可以实现将TUNNEL映射为DMAC的功能，即它可以实现：

[0028] INPORT+TUNNEL--＞OUTPORT，以及

[0029] TUNNEL--＞DMAC；

[0030] 因此，首先TUNNEL MAP芯片进行TUNNEL到DMAC的映射，然后后级的DMAC交叉芯片再对DMAC配置L2MAC表的单播或者组播条目进行转发，从而达到系统TUNNEL层面的大容量交叉。

[0031] 3)L2MAC表的HASH(哈希)存储原理：

[0032] HASH主要是用来提供一种简单快速的索引功能，它需要两个计算因素：关键字KEY和算法，然后用算法对KEY进行计算得到HASH值，即索引值。

[0033] 对于L2MAC表，KEY主要是MAC值，算法可以有多种，如CRC16，CRC32，异或等。如图2，L2MAC表由X个BUCKET(桶)组成，每个BUCKET由Y个ENTRY(条目)组成，则L2MAC表的物理存储容量为MAX＝X*Y(X＞＝1，Y＞＝1)。

[0034] 每条TUNNEL交叉Cross_n都会映射到某个地址Mac_n，n＝1、2、3、……，再由Mac_n根据HASH算法计算出BUCKET索引值，BUCKET的范围为[0，X-1]，相同的BUCKET值指向相同的BUCKET存储区，BUCKET里的空闲ENTRY将被随机选取一个用于存储Mac_n。当HASH指向的BUCKET满后，则出现HASH存储冲突，虽然此时L2MAC表还有大量的BUCKET还未使用。比如：

[0035] 设L2MAC表的物理容量为32k个ENTRY条目，每个BUCKET包含8个ENTRY，则L2MAC表共有BUCKET个数：32K/8＝4K(即＝2^12)，则其HASH比特需要12位。假设HASH算法为取MAC地址的低12位进行HASH，则当有8个MAC地址分别为：0X0000，0X1000，0X2000，0X3000，0X4000，0X5000，0X6000，0X7000时，其HASH结果都是0(因为这些MAC地址的低12位都相同，故HASH结果也相同)，此时BUCKET＝0的桶就会存满。若再有一个MAC＝0X8000需要存储，由于它的HASH值也是0，所以此时虽然L2MAC物理表还有很多其他的BUCKET＞＝1未使用，但是该MAC地址已经由于BUCKET＝0的HASH冲突而无法存储了。

[0036] 一般的DMAC交叉芯片的L2MAC表都是使用HASH方式进行索引存储，HASH算法虽然有多种，但是不管哪种算法都会存在HASH存储冲突，也即若TUNNEL--＞DMAC的映射方式采用非HASH映射，如直接映射方式，则理论上肯定会带来天生的HASH冲突。以下举例说明：

[0037] 采用直接映射方式，映射结果如下：

[0038] 单播交叉DMAC＝(OUTPORT＜＜20)+TUNNEL；

[0039] 组播交叉DMAC＝0X010000000000+(OUTPORT＜＜20)+TUNNEL；

[0040] 采用直接映射方式存在以下问题：

[0041] A)直接映射的DMAC值包含TUNNEL信息，映射方式虽然简单明了，但是无法避免HASH冲突问题。

[0042] B)L2MAC表会出现使用率低下的问题，交叉条目数不等同于L2MAC表的容量。

[0043] 在实际应用中，对于一条正确的交叉配置，当然不允许由于HASH算法等原因而出现配置不能存储的问题。针对这个问题虽然可以用ACL等资源进行HASH冲突以后的拟补，但是其始终不是最好的解决方法，毕竟不是所有的DMAC交叉芯片都有ACL(访问控制列表)资源。

发明内容

[0044] 针对现有技术中存在的缺陷，本发明的目的在于提供一种基于HASH进行标签映射的交叉方法，彻底解决因HASH冲突而引起的交叉限制，交叉条目数完全等于MAC表的物理容量；交叉配置所对应的MAC表物理位置已提前算出，易于错误定位。

[0045] 为达到以上目的，本发明采取的技术方案是：

[0046] 一种基于HASH进行标签映射的交叉方法，其特征在于，包括以下步骤：

[0047] 步骤1，生成一张MAC地址和所有ENTRY的HASH关系对应表，所有ENTRY的初始状态都为空闲态；

[0048] 步骤2，为每条新业务分配一个空闲的ENTRY：

[0049] 对于每一条新配置的交叉业务，从HASH关系对应表中申请一个空闲的未使用的ENTRY，

[0050] 若新配置的交叉业务的交叉属性是单播交叉，则选择ENTRY内容中对应的单播MAC地址做为业务的映射地址；

[0051] 若新配置的交叉业务的交叉属性是组播交叉，则选择ENTRY内容中对应的组播MAC地址做为映射地址；

[0052] 分配后，该ENTRY的状态变为使用态；

[0053] 步骤3，使用分配的MAC地址进行映射配置：

[0054] TUNNEL MAP芯片使用分配的MAC地址进行标签映射，MAC交叉芯片也用该MAC地址设置L2地址表；

[0055] 由于新分配的MAC地址总能对应交叉芯片MAC表里的一个已知位置的但未使用的ENTRY，所以对于每条新交叉业务，MAC交叉芯片将不再出现MAC表的HASH冲突问题；

[0056] 步骤4，业务删除，释放ENTRY：

[0057] 一个ENTRY只能被分配一次，直到对应的交叉业务被删除，才能重新被分配；

[0058] 当交叉业务被删除时，ENTRY被释放，且被释放的ENTRY状态将重新赋值为空闲态。

[0059] 在上述技术方案的基础上，步骤1中生成一张MAC地址和所有ENTRY的HASH关系对应表时，若HASH算法为直接索引算法，且算法使用MAC地址的低位进行索引，HASH关系对应表的生成方法如下：

[0060] MAC地址为48BIT，表示为BIT1～BIT48，值范围为[0，2^48-1]；

[0061] 若BIT8＝0，则MAC为单播地址；若BIT8＝1，且所有BIT不全为1，则MAC地址为组播地址；

[0062] 设BUCKET个数为4K，4K＝2^12，则索引BUCKET的位数需要12BIT，[0063] 设每BUCKET有8个ENTRY，8＝2^3，则索引对应BUCKET里的8个ENTRY位置需要3BIT，

[0064] 使用数组MAC_UC[4K][8]存储对应的单播MAC地址，

[0065] 使用数组MAC_MC[4K][8]存储对应的组播MAC地址，

[0066] 由于算法使用MAC地址的低位进行索引，即MAC高位不参与HASH算法，高位可以都为0，所以MAC地址的取值为：

[0067] MAC_UC[B_NUM][E_NUM]＝(E_NUM＜＜12)|(B_NUM)；

[0068] MAC_MC[B_NUM][E_NUM]＝(0X01＜＜40)|(E_NUM＜＜12)|(B_NUM)；

[0069] 其中B_NUM为12BIT，值范围为[0，4095]；

[0070] E_NUM为3BIT，值范围为[0，7]；

[0071] 得出单播MAC数组MAC_UC[X][Y]和组播MAC数组MAC_MC[X][Y]，即得出了一张MAC地址和ENTRY的HASH关系对应表，每个ENTRY将对应一个单播地址和一个组播地址。

[0072] 在上述技术方案的基础上，步骤1中生成一张MAC地址和所有ENTRY的HASH关系对应表时，若HASH算法为间接索引算法，

[0073] 设HASH算法为CRC-32校验，取校验值的低位进行HASH，

[0074] a)计算的CRC多项式为：

[0075] G(x)＝X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1[0076] b)计算的过程为：

[0077] 设BUCKET个数为4K，4K＝2^12，则索引BUCKET的位数需要12BIT，[0078] 设每BUCKET有8个ENTRY，对于同一个BUCKET，需要找出8个HASH值相同的MAC地址来对应其包含的8个ENTRY，

[0079] 首先，进行单播MAC地址的查找：

[0080] 数组MAC_UC[4K][8]用于存储相同BUCKET的单播MAC值，数组COUNT_UC[4K]用于累计每个BUCKET存储的单播个数，变量TOTAL_UC用于累计当前已得的单播MAC值总数，所有数组和变量的初始值都为0，当TOTAL_UC＝4K*8＝32K时，单播MAC地址查找将终止；

[0081] 将MAC地址从小到大依次进行CRC-32的计算，MAC地址的取值范围为[0，2^48-1]内的单播地址；

[0082] 若某个单播地址MAC_UC_N的CRC值的低12位为B_NUM，其对应BUCKET的ENTRY存储个数值E_NUM＝COUNT_UC[B_NUM]，则将MAC_UC_N存储于MAC_UC[B_NUM][E_NUM]位置，然后将COUNT_UC[B_NUM]加一，TOTAL_UC加一；即执行：

[0083] MAC_UC[B_NUM][E_NUM]＝MAC_UC_N；

[0084] COUNT_UC[B_NUM]++；

[0085] TOTAL_UC++；

[0086] 当NUM＝COUNT_UC[B_NUM]值＝8时，表示对应B_NUM位置的BUCKET已经装满8个ENTRY的单播MAC地址，则该BUCKET无需再存储，直接进行下一个单播MAC的CRC计算；

[0087] 当TOTAL_UC＝32K时，表示单播地址已经存满，则单播查找终止，继续进行组播查找；

[0088] 接下来，进行组播MAC地址的查找，进行组播MAC地址的查找与进行单播MAC地址的查找同理，

[0089] 数组MAC_MC[4K][8]用于存储相同BUCKET的组播MAC值，数组COUNT_MC[4K]用于累计每个BUCKET存储的组播个数，变量TOTAL_MC用于累计当前已得的组播MAC值总数，所有数组和变量的初始值都为0，当TOTAL_MC＝4K*8＝32K时，组播MAC地址查找将终止；

[0090] 将MAC地址从小到大依次进行CRC-32的计算，MAC地址的取值范围为[0，2^48-1]内的组播地址；

[0091] 若某个组播地址MAC_MC_N的CRC值的低12位为B_NUM，其对应BUCKET的ENTRY存储个数值E_NUM＝COUNT_MC[B_NUM]，则将MAC_MC_N存储于MAC_MC[B_NUM][E_NUM]位置，然后将COUNT_MC[B_NUM]加一，TOTAL_MC加一；即执行：

[0092] MAC_MC[B_NUM][E_NUM]＝MAC_MC_N；

[0093] COUNT_MC[B_NUM]++；

[0094] TOTAL_MC++；

[0095] 当NUM＝COUNT_MC[B_NUM]值＝8时，表示对应B_NUM位置的BUCKET已经装满8个ENTRY的组播MAC地址，则该BUCKET无需再存储，直接进行下一个组播MAC的CRC计算；

[0096] 当TOTAL_MC＝32K时，表示组播地址已经存满，则组播查找终止；

[0097] 得出单播MAC数组MAC_UC[X][Y]和组播MAC数组MAC_MC[X][Y]，即得出了一张MAC地址和ENTRY的HASH关系对应表，每个ENTRY将对应一个单播地址和一个组播地址。

[0098] 本发明所述的基于HASH进行标签映射的交叉方法，彻底解决因HASH冲突而引起的交叉限制，交叉条目数完全等于MAC表的物理容量；交叉配置所对应的MAC表物理位置已提前算出，易于错误定位。

附图说明

[0099] 本发明有如下附图：

[0100] 图1标签映射的业务交叉模型，

[0101] 图2L2MAC表的HASH过程，

[0102] 图3HASH映射的业务配置流程图。

具体实施方式

[0103] 以下结合附图对本发明作进一步详细说明。

[0104] 本发明所述的基于HASH进行标签映射的交叉方法，使用HASH映射方式来解决因HASH冲突引起的交叉配置问题。图3为本发明所述的基于HASH进行标签映射的交叉方法的业务配置流程图，下面详细介绍其实现过程：

[0105] 步骤1，生成一张MAC地址和所有ENTRY的HASH关系对应表；

[0106] 设L2MAC表由X个BUCKET组成，每个BUCKET由Y个ENTRY组成，则该L2MAC表的存储容量最大为MAX＝X*Y；

[0107] 每个ENTRY条目包含以下四项信息：

[0108] 物理位置编号，范围为[0，MAX-1]，

[0109] BUCKET编码，范围为[0，X-1]，

[0110] MAC地址内容，MAC地址内容有单播、组播两种，

[0111] 当前状态，当前状态有空闲、使用两种；

[0112] 所有ENTRY的初始状态都为空闲态；

[0113] 步骤1.1)若HASH算法为直接索引算法，即使用48位MAC地址的某几位进行直接索引。当前的直接索引算法主要是取MAC地址的低位进行HASH算法，所以本文以此进行举例。

[0114] 举例如下：使用MAC地址的低位进行索引。

[0115] MAC地址为48BIT，表示为BIT1～BIT48，值范围为[0，2^48-1]。若BIT8＝0，则MAC为单播地址；若BIT8＝1，且所有BIT不全为1，则MAC地址为组播地址。

[0116] 设BUCKET个数为4K，4K＝2^12，则索引BUCKET的位数需要12BIT，[0117] 设每BUCKET有8个ENTRY，8＝2^3，则索引对应BUCKET里的8个ENTRY位置需要3BIT。

[0118] 使用数组MAC_UC[4K][8]存储对应的单播MAC地址，使用数组MAC_MC[4K][8]存储对应的组播MAC地址。

[0119] 由于算法使用MAC地址的低位进行索引，即MAC高位不参与HASH算法，高位可以都为0，所以MAC地址的取值为：

[0120] MAC_UC[B_NUM][E_NUM]＝(E_NUM＜＜12)|(B_NUM)；

[0121] MAC_MC[B_NUM][E_NUM]＝(0X01＜＜40)|(E_NUM＜＜12)|(B_NUM)；

[0122] 其中B_NUM为12BIT，值范围为[0，4095]；

[0123] E_NUM为3BIT，值范围为[0，7]；

[0124] 步骤1.2)若HASH算法为间接索引算法，即使用48位MAC地址进行某种特定算法的计算得出一个结果，再对这个结果进行HASH取值。当前的间接索引算法主要为CRC算法，所以本文以CRC算法进行举例。

[0125] 举例如下：HASH算法为CRC-32校验，取校验值的低位进行HASH。

[0126] a)计算的CRC多项式为：

[0127] G(x)＝X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1[0128] b)计算的过程为：

[0129] 设BUCKET个数为4K，4K＝2^12，则索引BUCKET的位数需要12BIT，[0130] 设每BUCKET有8个ENTRY，对于同一个BUCKET，需要找出8个HASH值相同的MAC地址来对应其包含的8个ENTRY。

[0131] 首先，进行单播MAC地址的查找。

[0132] 数组MAC_UC[4K][8]用于存储相同BUCKET的单播MAC值，数组COUNT_UC[4K]用于累计每个BUCKET存储的单播个数，变量TOTAL_UC用于累计当前已得的单播MAC值总数，所有数组和变量的初始值都为0，当TOTAL_UC＝4K*8＝32K时，单播MAC地址查找将终止。

[0133] 将MAC地址从小到大依次进行CRC-32的计算，MAC地址的取值范围为[0，2^48-1]内的单播地址。

[0134] 若某个单播地址MAC_UC_N的CRC值的低12位为B_NUM，其对应BUCKET的ENTRY存储个数值E_NUM＝COUNT_UC[B_NUM]，则将MAC_UC_N存储于MAC_UC[B_NUM][E_NUM]位置，然后将COUNT_UC[B_NUM]加一，TOTAL_UC加一。即执行：

[0135] MAC_UC[B_NUM][E_NUM]＝MAC_UC_N；

[0136] COUNT_UC[B_NUM]++；

[0137] TOTAL_UC++；

[0138] 当NUM＝COUNT_UC[B_NUM]值＝8时，表示对应B_NUM位置的BUCKET已经装满8个ENTRY的单播MAC地址，则该BUCKET无需再存储，直接进行下一个单播MAC的CRC计算。当TOTAL_UC＝32K时，表示单播地址已经存满，则单播查找终止，继续进行组播查找。

[0139] 其次，进行组播MAC地址的查找。

[0140] 同理，对应组播MAC地址的查找需要存储数组和变量：MAC_MC[4K][8]，COUNT_MC[4K]，TOTAL_MC。MAC地址的取值范围为[0，2^48-1]内的组播地址。

[0141] 数组MAC_MC[4K][8]用于存储相同BUCKET的组播MAC值，数组COUNT_MC[4K]用于累计每个BUCKET存储的组播个数，变量TOTAL_MC用于累计当前已得的组播MAC值总数，所有数组和变量的初始值都为0，当TOTAL_MC＝4K*8＝32K时，组播MAC地址查找将终止；

[0142] 将MAC地址从小到大依次进行CRC-32的计算，MAC地址的取值范围为[0，2^48-1]内的组播地址；

[0143] 若某个组播地址MAC_MC_N的CRC值的低12位为B_NUM，其对应BUCKET的ENTRY存储个数值E_NUM＝COUNT_MC[B_NUM]，则将MAC_MC_N存储于MAC_MC[B_NUM][E_NUM]位置，然后将COUNT_MC[B_NUM]加一，TOTAL_MC加一；即执行：

[0144] MAC_MC[B_NUM][E_NUM]＝MAC_MC_N；

[0145] COUNT_MC[B_NUM]++；

[0146] TOTAL_MC++；

[0147] 当NUM＝COUNT_MC[B_NUM]值＝8时，表示对应B_NUM位置的BUCKET已经装满8个ENTRY的组播MAC地址，则该BUCKET无需再存储，直接进行下一个组播MAC的CRC计算；

[0148] 当TOTAL_MC＝32K时，表示组播地址已经存满，则组播查找终止。

[0149] 步骤1.3)由步骤1.1或步骤1.2可得出单播MAC数组MAC_UC[X][Y]和组播MAC数组MAC_MC[X][Y]，即得出了一张MAC地址和ENTRY的HASH关系对应表，每个ENTRY将对应一个单播地址和一个组播地址，结果如下：

[0150]

[0151] 步骤2，为每条新业务分配一个空闲的ENTRY；

[0152] 对于每一条新配置的交叉业务，从HASH关系对应表中申请一个空闲的未使用的ENTRY。

[0153] 若新配置的交叉业务的交叉属性是单播交叉，则选择ENTRY内容中对应的单播MAC地址做为业务的映射地址；

[0154] 若新配置的交叉业务的交叉属性是组播交叉，则选择ENTRY内容中对应的组播MAC地址做为映射地址；

[0155] 分配后，该ENTRY的状态变为使用态。

[0156] 步骤3，使用分配的MAC地址进行映射配置；

[0157] TUNNEL MAP芯片使用分配的MAC地址进行标签映射，MAC交叉芯片也用该MAC地址设置L2地址表。由于新分配的MAC地址总能对应交叉芯片MAC表里的一个已知位置的但未使用的ENTRY，所以对于每条新交叉业务，MAC交叉芯片将不再出现MAC表的HASH冲突问题。

[0158] 步骤4，业务删除，释放ENTRY。

[0159] 一个ENTRY只能被分配一次，直到对应的交叉业务被删除，才能重新被分配；

[0160] 当交叉业务被删除时，ENTRY被释放，且被释放的ENTRY状态将重新赋值为空闲态。