A retransmission Protocol for a broadcast connection (point-to-multipoint) is proposed and its performance characteristics are considered. The protocol is designed for transfers of large files Over a satellite channel that is time-shared to carry both the data from the broadcasting transmitter and the set of acknowledgments from the multiple receiver sites. A mathematical model of the transmission system that includes separate error processes for uplink and downlink errors on data transmissions, and similar processes for errors on the acknowledgment frames as well, is used to analyze the performance of the scheme. Exact analytical expressions for the relative throughput of the channel are obtained for two special cases: 1) the uplink is error-free; and 2) the acknowledgments are error-free. For the general case, upper and lower bounds are derived and are shown to be virtually indistinguishable for many practical sets of system parameters. The results demonstrate that the broadcasting of large files to multiple receivers can be done both efficiently and reliably.

The design of selective-repeat retransmission protocols to provide reliable transfer of large data files is discussed. The transmission system is assumed capable of losing, distorting, or reordering the transmitted data frames and acknowledgment frames. The principle design considerations center on methods for managing the finite sequence number space and methods for managing the finite-sized receiver buffer. Under the assumption that there exists a maximum time from transmission of a frame to receipt of an acknowledgment for that frame, methods are described for safe reuse of frame sequence numbers. Previous results by Metzner and Morgan on buffer overflow control are extended to cover non-FIFO transmission systems. A two-dimensional space of design parameters is explored by way of Monte Carlo simulations. For appropriate designs, it is shown that significant increases in throughput over that achieved by the Go-Back-Nprotocol are possible on high-rate long-delay channels.

In this note, an efficient method for weighted sampling of K objects without replacement from a population of n objects is proposed. The method requires $O(K\log n)$ additions and comparisons, and $O(K)$ multiplications and random number generations while the method proposed by Fagin and Price requires $O(Kn)$ additions and comparisons, and $O(K)$ divisions and random number generations.

The batch throughput efficiency is studied for three variants on selective reject protocols that operate in a full duplex asynchronous response mode and that adhere to the common architectural features of ADCCP, HDLC, and SDLC. In these architectures, the receiver of information frames may use the REJ supervisory frame to request the sender of information frames to back up to an earlier point in the send sequence. Alternatively, the receiver of information frames may issue the SREJ supervisory frame, which requests resending of a single previous information frame followed by continuation of the ongoing send sequence. The first protocol discussed here uses SREJ as the principle method for recovering lost frames but reverts to REJ recovery if certain combinations of errors occur. The second protocol uses SREJ as the only means for recovery. The third protocol uses SREJ for "isolated" frame losses; if a second frame loss occurs within a specified time after the first, then recovery of the first loss is done by REJ. Results plotted for transmission via satellite at 1.544 Mbits/s show that the selective reject protocols permitted by the current versions of ADCCP, HDLC, and SDLC outperform the simpler REJ protocol only for bit error rates in a narrow range. Thus, it may be worthwhile to consider modifications to these architectures that will permit more flexible selective reject protocols.

In paged storage systems, page replacement policies generally depend on a use bit for each page frame. The use bit is automatically turned on when the resident page is referenced. Typically, a page is considered eligible for replacement if its use bit has been scanned and found to be off on µ consecutive occasions, where µ is a parameter of the algorithm. This investigation focuses on the dependence of the number of bit-scanning operations on the value of µ and on properties of the string of page references. The number of such operations is a measure of the system overhead incurred while making replacement decisions. In particular, for several algorithms, the number of scans per reference is shown to be approximately proportional to µ However, empirical results from single-program traces show that the value of µ has little effect on the miss ratio. Although the miss ratios for the bit-scanning algorithms are close to those of least recently used (LRU), it is pointed out that increasing the value of µ need not bring the bit-scanning policies closer to LRU management.

Cold-start miss ratios are miss ratios that are measured with an initially empty first-level store. The values obtained depend on C, the first-level storage capacity, and on T, the number of references. These miss ratios, measured for various values of T, are useful in evaluating the effect of task switching on cache miss ratios when the cache capacity is C. For a particular (C, T) a practical method is described for obtaining the average of the w - T + 1 cold-start miss ratios measured on the substrings of length T of a reference string of length w. The method, which applies to set-associative LRU, can be used to find average cold-start miss ratios for a matrix of (C, T) pairs in one pass. In the general case, the computation time increases approximately logarithmically in the number of (C, T) pairs as the number of pairs is increased.

A theoretical justification is given to the empirical observation that in some computing systems with a paged, 2-level storage hierarchy, long-term miss ratio is roughly independent of page size. Let MISS be the expected working-set miss ratio in the independent reference model, with expected working set size CAP pages. Now form blocks, by combining the B pages with the highest probabilities of reference into one block, the B pages with the next-highest probabilities of reference into a second block, and so on. Let MISS * be the expected working-set miss ratio when all data are moved in blocks and when the expected working set size is again CAP pages, that is, CAP / B = C blocks. It is proved that | MISS — MISS * | < (2/ C ) + (33/ C 2 ). Thus, if the expected working-set size (in blocks) is sufficiently large, then the miss ratios in the blocked and unblocked cases are approximately equal. This result is used to argue the approximate independence of miss ratio on page size in more realistic models of page references.

article Free Access Share on The Effect of a Capacity Constraint on the Minimal Cost of a Partition Authors: C. K. Wong IBM Thomas J. Watson Research Center, P O. Box 218, Yorktown Heights, NY IBM Thomas J. Watson Research Center, P O. Box 218, Yorktown Heights, NYView Profile , M. C. Easton IBM Thomas J. Watson Research Center, P O. Box 218, Yorktown Heights, NY IBM Thomas J. Watson Research Center, P O. Box 218, Yorktown Heights, NYView Profile Authors Info & Claims Journal of the ACMVolume 22Issue 4Oct. 1975 pp 441–449https://doi.org/10.1145/321906.321907Online:01 October 1975Publication History 9citation325DownloadsMetricsTotal Citations9Total Downloads325Last 12 Months7Last 6 weeks0 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