SECOND EDITION
`
`COMPUTER
`NETWORKS
`
`ANDREWS. TANENBAUM
`
`AA/SWA Ex. 1017, p.1 of 22
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00786
`
`

`

`Library of Congrnj Cawlogtllg·ln·Publication Data
`Tancnboum. Andrew S.
`Computer nelwor\<S I AndrewS. Tancnbaum.-2nd ed.
`p. em.
`Biblioglllphy: p.
`Includes index.
`ISBN ().13·1629.19-X
`I. Compuler ne1works
`TKSIOS.S.T.l6 1983
`00<1.6-«19
`
`I. Title.
`
`88-16937
`CIP
`
`EditoriaVproduction supervision: Lisa Schulz Garboski
`Manufacturing buyer: Mary Ann Gloriande
`
`Premice Hall Siftware Series
`Brian W. Kernighan, Advisor
`
`The publisher offers discounts on this book when ordered in bulk
`quantities. For more information, write:
`Special Sales/College Marketing
`Prentice Hall
`College Technical and Reference Division
`Englewood Cliffs, NJ 07632
`
`Q 1988 by Prentice-Hall, Inc.
`A Division of Simon & Schuster
`Englewood Cliffs, New Jersey 07632
`
`All rights reserved. No part of this book may be
`reproduced, in any form or by any means,
`without permission in writing from the publisher.
`
`Printed in the United States of America
`10 9 8 7 6 5 4 3
`ISBN 0-13-162959-X
`
`Prentice-Hall International (UK) Limited, London
`Prentice-Hall of Australia Pty. Limited, Sydney
`Prentice-Hall Canada Inc., Toronlo
`Prentice-Hall Hispanoarnericana, S.A., Mexico
`Prentice-Hall of India Private Limited, New Delhi
`Prentice-Hal I of Japan, Inc. , Tokyo
`Simon & Schuster Asia Pte. Ltd., Singapore
`Editora Prentiee-Hall do Brasil, Ltda., Rio de Janeiro
`
`AA/SWA Ex. 1017, p.2 of 22
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00786
`
`

`

