5 Search Results for "Sterbenz, James"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.30
Approximating Optimal Broadcast of Files in a Hose-Model Network

Authors: Thomas Erlebach, Naveen Garg, Sukriti Gupta, and Amitabh Trehan

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
The paper considers the problem of file sharing among peers who are connected to a common core network through links of differing upload and download capacities, as is the case in networks provisioned according to the hose model. The file is assumed to be divided into equal-sized chunks, and a peer can start sending a "chunk" of the file to another peer only after it has received the entire chunk. The objective is to share a chunk, initially residing on one of the peers, with all other peers in the least time possible. Peers can simultaneously send/receive parts of a chunk to/from multiple peers, subject to the upload and download capacity constraints. We only consider the problem of broadcasting one chunk to all peers. We consider two different models - in the migratory model, a peer can receive the chunk from multiple peers, while in the non-migratory model, any peer can receive the chunk only from one peer. For the migratory model, introduced in this paper, we show a novel integer program and use the optimum solution to the LP-relaxation to give a schedule with makespan e^{1/e} OPT+P where P is the time required by the slowest peer to download the chunk. Minimising makespan in the non-migratory model is known to be NP-hard. We give a solution with makespan 18OPT+P and this is the first approximation algorithm for heterogeneous and asymmetric upload/download capacities. We also consider 2 special cases. For uniform download capacities, we obtain a solution with makespan 2OPT extending a result due to Liu [Pangfeng Liu, 2002]. For uniform upload capacities, we give the first approximation algorithm, producing makespan at most 2OPT+2P.
Cite as

Thomas Erlebach, Naveen Garg, Sukriti Gupta, and Amitabh Trehan. Approximating Optimal Broadcast of Files in a Hose-Model Network. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.FSTTCS.2025.30,
  author =	{Erlebach, Thomas and Garg, Naveen and Gupta, Sukriti and Trehan, Amitabh},
  title =	{{Approximating Optimal Broadcast of Files in a Hose-Model Network}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{30:1--30:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.30},
  URN =		{urn:nbn:de:0030-drops-251118},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.30},
  annote =	{Keywords: File sharing, scheduling, peer-to-peer networks}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.15
Parameterized Complexity of Directed Traveling Salesman Problem

Authors: Václav Blažej, Andreas Emil Feldmann, Foivos Fioravantes, Paweł Rzążewski, and Ondřej Suchý

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The Directed Traveling Salesman Problem (DTSP) is a variant of the classical Traveling Salesman Problem in which the edges in the graph are directed and a vertex and edge can be visited multiple times. The goal is to find a directed closed walk of minimum length (or total weight) that visits every vertex of the given graph at least once. In a yet more general version, Directed Waypoint Routing Problem (DWRP), some vertices are marked as terminals and we are only required to visit all terminals. Furthermore, each edge has its capacity bounding the number of times this edge can be used by a solution. While both problems (and many other variants of TSP) were extensively investigated, mostly from the approximation point of view, there are surprisingly few results concerning the parameterized complexity. Our starting point is the result of Marx et al. [APPROX/RANDOM 2016] who proved that DTSP is W[1]-hard parameterized by distance to pathwidth 3. In this paper we aim to initiate the systematic complexity study of variants of Directed Traveling Salesman Problem with respect to various, mostly structural, parameters. We show that DWRP is FPT parameterized by the solution size, the feedback edge number and the vertex integrity of the underlying undirected graph. Furthermore, the problem is XP parameterized by treewidth. On the complexity side, we show that the problem is W[1]-hard parameterized by the distance to constant treedepth.
Cite as

Václav Blažej, Andreas Emil Feldmann, Foivos Fioravantes, Paweł Rzążewski, and Ondřej Suchý. Parameterized Complexity of Directed Traveling Salesman Problem. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blazej_et_al:LIPIcs.ISAAC.2025.15,
  author =	{Bla\v{z}ej, V\'{a}clav and Feldmann, Andreas Emil and Fioravantes, Foivos and Rz\k{a}\.{z}ewski, Pawe{\l} and Such\'{y}, Ond\v{r}ej},
  title =	{{Parameterized Complexity of Directed Traveling Salesman Problem}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.15},
  URN =		{urn:nbn:de:0030-drops-249231},
  doi =		{10.4230/LIPIcs.ISAAC.2025.15},
  annote =	{Keywords: Directed TSP, parameterized complexity, vertex integrity, treedepth}
}
Document
DOI: 10.4230/DagSemProc.08102.4
4. 8102 Working Group – Attack Taxonomy

Authors: Marc Daciér, Hervé Debar, Thorsten Holz, Engin Kirda, Jan Kohlrausch, Christopher Kruegel, Konrad Rieck, and James Sterbenz

Published in: Dagstuhl Seminar Proceedings, Volume 8102, Perspectives Workshop: Network Attack Detection and Defense (2008)

Abstract
The starting point of this working group was the question about the kinds of attacks that can be detected by inspecting in network traffic. In general, we identified four major problems that network-based intrusion detection systems are facing: 1. Encrypted network traffic 2. Application-level attacks 3. Performance 4. Evasion attack.
Cite as

