MEMORANDUM
`RM- 3420 -PR
`AUGUST 1964
`
`ON DISTRIBUTED C+O~IM~..~NICATIONS:
`I. IN~R~DUCTION ,T4
`DISTRIBUTED GOMMUI~TICA`~'~~C7NS iVETWORKS
`
`PrLll~ B~LI'.L1]
`
`PREPARED FOR:
`
`UNITED STATES AIR ~'C7RG~ P~,OJECT Ft,AND
`
`".
`
`5+1i+~TA M~NICA CALIFORNIA
`
`'~~e
`
`' ~c
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 1
`
`
`RM- 3420 -PR
`AUGUST 1964
`
`ON DISTRIBUTED C+O~IM~..~NICATIONS:
`I. IN~R~DUCTION ,T4
`DISTRIBUTED GOMMUI~TICA`~'~~C7NS iVETWORKS
`
`PrLll~ B~LI'.L1]
`
`PREPARED FOR:
`
`UNITED STATES AIR ~'C7RG~ P~,OJECT Ft,AND
`
`".
`
`5+1i+~TA M~NICA CALIFORNIA
`
`'~~e
`
`' ~c
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 1
`
`
`
`~~
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 2
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 2
`
`
`
`MEMORANDUM
`
`RM- 342U -PR
`
`AUGUST 19G4
`
`ON DISTRIBUTED COMMUNICATIONS:
`I. INTRODUCTION TO
`DISTRIBUTED GOMMUNICATICaNS NETW(JRKS
`
`Paul Baran
`
`This research is sponsored h~• the I.'nit~d States .Air Force under Project R.A1n Can-
`tract :\o. A1~ ~91h381.7Q0 mi~nitnred h~~ the Dirr~toratc of Dc+•cloPment Plan. Df~put}•
`Chief of Staff. Research and Det•elnpment. Hq L~S_AF_ VieH•s or conclu~ion~ ~ontein~d
`in this !1'Iemnrairdum should not }~e interpreted as reprPcrnting thr official upitiicm i>r
`policy of the United StatP~ Air Forcc.
`
`qDC AVAILAB)L.IT~' 10T10E
`~ capics of t}tis report from the Defen~r Dc7cumentation
`C~ualified requeslers m8}'
`Center (I7T)C}.
`
`..
`
`~.
`~~~~~
`
`~~ Rol I l [)e~~
`
`)UC ~+~~~+ 1~
`
`~~N'~ MUNI(• (All101 Ni• ~0~01
`
`Copyrigh~ C~; 19b4
`THE RAND CORF't)RATION
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 3
`
`
`
`I~~ ~E
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 4
`
`
`
`-iiz-
`
`PREFACE
`
`This Memorandum is one in a series of eleven RAND
`Memoranda detailing the Distributed Adaptive Message B7_ock
`Network, a proposed digital data communications system
`based on a distributed network concept. Various ifiems in
`the series deal with the concept in general and with its
`specific features, results of experimental modelings,
`engineering design considerations, and background and future
`implications.
`The serzes, 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 o£ command and control and i_1z
`governmental and military planning and policy making.
`The present Memorandum, the first in the series,
`introduces the system concept and outlines the requirements
`for and design considerations of a digital data communica-
`tions system based on the distributed concept, especially
`ash egards implications for such systems in the 1970s. In
`particular, the Memorandum is directed toward examining
`the use of redundancy as one means of building communications
`systems to withstand heavy enemy attacks.
`While highly survivable and reliable communications
`systems are of primary interest to those in the military
`concerned with automating command and control functions,
`the basic notions are also of interest to communications
`systems planners and designers having need to transmit
`digital data.
`Various aspects of the concept as reported in this
`Memorandum were presented before selected Air Force audiences
`in the summer of 1961 in the form of a RAND briefing (B-265),
`and contained in RAND Paper P-2626, which this Memorandum
`supersedes.
`
`*A list of all items in the series is found an p. 35.
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 5
`
`
`
`~~~
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 6
`
`
`
`
`~V~
`
`SUNQ3ARY
`
`This Memorandum briefly reviews the distributed
`
`communications network concept and compares ~.t to the
`
`hierarchical or more centralized systems. The payoff
`
`in terms of survivability tar a distributed configuration
`
`in the cases of enemy attacks directed against nodes,
`
`links, or combinations of nodes and links is demonstrated.
`
`The requirements for a future a11-digital-data
`
`distributed network which provides common user service
`
`for a wide range o~ users having different requirements
`
`is considered. Z'he use of a standard format message black
`
`permits building relatiively simple switching mechanisms
`
`using an adaptive store-and-forward routing policy to
`
`handle all forms of digital data including "real-time"
`
`voice. This network rapidly responds to changes in the
`
`network status. Recent history of measured network traf-
`
`fa.c is used Co modify path selection. Samulatian results
`
`are shown to indicate `that highly efficient routing can
`
`be performed by 1r~cal control without the necessity for
`
`any central--and therefore vulnerable--control point.
`
`A comparison is made between "diversity of assignment"
`
`and "perfect switching" in distributed networks. The
`
`high degree of connectivity afforded allows the use of
`
`low-cost links so unreliable as to be unusable in present
`
`type networks.
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 7
`
`
`
`~~~
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 8
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 8
`
`
`
`-vii-
`
`FOREWORD
`
`The series that this Memorandum introduces describes
`
`work o~ distributed communica~ians. Originally, i~ was
`
`thought that each of the eleven volumes would be able to
`
`stand by itself, But, somewhere downstream it became
`
`clear that this goal could not b~ fully met, as each part
`
`hinged upon others. Therefore, publication of the indi-
`
`vidual Memoranda of the series was delayed in order to
`
`release the set as a whole.
`
`While the resulting mound a£ paper forms a frighCening
`
`pile, it need nat all be read in depth, nor wi11 X11
`
`readers be interested in all the volumes. It is suggested
`
`that the present volume be read first especially if the
`
`reader is not familiar with its antecedents, B-265 or
`
`P-2b26. Then the reader should advance directly to the
`
`summary overview in Vol. XI. Once in context, it will be
`
`easier to selectively examine the other papers of the
`
`series in more detail.
`
`Two types of papers will be found. The first set,
`
`Vols. I, IV, V, IX, and XI, describes in general terms
`
`the underlying system philosophy and what this system
`
`approach has ~a offer. The second set, Vo1s. II, III,
`VI, VII, VIII, and X, describes in nuts-and-bolts detail
`
`one possible way of implementing the proposed mechanisms,
`
`'the purpose of this second set is to supply the technical
`
`details of the proposed system in sufficient detail, a.~t
`
`is hoped, to permit the reader to focus his questions on
`
`the potential feasibility of the system in a meaningful.
`
`manner.
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 9
`
`
`
`~V111-
`
`It should be staffed at the outset that we are dealing
`
`with an extremely complicated system and one that is even
`
`more complicated to describe. It would be treacherously
`
`easy fox the casual reader to dismiss the entire concept
`
`as impractically complicated--especially if he is unfa-
`
`miliar with the ease with which logical transformations
`
`can be performed in a time-shared digital apparatus. The
`
`temptat~an to throw up one's hands and decide that it is
`
`all "too complicated," or to say, "It w~.11 require a
`
`mountain of equipment which we all know a.s unreliable,"
`
`should be defexred until the fine print has been read.
`
`Tn the interim, let us agree on what we mean when we
`
`speak of "complexity." It can be defined in several ways;
`
`for example, by size, by ~l.exibility, or by number of
`
`components. $ut these are not identical measures. Con-
`
`sider an ancient electro-mechanical computer composed of
`
`bays of clacking relays. The logical di_agrarns are simple--
`
`a few conceptually simple boxes perform almost trivial
`
`logical functions. But the physical dimensions of the
`
`package and the amount of maintenance effort required
`
`constitute a frightening aspect of complexity.
`
`Conversely, consider a "shoe-box" of electronic
`
`equipment that performs all the functions the larger unit
`
`did, plus many new ones, and does them more quickly. It's
`
`smaller, more reliable, quieter, and requires less main-
`tenance. But it may actually contain more components and
`
`its logical equations may be more difficult to comprehend.
`
`Is the shoebox more complex or less complex than ids
`
`room-size electra-mechanical counterpart?
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 10
`
`
`
`- ix-
`
`ACKNOWLEDGMENTS
`
`In developing this work, I received a large number
`
`of excellent ideas and suggestions--so many, in fact, that
`
`it has become impossible to fully acknowledge each person
`
`who has contributed in some way without unduly Lengthening
`
`these manuscripts.
`
`I wish to take this opportunity to thank the follow-
`
`ing contributors, each of whom reviewed one or more of
`
`the Memoranda in the series and who offered highly appreci-
`
`ated and accepted suggestions. The process of review of
`
`a manuscript does not necessarily imply fu11 agreement
`
`with all ghat is said, so I alone must accept responsi-
`
`bility for any mistakes in the work.
`
`Reviewers included:~~ Marvin Adelson (National Academy
`
`of Sciences), C. L. Baker, Edward Bedrosian, Sharla Boehm,
`
`J. L. Bower, J. B. Carne, L. J. Craig, J. Y. Derr, F. E.
`
`Eldridge (Office of the Assistant Secretary of Defense,
`
`Comptroller), T. 0. Ellis, Jarnes Farmer, N. E. Feldman,
`
`H. Hambrock (North Electric Company), W. B. Holland,
`
`J. L. Hult, C. B. Laning (System Development Corporation),
`
`C, R. Lindholm, I. S. Reed, E. E. Reinhart, R. H. Scherer
`
`(Office of the Director of Defense Research and Engineering),
`
`J. W. Smith, Harold Steingold, C. G. Svala (North Electric
`
`Company), Rein Turn, K. W. Uncapher, T. G. Williams
`
`(Philco Corporation).
`
`_~
`~~Unless otherwise noted, those listed are with The
`RAND Corporation.
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 11
`
`
`
`~~
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 12
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 12
`
`
`
`-Xl-
`
`PREFACE ..........................................
`
`iii
`
`SUMI~I~iRY ..........................................
`
`v
`
`FOREWORD .........................................
`
`vi_i
`
`ACKNOWLEDGMENTS ..................................
`
`ix
`
`Section
`I. INTRODUCTION .............................
`
`II. EXAMINATION OF A DISTRIBUTED NETWORK .....
`Node Destruction .......................
`Link Destruction .......................
`Combination Link and Node Destruction ..
`
`III. DIVERSITY OF ASSIGNMENT ..................
`Simulation .............................
`Gomparisan with Present Systems ........
`
`IV. ON A FUTURE SYSTEM DEVELOPMENT ...........
`Future Low-Cost A11-Digital
`Communications Links .................
`Variable Data Rate Links ...............
`Variable Data Rate Users ...............
`Common User ............................
`Standard Message Block .................
`Switching ..............................
`Forgetting and Imperfect Learning ......
`Loraest-Cost Path .......................
`
`V. WHERE WE STAND TODAY .....................
`
`1
`
`3
`6
`9
`9
`
`13
`13
`15
`
`16
`
`17
`19
`19
`20
`20
`23
`30
`33
`
`34
`
`LIST OF PUBLICATIONS IN THE SERIES ...............
`
`35
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 13
`
`
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 14
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 14
`
`
`
`-1-
`
`I. INTRODUCTION
`
`Let us consider the synthesis of a cammunicatzon
`network which wi11 a11ow several hundred major cammunica-
`tions stations to talk with one another after an enemy
`attack. As a criterion of survivability we elect to use
`the percentage of stations both surviving the physical
`attack and remaining i.n electrical connection with the
`largest single group of surviving stations. This criterion
`is chosen as a conservative measure of the ability of the
`surviving stations to operate together as a coherent
`entity after the attack. This means that small groups of
`stations isolated from the single largest group are con-
`sidered to be ineffective.
`Although one can draw a wide variety of networks,
`they all factor into two components: centralized (ox
`star) and distributed (or grid or mesh) (see Fig. 1).
`The centralized network is obviously vulnerable as
`destruction of a single central node destroys communica-
`tion between the end stations. In practice, a mixture
`of star and mesh components is used to form communica-
`tions networks. For example, type (b) i.n Fig. 1 shows
`the hierarchical structure of a set of stars connected
`in the form of a larger star with an additional link
`forming a loop. Such a network is sometimes called a
`"decentralized" network, because complete reliance upon
`a single point zs not always required.
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 15
`
`
`
`F1G. I —Centralized, Decentralized and Distributed Networks
`
`tC~
`
`DiSTR18UTED
`
`(B)
`
`DECENTRALIZEd
`
`tA)
`
`CENTRALIZED
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 16
`
`
`
`-3-
`
`II. EXAMINATION QF A DISTRIBUTED NETWORK
`
`Since destruction of a small number of nodes in a de-
`centralized network can destroy communications, the
`properties, problems, and hopes of building "distributed"
`communications networks are of paramount interest.
`The term "redundancy level" is used as a measure of
`connectivity, as defined in Fig. 2. A minimum span network,
`one formed with the smallest number of links possible, is
`chosen as a reference point, and is called "a network of
`redundancy level one." If two times as many links are
`used in a gridded network than in a minimum span network,
`the network is said to have a redundancy level of two.
`Figure 2 defines connectivity of levels 1, 12, 2, 3, 4,
`6, and 8. Redundancy level is equivalent to link-to-node
`ratio in an infinite size array of stations. Obviously,
`at levels above three there are alternate methods of
`constructing the network. However, it - was found that
`there is little dif~'erence regardless of which method is
`used. Such an alternate meChod ~.s shown for levels three
`and four, labelled R'. This specific alternate mode is
`also used for leve3s six and eight.*
`Each nods and link in the array of Fig. 2 has the
`capacity and the switching flexibility to allow trans-
`mi_ssian between any ith station and any jth station,
`pravi_ded a path can be drawn from the ith to the j th
`station.
`Starting with a network composed of an array of
`stations connected as in Fig. 3, an assigned percentage
`of nodes and links is destroyed. If, after this opera-
`tion, it is still possible to draw a line to connect the
`ith station to the j th station, the ith and j th stat~.ons
`are said to be connected.
`
`See Cxaig, L. J., and I, S, Reed, "Overlapping
`Tessellated Communications Networks," IRE Trans. Conan,
`sys• , CS-10 (1962) I25-129,
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 17
`
`
`
`-4-
`
`0
`
`0
`
`0 ~
`
`o
`
`0
`
`0
`0
`R-1.5
`
`0
`R=2
`
`0
`
`0
`
`0
`
`0
`R=1
`
`0
`
`0
`
`0
`
`O
`
`O
`
`R=3
`
`R=4
`
`0 0
`
`0 0
`
`o O
`
`o 0
`
`0 0
`
`0 0
`
`0 0
`
`0 0
`
`0
`
`0
`
`0---
`
`0 0
`
`0 0
`
`0 0
`
`0 0
`
`0 0
`0 0
`R~ = 3
`
`0 0
`
`0 0
`
`R~= 4
`
`0 0
`
`0 0
`
`o Q o s~
`
`o
`
`O Q O b O
`
`O O
`
`O O
`
`R~=6
`
`R~ = 8
`
`F1G. 2 - Definition of Redundancy Level
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 18
`
`
`
`-5-
`
`FfG. 3 — An Array of Stations
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 19
`
`
`
`NODE DESTRUCTION
`
`Figure 4 indicates network performance as a function
`
`of the probability of destruction for each separate node.
`
`If the expected "noise" was destruction caused by conven-
`tional hazdware failure, the failures would be randomly
`
`distributed through the network. But, if the disturbance
`were caused by enemy attack, the passible "worst cases"
`
`must be considered.
`To bisect a 32-li.nk network requires direction of 288
`
`weapons each with a probability of ki11, pk = 0.5, or
`160 with a pk = 0.7, to produce over an 0.9 probability
`of successfully bisecting the network. If hidden alterna-
`tive command is allowed, then the largest single group
`would sti.I1 have an expected value of almost 50 per cent
`of the initial stations surva.ving intact. If th~_s raid
`misjudges complete availability of weapons, or complete
`knowledge of all links in the cross section, or the
`effects of the weapons against each and every link, the
`raid fails. The high risk of such raids against highly
`parallel structures causes examination of alternative
`
`attack policies. Consider the following uniform raid
`example. Assume that 2,000 weapons are deployed against
`a 1000-station network. The stations are so spaced that
`
`destruction of two stations with a single weapon is
`unlikely. Divide the 2,000 weapons into two equal 1000-
`weapon salvos. Assume any probability of destruction of
`a single node frcm~ a single weapon less than 1.0; for
`
`example, 0.5. Each weapon on the first salvo has a 0,5
`
`probabila.ty of destroying its target. But, each weapon
`of the second salvo has only a 0.25 probability, since
`one-half the targets have already been destroyed. Thus,
`the uniform attack is felt to represent a known worst-
`case configuration in the following analysis,
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 20
`
`
`
`~-.
`~ ~
`C ~Z
`
`cp
`
`O
`
`~
`_
`
`0 Z n
`
`V
`
`C n
`
`'^ ~ Q
`
`0
`
`m
`
`~
`Q X
`
`.~ z
`
`..~.
`
`~ ~ O
`
`O ~ W
`1 m
`N ~ ~
`
`~~o -D~
`r- r*~ o
`"' n o
`o
`
`p
`
`~~ Z
`
`_
`
`LARGEST FRACTION OF STATIONS IN COMMUNICATION
`
`~~SURVIVABILITY~~
`
`o
`
`c
`
`o
`
`o
`
`O
`
`N
`
`~,
`
`~ ~ "
`m vw
`~ ~" ~ O
`
`'~' Z
`~ ~ ~
`O {~}
`-+-
`~ ~,
`
`rn
`-. -,,
`~ v <o ro
`~
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 21
`
`
`
`Such worst-case attacks have been directed against
`an 18x1$-array network model of 324 nodes with varying
`probability of ki11 and redundancy level, with results
`shown in Fig. 4. The probability of ki11 was varied from
`zero to unity along the abscissa while the ordinate
`marks survivability. The criterion of survivability used
`is the percentage of stations not physically destroyed and
`remaining in communications with the largest single group
`of surv~tving stations. The curves of Fig. 4 demonstrate
`survivability as a function of attack Zevel for networks of
`varying degrees of red~xndancy. The line labeled "best
`possible line" marks the upper bound of loss due to the
`physical failure component alone. For example, if a net-
`work underwent an attack of 0.5 probability destruction
`of each of ids nodes, tY~en only 50 per cent of its nodes
`would be expected to survive--regardless of how perfect
`its corrm►unica~ions . We are primarily interested in the
`additional system degradation caused by failure of
`communications. Two key points are ~o be noticed in the
`curves of Fig. 4. First, extremely survivable networks
`can be built using a moderately low redundancy of connec-
`tivity 1eve1. Redundancy levels on the order of only
`three permit withstanding extremely heavy level attacks
`with negligible additional loss to communications.
`Secondly, the survivability curves have sharp break-points.
`A network of this type will withstand an increasing attack
`level until a certain point is reached, beyond which the
`network rapidly deteriorates. Thus, the optimum degree
`of redundancy can be chosen as a function of the expected
`level of attack. Further redundancy buys little. The
`redundancy level required to survive even verb heavy
`attacks is not great--on the order of only three or four
`times. that o~ the minimum span network.
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 22
`
`
`
`LINK DESTRUCTTON
`
`In the previous example we have examined network
`performance as a function of the destruction of the ngdes
`(which are better targets than links) . We sha11. now
`re-examine the same network, but using unreliable 1~_nks.
`In particular, we want to know how unreliable the links
`may be without further degrading the performance of the
`network.
`Figure 5 shows the results for the case of perfect
`nodes; only the links fail.. There is little system
`degradation caused even using extremely unreliable links--
`on the order of 50 per cent down-time--assuming all nodes
`are working .
`
`COMBINATION LINK AND NODE DESTRUCTION
`
`The worst case is the composite effect of failures
`of both the links and the nodes. Figure 6 shows the
`effect of Zink failure upon a network having 40 per cent
`of its nodes destroyed. It appears that what would today
`be regarded as an unreliable link ern be used in a.
`distributed network almost as effectively as perfectly
`reliable links. Figure 7 examines the result of 100 trial
`cases i_n order to estimate the probability density dis-
`tribution of system performance for a mixture of node and
`link failures. This is the distribution o~ cases far 20
`per cent nodal damage and 35 ger cent link damage.
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 23
`
`
`
`-10-
`
`aw
`
`z~-Q
`a
`~W
`zQ
`0_~
`y. a z
`F- ~ O
`_.J
`F-
`
`j ~ ~ 0.5
`
`> OZ
`~ ~Q
`
`~ Q =
`~' ~ F-
`L~.
`
`Q F-
`W U
`~4
`
`HZOU
`
`aR
`a
`
`o.i
`
`o,a
`o.~
`a.s
`o.7
`oz
`o.s
`o.s
`SINGLE LINK PROBABILITY OF DESTRUCTION
`
`o.9
`
`i.o
`
`FlG. 5 — Perfect Switching in a Distributed Network — Sensitivity to
`Link Destruction, i00% of Nodes Operative.
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 24
`
`
`
`-11-
`
`z o.e
`
`0 a z 0U z
`
` 0.6
`~ -
`h-
`~~z
`m o
`> ~a
`> ~
`~ ~
`~ ~
`~o
`Z 0.4
`
`O UQ L
`
`~ H W(
`
`.7
`Q 0.2
`J
`
`~l
`0
`
`i
`
`i
`
`I
`~,
`0.4
`0.6
`0.2
`SINGLE LINK PR08ABILITY OF DESTRUCTION
`
`0.8
`
`~
`!.0
`
`FIG. 6 — Perfect Switching in a Distributed Network — Sensitivity to Lank
`Destruction After 40°/p Nodes Are Destroyed.
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 25
`
`
`
`FIG. 7 -Probability density Distribu#ion of Largest Fraction of Stations in Communication
`
`Perfect Switching, R = 3, J00 Cases, 80% Node Survival, 65%Link Survival.
`
`COMMUNICATION WITH ONE ANOTHER
`LARGEST FRACTION OF STATIONS IN
`
`0.8
`
`a.z5
`
`0.7
`
`0.6
`
`0.5
`
`0.4
`
`YN
`
`.05
`
`.10
`
` 0
` 0
`v 0 z0~
`wQ
`_a
`
`0-~ 5
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 26
`
`
`
`-13-
`
`IIT. DIVERSITY OF ASSIGNMENT
`
`There is another and more common technique for using
`redundancy than in the method described above in which
`each station is assumed to have perfect switching ability.
`This alternative approach is called "diversity of assign-
`ment." In diversity of assignment, switching is not
`required. Instead, a number of independent paths are
`selected between each pair of stations in a network :which
`requires reliable communications. But, there are marked
`differences in performance between distributed switching
`and redundancy of assignment as revealed by the following
`Monte Carlo simulation.
`
`SIMULATION
`
`In the matrix of N separate stations, each ith
`station is connected to every jth s~a~ion by three shortest
`but totally separate independent paths (i=1,2,3,...,N;
`j=1,2,3,...,N; i~j). A raid is laid against the network.
`Each of the pre-assigned separate paths from the ith
`station to the jth station is examined. Tf one or more
`of the pre-assigned paths survive, coirnuunication is said
`to exist between the ith and the j th station. The
`criterion of survivability used is the mean number of
`stations connected to each station, averaged over all
`stations.
`Figure 8 shows, unlike the distributed perfect
`switching case, that there is a marked loss in communi.ca-
`tions capability with even slightly unreliable nodes or
`links. The difference can be visualized by remembering
`that fully flexible switching permits the communicator
`.the privilege of ex post facto decision of paths. Figure
`$ emphasizes a key difference between some present day
`networks and the fu11y flexible distributed network we
`are discussing.
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 27
`
`
`
`-14-
`
`WZO >
`
`- 4 O~
`
`r
`Y Q
`J ~
`Q ~
`~ Q
`
`Z ~
`Qx
`U ~
`
`r =~
`~ VO
`J T ti
`m 3Y
`j cn Q 0.
`o~
`c=n a a~~~w
`F-
`~~
`Oa
`
`O O
`
`a~~~
`
`w Q w Q
`
`~0
`
`0.1
`
`0.2
`
`0.4
`0.3
`0.7
`0.6
`0.5
`SINGLE NODE PROBABILITY OF KILL
`
`0.8
`
`Q 9 I.0
`
`FIG. 6 — Diversity of Assignmer~ vs. Perfect Switching in a Distributed
`Network.
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 28
`
`
`
`-15-
`
`COMPARISON WITH PRESENT SYST~^'IS
`
`Present conventional switching systems try only a
`sma11 subset of the potential paths that can be drawn on
`a gridded network. The greater the percentage of poten-
`tial paths tested, the closer one approaches the perform-
`ance of perfect switching. Thus, perfect switch~.ng provides
`an upper bound of expected system performance for a gridded
`network; the diversity of assignment case, a lower bound.
`Between these two limits lie systems composed of a mixture
`of switched routes and diversity of assignment.
`Diversity of assignment is useful for short paths,
`eliminating the need for switching, but requires surviv-
`ability and reliability for each tandem element in long
`haul circuits passing through many nodes. As every
`component in at Ieast one ouC of a sma11 number of
`possible paths must be szmultaneausly operative, high
`reliability margins and full standby equipment are usual.
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 29
`
`
`
`-16-
`
`IV. ON A FUTURE SYSTEM DEVELOPMENT
`
`We will soon be living in an era in which we cannot
`guarantee survivability of any single point. However, we
`can still design systems in which system destruction re-
`quires the enemy to pay the price of destroying n of n
`stations. If n is made sufficiently large, it can be shown
`that highly survivable system structures can be built--even
`in the thermonuclear era. In order to build such networks
`and systems we will have to use a large number of elements.
`We are interested in knowing how inexpensive these elements
`may be and still permit the system to operate reliably.
`There is a strong relationship between element cost and
`element reliability. To design a system that must antici-
`pate a worst-case destruction of both enemy attack and
`normal system failures, one can combine the failures ex-
`pected by enemy attack together with the failures caused by
`normal reliability problems, provided the enemy does not
`know which elements are inoperative. Our future systems
`design problem is that of building very reliable systems
`out of the described set of unreliable elements at lowest
`cast. In choosing the communications links of the future,
`digital links appear increasingly attractive by permitting
`low-cost switching and low-cost links. For example, if
`"perfect swa.tching"+~ is used, digital links are mandatory
`to permit tandem connection of many separately connected
`links without cumulative errors reaching an irreducible
`magnitude. Further, the signaling measures to implement
`
`,,,.
`See ODC-V. (ODC is an abbreviation of the series
`title, On Distributed Communications; the number following
`refers to the volume in the series. See list on p. 35.)
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 30
`
`
`
`-17-
`
`highly flexible switching doctrines always require digzts.
`
`FUTURE LAW-COST AI.,L-DIGITAL COMMUNICATIONS LINKS
`
`When one designs an entire system optimized for digits
`
`and high redundancy, certain new communications link tech-
`
`niques appear more attractive than those common today.
`
`A key attribute of the new media is that it permits
`
`formation of new routes cheaply, yet allows transmission
`
`an the order of a million or so bits per second, high enough
`
`to be economic, but yet law enough to be inexpensively pro-
`
`cessed with existing digital. computer techniques at the re-
`
`1ay station nodes. Reliability and raw error rates are
`
`secondary. The network must be built with the expectation
`
`of heavy damage, anyway. Powerful error removal methods
`
`exist.
`
`Some of the communication construction methods that
`
`look attractive in the near future include pulse regenera-
`
`tive repeater line, minimum-cost ar "zn~x~i-cost" microwave,
`
`TV broadcast station digital transmission, and satellites.
`
`Pulse Regenerative Repeater Line
`
`Samuel B. Morse's regenerative repeater invention for
`
`amplifying weak telegraphic signals has recently been res-
`
`urrected and transistorized. Morse's electrical relay
`permits amplification of weak binary telegraphic signals
`
`above a fixed threshold, Experiments by various organiza-
`
`tions (primarily the Bell Telephone Laboratories) have
`
`shown that digital data rates on the order of l.S million
`
`bits pex second can be transmitted aver ordinary telephone
`
`line at repeater spacings on the order of 6,000 feet for
`
`~k22 gage pulp paper insulated copper pairs. At present,
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 31
`
`
`
`more than 20 tandemly connected amplifiers have been used
`in the Bell System T-1 PCM multiplexing system without
`retiming synchronization problems. There appears ~.o be no
`fundamental reason why either lines of lower loss, with
`corresponding further repeater spacing, or more powerful
`resynchronization methods cannot be used to extend link
`distances to in excess of 200 miles. Such distances would
`be desired for a possible national distributed network.
`Power to energize the miniature transistor amplifa.er
`is transmitted over the copper circuit itself.
`
`"Mini-Cost" Microwave
`
`While the price of microwave equipment has been de-
`clining, there are sti11 untag}~ed major savings. In an
`analog signal network we require a high degree of relia-
`bility and very low distortion for a long string of tandem
`repeaters. However, using digital modulation together with
`perfect switching we minimize these two expensive considera-
`tions from our planning. We would envision the use of low-
`power, mass-pxoduced microwave receiver/transmitter units
`mounted on low-cost, short, guyed towers. Relay station
`spacing would probably be on the order of 20 miles. Further
`economies can be obtained by only a minimal use of standby
`equipment and reduction of fading margins. The ability to
`use alternate paths permits consideration of frequencies
`normally troubled by rain attenuation problems reducing
`the spectrum availability problem.
`
`Preliminary indications suggest that this approach
`appears to be the cheapest way of building large networks
`of the type to be described (see ODC-V1).
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 32
`
`
`
`-19-
`
`TV Stations
`
`With proper siting of receiving antennas, broadcast
`
`television stations might be used to form additional high
`
`data rate links in emergencies.'
`
`Satellites
`
`The problem of building a reliable network using
`
`satellites is somewhat similar to that of building a com-
`
`munications network with unreliable links. When a satellite
`
`is overhead, the link is operative. When a satellite is not
`
`overhead, the link is out of service. Thus, such links are
`
`highly compatible with the type of system to be described.
`
`VARIABLE DATA RATE LINKS
`
`In a conventional circuit switched system each of
`
`the tandem links requires matched. transmission bandwidths.
`
`In order to make fullest use of a digital link, the post-
`
`errar-removal data rate would have to vary, as it is a
`
`function of noise level. The proble~i thin is to build a
`
`communication network made up of links of variable data
`
`rate to use the communication resource most efficiently.
`
`VARIABLE DATA RATE USERS
`
`We can view bath the l~.nks and the entxy point nodes
`
`of a multiple-user a11-digital communications system as
`
`elements operating at an ever changing data rate. From
`
`instant to instant the demand for transmission will vary.
`
`~:
`Baran, P., Coverage Estimate of FM,_ TV and Power
`Facilities Useful in a Broadband Distributed Network (UFOUQ)~
`The RAND Corporation, RM-3008-PR, March 1962.
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 33
`
`
`
`-za-
`
`We would like to take advantage of the average demand over
`all users instead of having to allocate a full peak demand
`channel to each. Bits can become a common denominator of
`
`loading for economic charging o~ customers. We would like
`to efficiently handle both those users who make highly
`intermittent bit demands on the network, and those who
`make long-term continuous, low bit demands,
`
`COMMON USER
`
`In communications, as in transportation, it is more
`economical for many users to share a common resource rather
`
`than each to build his own system--particu~.arly when
`
`supplying intermittent ox occasional service. This inter-
`mit~ency of service is highly characteristic of digital
`communication requirements. Therefore, we would like to
`
`consider the interconnection, one day, of many a11-digital
`links to provide a resource optimized for the handling of
`
`data for many potential intermittent users--a new comman-
`
`user system.
`
`Figure 9 demonstrates the basic notion. A wide mix-
`
`ture of different digital transmission links is combined
`
`to form a common resource divided among many potential
`
`users. But, each of these communications links could pos-
`
`sibly have a different data rate. Therefore, we shall
`
`next consider how links of different data rakes may be
`
`interconnected.
`
`STANDARD MESSAGE BLOCK
`
`Present common carrier communications networks, used
`
`for digital transmission, use links and concepts originally
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 34
`
`
`
`-~'
`
`NF
`
`s
`
`FIG. 9 -All Digital Network Composed of Mixture of L+nks
`
`LfNK
`
`SATELLITE
`
`-----
`
`--------------
`BURIED CABLE
`
`----------- --,----------
`
`WAVEGUI OE
`
`TEo~
`
`LINES ,~
`TELEPHpNE
`
`~ '
`
`MICROWAVE
`
`STATION
`
`TELEVISION
`
`CISCO SYSTEMS, INC. Ex. 1144 Page 35
`
`
`
`-22-
`
`designed for another purpose--voice, These systems are
`built around a frequency divi.sian multiplexing link-to-link
`interface standard. The standard between links is that of
`data rate. Time division multiplexing appears so natural to
`data transmission that w~ might wish to consider an alter-
`native appxoach-~a standardized message black as a network
`interface standard. While a standardized message block is
`common in many computer-cc:nmunications applications, no
`serious attempt has ever been made to use it as a universal.
`standard. A universally standardized message block would be
`composed of perhaps 1024 bits. Most o~ the message block
`would be reserved for whatever type data is to be transmitted,
`while the remainder would contain housekeeping information
`such as error detection and routing data, as in Fig. 10.
`As we move to t
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ Charge
Still Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site
