Computing The Throughput Of A Network With Dedicated Lines

Suppose that we wish to transmit many messages from a node of a network to another, and the delays of the arcs of the network are known. Once a message has been sent along an arc, the arc cannot be used to transmit another message until the first message arrives at the other end. We wish to estimate the throughput of such a network, that is, the number of messages from the source to the destination that can be transmitted within a given time T. We show that this throughput is hard to compute for finite values of T, but can be estimated asymptotically using flow techniques.