Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
452585 | Computer Networks | 2006 | 9 Pages |
Abstract
The end-to-end communication problem is a protocol design problem, for sending a packet from a specified source-node s to a specified target-node t , through an unreliable asynchronous memoryless communication network. The protocol must insure reception and termination. In this paper, we measure the complexity of the protocol in term of header size, i.e., the quantity of information that must be attached to the packets to insure their delivery. We show that headers of Ω(loglogτ)Ω(loglogτ) bits are required in every network, where τ denotes the treewidth of the network. In planar networks, Ω(logτ)Ω(logτ) bits are required.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Networks and Communications
Authors
Pierre Fraigniaud, Cyril Gavoille,