`6
`CHAP. 1
`INTRODUCI'ION
`computer network as a sophisticated communication system may reduce the
`amount of traveling done, thus saving energy. Home work may become popular,
`especially for part-time workers with young children. The office and school as we
`now know them may disappear. Stores may be replaced by electronic mail order
`catalogs. Cities may disperse, since high-quality communication facilities tend to
`reduce the need for physical proximity. The information revolution may change
`society as much as the Industrial Revolution did.
`
`1.2. NETWORK STRUCTURE
`It is now time to turn our attention from the social implications of networking to
`the technical issues involved in network design. In any network there exists a col-
`lection of machines intended for running user (i.e., application) programs. We will
`follow the terminology of one of the first major networks, the ARPANET, and call
`these machines hosts. The term end system is sometimes also used in the litera-
`ture. The hosts are connected by the communication subnet, or just subnet for
`short. The job of the subnet is to carry messages from host to host, just as the tele-
`phone system carries words from speaker to listener. By separating the pure com-
`munication aspects of the network (the subnet) from the application aspects (the
`hosts), the complete network design is greatly simplified.
`In most wide area networks, the subnet consists of two distinct components:
`transmission lines and switching elements. Transmission lines (also called cir-
`cuits, channels, or trunks).move bits between machines.
`The switching elements are specialized computers used to connect two or more
`transmission lines. When data arrive on an incoming line, the switching element
`must choose an outgoing line to forward them on. Again following the original
`ARPANET terminology, we will call the switching elements IMPs (Interface
`Message Processors) throughout the book, although the terms packet switch node,
`intermediate system, and data switching exchange are also commonly used.
`Unfortunately, there is no consensus on terminology here; every writer on the sub-
`ject seems to use a different name. The term "IMP" is probably as good as any. In
`this model, shown in Fig. 1-2, each host is connected to one (or occasionally
`several) IMPs. All traffic to or from the host goes via its IMP.
`Broadly speaking, there are two types of designs for the communication subnet:
`
`1. Point-to-point channels.
`2. Broadcast channels.
`
`In the first one, the network contains numerous cables or leased telephone lines,
`each one connecting a pair of IMPs. If two IMPs that do not share a cable
`nevertheless wish to communicate, they must do this indirectly, via other IMPs.
`
`AA/SWA Ex. 1017, p.3 of 22
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00786
`
`

`

`SEC. 1.3
`
`NETWORK STRUCfURE
`
`9
`
`I I I I I I I
`
`(a)
`
`s.ton;.,
`
`7 \
`!111
`
`(b)
`
`(c)
`
`Fig. 1·4. Communication subnets using broadcasting. (a) Bus. (b) Satellite or ra·
`dio. (c) Ring.
`'\
`how the channel is allocated. A typical static allocation would be to divide up time
`into discrete intervals, and run a round robin, allowing each machine to broadcast
`only when its time slot comes up. Static allocation wastes channel capacity when a
`machine has nothing to say during its allocated slot, so some systems attempt to
`allocate the channel dynamically (i.e., on demand).
`Dynamic allocation methods for a common channel are either centralized or
`decentralized.· In the centralized channel allocation method, there is a single entity,
`for example a bus arbitration unit, which determines who goes next. It might do
`this by accepting requests and making a decision according to some internal algo-
`rithm. In the decentralized channel allocation method, there is no central entity;
`each machine must decide for itself whether or not to transmit. You might think
`that this always leads to chaos, but it does not. Later we will study many algo-
`rithms designed to bring order out of the potential chaos.
`
`1.3. NETWORK ARCHITECTURES
`Modern computer networks are designed in a highly structured way. In the fol-
`lowing sections we examine the structuring technique in some detail.
`1.3.1. Protocol Hierarchies
`To reduce their design complexity, most networks are organized as a series of
`layers or levels, each one built upon its predecessor. The number of layers, the
`name of each layer, the contents of each layer, and the function of each layer differ
`from network to network. However, in all networks, the purpose of each layer is to
`offer certain services to the higher layers, shielding those layers from the details of
`bow the offered services are actually implemented.
`
`AA/SWA Ex. 1017, p.4 of 22
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00786
`
`

`

`10
`
`CHAP. l
`INTRODUCTION
`Layer n on one machine carries on a conversation with layer n on another
`machine. The rules and conventions used in this conversation are collectively
`known as the layer n protocol, as illustrated in Fig. 1-5 for a seven-layer network.
`The entities comprising the corresponding layers on different machines are called
`peer processes. In other words, it is the peer processes that communicate using the
`protocol.
`
`Host B
`
`Host A
`
`Layer 7 protocol
`
`Layer 6 protocol
`
`Layer 5 protocol
`
`Layer 4 protocol
`
`Layer 3 protocol
`
`Layer 2 protocol
`
`Layer 1 protocol
`
`Physical medium
`
`Fig. 1-5. Layers, protocols, and interfaces.
`In reality. no data are directly transferred from layer n on one machine to layer
`n on another machine. lnstead, each layer passes data and control information to
`the layer immediately below it, until the lowest layer is reached. Below layer 1 is
`the physical medium through which actual communication occurs. In Fig. 1-5,
`virtual communication is shown by dotted lines and physical communication by
`solid lines.
`Between each pair of adjacent layers there is an interface. The interface
`defines which primitive operations and services the lower layer offers to the upper
`one. When network designers decide how many layers to include in a network and
`
`AA/SWA Ex. 1017, p.5 of 22
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00786
`
`

`

`14
`INTRODUCTION
`CHAP. 1
`demultiplexing is done transparently, it can be used by any layer. Multiplexing is
`needed in the physical layer, for example, where all the traffic for all connections
`has to be sent over at most a few physical circuits.
`When there are multiple paths between source and destination, a route must be
`chosen. Sometimes this decision must be split over two or more layers. For exam-
`ple, to send data from London to Rome, a high level decision might have to be
`made to go via France or Germany based on their respective privacy laws, and a
`low-level decision might have to be made to choose one of the many available cir-
`cuits based on current traffic.
`
`1.4. THE OSI REFERENCE MODEL
`Now that we have discussed layered networks in the abstract, it is time to look
`at the set of layers that will be used throughout this book. The model is shown in
`Fig. 1-7. This model is based on a proposal developed by the International Stan-
`dards Organization (ISO) as a first step toward international standardization of the
`various protocols (Day and Zimmermann, 1983). The model is called the ISO OSI
`Open Systems Interconnection) Reference Model because it deals with connect-
`ing open systems-that is, systems that are open for communication with other sys-
`tems. We will usually just call it the OSI model for short.
`The OSI model has seven layers. The principles that were applied to arrive at
`the seven layers are as follows:
`1. A layer should be created where a different level of abstraction is
`needed.
`2. Each layer should perform a well defined function.
`3. The function of each layer shoulci be chosen with an eye toward
`defining internationally standardized protocols.
`4. The layer boundaries should be chosen to minimize the information
`flow across the interfaces.
`5. The number of layers should be large enough that distinct functions
`need not be thrown together in the same layer out of necessity, and
`small enough that the architecture does not become unwieldy.
`In Sections 1.5.1 through 1.5.7 we will discuss each layer of the model in tum,
`starting at the bottom layer. Note that the OSI model itself is not a network archi-
`tecture because it does not specify the exact services and protocols to be used in
`each layer. It just tells what each layer should do. However, ISO has also pro-
`duced standards for all the layers, although these are not strictly speaking part of
`the model. Each one has been published as a separate international standard.
`
`AA/SWA Ex. 1017, p.6 of 22
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00786
`
`

