Leonard Kleinrock investigated the Message Delay in Communication Nets with Storage in his PhD thesis. As a concrete example for a message switching network, he referred to Western Union's Plan 55-A system.

There is a description available in the WWW.

With respect to the Internet, it would be interesting to investigate, whether the resource consumption of the net and delay variations for individual packets (which are the "messages" in the Internet today) scale uo in acceptable manner.

In this context, it may be useful to describe the development from the Plan 55 A system towards the Internet, as it is known today.

From Plan 55 A towards the Internet

From Plan 55 A towards the ARPANet

IMP themselves established an independent subnet.

In 1969, Len Kleinrock et al. started the first four of a number of Interface Message Processors (IMP) which established the ARPANet. In a sense, the ARPANet was an electronic reimplementation of the Plan 55 A system, where IMP served as a replacement for the former electromechanical switching offices.

Heart, Frank; Kahn, Robert; Ornstein, Severo; Crowther, William; Walden, David (1970). "The Interface Message Processor for the ARPA Computer Network". 1970 Spring Joint Computer Conference. AFIPS Proc. 36: 551–567. describes the Host to Host Protol, which is used on the IMP.

Hence, for a more detailed discussion, two cases are to be distinguished.

A good description of the ARPANet (in German) can be found in a work by Stefan Kinkartz. Refer to this description of the ARPAnet and particularly to this sketch by Larry Roberts.

(Source: ARPANEt page of Larry Roberts) which shows the basic architecture. Hosts and Terminals were connected to IMP, the set of interconnected IMP established the so called "subnet".

AHIP ARPANET Host-IMP Protocol RFC 802, The ARPANET 1822L Host Access Protocol


21. BELS74A D. Belsnes, "Flow control in packet switching networks," INWG Note #63, October 1974.

Congestion and Buffer Bloat

It is interesting to listen to the Talk by Jim Gettys:"Bufferbloat: Dark Buffers in the Internet" and to have a look at John Nagle'as Paper "On Packet Switches With Infinite Storage", which appeared as RFC 970.

I'm still to understand, at which time TCP finally adopted the sliding window scheme including Go Back N, as it was used in the 80ies in point to point protocols, e.g. in Kermit. In RFC 793, TCP adopts the sliding window scheme, however, the Go Back N scheme was not yet adopted in the RFC. However, to the best of my knowledge, the retransmission scheme as described in RFC 793, which uses individual retransmission timers and copies for each sent packet, was never used. All practical implementations adopted a Go Back N scheme.

Some Remarks on Flow Control

In RFC 675 we read the following about flow control.

4.5.3 The RECEIVE Side

   At the receiving side there are two requirements for buffering:

   (l) Rate Discrepancy:

      If the sender produces data much faster or much slower than the
      receiver consumes it, little buffering is needed to maintain the
      receiver at near maximum rate of operation. Simple queuing
      analysis indicates that when the production and consumption
      (arrival and service) rates are similar in magnitude, more
      buffering is needed to reduce the effect of stochastic or bursty
      arrivals and to keep the receiver busy.

   (2) Disorderly Arrivals:

      When packets arrive out of order, they must be buffered until the
      missing packets arrive so that packets (or letters) are delivered
      in sequence. We do not advocate the philosophy that they be
      discarded, unless they have to be, otherwise a poor effective
      bandwidth may be observed. Path length, packet size, traffic
      level, routing, timeouts, window size, and other factors affect
      the amount by which packets come out of order. This is expected to
      be a major area of investigation.


Actually, the second part is important. Of course, there may be a rate discrepancy between sender and receiver. However, using buffering and flow control to overcome this, is a quite cumbersome job. Basically, flow control can cause a sender to pause or to continue. So, when a sender's rate is too fast for the receiver, a receiver often does not slow down the sender's rate. Actually, it causes the sender to send data at it's rate in bursts and causes the sender to pause now and then, so that the average arrival rate at the receiver can be handled.

Unfortunately, in a TCP connection, we don't know, how fast data is offered to the network by the application, we don't know how fast an application can process incoming data, We don't even know for sure the throughput at the links in charge, which may be even volatile in some cases.

