Back to results
US 7,398,278 B2Granted
Prefix processing technique for faster IP routing
AssigneesNEC Electronics Corporation, NEC Laboratories America, Inc.
InventorsSrihari Cadambi, Srimat Chakradhar, Hirohiko Shibata
Life of this patent
Estimating the term…
Abstract
A method of storing addresses in a database comprising generating original prefixes representing the addresses to be stored in the database. The prefix lengths are determined dynamically. Reduced prefixes are generated by collapsing or expanding the original prefixes such that a number of reduced prefixes is less than a number of original prefixes. The reduced prefixes are stored in the database.
Claims6
A method of storing addresses in a database comprising:
- generating original prefixes representing the addresses to be stored in the database;
- dynamically determining prefix lengths;
- generating reduced prefixes by at least one of collapsing and collapsing followed by expanding the original prefixes such that a number of reduced prefixes is less than a number of original prefixes, wherein the expanding is performed using a sub-process comprising:
- (a) selecting a largest prefix length;
- (b) allocating prefixes of the largest prefix length into one or more bins with preselected capacities;
- (c) selecting a bin from the number of bins that is partially filled;
- (d) expanding a subset of prefixes of a next largest populated length and allocating them to the selected bin until the selected bin is full;
- (e) repeating (a) through (d) for all prefix lengths;
- and
- storing the reduced prefixes in the database.
7 more elements
Dependencies are inferred from the claim text.