Diversified host based route selection metric
View Patent ↗An embodiment of the invention evaluates the suitability of routes for use in a network route cache. An embodiment of the invention allows the use of network routing caches to be optimized such that routes that are not used to route to a large number of destinations can be offloaded into a less expensive host route cache.
1. A method for a diversified host based route selection metric, the method comprising:
using a diversified route profile table to measure values of a plurality of route information in a routing cache;
wherein a value is based on a breadth of use for a route and a frequency of use for the route, wherein the breadth of use indicates a number of destinations of packets in a sampling period for the route, and wherein the frequency of use indicates a number of packets that were transmitted along the route in the sampling period; and
removing, from the routing cache, a route information with a lowest value and subsequently adding a new route information to the routing cache.
2. The method of claim 1 , wherein data collected in the table is used by an analyzer to rank the routes based on the values of the routing information.
3. The method of claim 1 , wherein the rank of the routes is used by a route selection algorithm to determine which routes in a routing table should be programmed into a network route cache.
4. The method of claim 1 , wherein the routing cache comprises a network route cache and a host route cache.
5. The method of claim 4 , wherein the use of the network routing cache is optimized such that routes that are not used to route to a large number of destinations can be offloaded into the host route cache.
6. The method of claim 4 , wherein the use of the network routing cache is optimized such that routes that are used to route to a large number of destinations are stored in the network routing cache.
7. The method of claim 1 , further comprising:
using a set of IP addresses that appear in a profile table, over the sampling period to measure the value of maintaining each route in a route cache.
8. The method of claim 7 , wherein the route cache is a routing table that only contains a subset of all the routes that are known by the router knows.
9. The method of claim 1 , further comprising:
assigning each route information, in a route cache, a unique identifier that can be inserted into a recorded data for each address that is programmed into the profile table, in order to improve the efficiency of evaluating routes in the routing cache.
10. The method of claim 1 , further comprising:
using a programmable hash function to generate the hash value hash(Pkt.daIP).
11. The method of claim 1 , further comprising:
varying a hash function that is used between sampling periods for the same route set in order to improve the quality of the data that is collected.
12. The method of claim 1 , further comprising:
shortening the time of the sampling period in order to obtain a more complete list of IP addresses that are using a particular set of routes.
13. The method of claim 12 , wherein if the time of the sampling period is shortened to correspond to the length of time that it takes to transmit a single packet, then a complete list of all IP addresses that are using a particular set of routes can be generated.
14. The method of claim 1 , further comprising:
adding a counter to each hash entry in a profile table, where the counter will be incremented for each time that a hash entry is written to.
15. The method of claim 1 , further comprising:
adding a counter for each hash entry in a profile table, where the counter will be incremented every time the hash entry is written with the same IP address and is reset every time the entry is written with a new IP address.
16. The method of claim 1 , further comprising:
using a list instead of a hash for profiling route breadth and frequency.
17. The method of claim 1 , further comprising:
using different inputs to a profiler other than the destination address of packets.
18. The method of claim 17 , wherein the different inputs are used to measure the breadth and frequency of flows as well as host routes.
19. The method of claim 1 , further comprising:
identifying routes by use of suitable identifier technique.
20. An apparatus for a diversified host based route selection metric, the apparatus comprising:
a device including a routing cache and a route profiler configured to use a diversified host route metric hash to measure values of a plurality of route information in the routing cache;
wherein a value is based on a breadth of use for a route and a frequency of use for the route, wherein the breadth of use indicates a number of destinations of packets in a sampling period for the route, and wherein the frequency of use indicates a number of packets that were transmitted along the route in the sampling period;
said device including a route selection algorithm configured to remove, from the routing cache, a route information with a lowest value and subsequently add a new route information to the routing cache.
21. The apparatus of claim 20 , wherein the breadth of use and frequency of use are used by an analyzer to rank the routes based on the values of the route information.
22. The apparatus of claim 20 , wherein the rank of the routes is used by a route selection algorithm to determine which routes in a routing table should be programmed into a network route cache.
23. The apparatus of claim 20 , wherein the routing cache comprises a network route cache and a host route cache.
24. The apparatus of claim 20 , wherein the use of the network routing cache is optimized such that routes that are not used to route to a large number of destinations can be offloaded into the host route cache.
25. The apparatus of claim 20 , wherein the use of the network routing cache is optimized such that routes that are used to route to a large number of destinations are stored in the network routing cache.
26. The apparatus of claim 20 wherein the route profiler is configured to use a set of IP addresses that appear in a profile table, over the sampling period to measure the value of maintaining each route in a route cache.
27. The apparatus of claim 26 , wherein the route cache is a routing table that only contains a subset of all the routes that are known by the router.
28. The apparatus of claim 20 , wherein the route profiler is configured to assign each route information, in a route cache, a unique identifier that can be inserted into a recorded data for each address that is programmed into a programmable hash function, in order to improve the efficiency of evaluating routes in the routing cache.
29. The apparatus of claim 20 , wherein the route profiler is configured to use a programmable hash function to generate the hash value hash (Pkt.daIP).
30. The apparatus of claim 20 , wherein the route profiler is configured to vary a hash function that is used between successive sampling periods for the same route set in order to improve the quality of the data that is collected.
31. The apparatus of claim 20 , wherein the route profiler is configured to shorten the time of the sampling period in order to obtain a more complete list of IP addresses that are using a particular set of routes.
32. The apparatus of claim 20 , wherein if the time of the sampling period is shortened to correspond to the length of time that it takes to transmit a single packet, then a complete list of all IP addresses that are using a particular set of routes can be generated.
33. The apparatus of claim 20 , wherein the route profiler further comprises:
a counter to each hash entry in a profile table, where the counter will be incremented for each time that a hash entry is written to.
34. The apparatus of claim 20 , wherein the route profiler further comprises:
a counter for each hash entry in a profile table, where the counter will be incremented every time the hash entry is written with the same IP address and is reset every time the entry is written with a new IP address.
35. The apparatus of claim 20 , wherein the route profiler is configured to use a list instead of a hash for profiling route breadth and frequency.
36. The apparatus of claim 20 , wherein the route profiler is configured to use different inputs other than the destination address of packets.
37. The apparatus of claim 20 , wherein the different inputs are used to measure the breadth and frequency of flows as well as host routes.
38. The apparatus of claim 20 , wherein the route profiler is configured to identify routes by use of suitable identifier technique.
39. An apparatus for a diversified host based route selection metric, the apparatus comprising:
a device including a routing cache and means for using a diversified route profile table to measure values of a plurality of route information in the routing cache;
wherein a value is based on a breadth of use for a route and a frequency of use for the route, wherein the breadth of use indicates a number of destinations of packets in a sampling period for the route, and wherein the frequency of use indicates a number of packets that were transmitted along the route in the sampling period;
said device including means for removing, from the routing cache, a route information with a lowest value and subsequently adding a new route information to the routing cache.
40. An article of manufacture, comprising:
a machine-readable medium having stored thereon instructions to:
use a diversified route profile table to measure values of a plurality of route information in a routing cache;
wherein a value is based on a breadth of use for a route and a frequency of use for route, wherein the breadth of use indicates a number of destinations of packets in a sampling period for the route, and wherein the frequency of use indicates a number of packets that were transmitted along the route in the sampling period; and
remove, from the routing cache, a route information with a lowest value and subsequently adding a new route information to the routing cache.