Predictive routing table cache population

• US 6,816,457 B1
• Filed: 08/07/2000
• Issued: 11/09/2004
• Est. Priority Date: 06/02/2000
• Status: Expired due to Term

• Current Assignee: Abdullah Ali Bahattab
• Original Assignee: Abdullah Ali Bahattab
• Inventors: Bahattab, Abdullah Ali
• Primary Examiner(s): Patel, Alit
• Assistant Examiner(s): SCHULTZ, WILLIAM C
• Application Number:
  US09/633,754
• Time in Patent Office: 1,555 Days
• Field of Search: 370/229, 370/230, 370/230.1, 370/231, 370/232, 370/234, 370/235, 370/389, 370/392, 370/395.7, 370/428, 370/429, 370/395.2, 370/395.21
• US Class Current: 370/232
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags

Abstract

A router and method for routing table cache population technique is disclosed. In particular, the illustrative embodiment routes packets through it more quickly than comparatively expensive routers in the prior art. The present invention recognizes that a fast router has small routing table cache that has a high hit ratio and that a high hit ratio can be achieved with a small routing table cache by predicting which entries will be needed in the routing table cache in the future and by populating the routing table cache with those entries before they are needed. The illustrative embodiment of the present invention comprises: an input port for receiving a succession of packets, wherein each of the packets comprises a destination address; a plurality of output ports; a switching fabric for interconnecting the input port to each of the plurality of output ports; a processor or building a temporal model of the occurrence of the destination addresses at the input port, for populating the routing table cache based on the temporal model and at least one entry that is stored in a routing table, and for routing at least one of the packets from the input port to one of the output ports through the switching fabric based on the entry that is stored in the routing table cache.

Claims

1. A router comprising:

an input port for receiving a succession of packets, wherein each of said packets comprises a destination address;

a plurality of output ports;

a switching fabric for interconnecting said input port to each of said plurality of output ports; and

a processor for building a temporal model of the occurrence of said destination addresses at said input port, for populating said routing table cache based on said temporal model and at least one entry that is stored in a routing table, and for routing at least one of said packets from said input port to one of said output ports through said switching fabric based on said entry that is stored in said routing table cache;

wherein said temporal model is based on the autoregressive moving average of the occurrence of said destination addresses.

2. A method comprising:

receiving a temporal succession of packets at an input port, wherein each of said packets comprises a destination address;

generating a temporal model based on the occurrence of said destination addresses;

populating a routing table cache based on said temporal model and at least one entry that is stored in a routing table; and

forwarding at least one of said packets from said input port to one of a plurality of output ports based on said entry that is stored in said routing table cache;

wherein said temporal model is based on the autoregressive moving average of the occurrence of said destination addresses.