METHOD AND SYSTEM FOR FAST IP ROUTING LOOKUP USING FORWARDING TABLES WITH GUARANTEED COMPRESSION RATE AND LOOKUP PERFORMANCE

摘要

A method for IP routhing lookup to determine where to forward an IP -datagram with a given destination address by retrieving from a routing table a next/hop index indicating where to forward said datagram, said next/hop index being associates with the longest matching prefix of said destination address, said address being a number in an address universe U, whereing a set of address prefixes P and a mapping of P onto a set of next/hop indices D are converted into a set of ranges R, constituting a partition of U, and a mapping of R onto D. The method involves the steps of building and storing in a memory a forwarding table representation from R and D by using a predetermined layered data structure where the construction of the layer is selected depending on the range density ¦R´¦ for the sub-universe U´represented by that layer to get a space efficient representation of the set of ranges R, and performing the lookup by a range matching operation in said forwarding table. A corresponding system comprises a first converting means for converting a set of address prefixes P into a set of ranges R constituting a partition of said universe U and a second converting means for converting the mapping from P onto a set of next-hop indices D to an equivalent mapping from R onto D. The system also comprises data structuring means for forming predetermined layered datastructures T representing the routing table, and building and memory means for building and storing a forwarding tablerepresentation from R and D by using a predetermined layered data structure where the construction of the layer is selected depending on the range density ¦R´¦ for the sub-universe U´ represented by that layer to get a space efficient representation of the set of ranges R, and means for performing the lookup by a range matching operation in said forwarding table.