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?) ? ( log log ? ) bits are required in every network, where ?  denotes the treewidth of the network. In planar networks, ?(log?) ? ( log ? ) bits are required.
end-to-end treewidth sequence transmission