`

`SEC. 1.5
`
`Layer
`
`THE OSI REFERENCE MODEL
`
`Presentation protocol
`
`Session protocol
`
`Transport protocol
`- ----------------- - ---------
`Communication subnet boundary
`
`Internal sub net protocol
`
`6
`
`5
`
`4
`
`3
`
`2
`
`Host A
`
`15
`Name of unit
`exchanged
`
`APDU
`
`P P D U
`
`S P D U
`
`TPDU
`
`Packet
`
`Frame
`
`- 1 Network
`Network f- --
`-- -1 o,<olmk
`D"'llok r
`'"'""' r--1
`'"'""' r -u
`l -1
`ll
`L Network layer host - IMP protocol
`
`IMP
`
`IMP
`
`-1 Ph,,,,, I • "
`
`Host B
`
`Data link layer host - IMP protocol
`Physical layer host - IMP protocol
`Fig. 1-7. The network architecture used in this book. It is based on the OSI
`model.
`1.4.1. The Physical Layer
`
`The physical layer is concerned with transmitting raw bits over a communica-
`tion channel. The design issues have to do with making sure that when one side
`sends a 1 bit, it is received by the other side as a 1 bit, not as a 0 bit. Typical ques-
`tions here are how many volts should be used to represent a 1 and how many for a
`0, how many microseconds a bit lasts, whether transmission may proceed simul-
`taneously in both directions, how the initial connection is established and how it is
`tom down when both sides are finished, and how many pins the network connector
`has and what each pin is used for. The design issues here largely deal with
`mechanical, electrical, and procedural interfaces, and the physical transmission
`medium, which lies below the physical layer. Physical layer design can be properly
`considered to be within the domain of the electrical engineer.
`
`AA/SWA Ex. 1017, p.7 of 22
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00786
`
`

