This dissertation examines the solutions, based on software, adaptive backoff algorithms, to two computer network problems and a shared-memory multiprocessor problem. For each problem we define a cost metric against which we adjust the adaptive backoff algorithm. This dissertation's unifying theme is that, when possible, backoff algorithms should tune themselves to their environment. The algorithms that we propose are software remedies to hardware shortcomings; they do not require changes to the hardware, however warranted these changes might be, but they may require that we periodically measure certain expected values or probability distributions.
We devote the majority of this dissertation to studying buffer overflow as it occurs during reliable, local area network, multicast. We develop a multiple round, soft real-time algorithm that trades latency for computational overhead: an n-round multicast is slower but suffers less computational overhead than an (n+1)-round multicast. Our prototype system measures the buffer service time distribution and employs it to calculate the algorithm's retransmission timeouts. We develop a preemptive, limited buffer queueing model that accurately models an operating system's communication protocol processes.
We study a memory contention problem that occurs during synchronization of bus-oriented, shared-memory multiprocessors with snoopy, invalidation-based caches. The connection occurs when such multiprocessors cache lock variables, lack advanced synchronization instructions, and synchronize with a test-and-set instruction embedded in a busy waiting loop. This type of synchronization structure has been dubbed a spin-lock. When a spin-lock is released, the cache invalidation signal can cause a burst of memory activity that we call an invalidation storm. Remedies for invalidation storms can waste memory cycles. Our spin-lock backoff algorithm wastes twenty to fifty percent fewer cycles than a recently proposed algorithm.
We consider how to calculate remote procedure call retransmission timeouts on lossy networks and on tariff-bearing networks with selectable grades of service. We develop an expression to calculate the optimal retransmission timeout and network service grade that minimizes a cost function composed of computational overhead, round trip service time, and network tariffs.
Title
Optimally Selecting the Parameters of Adaptive Backoff Algorithms for Computer Networks and Multiprocessors
Published
1989-12-01
Full Collection Name
Electrical Engineering & Computer Sciences Technical Reports
Other Identifiers
CSD-89-542
Type
Text
Extent
90 p
Archive
The Engineering Library
Usage Statement
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).