德赢Vwin官网
App
为解决高速以太网链路接口中软件方式实现的MAC层地址表机制在处理效率上受到制约的问题，提出了一种基于FPGA （现场可编程门阵列）硬件电路方式实现以太网交换机中MAC地址表的查找，学习和老化。该方法采用hashing算法建立地址表项索引值与MAC地址之间的对应关系，完成满足平均时间复杂度为Ｏ （１）的地址查找。由于实际交换机中地址表容量有限，地址学习只能是MAC地址的子集，通过优化hashing函数降低地址冲突发生的概率以及设计一种地址老化机制提高地址表查找能力。仿真结果表明，地址表机制采用硬件电路方式实现比软件方式处理效率更高。
引 言
在计算机网络中，数据链路层完成节点到节点的通信，二层以太网交换机属于数据链路层设备［１］。ＭＡＣ （介质访问控制）地址是在网络通信用来识别主机的标识。交换机的缓存中有一个ＭＡＣ地址表，需要转发数据时，交换机会在地址表查询是否有与目的ＭＡＣ地址对应的表项，如果有，交换机立即将数据报文往该表项中的转发端口发送；如果没有，交换机则会将数据报文以广播的形式发送到除了接收端口外的所有端口，尽最大能力保证目的主机接收到数据报文。因此，交换机地址表的构建和维护决定了数据转发的方向和效率。
ＭＡＣ层地址表存储查找多基于ｈａｓｈ表。Ｈａｓｈｉｎｇ是一种用于以常熟平均时间插入、删除和查找的技术，ｈａｓｈ表通过把关键码值映射到表中一个位置来访问记录。这个映射函数叫做ｈａｓｈｉｎｇ函数，存放记录的数组叫做ｈａｓｈ表。交换机地址表存储的是全部ＭＡＣ地址的一个子集因此必然会发生地址冲突，文献［２－３］对比了几种解决冲突的方法。
ＭＡＣ地址表的容量是有限的，因此交换机采用老化机制来维护ＭＡＣ地址表，以保证最大限度地利用地址表项资源。交换机在构建某条表项时，会相应地开启该表项的老化定时器［４］，如果在老化时间内，交换机始终没有收到该表项中的ＭＡＣ地址的报文，交换机就会将该表项删除，失效的表项不会继续占用ＭＡＣ地址表资源。这样，即使网络中的设备更换或者移除，交换机的ＭＡＣ地址表始终能保持网络中最新的拓扑结构记录。合适的老化时间可以提高ＭＡＣ地址表项资源的利用率，但过长或过短的老化时间，反而影响交换机的性能。如果老化时间过长，交换机中保存的ＭＡＣ地址表项的数量过多会将地址表资源消耗完，网络中的拓扑变化就无法及时更新；如果老化时间过短，则有效的ＭＡＣ地址表项会被交换机过早删除，从而降低交换机的转发效率。
传统的ＭＡＣ地址表处理机制主要采用软件的方式实现［５］。随着以太网链路接口的速率从１Ｇｂ／ｓ发展到１０Ｇｂ／ｓ，基于软件的算法在速度上受到串行计算机系统的制约。新一代现场可编程门阵列（ＦＰＧＡ）的出现以后，算法通过硬电路描述，所有的延迟只来源于门电路，而一般门电路的延迟都在ｎｓ级别。减少了系统运行所需的时钟周期数，实现了真正的高速率。
１ 地址表处理机制
本数字电路设计中，采用单一时钟域的同步时序设计，所有的触发器都是在同一个时钟节拍下进行翻转。这样就简化了整个设计，后端综合、布局布线的时序约束容易实现。
地址表占用的空间由片内存储器ＲＡＭ 提供，片内存储器是基于ＦＰＧＡ的系统可使用的最简单的存储器，存储、读取是在ＦＰＧＡ内部完成，电路板上无需外部连线，具有最高吞吐量和最低反应延时的，适用于缓存和查找表。地址表表项中至少记录ｍａｃ物理地址，端口号。每个ｍａｃ地址表项的数据结构见表１。
定义如下：
Ｖａｌｉｄ：表项有效指示，１代表有效表项，０代表空闲表项。
Ａｇｅ：老化比特，地址表更新时查询的位段，１代表年轻，０代表老化。
Ｍａｃ ａｄｄｒｅｓｓ：４８ｂｉｔ物理地址。
Ｐｏｒｔ＿ｉｄ：物理地址对应的端口号。
地址表项写入表中的位置即地址学习由源地址（ＭＡＣ地址）经过ｈａｓｈｉｎｇ算法求得的索引值决定。地址表项的读取即地址表查询由目的地址（物理地址）经过ｈａｓｈｉｎｇ算法求得的索引值决定。Ｈａｓｈｉｎｇ算法本身消耗一部分时序，物理地址的学习和查询就需要等待这部分时序，为了使得地址表处理起来更加清晰、明确，整个设计分为３个模块（如图１所示）：地址表的输入调整、地址表处理机制、地址表的输出调整。
模块划分后，本级模块向下一级模块一次性交付需要处理的所有并行数据。
１．１ 地址表输入调整（ｆｉｆｏ＿ｉｎ）
Ｆｉｆｏ＿ｉｎ模块完成两种操作，对输入的ＭＡＣ地址求解ｈａｓｈｉｎｇ索引值（ｘｘ＿ｍａｃ＿ｉｎｄｅｘ）；间隔４ｓ产生地址表更新信号（ｕｐｄ＿ｅｎ），更新信号为高电平有效，持续时间由地址表的深度决定，遍历地址表，一个时钟周期处理一个表项。
Ｈａｓｈｉｎｇ算法：为了快速的存取地址表项，采用ｈａｓｈｉｎｇ算法［６］建立地址表项索引值与实际ＭＡＣ地址之间的对应关系（每个ＭＡＣ地址只能对应一个索引值，但是每个索引值有可能对应多个ＭＡＣ地址，即发生了地址冲突）。
使用复杂的ｈａｓｈｉｎｇ算法，会延长计算索引的时间，降低地址表的查找速度，增加交换机的包转发时延。
在交换控制芯片设计中本项目算法使用ＣＲＣ－ＣＣＩＴＴＤ多项式 为ｈａｓｈｉｎｇ函数，４８位ＭＡＣ地址由ＣＲＣ［７－８］校验方法后的结果通过ｈａｓｈｉｎｇ函数求得１６位余数，取结果１６位余数中１１个比特用于２ＫＢ地址表项索引值。Ｈａｓｈｉｎｇ函数计算的状态机如图２所示。
交换机ＭＡＣ层容纳的地址表大小是有限的，理论上实际的物理地址有２的４８次方个，地址表只能记录其中一个很小的子集，因此ｈａｓｈｉｎｇ函数不可避免地将不同的ＭＡＣ地址映射到相同的地址表项索引值。如果以太网中地址表项索引值与ＭＡＣ地址存在多对一的情况，就是发生了“地址冲突”。地址冲突的存在也说明总有部分ＭＡＣ地址丢失，不能被交换机学习到。地址冲突的解决方法在１．２中予以实现。
地址表组织结构如图３。图３左边列出的是地址表ＲＡＭ 中每个ｈａｓｈｉｎｇ桶内表项０在ＲＡＭ 中的地址。在开始地址存储和查找时，通过ＣＲＣ校验得到的索引值指向的ｈａｓｈｉｎｇ桶内表项０与表项１被读出，通过对ＭＡＣ地址域进行比较确定匹配的表项，得到转发端口的信息。
１．２ 地址表处理机制的实现方法（ＡｄｄｒＬｉｓｔ＿Ｐｒｏｃ）
１．２．１ 地址学习和查找的实现
以太网帧结构中的源地址（ｓａ＿ｍａｃ）用于地址学习。目的地址（ｄａ＿ｍａｃ）用于地址查找。
对于较大吞吐量的交换芯片，能做到平均时间复杂度满足线性的学习和查找。学习和查找采用ｈａｓｈｉｎｇ算法，发生碰撞采用ｈａｓｈｉｎｇ算法，碰撞后采用相邻空间开放定址法（ｏｐｅｎ ａｄｄｒｅｓｓｉｎｇ ｈａｓｈｉｎｇ）［９－１０］。
学习的过程如下：
（１）根据ｈａｓｈｉｎｇ索引值ｓａ＿ｉｎｄｅｘ，检索ＭＡＣ 地址表。
（２）表项中Ｖａｌｉｄ字段若为１代表该表项已占用，转（３），否则表项空闲，转（７）。
（３）表项内容中的ＭＡＣ地址与ｓａ＿ｍａｃ进行比较，若相同Ｉ＿Ｆｉｎｄ置１，转（７），否则转（４），此时发生地址冲突。
（４）ｓａ＿ｉｎｄｅｘ＋１表项中Ｖａｌｉｄ字段若为１代表此处表项已占用，转（５），否则表项空闲转（７）。
（５）表项内容中的ＭＡＣ地址与ｓａ＿ｍａｃ进行比较，若相同Ｉ＿Ｆｉｎｄ置１，转（７），否则转（６），此时发生地址冲突。
（６）此时有超过两个不同的ＭＡＣ地址映射同一索引值，并且先到的写入ｓａ＿ｉｎｄｅｘ和ｓａ＿ｉｎｄｅｘ＋１处。后面到达的ＭＡＣ地址覆盖掉ｓａ＿ｉｎｄｅｘ处表项，完成一次学习。
（７）写入该位置，Ｖａｌｉｄ置１，Ａｇｅ置１，完成一次学习。
查找的过程如下：
（１）判断是不是广播包，若是转（１０），否则转（２）。
（２）根据ｈａｓｈｉｎｇ索引值ｄａ＿ｉｎｄｅｘ，检索ＭＡＣ 地址表。
（３）ｄａ＿ｉｎｄｅｘ和ｄａ＿ｉｎｄｅｘ＋１的Ｖａｌｉｄ字段组成二元组＜ｖａｌｉｄ０，ｖａｌｉｄ１＞，＜０，０＞转（４）、＜０，１＞转（５）、＜１，０＞转（６）、＜１，１＞转（７）。
（４）ｄａ＿ｍａｃ不在地址表中，转（９）。
（５）ｄａ＿ｉｎｄｅｘ＋１表项内容中ＭＡＣ地址与ｄａ＿ｍａｃ比较，若两者相同，转（８），否则转（９）。
（６）ｄａ＿ｉｎｄｅｘ表项内容中ＭＡＣ地址与ｄａ＿ｍａｃ比较，若两者相同，转（８），否则转（９）。
（７）ｄａ＿ｍａｃ在地址表中转（８），否则转（９）。
（８）读取表项内容中的端口号，与ｄａ＿ｍａｃ组成一组数据发给到ｆｉｆｏ＿ｏｕｔ，完成一次查找。
（９）广播该ＭＡＣ地址，发送ｄａ＿ｍａｃ和需要广播标志位给ｆｉｆｏ＿ｏｕｔ，完成一次查找。
（１０）Ｉ＿Ｆｉｎｄ标志位为１代表地址表中有广播请求的ＭＡＣ地址，不需要继续广播下去。Ｉ＿Ｆｉｎｄ标志位为０代表需要继续广播下去，转（１１）。
（１１）发送ｓａ＿ｍａｃ和需要广播标志位给ｆｉｆｏ＿ｏｕｔ，完成一次查找。
１．２．２ 地址老化的实现
交换机通过端口发送和接收帧的源地址（源ＭＡＣ地址、端口号）将存储到地址表中。老化时间是一个影响交换机学习进程的参数。为地址表中每条地址项添加一个计数器用于表示该地址项的更新时间，通过查询计数器位是否为零判断一个地址是否已经老化。在更新过程中，所有的输出引脚处于“悬挂”。
老化过程如下：
（１）检测到更新信号ｕｐｄ＿ｅｎ为高电平时，开始遍历整个地址表。
（２）表项中Ａｇｅ字段为１，代表上一次遍历周期到此遍历周期内该表项对应的ＭＡＣ 地址被重新写入过，转（３），否则（４）。
（３）表项中的Ｖａｌｉｄ字段保持１，Ａｇｅ字段置０。
（４）表项中的Ｖａｌｉｄ字段置０ （删除已老化的）。
（５）等待ｕｐｄ＿ｅｎ为低电平时停止遍历，完成一次地址老化。
３ 地址表的输出调整（ｆｉｆｏ＿ｏｕｔ）
Ｆｉｆｏ＿ｏｕｔ模块根据前一级提供的各种标志信号，实现对输出的控制。输入的数据信号有源地址，目的地址，查找到的表项，输入的标志信号有ｎｄ＿ｂｒ＿ｐａｃｋｅｔ （需要广播标志），Ｉｓ＿ｂｒ＿ｐａｃｋｅｔ（是广播包标志）。
Ｉｓ＿ｂｒ＿ｐａｃｋｅｔ＝１，ｎｄ＿ｂｒ＿ｐａｃｋｅｔ＝０代表“是广播包，不需要广播”，对应地址表处理机制中的事件—接收到广播包中的ＭＡＣ地址存在地址表中。没有输出。
Ｉｓ＿ｂｒ＿ｐａｃｋｅｔ＝１，ｎｄ＿ｂｒ＿ｐａｃｋｅｔ＝１代表“是广播包，需要广播”，对应地址表处理机制中的事件—继续广播下去。ｓａ＿ｍａｃ经过封装由ｄｏｕｔ０～ｄｏｕｔ３输出。
Ｉｓ＿ｂｒ＿ｐａｃｋｅｔ＝０，ｎｄ＿ｂｒ＿ｐａｃｋｅｔ＝０代表“不是广播包，不需要广播”，对应地址表处理机制中的事件—单播包中目的地址存在地址表中。表项经过封装，对应端口输出。
Ｉｓ＿ｂｒ＿ｐａｃｋｅｔ＝０，ｎｄ＿ｂｒ＿ｐａｃｋｅｔ＝１代表“不是广播包，需要广播”，对应地址表处理机制中的事件—目的地址不存在地址表中。ｄａ＿ｍａｃ经过封装由ｄｏｕｔ０～ｄｏｕｔ３输出。
２ 不同ｈａｓｈｉｎｇ函数的冲突率
Ｈａｓｈｉｎｇ算法的主要原理就是把大范围映射到小范围，冲突率和ｈａｓｈｉｎｇ函数的选取有密切的关系，图４中选取了４种不ｈａｓｈｉｎｇ函数下发生地址冲突的概率。情况一采用的Ｈａｓｈｉｎｇ函数为ＭＡＣ地址和自身倒序做异或运算所得的结果经过ＣＲＣ计算后取最后１１位索引值；情况二采用的Ｈａｓｈｉｎｇ函数为ＭＡＣ地址和自身倒序做异或运算所得的结果经过ＣＲＣ计算后取前１１位索引值；情况三采用的Ｈａｓｈｉｎｇ函数为ＭＡＣ地址平方后取中间１１位为索引值，情况四采用的Ｈａｓｈｉｎｇ函数为将ＭＡＣ地址分割成位数相同的３部分，叠加这三部分的和取后１１位为索引值。
仿真过程描述如下：
４８位二进制数表示的范围划分为三子段，每个子段随机生成３０００个数。一共有９０００个随机ＭＡＣ地址，依次按照４种情况提供的ｈａｓｈｉｎｇ函数计算结果，索引值一样冲突加一，分别在不同的地址表容量下求冲突率。
不同ｈａｓｈｉｎｇ函数冲突率如图４所示。
仿真结果表明地址表项容量和ＭＡＣ地址数量接近时基本不发生冲突，在地址表较小情况下对于本次实验给出的信源情况三的ｈａｓｈｉｎｇ函数有较小的冲突率。所以在选取ｈａｓｈｉｎｇ函数时要结合该节点实际收发ＭＡＣ地址的概率模型，这样才能有效的降低地址冲突发生。
３ 设计与验证
仿真过程中，时钟周期１００ｎｓ，ＭＡＣ地址取４８ｂｉｔ中的后１６ｂｉｔ，地址表深度为６４，ｈａｓｈｉｎｇ算法采用ＣＲＣ８取结果的后６ｂｉｔ。这样处理的理由有两点：第一４８ｂｉｔ与１６ｂｉｔ原理相同，１６ｂｉｔ占用的资源少；第二ＭＡＣ地址前２４ｂｉｔ是由设备厂商分配的序列号，对于一部分ＭＡＣ地址只有后１６ｂｉｔ不同。
ｓａ＿ｍａｃ既是输入也是输出，ｆｉｆｏ＿ｉｎ内的寄存器保存一次输入信号，待ｈａｓｈｉｎｇ算法后和索引值同步输出，如图５所示。
图６的仿真结果中可以看到，１２００ｎｓ学习到ＭＡＣ地址（１６′ｈ７Ａ０Ｃ），１５００ｎｓ接收到对该ＭＡＣ地址的广播包，停止继续广播下去。
图７的仿真结果中可以看到２１００ｎｓ查询的目的地址（１６’ｈＣ０Ａ７）存在于地址表中，它是２０００ｎｓ写入地址表中的。
图８中所示２６００ｎｓ开始地址更新，消耗６４个时钟周期，遍历所有的表项。９０００ｎｓ后的输入和地址表更新前得输入相同，可以看出有相同的输出。
图９所示不同的标志信号控制不同的输出，可以看到１７００ｎｓ和１８００ｎｓ都是向端口２转发数据。１４００ｎｓ向４个端口广播。
４ 结束语
对于以太网交换机来说，主要工作是根据收到数据帧中的目的ＭＡＣ地址，对ＭＡＣ地址表进行查找，把数据帧转发到相应的端口。ＭＡＣ地址表的查表效率直接影响交换机的性能。Ｈａｓｈｉｎｇ算法可以实现高效率的存储和查找，但存在地址冲突，选择合适的ｈａｓｈｉｎｇ函数是解决问题的有效途径之一。比如可以统计交换机各端口ｈａｓｈｉｎｇ索引值的概率分布，找出发生冲突较高的区域，对这些区域按照概率进行排序，ｈａｓｈｉｎｇ函数针对冲突域中概率大的几个ＭＡＣ地址来构造。
工商网监
评论