E1AR0002@SMUVM1.BITNET (03/12/86)
Naomi Schulman
Publications
COMPUTER SYSTEMS LABORATORY
STANFORD UNIVERSITY
Stanford, CA 94305
RECENT REPORTS & NOTES
LIST #6
MARCH, 1986
ABSTRACTS
-------------------------------------------------------------------------------
CSL T.R. 85-272
Bibliography of the Computer Systems Laboratory: 1968-1985
Edited by Naomi Schulman
March 1985 52 pages.....$5.00
This report lists, in chronological order, all technical reports and notes
published by the Computer Systems Laboratory (formerly named Digital Systems
Laboratory) of Stanford University, from l968 to date. Information regarding
availability, prices, and alternative sources is included.
-------------------------------------------------------------------------------
CSL T.R. 85-273
Theoretical Results on Distributed Processing with Limited Computing Resources
by Hemant Kanakia and Fouad A. Tobagi
March 1985 43 pages.....$3.55
A task is a set of related operations which can be performed on some input
data. An algorithm is a collection of tasks with an underlying structure
defined in terms of precedence relationships among the tasks. Two models of
processing systems are considered. A distributed processing system consists of
separate processors, each one dedicated to perform a single task, and permits
pipelined processing of consecutive requests, as well as concurrent processing
of tasks for a given request. A centralized processing system consists of a
single processor which performs all the tasks for a given request sequentially,
and services the requests sequentially without pipelining. The performance of
these two systems is compared in terms of average execution times, under the
constraint that the capacity of the processor in the centralized system is
equal to the sum of the capacities of individual processors in the distributed
system.
-------------------------------------------------------------------------------
CSL T.R. 85-274
Conditions for Product Form Solutions in Multihop Packet Radio Network Models
by Jose M. Brazio and Fouad A. Tobagi
April, 1985 35 pages.....$3.25
Consider multihop packet radio networks operating under a general class of
channel access protocols. For the purpose of throughput analysis, analytical
models are considered which describe the joint activity of the transmitters in
the network, under the assumptions of heavy traffic and zero propagation and
processing delays. The problem addressed in this paper is that of finding
conditions for the existence of product form solutions for the steady-state
probabilities of these models. The main result states that a necessary and
sufficient condition for a given network topology, channel access protocol, and
traffic pattern, to lead to a product form solution is that the blocking
between each pair of used links, as specified by the access protocol, be
symmetric. This result assumes Poisson scheduling point processes associated
with the links of the network. The proof is given in two steps: first, for
systems where all packet length distributions are exponential, giving rise to
Markovian processes; and second, for general packet length distributions
(subject to the restriction of possessing a positive density almost
everywhere), giving rise to Generalized Semi-Markov Processes. It is also shown
that a product form solution does not exist whenever any of the scheduling
point processes in the network is not Poisson. In addition, it is proven that
the computation of the normalization factor appearing in the expression of the
product form solution is an NP-hard problem.
-------------------------------------------------------------------------------
CSL T.R. 85-275
Packet Voice on a Local Area Network with Round Robin Service
by Michael Fine and Fouad A. Tobagi
April, 1985 52 pages.....$3.80
In this paper, we propose a combined voice/data protocol suitable for multiple
access broadcast networks that provide round robin service to the stations.
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 one such network proposal --- namely Expressnet --- as
a representative scheme, we examine the characteristics of the service that
voice traffic experiences under the voice/data 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 examine the cost of overloading the network in terms of
the amount of speech discarded.
-------------------------------------------------------------------------------
CSL T.R. 85-276
Fred Terman, The Father of Silicon Valley
by Carolyn E. Tajnai
May 1985 20 pages.....$2.65
Silicon Valley, located on the San Francisco, California, peninsula, radiates
outward from Stanford University. It is contained by the San Francisco Bay on
the east, the Santa Cruz Mountains on the west, and the Coast Range to the
southeast. At the turn of the century, when fruit orchards predominated, the
area was known as the Valley of Heart's Delight. Today, semiconductor chips,
made of silicon, are the principal product of the local high-tech industries.
It has been said that an institution is but the lengthened shadow of one great
man. Inasmuch as Silicon Valley is an institution, Fred Terman was such a man.
-------------------------------------------------------------------------------
CSL T.R. 85-277
Throughput Performance of a Direct Sequence CDMA Packet Radio Network
by J. S. Storey & F. A. Tobagi
June 1985 99 pages.....$5.45
A Code Division Multiple Access (CDMA) spread spectrum pack radio network model
is presented. The topology is single-hop fully connected network with
identical users. The network model allows the performance of the radio links
to be specified in detail. A model of a BPSK Direct Sequence (DS) CDMA radio
channel with convolutional Forward Error Correction (FEC) coding is used. A
refinement of the network model takes into account the restriction that
hald-duplex radios cannot transmit and receive simultaneously. Single hop
throughput and probability of successful first transmission are derived. The
effects on throughput of the received signal strength E /N , the number of
b o
chips per bit N and the number of users M are shown. A channel load sense
access protocol is introduced in which radios are blocked from transmitting
when the channel is heavily loaded. The increase in throughput due to this
protocol is shown for zero and for non-zero propagation delay.
-------------------------------------------------------------------------------
CSL T.R. 85-278
Performance Evaluation of Channel Access Schemes in Multi-Hop Packet Radio
Networks with Regular Structure by Simulation
by F. A. Tobagi and D. H. Shur
June 1985 72 pages.....$4.55
In this report, the performance of various channel access schemes in multi-hop
packet radio networks with a regular structure is studied by means of
simulation. The channel access schemes considered are: ALOHA (pure and
slotted), Carrier Sense Multiple Access (CSMA), Busy Tone Multiple Access
(BTMA), Code Division Multiple Access (CDMA), and a new hypothetical scheme
introduced here for comparison purposes referred to as Coded Activity
Signalling Multiple Access (CASMA). Network throughput and packet delay are
evaluated, as well as the effects on performance of the nodal transmission
scheduling rate, the propagation delay among nodes, and to some extent the
input flow control. In this study, we consider networks in which both the
topology and the traffic pattern are symmetric. This renders all nodes in the
network statistically identical, and thus helps reduce the complexity of the
simulation task considerably without jeopardizing the objective. The
performance of CSMA in such networks is shown to be rather poor as compared
with its performance in fully connected networks, while relatively high
performance is achieved by the CASMA scheme, the various BTMA protocols, as
well as the CDMA scheme, as compared with CSMA and the ALOHA schemes.
-------------------------------------------------------------------------------
CSL T.R. 85-279
Multi-Level Logic Array Synthesis
by Chris Rowen
July 1985 169 pages.....$7.90
Automatic synthesis of VLSI circuits from function descriptions creates the
opportunity for vastly reduced design cost, but presents formidable challenges.
This silicon compilation can be accomplished by a four step translation: 1)
writing the function in terms of available logic components, 2) minimization of
this logic representation, 3) mapping of logic into the target technology's
circuit primitives and 4) selection of a detailed layout configuration.
Multi-level logic and Weinberger arrays serve as ideal partners in synthesis of
large circuit structures. Deeply nested logic expressions can save area,
power, and circuit delay compared to their more common sum-of-products
equivalents, and Weinberger arrays can directly implement the arbitrary
interconnections required by these complex logic functions. The Stanford
Weinberger Array Minimizer and Implementor (SWAMI) system explores two phases
of this compilation with special care, heuristic minimization of multi-level
logic expressions, and gate placement in Weinberger arrays. SWAMI's logical
optimization phase adopts heuristic methods to reduce the circuit area and
delay for each logic function. Three transformations, decomposition,
composition and local rewriting, change the depth of the logic representation
and capitalize on commonly used subexpressions. The topological optimization
phase presents new algorithms for linear ordering placement in one-dimensional
Weinberger arrays, and introduces a new topology for two-dimensional logic
arrays. SWAMI tunes nMOS and CMOS layouts for area and performance according
to designer specifications, and produces VLSI logic blocks that are often
smaller or faster that equivalent PLA-based implementations.
-------------------------------------------------------------------------------
CSL T.R. 85-280
Host Groups: A Multicast Extension for Datagram Internetworks
by D.R. Cheriton & S.E. Deering
July 1985 8 pages.....$2.50
The extensive use of local networks is beginning to drive requirements for
internetwork facilities that connect these local networks. In particular, the
availability of multicast addressing in many local networks and its use by
sophisticated distributed applications motivates providing multicast across
internetworks.
In this paper, we propose a model of service for multicast in an internetwork,
describe how this service can be used, and describe aspects of its
implementation including how it would fit into one existing internetwork
architecture, namely the US DoD internet Architecture.
-------------------------------------------------------------------------------
CSL T.R. 85-281
Prolog Memory-Referencing Behavior
by Evan Tick
September 1985
This report describes Prolog data and instruction memory-referencing
characteristics. Prolog exhibits unconventional referencing behavior of
backtracking; the saving and subsequent restoration of a program state.
Backtracking introduces memory bandwidth requirements above those of procedural
languages. The significance of this and other characteristics was measured by
emulating a Prolog architecture running three benchmark programs and simulating
various memory models. The results indicate that so-called determinate
programs require substantial memory bandwidth because of a limited form of
backtracking (shallow). However, this referencing behavior exhibits spatial
locality enabling small memory buffers to reduce the bandwidth requirement. A
modification to the Prolog architecture having the advantage of further
increasing locality is described.
-------------------------------------------------------------------------------
CSL T.R. 85-282
Partitioning of Function in a Distributed Graphics System
by William I. Nowicki
March 1985
Although recent advances in graphics workstations promise much computing power
for the future needs of researchers, traditional approaches to software
organization waste much of this power. Most systems treat the workstation as
either a fixed-function terminal or a self-contained personal computer; these
roles have limitations that can be overcome by considering the workstation a
multi-function component of a distributed system. Traditional standard
graphics packages and object-oriented window systems offer important
functionality, but a third approach, virtual terminal management systems, is
more appropriate for a distributed operating system.
The Stanford Distributed Systems Group has implemented such a distributed
system for graphics workstations, organized as a collection of servers
providing services to clients. Major issues are how to partition functions
between the server and its clients, and physically partition the server. In
particular, the service that displays graphical objects is called the Virtual
Graphics Terminal Service (VGTS). The VGTS architecture is described, as well
as a prototype implementation.
This thesis discusses the trade-offs involved in partitioning of function in a
distributed graphics system. Performance is one important property traded for
advanced functionality or decreased cost. To provide adequate performance in a
distributed system, communication costs should be kept low, as well as the
frequency of the communication. By providing modeling as well as viewing
facilities, the VGTS reduces the communication required between applications
and the service.
Measurements verify that performance is insensitive to network bandwidth, but
depends heavily on CPU speed and protocol characteristics. Using structure
provides important speed improvements in some cases, but other basic factors
such as inner loop optimization and proper batching of requests make even
larger differences.
Finally, conclusions are drawn regarding the partitioning approaches taken in
the VGTS. The VGTS is suitable for a large class of applications that perform
graphics as an aid to user interface, and is portable to a wide range of
powerful workstations. Moreover, the VGTS can be used as a basis for further
research on many open questions in distributed systems.
-------------------------------------------------------------------------------
Publications
COMPUTER SYSTEMS LABORATORY
Stanford University
Stanford, CA 94305
ORDER FORM
To Order Reports: Print or type your name and address in the space provided.
If your address differs from our mailing label, please indicate that it is new
or corrected.
Check the report(s) you wish to purchase, whether hardcopy or microfiche. All
orders must be PREPAID. California residents must add 7% sales tax. 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 payable in dollars through a U.S. bank.
Please type or print your name and complete address:
Report # Hardcopy Microfiche Report # Hardcopy Microfiche
T.R. 272 $5.00 $2.00 T.R. 277 $5.45 $3.00
T.R. 273 $3.55 $2.00 T.R. 278 $4.55 $2.00
T.R. 274 $3.25 $2.00 T.R. 279 $7.90 $3.00
T.R. 275 $3.30 $2.00 T.R. 280 $2.50 $2.00
T.R. 276 $2.65 $2.00 T.R. 281 $4.10 $2.00
Subtotal
CA 7% Tax
Total
-------