On Distributed Communications Series

VII. Tentative Engineering Specifications and Preliminary Design for a High-Data-Rate Distributed Network Switching Node

General Specifications

A. Purpose

A1. Together with suitable Multiplexing Stations and Communications Links, the Switching Nodes shall form a high-data-rate distributed network (see ODC-I[1]).

A2. The specified function of the Switching Node shall be to transfer Message Blocks of information from link to link in a highly efficient manner while remaining generally insensitive to heavy link and node destruction.

A3. The distributed network shall be able to simultaneously process signals from a number of separate Terminal Stations[2] without unfavorable reaction to interference of either internal or external cause.

A4. The complete system shall process military and/or civilian traffic for a large number of subscribers On a common user or common carrier basis.

B. Construction

B1. Lowest-cost construction commensurate with a minimum ten-year overall total system cost shall be a fundamental design criterion.

B2. The system shall provide fully stable operation with any number of Switching Nodes inoperative.

B3. Dual-diversity and other premium construction techniques shall not be used except where they can be shown to reduce overall, ten-year costs.

B4. All nodes shall be built of interchangeable units, replaceable without soldering or adjustments.

B5. Full advantage shall be taken of mass-production techniques, since a large number of identical Switching Nodes will be required, and since much of the equipment in each Switching Node is composed of identical units.

B6. Wherever possible, no individual plug-in box shall be heavier or larger than can be carried by one man.

B7. Bench-test jigs, not forming part of the Switching Node, shall be available to repairmen to permit location of defective flip-flop stages. Individual flip-flops need not be plug-removable, but in the interest of economy, may be soldered, welded, or microminiaturized, and fastened to larger circuit boards.

B8. Electrical components used in the Switching Node shall be of present-day state-of-the-art; all design calculations are based upon components available at the time of this writing (December 1962).

C. Number of Connecting Links

C1. Each node shall be designed to process a maximum of eight duplex links. (Inasmuch as most of the payoff for redundancy of connectivity is obtained at the modest redundancy levels of three or four, this number is deemed sufficient.)

C2. Each duplex (simultaneous two-way operation) link shall be capable of being connected either to adjacent Switching Nodes or to Multiplexing Stations.

C3. The Switching Node shall be capable of processing traffic at whatever data rate is demanded by the connected link, with a maximum rate of 1.54-million bits per second.

C4. When externally synchronized links are used, each link shall be capable of operating from remote timing and be capable of slaving its operations to that of the remote timing device.

C5. The Switching Node shall be capable of operating with any combination of links, using either local or remote timing, and with different data rates over the various connected links.

D. Major Elements

The Switching Node shall be composed of the following major assemblies, which are further divided into major subassemblies (see Fig. 1):

D1 Eight Link Units--Each Link Unit shall be comprised of an Input Link Unit and an Output Link Unit. The Input Link Unit shall provide a termination for the Input Line and shall contain means for error detection and cryptographic decoding of the input signal. The Output Link Unit shall contain means for encrypting outgoing Message blocks and for inserting error detection tags. Each Link Unit shall contain cryptographic key base storage and key generation apparatus. Each Link Unit shall contain local timing equipment to synchronize the input and output message streams.

D2. Eight Buffer Units--Each Buffer Unit shall be comprised of an Input Buffer and an Output Buffer. Both the Input and the Output Buffers shall contain two 32-bit registers.[3] Buffer unit capability shall be to perform serial/parallel and parallel/serial transformations. Each Input and Output Link Unit shall be capable of operating in a serial-bit manner at a timing rate that may be asynchronous to the Central Processor Unit. It is necessary to block the input serial stream into parallel words for most effective processing by the Central Processor. A similar requirement for parallel-to-serial output conversion exists for outgoing signals. Two Buffer Registers shall be provided, so that while one register is in the process of being filled, sufficient time is allowed to the Central Processor to find a convenient moment to process the already-filled register requiring attention.

