公开(公告)号：US20130034096A1

公开(公告)日：2013-02-07

申请号：US13649633

申请日：2012-10-11

Applicant: Huawei Technologies Co., Ltd.

Inventor： Rui Hu ,  Hongfei Chen ,  Jun Gong ,  Suping Zhai ,  Xiaozhong Wang ,  Hexuan Zhao

IPC: H04L12/44 ,  H04L12/56

CPC classification number: H04L45/54 ,  H04L45/742 ,  H04L45/748

Abstract: The embodiments of the present invention relate to a routing table establishment method and device and a routing table lookup, method and device. The routing table establishment method includes: partitioning a data structure of a routing table into a trunk and a TRIE sub-tree (101); adding entries of the routing table to the TRIE sub-tree (102); and storing an upgrade sub-node of the TRIE sub-tree's root in the trunk, where the height of the TRIE sub-tree is smaller than or equal to a set height threshold (103), and the upgrade sub-node of the TRIE sub-tree's root is a sub-root among prefix sub-nodes included in the TRIE sub-tree's root. Thereby ensuring the high compression ratio of the routing table; and the height of the TRIE sub-tree is controlled according to the height threshold, thereby reducing times for accessing a memory, improving lookup speed, and reducing lookup delay.

Abstract translation: 本发明的实施例涉及路由表建立方法和设备以及路由表查找，方法和设备。 路由表建立方法包括：将路由表的数据结构划分为中继线和TRIE子树（101）; 将所述路由表的条目添加到所述TRIE子树（102）; 并且将所述TRIE子树的根的升级子节点存储在所述中继线中，其中所述TRIE子树的高度小于或等于设定的高度阈值（103），并且所述TRIE的升级子节点 子树的根是包含在TRIE子树根中的前缀子节点之间的子根。 从而确保路由表的高压缩比; 并根据高度阈值控制TRIE子树的高度，从而减少访问存储器的时间，提高查找速度，减少查找延迟。