Header-size lower bounds for end-to-end communication in memoryless networks

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.