D3. Central Processor Unit--The Central Processor Unit is a digital computer type subsystem organized along the lines of a multi-sequence processor.[4] Several different computer programs are handled simultaneously by hopping to the Buffer Unit that needs immediate attention. The intermediate results at the points of program interruption are stored so that processing can be continued at the interrupted point without the delay of having to back up. The Central Processor is a time-shared computer simultaneously serving eight input and eight output channels. The Central Processor Unit shall contain a high-speed magnetic core memory, together with necessary read/write amplifiers and word selection equipment. Tentatively, a l-

Basic Timing Calculations

  1. All traffic is processed through the Central Processor.
  2. Worst-case assumption: 8 lines at 1,540,000 bits per second throughput: 1,540,000 x 8 = 12.32 megabits/sec.
  3. Assume that the memory is composed of 4096 words, each 32 bits in length: 4096 x 32 = 131,072 bits.
  4. Assumed storage required for all in-transit messages for all 8 lines: 8 lines x 1024 bits per line = 8192 bits; 3 verification copies are needed (one for each of the last 3 Message Blocks handled) plus a copy of the Block being processed, = 4 x 8192 = 32,768 bits for message storage (the verification copies are called "carbon copies").
  5. To store the handover number table for 1000 stations at 8 bits x 8 lines
  6. Thus, total high-speed memory storage
  7. Assume that all input/output buffers are 32-bit word length. At a throughput rate of 12,320,000 bits/sec, there will be about

    As most of the time will be spent in reading these words into and out of the high-speed core, we shall tentatively choose a l-mcycle time memory. If this proves insufficient, we then face the choice of a faster memory or a longer word length. However, with careful design one can overlap many operations and we shall try to live within this

D4. Power Supply--A Power Supply Unit is needed to convert primary input power to the voltages required by the transistorized equipment. The Power Supply shall contain means to detect a failure of the primary power source and to provide capability for transient-free switch-over to an emergency secondary power source. In the event of restoration of primary power, the power supply shall provide transient-free switch back to the primary power source and provide signals to shut down the secondary power source.

D5. Trouble Box--A Trouble Box shall contain a register whose bit-states are controlled by local switch closures. The Trouble Box shall monitor the status of local burglar alarms, locks on the cryptographic equipment, local temperature, power source status, and signals from the Central Processor indicating any out-of-normal conditions, such as inoperative links. The output of the Trouble Box shall be formed into Message Blocks by a subroutine within the Central Processor and transmitted into the network, directed toward the nearest Repair Depot. Such trouble messages shall be transmitted only upon receipt of an abnormal condition by the Central Processor.

D6. Air-Cooling System--The electronic equipment comprising the Switching Node shall be exclusively of solid-state construction; refrigeration is not mandatory under all environmental conditions. However, as the mean time between failures of the germanium transistorized equipment can be markedly extended by air conditioning, such equipment shall be included. [6] As mechanical air conditioning equipment may be unreliable, its failure shall not constitute sufficient grounds to cause the Switching Node to be shut down, provided that suitable backup capability is provided.

E. Failure Propagation

El. It is imperative that the Switching Node never propagate any possible malfunctions into the remainder of the distributed network. A means of testing incoming signals and disconnecting any link feeding data not conforming to a rigid data format shall be included.

E2. Each of the last four Switching Nodes to process a Message Block shall imprint the Message Block with the Link Number used in transmission; this will allow tracking down any malfunction not detected automatically otherwise.

E3. The logical design of the Switching Node should be premised on expectation of unmanned operation of the nodes and low-quality, accident-prone maintenance personnel.

F. Cryptographic Provisions [7]

Fl. The system design shall include cryptographic apparatus as an integral part of the Switching Node. While this is not a conventional procedure, it is felt that to do otherwise would require the later addition of equipment duplicating many of the functions already being performed within the Switching Node.

