MEMORANDUM RM-3578-PR AUGUST 1964 ON DISTRIBUTED COMMUNICATIONS DETERMINATION OF IN A J W Smith PREPARED FOR UNITED STATES AIR FORCE PROJECT RAND SANTA MONICA - CALIFORNIA MEMORANDUM RM- 3578 -PR AIJGUST 1964 ON DISTRIBUTED COMMUNICATIONS DETERMINATION OF IN A DISTRIBUTED NETWORK J W Smith 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 Sta Research and DeveIOpment Hq USAF Views or conclusions contained in this Memorandum should not he 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 74 1700 MAIN ST - SANTA MONICA - 0040 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 On 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 third in the series is a continuation of the model simulation study reported in the previous volume Since a network of the type proposed had never been built there was much we did not know about its performance For example we wanted to learn more about the distribution of message in the network in order that transmission times might be de termined we wanted to know how the network behaved under heavy loading--such as would occur during a crisis A list of all items in the series is found at the end of the Memorandum -iv- we wanted to know how the network would react when a hog station or stations attempted to purposely overload the network we wanted to know how many message blocks would be lost if a policy of dropping traffic that has circu- lated longer than some Specified time were used Because of the complexity of such networks our only high-confidence tool for predicting performance was the Monte Carlo simulation wherein messages are created and circulated in a computer model of the network statistics of traffic-flow are examined network parameters are changed and the network is re-examined A FORTRAN simulation for the IBM 7090 computer was described in Vol II in the series together with the re- sults of the simulation performed There were three short- comings to this effort first the size network that could be accommodated was smaller than desired second an undue number of messages was being lost during heavy overload conditions when messages began to take circuitous routes and third when the routing doctrine was improved to pre- vent such message losses it became economically unfeasible to run the computer simulation long enough to determine the number of messages which could be expected to be lost A target of less than one lost message per 100 000 000 was sought this extreme requirement was selected because it was felt that future systems should be able to transmit digital data between computers- and computers are often intolerant of errors A new simulator designed to resolve these problems was encoded in the SCAT language This Memorandum de- scribes that simulator and its appurtenances and reports on the successful rectification of the previous effort's shortcomings In addition some analytical investigations of traffic-flow are described and evaluated International Business Machines Corporation SHARE SOS Reference Operating System for the IBM 709 IBM Applied Programming Publication New York I960-61 -vii- SUMMARY Results of investigations into the behavior of distributed communications networks under various loading conditions are reported A mathematical model and a deterministic equation for predicting the distribution of message are derived and evaluated A BOAT-encoded simulation program that corrects deficiencies of earlier simulations is described An input-choking doctrine together with a short purposeful delay of messages passing through each station when necessary proved to be a powerful device in pre- venting loss of messages within networks operating at high loading ratios The decrease in delay and in message I flow rate caused by the doctrine was negligible For the networks studied a policy of dropping messages that have traversed paths greater than twice the longest possible path between the extremities of the network resulted in a message dropout rate of less than one in 100 000 000 when the networks were operating at normal and even higher than normal loadings At low loadings there were even fewer messages dropped -ix- PREFACE 111 SUMMARY v11 SYMBOLS x1 FIGURES Section I INTRODUCTION I II THE ROUTING DOCTRINE 4 COMPUTATIONAL TECHNIQUES 8 Monte Carlo Simulation 8 Model A Ma 10 Model Mb 12 Comparison of Results 13 IV INPUT-CHOKING AND STACK 18 V EDGE BINDING 23 VI VARIATIONS IN TRAFFIC DENSITY 28 VII THE BEST-PATH ALGORITHM 31 Appendix A PROGRAM DESCRIPTION 33 B PROGRAM LISTING 40 LIST OF PUBLICATIONS IN THE SERIES End xi- SYMBOLS INTRODUCED SYMBOL ON PAGE Si The 1th station in a network 1 in an array of stations Hi j k The expected number of stations 3 to be traversed by a message originating at Si transmitted via link of Si before being delivered to Sk' Lj i Link of station Si links are 3 numbered from 0 through 7 and are displayed clockwise around the station with L0 at high noon 1 S0 A message's station of origin 4 Sd A message's addressee 4 The hand over number associated 4 with a message the number of stations traversed by a message in its wanderings HMAX The maximum allowable number of 4 traverses a message may take before being dropped from cir culation B i k By definition the length of the 5 best path between Si and Sk' Nx The number of best paths of 5 length x x' The maximum best path length 5 The best-path distribution 5 XI N SYMBOL ML -xii- The number of links in a network Message loading factor for a simulation The probability that a link is impaired unavailable or busy Message-unit length INTRODUCED ON PAGE 8 FIGURES Figure 1 Definition of Redundancy Level 2 Flowchart of Model A 3 Distribution of of 10 ll 12 13 Delivered Messages 14 7 Network Statistics for Networks NO_Ch0king Statistics to to DOI- Distribution of Stack Waiting Times of Delivered Messages 14 7 Network Redundancy 3 Choking Edge Binding 0 Traffic Flow Distribution Statistics for Networks Edge Binding Distribution of of Delivered Messages 14 7 Network 3 Edge Binding 0 I 0 Sample Network Program Network Parameters WEAVE Parameter 11 14-26-27 I INTRODUCTION The distributed communications network examined in this Memorandum is a collection of communication stations interconnected in a more or less regularized manner and employing a common switching doctrine The connectivity is such that the number of bi-directional lines or uni- directional links between a station and its neighbors is constant over the interior of the network and bandwidth capabilities of the lines may vary over the network Switching or routing is performed by choosing a best initial link toward a desired addressee rather than by attempting to choose a best overall path Certain stylized connectivities may be introduced to define the redundancy level of such networks--the concept is illustrated in Fig It is useful and in- structive to deal with such connectivities and we shall do so However many of the observations reported in this Memorandum are dependent on a constancy of connectivity and routing doctrine rather than on any specific regularity of connectivity The choice of a best initial link is effected by adjoining to each station Si a matrix Hi which assigns Figure is taken from ODC-I where the concept of redundancy levels is fully described CDC is an abbrevia- tion of the series title On Distributed Communications The number following refers to the particular volume within the series Fig 1 Definition of Redundancy Level to each link L of station Si a measure J i of link j's merit as an initial link along which to route messages destined for station Sk--for all stations Sk in the network The figure of merit used in this Memor- andum is the expected number of stations to be traversed before delivery of the message That is a value states that station Si expects a message destined for station Sk that is sent out along link Lj i to traverse stations before delivery By adjoining to every message an integer h--the hand-over number Which is incremented by unity each time the message is re transmitted by a station--the values of Hi may be con- tinuously updated as a function of the hand-over numbers associated with incoming messages and of the current values of Hi' Messages are routed by applying a decision procedure to those Hi values pertinent to the messages' destinations The transient behavior of the Hi and of message-flow as the Hi change under suitable updating algorithms is discussed in ODC-II The present Memorandum is concerned with steady-state flow wherein the Hi have assumed their best values and there remain fixed II THE ROUTING DOCTRINE Let 80 Sd and refer to a message's originating station addressee and hand-over number respectively Messages arriving at station Si via link Lj i cause the values of Hi to be updated by the following updating doctrine U1 U1 Hi j o minimum h Let station Si have links Ll i Lni i and let HMAX the maximimum allowable hand-over number be a fixed parameter Station Si retransmits messages by applying the following routing doctrine R1 R1 a if h'z HMAX the message is dropped b if all links are in use or otherwise un- available the message is stacked until some link is freed c if links are available is incremented by unity and the message retransmitted over that link Lj' i for which for all available links Lj In practice the Hi are originally set equal to as messages move through the network these values eventually assume their absolute minima These minimum values may be calculated a priori by a best-path algorithm a See Sec VI Assume this has been done resulting in values De- fine for all stations Si and Sk kx i B i k for all links 2 1 L of station 3 1 1 the number of B i k equal to 2 2 for all i k x' for all i k 2 3 That is B i k is the length of the best path from S1 to Sk NX is the number of such best paths of length x and x' is the length of the longest best path The distribution B defined by B x Nx 2 4 y is called the best-path distribution for the network It will be shown later that is of great utility in pre- dicting traffic flow in steady-state networks If messages are generated by choosing origins and destinations randomly from a uniform distribution of stations and if each message is completely routed through the network before the next message is originated then the resulting distribution of message is clearly B That is equally valid for low-load conditions is shown by Fig to be discussed later The HMAX test in routing doctrine R1 is essential Traffic will in practice be cut into message blocks of fixed length and be sent piecemeal but serially If the differential time delay is excessive then the order of arrival of these message blocks could fall out of sequence This differential time delay is equivalent to the difference in hand-over numbers of the arriving message blocks Therefore the lower the tolerable maximum hand-over number the higher the overall data rate between two network users will be We also chose to drop message blocks whose hand-over number exceeds this maximum allowable to insure flushing out message blocks addressed to nonexisting stations Since fixing the length of message blocks implies fixing station processing time for routing network time may be equated to station traverses by using an average link-length for the network and temporal decisions can then be made on the basis of some maximum hand-over number and the hand- over number associated with messages Thus the problem of choosing an HMAX small enough to maintain integrity of communications yet large enough to guard against excessive message dropout is a central one The choice See p 14 of such a value for a given network depends on a knowledge of the distribution of message of delivered messages under varying traffic densities and using an un- bounded HMAX Three methods for determining such dis- tributions- Monte Carlo simulation mathematical modeling and approximate calculation- are described and compared in the next section COMPUTATIONAL TECHNIQUES MONTE CARLO SIMULATION The simulator is described in detail in the program listing of Appendix briefly it operates in the fol lowing manner 1 a network is defined in terms of its size con- figuration and connectivity 2 are assigned--as transmission times - by being drawn from a uniform distribution bounded by the parameters TPMAX and 3 the hand-over number tables Hi are preset to either i or to values bounded by HMAX and 4 a fixed number of messages is intro- duced into the network origins and destinations of messages being drawn from a uniform distribution of station numbers --A is the total number of links twice the number of lines in the network and a is a loading factor 5 the routing and transmission of messages through the network is directly simulated by applying the routing doctrine 6 delivery or dropping of a message results in the insertion of a new random message into the network thus maintaining loading a This defines uniform loading 7 new messages may be choked by applying R1 first to enroute messages then to new messages which are in effect kept on a special stack The parameter a is a measure of the activity of the network We may assume that under uniform loading traffic density can be equated with a probability u that a link is unavailable or busy and may then relate to activity by - 3 1 where ML is the processing time per message-unit message-unit length is the average line-length or average transmission time and a message- unit requires ML time units to be inserted into or with- drawn from a link In 3 1 a is treated as the number of message-units that may be on a link either in transit or being transmitted into the link and the first factor is interpreted as the probability that a message is being transmitted into a link thus making the link unavailable Under uniform loading in a fully loaded network at each time period all links would be jammed and all stations would be simultaneously accepting and transmitting a message The average number of messages in a fully loaded network would therefore be equal to -10- A 2 The loading ratio of a network is then equal to N dl which is equal to n thus may be equated to the loading ratio or traffic density of a network MODEL A Ma A model of network behavior is abstracted by con- sidering the four possibilities that exist for the dis- position of messages at any station disregarding the possibility of dropout A message being routed at a station has associated with it that station's prediction of the best-path length to the message's addressee The message may either 1 remain at the station or 2 be retransmitted to a neighbor whose best-path prediction is a one 1 less than the previous station's prediction b the same as the previous c one 1 greater than the previous That is links may be characterized as being best next best or worst for any message The model de- fined in Fig 2 assumes l a uniform distribution of links with respect to best next best and worst overall addressees Choose a random path-length K from the distri- bution B jun 0 j j'l'l Is best link available no Is next best link available no N Is worst link available yes K l Fig 2 Flowchart of Model A yes Record the path-length j -12- 2 a uniform probability n of link nonavailability 3 uniform loading 4 stations connected to neighbors only The first assumption is the weakest of the four however within the interior of reasonably connected networks satisfying the last assumption it is reasonably valid MODEL Mb Model is obtained from the previous one by aggre- gating next best and worst links In therefore a message at a station whose best-path prediction for the message is say n will have a probability p n x of being delivered in traverses given by mm some 1 - 3 2 'where is the probability of link nonavailability and g n x is the number of combinations of best paths chosen with probability 1 - n and worst paths chosen with probability n ending in a best path That is x-l 8 n 8 11-1 3 3 The distribution generated by this model is given by 713- x M x n 3 4 i 1 I Letting l a and using 3 2 we obtain xl - 3 5 i 1 Since we have x 1 a x' 2 3 1 1 3 6 x l i 1 and for the tail of the distribution from x' k on a i 1 3 7 I k i 1 COMPARISON OF RESULTS The three techniques were applied to networks of size 10x10 and 14x7 using redundancy levels of 2 3 and 4 Figure 3 exhibits the results of the 14x7 redundancy- three case--a11 other runs produced the same behavior Fig 4 tabulates statistics for the various runs D nuanad sabossew 04 a I Best path Path Iength Sinu otor I I I I Modd A Probability'that each link is busy or impaired ModeIB 5663 #14- 6 Simulator 11 03 8 Model Model 28354249 2835 4249 4956 63 I 7 I4 2 28354249 56 63 Fig 3 Distribution of of Delivered Messages 14 7 Network 3 Net Description Best-Path Average Longest S1 Average Path-Length Ma Mb HMAX Required to Reduce Dropouts to One in 108 14 7 a 4 5 21 13 11 17 12 16 10 40 8 31 9 72 8 67 6 58 47 95 7143 5 82 6174 6 61 5 43 6184 5 78 14 7 3 6 11 19 14 36 14 23 12 19 10156 11 406 10 16 8 14 9 28 8 71 7 0-11 7 86 7 62 46 43 6 88 6 77 7 00 19 17 19 16 24 13 97 15 30 13 05 11 64 11 25 10 63 9 98 8 95 9 04 817% 7 66 7 857 7 76 10 10 3 5 67 18 12 32 13 23 11 32 9 39 10 30 9 43 7 53 8 64 8 09 6 50 7 33 7 07 nd UL and quwnqu 5 98 6 37 6 29 Sl Simulation Ma - Model A Fig 4 Statistics for Networks Mb - Model _117- - n- Relation 3 1 was used to equate simulator loading with the probability of link impairment n used by the models Since this is an approximate relation no exact comparisons between simulation and modeling can be made Nevertheless it is clear that both models produce distributions which are commensurate with those produced by the simulator Model A tending to reproduce the shape of the simulator distributions more faithfully than Model B Moreover note that both models tend to produce distribution tails which are generally pessimistic The same comparisons held for the other runs We therefore conjecture that both models may be used to predict approximate behavior of networks of the type examined and that 3 7 may be used to obtain approximate estimates of for desired dropout rates Figure 4 indicates that the transition from a re- dundancy level of three to a level of four results in diminishing returns For redundancy levels greater than two it appears that an HMAX equal to twice the longest best-path is sufficient to reduce dropouts to the noise level under normal and even higher than normal loadings s IV INPUT-CHOKING AND STACK Input-choking in networks has two important conse- - quences First since a link can be usurped by a message for no greater period of time than it takes to insert a message into a link ML it is clear that stack length can never exceed the number of links associated with a station that is stations require only one word of stack storage per link Moreover choking tends to smooth out potential activity peaks particularly in the vicinity of hog stations and around the center of the network Removal of input-choking simply means that new messages are treated as enroute messages Under such conditions stack cannot be contained Since stack storage must be finite a new message-dropping criterion must be added to the routing doctrine R1 R1 d if no links are available and the stack is full the message is dropped Thus the choice of a fixed stack-storage length STACK large enough to reduce stack dropouts to the noise level becomes as important as a choice of HMAX Since stack length is a highly local phenomenon--strongly dependent on traffic distributions--there seemed to be no simple way of determining STACK without direct simulation Ac- cordingly the simulator was applied--with no input-choking-- to a 14x7 net of redundancy-three with maximum stack See p 9 of 6 9 and 12 The distributions obtained were almost identical to the choked distributions They are not reproduced here however Fig 5 compares the perti- nent simulations and leads us to the following conjectures l dropouts will occur under no-choke conditions to insure a low dropout rate STACK will have to be un- conscionably 1arge--hence unfeasible 2 under uniform loading no-choking produces a small uniform increase in loading 3 hence there seems to be no justification for adopting a no-choking doctrine These conjectures are fortified by a consideration of the distribution of total time in stacks including input- waiting time for delivered messages These distributions were identical for the choke and no-choke cases In fact the distributions shown in Fig 6 were typical of all net- works simulated they show that the probability of exces3' sive delays-in-stack is exceedingly small even under high loading -20- Mode Probability Value of Link - HO HO of HO Stack No in Impairment57r Average Variance No Choke Drops Stack 1 6 5 13 2 4 yes 6 5 13 5 4 no 0 12 6 5 13 5 4 no 0 9 3 8 0 20 6 5 yes 8 1 21 7 5 no 0 12 8 1 21 7 5 no 0 9 5 13 7 104 3-7 yes 14 3 117 3-7 no 5 12 1417 9 166 3-7 yes 17 4 167 3-7 no 27 12 17 9 176 3-7 no 251 9 Fig 5 No-Choking Statistics 0-21Waiting times I z message unit Fig 6 Distribution of Stack Waiting Times of Delivered Messages 14 7 Network Redundancy 3 Choking -22- Fig 7 Edge Binding V EDGE BINDING In any network much of the routing power of peripheral stations is wasted simply because peripheral links are unused Thus messages tend to reflect off the boundary into the interior or to move parallel to the periphery Providing alternate paths by edge binding as illustrated in Fig 7 should tend to shorten average measurably Figure 8 exhibits flow patterns produced by simulations of a 14x7 network of redundancy-three with and without edge binding Each diagram is a spatial re- presentation of the network the entry in position of the representation indicating the number of messages routed through the corresponding station since the start of the simulation The effect of edge binding in reducing interior clustering is clear Figure 10 exhibits the dis- vtributions for the edge bound net while Fig 9 gives statistics for the various runs Although edge binding reduces clustering and results in an increase in flow- rate it seems clear that the resultant distributions are less desirable than those obtained without edge binding Apparently edge binding tends to overly penalize paths through the center of the network and seems to provide higher flow rates at the expense of higher drop- out rates n 0 5 n 0 3 n 0 1 219 506 759 1045 1476 2256 3036 3513 3699 3689 3568 3002 1732 493 287 658 937 1176 1444 1664 1842 2028 2129 2002 1678 1284 827 424 116 250 371 430 516 556 591 598 570 533 510 415 287 142 Number of 408 941 1397 2043 3114 4481 5326 5656 5678 5620 5282 4114 2072 579 512 1122 1621 2096 2542 2893 3224 3484 3442 3153 2689 2018 1350 542 205 466 665 800 967 988 1058 1066 1030 959 826 637 483 177 UNBOUND 514 1209 1866 2914 4399 5328 5705 5824 5798 5634 5145 3641 1796 645 594 1300 1939 2554 3070 3491 3782 3889 3717 3448 2942 2277 1477 636 244 542 808 932 1081 1169 1273 1274 1179 1089 949 780 520 216 601 1419 2403 4066 5263 5702 5875 5855 5770 5476 4613 2923 1457 627 638 1434 2206 2933 3466 3833 4054 4072 3893 3518 2999 2262 1445 646 239 568 819 1007 1189 1298 1307 1344 1276 1150 994 810 520 214 566 1510 3110 4773 5579 5858 5920 5864 5653 5089 3710 2161 1223 567 597 1404 2198 2895 3374 3701 3932 3950 3718 3292 2731 2070 1357 593 233 538 790 1006 1151 1216 1281 1280 1183 1086 981 776 522 224 'Fig 8 Messages 525 1689 3582 5128 5687 5876 5868 5695 5286 4191 2657 1561 1028 477 490 1296 1929 2538 2995 3353 3553 3471 3099 2659 2160 1665 1111 489 183 480 687 874 943 998 1052 1072 977 938 757 604 387 180 -24- 413 1375 2788 3567 3860 3890 3819 3575 3071 2109 1251 799 551 249 330 760 1165 1500 1791 2037 2120 1969 1718 1462 1160 904 631 273 115 274 404 509 591 627 643 599 577 511 441 346 261 113 872 1664 2942 4135 4753 5273 5477 5548 5478 5498 5312 5168 4022 3747 567 889 1512 2448 3118 3934 4170 4521 4521 4558 4212 3876 2725 2655 251 355 624 924 1122 1452 1515 1755 1571 1707 1362 1423 782 1089 919 1326 2238 3194 3971 4472 4784 4807 4826 4592 4208 3732 3279 2240 616 776 1125 1592 2210 2500 2850 2961 3084 2857 2531 2040 1873 1492 279 334 472 548 673 675 701 666 717 691 629 583 527 487 1893 1344 1787 2714 3451 4031 4234 4322 4231 3719 3156 2464 1859 2701 1179 842 1169 1674 2013 2203 2325 2387 2327 2155 1849 1494 1180 1910 555 344 511 738 752 804 791 817 819 819 723 602 407 805 BOUND 2452 2097 2408 3216 3831 4260 4471 4429 4165 3633 2855 2045 1428 1442 1216 1124 1523 1974 2239 2425 2454 2466 2413 2137 1933 1424 1042 1171 484 432 625 751 860 867 918 885 886 869 772 606 417 462 Traffic Flow Di strib t ion Routed Through Node in 7 4131 3277 3763 4284 4615 4861 4916 4749 4489 3886 3098 2051 1203 1444 2109 1328 1795 2113 2410 2663 2670 2599 2453 2143 1732 1213 836 1149 891 431 599 714 797 832 861 830 827 781 702 570 355 520 3715 4859 5125 5365 5477 5454 5352 5296 5066 4732 4000 2972 1768 880 1763 2402 2710 3195 3472 3683 3669 3537 3168 2742 2015 1345 830 634 531 579 618 690 760 785 748 794 675 685 602 500 323 269 14 Network 4641 4742 5790 5862 5836 5827 5777 5757 5671 5487 5111 4077 2434 1270 3138 3332 4578 4796 5124 5153 5109 4883 4631 3952 3129 2064 1149 656 1255 966 1606 1637 1994 1872 1998 1748 1618 1297 1028 646 419 251 Net Description Best-Path Average Longest Average Path Length S1 a Mb HMAX Required to Reduce Dropouts to One in 108 14 7 4 32 10 9 98 10 10 8 61 7 77 7 98 7 18 6 29 6 58 6 16 museum 5 35 5 587 5 39 4 78 4 87 4 79 4 86 10 12 10 11 31 9 70 9 85 9 02 8 09 7 84 7143 6 93 6 34 6 27 6 07 quwoburd 5 44 5 48 5 39 5 46 11 Ln 14 11 12 66 10 89 t 11 20 0 09 9 07 8 56 8 36 7178 7 00 7 06 6 81 6 01 6 11 6 05 4 83 10 10 48 11 27 9 65 8 10 8 97 8 04 6 74 7 37 6 89 5 84 6 23 6 03 Wm f bd 5 26 5 44 5 36 1 - Simulation Fig - Model A a 9 Statistics 10f Networks Edge -25- Iuaa Jed sabossaw C14 28 35 42 49 56 63 Model A I I TT Probability that each link is busy or impaired ModeI 3542495663 354249 56 63 7 4 2 28 354249 5663 26- SimquIor I I I I Model Modd 8 4 I I I 2 283542495653 7 42 283542495663 4111 263542495663 283542495663 IFig 10 Distribution of of Delivered Messages 14 7 Network 3 Edge Binding -27- 28- VI VARIATIONS IN TRAFFIC DENSITY Techniques for smoothing out fluctuations in traffic density are discussed in CDC-II A technique suggested and evaluated in that Memorandum uses a modification of the HO-table updating algorithm which allows the values of Hi j k to to changing traffic conditions The adaptation algorithm is described in the footnote to Fig 12 of the present Memorandum 37 which considers the effects of bursts of activity from a single station or between a pair of stations Such effects can be studied by appending to the simulator provisions for treating specified stations as message sources or sinks with specified weights associated with each station so chosen A station specified as a source sink of weight 1 will be chosen by the simulator as a message origi- nator addressee with probability k Since correct receipt of each message block is acknowledged by the adjacent receiving station it is clear that any pro longed increase in the rate of message generation by a single station will result in a commensurate increase in network loading In such cases we would expect effects similar to those produced by an increase in message load- ing In cases where many stations suddenly increase their rate of message generation to a particular Station a similar increase in network loading should occur This -29- is prevented from occurring by mechanisms described in Several hog cases were simulated on a 7X7 network of redundancy three The procedure used was the following first simulate the network at a 20 per cent loading ratio without sources or sinks then increase the loading ratio to 40 per cent specify a commensurate source sink con figuration and continue the simulation comparing Statistics at each step The results are summarized 1 Regions of heavy flow activity centered about sources and sinks 2 Source sink configurations caused a 50 per cent decrease in the message-flow rate -this was probably caused by input-choking 3 Distributions of stack waiting times--with sources and sinks--were identical to those obtained for 40 per cent loadings without sources or sinks 4 Single stations acting as both source and sink had little effect on the distribution of of delivered messages the distributions being only less desirable than those obtained for 20 per cent loading with no sources or sinksgi 5 Two stations each acting as both source and sink had effects on the path-length distribution which depended on the relative positions of the stations within -30- the network--the more remote the stations the worse the distributions We conjecture that single stations acting as a hog source will reduce message-flow rate but will result in few if any dropped messages The case of a single source was simulated such as would occur when a fraudulent station attempted to over- load the network The results were as anticipated the increased loading produced distributions expected from the new loadings Single sources had essentially the _same effects as single source sinks with the exception that stack waiting times remained relatively unchanged -31- VII THE BEST-PATH ALGORITHM Although the algorithm used to set the hand-over number tables Hi to their best values was designed solely to minimize computer running time it might also con ceivably find use other than in the Distributed Adaptive Message Block Network in allowing broadcast of best-path information through a network The algorithm requires a specific recognizable message-type an info-message and a variation of the standard routine doctrine to process such messages The algorithm is as follows 1 a station 80 that wishes to broadcast best- path information to the rest of the network originates an info-message and transmits the message over all its links Lj o 2 a station 81 receiving an info-message charac- terized by via link Lj i compares with a if 3 Hi j o the message is dropped b otherwise Hi j o is set to h is in- cremented by unity and the message is re- transmitted over all of 81's links The best-path algorithm used is a parallel application of l and 2 above with all stations acting as originators once and only once In practice info-messages may be characterized either by the absence of an addressee or by a universal addressee Appendix A PROGRAM DESCRIPTION A listing of a collection of SCAT-encoded computer routines designed to operate under the aegis of a user composed supervisory routine is contained in Appendix B The collection includes routines for defining networks in terms of pertinent parameters for assigning and re-assigning parameter values for performing Monte Carlo simulations on networks for applying Model A and Model to networks and for displaying results of simulations and model-runs The routines are operative on the IBM 7090 require the RAND versions of 308 for that machine and are well- described by the listing of Appendix B Supervisory routines to perform network calculations must be encoded in SCAT and should use the macro directives described on p 4 of the listing Figure 11 contains an example of a supervisory routine suitably annotated The general procedure is to first assign parameter values then to simulate or model and finally to display or interrogate results and perhaps iterate the procedure Network parameters are described in Fig 12 the normal values there listed remain in effect until changed by the Bryan G E Ed The RAND-SHARE Qperating_System Manual for the IBM 7090 Computer The RAND Corporation September 1962 If 4 oA L2 0L4 FIRST JOB ASSIGN LOAD CHANGE ROW COLUMN WEAVE CHOKE NOBIND FLOW BESTHO AXT IMPAIR SIMUL PRINT PRINT PRINT MODELA MODELB TIX IMPAIR SIMUL IMPAIR SOURCE CONT PRINT PRINT PRINT SINK CONT PRINT PRINT PRINT TRA DEC DEC DEC DEC DEC EOU -34- NETPGM 14 7 3 SYSTEM THEN APPLY 591 oL l SYSTEM93000 SIDIST SUFLOW SYSTEM SYSTEM IA'l l L2 L4 19-5 1000 SIDIST SIWAIT SIFLOW 1 5 1000 SIWAIT s1FLow SYSTEM 1 2 3 5 BEGINNING OF SUPERVISORY ROUTINE REDUNDANCY THREE- WITH INPUT CHOKING AND NO MESSAGE FLOWS DESIRED PRINT BEST-PATH DISTRIBUTION EXIT IF NOGO AND MODEL 3 -- VARYING LOADING FROM 10 PERCENT TO 50 PERCENT IN JUMPS OF 10 USING UNBOUNDED HMAXINORMAL CASE SET LOADING THEN SIMULATE FOR 3000 CYCLES THEN DISPLAY DISTRIBUTION STACK-WAITING-TIME DISTRIBUTION AND MESSAGE-FLOW PATTERNS NEXT APPLY MODELS I DISTRIBUTIONS ARE DISPLAYED NEXT RUN FOR BOCC CYCLES AT 20 PERCENT LOADING NEXT DOUBLE LOADING AND DEFINE STATION 1 AS A SOURCE OF WEIGHT 1 2 THEN DISPLAY THEN MAKE STATION 1 A SINK OF WEIGHT 1 29 MAINTAINING ITS SOURCF STATUS FINI 11 Sample Network Program -35 supervisory program Much of Figs 11 and 12 and the macro-directive listing in Appendix B is self-explanatory The parameter WEAVE which specifies network con- nectivity is defined by Fig 13 The parameter GRAIN defines the ratio of message-unit length time required to insert a message into a link to the time required by a station to route a message Since messagewrouting time is equivalent to simulation cycle time GRAIN defines the coarseness of the simulation Note that simulations may be halted and then continued during these pauses the user may display results of the simulation and may change the values of certain parameters Parameters which may be changed during the course of a simulation are in dicated in Fig 12 with an asterisk Sources and sinks may be defined deleted or have their weights changed during a simulation Deletion of a source or sink is accomplished by assigning a zero weight One further restriction exists the impairment factor IMPAIR may not be reset to a value greater than that which held at the initiation of the simulation this however is not a real restriction since the simulator can be initiated for a zero-time run Execution times for application of the two models are negligible Simulation times are a function of the size and connectivity of the net being simulated and of the traffic density A reasonable approximation to Parameter Name Function Restrictions Normal Value ALPHA HMAX HPRIME ROW COLUMN GRAIN TPMAX TPMIN 0 implies no input-choking 0 implies input-choking The loading factor described in Sec The maximum hand-over number HMAX 63 implies messages are never dropped Used to preset the hand-over table HPRIME 0 implies is preset to best values otherwise is preset with values drawn from uniform distribution between HPRIME and HMAX rows Number of in network columns The grain of the simulation the ratio of message-length time to place messa on or accept message from a link to the time required by a station to process the message are assigned values drawn from uniform distribution bounded by GRAIN none computed as function of IMPAIR HMAX an integer HMAX 63 h' an integer integers integer integral number of station pro- cessing times Fig 12 Network Parameters 0 63 -36- Parameter Name Function Restrictions Normal Value STACK WEAVE RANDOM FLOW BIND Maximum stack-storage described in Sec IV The connectivity of the network see Fig 13 The probability of link impair ment used by Ma and Mb and the simulator An initial pseudo random number implies message-flow statistics are desiredimplies implies implies none are desired edge binding Fig no edge binding implies Hi table entries i are updated by hi minimum 0 implies Hi table entries are updated by adaptation algorithm a Learning factor for adaptation Forgetting factor for adaptation integer decimal fraction large odd integer none none none 0 LEARN 5 1 0 FORGET 1 976525005 aLet then H0 H0 ll Fig 12 Continued -37- -33- WEAVE Redundancy Level Fig 13 WEAVE Parameter -39- execution times for an net of redundancy rgis given by time per simulation cycle ms where a is the loading factor described in Sec Computer storage required is a function of net size and connectivity of traffic density and of other desiderata An net of redundancy-r requires approxi- mately n'm n-m-r words of computer storage 24 000 words being available A 10x10 network of redundancy four or a network of redundancy-three can be accommodated -40- Appendix PROGRAM LISTING In this appendix is presented the program listing together with a Table of Contents to the routines listed The page numbers referred to in this table are the numbers internal to the listing not the pages in the Memorandum TABLE OF CONTENTS INDICATES ROUTINES OF DIRECT INTEREST TC USERS ROUTINE DESCRIPTION MACRO DESCRIPTIONS NETDHP ERROR DUHPS AND DISPLAYS NETPGM SUPERVISORY PROGRAM PARSET USED TO SET PARAMETER VALUES ENTRY ENTRY ROUTINE FOR SUPERVISORY MACROS PRESET INITIALIIES NETHURKS- USED BY SIMULATOR AND BY MODELS USES INLI INS IL 8H INL SETS CONNECTIVITY HAP INS CCNPUTES STORAGE HAP IA SETS LINK TABLE IL GENERATES LINK IF GENERATES INITIAL HO TABLE BF GENERATES BEST HO TABLE NEVER USED BY SIMULATOR TO MOVE HSGS HCVER USED BY ROVER AND BH TO UPDATE HO TABLE UPDATE i USED BY HOVER AS UPDATING ALGORITHM DELIVR USED VARIOUSLY TO STACK MESSAGES AT STATIONS ROUTER I USED BY SIMULATOR TO ROUTE HSGS LSES FA FB FA DETERHINES A STATIONS AVAILABLE LINKS FB ORDERS AVAILABLE LINKS H R T HO-TABLE VALUES PAGE 34 36 37 39 42 43 PAGE 1 DROP RECORD HG ACTIVE GM aw SIMULB CONT SKTLU SCTLU SIDIST SIFLOH PB SETHHX CLEAR BESTHO HTF HTS HODELZ HCDELI PLACES DROPPED HSGS ON DROP LIST PLACES DELIVERED MSGS ON ARRIVAL LIST USED VARIOUSLY TO PLACE 565 ON LISTS USED BY SIMULATOR TO PRESET MSG LOADING I RECALCULATES MESSAGE LOADING ALPHA USED VARIOUSLY TO GENERATE AND INSERT NEH MSGS USED BY SIMULATOR TO MAINTAIN LOADING I THE SIHULATOR $1 I CONTINUES SIMULATION INITIATED BY SIMULB I INTRODUCES MESSAGE SINKS I INTRODUCES MESSAGE SOURCES I DISPLAYS DISTRIBUTION I DISPLAYS TRAFFIC FLOW I DISPLAYS STACK BATTING TIME DIST DISPLAYS DISTRIBUTIONS I SETS HHAX TD VALUE THAT INSURES DESIRED DROP RATE INITIALIZES ALL COUNTERS ETC I DISPLAYS THE BEST BEST-PATH DIST COHPUTES BEST DIST COMPUTES AVERAGE AND VARIANCE OF DIST APPLIES MODELB AND DISPLAYS DIST I APPLIES MODELA AND PAGE 2 FACE 3 PCUL LIIERALS PASKS SHIICFES Etc 7 APARAM PARAPETERS 7 - lw TABLES LISTS AND TABLES USED BY VARICLS 77 BIND NCBIND CFOKE NCCHOK FLOR ADAPT NCOAPT HFAX HEAVE RGH COLUMN TPHAX TPHIN STACK HPRIME GRAIN IMPAIR SOURCE SINK LIST OF MACRO-DIRECTIVES ALL MACROS PRESERVE AND SENSE MEANS EITHER OF I INTEGER 2 LOCATION 3 LOCATION TAG MACRDS FOR SETTING PARAPS NO ADAPTATION TO BE USED unwound unhi- HACROS TO CEFINE STATIONS STATION IS TO BE ASSIGNED AS A MESSAGE SOURCE IOR SINKIHITH PROBABILITY N K A DECIHAL FRACTION N K PAGE L PAGE 5 HACROS IO DEFINE LINKS TO BE ADDFC 0R DELETED LINK LINK FRCM SIATICN N1 LINK NR Kl TC SIATICN NR K2 IS TO BE ADDED CLT SIMUL CONT MCOELA MODELB BESTHO SETHMX PRINT PRINT PRINT MACRC DIRECTIVES MEANS MEANS OF SPECIAL-LINK HHERE IL CONTAINS LOCATION OF FIRST SPECIAL OF SPECIAL LINKS AND 0R IMPLIES NO LINKS I REFERS TC EITHER LOCATION OR INTEGER E I L START SI SIMULATION RUN FOR I OR II CYCLES CONTINUE SIMUL FOR I OR CYCLES APPLY MODEL A DISPLAY DIST APPLY MODEL 8 DISPLAY DIST GENERATE HO-TABLE BY ALGORITHM DISPLAY DIST HBAR USED IMMEDIATELY AFTER APPLICATION OF MODEL A OR 8 TO SET HMAX TO A VALUE TFAT CN BASIS OF THE APPLICABLE RESULTSICISTRIBLTICAI HILL INSURE A FRACTICNAL NCT EXCEEDIAU ILI EXITS IO IF NO SUCH VALUE EXISTS MAY ALSO BE USED AFTER OR DURING SIMULATION RCA TO ADJUST HMAX SIDIST DIST OF OF MSGS BY SI SIFLOH TRAFFIC GENERATED BY SI SIHAIT DIST OF STACK HAITING TIMES PAGE 6 page 7 BEGINNING OF NETWORK NETPGM TSX TC DEFINE SUPERVISDRY PRUGRAF l TRA SYSTEM PRCTECTICN DUMP 1ADDTXL CURE 7 STL ll TRA 2 4 PANEL ERROR STL 2 TSK DUMP 4 3 PZE IABLES ok FSX CUMP 4 OS PIE LINTBL 6 TSX 7 PZE BUSY 8 TSX O9 PZE 10 TSX CUMP 4 ll PZE 12 TSX 13 PIE 14 TSX DUM9 4 15 PZE FUTBLE 16 TSX DUMP 4 #17 PZE SIDTBL 18 TSX DUHP94 f19 PZE 20 TSX DUMP 4 Zl PZE 22 TSX UUMP 4 23 PZE PUUL 24 15X DUMP 4 25 PZE PARAM 26 TSX 927 TSX 028 TSX SIHAIT34 #29 TRA SYSTEM PARSET PRSZ 10 11 12 13 14 15 15 17 13 19 20 21 22 23 24 25 26 9951 1 PR53 1 2 3 4 5 6 SXA CLA- ARS STA CLA ADD STA ADD STA CLA 51A STT PCX TXP CAL ANA CA5 LDO LDC SSP CAS TRA IRA TRA XCA PXA LLS SUB TPL PXA STA PXA LLS XCA SIQ IRA XCA SSP CAS TRA NOP ORA FAD PAGE 8 PARSET USED TO SET ALL PARAHS CALL SEOU STL EXIT TXL PARSET PARAM NAPE TXL 1 CR 2 SAVES INC SENSE PRSX 4 EXIT 18 EXII PRSZ Exlt to PRS4 PRS4 9254 4 PRS3 4 0 SYSORG K H6 PRSG PRSQ PR54 K M2 n 2 IIO IIG PRSX K M2 n 4 KINTI PARAN NAME FETCH ARGLPENTS LDC 0F NEH VALLEICR VALLE ITSELF C l DR 2 SETTING FLOATING PCIKT CUANTITTES ELSE TEST IF VALLE OR LCC UF VALUE VALLE VALUE LCC CF VALLE PAGE 9 07 STU PRSX 1 IRA EXIT PR34 PIE EXIT ENTRY EN4 EN3 1 2 3 EN2 010 ENS ENX 1 ERROR 1 2 3 4 5 P26 SHT TRA IRA CLA ALS STD SXA POX Ix SXA PDX TXI SKA SKA PDX CLA STU TIX CLA STD- YSX TSX ISX TSX ISX ISX TRA AXT TRA- ARS STA LXA TRA ENIRY USED CALL SEQU 5 0 5 9 2 SYSYEM EXIT 18 ENX 4 EXIT 4 EN3 4 4 I l 4 ulc QENQIIQ EXIT 4 4 I lg4 l 004 EN4u4gl EN5 4 EN3 ERR0R94 ERROR 4 ERROR 4 ENX Opq EXIT 1 4 EN3 18 IOZ ENX 4 IIO PAGE 10 FOR ALL MACRO DIRECTIVES STL EXIT TXL CF CALL SECU 15X PR0CESSOR94 CALLING SEOU FOR PROCESSOR MAX CALL SEQU LENGTH I 8 EXCESS VINE IESI FINI PRES 1 PRESET PRO 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 PARAPS PAGE 11 PRESET VALIDATES PARAMS DISPLAYS PARAMS INITIALIZES NET AND ALLOCATES STORAGE CALL SEOU TSX PIE LOC OF FIRST SPEC OF LINKS RETURN IF STORAGE EXCEEDED CR NORMAL RETURN STL ESPY ENTRY FROM SIMLLATCR TRA PRO STZ DSPY ENTRY FROM MODELS AND BEGIN 307 1 TXL SLBROUTINE LINKAGE CLA 1 5 STU PR5 SET RANDOM ANO SET ACTIVITY LEVELS CLA TPMAX SUB TPMIN SSP ORA KINTI FAD KINTI SUB KINT3 ITPMAX-TPMINIIZ STO K T1 CLA GRAIN ORA KINTI FAD KINTI ML 3 MESSAGE LENGTH STO K T2 FAD K T2 FAD K T1 FDP K T2 8 ACTIVITY FACTOR 5T0 FACTOR FMP IMPARE ACTIVITY LEVEL STD ALPHA STD MAXACT CLA RANDOM LBT CLA K R SLH RANDOM SLH RND NZT DSPY TRA PR7 DISPLAY PARAMETERS TSX TRA PR7 PARAMS PRINTS PARAMETER VALUES BEGIN 1 7 1 TXL SLBROUTINE LINKAGE 10 11 12 13 15 16 17 XEJECT STL AXT AXT XPRINT STL PZE PZE le TIX XPRINT STL PZE PZE TIX XPRINT STL PZE PZE AXT AXT ZET AXT XPRINT STL PZE PIE TXI TXH RETURN TRA SYSUED 4 2 0 2 SYSUED 91019 1 SYSDED PM lcl F 2 SYSUED P ggl 0 492 31 1 1 6 2 SYSUED lpZol PARAHS FLUSH OUTPUT BUFFERS STL TSX PZE TSX PIE SYSMIT STZ SYSIBC TSX PZE STR STZ TEST IND SET CONNECTIVITY LXA TXH ' 2g490 TRA PRX TXL TRA PRX LAC CLA STU LINKS TEST LINK-LENGTH LIMITS PAGE 12 018 4 CLA TPHAX 2 IRA PRX CA5 TPHIN TRA TRA n 2 IRA PRX ADD GRAIN ADD K6A1 CA5 TPHIGH PRX NUP TEST LIMITS CLA MAXHU ALS 3 TNZ IRA PRX CA5 HUHII CLA HUHII NCP 5Y0 HUHAX CLA INITHU ALS 3 CAS HUHAX TRA PRX NUP STU HUHEI AXT STZ CLEAR STCRE TIX -lolol LXD CLEAR COLNTS STZ TIX AXT TPU 1 CLEAR HEADS STZ Tpol TIX ltlol SKA TSX INL04 SE1 LINK TABLE TSX GENERATE STCRAGE HAP TRA PRX DRAT NZT NUDES TEST VALIDITY OF PARAHS TRA PRX NIT LINES TRA PRX NZT H555 TRA PRX 75X SET LINE TIBLE TSX SET AND LINKS PIE 00p 0 DEFINES SPECIAL LINKS TRA PRX HDHEI TR PAGE 13 10 11 12 NON CALCULATE EXACT LEADING FROM TRUE NR 0F LIMKS LDC NODES HPY STQ K T4 LDQ PXA DVP NUUES XCA 5T0 K T3 XCA HPY MSGS DVP CAL ARS 19 ANA K H6 TLQ i 2 XCA 5T0 HSGS EXACT LOADING STU LOAD CLA HUNCNT SUB 5T0 HUNCNT ILLCT EXTRA BUFFERS 1F STORAGE AVAILABLE LAC TXL PR4 1 255 STL SXD 5 l LXI TH7gl SKA ' 231 TSX PIE STR RETURN PRO TRA Paco DUMP TABLES TSX DUHP PARIH TSX RETURN 1 8C1 BCI IIBIND 8C1 1 10191 IIALPHA 8C1 IUIHPAIR 5C1 8C1 5C1 IIHEAVE 3C1 BCI PAGE 1h PM 13 014 15 16 8C1 BCI pace 15 INL INLO INLZ 1 2 INL PRESETS LINK TABLE AS FCT OF COLUPN DIN CALL SEQU TSX TRA BEGIN TXL CLA STA PAC AXT AXT SXD PXA STA PAC PIA STA TXI AXT TIX RETURN TRA 01 1 7 530'0 CX INLI ll 4 4 192 cl 2 2 0 1 1 Inc INL3g ol INLO RETURN INL04 LINKAGE PAGE 15 INS INSO 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 43 44 45 PAGE 17 INS COMPUTES STORAGE MAP AS FUNCTION OF CK CULLMN DIP RX LINKS LINKS PER NUDE PERCENT MSG ACTIVITY CALL SEC TSX INS 4 RETURN IF STORE EXCEEDED NORMAL RETLRN TRA i 1 BEGIN 2 7 TXL ' 500n0 LINKAGE LDQ STD LINES DF NDDES LINE TABLE LENGTH LRS 3 STQ NDDES NR OF NDCES CALCULATE MSG LOADING USING APPARANT NR DF LIAKS MPY LINKS XCA ORA KINTI FAD KINTI XCA CLA ALPHA CAS K M2 IRA NDP STZ ALPHA FHP ALPHA SSP XCA PXA LLS 8 SUB KINTZ TPL 5MSG STG NEEDED FCR NCDELS ADD K A1 STD MSGS DESIRED NR BF PSGS NEXT ALLUCATE STORAGE FOR ALL TABLES ADD RX ALLCH EXTRA STCRAGE ADD RX FUR POSSIBLE HINDING ADD CX 0F CDARSELY CUNRECTED ADD CX NETS OF RED 2 FCR EXANFLE ALS LENGTH OF MESSAGE TABLE PAX 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 67 88 89 90 91 92 93 94 95 96 97 98 99 SXD ADD ADD STD LXA SXD ADC STA ADD STA STA STA ADD STD CLA CA5 TRA TRA STD STD ADD STA STA STA ADD ADD STA STA STA ADD ADD STA STA STA NZT TRA ADD ADD STA STA STA SUB PAX ADD SXD ADD STU ADD STA STA STA ADD STD ADD BASE LINTBL LINES K A7 LINEA LINED LINEC NCDES K H5 TNSX INSX SKH SCH NUCTBL NIA NIB NIC NCDES Kuhl NZA N23 NZC NCDES N3A N38 N3C SNAP n 6 NCDES KgAl NQA NQB N4C NUDTBL ol HUDTBL HAXHU HCDA HUDB FUDC HAXHU PAGE 18 TOP OF LINE TABLE BASE CF LINE TABLE TCP DF NUDE TABLE CVERSIZF MET ALLOCATE TABLE 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 4138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 STA STA STA LXA SXD SXD ADD STD ADD STA STA STA ADD ADC STA STA STA ADD STD ADD STA STA STA ADD ADD STA STA STA STZ STZ STZ LXA SXD TXI SXD SXD ADD STU ADD ADD STA STA STA LXA SXD ADD STU CAS TRA TRA CAS TRA TRA STDA STDB STDC SCIB SCIC SSLIM SCZA SCZB SCZC SKIB SKZA SKZB SKZC SOURCE SINK SKCUH SCCUH SSLi vl 5 101 BUSY LINES K A7 BUSYA BUSYB BUSYC LINESDI KoAl UPPER INSX INSX LUHER INSX PAGE 19 PAGE 20 154 TRA INSX 155 LXA 156 PXU 1 '15 ADD NUDES 158 STD NBA PRESET REFERENCE IABLE 159 SUB 160 5-20191 161 CLA LINEI 162 ABC 01 163 SUB LINES 164 STA BUYTOH 165 ADD LINES 166 SUB K A8 167 STA LEFT RETURN INSO 168 TRA RETURN AXT 1 4 TRA BEGIN IXL LXA LXA AXT LDC PXA LLS RQL TNX IIX IRA LXA SXC CAL LDQ AXT TQP RQL TOP DRSI HQL TNX 11x TRA LXA SXA AXT AXT LDQ TQP CR5- RQL FOP URSI RQL TNX TXI fix LXA Ix PAGE 21 IA INITIALIZES LINE TABLE IPAGINARY LINES ARE MADE BUSY CALL SECL TSX IA 4 RETLRN CCAN CCNKECTIVITY TYPF DESCRIBED '41 1 7 ' 5 000 LINKAGE 8 4 0 BUSY-FLAG OFF FCR REAL LINE CN FUR IPAG LIKES 1 IA3 2 1 520491 1A1 SET BCUKEARIES IA9 2 K MZE B T 8 4 BUTTON 18 n 2 TOP 19 1A5o4nl 101 n 0 2 8 4 SIDES n 2 LINEI RIGHT 18 LEFT 19 10 50 LINES 1 DU SAVE FUR BUSY TABLE 101 7 LINEA 4 05 6 7 STD- TKH RETURN TRA BUSYA 101v'l 3vll7 IAO PAGE 22 LINK 11 2 11ILOO 1 2 3 II BEGIN TXL CLA SUB ADD STU CLA Pox IXL Ax SXA STL PAX SXD SKA LXA SXD SXD CLA PAX PDX IXL TXL TXH TXH TPL CLA SID- STO- STD- ZET TRA SKA LXA PAGE 23 IL INSERTS NEH LINKAGES ASSIGNS FROM UNIFORM DIST BTHN TP-BCUNDS TO ALL REAL CALL SEOU AND POINTS IMAGE LINES AT EACH CTPER TSX IL34 PIE A003 ERROR RETLRN RETURN HHERE 8 NR OF SPECIAL LINKS A ABDRESS OF FIRST LINK SPECIFIER LINKS FROM TO ARE SPECIFIED BY oJloIngZ 3 7 '95'0'0 TPHAX TPHIN 1 1 K T2 g Iil l 0 IL134 loZo 9 0 1 I110 K MZE LINES LINEC BUSYB BUSYC BIND IRIS IAlSll SUBRCUTINE LINKAGE NO SPECIAL LINKS SET RETURN SWITCH HIGHEST LINE NR GET LINK SPECIFIER II2 J2 ARE LINES HITHIN BCUNDS TO IAIC IF LINK CUT LINK TEST FOR EDGE-BINDING TO BE BOLNO NON SET RETURN SWITCH AND BEGIN ORDINARY LINKS 4 Al 1 IAID 1 1 3 4 5 IA13 10 11 12 13 14 15 16 17 1A16 1 2 3 9 1115 10 011 12 13 TMI TNZ LDO MPY STQ MPY ADD ADD ALS ZET TRA SID PXA LGR PAX PXA LGR CAO SXD TXI XCL PXA LGL PAX CLA PXA STOI PXA STD- TXI TXH RETURN TRA RETURN AXT AXT SXA CLA STD STD ALS STD SSM STD CLA STD STD XCA MPY K T2 LINEB IAIS 1115 RND K R RND IL T TPMIN GRAIN 18 LINEB K T2 Alb '2 3 4 3 LINK 1 1 n 1 1 4 3 KCII LINEC 2 BUSYC 4 BUSYB IL ILgl 1 4 IA17 1 CX 3 01 0-3 RUH oLS l LD-3 PAGE 2% IGNORE DEAD LINES IGNORE PROCESSED LINES TP MSG LENGTH USED AS TP SET TP SPECIAL LINE GENERATE IMAGE LINE NR SAME TP TD IMAGE LINE IMAGES POINT TO EACH OTHER RETURN SHITCH BINDING EDGES SET RETURN SHITCH COLUMN BECOMES TDP-EDGE-COUNT RIGHT-SIDE DELTA AND SCALED LEFT-SIDE DELTA 1- RDH BECOMES SIDE-COUNTS RON COLUMN ISCALEDI 14 15 16 17 18 19 20 21 22 23 25 26 27 23 29 30 31 32 33 34 35 36 31 33 39 1220 10 11 1119 1 2 3 IAZI 1 2 3 4 STQ XCA ALS ADD SUB ORA STD CLA ALS ADD ALS ADD ORA STD CLA ADD SUB SID ALS ADD SUB SUB ORA SID TRA AXT TNX SXA CLA ALS ADD 5T0 LDO CLA PAX XCA TXI AXT TNX CLA ADD STD SXA PAX PDX TRA K TI 8 K A16 LKZ-Z IT LD-3 OLD-3 LKI-S 0LK2-3 KOYI K AB K TI 18 Kutl LD-3 oLKl-l LKZ-I 4 1 no 1 IL00 1 1 IAZOII L gl 18 OLD 1 K TZ LK2 I Ls 1 II lAZl l -2 500 1 IAZOulol 02 0Q IAID p305 25 LINKIC 2 3C II INITIALIZE EDGE-COUNT FINI IF ALL EDGES BOUND NEH INCREMENT FIRST LINK IN NEXT EDGE NEH BUT IF EDGE HAS BEEN BCUKD LINK TO SET LINKS IN KEY BEGIN CLA ADD ARS STU CAL- XCA CLA- SSP 1L0 XCA CAS TRA IRA STU SIG 511 CLA TOP TRA ADD XCA CLA ADD STD XCA TXI IXH CAS TRA IRA CAS TRA TRA TRA STA SUB PAX SXD PAGE 26 CHAINS REAL LINES TU H0 TABLE IS PRESET FRUN UNIFORM DIST A AND B CALL SEQU FSX Hyk A RETLRN 1F STCRE EXCEECED NORMAL RETURN 4 7 ' 5v0p0 SUBRUUT1NE NUDES 2 NR PER HU-TABLE ENTRY HULINE AT FOUR 1IEVS PER HERD 2 4 1 4 1LLEGAL HO BCUNDS IHA IHB 19107 HUYBLE LINEA 5 2 1H2 NU ENTRIES FCR 1PAG LINES LINEA HOLINE HONCNT NDDES 1t1r 1 1H1 1 7 UPPER IHX IHX LOWER 1H3 1HX IHX 1H7 HUTBLE o1 1H6 1H4 1H5 1H9 CLA FIE SUB YNZ CLA XCA HPY SID STC CAL ALS ORA ALS ORA ALS ORA TIX ZET NZT IRA TRA TSX RETURN IRA SUB SLH LXA 5T1 AXT LDQ MPY 5T0 MPY ADD ANA TXL TXI CAL ORS TRA GRS ADD 510 PET IRA CLA ADD 5T0 CAL ALS SLH TRA 1H8 n 3 1HA FDTUTI H0101 9 9 9 IPA 1h 1H8 USPY 1H6 1H HGINC 4 2 RND K R RND 1H0 IHB ' 2o430 4040'1 IHC 1H9 IHC 0 4 KOAI HDTUTI IHC IHT 2 1 9 IHC IHS PAGE 27 IF HPRIME IS ZERC CR ENIEREC FRCP NCDELS CR BEST-PATH USE BESF-PATH ALGCRITHM ELSE FILL PRESET TC BEST VALLPS 1 2 3 u SLH 001 IXH LXA 1H4lltl RETURN 1H YRA rel RETURN Hvl AXT 1'4 PAGE 28 BEGIN TXL CLA STU CLA STU LXA SXA LXA CLA STU- TIX 5T1 STL TRA STZ LXA STZ SKA CLA- STD AXT PXA ALS PAX SXD CLA- PDX TXL PXA STDPRESETS HO TABLE TO CALL SEQ 1'7 5 030 UPDAIE BHX UPDATE K U 4 HUHAX N28 -112'l NZC BH A 8H3 BH A NUDE514 K N 4 NZC B HU 3 2 4 3 Bh9p4 BUSYC 3H6 II BUSYC o1 KCHU B HO n 4 9 3 B HO HOVER K L 4 BHIO 8-HO ISX BH 4 RETURN PAGE 29 VALUES SUBRCUTINE LINKAGE SAVE HO-IABLE UPDATING ALGCRIIHN USE MIN AS UPDATER I NR OF RECYCLE ON I HOIK HAXHC UIUIN HOII ACIION-TOGGLE OFF HOVE-IOGGLE ON INTO INNER LOOP HIIH I BEGIN IANER LOOP ACTION OFF RECYCLE ON J FOVE IS OFF B HO HOIJ C COUNT FRCF 8-K IO 1 IS REL PCS OF IN LINE TABLE IGNORE IF LINE DEAD IGNORE IF NO PSG Ch LINE ERASE MSG FOR FLIURF BY FOVER B HO MINIB HC HC CF #56 MOVE IS CN IF DECREASES SAVE LINE NR UPDATE ENTRY INCREMENI Kg IESI AND RECYCLE LESS THAN 8 TEST MOVE TOGGLE OFF NOOE SEADS AC FSGS ON EH10 10 11 LXA STOI ADD ALS STU CLA- THI PAX CLA STD- TXL STL LXA TIX ZET IRA LXA TIX LXA STZI CLA STD RETURN TRA PZE N28 18 K H0 BUSYC 8H9 2 KOHO BUSYB 5 2 4 000 BH A K N 4 8H4 4 1 BH A BHZ Ko ol9 BHl 4 l NZC lilinl BHX UPDATE BH RESET HCIJ AND INC B HC - - SENT TO ALL IGNORE DEAD LINES IMAGE LINE NSGS SENT T0 0 DECREMENT AND RECYCLE RECYCLE IKNER LCCP CN TEST ACTION CN REDO IKNFR LCCP CFF CN I FINI CLEAR THINGS RESTORE UPDATING ALGORITHM PAGE 30 pace 31 HCVER MOVES MESSAGES THRU NET UPDATES HO TABLE FOR REROUTED HSGS STACKS REROUTED HSGS AT APPROPRIATE NODE PROCESSES DELIVERED FSGS CALL SEQ IEC HCVER NORMAL RETURN SAVES IRZ AND SENS PAO TSX BEGIN TXL LXA TIX SXA CLA STZ PDX TRA LXD TXH RETURN TRA CLA STE SKA PAX PAX STA ARS PAX STA CLA- LDQ PXA LGL STD PXA LGL STC PXA LGL STD PXA LGL STD PXA LGL ADD STU XEC CLA SUB TNZ XEC IRA CLA CAS PAGE 32 NA 15 A HUVER 1 791 ' 790 0 LINKAGE TP 1 ' 1v1u1 NEXT TRAFFIC LIST FOCULC TPL TP31 TP 1 2 MAO END TRAFFIC HSGZIZ TP 1 EFFERENT LIKE NR BUSYA '1 IMAGE LINE K L 3 '4 K N AFFERENT NUDE NIC CROP MSG MAch 7 K U ORIGIN K D CESTINATICN K P PRIORITY K ST TIME DELAYED INSTACKS HDINC H0 HOVER UPDATE HC TABLE RECORD RECORD ARRIVAL HCHAX DROP MSG IF hO EXCESSIVE FA2 1 2 3 oh TRA NDP CAL ADD SLH XEC CAS IRA TRA XEC TRA CLA STD IRA HA2 $6102 M50102 CELIVR MAI HCHII n 3 CROP HA1 HCHII K HD MAI INC H0 IN MSG TABLE STACK MSG pass 33 PAGE 31 HOVER UPDATES FOR LINE 1 PESSAGE AFTER INCREHENTING H0 IN PSG TABLE CALL SEQ XEC HOVER RETURN TK L 8 I IK HSG 3 8 CURRENT NUDE TK OI ORIGINTJ IK HOI IK D DESTIJ TK P 8 PRIORITYIJ SAVES 1R2 AND SENS HA HAO YSX BEGIN TXL CLA CAS TRA STZ SUB PAC PXA LGL PAX LXA CLAI STA CAL XEC ANA LDO SXA XEC TRA AXT 5T0 CAL XEC COM ANA- STGI ORSI 615 A00 A00 SLH TZE PBT TRA CLA ADD STU EOU RETURN IRA CLA SUB SLH RETURN TRA HA 5 A HUVER 001 4 10701 K 0 K N 0 2 K HU K A1 2 9h 2 92 KOLI LINEA Kg UPDATE HA2 01 K H7 HA4 HA4 HA4 HA 1 K H0 HUTOT HUTDT HA5 HA3 HA5 HGIDTI HUIOTI HA2 HAO HOTDTI PAD pass 35 SUBRULTINE LINKAGE REL HRD NR CF HRI CRIGIN POSITION IN 0F ITEN HO HDRD SHIFT EXECUIE LPDATING ALGCRITHF MIN LRN LRNO 10 011 12 TLO TSX STD XCA SUB TZE XCA TOP MPY TRA MPY ADD XGA CLA TIA PAGE 35 UPDATE EXECUTES MD-TABLE LPDATTNG ALGORITHM CALL SEQ ENTRY EXIT XEC UPDATE RETURN IF NO CHANGE IN HG-TABLE RETURN IF TABLE TO BE UPDATED AGE 8 OLD ENTRY M0 HD OF MESSAGE M0 NEH ENTRY SAVES AND SENSE MIN UPDATES BY MAKING NEH ENTRY HA1 LRN UPDATES H0 ENTRIES MSG HO - IS REG H0 8 HO KZITMSG H0 - H0 IF MSG HU - H0 TS PCS LRNO 4 LRNI 2 4 8 0F MSG 1-- HD ENTRY MSG H0 - HC N0 CHANGE LEARNING - USE Kl FDRGETTING - USE K2 DELIVR APPENDS MESSAGE T0 TRAFFIC STACK FOR CURRENT NUDE CALL SEQU XEC DELIVR RETURN INITIAL CONDITIONS AS FOR HOVER SAVES 1R1 1R2 AND SENS pass 37 DELIVR PAGE 38 DA STACKS MESSAGES AS DECREMENT ADDRESS OF NCDEIIJ POINTS TC FIRST ENROUTE INEHI MSG ON STACK FOR NUDE J FOR ALL HSGS IN STACK HO IS INCREMENTED AND FSGZ IS PREFIX DECR TAG ADDRESS A ZERO LINE A ZERD POINTER TSX BEGIN 1'701 TXL 7'030 CAL ALS 15 ANA ORA SLH $6202 LXA NIA PDX 4 IET TRA NZT CHOKE IRA DAA PAX 0 TXH PXA 2 NIA RETURN DAO TRA TXH DAZ 4 0 PXD 2 STD NIA RETURN DAD IRA SKA CLA 3529 PDX US TXH DA29A00 AXT 004 PAD 02 STD $52 9 RETURN DAD TRA POINTER TC NEXT MSG INCOMING LINK NUMBER TIRE STACK ORIGINALLY ZERO NR IK L1 INDICATES NEH NSG INDICATES END OF STACK SUBROLTINE LINKAGE STACK-FLAG UN LINK NR IN TAG TEST HSG ENRDUTE PSG NEH MSG ARE HE CFOKING INPUT ND TREAT AS ENROLTE FSG YES - PLACE ON SPECIAL INPUT STACK IS STACK EMPTY - NC YES IS STACK EMPTY - STACK PAGE 39 RA IS A MESSAGE STACK PROCESSOR RA RAD MI 012 RAO3 RAOZ 91 RAOO 1 2 4 05 6 RAOI FDR EACE MESSAGE DN STACK FOR NUDE J RA CHCOSES NDN-BLSY EFFERENT LINE SHALLEST HARDCVER NUMBER TO DESTINATION STACKS ARE USED - A STACK AND A STACK THE LATTER BEING LSED FOR INPLT CHCKING CNLY IF NO LINES ARE AVAILABLE PSG REMAINS CN STACK THE STANDARD STACK IS PROCESSED BEFORE NEH-MESSAGE STACK AND MESSAGES IN LATTER STACK ARE NEVER DROPPED - THUS STACKING AT INPUT IS ENFORCED CALL SEQUENCE XEC RA RETURN SAVES AND SENSE TSX BEGIN 1 701 TXL SUBRUUTINE LINKAGE LXA TXI l I-Iu7 BUSYA FOR ALL LINES THI RAOZ IGNORE DEAD LINES PDX 2 TXL RAOZDZIO IGNORE FREE LINES TXI 1v2v l DECREMENT PXD 2 - BUSY STCI BUSYA COLNTER TNZ RAOZ LINEA FREE LINE IF CCUNT BECCKES ZERO SLH LINEA TIX RA03 1 I LXA NCDESQZ SKA STZ RA O FIRST CYCLE PROCESSES ENRUUTE FSGS STZ BUSY-FLAG DEF STZ RA 5 STACK-LSE FLAG CFF STE NZB CLEAR STACK COUNT NIB STU HSGZ AXT nl SKA RA I I LAST HSG NR CLA PDX '1 TXH RA3 1 0 TEST L00 HSGZ END RQL 18 STQ H562 ZET RA 0 TEST CYCLE IRA RAX LAST FINI STL RA 0 IRA RAOI STU NIB RA3 10 11 12 13 11IIX RETURN TRA SXA IRA ISK LXA TKN SIL ZEI IRA CLAI CAS IRA IRA ADD SIDI CAL ADD SIA SIL CAL ADD SLH IRA CLA LXA SID XEC IRA CLA PAX SIA SIP CAL SIP- CLA ADD ALS ADD SID- SID CLA LXA SID CLA- SID LXA IXI It RAO n 4 FA 4 K AL94 RA g po RA9 N28 STACK RAT RAT K AI N28 MSGZII HSGZII RA 5 STKINC 55101 RAI 552 1 RAalpl $6231 DROP RAI AL34 4 562 1 55201 K HZE LINEC GRAIN K AI 18 BUSYC BUSYC RAB HSGZII RAoltl LINEC Ii3 I 1 1 Iuo PAGE #0 CURRENT PSG NR ARE ALL LINES BUSY YES ORDER AVAIL- LINES FOR ROUTING NR OF AVAILABLE LINES ANY AVAIL LINES NC SET BUSY FLAG TEST CYCLE SECOND CYCLE INPUT STACK FIRST CYCLE STACK IS STACK FULL YES YES NO INCREHENT INCREMENT STACK IN USE INC STACK-TIME CCUNTER DELETE MSG FROP STACK ROLTE FSG OVER THIS LINE LINE NR T0 56 TABLE STACK-FLAG OFF MAKE LINE BUSY MAKE LINE BUSIER BY DELETE HSG FROF STACK SET MSG TP MSG ARRIVES NEXT STATION AT TIME TPILINE BUSYILINE A GRAIN HODLLC TPU STACK MSG ON LIST FOR TIME-FRAME-NR 45 67 8 9 10 11 LXA TRA CLA- ADD STU- IRA RA l l SNAP N48 N48 PAGE 41 FESSAGES PASSING THRL NCDE IF CF FLUH ARE BEING TAKEN BEGIN TXL PXA ALS PAX LDQ LGL PXA LGL STU SUB LGR STA PXA LGL PAX CLA SID AXT CLAI TMI SXA STA AXC CAL NDP ANA STD SIG SXA Itx REIUR TRA PAGE #2 FA COHPILES FOR GIVEN NUDE AND MSG A LIST OF AVAILABLE AFF LINES ORDERED BY INCREASING H C AR H R T DESTINATION NODE OF MSG LINES HAVING IDENTICAL H O NRS ARE ORDERED RANCOHLY HITHIN THEIR COPHON H O NR CALL SEQ TSX FA 4 RETURN lIRl MESSAGE NR IK HSG IIRZI NUDE NR IK N EXIT IK ALI 3 NR AVAILABLE LINES BEST CHOICE OF LINES 3 LINE NR BITS 0-9 8 BITS 10-21 I ASSOC HO NR FOR DESI NCDE 1 7 n 5g000 SUBROUTINE LINKAGE K AL 2 92 FIRST LINE NR FROM SOURCE NODE DESTINATION NODE A2 REL HO HORD HRT TC DESI NODE 4 POSITION IN NORD CF ITEM SHIFT LINEB RECYCLE IF LINE BUSY FETCH H0 HDRD SHIFT SAVE AL ENTRY PZE INSERT NEH AL ENTRY FA PAGE #3 FB UPDATES AL LIST INSERTING ENIRY FOUND IN IALHDI ORDERED BY h D NR IN IALFCI AL COUNT IN BEGIN FB IXL SUBRCUTINE LINKAGE 3 LXI 9 IXH 20130 010 TXI FBZalol CIS ALHU #3 TXI INSERT ABCVE HERE 4 TRA F33 EQUALITY - RESCLVE CONFLICT F36 TIX FBIvlol F32 SXC SAVE PCIRTER 1 LXA 2 TXI INCREHENI CCUNTER 3 SKA K AL91 F34 TXL 1 #2 5T0 ALol MOVE UP 3 IXI F35 ALHD INSERT HERE #1 STU ALol RETURN IQP F86 FLIP CUIN TU RESULVE CUNFLICI 02 TXI F82 1 I DROP BRO 8 9 10 11 12 013 14 15 16 18 019 20 21 22 023 24 25 026 TSX DEG TXL LXA CAL AXT PBT AXT ARS ANA SSH ORA STO CLA ADD STO CLA SUB STD TSX RET TRA PAGE Ah DROP APPENDS DISCARDED TRAFFIC TO USING MSG TABLE AS STACK M562 BECOMES PZE CURRENT NODE POINTER TC NEXT PSG HHERE 8 4 HSG IN STACK ELSE 0 TOTAL DROPS AND DROPS AT NUDE ARE INCREMENTEC CALL SEOU XEC DROP RETURN IK N NOCE NR K FSG I #56 NR SAVES 1R1 1R2 AND SENSE I lg4 IN 1'7 '95t0'0 LINKAGE $5201 02 VSG INSTACK 1 2 ND 18 Kc TAG 4 IF STACK PREFIX 3 K N ADD 3 NOCE $62 1 CULNT DROPS DR URN DRO RECORD RCO 8 9 10 11 12 13 lk 15 16 11 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 35 36 37 38 39 k0 41 0 3 RECORD APPENDS COMPLETED TRAFFIC 10 ARRIVAL-LIST CALL SEQ XEC RECORD RETURN K FSG MSG NR 15 BEGIN IXL LXA CLA SIG CLA ADD SID CLA ADD 5T0 P31 TRA CLA ADD STD CLA TZE ARS PAX ADD STD- CLA PAX CA5 NUP LXA CLAI ADD STU- CLA SUB $10 st RETURN IRA SAVES 1R1 IRZ AND SENSE 59010 K HSG 2 K HZE 552 2 ARRCNI KoRl ARRHU ARRHO n 4 ARRHDI ARRHOI K HC 5 6 3 1 HODA HUDA K ST 1 5 1 1 1 HAXHO HAXHO 1 SIDA 510A AR RCO SLBRULTINE LINKAGE COUNT ARRIVALS PAGE #5 GENERATES A RANDOM NUDE NR CALL SEQ YSX GNuk RETURN EXIT IACC 8 NUDE NR BEGIN TXL LDC HPY STQ MPY ADC RETURN TRA SAVES 1R1 1R2 AND SENSE ' 3v0g0 SUBRULTINE LINKAGE RND KOR RND NDDES K A1 GN PAGE 1 6 PAGF 47 CHAIN ADDS MSG TO TOP OF LIST CHAINED VIA EECR FEAD 0F LIST IS PIE LAST MSG NR 9 9 FIRST NSC NR CALL SEC TSX PZE LIST-NAME MAY BE TAGGEC RETURN SAVES 1R1 SENS BEGIN 29 CHIIN TXL 5 30090 SLBRUUTINE LINKAGE 4 LOG 194 5 CLA K HSG 6 1 4 UPCATE TAIL 07 ALS 18 3 99 TNZ CH1 10 XCA EMPTY LIST ll STD 1 HEAD 3 TAIL 012 TRA CH3 CH1 PAX 4 1 XCA 02 STU CHAIN LAST TC CLRRENT CH3 PCX 04 1 PXA 2 STD 562 4 CURRENT BECUPES LAST RETURN CHATN CH2 TRA NRPRESETS MSG STACKS AND GENERATES DESIRED 0F H555 CALL SEQ BEGIN 1 7 TXL HSGS ALS VAC '1 $72 SKA TSX NDP 001 192 TXH 610110 512 AR STZ DR 5'1 BL RETURN HG IRA H641 TSX RETURN MG 4 SUBRCLIINE LINKAGE SYSIEM LCACEC PAGE 1 8 ACTIVE 8 9 10 11 12 13 014 415 16 18 19 20 21 22 23 24 25 026 ACTVI 1 2 03 6 49 910 ll ACTIVE RESETS CALL SEQU TSX ACTIVEO4 RETURN BEGIN 07 TXL LDQ INPARE FMP FACTOR CA5 HAXACT TRA TRA TRA '45 CLA MAXACT STU ALPHA CLA 55$ TRA ACTVI STU ALPHA FDP HAXACT PXA LLS 8 SUB KINTZ STA PXA LRS 0 H555 STU LOAD NZT PRETGL RETURN ACTIVE TRA XEJECT STL SYSUEC XPRINT 0'2 STL SYSUED PZE PZE RETURN ACTIVE TRA ACTIVITY LEVELS LINKAGE IS DESIRED ACTIVITY TCC LARGE YES YES NO LSE MAXIPUN PAGE 49 BEG TXL LXA IXL LXA LDQ MPY STD XCA TXI CAS TRA NDP CAS TRA IRA TIX LDC HPY STQ HPY ADC PAX CLA STZ STA PAX CLA THI LXA TXL LIA LDQ HPY STQ XCA TXI CAS IRA NDP CA5 TRA IRA PAGE 50 GM GENERATES A RANDOM MSG MSG NR IS IK FSGI IF DESIRED NSG LEADING PAS NCT BEEN ATTAINED MSG ENIERS SYSIEM VIA DELIVR - OTHERWISE MSG IS PLACED ON DROP LIST CALL SEQU IN 217 GM3I1IO RND K R RND I lg gl I SCIA 5M3 SCZA 6N2 6M2 6M4 1 l RND K R RND SCH KOAI 4 N3C K N K N 4 NIC GHI 6M1 1 o SKH 4 RND K R RND lv ol SKI 6H7 0 SKZA 6M6 6M6 TSX RETURNED IF LOADED NORMAL RETURN LINKAGE GENERATE CRIGIA NC DIST LSE DIST LSE LNIFCRF CISI DISCARD IF DEAD GENERATE DESTINATICN NU SINK DIST LSE SINK DIST TIX LDQ MPY STQ MPY ADD PAX CLAI ARS CA5 TRA TRA STU ALS XCL CLA LGR LXA STQ STZ CLA CA5 IRA IRA ADD STU STZ XEC RETURN TRA ISX PZE RETURN AXT RND K R RND SKH KCAI K MSG Z LCAD GH9 6M9 K L DELIVR GM DR Gle 1 4 pace 51 DISCARD IF IRCESTVCUS ORG DESY IS SYSTEP LOADED YES YES NC INITIALIZE FCR CELIVR STACK PESSAGE MSG TO DROP LISI BEGIN TXL LXD TXL CLA STD SXA TSX RETURN TRA TRA LXD TXL CLA STD SXA TSX RETURN TRA TRA STZ STZ TRA RM REPLACES DROPPED AND DELIVERED MSGS HITH RANDDMELY INITIATED FRESH MSGS CALL SEQU 107 ARpl RMZ 1 0 $52 1 AR RH RMI RH3'lv0 $62 1 DR K HSG 1 G gk RM RHZ AR DR SLBROLTINE LINKAGE SYSTEM LOADED SYSTEM LOADED PAGE 52 SIM SIP SIM CON NGO NGC ULB SPACE -2 -l 1 PAGE 53 SIMULB CYCLES THRU SIMULATOR YIPES AFTER NET CALL SEQU TSX SIMCLE 4 PZE OR LOC 0F PZE VFD HBEIK OR LCC OF RETURN IF NUGC NORMAL REYURN WHERE CONTAINS - LDC OF FIRST SPECIAL OF SPECIAL LINKS AND IMPLIES NO SPECIAL LINKS BEGIN 537 1 TXL 700v0 SUBRCUYINE LINKAGE SIZ CLA 1 4 STU SIHI CLA 3'4 STU $1Ml l CLA 2-4 VIE 2 STU ISX NET DISPLAY PARAVS PZE VRA SIHZ ERROR 571 INITGL TSX PIE VFC H36 RETURN SIMULB TRA RETURN AXT CUNIINUE SINULAIIUN FUR MORE CYCLES CILL SEQU TSX PZE BEGIN 39701 SLBRUUTINE LINKAGE EQU CONT AXT 6N68 N60 NGA PAGE 54 TEST IF IMPLIES LOCATICN BLANK TEST IF NUMERIC IMPLIES LOCATION OITTO NUHERIC IMPLIES EXIT IF ZERO CYCLE COUNT TEST IF FLOATING CONVERT TO INTEGER CALCULATE OUTPUT INTERUPT FREQUENCY FROM CA5 K A48 TRA NGB TRA CAS K A9 TRA NGB NOP TIX CLA 1 4 TRA 1'4 SSP TZE CA5 K SUB KINTZ TPL PXA STA NGD PXA LLS IIO NOP STU N63 LDC N63 ARS 1 TZE STU N63 IRS 1 TIE n 2 STU N53 XCA ZET INITGL TRA NGA STU TSX STZ COUNTS STL INITGL TSX 6 4 TRA ADD NGI STU N51 CLA N53 TIE ADD COUNTS STU CLA HHAX ALS 3 STU HUHAX LDQ FACTOR IS ENTRY VIA SIMULB NO - CONTINUATION YES - CLEAR THINGS PRESET MESSAGES - STACK THEM AT NOOES RESET HHAX IN CASE CHANGED 10 11 012 #13 IFPARE ALPHA n 2 ACTIVE94 LEARN FRACT 4 KFULL K1 FORGET FRACT 4 KFULL K2 MIN ADAPT LRN UPDATE 5 SYSTEM ROUTER MCVER RM 4 COUNTS K A1 COUNTS NGI NGS NGZ NGA 0HDAVG KOTI K T1 K A100 PAGE 55 BEEN CPANGED YES NC YES - CALCULATE NEH ACTIVITY LEVELS RESET LEARN AND FCRGET SET HC-ENTRY LPDATING ALGCRITHF EXCESS TIME TEST OKAY - CONTINUE RCLTE MSGS AT ACDE MOVE MSGS THRU REPLACE PSGS WITH FRESH INC AND TEST CYCLE MEAN UF FC TABLE N61 12 13 14 15 16 17 18 19 20 LLS DVP STU CLA LDQ LLS DVP 5T0 RETURN TRA OCT 10 DROPPC ARRHGI ARRHD ARRAVG NGO 0 use 56 PERCENT PSGS MEAN HC CF DELIVERED MSGS SKT3 SKTS SKTLU APPENES NEH TC SINK IABLF CALL SEC YSX SKTLU 4 PIE NCDE NR DEC PERCENT VSGS IC BE PRFEVPTEC BEGIN 3 7 TXL 50000 LINKAGE CLA 1'4 SID 5C1 TNZ TSX CA5 NCOES TSX NOP CLA 2'4 TSX ERR0R94 STU 5C2 LXA CLA SCI PAX 4 CALIRA TRA I-b SXD l lyl TXL NEH ENTRY 5X0 CHANGING OLD EATRY SXA LXA FIRST TXL DELETE N3C CLC LDC N33 ENTRY 515' N38 XCL N3C NUDES DELEYE SUB 5C1 FRCF LXI SINK SXD VABLE PAX 36 13691 CLAI SKZC STD SCI SUB SKCUH SLH SKCUM O l 2gl PAGE 57 SKYA SCTLU 8 9 10 11 12 13 15 16 17 TXF SKIB SUB 5C1 STCI SKIC CLAI SKZB SUB 5C1 STCI SKZC 1X1 ZET SCZ IRA SKTT SKA TXI 1 111 SXA RETURN SKTLU TRA N3C N3A XCL N3C SKA LXA ly ol SKA CLA SKCUM SKZC CLA 5C2 TUV ACE SKCUM TNO 5 2 TSX 5T0 SKCUM SK1C RETURN SKTLU TRA SCTLU BEG1N 3 7 YXL CLA 194 STD 5C1 TNZ n 2 TSX CA5 NUDES TSX NOP 23 TSX FRAC104 75X CHANGINB ENTRY EELETING ENFRY PERFORMS SAME FUNCTION AS SKTLU FR SOURCES SUBRUUTINE LINKAGE PAGE 58 13 19 20 21 22 23 24 25 26 27 20 29 30 31 32 5012 5013 10 SCTS 5614 SCTI 2 STO LXA CLA FAX ANA CAS TRA TRA IRA SXD IXL SXD SXA LXA Ix TXL CLAI 1 004I STA- XCL TXI CLA SUB LXA SXD PAX Ix CLAG SUB- STD SUB SLH TXH SUB CLA- SUB STOI Ix ZET TRA SKA 1x1 SXA RETURN TRA CLA- SIA- SCZ SCHII SCI 4 NBC K H6 SCI 4 0 2 6 lol SCIIZ N3C N38 N38 N3C SCng g-I NDDES SCI SCT404 6 llboI SCIC SCZC SCI SCCUH SCCUM 102ul SCIB SCI SCIC SCZB SCI SCZC 5C2 SCTT 1049-1 IolsI SCHOI SCTLU NBC N3A N3 PAGE 59 NEH ENTRY CHANGING OLD EATRY FIRST DELETE ULC ENTRY NEXT DELETE TABLE CHANGING ENTRY DELETING ENTRY SCTT XCL SXA LXA SXA CLA STD- CLA TOV ADD TNO TSX RETURN TRA N3C ' lulg'1 SOURCE-4 50URCE 4 SCCUM SCZC 5C2 SCCUH I92 ERRURIQ SCCUH SCIC SCTLU SCTLUOI PAGE 60 SIDIST 3 6 POD 5 6 7 Hoax 8 #10 11 12 13 014 18 21 22 SIFLCH FLHO -PAGE 61 SIDISI PRINTS DISTRIBLTICN 0F OF #565 DELIVERED BY SIMULATOR XEJECT STL XPRINI STL PIE BEGIN IXL CLA ISX TSX RETURN IRA BEGIN TXL LDQ MPY LRS XCA SUB SLH XPRINT SIL PZE XPRINI STL PZE RETURN IRA SYSUEU SYSUED Flo 3 2 194 HUDA HUD 1'7 5'0 0 ARRAVG ARRAVG IO MU HU KII SYSUED F11 l 12 A91 SYSUED HUDX SLBROLIINE LINKAGE LINKAGE FLUH DISPLAYS FLOH IHRU NETHORK MESSAGES PASSED THRU MODES ARE DISPLAYED BEGINNING FIRSI RUN BEGIN IXL EOU NIT IRA XEJECT STL XPRINI SIL PIE CLA SIA LXA SXD 1 7 59090 SIFLUH SNAP 1-4 SYSUED J91 SYSUED NAA FLNI CGLUHN 4 SUBROLIINE LINKAGE '3 2 FLHB 2 03 FLHI FLHZ SIHAIT #10 011 SXD LXA TXL CLA SUB STA XPRINT STL PZE TIX RETURN TRA SIFLOH PRINTS DIST 0F XEJECT STL XPRINT STL PZE CLA BEGIN TXL STA LXA CLA- TNZ TIX RETURN TRA SXD AXT LDC PXA XCA DVP TXL RETURN IRA BEGIN TXL STO HPY RND PIX FLHI COLUMN FLHI SYSOED FLHO SYSOED SYSOEO FIO 5 2 STDA 1'791 700'0 P81 NU P81 PBZ PB P3301 1 1 ltlol PBIDIDI G PB 1 7 5 0 0 0101 K AIOO r2 DELAYS IN STACKS FCR DLVC MSGS SUBROUTINE LINKAGE SUBRUUTINE LINKAGE PAGE 62 PAGE 63 12 '92 00 13 1ng1 14 AXT 17 15 CAL FILL-6 - lb TIX ' 3u2v6 CAL 18 AXT '2 #19 SLH 20 IIX 21 SXA 01 1 XPRINI Col 22 STL SYSUFC 025 PZE 0T 12C 26 L00 UT 27 MPY UT 28 MPY 01 32 STL RETURN PBX 33 TRA SETHHK SEIS TO VALLE INSLRES LESS THAN A FRACTION Kc UF DRCP-CUTS CALL SEQU TSX SETHHX 4 PZE LDC OF K TAG RETURN IF NOGC NORMAL RETLRN BEGIN 3 7 1 SETHVX TXL I 7y0n0 LINKAGE 15 SUB KINIZ 16 STA I04 17 12E 18 TPL 2 4 19 PXA 20 LRS I90 21 510 22 K TZ 23 LXA MAXHD 4 SE11 HUDC 1 PXA 2 XCA 3 DVP ARRCNI 4 XCA 05 06 7 08 9 10 SEIZ 1 2 3 CLEAR 4 5 6 7 8 9 10 011 12 013 14 15 16 17 #18 ADD SIC CA5 TXI TIX SETlphol IXH '53 63 SXA RETURN SETHHX TRA RETURN SEYHPX 1 1 9 CLEAR ZERDES ALL CDUNIS CALL SEQU TSX CLEAR 4 REIURN BEGIN TIL 3'0'0 HAXH014 HCDC STDC TIX -2v ll LXA NZA ZET SNAP NQA TIX 3nlol STZ STZ STZ STZ ARRHOI $71 ARRHU REYURN CLEAR TRA CLEAROI LINKAGE PAGE 64 BESTPO 11 12 13 14 15 16 17 18 19 20 21 HDDIST HTO 'PAGE 65 BESTHO PRESETS HOTABLE TC BEST-PATHS THEN INVDKES HODISTIBELOH CALL SEOU TSX BESTHC94 PZE L TAG RETURN IF NET CAN NOT BE RUN NORMAL RETLRN HHERE CONTAINS LOCATION OF FIRST SPECIAL OF SPECIAL LINKS AND IMPLIES NO SPECIAL LINKS BEGIN TXL 70000 SUBRUUTINE LINKAGE STL NU ACTIVITY CLA 10 T15 i 2 CLA 1 STD TSX PIE TRA TSX RETURN BESTHO TRA RETURN AXT 1 4 COHPUTES AND DISPLAYS THE BEST-PATH DIST FOR THE HOTABLE EXTANT CALL SEQU TSX HDDIST 4 RETURN BEGIN 197 1 TXL 7o090 SUBROUTINE LINKAGE EQU HDDIST TSX HTF 4 COMPETE FDDII TSX COHPUTE HO STAT XEJECT STL SYSOED XPRINT STL svsoeo PIE Flo 2 Hoo PRINT Reruns are TRA Hrc 1 HIF BEGIN TXL ISX LXA SXA PXA ALS FAX SXD CLAO SIA SXA AXT LXA AXT LDQ PXA LGL NZT- TRA CA5- IRA TRA INX IIX Ax TXL 1x1 LXA CLAI IRS CA5 CLA NDP PAX CLAI ADD STZG TIX Ax REYURN IRA 197 NUDESVI 1 3 '1 lolp' LINEA HTZ HT4 HTSQI cl NUDESIZ 4 4 a 0 1 9 N28 n 4 NZB n 2 N23 39201 HTQro tl HF -lplg-l llo 1 NZA 3 HAXHU HAXHO 2 H008 Kohl H008 H77olvl vl HIO 1 1 HVF SUBROUTINE LINKAGE PAGE 66 N18 10 11 12 BEGIN TXL LXA PXA FIX STD SYZ PXA XCA MPYI XCA ADD STO FIX XCA PXA LLS DVP $70 REYURN TRA 59010 HDDA ARRAVG 2 H008 ARRAVG ARRAVG 10 ARRAVG HTS COMPUTE AVG AND CF LINKAGE PAGE 67 NDDELZ PAGE 68 IS COMPUTES AND PRINTS DIST AS FUNCIIDN OF IMPARE CALL SECU TSX PZE RETURN IF NET CAN NOT BE RUN NORMAL RETURN HFERE CONTAINS LOCATION OF FIRST SPECIAL OF SPECIAL LINKS AND INPLIES ND SPECIAL LINKS BEGIN 3g7o1 TXL SLBRUUTINE LINKAGE STL N0 ACIIVITY CLA 1 4 TZE 1 STD 2 INIT NET PZE TRA NO GD EQU MODELZ XEJECI SIL SYSUED XPRINI Jul STL SYSUEC PIE Flo-2'02 XPRINT STL SYSUED PZE IHPARE I CLA IMPARE TSX TRA TSX STD K PII CLA KFULL SUB K PII STC K PI ISX HTF 4 ISX LXA HAXHO 1 HUDA TIX ' lulul SXA HODA PXA XCA DVP ARRCNI SIC HDDA SIZI STDA IIX 60101 AXT p1 SIDA 151 152 153 TSX -STZ STZ STZ AXT CLA PXA SYU AXT 512 ADD STU TIE LXA STU XCA TSX PXA XCA MPY LLS ADD 510 1x1 SKA LXA TXI MPY STD LDGI HPY A00 510- TIX TRA TSX RETURN IRA REYURN AXT MU ARRAVG 1 1 K P1 SIDA 01 TS T1 KOTZ HCDA STDA K TZ K TZ 4llpl 153 ISoTl'l '1 15 12 10 ARRAVG ARRAVG TS T191 151-3 STDA K P11 TS IZ STDB K 91 SFDA 152 1p1 T51 HUDX 4 13 15 1 15 1 1 4 PAGE 69 PDDELI PAGE 70 MD CCHPUIES AND PRINTS DIST AS AS FUNCTION OF IMPARE CALL SEQU ISX PZE REIURN IF NET CAN NOT BE RUN NORMAL RETLRN WHERE CONTAINS LOCATION OF FIRST SPECIAL OF SPECIAL LINKS AND IMPLIES NU SPECIAL LINKS BEGIN 3 7 1 IXL ' 7 Ooc LINKAGE STL NU ACIIVITY CLA 1 4 TZE STU ISX PRESETQQ INIIEQU HUUELI CLA IHPARE TSX IRA FCX SIC MD 0 MPY MD O SIC no 1 XCA HPY Coo STU HC 2 ISX TSX hISp4 AXI l'l STZG STDA LOCI HUDA PXA XCA TIE HUI HUDA DVP ARRCNI XCA SIDA PBT IXI Zglul IRA H02 SID STDA IRA HBO IXI M02 1 -1 SKA MDJ I IXI SXD Hval F09 F03 F04 H05 F06 FOB FOX 11 11 15 18 19 20 LXA SXD SXD AXT LDQ AXT HPY IRA CLA- TLO AXT IXH MPY CLA FLO TRA CLA TLQ CLA TLO TXH TXI 11x TXL LXA ADD 5T0 TSX XEJECT STL XPRINT STL PIE XPRINI STL TSX RETURN IRA REYURN AXT FRACT CONVERTS FLOATING FRACTION CALL SEOU TSX Ball 32000 4 RND 091 0 2 STDA H04 2 102'1 K R 0 0 n 2 0 1 n 2 no 2 05'101 H05 1 1 c 2 2 nlo H008 K A1 HUDB 03-491 RNO HTS 4 SYSUED J91 SYSOEU F10 l 2 1'1 SYSUED H0004 H0 0 1 0'1 TC BINARY CNE IACC1 RETURN IF GREATER THAN 1 - - NR PAGE 71 PAGE 72 NORMAL RETURN MO 8 BINARY AR FRACI XCL MAKE POSITIVE 2 LLS 8 3 SUB KINTZ IRA Zg DEFINE FORMATS BEGIN FURFAT TXL 33090 LINKAGE XFURM 11 4 STL svsoeo 7 PIE 3 PIE FH2303 9 PZE FH3 4 10 PZE Fue 4 011 PZE 012 PZE FMbuuB #13 PZE FMT 3 01$ PIE FMB 3 015 PIE FM9 5 16 PIE PIE RETURN FORMAT 018 IRA pass 73 POOL LIMIT EOU 32767 TPU E00 20 POOL K A1 1 K A101 PIE x 12 2 K A3 3 K A7 7 K AB K A9 DEC 9 K A16 DEC 16 K A100 DEC 100 K A48 DEC 48 KINTI OCT 233000000000 KINTZ OCT 200 KINT3 OCT 1000000000 KFULL OCT 377777777777 K HZE HZE K PI DEC 0 K P11 DEC 0 K R OCT 11060471625 MLLT FOR RANDOH K TZ K 73 PZE OCT 77700000 K H2 OCT 777777777 K F3 7 TAG OCT 777700000 K M5 OCT 777 K H6 OCT 77777 K H7 EQU K HS K-D DESTINATION HO NUMBER K-L LINE NR K PSG MESSAGE ER NUDE NR ORIGIN Kop PRIORITY K-ST TIME DELAYED IN STACKS KolL COUNTER PIE 855 8 IL OCT ILHD OCT 0 ILHD OCT 0 IR ARRIVAL LIST PIE PIE PIE PIE 0 Doz B T CONN CX BELIVR ESPY FACTOR FMB FHZ FHQ FMS FHB FH9 FlO l F10 2 F10 3 F10 k F10 6 '010 YES lo HDHIGH HOHII HOLINE HOVER OCT ECU EOU TSX PZE DEC EOU TSX ARS ARS IRS NOP LGL LGL HEAVE COLUMN 010 4 0 0 one LIST 1 In 0 nA 2 l0x k l 3lF10 4325 3 F9 7 u 5 'Ab 3 F7 4 5chkOX A 2 l3H DISTRIBUTION PAGE 74 90TIHE STACK-DROPS DELIVERIES 2 VARIANCE 1 YES 1 N0 776 770 HUINC 1000 HAO 4 18 27 18 3 LKI 1 LKZ L0 L5 PAXACT FD O 0 1 HD 2 N63 OT 91 CTol 10 PRETGL RA D RA 1 31 2 RA 3 RA 5 RND ROUTER SCI SCZ LGL ALS ALS IRS IRS DEC DEC DEC DEC DEC PZE VFO VFD VFD VFD OCT OCT OCT OCT DEC TSX DEC DEC DEC DEC PZE OCT PZE OCT OCT OCT OCT OCT OCT EOU OCT 27 15 2 000 GO 002 $02 15 0 3 2 15 o 3 1 15 0 3 0 15 0 3 5 1511 3 o 15 3 3 1 0 0 0 10 0 -10 c 0 0 0 0 0 2580 ct 0000000000 3 I R1004 PAGE 75 SCH SIDES SINK SKCUM SKH SOURCE SSLIP TPHIGH TS TI TS T2 UPPER UPDATE COUNTS DROPPC IRRAVG HU HOAVG ARRHCI IRRHC HOTDTI HOTUT CNTTEL POOL PIE PIE 0 0 IO TPU LIMIT HA1 COUNts --couwts' PAGE 76 NR MSGS NR MSGS DRUPPEC h STACK NR 0F ARRIVALS PERCENT AVG H0 CF DELIVERED HSGS SECOND HEMENT CF DIST AVG OF H0 TABLE TOTAL HO 0F DELIVERED PSGS NR 0F ENTRIES IN HD-TABLE SUM OF ENTRIES IN HO-TABLE CHOKE SNAP FLOR EIND ADAPT ALPHA IHPARE IMPAIR LEARN FORGET HHAX PAXHC HEIVE RDH CULUFN TPHAX TPHIN STACK HPRIPE INITED GRAIN RANDCH LINKS IABLES PZE PZE ECU PZE PZE DEC DEC ECU DEC DEC DEC EQU DEC DEC DEC DEC DEC DEC DEC EQU DCT OCT DEC LIST I SNAP 0 IMPARE 1 0 63 HHAX 0 6 8 HPRIHE 2 10604716255 0 BEGINNING OF IABLES INC LISTS pass 77 LINK FOR FVE SIX SVN PZE PDN PTH PTH PAGE 78 LINK TABLE - CONTAINS IMAGE LINK NR5 AND DISTANCE FRCM EFF T0 AFF NUDE LINKS ARE NUMBERED 0 THRU VIILINE NR THEN 8 EFF NUDE NR 8 INTEGER - EFF LINK NR REHAINDER LIB I AFF NUDE NR 4 ACDRESS PART OF IMAGE LINK NR I FIRST 3 BITS 0F LINK TABLE IIO 5IPTBLE TP 855 PAGE 79 TP L151 CCNIAINS POINTERS ID FIRSI AND LASI MESSAGES CN TRAFFIC LISTS IPil' IS HEAD CF LIST FOR TIME 1' HHERE 1' IS COUNTEC MUDULU TPL THE MAXIMLV TIME PZE LAST NSC NR FIRST #50 NR a HHERE CURRENT TIME 0 CTABLE OCT OCT DCT OCT CCT DCT DCT OCT DEC DEC DEC DEC DEC DEC DEC CONNECTIVITY TABLE CTABLE HAS ENTRIES TC ALLCHABLE CONNECTIVITIES ISEE LINK TABLE CONN LINKS USED 1 6 2 2 6 4 2 0 3 1 6 4 3 200 ALL AS REQUIRED 314000000000 46000000000 -20000000000 0 104000000000 -124000000000 377000000000 NDH NLHBER 0F LINES ERROR PER NCDE CONN CONN 3 ETC CTABLEICCKK 10111011 0101010 FDR GIVEN CONN PAGE 80 once 81 LINE TABLE PREFIX ausv SIGNAL DECR PIPE-FILLING T1ME TP tAc zpao ACCR POINTER TO FIRST HCTABLE ENIRY FCR THIS LINE ZERO IF NO DEC 0 LINEI u0 2 LINEA IIO 1 LINEE 0v2 LINEC 0l LINTBL 0Iv 0 NOOES ll NIB NIC NZA N28 NZC NBA N38 NBC N48 mac NODTBL DEC PZE PZE PIE PZE PZE use 82 NODE TABLE THREE PARTS PART ONE PREFIX 8 4 IF KILLED ZERO IF ALIVE DECREMENT I STANDARD-STACK POINTER TAG ZERO ADDRESS POINTER PART THO CURRENT DEPTH OF STANDARD STACK PART THREE ADDRESS DECREHENT CONTAINS REFERENCE NUDE NLPBER FOR CHOOSING ORIGINS DESTINATIONS PART FOUR EXISTS ONLY IF FLCH ARE BEING TAKEN AND THEN CONTAINS NR CF MESSAGES PASSED THRL NCDE 0 000 2 510 4 0'2 P'0c4 050 1 '092 9 0 oa0 BUSY EUSYA EUSYE BUSYC PZE PZE PIE PIE BUSY TABLE PREFIX PZE IMPLIES LINE IS DEAD CECR TINE REMAINING BEFORE LINE IS FREE ADDR 8 PCINYER TU IMAGE LINE 'Ovl 0 1 0 1 5 0 2 0 4 PAGE 83 PAGF 8h NUMBER TABLE INITIALIZED BY ROUTINES INH AND BNF PACKED FOURIHCRD 0RDERED IFUR A GIVEN LINE BY INCREASING NUDE NR AND READ FGRHARD FUTBLE 0-0 0 F0 DISTRIBUTION TABLE - READ BACKHARD LINE I CF FOOTBL CCNTAINS CF DELIVERED NSGS HHOSE H0 NR5 LIE BETHEEN I AND 1 1 FUDA 091 FUCB 092 HUCC 004 FUDTEL CONTAINS DISTRIBUTION OF DELAYS IN STACKS FOR CLVC MSGS STEA Il gl STCB STCC IDO 4 STDTEL Ilo 'llo YABLE CURTAINS PFRCENIAGE CF TC BE PREENPTED BY PFRC IN PART I LCHER 2 SCIA 091 SCIB SCIC SCZA IlOol 5525 SCZC 5 0 4 SKIA SKIB 5'0'2 SKIC SKZA l'O'l SKZB 0 2 SKZC Opq PAGE 85 LOAD PSGCAT VSGS EASE FSGTEL PSGI RSGZ EEC EEC DEC END MESSAGE TABLE THC PARTS PSGI CONTAINS 7 BITS - ORIGIN NUDE RR 7 BITS - DESTINATION NUDE NR 4 BITS - PRIORITY 9 BITS - TIME DELAYED IN STACKS 9 BITS - CLRRENT EC M502 CONTAINS PREFIX ZERO IF MOVING AND ALIVE FOLR IF STACKED CECREFENT POINTER TO NEXT MESSAGE Gk TRAFFIC LIST FCR SAME TIME-FRAME ZERO TAG CURRENT LINK NR ADDRESS CURRENT LINE NR 0 NETPGM IF LAST SEE Tp DESCRIPTION PAGE 86 ACTIVE ARRAVG 8ES7H0 80770 CNIIBL COLUMN counts CYABLE DELIVR DROPPC FACTOR FDRGE7 FORHA7 HUDIBL HUHIGH HDINCI HOL1NE HONCN7 HOTBLE H07071 HPRIHE IMPAIR IMPARE INIIGL INITHO K A100 K A101 LINTBL HAXAC7 MODELZ NETPGH NODTBL PARAHS PARSET PRESET PRETGL RANDOM RECORD ROUTER $10157 SETHMK 0069 0073 0076 0076 0076 0065 0073 0076 0077 0076 0080 0076 0076 0076 0076 0077 0072 0065 0086 0076 0076 0076 0076 0086 0076 0077 0077 0077 0075 0077 0073 0073 0081 0075 0070 0068 0086 0086 0007 0082 0011 I0008 0011 0075 0077 0065 0075 0061 0061 0062 0085 0063 0053 0085 DCNET SOURCE STC7EL S7KCNT STKIAC $75001 $78082 SYSIEC SYSHIT SYSCED SYSURG SYS7EH IAELES TPHIGH 7P7BLE UPDATE ENTRY ERRCR PARAH ADAPT AL ALHC ALPHA ALHC AR ARRHO BASE 8FTS7 8H 8H1 BH10 8H2 0H3 3H6 8H5 8H6 0H8 8H9 BHK BH A BINC BUSV BUSYA BUSYC B HC 8 7 CH1 0076 0086 0076 0076 C000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0077 0076 0079 0076 $0010 0010 0077 0069 0077 0073 0073 0077 0073 0073 0076 0006 0073 0029 0029 0030 0029 0029 0029 0029 0029 0030 0030 0030 0073 0073 0077 0083 0083 0033 0003 0073 0076 0067 CH2 CH3 CHAIN CPCKE CLEAR CORN CONT 0R0 DRCP ESPY DUMP ERROR F10 1 F10 2 F10 3 F10 6 PIC-5 F10 6 F11F81 F82 F83 F86 F85 F86 FILL FLCH FLHO FLHZ FLH 7M1 FMIO FHZ FM6 FMS FM6 0067 0067 0067 0077 0066 0076 0053 0076 0076 I003B 0038 I0038 0038 0038 0038 0076 0066 0066 0076 0007 0007 0076 0076 0076 0076 0076 0076 0076 0062 0062 0062 0062 0062 0063 0063 0063 0063 0063 0063 0063 0076 I0077 0061 0062 0062 0062 0076 0076 0076 0076 0076 0076 0076 0076 FP7 FPB FV9 FRACT GRAIN HA HAO HA1 HA2 HA3 FA6 HA5 HA 1 HFAK HCAVG H00 HCDA HCDB #000 HCDX HCINC HCNEI H0707 HCVER HSH HSHZ H70 H71 H72 H73 H76 H75 H76 1477 H78 H70 HTF H75 0076 0076 0076 0072 0050 0050 0050 0050 0050 0050 0051 C051 0050 0051 0066 0077 I0035 0035 0035 0035 0035 0035 0035 0076 007 0076 0061 0086 0086 0086 0061 0076 0076 0076 0076 0076 0076 0076 0075 0076 0066 0066 0066 0066 0066 0066 I0066 0066 0067 0065 0066 0067 0021 0021 PAGE 1A1 1A13 1A16 IA15 Alb 1A17 IAIB 1A10 1A2 1A20 IAPI 1A3 1A6 1A5 1A6 1A9 1H1 1H2 1P3 1H6 1H5 167 1H9 IHA 1H8 IHC 1H0 IHX 1L0 111 112 1L3 1L6 ILX 1L T INL IALO IALZ INS K1 K2 KFULL 87 0021 0026 I0026 0026 0026 0026 0026 0026 0025 0021 0025 0025 0021 0021 0021 0021 0071 0021 0021 0026 0026 0026 0026 0027 0027 0027 0028 0027 0075 0075 0075 0075 0028 0023 0023 0023 0023 0023 0023 0023 0026 0075 0016 0016 0016 0016 0016 0017 0017 0020 0075 0075 0073 0073 KIN72 K1N73 K A1 K A16 K A2 K A48 87 K IO K A9 K AL K D K L K H1 K H2 K H3 K H4 K H5 K M6 K H7 K NSG K NZE K N K 0 Ko l K P11 K ST K 71 K 72 K 73 Ko74 LEARN LEF7 LIMIT LINEI LINEA LINEB LINEC LINES LINK LINKS L080 LOHER LRN 0073 0073 0073 0073 00073 0073 0073 0073 0073 0073 0073 0073 0073 0073 0073 0073 0073 00073 0073 0073 0073 0073 0073 0073 0073 0073 0073 0073 0073 0073 0073 0073 0073 0073 0077 0075 0073 0081 0081 0081 0081 0081 0078 0077 0086 0075 0036 DCNET N10 N28 N28 N20 N3A N38 N30 N4A N48 N40 N00 N01 0036 0075 00032 0032 0032 0033 0033 0032 0032 0077 0070 0070 0070 0070 0071 0071 0071 0071 0071 0071 0071 0071 0075 0075 0075 0048 0048 0036 0075 0086 0086 0086 0076 0082 0082 0082 0082 0082 0082 0082 0082 0082 0082 0082 0082 0053 0056 RICO RAOZ 8803 RAI RAZ RA3 RA4 0055 0075 0075 0055 0054 0054 0053 0054 0074 0082 0075 0075 0075 0077 0062 0062 0062 0062 0062 0015 0014 0073 0011 0012 0012 0014 0013 0012 0012 0011 0008 0008 0008 0009 0009 0014 0075 I0039 0039 0039 0039 0039 0039 0039 '0039 0040 0040 04 16 63 RA7 R88 RA9 RA 0 RA 1 RA 2 RA 3 ISA-IO 718SCI 5018 $010 502 $028 5028 $020 SCH 5071 5072 5073 $074 $075 $076 SCTLU SE71 SE72 SIDES SIMI SINK SKIA SKIS SKIC SKZA ICO4C 004C 0040 0040 C039 0075 0075 0075 ICCTS 0075 0075 0045 0052 0052 0052 0052 0075 0077 0075 0075 0085 0085 0085 0075 0085 0085 0085 0075 0076 0059 0069 0059 0059 0059 0059 0060 0058 0063 0064 0076 0053 0053 076 0085 0085 0085 0085 PAGE SKZB SKZC SKCUM SKH SK71 SK72 SK73 SK74 SK75 SK76 SK77 SKTLU SNAP SSLIH S7ACK 570 $708 5700 7P TPMAX 7PMIN TPU TS 751 752 753 75X 75 71 75 72 UPPER HEAVE YES ENI EN2 EN3 EN4 ENS ENX EXIT CLO LKI LKZ LS PCCL 0085 0085 0076 0076 0058 0057 0057 0058 0057 0058 0058 0057 0077 0076 0077 0084 0084 0084 0079 0077 0077 0073 0068 0069 0069 0069 0069 0076 0076 0076 0077 0010 0010 0010 0010 0010 0010 0010 0075 0075 0075 0075 0076 -89- 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 proposal may be obtained by reading this volume and Vol XI II Digital Simulation of Hot-Potato Routing in a Broadband Distributed Communicati ns 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 Mbnte 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 IV Priority Precedence and Overload Paul Baran 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 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 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 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