Marc Daciér, Hervé Debar, Thorsten Holz, Engin Kirda, Jan Kohlrausch, Christopher Kruegel, Konrad Rieck, and James Sterbenz. 4. 8102 Working Group – Attack Taxonomy. In Perspectives Workshop: Network Attack Detection and Defense. Dagstuhl Seminar Proceedings, Volume 8102, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{dacier_et_al:DagSemProc.08102.4,
  author =	{Daci\'{e}r, Marc and Debar, Herv\'{e} and Holz, Thorsten and Kirda, Engin and Kohlrausch, Jan and Kruegel, Christopher and Rieck, Konrad and Sterbenz, James},
  title =	{{4. 8102 Working Group – Attack Taxonomy}},
  booktitle =	{Perspectives Workshop: Network Attack Detection and Defense},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8102},
  editor =	{Georg Carle and Falko Dressler and Richard A. Kemmerer and Hartmut K\"{o}nig and Christopher Kruegel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08102.4},
  URN =		{urn:nbn:de:0030-drops-14955},
  doi =		{10.4230/DagSemProc.08102.4},
  annote =	{Keywords: Intrusion detection and prevention, attack response and countermeasures, reactive security, automated security, survivability and self-protection, ma network monitoring, flow analysis, denial of service detection and response, event correlation}
}
Document
DOI: 10.4230/DagSemProc.08102.6
6. 08102 Working Group – Requirements for Network Monitoring from an IDS Perspective

Authors: Lothar Braun, Falko Dressler, Thorsten Holz, Engin Kirda, Jan Kohlrausch, Christopher Kruegel, Tobias Limmer, Konrad Rieck, and James Sterbenz

Published in: Dagstuhl Seminar Proceedings, Volume 8102, Perspectives Workshop: Network Attack Detection and Defense (2008)

Abstract
Detection of malicious traffic is based on its input data, the information that is co-ming from network-based monitoring systems. Best detection rates would only be possible by monitoring all data transferred over all network lines in a distributed net-work. Monitoring and reporting this amount of data are feasible in neither today's, nor will be in future's systems. Later analysis like stateful inspection of the traffic imposes even more processing costs. But only at this level of monitoring and analysis there may be a chance to capture all attacks inside a system. So there needs to be a trade-off between detection success and the processing costs.
Cite as

Lothar Braun, Falko Dressler, Thorsten Holz, Engin Kirda, Jan Kohlrausch, Christopher Kruegel, Tobias Limmer, Konrad Rieck, and James Sterbenz. 6. 08102 Working Group – Requirements for Network Monitoring from an IDS Perspective. In Perspectives Workshop: Network Attack Detection and Defense. Dagstuhl Seminar Proceedings, Volume 8102, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{braun_et_al:DagSemProc.08102.6,
  author =	{Braun, Lothar and Dressler, Falko and Holz, Thorsten and Kirda, Engin and Kohlrausch, Jan and Kruegel, Christopher and Limmer, Tobias and Rieck, Konrad and Sterbenz, James},
  title =	{{6. 08102 Working Group – Requirements for Network Monitoring from an IDS Perspective}},
  booktitle =	{Perspectives Workshop: Network Attack Detection and Defense},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8102},
  editor =	{Georg Carle and Falko Dressler and Richard A. Kemmerer and Hartmut K\"{o}nig and Christopher Kruegel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08102.6},
  URN =		{urn:nbn:de:0030-drops-14970},
  doi =		{10.4230/DagSemProc.08102.6},
  annote =	{Keywords: Intrusion detection and prevention, attack response and countermeasures, reactive security, automated security, survivability and self-protection, ma network monitoring, flow analysis, denial of service detection and response, event correlation}
}
Document
DOI: 10.4230/DagSemProc.04411.14
Peer-to-Peer vs. the Internet: A Discussion on the Proper and Practical Location of Functionality

Authors: James P.G. Sterbenz

Published in: Dagstuhl Seminar Proceedings, Volume 4411, Service Management and Self-Organization in IP-based Networks (2005)

Abstract
Peer-to-peer information sharing has become one of the dominant Internet applications, measured not only in the number of users, but also in the network bandwidth consumed. Thus, it is reasonable to examine the location of support functionality such as self-organisation, resource discovery, multipoint-to-multipoint group communication, forwarding, and routing, to provide the needed service to applications while optimising resource usage in the network. This position paper is intended to stimulate discussion in two related areas: First, where {\em should} functionality to support peer-to-peer applications be located: in the network, or as an application overlay among end systems. Second, where {\em can} functionality be located, given the practical constraints of the modern Internet including closed systems and middleboxes, as well as administrative, legal, and social issues. We will discuss the performance implications of these decisions, including whether low latency bounds for delay sensitive peer-to-peer applications (such as distributed network computing) can ever be achieved in this environment.
Cite as

James P.G. Sterbenz. Peer-to-Peer vs. the Internet: A Discussion on the Proper and Practical Location of Functionality. In Service Management and Self-Organization in IP-based Networks. Dagstuhl Seminar Proceedings, Volume 4411, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{sterbenz:DagSemProc.04411.14,
  author =	{Sterbenz, James P.G.},
  title =	{{Peer-to-Peer vs. the Internet: A Discussion on the Proper and Practical Location of Functionality}},
  booktitle =	{Service Management and Self-Organization in IP-based Networks},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4411},
  editor =	{Matthias Bossardt and Georg Carle and D. Hutchison and Hermann de Meer and Bernhard Plattner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04411.14},
  URN =		{urn:nbn:de:0030-drops-1156},
  doi =		{10.4230/DagSemProc.04411.14},
  annote =	{Keywords: network architecture , peer-to-peer , client/server , nd-to-end arguments , protocol layering , policy , ussle}
}
  • Refine by Type
  • 5 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 2 2008
  • 1 2005

  • Refine by Author
  • 2 Holz, Thorsten
  • 2 Kirda, Engin
  • 2 Kohlrausch, Jan
  • 2 Kruegel, Christopher
  • 2 Rieck, Konrad
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs
  • 3 DagSemProc

  • Refine by Classification
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 2 Intrusion detection and prevention
  • 2 attack response and countermeasures
  • 2 automated security
  • 2 denial of service detection and response
  • 2 event correlation
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact