IVIERIORANDUM AUGUST 1984 ON DISTRIBUTED COMMUNICATIONS II DIGITAL SIMULATION OF HOT-POTATO ROUTING IN A BROADBAND DISTRIBUTED COMMUNICATIONS NETWORK Sharla P Boehm and Paul Baran PREPARED FOR UNITED STATES AIR FORCE PROJECT RAND We Dec-9mm SANTA MONICA - CALIFORNIA MEMORANDUM RM- 3103-PR AUGUST 1964 ON DISTRIBUTED COMMUNICATIONS II DIGITAL SIMULATION OF HOT-POTATO ROUTING IN A BROADBAND DISTRIBUTED COMMUNICATIONS NETWORK Sharla P Boehm and Paul Baran This research is sponsored by the United States Air Force under Project tract No AF 49 638l-700 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 official 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 74c ll Deowm 1700 5 - SANTA MONICA - CALIIOINIA - no 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 second in the series describes preliminary computer simulation of a message routing scheme investigated as part of a study of ways of - reducing the vulnerability of command and control communica- tions networks This routing doctrine referred to as the hot potato switching doctrine differs from normal store-and-forward switching in that it permits an apparent real-time transmission of data even though it itself uses store and-forward techniques The purpose of the simulation was primarily to de termine whether the doctrine contained any unforeseen problems and to define first cut design parameters A A list of all items in the series is found on p 47 -iv- further simulation permitting faster Operating speeds and a larger array of nodes is reported in Vol in the series SUMMARY The small-memory stochastic hot potato routing scheme described in Vol I in this series has been simulated on the IBM 7090 computer using FORTRAN language The simu- lation has shown that an efficient store-and-forward routing doctrine can be performed in a distributed network using a relatively simple policy at each Switching Node The computer program simulated real-time operation of the network with a time factor of about 540 seconds of computer time to one second of real-time operation Network learning time was determined as a function of traffic volume redundancy of connection and maximum allowable handover number It was found that from a dead start a 49-node network can learn to route messages very effectively within about one second of scaled real-world time The traffic-handling capacity of the network was examined and it was found that loadings on the order of about 50 per cent of peak capacity were possible without excessively increasing the transmission path length or delay time The mean handover number path length for messages traveling through the network was studied as a function of maximum allowable handover number and of redundancy It was found that the handover number is quite in- sensitive to maximum allowable handover number and the greater the link redundancy the lower the mean handover number During the simulation it was found that a certain percentage of the messages were dropped when the handover number exceeded the allowable maximum This problem has been solved by J W Smith and is described in Vol which is a continuation of the work started in the present Memorandum With this exception no major difficulties were encountered It appears that the basic routing doctrine examined can permit a network to suffer a large number of breaks then quickly reconstitute itself by rapidly relearning to make optimum use of the surviving links -vii- CONTENTS PREFACE SUWARY I I I Section I INTRODUCTION 1 II THE SIMULATED NETWORK 4 Description 4 Purpose 5 The Routing Doctrine in the First Simulation 6 DESCRIPTION OF THE PROGRAM SUBROUTINES 7 MAIN I I 7 SETTA000000000000000 7 RANTIM MOVE SELINK 9 SHINOD PRINT and ERROR 10 DAMAGE 10 IV TIME SCALE AND SCALING FACTORS 11 V DETERMINATION OF LEARNING TIME 13 Traffic Volume 13 RadundaDCY Location The Learning Rate Constant 16 VI DETERMINATION OF TRAFFIC HANDLING CAPACITY VII DETERMINATION OF PATH LENGTH Traffic 22 Appendix A SAMPLE OUTPUT B PROGRAM LISTING LIST OF PUBLICATIONS IN THE SERIES 47 I INTRODUCTION This study examines a communications network which is comprised of an array of stations interconnected by links A dynamically changing routing doctrine is used such that if any paths exist between the iEh station and the jEll station the network will seek to route messages by the shortest such path Such a network routing doctrine pro- vides a very much higher degree of alternate routing capa- bility than other networks now in use As it is difficult to visualize in a straightforward analysis how such networks behave we have resorted to a Monte Carlo simulation Hypothetical messages are generated at many stations and transmitted to other stations using simple pre-arranged switching rules at each node From time to time parameters such as the number of messages per unit time are varied and the behavior of the network is observed The approach is like that of the who regards a human being as a black box he applies inputs and observes the outputs All traffic to be transmitted within the model is generated at the stations or nodes Traffic to be trans- mitted is first chopped into small blocks called Message Blocks or simply messages These messages are then re- layed from station to station through the network with each station acting as a small post office connected to ad- jacent post offices Messages will eventually arrive at the desired destination In the proposed system the transmission time and storage time at the nodes is so short that to the user there appears to be a direct link between the originating station and the end station In effect a slow digital stream of bits inserted into the i-Eh station has been stored in a buffer until enough bits are received to form the Message Block Each Message Block is whipped into the network and transmitted over high speed transmission links to finally emerge at the th receiving station At the th station the bit stream is reconstructed into its original slow digital-stream Each node starts with complete ignorance of the state of its neighbors whether its neighbors are alive or dead and which links exist and which do not With the routing doctrine used each node soon learns enough about its external environment to be able to operate independently creating a reasonably efficient overall switching flow The term efficient switching is used to describe the case where messages are transmitted over paths which approximate the shortest possible path be- tween the transmitting and receiving stations and allow high average throughput rates Messages are assumed to originate uniformly in the network at the early stage of the simulation The end destination stations are chosen at random but a message cannot have the same origin and destination Delays are assumed for transmission and processing time at each node and link In practice this would be done at a substation called the Multiplexing Station as described in CDC is an abbreviation of the series title On Distributed Communications the number following refers to the particu- lar volume within the series A list of all items in the series is found on p 47 A decision is made at each node as to the best non- busy link over which each Message Block shall be relayed Best is defined as the shortest measured path length from the desired end station Rather than wait for the best link to be free the second third etc best link that is not busy or down is taken If at a particular node or station several links of the node equally fulfill this requirement one is chosen at random In general the link chosen is the one that appears to be the next one on the shortest path to the end station This path choice is determined by an information tag affixed to each mes sage called a handover number Each station or node notes the handover number number of steps of each incoming message It keeps track of these numbers on a handover number table which it uses to determine which of its neighbors appears to be most directly connected with each originating station Later the node uses this recorded information to select the preferential link over which messages to each end station should be directed As links may be destroyed and other links may be repaired and as traffic loads vary throughout the net- work it is necessary to provide some means at the node for learning and forgetting the best direction in which to send messages going to any destination II THE SIMULATED NETWORK DESCRIPTION The size of the network simulated was limited by the amount of storage available in the IBM 7090 computer using FORTRAN A heavy storage requirement was dictated by the need for each simulated node or station to maintain a table of recorded handover numbers--the tag appended to each message indicating the number of times that message has been relayed For each node a table containing hand- over numbers to every other node via every one of up to a maximum of eight links is needed The choice of a maximum of eight links was made by limiting the simulation to networks with a redundancy level R of four or less defined as follows Station or node link link I 3-1 5 as R-Z Specifically the configurations considered were for redundancy levels of l 1 large array the number of links emerging from a node is equal to two times the redundancy level The network under con- sideration was limited to a seven-by seven array PURPOSE This simulation was written to examine and to test the properties of a network of a type which has never been built It was hoped that the choice of such hitherto un- Specified parameters as the maximum handover number and the allowable traffic volume could be narrowed Results vary decisively as these parameters change We sought first a reasonably good set of basic key parameters be- fore adding additional refinements necessary to simulate a real-world system Thus the simulation changed in midstream as modifications were made from time to time to improve the routing doctrine For example while tracing a message as it moved through the system it was found that certain conditions would cause two nodes to relay mes- sages in a ping-pong fashion VInstead of moving out into the system the message simply bounced back and forth between the two nodes This was straightened out by a modification to the switching rules before continuing subsequent runs A larger array of stations 11 11 has been simulated by J W Smith as described in THE ROUTING DOCTRINE IN THE FIRST SIMULATION The initial constraints were a Each node accepts new traffic messages if and only if open storageicapacity exists at the node b A from address and a handover number tag is appended to each message inserted into the network c Every time a message is relayed from one node to another the handover number is incremented by one d A table of the minimum handover number en- countered relative to each originating station over each link in the network is stored at each node e Before the simulation is started the entries on the tables of handover numbers are set to predetermined maximum values f Messages found in the network with a handover number exceeding a maximum allowable value are dropped On some runs the location the source and the desired end point of such dropped messages are output to facilitate isolation of trouble spots g Messages correctly delivered are erased On some runs the handover number station of origin and terminal or sink station are printed out for analysis h Messages are routed by examining the handover number table and choosing the outgoing non-busy line bearing the lowest handover number table entry i If all lines are busy a message waits at the node until one is free This has since been changed to prevent the all- lines-busy case from ever occurring the procedure is called choking and is described in detail in -IV DESCRIPTION OF THE PROGRAM SUBROUTINES The program consists of a set of subroutines written in FORTRAN As the program was constantly changed certain parts of the program listing in the Appendix are residuals from earlier runs MAIN MAIN reads the input and calls up most of the sub- routines in the basic program SETTAB SETTAB is used at the beginning of each run to establish an initial maximum handover number table for each link of each node The handover number from each node to every other node via all possible links is set to the value KMAX which is simply a starting value The border links of the network are set to IFIN 32 000 to keep messages within the chosen site network RANTIM RANTIM sets values of random-length time delays It has changed since the first draft of the program when it was thought necessary to maintain separate values for switching delays in the nodes and in the links However as it now seems possible to build hardware to switch all messages within an almost constant time interval see This section presumes familiarity with FORTRAN The reader who is not so conversant may wish to advance directly to Sec 11 - ODC-VII we have chosen to combine these delays into a single pipe filling and message-length combination delay As real-world networks have varying-length paths each separate transmission delay is chosen by use of a random number generator test per network run As each link in the system can send and receive simultaneously full duplex this subroutine sets the delay time on both legs of each link to the same value MOVE MDVE is the heart of the program It contains an iterative FORTRAN 100p to manage all of the message propagation actions of the system Snapshot printouts which indicate network status behavior are performed with- in this subroutine Each message in the network is tested to determine its location and whether sufficient propagation time has elapsed to change its status If at the time of examination the message is at a node and is free to move to an output link subroutine SELINK see below is called Similarly if the message is traveling down a link and exceeds the propagation time delay SELNOD see below is called into play NEW Subroutine NEW is used to generate messages If the message has either reached its desired terminal destina- tion or its maximum allowable handover number has been exceeded subroutine NEW is called to generate a new message Since we are simulating an array of 49 stations it was convenient to make the from address of a message exactly equal to the number of the message modulo 49 This explains why the number of messages in the system - at any one time in most of the runs is a multiple of 49 The to address of each message is chosen at random For example when a message from Node 3 has been delivered another message will start from Node 3 One set of trial runs was made with all messages starting from a central node while all other runs generated traffic uniformly at all nodes SELINK SELINK selects the link or path to be taken to con- vey each message through the network Each link is tested to see if it is usable The output link chosen is that link which is not busy and which has the lowest-value entry on the local handover number table SELNOD Subroutine SELNOD serves two purposes It checks to see if messages have arrived at end destinations and it updates the learning table Subroutine SELNOD checks the handover number and the destination of the message If either the maximum allowable handover number has been ex ceeded or the desired end destination has been reached a signal is set to call subroutine otherwise the handover number is merely increased by one Next the lowest previously-found entry in the handover table is compared to that of the handover number of the newly- arrived message Whichever is smaller replaces the former value on the handover table This permits the node to -10- determine the best directions for sending future traffic This minimum-value substitution is called perfect learn- ing as it provides a record of the shortest path a message 3393 took to arrive at the node In order to make the network insensitive to possible errors and to allow for rapid change of routing imperfect learning is used Imperfect learning includes weighting factors to allow for error failure of the network and repair of the network PRINT and ERROR These routines control the various forms of print outs needed to evaluate network performance DAMAGE Subroutine DAMAGE is used to destroy nodes in order to simulate failure or damage effects The basic DAMAGE subroutine can destroy nodes in a controlled random fashion where the percentage of nodes to be destroyed has been specified -11- IV TIME SCALE AND SCALING FACTORS The network is a highly parallel system in which separate simultaneous transactions are taking place as in a three-ring circus In order to simulate this net- work on a computer which is a pure serial device capable of processing only one event at a time it is necessary to examine each link and each node sequentially Perfect simulation of events can only be performed if the assumed sequential time intervals of examination are so short that not more than one interacting change of state takes place during any single time interval This approach of course is quite wasteful of computer time Fortunately it was found that good simulation could be performed with a very coarse grain size of time We have standardized upon this time unit as a standard time- frame All other times are scaled in terms of this basic value The following is a scaling of real-world times in time-frame units tf - 0 33 milliseconds 1 time-frame station processing delay thme variable from 0 to 0 66 ms 3 0 33 milliseconds average time-frame - pipe filling plus message-length time variable from 0 66 to 2 64 ms 2 to 8 time frames te - message length 0 66 ms 2 time frames The values assumed here are for links up to about 150 miles in length transmitting 1024-bit Message Blocks at a data rate of about 1 500 000 bits per second A period of 3000 time-frames is equivalent to one second -12- of real-world time Since it takes about nine minutes to simulate one second of real-world time the ratio between real-world time and simulation time is about 1 540 Each message is held at each node for a single time frame If a link is free the message may move after the count It takes from two to eight time-frame counts to move from one node to the next The random value within the limits of tP is re-chosen whenever a new network is defined the greater the value chosen the greater the geographical length of the assumed communication link -13- V DETERMINATION OF LEARNING TIME We define learning as the utilization of knowledge acquired by each node of the system as to the network status so as to best determine the link that lies on the shortest route to each end station If messages are routed over paths whose mean approach the shortest possible path we say the network has learned well A useful metric for evaluating learning is the total value of all entries in the handover number tables of all nodes This value is called the table total the lower the value the better the learning This learn- ing curve approaches a theoretical minimum with network use TRAFFIC VOLUME The network learns quickly as the volume of traffic inserted into the virgin network is increased and levels off as the capacity of the system is approached It can be seen in Fig 1 that starting off a new network with dummy traffic is desirable if the absolute shortest learning time is desired otherwise many links that may lie on short paths would never be tested In Fig 1 the maximum allowable handover number was set at 40 and the number of messages per unit time was varied With a small volume of message traffic initially the system took longer to learn as expected In Fig 2 it can be seen that the number of messages delivered per unit time increased with network load but leveled off at 60 per cent capacity providing an upper -14- An Estimator of Mean Path Length x 1000 SUMMATION 0F HANDOVER NUMBER TABLE ENTRIES Maximum allowable handover number 40 Redundancy 2 Maximum loadin for 2 168 LOADING PER CENT250- 200 1500 Time-Frames About 1 2 sec of Real-World Time 150 - Maximum Possible Loading 123 147 168 NUMBER OF MESSAGES IN SYSTEM Fig l--Learnin% as a Function of Traffic Volume rom a Cold Start -15- TRAFFIC DENSITY PERCENTAGE OF MAXIMUM POSSIBLE2000 11 2 12 9 131500 - Average Path Length I nag 1000- Mean Handover Number123 147 168 NUMBER OF SIMULTANEOUS MESSAGES PROCESSED BY NETWORK Based on 1500 Maximum time-frames handover about sec number 40 of real-world time Fig 2--Learning as a Function of Traffic Density -16- bound for system load-carrying capacity under the assumed loading conditions The mean handover number increased as the number of messages processed per unit time increased Figure 2 shows that the average path length did not in- crease sharply even up to 50 per cent loading The definition of the term capacity as used here refers to a comparison of the number of messages in the system times 100 divided by the number of links EDUNDANCY The rate of initial learning improved as the re- dundancy of the network was increased Keeping other factors constant twice as many messages could be de- livered per unit time for a network of redundancy level 4 as for one with 1 5 The slopes of Fig 3 indicate the overall learning rate LOCATION From a preliminary examination of the learning power relative to the location of a node it appears that the nodes on the border do the best see Fig 4 These nodes have fewer links to educate The most centralized nodes do next best as they have the most traffic The inter mediate zone between these groups showed the poorest initial learning rate THE LEARNING RATE CONSTANT The formula for learning or modifying the handover number table was chosen to be a - a where t l Percentages are of Traffic Volume 250- AN ESTIMATOR 0F MEAN PATH LENGTH x 50' SUMMATION 0F HANDOVER NUMBER TABLE ENTRIES 49 MESSAGES HANDOVER MAX FIG AS A FUNCTION OF TRAFFIC VOLUME REDUNDANCY AND MAXIMUM ALLOWABLE HANDOVER NUMBER HHAOGNVH JO OILVH GHZITVNHON 838N014 HHAOCINVH WININ OI 7 ROUTES Average number of messages 1 in network at one time 98 7 to 43 Maximum a1 lowable handover number and initial table D -i3 9 to 41 value -13- Min Possible 1 125 Min Possible 1 2 Min Possible 1 0 TIME Fig 4 -Learning as a Function of Node Location -19- a is the handover value in the table is the handover number of the newly delivered message and is a constant The choice of learning function was partially based upon the requirement that in the real-world it should be capable of being implemented by simple circuitry Figure 5 shows the effect of varying the learning constant 0 6 0 8 and 1 0 The initial value of table total was the same in the three cases -20- at 1 at K bt at where a is the handover value in the table and is the measured handover number 250- LEARNING CONSTANT K 6 8 1 0 200- Redundancy Maximum handover number initial 2 table value 150- 0 Number of messages in net 23 3 53 E 100 E4 50- 0 400 1200 2000 TIME FRAMES 40 98 Fig 5--Learning as a Function of Learning Constant -21- VI DETERMINATION OF TRAFFIC HANDLING CAPACITY As expected more traffic can be handled with an increase in the number of links per node If the average number of messages delivered for two links were to be set with a base of unity the following table could be formed Links No of Messages Delivered Redundancy Node Per Fixed Time Interval 21 9 4 8 28 9 These numbers would vary a bit if more messages were introduced However the number of messages delivered per unit time does not appear to increase significantly as the maximum allowable handover number increases Therefore one can place a bound on the maximum allowable handover number If this value is set too high it could permit consecutive data blocks to arrive out of sequence at high user input data rates Methods to prevent such an occurrence are described in ODC-VII -22- VII DETERMINATION OF PATH LENGTH REDUNDANCY The measured mean handover numbers appeared to settle at about the following equilibrium values No of Messages in System Redundancy TRAFFIC For a test with 2 and the handover maximum at 40 the mean handover number increased as the traffic increased No of Messages Mean Handover Number 49 98 147 8 7 11 2 13 5 -23- Appendix A SAMPLE OUTPUT LOADING MAP A sample computer output containing the map used to indicate the location of all the subroutines of the simulation program is shown in Fig 6 The values shown are the addresses of the subroutines in the core memory and are used for checkout purposes only INITIAL INPUT PARAMETERS Under the printed heading twelve separate parameters that can be selected as input quantities and inserted into the program as a control card are shown These separate quantities shown in Fig 6 are 1 An arbitrary number used to start the random number at a different selectable starting point for each run 5351 in the example shown 2 The number of columns in the rectangular array of nodes 7 3 The number of rows in the rectangular array of nodes 7 4 The number of links connected to each node 8 The value of eight links corresponds to a redundancy level of - 4 5 The number of time-frames between computer printout snapshots 200 6 If the program is used to observe the learning occurring between two selected nodes this LUADING NAP I It SELINK 00152 ROUTE 03305 THTCI 06166 IETTI 06602 ITRCI 06606 RSTART 06767 TEXEH 06676 EXECUTION 5351 3000 7 60 PROGRAM SELVUD 03507 PRINT 03526 06113 REHT 06601 IIQUI 06625 IRTWT 06671 120617 TJTAL VEH 00701 03662 06223 THEFT 06600 TEST 06500 IFILT 06660 200 INDICATES ENTRY 000000 01016 ITSHH 03160 06201 65R 06377 PDUMF -06506 llUH 05023 TINE 203700 0 MOVE 01226 ITSHT 03755 06605 IHRSI 06376 DUMP 06503 HUT 06622 RETURN-07512 0 60 RANTIH 01653 06020 06606 IRDSI 06375 RAN 06756 EXLT 07512 98 Fig 6-Computer Subroutine Location Map and Input Parameters SETTAB 02220 ISTH -06015 IRCHI 06603 TLOS 06263 RANDOM 06760 -24- 7 8 9 10 11 12 OUTPUT -25- parameter would indicate the from node not examined in the attached printouts Same as the previous input but for the to node Minimum path between the inputs of 6 and 7 not used in the following printouts Initial table value Number of messages flowing around in the system at any time 98 Number of time-frames the system is to be run 3000 Maximum allowable handover number 60 The next form of output Fig 7 presents a snapshot summary of traffic status in the network each 200 in this case time-frames 1 2 3 4 Number of messages delivered during the last 200 time-frames 271 503 592 etc Mean value of all handover number table entries during the last 200 time-frames 10 324723 7 109344 5 500000 Percentage of messages dropped because handover numbers exceeded maximum allowable values 0 0 001984 0 01033 0 004458 Total value of the sum modulo 131 172 of all entries on the handover number table 69422 26960 126426 101382 It is to be noted that this table summation is fixed point and modulo 131 172 Thus the first few entries of NUMBER NUMBER NUMBER NUMBER NUMBER NUMBER NUMBER NUMBER NUMBER NUMBER NUMBER NUMBER NUMBER NUMBER NUMBER OF MESSAGES UEL 271 694 TABLE TJTAL 3F MESSAGES DEL 503 26960 TABLE TOTAL OF MESSAGES DEL 532 126426 TABLE TOTAL 3F MESSAGES DEL 670 101382 TABLE TJTAL 0F MESSAGES DEL 623 80662 TABLE TDTAL 0F MESSAGES DEL 668 63549 TABLE TDTAL 3F MESSAGES DEL 685 50456 TABLE TOTAL 3F MESSAGES DEL 731 3748 TABLE TJTAL 0F MESSAGES DEL 701 27134 TABLE TJTAL 0F MESSAGES DEL 702 17743 TABLE TJTAL 0F MESSAGES DEL 743 8352 TABLE TOTAL OF MESSAGES DEL 693 447 TABLE TOTAL DE MESSAGES DEL 734 124178 TABLE TBTAL 0F MESSAGES DEL 710 117393 TABLE TJTAL NF MESSAGES DEL 744 MEAN MEAN MEAN NEAN MEAN MEAN MEAN MEAN NEAN MEAN MEAN MEAN NEAN MEAN MEAN HANUDVER HANDDVER HANDDVER HANDDVER HANDOVER HANDDVER HANDDVER HANDDVER HANDDVER HANDDVER HANDOVER HANDUVER HANUUVER HANDDVER HANDUVER NUMBER PERCENT NUMBER PERCENT NUMBER PERCENT NUMBER PERCENT NUMBER PERCENT NUMBER PERCENT NUMBER PERCENT NUMBER PERCENT NUMBER PERCENT NUMBER PERCENT NUMBER NUMBER PERCENT NUMBER PERCENT NUMBER PERCENT NUMBER Fig 7-Snapshots of Traffic DP MESSAGES 10 324723 UF MESSAGES 7 109344 UF MESSAGES 5 500000 0F MESSAGES 4 743284 0E MESSAGES 4 632424 0F MESSAGES 4 652695 0F MESSAGES 4 049635 0F MESSAGES 3 907688 0F MESSAGES 4 186076 0F MESSAGES 4 116809 HF MESSAGES 3 069044 0F MESSAGES 4 190476 0F MESSAGES 4 102098 0F MESSAGES 4 240845 HF MESSAGES 4 063172 Sunmuxry DRUPPED DRUPPED DROPPED DRUPPED DROPPED DRUPPED DRUPPED DROPPED DROPPED DROPPED DROPPED DRUPPED DROPPED DROPPED 0 0 001984 0 010033 0 004450 0 011111 0 013294 0J007246 0 022727 0 005674 0 015428 0 010652 0 011412 0 006420 0 009763 0 014570 -26- -27- the table totals are in excess of 131 172 However after only several cycles the values drop below 131 172 and remain below this point for the period of interest HANDOVER NUMBER TABLES The following two illustrations define the number- ing procedure for node and link used in the simulationNODE NUMBER DEFINITION LINK NUMBER DEFINITION In the distributed network being simulated a separate handover number table is stored at each node Each node's table is an ordered list of desired nodes sought For example Node 1 would have its table ordered in terms of 3 Node 11 to Node 25 9 Node 49 etc However in the simulation it was more convenient to combine all the tables and to order it in terms of the from stations Hence Fig 8 shows the handover number table for Node 1 which is in the upper left-hand corner of the network Thus it can be seen that traffic from all stations to the east of Node 1 arrived with relatively low handover numbers over Link 2 of Node 2 YO NUDE I FROM NUDE LINK I LINK 2 LINK 3 LINK 4 5 LINK 6 LINK 7 LINK 3 32000 3 32000 32000 8 32000 0 32000 32000 0 32000 3 32000 32000 $0 32000 0 32000 32000 #0 32000 7 32000 32000 10 32000 0 32000 32000 II 32000 32000 32000 32000 32000 32000 6 2 3200 ON 3200 l-l l l 16 32000 15 5 3200 dud IF 3200 NR1 00 Cu uld -32000 0 3 32000 Mmm at oe r m 28 32000 1 3200 $0 6 32000 ro oo u w c If 15 32000 7 40 35 7 32000 32000 #0 as 0 32000 32000 64 3Q 7 32000 65 28 32000 #6 3h 0 32000 67 ll 6 32000 35 7 32000 #0 32000 8 an a 32000 I0 0 32000 16 32000 a 32000 27 37000 #0 #0 32000 32000 32000 10 VUDE 2 FRUH VHHL LINK I 2 LINK 3 LINK LINK 5 LINK LINK 7 LINK 8 3200 wt 4' moc t m ocmmu p In -I Its a Fig 8-Handover Number Table -28- I I I CMAINS INPUT INPUT 1 100 101 102 103 CARDSCOLUMN LIST LABEL DIMENSION COMMON RESET RNDM NO INPUT OUTPUT CALL SETTAB CALL RANTIM DO 5 CALL NEHTM CALL MOVE DO 6 1 1 400 FORMAT15E14 61 FORMAT110110 END CARD COUNT FINAL CARD COUNT 31 31 PROGRAM LISTING Appendix -29- CARDSCULUMN LIST LABEL SUBRUUTINE SETIAB DIMENSION COMMON K lpK4 3 4 DD 5 I ltlJ I lle DU 0 DU 7 7 998CONTINUE DU 11 -30- CONTINUE CONTINUE DU 15 KJ vi2 LUNTINUE GU TU 21 DU 7 I lvlJ DU 16 CONTINUE DU 7 -31 CONTINUE CONTINUE DU 19 CONTINUE GO TO 21 CALL RETURN END CARD COUNT FINAL CARD COUNT 102 102 -32 CARDSCULUMN LISY LABEL SUBRUUTINE ERROR DIMENSION COMMON DU 10 J leJ OUTPUT DU 10 K loK4 OUTPUT 42 90pK OUTPUT 10 CONTINUE RETURN 80 TU NUDE 90 FORMATIIOH LINK NU I3 100 END CARD COUNT 20 FINAL CARD COUNT 20 -33- NM CARDSCULUMN LIST LABEL SUBRUUTINE DIMENSION COMMON 16'192 GO TO 16 16 394 L l 00 TU 16 16'596 GO TU 16 16 7 8 GU T0 16 16 9910 GO TO 16 lF L b 16 11 12 -34- 16 13114 GU IO 6 16 15 16 RETURN END CARD COUNT FINAL CARD COUNT 42 42 -35- CARDSCOLUMN LIST LABEL SUBROUTINE PRINT DIMENSION COMMON DO 20 OUTPUT OUTPUT 42'110 DO 20 OUTPUT 20 CONTINUE RETURN 80 FORMATIIOH TO NOUE I3 110 FROM NUDE LINK LINK 2 LINK 3 LINK 4 LINK 5 LINK 6 LINK 7 LINK 8 120 END CARD COUNT 21 FINAL CARD CUUNT 21 -36 I I I CARDSCOLUMN LIST LABEL CSELNDB SUBROUTINE SELNODIMI DIMENSION COMMON CALL KAMZKATIMI 41514 KKIMI GU T0 6 IFIKHANDIMI-KHMAXI 6 313 KKIMI3-IFIN RETURN END -37- CARD COUNT 29 FINAL CARD COUNT 29 I I I CARDSCULUMN LIST LABEL 11 IO 12 SUBRUUTINE DIMENSION COMMON DU 2 2 1 2 CALL 9 599 GO TO 2 CONTINUE 3t7v7 CALL RANDUMLR 393 11 10 1013 394 3 3 1293 1393913 -38 13 GO TO RETURN END CARD COUNT FINAL CARD COUNT 40 -39- CNEH3 CARDSCULUMN Lle LABEL SUBRUUTINE DIMENSION COMMON CALL 60613 5 395 RETURN END CARD COUNT 24 FINAL CARD COUNT 24 -40- CARDSCULUMN LIST i LABEL CNEH3 SUBRUUTINE DIMENSION CUMMUN 3 7 3 7 3 CALL 393 4 IFIK-IJ 6 6 3 RETURN END cm FINAL CARD CUUNT 20 -41- I I CRANT p 10 ll 12 13 14 CARDSCULUMN LIST LABEL M2 SUBRUUTINE RANTIM DIMENSION COMMON CALL DU 9 DD 9 CALL RANUUMIR 69797 BuByb 17110 11 L l GU T0 3 17112113 00 T0 3 iF K-b 17 14v15 J l K3 l -42- 15 16 8 GO TO 3 IF1K-8 17916117 9 9 4 CONTINUE GO T0 18 CALL RETURN END CARD COUNT FINAL CARD COUNT A2 42 -43- CAROSCOLUMN LIST LABEL CMOVES SUBROUTINE MOVE DIMENSION COMMON DO ll 20 21120 21 DO 30 DO 30 J leJ DU 30 K lyK4 25 25 30 25 30 CONTINUE OUTPUT 42 1809KTOT OUTPUT 42 1509PCH OUTPUT 20 DU 11 -44- 12 7 9 7 12 3111 8 CALL SELINKIM GU TU ll 9 10 CALL SELNUDIM GU TU 11 2 CALL NEHIM ll CONTINUE l3 RETURN 18 CALL 150 FORMATI76H PERCENT 0 IF MESSAGES DRUPPED 170 FURMATIZSH NUMBER OF MESSAGES DEL MEAN HANUDVER NUMBER F1 12 6 180 TABLE TOTAL END CARD COUNT 56 FINAL CARD CUUNT 56 -45- -47- ON DISTRIBUTED COMMUNICATIONS List of Publications in the Series I Introduction to Distributed Communications Networks Paul Baran RM-3420-PR 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 preposal 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 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 48 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 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 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 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 -49- scheme provide a strong roundation for the belief that the construction and use of the node is practical The Multiplexing Station Paul Baran 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 RM-3765-PR 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 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 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