Packet Forwarding Algorithms in a Line Network

Antonios Antoniadis; Neal Barcelo; Daniel Cole; Kyle Fox; Benjamin Moseley; Michael Nugent; Kirk Pruhs

doi:10.1007/978-3-642-54423-1

Packet Forwarding Algorithms in a Line Network

Antonios Antoniadis, Neal Barcelo, Daniel Cole, Kyle Fox, Benjamin Moseley, Michael Nugent, Kirk Pruhs

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

7 Citations (Scopus)

Abstract

We initiate a competitive analysis of packet forwarding policies for maximum and average flow in a line network. We show that the policies Earliest Arrival and Furthest-To-Go are scalable, but not constant competitive, for maximum flow. We show that there is no constant competitive algorithm for average flow.

Original language	English
Title of host publication	LATIN 2014: Theoretical Informatics
Subtitle of host publication	11th Latin American Symposium, Montevideo, Uruguay, March 31–April 4, 2014. Proceedings
Editors	Alberto Pardo, Alfredo Viola
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	610-621
ISBN (Electronic)	978-3-642-54423-1
ISBN (Print)	978-3-642-54422-4
DOIs	https://doi.org/10.1007/978-3-642-54423-1
Publication status	Published - 2014
Externally published	Yes
Event	11th Latin American Symposium on Theoretical Informatics, LATIN 2014 - Montevideo, Uruguay Duration: 31 Mar 2014 → 4 Apr 2014 Conference number: 11

Conference

Conference	11th Latin American Symposium on Theoretical Informatics, LATIN 2014
Abbreviated title	LATIN
Country/Territory	Uruguay
City	Montevideo
Period	31/03/14 → 4/04/14

Access to Document

10.1007/978-3-642-54423-1

Cite this

Antoniadis, Antonios ; Barcelo, Neal ; Cole, Daniel ; Fox, Kyle ; Moseley, Benjamin ; Nugent, Michael ; Pruhs, Kirk. / Packet Forwarding Algorithms in a Line Network. LATIN 2014: Theoretical Informatics: 11th Latin American Symposium, Montevideo, Uruguay, March 31–April 4, 2014. Proceedings. editor / Alberto Pardo ; Alfredo Viola. Berlin, Heidelberg : Springer, 2014. pp. 610-621

@inproceedings{c023b3996fc04c5c90a0022ceb564ed9,

title = "Packet Forwarding Algorithms in a Line Network",

abstract = "We initiate a competitive analysis of packet forwarding policies for maximum and average flow in a line network. We show that the policies Earliest Arrival and Furthest-To-Go are scalable, but not constant competitive, for maximum flow. We show that there is no constant competitive algorithm for average flow.",

author = "Antonios Antoniadis and Neal Barcelo and Daniel Cole and Kyle Fox and Benjamin Moseley and Michael Nugent and Kirk Pruhs",

year = "2014",

doi = "10.1007/978-3-642-54423-1",

language = "English",

isbn = "978-3-642-54422-4",

pages = "610--621",

editor = "Alberto Pardo and Alfredo Viola",

booktitle = "LATIN 2014: Theoretical Informatics",

publisher = "Springer",

address = "Netherlands",

note = "11th Latin American Symposium on Theoretical Informatics, LATIN 2014, LATIN ; Conference date: 31-03-2014 Through 04-04-2014",

}

Antoniadis, A, Barcelo, N, Cole, D, Fox, K, Moseley, B, Nugent, M & Pruhs, K 2014, Packet Forwarding Algorithms in a Line Network. in A Pardo & A Viola (eds), LATIN 2014: Theoretical Informatics: 11th Latin American Symposium, Montevideo, Uruguay, March 31–April 4, 2014. Proceedings. Springer, Berlin, Heidelberg, pp. 610-621, 11th Latin American Symposium on Theoretical Informatics, LATIN 2014, Montevideo, Uruguay, 31/03/14. https://doi.org/10.1007/978-3-642-54423-1

Packet Forwarding Algorithms in a Line Network. / Antoniadis, Antonios; Barcelo, Neal; Cole, Daniel; Fox, Kyle; Moseley, Benjamin; Nugent, Michael; Pruhs, Kirk.

LATIN 2014: Theoretical Informatics: 11th Latin American Symposium, Montevideo, Uruguay, March 31–April 4, 2014. Proceedings. ed. / Alberto Pardo; Alfredo Viola. Berlin, Heidelberg : Springer, 2014. p. 610-621.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Packet Forwarding Algorithms in a Line Network

AU - Antoniadis, Antonios

AU - Barcelo, Neal

AU - Cole, Daniel

AU - Fox, Kyle

AU - Moseley, Benjamin

AU - Nugent, Michael

AU - Pruhs, Kirk

N1 - Conference code: 11

PY - 2014

Y1 - 2014

N2 - We initiate a competitive analysis of packet forwarding policies for maximum and average flow in a line network. We show that the policies Earliest Arrival and Furthest-To-Go are scalable, but not constant competitive, for maximum flow. We show that there is no constant competitive algorithm for average flow.

AB - We initiate a competitive analysis of packet forwarding policies for maximum and average flow in a line network. We show that the policies Earliest Arrival and Furthest-To-Go are scalable, but not constant competitive, for maximum flow. We show that there is no constant competitive algorithm for average flow.

U2 - 10.1007/978-3-642-54423-1

DO - 10.1007/978-3-642-54423-1

M3 - Conference contribution

SN - 978-3-642-54422-4

SP - 610

EP - 621

BT - LATIN 2014: Theoretical Informatics

A2 - Pardo, Alberto

A2 - Viola, Alfredo

PB - Springer

CY - Berlin, Heidelberg

T2 - 11th Latin American Symposium on Theoretical Informatics, LATIN 2014

Y2 - 31 March 2014 through 4 April 2014

ER -