Home > Topics > Passive Monitoring > Load management in network monitoring > Load shedding

Load shedding


Warning: file_get_contents(http://www.bibsonomy.org/bib/bibtex/28654590f2f44d00150864eca9cc4999e) [function.file-get-contents]: failed to open stream: HTTP request failed! HTTP/1.1 404 Not Found in /var/www/vhosts/tma-portal.eu/httpdocs/wp-content/plugins/bib2html/bib2html.php on line 252

Warning: file_get_contents(http://www.bibsonomy.org/bib/bibtex/2e6135d0c95562cf22ed12afa418167ee) [function.file-get-contents]: failed to open stream: HTTP request failed! HTTP/1.1 404 Not Found in /var/www/vhosts/tma-portal.eu/httpdocs/wp-content/plugins/bib2html/bib2html.php on line 252

Load shedding has been recently proposed as an effective alternative to overprovisioning for handling overload situations in several real-time systems [Welsh et al., 2001]; [Tatbul et al., 2003]; [Babcock et al., 2004]; [Tu et al., 2006]. Load shedding is the process of dropping excess load in such a way that the system remains stable and no overflow occurs in the system buffers. The idea of load shedding originally comes from the field of electric power management, where it consists of intentionally disconnecting the electric current on certain lines when the demand becomes greater than the supply.

CoMo

CoMo (Continuous Monitoring) is an open-source passive network monitoring system that allows for fast implementation and deployment of network monitoring applications. Applications in CoMo (or modules) are written in the C language, making use of a feature-rich API provided by the core platform.

The load shedding scheme in CoMo [Barlet-Ros et al., 2007]; [Barlet-Ros et al., 2009] models and predicts in real-time the CPU usage of the monitoring system, which allows it to anticipate future bursts in the resource requirements. Without any knowledge of the computations performed on the packet streams, the system infers their cost from the relation between a large set of pre-defined features of the input stream and the actual resource usage. A feature is a counter that describes a specific property of a sequence of packets (e.g., number of unique source IP addresses).

The intuition behind this method comes from the empirical observation that the cost of a monitoring application is often dominated by the overhead of basic operations used to maintain its state (e.g., adding, updating or searching entries), which can be modeled by considering the right set of simple traffic features. The features computed on the input stream have the advantage of being lightweight with a deterministic worst case computational cost, thus introducing a minimum delay in the operations of the monitoring system.

The load shedding scheme automatically identifies those features that best model the resource usage of each monitoring application based on previous measurements of its resource usage and uses them to predict the overall load of the system. This short-term prediction is used to guide the system on deciding when, where and how much load to shed. In the presence of overload, the system can apply several load shedding techniques, such as packet, flow sampling or custom user-defined methods, to reduce the amount of resources required by the applications to run.

TelegraphCQ

TelegraphCQ [Chandrasekaran et al., 2003] is a stream query processor developed at UC Berkeley. The software architecture of TelegraphCQ is based on the relational DBMS PostgreSQL, but it includes large extensions to support streaming data and continuous queries. An important feature of TelegraphCQ is that it has built-in support for network monitoring (Reiss and Hellerstein, 2006).

In order to deal with overload situations, TelegraphCQ implements an architecture called Data Triage [Reiss and Hellerstein, 2005]; [Reiss and Hellerstein, 2006]. The main difference between Data Triage and other load shedding schemes, such as those implemented in Aurora [Tatbul et al., 2003] and STREAM [Babcock et al., 2004], is that it applies approximate query processing techniques, instead of dropping tuples, in order to provide approximate and delay-bounded answers in presence of overload.

The architecture of Data Triage is divided in two data paths: a primary data path that performs normal query processing and a secondary data path that uses approximation. When the system detects that there is no enough time to perform full query processing on every tuple, Data Triage sends selected tuples through the secondary path in order to keep the delay within the bounds defined by end users.

In the secondary path, the tuples are first summarized and provisionally stored into a summary data structure. At the end of each time window, the summarized data are processed by a shadow query that uses approximate processing techniques. Finally, the results of the shadow query as well as those of the main query are presented to the user, who can combine them to obtain an approximate version of the query answer.

References

http://www.bibsonomy.org/bib/bibtex/28654590f2f44d00150864eca9cc4999e bibtex file empty

  • [conf-usenix-Barlet-RosISAS07] bibtex
    P. Barlet-Ros, G. Iannaccone, J. Sanjuàs-Cuxart, D. Amores-López, and J. Solé-Pareta, "Load Shedding in Network Monitoring Applications.," in USENIX Annual Technical Conference, 2008-01-14 2007, pp. 59-72.
    @inproceedings{conf/usenix/Barlet-RosISAS07, added-at = {2008-01-14T00:00:00.000+0100},
      author = {Barlet-Ros, Pere and Iannaccone, Gianluca and Sanjuàs-Cuxart, Josep and Amores-López, Diego and Solé-Pareta, Josep},
      biburl = {http://www.bibsonomy.org/bibtex/2b73e4c019057f41354ff66308f16e86e/dblp},
      booktitle = {USENIX Annual Technical Conference},
      crossref = {conf/usenix/2007},
      date = {2008-01-14},
      description = {dblp},
      ee = {http://www.usenix.org/events/usenix07/tech/barlet-ros.html},
      interhash = {b215a5ca2ea0ab1a1ba12ca28523dd57},
      intrahash = {b73e4c019057f41354ff66308f16e86e},
      keywords = {dblp},
      pages = {59-72},
      publisher = {USENIX},
      timestamp = {2008-01-14T00:00:00.000+0100},
      title = {Load Shedding in Network Monitoring Applications.},
      url = {http://dblp.uni-trier.de/db/conf/usenix/usenix2007.html#Barlet-RosISAS07},
      year = 2007 }
  • P. Barlet-Ros, G. Iannaccone, J. Sanjuàs-Cuxart and J. Solé-Pareta. Robust network monitoring in the presence of non-cooperative traffic queries. Computer Networks,
    53(3), 2009.
  • [conf-cidr-ChandrasekaranDFHHKMRRS03] bibtex
    S. Chandrasekaran, O. Cooper, A. Deshpande, M. J. Franklin, J. M. Hellerstein, W. Hong, S. Krishnamurthy, S. Madden, V. Raman, F. Reiss, and M. A. Shah, "TelegraphCQ: Continuous Dataflow Processing for an Uncertain World.," in CIDR, 2003.
    @inproceedings{conf/cidr/ChandrasekaranDFHHKMRRS03, added-at = {2006-09-20T11:53:51.000+0200},
      author = {Chandrasekaran, Sirish and Cooper, Owen and Deshpande, Amol and Franklin, Michael J. and Hellerstein, Joseph M. and Hong, Wei and Krishnamurthy, Sailesh and Madden, Samuel and Raman, Vijayshankar and Reiss, Frederick and Shah, Mehul A.},
      biburl = {http://www.bibsonomy.org/bibtex/27adfa197ad9e94b1f395e8df4e792b57/wolfey},
      booktitle = {CIDR},
      ee = {http://www-db.cs.wisc.edu/cidr/cidr2003/program/p24.pdf},
      interhash = {78e5135d973d2559f3869a957d36bfe8},
      intrahash = {7adfa197ad9e94b1f395e8df4e792b57},
      keywords = {processing telegraphcq stream distributed},
      timestamp = {2006-09-20T11:53:51.000+0200},
      title = {TelegraphCQ: Continuous Dataflow Processing for an Uncertain World.},
      url = {http://dblp.uni-trier.de/db/conf/cidr/cidr2003.html#ChandrasekaranDFHHKMRRS03},
      year = 2003 }
  • [conf-cidr-ChandrasekaranDFHHKMRRS03] bibtex
    S. Chandrasekaran, O. Cooper, A. Deshpande, M. J. Franklin, J. M. Hellerstein, W. Hong, S. Krishnamurthy, S. Madden, V. Raman, F. Reiss, and M. A. Shah, "TelegraphCQ: Continuous Dataflow Processing for an Uncertain World.," in CIDR, 2005-11-17 2003.
    @inproceedings{conf/cidr/ChandrasekaranDFHHKMRRS03, added-at = {2005-11-17T00:00:00.000+0100},
      author = {Chandrasekaran, Sirish and Cooper, Owen and Deshpande, Amol and Franklin, Michael J. and Hellerstein, Joseph M. and Hong, Wei and Krishnamurthy, Sailesh and Madden, Samuel and Raman, Vijayshankar and Reiss, Frederick and Shah, Mehul A.},
      biburl = {http://www.bibsonomy.org/bibtex/27adfa197ad9e94b1f395e8df4e792b57/dblp},
      booktitle = {CIDR},
      date = {2005-11-17},
      description = {dblp},
      ee = {http://www-db.cs.wisc.edu/cidr/cidr2003/program/p24.pdf},
      interhash = {78e5135d973d2559f3869a957d36bfe8},
      intrahash = {7adfa197ad9e94b1f395e8df4e792b57},
      keywords = {dblp},
      timestamp = {2005-11-17T00:00:00.000+0100},
      title = {TelegraphCQ: Continuous Dataflow Processing for an Uncertain World.},
      url = {http://dblp.uni-trier.de/db/conf/cidr/cidr2003.html#ChandrasekaranDFHHKMRRS03},
      year = 2003 }

http://www.bibsonomy.org/bib/bibtex/2e6135d0c95562cf22ed12afa418167ee bibtex file empty

  • [conf-icde-ReissH06] bibtex
    F. Reiss and J. M. Hellerstein, "Declarative Network Monitoring with an Underprovisioned Query Processor.," in ICDE, 2006-04-18 2006, p. 56.
    @inproceedings{conf/icde/ReissH06, added-at = {2006-04-18T00:00:00.000+0200},
      author = {Reiss, Frederick and Hellerstein, Joseph M.},
      biburl = {http://www.bibsonomy.org/bibtex/2edfb1e0695d5faa7e4339f0503eaed4c/dblp},
      booktitle = {ICDE},
      crossref = {conf/icde/2006},
      date = {2006-04-18},
      description = {dblp},
      editor = {Liu, Ling and Reuter, Andreas and Whang, Kyu-Young and Zhang, Jianjun},
      ee = {http://doi.ieeecomputersociety.org/10.1109/ICDE.2006.46},
      interhash = {c2a9ec00ba5680046ba36d3aea4a7b2e},
      intrahash = {edfb1e0695d5faa7e4339f0503eaed4c},
      keywords = {dblp},
      pages = 56, publisher = {IEEE Computer Society},
      timestamp = {2006-04-18T00:00:00.000+0200},
      title = {Declarative Network Monitoring with an Underprovisioned Query Processor.},
      url = {http://dblp.uni-trier.de/db/conf/icde/icde2006.html#ReissH06},
      year = 2006 }
  • [conf-vldb-TatbulCZCS03] bibtex
    N. Tatbul, U. Çetintemel, S. B. Zdonik, M. Cherniack, and M. Stonebraker, "Load Shedding in a Data Stream Manager.," in VLDB, 2004-01-06 2003, pp. 309-320.
    @inproceedings{conf/vldb/TatbulCZCS03, added-at = {2004-01-06T00:00:00.000+0100},
      author = {Tatbul, Nesime and Çetintemel, Ugur and Zdonik, Stanley B. and Cherniack, Mitch and Stonebraker, Michael},
      biburl = {http://www.bibsonomy.org/bibtex/292860352ee495616c6faab1167954690/dblp},
      booktitle = {VLDB},
      date = {2004-01-06},
      description = {dblp},
      ee = {http://www.vldb.org/conf/2003/papers/S10P03.pdf},
      interhash = {fce3e7cdc81ab84447115108470c99db},
      intrahash = {92860352ee495616c6faab1167954690},
      keywords = {dblp},
      pages = {309-320},
      timestamp = {2004-01-06T00:00:00.000+0100},
      title = {Load Shedding in a Data Stream Manager.},
      url = {http://dblp.uni-trier.de/db/conf/vldb/vldb2003.html#TatbulCZCS03},
      year = 2003 }
  • [conf-vldb-TuLPY06] bibtex
    Y. Tu, S. Liu, S. Prabhakar, and B. Yao, "Load Shedding in Stream Databases: A Control-Based Approach.," in VLDB, 2006-09-27 2006, pp. 787-798.
    @inproceedings{conf/vldb/TuLPY06, added-at = {2006-09-27T00:00:00.000+0200},
      author = {Tu, Yi-Cheng and Liu, Song and Prabhakar, Sunil and Yao, Bin},
      biburl = {http://www.bibsonomy.org/bibtex/2f989d1303e30369e0988ca291ea7ddc5/dblp},
      booktitle = {VLDB},
      crossref = {conf/vldb/2006},
      date = {2006-09-27},
      description = {dblp},
      editor = {Dayal, Umeshwar and Whang, Kyu-Young and Lomet, David B. and Alonso, Gustavo and Lohman, Guy M. and Kersten, Martin L. and Cha, Sang Kyun and Kim, Young-Kuk},
      ee = {http://www.vldb.org/conf/2006/p787-tu.pdf},
      interhash = {6f1bceb8a5bb8ce9e281ceb93aaa46c2},
      intrahash = {f989d1303e30369e0988ca291ea7ddc5},
      isbn = {1-59593-385-9},
      keywords = {dblp},
      pages = {787-798},
      publisher = {ACM},
      timestamp = {2006-09-27T00:00:00.000+0200},
      title = {Load Shedding in Stream Databases: A Control-Based Approach.},
      url = {http://dblp.uni-trier.de/db/conf/vldb/vldb2006.html#TuLPY06},
      year = 2006 }
  • [conf-sosp-WelshCB01] bibtex
    M. Welsh, D. E. Culler, and E. A. Brewer, "SEDA: An Architecture for Well-Conditioned, Scalable Internet Services.," in SOSP, 2004-12-10 2001, pp. 230-243.
    @inproceedings{conf/sosp/WelshCB01, added-at = {2004-12-10T00:00:00.000+0100},
      author = {Welsh, Matt and Culler, David E. and Brewer, Eric A.},
      biburl = {http://www.bibsonomy.org/bibtex/2fbdd80ca43d2bff0a9c7d28f8e25a806/dblp},
      booktitle = {SOSP},
      date = {2004-12-10},
      description = {dblp},
      ee = {http://doi.acm.org/10.1145/502034.502057},
      interhash = {641f26f6e7eeeafe771c5c87fcf0c882},
      intrahash = {fbdd80ca43d2bff0a9c7d28f8e25a806},
      keywords = {dblp},
      pages = {230-243},
      timestamp = {2004-12-10T00:00:00.000+0100},
      title = {SEDA: An Architecture for Well-Conditioned, Scalable Internet Services.},
      url = {http://dblp.uni-trier.de/db/conf/sosp/sosp2001.html#WelshCB01},
      year = 2001 }