Text is from PROCEEDINGS OF THE IEEE, VOL. 60, NO. 11, NOVEMBER 1972 pp 1408-1423. © IEEE 1972
Manuscript received July 21, 1972. This work was supported by the National Science Foundation under Grants GK 31469 and GK 33352, and by NASA under Grant NGR 33-006-020.
M. Schwartz and R. R. Boorstyn are with the Polytechnic Institute of Brooklyn, Brooklyn, N. Y. 11201.
R. L. Pickholtz is with George Washington University, Washington, D.C.
Terminal-Oriented Computer-Communication Networks
MISCHA SCHWARTZ, FELLOW, IEEE ROBERT R. BOORSTYN, MEMBER, IEEE AND RAYMOND L. PICKHOLTZ, MEMBER, IEEE
Invited Paper
TYMNET
General Electric Information Serivces
NASDAQ
CSC INFONET
Abstract—Four examples of currently operating computer-communication networks are described in this tutorial paper. They include the TYMNET network, the GE Information Services network, the NASDAQ over-the-counter stock-quotation system, and the Computer Sciences Infonet. These networks all use programmable concentrators for combining a multiplicity of terminals. Included in the discussion for each network is a description of the overall network structure, the handling and transmission of messages, communication requirements, routing and reliability consideration where applicable, operating data and design specifications where available, and unique design features in the area of computer communications.
INTRODUCTION
DATA NETWORKS of various kinds are currently in operation, are in the process of being set up, or have been proposed for future development and construction. They include large-scale computer networks (e.g., the Advanced Research Projects Agency (ARPA) network and similar networks under development in Europe and elsewhere), multipurpose data networks (e.g., AT&T, Western Union, and the system proposed by Datran), airline reservation systems, bank transaction systems, retail chain dataflow systems, stock information and securities exchange networks, medical data networks, geographically dispersed timeshared computer systems operated by various computer service organizations, public service networks (combining fire, police, health, and other vital functions) under development in various urban areas, educational data networks, etc. The list is seemingly endless and growing larger literally day by day.
Although the applications and uses for which they are intended cover a broad spectrum of sometimes overlapping data-flow functions, and although the designs entailed may cover a seemingly bewildering variety of approaches, all these networks are similar in their symbiotic mix of computers and communications. It is for this reason that we find them labeled computer-communication networks. It is also no accident that the traditional common-carrier companies, the computer manufacturers, and computer-communication companies are all vitally interested in this burgeoning field.
Although the variety of networks in existence or under development is large, and their design philosophies are often complex—often based as much on questions of history and original applications for which they are intended as on up-to-date technical and cost considerations—a detailed overview may bring out similarities in structure and design (as well as differences), and inject some order into the seeming chaos. It is for this purpose that this tutorial paper has been written.
It is geared to the nonspecialist in the field of computer communication networks, interested in obtaining an overall view of how the interaction of computer and communication facilities is used to manage the data flow in rather complex networks.
We focus here by way of example on terminal-oriented networks, those designed to accommodate input-output devices, such as Teletypewriters, push-button control units, and their associated display devices, where they exist. The network design and design philosophy is then predicated on providing the appropriate services to these terminal-type users. Four existing networks will be described in some detail so that comparisons can be made in the overall system design, in message formatting and processing, in data-handling capability, etc. These particular networks (the NASDAQ over-the-counter stock quotation network, the Computer Sciences Infonet, the Tymshare TYMNET, and the GE Information Services Network) are typical of many of the other networks in existence and were chosen because information concerning their design and operation was available or could be obtained readily. (Acknowledgment is given at the end of this paper to individuals consulted in the gathering of the necessary information.)
Except for TYMNET, the pattern of data flow in these networks is generally inbound from a particular terminal to a large computer (or group of computers) that carry out the data processing and/or data retrieval that may be called for, and then outbound back from the computer to the same terminal. This contrasts with a more general network in which data could be switched or routed from one terminal to one or more others, geographically distant, either going through a computer or sets of computers first, or directly to the other terminals. TYMNET provides an example here. The Western Union Telex and TWX systems, among other networks, the AT&T public switched network, and the proposed Datran system provide other examples of this more general type of message routing. The basic concepts of network design and data handling, derived from a comparative study of these four network examples, are thus appropriate to a large class of networks, including those with more complex routing strategies.
OVERALL VIEW
Before undertaking a summary of the four networks mentioned, it is appropriate to attempt an overall view of the terminal-oriented computer-communications network. This will serve to put the networks described in focus and to enable some sort of comparison of network designs and operations to be made.
Two distinct tasks may be distinguished in the design of any network: 1) the problem of putting a terminal on line; when it desires service, combining its messages with those of other, geographically contiguous terminals; and 2) the problem of then directing the resultant message stream to the appropriate destination for further processing. We can call these tasks" respectively, message combining, concentration, or multiplexing, and message distribution or routing.
In the message-combining phase the individual message characters, once in the system, may be recoded to a standardized message character format (generally the United States. of America Standard Code for Information Interchange (USASCII) 8-bit character code) for use throughout the network, if different types of input devices may be used in the network. Additional bits or characters may be added for error control, addressing, synchronization, and other necessary control purposes. The combining function itself may be carried out in a variety of ways: a polling technique may be used in which terminals associated with the particular concentration point are regularly (or irregularly) asked to transmit any data ready to enter the system. The combiner may have a fixed number of input ports to which the terminals are either always connected, or to which they may be connected, if not already occupied. Messages may be fed directly into a buffer in the combiner; after address bits are added, and then the buffered messages taken out, either sequentially or following some priority scheme.
Note that the combining procedures [13] vary from rather simple multiplexing schemes to sophisticated concentration schemes requiring a small computer [14] to carry them out. The incoming messages may be directly multiplexed onto outgoing trunks, using either frequency-division modulation (FDM) or time-division modulation (TDM) trunks, or multiplexed onto the outgoing trunks after buffering and some preliminary processing of the type noted previously. Corresponding to these two alternatives, two types of networks are currently in use or under development-the line- or circuit-switched type and the message-switched or store-and-forward type.1 (Some planned networks call for a combination of the two.) In the line-switched system multiplexers are used throughout the network to allow entry of messages and their continuous transmission throughout the network. Here, as in the analogous public switched-voice telephone network, a terminal desirous of entering the network calls in its destination. A complete path is set up, from end to end, and then, once the complete connection is established, messages may be multiplexed into the system. In the message-switched case a message may enter the system at a message concentrator, queuing up or being stored in a buffer until the outgoing trunk is ready to accept it, and then work its way through the network, from concentration point ("node") to concentration point, queuing up at various points if necessary, until the destination is reached.
The line-switching system, requiring only multiplexers for the combining function, may be considerably less costly, equipment-wise, than the equivalent message-switching system. The latter requires as its combiner a small computer (minicomputers are often used). These latter devices have been variously labeled communications processor, programmable concentrator, message concentrator, and the like [14], [15]. Because of their computational capability these devices can, however, carry out some processing normally associated with larger computers in a system, and they may do the routing and switching associated with switching computers in the line-switched system. They are of course quite flexible and can be programmed to accept various types of terminals at their inputs; they may carry out some control functions, etc. Because of their buffering capability they can smooth out statistical variations in the incoming data—number of terminals vying for service, lengths of messages and frequency of message transmission of a particular terminal, etc.
For example, a terminal that transmits short messages spaced at relatively long time intervals apart, once connected into the system, might find a programmable concentrator type of combiner and message switching throughout the network more economical for its purposes. For the terminal then shares the network facility with the other terminals connected in: it is charged only for the time that messages are actually transmitted, and messages from other terminals fill in the empty time gaps. The same terminal connected to the line-switched network must pay for the entire time it is connected, just as in telephone transmission, for it has a channel dedicated to its use throughout the connection time. Conversely, a data terminal with relatively long messages, spaced close together, may find the line-switched network more economical for its purposes. But this is not a clear-cut situation—it depends on trunk line costs, type of service available from the common carrier if leased lines are used, etc. (For example, the same terminal transmitting short messages may receive long messages back from the computer. Full duplex lines—those capable of handling two-way traffic simultaneously—are commonly used, and the line capacity would then be dictated by the outbound computer-user message stream. The inbound lines are then very inefficiently used, but current communication line costs do not warrant any change in this procedure.) The systems to be described in the sections following provide message switching in the sense previously described. (TYMNET system personnel prefer to use the words virtual line switching to describe the function of their network, however, because of the use of dedicated paths or routes once a connection is set up. This will be discussed in more detail in the next section.)
The message distribution or routing task, once the messages from geographically contiguous terminals are combined and formatted for transmittal, consists, of course, of directing the messages to their appropriate destination. Various design questions immediately arise here. In mentioning message concentration or multiplexing we did not at all indicate the placement or location of the combining point. This is part of the rather broad or global question of overall network design [16 ]—where shall the network nodal points be placed? (These are the points where terminals are concentrated or multiplexed, where messages may be dropped, where they may be further multiplexed with other message streams in a hierarchy of multiplexing procedures, where they may be rerouted, etc.) Involved here are questions of cost, reliability, network response or delay time, trunk or link capacities, etc. These are all interrelated and much of the network design, as will be noted in the examples following, involves a mixture of some analysis, simulation, and engineering "feel" for the problem.
Specifically, what are the tradeoffs, cost-wise, in adding more concentrators to cover widely dispersed terminals and decreasing cable costs correspondingly, or vice versa? What capacity (in bits per second) trunks are needed to cover the anticipated traffic between nodes (these are called the links of the network)? How many terminals can a given combiner handle? Both of these latter two questions are related to the network delay or response time, a typically important constraint in network design. In the case of a message-switched network, increasing trunk capacity decreases the queuing (buffer) time of messages as they traverse the network and hence reduces the overall response or delay time. In the case of a line-switched network, the chance of a busy signal is obviously reduced as capacity is increased. In addition, as provision is made for more terminals to be handled at any concentrator, the outgoing trunk capacity must be increased correspondingly to handle the additional traffic and keep the response time acceptable. The network performance criterion is sometimes given as an average or median response time, or some related measure. Alternatively, it may be given in terms of a tolerable busy-signal probability.
Reliability also plays an extremely important role in network design [16]. Systems are often designed to ensure at least two alternate paths between any two nodes in the network. In some cases this is accomplished by using two geographically separate trunk connections, in others by designing the network topology to ensure an alternate route between any two nodes if any link in a given route is interrupted.
Finally, once the network design is established, routing strategies must be established in those networks in which messages may traverse several modes before arriving at a destination. Examples will be given in the systems to be considered of strategies adopted in practice. It is apparent that the routing procedures are related to the reliability constraint. For should a link in the network fail, an alternate route must be used. Routing is also an attempt to equalize the traffic and response time throughout the network—messages should be sent via routes that carry relatively less traffic and that are relatively less error prone than other routes. The route set up for a given user-destination pair may be globally determined by a centralized computer that monitors the state of the entire network, or, locally, by each node making estimates of least time to any other node in the network and corresponding paths to follow. In the message-switched networks the nodal processors are often used to carry out the processing needed to determine the message routing or to direct messages following the directions from the centralized source. The routing strategy in the line-switched network case is generally determined beforehand and used to search out a complete route or circuit before allowing messages to enter the system. In the message-switched network case, the routing can be adaptive and updated periodically, or on demand, as traffic conditions change.
TYMNET
Overall Network
A recent article has stressed the fact that time-sharing companies have in the past two years moved dramatically beyond their initial phase of providing service for the "one-time problem solver" [1]. The networks they have set up have begun to emerge as national computer-communications networks, in the fullest sense of the words: they are used to provide computer power and access to data bases for various businesses, often replacing or augmenting expensive in-house computer operations, as well as providing a data-communications facility for connecting user computers and remote terminals.
Tymshare, Inc.'s TYMNET computer-communication network exemplifies this change in function and approach. The network, as shown in the accompanying map (see Fig. 1), is a sophisticated data-communications network employing 80 communications processors deployed all over the country to access 26 large host computers located at computer centers in Cupertino, Calif.; Englewood Cliffs, . N. J.; Houston, Tex.; and Buffalo, N. Y. (The European network CETNET has been operational for two years with one XDS 940 computer located in Paris. The two networks were scheduled to be connected in September, 1972.) The communications processors, called TYMSATS, use modified Varian 620 computers. Twenty-three of them serve as so-called base computers (base TYMSATS), each associated directly with its own central processing unit (CPU); the other 57 form remote nodes (remote TYMSATS), through which individual terminals gain entry to the system. The 26 large computers include 23 XDS 940's and 3 PDP-10's.
The network topology, as shown in the map (see Fig. 1), has not been laid out following any specific design strategy. It has essentially just "grown" in response to customer's needs or to the business expected in various areas. Unlike some of the other time-shared networks (see, e.g., the section on the GE network following), the network configuration is basically that of a multiple ring rather than a star, although, depending on the traffic expected at any node, some of the nodes are connected daisy-chained or in a star fashion, in addition to the ring configuration [2].
Most of the 48 links connecting the various nodes are made up of leased 2400-bit/s full duplex trunks. NEED FOOTNOTE Any one nodal concentrator may have as many as 200-300 terminals associated with it. But no more than 31 terminals at anyone time can have full duplex access to the concentrator. A terminal joining the network gets a local number to call, connecting to the closest node. The network may be extended with the addition of a new concentrator if business in anyone nodal region approaches or exceeds 31 simultaneous users during the busy hour.
Since the network is of the store-and-forward type with computers used to carry out processing and routing at each node, it would normally be called a message-switched system in the sense indicated in the Introduction to this paper. TYMNET personnel and publications [3] prefer to consider the network a line-switched network in a virtual sense, however: a user calling into a particular node is assigned a route or "virtual channel" (circuit) through the network to the appropriate CPU. The user keeps that virtual channel throughout transmission. The route is assigned by a supervisory program maintained at one of the CPU's. The routing algorithm, in selecting the set of links between user remote TYMSAT and the appropriate CPU that comprises the virtual channel, chooses an unused virtual channel and avoids links that are heavily loaded or that have a high error rate. A heavily loaded link is one that is carrying 57 users over that link in the same direction. A high error rate means at least 10 detected errors in transmission per minute. NEED FOOTNOTE
Because of the ring configuration, traffic over any one link, in a given direction, may be either outbound (computer to user) or inbound (user to computer). There is no distinction made as to direction, unlike the star configuration. Tymshare personnel indicate that the "virtual-channel" or line-switched approach used provides more efficient message transmission: the overhead (nondata characters transmitted) is reduced since message addressing is much smaller than in the usual message-switched case. (As will be seen later in discussing the message format, a one-character virtual-channel number is used for addressing,) Message transmission in the computer-to-user direction (the bulk of the traffic carried, as in most time-shared systems) can approach 80-percent efficiency, rather than the 60-percent figure that might be associated with message switching.
Message Transmission
Although TYMNET is often used for computer-to-computer communication and for driving high-speed peripherals, it was primarily designed for the 10-30 character/s terminal. The system allows any 10-30-character/s terminal device to access the network. An identifying character is first typed in. A software program at the incoming TYMSAT uses the character to identify the tvpe of terminal, code used, and speed of character transmission [4]. All characters following are then converted to American Standard Code for Information Interchange (ASCII) (8-bit) code [5] for internal network transmission.
A user calling the TYMSAT with which he is associated is connected in through one of the 31 ports of the TYMSAT. The identifying character he types in, in addition to allowing code conversion at the TYMSAT, sets up a special duplex path to the network supervisor. The supervisor asks for the user name and password, and then uses these to determine at which CPU the user file is located. (Alternatively the user may ask for a particular one of several computers in which he has files.) The supervisor then proceeds to determine and set up the virtual channel mentioned. (This takes of the order of milliseconds.) It sets up the channel by sending control information to each TYMSAT along this route, causing the appropriate entries to be made in each TYMSAT's switching tables. These tables essentially associate a particular channel number with one of the outgoing links from the TYMSAT in question.
Any given TYMSAT handles traffic from its 31 ports as well as traffic coming through from the adjacent nodes to which it is connected. Messages from all these sources are stored (in ASCII code) in character buffers as they arrive. The character buffers as a group occupy 1200 words of core (2400 characters) in the concentrator. This space is dynamically allocated as needed. Each character—whether locally inputted from one of the 31 ports or passing through—has a virtual channel number associated with it.
Message transmission to adjacent nodes is accomplished by assembling a block of characters, from those stored in the buffers, for each outgoing link. A block is assembled by searching through the character buffers, on a first-come-first-served basis, for those characters with virtual channel numbers associated with that particular link (i.e., those virtual channels associated with that link in the TYMSAT switching table). The search continues in round robin fashion (returning to the first buffer queried for additional characters that might have been entered in the interim) until a maximum of 66 characters, including control and error detection characters to be discussed below, have been assembled. If fewer than 66 characters are assembled, whatever is available is transmitted. If there are no data to be sent, control characters only are transmitted.
The format of the block as finally assembled is shown in Fig. 2. A 16-bit header is first transmitted. This consists, in order as shown, of a 4-bit synchronization pattern, a 4-bit word count, and 8 bits for block number and acknowledgment. (These are discussed later.) Each message associated with a particular user then follows, The user message, called a logical record, consists first of a one-character virtual channel number, then of a one-character count, telling how many data characters are to follow, followed by the 8-bit data characters themselves. additional logical records, for different users, follow. The final 32 bits or 4 characters of the block are used for error detection. They consist first of a 16-bit spiral check sum and then a 16-bit vertical check sum.
No more than one such 66-character block is transmitted every 0.25 s. This corresponds to 264 characters/s or 2112 bits/s to be transmitted over the 2400-bit/s trunks. There will always be at least one block sent every half second because the data rate control logic executes every half second, Experience has shown that this format will accommodate up to 50 users over a 2400-bit/s link and up to 100 on a 4800-bit/s link. This is based on an average user transmission rate of up to 4 characters/s [2]. As noted earlier, this information is used in the routing strategy for the system.
The block as transmitted is disassembled at the next node, at the end of the link, the message characters are stored in the appropriate buffers at that node, and the block assembly process is then again repeated, as before.
Error correction is carried out by retransmission of the entire block if necessary: as soon as a block is received, the number of that block is returned to the sending TYMSAT as part of the next outgoing block on the reverse path of the link in question. If a block is not acknowledged for any reason, it is automatically retransmitted. by the sending TYMSAT. If an error in the block is detected at the receiving TYMSAT, the block is disregarded and not acknowledged. Retransmission then automatically takes place. In addition, notification of the error is sent to the supervisor which keeps track of error counts on all links. As noted earlier, this information is then used in establishing a user-computer route. (Links with more than 10 block errors/min are avoided.) The check-sum technique used for error detection (see Fig. 2) provides a very low error rate, theoretically of the order of 1 bit in 232 or the order of 1 in 109 bit transmitted.
Errors occurring between the user terminal and the connected TYMSAT are detected visually by remote echoing: the TYMSAT itself retransmits each character as received over the full duplex local loop, causing the terminal keyboard to print. (Originally characters were echoed by the CPU, but this caused an unacceptable time lapse between the time of the user depressing his key and the printing of the character.) The TYMSAT does the echoing only if no other characters are waiting to be printed, if no characters are known to be coming down the channel from the CPU, or if it has not been signaled by the CPU not to echo. If the remote TYMSAT does not echo the character, the CPU is so notified. The CPU itself then echoes the character at an appropriate place in the character stream [2].
Traffic-Handling Capability
As noted earlier, each remote TYMSAT is capable of accommodating up to 31 simultaneous users. This provides some indication of the possible number of simultaneous users on the network. In addition, each CPU has 60 input ports, each corresponding to a different user. This corresponds to the order of 1600 simultaneous users. In practice the traffic carried peaks at about 1000 users. Typically a peak figure of 24-30 users may be accessing one of the XDS computers while 40-50 may be accessing the PDP-10's.
In addition to this use by customers accessing the network's own computers, the TYMNET system has begun to take on a network service function. This is precisely one of the areas of applicability mentioned at the beginning of this section on TYMNET. In this service the system provides routing and connection facilities while the customer provides his own computing facilities, This service is provided under FCC Tariff 260 "Joint User" section. As an example, the National Library of Medicine uses TYMNET to provide access by remote terminals located anywhere in the United States to its own computer facilities (several 370/155's and a PDP-9) distributed at several locations. Such a service presumably provides higher efficiency at less cost than would be possible if the customer were to set up his own network using leased lines, for the network in this case is shared with the other TYMNET customers. The customer in this case also shares in the increased dependability and reliability made available through the network rerouting and error-detection capabilities.
The reader may have wondered how 2400-bit/s trunks could possibly handle all the traffic that might be encountered, particularly on links close to the CPU's. The routing strategy, avoiding heavily loaded links, serves to distribute the traffic more smoothly over the network and thus helps to avoid traffic pileups. In addition, there is a computer-to-user direction shutoff feature that prevents traffic from building up. This is particularly necessary in buffering the output flow from the CPU. For the computer output rate may run as high as 1000 characters/s, yet the terminal to which it is directed may only be able to print 10 characters/so Intermediate node buffers are limited in size and so cannot handle too large a data input. To prevent data from piling up on any one channel, a given sending node subtracts the number of characters sent out over that channel from a counter associated with the channel. When the counter reaches zero, no more characters are sent over that channel. Twice a second the receiving node sends 1 bit back to the sending node, indicating whether it has less than or more than 32 characters in the receiving buffer for the channel. If it has less the sending node resets its counter to 32 and starts transmitting again [3]. (For high-speed channels that accommodate 120 characters/s, a count of 128 is used.)
Final Comments
Some features utilized in the TYMNET system bear expansion and further discussion. First, note that minicomputers are used throughout the network in a manner similar to the IMP's and/or TIP's in the ARPA network: they serve as interfaces to the larger computers; they connect computer centers for intercomputer communications; they serve as intermediate nodes in the routing of messages; and finally they serve as terminal multiplexers and drivers. Since most of the functions are carried out under software control, there is built-in flexibility. New types of terminals coming on the market can be readily accommodated by simple changes in a program.
The cost of minicomputers has been decreasing rapidly with a concomitant increase in speed. Since each node is essentially an independent module, new hardware and software can be phased in one unit at a time. (The software used at present at each node is of the order of 4000 instructions. The special hardware used is also very primitive. It is therefore relatively easy to convert to another minicomputer if necessary. )
Some words on the supervisory concept are in order [3]. As noted earlier, a supervisor handles channel assignment and routing. This is actually a program run under time sharing in one of the XDS 940's. In addition to establishing an initial route or virtual channel, the supervisor will reroute all circuits affected by node or link failures, if an alternate route can be found. (Node failures have in practice been infrequent, averaging 1.4 failures/year/TYMSAT.)
To guard against supervisor failure, three other host computers have supervisory programs running as well, arranged in a predetermined pecking order. (The CPU in Paris will contain a supervisor as well when the two networks are joined in September.) These dormant supervisors receive messages from the active supervisor about once a minute, confirming its activity. If a confirmation is not received, the next supervisor in order takes over. The dormant supervisors have no prior knowledge of the state of the network, so that the new supervisor must learn the network. It does this by probing the network systematically node by node and link by link until an up-to-date representation of the network (including, for example, all virtual channels and the contents of the nodal switching tables) is constructed in its memory.
This centralized supervisory control provides the following features [3].
1) The individual nodes have no global knowledge of the network. They may thus be handled independently. The software in one does not affect the software in another, simplifying any debugging necessary.
2) A newly activated supervisor has no prior knowledge of the network, It simply accepts the network configuration as it exists. Changes in the network are thus easily made.
3) The fact that the supervisory programs are run under time sharing provides debugging advantages.
4) All global information about the network is available at one place: this facilitates diagnostics, record keeping, and debugging.
GE INFORMATION SERVICES
Overall Network
The GE Information Services Network is also an example of a computer-communication network that has in the past few years evolved from an initial phase of providing timeshared computer service for the problem solver to the current one of providing facilities as an information network. For example, it now offers a service called Interprocessing, in which files may be transferred from a customer's own computer to the GE System computers for accessing by the customer's own terminals that may be geographically dispersed throughout North America and Europe. Pontiac Division of General Motors, as an example, uses this service to provide up-to-date information to several thousand car dealers [1].
The network, as shown in the accompanying map (see Fig. 3), covers the United States, portions of Canada and Mexico, plus Europe. The configuration follows a hierarchical or a tree-like structure: individual terminals are connected into remote concentrators located in 13 U. S. and 3 European cities. (These are indicated as distribution points in the map.) The remote concentrators are in turn connected to central concentrators located at the main computer center in Cleveland, Ohio. The central concentrators then access the computer systems that are at the heart of the network.
The approximately 50 remote concentrators consist of modified Honeywell 416's with 16K word (16-bit) memory. The concentrators have 48 ports connected to the public switched telephone network, via local loops, foreign exchange lines, or multiplexed lines. A customer wanting to access the network dials a number that connects him to an available port. At the periphery of the network there are some FDM multiplexers used that combine up to three ports before coming in, on a local loop, to the remote concentrator. Local telephone numbers are available in more than 250 cities.
Most of the communications cost of the network is in the local loops, and the remote concentrators are generally placed to reduce these costs. There may be several remote concentrators located in heavy load regions.
The remote concentrators are connected via full duplex 4800- or 9600-bit/s lines to the central concentrators in Cleveland. Two alternate paths or circuits are available to maintain reliability. The central concentrators consist of GEPAC 4020 computers. Each central concentrator may have a maximum of eight remote concentrators connected to it. A central concentrator in London, England, fed by three remote concentrators for European traffic, is also connected to the central concentrators in Cleveland. Satellite and underwater cable are used to provide the alternate-path reliability in this case.
Each central concentrator in turn is connected to a number of large computer systems. The number connected ranges from one to six and depends on the type of computer system. (Fewer Mark II systems will be served by the concentrator than Mark I systems. These terms are briefly explained in the following paragraphs.) Each central concentrator is also connected to two switching concentrators located within the same building that connect users coming in on a particular central concentrator to the one associated with the computer system holding their files. The process is explained schematically in Fig. 4.
Four types of computational service are available from the system, each corresponding to a particular one of the computer systems previously noted;
1) Mark I time-shared services. This is essentially a problem-solving service. It handles the Basic language, some Algol, and a simple version of Fortran. This service is an outgrowth of the original Dartmouth-designed system. It is currently handled by Honeywell G-265 computers,
2) Mark II time-shared service. This is provided by a number of Honeywell G-635 computers. It is the largest and most used system in the network. The system is the outgrowth of a joint Dartmouth-GE project and was commercially introduced in 1968.
3) Mark Delta service. Provided by Honeywell G-605's, this is the most demanding system in terms of the customer's ability to program.
4) Resource service. This service provides remote batch processing plus some time-shared service and is handled by a Honeywell 6070 system.
In addition, a Mark III system is due to go on the air by the third quarter of 1972. In this system multiple Mark II's will be coupled to a Honeywell 6080 (a much larger machine) for batch processing.
Although the fundamental design of the current network grew out of the original Mark II time-sharing system developed at Dartmouth, the network, as it exists at present, is very different. As in the case of TYMNET discussed earlier, the network has essentially evolved in response to market demand and customer needs, with incremental changes made as required. I t is a store-and-forward message-switched network, as will become apparent in the following section. The use of remote concentrators provides flexibility in accepting various types of user terminals and in adjusting to market demands,
Message Transmission
Any terminal transmitting up to 30 characters/s (300 bits/s) may be used to access this system. The remote concentrator will convert non-ASCII code inputs to ASCII, used throughout the system. Identification of the machine, speed, and code used is accomplished by typing in the letter H, The sign-on procedure consists of typing in this identifying character, followed by the user number. This number is forwarded by the remote concentrator to the central concentrator to which it is connected. Each central concentrator has a user table showing the central concentrator associated with the computer system responsible for each user, thus indicating the appropriate computer or central concentrator to which a particular user message should be forwarded. Following the user number a password is typed in. This is checked against the password stored in the user system to see if it is valid, The user is then ready for transmission.
User inputs are of two types generally. These consist of system-command and file-building-mode messages. The file-building mode begins with a line number. The characters following, up to 150 in number, and comprising a line, are stored in the remote concentrator message buffer. (Recent characters or the entire line may be deleted if the user desires.) The line is concluded by depressing the carriage-return key, causing one or more messages of up to 36 characters to be transmitted, with appropriate overhead characters added to the appropriate computer system. (Note that this differs from the TYMNET format, in which messages from various users may be combined to form one block.) System-command messages with no line number at the beginning are handled as priority messages and sent right out as received. (There is no echoing in this system. Characters are printed by the terminal as soon as the key is depressed,)
The message buffer at the remote concentrator is dynamically managed, with space allocated to terminals that need it, on demand. Buffer allocation to any one terminal is based on terminal speed and mode. Messages flowing in either direction (user-computer or computer-user) use the same set of buffers and are provided the same buffer allocation. GE personnel indicate that the buffer sizes are quite sufficient with very little message queuing taking place at this point.
The message format, in block form, uses a modified version of the ASCII format [5]. It consists of 9 characters of overhead and from zero to 36 characters of text. The same format is used in both directions of data transmission. As shown in Fig. 5, the first 7 characters constituting the header consist, in order, of 1) an ASCII start-of-header (SOH) character, 2) the port number of the remote concentrator, 3) the number of the remote concentrator (R/C), 4) the length of text following, 5) type of message character, 6) a control character for setting up a function, and 7) the ASCII start-of-text (STX) character. The text then follows, and the block is concluded with an ASCII end-of-text (ETX) character and an error-detection character. (This final character is the EXCLUSIVE-ORed value of everything but itself.)
Messages are sent, a block at a time, from the remote concentrator to the central concentrator to which it is connected. The path used (of the two available) is the one which is free or the one not used for the last transmission. Each block is acknowledged as received by the transmission over the return path of a six-character acknowledgment block. This consists of six of the overhead characters in the standard message block (see Fig. 5)-the first three characters and the STX character of the header, plus the last two characters in the block. If an acknowledgment is not received, the remote concentrator retransmits the message. This automatically provides alternate path selection in the event of a noisy path or circuit. Since the remote concentrator selects the path of the two available that has been most recently vacant, a noisy circuit with a correspondingly increased number of retransmissions is vacant less often and is hence not used.
A second acknowledgment step is similarly carried out if the message must further be switched through the switching concentrators to a second central concentrator interfacing with the user's computer system. The switching concentrator remains transparent to this additional acknowledgment step. Each remote and central concentrator counts the number of retransmissions over each circuit, and every 30 min the central concentrator prints out on its own console a report on the condition of each circuit.
The process of transmitting a user message to a second central concentrator if necessary is first begun with the transmission of the user number, as indicated earlier. The central concentrator to which the user message is first transmitted (corresponding to the remote concentrator to which the user is connected) associates the user port and remote concentrator number with the first character of the user number. This character in the user table, available at each central concentrator, determines the central concentrator to which the user message should be switched. Once log-on is complete and the remote concentrator port-processor association has been established, further messages originating from the same port on the same remote concentrator are accorded the same routing. The message format in going through the switches is essentially the same as that of the transmission format between remote and central concentrators, with the addition of two delete characters added after the SOH character plus one character indicating the central concentrator for which it is destined. The switching concentrator ports are numbered to represent the destination central concentrators.
Traffic-Handling Capability
The maximum port capacity of the network as deployed in June 1972 was of the order of 2000 simultaneous users. This is of course the current maximum capacity. The message and routing disciplines used make it possible to expand the network indefinitely and to serve computers of many kinds which may he located at any major node.
To make sure the network can accommodate the traffic, there is a daily review of the network, in which the following four items are assessed:
1) the assignment of user numbers (and hence number of users) to each computer system,
2) the assignment of remote concentrators to central concentrators,
3) the assignment of ports to the remote concentrators, and
4) the deployment of ports.
Based on this assessment, the network topology may actually be changed daily. Thus a computer algorithm reassigns user numbers and remote concentrators daily in an attempt to balance the peak load of the machines. User file catalogs may thus be moved from machine to machine. The reassignments are also facilitated since all programs in the remote concentrators are loaded from the center. The last two items above are changed once a month, or more often if necessary.
The performance criterion used for the network provides a 95-percent probability of port availability on a Poisson basis at the local peak load, generally 2-3 P.M. local time. On this basis roughly 5-6 users can be accommodated per remote concentrator port, for a total of 10000 individual users for the entire system. There are currently about 3000 firms with varying numbers of individual users validated for use of the network.
GE personnel indicate that response time throughout the network is negligible and is hence not used as a criterion of performance. The only significant queuing occurs within the computer systems themselves. Several queues may exist there, depending on the user's needs. (For example, there may be a queue of programs waiting to be processed.)
Some additional traffic statistics may be of interest. As in most such systems, the outbound traffic (computer-user) dominates. I t runs typically 3-5 times the input speed. The average length of messages, outbound, runs 30 characters per line. Although most terminals currently used are 10-character/s units, a growing number are 30-character/s units. Terminal duty factors based primarily on outbound statistics run 70 percent—i.e., 7 character/s on 10-character/s terminals and 21 character/ s on 30-character/ s terminals.
THE NASDAQ SYSTEM [7], [8], [9]
How the System Is Used
The National Association of Securities Dealers Automated Quotations (NASDAQ) System is a computerized communications system, designed by Bunker-Ramo Corp., which makes available to its users a means of rapidly obtaining quotations on the bid and asked prices of over-the-counter securities. In addition, changes in these quotations, by specially designated users, are rapidly entered into the system.
Each security2 in the over-the-counter market, which is regulated by the National Association of Securities Dealers, has assigned at least two but not more than 64 traders, specially approved as market makers. These market makers are responsible for individually establishing their own bid (buy) and ask (sell) prices for their security. They are committed to trade at least 100 shares of the security at their price. Previously, a trader receiving a request about a certain security would have to contact, by telephone, a number of the market makers in that security to determine their current prices and, after deciding the "best deal," recontact that market maker and complete the transaction. Often the trader would shorten this lengthy procedure by calling only several of the market makers. Frequently the prices would change before the trader could return to the market maker. Thus it was difficult and time consuming to determine all current prices in a security. Even representative bid and ask prices (median prices of all market makers in a security) were sometimes several days old. As a consequence, there were often large differences between the prices of different market makers. The NASDAQ system, which began operation on February 8,1971, was set up to automate this process.
Now a broker can type in the code name for a security on a special terminal and receive in seconds on a cathode-ray tube (CRT) display the current representative bid and ask prices. Terminals which are restricted to only this response are called Level I terminals and are not essentially part of the network. This, and other information, is also supplied periodically to the news media. Level II and III terminals receive, in addition to the representative bid and ask prices, the current bid and ask prices of each market maker in that security. If a bid price is requested, the market makers are listed in order of descending bid price. If an ask price is requested, they are listed in order of ascending ask prices.
For example, suppose a customer wants information on a particular security. He contacts his broker and immediately receives the current representative bid and ask price. If the customer wants to buy the stock, the broker contacts his trader, who, using a Level II or III terminal, types in the code name of the security and an "ask" symbol to denote that he wants the market makers listed in order of ascending ask price, i.e., the price at which the market maker will sell. The market makers' prices are displayed in frames of up to five market makers each. If there are "more than five market makers in that security, the characters MOR are printed in the lower right half corner of the CRT, and the trader, by pressing a MOR key, can receive the prices of the next five market makers. This continues until all market makers are listed. If the trader wants to buy the stock from one of the market makers, he calls him on a telephone and arranges the transaction.
The Level III terminal, used by the market maker, has all the capabilities of a Level II terminal. In addition, the market maker can change the bid and ask prices in his securities. These changes are processed by the system in seconds.
The terminals (Levels II or III) are connected directly to over-the-counter control units (OCU's). There is one OCU in each brokerage office. Although the system is designed so that up to 24 terminals may be connected to each OCU, most offices have only a few terminals. The national average of terminals per OCU is 1.45 (1.75 in the Northeast, only 1.2 elsewhere). The terminals are relatively simple, consisting mainly of a specially designed keyboard and a CRT display. Most of the work is done in the OCU—buffering, message formatting, addressing, etc.
The OCU's are connected by leased full duplex 1600-bit/s multidrop lines to a concentrator. Each of these lines, called regional circuits, can accommodate up to 32 OCU's. Each concentrator can handle up to 48 regional lines. These design limitations, and the maximum number of terminals per OCU, are due to the addressing structure, the amount of storage, etc. If the entire capability were used, inordinate delays would result. Thus, to achieve adequate performance, the actual numbers are far below these maxima (see Table I).
The concentrators are located at four sites—New York, N. Y.; Chicago, Ill.; San Francisco, Calif; and Atlanta, Ga. These sites were chosen on the basis of expected customer density and were located at existing Bunker-Ramo locations to save on the cost of installation. Originally a concentrator at Dallas, Tex., was also planned, but after a network study it was found that considerable savings resulted from merging this with the Atlanta facility. The concentrator sites in Chicago, San Francisco, and Atlanta consist of a pair of concentrators, each using a Honeywell DDP-516 computer, and other equipment. Both concentrators are always on line and share the traffic. For reliability the system is designed so that if any unit fails, the entire traffic can be handled by the remaining unit. The switchover can be accomplished in several minutes. The New York site contains four such concentrators and has the same redundancy capability. The concentrators poll the OCU's on each regional circuit, store the messages, control traffic to the CPU, and perform multiplexing and other communications tasks.
Each concentrator site is connected to the CPU by a pair of leased full duplex high-speed lines called trunk circuits. Again for redundancy either one of a pair of lines can handle the entire traffic if necessary. Furthermore, each of a pair of lines is diversely routed-connected over separate geographic paths. The trunks connecting New York to the CPU each have a capacity of 50 000 bits/s; the other trunks each have a capacity of 7200 bits/s. The CPU is located in Trumbull, Conn., and contains two UNIVAC 1108 multiprocessing computers, again operating redundantly so if necessary either one can handle the combined traffic, The CPU receives requests, searches its files, responds, updates quotations, and performs other operations of the system. The network is shown in Fig. 6.
Terminals and OCU's (Query Message)
The terminals consist mainly of a specially designed keyboard and a CRT display. A typical query (quote request) message (Level II or III) would be a bid or ask character and the four- or five-character code for a security. (A quote-change message by a market maker would require a slightly longer message. The ratio of quote requests to quote changes is approximately 20 :1.) Since the connection between the terminals and the OCU's is asynchronous, the five characters are each 10 bits long—8 for the ASCII code, including 1 for parity, and 2 for start and stop. The OCU's have provisions for up to 24 buffers, one for each terminal, arranged in six delay lines of four buffers each. Thus each terminal has a specific fixed address in the OCU. Each delay line can store approximately 10000 bits. (Since the reply (return) message is very much longer than the query message, and they always occur in pairs, the network is designed on the basis of the reply messages. The CRT has a maximum of six lines with 37 characters each and thus requires 2220 bits.) The OCU rapidly receives these characters from the keyboard and stores them in the appropriate buffer. This operation can be considered instantaneous. Once a query message is finished, indicated by an appropriate key on the terminal, the message at the OCU is ready to be transmitted to the appropriate concentrator.
The OCU appends to each, query message of five characters one SOH character, two characters permanently identifying the brokerage office,3 two characters identifying the OCU address and the terminal address, one more for control, the query message, one "end-of-transmission" (EOT) character, and a horizontal parity character—13 characters in all.
Concentrators (Query Message)
The OCU's are connected to their concentrators by full duplex asynchronous 1600-bit/s multidrop lines arrayed in several regional circuits. The concentrators have a single buffer for each regional circuit to be used for the query message only. The concentrators poll the OCU's on a regional line cyclically. The poll messages are two characters long—one character to initiate the polling request and a second used for addressing each OCU in turn. If a message is present, that message is transmitted to the concentrator; if not, then a one-character reply is sent to the concentrator. If more than one message is waiting at an OCU, only one of these is transmitted on a single poll. Once a query message is received by the concentrator, the polling stops on that regional circuit until that message is transmitted to the CPU. Furthermore, to prevent any OCU from dominating the traffic, an OCU will not be repolled until a response to an earlier query or an error message has been received. Additional features of the polling and multiplexing will be discussed when the reply message is considered. The concentrator inserts two characters into the message for concentrator and line address. Since the high-speed lines connecting the concentrators to the CPU are synchronous, each character is only 8 bits long—the start and stop bits are no longer needed. But three synchronization characters precede the message. Thus the message is a total of 18 characters.
CPU
The CPU is connected to each concentrator by a pair of full duplex synchronous high-speed 7200- (50 000- in New York) bit/s trunk lines. The CPU has a pair of separate input buffers (three input buffers for the lines from New York) for each trunk line. These buffers, each capable of storing 225 characters, are filled cyclically, Messages are routed over each pair of lines so as to equalize traffic. The CPU consists of two UNIVAC 1108 processors operating duplexed so that, again for reliability, if anyone unit fails, the other can handle the entire load. Similarly, the drums for storing data are duplicated. In addition to its other functions—reporting of prices and indices to the media, supervision of trading, system control, etc.—the CPU receives quote requests, searches its memory for the appropriate security, formats the message comprising the prices for the particular frame of five market makers in appropriate order, and transmits the reply message. If a quote change message is received from a market maker, the files must be updated in that security, including a recomputation of the median bid and asked prices.
The first frame (first five market makers) in any security is more frequently requested than subsequent frames. Thus the first frame is always kept ready for transmission; subsequent frames must be formatted when requested. Furthermore, data for frequently requested securities are stored on readily accessible drums. Data for less active securities require additional time for retrieval. Typical times required for the CPU to respond to the various request messages are 4 ms to process the first frame of a quote request and 8 ms to process a quote request for subsequent frames or a quote change. In addition the average time required to retrieve the data from the files is 4, ms for a quote request and 8 ms for a quote change for active securities, and four or five times this for inactive securities. Thus the total time required by the CPU is, on the average, 8-50 ms.
The reply message is similar in form to the query message, except that the two permanent identification characters for the brokerage firm are not transmitted. The reply message is typically about 115 characters long. The CPU has a pool of 70 buffers, each 225 characters long, to store reply messages. If more than five messages are waiting to be transmitted to any one concentrator on anyone trunk, then a message is sent to that concentrator to stop polling for a specified period of time, Typically, during a busy period, 20-30 of the buffers are occupied.
Reply Message
Each concentrator has a pool of 31 reply buffers. (The concentrators will transmit a query message to the CPU only if there is a reply buffer available.) The reply message is then transmitted to the appropriate OCU. An excessive delay would result if polling were to be suspended during the time a reply message is being transmitted from the concentrator to the OCU along the multi-drop regional line. To alleviate this, a system of nested polling is used. Two-character polling messages are inserted into the reply message. A result of this entire procedure is that messages are made to wait at the OCU rather than the concentrator.
System Design and Performance
The network design (assignment of OCU's to regional circuits and regional circuits to concentrators) was based upon location of existing Bunker-Ramo facilities (for location of concentrators and CPU), estimates of numbers and locations of customers and frequency of use, and line tariffs for the trunk lines and the multi-drop regional lines taking into account differences between interstate and intrastate rates. Response times called for in the design were a response to a quote request or a quote change within 5 sec 50 percent of the time and within 7 sec 90 percent of the time. The quote files were to be updated within 5 sec at least 95 percent of the time. The system design encompassed the indicated response time assuming a busy-time load of 28 calls/s system-wide.
The following peak statistics have been obtained: 1 262 000 calls on a very busy day, 240 000 calls during a busy hour, and 100 calls/s during a peak minute—67 from New York, 14 from Chicago, 12 from San Francisco, and 7 from Atlanta. On the average l.5 calls/min are to be expected per terminal. Twice this number has been observed during peak periods, and even an extreme of 12 calls/min has been observed on a single very active terminal. A design rule of thumb that has been developed is that a limitation of 20 terminals per regional circuit will guarantee meeting of response time specifications. Even during observed peak activity the system is still performing satisfactorily. During such peak activity, however, trunk line redundancy may be lost in certain areas for a certain time period if one of a pair fails, but in this event there is a dial-up capability which is used as a second-level backup. In sum, the system seems to be well designed and can even handle traffic well in excess of what it was designed for.
INFONET
Introduction
INFONET is a remote computing system conceived and designed by Computer Sciences Corporation in response to the requirement for a versatile remote computing environment which would fulfill the needs of a wide spectrum of user-oriented requirements. The INFONET system architecture and communication network are based upon the objective of providing service to both conversational (10-30 characters/s) and remote job entry (2000-8000 bits/s) terminals in a single integrated system and the ability of the network to evolve to the next generation of hardware, software, and communications.
INFONET has been in full commercial operation in the United States since January, 1970, and also has networks installed in Canada, Australia, and South Africa. Since the initial operation, the network has expanded geographically, and a second-generation operating system and enhanced communication network have been installed. INFONET was recently selected by the General Services Administration to be a unified supplier of nationwide teleprocessing services for Federal agencies.
The operating system for INFONET is known as the Computer Sciences Teleprocessing System. This system was specifically designed to avoid partitioning of resources to support multiple operating modes, but to allow all hardware capabilities, operating-system features, language processors, application programs, and data files to be available for both interactive and batch processing without special user action. To support the single integrated-system concept, the communication network for both low-speed conversational access and high-speed batch was designed and implemented as a single common network.
Two principal programming subsystems are used-the BASIC subsystem and the General Programming Subsystem (GPS). Both systems have access to the full computing resource and the same files. BASIC is an enhanced version of the Dartmouth College BASIC. GPS includes several language processors: Fortran IV, Fortran V, Cobol, Data Management Language, Program Checkout Facility, and an Assembler.
INFONET currently uses six UNIVAC 1108 computers in the network. The 1108 has a main storage capacity of 106 characters, which is augmented by a magnetic drum subsystem. Immediate-access storage is provided by a Multiple Disk Drive subsystem. Dual access and multiple drives provide improved reliability. Additional storage is provided by eight magnetic tape drives per 1108 with support for both seven- and nine-track recording formats.
Communications Network
The computer centers are in Washington, D. C., Chicago, and Los Angeles. Each location contains from one to three 1108's and associated peripherals. Each functions as a regional center serving several major metropolitan cities via communications concentrators and multiplexers. In addition, the Los Angeles center serves as the national center, providing access on a nationwide basis to customers with requirements for access to common data bases and files from geographically dispersed locations throughout the country. By designing a nationwide system with only three centers and multiple computers per center, INFONET is more dependent upon a reliable communications network than it would be had it elected to place a single main frame in each of numerous centers. Principal motivations for the small number of centers were the higher reliabilities and longer operating hours achievable with such a configuration, greater flexibility, and user access to common files from diverse locations. Efficient utilization of existing common-carrier facilities also renders this a more economical choice. Recall that both the TYMNET and GE Information Service Networks used a small number of centers as well (see Figs. 1 and 3).
A map of the INFONET communication network is shown in Fig. 7. Only the major cities and the backbone network are shown. The number of circuits connecting each remote branch to a computer center is not indicated; a minimum of two diversely routed circuits are provided. INFONET utilizes one network with common hardware for all communications—both low-speed asynchronous requirements and high-speed remote batch terminal needs. In order to provide highly versatile communications, a special concentrator was necessary. This led to the design and development of the Remote Communications Concentrator (RCC). The RCC serves as the communications interface for the network and functions as a combination of statistical multiplexer, incremental front end, and error-control device.
A functional diagram showing the essential elements of the INFONET network and their relation to the RCC is shown in Fig. 8. In Fig. 8, City A represents a typical major branch location. Users with low-speed terminal devices in the metropolitan area of City A would place a local (toll-free) call to the low-speed access rotary. As in the GE and TYMNET systems described previously, a variety of low-speed data terminals will be handled by this system. Upon hearing the tone from the low-speed data set at the RCC (Bell 103E5 or 113B), the user types a single character. The RCC will use this character to determine the terminal speed and code type. Currently, INFONET supports ASCII code at 110, 150, and 300 bits/s (10, 15, and 30 characters/s), and IBM Correspondence and EBCD codes at 134.2 bits/s (14.8 characters/s). All terminal devices compatible with these code descriptions may be used with the INFONET system.
Once the RCC has identified the code and terminal type, the user may sign on the system and perform his desired tasks. RCC software converts all terminal codes to ASCII; This relieves the central computer of performing any code translation tasks.
In addition to providing access for low-speed terminals, the RCC accommodates high-speed (2000 bits/s), remote job entry (RJE) dual access (2000 bits/s), high-speed; RJE with dedicated lines (up to 4800 bits/s), and multiplexer ports. Currently, the network supports all remote terminals (card-reader, card-punch, and line-printer) which are compatible with the 2780 Binary Synchronous Communication discipline.
Other disciplines may be accommodated by adding a new high-speed terminal handler (software) in the RCC.
High-speed dial access permits users with their own RJE terminals to access INFONET via a local call and a standard Bell System 201A data set (or equivalent). Users with a requirement for a dedicated RJE circuit may interface the RCC via standard Bell leased circuits and either Bell or non-Bell modems.
As depicted in Fig. 8, the RCC may also be used as an interface for multiplexer links. Typically, cities with smaller traffic requirements will be served by a multiplexer with evolution to an RCC as usage demands. INFONET uses time-division multiplexers in conjunction with high-speed synchronous modems for these applications. The multiplexers are synchronous character-oriented devices, with frame division such that 10-, 15-, and 30-character/s inputs are accommodated. Since the multiplexers do not have provision for automatic speed and code detection, separate telephone rotary groups are provided for each of the various terminal classes served.
The multiplexers are connected to the nearest RCC via a dedicated circuit and synchronous modems. Forward error correction is used on certain multiplexer links to overcome transmission errors. The code is a rate-[3/4] convolutional burst correcting code. The transmission rate is 4800 bits/s with an information rate of 3600 bits/s. The burst correction interval (i.e. the span over which all errors are guaranteed to be corrected) is selectable at 32, 64, 128, 256, 512, or 1024 bits; this choice is dependent upon channel characteristics. The longer correction intervals introduce greater delays into the system; a correction interval of 256 bits is normally used.
The primary communication link from the RCC to the 1108 is a Bell System C2 dedicated full duplex circuit. The transmission rate (modem speed) is selected according to anticipated input load. Currently, transmission rates of 4800, 7200, and 9600 hits/s are used. The software and hardware has been designed to accommodate higher rates; however, these have not been utilized to date because of adverse performance and economies of remote transmission above 9600 bits/s. RCC's which are located together with an 1108 may operate at 19 200 bits/s since there is no complex modem/ transmission path to be considered.
As indicated in Fig. 8, each INFONET branch office has a high-speed RJE terminal. This terminal may communicate with the central computer either via dedicated circuits or directly interfaced with the RCC. Typically, a separate diversely routed circuit is used, with this circuit serving as a backup for the RCC. (In this case, the RJE terminal would use the dial-up backup which has been provided.) In all cases, an INFONET branch has at least two dedicated diversely routed circuits (to increase overall reliability) connecting the branch location to the central computer site.
Further flexibility is achieved by the multiple trunk capability of the RCC. As shown in Fig. 8, the RCC can serve two distinct high-speed trunks. This facilitates access to two distinct 1108's from the same RCC. For example, users in city A could access either the regional center or the national center depending upon their specific requirements. Similarly, the dual high-speed trunks may be connected to the same 1108 if required by capacity considerations. This same functional capability may be achieved in cities served by multiplexers. This is obviously less efficient than the RCC implementation but is used if that functional capability is required for a particular city.
This network has been designed to facilitate load balancing in a way similar to that previously described in the GE system. If one central processor becomes heavily loaded, one or more RCC's serving that processor may be shifted to. another 1108. User files are transferred on an overnight basis, the communications are realigned, and the shift is accomplished unknown to the user.
The network was designed to facilitate a logical evolution of hardware in each city. The most economical means of servicing a given load is a complex function of statistics of the user population, distance from the central computer site, and other RCC's and intra- and interstate tariffs. A general evolution within a city may be from Direct Distance Dialing (DDD) to Foreign Exchange (FX), to time-division multiplexing (TDM) and/or frequency-division multiplexing (FDM), and finally to an RCC. Calculations as to the economics of network growth, characteristic of all the networks described in this paper, may be carried out on the basis of curves such as those given in Fig. 9.
Fig. 9. Economics of data communications-Summary.
Fig. 9 illustrates an example of the basic economic tradeoffs for a city which requires 250-mi communication links. The abscissa is a measure of incoming load and is expressed in port-hours per month. Loading and rotary capacities are based upon Erlang B statistics with a daily peak-to-average ratio of 1.8 and a design busy probability of 0.05 during the peak hour. The step functions are points at which new hardware is assumed to be added to meet capacity requirements. The ordinate shows monthly expense for this example; interstate tariffs, hardware amortization, and local data service are included.
The dashed line in Fig. 9 is referenced to the right-hand ordinate. This line shows the locus of minima and is normalized to cost per port hour. This curve shows the high "startup" cost for providing service in a new location. Similar relationships may be obtained for different distances; the relationships become more complex as adjacent RCC's and multipoint networks are considered. Hence the above should be viewed as illustrative of the considerations involved but not construed as a "design chart."
As is true of other networks, operational reliability is of paramount importance in the network operation. Incorporated as an integral part of the network design were such aspects as extensive fault isolation, on-line performance monitoring, instrumentation, and redundancy. On-line performance monitoring includes both hardware and software means. The objective is to sense circuit degradation before it becomes sufficiently adverse and affects user terminal performance. Communication hardware used in the network contains complete loopback facilities to facilitate fault isolation. For example, high-speed modems have both analog and digital transmit and receive loopback.
Remote Communications Concentrator (RCC)
The RCC was built for INFONET by Comten Corp. and is designated the Comten-20. The Comten-20 has a maximum core memory size of 65K bytes, which may be incrementally increased in 16K-byte modules. Typical INFONET configurations use 48K words with variations determined by such factors as total load and conversational bulk-terminal mix. Cycle time of the Comten-20 is 900 ns.
The Comten-20 communication interfaces are designated Modem Interface Modules. A combination of asynchronous and synchronous modules are used to interface with the range of terminals and speeds supported by INFONET. The modules provide the necessary timing, data-set interfacing, automatic answering, and error checking (either cyclic redundancy check or longitudinal/ vertical parity checking) required to interface the communications network with the RCC software.
One of the more important and interesting functional characteristics of the software is the combined ability to allocate buffers dynamically and provide a temporary choke mechanism. This choke mechanism permits operation at high trunk utilizations without the inherent risk of buffer overflow which is characteristic of statistical multiplexing. As a function of buffer filling and trunk utilization, the RCC will automatically slow down the terminals by appropriate action. As either input or output to the RCC approaches capacity, RCC buffers will "choke down" and reduce terminal transmission rate. For example, the apparent print rate of an RJE terminal may be temporarily slowed down by a small percentage in order that conversational terminals may not be affected.
As evidenced by the description of the network, the RCC is the key element of the INFONET communication system; there are currently about 25 RCC's in the network. They are the major "building blocks" which provide both the flexibility and the capacity for network expansion.
A major aspect of the flexibility of the RCC arises from its ability to interface with low-speed, high-speed, and multiplexer inputs. For example, in Fig. 8, routing the lower traffic density of city B via the RCC in city A is substantially more economical than routing that traffic directly to the computer center if city B is considerably closer to city A than to the computer center.
The statistical (asynchronous) multiplexing function of the RCC permits a much more efficient dedicated circuit utilization than synchronous TDM, which is, in itself, more efficient than FDM. The RCC realizes this efficiency by taking advantage of the statistical nature of both inbound (toward the computer) and outbound (toward the terminal) data. For a representative discussion of statistics of time-sharing systems inbound and outbound traffic, the reader is referred to [11]. Experience at INFONET has shown that inbound traffic statistics are evolving from those presented in [11] to a higher utilization per input terminal; this is attributed to the increased use of higher speed asynchronous devices (e.g., 30character/ s CRT devices) and increased use of magnetic tape cassettes. The net effect is a requirement for increased buffer space in the RCC.
The RCC provides sufficient high-speed trunk buffer space to permit a complete full duplex error-control system. Data in both inbound and outbound directions are formatted in variable length blocks which may contain up to 2048 information bits. Positive and negative acknowledgments (ACK/NAK) are embedded in data blocks to reduce message-acknowledgment time. All blocks are verified as correct by either the 1108 communications interface (see Fig. 8) or the RCC, depending upon the direction. This positive error detection and retransmission facilitates the use of higher speed data transmission between RCC and 1108. That is, while bit error probabilities increase at the higher data rates (7200 and 9600 bits/s), the block throughput remains on the order of 99 percent and the net effect is transparent to the user. In addition, the use of the higher data rates is a more efficient use of a standard voice grade leased circuit.
A very significant system feature made possible by the RCC is the shielding of the user from temporary communication or system prob1ems. During such problem periods, the user will observe a "STANDBY" message but will not be "dropped off" the system. Upon correction of the trouble condition, the user may resume his session. (The system will even inform him of the last valid transmission.)
The RCC is designed so that the software can be remote-loaded from the central computer site. This capability is important since many remote sites are INFONET sales offices which are not staffed on a 24-h basis. Operations personnel may remote-load (bootstrap) the remote RCC and restore it to operation after a major communications outage, computer failure, or normal shutdown. Similarly, RCC software changes may be made without visiting the RCC physical location to perform the change. This remote loading is a special mode of operation in which the 1108 commands the RCC to consider a block of information as an executable program rather than as data to be sent on to a terminal.
The capacity of the RCC, expressed in terms of number of simultaneous users, is a complex function of user input and output statistics; a mix of low-speed, asynchronous, and highspeed RJE terminals; buffer size; and high-speed trunk capacity. Typically, INFONET RCC's are configured for a maximum of eight RJE ports and 64 low-speed ports. High-speed trunks range from 4800-9600 bit/so The precise configuration for any specific location depends upon the customer mix and projected growth.
The RCC capacity is essntial1y limited only by the high-speed trunk capacity and not by any number of physical input ports. Because of this, it is difficult to discuss the number of "terminals" supported by a single RCC. Experience has shown that the 48 low-speed/4 high-speed configuration results in an inbound and outbound statistical distribution of the composite information rate which is at or below the trunk maximum data rates and thereby provides the design performance.
Since the state of the art of statistical or asynchronous multiplexing is quite new, the RCC was heavily instrumented to maintain continually good performance. The work of Chu [12] was used as a guide during the design. However, the multiple tandem buffers used in the RCC software lead to unsolved problems of queuing theory. Hence the approach was to parameterize the design so that optimization could occur as buffer interaction became known, based upon observed behavior. The RCC collects statistics on buffer usage and error rates and reports these statistics to the 1108 for subsequent analysis.
Diagnostics have been provided in the RCC to assist in problem analysis. There is a remote dump program which the central computer can load into the RCC, in case of a software error; the content of the core is then communicated back to the central computer. It is also possible to diagnose certain RCC hardware faults by a remote diagnostic program. The RCC was designed so that it can be used either remotely or as described above or located together with the 1108; location is transparent to the operating system. Because of this design concept, it was not necessary to provide a local "front-end" computer for the 1108—the RCC provides all required functions; hence a user's transmission is always routed via only one RCC. This concept provides fewer queues than there would be if the concentrators were concatenated, and therefore tends to provide shorter response times.
CONCLUSIONS
This paper has presented descriptions of four representative terminal-oriented computer-communication networks All four have been operational for some time now and are continually in a state of growth and modification. The GE and TYMNET systems evolved from remote conversational-mode computing systems; INFONET was designed from the beginning to handle remote job entry and batch processing along with conversational general computing, while NASDAQ had the narrower objective of remote automatic quotation and updating of files. Nevertheless, the communication-network features of all four show a great similarity in structure and function. A key component in all the networks is a programmable concentrator which not only permits more economical use of the communication lines, but affords the opportunity to do the vital communication tasks such as buffering, line control, message assembly and formatting, error control, and traffic control. The concentrators, whether remote or located at the central computer site, handle virtually all the communications functions of the network, leaving both the user and the computer free to perform their primary tasks. In addition, since the concentrators (which are essentially minicomputers) are programmable, they can be modified to accommodate any new needs that arise in the network. All of the networks contain considerable sophisticated software for network control, which was only lightly touched upon in the paper.
The evolution of computer-communication networks such as those described in this paper and others is progressing at a very rapid rate, and the pressure is constant to expand the network and add new features. For example, because of the adaptability of software as contrasted with hardware, there will likely be a tendency to replace hardware devices with programmable ones. The trend has been established, and the movement toward more "intelligent" terminals and concentrators will he inexorable.
There is already pressure to introduce network features such as higher speed dialup, positive error control complete from terminal to computer, higher speed asynchronous terminals (120 characters/s), and even provisions for computer-to-computer communications with all the potential for file and load sharing. Virtually all the existing networks today rely on leased lines from the common carriers such as AT&T. The evolution of the special service carriers such as DATRAN and MCI may have a significant impact not only on the growth of the networks, but on the design philosophy This would be especially true if the tariffs were based on the number of bits transferred rather than monthly cost of a voice grade line. The economic factors (principally communications costs) play a dominant role in the design of these networks. Finally, the introduction of domestic communication satellites within the next five years is certain to play a part in shaping data networks.
ACKNOWLEDGMENT
The authors wish to thank the following individuals; for help in the preparation of this article; M. P. Beere, Tymshare, Inc.; N. C. Sullivan, Tymshare, Inc.; Dr. R. C. Raymond,, General Electric Co.; M. Sumner, Bunker-Ramo Corp.; Dr. G. Harrison, Bunker-Ramo Corp.; Dr. H. Frank, Network Analysis Corp.: and Dr. P. Tenkhoff, Computer Sciences Corp.
REFERENCES
[1] E. C. Gaines, Jr., and J. M. Taplin, "The emergence of national networks: Remote computing—Year VI," Telecommunications, p. 27, Dec. 1971.
[2] M. P. Beere and N. C. Sullivan, "TYMNET—A serendipitous evolution." IEEE Trans. Commun., vol. COM-20, pp. 511-515, June 1972.
[4] J. F. Ossanna, "Identifying terminals in terminal-oriented systems," IEEE Trans. Communications vol. COM-20, pp. 565-568, June 1972.
[5] S, R. Rosenblum, "Progress in control procedure standardization," in Proc. ACM/IEEE 2nd Symposium Problems in the Optimization of Data Communications Systems (Palo Alto, Calif.), pp. 153-159, Oct. 1971.
[6] "The long arm of teleprocessing networks," ADP Newsletter, vol. 15, June 14, 1971.
[7] M. Sumner, "What is NASDAQ?" Bus. Commun. Rev., vol. 1, pp, 23-28, Nov.-Dec. 1971.
[8] N. Mills, "NASDAQ—A user-driven, real time transaction system," in Spring Joint Computer Can/., AFIPS Conf. Proc. Washington, D.C.: Spartan. 1972, pp. 1197-1206.
[9] H. Frank, I. T. Frisch, and R. Van Slyke, "Testing the NASD automated quotation system," in ProG. Symp. Computer-Communications Networks and Teletraffic (Poly tech. Inst. of Brooklyn, Brooklyn. N. Y.), Apr. 1972.
[10] "Switching networks and traffic concepts." in Reference Data for Radio Engineers, 5th ed. Indianapolis: Howard W, Sams and Co., 1968, Ch. 31, pp. 31.11-31.16.
[11] P. E. Jackson and C. D. Stubbs. "A study of multiaccess computer communications," in 1969 Spring Joint Computer Conference, AFIPS Conf. Proc., vol. 34. Washington, D, C.: Spartan, 1969, pp. 491-504.
[12] W, W, Chu, "A study of asynchronous time division multiplexing for time-sharing computer systems," in 1969 Fall Joint Computer Conference, AFIPS Conf. Proc., vol. 35. Washington, D. C.: Spartan, 1969, pp. 669-678.
[13] D. R. Doll, "Multiplexing and concentration," Proc. IEEE, VOL. 60, No. 11, Nov. 1972, pp. 1313-1321.
[14] C. B. Newport and J. Ryzlak, "Communication processors, " Proc. IEEE, VOL. 60, No. 11, Nov. 1972, pp. 1321-1332.
[15] D. L. Mills, "Communications software," this issue, pp. 1333-1341.
[16] H. Frank and W. Chou, "Topological Optimization of computer networks," Proc. IEEE, VOL. 60, No. 11, Nov. 1972, pp. 1385-1397.
FOOTNOTES
1] The term "packet switching" is sometimes used in place of "message switching." BACK
2] As of this writing there are 3000 securities in the NASDAQ system. BACK
3] The assignments of OCU's to regional circuits are infrequently changed to equalize traffic flow. These two characters provide permanent identification of the brokerage office for bookkeeping purposes. The next two characters identify the current physical address of the terminal and the OCU for message routing. BACK