386
, [291
L. G. Roberts and B. D. Wesaler, "Computer network develop-
ment to achieve rource sharing," in AFIP$ JCCProc., vol. 36,
p. 543, May 1970.
[30] M. Shaw, W. Pu Wulf and R. L. London, "Abstraction and veri-
fication in Alphard: Defining and specifying iteration and gen-
erators," CACM, vol. 20, no. 8, p. 553, Aug. 197'/.
[31 J R. F. Sproull, "Omnigraph-Simple terminal-independent graphics
software," Xerox Pale Alto Res. Center, CSL-73-4, 19'/3.
[32 ] --, "InterLisp display primitives," Xerox Pale Alto Res. Center,
197'7, informal note.
[33 [ R. F. Sproull and E. L. Thomas, "A network graphics protocol,"
Cornput. Graphics, vol. 8, no. 3, Fall 1974.
[34] C. Pu Sunshine, "Survey of protocol definition and verification
techniques," in Computer Network Protocols, Pu Danthine, Ed.
Liege, Belgium, Feb. 19'/8.
Issues in
PROCEEDINGS OF THE 1EEE, VOL. 66, NO. 11, NOVEMBER
[ 35] W. Teitelman, "A display oriented programmer's assistant...3,,
Pale Alto Res. Center, CSL-77-3, 1977.
.[36] R. H. Thomas, "A resource sharing executive for Ihe ARPAa.
in AFIP$ Proe., NCC, p. 155, 1973. '
[37 J -- "MSG: The interprocess communication facility fo
tiehal software work, Bolt Bernrick and NeWman, Rap. 34lj
[313] D.C. Walden, "A system for interproce. cOmmun ctioa,
reSource-sharing computer network," CACM, vol. 15, no. i
221, Apr. 1972. '
[391 J. E. White, "A high-level framework for network-based
sharing," AFIP$ Proc., NCC, p. 561, 19'76.
[40[ P, A. Woodsford, "The design and implementation of thz C.
3D graphics software package," Software Practice and
ence, vol. 1, p. 335, Oct. 19'71.
Packet-Network Interconnection
VINTON G. CERF AND PETER T. KIRSTEIN
Invited Paper
Abstract-This paper introduces the wide range of technical, legal,
and political. issues associated with the 'interconnectiOn of packet-
switched data communication notwoTk Motivations for interconnec-
tion are given, desired user services are described, and a range of tech-
nical choic for achieving interconnection are compared. Issues such
as the level of interconnection, the role of gateways, naming and
addressing, flow and congestion control, accounting and access contxol,
and ba=ic internet services are discussed in detail. The CCITT X.25[
X. 75 packet-network triterface reCommendations axe evaluated in terms
of their applicability to network interconnection. Alternatives such as
datagram operation and general host gateways axe compared with he
virtual cixcuit methods. Some observations on the regulatory aspects of
interconnection are offe.d and the paper concludes with a statement
of open reearch problems and some tentative conclusions.
1[. INTRODUCTION
-T IS THE THEME of many papers in this issue, that people
need access to data resources. In many cases this access
must be over large distances, in others it may be local to a
building or a single site. Data networks have been set up to
meet many user needs-often, but not necessarily, using packet-
Manuscript received June 20, 1978;revi,ed July 21, 1978.
V. G. Cerf is with the Advanced Research Projects Agency, US. De-
partment of Defense, Arlington, VA 22209.
P. T. Kitstein is with the Department of Statistic and Computer
Science, University College, London, England.
qD KIRSTt
may desi
- From
.ta networi
' used as
llmodvation
.xes/t of tb
i]iuteres t in
[231-[2,
f ata
From t[
?nderable
2fernt
packet-s,
o. the
Ifion of
ork interco
'Wd th per
'so that pac)
o"' othr?
d? What
'. trconne,
d operati,
lCC½ to rcs
d to ach
on Wh
switchStag technology. For single organizations, thes ,
networks are often private ones, built with a lechna4:
optimized to the specific application. For communica:"
between organizations, these networks are being set u;
licensed carriers. In North America, there are many
licensed carriers, e.g., TELENET [I], DATAPAC 121.
TYMNET [3]. In the rest of the world, the Post, Tek :ns
and Telephone Authority (PTT) in each country as a
monopoly on such services; special public data
being set up in these countries include TRANSPAC {.i
France, EURONET [61 for inter-European traffic, DD.X
in Japan, EDS [8] in the Federal Republic of GermS?.
the Nordic Public Data Network (NPDN, [9]) in Sc an=
These public data networ are considered in greater aa .nsible for
in other references (e.g., [ 10]-[ 12]). Most of the a ','ther?
works use packet-switching technology; some of them. " learode t possi
EDs and the NPDN, do not do so yet, but may do so t we deal
future. In some cases special data networks have been :'' ,'.
ial and pc
ones. C
must the,
How is'
ver the k
Are ther,
Iight be af
lntworks?
l'._ahoul d app
ra be da
b responsit
U.S. Government work not protected by U.S. copyright
rized for specific communities, e.g,SITA[13] for j'l½'__
and SWIFT [14] for the banks In addition many P '
works have been set u amen' individual organizatio Jor/' ,''
P g ha "- m:-
ex erimental networks of different technologies _
P 16], cYCDU''
developed also, e.g., ARPANET [15], [ '20] [:ll J the cone
[17], ETHERNET [18], SPYDER [19], PRNT t ' 'JSeetion
and SATNET [22]. luces the
a. tion and
on the fu
-----------------------------------------------------------
NOVF. M! t f AND KIRSTEIN: ISSUES IN PACKET NETWORK INTERCONNECTION
': assis..t,'.g. a common user requirement that a single terminal and
for t{e"Al__ port should be able to access any computing resource
' .-'i may desire-even if the resource is on another data
feili r . From this requirement, there is a clear user need to
'man,.m.t al data networks connected together. By the same token,
oraraunle
vol.'is;,a .... lt0viders of data network services would like to have their'
': :d: d ,.0rks used as intensively as possible; thus they also have a
otk-baa,.K, ['ke/! .o motivation to connect their data networks to othem.
ß .. c. result of these considerations, there has been a high
tation of te ' " ' j
r½aee i... t inerest in the issues arising in the connection of data
.'." ]l L-ors the user viewpoint, the requirement for interconnec-
:-,.' ] of data networks is independent of the network tech-
,..fS% , . From the implementation viewpoint, there can be
ß .v../;, a , considerable complications in connecting networks of
traffic,
of
'l)in
of the
me O
may
31 for
many
161,
RNET
,.:[y different technologies-such as circuit-switched and
..:a.aam packet-switched networks (these terms are explained
._:,.). On the whole we will consider only, in this paper, the
.x0nnection of packet-switched data networks. In many
z,'. hog. ever, the arguments will he equally valid for the inter-
.nection of packet-switched to circuit-switched networks.
:twork'interconnection raises a great many technical, legal,
: ?olitical questions and issues. The technical issues gen-
.,.'y revolve around mechanisms for achieving interconnec-
and their performance. How can networks be intercon-
:::.'d so that packets can flow in a controllable way from one
to another? Should all computer systems on all nets be
o., to communicate with each other? How can this be
a.:vecl? What kind of performance can be achieved with a
r of it'..t2rconnected networks of widely varying internal
-..m and operating characteristics? How are terminals to be
,:. access to resources in other networks? What protocols
ß -. :equired to achieve this? Should the protocols of one net
ß ::assisted into those of another, or should common proto-
., be defined? What kinds of communication protocol
ß .'.lards are needed to support efficient and useful inter-
=:oction? Who should take responsibility for setting
ards?
he legal and poetical issues are at least as complex as the
r&ical enos. Can private networks interconnect to each
e-. or must they do so through the mediation of a public
How is privacy to be protected? Should there be
'aaol over the kinds of data which move from one net to
Are there international agreements and conventions
might be affected by international interconnection of
ß networks? What kinds of' charging and accounting
apply to multinetwork traffic? How can faults
be diagnosed in a multinet environment? Who
he responsible for correcting such faults? Who should
:-ponsible for maintaining the gateways which connect
: cannot possibly answer all of these questions in this
we deal with many of them in the sections belowß
ß va paper is divided into eleven sections. In the next see-
we provide some definitions, and in Section III we ex-
Some of the motivations for network interconnection.
::tion IV we discuss the range of end-user service require-
choices for providing multinetwork service. Section
-'r4ews the concept of computer-communication protocol
ag. Section VI reviews the basic interconnection choices
the concept of gateways between nets, proto-
aslation and the impact of common protocols; it elabo-
on the function of gateways. Section VII discusses
the CCITT recommendations X.25 and X.75 and their role in
network interconnection. Section VIII describes some of the
network interconnections achieved and some of the experi-
ments in progress. Section IX outlines regulatory issues raised
by network interconnection alternatives. Section X mentions
some unresolved research questions, and the final section
offera some tentative conclusions on network interconnection
issues.
II. THE DEmiraTION O TERMS
The vocabulary of networking is extensive and not always
consistent. We introduce some generic terms below which we
will use in this paper for purposes of discussion. It is impor-
tant for the reader not to make any a priori assumptions about
the physical realization of the objects named or of the bound-
ary of jurisdictions owning or managing them. For instance,
a gateway (see below) might be implemented to share the
hardware of a packet switch and be owned by a packet-switch-
ing service carrier; alternatively it might be ßembedded in a host
computer which subscribes to service on two or more com-
puter networks. Roughly speaking, we are assigning names to
groups of functions which may or may not be realized as
physically distinct entities.
Packet: A packet of information is a finite sequence of bits,
divided into a control header part and a data part. The header
will contain enough information for the packet to be routed
to its destination. There will usually be some checks on each
such packet, so that any switch through which the packet
passes may exercise error control. Packets are generally
associated with internal packet-network operation and are not
necessarily visible to host computers attached to the network.
Datagram: A finite length packet of data together with
destination host address information (and, usually, source
address) which can be exchanged in its entirety between hosts,
independent of all other datagrams sent through a packet
switched network. Typically, the maximum length of a data-
gram lies between I000 and 8000 bits.
Gateway: The collection of hardware and software requixed
to effect the interconnection of two or more data networks,
enabling the passage of user data from one to another.
Host: The collection of hardware and software which uti-
lizes the basic packet-switching service to support end-to-end
interprocess communication and user services.
Packet Switch: The collection of hardware and software re-
sources which implements all intranetwork procedures such as
routing, resource .allocation, and error control and ßprovides ac-
cess to network packet-switching services through a host/
network interface.
Protocol: A set of communication conventions, including
formats and procedures which allow two or more end points
to communicate. The end points may be packet switches,
hosts, terminals, people, f'fie systems, etc.
Protocol Translator: A collection of software, and possibly
hardware, required to convert the high level protocols used in
one network to those used in another.
Terminal: A collection of hardware and possibly software
which may be as simple as a character-mode teletype or as
complex as a full scale computer system. As terminals increase
in capability, the distinction between "host" and "terminal"
may become a matter of nomenclature without technical
substance.
Virtual Circuit: A logical channel between source and desti-
nation packet switches in a packet-switched network. A
-----------------------------------------------------------
virtual circuit requires some form of "setup" which may or
may not be visible to the subscriber. Packets sent on a virtual
circuit are delivered in the order sent, but wiih varying delay.
tTT: Technically PTT stands for Post, Telegraph, and Tele-
phone Authority; th/s authority has a different form in differ-
ent countries. In this paper, by PTT we mean merely the
authority (or authorities) licensed in each country to offer
public data transmission services.
We have attempted to make these definitions as noncontro-
versial as possible. For example, in the definition of packet
switch, we alluded to a host/network interface. The reader
should not assume that subscriber services are limited to those
offered through the host/network interface. The packet-
switching carrier might also offer host-based services and
terminal access mechanisms as addition.al subscriber services.
III. THE MOTIVATING FORCES IN THE
INTERCONNECTION OF DATA NETWORKS
In the introduction, we mentioned that there was a strong
interest, among both the users and suppliers of data serivces, 67,
the interconnection of data networks. However, the technical
interests of the different parties are not identical. The end
user would merely like to be able to access any resources from
a single terminal, with a single access port, as economically
as possible according to his own performance criteria. A
Public Carrier, or PTT, has a strong motivation to connect its
network to other PTT's. As in the telephone system, the
concept of all subscribers being accessible through a single
Public Data Service, is considered highly desirable; however
the different PTT's may have restricted geographic coverage,
or only a specific market penetration.
The motivation of the PTT's to interface to private networks
is weaker and more complex. They always provide facilities
to attach single terminals, where a terminal may be a complex
computer system; they are often not interested, at present, in
making any special arrangements when the "terminal" is a
whole computer network. The operators of private networks
often have a vital interest in connecting their networks to
other private networks and to the public ones. Even though
in many cases the bulk of its traffic is internal to the private
network, which is why it was set up in the first place, there is
usually a vital need to access resources not available on that
network. The regulatory limitations often imposed on the
method of interconnection of private networks are discussed
in Section IX. In some countries, it is not permitted to build
private networks using leased line services, but intrabuilding
networks may be pern'dtted. Interconnection of such local
networks to public networks may play a crucial role in making
the local network useful
To date the PTT's have tried to standardize on access pro-
cedurcs for their Public-Packet Data Services. The standardiza-
tion has taken place in the International Consultative Commit-
tee on Telegraphy and Telephony (called CCITT) in a set of
recommendations called X.3, X.25, X.28, and X.29 ([27]-
[29]). Not all PTT's have such forms of access yet, but most
of the industrialized nations in. the West are moving in this
direction. This series of recommendations is discussed in
much more detail in Section VI; it does not pay special atten-
tion to the attachment of private networks ([31], [32]), but
the recommendations are themselves expected to change to
meet this requirement. The PTT's are agreeing on a set of inter-
face recommendations and procedures called X.75 [33], to
connect their networks to each other; so far this interface
PROCEEDINGS OF THE ]EEE. VOL. 66, NO. II, NOVE).IB)7) KIRSTI
ios will invc
procadurc (and its coesponding hardware) is not ithdmhtrat
to be provided to private networks.
While most PTT's have preferred to ignore the tec 4 , be inter
tercon
implications of the attachment of pvate network
public ones, most pvate network operators cannot '. We
ts requirement. They are often motivated to add some n fion to .
"Fore Exchange" capabty as an aftehout, with - 'ec[ed, a
mum change to their ntranetwork procedures; this ap pport the
can be successful up to a pdin[, but will usuflly be limue4
the lack of -level procedures between the different .øbfl c
works. ese hi-level procedures have not yet cn *conclusion
siderod y CCITT, but it has been proposed that CCI 5 e most im]
Group VII investigate -level procedures and architce e outset.
models, in cooperaon with the investigation of "open q ecology
architectures" by Teenier Committee 97, SuComv sifion
16 of the lntemationfl Standards Organisation (ISO
subject is so considered later in ts paper, in' Section Vl
.An m of these standardization exercises is to ensur :
both manufacturer d user plementations of net,- 1
resources can communicate with each other throu O 'stronSy:
private or public data networks. A consequence shouij
M supporte
that the resources are flso compatibly access% over : foreseeat
neeted data networks. precise n
Depending on the appUcations and spatiM distilbutte, a We w le:
subscribers the prefeed choice of packet-switching ..e,... m,;,,.: ofsu ori
, . . PP
wZ va. lntrabuding appcations such as electronic ,:.., m) ket tc
seaices may be most economically provided throu the
of a coaxial-packet cable system such as the Xerox ETIII:R) '
[18] and LCSNET [64], or twisted pair ngs such
[341 coupled wzth a m of self-contorted user comr
' . ms of the c,
(e.g., intelfigent terminus Mth substantifl computms 'fintof
memory capacity) and shared computing, stor:g. and = m':
output faceties. Larger ea reon applications mii fl ace
' mmmotejob,
employ shared video cables [35] or packet radios )-0l...
for mobile use. Nailend stems mit be composed of
ture of domestic satete chnels and convenfion I, nction
line seces. Intemafionfl systems mit use point-teF /e-shafi
Un plus a shed communication satelHte channel and ga :network an
ple ound stations to aceve the most cost-effective sc, I ,E and fi
many different network, both private and publ)c ' av ce
A network interconnection strate, if properly designc&
permit Iocfl networks to be optimized without sacdfic 2- of seic(
poibty of proving effective intemetwork seces % , learib:
potential economic d functionfl advantages of li sfer req
works such as ETHERNET or DCS w lead naturalb' :: ? delays
' vate user networks. Such private network developme:' 0be transf(
anflogous to telephone network private automated . buted
exchanges (PABX) and represent a naturfl conseque
the mage of computer and telecommunication technd A prot
Two fuher developmen can be expected. First. o A Nat
tiens wch are dispeed eoa c natlonelY or
g P Y' ' t.. i' qx
nationy, w wt to interconnect these private ne - quicy
both to shoe centrzed resources and to effect trao
tion electronic m d other automated office '.7
Second, there w be increasing interest terorn be stor
terconnections to ow automated procurement and f d to pro
transaction seces, for example, to be appHed to inte con se
zation afro. atems, cr
In m6st countries where private networks e
, ' VOl " '
tcroTganJzation t½]ecommucaton TqUJTCS hc m sup]3
of a PTT. enc the most pic nwork jntcøn' .
-----------------------------------------------------------
)V. / glAND KIRSTEIN: ISSUES IN PACKET NETWORK INTERCONNECTION 1389
ia6't; ' .os will involve three or four networks. Within one ha- SEUVEU
' u admintrafion the private nets of different organiza- .osv / ..... [
i( : . terconnections will volve at least two public
two:: -wl be interconnected throu a public network. Inter- '"
B0 . ' ....
P _.ec We return to this topic In Section VI. USER TERMINAL
]*] support the adu introduction of new nctworg oseu
ff ,' aologY into exiting systems without rcquMng sul- osv
f eous gobfl change throuout. Th consideration leads
Yet : te conclusion that the pubUc data networks should sup- veumt
t CCTIT 1
d
' "open':
n (lSOk::'
'eCtion
,s
nee
;ible or
ditribu
ectroati
,x
s such s'C
ser corn l:
omputi
ge, and
ohs mi!
los [201.
osed of /
ntionfi k
nnel and
:ctive
,gies whi:m
cations'
;, may 'j
velopm'
mated,
.onseqU"
m teclmci0.
.:. the most important user requirements for internet service
t: the outset. If this were the case, then changes in net-
,:rk technology which require a multinetwork system during
.:.xsed transition would not, a priori, have to affect user
. ices.
)'. PROVISION OF END-UsER MULTINETWORK SERVICES
e ultimate choice of a network interconnection strategy
/1 be .,,trongiy affected by the types of user services which
:.st be supported. It is useful to consider the range of exist-
z; and foreseeable user service requirements without regard
.: :he precise means by which these requirements are to be
::. We will leave for discussion in subsequent sections the
_-ce of supporting the various services within or external to
:: packet-switched network. The types of service discussed
20w are general requirements for network facilities. For this
-.con they also should be supported across interconnected
.:,,,,'or ks.
qost ?f the currently prevalent computer-communication
oces fall into four categories:
!1 terminal access to time-shared host computers;
' remote job entry services (RJE);
) bulk data transfer;
: transaction processing.
The time-sharing and transaction services typically demand
'.oa network and host response times but modest bandwidth.
7x RJE and file transfer services more often require high
mounts c,f data transfer, but can tolerate longer delay. Some
.':.tworks were designed to support primarily terminal service,
rating RIE or file transfer services to be supported by dedi-
-,ted leased lines. Packet-switching techniques permit both
.p½s of service to be supported with common network
.ources, leading to verifiable economies. However, bulk
,a transfer requires increasingly higher }hroughput.rates if
alivery delays are to be kept constant as the amount of
:ata to be transferred increases.
.is distributed operating systems become more prevalent,
'-:re wfii be an increased need for host-to-host transaction
a'ices. A prototypical example of such a system is found in
t: DARPA National Software Works [4t, [36t. In such a
r"em, small quantities of control information must he ex-
nged quickly to coordinate the activity of the distributed
:>rnPonents. Broadcast or multidestination services will be
'ded to support distributed File systems in which inferran-
:on can be stored redundantly to improve the reliability of
Ccess and to protect against catastrophic failures.
bansaction services are also finding application in reserva-
.n systemS; credit verification, point of sale, and electronic
"ns-transfer systems in which hundreds or thousands of
'inals request of, hosts small amounts of
, supply to, or
:ormation at random intervals. Real-time data collection for
Fig. 1. Network concatenation.
weather analysis, ground and air traffic control, and meter
reading, for example, also fall into this category.
More elaborate user requirements can be foreseen as elec-
tronic mail facilities propagate. Multiple destination address-
ing and end-to-end encryption for the protection of privacy
as well as support for text, digitized voice, and facsimile mes-
sage transmission are all likely requirements. Electronic tele-
conferencing using mixtures of compressed digital packet
speech, videographics, real-time cursors (for pointing at video
images under discussion), and text display will give rise to re-
quirements for closed user groups and time-synchronized
mixes of transaction-like (e.g., for cursor tracking and packet
speech) and reliable circuit-like services (e.g., for d/splay
management).
Reliability and rapid response will be increasingly important
as more and more computer-based applications requiring tele-
communications are integrated into the business, government,
military, and social fabric of the world economy. The more
such systems are incorporated into their daily activities, the
more vulnerable the subscribers are to failures. Reliability
concerns lead to the requirement for redundant alternatives
such as distributed file systems, richly connected networks,
and substantial local processing and storage capability. These
trends increase the need for networking to share common
hardware and software resources (and thus reduce their mar-
ginal cost), to support remote software maintenance and de-
bugging, and to support intra- and inter-organizational infor-
mation exchange.
We have described the end-user services required across one
or more data networks. We have carefully refrained from dis-
cussing which services should be provided in the data network,
and' which shfuld be provided in the hosts..Here the choice
in single networks will depend on the network technology ahd
the application requirements. For example, in a network using
a broadcast technology such as ETHERNET or the SATNET,
multidestination facilities may well be incorporated in the data
network itself. In typical store-and-forward networks, this
feature might be provided at the host level by the transmission
of multiple copies of packets. This example highlights im-
mediately the difficulty of using sophisticated services at the
data network level across concatenated networks. If A, B,
and C are data networks connected as in Fig. 1, and A and C
but not 8 support broadcast or real-time features, it is very
difficult to provide them across the concatenation of A, 8, and
C.
The problem of achieving a useful set of internetwork ser-
vices might be approached in several ways, as follows.
1) Require all networks to implement the entire range of
desired services (e.g., datagram, virtual circuit, broadcast, real-
-----------------------------------------------------------
1390
time, etc.), and then attempt to support these services across
the gateways between the networks.
2) Require all networks to implement only the most basic
services (e.g., datagram or virtual circuit), support these ser-
vices across gateways, and rely on the subscriber to imple-
ment all other services end-to-end.
3) Allow the subscriber to identify the services which he
desires and provide error indications if the networks involved,
or the gateways between them, cannot provide the desired
services.
4) Allow the subscriber to specify the internetwork route to
be followed and depend on the subscriber to decide which
concatenation of services are appropriate and what end-to-end
protocols are needed to achieve the ultimately preferred class
of service.
ß ß $) P. rovide. one set of sen'ices for local. use. within each net-
work 'and another, I{0ssiily different set for internetwork
use.
The five choices above are by no means exhaustive, and, in
fact, only scratch the surface of possibilities. Nothing has
been said, thus far, about the compatibility of various levels
of communication protocols which exist within each network,
within subscriber equipments, and within the logical gateway
between networks. To explore these issues further, it will be
helpful to have a model of internetwork architecture, taking
into account the common principle of protocol layering and
the various possible choices of interconnection strategy which
depend upon the protocol layer at which the networks are
interfaced. We consider this in the next section.
V. LAYERED PROTOCOL CONCEPTS
Both to provide services in single networks, and to compare
the capabilities of different networks, a very useful concept
in networking is protocol layering. Various services of increas-
ing capability can be built one on top of the other, each using
the 'facilities of the service layer below and supporting the
facilities of the layer above. A thorough tutorial on this con-
cept can be found in the paper by Pouzin and Zimmermann in
this issue [37]. We give some specific examples below of layer-
ing as a means of illustrating the scope of services and inter-
faces to be found in packet networks today-and some of the
problems encountered in offering services across multiple
networks.
Table I offers a very generic view of a typical protocol
hierarchy in a store-and-forward computer network, including
layers usually found outside of the communication network
itself. There are several complications to the use of generic
protocol layering to study network interconnection issues.
Chief among these is that networks do not all contain the same
elements of the generic hierarchy. A second complication is
that some networks implement service functions at different
protocol layers. For instance, virtual circuit networks imple-
ment an end/end subscriber virtual circuit in their intranet,
end/end level protocol. Finally, the hierarchical ordering of
functions is not always the same in all networks. For instance,
TYMNET places a terminal handling protocol within the net-
work access layer, so that hosts look to each other like'one or
more terminals. Figs. 2-7 illustrate the functional layering
of some different networks. It is important to note how the
functions vary with the choice of transmission medium.
A. ETHERNET
In Fig. 2, we represent the Xerox ETHERNET protocol
hierarchy. Th basic link control mechanism is the ability of
PROCEEDINGS OF THE IEEE, VOL. 66, NO. 11,
KIR
TABLE I
GENERIC PROTOCOL LAYERS
PROTOCOL LAYER
6. APPLICATION
5. U TILITV
4. ENDSEND SUBSCBtBER
3. NETWORK ACCESS
2. INTRANET. END.TO.END
1. INTRANET, NODE-TO-NODE
FUNCTION MATION'' ,i
FUNDS TRANSFERß INFOR
RETRIEVAL. ELECTRONIC MAIL.
SUPPORT
INTERPROCESS CO
RAL-TIME. BROADCAST) '
(E,G. VIRTUAL CIRCUIT, DATAGRAM
CONGESTION CON
APPLICATION
UTILITY FILE TRANSFER) VIRTUAL TERMINAL )IRECTORY
FILE
STRSAM PROTOCOL
END.TO.END
SUBSCRIBER
RELIABL:- PACKET PROTOCOL
NETWORK ACCESS BROADCAST DATAGRAM (UNRELIABLE)
LINK CONTROL
Fig. 2. ETHERNET protocol layering.
' '.red in se
' 'aglan-like :
'ided even t
'' this ser
J:{_"'. a seqm
for eae;
servic
an
the interface device to detect conflict on a shared coaxial c TM circuits
If a transmitting interface detects that another interh;, ' "as desig
also transmitting, it immediately aborts the transmt," the on;
Hosts attached to the network interface present datagram* :' unreliaL
be transmitted and are told if the datagram as aboa*a e
Datagrams can be addressed to specific interfaces or to ,r_ ..;
them. The end/end subscriber layer of protocol is spht -"' Voict
two parts: a reliable datagram protocol in which each '"-' Protocc
gram is reliably delivered and separately acknowledged. .a dela3
a stream protocol which can be thought of as a virtual
This split is possible, in part, because there is a fairly ' e.found
maximum datagram size (about 500 bytes) so that user :,' a
cations can send datagrams without having to fragmen. (e, end/
reassemble them. This makes the datagam service use!
many applications which might otherwise have to u ' (TE]
stream protocol. All higher level protocols, such as X'"'*'$ '[40], [4
Terminal and File Transfer, are carried out in the hosts. req
level a
B. ARPANET
The ARPANET protocol hierarchy is shown in Fig. 3. (R.'
basic link control between packet switches treats the phi ).effect
link as eight independent virtual links. This increases i0 the
tive throughput, but does not necessarily preserve the :aetwo:
in which packets were originally introduced into the net itY, a .
The intranet node-to-node protocols deal with'adaptive dli. Th
(IMP,
ing decisions, store-and-forward service, and
trol. Hosts have the option of either passing messages
-----------------------------------------------------------
)VEM
4ATI01
4AlL
IECTORY
FID[ ACE .
Jd coaxial
.her inteffa
e transmLviea
nt datagramS
m w a
'aces or
col fl at
ch ea
that
to frat.
such
the
nin
-eats
s
resel'e
into the
th
con
AND KIRSTEIN: ISSUES IN PACKET NETWORK INTERCONNECTION
ATION RJE ELECTRONIC
' MAIL
y TELNET FTP
IRK ACCESS PERMANENT VIRTUAL CIRCUIT DATAGRAM
NET, END/END FLOW CONTROl... SEQUENCING.
MESSAGE REASSEMBLY
NET. NODFJNODE ADAPTIVE ROUTING, STORE AN0 FORWARD,
CONGESTION CONTROL
ONTROL NON,SEQUENCED, MULTI-CHANNEL ERROR CONTROL
sUBS
iNT
Fig. 3. ARPANET protocol layering.
,.3 bits of text) across the host/network interface, which
,,11 be delivered in sequence to the destination, or passing
ß ,3rams (up to I008 bits of text) which are not necessarily
zlivered in sequence. The user's network access interface is
ß ,[3gram-like in the sense that no circuit setup exchange is
::.,fled even to activate the sequenced message service. In
ß ..!ct, this service acts like a permanent virtual circuit over
,.',ich a sequence of discrete messages are sent. For the
equenced messages, there is exactly one virtual circuit main-
',,ned for each host/host pair. In fact, these virtual circuits
L':. set up dynamically and terminated by the source/destina-
n packet switches so as to improve resource utilization
-:$1, [62].
The end/end subscriber layer of ARPANET contains two
:in protocols: Network Control Protocol (NCP, [39], [40] )
,'4 Transmission Control Protocol (TCP, [25] ). NCP was the
L't interprocess communication protocol built for ARPANET.
relies on the sequenced message service provided by the net-
,rk and derives multiple virtual circuits between pairs of
'.:m by multiplexing. The TCP can use either the sequenced
::sage service or the datagram service. It does its own
quencing and end/end error control and derives multiple
,-'tual circuits through extended addressing and multiplexing.
œ? was designed for operation in a multinet environment in
,ich the. only service which reasonably could be expected
,u an unreliable, unsequenced datagram service.
1% support experiments in packetized voice communication,
',0 protocols were developed for use on the ARPANET. The
setwork Voice Protocol (NVP) and Network Voice Confer-
=ciag Protocol (NVCP) use the datagram service to achieve
-.ry low delay and intorarrival time.variance in upport of
.ital, compressed packet speech (more on these rotocols
=iY be found in [411). The NVP could be considered the
asis for a generic protocol which could support a variety of
'-Ltime, end/end user applications.
le higher level utility protocols such as terminal/host
(TELNET, [40], [42]) and f'rie transfer protocol
, [42] ) use virtual circuits provided by NCP or TCP.
ß :t FTP requires one live interactive stream to control the
'ta transfer, and a second for the data stream itself. Yet
er level applications such as electronic mail and remote
entry (RJE, [40], [42]) use mixtures of TELNET and
to effect the service desired. These protocols are usually
at into the hosts. There is one anomaly, which occurs in
networks. Because terminal handling is required so
Terminal Interface Message Processor (TIP, [43 ] )
ns built. This device is physically integrated with the packet
(IMP, [38]); it includes also the NCP and TELNET
1391
END/END
SUBSCRIBER TERMINAL-TO-HOST
NE'NORK ACCESS' VIRTUAL CIRCUIT
END-END
INTRANET FRAME DISASSEMBLY. REASSEMBLY,
N00E.NODE ROUTING. STORFJFORWARD. CONGESTION CONTROL
LINK CONTROL FRAME-BASED ERROR CONTROL..
RETRANSMISSION. SEQUENCING
Fig. 4. TYMNET protocol layering.
C. TYMNET
TYMNET (see Fig. 4) is one of the oldest of the networks in
the collection described here [3]. Strictly speaking, it oper-
ates rather differently than other packet-switched networks,
because the frames of data that move from switch to switch
are disassembled and reassembled in each switch as an integral
part of the store-and-forward operation. Nevertheless, the net-
work benefits from the asynchronous sharing of the circuits
between the switches in much the same way that more typical
packet-switched networks do. The network was designed to
support remote terminal access to time-shared computer re-
sources. The basic service is the transmission of a stream of
characters between the terminal and the serving host. A
frame is made up of one or more blocks of characters, each
block labeled with its source terminal identifier and length.
The switch-to-switch layer of protocol disassembles each frame
into its constituent blocks and uses a routing table to deter-
mine to which next switch the block should be sent. Blocks
destined for the same next switch axe hatched together in a
frame which is checksummed and sent via the link control
procedure to the next switch. Batching the blocks reduces
line overhead (the blocks share the frame checksum) at the
expense of more CPU cycles in the switch for frame dis-
assembly and reassembly.
The protocol between TYMNET switches also includes a
flow control mechanism which, because of the fixed routes,
can be used to apply back pressure all the way back to the
traffic source. This is not precisely an end-to-end flow control
mechanism,'but a hop-by-hop back pressure strategy. Charac-
ter blocks are kept in sequence along the fixed routes so that
no resequencing is required as they exit from the network at
their destinations. The network interface is basically a virtual
circuit designed to transport character streams between a
host and a terminal. The ame.virtual' circuits can be used to .
transport character streams between hosts, which ldoli io each
other like a collection of terminals. Above the basic virtual
circuit service, is a special echo-handling protocol which
allows the host and the terminal handler in the "remote
TYMSAT" to coordinate the echoing of the characters typed
by a user.
D. PTT Networks
Many PTT networks, e.g., TELNET, TRANSPAC, DATA-
PAC, and EURONET use a particular network-access protocol,
X.25 [28], [29] (see Fig. 5). This protocol has been recom-
mended by the CCITT for public packet-switched data .net-
works. X.25 is a three-part protocol consisting of a hardware
electrical interface, X.21 [44], the digital iquivalent of the
usual V.24 or EIA-RS232C modem interface [45], a link
control procedure, High Level Data Link Control (HDLC,
[46]), and a packet-level protocol for effectins the setup,
use, termination, flow, and error contr6l of virtual circuits.
-----------------------------------------------------------
1392
UTILITY TERMINAL HANDLING X. X.29
SUBSCRIBER
NETVVORK ACCESS X5. PERMANENT OR TEMPORARY
VIRTUAL CIRCUITS
INTRANET. MULTIPLE VIRTUAL CIRCUITS,
END-END FLOW CONTROL
INTRANET ROUTING. STORFJFORWARD.
NODE.NODE CONGESTION CONTROL
LiNK CONTROl. HDLC OR EQUIVALENT
Fig. S. PTT protocoltayer[ng.
In all but the DATAPAC network, a fixed route for routing
packets throtlgh the network is selected at the time the virtual
circuit is created. "Permanent" virtual circuits are a customer
option; if used, the'setup-phase is invoked only in the case of
a network failure. Between source and destination packet
switches, a virtual circuit protocol is operated which imple-
ments end-to-end flow control on multiple virtual circuits
between pairs of packet switches. Up to 4096 virtual circuits
between pairs of host ports can be maintained by each packet
switch, as compared to the single virtual circuit provided by
ARPANET (on which hosts can multiplex their own virtual
circuits). This choice has a noticeable impact on the sub-
scriber interface protocol which becomes complicated be-
cause the subscriber host and the packet switch to which it
attaches must maintain a consistent view of the state of each
vixtual circuit in use.
To provide for echo control, user commands, code conver-
sion, and other terminal-related services, these networks
implement CCITT Recommendations X.28 [29] and X.29
[29] in a PAD (Packet Assembly and Disassembly unit).
These protocols sit atop the virtual circuit X.25 protocol. In
order to serve customers desiring a terminal-to-host service
with character terminals, such as is provided by TYMNET or
by the ARPANET (through the TIP), most of the PTT net-
works mentioned are developing a PAD unit. A matching
X.29 (PAD control protocol) layer must be provided in hosts
offering to service' terminals connected to PAD's.
E. High Level Protocols
The X.25/X.28/X.29 protocol hierarchy does not include an
end/end subscriber or high-level protocol layer. Some cus-
tomers will, in fact, implement end-to-end protocols on top
of the virtual circuit protocol, but others may not. Several
attempts are being made to standardize protocols above the
network access level. The ARPANET community has de-
veloped a Transmission Control Protocol [25]. for internet-
work operation to replace the Network Control Program
(NCP) developed early in the ARPANET project. The Inter-
national Federation of Information Processing (IFIP) has
proposed a Transport Station through its Working Group 6.1
on Network Interconnection [47]; the proposal has been sub-
mitted to the International Standards Organisation (ISO) as
a draft standard. In addition, other communities, e.g., the
High Level Protocol Working Group in the UK, have devised
protocols for Virtual Packet Terminals (VPT, [48]) and File
Transport Protocol (FTP, [49] ) which are intended to be net-
work independent and which may be submitted to CCITT.
The ISO study on "open systems architecture" and the pro-
posed similar study by CCITT Study Group VII will attempt
to evolve higher level protocol recommendations for existing
and future data networks.
PROCEEDINGS OF THE IEEE, VOL. 66, NO. I 1, NOVEMBER
This brief summary of different network-protocol layertoo
is in no Way comprehensive, but illustrates the divemiry
protocol desigfis which can be found on nets providing
ent types of services to subscribers.
VI. TECHNICAL INTERCONNECTION CHOICES
A. The Issues
Beginning with the earliest papers dealing with strater
for packet-network interconnection [23]-[26], [32], t,
common objective of all the proposed methods is to Prm-.a
the physical means to access the services of a host on one
work to all subscribers (including hosts) of all the interco,
neeted networks. Of course, limitations to this accessib-,h:t
are envisaged, imposed either for administrative ressore
by the scarcity of resources. The achievement of this
ß rive invari'ably requires that data produced at a source in
net be delivered and correctly interpreted at the destinatzo.,
in another network. In an abstract sense, this boils do.-.
providing interprocess communicati'on across network
aries. Even if a person is the ultimate source of the
packet-switching networks must interpose some degree of
ware processing between the person and the destinetiDe .-
vice, even if only to assemble or disassemble packets produ.,,
by a computer terminal.
A fundamental aspect of interprocess communicat,.-.
that no communication can take place without some a:r,
conventions. The communicating processes must share -.
physical transmission medium (wire, shared memory.
spectrum, etc.), and they must use common conventior,
agreed upon translation methods in order to successfulb
change and interpret the data they wish to commmicate.
of the key elements in any network interconnection
is therefore how the required commonality is to be obta'..'.'
In some cases, it is enough to translate one protocol ""
another. In others, protocols can be held in common
the communicating parties.
In any real network interconnection, of course, a nutone:
secondary objectives will affect the choice of interconncc:-
strategy. For example achievable bandwidth,
robustness (i.e., resistance t
