Patent ID: 7573880

Claim:
A method for storing information for packet routes in a routing table in one or more memory devices, the routing table used for routing packets through a multi-node packet-based network, each packet route comprising an unexpanded prefix and routing data, the method comprising: (a) dividing the packet routes into two or more different classes, at least one of which corresponds to an expanded prefix length; (b) generating two or more expanded-prefix packet routes for at least one packet route by expanding the unexpanded prefix of the packet route to the expanded prefix length corresponding to the packet route's class; and (c) for each of one or more of the two or more expanded-prefix packet routes: (1) dividing the expanded prefix into an index and a tag, wherein: the routing table has a different row for each different possible index value; and the routing table has a plurality of columns adapted to store information for a corresponding plurality of expanded-prefix packet routes; and (2) storing information in the routing table for the expanded-prefix packet route, wherein: the information comprises the corresponding tag, the length of the corresponding unexpanded prefix, and the corresponding routing data; and the information is stored into a row corresponding to the index value and into an available column.