DISTRIBUTED COORDINATION OF CACHING AND PROCESSING BY NETWORKING DEVICES

• US 20190079869A1
• Filed: 09/11/2017
• Published: 03/14/2019
• Est. Priority Date: 09/11/2017
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Baldi, Mario, Sapio, Amedeo, Risso, Fulvio Giovanni Ottavio, Anand, Narendra, Nucci, Antonio
• Granted Patent: US 10,642,739 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0817 using directory methods
• CPC Class Codes: G06F 2212/284 being distributed
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data

Abstract

In one embodiment, a device in a network receives one or more data units. The device calculates a hash value based on the one or more data units and using a hash function. Ranges of hash values generated by the hash function are assigned to different devices along the path such that any given hash value generated by the hash function is assigned to a predefined number of the devices along the path. The device determines whether the calculated hash value is within the range of hash values assigned to the device. The device stores data derived from the one or more data units, when the device determines that the calculated hash value is within the range of hash values assigned to to the device.

Claims

1. A method comprising:

receiving, at a device along a path in a network, one or more data units;

calculating, by the device, a hash value based on the one or more data units and using a hash function, wherein ranges of hash values generated by the hash function are assigned to different devices along the path such that any given hash value generated by the hash function is assigned to a predefined number of the devices along the path;

determining, by the device, whether the calculated hash value is within the range of hash values assigned to the device; and

storing, by the device, data derived from the one or more data units, when the device determines that the calculated hash value is within the range of hash values assigned to the device.

2. The method as in claim 1, wherein the data derived from the one or more data units comprise data copied from the one or more data units.

3. The method as in claim 1, further comprising:

performing, by the device, a computation based on the one or more data units, when the device determines that the calculated hash value is within the range of hash values assigned to the device, wherein the stored data derived from the one or more data units comprises an output of the computation.

4. The method as in claim 1, further comprising:

adjusting, by the device, the ranges of hash values assigned to the different devices along the path, in response to determining that a routing change to the path has occurred.

5. The method as in claim 1, further comprising:

identifying, by the device, an ingress and egress of the path by analyzing the one or more data units; and

determining, by the device, the range of hash values assigned to the device based on the identified ingress and egress of the path.

6. The method as in claim 1, further comprising:

maintaining, by the device, an index value associated with the stored data derived from the one or more data units;

retrieving, by the device, the stored data derived from the one or more data units using the index value and in response to a query from a remote device; and

providing, by the device, the stored data to the remote device.

7. The method as in claim 6, further comprising:

receiving, at the device, the query from the remote device, wherein the index value is based on the calculated hash value, and wherein the query comprises the index value.

8. The method as in claim 1, wherein the path is a first path in a set of equal-cost multi-path (ECMP) paths with different egresses, and wherein a range of hash values assigned to one or more devices along the first path that do not overlap a second ECMP path in the set are apportioned and assigned to one or more devices along the second ECMP path and are not in the first path.

9. The method as in claim 1, wherein the path is a first path in a set of equal-cost multi-path (ECMP) paths with different intermediate devices, and wherein a range of hash values assigned to one or more intermediate devices along the first path that do not overlap a second ECMP path in the set are apportioned and assigned to one or more intermediate devices along the second ECMP path and are not in the first path.

10. The method as in claim 1, wherein the path is a first path in a set of equal-cost multi-path (ECMP) paths with different ingress devices, and wherein a range of hash values assigned to the ingress along the first path is apportioned and assigned to a set of one or more devices along a second ECMP path in the set of ECMP paths, wherein the set of one or more devices along the second ECMP path comprises one or more devices that are not along the first path.

11. An apparatus, comprising:

one or more network interfaces to communicate with a network;

a processor coupled to the network interfaces and configured to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed configured to;

receive one or more data units;

calculate a hash value based on the one or more data units and using a hash function, wherein ranges of hash values generated by the hash function are assigned to different devices along the path such that any given hash value generated by the hash function is assigned to a predefined number of the devices along the path;

determine whether the calculated hash value is within the range of hash values assigned to the apparatus; and

store data derived from the one or more data units, when the apparatus determines that the calculated hash value is within the range of hash values assigned to the apparatus.

12. The apparatus as in claim 11, wherein the data derived from the one or more data units comprise data copied from the one or more data units.

13. The apparatus as in claim 11, wherein the process when executed is further configured to:

perform a computation based on the one or more data units, when the apparatus determines that the calculated hash value is within the range of hash values assigned to the apparatus, wherein the stored data derived from the one or more data units comprises an output of the computation.

14. The apparatus as in claim 11, wherein the process when executed is further configured to:

adjust the ranges of hash values assigned to the different devices along the path, in response to determining that a routing change to the path has occurred.

15. The apparatus as in claim 11, wherein the ranges of hash values assigned to the different devices along the path are based on routing information in the network.

16. The apparatus as in claim 11, wherein the process when executed is further configured to:

maintain an index value associated with the stored data derived from the one or more data units;

retrieve the stored data derived from the one or more data units using the index value and in response to a query from a remote device; and

provide the stored data to the remote device.

17. The apparatus as in claim 16, wherein the process when executed is further configured to:

receive the query from the remote device, wherein the index value is based on the calculated hash value, and wherein the query comprises the index value.

18. The apparatus as in claim 11, wherein the process when executed is further configured to:

apportion a range of hash values assigned to a particular device along the path to one or more other devices along another path in the network.

19. A tangible, non-transitory, computer-readable media having software encoded thereon, the software when executed by a device along a path in a network cause the device to perform a process comprising:

receiving, at the device, one or more data units;

calculating, by the device, a hash value based on the one or more data units and using a hash function, wherein ranges of hash values generated by the hash function are assigned to different devices along the path such that any given hash value generated by the hash function is assigned to a predefined number of the devices along the path;

determining, by the device, whether the calculated hash value is within the range of hash values assigned to the device; and

storing, by the device, data derived from the one or more data units, when the device determines that the calculated hash value is within the range of hash values assigned to the device.

20. The computer-readable medium as in claim 19, wherein the process further comprises:

identifying, by the device, an ingress and egress of the path by analyzing the one or more data units; and

determining, by the device, the range of hash values assigned to the device based on the identified ingress and egress of the path.