ABSTRACT
The development of the RCP network was undertaken in 1971 by the French PTT for the purpose of experimenting packet switching techniques in the context of a public service.
The primary choices are debated. They concern the form and rough outlines of the offered services and the related mechanisms necessary to their implementation :
- The choice of virtual circuits as a basic service.
- The choice of controlling the resources involved all along a virtual path by assigning to it a fixed route during its life time.
Some other options evolved to a certain extent, benefiting from experience and from a better knowledge of the customer's needs, mainly those of structuring transmitted data into messages. New schemes were thought of for signalling and flow control on the virtual circuits.
Although they could not have been implemented in the RCP network these amended options were proven to be highly effective in the design of the "procedure converter" software, which reinforced the RCP experiment in 1975. In the mean-time the first specifications of TRANSPAC, a national public network, were carried out.
INTRODUCTION
The aim of this paper is not to provide a detailed description of the RCP network[1], but to throw light on the motivations of the fundamental choices in the context of the years 1971 to 1973 which saw the project take shape after a rather timid start.
At the beginning of 1974, it became necessary to fix the specifications of the network in order to permit an operational phase to be started and allow the connection of computers belonging to customers both internal and external to the Administration of the PTT.
Meanwhile, experience having showed up new necessities and certain weaknesses, improvements were considered and some of them tried out by means of a "procedure converter" programmed on a minicomputer. At that stage however, the main effort was to be directed towards the elaboration of the specifications of the TRANSPAC network, the fullscale successor of RCP.
A FUNDAMENTAL CHOICE : PACKET SWITCHING
It was in 1971 that the idea of packet switching appeared at the CNET in the framework of the HERMES project (This vast project, aiming to endow the whole of the french territory with an infrastructure of data transmission sufficient to cope with a rapidly increasing demand, was initially oriented towards circuit switching).
That new technique (which however had already been confirmed by ARPANET), of a mesh network with packet switching nodes offered the following advantages :
(a) The possibility of rapid implementation by using standard computing hardware, either already in existence or announced for the very near future.
(b) Sharing time on a means of transmission is well adapted to the bursty character of most computing communications and is economically advantageous.
(c) The possibility of using the "intelligence" of the switching nodes to overcome the diversity and incompatibility of the various pieces of hardware on the market : for example, conversions of code, of speed or procedure.
The decision to undertake the realization of an experimental network (RCP) was taken to answer the following double question :
Can the technique of packet switching be used in the environment of a national public network? And if so, in what form?
The success of the experiment led to the official announcement in 1973 of the national network TRANSPAC.
OUTLINE OF THE SERVICE OFFERED
The Market Aimed At By This Sort Of Network.
Two broad families of applications seem to be able to benefit more directly (without breaking too much with tradition) from the packet-switching technique.
(a) Dialogue between two processes (in the widest sense). Two typical examples of these are :
Conversation between a user at an interactive terminal and a process, in the context of a time sharing service offered by a computing center.
Conversation between a remote-batch station and the main computer. In this type of dialogue, the existence of a context which is constructed progressively gives meaning to the messages exchanged.
The analogy with a communication established in a telephonic sense is unavoidable.
(b) Transactional systems of the "question/reply" type, where each message contains all the information necessary for its comprehension, including the identification of both its sender and destination. These systems lead naturally to an analogy with a postal service.
The Most Important Factors In The Technical Decision.
If a public service is to be offered a precisely defined quality of service must be maintained. This quality of service is observed by the client as a set of parameters.
Among the principal ones, we note :
1) Permanence of the service.
2) Accessibility
3) Security in use.
(Protective measures should be of the strongest, since wrong or even malevolent use of the network should remain invisible for others users. Similarly, the inevitable failures of certain elements of the system should not jeopardize the secrecy of information, the effective charging for the service offered or the other parameters).
4) Data transfer rates offered, and the tolerances allowed in their fluctuation.
5) Transmission delays and the associated tolerances.
6) The residual error rate in the transmitted data.
It is relatively easy to draw up a qualitative list, but the problem becomes more complex when we look at the quantitative side.
In fact, the needs are relatively unknown, varying from one application to another and evolving rapidly in time.
The aim of the technician is not to fix these parameters, but to supply the means to control them, to allow them to evolve, and to evaluate precisely the investment necessary to obtain Such and such a value for such and such parameter
The only way to achieve this result is to be able to associate the values of the parameters with the material resources used. Thus, the specifications concerning the quality of the service are almost of a political nature and the operator of the service can define them with full knowledge of what he is doing, and improve them according to the evolution of techniques and of the demand.
In particular, the network operator should not be influenced in his choice be ill-explained phenomena of sudden deteriorations of performance beyond a certain load which would force him to make his network oversized. On the contrary, the network should keep its maximum throughput when the transport capacity is saturated.
Choice Of The Virtual Circuit As The Basic Service.
Two quite radically different solutions were possible :
(a) A basic service using an exchange of postal-type messages, which were later given the name datagram. The main characteristic of a datagram is to explicitely contain the address of the sender and that of the addressee.
The concept of communication, of which the usefulness remained obvious, would have been constructed as a higher level protocol using the basic service and implemented on the user's equipment (a Cyclades-type transfer station).
(b) A basic service directly constituted by
virtual circuits (V.C). A virtual circuit appears to the user much like a point to point actual circuit. It enables two users to exchange sequences of messages according to a normalized link control procedure.
The main features of virtual circuits are :
- Full duplex operation.
- End to end preservation of the sequential order of data transmitted.
- Flow control.
- Upper bound for residual error rate.
Two types of virtual circuits may be thought of :
- Permanent V.C. playing a role similar to that of leased lines
- Switched V.C., or virtual call, set up for the duration of the communication.
A fundamental parameter attached to a virtual circuit is its throughput class, i.e. the data transfer rates that can be offered to the users once the virtual circuit is set up.
The RCP project being at its inception relatively modest, the solution consisting of experimenting on the two basic services by making them coexist, could not be considered.
During 1972, some very interesting discussions between the technicians of the RCP project and those of the Cyclades project helped considerably in specifying the "virtual circuit" service.
The solution finally decided on for RCP was not only to offer the virtual circuit as the basic service to the external users, but to use this concept for its own internal use.
While in other networks offering that service the virtual circuit is achieved by an end-to-end protocol between the nodes to which the users are connected, in the RCP network a path is chosen at the establishment of the virtual circuit (RCP only handles switched virtual circuits). This path set up by updating information in each node traversed is conserved until the virtual circuit is cleared.
This choice is principally justified by the following advantages : At any moment, a node "knows" all the virtual circuits which traverse it or start or end at it, with their characteristics (especially the throughput class), and consequently knows the maximum demands on resources which may occur either at the node level (store and CPU Time) or at the line level (data transmission rate).
There are three types of consequences of this total control of resources :
(a) Resource allocation becomes a political choice for the operator. For example, a strict allocation, refusing communication as soon as the resources are theoretically saturated, allows the operator to offer guarantees of flow and of response. On the other hand "overallocation" such that the resources theoretically offered are greater by x% than the existing potential, produces a degradation of the service whose limit is calculable.
This degradation becomes less probable as the dimensions of the network increase, and the number of virtual circuit grows.
It is then still possible to guarantee an average service and also a minimal service.
(b) The knowledge of the resources in use at every point in the network gives simple and accurate criteria for the choice of a path at the time of set-up of the virtual circuit.
(c) Advance reservation of resources protects the network against possible failures occurring at an external user's level or in an internal element. In fact, an element that fails can only saturate, in a "healthy" element, the resources reserved for their interaction : only the virtual circuits passing through a failing element will be affected.
On the other hand, the possibility of dynamically routing each packet is abandoned. The loss of reliability which would seem to result necessarily at first sight is no longer obvious after careful consideration of the subject (cutting a line doesn't entail the breaking of a link and the average number of intermediate transit nodes is small anyway).
THE IDEA OF LINK AND SEPARATION OF LEVELS
The concept of link refers to a group of means of communication directly joining two separate elements of the network.
It consists, in general, of lines, modems, interfaces and the necessary software to give it the following characteristics :
A link acts like a black box with two ends. Data introduced at one end come out of the other end in the same order as they went in, with a small and known expectation of error (about 10-10). Moreover, the flow from the data source can be controlled by the box and conversely the flow from the box is controlled by the data consumer.
These are the properties expected from a transmission procedure at the frame level.
With this in mind, a frame-level procedure was put together in 1972. Experiments were performed on a 2-node RCP network at the end of that year. In parallel, the study of another offering the same services, but able to use several lines simultaneously, was undertaken. Though this multiline procedure was not on the RCP network, it remains the solution for the internal links in the TRANSPAC network.
The idea of a link as a black box being well-understood, it remained to make precise the interface, in particular the form in which the data are to be supplied and delivered by it.
Knowing on one hand that the black box must necessarily cut the information up into frames, and thus operate a system of delimiters which guarantees transparency; knowing on the other hand that the procedures external to the box would equally need a similar system of delimiters to work the multiplexing of virtual circuits over the link and the signalling, the natural decision was to provide the information as blocks which should come out unchanged at the other end.
The frames of the procedure thus become blocks surrounded by service information required for the operation of the procedure.
MANAGEMENT OF CHANNELS AND TRANSIT POINTS
Let's give two preliminary definitions :
The occurrence of a virtual circuit in a link is called a channel, and the occurrence of a virtual circuit in a node is called a transit point; more simply a virtual circuit results from the concatenation of channels by means of transit points.
The function remaining to be defined were thus :
- The multiplexing of channels to obtain a link.
- The operating procedure for a channel.
- The transit point.
Their relationships appear in the following diagram:
The unit of exchange between the two ends "CH" of a channel is the packet. The only interference between the frame level and the channel level in RCP is that the start of each block must coincide with the start of a packet.
This simple rule avoids the necessity of superposing a new and complex system for delimiting packets, which must be transparent to the user.
The three following problems were then to be solved :
- Flow control on the channel.
- Storage allocation at the transit points.
- Structure under which the data in transit would be saved before or after their transmission.
There was a great variety of possible solutions. Several of them were studied and some were simulated.
To begin with, solutions were sought which would permit dynamic storage allocation either at the arrival of the information or on request by the neighboring node when ready to transmit. The difficulty was the elimination of all risk of deadlock, while giving high priority to efficient use of the links (a substantial part of the cost of a network lies in the link as defined above) and at the same time to respect the throughput classes.
The final decision was to allocate the storage necessary to each transit point at the time of establishment of the virtual circuit as a function of the throughput class of that circuit, and to internally use small packets, at least for throughput classes corresponding to low throughputs.
The scheme arrived at in 1973 was the following:
1) The concept of packet does not exist at the level of the transit point. The data appear there only as a sequence of bytes placed in a circular buffer, one buffer for each direction of transmission. The size of each buffer is a function of the throughput class.
2) Multiplexing of the channels of a link is performed by circular inspection of the transit point connected to these channels. The time needed to sweep through all the active channels depends on the load on the link and also possibly on the load on the processor responsible for the inspection. If the bottleneck is at this level, then the buffers of the virtual circuits actually slowed down will be full when they are being inspected, and on condition that the flow control allows it (if it does not, the bottleneck will be further down the line) the throughput di of channel i for which the buffer contains ti octets will be greater than D×ti /Σtj where D is the useful throughput of the link. In consequence, the packets have a variable length. An arbitrary upper limit is fixed at 63 bytes in the RCP network.
3) The flow is controlled to the nearest byte. One end of the channel is kept informed of the number of available places in the "downstream" transit point by "ready to receive" messages.
Thus any packet entrusted to the link is sure to find enough room for it at the next stage in its journey, and its content can be forgotten by the transit point as soon as it has been passed to the frame level.
4) The number of packets in a frame is only limited by the maximum length of a block, which is a parameter of the link. The merit of this system is to keep a reasonable productivity for the link when the packets are short, and all the more so in that the number of service bytes necessary for the separation of the packets and for the operation of the channel procedure is smaller (two bytes in the case of RCP).
SET UP AND CLEARING VIRTUAL CIRCUITS
The schemes established in 1972 for transmitting signalling do not differ from the now classical propositions of end-to-end confirmation of the set up of a circuit and local confirmation of its clearing. However, the problem of flow control of the signalling messages had found a rather particular solution (later abandoned in the specification of TRANSPAC) :
A special channel (channel zero) was reserved in each link for the transmission of messages relative to the operation of the virtual circuits.
The rhythm of exchange of signalling was thus limited by the throughput class of channel zero. To be consistent, the throughput class being determined by buffering capabilities of the transit point, the programs dealing with the virtual circuit management were connected to channel zero by a transit point. A drawback of this system came from the fact that on the other side of the transit point the packet separation had been removed and a system of delimiters to separate signalling messages had to be recreated.
It became clear later that this protection was unnecessary :
A commutator is constrained to deal only with correct signalling, and since correct signalling possesses a dialogue structure it is impossible to overwhelm a commutator via a link with signalling information.
Only calling messages necessitate an immediate mobilization of resources in the form of input buffers. If need be an excellent protection car be guaranteed by a simple rule of the form "no more than 'n' calling messages may remain unanswered on a link".
THE STRUCTURING OF DATA TRANSMITTED ON VIRTUAL CIRCUITS
In 1974, when the network was beginning to work along the lines which have just been explained a problem, neglected until then, came to the surface.
For different reasons (management of protocols, "re-awakening" of processes waiting for the completion of some information), it became clear that two computers conversing over a virtual circuit would have their task simplified if the network offered them a simple mean of structuring to their own convenience, the data being exchanged in the form of messages of arbitrary lengths.
The transit point of the RCP node had only been designed to transmit unlimited sequences of bytes and unbuffered signalling information which must comply with the rule "There can only exist one such signalling packet which is not acknowledged on a channel at a time".
Building a message separation mechanism with this simple tool led to the following scheme.
To force message separation, the sending end of the channel transmits a special separator packet called an "M"-packet and then waits for a special "P"-packet in the opposite direction before resuming data transmission.
At the other end, when receiving an "M"-packet, the packet-receiving procedure will wait until the related circular data buffer becomes empty and only then will send back a "P"-packet and forward a "M"-packet. See next diagram.
One can see that for each message separation transmitted the channel is inoperable at least during two transmit-frame times. This can be a source of inefficiency for RCP when handling short messages mainly in the case of single channel link such as a link to a synchronous terminal. On the other hand, on a link handling several channels, the silences on a channel are recuperated by the others.
THE LESSON OF EXPERIENCE
Most of the options in RCP were carried over to the first specifications of TRANSPAC :
The principle of virtual circuits and their operation.
The operating procedure of a line at the frame
The channel level (see above) however was not satisfactory. In fact, given the need to structure and "label" the data transmitted by a virtual circuit, it was not possible to take them into account at the byte level; the solution was to regroup the bytes into larger blocks to which the necessary labelling bytes would be added (of the sort : last part of a message; information of level 0,1).
The conversion of blocks into packets and vice-versa needing to be efficient, the decision was taken to choose packet sizes as powers of two. The length of a packet remained constant on a channel at least for the duration of a communication. Thus, any packet which do not have the local maximum data field length is ipso facto the last of a message. Thus the unit used for flow control logically became the packet.
CONCLUSION
The RCP network had thus amongst other merits that of providing a solid experimental base to support the proposition of the French Administration of the PTT in the domain of packet-switching and in particular in the definition of the "virtual circuit" service.
Further, it continues to play its role as a test bed for users wishing to test out the impact of this technique on their applications.
Finally, it allows the pinpointing of the problems facing the potential operator of this type of network.
REFERENCES
A. Bache : received the degree of Engineer in electrotechnology from the Ecole Nationale Superieure d'Informatique, d'Electronique, d'Electrotechnique et d'Hydraulique de Toulouse, France, in 1961. From 1963 to 1964, he worked on reliability measures for an electronic component firm; in 1965, he joined the Centre National d'Etude des Télécommunications where he gained experience in computer software engineering (mainly on compilers, operating systems and real time systems). In 1971, he was the software project manager for the first French experiment on packet switching networks (RCP). In 1973, he came to the CCETT, Rennes, to develop a new release of the RCP software and to participate in the specifications of TRANSPAC and other related teleprocessing problems.
Y.A. Matras : began his professional life in 1966 at the Computing Center of the French Atomic Energy Commission. He taught computer science for two years at the Faculté des Sciences d'Orsay, near Paris, and spent three years as a visiting assistant professor of mathematics in two American Universities. He was hired in 1973 by the French PTT and appointed as Director of the Computing Center of the Centre Commun d'Etudes de Télévision et Télécommunications in Rennes, France. In early 1975, he became head of the Département RSI (Réseaux de Systèmes Informatiques) in the same organization. Mr Matras has a PhD (Doctorat ès Sciences) in mathematics from the University of Paris.