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 proceedingConference contributionAcademicpeer-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 languageEnglish
Title of host publicationLATIN 2014: Theoretical Informatics
Subtitle of host publication11th Latin American Symposium, Montevideo, Uruguay, March 31–April 4, 2014. Proceedings
EditorsAlberto Pardo, Alfredo Viola
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages610-621
ISBN (Electronic)978-3-642-54423-1
ISBN (Print)978-3-642-54422-4
DOIs
Publication statusPublished - 2014
Externally publishedYes
Event11th Latin American Symposium on Theoretical Informatics, LATIN 2014 - Montevideo, Uruguay
Duration: 31 Mar 20144 Apr 2014
Conference number: 11

Conference

Conference11th Latin American Symposium on Theoretical Informatics, LATIN 2014
Abbreviated titleLATIN
CountryUruguay
CityMontevideo
Period31/03/144/04/14

Cite this