MEMORANDUM RM- 3097-PR AUGUST 1964 ON DISTRIBUTED COMMUNICATIONS v HISTORY ALTERNATIVE APPROACHES AND COMPARISONS Paul Baran PREPARED FOR UNITED STATES AIR FORCE PROJECT RAND 74c SANTA MONICA - CALIFORNIA MEMORANDUM RM- 3097 AUGUST 1964 ON DISTRIBUTED COMMUNICATIONS V HISTORY ALTERNATIVE APPROACHES AND COMPARISONS Paul Baran This research is Sponsored by the United States Air Force under Project tract No AF monitored by the Directorate of Development Plans Deputy Chief of Staff Research and Development Hq USAF Views or conclusions contained in this Memorandum should not be interpreted as representing the of cial opinion or policy of the United States Air Force DDC AVAILABILITY NOTICE Quali ed requesters may obtain copies of this report from the Defense Documentation Center DDC 71 21 II D omwm 1700 MAIN ST SANTA MONICA CALIFORNIA I 0400 Copyright 1964 THE RAND CORPORATION PREFACE This Memorandum is one in a series of eleven RAND Memoranda detailing the Distributed Adaptive Message Block Network a proposed digital data communications system based on a distributed network concept as presented in Vol I in the series Various other items in the series deal with specific features of the concept results of experimental modelings engineering design considerations and background and future implications The series entitled 0n Distributed Communications is a part of The RAND Corporation's continuing program of research under U S Air Force Project RAND and is related to research in the field of command and control and in governmental and military planning and policy making The present Memorandum the fifth in the series is primarily a background paper acknowledging the efforts of people in many fields working toward the development of large communications systems where system reliability and survivability are mandatory As these requirements be come increasingly stringent we are forced to consider new and more complicated systems than we might otherwise prefer In a very short period of time--within the past decade--the research effort devoted to these ends has de- veloped from analyses of how a mechanical mouse might find his way out of a maze to suggestions of the design of an all-electronic world-wide communications system Because this is a new field of study its terminology has been borrowed from different specialities and lacks A list of all items in the series is found on p 49 iv_ consistency This Memorandum should be useful to one wishing to trace some of the related research efforts focusing upon differences and their definitions It should also be of interest to military planners in aiding them to understand the subtle differences between several systems all called distributed but which exhibit com- pletely different properties This Memorandum forms a bridge between the previous items in the series concerned with the system concept and early modeling studies and the remaining volumes which detail the actual design and implementation of a network of the type proposed SUMMARY This Memorandum describes some of the System design alternatives that delineate the proposed Distributed Adap- tive Message Block Network from earlier distributed Systems The discussion is restricted to Systems using identical local switching policies at each switching node and which do not rely on a single or a small hierarchy of critical routing control centers A brief history of the develoPment of some sample distributed networks is given with emphasis on the development of heuristic routing doctrines able to find best surviving paths in a heavily damaged network The term distributed network is often used as a generic term encompassing different systems These sys tems while appearing superficially identical have markedly different properties equipment and survivability characteristics Survivability is shown to depend upon the flexibility of switching with the limit of switching flexibility being defined as perfect switching These differences of flexibility of switching are often not fully appreciated One cannot look at a communications network and necessarily predict survivability properties Several described example systems are categorized for comparison to aid in evaluating proposed systems and in new ones vii- CONTENTS PREFACE SUMMARY Section I INTRODUCTION I II THE DISTRIBUTED NETWORK CONCEPT 5 Definition of Distributed Network 5 Definition of Perfect Switching 8 Heuristic Learning 10 Store-and-Forward Versus Circuit Switching 11 Need for Switching 11 EARLY HISTORY 16 Mouse in a Maze 16 Barnstable 16 Voice Relay 19 IV SPECIFIC HARDWARE PROPOSALS 20 Time-of-Arrival 20 Random Repeated Relay 23 Directional Relay 25 Flooding 30 Saturation Signaling 33 Two-Phase Routing 37 Hot-Potato Routing 38 Tessellated Network 39 V CONCLUSIONS 41 Appendix A SUMMARY CHARTS 43 B THE SYSTEM 45 LIST OF PUBLICATIONS IN THE SERIES 49 I INTRODUCTION The term distributed networks is commonly used as a broad generic term encompassing a number of communica- tions systems with different properties A brief history of the development of distributed networks is provided in the following sections with emphasis on the develop- ment of heuristic routing doctrines that seek perfect switching those able to find best surviving paths in a heavily damaged network The discussion is restricted to those systems using locally implemented switching rules and which do not need a single highly critical control center Such systems have different properties require dif ferent equipment and exhibit different survivability characteristics But they can be factored into categories for comparison The work of at least six separate disciplines is germane but inasmuch as the members of these separate disciplines reside in different communities of interest the all too common problem of a lack of communication be- tween one another is quite noticeable And when there is an interchange of ideas the words used take on different meanings to the representatives of the various fields of study The term distributed networks is one of these very ambiguous entities Sometimes it is simply a mean- ingless 0k word used to Spice up hardware proposal brochures To others the meaning is exact and narrow One writer has defined distributed switching as any switching medium noncollocated with the communications subscriber another has implied that collocation is almost a necessary condition in a distributed system Though these two definitions contain explicit delineations they are at opposite ends of a Spectrum In our usage collocation has no bearing whatsoever in determining whether or not a system is distributed It might be helpful to enumerate the fields concerned in these studies Distributed networks of one sort or another are of interest to 1 Those concerned with artificial intelligence 2 Those concerned with communications within organisms and organizations 3 Mathematicians working with Optimization of flow in networks I 4 Mathematicians using dynamic programming to optimize incompletely understood and changing systems 5 Those connected with civilian common carrier tele- phone plant switching 6 Military systems planners especially those dis- satisfied with existing communications network techniques The present Memorandum is written primarily from the view- point of the latter group And while significant con- tributions have come forth from each and every one of the above listed disciplines the present work has taken its examples principally from projects concerned with study of military systems Just as there are various definitions of distributed networks there are many ways to build such networks in fact there are probably as many ways of building them as there are designers Therefore several properties have been factored out and our attention will be focused on distributed networks which possess these characteristics 1 A certain degree of routing flexibility 2 Capability for implementation by real-world hard- ware at a reasonable price 3 Compatibility with existing input devices 4 Survivability in an unfriendly environment 5 Capacity for orderly system growth 6 Operational routine of sufficient simplicity-- that is one that can be maintained by reasonably intelligent personnel Design of such systems tends to be quite complex and the systems themselves are inherently intolerant of poor design due to the practical difficulties encountered in preventing or minimizing propagation of system malfunctions But the potential promise of a high degree of survivability and the potential use of low-reliability elements makes the labor of a complex design The switching criteria will receive considerable attention since survivability is a function of switching flexibility The resulting detailed insPections of system proposals are necessary to accurately determine surviv ability properties The following section is devoted to a presentation of the distributed network concept and its characteristics while Sections and IV detail some of the history of distributed networks both in theoretical studies and ex- periments and in hardware implementation preposals To those interested in the evolution of modern systems and proposed systems Appendix A contains several charts which summarize the stages of this develoPment using Specific proposals as signposts along the evolutionary path _ II THE DISTRIBUTED NETWORK CONCEPT DEFINITION OF In it is suggested that the term distributed network is best used to delineate those communications networks based on connecting each station to all adjacent stations rather than to just a few switching points as in a centralized network It is difficult to limit the use of the term to describe a single network since it is fre- quently used in this broader meaning--as delineating that portion of the spectrum of networks having a more decen- tralized configuration than those which exist as a single inseparable entity Various modes of System connectivity--i e configura- tions--are depicted in Fig 1 Figure l-a shows a gen tralized communications network Fig l-b a decentralized network and Fig lc a distributed network Figure l-d is a series of points along a continuum representing more accurately how Figs l-a l-b and l-c delineate zones on a broad spectrum of possible system designs where the boundaries between zones are fuzzy To appreciate how fuzzy these boundaries can be con- sider Fig 2 One very large communications network in existence today is called the spider web When this network is viewed in a schematic one obtains the illusion of Fig Z-a However when only allowable paths between is an abbreviation for the series title 93 Distributed Communications The numeral refers to the specific volume in the series A list of all items in the series is found on p 49 Centralized Av Decentralized 4 Distributed 0 Single critical node systems a r Alternate Diversity-of Destruction center assignment of small approaches techniques set of nodes required for destruction of network Fig 1-The Spectrum of System Circuit- switched distributed networks Connectivity 'Perfect switching Infinite size array Bandwidth of links data rate required Complete flexibility of channel use In '2 his o 99 4' Fig 2--The Spider Web Communications nodes are examined one finds the number of such possible paths highly limited so much so in fact that it would appear that the network is formed by a superposition of the separate overlay networks of Fig 2-b and Fig 2-c It can be seen that there is little if any connection of the warp and the woof of the spider web While Fig 2 is an exaggeration of such actual networks Fig 3 is a somewhat less strained example of this phenomenon the separate non-switchable links are shown on maps as in Fig 3 b Thus one must be careful in examining a graph of a communications network in considering the limitations of signal paths at the nodes To do otherwise would lead to confusing a network with nil survivability with a highly connected and more survivable one having full switching capability at all nodes In the systems being considered networks in which a single point is entrusted with the entire task of trans mission path selection are also avoided Such a central control node forms a single very attractive target in the thermonuclear era We are thus interested Specifically in communication switching node doctrines that are able to produce efficient traffic routing using local control only and without need for a central control point A second payoff for use of local control is that it avoids telling a possible enemy precisely which links are not destroyed a probable occur rence should it be necessary to transfer network station and link information to a remote control point DEFINITION OF PERFECT SWITCHING Perfect switching is defined as that form of f view of a proposed distributed network Side view of same network Fig 3--The Spider Web Projected on a Rectilinear Grid -10- switching that permits a connection to be established be- tween any two points in a network composed of short links that connect switching nodes Each link terminates at two and only two switching nodes and any number of tandem links may be used to form the connection The channel capacity of all links and nodes permits all such possible connections to exist simultaneously This implies no blocking establishment of any connection between two points shall not preclude connection between any two other points HEURISTIC LEARNING The underlying concept of distributed networks is as old as man Any interconnected grid of paths or roads may be considered as being a distributed network When one drives to work over a distributed or grid road system and encounters a potential delay it is possible to turn off bypassing the traffic jam or obstruction Thus the actual route taken depends not only upon a predetermined route but also upon the happenstance of encountering necessary detours which take us off the preferred shortest path In spite of this uncertainty and regardless of the number of detours we almost always manage to get to work On some mornings when we have a little extra time we may chance to try a route that we have never taken be- fore If we find that this new route is quicker because of less traffic than our old route we will probably take this newer route in the future By this process we learn in a relatively short time the quickest route between home and work We may say that we have used a heuristic pro- cess to learn a best path in a network -11- While this Memorandum examines different types of distributed communication networks we shall emphasize the development of those networks that use heuristic route- learning STORE-AND-FORWARD VERSUS CIRCUIT SWITCHING Networks are described as being either of the store-and- forward type or the circuit switched type If the switches at the switching nodes of a network are semi-permanently engaged so that a real-time channel exists between the calling and called parties circuit switching is being used If messages are relayed from a source station via relay stations and stored at each relay station until a circuit is available to the next relay station as in a telegraph system store-and forward switching is being utilized The differentiation between the two categories store-and-forward switching and circuit switching is not always precise For example present-day telephone switch- ing practice is called circuit switching yet it makes use of a store and-forward technique to relay dial pulses from switching center to switching center When a call is placed from New to Los Angeles store-and-forward is used to establish the switching connection After the connection is established circuit switching commences Thus we must exercise caution in the interpretation of these differentiating terms NEED FOR SWITCHING Figure 4-a shows three stations A B and C that are to communicate with one another Three bi-directional links are required In Fig 4-b six stations A B C D Number of Links L Fig J 500 000 400 000 300 000 200 000 100 000 -12- NIZ 200 #00 600 800 1000 Number of Terminal Stations 4--Number of Links as a Function of Number of Terminal Stations The Necessity for Switching in a Communications Network -13- E and F are to communicate with one another Fig 4 c plots the number of links required as a function of the number of terminal stations in a network in which each station must be able to communicate with every other station in the network and where no switches are allowed The number of links required by the network is where is the number of terminal stations Thus the number of links in this communication network will increase roughly as the square of the number of stations in the network To keep the number of links in the network within reason as network size increases we are forced to the expedient of Fig 5 In Fig S-a we see three links connecting three communica tions stations but in Fig 5-b we add a switching center W to connect A to or to C as needed If A is Speaking to B then there is no need for a channel between A and C since A is already busy Figure 5-c shows six stations each communicating with one another If we imagine the links of Fig 5-c as rubber bands the links can be bundled in any manner without upsetting the basic topography of Fig 5-c We can visualize all the stations being connected to a single node as in Fig 5-d or alternatively we can connect the stations to the two separate switching nodes and Z Figure 5-f shows 12 stations interconnected to one another One can visualize the large number of possible groupings of these rubber-band links such as in Figures S-g and 5-h In the past much work has been done to pick that net- work topology that most economically connects stations or groups channels in such a manner by applying switching at Three terminal station network -14- Six-terminal- Twelve-terminals station network stntion network Fig 5-Use of Intermediate Switching Stations -15- the nodes It is not necessary to always have as many separate channels to connect switching stations to S for example as there are link paths in Fig 5-f At any one time very few of the subscribers in the network will be talking If there were an overload between switching station and S for instance then by proper design of the switching centers and transmission characteristics of the links an alternate path might be found from the eventual and station When- ever it is necessary to have a large number of stations communicate among a large number of potential addressees it is a practical necessity to use some form of switching There is always a very wide variety of potential groupings and possible network configurations The shape and com- plexity of the resulting network is very much dependent upon the economies one wishes to make in circuit groupings The choice of these groupings in turn depends upon the statistics of the expected traffic If the traffic sta- tistics are known very accurately large savings in cost of selection of routes and assignment of channels can be realized However if it is necessary to build a military network whose configuration and demands are subject to drastic changes with little advance notice then a network whose design is based on peace-time statistics may be ex- pected to block or overload and prevent fulfillment of the original goal--i e permitting any subscriber to talk to any other subscriber -16- EARLY HISTORY MOUSE IN A MAZE In 1952 Claude Shannon demonstrated a machine which was a model of a mouse able to find its way out of a maze see Figs 6 and 7 Shannon showed that a relatively simple routing policy could be used to have the mouse ex- amine the entire maze to find the piece of cheese Shannon's mouse was not a distributed system as his controls were centralized but he did use a heuristic routing doctrine There was no guarantee that his mouse would ever traverse the entire maze but the probability that it would was near unity BARNSTABLE In the Final Report of MIT's Project Barnstable another mouse-in-a-maze technique was suggested whereby a mouse could find its way out of a maze by marking each maze function point node traversed with a chalk mark This technique appears to have the limitation that a message must store within itself the identity of all switch- ing nodes traversed Alternatively each switching node would have to store a long history of recent traffic In such a case it would be necessary to compare each new message with previously encountered traffic to determine which paths have already been tried Eighth Conference of the Josiah Macy Jr Foundation New York 1W Barnstable Summer Study Study of Communications Theory Applied to Military Communications Systems U MIT Research Laboratory for Electronics Cambridge Massachusetts October 30 1958 Confidential -17- Fig 6--Shannon's 1952 Maze mama IL - nu FLEXIBLE CABLE To CARRIAGE CARRIAGK WHEELS cannmot HORTH-SWTH cast-wen 2 CENTERING SWIYCH or EAST - sm rcuts MAI humans smsmo mus roa GOAL 9 INDICATINC HOV couurtn I 0 0 STEP caught 0 MANUAL 51w On STEP 3 57 OUT gut- ON SWITCH MANUAL uo'ro CONTROLS c F Dunn-rug Fig 7--Shannon's Electrical Mouse Figure courtesy of Shannon Claude Maze Solving Machines in Cybernetics Heinz von Foerster Josiah Macy Jr Foundation New York 1952 -19- VOICE RELAY In 1955 Frank Collbohm of RAND suggested that traffic could be relayed from broadcast station to broadcast sta- tion to provide an emergency means for transmitting extremely urgent messages The routing was to be handled by human judgment -20- IV SPECIFIC HARDWARE PROPOSALS The following Specific system descriptions are not intended to imply an exhaustive survey of distributed sys- tems only enough cases are given to provide an introduc- tion to the general subject TIME-OF-ARIVAL In 1957 Frank Yates of the Hughes Aircraft Company described in engineering detail a time- of-arrival procedure to connect a group of stations to gether into a circuit-switched tree structure Each node is connected via relay points to the origination station via the shortest possible path In Fig 8 origination station A is connected via links K E and H In Yates' method shown in Fig 9 a repet- itively available time slot is reserved for each station allowed to transmit new traffic During the initiation of each time slot all stations in the network listen over all their input lines to their neighbors The leading edge of the first signal to arrive at each node via the several input lines throws local switches to disconnect all input lines Figure 9 shows four digital signals racing to arrive via lines 1 2 3 and 4 The message arriving first came over line 3 Thus the switching node ignores later inputs from all stations other than from line 3 The signal from line 3 is amplified and sent outward on all connected outgoing lines This procedure is shown to produce Yates' goal of transmitting messages which flood the network and try all possible paths yet avoids the -21- Relay Points Switching Nodes Origination Station A-o Each station receiving messages from station A by the shortest possible path Fig 8--Yates 1957 Time-of-Arrival Flooding Message Flow Diagram -22- In the READY MODE Line 2 Line 3 Line 1 Transmits the first received signal line 2 Switching Node Line 3 Line 1 Line Line 1 Line 2 Line 3 Line 4 Time at at 5 Fig 9--Yates' 1957 Time-of Arrival Flooding Timing Diagram -23- ring-around the-rosy effect a defective route selection doctrine which allows tandem points which form a closed loop to be tried the result is identical to falling into a closed loop in an improper computer pro- gram -useful work ceases until the loop is broken In Yates' approach time slots must be assigned to every potential user 'If the potential user has nothing to transmit during his time slot this time is generally wasted Each transmitting station floods the entire net- work and so the system lends itself to simultaneous user- to-user communication between pairs of end users RANDOM REPEATED RELAY In early 1958 Jack Carne of The RAND Corporation suggested a random relay scheme designed for transmitting a small volume of critical data over a meteor-burst net- work see Fig 10 Carne's notions have not been described in any published document but Carne examined his scheme using pencil-and-paper Monte Carlo simulation to provide an indication of whether it would work or not The scheme uses memory at each node of the network to implement a store-and forward relay operation Long- range meteor-burst transmission radio pr0pagation occurs when a meteor trail is in a favorable point in space to cause reflection of a transmitted station radio beam to a ground station These links are fundamentally unreliable since favorably located meteor trails occur only on a random basis Carne's propagation rules were 1 Each node has sufficient storage to simultaneously store messages from all potential transmitting stations we -24- in operation Qircuit out of Operation Time- Assumed characteristics of meteor burst relay Message length 4 3 Serial number of message to Entire last message Storage table at each switching node Transmitter s Sequentially transmit all messages for all stations now held in memory continuously I Receivers Insert into memory in lieu of message addressed to station in memory Read input message lncrenent from receiver tuned i to i l to ith station modulo where is number of adjacent stations Does message have a latel serial number that one in memoryi Block diagram Fig 10--Carne's 1958 Meteor-Burst Relay -25- 2 Each message from each origination station carries a time-stamp or a serial number tag 3 Each station serially transmits the latest message it has received from each possible transmitting station 4 Each station receives data from several stations and sends to several stations 5 New traffic serves to flush out old traffic 6 A serial number appended to each standard-length message block provides a means for selecting newer traffic in preference to older traffic The original application envisioned for this doctrine had a low data rate requirement where the efficiency of a network utilization was not important DIRECTIONAL RELAY In 1959 Lt Colonel Todd Williams of the Rome Air Development Center proposed a circuit-switched system com- prising a linear grid array of microwave stations trans- mitting voice-bandwidth frequency-division channels Any array of stations in which each node is connected to its neighbors by four or fewer links planar networks can be drawn in the form of a rectangular grid for ease of analysis or description Williams recently graciously supplied the writer with a detailed description of his network switching doctrine and Sharla Boehm of RAND performed a simulation of this HI The equipment necessary to implement a meteor-burst system using this routing doctrine was examined in an un- published study written by the consulting engineering firm of Janskey and Bailey Washington for The RAND Corporation -25- network which compared it against distributed networks that were able to use perfect switching those that test all possible paths Williams' routing doctrine avoided the ring-around- the-rosy problem by the following procedures 1 All stations in the grid array are assigned a coordinate address comprising a column and a row number see Fig ll-a 2 The coordinates of the addressee station are sub- tracted from those of the calling station to determine the quadrant of the addressee station relative to the calling station see Fig ll-b 3 If addressee station is in quadrant I one can go east or north to reach the end destination if addressee station is in quadrant II one can go west or north to reach the end destination if addressee station is in quadrant 111 one can go west or south to reach the end destination if addressee is in quadrant IV one can go east or south to reach the end destination 4 The operation of each tandem mode is tested before the switch connection is locked up thereby avoid- ing defective links 5 Backing out upon encountering a dead end is al- lowed provided one remains in the same quadrant 6 After path is found then and only then are the circuit relays locked up Several assumptions were made in the RAND simulation of the Williams' network in order to compare it against the goal of perfect switching -27- away if 1 1 1 2 1 3 4 1 5 1 6 i T 2 1 2 2 2 3 c5 u 5 5 3 1 c 2 9'3 c 5 9 5 r 1 f'B q'q Designation of stations OEQJ U quadrant Quadrant II I 47 1 quadrant quadrant IV IN Determination of quadrant Fig 11 -Williams' 1959 Directional Relay -28- l A network array of 324 stations consisting of an 18 18 grid was used 2 The network had a uniform connectivity of redundancy level 2 3 There was infinite channel capacity for each switch- ing point and link 4 An infinite number of dr0ps to baseband was per- mitted 5 Only nodes were destroyed Because all surviving stations in a large group of adjacent surviving stations cannot always communicate with one another except in the case of perfect switching several different survivability criteria were used for comparison see Fig 12 Criterion I Perfect Switching --Curve I is the number of stations contained within the largest single group of surviving stations under the assumption of perfect switching This curve is included as a comparison reference Criterion II Williams' Switching --Curve II is the largest number of stations in the largest single group of surviving stations with which any single station was able to communicate Criterion Williams' Switching --Curve is the average number of stations in the largest single group of surviving stations with which any single station was able to communicate This demonstrates that al- though a station is a member of the largest single group it cannot communicate with all of the stations in the group see ODC-I Criterion IV Williams' Switching --Curve IV is the average number of stations with which the average station surviving or not was able to communicate NUMBER OF NODES 300 250 200 150 100 50 -29- 2 Perfect Switching No stations in largest surviving group Williams' Switching Largest in largest sur- viving group Williams' Switching Average in largest sur- viving group Williams' Switching Average for all 324 nodes1 0 SINGLE STATION PROBABILITY OF KILL Fig 12--Survivability of Williams' Switching Compared to Perfect Switching -30- There is a premium for being able to try all the path combinations possible under perfect switching--particu1ar1y in the event of heavy damage For example if in Fig ll-a stations and are destroyed it would be impossible to communicate with and because of the quadrant-crossing limitation used to prevent the ring around-the rosy effect Williams' directional relay method has one very strong factor to recommend it it is a relatively simple circuit- switched system able to handle voice This simplicity must be weighed against a less than full realization of what perfect switching offers in survivability As in any circuit switched system there will also be additional losses due to finite channel capacity of the links and number of tandem links that can be used FLOODING In 1959 the writer while employed at the Hughes Aircraft Company described a switching scheme in a pro- posal submitted to Boeing The peculiar requirement of the application called for a very-low-data-rate system requiring the path-seeking ability of the Yates' system coupled with freedom from the possibility of the network being seized by either equipment failure or by intentional acts The system uses what might be called a flooding routing doctrine Distances and bit rates are such that it is possible to each station in the network to operate in step Each relay station receives messages from all adjacent stations simultaneously The -31- number of simultaneous messages received is as great as the number of links connecting each station All messages transmitted by a single message origination station are simultaneously examined at each node A decision is reached as to whether a correct message has been received and the single assumed correct message is sent out on all lines Logical apparatus for reaching this decision is contained at each node and operates as follows 1 2 3 4 A number called a hand-over number is affixed to each originated message This hand-over number tag provides a measure of the path length traversed by each message The hand-over number tag is incremented every time a message is relayed The hand-over numbers of all messages transmitted by each origination station are examined simul- taneously Those messages with the lowest hand- over number are assumed to be the most recent messages and are propagated while all other messages are dr0pped Two messages arriving simultaneously and bearing the same hand-over number but differing in message content are rejected to eliminate distorted mes sages Also rejected are those messages which have been sent by two separate stations both claiming to be the same station If two messages arrive by different directions and have the same path length they must match If they are dif ferent something is wrong and wrong messages are not prepagated However no valid messages will be lost because a verified valid message will arrive later by an alternative path- Messages bearing a hand-over number less than the predetermined minimum possible hand-over number are rejected and a trouble indication message sent- For example if two stations are a minimum of five links apart then it is clearly impossible for messages to be transmitted from one to the other with a hand-over number of less than five -32- 5 Messages having a hand-over number greater than a predetermined maximum value are assumed to be undesirably old and are rejected Under these selection criteria one and only one received message survives This latest assumed valid mes- sage is stored and held in storage until the proper trans- mission time frame occurs A sequential time frame is re- served for the consecutive transmission of a standard- length message from each possible orgination station The relay scheme is really a broadcasting system since each message is transmitted to all stations Hence it is called a flooding technique Its chief merit is that in the event of fraudulent signal intervention only a few stations in the network will receive the fraudulent message Undesired signals are generally suppressed at most nodal points in the network The System automatically uses its redundancy to provide automatic error correction If an independent error occurs in the text portion of the message it will be propagated only until the node is reached where comparison of messages bearing the same hand-over number takes place Such messages will then be rejected The limitations of this method of propagation include 1 Inability to rapidly relocate the positions of stations in the network because of the minimum- fixed-distance-between-nodes test 2 Suitability only for very low data rates 3 Requirement for local storage and relatively long time delays necessitated by reception of messages from several different directions Although flooding is perhaps somewhat more secure than other networks described it also makes least efficient use of the communications resource -33- Figure 13 is a detailed example of message propaga tion in this network Signals originate at Station 22 and are transmitted simulteneously to the north east south and west Messages arriving at Station 32 for example will bear a hand-over number of 0 The hand-over number is incremented and passed on to the next station No 42 Messages at Station 33 arrive from two different direc- tions from Station 23 bearing a hand-over number of l and from Station 32 also bearing a hand-over number 1 These two simultaneously arriving messages are compared If identical the common message is transmitted out in all four directions All stations other than those in the diagonally- shaded area Fig 13 will simultaneously with the same hand-over number receive messages from two or more links These messages must exactly match otherwise these messages will Egg be relayed If a fraudulent Station were to insert messages it could theoretically pretend it was Station 22 to those stations on the right hand side of the network However if a rule that a known minimum distance exists between any two stations is in- cluded then this counterfeiting would be credible only within the smaller dot-shaded area If the number of co- operating friendly stations is much greater than the number of fraudulent stations then even these few fraudulent -stations can be located or cut out of the network with little impairment of residual network performance SATURATION SIGNALING In 1959 Gunner Svala of the North Electric Company described a circuit-switching arrangement which he calls Zone of temporary seizure of Station22 messages by source 69 if the rule is used that messages from Station22 must have traversed minimum known distances ggy 7 n1 Station number at an Y5 Handover number from Station in so I I 7 if7 7 4% NW Zone of no verification of messages of Station22 22 Fig 13-Message Propagation -34- -35 - saturation signaling In this system high-speed sig- naling information is broadcast throughout the entire 'network When the end-party responds a circuit is estab- lished between the called end-party and the calling party and all the tentative searching connections are closed off In saturated signaling each node or switching center may be connected to adjacent neighbors in the canonical manner of the distributed network Each switching center is es- sentially a conventional switched toll telephone exchange but with the addition of a rapid access memory and a sequential line-scanning device The rapid access memory keeps a record of the telephone numbers of all local subscribers currently connected to the local switching center The rapid-scanning device sequen- tially examines all circuits trunks and lines connected to the switching center Basically the system uses a flooding technique in which the called number is transmitted throughout the net- work in a manner somewhat similar to Yates' method Ring around-the-rosy is prevented by each switching center asking the question Have I just received this called number The rapid-access memory at each node traversed is scanned until the called number is found At this time revertive signals are sent which lock up the circuit connection Figure 14 illustrates the propagation of signals in Svala's system Switching center A transmits the telephone number of the party being called to several adjacently connected stations B C and E Each of these centers examines its own local memory to see if the called station is a local one If not the called number is relayed to other switching centers -36- Fig 14--Propagation of Signals in Svala's Saturated Signaling -37- The saturated signaling system appears to be a form of perfect switching with the resulting high survivability expected from such systems There is of course an in- evitable set of problems found in any complex system of this sort What happens if many of the stations are destroyed Will there be blocking because the signaling is overloaded while waiting to time out How much time is Spent in signaling relative to active circuit usage These questions are most readily answered by a simulation and such simulation is being conducted by the North Electric Company under a feasibility study contract with the U S Army Research and Development Laboratories A key feature of this network is that it allows a user to move across the country and take his telephone number with him He has only to inform his last connected central office and his new one of the change of address TWO-PHASE ROUTING In 1960 John Bower in a patent disclosure entitled Logic for an Interconnected Net described in operational form only a communication system which would essentially operate in two sequential time phases During time phase A information at the nodes on the status of traffic loads at each station in the network is transmitted to all other nodes Each node contains memory to record the status thereby enabling it to determine the optimum direction for routing traffic to any given end station During a much longer time phase B useful traffic is sent based upon a flow pattern that correSponds to the most recent network status and loading measurements -33- HOT-POTATO ROUTING In 1960 the writer Suggested the use of a hot potato routing doctrine upon which to build a common-user all-digital communications network this system is described in detail in the other papers of this series All traffic is converted to digital signals and blocked into standardized- format packets of data Each packet of data or message block is rubber-stamped with all the signaling informa- tion needed by other stations to determine optimum routing of the message block The system has a set of properties that are markedly different than present-day networks Some are advantageous and others disadvantageous These are described in detail in ODC-XI Briefly some of the features include 1 Very efficient usage of time-shared digital links 2 A high upper limit on allowable data rates 3 Relative immunity to the effects of illicit intervention 4 Application of a future all-digital network com- munication requirement 5 Allows a reliable system to be built using low- cost and unreliable links The disadvantages of the hot-potato system include 1 It is fundamentally an all-digital system 2 It requires a more complex routing logic at the nodes than has ever been previously attempted In summary one pays the price of logical switching complexity but buys a set of unusual network properties -39- the network can handle digital data on an extremely short-term store-and-forward basis and the system appears to be able to handle real-time digital voice TESSELLATED NETWORK In 1961 Jack Craig of The RAND Corporation proposed a Tessellated Network This network was designed to meet the communications requirements of a specific task-- the air defense problem In this network each station transmits information to a small ring of adjacent stations The inherent broadband capability of a microwave link is utilized together with conventional frequency division multiplexing to provide a large number of separate voice bandwidth channels These channels are then so assigned that separate channels emanate from each station to ad- jacent stations Switching per se is not used Craig and Reed suggest that a modest amount of manual patching at each node can be used to restore communications between essentially adjacent stations after attack While this network makes inefficient use of a broadband channel by conventional communication practices since but few of the potential channels in the microwave link are in active use it should be pointed out that all distributed networks designed to withstand heavy attack are fundamentally in- efficient After attack the last surviving link of the redundant network might have to carry the entire network traffic Therefore one must start with a built-in excess Craig L J and I S Reed Overlapping Tessellated Communications Networks The RAND Corporation P-2359 July 5 1961 -40- capacity To build a network with merely enough capacity to handle the normal pre-attack load is to be certain of not having enough capacity after an attack While the tessellated network conceptually is the simplest of the networks proposed it appears to be of primary use in those cases where a station uSually needs only to speak to ad- jacent stations or stations only a few spans away If the tessellation is extended to too many remote stations the bandwidth number of channels required builds up tremendously and survivability decreases markedly due to the requirement for a greater number of tandem serial connections The survivability of a network using tessellation is highly dependent upon the span distance required given finite bandwidth link capacities If the Span distances are short with connection made only to adjacent stations the survivability of the network is excellent--resembling perfect switching But if the span distances between con- nected nodes are very great then the survivability will be closer to that of diversity of assignment -leaving much to be desired The efficacy of diversity of assignment dr0ps off markedly with increasing Span length see ODC-I -41- V CONCLUSIONS There is no single distributed network Many highly different systems can all be correctly called distributed and some of these can be categorized as using perfect switch ing Sufficient simulation has been run to predict the effects of overt destruction upon those using perfect switch- ing and those using only diversity-of-assignment techniques Generally the more perfect the switching the greater the survivability While those systems that use only diversity of assign- ment over large spanning distances are more vulnerable than those that use perfect switching the essentially simple diversity-of-assignment technique appears satisfactory when only short Spanning distances need to be considered The survivability of other switched networks that fall somewhere between these two known points of system per- formance cannot be determined without a Specific examination being made After many more such Specific intermediate Systems are examined in detail we will have more known points upon which to interpolate performance characteristics of other preposed systems under overt attack It will always be necessary though to examine each switched system separately to determine its ability to withstand sophisticated tampering -43- Appendix A SUMMARY CHARTS Table I BIBLIOGRAPHY OF SEVERAL DISTRIBUTED NETWORK ROUTING DOCTRINES Principal Published Date Designation Investigator Reference 1 1952 Mouse in a C Shannon C Shannon in Cybernetics H van Foerster Maze Editor Transactions of Eighth Conference Josiah Macy Jr Foundation New York 1952 p 173 2 1958 Barnstable D A Huffman Final Report Barnstable Summer Study C- 5- Shannon Study of Communications Theory Applied to Gllb t Military Communications Systems Con- 1 entia esearc a orator or e1E 111 er f'd 1 MIT Electronics Cambridge Massachusetts October 30 1958 p 117 3 1955 Voice Relay F R Collbohm F R Eldridge J B Carne H A Shapiro B Holfer Vulnerability of Landline Communications for SAC and ADC The RAND Corporation RM-1774 October 1 1956 p 67 4 1957 Time-of-Arrival F Yates Paul Baran and Frank Yates Non- Digital Data Link Transmission System Using Randomly Surviving Relay Points The RAND Corporation May 25 1960 5 1958 Random Repeated J Carne None Relay 6 1959 Directional T G Williams William 6 Todd National Survival Com- Relay munications System Rome Air Development Center Technical Memorandum RCU-TM-59-1 February 1959 7 1959 P Baran Paul Baran and Robert Hammerly Flooding Verified Point of Origin Digital Data Link Transmission System Using Randomly Surviving Relay Points The RAND Corporation May 25 1960 8 1959 Saturation G Svala Gunnar Svala Saturation Signalling and Signaling Switching System North Electric Company Galion Ohio 1959 9 1960 Two-Phase J Bower Patent disclosure 10 1960 Hot-Potato P Baran Current series Routing 11 1961 Tessellated L J Craig L J Craig and I S Reed Overlapping Network Tessellated Communications Networks The RAND Corporationer-2359 June 13 1961 COMPARISON OF PROPERTIES OF DIFFERENT DISTRIBUTED NETWORK Table II PROPOSALS SWITCHING DOCTRINE SERVICE OFFERED go ad l SUIQOJIMS uornoaras annex pause sannog go JaqmnN SUIPOOIJ SI Method Used to Purge Signaling Data 'xeg SoIeuV 3310A BoIeuv XIITISIXHTJ INHN TENNVHO IEDIBIQ Barnstable 5 Remember Path Taken r l 0 Path cannot pass same point more than twice - -4 CU Lu All 1911810 9290 1931810 Time-of-Arrival CS T-of A All Yes New traffic flushes out old Poor Fair Random Repeated Relay Traffic Age Very Manyi Yes Later serial number flushes out old traffic Fair Directional Relay CS Determine Quadrant Limited Number No No problems number of paths tested is limited Good Flooding Handover Number All Yes Lower handover number traffic flushes out old traffic Poor Saturated Signaling CS T of-A All Maximum time to make connection revertive signal knocks down un- desired connections Good Two-Phase Routing Traffic Statistics Broadcast Many No Network status information sent periodically Fair Good Hot Potato Routing Handover Number Almost All No Maximum allowable handover number Good Tessellated NetWork CS None Manual Patch Limited Number No No-write signaling used Fair aSignaling Yes bIf buffering is used Established Circuit No CS-Circuit Switching T-of A-Time of Arrival -45- Appendix THE SYSTEM In the Bell System Direct Distance Dialing net- work Fig 15 telephone number dial pulses are relayed to a Toll Center if there are no lines available to the desired end destination the call is routed to the next higher hierarchical level the Primary Center If again there are no free circuits to the end destination the call is relayed via a Sectional Center and thence to a Regional Center All Regional Centers in the United States are connected to each other Thus a telephone call starting from any place in the country will work its way up the hierarchical network seeking an end link to the called telephone via a Toll Primary Sectional or Regional Center then back down the chain to the end telephone Destruction of a small number of the upper echelon targets is magnified in the remainder of the communication network The hierarchical procedure increases the target value of upper echelons of the switch- ing network An ever increasing number of calls in the Direct Distance Dialing System are being transmitted from one Toll Center to an end Toll Center by direct trunk lines without requiring transmission through the upper echelons In telephone language these direct paths are called high usage groups The feasibility of being able to use such 'point-to-point non-switched high-usage circuit groups increases as the number of subscribers using the long distance telephone plant increases REGIONAL CENTER CALLING AREA 1 SECTION AL CENTER PRIMARY CENTER END OFFICE I Numbers in indicate order of choice of route at each center 2 Arrows from a center indicate trunk groups to other lower rank centers 2 that home on it Omitted in right-hand chain Fig 15-DirectlDistance Dialing Hierarchy CALLED AREA 2 -46- -47- Each of the links shown in Fig 16 is made up of channels following separate paths or using diversity of Iassignment see ODC-I While determination of the vulnerability of switching will depend upon the actual numbers of options tested at each switching center it is found in practice that very few of the large set of all possible connections existing are ever tried as alternate routing is designed primarily to effect more economical handling of traffic Figure 16 shows that in practice most connections are established by the use of only a few tandemly connected links Therefore it appears reasonable to assume that the survivability curves for diversity of assignment may be indicative of network performance Truitt C J Traffic Engineering Techniques for Determining Trunk Requirements In Alternate Routing Trunk Networks The Bell System Technical Journal Vol 33 March 1954 pp 277-304 Probability -480 01 003 0 001 0 0001 0 00001 Number of Intermediate Links Fig 16--Probability that or More Links will be Required to Complete a Toll Ca11 Courtesy Transmission Systems 2d ed Bell Telephone Laboratories New York 1958 -49- ON DISTRIBUTED COMMUNICATIONS List of Publications in the Series I Introduction to Distributed Communications Networks Paul Baran Introduces the system concept and outlines the requirements for and design considerations of the distributed digital data communications net- work Considers especially the use of redundancy as a means of withstanding heavy enemy attacks A general understanding of the proposal may be obtained by reading this volume and Vol XI II Digital Simulation of Hot-Potato Routing in a Broadband Distributed Communications Network Sharla P Boehm and Paul Baran Describes a computer simulation of the message routing scheme proposed The basic routing doctrine permitted a network to suffer a large number of breaks then reconstitute itself by rapidly relearning to make best use of the surviving links Determination of in a Distributed Network J W Smith RM-3578-PR Continues model simulation reported in Vol II The program was rewritten in a more powerful computer language allowing examination of larger networks Modification of the routing doctrine by intermittently reducing the input data rate of local traffic reduced to a low level the number of message blocks taking excessively long paths The level was so low that a deterministic equation was required in lieu of Monte Carlo to examine the now rare event of a long message block path The results of both the simulation and the equation agreed in the area of overlapping validity -50- IV Priority Precedence and Overload Paul Baran RM-3638-PR The creation of dynamic or flexible priority and precedence structures within a communication system handling a mixture of traffic with dif- ferent data rate urgency and importance levels is discussed The goal chosen is optimum utiliza- tion of the communications resource within a seriously degraded and overloaded network V History Alternative Approaches and Comparisons Paul Baran RM-3097-PR A background paper acknowledging the efforts of peOple in many fields working toward the develop- ment of large communications systems where system reliability and survivability are mandatory A consideration of terminology is designed to ac- quaint the reader with the diverse sometimes conflicting definitions used The evolution of the distributed network is traced and a number of earlier hardware proposals are outlined VI Mini-Cost Microwave Paul Baran RM-3762-PR The technical feasibility of constructing an extremely low-cost all-digital X- or Ku-band microwave relay system operating at a multi- megabit per second data rate is examined The use of newly developed varactor multipliers permits the design of a miniature all-solid state microwave repeater powered by a thermo- electric converter burning L-P fuel VII Tentative Engineering Specifications and Preliminary Design for a High Data-Rate Distributed Network Switching Node Paul Baran RM-3763-PR High speed or hot-potato store-and-forward message block relaying forms the heart of the proposed information transmission system The Switching Nodes are the units in which the com- plex processing takes place The node is de- scribed in sufficient engineering detail to estimate the components required Timing calcu- lations together with a projected implementation -51- scheme provide a strong foundation for the belief that the construction and use of the node is practical The Multiplexing Station Paul Baran RM-3764-PR A description of the Multiplexing Stations which connect subscribers to the Switching Nodes The presentation is in engineering detail demonstrat- ing how the network will simultaneously process traffic from up to 1024 separate users sending a mixture of start-stop teletypewriter digital voice and other signals at various rates IX Security Secrecy and Tamper-Free Considerations Paul Baran Considers the security aSpects of a system of the type proposed in which secrecy is of paramount importance Describes the safeguards to be built into the network and evaluates the premise that the existence of Spies within the supposedly secure system must be anticipated Security provisions are based on the belief that protec- tion is best obtained by raising the price of espied information to a level which becomes ex- cessive The treatment of the subject is itself unclassified X Cost Estimate Paul Baran RM-3766-PR A detailed cost estimate for the entire proposed system based on an arbitrary network configura- tion of 400 Switching Nodes servicing 100 000 simultaneous users via 200 Multiplexing Stations Assuming a usable life of ten years all costs including operating costs are estimated at about $60 000 000 per year XI Summary Overview Paul Baran RM-3767-PR Summarizes the system proposal highlighting the more important features Considers the particular advantages of the distributed network and comments on disadvantages An outline is given of the manner in which future research aimed at an actual imple- mentation of the network might be conducted To- gether with the introductory volume it provides a general description of the entire system concept