最適ルーティング・テーブル圧縮のためのルータ及び方法

Japanese Patent JP4268337

B2

A method for compressing a routing table involves constructing a binary tree representation of the routing table. The compression method makes three passes through the tree. In a first pass, the compression method propagates routing information down to the tree leaves. During this pass, the program assigns every leaf node in the tree an associated next hop or an inherited next hop from a higher level ancestral node. In a second pass, the compression method migrates prevalent next hops up the tree. This bottom up pass involves forming a set of next hops at a parent node by supernetting the sets of next hops A and B for a pair of child nodes corresponding to the parent node, according to the following operation:where A*B is a set of next hops formed at the parent node. In the third pass, the compression method eliminates redundant branches in the tree. This top down pass begins at a parent node and selects a next hop from a parent node. The method then examines a child node branching from the parent node to determine whether the selected next hop is an element of next hops for the child node. If it is, the method eliminates the next hops for the child node. After the tree is restructured by the three-pass process, the compression method converts it back to a new routing table.

Draves, richard pee
King, Christopher S
Venkata Charlie, Srinivasan

JP2000581783A

May 27, 2009

August 31, 1999

Click for automatic bibliography generation  

MICROSOFT CORPORATION

H04L12/56; H04L12/46

1998 ACM SIGMETRICS,p1-10
IEEE INFOCOM'99,p88-97
ACM Computer Communications Review,Vol.27 No.4,p3-14
ACM Computer Communications Review,Vol.27 No.4,p25-36
IEEE Journal on Selected Areas in Communications,Vol.17 No.6,p1083-1092

Yoshikazu Tani
Kazuo Abe

Previous Patent: ABRASIVE

Next Patent: 埋込型ボックスの防耐火構造