As a result, naive approaches for using flow control for rate adaptation may cause quite funny effects. (Actually the quoted text proposes some flow control scheme, we don't discuss it in detail here.

In summary, flow control is hardly a suitable means for making the sender send with an appropriate rate. Buffering and flow control are mainly used to keep incoming packets and to reconstruct the original data flow.

Some Notes on the Congavoid Paper

For the discussion of the congavoid paper itself, it is inevitable to discuss the terms stationarity and stability in the context of queueing systems. At least, what the congavoid paper is concerned, the difference between these is not perfectly clear. This might be due to the fact that the term "stability" is coined in the context of system theory, while the term "stationariy" is coined in the context of queueing systems and stochastic processes.

As a work in progress, I'm working on an annotated version of the congavoid paper. In addition, I work on an annotated version of RFC 896.

System Theory and Queueing Theory

System theory and queueing theory pursue completely different goals. In very brief terms, the difference can be described as follows.

As a typical example, the reader may consider the queue at the counter of his local supermarket. When this is described by a stochastic process, the individual events are time lines where the length of the queue is listed with respect to time. The event space is the set of all possible lists. Any information available for this system is the probability measure associated with the subsets of the event space as defined in the event algebra (which is of course defined upon the event pace).

Please note: When random experiments are conducted here, the random events are not "a customer enters the queue" or "a customer leaves the queue". Random experiments are conducted by choosing a complete time series here, otherwise a customer's enty to a queue or a customer's leaving may belong to completely different random events and a discussion would compare peaches with oranges.

The only informtion availabe for the system is the event space, the event algebra and the probabilty measure. There is absolutely no information available about the internal structure, reasons for a particular behaviour, (causal) interdependencies between states etc.

A very brief introduction into a system's representation in state space can be found here>.

With respect to system theory, there is a quite useful Wikipedida article on stabilty theory.

Stability in System Theory

As described in the Wikipedida article. system theory aims to describe systems in terms of differential or difference equations. In the ideal case, a system's behaviour can be described of a function of time. Please note: This function is deterministic.

A crucial point in stability theory, and perhaps this is a basic misconception in the congavoid paper, is the concept of equilibrium points.

When we describe a system in terms of equations, our equations describe state variables and their interaction in time. In colloquial speech, state variables are energy stores and the dynamic behaviour of a dynamic system is "doing work", i.e., coll., moving around energy from (one) store(s) to other(s). This process may come to an end, if the system is sufficiently damped, i.e. all energy in the system is eventually exhausted. And it may come to an end when the system reaches an equilibrium point, i.e.&nspb;the system will stay in this state permanently, unless it is deflected by an external influence.

The reader my find a deeper introduction to state variables in Rudolf Kalman, On the general theory of control systems in Proc. First IFAC Congress Automatic Control, Moscow, 1960, Butterworths, London, vol. 1, pages 481-492

NB in the congavoid paper, the term "equilibrium" refers to an equilibrium between the number of packets which enter a path and the number of packets which leave the path. This well make sense, but it is completely different from what is meant by the term equilibrium in system theory.

Please note that the notion of state variables is not really found in the congavoid paper. It would be quite interestig, nevertheless, to consider this concept in the TCP context, when packets are identified with "energy" (i.e. the ability to do work) and buffers in the systems are identified with "energy stores", i.e. state variables etc.. The tough problem however is to state the differential equations then, consider e.g. a Wifi system: How long does it take to convey a packet from one buffer to the next in a Wifi-system?

There is a huge bunch of work dealing exactly with questions like this (by Saverio Mascolo, Laurent Massoulie, only to mention two authors) and the whole work on "fluid flow models" which unfortunately fails in this point. And the very reason is that differential equations, though being well suited to describe deterministic state transions, are ill suited to describe non determimistic ones.

In very brief terms, a system is in equilibrium state, when no energy flow occurs. The system has calmed down, or thermodynamically: cooled down. In other words: Without external intervention, nothing is going to happen at all. In contrast to that, according to the congavoid paper a TCP in equilibrium state is surprisingly active.

The reader might rise the question, how an undamped pendulum will fit into this model. Now, Aleksandr Mikhailovich Lyapunov introduced the concept of Lyapunov stability, which means that a stable system will permanently follow a certain trajectory in state space, unless it is deflected. So, the pendulum follows a state space trajectory, where energy constantly swings between potential energy and kinetic energy.

Stability in Queueing Theory

The first question here is what "stability" in queueing systems should be at all. Emilio Leonardi el al. provide a possible answer in On the Stability of Input-Queued Switches with Speed-Up.

Congestion in General

Particularly in the congavoid-paper, "congestion" appears to be a catchall element for "network problems". There is a basic concern, a lack of throughout, and the question arises: What's actually the problem?

So, we gathered:

Perhaps clumsy traffic is a the most important concern in congestion control, actually this is the reason why the "isarithmic scheme" by Davies, 1972, was abandoned. End to end congestion control schemes suffer from the same problem as the isarithmic scheme: It is possible, that the path from a packet's sender to its destination may carry 100 packets, however the link and hop, which immediately follow the sender, can only carry one or two packets. Hence, when the sender offers 100 packets load to the network, packets will be dropped.