METHOD AND SYSTEM FOR EFFICIENT ROUTING TABLE COMPRESSION AND FAST ROUTING LOOKUPS

摘要

A system for IP routing lookup in a routing table, comprising entries of arbitrary length prefixes with associated next-hop information in a next-hop table, for determining where IP datagrams are to be forwarded, and data structure means for representing the set of dominating points in the IP address space for each prefix in the routing table, said means comprising three levels of compressed pointer arrays (CPA), each including a chunk and an array of associated pointers, wherein each pointer comprises a next hop index or a pointer to the next level of chunk.