Ethernet: Distributed Packet Switching for Local Computer Networks
Robert M. Metcalfe and David R. Boggs
Xerox Palo Alto Research
Center
Reprinted from Communications of the ACM,
Vol. 19, No. 5, July 1976 pp. 395 - 404
Copyright © 1976, Association for Computing
Machinery Inc.
This is a digitized copy derived from an ACM copyrighted work.
It is not guaranteed to be an accurate copy of the author's original
work.
Table of Contents
Abstract
1. Background
2. System Summary
3. Design Principles
4. Implementation
5. Growth
6. Performance
7. Protocol
8. Conclusion
References
Ethernet is a branching broadcast communication system for carrying
digital data packets among locally distributed computing stations. The packet
transport mechanism provided by Ethernet has been used to build systems
which can be viewed as either local computer networks or loosely coupled
multiprocessors. An Ethernet's shared communication facility, its Ether,
is a passive broadcast medium with no central control. Coordination of access
to the Ether for packet broadcasts is distributed among the contending transmitting
stations using controlled statistical arbitration. Switching of packets
to their destinations on the Ether is distributed among the receiving stations
using packet address recognition. Design principles and implementation are
described, based on experience with an operating Ethernet of 100 nodes along
a kilometer of coaxial cable. A model for estimating performance under heavy
loads and a packet protocol for error controlled communication are included
for completeness.
Key Words and Phrases: computer networks, packet switching, multiprocessing,
distributed control, distributed computing, broadcast communication, statistical
arbitration
CR Categories: 3.81, 4.32, 6.35
One can characterize distributed computing as a spectrum of activities varying
in their degree of decentralization, with one extreme being remote computer
networking and the other extreme being multiprocessing. Remote computer
networking is the loose interconnection of previously isolated, widely separated,
and rather large computing systems. Multiprocessing is the construction
of previously monolithic and serial computing systems from increasingly
numerous and smaller pieces computing in parallel. Near the middle of this
spectrum is local networking, the interconnection of computers to gain the
resource sharing of computer networking and the parallelism of multiprocessing.
The separation between computers and the associated bit rate of their communication
can be used to divide the distributed computing spectrum into broad activities.
The product of separation and bit rate, now about I gigabit-meter per second
(1 Gbmps), is an indication of the limit of current communication technology
and can be expected to increase with time: | Activity |
Separation | Bit rate |
|---|
| Remote networks |
> 10 km | < .1 Mbps |
| Local networks |
10-.1 km | .1-10 Mbps |
| Multiprocessors | .1
km | > 10 Mbps |
1.1 Remote Computer Networking
Computer networking evolved from telecommunications terminal-computer communication,
where the object was to connect remote terminals to a central computing
facility. As the need for computer-computer interconnection grew, computers
themselves were used to provide communication [2, 4, 29].
Communication
using computers as packet switches [15-21, 26]
and communications among
computers for resource sharing [10, 32]
were both advanced by the development
of the Arpa Computer Network.
The Aloha Network at the University of Hawaii was originally developed to
apply packet radio techniques for communication between a central computer
and its terminals scattered among the Hawaiian Islands [1, 2]
. Many of the
terminals are now minicomputers communicating among themselves using the
Aloha Network's Menehune as a packet switch. The Menehune and an Arpanet
Imp are now connected, providing terminals on the Aloha Network access to
computing resources on the U.S. mainland.
Just as computer networks have grown across continents and oceans to interconnect
major computing facilities around the world, they are now growing down corridors
and between buildings to interconnect minicomputers in offices and laboratories
[3, 12, 13, 14, 35].
1.2 Multiprocessing
Multiprocessing first took the form of connecting an I/O controller to a
large central computer; IBM's Asp is a classic example [29]. Next, multiple
central processors were connected to a common memory to provide more power
for compute-bound applications [33] For certain of these applications, more
exotic multiprocessor architectures such as Illiac IV were introduced [5].
More recently minicomputers have been connected in multiprocessor configurations
for economy, reliability, and increased system modularity [24, 36]. The
trend has been toward decentralization for reliability; loosely coupled
multiprocessor systems depend less on shared central memory and more on
thin wires for interprocess communication with increased component
isolation [18, 26].
With the continued thinning of interprocessor communication
for reliability and the development of distributable applications, multiprocessing
is gradually approaching a local form of distributed computing.
1.3 Local Computer Networking
Ethernet shares many objectives with other local networks such as Mitre's
Mitrix, Bell Telephone Laboratory's Spider, and U.C. Irvine's Distributed
Computing System (DCS) [12, 13, 14, 35].
Prototypes of all four local networking
schemes operate at bit rates between one and three megabits per second.
Mitrix and Spider have a central minicomputer for switching and bandwidth
allocation, while DCS and Ethernet use distributed control. Spider and DCS
use a ring communication path, Mitrix uses off-the-shelf CATV technology
to implement two one-way busses, and our experimental Ethernet uses a branching
two-way passive bus. Differences among these systems are due to differences
among their intended applications, differences among the cost constraints
under which trade-offs were made, and differences of opinion among researchers.
Before going into a detailed description of Ethernet, we offer the following
overview (see Figure 1).
- Figure 1. A two-segment Ethernet
-
Ethernet is a system for local communication among computing stations. Our
experimental Ethernet uses tapped coaxial cables to carry variable length
digital data packets among, for example, personal minicomputers, printing
facilities, large file storage devices, magnetic tape backup stations, larger
central computers, and longer-haul communication equipment.
The shared communication facility, a branching Ether, is passive. A station's
Ethernet interface connects bit-serially through an interface cable to a
transceiver which in turn taps into the passing Ether. A packet is broadcast
onto the Ether, is heard by all stations, and is copied from the Ether by
destinations which select it according to the packet's leading address bits.
This is broadcast packet switching and should be distinguished from store-and-forward
packet switching, in which routing is performed by intermediate process
processing elements. To handle the demands of growth, an Ethernet can be
extended using packet repeaters for signal regeneration, packet filters
for traffic localization, and packet gateways for internetwork address extension.
Control is completely distributed among stations, with packet transmissions
coordinated through statistical arbitration. Transmissions initiated by
a station defer to any which may already be in progress. Once started, if
interference with other packets is detected, a transmission is aborted and
rescheduled by its source station. After a certain period of interference-free
transmission, a packet is heard by all stations and will run to completion
without interference. Ethernet controllers in colliding stations each generate
random retransmission intervals to avoid repeated collisions. The mean of
a packet's retransmission intervals is adjusted as a function of collision
history to keep Ether utilization near the optimum with changing network
load.
Even when transmitted without source-detected interference, a packet may
still not reach its destination without error; thus, packets are delivered
only with high probability Stations requiring a residual error
rate lower than that provided by the bare Ethernet packet transport mechanism
must follow mutually agreed upon packet protocols.
Our object is to design a communication system which can grow smoothly to
accommodate several buildings full of personal computers and the facilities
needed for their support.
Like the computing stations to be connected, the communication system must
be inexpensive. We choose to distribute control of the communications facility
among the communicating computers to eliminate the reliability problems
of an active central controller, to avoid creating a bottleneck in a system
rich in parallelism, and to reduce the fixed costs which make small systems
uneconomical.
Ethernet design started with the basic idea of packet collision and retransmission
developed in the Aloha Network [1].
We expected that, like the Aloha Network,
Ethernets would carry bursty traffic so that conventional synchronous time-division
multiplexing (STDM) would be inefficient
[1, 2, 21, 26]. We saw promise
in the Aloha approach to distributed control of radio channel multiplexing
and hoped that it could be applied effectively with media suited to local
computer communication. With several innovations of our own, the promise
is realized.
Ethernet is named for the historical luminiferous ether through
which electromagnetic radiations were once alleged to propagate. Like an
Aloha radio transmitter, an Ethernet transmitter broadcasts completely-addressed
transmitter- synchronous bit sequences called packets onto the Ether and
hopes that they are heard by the intended receivers. The Ether is a logically
passive medium for the propagation of digit signals Is and can be constructed
using any number of media including coaxial cables, twisted pairs, and optical
fibers.
3.1 Topology
We cannot afford the redundant connections and dynamic routing of store-and-forward
packet switching to assure reliable communication, so we choose to achieve
reliability through simplicity. We choose to make the shared communication
facility passive so that the failure of an active element will tend to affect
the communications of only a single station. The layout and changing needs
of office and laboratory buildings leads us to pick a network topology with
the potential for convenient incremental extension and reconfiguration with
minimal service disruption.
The topology of the Ethernet is that of an unrooted tree. It is a tree
so that the Ether can branch at the entrance to a building's corridor, yet
avoid multipath interference. There must be only one path through the Ether
between any source and destination; if more than one path were to exist,
a transmission would interfere with itself, repeatedly arriving at its intended
destination having traveled by paths of different length. The Ether is unrooted
because it can be extended from any of its points in any direction: Any
station wishing to join an Ethernet taps into the Ether at the nearest convenient
point.
Looking at the relationship of interconnection and control, we see that
Ethernet is the dual of a star network. Rather than distributed
interconnection through many separate links and central control
in a switching node, as in a star network, the Ethernet has central
interconnection through the-Ether and distributed control among
its stations.
Unlike an Aloha Network, which is a star network with an outgoing broadcast
channel and an incoming multi-access channel, an Ethernet supports many-to-many
communication with a single broadcast multiaccess channel.
3.2 Control
Sharing of the Ether is controlled in such a way that it is not only possible
but probable that two or more stations will attempt to transmit a packet
at roughly the same time. Packets which overlap in time on the Ether are
said to collide; they interfere so as to be unrecognizable by a receiver.
A station recovers from a detected collision by abandoning the attempt and
retransmitting the packet after some dynamically chosen random time period.
Arbitration of conflicting transmission demands is both distributed and
statistical.
When the Ether is largely unused, a station transmits its packets at will,
the packets are received without error, and all is well. As more stations
begin to transmit, the rate of packet interference increases. Ethernet controllers
in each station are built to adjust the mean retransmission interval in
proportion to the frequency of collisions; sharing of the Ether among competing
station-station transmissions is thereby kept near the optimum [20, 21].
A degree of cooperation among the stations is required to share the Ether
equitably. In demanding applications certain stations might usefully take
transmission priority through some systematic violation of equity rules.
A station could usurp the Ether by not adjusting its retransmission interval
with increasing traffic or by sending very large packets. Both practices
are now prohibited by low-level software in each station.
3.3 Addressing
Each packet has a source and destination, both of which are identified in
the packet's header. A packet placed on the Ether eventually propagates
to all stations. Any station can copy a packet from the Ether into its local
memory, but normally only an active destination station matching its address
in the packet's header will do so as the packet passes. By convention, a
zero destination address is a wildcard and matches all addresses; a packet
with a destination of zero is called a broadcast packet.
3.4 Reliability
An Ethernet is probabilistic. Packets may be lost due to interference with
other packets, impulse noise on the Ether, an inactive receiver at a packet's
intended destination, or purposeful discard. Protocols used to communicate
through an Ethernet must assume that packets will be received correctly
at intended destinations only with high probability.
An Ethernet gives its best efforts to transmit packets successfully, but
it is the responsibility of processes in the source and destination stations
to take the precautions necessary to assure reliable communication of the
quality they themselves desire [18, 21]. Recognizing the costliness and
dangers of promising "error-free" communication, we refrain from
guaranteeing reliable delivery of any single packet to get both economy
of transmission and high reliability averaged over many packets
[21]. Removing
the responsibility for reliable communication from the packet transport
mechanism allows us to tailor reliability to the application and to place
error recovery where it will do the most good. This policy becomes more
important as Ethernets are interconnected in a hierarchy of networks through
which packets must travel farther and suffer greater risks.
3.5 Mechanisms
A station connects to the Ether with a tap and a transceiver. A tap is a
device for physically connecting to the Ether while disturbing its transmission
characteristics as little as possible. The design of the transceiver must
be an exercise in paranoia. Precautions must be taken to insure that likely
failures in the transceiver or station do not result in pollution of the
Ether. In particular, removing power from the transceiver should cause it
to disconnect from the Ether.
Five mechanisms are provided in our experimental Ethernet for reducing the
probability and cost of losing a packet. These are (1) carrier detection,
(2) interference detection, (3) packet error detection, (4) truncated packet
filtering, and (5) collision consensus enforcement.
3.5.1 Carrier detection.
As a packet's bits are placed on the Ether by a station, they are phase
encoded (like bits on a magnetic tape), which guarantees that there is at
least one transition on the Ether during each bit time. The passing of a
packet on the Ether can therefore be detected by listening for its transitions.
To use a radio analogy, we speak of the presence of carrier as a packet
passes a transceiver. Because a station can sense the car carrier of a passing
packet, it can delay sending one of its own until the detected packet passes
safely. The Aloha Network does not have carrier detection and consequently
suffers a substantially higher collision rate. Without carrier detection,
efficient use of the Ether would decrease with increasing packet length.
In Section 6 below, we show that with carrier detection, Ether efficiency
increases with increasing packet length.
With carrier detection we are able to implement deference: no station
will start transmitting while hearing carrier. With deference comes acquisition:
once a packet transmission has been in progress for an Ether end-to-end
propagation time, all stations are hearing carrier and are deferring; the
Ether has been acquired and the transmission will complete without an interfering
collision.
With carrier detection, collisions should occur only when two or more stations
find the Ether silent and begin transmitting simultaneously: within an Ether
end-to-end propagation time. This will almost always happen immediately
after a packet transmission during which two or more stations were deferring.
Because stations do not now randomize after deferring, when the transmission
terminates, the waiting stations pile on together, collide, randomize, and
retransmit.
3.5.2 Interference detection.
Each transceiver has an interference detector. Interference is indicated
when the transceiver notices a difference between the value of the bit it
is receiving from the Ether and the value of the bit it is attempting to
transmit.
Interference detection has three advantages. First, a station detecting
a collision knows that its packet has been damaged. The packet can be scheduled
for retransmission immediately, avoiding a long acknowledgment timeout.
Second, interference periods on the Ether are limited to a maximum of one
round trip time. Colliding packets in the Aloha Network run to completion,
but the truncated packets resulting from Ethernet collisions waste only
a small fraction of a packet time on the Ether Third, the frequency of detected
interference is used to estimate Ether traffic for adjusting retransmission
intervals and optimizing channel efficiency.
3.5.3 Packet error detection.
As a packet is placed on the Ether, a checksum is computed and appended.
As the packet is read from the Ether, the checksum is recomputed. Packets
which do not carry a consistent checksum are discarded. In this way transmission
errors, impulse noise errors, and errors due to undetected interference
are caught at a packet's destination.
3.5.4 Truncated packet filtering.
Interference detection and deference cause most collisions to result in
truncated packets of only a few bits; colliding stations detect interference
and abort transmission within an Ether round trip time. To reduce the processing
load that the rejection of such obviously damaged packets would place on
listening station software, truncated packets are filtered out in hardware.
3.5.5 Collision consensus enforcement.
When a station determines that its transmission is experiencing interference,
it momentarily jams the Ether to insure that all other participants in the
collision will detect interference and, because of deference, will be forced
to abort. Without this collision consensus enforcement mechanism, it is
possible that the transmitting station which would otherwise be the last
to detect a collision might not do so as the other interfering transmissions
successively abort and stop interfering. Although the packet may look good
to that last transmitter, different path lengths between the colliding transmitters
and the intended receiver will cause the packet to arrive damaged.
Our choices of I kilometer, 3 megabits per second, and 256 stations for
the parameters of an experimental Ethernet were based on characteristics
of the locally distributed computer communication environment and our assessments
of what would be marginally achievable; they were certainly not hard restrictions
essential to the Ethernet concept.
We expect that a reasonable maximum network size would be on the order of
I kilometer of cable. We used this working number to choose among Ethers
of varying signal attenuation and to design transceivers with appropriate
power and sensitivity.
The dominant station on our experimental Ethernet is a minicomputer for
which 3 megabits per second is a convenient data transfer rate. By keeping
the peak rate well below that of the computer's path to main memory, we
reduce the need for expensive special-purpose packet buffering in our Ethernet
interfaces. By keeping the peak rate as high as is convenient, we provide
for larger numbers of stations and more ambitious multiprocessing communications
applications.
To expedite low-level packet handling among 256 stations, we allocate the
first 8-bit byte of the packet to be the destination address field and the
second byte to be the source address field (see figure 2). 256 is a number
small enough to allow each station to get an adequate share of the available
bandwidth and approaches the limit of what we can achieve with current techniques
for tapping cables. 256 is only a convenient number for the lowest level
of protocol; higher levels can accommodate extended address spaces with
additional fields inside the packet and software to interpret them.
Our experimental Ethernet implementation has four major parts: the Ether,
transceivers, interfaces, and controllers (see Figure 1).
4.1 Ether
We chose to implement our experimental Ether using low-loss coaxial cable
with off-the-shelf CATV taps and connectors. It is possible to mix Ethers
on a single Ethernet; we use a smaller-diameter coax for convenient connection
within station clusters and a larger-diameter coax for low-loss runs between
clusters. The cost of coaxial cable Ether is insignificant relative to the
cost of the distributed computing systems supported by Ethernet.
4.2 Transceivers.
Our experimental transceivers can drive a kilometer of coaxial cable Ether
tapped by 256 stations transmitting at 3 megabits per second. The transceivers
can endure (i.e. work after) sustained direct shorting, improper termination
of the Ether, and simultaneous drive by all 256 stations; they can tolerate
(i.e. work during) ground differentials and everyday electrical noise, from
typewriters or electric drills, encountered when stations are separated
by as much as a kilometer.
An Ethernet transceiver attaches directly to the Ether which passes by in
the ceiling or under the floor. It is powered and controlled through five
twisted pairs in an interface cable carrying transmit data, receive data,
interference detect, and power supply voltages. When unpowered, the transceiver
disconnects itself electrically from the Ether. Here is where our fight
for reliability is won or lost; a broken transceiver can, but should not,
bring down an entire Ethernet. A watchdog timer circuit in each transceiver
attempts to prevent pollution of the Ether by shutting down the output stage
if it acts suspiciously. For transceiver simplicity we use the Ether's base
frequency band, but an Ethernet could be built to use any suitably sized
band of a frequency division multiplexed Ether.
Even though our experimental transceivers are very simple and can tolerate
only limited signal attenuation, they have proven quite adequate and reliable.
A more sophisticated transceiver design might permit passive branching of
the Ether and wider station separation.
4.3 Interface
An Ethernet interface serializes and deserializes the parallel data used
by its station. There are a number of different stations on our Ethernet;
an interface must be built for each kind.
Each interface is equipped with the hardware necessary to compute a 16-bit
cyclic redundancy checksum (CRC) on serial data as it is transmitted and
received This checksum protects only against errors in the Ether and specifically
not against errors in the parallel portions of the interface hardware or
station. Higher-level software checksums are recommended for applications
in which a higher degree of reliability is required.
A transmitting interface uses a packet buffer address and word count to
serialize and phase encode a variable number of 16-bit words which are taken
from the station's memory and passed to the transceiver, preceded by a start
bit (called SYNC in Figure 2) and followed by the CRC. A receiving interface
uses the appearance of carrier to detect the start of a packet and uses
the SYNC bit to acquire bit phase. As long as carrier stays on, the interface
decodes and deserializes the 'incoming bit stream depositing 16-bit words
in a packet buffer in the station's main memory. When carrier goes away,
the interface checks that an integral number of 1 6-bit words has been received
and that the CRC is correct. The last word received is assumed to be the
CRC and is not copied into the packet buffer.
These interfaces ordinarily include hardware for accepting only those pa
ckets with appropriate addresses in their headers. Hardware address filtering
helps a station avoid burdensome software packet processing when the Ether
is very busy carrying traffic intended for other stations.
An Ethernet controller is the station-specific low level firmware or software
for getting packets onto and out of the Ether. When a source-detected collision
occurs, it is the source controller's responsibility to generate a new random
retransmission interval based on the updated collision count. We have studied
a number of algorithms for controlling retransmission rates in stations
to maintain Ether efficiency [20, 22]. The most practical of these algorithms
estimate traffic load using recent collision history.
Retransmission intervals are multiples of a slot, the maximum time between
starting a transmission and detecting a collision, one end-to-end round
trip delay An Ethernet controller begins transmission of each new packet
with a mean retransmission interval of one slot. Each time a transmission
attempt ends in collision, the controller delays for an interval of random
length with a mean twice that of the previous interval, defers to any passing
packet, and then attempts retransmission. This heuristic approximates an
algorithm we have called Binary Exponential Backoff (see
Figure 3) [22].
- Fig. 3. Collision control algorithm
-
When the network is unloaded and collisions are rare, the mean seldom departs
from one and retransmission are prompt. As the traffic load increases, more
collisions are experienced, a backlog of packets builds up in the stations,
retransmission intervals increase, and retransmission traffic backs off
to sustain channel efficiency.
5.1 Signal Cover
One can expand an Ethernet just so far by adding transceivers and Ether.
At some point, the transceivers and Ether will be unable to carry the required
signals. The signal cover can be extended with a simple unbuffered packet
repeater. In our experimental Ethernet, where because of transceiver simplicity
the Ether cannot be branched passively, a simple repeater may join any number
of Ether segments to enrich the topology while extending the signal cover.
We operate an experimental two-segment packet repeater, but hope to avoid
relying on them. In branching the Ether and extending its signal cover,
there is a trade. off between using sophisticated transceivers and using
repeaters. With increased power and sensitivity, transceivers become more
expensive and less reliable. The introduction of repeaters into an Ethernet
makes the centrally interconnecting Ether active. The failure of a transceiver
will sever the communications of its owner; the failure of a repeater partitions
the Ether severing many communications.
5.2 Traffic Cover
One can expand an Ethernet just so far by adding Ether and packet repeaters.
At some point the Ether will be so busy that additional stations will just
divide more finely the already inadequate bandwidth. The traffic cover can
be extended with an unbuffered traffic-filtering repeater or packet filter,
which passes packets from one Ether segment to another only if the destination
station is located on the new segment. A packet filter also extends the
signal cover.
5.3 Address Cover
One can expand an Ethernet just so far by adding Ether, repeaters, and traffic
filters. At some point there will be too many stations to be addressed with
the Ethernet's 8-bit addresses. The address cover can be extended with packet
gateways and the software addressing conventions they implement [7]. Addresses
can be expanded in two directions: down into the station by adding fields
to identify destination ports or processes within a station, and up into
the internetwork by adding fields to identify destination stations on remote
networks. A gateway also extends the traffic and signal covers.
There can be only one repeater or packet filter connecting two Ether segments;
a packet repeated onto a segment by multiple repeaters would interfere with
itself. However, there is no limit to the number of gateways connecting
two segments; a gateway only repeats packets addressed to itself as an intermediary.
Failure of the single repeater connecting two segments partitions the network;
failure of a gateway need not partition the net it there are paths through
other gateways between the segments.
We present here a simple set of formulas with which to characterize the
performance expected of an Ethernet when it is heavily loaded. More elaborate
analyses and several detailed simulations have been done, but the following
simple model has proven very useful in understanding the Ethernet's distributed
contention scheme, even when it is loaded beyond expectations
[1, 20, 21,22, 23, 27].
We develop a simple model of the performance of a loaded Ethernet by examining
alternating Ether time periods. The first, called a transmission interval,
is that during which the Ether has been acquired for a successful packet
transmission. The second, called a contention interval, is that
composed of the retransmission slots of Section 4.4, during which stations
attempt to acquire control of the Ether. Because the model's Ethernets are
loaded and because stations defer to passing packets before starting transmission,
the slots are synchronized by the tail of the preceding acquisition interval.
A slot will be empty when no station chooses to attempt transmission in
it and it will contain a collision if more than one station attempts to
transmit. When a slot contains only one attempted transmission, then £he
Ether has been acquired for the duration of a packet, the contention interval
ends, and a transmission interval begins.
Let P be the number of bits in an Ethernet packet. Let C
be the peak capacity in bits per second, carried on the Ether. Let T be
the time in seconds of a slot, the number of seconds it takes to detect
a collision after starting a transmission. Let us assume that there are
Q stations continuously queued to transmit a packet; either the
acquiring station has a new packet immediately after a successful acquisition
or another station comes ready. Note that Q also happens to give
the total offered load on the network which for this analysis is always
l or greater. We assume that a queued station attempts to transmit in the
current slot with probability 1/Q, or delays with probability 1
- (1/Q)); this is known to be the optimum statistical decision
rule, approximated in Ethernet stations by means of our load-estimating
retransmission control algorithms [20, 21].
6.1 Acquisition Probability
We now compute A, the probability that exactly one station attempts a transmission
in a slot and therefore acquires the Ether. A is Q*(l/Q)*((1
- (l/Q))**(Q- 1)); there are Q ways In which
one station can choose to transmit (with probability ( 1/ Q) )
while Q-l stations choose to wait (with probability l- (I/Q)).
Simplifying,
A = (l -(1/Q))**(Q-l) .
6.2 Waiting Time
We now compute W, the mean number of slots of waiting in a contention
interval before a successful acquisition of the Ether by a station's transmission.
The probability of waiting no time at all is just A, the probability that
one and only one station chooses to transmit in the first slot following
a transmission. The probability of waiting l slot is A*(l-A);
the probability of waiting i slots is A*((1-A)**i).
The mean of this geometric distribution is
W = (l -A)/A.
6.3 Efficiency
We now compute E, that fraction of time the Ether is carrying good
packets, the efficiency. The Ether's time is divided between transmission
intervals and contention intervals. A packet transmission takes P/C
seconds. The mean time to acquisition is W*T. Therefore,
by our simple model, E = (P/C)/((P/C)
+ (W*T)). Table 1 presents representative performance
figures (i.e. E) for our experimental Ethernet with the indicated
packet sizes and number of continuously queued stations. The efficiency
figures given do not account for inevitable reductions due to headers and
control packets nor for losses due to imprecise control of the retransmission
parameter l/Q; the former is straightforwardly protocol-dependent
and the latter requires analysis beyond the scope of this paper. Again,
we feel that all of the Ethernets in the table are overloaded; normally
loaded Ethernets will usually have a Q much less than l and exhibit
behavior not covered by this model. For our calculations we use a C
of 3 megabits per second and a T of 16 microseconds. The slot duration
T must be long enough to allow a collision to be detected or at
least twice the Ether's round trip time. We limit in software the maximum
length of our packets to be near 4000 bits to keep the latency of network
access down and to permit efficient use of station packet buffer storage.
For packets whose size is above 4000 bits, the efficiency of our experimental
Ethernet stays well above 95 percent. For packets with a size approximating
that of a slot, Ethernet efficiency approaches 1/e, the asymptotic
efficiency of a slotted Aloha network [27].
There is more to the construction of a viable packet communication system
than simply providing the mechanisms for packet transport. Methods for error
correction, flow control, process naming, security, and accounting must
also be provided through higher-level protocols implemented on top of the
Ether control protocol described in Sections 3 and
4 above.
[7, 10, 12,21, 28, 34].
Ether control includes packet framing, error detection, addressing
and multi-access control; like other line control procedures, Ethernet is
used to support numerous network and multiprocessor architectures
[30, 31].
Here is a brief description of one simple error-controlling packet protocol.
The EFTP (Ethernet File Transfer Protocol) is of interest both because it
is relatively easy to understand and implement correctly and because it
has dutifully carried many valuable files during the development of more
general and efficient protocols.
7.1. General Terminology
In discussing packet protocols, we use the following generally useful terminology.
A packet is said to have a source and a destination. A
flow of data is said to have a sender and a receiver,
recognizing that to support a flow of data some packets (typically acknowledgments)
will be sourced at the receiver and destined for the sender. A connection
is said to have a listener and an initiator and a service
is said to have a server and a user. It is very useful
to treat these as orthogonal descriptors of the participants in a communication.
Of course, a server is usually a listener and the source of data-bearing
packets is usually the sender.
7.2 EFTP
The first 16 bits of all Ethernet packets contain its interface-interpretable
destination and source station addresses, a byte each, in that order (see
Figure 2). By software convention, the second 16 bits of all Ethernet packets
contain the packet type. Different protocols use disjoint sets of packet
types. The EFTP uses 5 packet types: data, ack, abort, end, and endreply.
Following the 16-bit type word of an EFTP packet are 16 bits of sequence
number, 16 bits of length, optionally some 16-bit data words, and finally
a 16-bit software checksum word (see Figure 4). The Ethernet's hardware
checksum is present only on the Ether and is not counted at this level of
protocol.
- Fig. 4. EFTP packet layout
-
It should be obvious that little care has been taken to cram certain fields
into just the right number of bits. The emphasis here is on simplicity and
ease of programming. Despite this disclaimer, we do feel that it is more
advisable to err on the side of spacious fields; try as you may, one field
or another will always turn out to be too small.
The software checksum word is used to lower the probability of an undetected
error. It serves not only as a backup for the experimental Ethernet's serial
hardware 16-bit cyclic redundancy checksum (in
Figure 2), but also for protection
against failures in parallel data paths within stations which are not checked
by the CRC. The checksum used by the EFTP is a l's complement add and cycle
over the entire packet, including header and content data. The checksum
can be ignored at the user's peril at either end; the sender may put all
l's (an impossible value) into the checksum word to indicate to the receiver
that no checksum was computed.
7.2.1 Data transfer.
The 16-bit words of a file are carried from sending station to receiving
station in data packets consecutively numbered from 0. Each data packet
is retransmitted periodically by the sender until an ack packet with a matching
sequen ce number is returned from the receiver. The receiver ignores all
damaged packets, packets from a station other than the sender, and packets
whose sequence number does not match either the expected one or the one
preceding. When a packet has the expected sequence number, the packet is
acked, its data is accepted as part of the file, and the sequence number
is incremented. When a packet arrives with a sequence number one less than
that expected, it is acknowledged and discarded; the presumption is that
its ack was lost and needs retransmission [21].
7.2.2 End.
When all the data has been transmitted, an end packet is sent with the next
consecutive sequence number and than the sender waits for a matching endreply.
Having accepted an end packet in sequence, the data receiver responds with
a matching endreply and then dallys for some reasonably long period of time
(10 seconds). Upon getting the endreply, the sending station transmits an
echoing endreply and is free to go off with the assurance that the file
has been transferred successfully. The dallying receiver then gets the echoed
endreply and it too goes off assured.
Table 1. Ethernet Efficiency.
| Q | P = 4096 | P = 1024 |
P = 512 | P = 48 |
| 1 |
1.0000 | 1.0000 | 1.0000 | 1.0000 |
| 2 | 0.9884 | 0.9552 | 0.9143 | 0.5000 |
| 3 | 0.9857 | 0.9447 | 0.8951 |
0.4444 |
| 4 | 0.9842 | 0.9396 | 0.8862 |
0.4219 |
| 5 | 0.9834 | 0.9367 | 0.8810 |
0.4096 |
| 10 | 0.9818 | 0.9310 | 0.8709 |
0.3874 |
| 32 | 0.9807 | 0.9272 | 0.8642 |
0.3737 |
| 64 | 0.9805 | 0.9263 | 0.8627 |
0.3708 |
| 128 | 0.9804 | 0.9259 |
0.8620 | 0.3693 |
| 256 | 0.9803 |
0.9257 | 0.8616 | 0.3686 |
The comparatively complex end-dally sequence is intended to make it practically
certain that the sender and receiver of a file will agree on whether the
file has been transmitted correctly. If the end packet is lost, the data
sender simply retransmits it as it would any packet with an overdue acknowledgement.
If the endreply from the data receiver is lost, the data sender will time
out in the same way and retransmit the end packet which will in turn be
acknowledged by the dallying receiver. If the echoed endreply is lost, the
dallying receiver will be inconvenienced having to wait for it, but when
it has timed out, the receiver can nevertheless be assured of successful
transfer of the file because the end packet has been received.
At any time during all of this, either side is free to decide communication
has failed and just give up; it is considered polite to send an abort packet
to end the communication promptly in the event of, say, a user- initiated
abort or a file system error.
7.2.3 EFTP shortcomings.
The EFTP has been very useful, but its shortcomings are many. First, the
protocol provides only for file transfer from station to station in a single
network and specifically not from process to process within stations either
on the same network or through a gateway. Second, process rendezvous is
degene~ate in that there are no mechanisms for finding processes by name
or for convenient handling of multiple users by a single server. Third,
there is no real flow control. If data arrives at a receiver unable to accept
it into its buffers, the data can simply be thrown away with complete assurance
that it will be retransmitted eventually. There is no way for a receiver
to quench the flow of such wasted transmissions or to expedite retransmission.
Fourth, data is transmitted in integral numbers of 16-bit words belonging
to unnamed files and thus the EFTP is either terribly restrictive or demands
some nested file transfer formats internal to its data words. And fifth,
functional generality is lost because the receiver is also the listener
and server.
Our experience with an operating Ethernet leads us to conclude that our
emphasis on distributed control was well placed By keeping the shared components
of the communication system to a minimum and passive, we have achieved a
very high level of reliability. Installation and maintenance of our experimental
Ethernet has been more than satisfactory. The flexibility of station interconnection
provided by broadcast packet switching has encouraged the development of
numerous computer networking and multiprocessing applications.
Acknowledgments. Our colleagues at the Xerox Palo Alto Research
Center, especially Tat C. Lam, Butler W. Lampson, John F. Shoch, and Charles
P. Thacker, have contributed in many ways to the evolution of Ethernet ideas
and to the construction of the experimental system without which such ideas
would be just so much speculation.
Received May 1975; revised December 1975
1. Abramson, N. The Aloha system. AFIPS Conf. Proc., Vol. 37, 1970 FJCC,
AFIPS Press, Montvale, N.J., 1970, pp. 281-285.
2. Abramson, N. and Kuo, F.F. Computer-Communication Net works. Prentice-Hall,
Englewood Cliffs, N.J., 1975.
3. Ashenhurst, R.L., and Vonderohe, R.H. A hierarchical network. Datamation
21, 2 (Feb. 1975), 40-44.
4. Baran, P. On distributed communications; Rand Corp. Memo RM-3420-PR,
Aug. 1964.
5. Barnes, G.H., Brown, R.M., Kato, M., Kuck, D.J., Slotnick, D.L., and
Stokes, R.A. The Illiac IV Computer. IEEE Trans. Computers C-17, 8 (Aug.
1968), 758-770.
6. Binder, R., Abramson, N., Kuo, F., Okinaka, A., and Wax, D. Aloha packet
broadcasting-a retrospect. AFIPS Conf. Proc., Vol. 44, 1975 NCC, AFIPS Press,
Montvale, N.J., 1975.
7. Cerf, V.G., and Kahn, R.E. A protocol for packet network intercommunication
IEEE Trans. Comm. COMM- 22, 5 (May 1974), 637-648.
8. The shrinking world: computer networks and communications. Computer
7, 2 (Feb. 1974).
9. Distributed-function computer architectures. Computer 7, 3 (March 1974).
10. Crocker, S.D., Heafner, J.F., Metcalfe, R.M., and Postel, J.B. Function-oriented
protocols for the Arpa computer network. AFIPS Conf. Proc., Vol. 40, 1972
SJCC, AFIPS Press, Montvale, N.J., 1972, pp. 271-279.
11. Crowther, W.R., Heart, F.E., McKenzie, A.A., McQuillan, J.M., and Walden,
D.C. Issues in packet-switching network de sign. AFIPS Conf Proc., Vol.
44, 1975 NCC, AFIPS Press, Mont vale, N.J., 1975, pp. 161-175.
12. Farber, D.J., et al. The distributed computing system. Proc. 7th Ann.
IEEE Computer Soc. International Conf., Feb. 1973, pp. 31-34.
13. Farber, D.J., A ring network. Datamation 21, 2 (Feb. 1975), 44 46.
14. Fraser, A.G. A virtual channel network. Datamation 21, 2 (Feb. 1975),
51-53.
15. Heart, F.E., Kahn, R.E., Ornstein, S.M., Crowther, W.R., and Walden,
D.C. The interface message processor for the Arpa computer network, AFIPS
Conf. Proc., Vol. 36, 1970 SlCC, AFIPS Press, Montvale, N.J., 1970, pp.
551-567.
16. Heart, F.E., Ornstein, S.M., Crowther, W.R., and Barker, W.B. A new
minicomputer-multiprocessor for the Arpa network. AFIPS Conf. Proc., Vol.
42, 1972 SJCC, AFIPS Press, Montvale, N.J., 1972, pp. 529-537.
17. Kahn, R.R. The organization of computer resources into a packet ratio
network. AFIPS Conf. Proc., Vol. 44, 1975 NCC, AFIPS Press, Montvale, N.J.,
1975, pp. 177-186.
18. Metcalfe, R.M. Strategies for interprocess communication in a distributed
computing system. Proc. Symp. on Computer Com mun. Networks and Teletraffic.
Polytechnic Press, New York, 1972.
19. Metcalfe, R.M. Strategies for Operating Systems in Computer Networks,
Proc. ACM National Conf.' August 1972, pp. 278-281.
20. Metcalfe, R.M. Steady-state analysis of a slotted and con trolled aloha
system with blocking. Proc. 6th Hawaiu Conf. on System Sci. Jan. 1973, pp.
375-380.
21. Metcalfe, R.M. Packet communication. Harvard Ph.D. Th., Project Mac
TR-I 14, Dec. 1973.
22. Metcalfe, R.M. Distributed algorithms for a broadcast queue. Talk given
at Stanford University in November 1974 and at the University of California
at Berkeley in February 1975, paper in preparation.
23. Murthy, P. Analysis of a carrier-sense random-access system with random
packet length. Aloha System Tech. Rep. B75-17, U. of Hawaii, May 1975.
24. Ornstein, S.M., Crowther, W.R., Kraley, M.F., Bressler, R.D., Michel,
A., and Heart, F.E. Pluribus-a reliable multiprocessor AFIPS Conf. Proc.,
Vol. 44, 1975 NCC, AFIPS Press, Montvale, N.J., 1970, pp. 551-559.
25. Retz, D.L. Operating system design considerations for the packet switching
environment. AFIPS Conf. Proc., Vol. 44, 1975 NCC, AFIPS Press, Montvale,
N.J., 1970, pp. 155-160.
26. Roberts, L., and Wessler, B. Computer network development to achieve
resource sharing. AFIPS Conf. Proc., Vol. 36, 1970 SJCC, AFIPS Press, Montvale,
N.J., 1970, pp. 543-549.
27. Roberts, L. Capture effects on Aloha channels. Proc. 6th Hawaii Conf.
on System Sci., Jan. 1973.
28. Rowe, L.A. The distributed computing operating system. Tech. Rep. 66,
Dep. of Information and Computer Sci., U. of California, Irvine, June 1975.
29. Rustin, R. (Ed.) Computer Networks (Proc. Courant Computer Sci. Symp.
3, December 1970), Prentice-Hall, Englewood Cliffs, N.J., 1970.
30. IBM synchronous data link control-general information. IBM Systems Development
Div., Pub. Center, Research Triangle Park, N.C., 1974.
31. IBM system network architecture-general information. IBM Systems Development
Div., Pub. Center, Research, Triangle Park, N.C., 1975.
32. Thomas, R.H. A resource sharing executive for the Arpanet. AFIPS ConL
Proc., Vol. 42, 1973 NCC, AFIPS Press, Montvale, N.J., 1973, pp. 155-163.
33. Thornton, J.E. Design of a Computer: the Control Data 6600. Scott Foresman
and Co., Glenview, III. 1970.
34. Walden, D.C. A system for interprocess communication in a resource sharing
computer network. Comm. ACM, 15, 4 (April 1972), 221-230.
35. Willard, D.G. Mitrix: A sophisticated digital cable communications
system Proc. National Telecommunications Conf., Nov. 1973.
36. Wulf, W., and Levin, R. C.mmp-a multi-mini-processor, AFIPS Conf. Proc.,
Vol. 41, 1972 FJCC, AFIPS Press, Montvale, N.J., 1972.
