公开(公告)号：KR1020030009707A

公开(公告)日：2003-02-05

申请号：KR1020010044274

申请日：2001-07-23

Applicant: 한국전자통신연구원

Inventor： 이상연 ,  이강복 ,  이형섭

IPC: H04L12/44

Abstract: PURPOSE: A method for retrieving and updating a tree using a node structure of a multi search tree is provided to reduce a retrieving time by increasing the number of keys capable of being stored in a node using one pointer necessary for one node of a B tree and decreasing the level number of tree path. CONSTITUTION: An initial 16-bit array is retrieved using an upper 16-bit segment of an inputted destination IP(Internet Protocol) address(101). It is judged whether an "I" flag of a corresponding entry is true in the retrieved initial 16-bit array(102). If the "I" flag of the corresponding entry is true, it is moved to a root node indicated by a node pointer and a multi-path retrieval is performed using a lower 16-bit offset of the inputted destination IP address(103). It is judged whether an exact matching is achieved before a leaf node is reached(104). If the exact matching is achieved before the leaf node is reached, it is judged whether the arrival of the retrieval is a branch node or a leaf node(105). If the arrival of the retrieval is the leaf node, a region port stored in a register is returned(106).

Abstract translation: 目的：提供使用多搜索树的节点结构来检索和更新树的方法，以通过使用B树的一个节点所需的一个指针增加能够存储在节点中的密钥的数量来减少检索时间 并减少树路径的数量。 构成：使用输入的目标IP（因特网协议）地址（101）的高16位段来检索初始的16位阵列。 在检索的初始16位阵列（102）中判断相应条目的“I”标志是否为真。 如果对应条目的“I”标志为真，则将其移动到由节点指针指示的根节点，并且使用输入的目的地IP地址（103）的低16位偏移量执行多路径检索。 判断在到达叶节点之前是否实现精确匹配（104）。 如果在到达叶节点之前实现精确匹配，则判断检索的到达是否是分支节点或叶节点（105）。 如果检索的到达是叶节点，则返回存储在寄存器中的区域端口（106）。

公开(公告)号：KR1020020059238A

公开(公告)日：2002-07-12

申请号：KR1020010085728

申请日：2001-12-27

Applicant: 한국전자통신연구원

Inventor： 이강복 ,  이형호 ,  이형섭

IPC: G06F17/30

CPC classification number: H04L45/742 ,  H04L49/90 ,  H04L49/901 ,  H04L49/9057 ,  Y10S707/99933

Abstract: PURPOSE: A method for generating a node of a multiple-search tree and for searching the data of a multiple-search node tree structure is provided to receive associated information in one cache line by using one pointer recorded in a corresponding node regardless of the number of the keys used in one node. CONSTITUTION: In an 8-way search tree applied with a B tree, one node consists of 7 32 bit keys(K1-K7), a 16 bit node pointer(Po), and a 16 bit key pointer(Kp). The keys express the value of the keys. The node pointer expresses the position of the first node. The key pointer expresses the position of the first key. Po means the address of the first node among children nodes is 20000. The key pointer is a value indicating the pointer corresponding to the first key of a node. In a branch node, the key pointer indicates the information on the corresponding port number when the value is the same as the key value. Otherwise, the key pointer indicates the area information enabling a maximum effective matching method.

Abstract translation: 目的：提供一种生成多搜索树节点并搜索多搜索节点树结构的数据的方法，通过使用记录在相应节点中的一个指针来接收一个高速缓存行中的相关信息，而不管数目如何 在一个节点中使用的密钥。 规定：在采用B树的8路搜索树中，一个节点由7个32位密钥（K1-K7），16位节点指针（Po）和16位密钥指针（Kp）组成。 键表示键的值。 节点指针表示第一个节点的位置。 键指针表示第一个键的位置。 Po表示子节点之间的第一个节点的地址是20000.关键指针是指示对应于节点的第一个键的指针的值。 在分支节点中，当该值与密钥值相同时，密钥指针指示相应端口号的信息。 否则，键指针指示能够进行最大有效匹配方法的区域信息。