Throughput in Asynchronous Networks - Computer Science > Networking and Internet ArchitectureReport as inadecuate

Throughput in Asynchronous Networks - Computer Science > Networking and Internet Architecture - Download this document for free, or read online. Document in PDF available to download.

Abstract: We introduce a new -worst-case- model for an asynchronous communicationnetwork and investigate the simplest yet central task in this model, namelythe feasibility of end-to-end routing. Motivated by the question of howsuccessful a protocol can hope to perform in a network whose reliability isguaranteed by as few assumptions as possible, we combine the main-unreliability- features encountered in network models in the literature,allowing our model to exhibit all of these characteristics simultaneously. Inparticular, our model captures networks that exhibit the following properties:1 On-line; 2 Dynamic Topology; 3Distributed-Local Control 4 AsynchronousCommunication; 5 Polynomially Bounded Memory; 6 No Minimal ConnectivityAssumptions. In the confines of this network, we evaluate throughputperformance and prove matching upper and lower bounds. In particular, usingcompetitive analysis perhaps somewhat surprisingly we prove that the optimalcompetitive ratio of any on-line protocol is 1-n where n is the number ofnodes in the network, and then we describe a specific protocol and prove thatit is n-competitive. The model we describe in the paper and for which weachieve the above matching upper and lower bounds for throughput represents the-worst-case- network, in that it makes no reliability assumptions. In manypractical applications, the optimal competitive ratio of 1-n may beunacceptable, and consequently stronger assumptions must be imposed on thenetwork to improve performance. However, we believe that a fundamental startingpoint to understanding which assumptions are necessary to impose on a networkmodel, given some desired throughput performance, is to understand what isachievable in the worst case for the simplest task namely end-to-end routing.

Author: Paul Bunn, Rafail Ostrovsky



Related documents