leff@smu.CSNET.UUCP (07/10/87)
Naomi Schulman
Publications
COMPUTER SYSTEMS LABORATORY
STANFORD UNIVERSITY
Stanford, CA 94305
RECENT REPORTS & NOTES
LIST #10
JANUARY 1987
To order reports, see end of this announcement.
ABSTRACTS
CSL-TR-87-313
A Macroscopic Profile of Program Compilation and Linking
M.A. Linton and R.W. Quong
January 1987 15 pages.....$3.25
To profile the changes made to programs during development and maintenance, we
have instrumented the make utility that is used to compile and link programs.
With minor modifications, we have used make to find out how much time
programmers spend waiting for compiling and linking, how many modules are
compiled each time a program is linked, and the change in size of the compiled
modules.
Our measurements show that most programs are relinked after only one or two
modules are recompiled, and that over 90% of all recompilations yield object
code that is less than 100 bytes larger in size. We are using these results to
guide the design of an incremental programming environment, particularly with
respect to an incremental linker.
-------------------------------------------------------------------------------
CSL-TR-87-314
Post-Game Analysis An Initial Experiment for
Heuristic-based Resource Management in Concurrent Systems
Jerry C Yan
February 1987 18 pages.....$3.40
In concurrent systems, a major responsibility of the resource management system
is to decide how the application program is to be mapped onto the
multi-processor. Instead of using abstract program and machine models, a
generate-and-test framework known as "post-game analysis" that based on data
gathered during program execution is proposed. Each iteration consists of (i)
(a simulation of) an execution of the program; (ii) analysis of the data
gathered; and (iii) the proposal of a new mapping that would have a smaller
execution time. These heuristics are applied to predict execution time changes
in response to small perturbations applied to the current mapping. An initial
experiment was carried out using simple strategies on "pipeline-like"
applications. The results obtained from four simple strategies demonstrated
that for this kind of application, even simple strategies can produce
acceptable speed-up with a small number of iterations.
-------------------------------------------------------------------------------
CSL-TR-97-315 also numbered STAN-CS-87-1149
Proceedings from the Nineteenth Annual Meeting
of the Stanford Computer Forum
Edited by: Katie Mac Millen,
Ann Diaz-Barriga
Carolyn Tajnai
February 1987 246 pages.....$15.00
}
Operating for almost two decades, the Stanford Computer Forum is a
cooperative venture of the Computer Science Department and the
Computer Systems Laboratory (a laboratory operated jointly by the
Computer Science and Electrical Engineering Departments. CSD and CSL
are internationally recognized for their excellence; their faculty
members, research staff, and students are widely known for leadership
in developing new ideas and trends in the organization, design and use
of computers. They are in the forefront of applying research results
to a wide range of applications.
The Forum holds an annual meeting in February to which three
representatives of each member company are invited. The meeting lasts
two days and features technical sessions at which timely computer
research at Stanford is described by advanced graduate students and
faculty members. There are opportunities for informal discussions to
complement the presentations.
This report includes information on the Forum, the program, abstracts
of the talks and viewgraphs used in the presentations.
-------------------------------------------------------------------------------
CSL-TR-87-316
PERFORMANCE OF DEMAND ASSIGNMENT MULTIPLE ACCESS SCHEMES IN BROADCAST BUS
NETWORKS
Michael Fine
March 1987 248 pages.....$14.90
Local area communications networks based on packet switching techniques provide
simple architectures and efficient and flexible operation. Various ring
systems and CSMA contention bus systems have been in operation for several
years. More recently, a number of demand assignment multiple access (DAMA)
schemes suitable for broadcast bus networks have emerged which provide
conflict-free broadcast communications by means of various distributed
round-robin scheduling algorithms. In some of these schemes, explicit tokens,
i.e., control messages, are used to provide the required scheduling. Other
schemes use implicit tokens whereby stations in the network rely on information
deduced from the activity on the bus to schedule their transmissions. In this
work, three basic access mechanisms, according to which these implicit-token
DANA schemes can be classified, are identified. We describe these three
mechanisms and the various service disciplines achieved by them together with
their network topologies. We present some representative schemes for each
class, discussing their performance and other important attributes. We show
that these schemes overcome some of the performance limitations of existing
random access schemes, making them particularly suited to the high bandwidth
requirements of an integrated-services digital local network. For a more
extensive and detailed evaluation of the performance of these DAMA schemes, we
examine two of them, Expressnet and Fasnet, operating under various service
disciplines. Throughput and delay characteristics over a range of operating
conditions are presented and discussed. Lastly we propose a combined
voice/data protocol suitable for DAMA broadcast networks. Such networks are
well suited to the integration of voice and data since they guarantee bounded
delay and provide high utilization of the channel even at high bandwidths.
Using Expressnet as a representative scheme, we examine the characteristics of
the service that the voice traffic experiences under this protocol. We show
that the access protocol is able to utilize the channel efficiently to support
a large population of voice sources while maintaining low packet delay and
guaranteeing some prespecified minimum bandwidth for data traffic. In
addition, we show the advantages of silence suppression, i.e., discarding
speech that constitutes silent periods, and we look at the effects of
overloading the network.
-------------------------------------------------------------------------------
CSL-TR-87-317
COMPARATIVE PERFORMANCE OF BROADCAST BUS LOCAL AREA NETWORKS WITH VOICE AND
DATA TRAFFIC
Timothy A. Gonsalves
March 1987 216 pages.....$13.30
Recently, local area networks have come into widespread use for computer
communications. Together with the trend towards digital transmission of
telephone signals, this has sparked interest in the use of computer networks
for the transmission of integrated voice/data traffic. This work addresses two
related aspects of local area network performance, a detailed characterization
of the performance of Carrier Sense Multiple Access with Collision Detection
(CSMA/CD), and the comparative performance of several broadcast bus networks
with voice/data traffic.
While prior analysis of CSMA/CD has shown that the protocol achieves good
performance with data traffic over a range of conditions, the widely used IEEE
802.3 (Ethernet) implementation of the protocol has several aspects that are
not easily amenable to mathematical analysis. These include the
binary-exponential back-off algorithm used upon collision, the number of
buffers per station, and the physical distribution of stations. Performance
measurements on operational 3 and 10 Mb/s networks are presented. These
demonstrate that the protocol achieves high throughput with data traffic when
the packet transmission time is long compared to the propagation delay, as
predicted by analysis. However, at 10 Mb/s, with short packets on the order of
64 bytes, performance is poorer. The inflexibility of measurement leads to the
use of simulation to further study the behaviour of the Ethernet. It is shown
that, with large numbers of stations, while the throughput of the standard
Ethernet is poor, a simple modification to the retransmission algorithm enables
near-optimal throughput to be achieved. The effects of the number of buffers
and of various distributions of stations are quantified. It is shown that
stations near the ends of the network and isolated stations achieve lower than
average performance.
The second focus of this research is the performance of broadcast bus networks
with integrated voice/data traffic. The networks considered are the
contention-based Ethernet and two contention-free round-robin schemes,
Expressnet and the IEEE 802.4 Token Bus. To accommodate voice traffic on such
networks, a new variable-length voice packetization scheme is proposed which
achieves high efficiency at high loads. While several studies of voice/data
traffic on local area networks have appeared in the literature, the differing
assumptions and performance metrics used render comparisons with one another
difficult. For consistency, a network-independent framework for evaluation of
voice/data networks is formulated. Using simulation, a systematic evaluation
is undertaken to determine the regions of good performance of the networks
under consideration. Interactions between the traffic types and protocol
features are studied. It is shown that the deterministic schemes almost always
perform better than the contention scheme. Two priority mechanisms for
voice/data traffic on round-robin networks are investigated. These are
alternating round mechanism and the token rotation times mechanism which
restricts access rights based on the time taken for a token to make one round.
An important aspect of this work is the accurate characterization of
performance over a wide region of the design space of voice/data networks.
-------------------------------------------------------------------------------
CSL-TR-87-318
CAPACITY ANALYSIS OF MULTIHOP PACKET RADIO NETWORKS UNDER A GENERAL CLASS OF
CHANNEL ACCESS PROTOCOLS AND CAPTURE MODELS
Jose Manuel Rego Lourenco Brazio
March 1987 295 pages.....$17.25
A packet radio network is a collection of geographically distributed packet
radio units communicating over a shared broadcast channel. Usually not all
radio units are within hearing range of each other, and thus multihop operation
is required. These networks represent the natural extension of point-to-point
packet-switched data networks when mobile operation is desired. An important
difference exists, however, with respect to the latter: due to the multiaccess
nature of the radio channel, the success of a packet at a destination depends
on the activity, during the transmission of the packet, of the neighbors of the
destination, and on system parameters such as the type of signaling and
received power levels. The conditions under which a packet is successfully
received in the presence of interfering packets are designated as the {\sl
capture mode.
Due to the existence of multiuser interference, some form of coordination among
the users is required when accessing the channel. This purpose is accomplished
by the {\sl channel access protocol.}
This thesis deals with the problem of the capacity analysis of a multihop
packet radio network; namely, given a network specified by its topology,
traffic pattern, channel access protocol, and capture mode, finding the maximum
feasible link traffics compatible with the given traffic pattern. In this
thesis we start by examining the capture behavior obtained from different
signaling methods, and the question of the feasibility of implementation of
different protocols under different signaling methods. The signaling schemes
that form the basis of the discussion are narrowband and direct-sequence
spread-spectrum. We then formulate a Markovian model that, through the
appropriate setting of its parameters, allows the representation of the capture
behavior of the different signaling methods, and the representation of the
actions of the protocols in a general class that includes some of the main
protocols of interest for packet radio applications. Examples of protocols in
this class are Carrier Sense Multiple Access (CSMA), Busy Tone protocols,
Disciplined-ALOHA, and ALOHA. From this model we derive throughput measures,
and develop algorithms for finding the network capacity under a given traffic
pattern. We then apply the analytical framework developed to the study of the
relative performance of a number of channel access protocols in some simple
topologies, and of the influence on this performance of system parameters such
as the type of signaling, the bit durations and, for spread spectrum systems,
the type of code assignment.
-------------------------------------------------------------------------------
CSL-TR-87-319
THROUGHPUT PERFORMANCE OF SPREAD SPECTRUM MULTIPLE ACCESS PACKET RADIO
NETWORKS
James Scott Storey
March 1987 219 pages.....$13.35
In this dissertation, an integrated model of an unslotted spread spectrum
multiple access (SSMA) packet radio network is developed. The model combines a
detailed model of the radio channel, accounting for the effect of multi-user
interference, with a network model that traces the evolution of the number of
interfering transmissons and accounts for the half-duplex nature of the radios.
A new analysis of the performance of a Viterbi decoder in a packet radio
environment allows the model to be used for a system with convolutional forward
error correction (FEC) coding. The synchronization process is also analyzed
and incorporated into the integrated model. The model makes use of several
approximations for tractability. A discrete event simulation is used to
validate these approximations.
The integrated model leads to numerical results which show the throughput and
the probability of success for a packet as a function of the channel level and
network level parameters. Specifically, for the radio channel, these parameter
include the modulation format, the received signal power, the spread spectrum
bandwidth expansion, and the presence or absence of FEC coding. Also, the
throughput is found as a function of the synchronization parameters, such as
the detection thresholds and correlation times, for several different
synchronization circuits and preamble structures. At the network level, the
parameters are the traffic rate and the network size. The random access
protocols considered include unslotted ALOHA and channel load sensing, which is
an extension of carrier sensing to an SSMA network.
The results indicate the effects on the throughput of receiver availability,
channel errors, and the synchronization process. For each of these effects,
regions are found where the effect is the primary factor limiting performance.
REsults for the network with a channel load sensing protocol showed little
improvement over the results for the network with the simpler ALOHA protocol.
Results for the FEC coded and uncoded systems are compared, and it is seen that
the systems with FEC coding outperform the uncoded systems. A further finding
is that by using a two stage acquisition circuit, the performance can be very
close to the performance achieved with an ideal synchronization process.
-------------------------------------------------------------------------------
CSL-TR-87-320
PERFORMANCE EVALUATION OF MULTIHOP PACKET RADIO NETWORKS BY SIMULATION
David Hilton Shur
March 1987 218 pages.....$13.40
Packet switched networks provide an efficient and flexible method for
interconnecting geographically distributed users for the purpose of digital
data transmission. In packet radio networks, nodes transmit packets over
multiple-access broadcast radio channels instead of wire, cable or fiber optics
links. If the destination node of a packet is not within the power range of
its source node, intermediate nodes are needed to deliver the packet in a
store-and-forward fashion. Therefore, multihop packet radio networks have both
the multiple-access feature typical of broadcast networks and the
store-and-forward feature of point-to-point networks. Since only under
restrictive assumptions is performance analysis tractable, simulation
techniques must be used.
The basic behavior of various existing channel access schemes, namely, ALOHA,
CSMA, CDMA, and BTMA, and a new scheme referred to as Coded Activity Signalling
Multiple Access (CASMA) is investigated. In networks with a regular structure
and balanced traffic flow, the effects of transmission scheduling rate, the
ratio of propagation delay to packet transmission time, store-and-forward
buffer size, and to some extent network access flow control on throughput and
delay performance are examined. We show that contrary to the case of
single-hop, fully connected networks, the performance of CSMA is not only
substantially degraded due to hidden nodes, but it is also affected to a much
lesser extent by propagation delay. BTMA and CASMA on the other hand are
observed to achieve a relatively high capacity, and to be more sensitive to
propagation delay. The performance of a number of variants of a well known
buffer management scheme, the Structured Buffer Pool (SBP) is also studied.
The effect of the number of buffers per repeater differs according to the
channel access scheme employed. The performance of ALOHA and CSMA is not very
sensitive to the buffer size, while BTMA and CASMA exhibit up to a 50\%
degradation in capacity in certain examples. In more general networks, we show
that the CSMA access scheme may exhibit a high degree of variance in the
achievable capacity among different PRUs and links, as compared with the other
access schemes. Simple sub-optimal transmission scheduling algorithms are
introduced to treat the problem of large-scale realistic networks, and are
shown to perform well in a `real-world' example.
-------------------------------------------------------------------------------
CSL-TR-87-321
CONCURRENT COMMUNICATION AMONG MULTI-TRANSCEIVER STATIONS OVER
SHARED MEDIA
Yitzhak Birk
March 1987 222 pages.....$13.60
Presently, most local-area networks employ a single broadcast bus to
interconnect single-transceiver stations. In order to increase a network's
throughput beyond a single bus's data rate without using dedicated switching
nodes, multiple buses and multi-transceiver stations are required. We explore
the design space of single-hop interconnections among such stations; i.e.,
interconnections that provide a passive transmission path between any two
stations. For example, we present interconnections whose throughput can grow
{\sl quadratically} with the number of transmitters and receivers per station.
They consist of a collection of buses, each of which interconnects only a
proper subset of the stations using one of their transceivers. Yet, for any two
stations, there is at least one bus to which they are both connected. We refer
to these as selective-broadcast interconnections, or \sbis's. The use of
unidirectional media significantly enriches the design space of \sbis's since,
unlike with bidirectional media, the sets of receivers that hear two
transmissions need not be identical or disjoint. A graph-theoretic criterion
for determining whether or not transmissions over a specified pair of paths
would interfere with each other is established. It is then used in studying the
performance of various \sbis's. Implementation-related issues, such as power
budget in fiber optic implementations, are discussed in the context of
local-area networks. Lastly, the concept of \sbis's is shown to also apply to
memory-processor interconnection, as well as to additional domains.
A spread-spectrum channel can accommodate several concurrent successful
transmissions, and a single-transceiver node can thus utilize only a small
fraction of the channel's capacity. In order to allocate the appropriate
fraction of capacity to a ``busy'' node, we propose to equip it with several
transmitters and receivers, thereby turning it into a ``supernode''. Several
architectures and operation policies for supernodes are suggested and compared;
it is shown that a supernode can significantly outperform a collection of
independent conventional nodes with the same total numbers of transmitters and
receivers. Packet-radio networks with half-duplex nodes, as well as networks
with full-duplex nodes, are considered.
-------------------------------------------------------------------------------
CSL-TR-87-322
CHANNEL ACCESS SCHEMES AND FIBER OPTIC CONFIGURATIONS FOR INTEGRATED-
SERVICES LOCAL AREA NETWORKS
M. Mehdi Nassehi
March 1987 165 pages.....$10.75
Local Area Networks have been in common use for data communications for several
years and have enjoyed great success. More recently, there has been a growing
interest in using a single network to support many applications (e.g., speech,
high-resolution graphics, facsimile, video, etc.) in addition to traditional
data traffic. This leads to so-called Integrated Services Local Area Networks.
These additional applications introduce new requirements in terms of volume of
traffic and real-time delivery of data which are not met by existing networks.
To satisfy these requirements, one needs a high-bandwidth transmission medium,
such as fiber optics, and a distributed channel access scheme for the efficient
sharing of the bandwidth among the various applications.
As far as the throughput-delay requirements of the various applications are
concerned, a network structure along with a distributed channel access scheme
are proposed which incorporate appropriate scheduling policies for the
transmission of outstanding messages on the network. The proposed solution is
developed in two steps. First, considering each message to be assigned a
delay-cost function based on the application to which it belongs, and assuming
perfect knowledge of all outstanding messages, a dynamic scheduling policy is
devised which outperforms all existing policies in terms of minimizing the
expected cost per message. Secondly, as required for the distributed
implementation of the scheduling policy, a broadcast mechanism is devised for
the efficient dissemination of all relevant information. The broadcast
mechanism is based on unidirectional network structures which provide ordering
among the stations.
As far as the high-bandwidth transmission medium is concerned, fiber optic
technology is considered in this work. The physical ordering among stations
which is required by the above access scheme may be achieved either by an
active configuration, such as a ring, or by a passive configuration, such as
unidirectional bus. In rings, the use of fiber optics does not introduce any
new technical problems, since there exist only point-to-point links between
neighboring stations. However, in the multi-tapped linear bus, the reciprocity
and excess loss of optical couplers along with the low impedance of optical
detectors severely limit the number of stations that can be accommodated. A
number of alternative passive configurations are proposed which overcome this
limitation. Also presented is a unified method for selecting coupler
coefficients to minimize the maximum path loss. This method is used to compute
the maximum number of stations that a configuration can support.
-------------------------------------------------------------------------------
Publications
COMPUTER SYSTEMS LABORATORY
Stanford University
Stanford, CA 94305
415-723-1430
(Hours: M-Th, 8-1)
ORDER FORM
To Order Reports: Print or type your name and address in the space provided.
Check or circle the report(s) you wish to purchase, whether hardcopy or
microfiche. All orders must be PREPAID. CALIFORNIA RESIDENTS must add sales
tax of their local county. Return this order form with your check or money
order made payable to Stanford University. FOREIGN ORDERS must be paid with an
international money order or a check drawn on a U.S. bank, payable in dollars.
Please type or print your name and complete address:
______________________________________________
______________________________________________
______________________________________________
______________________________________________
______________________________________________
______________________________________________
Report # Hardcopy Microfiche Report # Hardcopy Microfiche
-------- -------- ---------- -------- -------- ----------
TR 313 $3.25 $2.00 TR 318 $17.25 $3.00
TR 314 $3.40 $2.00 TR 319 $13.35 $3.00
TR 315 $16.10 $3.00 TR 320 $13.40 $3.00
TR 316 $14.90 $3.00 TR 321 $13.60 $3.00
TR 317 $13.30 $3.00 TR 322 $10.75 $3.00
Subtotal __________
Your Local County CA tax __________
Total __________
-------