Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
A Glimpse at Paul G. Spirakis Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Stability in Heterogeneous Dynamic Multimedia Networks

Author : Dimitrios Koukopoulos

Published in: Algorithms, Probability, Networks, and Games

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Internet and other multimedia packet-switched networks are heterogeneous due to the simultaneous running (composition) of different contention-resolution protocols over different network hosts and the existence of various types of network links. Also, real networks are dynamic in their nature due to intentional or unintentional changes on network link service rates or tra nsient link failures. Our interest is focused on FIFO compositions with other contention-resolution protocols due to the FIFO popularity for offering best-effort services in packet-switched networks. A packet-switched network is stable, if the number of packets in the network remains bounded at all times against any adversary. We use an enhanced adversarial framework that is based on an adversary that controls packet injection rates, along with packet paths, and manipulates link slowdowns or capacities. Within this framework, we study the impact of specific compositions of FIFO with other protocols on the network stability using as a test-bed specific network topologies which have been proved forbidden for stability for a single protocol, fixed link slowdowns/capacities and packet paths without repeated links/edges. Our results suggest that the instability behavior of a network using FIFO compositions under adversarial attacks, that dynamically change link slowdowns/capacities, is not only maintained, but, also, may become worse than in the case of attacks that do not change slowdowns/capacities or when a single protocol, like FIFO, is employed on all network queues for contention-resolution. We believe that this study can advance the research for the provision of trustworthy heterogeneous networks.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Data-Streaming and Concurrent Data-Object Co-design: Overview and Algorithmic Challenges
next chapter Advances in the Parallelization of the Simplex Method
Literature
1.
Alvarez, C., Blesa, M., Serna, M.: A characterization of universal stability in the adversarial queuing model. SIAM J. Comput. 34, 41–66 (2004)MathSciNetCrossRefMATH
2.
Alvarez, C., Blesa, M., Serna, M.: The robustness of stability under link and node failures. Theor. Comput. Sci. 412, 6855–6878 (2011)MathSciNetCrossRefMATH
3.
Andrews, M.: Instability of FIFO in the permanent sessions model at arbitrarily small network loads. ACM Trans. Algorithms 5(3), 1–29 (2009)MathSciNetCrossRefMATH
4.
Andrews, M., Awerbuch, B., Fernández, A., Kleinberg, J., Leighton, T., Liu, Z.: Universal stability results for greedy contention-resolution protocols. J. ACM 48, 39–69 (2001)MathSciNetCrossRefMATH
5.
Berger, D., Karsten, M., Schmitt, J.: On the relevance of adversarial queueing theory in practice. In: Proceedings of the ACM International Conference on Measurement and Modeling of Computer Systems, pp. 343–354 (2014)
6.
Berger, D., Karsten, M., Schmitt, J.: Simulation of adversarial scenarios in OMNeT++: putting adversarial queueing theory from its head to feet. In: Proceedings of the 6th International ICST Conference on Simulation Tools and Techniques, pp. 291–298 (2013)
7.
Bhattacharjiee, R., Goel, A., Lotker, Z.: Instability of FIFO at arbitrarily low rates in the adversarial queueing model. SIAM J. Comput. 34(2), 318–332 (2005)MathSciNetCrossRefMATH
8.
Blesa, M.J.: Deciding stability in packet-switched FIFO networks under the adversarial queuing model in polynomial time\(^{,}\). In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol. 3724, pp. 429–441. Springer, Heidelberg (2005) CrossRef
9.
Blesa, M., Calzada, D., Fernandez, A., Lopez, L.: Adversarial queueing model for continuous network dynamics. Theory Comput. Syst. 44, 304–331 (2009)MathSciNetCrossRefMATH
10.
11.
Borodin, A., Ostrovsky, R., Rabani, Y.: Stability preserving transformations: packet routing networks with edge capacities and speeds. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 601–610 (2001)
12.
Chlebus, B.S., Cholvi, V., Kowalski, D.R.: Stability of adversarial routing with feedback. In: Gramoli, V., Guerraoui, R. (eds.) NETYS 2013. LNCS, vol. 7853, pp. 206–220. Springer, Heidelberg (2013) CrossRef
13.
14.
Cholvi, V., Echague, J., Fernandez, A.: Stability of FIFO networks under adversarial models: state of the art, computer networks. Int. J. Comput. Telecommun. Netw. 51(15), 4460–4474 (2007)CrossRef
15.
Diaz, J., Koukopoulos, D., Nikoletseas, S., Serna, M., Spirakis, P., Thilikos, D.: Stability and non-stability of the FIFO protocol. In: Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 48–52 (2001)
16.
Floyd, S., Paxson, V.: Difficulties in simulating the Internet. IEEE/ACM Trans. Netw. 9, 392–403 (2001)CrossRef
17.
Koukopoulos, D.: Instability behaviour of heterogeneous multimedia networks under dynamic adversarial attacks. J. Math. Comput. Model. 57, 2671–2684 (2013)MathSciNetCrossRefMATH
18.
Koukopoulos, D.: The impact of FIFO compositions with other protocols on the stability of multimedia networks facing dynamic adversarial attacks. In: Proceedings of the 5th International Conference on Multimedia Information Networking and Security, pp. 575–578 (2013)
19.
Koukopoulos, D.: The impact of dynamic adversarial attacks on the stability of heterogeneous multimedia networks. J. Comput. Commun. 33, 1695–1706 (2010)CrossRef
20.
Koukopoulos, D.: Stability in heterogeneous multimedia networks under adversarial attacks. J. Univ. Comput. Sci. 14(2), 444–464 (2009)
21.
Koukopoulos, D.: The impact of dynamic link slowdowns on network stability. In: Proceedings of the 8th International Symposium on Parallel Architectures, Algorithms and Networks, pp. 340–345 (2005)
22.
Koukopoulos, D., Mavronicolas, M., Nikoletseas, S., Spirakis, P.: The impact of network structure on the stability of greedy protocols. Theory Comput. Syst. 38, 425–460 (2005)MathSciNetCrossRefMATH
23.
Koukopoulos, D., Mavronicolas, M., Nikoletseas, S., Spirakis, P.: On the stability of compositions of universally stable, greedy, contention-resolution protocols. In: Malkhi, D. (ed.) DISC 2002. LNCS, vol. 2508, pp. 88–102. Springer, Heidelberg (2002) CrossRef
24.
Koukopoulos, D., Mavronikolas, M., Spirakis, P.: Performance and stability bounds for dynamic networks. J. Parallel Distrib. Comput. 67, 386–399 (2007)CrossRefMATH
25.
Koukopoulos, D., Mavronikolas, M., Spirakis, P.: The increase of the instability of networks due to quasi-static link capacities. J. Theor. Comput. Sci. 381, 44–56 (2007)MathSciNetCrossRefMATH
26.
Koukopoulos, D., Mavronicolas, M., Spirakis, P.: Instability of networks with quasi-static link capacities. In: Proceedings of the 10th International Colloquium on Structural Information and Communication Complexity, pp. 179–194 (2003)
27.
Koukopoulos, D.K., Nikolopoulos, S.D.: Heterogenous networks can be unstable at arbitrarily low injection rates. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds.) CIAC 2006. LNCS, vol. 3998, pp. 93–104. Springer, Heidelberg (2006) CrossRef
28.
Koukopoulos, D.K., Nikoletseas, S.E., Spirakis, P.G.: Stability issues in heterogeneous and fifo networks under the adversarial queueing model. In: Monien, B., Prasanna, V.K., Vajapeyam, S. (eds.) HiPC 2001. LNCS, vol. 2228, pp. 3–14. Springer, Heidelberg (2001) CrossRef
29.
Levine, D., Kessler, G.: Denial of service attacks. In: Kabay, M., Bosworth, S. (eds.) Computer Security Handbook, 4th edn. Wiley, New York (2002)
30.
Lynch, N.: Distributed Algorithms. Morgan Kaufmann, San Francisco (1996)MATH
31.
Moore, D., Shannon, C., Brown, D., Voelker, G., Savage, S.: Inferring Internet denial-of-service activity. ACM Trans. Comput. Syst. 24(2), 115–139 (2006)CrossRef
32.
Weinard, M.: Deciding the FIFO stability of networks in polynomial time. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds.) CIAC 2006. LNCS, vol. 3998, pp. 81–92. Springer, Heidelberg (2006) CrossRef
33.
Yau, D., Lui, J., Liang, F., Yam, Y.: Defending against distributed denial-of-service attacks with max-min fair server-centric router throttles. IEEE/ACM Trans. Netw. 13(1), 29–42 (2005)CrossRef
Metadata
Title
Stability in Heterogeneous Dynamic Multimedia Networks
Author
Dimitrios Koukopoulos
Copyright Year
2015
Book
Algorithms, Probability, Networks, and Games

Print ISBN: 978-3-319-24023-7

Electronic ISBN: 978-3-319-24024-4

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-24024-4_16

Premium Partner

    Image Credits