Methods, systems, and computer program products for controlling updating of a layer 3 host table based on packet forwarding lookup miss counts
Methods, systems, and computer program products for controlling updating of a layer 3 host table based on packet forwarding miss counts are disclosed. According to one method, layer 3 packets are routed using at least one of a layer 3 host table containing entries corresponding to remote hosts and a longest prefix matching table containing prefixes corresponding to remote hosts. For each layer 3 destination address for which a lookup in at least one table fails, a number of packets received within a time period are counted. Remote destination entries in the host table are replaced based on the counts.
1. A method for controlling updating of a layer 3 host table in
a packet forwarding device based on packet forwarding lookup miss counts, the method comprising:
(a) routing layer 3 packets received at a packet forwarding device using a layer 3 host table containing entries corresponding to remote hosts;
(b) for each layer 3 destination address for which a lookup in the layer 3 host table fails because the layer 3 host table lacks an entry for the layer 3 destination address:
counting by the packet forwarding device a number of packets received for the destination address within a time period;
maintaining a packet miss count table with entries for the layer 3 destination addresses for which the misses occurred and that are not in the host table, where the entries in the miss count table include the corresponding miss counts;
determining whether an entry is present for the layer 3 destination address in the packet miss count table;
in response to determining that an entry for the layer 3 destination address is not present in the packet miss count table, adding an entry for layer 3 destination address to the packet miss count table;
in response to determining that an entry is present for the layer 3 destination address in the packet miss count table, incrementing a packet miss counter for the entry; and
(c) replacing remote destination entries in the host table based on the miss counts by the packet forwarding device determining which of the entries in the miss count table should be used to replace entries in the host table based on the miss counts.
2. The method of claim 1 wherein routing layer 3 packets using a layer 3 host table includes routing layer 3 packets using a layer 3 host table implemented in hardware.
3. The method of claim 1 wherein routing layer 3 packets using a layer 3 host table includes performing a lookup in the layer 3 host table using a destination IP address extracted from each packet and determining packet forwarding information based on the lookup.
4. The method of claim 1 wherein routing layer 3 packets using a layer 3 host table performing a first lookup in the layer 3 host table, and, in response to failing to locate a matching entry in the layer 3 host table, performing a second lookup in a longest prefix matching (LPM) table.
5. The method of claim 1 comprising determining whether the host table has space available for entries corresponding to remote layer 3 hosts, and wherein performing step (c) includes replacing remote destination entries in the host table based on the counts in response to the determination that the host table does not have space available for entries corresponding to remote layer 3 hosts.
6. The method of claim 1 wherein replacing the remote destination entries in the host table based on the counts includes comparing counts associated with the packets for which the lookup failed with counts corresponding to entries in the layer 3 host table and replacing an entry in the layer 3 host table with an entry in a packet miss count table for which a layer 3 destination address lookup fails in response to determining that the count for the entry in the host table is less than or equal to the count for the entry in the packet miss count table.
7. The method of claim 1 comprising storing counts with the entries in the layer 3 host table.
8. The method of claim 7 comprising updating the counts associated with the entries in the host table in response to receiving packets that match the entries.
9. The method of claim 1 wherein replacing remote destination entries includes determining an age associated with each entry and replacing the entry in response to determining that the age meets or exceeds a threshold value.
10. The method of claim 1 wherein replacing the remote destination entries based on the counts includes replacing the remote destination entries with entries for destinations having miss counts that meet or exceed a threshold.
11. A system for controlling updating of a layer 3 host table in a layer 3 packet forwarding device based on packet forwarding lookup miss counts, the system comprising:
(a) a layer 3 host table including entries corresponding to remote hosts;
(b) a packet forwarding engine hardware for receiving layer 3 packets and for performing lookups in the layer 3 host table and routing the packets based on results of the lookups; and
(c) a host table update controller configured to:
count, for each layer 3 destination address for which a lookup in the host table fails because the host table lacks an entry corresponding to the layer 3 destination address, a number of packets received within a time period;
maintain a packet miss count table with entries for the layer 3 destination addresses for which the misses occurred and that are not in the host table, where the entries in the miss count table include the corresponding miss counts;
determine whether an entry for a destination of the packet exists in the packet miss count table, and in response to determining that entry does not exist, create an entry corresponding to the destination, and in response to determining that an entry exists for the destination in the packet miss count table, increment a packet miss count for the entry; and
replace remote destination address entries in the host table based on the miss counts by determining which of the entries in the miss count table should be used to replace entries in the host table based on the miss counts.
12. The system of claim 11 wherein the host table is implemented in hardware.
13. The system of claim 11 wherein each entry in the host table includes an Internet protocol (IP) address and corresponding packet forwarding information.
14. The system of claim 11 comprising a longest prefix matching (LPM) table, wherein the packet forwarding engine performs a lookup in the host table, and, in response to failing to locate a matching entry in the host table, the packet forwarding engine performs a lookup in the LPM table.
15. The system of claim 11 wherein the host table update controller replaces remote destination entries in the host table in response to determining that the host table does not have space available for additional remote host entries.
16. The system of claim 11 wherein the host table update controller compares counts associated with the destinations for which lookups failed with counts stored with entries in the host table and to replace entries in the host table in response to determining that the counts associated with the destinations for which the lookup fails are greater than or equal to counts associated with entries in the host table.
17. The system of claim 11 wherein the host table update controller maintains a usage count for each entry in the host table.
18. The system of claim 17 wherein the host table update controller updates the usage count for each entry in response to receiving a packet corresponding to the entry.
19. The system of claim 18 wherein the host table update controller replaces entries in the host table using the usage counts and the counts for which the lookups failed.
20. The system of claim 11 wherein the host table update controller replaces remote destination entries in the host table in response to the entries being present in the table for a predetermined time period.
21. The system of claim 11 wherein the host table update controller replaces remote destination entries in the host table with entries for destinations having packet miss counts that meet or exceed a threshold value.
22. A computer program product comprising computer-executable instructions embodied in a computer-readable non-transitory medium for performing steps comprising:
(a) routing layer 3 packets received at a packet forwarding device using a layer 3 host table containing entries corresponding to remote hosts;
(b) for each layer 3 destination address for which a lookup in the layer 3 host table fails:
counting by the packet forwarding device a number of packets received for the layer 3 destination address within a time period because the host table lacks entries corresponding to the layer 3 destination address;
maintaining a packet miss count table with entries for the layer 3 destination addresses for which the misses occurred and that are not in the host table, where the entries in the miss count table include the corresponding miss counts;
determining whether an entry is present for the layer 3 destination address in the packet miss count table;
in response to determining that an entry for the layer 3 destination address is not present in the packet miss count table, adding an entry for layer 3 destination address to the packet miss count table;
in response to determining that an entry is present for the layer 3 destination address in the packet miss count table, incrementing a packet miss counter for the entry; and
(c) replacing remote destination entries in the host table based on the miss counts by the packet forwarding device determining which of the entries in the miss count table should be used to replace entries in the host table based on the miss counts.