Method and system for reducing cache warm-up time to suppress transmission of redundant data

• US 7,640,356 B2
• Filed: 03/10/2006
• Issued: 12/29/2009
• Est. Priority Date: 03/10/2006
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vittal, Mahesh, Ananthakrishnan, Hariharan
• Primary Examiner(s): Chan; Wing F
• Assistant Examiner(s): WILLIS, JONATHAN U
• Application Number:
  US11/372,708
• Publication Number:
  US 20070234324A1
• Time in Patent Office: 1,390 Days
• Field of Search: 711/119, 711/130, 711/216, 709/214, 709/225, 709/228, 709/232, 710/118, 710/125, 707/101, 707/201, 370/231, 370/233, 370/351
• US Class Current: 709/232
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/288 Distributed intermediate devices, i.e. intermediate devices for interaction with other intermediate devices on the same level
• CPC Class Codes: H04L 67/56 Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04L 67/5651 Reducing the amount or size of exchanged application data
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data

Abstract

In one embodiment, an optimizing device is used to suppress transmission of redundant data over networks. The first optimizing device receives information regarding associated optimizing devices associated with a second optimizing device. The information regarding the associated optimizing devices is received from the second optimizing device. Moreover, the first optimizing device receives information regarding indices identifying redundant data. The redundant data comprises data transmitted by the second optimizing device to the associated optimizing devices. The information regarding the indices identifying the redundant data is received from the second optimizing device.

Claims

1. A method for reducing cache warm-up time of a first optimizing device, the method comprising:

receiving information at a first optimizing device from a second optimizing device regarding a third optimizing device associated with the second optimizing device, wherein the first, second, and third optimizing devices include respective first, second, and third caches; and

the first, second, and third caches include respective first, second, and third tables, and wherein the first optimizing device is a new optimizing device that is added to a network that already includes the second and third optimizing devices, wherein receiving the information comprises receiving a hot working set of indices identifying redundant data transmitted by the second optimizing device to a third optimizing device for more than a predefined number of times;

receiving identifying indices at the first optimizing device from the second optimizing device, wherein the identifying indices identify redundant data transmitted by the second optimizing device to the third optimizing device, wherein the first, second, and third caches store the redundant data, and wherein the first, second, and third tables store the identifying indices, and wherein the first table of the first optimizing device is populated with the identifying indices when the first optimizing device is added to the network; and

transmitting identifying indices between the first optimizing device and the third optimizing device, wherein the identifying indices correspond to redundant data and are transmitted in place of the redundant data.

2. The method of claim 1, further comprising determining a hot working set of peers, wherein the hot working set of peers includes an optimizing device that is associated with the second optimizing device and interacts with the first optimizing device.

3. The method of claim 2, wherein determining the hot working set of peers comprises determining an optimizing device that is associated with the second optimizing device and interacts with the first optimizing device for a predefined number of times in a predefined time period.

4. The method of claim 2, wherein the hot working set of peers is determined at least in part on the basis of static information by a central managing device.

5. The method of claim 2, wherein the hot working set of peers is determined at least in part on the basis of dynamic information by a Self Organizing Distributed Architecture (SODA).

6. The method of claim 2, wherein determining the hot working set of peers comprises:

sending a multicast probe in a multicast cloud of associated optimizing devices;

receiving reply signals from a set of optimizing devices, wherein the set of optimizing devices are included in the multicast cloud of the associated optimizing devices; and

identifying the replying set of optimizing devices as the hot working set of peers.

7. The method of claim 2, wherein receiving the identifying indices comprises receiving identifying indices identifying redundant data transmitted by the second optimizing device to the hot working set of peers.

8. The method of claim 1, wherein receiving the identifying indices comprises:

determining the hot working set of indices using a heuristically guided technique, wherein the heuristically guided technique comprises;

determining number of hits for an index, wherein the number of hits for the index is determined on the basis of number of times the index is transmitted;

identifying a hot working index, wherein the number of hits for the hot working index is more than a predefined number of times in a predefined time period; and

determining the hot working set of indices, wherein the hot working set of indices comprises each of the hot working index.

9. The method of claim 1, wherein receiving the identifying indices comprises receiving information regarding the hot working set of indices in a compressed form.

10. The method of claim 1, wherein receiving the identifying indices comprises receiving a summary of the information regarding the hot working set of indices.

11. The method of claim 10, wherein summarizing the hot working set of indices comprises summarizing the hot working set of indices using bloom filters.

12. The method of claim 11, further comprising:

maintaining a local bloom filter at each optimizing device; and

updating the local bloom filter periodically.

13. The method of claim 1, further comprising pinning a data cache of each optimizing device, wherein the pinning prevents automatic refreshing of the data cache.

14. A system for reducing cache warm-up time of a first optimizing device, the system comprising:

means for receiving information at a first optimizing device from a second optimizing device regarding a third optimizing device associated with the second optimizing device, wherein the first, second, and third optimizing devices include respective first, second, and third caches; and

the first, second, and third caches include respective first, second, and third tables, and wherein the first optimizing device is a new optimizing device that is added to a network that already includes the second and third optimizing devices, wherein receiving the information comprises receiving a hot working set of indices identifying redundant data transmitted by the second optimizing device to a third optimizing device for more than a predefined number of times;

means for receiving identifying indices at the first optimizing device from the second optimizing device, wherein the identifying indices identify redundant data transmitted by the second optimizing device to the third optimizing device, wherein the first, second, and third caches store the redundant data, and wherein the first, second, and third tables store the identifying indices, and wherein the first table of the first optimizing device is populated with the identifying indices when the first optimizing device is added to the network; and

means for transmitting identifying indices between the first optimizing device and the third optimizing device, wherein the identifying indices correspond to redundant data and are transmitted in place of the redundant data.

