Peter B. Danzig

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-89-542
December 1989

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/CSD-89-542.pdf

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.

Advisor: Domenico Ferrari

BibTeX citation:

@phdthesis{Danzig:CSD-89-542,
    Author = {Danzig, Peter B.},
    Title = {Optimally Selecting the Parameters of Adaptive Backoff Algorithms for Computer Networks and Multiprocessors},
    School = {EECS Department, University of California, Berkeley},
    Year = {1989},
    Month = {Dec},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/5312.html},
    Number = {UCB/CSD-89-542},
    Abstract = {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. <p>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. <p>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. <p>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.}
}

EndNote citation:

%0 Thesis
%A Danzig, Peter B.
%T Optimally Selecting the Parameters of Adaptive Backoff Algorithms for Computer Networks and Multiprocessors
%I EECS Department, University of California, Berkeley
%D 1989
%@ UCB/CSD-89-542
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/5312.html
%F Danzig:CSD-89-542