Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1998-01-01

Filename

WUCS-98-13.PDF

DOI:

10.7936/K79S1P9N

Technical Report Number

WUCS-98-13

Abstract

This paper describes an algorithm which can roughly halve the size of the current Internet routing tables. This algorithm is based on the radix trie representation of routing tables, which was firstly used in the BSD Unix distributions. The binary tree representation, which is a simplified case of radix tree, does well at showing the relationships among all routing table entries and provides us a way to build a collapse algorithm based on its internal structure. The binary tree collapse algorithm consists of three techniques, with the first two quite intuitive while the third is a bit more elaborate. All techniques used in this algorithm are discussed and their effects on reducing the size of the routing table are listed and compared.

Comments

Permanent URL: http://dx.doi.org/10.7936/K79S1P9N

Download

Share

COinS