The main purpose of routing and flow control in a communication network is, roughly speaking, to keep delay per message (ie travel time from origin to destination) within an acceptable level while minimizing the amount of offered traffic t~ at is rejected by the network due to overloading. These two objectives are clearly contradictory so a good routing and flow control scheme must strike a balance between the two. It should also take into account a number of other issues such as fairness for all users, the possibility that the network topology can be altered due to unexpected link or node failures, and the fact that tke statistics of offered traffic change with time.

In this expository paper we consider some aspects of routing and flow control for long-haul wire data ne£ works in which the communication resource is scarce (as opposed to local networks such as Ethernet where it is not), and where there are no issues of contention resolution due to random access of a broadcast medium (as in some satellite, local, and packet radio networks). We place primary emphasis on optimal procedures since these offer a more sound philosophical basis than heuristic schemes and also provide a yardstick for measuring the effectiveness of