High speed routing using compressed tree process

摘要: A router uses the destination address of its incoming packets to decide proper outgoing interfaces by searching among all stored prefixes for prefix which has longest match when compared in packet. Prefix trees are employed represent set be searched and high-speed, matches performed. An efficient data structure compresses any tree so that number memory accesses needed find depends only on length rather than prefixes. Illustratively, four, 64-bit required each IPv4 worst case, while 3 Mbytes store a 128K-entry routing table.