We discuss gateway queueing algorithms and their role in controlling congestion in datagram networks. A fair queueing algorithm, based on an earlier suggestion by Nagle, is proposed. Analysis and simulations are used to compare this algorithm to other congestion control schemes. We find that fair queueing provides several important advantages over the usual first-come-first-serve queueing algorithm: fair allocation of bandwidth, lower delay for sources using less than their full share of bandwidth, and protection from ill-behaved sources.

In recent years, a wide variety of mobile computing devices has emerged, including portables, palmtops, and personal digital assistants. Providing adequate network connectivity for these devices will require a new generation of wireless LAN technology. In this paper we study media access protocols for a single channel wireless LAN being developed at Xerox Corporation's Palo Alto Research Center. We start with the MACA media access protocol first proposed by Karn [9] and later refined by Biba [3] which uses an RTS-CTS-DATA packet exchange and binary exponential back-off. Using packet-level simulations, we examine various performance and design issues in such protocols. Our analysis leads to a new protocol, MACAW, which uses an RTS-CTS-DS-DATA-ACK message exchange and includes a significantly different backoff algorithm.

We discuss gateway queueing algorithms and their role in controlling congestion in datagram networks. A fair queueing algorithm, based on an earlier suggestion by Nagle, is proposed. Analysis and simulations are used to compare this algorithm to other congestion control schemes. We find that fair queueing provides several important advantages over the usual first-come-first-serve queueing algorithm: fair allocation of bandwidth, lower delay for sources using less than their full share of bandwidth, and protection from ill-behaved sources.

Article Free Access Share on Epidemic algorithms for replicated database maintenance Authors: Alan Demers Xerox Palo Alto Research Center Xerox Palo Alto Research CenterView Profile , Dan Greene Xerox Palo Alto Research Center Xerox Palo Alto Research CenterView Profile , Carl Hauser Xerox Palo Alto Research Center Xerox Palo Alto Research CenterView Profile , Wes Irish Xerox Palo Alto Research Center Xerox Palo Alto Research CenterView Profile , John Larson Xerox Palo Alto Research Center Xerox Palo Alto Research CenterView Profile , Scott Shenker Xerox Palo Alto Research Center Xerox Palo Alto Research CenterView Profile , Howard Sturgis Xerox Palo Alto Research Center Xerox Palo Alto Research CenterView Profile , Dan Swinehart Xerox Palo Alto Research Center Xerox Palo Alto Research CenterView Profile , Doug Terry Xerox Palo Alto Research Center Xerox Palo Alto Research CenterView Profile Authors Info & Claims PODC '87: Proceedings of the sixth annual ACM Symposium on Principles of distributed computingDecember 1987 Pages 1–12https://doi.org/10.1145/41840.41841Online:01 December 1987Publication History 1,040citation6,731DownloadsMetricsTotal Citations1,040Total Downloads6,731Last 12 Months479Last 6 weeks90 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The energy usage of computer systems is becoming an important consideration, especially for battery-operated systems. Various methods for reducing energy consumption have been investigated, both at the circuit level and at the operating systems level. In this paper, we propose a simple model of job scheduling aimed at capturing some key aspects of energy minimization. In this model, each job is to be executed between its arrival time and deadline by a single processor with variable speed, under the assumption that energy usage per unit time, P, is a convex function, of the processor speed s. We give an off-line algorithm that computes, for any set of jobs, a minimum-energy schedule. We then consider some on-line algorithms and their competitive performance for the power function P(s)=s/sup p/ where p/spl ges/2. It is shown that one natural heuristic, called the Average Rate heuristic, uses at most a constant times the minimum energy required. The analysis involves bounding the largest eigenvalue in matrices of a special type.

In recent years, a wide variety of mobile computing devices has emerged, including portables, palmtops, and personal digital assistants. Providing adequate network connectivity for these devices will require a new generation of wireless LAN technology. In this paper we study media access protocols for a single channel wireless LAN being developed at Xerox Corporation's Palo Alto Research Center. We start with the MACA media access protocol first proposed by Karn [9] and later refined by Biba [3] which uses an RTS-CTS-DATA packet exchange and binary exponential back-off. Using packet-level simulations, we examine various performance and design issues in such protocols. Our analysis leads to a new protocol, MACAW, which uses an RTS-CTS-DS-DATA-ACK message exchange and includes a significantly different backoff algorithm.

The following abstract problem models several practical problems in computer science and operations research: given a list L of real numbers between 0 and l, place the elements of L into a minimum number $L^ * $ of “bins” so that no bin contains numbers whose sum exceeds l. Motivated by the likelihood that an excessive amount of computation will be required by any algorithm which actually determines an optimal placement, we examine the performance of a number of simple algorithms which obtain “good” placements. The first-fit algorithm places each number, in succession, into the first bin in which it fits. The best-fit algorithm places each number, in succession, into the most nearly full bin in which it fits. We show that neither the first-fit nor the best-fit algorithm will ever use more than $\frac{17}{10}L^ * + 2$ bins. Furthermore, we outline a proof that, if L is in decreasing order, then neither algorithm will use more than $\frac{11}{9} L^ * + 4$ bins. Examples are given to show that both upper bounds are essentially the best possible. Similar results are obtained when the list L contains no numbers larger than $\alpha < 1$.

article Free Access Share on Managing update conflicts in Bayou, a weakly connected replicated storage system Authors: D. B. Terry Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile , M. M. Theimer Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile , Karin Petersen Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile , A. J. Demers Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile , M. J. Spreitzer Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile , C. H. Hauser Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile Authors Info & Claims ACM SIGOPS Operating Systems ReviewVolume 29Issue 5Dec. 3, 1995 pp 172–182https://doi.org/10.1145/224057.224070Online:03 December 1995Publication History 630citation5,089DownloadsMetricsTotal Citations630Total Downloads5,089Last 12 Months311Last 6 weeks48 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Flexible update propagation for weakly consistent replication Authors: Karin Petersen Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile , Mike J. Spreitzer Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile , Douglas B. Terry Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile , Marvin M. Theimer Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile , Alan J. Demers Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California and Oracle Corporation, 500 Oracle Way, Redwood Shores, CA Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California and Oracle Corporation, 500 Oracle Way, Redwood Shores, CAView Profile Authors Info & Claims SOSP '97: Proceedings of the sixteenth ACM symposium on Operating systems principlesOctober 1997 Pages 288–301https://doi.org/10.1145/268998.266711Online:01 October 1997Publication History 334citation2,454DownloadsMetricsTotal Citations334Total Downloads2,454Last 12 Months41Last 6 weeks11 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF