Source: http://www.google.es/patents/US8839254
Timestamp: 2017-12-16 07:39:01
Document Index: 650522645

Matched Legal Cases: ['art 2', 'art-2', 'art 2', 'art-2', 'art 1', 'Application No. 201080009556', 'Application No. 201080009556', 'Application No. 201080009556', 'Application No. 10744134', 'Application No. 10744134', 'Application No. 2011', 'Application No. 2011']

Patente US8839254 - Precomputation for data center load balancing - Google Patentes
Pre-computing a portion of forecasted workloads may enable load-balancing of data center workload, which may ultimately reduce capital and operational costs associated with data centers. Computing tasks performed by the data centers may be analyzed to identify computing tasks that are eligible for pre-computing,...http://www.google.es/patents/US8839254?utm_source=gb-gplus-sharePatente US8839254 - Precomputation for data center load balancing
Número de publicación US8839254 B2
Número de solicitud US 12/492,385
También publicado como US20100333105
Número de publicación 12492385, 492385, US 8839254 B2, US 8839254B2, US-B2-8839254, US8839254 B2, US8839254B2
Inventores Eric J. Horvitz, Christian L. Belady
Citas de patentes (135), Otras citas (108), Citada por (1), Clasificaciones (6), Eventos legales (2)
US 8839254 B2
1. A method implemented by one or more processors of load-balancing a data center workload of a data center, the method comprising:
ascertaining a low-volume period prior to the high-volume period based at least in part on an inverse curve of a cumulative curve, the cumulative curve being an overlay of data center operational factors that indicate a price per operation unit for operating the data center;
performing the pre-computation of the computing tasks associated with the forecasted workload during the low-volume period to generate manipulated data; storing the manipulated data in cache; and
retrieving the manipulated data upon a request that uses the manipulated data during the high-volume period to expedite processing of the request.
2. The method as recited in claim 1, wherein the data center operational factors indicate efficient periods to schedule workloads for pre-computation that are preferentially selected over non-efficient periods.
3. The method as recited in claim 1, wherein the data center operational factors further include a cost of power from a power grid that is shared by the data center and another power consumer and another cost of power from a dedicated power supplier that exclusively supplies power to the data center.
5. The method as recited in claim 1, wherein the selecting computing tasks is based on a historical analysis of tasks that are anticipated to reoccur on one or more future dates.
6. The method as recited in claim 1, wherein the selecting occurs at near-real time as the data center workload enters the high-volume period.
a communication adapter configured to enable a data center to receive a request from an entity computing device and transmit a response to the entity computing device;
memory storing computer readable instructions executable by the one or more processors, wherein the computer readable instructions provide a decomposer module configured to:
ascertain a low-volume period based at least in part on an inverse curve of a cumulative curve, the cumulative curve being an overlay of data center operational factors that indicate a price per operation unit for operating the data center;
pre-compute the computing tasks during the low-volume period to create manipulated data based on a computing blueprint that uses historical computing trends to determine how to pre-compute the computing tasks;
store the manipulated data in cache for access during the high-volume period; and
retrieve a portion of the manipulated data to expedite satisfying the request upon receipt of the request.
8. The system as recited in claim 7, wherein the decomposer module is further configured to delete unused instances of the manipulated data when the manipulated data becomes stale.
12. The system as recited in claim 7, wherein the instructions further provide a scheduler module configured to:
schedule the pre-compute to occur during the low-volume period.
13. The system as recited in claim 12, wherein the scheduler module is further configured to provide the overlay of the data center operational factors that affect workload scheduling.
14. A method implemented by one or more processors of processing a portion of a computing workload of a data center prior to a request of the computing workload, the method comprising:
ascertaining a low-volume workload period of the data center based at least in part on an inverse curve of a cumulative curve, the cumulative curve being an overlay of data center operational factors that indicate a price per operation unit for operating the data center, the inverse curve having at least one high curve portion that is equivalent to a mean workload of the data center;
performing the pre-computing of computing tasks during the low-volume workload period of the data center prior to a high-volume workload period, the pre-computing tasks to create manipulated data;
storing the manipulated data in cache; and
retrieving the manipulated data in response to a received request that corresponds to the computing tasks.
15. The method as recited in claim 14, wherein the inputs include keywords selected from an early data release that are search terms for queries.
16. The method as recited in claim 14, wherein the inputs include transaction information to enable pre-computing of a transaction by performing at least one of compiling a portion of a transaction, adding items to an order, processing a payment, or assigning a customer.
17. The method as recited in claim 14, further comprising generating a forecasted schedule of the computing workload of the data center that includes the low-volume workload period and the high-volume workload period.
18. The method as recited in claim 17, wherein the operational factors include at least one of a cooling cost for one or more servers in the data center, a cost of power from a power grid that is shared by the data center and another power consumer, or another cost of power from a dedicated power supplier that exclusively supplies power to the data center.
19. The method as recited in claim 14, wherein the identifying includes identifying the computing tasks performed by the data center based on statistical models using at least one of a user history, machine usage, or data center performance.
US7711587 * 5 Ene 2007 4 May 2010 Ita Software, Inc. Providing travel information using cached query answers
US8189561 9 Dic 2009 29 May 2012 Broadcom Corporation Method and system for power-limited switching and/or routing in a network
US8225119 23 Feb 2009 17 Jul 2012 Microsoft Corporation Energy-aware server management
US20080049714 25 Ago 2006 28 Feb 2008 International Business Machines Corporation A technique for synchronizing data with a mobile device based on a synchronization context
US20090265704 17 Abr 2008 22 Oct 2009 Branda Steven J Application Management for Reducing Energy Costs
US20110205949 27 Ago 2008 25 Ago 2011 Telefonaktiebolaget L M Ericsson (Publ) Routing Mechanism for Distributed Hash Table Based Overlay Networks
US20110282982 13 May 2010 17 Nov 2011 Microsoft Corporation Dynamic application placement based on cost and availability of energy in datacenters
US20110288898 26 Jun 2009 24 Nov 2011 Nokia Corporation Coordinating Services
US20120030356 30 Jul 2010 2 Feb 2012 International Business Machines Corporation Maximizing efficiency in a cloud computing environment
US20120130554 22 Nov 2010 24 May 2012 Microsoft Corporation Dynamically placing computing jobs
KR20090120704A Título no disponible
WO2004049157A3 27 Oct 2003 6 May 2005 Ibm Automated power control policies for distributed server pools based on application-specific computational requirements
WO2009012451A2 18 Jul 2008 22 Ene 2009 Exaflop Llc Power supply for a data center
WO2010010544A2 24 Jul 2009 28 Ene 2010 Sonajalg Andres Wind power generator
1 "About Vibes Interactive", Vibes Interactive LLC, retrieved from <<http://vibesinteractive.com/about—us—html>>, 2010 2 pages.
2 "About Vibes Interactive", Vibes Interactive LLC, retrieved from >, 2010 2 pages.
3 "ASG-Workload Optimization Suite for Comprehensive Workload Analysis and Forecasting", retrieved on May 11, 2009 at http://www.asg.com/products/product-details.asp?code=WOS, Allen Systems Group, Inc., 2009, 2 pages.
4 "ASG-Workload Optimization Suite for Comprehensive Workload Analysis and Forecasting", retrieved on May 11, 2009 at http://www.asg.com/products/product—details.asp?code=WOS, Allen Systems Group, Inc., 2009, 2 pages.
5 "Carbon Tax Center", retrieved from <.carbontax.org>>on Aug. 8, 2010, 7 pages.
6 "Carbon Tax Center", retrieved from >on Aug. 8, 2010, 7 pages.
7 "Consultants:HOW and WHY Pay Per Performance Works (Part 2-continuation form last post)", Weblog posting, retreived from <://bizrelationships.wordpress.com/2010/04/19/consultants-how-and-why-pay-per-performance-works-part-2-continuation-from-last-post>>, Apr. 2010, 5 pages.
8 "Consultants:HOW and WHY Pay Per Performance Works (Part 2—continuation form last post)", Weblog posting, retreived from <://bizrelationships.wordpress.com/2010/04/19/consultants-how-and-why-pay-per-performance-works-part-2-continuation-from-last-post>>, Apr. 2010, 5 pages.
9 "PlateSpin Recon", retrieved on May 11, 2009 at http://www.novell.com/products/recon/consolidation-ratios.html, Novell, Inc 2009, 2 pages.
10 "PlateSpin Recon", retrieved on May 11, 2009 at http://www.novell.com/products/recon/consolidation—ratios.html, Novell, Inc 2009, 2 pages.
11 "Sensible Cloud: What is an SLA?", retrieved from .sensiblecloud.com/2010/11/what-is-sla>>, Nov. 2010, 8 pages.
12 "Solar chimney", Wikipedia, Published on or before Feb. 27, 2005.
13 "Solar updraft tower", Wikipedia, Published on or before Aug. 30, 2006.
14 "Tout+Interactive", retreived from ://toutinteractive.com>>, retrieved on Mar. 22, 2011, earliest weblog entries from Nov. 2010, 8 pages.
15 "Window Azure Platform", retrieved on Aug. 5, 2010 from <<http:www.azure.com>>, 2 pages.
16 "Window Azure Platform", retrieved on Aug. 5, 2010 from >, 2 pages.
17 "Zeus Launches Data Center Load Balancing Solution", retrieved on May 11, 2009 at http://www.continuitycentral.com/news03343.htm, Continuity Central, Jun. 28, 2007, 1 page.
18 Ardagna, "SLA Based Profit Optimization in Multi-tier Systems", Proceedings of the Fourth IEEE International Symposium on Network Computing and Applications, Jul. 27-29, 2005.
19 Bansal, et al., "A Primal-Dual Randomized Algorithm for Weighted Paging", Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, Oct. 2007, 11 pages.
20 Bansal, et al., "Metrical Task Systems and the k-Server Problem on HSTs", Proceedings of the 37th International Colloquiumon Automata, Languages and Programming, Jul. 2010, 12 pages.
21 Bansal, et al., "Randomized Competitive Algorithms for Generalized Caching", Proceedings of the 40th Annual ACM Symposium on Theory of Consulting, May 2008, 10 pages.
22 Bansal, et al., "Towards the Randomized k-Server Conjecture: A Primal-Dual Approach", Proceedings of the 21st Annual ACM-SIAM Syposium on Discrete Algorithms, Jan. 2010, 24 pages.
23 Bartal, et al., "A polylog(n)-competitive algorithm for metrical task systems", Proceedings of the 29th Annual ACM Symposium on Theory Computing, Jun. 1997, 9 pages.
24 Battles, et al., "Reducing Data Center Power Consumption Through Efficient Storage", Network Appliance, Inc., NetApp Vision Series, Feb. 2007, 9 pages.
25 Belady, "In the Data Center, Power and Cooling Costs More Than the IT Equipment it Supports", Electronics Cooling, Feb. 2007, 6 pages.
26 Beloglazov, "Energy Efficient Resource Management in Virtualized Cloud Data Centers", Proceedings of the 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing, May 17-20, 2010.
27 Bianchini, "Power and Energy Management for Server Systems", IEEE Computer, vol. 37, No. 11, Nov. 2004.
28 Bonvin, et al., "Autonomic SLA-driven Provisioning for Cloud Applications", 11th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, May 2011, 10 pages.
29 Borenstein, et al., "Dynamic Pricing, Advanced Metering and Demand Response in Electricity Markets", University of California Energy Institute, Oct. 2002, 102 pages.
30 Borgs, "Optimal Mechanisms for Perishable Goods With Variable Supply and Demand", Aug. 11, 2010.
31 Borodin, et al., "An Optimal On-Line Algorithm for Metrical Task System", Journal of the ACM, vol. 39, No. 4, Oct. 1992, pp. 745-763.
32 Borodin, et al., "Online Computation and Competitive Analysis", Cambridge University Press, New York, NY, 1998, 6 pages.
33 Brocade, "Leading the Evolution of the Data Center", Brocade Communications Systems, Inc., Sep. 2008, 8 pages.
34 Buchbinder, et al., "The Design for Competitive Online Algorithms via a Primal-Dual Approach", Foundaions and Trends in Theoretical Computer Science, vol. 3, Nos. 2-3, Feb. 2009, 174 pages.
35 Buckbinder, et al, "Online Job-Migration for Reducing the Electricity Bill in the Cloud", Lecture Notes in Computer Science Networking 2011, Proceedings of the International IFIP TC 6 Conference on Networking, vol. 6640, Part 1, May 2011, 14 pages.
36 Butler, "France unveils carbon tax", Nature, Sep. 2009, 4 pages.
37 Buyya, et al., "Cloudbus Toolkit for Market-Oriented Cloud Computing", Proceedings of the 1st International Conference on Cloud Computing, Oct. 2009, pp. 24-44.
38 Chase, et al., "Managing Energy and Server Resources in Hosting Centers", Proceedings of the Eighteenth ACM Symposium on Operating Principles, Oct. 2001, 14 pages.
39 Chatwin, "Optimal dynamic pricing of perishable products with stochastic demand and finite set of prices", European Journal of Operational Research, 125 (2000), available as early as Aug. 1997, pp. 149-174.
40 Chaver, "Energy-Aware Fetch Mechanism: Trace Cache and BTB Customization", Proceedings of the 2005 International Symposium on Low Power Electronics and Design, Aug. 8-10, 2005.
41 Chen, et al., "Energy-Aware Server Provisioning and Load Dispatching for Connectino-Intensive Internet Services", Proceedings of the 5th USENIX Symposium on Networked System Design and Implementation, Apr. 2008, 14 pages.
42 Cho, et al., "Strategic Consumer Response to Dynamic Pricing of Perishable Products", International Series in Operations Research and Management Science, vol. 131, Aug. 2008, 36 pages.
43 Clark, "Live Migration of Virtual Machines", Proceedings of the 2nd ACM/USENIX Symposium on Networked Systems Design & Implementation, May 2-4, 2005.
44 CN Notice on the First Office Action for Application No. 201080009556.7, Jul. 29, 2013.
45 CN Notice on the Second Office Action for Application No. 201080009556.7, Dated Feb. 21, 2014.
46 CN Response to Second Office Action for Application No. 201080009556.7, Filed May 7, 2014.
47 Dasu, et al., "Dynamic pricing when consumers are strategic: Analysis of a posted pricing scheme", European Journal of Operational Research, vol. 204, Issue 3, Aug. 2010, 23 pages.
48 Dept of Energy EPA, "Carbon Dioxide Emissions from the Generation of Electric Power in the United States", retrieved from <www.eia.gov/cneaf/electricity/page/co2-report/co2report.html, Jul. 2000, 21 pages.
49 Dept of Energy EPA, "Carbon Dioxide Emissions from the Generation of Electric Power in the United States", retrieved from <www.eia.gov/cneaf/electricity/page/co2—report/co2report.html, Jul. 2000, 21 pages.
50 Dunn, "Data Center Energy Efficient Through BCM", Industry Perspectives, Jan. 2010, 7 pages.
51 EMC2, "Managing Energy Efficiency in the Data Center", EMC Corporation, May 2008, 6 pages.
52 EP Communication for Application No. 10744134.7-2211/2399183 PCT/US2010023253, Nov. 14, 2012.
53 EP Response to Rules 70(2) and 70a(2) EPC Communication for Application No. 10744134.7, Filed Jan. 30, 2013.
54 Fan, et al., "Power Provisioning for a Warehouse-sized Computer", Proceedings of the ACM International Symposium on Computer Architecture, Jun. 2077, 11 pages.
55 Felter, "A Performance-Conserving Approach for Reducing Peak Power Consumption in Server Systems", Proceedings of the 19th Annual International Conference on Supercomputing, Jun. 20-22, 2005.
56 Fiat, et al., "Better Algorithms for Unfair Metrical Task Systems and Applications", Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, May 2000, 20 pages.
57 Giannakoudis, "Optimum design and operation under uncertainty of power systems using renewable energy sources and hydrogen storage", International Journal of Hydrogen Energy, ScienceDirect, Available online Nov. 27, 2009.
58 Gmach, "Capacity Planning and Power Management to Exploit Sustainable Energy", Proceedings of the 6th International Conference on Network and Service Management, Oct. 25-29, 2010.
59 Grossman, "The Case for Cloud Computing", IT Professional. Volume 11, No. 2, Mar. 2009, pp. 23-27.
60 Harrison, "Symantic Energy Efficient Data Center Solutions-An Executive Overview", Symantic Technology Network: Energy Efficient Data Center, Symantic Corporation, Jan. 2008, 15 pages.
61 Harrison, "Symantic Energy Efficient Data Center Solutions—An Executive Overview", Symantic Technology Network: Energy Efficient Data Center, Symantic Corporation, Jan. 2008, 15 pages.
62 Hitachi, et al., "The Path to a Green Data Center", Hitachi Data Systems and Brocade Joint Solution Brief, Mar. 2007, 8 pages.
63 International Search Report dated Jan. 31, 2013 for PCT Patent Application No. PCT/US2012/042110, 9 pages.
64 Iranli, "System-Level Power Management: An Overview", In The VLSI Handbook Second Edition, CRC Press, Dec. 26, 2006.
65 Jain, "An Optimization Framework for Dynamic Client-Server Partitioning in the IMA Application", Apr. 16, 2010.
66 Jain, "SLA-Integrated Pricing Models for Cloud Computing", Microsoft Research, Oct. 18, 2010.
67 Jiang, et al., "Enabling Autonomic Power-Aware Management of Instrumented Data Centers", Proceedings of the IEEE International Symposium on Parallel & Distributed Processing, May 2008, 8 pages.
68 JP Notice of Rejection for Application No. 2011-551110, Jul. 2, 2013.
69 JP Second Office Action for Application No. 2011-551110, Dated Mar. 11, 2014.
70 Kahn, "As power demand soars from hot weather, grid holds up so far", Associated Press, Jul. 2010, 1 page.
71 Kant, "Data center evolution: A tutorial on state of the art, issues, and challenges", Computer Networks, Nov. 12, 2009.
72 Kant, "Distributed Energy Adaptive Computing", IEEE International Conference on Communications, May 23-27, 2010.
73 Kant, "Power Control of High Speed Network Interconnects in Data Centers", Proceedings of the 28th IEEE International Conference on Computer Communications, Apr. 19-25, 2009.
74 Karve, "Dynamic Placement for Clustered Web Applications", Proceedings of the 15th International World Wide Web Conference, May 22-26, 2006.
75 Levin, et al., "Dynamic Pricing in the Presence of Strategic Consumers and Oligopolistic Competition", Management Science, vol. 55, No. 1, Jan. 2009, pp. 32-46.
76 Levin, et al., "Optimal Dynamic Pricing of Perishable Items by a Monopolist Facing Strategic Consumers", Production and Operations Management (POMS), vol. 19, Issue 1, Jan./Feb. 2010, 53 pages.
77 Li et al., "Load Balancing for Multi-tiered Database Systems through Autonomic Placement of Materialized Views", retrieved on May 8, 2009 at http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1617470&isnumber=33902, Proceedings of the 22nd International Conference on Data Engineering (ICDE 2006), 12 pages.
78 Liu, "GreenCloud: A New Architecture for Green Data Center", Proceedings of the 6th International Conference on Autonomic Computing and Communications Industry Session, Jun. 16, 2009.
79 McGeehan, "Heat Wave Report: 102 Degrees in Central Park", The New York Times, Jul. 2010, 17 pages.
80 Pauley, "Cloud Provider Transparency: An Empirical Evaluation", IEEE Security and Privacy, vol. 8, No. 6, Nov./Dec. 2010, pp. 32-39.
81 PCT International Search Report and Written Opinion for Application No. PCT/US2010/023253, Sep. 30, 2010.
82 PCT International Search Report and Written Opinion for Application No. PCT/US2011/036364, Dec. 23, 2011.
83 PCT International Search Report and Written Opinion for Application No. PCT/US2012/042110, Jan. 31, 2013.
84 Perry, "Australian Greens propose A$23/ton carbon tax", Reuters, Jun. 2010, 2 pages.
85 Pflueger, et al., "Data Center Efficiency in the Scalable Enterprise", Dell Power Solutions, Feb. 2007, 7 pages.
86 Popa, et al., "Enabling Security in Cloud Storage SLAs with CloudProof", Microsoft Research Technical Report MSR-TR-2010-46, May 2010, 12 pages.
87 Qureshi, et al., "Cutting the Electric Bill for Internet-Scale Systems", SIGCOMM'09, Aug. 2009, 12 pages.
88 Rao, et al."Minimizing Electricity Cost Optimization of Distributed Internet Data Centers in a Multi-Electricity-Market Environment", INFOCOM, Mar. 2010, 9 pages.
89 Rasmussen, "Implementing Energy Efficient Data Centers", White Paper #114, American Power Conversion (APC), retrieved at <<www.sidepath.com/infrastructure/files/Implementing%20Energy%20Efficient%20Datacenters. pdf>>, 2006, 15 pages.
90 Rasmussen, "Implementing Energy Efficient Data Centers", White Paper #114, American Power Conversion (APC), retrieved at >, 2006, 15 pages.
91 Sleator, et al., "Amortized Efficiency of List Update and Paging Rules", Communications of the ACM, vol. 28, No. 2, Feb. 1985, pp. 202-208.
92 Sweeting, "Dynamic Pricing Behavior in Perishable Goods Markets: Evidence from Secondary Markets for Major League Baseball Tickets", Department of Economics, Duke University, Durham, NC, Feb. 2010, 65 pages.
93 Timmer, "Renewable energy and the future of the datacenter", Arstechinica.com Business News, May 2008, 2 pages.
94 U.S. Appl. No. 12/391,188, filed Feb. 23, 2009, Navendu Jain.
95 U.S. Appl. No. 12/781,445, filed May 17, 2010, Douglas C. Burger.
96 U.S. Appl. No. 12/903,227, filed Oct. 13, 2010, Christian H. Borgs.
97 U.S. Appl. No. 12/913,763, filed Oct. 28, 2010, Christian L. Belady.
98 U.S. Appl. No. 12/951,977, filed Nov. 22, 2010, Navendu Jain.
99 U.S. Appl. No. 12/973,399, filed Dec. 20, 2010, Navendu Jain.
100 U.S. Appl. No. 13/169,890, filed Jun. 27, 2011, Navendu Jain.
101 U.S. Appl. No. 13/169,923, filed Jun. 27, 2011, Navendu Jain.
102 U.S. Appl. No. 17/779,059, filed May 13, 2010, Navendu Jain.
103 Urgaonkar, "Dynamic Provisioning of Multi-tier Internet Applications", In Proceedings of the Second International Conference on Autonomic Computing, Jun. 13-16, 2005.
104 Vazirani, "Approximation Algorithms", Springer, 2001, 396 pages.
105 Verma, "Brownmap: Enforcing Power Budget in Shared Data Centers", IBM Research Report, Dec. 17, 2009.
106 Wang, "Feedback Control Algorithms for Power Management of Servers"; Third International Workshop on Feedback Control Implementation and Design in Computing Systems and Networks, Jun. 6, 2008.
107 Wang, et al., "Markdown money contract for perishable goods with clearance pricing", Eurpean Journal of Operational Research, Aug. 2009, pp. 1113-1122.
108 Zhang, et al. "Cloud computing: state-of-the-art and research challenges", Journal of Internet Services and Application, vol. 1, May 2010, pp. 7-18.
Clasificación de EE.UU. 718/102, 718/105
Clasificación internacional G06F9/46, G06F9/48
Clasificación cooperativa Y02B60/144, G06F9/4893
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:HORVITZ, ERIC J.;BELADY, CHRISTIAN L.;SIGNING DATES FROM20090626 TO 20090714;REEL/FRAME:022964/0864