15. A machine-readable storage medium storing instructions for reducing cache warm-up time of a first optimizing device executable by the processor, the instructions comprising:

one or more instructions for receiving information at a first optimizing device from a second optimizing device regarding a third optimizing device associated with the second optimizing device, wherein the first, second, and third optimizing devices include respective first, second, and third caches; and

the first, second, and third caches include respective first, second, and third tables, and wherein the first optimizing device is a new optimizing device that is added to a network that already includes the second and third optimizing devices, wherein receiving the information comprises receiving a hot working set of indices identifying redundant data transmitted by the second optimizing device to a third optimizing device for more than a predefined number of times;

one or more instructions for receiving identifying indices at the first optimizing device from the second optimizing device, wherein the identifying indices identify redundant data transmitted by the second optimizing device to the third optimizing device, wherein the first, second, and third caches store the redundant data, and wherein the first, second, and third tables store the identifying indices, and wherein the first table of the first optimizing device is populated with the identifying indices when the first optimizing device is added to the network; and

one or more instructions for transmitting identifying indices between the first optimizing device and the third optimizing device, wherein the identifying indices correspond to redundant data and are transmitted in place of the redundant data.

16. The machine-readable storage medium of claim 15, further comprising one or more instructions for determining a hot working set of peers, wherein the hot working set of peers includes an optimizing device that is associated with the second optimizing device and interacts with the first optimizing device.

17. The machine-readable storage medium of claim 16, wherein one or more instructions for determining the hot working set of peers comprises one or more instructions for determining an optimizing device that is associated with the second optimizing device and interacts with the first optimizing device for a predefined number of times in a predefined time period.

18. The machine-readable storage medium of claim 16, further comprising one or more instructions for determining the hot working set of peers at least in part on the basis of static information by a central managing device.

19. The machine-readable storage medium of claim 16, further comprising one or more instructions for determining the hot working set of peers at least in part on the basis of dynamic information by a Self Organizing Distributed Architecture (SODA).

20. The machine-readable storage medium of claim 16, wherein one or more instructions for determining the hot working set of peers comprises:

one or more instructions for sending a multicast probe in a multicast cloud of associated optimizing devices;

one or more instructions for receiving reply signals from a set of optimizing devices, wherein the set of optimizing devices are included in the multicast cloud of the associated optimizing devices; and

one or more instructions for identifying the replying set of optimizing devices as the hot working set of peers.

21. The machine-readable storage medium of claim 16, wherein one or more instructions for receiving the identifying indices comprises one or more instructions for receiving identifying indices identifying redundant data transmitted by the second optimizing device to the hot working set of peers.

22. The machine-readable storage medium of claim 15, wherein one or more instructions for receiving the identifying indices comprises:

one or more instructions for determining the hot working set of indices using a heuristically guided technique, wherein the heuristically guided technique comprises;

one or more instructions for determining number of hits for an index, wherein the number of hits for the index is determined on the basis of number of times the index is transmitted;

one or more instructions for identifying a hot working index, wherein the number of hits for the hot working index is more than a predefined number of times in a predefined time period; and

one or more instructions for determining the hot working set of indices, wherein the hot working set of indices comprises each of the hot working index.

23. The machine-readable storage medium of claim 15, wherein one or more instructions for receiving the identifying indices comprises one or more instructions for receiving information regarding the hot working set of indices in a compressed form.

24. The machine-readable storage medium of claim 15, wherein one or more instructions for receiving the identifying indices comprises one or more instructions for receiving a summary of the information regarding the hot working set of indices.

25. The machine-readable storage medium of claim 24, wherein one or more instructions for summarizing the hot working set of indices comprises one or more instructions for summarizing the hot working set of indices using bloom filters.

26. The machine-readable storage medium of claim 25, further comprising:

one or more instructions for maintaining a local bloom filter at each optimizing device; and

one or more instructions for updating the local bloom filter periodically.

27. The machine-readable storage medium of claim 15, further comprising one or more instructions for pinning a data cache of each optimizing device, wherein the pinning prevents automatic refreshing of the data cache.

28. A method for controlling index use of a first optimized device in a network, the method comprising;

performing the following in accordance with a control parameter, wherein the control parameter is generated by an application;

receiving information at a first optimizing device from a second optimizing device regarding a third optimizing device associated with the second optimizing device, wherein the first, second, and third optimizing devices include respective first, second, and third caches; and

the first, second, and third caches include respective first, second, and third tables, and wherein the first optimizing device is a new optimizing device that is added to a network that already includes the second and third optimizing devices, wherein receiving the information comprises receiving a hot working set of indices identifying redundant data transmitted by the second optimizing device to a third optimizing device for more than a predefined number of times;

receiving identifying indices at the first optimizing device from the second optimizing device, wherein the identifying indices identify redundant data transmitted by the second optimizing device to the third optimizing device, wherein the first, second, and third caches store the redundant data, and wherein the first, second, and third tables store the identifying indices, and wherein the first table of the first optimizing device is populated with the identifying indices when the first optimizing device is added to the network; and

transmitting identifying indices between the first optimizing device and the third optimizing device, wherein the identifying indices correspond to redundant data and are transmitted in place of the redundant data.

29. The method of claim 28, wherein the control parameter determines whether the identifying indices are stored at the first optimizing device.

30. The method of claim 29, wherein the control parameter is set at least in part in response to a signal from a user input device.

31. The method of claim 29, wherein the control parameter is set at least in part in response to time.

32. The method of claim 29, wherein the control parameter is set at least in part in response to network traffic load.

33. The method of claim 29, wherein the control parameter is set at least in part in response to a quality of service consideration.

34. The method of claim 29, wherein the control parameter is set at least in part according to a data type being transferred over the network.