`

`CHAP. 1
`
`INTRODUCTION
`
`16
`1.4.2. The Data Link Layer
`The main task of the data link layer is to take a raw transmission facility and
`transform it into a line that appears free of transmission errors to the network layer.
`It accomplishes this task by having the sender break the input data up into data
`frames (typically a few hundred bytes), transmit the frames sequentially, and pro-
`cess the acknowledgement frames sent back by the receiver. Since the physical
`· ·layer merely accepts and transmits a stream of bits without any regard to meaning
`or structure, it is up to the data link layer to create and recognize frame boundaries.
`This can be accomplished by attaching special bit patterns to the beginning and end
`of the frame. If these bit patterns can accidentally occur in the data, special care
`must be taken to avoid confusion.
`A noise burst on the line can destroy a frame completely. In this case, the data
`link layer software on the source machine must retransmit the frame. However,
`multiple transmissions of the same frame introduce the possibility of duplicate
`frames. A duplicate frame could be sent, for example, if the acknowledgement
`frame from the receiver back to the sender was destroyed. It is up to this layer to
`solve the problems caused by damaged, lost, and duplicate frames. The data link
`layer may offer several different service classes to the network layer, each of a dif-
`ferent quality and with a different price.
`Another issue that arises in the data link layer (and most of the higher layers as
`well) is how to keep a fast transmitter from drowning a slow receiver in data.
`Some traffic regulation mechanism must be employed to let the transmitter know
`how much buffer space the receiver has at the moment. Frequently, this flow regu-
`lation and the error handling are integrated, for convenience.
`If the line can be used to transmit data in both directions, this introduces a new
`complication that the data link layer software must deal with. The problem is that
`the acknowledgement frames for A to B traffic compete for the use of the line with
`data frames for the B to A traffic. A clever. solution (piggybacking) has been de-
`vised; we will discuss it in detail later.
`1.4.3. The Network Layer
`The network layer is concerned with controlling the operation of the subnet. A
`key design issue is determining how packets are routed from source to destination.
`Routes could be based on static tables that are "wired into" the network and rarely
`changed. They could also be determined at the start of each conversation, for
`example a terminal session. Finally, they coqld be highly dynamic, being deter-
`mined anew for each packet, to reflect the current network load.
`If too many packets are present in the subnet at the same time, they will get in
`each other's way, forming bottlenecks. The control of such congestion also belongs
`to the network layer.
`·
`Since the operators of the subnet may well expect
`for their efforts,
`
`AA/SWA Ex. 1017, p.8 of 22
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00786
`
`

`

`. 17
`SEC. 1.5
`THE OS! REFERENCE MODEL
`there is often some accounting function built into the network layer. At the very
`least, the software must count how many packets or characters or bits are sent by
`each customer, to produce billing information. When a packet crosses a national
`border, with different rates on each side, the accounting can become complicated.
`When a packet has to travel from one network to another to get to its destina-
`tion, many problems can arise. The addressing used by the second network may be
`different from the first one. The second one may not accept the packet at all
`because it is too large. The protocols may differ, and so on. It is up to the network
`layer to overcome all these problems to allow heterogenous networks to be inter-
`connected.
`In broadcast networks, the routing problem is simple, so the network layer is
`often thin or even nonexistent.
`
`1.4.4. The Transport Layer
`
`The basic function of the transport layer, is to accept data from the session
`layer, split it up into smaller units if need be, pass these to the network layer, and
`ensure that the pieces all arrive correctly at the other end. Furthermore, all this
`must be done efficiently, and in a way that isolates the session layer from the inevi-
`table changes in the hardware technology.
`Under normal conditions, the transport layer creates a distinct network connec-
`tion for each transport connection required by the session layer. If the transport
`connection requires a high throughput, however, the transport layer might create
`multiple network connections, dividing the data among the network connections to
`improve throughput. On the other hand, if creating or maintaining a network con-
`nection is expensive, the transport layer might multiplex several transport connec-
`tions onto the same network connection to reduce the cost. In all cases, the trans-
`port layer is required to make the multiplexing transparent to the session layer.
`The transport layer also determines what type of service to provide the session
`layer, and ultimately, the users of the network. The most popular type of transport
`connection is an error-free point-to-point channel that delivers messages in the
`order in which they were sent. However, other possible kinds of transport service
`are transport of isolated messages with no guarantee about the order of delivery,
`and broadcasting of messages to multiple destinations. The type of service is deter-
`mined when the connection is established.
`The transport layer is a true source-to-destination or end-to-end layer. In other
`words, a program on the source machine carries on a conversation with a similar
`program on the destination machine, using the message headers and control mes-
`sages. In the lower layers, the protocols are between each machine and its immedi-
`ate neighbors, and not by the ultimate source and destination machines, which may
`be separated by many IMPs. The difference between layers 1 through 3, which are
`chained, and layers 4 through 7, which are end-to-end, is illustrated in Fig. 1-7.
`
`AA/SWA Ex. 1017, p.9 of 22
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00786
`
`

`

`18
`
`CHAP. 1
`INTRODUCflON
`Many hosts are multiprogrammed, which implies that multiple connections will
`be entering and leaving each host. There needs to be some way to tell which mes-
`sage belongs to which connection. The transport header (H 4 in Fig. 1-6) is one
`place this information could be put.
`In addition to multiplexing several message streams onto one channel, the trans-
`port layer must take care of establishing and deleting connections across the net-
`work. This requires some kind of naming mechanism, so that a process on one
`machine has a way of describing with whom it wishes to converse. There must also
`be a mechanism to regulate the flow of information, so that a fast host cannot over-
`run a slow one. Flow control between hosts is distmct from flow control between
`IMPs, although we will later see that similar principles apply to both.
`
`1.4.5. The Session Layer
`
`The session layer allows users on different machines to establish sessions
`between them. A session allows ordinary data transport, as does the transport layer,
`but it also provides some enhanced services useful in a some applications. A ses-
`sion might be used to allow a user to log into a remote time-sharing system or to
`transfer a file between two machines.
`One of the services of the session layer is to manage dialogue control. Sessions
`can allow traffic to go in both directions at the same time, or in only one direction
`at a time. If traffic can only go one way at a time (analogous to a single railroad
`track), the session layer can help keep track of whose turn it is.
`A related session service is token management. For some protocols, it is
`essential that both sides do not attempt the same operation at the same time. To
`manage these activities, the session layer provides tokens that can be exchanged.
`Only the side holding the token may perform the critical operation.
`Another session service is synchronization. Consider the problems that might
`occur when trying to do a two-hour file transfer between two machines on a net-
`work with a 1 hour mean time between crashes. After each transfer was aborted,
`the whole transfer would have to start over again, and would probably fail again
`when the network next crashed. To eliminate this problem, the session layer pro-
`vides a way to insert checkpoints into the data stream, so that after a crash, only the
`data after the last checkpoint have to be repeated.
`
`1.4.6. The Presentation Layer
`
`that are requested
`functions
`layer performs certain
`The presentation
`sufficiently often to warrant finding a general solution for them, rather than letting
`each user solve the problems. In particular, unlike all the lower layers, which are
`just interested in moving bits reliably from here to there, the presentation layer is
`concerned with the syntax and semantics of the information transmitted.
`
`AA/SWA Ex. 1017, p.10 of 22
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00786
`
`