F2. Two levels of cryptography will be used in this system: terminal-to-terminal, and link-to-link. Because of the large number of unmanned nodes in the network, link-to-link encryption cannot be considered to be a high-confidence security measure. If end-to-end encryption were used alone, the addresses of all Message Blocks would necessarily have to be transmitted in the clear in order that the Switching Node could determine routing. This would be undesirable, as rapid changes in network loading status would be conveyed to all listeners. However, a combination of link-to-link and terminalto-terminal encryption would appear to extract such a high price from an eavesdropper simply to determine Message Block heading data, that it is probable that only very highly classified traffic need be given the terminal-to-terminal double encryption treatment. Thus, it is tentatively suggested that the bulk of the traffic can be safely handled by link-to-link encryption. As a practical matter, all traffic in the network can thus be considered as being encrypted.

F3. All cryptographic operations shall be performed in the Link Units, and none in the remainder of the system. However, it is necessary to protect the entire system since message headings are in the clear within the Central Processor Unit.

F4. Each separate Link Unit shall contain a separate Cryptographic Key Box, sealed by both a key and a combination lock. Any movement of the combination lock or key shall be transmitted to the Trouble Box for retransmission.

F5. Each Cryptographic Key Box shall contain two or more key bases for transmission and two or more key bases for reception, together with means of synchronization.

F6. One of the two key bases shall be changed at least once each month. On the following month, or applicable period, the previously unchanged key base shall be changed. The period of use of a key base shall be chosen to allow a single person to change the keys sequentially at both ends of a link (instead of requiring two people, as would be the case if only one key base were used).

F7. The key base shall be of a plug-in type and be fundamentally volatile in nature; i.e., the information contained in the key base shall be easily and rapidly destroyed if any attempt is made to tamper with or determine its contents.

F8. The resynchronization used in the cryptographic apparatus shall be such as to permit an automatic pull-in after the communications link has been interrupted for as long as twelve hours.

F9. To permit low-cost cryptographic clocks to be used and to meet the requirement of a long link-interrupt time, each Message Block on each link shall contain a Block Sequence Number. Tentatively, the Block Sequence Number will be eight bits (modulo 256) in length (see below). This number is incremented by one for each successive Message Block.

F10. The Key Base Counter shall be capable of operating without recycling or repetition for a period much in excess of the time between key base changes.

F11. An eavesdropper's knowledge of the construction of the Switching Node, his access to input traffic, and his knowledge of the data format shall be assumed. The generator key shall be undecipherable using any known technique of analysis and using any known computer, working full time on such an analysis for a period of up to five years.

F12. When no valid traffic is being sent, dummy traffic derived from a noisy'' generator shall be sent as filler.

F13. The Switching Node shall be housed in a structure able to delay a forced entry in excess of one hour.

F14. Automatic alarms shall allow automatic destruction of all information in the core of the Central Processor and the key base upon detection of unauthorized tampering.

F15. Switching Nodes shall be situated so that local police protection can be obtained if needed.

Cryptographic Clock Drift Calculation

  1. Assume that the link between two Switching Nodes is operating at 1,540,000 bits/ sec.
  2. Assume that the Message Block length is 1024 bits.
  3. Assume that both the transmitting node and the receiving node are in cryptographic synchronism at time t = 0.
  4. Assume that the link between the two Switching Nodes is interrupted at t = 0.
  5. Assume that each Link Unit contains an inexpensive piezoelectric time base that does not drift more than 10-6 sec/sec.
  6. Assume that each Message Block contains a Block Sequence Number.
  7. Assume that the interrupted link is restored at t = 12 hr.
  8. The number of bits necessary to contain a number equal to the maximum number of drifted Message Blocks is based on the following calculations:

    1. Assume, as a worst-case condition, that the drift of both clocks is in opposite directions.
    2. Total number of blocks in 12 hr

G. Reliability

