公开(公告)号：US08965911B2

公开(公告)日：2015-02-24

申请号：US13629912

申请日：2012-09-28

Applicant: Metaswitch Networks Ltd.

Inventor： Adam Dinwoodie

IPC: G06F17/30 ,  H04L12/745

CPC classification number: G06F17/30327 ,  G06F17/30625 ,  H04L45/748 ,  Y10S707/956

Abstract: Nodes in a tree data structure are associated with respective node keys. At least some of the nodes are associated with at least one respective node rank. The structure is searched to attempt to identify a preferred prefix-matching node on the basis of attempting to find a prefix-matching node that has a prefix match with a search key and which has a preferred node rank relative to a node rank associated with a node which may have a longer prefix match. If the prefix-matching node is identified, a dependent node rank identifier associated with the prefix-matching node is used to determine that the prefix-matching node has the preferred node rank. The dependent node rank identifier indicates at least a node rank of a node which may have a longer prefix match than the prefix-matching node. The prefix-matching node is selected, if identified, as a preferred prefix-matching node.

Abstract translation: 树状数据结构中的节点与相应的节点密钥相关联。 至少一些节点与至少一个相应的节点等级相关联。 搜索结构以尝试基于尝试找到具有与搜索关键字匹配的前缀的前缀匹配节点并且具有相对于与一个节点相关联的节点等级的优选节点等级的首选前缀匹配节点 可能具有较长前缀匹配的节点。 如果前缀匹配节点被识别，则使用与前缀匹配节点相关联的依赖节点等级标识符来确定前缀匹配节点具有优选节点等级。 依赖节点等级标识符至少指示可能具有比前缀匹配节点更长的前缀匹配的节点的节点等级。 如果标识，则选择前缀匹配节点作为优选前缀匹配节点。

公开(公告)号：US20130268542A1

公开(公告)日：2013-10-10

申请号：US13629912

申请日：2012-09-28

Applicant: METASWITCH NETWORKS LTD.

Inventor： Adam Dinwoodie

IPC: G06F17/30

CPC classification number: G06F17/30327 ,  G06F17/30625 ,  H04L45/748 ,  Y10S707/956

Abstract: Nodes in a tree data structure are associated with respective node keys. At least some of the nodes are associated with at least one respective node rank. The structure is searched to attempt to identify a preferred prefix-matching node on the basis of attempting to find a prefix-matching node that has a prefix match with a search key and which has a preferred node rank relative to a node rank associated with a node which may have a longer prefix match. If the prefix-matching node is identified, a dependent node rank identifier associated with the prefix-matching node is used to determine that the prefix-matching node has the preferred node rank. The dependent node rank identifier indicates at least a node rank of a node which may have a longer prefix match than the prefix-matching node. The prefix-matching node is selected, if identified, as a preferred prefix-matching node.

Abstract translation: 树状数据结构中的节点与相应的节点密钥相关联。 至少一些节点与至少一个相应的节点等级相关联。 搜索结构以尝试基于尝试找到具有与搜索关键字匹配的前缀的前缀匹配节点并且具有相对于与一个节点相关联的节点等级的优选节点等级的首选前缀匹配节点 可能具有较长前缀匹配的节点。 如果前缀匹配节点被识别，则使用与前缀匹配节点相关联的依赖节点等级标识符来确定前缀匹配节点具有优选节点等级。 依赖节点等级标识符至少指示可能具有比前缀匹配节点更长的前缀匹配的节点的节点等级。 如果标识，则选择前缀匹配节点作为优选前缀匹配节点。