`

`19
`THE OSI REFERENCE MODEL
`SEC. 1.5
`A typical example of a presentation service is encoding data in a standard
`agreed upon way. Most user programs do not exchange random binary bit strings.
`They exchange things such as people's names, dates, amounts of money, and
`invoices. These items are represented as character strings, integers, floating point
`numbers, and data structures composed of several simpler items. Different comput-
`ers have different codes for representing character strings (e.g., ASCII and
`EBCDIC), integers (e.g., one's complement and two's complement), and so on. In
`order to make it possible for computers with different representations to communi-
`cate, the data structures to be exchanged can be defined in an abstract way, along
`with a standard encoding to be used "on the wire." The job of managing these
`abstract data structures and converting from the representation used inside the com-
`puter to the network standard representation is handled by the presentation layer.
`The presentation layer is also· concerned with other aspects of information
`representation. For example, data compression can be used here to reduce the
`number of bits that have to be transmitted and cryptography is frequently required
`for privacy and authentication.
`1.4.7. The Application Layer
`The application layer contains a variety of protocols that are commonly needed.
`For example, there are hundreds of incompatible terminal types in the world. Con-
`sider the plight of a full screen editor that is supposed to work over a network with
`many different terminal types, each with different screen layouts, escape sequences
`for inserting and deleting text, moving the cursor, etc.
`One way to solve this problem is to define an abstract network virtual termi-
`nal that editors and other programs can be written to deal with. To handle each ter-
`minal type, a piece of software must be written to map the functions of the network
`virtual terminal onto the real terminal. For example, when the editor moves the vir-
`tual terminal's cursor to the upper left -hand corner of the screen, this software must
`issue the proper command sequence to the real terminal to get its cursor there too.
`All the virtual terminal software is in the application layer.
`Another application layer function is file transfer. Different file systems have
`different file naming conventions, different ways of representing text lines, and so
`on. Transferring a file between two different systems requires handling these and
`other incompatibilities. This work, too, belongs to the application layer, as do elec-
`tronic mail, remote job entry, directory lookup, and various other general-purpose
`and special-purpose facilities.
`1.4.8. Data Transmission in the OSI Model
`Figure 1-8 shows an example of how data can be transmitted using the OSI
`model. The sending process has some data it wants to send to the receiving pro-
`cess. It gives the data to the application layer, which then attaches the application
`
`AA/SWA Ex. 1017, p.11 of 22
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00786
`
`

`

`20
`CHAP. 1
`INTRODUCTION
`header, AH (which may be null), to the front of it and gives the resulting item to the
`presentation layer.
`
`-1 Data J-
`------ j__ - - - j__--- -
`
`I
`I
`Application protocol-! AH I Data I -
`I
`I
`
`__ +--=-=-__ -1----la-ye--r---+--1
`
`- ------+-.
`
`Application
`layer
`
`Presentation
`
`Session
`layer
`
`Transport
`layer
`_ __ ---4-t
`Network
`layer
`
`Data link
`layer
`
`Physical
`layer
`
`Sending
`Process
`
`r+----......
`
`Application
`layer
`
`Presentation
`
`Session
`layer
`
`/
`
`I
`
`_
`
`Data
`
`Session ...._, SH I
`protocol
`.
`.
`Transport...._, TH I
`I
`I I
`
`NH
`
`I
`
`Data
`
`I
`
`/ -
`.
`I
`
`1-
`I
`
`Transport
`layer
`.
`Data
`protoco I
`.
`.
`J--t- - - - --t ------L_ _________ j__ __ ___ _._ _
`I
`I
`Network
`Network
`-
`layer
`I
`
`Data link
`layer
`
`Physical
`layer
`
`---IDHI
`1
`
`-----[
`
`Data
`
`Bits
`
`jDT/-
`I
`
`[--
`
`\Actual data transmission path
`Fig. 1-8. An example of how the OSI model is used. Some of the headers may be
`null. (Source: H.C. Folts. Used with permission.)
`
`The presentation layer may transform this item in various ways, and possibly
`add a header to the front, giving the result to the session layer. It is important to
`realize that the presentation layer is not aware of which portion of the data given to
`it by the application layer is AH, if any, and which is true user data. Nor should it
`be aware.
`This process is repeated until the data reach the physical layer, where they are
`actually transmitted to the receiving machine. On that machine the various headers
`are stripped off one by one as the message propagates up the layers until it finally
`arrives at the receiving process.
`The key idea throughout is that although actual data transmission is vertical in
`Fig. 1-8, each layer is programmed as though it were really horizontal. When the
`sending transport layer, for example, gets a message from the session layer, it
`attaches a transport header and sends it to the receiving transport layer. From its
`
`AA/SWA Ex. 1017, p.12 of 22
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00786
`
`

`

`21
`SEC. 1.5
`THE OSI REFERENCE MODEL
`point of view, the fact that it must actually hand the message to the network layer
`on its own machine is an unimportant technicality. As an analogy, when an
`Uighur-speaking diplomat is addressing the United Nations, he thinks of himself as
`addressing the other assembled diplomats. That, in fact, he is really only speaking
`to his translator is seen as a technical detail.
`
`1.5. SERVICES
`The real function of each layer in the OSI model is to provide services to the
`layer above it. In this section we will look at precisely what a service is in more
`detail, but first we will give some of the OSI terminology.
`1.5.1. OSI Terminology
`The active elements in each layer are called entities. An entity can be a
`software entity (such as a process), or a hardware entity (such as an intelligent I/0
`chip). Entities in the same layer on different machines are called peer entities.
`The layer 7 entities are called application entities; the layer 6 entities are called
`presentation entities, and so on.
`The entities in layer N implement a service used by layer N + 1. In this case
`layer N is called the service provider and layer N + 1 is called the service user.
`Layer N may use the services of layer N - 1 in order to provide its service. It may
`offer several classes of service, for example, fast, expensive communication and
`slow, cheap communication.
`Services are available at SAPs. (service access points), The layer N SAPs are
`the places where layer N + 1 can access the services offered. Each SAP has an
`address that uniquely identifies it. To make this point clearer, the SAPs in the tele-
`phone system are the sockets into which modular telephones can be plugged, and
`the SAP addresses are the telephone numbers of these sockets. To call someone,
`you must know his SAP address. Similarly, in the postal system, the SAP
`addresses are street addresses and post office boxes. To send a letter, you must
`know the addressee's SAP addiess. In Berkeley UNIXt, the SAPs are the sockets
`and the SAP addresses are the socket numbers. The SAP concept is discussed in
`detail by Tomas et al. (1987).
`In order for two layers to exchange information, there has to be an agreed upon
`set of rules about the interface. At a typical interface, the layer N + 1 entity passes
`an IDU (Interface Data Unit) to the layer N entity through the SAP as shown in
`Fig. 1-9. The IDU consists of an SDU (Service Data Unit) and some control infor-
`mation. The SDU is the information passed across the network to the peer entity
`t UNIX is a registered trademark of AT&T Bell Laboratories.
`
`AA/SWA Ex. 1017, p.13 of 22
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00786
`
`

`

`35
`
`EXAMPLE NETWORKS
`
`SEC. 1.8
`1.7.2. The ARPANET
`The ARPANET is the creation of ARPA (now DARPA), the (Defense)
`Advanced Research Projects Agency of the U.S. Department of Defense. Starting
`in the late 1960s it began stimulating research on the subject of computer networks
`by providing grants to computer science departments at many U.S. universities, as
`well as to a few private corporations. This research led to an experimental four-
`node network that went on the air in December 1969. It has been operating ever
`since, and has subsequently grown to several hundred computers spanning half the
`globe, from Hawaii to Sweden. Much of our present knowledge about networking
`is a direct result of the ARP ANEf project. To honor this pioneering work, we have
`adopted some of the original ARPANET terminology (e.g., host, IMP, subnet).
`After the ARPANET technology had proven itself by years of highly reliable
`service, a military network, MILNET, was set up using the same technology. An
`extension of MILNET in Europe, called MINET, was also created. MILNET and
`MINET are connected to the ARPANET, but the traffic between the parts is tightly
`controlled. Two satellite networks, SA TNET and WIDEBAND, were also hooked
`up later. Since many of the universities and government contractors on the
`ARPANET had their own LANs, eventually these were also connected to the IMPs,
`leading to the ARPA internet with thousands of hosts and well over 100,000 users.
`The ARPANET will be frequently cited throughout this book, but most of what is
`said about the ARPANET (e.g., the protocols used) also holds for the entire inter-
`net.
`The original ARPANET IMPs were Honeywell DDP-516 minicomputers with
`12K 16-bit words of memory. As time has gone on, the lMPs have been replaced
`several times by more powerful machines. They are now called PSNs (Packet
`Switch Nodes), but their function is the same as it was.
`Some of the IMPs have been configured to allow user terminals to call them
`directly, instead of logging into a host. These were called TIPs (Terminal Inter-
`face Processors) and are now called TACs (Terminal Access Controllers). The
`IMPs were originally connected by 56 kbps leased lines, although higher speed
`(e.g., 230.4 kbps), lines are now also used. The original IMPs could handle one to
`four hosts apiece. The current ones can handle tens of hosts and hundreds of termi-
`nals simultaneously.
`The ARPANET does not follow the OSI model at all (it predates OS! by more
`than a decade). The IMP-IMP protocol really corresponds to a mixture of the layer
`2 and layer 3 protocols. Layer 3 also contains an elaborate routing mechanism. In
`addition, there is a mechanism that explicitly verifies the correct reception at the
`destination IMP of each and every packet sent by the source IMP. Strictly speak-
`ing, this mechanism is another layer of protocol, the source IMP to destination IMP
`protocol. However, this protocol does not exist in the OSI model. We will treat it
`as part of layer 3, since it is closer to that layer than to any other.
`The ARPANET does have protocols that roughly cover the same territory as the
`
`AA/SWA Ex. 1017, p.14 of 22
`American Airlines, et. al. v. Intellectual Ventures, et.al.
`IPR2025-00786
`
`

`

`INTRODUCfiON
`CHAP. 1
`OSI network and ttansport protocols. The