[0026] 以下通过特定的具体实例说明本发明的实施方式，本领域技术人员可由本说明书所揭露的内容轻易地了解本发明的其他优点与功效。本发明还可以通过另外不同的具体实施方式加以实施或应用，本说明书中的各项细节也可以基于不同观点与应用，在没有背离本发明的精神下进行各种修饰或改变。需说明的是，在不冲突的情况下，以下实施例及实施例中的特征可以相互组合。
[0027] 需要说明的是，以下实施例中所提供的图示仅以示意方式说明本发明的基本构想，遂图式中仅显示与本发明中有关的组件而非按照实际实施时的组件数目、形状及尺寸绘制，其实际实施时各组件的型态、数量及比例可为一种随意的改变，且其组件布局型态也可能更为复杂。
[0028] 本发明的基于跳表的MAC表项检索方法及系统采用跳表这种相对比较高效的数据结构，对业务流中新增的、删除的以及变更的MAC表项信息进行本地保存与管理，并与PON MAC芯片交互获取MAC地址对应的ONU ID，并对应保存到跳表结构。
[0029] 跳表是一种随机化的数据结构，只不过在链表的基础上增加了跳跃功能。正是这个跳跃功能，使得在查找元素时，跳表能够提供O(logN)的时间复杂度。红黑树等这样的平衡数据结构查找的时间复杂度也是O(logN)，但是相比较实现像红黑树这样的数据结构，跳表实现显得更加简洁快速。因此，本发明的基于跳表的MAC表项检索方法能够在查询多条甚至全部MAC表项时更加地快速与准确。
[0030] 具体地，跳表通过在每个节点中增加了向前的指针，从而提升查找的效率。跳跃列表是按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的“快速跑道”，而最高层的元素在O(log1/p n)个列表中出现。跳表的核心思想就是把数据不断的提取出来，作为索引，其原理如图2所示。跳表以空间换时间，无论是单条表项还是多条甚至全部表项，都可以采用直接对本地跳表进行查询与搜索，从而加快了数据的处理速度。
[0031] 因此，跳表至少包括两层结构；每一层都是一个有序的链表；最底层的链表包含所有元素；上一层的元素均包含在下一层链表中，对下一层链表进行检索时，跳过上一层所包含的元素。故跳表具有如下性质：
[0032] (1)由至少两层结构组成；
[0033] (2)每一层都是一个有序的链表；
[0034] (3)最底层(Level 1)的链表包含所有元素；
[0035] (4)如果一个元素出现在Level i的链表中，则它在Level i之下的链表也都会出现。
[0036] (5)每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。
[0037] 参照图1，本发明的基于跳表的MAC表项检索方法包括以下步骤：
[0038] 1)将MAC表项信息以跳表的方式进行存储。
[0039] 其中，MAC表项信息包括MAC地址对应的VLAN、流量和ONU ID。MAC表项信息存储在包括至少两层结构的跳表中。
[0040] 2)检索所需的MAC表项信息时，在跳表中进行查找。
[0041] 其中，由于跳表由很多层组成，在查找MAC表项信息时，首先从跳表的较高层开始查找，并根据查找结果跳至下一层继续进行查找。如此反复，直至查找到为止。由于跳表结果的特殊性，使得MAC表项信息的查找速度相较于逐个查找的速度有很大的提高。
[0042] 如图2所示的跳表中，每个节点中存储一个MAC表项信息。该跳表共包含两层结构，其中第一层包括5-68这64个节点；第二层，也就是第一层的下层包含4-68这65个节点。当目标节点为节点4时，首先检索跳表的第一层。由于第一层包含的是5-68的节点，故通过对第一层的查找，无法找到节点4；于是转向第二层进行查找，由于第一层已经对5-68的节点进行过查找，故在第二层查找时，跳过5-68的节点，只对剩余节点进行查找，故在第二层时通过一次查找即可找到节点4，从而相较于逐个遍历的查找方式，极大地提高了检索速度。
[0043] 本发明的基于跳表的MAC表项检索方法在MAC表项的新增、删除以及变更过程中，业务进程根据不同的指示(indication)回应，会自动的增添与删除相关的MAC配置信息，同时查询对应的ONU ID，并把对应的VLAN和流量等信息保存到跳表。
[0044] 具体地，新增MAC表项时，与PON MAC芯片进行交互获取MAC地址对应的ONU ID，并将MAC地址对应的虚拟局域网(Virtual Local Area Network，VLAN)、流量(flow)和ONU ID保存至跳表。
[0045] 删除MAC表项时，以MAC地址为关键值，从跳表中删除该MAC地址对应的MAC表项。
[0046] 变更MAC表项时，与PON MAC芯片进行交互获取MAC地址对应的ONU ID，从跳表中删除该MAC地址对应的MAC表项，并更新流量值，并将VLAN、更新的流量和ONU ID保存至跳表。
[0047] 参照图3，本发明的基于跳表的MAC表项检索系统包括存储模块1和查找模块2。
[0048] 存储模块1用于将MAC表项信息以跳表的方式进行存储储。
[0049] 其中，MAC表项信息包括MAC地址对应的VLAN、流量和ONU ID。MAC表项信息存储在包括至少两层结构的跳表中。
[0050] 查找模块2与存储模块1相连，用于在检索所需的MAC表项信息时，在跳表中进行查找。
[0051] 其中，由于跳表由很多层组成，在查找MAC表项信息时，首先从跳表的较高层开始查找，并根据查找结果跳至下一层继续进行查找。如此反复，直至查找到为止。由于跳表结果的特殊性，使得MAC表项信息的查找速度相较于逐个查找的速度有很大的提高。
[0052] 本发明的基于跳表的MAC表项检索方法在MAC表项的新增、删除以及变更过程中，业务进程根据不同的指示(indication)回应，会自动的增添与删除相关的MAC配置信息，同时查询对应的ONU ID，并把对应的VLAN和流量等信息保存到跳表。
[0053] 具体地，新增MAC表项时，与PON MAC芯片进行交互获取MAC地址对应的ONU ID，并将MAC地址对应的虚拟局域网(Virtual Local Area Network，VLAN)、流量(flow)和ONU ID保存至跳表。
[0054] 删除MAC表项时，以MAC地址为关键值，从跳表中删除该MAC地址对应的MAC表项。
[0055] 变更MAC表项时，与PON MAC芯片进行交互获取MAC地址对应的ONU ID，从跳表中删除该MAC地址对应的MAC表项，并更新流量值，并将VLAN、更新的流量和ONU ID保存至跳表。
[0056] 综上所述，本发明的基于跳表的MAC表项检索方法及系统通过采用跳表这种数据结构，对MAC表项信息进行统一管理，提升了MAC配置表项查询与反查的效率；数据的管理更加的简洁与高效，在查询多条甚至全部MAC表项时更加地快速与准确。所以，本发明有效克服了现有技术中的种种缺点而具高度产业利用价值。
[0057] 上述实施例仅例示性说明本发明的原理及其功效，而非用于限制本发明。任何熟悉此技术的人士皆可在不违背本发明的精神及范畴下，对上述实施例进行修饰或改变。因此，举凡所属技术领域中具有通常知识者在未脱离本发明所揭示的精神与技术思想下所完成的一切等效修饰或改变，仍应由本发明的权利要求所涵盖。