G1. while unit reliability in a distributed network is not needed to the same degree as in the case of conventional communications network elements, conservative design practice shall be used to produce an expected mean time between failures (MTBF) of not less than 30 days for the Central Processor and Power Supply or for any single Link Unit. (See p. 77 for a detailed estimate of the proposed implementation's MTBF reliability values.)

H. Servicing Provisions

H1. All Switching Nodes shall be capable of unmanned operation.

H2. Link failures shall be repaired during routine test and maintenance periods.

H3. A complete Node failure shall, wherever possible, be indicated by a Trouble Box indication to adjacent Multiplexing Stations. In such cases, a repairman shall be detached to effect repairs.

H4. The field maintenance repairman shall narrow trouble location to within a single major assembly or subassembly, but when in the field shall generally not pin-point the trouble to a specific component. The field maintenance repairman shall carry a full complement of major replacement assemblies in his repair truck. Pin-pointing of faults in specific components and the replacement of defective components shall generally be performed at a Maintenance Center.

H5. All components used shall be commercially available to eliminate the necessity for the maintenance of large stocks of components.

H6. All field maintenance personnel shall have appropriate security clearances.

I. Error Rate [8]

I1. The Switching Node shall be capable of an overall user-to-user system error rate of less than one in 108 bits or Message Blocks,[9] provided that the raw error rates of the links comprising the distributed network have an average value of less than one in 105 bits in error.[10]

12. Inasmuch as the statistical error distributions of the low-cost transmission media being considered for use within the distributed network have not yet been fully determined, the calculations for error distribution shall not assume a Gaussian, hyperbolic, or similar distribution that could. introduce an optimistic bias into the error rate calculation.

Error Rate Calculation

  1. Assume that automatic error detection and repeat transmission shall be used.
  2. Assume that a Message Block length of 1024 bits is used, including error detection symbols.
  3. Assume the cyclic code method described by W. W. Peterson and D. T. Brown is used.[11]
  4. Using the cyclic code technique, the binary Message Block to be transmitted is divided by a fixed Boolean polynomial. Both the Message Block (less the check digits) and the remainder (which forms the check digits) are transmitted. The receiving station performs a verification Operation on the received message using a Boolean polynomial identical to that used in the original transformation. If there are no errors in transmission, the remainder is zero. But, if there is an error in transmission, it can be shown that the probability of creating a nonzero remainder can be made arbitrarily low by proper choice of the Boolean polynomial used in the two operations. This coding scheme is particularly attractive for the proposed system inasmuch as the divide and multiply operations are easily performed by a short shift register with feedback connections. Further, the technique is highly efficient, requiring only a small number of check digits for very powerful error filtering.
  5. Consider, for example, the use of the following coding polynomial, P(X) = 1 + X2 + X13 + X22. A cyclic code error detection encoder or decoder using this polynomial can be built using only a 22-stage shift register. Only 2.3 percent of the transmitted data rate need be expended on error detection.
  6. According to Peterson, this resulting code should be able to detect: two bursts of combined length 12 or less; any odd number of errors; a burst of 22 or less; 99.99996 per cent of the bursts of length 23; 99.99998 per cent of longer bursts.
  7. If even better performance is required, it can be obtained by the choice of a slightly longer coding polynomial.
  8. As a worst-case assumption in the specific system of interest, assume a raw link error rate of 1 x 10-5. Since the error detection scheme is perfect for error blocks of less than 12 bits, we could then expect only about one such 12-bit or greater error in about 1200 Message Blocks, each 1024 bits in length. Of these, 99.99996 per cent will be caught. Thus, the actual probability of an undetected error passing through the system will be equal to the probability of an error occurring in a block, times the probability of the error passing through undetected:

  9. Another, and completely different, source of errors should also be considered. This is the possibility of a catastrophic Switching Node failure occurring just after a Switching Node issues a verification of correct receipt of a message.

    If a conservative mean time between failure of one month is assumed for the Central Processor Unit within the Switching Node, then such an occurrence can take place only once during this period. The probability of loss of a message due to this cause is then approximately:

  10. We can expect three primary sources of errors within the system:

    1. The probability of an undetected error caused by a noisy link passing through the error detection filter, equals 3.32 x 10-9
    2. The probability of a Switching Node failure, after having sent a receipted acceptance to an adjacent node, equals 3.87 x 10 10-9
    3. The probability of a circuitous path being taken during a transient network overload, longer than about twice the minimum shortest network extremity path-length, is less than 10-8, under the worst-case assumption of a heavily loaded network.[12]
  11. Thus, it is felt that the target average overall 10-8 system error rate appears to be an attainable goal.

J. Link and Link Unit Specification

J1. Each Switching Node shall have provision for accepting up to eight Link Units.

J2. Each Link Unit shall be capable of simultaneously sending to and receiving from any adjacent Switching Node.

J3. Each Link Unit shall be able to operate at data rates up to 1,540,000 bits per second.

J4. Each Link Unit shall have means to permit adjustment of the transmission and reception rate so as to make most economic use of the transmission facility. It shall be sufficient that the Link Unit be able to operate at up to six different data rates.

J5. Each Link Unit shall have means to operate either on independent timing or to have its timing slaved to its remotely terminated adjacent Switching Node.

J6. In the event of a line failure or propagation fade, the Link Unit timing shall be capable of pulling into synchronization after circuit restoration within a period of up to 12 hours after the time of failure.

J7. The Link Unit shall be designed to operate with unreliable and noisy communications links. A communication line shall be considered as operating well if it is exhibiting a short-term error rate of 10-5 or better.

J8. To avoid the necessity of transmitting DC levels,[13] every sixteenth bit shall be selected so that not more than 15 consecutive bits are ever transmitted with the same polarity.

J9. It shall be assumed that all communication lines are exposed to public access, but it shall be impossible for traffic inserted into any line by an outside agent to be propagated within the system. (For example, if one were to record traffic on a line and play it back a short time later, such traffic should be automatically rejected and not be allowed to propagate.)

J10. Input timing jitter shall be less than

J11. Output timing jitter shall be less than

J12. Each Link Unit shall contain internal cryptographic key generation equipment able to create binary streams in excess of three months operation at 1,540,000 bits per second.

Cryptographic Pseudo-Random Generator Calculation

  1. A cryptographic generator period of three months is assumed.
  2. A shift register has a maximum period of N2N bits, where N equals the number of stages of the register.
  3. Assume a 1,540,000-bit rate.

[1] ODC is an abbreviation of the series title, On Distributed Communications; the number following refers to the particular volume within the series.

[2] The Terminal Stations are connected to the Switching Nodes via the Multiplexing Stations.

[3] 32-bit registers are tentatively chosen as a compromise between the amount of equipment required for longer word length, and the limitation of the cost of high-speed random access computer memories if one attempted to use a shorter word length.

[4] Ackley, J. N., "The Multi-Sequence Computer as a Communications Tool," Proceedings EJCC, No. 16, 1959, pp. 114-119.

[5] The "handover" concept is fully described in ODC-I.

[6] Since the time this section was first written, it has become apparent that low-cost, silicon transistors are available, eliminating much of the need for life-prolonging cooling.

[7] The government agency responsible for cryptographic considerations does not normally enter initial system design discussions. However, the high data rates and the large number of nodes used make it advisable that preliminary cryptographic requirements be considered by the designer of the Switching Node (see ODC-IX).

[8] Inasmuch as this system shall be used to transmit digital data between computers, a very low overall system error rate is specified.

[9] It is assumed that if a single bit is in error, the entire Message Block is in error; if a Message Block is in error, all bits of the Block are in error.

[10] Expected link error rate is one in lO-6 or less (see ODC-VI).

[11] Peterson, W. W., and D. T. Brown, "Cyclic Codes for Error Detection," Proceedings of the IRE, Vol. 49, No. 1, January 1961, pp. 228-235.

[12] See ODC-III.

[13] Required in certain types of data links, but not in the mini-cost microwave link described in ODC-VI.

Part Two: I. Detailed Flow Charts