August 1970
ADVANCED RESEARCH PROJECTS AGENCY
SEMIANNUAL TECHNICAL REPORT
G. Estrin L. Kleinrock M. Melkanoff R. R. Muntz
Reproduced by the
CLEARINGHOUSE
for Federal Scientific & Technical Information Springfield Va. 22151
D D C
EDM2I
SEP 10 1970
Et5ED OIL
BEST
AVAILABLE COPY
ADVANCED RESEARCH PROJECTS AGENCY
SEMIANNUAL TECHNICAL REPORT August 15, 1970
COMPUTER NETWORK RESEARCH DAHC-15-69-C-0285
Ccmputer Science Department School of Engineering and Applied Science university of California, Los Angeles
Principal Investigator: Leonard Kleinrock
Co-Principal Investigators: Gerald Estrin
Michel Melkanoff Richard R. Muntz
UNCLASSIFIED
ADVANCED RESEARCH PROJECTS AGENCY SEMIANNUAL TECHNICAL REPORT August 15, 1970
Project Computer Network Research ARPA Order Number 1380 Contract Number DAHC-15-69-C-0285
Effective Date of Contract Vl/69 Contract Expiration Date 10/31/70
Amount of Contract $873,109* _
Contractor: School of Engineering and Applied Science Computer Science Department 405 Hilgard Avenue University of California Los Angeles, California 90024
Project Scientist and Principal Investigator Dr. Leonard Klelnrock _
Phone (213) 825-2543 _
"Since this contract has had a number of amendments since its initial acceptance, we list below the pertinent chronology:^
Date Funds Requested Period Covered
Amount
Status
November 1968 November 1968 August 19G9 August 1969 December 1969 December 1969
Vl/69-10/31/69 $229,300 11/1/69-10/31/70 $344,1 *113 Vl/69-10/31/70 $ 69,396 11/1/70-6/30/71 $243,3^5 12/1/69-6/30/70 $230,000 7/1/70-6/30/71 $300,000
Approved
it
11
In process Approved In process
TABLE OP CONTENTS
Section Page
1. INTRODUCTION . 1
2. MATHEMATICAL MODELLING AND ANALYSIS
OF COMPUTER SYSTEMS . 2
3. NETWORK MEASUREMENTS . 8
4. NETWORK AND SYSTEMS SOFTWARE . 17
5. CONCLUSIONS AND SELF-EVALUATION . 20
REFERENCES . . . . 21
APPENDICES . 24
APPENDIX A
Swap-Time Considerations In Time-Shared Systems, by Leonard Kleinrock . 25
APPENDIX B
A Continuum of Time-Sharing Scheduling Algorithms, by Leonard Kleinrock . 33
APPENDIX C
Multilevel Processor-Sharing Queueing Models for Time-Shared Systems,
by L. Kleinrock and R. R. Muntz . 40
APPENDIX D
Buffer Behavior for Batch Poisson Arrivals and Single Constant Output, by Wesley W. Chu 49
ii
APPENDIX E
Selection of Optimal Transmission Rate for Statistical Multiplexors, by Wesley W. Chu .... .
APPENDIX P
Ccnputer Network Studies, by Gary Fultz . . . .
APPENDIX G
Dynamic Storage Allocation for Binary Search Trees in a Two-Level Memory, by Richard Muntz and Robert Uzgalis .
ADVANCED RESEARCH PROJECTS AGENCY SEMIANNUAL TECHNICAL REPORT August 15, 1970
'T/IE (LEEotfT
tfale -projeot- is to create an environment suitable for high quality computer research activities in the understanding and in the development of methods for information processing. One principle area of activity is in the mathematical modelling of computer systems. This includes modelling time-shared systems, memory hierarchical systems, and the ARPA experimental computer network. Another principle area is our network measurement procedures which we Intend to use in studying the net¬ work behavior as well as for evaluating the validity of our modelling and analytical work. Lastly, we are responsible for establishing a suitable HOST-HOST software protocol for use in the network/^
Progress toward the goals listed above has progressed well since the initiation of this contract. Seme of our earlier work was reported upon in our Semiannual Technical Reported dated February 15, 1970. References [1] through [6] listed at the end of this Technical Report include work which took place prior to the current reporting period.
In the following three sections we report upon the progress which has taken place in this current reporting period. Section 2 describes sane of the mathematical modelling and analytical work for computer systems which we have developed. The ARPA research group at UCLA has established itself
lx INTRODUCTION ^The goal of
1
mm WHWfflUH
as perhaps the strongest analytical group for ccrputer systems modelling in the country. In Section 2.1 we describe our work in the analysis of time-shared ccrputer systems. In Section 2.2 we give results for ccnputer- cannunication network investigations. Finally, in Section 2.3 we describe a recent paper on storage allocation in hierarchical memories. Section 3 is a report on our measurement activity in the AKPA Network. Progress here has been strong but it is not as yet highly visible outside of UCLA.
In the next six months we intend to carry out elaborate measurement experi¬ ments which will involve interaction with other nodes in the network and will permit measurement work to take place at remote locations with the aid of the UCLA system. Section 4 describes progress in the area of software; in particular, progress on the network protocol and the growth of our time¬ sharing system at UCLA are described. Section 5 offers sane conclusions regarding the impact of the studies reported herein.
2. MATHEMATICAL MODELLING AND ANALYSIS OF COMPUTER SYSTEMS
Oar effort in the modelling of computer systems has applied mainly to the following three areas: time-shared scheduling algorithms ; ccmputer- conmunication networks; and storage allocation in memory liierarchles .
2.1. Time-Shared Systems Analysis
Ibis period has been most profitable in generating new results in the field of time-shared scheduling analysis. A paper entitled "Swap Time Con¬ siderations in Time-Shared Systems" was published by Kleinrock in June 1970 [13]. In this paper a procedure was developed for calculating the average swap time expended on all those customers still remaining in the
2
SIMWiii
time -sharing system for a very general class scheduling algorithms. An interesting set of examples is given in that paper to which this result is applied and which permit one to gain considerable insight into the operation of these example algorithms. For further details, see a copy of the paper given in Appendix A.
In the 1970 Spring Joint Computer Conference, Kleinrock gave a paper
j 4 r • • • '
entitled "A Continuum of Time-Sharing Scheduling Algorithms” [9]. This work reports upon a new class of scheduling algorithms which, on the one hand permits a continuum of algorithms to be defined which range smoothly from batch processing ( f irs t-c cme-f irs t-served ) to the well-known round- robin scheduling algorithm, and on the other hand permit this entire class of algorithms to be implemented in a surprisingly easy fashion. The prin¬ ciple result in this paper shows that for the entire range of scheduling algorithms analyzed, the average response time conditioned on a service time of t seconds is equal to a constant plus a linear function of t. Furthermore, all of these algorithms yield the same value of response time when the service time equals the average service time. This paper is repro¬ duced as Appendix B.
Carl Hsu, a graduate student working under contract, has made progress in extending the work reported upon in Ref. [9]. In particular, he has successfully obtained the Laplace transform for the waiting time distribu¬ tion for the continuum of scheduling algorithms described above. In addi¬ tion, under the supervision of Kleinrock, he is developing extended models which permit the continuum of algorithms to range beyond the round-robin case all the way to the foreground-background case. This will then permit
3
one to implement a class of well-under3tood algorithms which pass from the case of no discrimination on the basis of service time (first-ccme- first-served) through the most cannon scheduling algorithm (round-robin) finally to the most discriminatory algorithm on the basis of service time ( foreground-background ) .
Recently, Kleinrock and Muntz [l1!] have successfully defined an ex¬ tremely broad class of scheduling algorithms which permit the designer a large number of new degrees of freedom. These multilevel queueing disci¬ plines allow different scheduling algorithms to be effective during a Job's progress through the time-shared system based upon the amount of attained service. The results of this work are to be reported upon in Munich, Germany, at the Sixth International Teletraffic Congress, September 1970. The details of that paper are reproduced in Appendix C. In this work, an integral equation was developed which defined the waiting time in the case where round-robin was the discipline used at same internal level within the system. Until recently that Integral equation remained unsolved; however, since publication of this paper, Kleinrock, Muntz, and Rodemich have solved that integral equation for a rather wide class of service time disciplines, and these results are reported upon Ref. [16] (currently in preparation). Moreover, the application of that result in a variety of interesting situ¬ ations is currently being prepared as Ref. [17].
As pointed out many times before by this research group, two outstand¬ ing problems remain unsolved in the area of time-shared scheduling algo¬ rithms. The first is the problem of considering a time-shared system as containing multiple resources for which competition takes place. For
4
BPWHPKP
iwpswii!|
mi
example, the storage capacity, the central processing unit, the input- output devices, and the data channels connecting these devices together and to the users are all resources which undergo competitive demand. It is clear that the single resource analyses (for example, those reported upon above) have reached a point beyond which it is perhaps not profitable to go before we understand considerably more about the multiple resource case. The second outstanding problem is that involving the cost of delay and defining in a careful and meaningful way an appropriate criterion of performance for time-shared systems. Once this is done, then optimization of scheduling algorithms and other resource allocation algorithms can be carried out. Regarding the first of these problems, some progress has been made by our group in the area of analyzing one aspect of user behavior as it affects the system performance. Chu has studied the effect of the bursty nature of user input over character-oriented input-output devices. This work is reported upon in Ref. [18] and forms Appendix D of this report. This problem grows out of studies on the design of statistical multiplexors which are useful in data ccmnunications problems.
2.2. Computer-Ccmnunicatlon Nets
Our effort in the analysis and optimization of ccrnputer-conmunicat ion networks has continued and accelerated since the last reporting period.
In this section we note results which have been obtained in the areas of multiplexing, routing, optimum channel capacity assignment, and certain topological studies.
At the 1969 Pall Joint Computer Conference, Chu presented a paper on "Asynchronous Time Division Multiplexing for Time-Sharing Computer Systems"
5
^0]. More recently, he has continued that study under our support and has published a paper entitled "Selection of Optimal Transmission Rate for Statistical Multiplexors" [12]. In this paper he considers the trade¬ off between the cost of transmission between computers and the cost of duplicating storage files at each. This paper fonns Appendix E.
We have for sane time now been involved with the design of the routing discipline in the ARPA Network and are continuing this interest. The prob¬ lem of stucfying a variety of message routing strategies forces one to create suitable models of the nodes in that network, as well as a means for describ¬ ing the message flow. Gary Fultz, another graduate student, has been ac¬ tively investigating this area, find Appendix F is devoted to his progress in computer network studies. The results so far indicate that the models we have created correspond very well to the simulation results over many operating ranges and operating modes. Jack Ziegler, also a graduate student, is investigating the propagation of nodal storage blocking effects within the network. Some analytical results have been obtained in this area, and he currently is conpleting the details on a digital simulation based upon an epidemiology model of the way in which this blocking phenomenon propa¬ gates through a network.
Our previous Semiannual Technical Report included a copy of Ref. [10] by Kleinrock on "Analytic and Simulation Methods ir. Computer Network Design." That pape:' was presented and published in the 1970 Spring Joint Computer Conference Proceedings.
Recently, Professor Cantor in the Mathematics Department has been con¬ tributing to our network effort at UCLA. His interest lies in network flow
theory and mathematical programming techniques. We have been collaborat¬ ing on seme shortest route algorithms for our ARPA Network simulation pro¬ gram. Recently, he completed a paper on "Non-Blocking Switching Networks" [15] J this work provides tighter upper bounds on the number of switches necessary to connect one set of input lines to a second set of output lines in a non-blocking network. Mario Gerla and Luigi Fratta have recently joined us as graduate students and are currently investigating connectivity, survivability, and optimum topological design for computer networks. This effort is beginning to receive the proper attention that it should at a modelling center such as ours.
2.3. Memory Allocation in Hierarchical Memories
A recent study by Muntz and Uzgalis on "Dynamic Storage Allocation for Binary Search Trees in a Two-Level Memory" is Included as Appendix G in this report (Ref. [18]). This paper presents a remarkably efficient algorithm for placing storage entries into a hierarchical memory in the case where the data set is tree-structured. An analysis has shown that the technique is near optimum.
7
..■>aatetiiy‘..ai ht. ** iw*u> i
i
3. NETWORK MEASUREMENTS
Ihe network measurement activity has consisted of two major efforts,
(1) the development of the network measurement and control programs which handle the measurement data and generate artificial traffic, and
(2) the analytical studies involved with the data analysis and relating the measurements to the network behavior and models of such behavior.
Other efforts have involved our continuing coordination with BBN, and seme initial network experimentation and measurements using artificial traffic. Each of these efforts is discussed in more detail in the follow¬ ing paragraphs.
3.1. The Measurement and Control Program
•*
Hie network measurement and control package was completed during the reporting period and is now operational. This program consists of a set of routines which (1) accept measurement data from the network,
(2) control its processing and print out, (3) handle the initialization, control and termination of tests, and (4) provide a substantial message generation facility to generate artificial traffic. The data handling routine is a FORTRAN program which formats and prints out the measurement statistics generated by the IMP'S. The program uses a number of assembly language subroutines wliich Interface with the system monitor and control the interrupts, the clock and the IMP interface. In addition, the program can generate artificial traffic over a number of links and with a variety of message lengths and frequencies. Ihe individual most active in this area at UCLA has been Gerald Cole, a graduate student on the contract.
8
The measurement program is controlled from the operator's console In a manner similar to that used to set up experiments at the IMP console. For example, the experimenter would type SNAP (Nl) followed by 5 (NL) if he wished to have only every fifth snap-shot data message printed out. He has similar control capabilities for the accumulated statistics and trace data messages, as well as having control over the destination of the data (the line printer or magnetic tape), the source of the data (from the IMP or magnetic tape), and other optional features such as a decimal "dump" printout of the received data.
The message generator portion of the program allows the user to specify which of the 63 possible generators that he wishes to utilize, and to define the destination, the Initial message length, the final message length, the increments for successive runs, the duration of the run in milliseconds, and the number of messages sent on each link. If a non-zero length increment has been specified, the experiment will .terminate after the end message length has been run; but for a zero increment value, it will create continuous traffic until stopped from the operator's console. Statistics on the artificial traffic can also be printed out on the console at the operator's request.
Since the measurement program is of value to a number of experi¬ mental and research efforts, it has been documented in considerable detail, including a well comnented program listing and a user guide
9
which was published as part of the Miscellaneous Network Note series.*
The latter document lists and describes each of the thirty different commands Including a precise format description as well as a descrip¬ tion of what functions each conmand performs.
3.2. Analytical Efforts Related to Measurements
3.2.1. Data Analysis Efforts
Most of the data analysis effort has been devoted to the study of how one interprets data which has been obtained in logarithmic histogram formats, i.e. such as are used to measure packet and short message lengths. The approach has been to consider the logarithmic data as being the re¬ sult of a transformation of variable from the actual variable of interest, x, to a new variable, 5 . Therefore, the desired information (the mo¬ ments and/or density function) have been transformed into functions of the variable 5 # and we must perform the inverse transformation to obtain the desired data. Results were obtained relating the moments of the density f(x) to the moments of the transformed function 4(5) but this relationship had very poor convergence properties, i.e. many higher moments in 5 were required to compute the moments in x. A second rela¬ tionship was subsequently found using central moments which had better convergence properties. The analysis also Included considerations of the grouped data aspects and resulted in the development of new moment cor¬ rection formulas which compensate (on the average) for the fact that the
* Misc. Network Note #9* "Network Measurement Program”, by D. Karas, 30 June 1970
10
data points are not uniformly distributed over a histogram Interval.
A relationship was found which relates the moments of x directly to the log-histogram values, which when combined with the correction formulas, should provide good estimates of the moments from the relatively coarse histogram data.
3.2.2. Relations Between Measurements, Models, and the 1 itual System
An attempt was made to formalize the relationship between the measurements which one takes on a system, the models of the system, and the system itself. Ihe system was considered to be represented by a set of structural relationships and a set of behavioral state variables. Measurements were then classified as being either subsets of the state variables or as a set of functions of present and past state variables, e.g. averages or histograms. Ihe structural aspects are generally implicit in the measurements, e.g. the connectivity of IMP'S as expressed by the modem output destinations.
Models of the system can vary considerably in the degree of detail which they include, and are not necessarily subsets or functions of a subset of the state variables. This difficulty leads us to at least tem¬ porarily abandon this approach as being a viable formalism, and subsequently it has been used merely as a classification vehicle for representing the various measurement techniques.
3.2.3. Control Aspects of Measurements
One of the functions of the measurement activity is to provide
11
mmm
insight into potential network, improvement:., fine-tuning, and perhaps eventually self-adaptive control. This necessary insight is developed by a combination of measuring and modelling efforts; and as an example, we are investigating the effects of varying the priority threshold.
This threshold is presently set at a length of five IMP words, i.e. messages are considered to be of a higher priority if they do not exceed this length. Cox and Smith have considered this problem based on an exponential service time and found the optimal threshold to minimize the average queueing delay.* This work has been extended during the recent weeks to consider hyperexponential service because the user-to- computer and the computer-to-user message lengths have considerably different means, although we have assumed that each can be modelled separately by an exponential service time. More detailed models which consider the truncation effects of packet size segnents are being developed.
3.3. Coordination With BBN
Coordination with BBN on the measurement effort has continued, but at a lesser degree since they have completed their portion of the measure¬ ment package. However, there have been some minor changes in the measure¬ ments such as deleting the ASCII conversion queue lengths from the snap¬ shot formats and improving the resolution of the round-trip and arrival time data. We requested that they change these readings to utilize the 100 usee, clock instead of the 25.6 msec, clock, since the latter was comparable to the times that were being measured.
* Cox, D. R. and W. L. Smith, "Queues”, Methuen's Monographs, 1961.
12
Various UCLA personnel cooperated with BBN in their network tests. Much of the artificial traffic capability discussed in section 3 .1 was originally developed as part of that effort.
3 . 4 . Experlmentat ion
Some experiments have been run to exercise the network and to check¬ out the usage of the measurement routines. Figure 1 is a portion of an accumulated (12-Sec.) statistics printout from one of tliese tests, and shows the traffic that was established on each inter- IMP conmunication line. This particular test utilized several of the measurement messages as artificial traffic to supplement the IMP'S pseudomessage generator.
A snap-shot of the modem queues for a similar situation, but with a different subset of the IMF's is shown in Figure 2, A trace message from a third test is shown in Figure 3# and represents the trace data from a short (priority) message from UCLA to SRI. The message was sent via UCS3 because the channel 1 modem at SRI was looped.
Other tests had been run to lebug our measurement routines and to gain familiarity with interpreting the measurement results, but some of the tests provided some interesting results in themselves. For example, the propagation delay between UCSB and SRI was calculated from trace data and was felt to be too high. We later found that the line between UCSB and SRI was routed via Los Angeles, which explained the slight extra delay.
13
4. channel activity
r
BSMMM
imum
t- U)
oor
CL <D Z O' •-0C Ui
*
V> D
V U CL til
or
v t- u z
< Ui V)
I
V o I > •~o
UI
o o o o
in -4- o <n • in
o
* > u u
r<-UJ
or
«D
> -JK JZ UJ UJ
I w
to
or o
UJ UJ
u >
U_ 03
z> r
00 UJ
or
<VJ
z
z
oo o o
.X
.u
w
*— 4
_l >-
: r~
UJ a.
o «-• in in o vfl oo
In | «-| r I if.
I
I
I
14
1
o
(VI
cu
H
o
CO
co
Ui
r
O
<
-j
o
w
ir
W
O
oc
3
CD
(0
co
u
co
*-«
t-
<
t-
CO
CD
I
CO
0-
<
z
(0
|
V |
; ' |
j |
|
u z |
CO i |
1 1 |
|
Ui |
►- |
1 |
|
a |
CO CD |
o o |
|
w |
X |
i |
|
oc |
a |
■I |
|
u |
i 1 |
|
|
(Vi |
||
|
i — ; |
i |
|
|
z |
»- |
|
|
M a j |
to <D |
o o |
|
a. ! |
X |
i |
|
i i |
cd |
i |
z
Ui
|
O j |
i |
| |
co |
|
Cv |
r |
||
|
1 i r- |
(O CD |
c o |
1 |
|
(VI I |
; x |
i |
i |
|
* 1 |
! cd |
J |
|
|
rt 1 |
i |
a |
|
|
•: ! |
i o |
i |
y L) |
|
» |
»- |
< |
|
|
Ui ! |
(0 |
O O . |
|
|
k~ |
CD |
i |
|
|
< |
X |
; i |
|
|
a ' ; |
CD |
J |
i- o o CO t
S I
CO
CD
I
o o
a
33
z
u
oc
►*
3
a.
»-
3
©
(O
I
I —
a
z
Ui
Ui
o
Ui
3
o
CO
©
X
|
Ui |
|
|
3 |
co |
|
UJ Ui |
X |
|
3 3 |
»- |
|
ui a |
CD |
|
3 |
Z |
|
Q >, l |
Ui |
|
~ a Ui < CD (0 |
_J |
|
< co • |
UI |
|
CO UI |
3 |
|
CO x |
Ui |
|
UI |
3 |
|
z >- »- |
CJ |
|
< oc |
_ J |
|
X o |
UJ |
|
oc *-> |
z |
|
cd or |
z |
|
z a. |
< X u • OJ |
o oo
Oho
•-* o o o
2. , I
oc i
a. i
o o o
0-3-0
„ CD
^ OJ ro <
— i — i _i Ui Ui lii Z Z z z z z < < < XIX u u u
cd
z
3
CD
oc
CO
UI
o
z
CD
<
I
oc
(D
U
Ui
a.
CD
X
z
CD
<
z
o
(Vi
o
(Vi
<D CO
*-< <
CO
UI
a
m x
— 1 *-• CO <
o o: u h-
UI
ci
<
a:
CD
h-
co
OC
Ui
u
u
=>
CQ
- n il- u n
I CO CO CO h cc a a; to UI UI Ui
z u u. u. Ui u u u J D 3 D co cd co
CO O >- li_ — Z< (/) <D JUW
< • UJ kC UJ ©
to OC 2.
< Ui
cc cc • _j
CD 3D CO < t— t— UI i— CO CO Z CD I —
UI u u
U* CD CD CC
U • •
CD CD
z z
CO
z
I
u
cvj
CO
(0
z
X
u
z
CD
U
Ui _J
> z
— I ~J u <
Ui
z
in
4. NETWORK AND SYSTEMS SOFTWARE
This section covers work done in the Spade group during the first half of calendar year 1970. The larger portion of our effort has gone into fixing and extending the SEX* time-sharing system, the remainder of our effort has been on the network. In terms of progress, however, the network effort has been much more visible.
4,1, Network Progress
Following a mandate to change the protocol so that it would per¬ mit access to a Host without logging Into it, the Network Work Group developed the present and more powerful protocol. UCLA has been a major participant in the Network Working Group, with Stt/e Crocker becoming chairman in May. A paper authored by S. Carr, S. Crocker and V. Cerf [11] was presented at the SJCC in May. Network meetings were held on March 17 at UCLA, May 7 in Atlantic City, May 8 at Lincoln Laboratories, June 29 at Harvard and July 1 at UCLA, and Network Work¬ ing Group/Request for Conments numbers 28 through 59 were written and distributed. About a third of these NWG/RFC’s were written at UCLA; eight other sites contributed the remainder.
The outcome of this effort i3 the agreement on a Host-Host proto¬ col, substantial progress in the development of the next layer of pro¬ tocol, and explanation of seme of the very hard problems in using comnlex
*Signa Executive.
17
interactive subsystems over the network. NWG/RPC's 33* 36-40, 44,
46-50, 54, 55* 57—59 relate to Host-Host protocol, NWG/RFC's 42 and 56 cover the next layer, and NWG/RPC's 31 and 51 pertain to higher level languages to deal with complex subsystems.
In addition to the effort on the general Host-Host protocol, we engaged in an experiment with SRI and another with Utah. These exper¬ iments stowed that all of the operating systems contained deficiencies which prohibited convenient network operation. These experiments did not use the Host-Host protocol. These deficiencies were that multiple layers of control character scanning on the FDP-10 prohibited getting necessary control characters, e.g. a carriage return down to the sub¬ system, and on the 940 it was not possible to log-in. Ch our system, it was very painful to operate in character-oriented mode. These systems are all undergoing modification to correct these problems; moreover, the Ho3t-Host protocol provides a general solution to some of the problems.
Finally, during March we provided programming support to the BB&N staff for their network experiments conducted at UCLA. We are also supporting Jerry Cole’s measurement work.
4.2. System Development
The GORDO time- sharing system acquired from LRL at Livermore re¬ quired major modifications and extensions at the beginning of this year; the system has been modified to run on our hardware, and extensions to the system are underway. The important differences between our
18
hardware and Livermore's are disk geometry, consoles and number of register blocks. The extensions to the system which have been com¬ pleted are the inclusion of a background batch processor, the modi¬ fication of the terminal handler to treat a variety of terminals and to provide for both character-oriented and line-oriented canmunication, and the construction of interactive utilities for moving, listing and deleting files and starting, stopping and examining processes. Current facilities also include FORTRAN, an assembler and loader, Meta5, and a very major effort has also been expended on documentation. The status of the system is detailed in notebook form and runs to about 350 pages. Design changes and preliminary specifications of new facilities are documented as Spade Design Notes; Spade Design Notes 5 tlirough 25 appeared in the first half of the year. More formal user documentation manual on Botch, the background batch processor, has been produced.
rIhe changes in the time-sharing system have been extensive enough to merit changing the name. Taking a cue from BB&N which is producing T3JE£, for TEN Executive, our system for the Signa Seven is SEX. The SEX system is currently running 2-6 hours per day and is servicing the Spade group. Full time operation is projected to begin after September 1 and before December 31. implementation of the protocol should be complete by September 5*
5. CONCLUSIONS AND SELF-EVALUATION
We feel that the effort expended in the modelling and analytical area has paid off handsomely and will continue to develop and grow in the dii-ections indicated in this progress report. Our measurement effort has been moving slowly as the network itself has unfolded during these last few months. That effort is now taking a step function increase in activity and extensive tests using artificial traffic are now being implemented.
When real traffic begins to throb in the network, then that measurement activity will shift over and measure the actual traffic conditions. We have put considerable effort into the network and systems software, and progress in that area has been substantial. The network protocol is now moving along very nicely and should peak out semetime within the next six months. The same may be said about our time-sharing system, SEX. The effort has been very large, and we are just now beginning to reap the bene¬ fits of that investment. We hope to be able to shift the enphasis from the hard core programing required of these last two tasks into the modelling and analysis area.
As a result of our efforts, UCLA now has an excellent reputation in the area of modelling and analysis among computer scientists and is an acknowledged and important participant in the ARPA Network community.
20
REFERENCES
1. Kleinrock, L. "Time-Sharing Systems: Analytical Methods," Proc. of the Symposium on Critical Factors In Data Management/1968 , UCtA,
March 20-22, 1968, 1Prentice-Hali, pp. 3-32, 19o9.
2. Martin, D. , and Q. Estrin. "Path Length Computations on Graph Models of Computations," Transactions of the IEEE, Vol. C-18, pp. 530-536,
June 1969.
3. Kleinrock, L. "Models for Computer Networks," Proc. of the IEEE Inter- national Conference on Conmunicationsa Boulder, Colo., pp. 21-16 to 21-29, June 9-il, I9S9.
4. KLeinrock, L. "Ch Swap Time In Time-Shared Systems," Proc. of the JEER Computer Group Conference, Minneapolis, Minn., pp. 37-41, June 1^-19,
T W.
5. Cofftnan, E. G., Jr., and R. R. Muntz. "Model of Pure Time-Sharing Disci¬ plines for Resource Allocation," Proc. of the 24th National Conference of ACM, August 1969.
6. Chu, W. W. "A Study of Asynchronous Time Division Multiplexing for Time-Sharing Computer Systems," 1970 Proc* of the Fall Joint Computer Conference, Las Vegas, Nev., pp. 659-678, November I969.
7. KLeinrock, L. "Comparison of Solution Methods for Computer Network
Models," Proc. of the Computer and Cormunications Conference, Rome, N.Y.. Oct. 2, I9S9: - - -
8. Muntz, R. R. , and R. Uzgalis. "Dynamic Storage Allocation for Binary Search Trees in a Two-Level Memory," Proc. of the Fourth Annual Princeton Conference on Information Sciences and Systems. Princeton.' ll. J. March
2T--277 im - - - * -
9. KLeinrock, L. "A Continuum of Time-Sharing Scheduling Algorithms,"
Proc. of the 1970 Spring Joint Computer Conference, Atlantic City, N.J., pp. 453-45^3, May 1970. K
10. KLeinrock, L. "Analytic and Simulation Methods in Computer Network
Design." Proc. of the 1970 Spring; Joint Computer Conference, Atlantic City, N.J., pp. 569-579, May m -
11. Carr, C. S., S. D. Crocker, and V. G. Cerf, "HOST-HOST Corrmunication Protocol In the ARPA Network," Proc. of the 1970 Spring Joint Computer Conference. Atlantic City, N.J., pp. 569-597, May 1970.
12. Chu, W. W. "Selection of Optical Transmission Rate for Statistical Multiplexors," Proc. of the 19? 0 .TEE International Conference on Com¬ munications, San F'rancisco, C-v . , pp. 28-22 to 28-25, June 8-10,
19V0.
23
13. Kleinrock, L. "Swap Time Considerations In Time-Shared Systems,"
IEEE Transactions on Computers, pp. 53^— 5^0, June 1970.
14. Kleinrock, L., and R. R. Muntz. "Multilevel Processor-Sharing Queue¬ ing Models for Time-Shared Systems," Proc. of the Sixth International Teletraffic Congress , Munich, Germany, pp. 341/1-3^1/8, August 1970.
15. Cantor, D. "Non-Blocking Switching Networks," to appear In J. Networks. Vol. I, Issue 1, 1970.
16. Kleinrock, L., and R. R. Muntz, and E. Rodemlch. "Ihe Processor-Sharing Queueing Model for Time-Shared Systems with Bulk Arrivals," to be published.
17. Kleinrock, L., and R. R. Muntz. "Processor-Sharing Queueing Models of Mixed Scheduling Disciplines," to be published.
18. Chu, W. W. "Buffer Behavior for Batch Poisson Arrivals and Single Constant Output," to be published in TREE Trans, on Communication Technology, October 1970.
Presentations
1. Kleinrock, L. "Analytic Methods and Results for Time-Shared Systems:
A Survey," presented at Princeton University, Princeton, N.J., October 17, 1969.
2. Kleinrock, L. "Mathematical Analysis of Time-Shared Scheduling Algo¬ rithms," presented at Uhiversity of Utah, Salt Lake City, December 5, 1969.
3. Kleinrock, L. "Queueing Theory, Computer Networks, and Time-Shared Systems," presented at Network Analysis Corp., Glen Cove, N.Y., January 21, 1970.
4. Kleinrock, L. "Analytic Models for Computer Systems," presented to the SIAM meeting at The RAT© Corp., Santa Monica, Calif., April 11, 1970.
5. Kleinrock, L. "Measurement and Modelling of the ARPA Computer Network," presented at the Operations Research Society of America Conference, Washington, D.C., April 20, 1970.
6. Kleinrock, L. "Time-Shared Computer Systems Analysis," presented at Brown University, Providence, R.I., May 8, 1970.
7. Kleinrock, L. "Analytic Models for Time-Shared Computer Systems," pre¬ sented at IBM, San Jose, Calif., June 8, 1970.
8. Kleinrock, L. "A Selected Menu of Analytic Results for Time-Shared Computer Systems," to be presented at IEM, Germany, September 18, 1970.
24
1
25
!
APPENDIX A
SWAP-TIME CONSIEERATIGNS IN TIME-SHARED SYSTEMS
by
Leonard Kle inrock
27
IEEE TRANSACTIONS ON COMPUTERS, VOL. C-19, NO. 6, JUNE 1970
normalized queuing delay due to buffering is equal to 1.25 character-service times. Since each service time equals l/p = 1/240 = 4.16 ms, the waiting time of each character is 5.06 ms. Now suppose the number of terminals increases from 48 to 96, so that the traffic intensity is less than unity, two trans¬ mission lines are needed, and the traffic intensity is still equal to 0.6. From Fig. 2, the buffer length corresponding to the desired overflow probability for two transmission lines is about 1 4 characters. The waiting time is about 0.8 character- service times which is equal to 3.33 ms. Although the differ¬ ence between 5.06 and 3.33 ms may not be detected by a user at a terminal, a common buffer of the same size operat¬ ing with two r>utput lines can handle twice the number of input lines as with one output line. Thus, the common buffer approach permits handling a wide range of traffic without substantial variation in buffer size.
Reference;,
[1 ) W. W. Chu, “A study of asynchronous time diviaion multiplexing for time-sharing computer communications/' presented at the 2nd Hawaii Internail. Conf. System Sciences (Honolulu, Hawaii), January 22-24, 1969.
[2] B. A. Powell and B. Avi-Itzhak, "Queuing systems with enforced idle time,” Operations Res., vol. 15, no. 16, pp. 1 145—1 1 56, November 1967.
[3 J T. G. Birdsall, M. P. Ristenbatt, and S. B. Weinstein, "Analysis of asynchronous time multiplexing of speech sources," IRE Trans. Communications Systems, vol. CS-10, pp. 390-397, December 1962.
[4] N. M. Dor, "Guide to the length ofbuffer storage required for random (Poisson) input and constant output rates,” IEEE Trans. Electronic Computers (Short Notes), vol. EC-16, pp. 683-684, October 1967.
[5] J. D. C. Little, “A proof of the queuing formula L*=Xw," Operations Res., vol. 9. pp. 383 -387, 1961.
[6] R. W. Hamming, Numerical Methods for Scientists and Engineers. New York: McGraw-Hill, 1962, pp. 363-364.
[7] P. M. Morse, Queues, Inventories and Maintenance. New York: Wiley, 1958, pp. 15-18.
[8] W. W. Chu, “Optimal file allocation in a multiple computer system,” IEEE Trans. Computers, vol. C-18, pp. 885-889, October 1969.
Swap-Time Considerations in Time-Shared Systems
LEONARD KLEINROCK, member, ieee
Abstract — Solved for is the expected swap time expended tot those customers in the system of queues In general models of time- shared systems. This quantity ia expressed In terms of the expected queueing time conditioned on required service time and is applied to a number of examples of interest.
Index Terms — Modeling and analysis, processor-sharing, queue¬ ing analysis, scheduling, swap time, time-shared.
Introduction1
NUM EROUS authors have addressed themselves .to the problem of solving for the average re¬ sponse time T in tinie-shared computer systems [l]-[lt] and an excellent summary of such investiga¬ tions is available [9 ]. Many of these studies condition T on the required service time (i.c., the required processing time) / which we denote by T{l). Some go further and introduce an external priority system, solving for TP{1) which is the average response. time for a customer from priority group p who requires / seconds of processing time [4 ].
Recently a new quautily, the distribution of attained service time Np(t) was calculated [6] for any priority
Manuscript received A iieusl 14, 1969; revised December 16, 1969. This work was snp|K>i ted by the Advanced Research I’rujccls Agency of lhc Department of Defense under Contracl DAI1C15- 69-C-0285. Reproduction in whole or in part is |>criniUed for any purpose of lhc United Stales f.o\ eminent.
The author is with the School of Kiii’inecrini' and Applied Science, University of California, l.ns Angeles, Calif. 90024.
1 This paper evolved from and is an extension of the paper in (31.
feedback queueing system which satisfies Little’s result (which states that the average number to be found in the system is equal to the average arrival rate of cus¬ tomers times the average time spent in that system). Np(r) is defined as the expectation of the number of customers in the system of queues front priority group p who have so far received exactly r seconds of useful processing. A customer is said to be in the system of queues whenever lie is waiting for his next quantum of service time during his request for t seconds of total service. We assume that on his nt’.i visit to service, a customer from priority group p will receive the atten¬ tion of the processing unit for gp,Q seconds.
Results
In this paper, we are interested in swap-time con¬ siderations. (Swap time is the time spent in removing the old customer from and bringing the new customer into service, as well as any other cost in time directly related to this operation.) Our main result is that a measure of this quantity is simply expressed in terms of Np(r) as follows. We direct our attention to the cus¬ tomers in the system of queues and we inquire as to the expected time S, which lias been expended in swapping for this set of customers. The answer comes directly from Np(r). First we note that all customers front group p who have visited the service facility exactly n times
28
PM
KLE1NR0CK.: SWAI’-TIME CONSIDERATIONS
must so far have received useful processing in an amount equal to
*
f, *= £ (gp<Q - er<) seconds (1)
»-l
where d,„ «= (wasted) swap time used for a customer from group p on his nth visit to service.1 Thus only r„ will appear as a meaningful argument for Np(t). Clearly, then, the expected swap time expended for all customers from group p who are in the system of queues must be
5, - £ 7pnAr,(rn) (2)
»-l
where
yPn = £ «„• (3)
i-1
But from Theorem 1 of [6] we have that
A>„) - x,[l - iJp(rn)][ir,(rM l) - IF,(r„)] (4)
where
X,«= average arrival rate of customers from group
P .
Bp(t) s r. /’(required processing time for customers from pth priority group </), and Wp(t) -expected wait in queues for customers from group p who require a total of t seconds of processing.
Finally, to solve for 5 (the expected swap time expended on all customers in the system of queues) wc have the following.
Theorem 1: For time-shared systems (£>>0)
7p«Xp[l - flp(r„)]
p-i p-i p-i w
•(»'p(r„+.) - H',(rn)]
where
/’ = total number of priority groups.
Observe that S is expressed in terms of known quanti¬ ties (7P„, A,, B„(t„)) and a function Wp(rn) which is the average conditional waiting time; this last measure is the usual one solved for in the analysis of time-shared systems.
Corollary 1 : For 6P„ -0P independent of n,
' r -
S~ £XP0|I| ^2, nbp(rn * i) If ,,(rn (.j)
p 1 L„., (6)
- £[l - /Jp(rn)]lFp(r,)
5 \\c nsMimc llic oliviom condition tli.it for all «.
30
where
frp(rB+i) - Bp(th+i) - Bp(r«)
= P [customer from group p has required service time! such thatTB</<TM.,]
*=P [customer from group p requires exactly n+1 visits to the service facility].
Proof: We have y p„=«0p. Substituting this in (S) and using 1-B,(r„)= [l — 2?p(r„+1) ] ~h [ZJiP(t„i ,) ~Bp(t „)] we get (6),
Corollary 2: For dpn--dp and P = 1 (i.c., no priorities and so we drop the subscript p) we have
5 - \e £ »6(rB+1)JF(rB+1)
W
- \6 £ [1 - B(jn)]lV (r„).
fl — 1
Proof here is immediate from Corollary 1.
We now consider Theorem 1 plus its corollaries for the processor-shared systems [4], These systems fc time-shared systems in which the quantum size Q it allowed to shrink to zero. In this limit for Q— >0, we must obviously contain the swap time dpn in a meaning¬ ful way such that gpnQ>0p„. This we do in the (theo¬ retically) natural way, namely, defining
0pn
Qpn
gpnQ
where we require 0<^pB<l. Thus <f>pn is that fraction of the nth quantum given to a customer from group p which is wasted due to swap time. In the limit as Q— >0, we must then define
4>p(t) “ lim 4>Pn (9)
O-o
where for a given p and t, wc consider an n-n{Q) in¬ creasing as Q decreases such that
n(Q)
t = lim £ (gpiQ - 0P ,) - lim <?—o ,„i O—o
x(0)
£ ip.(?(i
i-l
4>pd- (10)
As discussed in [4], this Q-*0 limit has useful character¬ istics in our analysis of time-shared systems. Developing the analogous equations here, wc have
where
(ID
(12)
Note that yp(r) is the time wasted in providing r seconds of useful service to a customer from group p. But, from Theorem 2 of [6], wc have that
r , d\Vp(r)
Ap(r) = Ap[l -
dr
(13)
where \p, Bp(t), and Wp{t) arc as defined above and Np{t) is now an expected density function.
i
IEEE TRANSACTIONS ON COMPUTERS, JUNE 1970
We tli us have 5 for this case as follows.
Theorem 2: For processor-shared systems (Q— >0)
the discrete round robin infinite-input population sys¬ tem [5 ] where
s - £s, - £ /%,«»,[! - 2,M] ■ (—)*■
This last may be interpreted as a Stieltjcs integral in the case that Wp(t) is discontinuous.
Corollary 1: For <I>p(t)—<I>p independent of r, wc have
p c * / d\V (V' \
5 = 23Mp Jo r[l - 5p(r)] (15)
Proof here is immediate since yP(r) = T<f>p by (12).
Corollary 2: For 0p(t)=</>p=$ (i.c., no dependence on r and P — 1 giving no priorities thus allowing us to drop all subscripts) wc have
5 = X* f r[l — B(r)] -)dr. (16)
(Observe that (11) through (16) for the processor¬ sharing case are analogous to (2) through (7) for the time-sharing case.) It is important to note in this last (simplest) case that ratio of 5 to f (the average attained service) is given simply as follows: f is defined by
f tN(t)<1t Jo
f N(r)dr Jo
where the denominator is merely N = expected number of customers in the system of queues. Since, from (11) and for P = 1 , wc have
S = f 4>tN(t)<It,
Jo
wc then obtain
5 _
— = (18) f
which clearly represents the ratio of average (wasted) swap time to average (useful) attained service time for the set of customers still in the system of queues. The simplicity and intuitive appeal of this last equation further supports the utility of using processor-shared models.
. Examples
In order to apply the results obtained above, wc must find in the published literature solutions for Wp(t) (the expected wait conditioned on a service requirement of t seconds) for time-shared systems which account lor swap time. Such results are not especially numerous. We do, however, find some useful examples.
Example 1: Lev. us apply Corollary 2 of Theorem 1 to
b( rn+1) = (1 - a)*” » = 0, 1, 2, • • ; 0 < <r < 1 (19) P[l arrival in interval of length Q ] = XQ;
0 < \Q < 1
^[0 arrival in interval of length Q] = 1 — \Q
gpn = 1; P = 1
where P[x] is read “probability of x.n This system has an exact solution for lF(r„), (for0 = O), and also a simple approximation to W(rn) given below (sec [5]):
priQv
trf / \ rrr / /v\ , w- /aa\
where
W(rn) = W(nQ) S
p = XQ/(1 - a).
When we consider 0>O, a number of considerations enter. The major question is now to keep the discrete model intact since, for example, if 6 = Q/3, then a customer requiring Q seconds of useful processing ( one quantum for 0 = 0) now requires a noninteger number of quanta. No satisfactory way appears to resolve this, and so we will take two approaches. We begin with a continuous distribution of service time, namely the exponential, where /’[service timegl] = 1 — c-"'. We then recognize that all customers with n(Q—6)<l £(n + l)(Q—0) will need exactly (n + 1) visits to the service facility (we make the simplifying, but serious assumption that unused portions of quanta are lost) and the. probability that a new arrival satisfies such a condition is
/> <n+ 1 >(«-•>
pro'dt = (1 - r»«-*>) [«-*•«-»>]».
mo-*)
Comparing this to (19), we make the correspondence
<r = (22)
Wc then apply (20) and (22) to Coro! 'ary 2 of Theorem 1 to give for this example,
«0
5 = X0 2^ «( 1 — o)vnpnQo/( 1 — p)
— \0 23 <7n'Hp»C)v/(l — p).
This gives
(i - p)(i -
where p and a arc given by (21) and (22), respectively. Note that for 5< wc require p<! which requires
Kl. I INROCK: SWAP-TIME CONSIDERATIONS
0 0.2 04 0.6 0.6 10
0
Fig. 1. Allowable values for Q shown as that region for which the curve 0 + 0 /m) log 1/(1 — \Q) lies below Q. (X «= l,p = 3) for Example 1 .
Q > 0 + - log 1/(1 - XQ). (24)
p
Equation (24) places lower and upper bounds on Q. The lower bound is due to the restriction that the maximum effective service rate must exceed the average arrival rate. The upper bound is due to the wasted excess quantum and also due to the constraint that the arrival probability XQ < 1.
In Fig. 1 we show the allowed range of Q as deter¬ mined from (24) for X «= 1 , /i = 3, and 0 as parameter. Fig. 2 gives 5 as a function of Q (in its allowed range) with 0 as parameter again and for the same values of X and ft. Here we also plot the locus of optimum Q over the family of 0 curves to give minimum 5.
The second approach to handling the 0>0 case in the first example is to allow the exponential distribution of required service time to remain, but not force it into the discrete form of (19). We then get an equivalent system with 0-0 if we segment this distribution into pieces of width Q — 0, each separated by a gap of size 0 as shown in Fig. 3. This results in a mean service time E(l) and a second moment /£(/*) given by
One may now use this service-time distribution in the continuous round robin model studied in [2], as well as in other models of time-shared systems, with additional care to replace Q by Q--0 in the appropriate places.
o
Fig. 2. Average swap time 5 as a function of quantum size Q with swap time (per quantum) 8 as a parameter for Example 1 (X = l, M =3).
»
t
F'ig. 3. Segmented exponential service-time distribution to account for swap time 0.
The following examples apply only to the processor- sharing case.
Example 2: Consider the continuous (processor¬ sharing) round robin infinite-population system [4], Again we assume - 1, P =\. Here we have Poisson arrivals at rate X and exponent ial service of average duration 1 'ji. For this system we know from [4] that for (/> ~ 0,
IF(r) = pr/(l - p) (25)
We do not carry out this exorcise here.
where
32
§
IEEE TRANSACTIONS ON COMPUTERS, JUNE 1970
P = Vp-
The original exponential distribution of service time with parameter p for this system must now be replaced with another exponential distribution with parameter p(l — 0) where 0- fraction of service time wasted (as above).
We now apply Corollary 2 of Theorem 2 to give
- H f
J 0
This results in
S =
1.<r#.(l-*)r[p/(l _ p)]*.
p*4>
where
p(1 ~ p)(1 “ 0)
P = VpO ~ 4>)-
(26)
(27)
The average swap time S is plotted in Fig. 4 versus 0 with X/p as parameter for this example.
It is interesting to note the application of (18) here. From [4] we have
= p7(1 - p)
and from [6] we have (with the new value p(l — 0))
Thus
f = l/p(l - <t>).
S =<t>7J f
_ _ P*0
p(l — p)(l - 0)
which is (26) again.
Further; we can calculate this by considering the average swap time per customer, S'. S' is the product of average service time ( = l/p(l — 0)) and the fraction of wasted (swap) time (=0). Thus, S' = 0/^c(l — 0). This multiplied by N must also give 5, as is obvious.
We now show that the result of Example 1 can be taken to the limit of Q — 0 with fixed <f>=8/Q to give the result of Example 2. From Example 1, we get as Q—*0
P = XQ/(l — a)
= \Q/( 1 - r*«-*>)
= XQ/ (1 - 1 + p«? - 0) - )
= X/pO — 0)-
Thus (21) limits to (27). Also, as Q—>0
p XOpQa 2
s = d-7)a -7y
a(— V — - —
\(?/V(l - 0)/ _
(] - - — Vi - c-*u-”y
V P(1 - 0)/
Fig. 4. Average swap time 5 as a function of percentage swap time <j> with \/n as parameter for Example 2 (ji=3).
X20(?2
[p(l -0) -x][l - l+p(Q-ff) - ]2
X20
[m(1 - 0) - X][p(1 - 0)]2
_ p20
p( 1 — 0) ( 1 - p)
Thus (23) limits to (26).
Furthermore, if we wish to find the average swap time Sr for all customers still in system (queues plus service), we merely replace F=p2/(1— p) with Ar total = p/(l— p) which then gives 5j=-p0/[p(l — p)(l — 0)].
Example 3: Here we consider the priority processor- shared case studied in [4], We have gpn~gp, Bp(t) = 1 and Poisson arrivals at rate Xp for group />, P = l, 2, • • • , P. Allowing swap time of form 8pn=8p, we recognize that we must modify the service time distribution to take the form BP{1) — 1 — ^—mpO— *»>>*. From [4] we get
N'pM «= S giPi (28)
|;.(1 “ P) .1
where
P„ X„/p„(l - 0„).
Applying Corollary 1 of Theorem 2 we get
(29)
KLEINROCK: SWAP-TIME CONSIDERATIONS
p
s~ E
pp<t>f E g‘p< 1
»-i i*(i - p)pP( i - <t>P)
(30)
where
p
P- E Pp-
p-i
In order to plot S, we must choose values for (g,,}, {mp}. { Xp } , and {</>*}. For the case \p-\/P, =
<t>p—a/&p (where 0<a<l) one ol'tains from (30),
p
E
/ aX* \ p-i
\n3r- )
_ i _ £ _jf_
(gr -<*)'£[ gi — ct
1 - — E ----
/iP y_! g, - a
. (31)
iV,
Pp
gp(l ~ p) i-
*iPi-
(32)
5, -
<t>pp? E g'p>
i- 1
(33)
Pp(1 - 4>p)gp( 1 - p)
7’(r) A’r
(31)
where A’ is some eonst.im. fo solve for this constant, we use the well-known result for 7’ = average (over r) of T(t) (see [7]).
This last is plotted in .Fig. 5 versus a with yi = 3, X = 1 , P-5, and for the following eight cases: gP-\, gp - (1.01)p, gP=(l.l)',) gP = log5 (/> + l), gP = p, gp = P"\ gP = Pi, gp = ptli- Note the interesting effect where 5 decreases as we progress through the first four cases and then increases as we progress through the last four cases. These cases have been arranged in order of increasing discrimination between classes.
We note here only one of other additional methods for obtaining 5. From [4] we have that the expected number Np of customers in the system of queues from group p is
Fig. 5. Average swap time as a function of swap loss for the priority processor-shared system.
T «
M/n
1 — 7T0 y
(35)
Also, for a job of average length (1/mp(1 — 4>P)), we spend <pp/np(\—<pp) seconds swapping. Thus we must have
where
But
where
v0
= r e — — - (-YT. (36)
LfTo (Jf -m)\ \J J
fKT(r)dB(r) J 0
(37)
Since 5= EPp-i 5,, we sum and obtain (30).
Example 7: For our last example, we consider the finite-population case with M consoles, exponential service with mean 1/m and exponentially distributed think time with mean \/y as studied in [l], [7], and [10]. From the curves given by Adiri and Avi-lt/.hak [l], we may approximate 7'(r) (the average total response time) by a linear function of r. We take this as the solution form for T(t) in the processor-shared case (Q— »0). Thus we have (for zero swap time, <p = 0)
B(t) = 1 - <rpr. From (34) and (37) we obtain
K = m T.
Thus, for the zero swap-time case T(r) ~ hTt
‘ M Ml
A — vo y J
(38)
Now for 0>O, we merely use m(1 — <t>) rather than ju to obtain
r M m(i - «)1
T(r) sH - - r
LI — vo y J
(39)
where
34
IEEE TRANSACTIONS ON COMPUTERS, JUNE 1970
Fig. 6. Average swap time as a function of percentage swap time for the finite console processor-shared case.
iro
Ml
Jm ~ m)l
|
r * i |
m~i— |
|
i 1 _5 |
(40)
Applying Corollary 2 of Theorem 2, \vc obtain for the average system (queue plus service) swap time Sr,
Sr S M f tc-',<|-*)tm(1 -• <t>)Tdr
J o
where X, the average input and output rale, is clearly A = /t(l — 0)(1 — ir0). Thus
Sr = (1 - Tro)<t>T
r M
L /*(!-*)
(1 - ^o) j
where 7r0 is given by (40). ST is plotted versus $ for various M in Fig. 0 for 1/pt = 0.88 and 1/7 = 35.2.
Conclusion
YVc have shown how to solve for the expected swap time expended on all customers in the system of queues. This we have done for the time-sharing systems (Q>0) in Theorem 1 and for the processor-sharing systems (Q-->0) in Theorem 2. The examples given show the case of obtaining results for the processor-sharing case.
References
[1] I. Adiri and R. Avi-Itzhak, “A time-sharing queue with a finit number of customers,” J. ACM, vol. 16, no. 2, pp. 315-323, April 1969.
[2] F.. G. Coffman and L. Klein rock, “Feedback queueing models for time-shared systems,” J. ACM, vol. 15, no. 4, pp. 549-576, October 1968.
[3] L. Klcinrock, “On swap time in time-shared systems,” 1969 Proc. IEEE Computer Croup Couf. (Minneapolis, Minn.), pp. 37-41.
[4] - — — , “Time-shared systems: A theoretical treatment,” J. ACM, vol. 14, no. 2, pp. 242-261, April 1967.
[5] - •, “Analysis of a time-shared processor,” Naval Res. Logistics
Quart., vol. 11, no. 10, pp. 59 73, March 1961.
[6] L. Klcinrock and F. G. Coffman, “Distribution of attained service ii time-shared systems,” J. Computer Sys. Sci., vol. 1, no. 3, pp. 287-298, October 1967.
IV] F. Klcinrock, “Certain analytic results for time-shared pro¬ cessors," 196S Proc. IFIP Cong. (Edinburgh, Soctland), pp. D1 19 1)125.
[8] B. Krishna moorthi and R. C. Wood, “Time-shared computer operations with both intcrarrival and service times exponential," J.ACM, vol. 13, no. 3, pp. 317-338, July 1966.
(9] J. M. McKinney, “A survey of analytical time-sharing models,” Computing Surveys, vol. 1, no. 2, pp. 105-116, June 1969.
(10] A. L. Schcrr, An Analysis of Tvne-Sliarcd Computer Systems. Cambridge, Mass.: M.l.T I'rcss, 1967.
(11] L. E. Schrage, “The queue M/G/l with feedback to lower priority queues,” Management Sci., scr. A., vol. 13, pp. 466-474, 1967.
35
APPENDIX B
A CONTINUUM OP TIME-SHARING SCHEDULING ALGORITHMS
by
Leonard Kleinrock
37
A contiuiim of time-sharing scheduling algorithms*
by LEONARD KLEINROCK
University of California
Los Angeles, California
INTRODUCTION
The study of time-sharing scheduling algorithms has now reached a certain maturity. One need merely look at a recent survey by McKinney1 in which he traces the field from the first published paper in 1964* to a succession of many papers during these past six years. Research which is currently taking place within the field is of the nature whereby many of 'the important theoretical questions will be sufficiently well answered in the very near future so as to question the justifica¬ tion for continuing extensive research much longer without first studying the overall system behavior.
Among the scheduling algorithms which have been studied in the past are included the round robin (RR), the feedback model with N levels (FBat), and varia¬ tions of these.1 The models introduced for these sched¬ uling algorithms gave the designer some freedom in adjusting system performance as a function of service time but did not range over a continuum of system behaviors. In this paper we proceed in that direction by defining a model which allows one to range from the first come first served algorithm all the way through to a round robin scheduling algorithm. We also find a variety of other models within a given famito which have yet to be analyzed.
Thus the model analyzed in this paper provides to the designer a degree of freedom whereby he may adjust the relative behavior for jobs as a function of service time; in the past such a parameter was not available. Moreover, the method for providing this adjustment is rather straightforward to implement and is very easily changed by altering a constant within the scheduler.
* This work was supported by the Advanced Research Projects Agency of the Department of Defense (DAHC15-69-C-0285).
A GENERALIZED MODEL
In an earlier paper* wc analyzed a priority queueing system in which an entering customer from a particular priority group was assigned a zero value for priority but then began to increase in priority linearly with time at a rate indicative of his priority group. Such a model may be used for describing a large class of time¬ sharing scheduling algorithms. Consider Figure 1. This figure defines the class of scheduling algorithms which we shall consider. The principle behind this class of algorithms is that when a customer is in the system waiting for service then his priority (a numerical func¬ tion) increases from zero (upon his entry) at a rate a; similarly, when he is in service (typically with other customers sharing the service facility simultaneously with him as in a processor shared system4) his priority changes at a rate 0. All customers possess the same parameters o and 0- Figure 1 shows the case where both a aud (3 are positive although, as we shall see below, this need not be the case in general. The history of a customer’s priority value then would typically be as shown in Figure 1 where he enters the system at time to with a 0 value of priority and begins to gain priority at a rate o. At time t\ he joins those in service after having reached a value of priority equal to a (h — to) . When he joins those in service he shares on an equal basis the capacity of the service facility and then continues to gain priority at a different rate, 0. It may be that a customer is removed from service before his requirement is filled (as may occur when one of the slopes is negative) ; in this case, his priority then grows at a rate of o again, etc At all times, the server serves all those with the highest value of priority. Thus we can define a slope for priority while a customer is queueing aud another slope for priority while a cus-
39
PRIORITY
Spring Joint Computer Conference, 1970
TIME
Figure 1— Behavior of the time-varying priority
tomer is being served as
|
queueing slope a |
(1) |
|
serving slope - 0. |
(2) |
A variety of different kinds of scheduling algorithms follow from this model depending upon the relative values of a and 0. For example, when both a and 0 are positive Rnd when 0 > a then it is clear that customers in the queue can never catch up to the customer in service since he is escaping from the queueing customers at least as fast as they are catching up to him; only when the customer in service departs from service after his completion will another customer be taken into service. This new customer to be taken into the service fac'lity is that one which has the highest value of priority. Thus we see that for the range
0 < a < 0 (3)
we have a pure first come first served (FCFS) scheduling algorithm. This is indicated in Figure 2 where we show the entire structure of the general model.
Now consider the case in which
0 < 0 < a. (4)
Figure 2— The structure of the general model
What happens in this case is that entering customers spend a period of time in the queue anti after catching up with the serving group proceed to be served in a round robin fashion. The duration of the time they spend in the queue depends upon the relative param¬ eters a and 0 as we shall see below. It is clear however that for 0 - 0 we have the case that customers in service gun no priority at all. Thus any newly entering customer would have a value of priority exactly equal to that of the group in service and so will immediately pass into the service group. Since all serving customers share equally, we see that the limiting case, 0 - 0, is a processor-sharing round robin (RR) scheduling algorithm! It happens that SRR yields to analysis very nicely (whereas some of the other systems mentioned below are as yet unsolved) and the results of this analysis are given in the next section.
Another interesting range to consider is that for which
a < 0 < 0. (5)
This is the case depicted in Figure 1. Here we see that the group of customers being served (which act among themselves in a processor-shared round robin (RR) fashion) is attempting to escape from the group of customers in the queue; their attempt is futile, how¬ ever, and it is clear from this range of parameters that the queueing customers will eventually each catch up with the group being served. Thus the group being served is selfishly attempting to maintain the service capacity for themselves alone and for this reason we refer to this system as the selfish round robin (SRR).
Here we have the situation in which queueing customers lose priority faster than serving customers do; in both cases however, priority decreases with time and so any newly entering customer will clearly have the highest priority and will take over the complete service facility for themselves. This most recent customer will continue to occupy the service facility until cither he leaves due to a service completion or some new customer enters the system and ejects him. Clearly what we have here is a classical last come first served (LCFS) scheduling algorithm as is indicated in Figure 2.
40
Contiuum of Time-Sharing Scheduling Algorithms
Now consider the range
a < 0 < 0. (6)
In this case a waiting customer loses priority whereas a customer in service gains priority. When an arriving customer finds a customer in service who has a negative value for priority then this new customer preempts the old customer and begins service while at the same time his priority proceeds to increase at a rate 0; from here on no other customer can catch him and this customer will be served until completion. Upon his completion, service will then revert back to that customer with the largest value of priority. Since customers lose priority with queueing time, then all customers in the system when our lucky customer departed must have negative priority. One of these will be chosen and will begin to gain priority; if now he is lucky enough to achieve a positive priority during his service time, then he will seize the service facility and maintain possession until his completion. Thus we call this range LCFS unth seizure (see Figure 2).
In the special case
a = O<0 (7)
we have the situation in which a newly emptied service facility will find a collection of customers who have been waiting for service and who have been kept at a zero value priority. Since all of these have equal priority they will all be taken into service simultaneously and then will begin to gain priority at a rate 0 > 0. Any customers arriving thereafter must now queue in bulk fashion since they cannot catch up with the current group in service. Oniy when that group finishes service completely will the newly waiting group be taken into service. We refer to this case as bulk service.
The last case to consider is in the range
0 < 0, 0 < a. (8)
In this case a customer being served always loses priority whereas a queueing customer loses priority at a slower rate or may in fact gain priority. Consequently, serving customers will tend to "run into” queueing customers and pick them up into the service facility at which point the entire group continues to decrease in priority at rate 0. We refer to this region as LCFS with pickup (see Figure 2).
Thus Figure 2 summarizes the range of scheduling algorithms which this two-parameter priority function can provide for us. We have described a number of regions of interest for this class of algorithms. The FCFS, LCFS, and RR systems, of course, are well known and solved. The three regions given by Equa¬ tions 4, 6, and 8 are as yet unsolved. As mentioned
before, the SRR system yields very nicely to analysis and that analysis is given in this paper. This system has the interesting property that we may vary its parameters and pass smoothly from the FCFS system through the SRR class to the familiar RR system. The others (LCFS with seizure and LCFS with pickup) are as yet unsolved and appear to be more difficult to solve than the SRR. Of course other generalizations to this scheme are possible, but these too are yet to be studied. Among these generalizations, for example, is the case where each customer need not have the same a and 0; also one might consider the case where growth (or decay) of priority is a non-iinear function of time. Of all these cases we repeat again that the SRR has been the simplest to study and its analysis follows in the next section.
THE SELFISH ROUND ROBIN (SRR) SCHEDULING ALGORITHM
We consider the system for which customers in service gain priority at a rate less than or equal to the rate at which they gained priority while queueing (see Equation (4) ) ; in both cases the rate of gain is positive. We assume that the arrival process is Poisson at an average rate of X customers per second
P [inter-arrival time < f] = 1 — e~Xl t > 0 (9) and that the service times are exponentially distributed P [service time < x] ■= 1 - tr ** x > 0 (10)
Thus the two additional parameters of our system are average arrival rate *= X (11)
average service time = 1 /n (12)
As usual, we define the utilization factor
P = X/m (13)
For the range of a, 0 under consideration it is clear that once a customer enters the service facility he will not leave until his service is complete. Consequently, we may consider the system as broken into two parts: first, a collection of queued customers; and second, a collection of customers in service. Figure 3 depicts this
situation where we define*
Tw = E[time spent in queue box] (14)
T, = £[time spent in service box] (15)
N„ = ^[number in queue box] (16)
N, = ^[number in service box] (17)
* The notation £[x| reads as "the expectation of x.”
41
Spring Joint Computer Conference, 1970
ARRIVALS •
|
1 I |
queue |
URVK( |
|
|
1 1 |
•ox |
•ox |
|
|
! |
T..N. |
"r " |
V, . M, |
DCMRTURCS
Figure 3— Decomposition of the SRU system
We further define
T *■ T„ + T, ■* I?[time in system] (18)
.V »■ S„ + N, - ^[number in system] (19)
Due to the memoryless property of the exponential service time distribution, it is clear that the average number in system and average time in system are independent of the order of service of customers; this follows both from intuition and from the conservation law given in Reference 15. Thus we have immediately
|
1/m 1 - p |
(20) |
|
p 1 -p |
(21) |
For our purposes we are interested in solving for the average response time for a customer requiring t seconds of service; that is for a customer requiring t seconds of complete attention by the server or 2 / seconds of service from the server when he is shared between two customers, etc. Recall that more than one customer may simultaneously be sharing the attention of the service facility and this is just another class of processor- sharing systems.4 Thus our goal is to solve for
T(t) « ^[response time for customer requiring
t seconds of service] (22)
where by response time we mean total time spent in the system. The average of this conditional response time without regard to service time requirement is given by Equation 20. Due to our decomposition we can write immediately
T(t) « T.(t) + T,(t) (23)
where Tw(t) is the expected time spent in the queue box for customers requiring / seconds of service and T,(t) is the expected time spent in the service box for customers requiring t seconds of service. Since the
system is unaware of the customer’s service time until he departs from the system, it is clear that the time he spends in the queue box must be independent of this service time and therefore
T„(!) - T„ (24)
Let us now solve for T,{t). We make this calculation by following a customer, whom we shall refer to as tho “tagged” customer, through the system given that this customer requires t seconds of service. His time in the queue box will be given by Equation 24. We now assume that this tagged customer has just entered the service box and we wish to calculate the expected time he spends there. This calculation may be made by appealing to an earlier result. In Reference 4, we studied the case of the processor-shared round robin system ( both with and without priorities) . Theorem 4 of that paper gives the expected response time con¬ ditioned on service time and we may use that result here since the system we are considering, the service box, appears like a round robin system. However, the arrival rate of customers to the service box conditioned on the presence of a tagged customer in that box is no longer X, but rather some new average arrival rate X'. In order to calculate X' we refer the reader to Figure 4. In this figure we show that two successive customers arrive at times t, and U where the average time between these arrivals is clearly 1/X. The service group moves away from the new arrivals at a rate 0 and the new arrivals chase the service group at a rate a; as shown in Figure 4, these two adjacent arrivals catch up with the service group where the time between their arrival to the service box is given by 1/X'. Recall that the calculation we are making is conditioned on the fact that our tagged customer remains in the service box during the interval of interest; therefore the service box is guaranteed not to empty over the period of our
TIME
Figure 4 —Calculation of the conditional arrival rate to the service box
42
Contiuum of Time-Sharing Scheduling Algorithms
calculations. X' is easily calculated by recognizing that the vertical offset y may be written in the following two ways
and so wc may solve for X' as follows
and so
T=T,C +
1/m
1 - p'
Using Equation 20 we have the result
rp 1/M 1/m
” 1 - p 1 - p'
(32)
(33)
Upon substituting Equation 33 into Equation 31 we obtain our final result as
X' =
(25)
T(t) =
1/m_ , t ~ 1/m 1 - p 1 - p'
(34)
(recall that for the SRR system /S < a). For con¬ venience we now define
P “ X'/m (26)
V*re may now apply Theorem 4 of Reference 4 and obtain the quantity we are seeking, namely,
T.(t) = (27)
l — p
Another convenient form in which to express this result is to consider the average time wasted in this SRR system where wasted time is any extra time a customer spends in the system due to the fact that he is sharing the system with other customers. Thus, by definition, we have
W(t) = T(t) - t (35)
and this results in
The only difference between Equation 27 anu the referenced theorem is that here we use p' instead of p since in all cases we must use the appropriate utilization factor for the system under consideration. That theorem also gives us immediately that
N. = (28)
l — p
This last equation could be derived from Equation 27 and the application of Little’s result* which states that
XT. = N, (29)
and where
T. m ( T.(t)p^‘dt •'o
T, = (30)
l — p
We may now substitute Equation 27 into Equation 23 to give
T(t) = T„ + —
l — p
(31)
In order to evaluate T„ we form thr average with respect to t over both sides of Equatio 31 to obtain
f TiDne-^dt = Jo
— , pe-"1 dt ~ P
W(t) =
p/m , (l - 1/m)p'
1 - p 1 - p'
(36)
In both Equations 34 and 36 we observe for the case of a customer whose service time is equal to the average service time (1/p) that his average response time and average wasted time are the same that he would en¬ counter for any SRR system; thus his performance is the same that he would receive, for example, in a FCFS system. We had observed that correspondence between the RR system and the FCFS system in the past; here we show that it holds for the entire class of SRR systems. In Figure 5 below we plot the perform¬ ance of the class of SRR systems by showing the de¬ pendence of the wasted time for a customer whose service time is t seconds as a function of his service time. We show this for the case p = % and p = 1. The truly significant part regarding the behavior of the SRR system is that the dependence of the conditional response time upon the service time is linear. Once observed, this result is intuitively pleasing if we refer back to Figure 3. Clearly, the time spent in the queue box is some constant independent of service time. However, the time spent in the service box is time spent in a round robin system since all customers in that box share equally the capability of the server; we know that the response time for the round robin system is directly proportional to service time required (in fact, as shown in Reference 8, this statement is true even for arbitrary service time). Thus the total time spent in the SRR system must be equal to some con-
43
Spring Joint Computer Conference, 1970
Figure 5 — Performance of the SRR system
stant plus a second term proportional to service time as in fact our result in Equation 34 indicates. Again we emphasize the fact that customers whose service time requirements are greater than the average service time requirement are discriminated against in the SRR system as compared to a FCFS system; conversely, customers whose service time requirement is less than the average are treated preferentially in the SRR sys¬ tem and compared to the FCFS system. The degree of this preferential treatment is controlled by the parameters a and 0 giving the performance shown in Figure 5.
CONCLUSION
In this paper we have defined a continuum of scheduling algorithms for time-shared systems by the introduction of two new parameters, a and 0. The class so defined is rather broad and its range is shown in Figure 2. We have presented the analysis for the range of pa¬ rameters that is given in Equation 4 and refer to this new system as the selfish round robin (SRR) scheduling algorithm. Equation 34 gives our result for the average response time conditioned on the required service time and we observed that this result took the especially simple form of a constant plus a term linearly de¬ pendent upon the service time. Moreover, we observe that the parameters a and 0 appear in the solution only as the ratio 0/a. This last is not overly surprising since a similar observation was made in the paper1 which was our point of departure for the model de¬ scribed herein; namely, there too the slope parameters
appeared only as ratios. Thus in effect we have intro¬ duced one additional parameter, the ratio 0/a, and it is throu'-n the use of this parameter that the designer of a time-sharing scheduling algorithm is provided a degree of freedom for adjusting the extent of discrimi¬ nation based upon service time requirements which he wishes to introduce into his algorithm; the implemen¬ tation of this degree of freedom is especially simple. The range of the algorithm is from the case where there is zero discrimination baser’ on service time, namely the FCFS system, to a case where there is a strong degree of discrimination, namely the RR system.
The mathematical simplicity of the SRR algorithm is especially appealing. Nevertheless, the unsolved sys¬ tems referred to in this paper should be analyzed since they provide behavior distinct from the SHE. In any event, this continuum of algorithms is simply imple¬ mented in terms of the linear parameters a and 0, and the scheduling algorithm can easily choose the desired behavior by adjusting a and 0 appropriately.
REFERENCES
1 J M MCKINNEY
A survey of analytical timesharing models Computing Surveys Vol I No 2 pp 105-116 June I960
2 L KLEINROCK
Analysis of a time-shared processor
Naval Research Logistics Quarterly Vol 11 No 1 pp 59-73
March 1964
3 L KLEINROCK
A delay dependent queue discipline
Naval Research Logistics Quarterly Vol 11 No 4 pp 329-341 December 1964
4 L KLEINROCK
Time-shared systems: A theoretical treatment JACM Vol 14 No 2 pp 242-261 April 1967
5 L KLEINROCK
A conservation law for a wide clou of queueing disciplines Naval Research Logistics Quarterly Vol 12 No 2 pp 181-192 June 1965
6 J D C LITTLE
A proof of the queueing formula L - MV Operations Research Vol 9 pp 383-387 1961
7 L KLEINROCK
Distribution of attained service in lime-shared systems J of Computers and Systems Science Vol 3 pp 287-298 October 1967
8 M SAKATA S NOGUCHI J OIZUMI
Analysis of a processor shared queueing model far timesharing systems
Proc of the Second Hawaii International Conference on Systems Science pp 625-628
University of Hawaii Honolulu Hawaii January 22-24 1969
44
APPENDIX C
MULTILEVEL PROCESSOR-SHARING QUEUEING MOEELS FOR TIME-SHARED SYSTEMS
by
L. Kleinrock and R. R. Muntz
|
IflBi' HylWWIj.WWilfJ |
*T :T "■ |
; ■ |
mm
MULTILEVEL PROCESSOR-SHARING QUEUEING MODELS FOR TIME-SHARED SYSTEMS’
L. Kielnrock and R. R. Muntz University of California Los Angeles, California USA
ABSTRACT
Scheduling algorithms for tine-shared computing facili¬ ties are considered in terns of a queueing theory model.
Hie extronely useful limit of "processor-sharing" is adopted, wherein the quantun of servioe shrinks to zero; this approach greatly simplifies the problem. A class of algorithms is studied for which the scheduling discipline may change for a given job as a function of the amount of servioe received by that jab. These multilevel disciplines form a natural extension to many of the disciplines previ¬ ously considered.
Solved for is the average response time for jobs condi¬ tioned on their servioe requironent. Explicit solutions are given for the system H/G/l in which levels may be first- cune-first-served (PCFS) or feedback (FB) in any order; in addition, the round-robin (RR) may be used at the first level. An integral equation is developed which defines (but dnan not as yet provide a solution for) the RR case at arbitrary level. The special case in which RR is used at the last level is solved under the condition that the serv¬ ioe time behave exponentially for this last level.
Examples are described far which the average response time is plotted. These exanples display the great versatil¬ ity of the results and dononstrate the flexibility avail¬ able for the intelligent design of discriminatory treatment among jabs (in favor of short jobs and against long jobs) in time-shared system design.
•This work was supported by the Advanced Research Projects Agency of the Department of Defense (DfUC-15-69- C-0285) .
47
341/1
l. introduction
Queueing models nave been used successfully in the ' ly¬ sis of time-shired ocrputer ays tans since the appea> r- wis of the first applied paper in this field in 1964 (1) . The re¬ cent survey [2] of such analytical work attests to this fact. Che of the first papers to consider the effect of feedback in queueing systems was due to Takacs (3] .
Generally, an arrival enters the time-shared system and competes for the attention of a single processing unit.
This arrival is farced to wait in a system of queues until he is permitted a quantum of servioe time; when this quan¬ tum expires, he is then required to join the system of queues to await his seocnd quantun, etc. The precise model for the system is developed in Section 2. In 1967 the no¬ tion of allowing the quantun to shrink to zero was first studied [4] and is referred to as "processor-sharing. " As the none implies, this zero-quantum limit provides a share or portion of the processing unit to many customers simul¬ taneously; in the case of round-robin (RR) scheduling [4] , all customers in the system simultaneously share (equally or on a priority basis) the processor, whereas in the feed¬ back (FB) scheduling (5) only that set of customers with the smallest attained servioe share the processor. We use the term processor-sharing here since it is the processing unit itself (the central processing unit of the ocrputer) which is being shared among the set of the customers; the phrase "time-sharing" will be reserved to iiiply that custo¬ mers are waiting sequentially for their turn to use the en¬ tire processor for a finite quantum. In studying the liter¬ ature one finds that the obtained results appear in a rather complex form and this complexity arises from the fact that the quantun is typically assumed to be finite as opposed to infinitesimal. Vtien one allows the quantun to shrink to zero, giving rise to a processor-sharing system, then the difficulty in analysis as well as in the form of results disappears in large part; one is thus encouraged to consider only the pzooessor-sharing case. Clearly, this limit of infinitesimal quantun is an ideal and can seldom be reached in practice due to considerations of swap time; neverthe¬ less, its extreme simplicity in analysis and results brings us to the studies reported in this paper.
The two processor-sharing systons studied in the past are the RR and the FB (4,5). Typically, the quantity solved for is the expected response time conditioned on the custo¬ mer's service time; response time is the elapsed time frcm when a customer enters the systan until he leaves completely serviced . This measure is especially important since it exposes the preferential treatment given to short jcos at the expense of the long jobs. Clearly, this discrimination is purposeful since it is the desire in time-shared systems that small requests should be allowed to pass through the system quickly. In 1969 the distribution for the response time in the RR system was found (6) . In this paper we con¬ sider the case of mixed scheduling algorithms whereby custo¬ mers are treated according to the RR algorithm, the FB algo¬ rithm, or first cone first served (PCI'S) algorithm, depend¬ ing upon how much total servioe time they have already re¬ ceived. Thus, as a customer proceeds through the system obtaining service at various rates he is treated according to different disciplines; the policy which is applied among cus toners in different levels is that of the FB system as explained further in Section 2. This natural generalization of the previously studied processor-sharing systems allows one to create a large nutter of new and interesting disci¬ plines whose solutions we present.
r
2. THE MODEL
The model we choose to use In representing the schedul¬ ing algorithms is drawn from queueing theory. This corre¬ sponds to the many previous models studied [1,2,4,5,6,7,81, all of which may be thought of in terms of the structure shown in Fig. 2.1. In this figure we indicate that new requests enter the 3ystem of queues upon arrival. When¬ ever the computer's central processing unit (CPU) becomes free, some customer is allowed into the service facility for an amount of time referred to as a quantun. If during this quantum, the total ewcren dated service far a customer equals his required service time, then he departs the sys¬ tem; if not, at the end of his quantun, he cycles bade to the system of queues aid waits until he is next chosen far additional service. Tne system of queues may order the customers according to a variety of different criteria in order to select the next customer to receive a quantum.
In this paper , we assure that the only measure used in evaluating this criterion is the amount of attained service (total service so far received).
CYCLED ARRIVALS
ARRIVALS
DEPARTURES
Figure 2.1. Tie FndbMk Ouwwlng Modal
In order to specify the scheduling algorithm in terms of this model, it is required that we identify the following:
a. The customer interarrival time distribution. We as¬ sure this to be exponential, i.e.,
P[ interarrival time t] ■ 1 - e”^ t > 0 (2.1) where X is the average arrival rate of customers.
b. The distribution of required servioe tine in the CPU. This we assure to be arbitrary (but independent of the interarrival times) . We thus assume
P[ service time < x) - B(x) (2.2)
Also assure 1/p » average service time
c. The quantun slse. Here we assure a processor-shared model in which customers receive an equal but vanishingly snail ancunt of servioe each time they are allowed into service. For more discussion of such systems, see (4,6,7).
d. The system of queuy. We consider here a generaliza¬ tion and consolidation of many systems studied in the past. In particular, we define a set of attained service times Uj) such that
5“*0<4l<a2 < — <aN< Vl“* (2'3)
The discipline followed far a job when it has attained service, r, in the interval
ai-l I T I ai 1 “ 1*2 . N + 1 (2.4)
will be denoted as D^. We consider for any given level i to be either: FIRST (XFG FIRST SERVED (PCFS) ; PROCESSOR SHARED-FB. (FB) ; or ROUND-ROBIN PROCESSOR SHAPED (RR) . The
FCFS system needs no explanation. The FB system gives serv¬ ice- next to that customer who so far has least attained service; if there is a tie (among K customers, say) for this position, then all K renters in the tie get served simul¬ taneously (each attaining useful service at a rate of 1/K sec/sec) , this being the nature of processor sharing sys¬ tems. The RR processor sharing syston shares the servioe facility among all customers present (say J customers)
giving attaint*, turvioe bo each at a rate of i/J sac/aec. Moreover, between intervals, the jobs are treated aa a set of FB disciplines. See Fig. 2.2. For example, for N • 0, we hove the usual single-level case of either (CPS, RR or FB.
FB
BETWEEN ^ LEVELS
ATTAINED SERVICE, r Du
SN*l | |
«
■ .
0. i
o. <
•N
~t "I
*1
•t
Figure 2.2. IntewR of Attains^ Santo*. t*Mi DMpNeae, D|
For N ■ 1, we oould have any of nine dlsdpl lnee (PCFS fol¬ lowed by FCFS . RR followed by RR) ; note that FB fol¬
lowed by FB is just a single FB system (due to the overall FB policy between levels) .
t
As an illustrative example, oon- siefcr the N - 2 case shown in Fig. 2.3.
Any new arrivals begin to share the processor in a RR fashion with all other customers who so far have less than 2 seconds of attained servioe.
Customers in the range of 2 < t < 6 may get served only if no customers present have had less than 2 seconds of service; in such a case, that custo¬ mer (or customers) with the least at¬ tained servioe will proceed to oocqpy the servioe in an FB fashion until they either leave, or reach t ■ 6, or some new customer arrives (in which case the overall FB rule provides that the RR 0
policy at level 1 preempts) . If all Figure M. EimphefN -2 customers have T > 6, then the "oldest1' customer will be served to acnplaticn unless in tempted by a new arrival. The history of sore customers in this exanple syston is shown in Fig. 2.4. We denote customer n by C . Note that the slops of attained
service varies as the muter of customers simultaneously being serviced changes. We see that required 5 seconds
of servioe end spent 14 seconds in system (i.e., respmwn time of 14 seconds! .
|
FCFS |
|
|
FB |
- • |
|
• RR |
_ 2 |
48
341/2
}
]
So much far the system specification. We may summarize by saying that vm have an M/G/l quaueing system* model with processor sharing and with a generalized multilevel sched¬ uling structure.
The quantity we wish to solve far is
T(t) * E[ response time for a custcmer requir¬ ing a total of t seocnds of attained (2.5) service]
we further make the following definitions:
T^(t) ■ E{time spent in interval i (a^, a^)
for cus toners requiring a total of t (2.6) seocnds of attained service}
He note that
T±(t) - ^(f) for t,t' > (2.7)
Furthermore, we have, for a^ < t <_ a^, that k
T(t>“i4Ti(t> <2,8>
Also, we find it convenient to define the following quan¬ tities with respect to B(t) truncated at t - x:
r x /•“
^<xm J tdB(t) + x J <JB(t)
-y /•* 2 2 r“
t <xmJ t dB(t) + dB(t)
o ■
w<x <x
x^t
wx - 2nr- p "j
(2.9)
(MO)
(2.11)
(2.12)
Note that Wx represents the expected work foind by a new
arrival in the system M/G/l where the aerviae time distri¬ bution is B(t) truncated at x.
3. RESULTS FOR MUUIIEVEL QUEUEING SYSTEMS
we wish to find an expression for T(t) , the mean system time (i.e. , average response time) for jobs with service time t such that a^_^ < t <_ a^, i.e., jobs which reach the
i**1 level queue and then leave the syston. To aooaplish
ll.
this it is convenient to isolate the ial level to sane ex¬ tent. we make use of the following two facts.
1. By the assunpticn of preceptive priority of lower level queues (i.e., FB discipline between levels) it
is clear that jcbs in levels higher than the 1th level can be ignored. This follows since these jobs cannot interfere with the servicing of the lower levels.
2. He are interested in jobs that will reach the 1th level queue and then depart from the sysbon before pass¬ ing to the (i + l)8t level. The system time of such a job can be thought of as occurring in two parts. The first portion is the time fran the job's arrival to
the queueing sysbon until the group at the 1th level is serviced for the first time after this job has
reached the i level. The second portion starts with
*M/G/1 denotes the single-server queueing system with Poisson arrivals and arbitrary service time distribution.
341/3
the end of the first portion and ends when the job leaves the system, it la easy to see that both the first and second portions of the job's system time are unaffected by the service disciplines used in levels 1 through i - 1. Therefore, we can assume any conven¬ ient disciplines. In fact, all these levels can be lumped into one equivalent level which services jobs with attained service between 0 and a, seocnds using uy service discipline.
Fran (1) and (2) above it follows that we can solve for
T(t> far jobs that leave the system from the 1th level by considering a two-level system. The lower level services jobs with attained service between 0 and a^ whereas the
second level services jcbs with attained serdce between aj_^ and a^. Jcbs that would have passed to the i + 1st level after receiving a^ seconds of service in the original
system are now assumed to leave the sysbon at that point.
In other words the service time distribution is truncated at a^.
3.1. 1th Level Discipline is re
Consider the two- level sysbon with the ssoond level
corresponding to the 1th level of the original syston.
Since we are free to choose the discipline used in the lower level, we can assume that the FB discipline is used in this level as well. Clearly the two-level system be¬ haves like a single level FB system with aaxviae time dis¬ tribution truncated at a, . The solution for such a system is known [5,11] :
T(t)
x?<t
2d - P<tr
(3.1)
3.2. 1th level Discipline is FCFS
Consider again the two-level system with break¬ points at a^_1 and a^. Regardless of the discipline in the
lower level, a tagged jefa entering the system will be de¬ layed by the sum of the work currently in both levels plus any new arrivals to the lower level queue during the inter¬ val this job is in the system. These new arrivals foam a Poisson process with parameter X and their contribution to the delay is a randem variable vboae first and seaend mo- -y
merits are E, end t respectively. By delay cycle analy- “i <ai sis [9] we have
T(t) -
W + t
“i
(3.2)
It is also possible to use these methods for solving last- cane- irst-served and randem order of service at any level.
3.3. 1th bevel Discipline is KR
Results to date allow explicit solutions for only two cases. (1) HR in the first level and (2) KR in the last level with the added restriction that onoe a job has reached this level the distribution of remaining aerviae time is exponential. The analysis will be developed for the general case as feu: as possible before being restricted to special cases.
He s'tart by considering the two-level systmn with breakpoints at a^_^ and a^. Consider the busy periods of
the lower level. During each such busy period there may be a number of jobs that pass to the higher level. He choose to consider these arrivals to the higher level as occurring at the end of the lower level busy period so that there is a bulk arrival to the higher level at this time. He also choose to temporarily delete these lower level buey periods fran the time axis. In effect we create a virtual time axis telescoped to delete the lower level busy periods.
Since the time from the end of one lower level busy period to the start of the next is exponentially distributed (Poisson arrivals l ) , the arrivals to the higher level appear
In virtual tine to be bulk arrivals at instants generated fran a Poisson process with parameter X.
Consider a job that requires t - + x seconds of
service (0 < x < a^ - ai_1) . Let be the mean real tine
the jab spends in the system until its arrival (at the end of the lower level busy period) at the higher level queue, let a2(i) be the mean virtual tine the job spends in the
higher level queue.
a1 can be calculated using delay cycle analysis. The
initial delay is equal to the mean work the jab finds in the lower level on arrival plus the a^_^ seconds of work
that it contributes to the lower level. This initial delay is expanded by new jcbe arriving at the lower level by a factor of 1/(1 - p ) (see (9)). Therefore
(Vi*M
If a2(x) Is the mean virtual time the job spends In
the higher level, we can easily convert this to the mean real time spent in this level. In the virtual time inter¬ val a2(t) there are an average of Xojh) lower level busy
periods that have been ignored. Each of these has a mean length of fc<a, .
o. - the probability that a job
which has received iq seocnds .. of servioe will require mere 'J'a) than (i + l)q seconds o£ service.
a « the mean bulk size of arrivals. (3.9)
b > the mean nuiber of arrivals ... with a tagged jcb.
Since we intend to lei q approach 0, the posi¬ tion of the tagged job with respect lo tim jobs tliat arrive in the same group is not important. We wt' assire for con¬ venience that the tagged job is ti* last j' h in the group.
The mean time until the tagged job lias re¬ ceived its first quantun of service is given by
t, ■ £ n(jq)q + bq + q (3.
1 j-o
In general, the mean time between the (i - l)st and 1th quantun of 'service to the tagged job is given by
Ti ■ §> ‘"'W’jV — °j+i-2
+ L ,x“ TjVi - °i-j-2 «>
Therefore, the mean real time the job spends in the higher level is given by
a2(r) + Xa2(x)
Combining these results we see that a job requiring t » + r seconds of servioe has mean system time givsr
by
T,a._i + x) - r_~i~ . (W + Vl + ou,(t) } (3.5)
ai-l 1-1
The only unknown quantity in this equation is (x) . To solve for a2(x) ws must, in general, oonsider an M/G/l
systan with bulk arrivals and RR processor sharing. Ths only exoeptlcn is the case of RR at the first levs! which has cnly single arrivals. Since the higher level queues can be Ignored, the solution in this exceptional case is the same as for a romd-rebin single level system with servioe time distribution truncated at a. . Therefore, from (8) we have for the first lew!
+ q + blOgOj^ ... Oj.jta (3.12)
The first term represents the time required by those jobs which were initially In the system and will still be there after the tagged jab has received i - 1 quanta of servioe. The second term is the contribution due to jobs that have arrived sinoe the tagged job entered the systan. The third term is due to the tagged job itself. The last term re¬ sults from those jobs which arrived with the tagged jcb and require more than i - 1 quanta of servioe.
Dividing both sides of Eq. (3.12) be q we get
■q " E, n(ta)oj°j+l ”• Vi-2
+ £ XaffaO.o. ... o. j-1 J u 1 1 2 *■
+ 1 + bo^ ...
Let iq - t and jq ■ x. Then as q •* 0:
0 < t < Si
Let us now consider the bulk arrival RR system in isolation in order to solve for the virtual time spent in the higter level queue, a2 (x) which we temporarily write as a(x).
3.3,1. The Bulk Arrival, RR Model
We approach this problan by first considering a discrete time systan with quantun size q > 0. Vte ass ire that arrivals and departures take plaoe cnly at times that are integral multiples of q. For snail q any continuous distribution can be approximated. By letting q approach 0 equations for continuous time systems can be found.
let n(iq) - the mean ranter of jobs in the
systan with iq seconds of at- (3.7) tailed servioe.
. 1 - B(X + t)
j+1 ”• °j+i-2 J. - B(x) n( jq) * n(x)
0°l ”• °i-j-2 * 1 - B(t - 50 OgOj^ ... Oi_1 -► 1 ■ B(t)
Therefore as q ♦ 0 Eq. (3.13) becomes
a'it)m{ n(x) 1 i **
+ Xi/ a* (x) (1 - B(t - x))dx
+ 1 + b(l - B(t) ]
341/4
that
From Kleinrock and Coffman [7] «e also have
n(x) - Aa[l - B(x)]a' (x) (3.20)
Substituting for n(x) we have
OB
a' (t) = XaJ" a' (x) (1 - B(x + t)]dx 0
t
+ X5 / o' (x)(l - B(t- x)]dx 0
+ 1 + b[l - B(t)] (3.21)
This integral equation defines o' (t) for the case of bulk arrival to a RR processor- sharing M/G/l system. Unfortun¬ ately no general solution has been found for this equation in terms of B(t). However, for exponential serviae time the equation can be solved.
3.3.1b. M/qyi with Bulk Arrival. Returning to our discussion of the two level queueing system with breakpoints at a^_^ and a^, we had Eq. (3.5)
T(ai_i + x)
1
1 - P
<a.
i-1
{%_! + ai-l + a2 <T> } (3-5)
where a2(x) was the mean virtual time spent in the higher
level queue. But in virtual time this is the solution for the bulk arrival case just studied. The study in the gen¬ eral case M/G/l led to an integral equation, Eq. (3.21), for which no more explicit solution was obtained. However, in the case of an exponential distribution, we have the solution given in Eq. (3.29) . hus, we may permit RR at the first level (see Eq. (3.6)) in M/B/l or at the last level in M/3V1* In the latter case, we therefore consider the equivalent two- level system in which the breakpoints a^_j and a^ are restricted to a^ and ■», respectively.
Thus, for the case t = a^ + x we have fran Eq. (3.29) that N
3.3.1a. M/M/1 with Bulk Arrival. In this
case
B(t) - 1 - e"pt (3.22)
Therefore the Eq. (3.21) becomes
o' (t) - a' (x)e-lJ <x+t)dx
0
+ Aa^ a' (x)e_w(t_Xldx 0
+ 1 + be"pt (3.23)
Fran Eq. (3.20) we obtain
OB BB
Aa J a’ Me uVUtdx - J n(x)e_Mtdx - ne"ut (3.24) 0 0
a2(-) = a(x) - + d[l - e~u(1_p)T] (3.30)
where C = u(l - p)d. Therefore, from Eq. (3.5),
T(^ + T> “ r^p— {% + “n + + d‘1 - e‘w(1'p>T](
w
(3.31)
_ In addition to the constant d we also need to solve for a, the mean size of the bulk arrivals to the RR queue, since this is contained in _ Aa . This we do
p = u
for the general case a. . a. . a is just the mean nunber of
jobs that arrive during a lower level busy period and re¬ quire more than a^_1 seconds of service. Therefore a must
satisfy the equation
a *= At a + [1 - B(a. ,)]1 (3.32)
ai-l 1-1
where n » E[no. found in system by a new arrival] . Using this expression for the first term on the right-hand side of Eq. (3.23) and taking Laplace transforms we obtain
sa*(s)
s(n 4- b + 1) 4- u s (s + u - A®
(3.25)
Inverting, we get for t > 0 (observing that a' (0) = n + b + 1) ,
a'(t) ■ 1 + <n » b ±4> 11 - Pi - 1 e-^a-0)t (3,26)
i - p i -p
In this equation AH
is the mean nuiber of jobs that
l-l
arrive during tht service time of the first job in the busy period. Since each of these jobs in effect generates a busy period, there are an average of At a arrivals to
<ai-l
the upper level queue due to these jobs. The second term is just the average nunber of times that the first job in the busy period will require more than a. . seconds of serviae . 1-A
Clearly then
where
P - ^ (3.27)
Here, n and b are unknown quantities which need not be solved for directly. Instead we combine them in a new un¬ known C - n + b - *-2 — and we obtain 1 - p
o' (t) - + Ce_u (1_p,t (3.28)
Integrating and using the initial condition that a(0) >0 we get
a(t) 3 + UTT“7T I1 ' e-p(i-p)t] (3.29)
In the next section we will evaluate the constant C and calculate a for a multilevel queueing system with RR at the last level where the service time distribu¬ tion ncy be general up to this level, but must be experien¬ tial in this last (semi-infinite) level; i.e., B(x) must have an exponential tail and we denote this system by M/oyi. The same method can be used to oorplete the solu¬ tion for a single level queue with bulk arrivals.
1 - BfV,)
I” o7a_
ai-l
(3.33)
Now we may complete the solution for t » a^ + x by solving for C by conserving the mean work in
the system. Sinoe the single server works at a constant rate as long as there is any work in the system, the amount of work in the system at any time is independent of the service disciplines and system levels. It follows immedi¬ ately that the mean work in the system is a constant (de¬ pending only on Aand the service time distribution) . The mean work in the system is given by (see Eq. (2.12)) .
We also have from Eq. (3.20) that n(t) =
A[1 - B(t) ]T ' (t) where n(t) is the mean nuiber of jobs in the system with t seconds of attained service. The mean re¬ maining service requirement for a job which has adready re¬ ceived t seconds of service is given by
C° xdB(x) j r~ B(t) ”
51
341/5
Therefore the mean work in the system is also given by
rr, pcrs, re i - 1
(3.35) DA - | ICTS, re i - 2,3, . ... N j (4.2)
RR, PCPS, re i - N + 1
or
m m
w.-/ xil - B(t)lTMt) y - t at (3.36)
0 ' t '
With no loM of generality, we may umm that the RR discipline is the lower level queue discipline. In this case we have from Eqs. (3.6), (3.31) and W from Eq. (2.12) that
-u (l-o) (t-*.) )
♦ d(l-e "] t > a,^ (3.37)
Using this expression for T(t) in Eq. (3.36) we can solve far d. Since B(x) is arbitrary in the range 0 < t < ^ (and exponential for t > ^) the solution is not
expressible in a aspect form, vtwn B(x) is exponential oust 0 < x < » the solution is simplified, m particular for all~>
xdB(x)
i - sra
(3.38)
Therefore
W m-J X[1 - B(t)]T'(t) idt - i f e^Vjtldt (3.39) Ncm using the Bq. (3.37) for T(t) wa have
That is, we also permit RR at the highest level if B(x) is of wporential form in the interval ^ < x.
Mb begin with three exanples from the system M/M/1- As Ben tiered in Section 2, we have nine disciplines for the case N • 1. This acmes about from Eq. {4.2) where we allow *iy one of three disciplines at level 1 and any ore of three disciplines at level 2. As we have shown, the behav¬ ior of the average ocnditicnal response tii e in .my particu¬ lar level is independent of the discipline in all other levels. In Fig. 4.1 we show the behavior of each of the three disciplines ter the system n ■ 1.
H(m4.1. RMeom Tim* SowIbNISw «w N«1. M/M/1. „ ■ 1. X - .75,., -2
In this case we have assuned g ■ 1, X * 0.75, and a^ ■ 2.
Note that for the case M/M/1 we have from Eqs. (2.9) , (2.10) , «xf (3.33) the following:
E,. • i <1 - e ) - 0.865
Setting W
■ ill -T«J ’
A
<e1 g
ntially have a
17 2
fc<a, “ "I
-tie, -pa.
11 - a A - ue1e ] - 1.19
solution far C. The solution is illustrated later in the examples section.
- *“*1
a - e 1 / (1 - Xt„ ) - 0.385
*1
4. EXAMPLES
In this section we demerits through examples the na¬ ture of the resulta we haws obtained. Recall that we have given explicit solutions for our general model in the case M/tJ/l with processor sharing where the allowed scheduling disciplines within a given level nay be either PCPS or FB. Moreover, for this general, system we allow RR at level 1. That la, for the caee M/3/.l,
I RR, PCPS, FB 1 - 1 )
D. - (4.1)
( reps, re i - 2,3, ..., n ♦ l J
Also, for the parameter values chosen, we have C - 2.42.
Fran Bq. (3.1) we see that the response time for the FB sys- tan is oatple .-ely independent of the values a^ and therefore
the curve shown in Fig. 4.1 far this response time is appli¬ cable to all of our M/M/1 cases. Note the inflection point in this curve which results in a linear growth for response time as t ♦ » (a phenqnencn not observable frun previously published figures) . As can be seen from its defining equa¬ tion, the response time for PCPS is linear regardless of the level; the RR system at level 1 is also linear, but as we aee fraa this figure and from Eq. (3.37) the RR at level N + 1 la non-linear. Thus one can determine the behavior of any of nine possible disciplines fron Fig. 4.1. Miri and Avi-Itihak considered the case (re, RR) [12] .
52
341/6
Furthermore, in the case M/Ot/1 we permit
Continuing with the case M/M/l, we shew in Tig. 4.2 the cose for N - 3 where D, » RR, D- ■ FB, D. - FCFS, and ■ RR. in this caaewe have aioeen ■ i and y ■ 1,
X ■ 0.75. He also show in this figure the case FB over the entire range as a reference curve for comparison with this discipline. Note (in general for M/H/l) that the response tine for any discipline in a given level nust either coin¬ cide with FB curve or lie above it in the early part of the interval and below it in the latter part of the interval; this is true due to the conservation law [10].
M Tima for an Examp) a of N - 3. M/M/1, y- 1, X -0.78, t| - I
Also shown in this figure is a dashed line corresponding to the FB system ever the entire range. Clearly, one may se¬ lect any eequanoe of FB and FCFS with duplicates in adja- oent intervals and the behavior far such systems can be found from Fig. 4.3. It is interesting to note in the general M/3/1 case with D. « FCFS that we have a solution for the FB system with finite quantun q^ » - ai_1 vhere
preemption within a quantum is permitted!
For our last exanple we choose the svston M/E-/1 with N » 1. In this system we have
- (2y)2xe_2yx x > 0 (4.6)
as shown in Fig. 4.4. We note that the mean service time here is again given by 1/p ; the second moment of this dis¬ tribution is 3/2 yz. We calculate
F . i - i
<ax y y
[1 + 2yax + 2 (ya^) 2]
the third exanplo for M/M/l is far the iterated struc¬ ture ■ FOB. Cnoe again we have chosen y ■ 1, X ■ 0.75,
Fifiira4.4. S*rvic* Tim* Dantity for M/Ej/I.y - 1
We choose the systan N » 1 with - RR and Dj - FCFS. For the cases a^ ■ l/2y, 1/y, 2/y, 4/y with y » 1 and X - 0.75 we show in Fig. 4.5 the behavior of this systan.
Figure 4.3. Rwpons*
i Tlm« for th» M/M/1 Ittrattd Structure, /i- 1,X-0.75,»|-l,N-«
Figure 4 5. Ritponre Tim* for RR. FCFS in M/E}/t
This figure demonstrates again the kind of behavior obtain¬ able from our result* as one varies the appropriate system parom tars; once again one may choose to discriminate in a variety of ways in favor of the short jobs and against the longer jobs.
5. OCNCUUSICN
Our purpose has been to generalise results in the model¬ ling and analysis of time-shared systems. The class of sys¬ tems considered was the processor-sharing systems in which various disciplines were permitted at different levels of attained service. The principle results for MAV1 are the following i (1) The average conditional response time at level i is independent of the queueing discipline at all other levels; (2) the performance for the FB discipline at any level la given by Eq. (3.1) ; (3) the performance for the RTFS discipline is linear with t within any level and is given by Eq. (3.2) ; (4) the performance for thu RR discipline at the first level la well-known 18] and la given by Eq. (3.6); (5) on Integral equation for the average conditional response time for RR at any level (equivalent to bulk arrival RR) is given by Eq. (3.21) and remains unsolved in general. For MAW/1 (exponential tall for t > ^) we have the perform¬ ance for RR at the last level as given by Eq. (3.37) .
Examples are given which display the behavior of same of the possible system configurations. Fran these, we note the great flexibility available In these multilevel systems.
References
1. Kleinrock, L. , "Analysis of A Tima-Shared Processor,"
Naval Research Logistics Quarterly, Vol. II, No. 1, pp. 59-73, March 1964.
2. McKinney, J. M. , "A Survey of Analytical Time-Sharing
Models," Ccmitinq Surveys, Vol. 1, No. 2, June 1969, pp. 105-116. -
3. Takers L. , "A SInglerServer Queue with Feedback," Bell Syitam Technical Journal, March 1963, pp. 505-519.
4. Kleinrock, L. , "Time Chared Systems: A Theoretical Treatment," JAQ4, Vol. 14, No. 2, April 1967, pp. 242- 261.
5. Kleinrock, L., end E. G. Gofftun, "Feedback Queueing Models for Time-Shared System," JACM, Vol. 15, No. 4, October 1S68, pp. 549-576.
6. Coffman, E.G., Jr., R.R. Muntx, and H. Trotter, "Wait¬ ing Time Distributions for Processor- Sharing System,” JACM, Vol. 17, No. 1, Jan. 1970, pp. 123-130.
7. Kleinrock, L. , and E. G. Oofflnan, "Distribution of Attained Service in Time-Shared Systems," J.ofCcm- puters and Systems Science, Vol. 3, October 1967, pp.
Sr^sr — -
8. Sakata, M. , s. Noguchi, and J. Oiruni, "Analysis of a Processor-Shared Queueing Model for Time-Sharing Sys¬ tems," Proc. , 2nd Hawaii International Oonf. on System Sciences, Jen. pp. 625-028.
9. Conway, R. W. , W. L. Maxwell, and L. w. Miller, Theory of Scheduling, Addiscn-Vbsley, 1967.
10. Kleinrock, L. , "A Conservation ha* for a wide Class of Queueing Disciplines," Navel research Logistics Quar¬ terly, Vol, 12, No. 2, 355 D557 pp. 161-192.
11. Schrage, L. E. , "The Queue MA5/1 with Feedback to Lower Priority Queues," Management Science, Vol., 13, No. 7, 1967.
12. Adiri, I., and B. Avi-Itzhak, "Queueing Models for Time-Sharing Service System,” Operations Research, Statistics and Eoonanics Mimeograph Series No. 27, Technion, Israel.
54
341/8
APPENDIX D
BUFFER BEHAVIOR FOR BATCH POISSON ARRIVALS AND SINGLE CONSTANT OUTPUT
by
Wesley W. Chu
1
BUFFER BEHAVIOR FOR BATCH POISSON ARRIVALS AND SINGLE CONSTANT OUTPUT
Wesley W. Chu Member, IEEE
ABSTRACT
A queuing model with limited waiting room (buffer), batch (burst) Poisson arrivals, and a synchronous single server (transmittion channel) with constant service time (constant transmission rate) is studied. Using average burst length and traffic intensity as parameters, the relationships among buffer size, overflow probabilities, and an approximation to the expected queuing delay of each burst due to buffering are obtained. These relationships are represented in graphs which provided a guide to the buffer design problem. A simple example is given which applies these results to the design of a buffer system in a time -sharing computer system. Although the problem discussed this paper arose in studies of design of statistical multiplexers, the queuing model developed is quite general, and may be useful for other industrial applications.
The author was with Bell Telephone Laboratories, Holmdel, N. J. He is now at the University of California, Los Angeles, California. This research it in part supported by Advanced Research Projects Agency of the Depart¬ ment of Defense (DAHC 15-69-0285) and the Office of Naval Research,
N 000 14 -69- A -02000-4027.
57
I.
INTRODUCTION
Buffer design is one of the important considerations in communication systems design, such as multiplexing system, data compression system etc. The problem of interest is: For a given buffer input traffic char¬ acteristics, buffer output transmission rate, what are 1) the relationship between the overflow probability (the average fraction of the total number of arriving data rejected by the buffer) and buffer size at various traffic
intensities, and 2) the expected queuing delay due to buffering. Birdsall*
2
and later Dor have analyzed the buffer behavior of Poisson input arrivals,
3
and constant output. Chu have further studied the buffer behavior of this model with multiple outputs. In many data communication systems, how¬ ever, the input traffic are in bursts (strings of characters) rather than in single characters. For example, in computer communication systems,
the computer output traffic are in bursts. From measurements of some
4
operating computer systems, Fuchs and Jackson have found that the bursts arrivals can be approximated as Poisson distributed and the burst length can be approximated as geometrically distributed. The buffer behavior with bursty input traffic are very different from that of the previous analyzed models. Therefore, in this paper, a finite waiting room queuing model is used to study the buffer behavior with bursty traffic inputs. The results obtained from this study are portrayed in graphs which provided a guide to the buffer design problem.
II. ANALYSIS OF BUFFER BEHAVIOR
Le: us define the time to transmit a character from the multiplex line as a unit service interval and denoted as n . For a line with a transmission rate R characters per second, then/u=l/R seconds per character. Next, we assume the burst length, X, is geometrically distributed with mean, i = 1/0, and the number of bursts arrived during a unit service interval Y, is Poisson distributed with a rate of X bursts per service time. The density functions of X and Y are as follows :
59
fx(i) = 6(1 - 6)
/
(1)
it ~ 1/ 2, , . ,
fy(n) = exp(- X) Xn/n! 11*0,1,2,... (2)
The total number cf characters that arrived during the time to transmit a character on the multiplexed line is a random sum and equals
Y
sv* 2 x (3)
i=0
where X^, a random variable distributed as (1), is the number of characters contained in the ith arriving burst, and Y, a random variable distributed as (2), is the total number of bursts arriving during the unit service interval. For simplicity in notation, we let S s Sy*
The characteristic function of S, $g(u), can be expressed in terms of the characteristic function of X, $x(u), and X.
<t> g(u) = exp[ -X + X<£x'u)] (4)
Since the burst lengths are geometrically distributed, the characteristic function of X is
^x(u) = 6 exp (iu) /(I - (1 -0) exp(iu)) (5)
where i = V’-l . Substituting (5) into (4), then
^g(u) = exp[ - X +X 0 exp(iu)/(l -(1 - 0) exp(iu)) ]
(6)
From, (6), it can be shown that the probability density function of j characters arriving during a unit service interval distribution as shown in the following:
arriving during a unit service interval, Pr(s = j) = it., is a compound Poisson
1
l (r-1l)(^)k(1-»)f'kexP(-X)/k! 1 = !<2. • ■■
exp ( - X)
3=0
The expected value of S is E[S] = E[X]*E[Y] = X/6 , and the variance
of S is
var [ S] = X (2 - 6)/9*
The time required to compute 7T. from (7) is dependent on the size
J
of j. For larger j (e. g. , j > 1000), the computation time could be very-
large and prohibitive. A convenient and less time consuming way to
compute 7T . is from 0 (u) by using the Fast Fourier Transform invertion 5 3 b
method as follows:
IV i
7T. = Y. <f>J r) exp[ -27Tirj/M] 3 rti S
3 = 0, 1, 2, . . . , M-l
where
r = 2ttu/M
M = total number of input points to represent 0 ( r)
b
= total number of output values of n\ .
In order to accurately determine 0 ( r), it is computed with double pi vision
b
on the IBM 360/65. Further, we would like to use as many points as possible
to represent 0 ( r); that is, we would like to make M as large as possible, b
Because of the word length limitation of the computer, double precision
-15
provides 15 -digit accuracy. Therefore, when 7T. < 10 , it is set equal to
-15 ^
zero. M is selected such that it. ^ < 10 . The M' s are different for
3 M
different values of X and £.
To establish the set of state equations for a buffer size of N charac¬ ters, we assume that the system has reached its equilibrium. Let pn be
61
i
the probability that there are exactly n characters in the buffer at the end of a service interval.^ Without loss of generality, we can express the probability of the number of characters in the buffer at the end of the unit service interval in terms of the probability of the number present at the end of the last interval, multiplied by the probability of a given number of characters arriving during the service interval. As this can occur in different combinations, we add the probabilities.
n
pn = ,I0pn+l + .2 Vi+lpi+%pO.
1=1
or
|
p. - ir p_ i n 0 J |
|
|
0, 1, 2, . . . , N - 1 |
(10) |
|
= 1 |
(ID |
and
Pi!N + l = 0
Equation (10) states that after a service interval, there are n characters in the buffer if: 1) there were n + 1 characters in the buffer at the beginning of the service interval, and no character arrived during the service interval;
^Xn queuing theory terminology, the system modeled is one in which there is a gate between the waiting room and the server, which is opened (and instan¬ taneously closed) at fixed intervals. Hence, pn should be understood as the number of characters (customers) in the buffer at the end of a service interval and immediately before the gate is opened.
62
k
or 2) i characters in the buffer at the beginning of the service interval, and n - i -» 1 characters arrived during the service interval, i = 1, 2, . . . , n; or 3) the buffer is empty and n characters arrived during the service interval.
Since the buffer has a finite size of N, P,- > ^ + 1 = 0* As a result, when a character arrives and the buffer is full, an overflow will result. Consequently, the average character departure -rate from the buffer (carried load), a, is less than the average character arrival -rate to the buffer (offered load), /3 = X/0. The carried load can be computed from the probability that the buffer is idle,
a = 1 - PQ (12)
The overflow probability of the buffer, the average fractions of the total number of arriving characters rejected by the buffer, is then equal to
_ offered load-carried load _ of offered load a **
(13)
Traffic intensity, p, measures the degree of congestion and indicates the impact of a traffic stream upon the service streams. It is defined as the ratio of offered load and unit service interval. Thus,
p= p/n = X/(0p) =\J/m (14)
Channel (server) utilization, u, measures the fraction of time that the lines are busy. It can be expressed as
u = ( 1 - PQf) ]3/p -alp s p
(15)
Since physically it is impossible for the transmission line to be more than 100 per cent busy, the utilization is limited to a numerical value less than unity. In the no-loss case, (unlimited buffer size), = 0, then u = p.
The set of state Equations (10) is an imbedded Markov Chain. The state probabilities can be solved iteratively and expressed in terms of p^.
63
The value of can be determined from (11). Thus we can find all the state probabilities. The overflow probabilities for various burst lengths can then be computed from (13). Numerical results are presented in
_6
Figures 1 through 6. Figure 7 provides the relationship (at P 10 )
between burst lengths and buffer sizes for selected traffic intensities.
In the above analysis, we have treated each character as a unit. However, in computing the expected burst delay, D, due to buffering, we should treat each burst as a unit. The service time is now the time required to transmit the entire burst. For a line with constant trans¬ mission rate, the service time distribution is the same as the burst length distribution except by a constant transmission rate factor. Hence, the service time is also geometrically distributed. When the overflow probability is very small, a good approximation for the expected delay can be computed from a queuing model with finite waiting room, Poisson arrivals and single server with geometric service time. The expected
g
burst delay can be expressed in terms of the expected number of bursts in the buffer, L, and the effective burst arrival rate, X = X(l-P ).
6 tx 0 OI
When overflow probability is very small, for example, PQ£= 10 , then
D = = L/X which implies that D can be approximated by the ex¬
pected burst delay of the infinite waiting room, M/G/l, model.7 Hence
^ XE(X2) X(2-0) . . ..
D = zrjz - r - zin character -service times (16)
2(1- p) 2(0-X)0
2
where E(X ) = second moment of burst length, X. The delays are computed from (16) for selected traffic intensities and burst lengths.
Their relationships are portrayed in Figure S.
HI. DISCUSSION OF RESULTS
An interesting property of the state probabilities is that for large n (for example, n t 10), the state probabilities p^ and p^+1 are related by
P7
wpmmmmrnrpm^ _
rn*mm*immmmmmmm*mM!rim,
a constant; that is, Pn+1/Pn= K, where K is a function of traffic intensity and expected burst length as shown in Table I.
TABLE I
VALUES OF K's AT VARIOUS p 's AND i 's
|
Ap |
0.3 |
0.4 |
0.5 |
0.6 |
0.7 |
0.8 |
0.9 |
|
1 |
0. 127 |
0. 198 |
0.285 |
0.388 |
0.509 |
0.650 |
0.813 |
|
2 |
0.619 |
0.664 |
0.712 |
0.763 |
0.817 |
0.874 |
0.935 |
|
4 |
0.818 |
0.842 |
0.867 |
0.892 |
0.918 |
0.944 |
0.972 |
|
6 |
0.680 |
0.897 |
0.913 |
0.930 |
0.947 |
0.964 |
0.982 |
|
8 |
0.911 |
0.932 |
0.936 |
0.948 |
0.961 |
0.974 |
0.987 |
|
10 |
0.935 |
0.939 |
0.949 |
0,959 |
0.969 |
0.979 |
0. 990 |
|
20 |
0.964 |
0.970 |
0,975 |
0.979 |
0.985 |
0.990 |
0.995 |
|
40 |
0.982 |
0.985 |
0.987 |
0.989 |
0.992 |
0. 994 |
0.997 |
|
60 |
0.988 |
0.989 |
0.992 |
0.993 |
0.994 |
0.996 |
0.998 |
The overflow probability depends upon the buffer size, the traffic intensity, and expected burst length. For a given average buffer length, the overflow probability increases as the traffic intensity increases (see Figures 1-6). For a given traffic intensity, as the average burst length increases, the buffer size has to increase in order to achieve the desired overflow probability as shown in Figure 7.
In the above analysis, we have assumed that the burst length is geometrically distributed which takes values from zero to infinity. In practice, however, the maximum burst length is limited to a finite number of characters. Because of the long tail effect of the geometric distribution, the result we obtain here will be more conservative than that of the truncated geometric distribution.
When the average burst length equals unity, then the result reduces
to the case of Poisson arrivals and constant service time as had been
1 2
analyzed by Birdsall, and Dor. For a given traffic intensity, the re¬ quired buffer size for average burst lengths £ ( £ > 1), N . to achieve
Xj
the same degree of overflow probability is much greater than that for
unity burst length, N^, In general, > jjxNj. As J increases, the
difference between N and £ x N increases. For example, for p = . 8,
X* a
mmmrn
65
„ -6
i= 1, the required buffer size to achieve PQf= 10 , is Nj= 28 characters.
When 1=4, then from Figure 7, N^= 212 > 4 x 28 = 112 characters. In the manner, if If-- 20, N = 1200 > 20 x 28 = 580 characters. This is due to
4 u
the fact that the variance of S is proportional to i as shown in (8). Figure 8 portrays the relationship between expected burst queuing delay and traffic intensity for selected expected burst lengths. For a given expected burst length, the expected queuing delay increases as traffic intensity increases; for a given traffic intensity, the expected queuing delay increases with burst length. These. are important factors that affect the delay.
In the above model, the data output from the buffer is assumed to be transmitted on a synchronous transmission system, i.e., the data are taking out synchronously from the buffer for transmission at each discrete clock time. The data arriving at the buffer during the period between clock times have to wait to begin transmission at the beginning of the next clock time, even the transmission facility is idle at the time of arrival. In queuing theory terminology, the above system implies there is a gate between the server and waiting room which is opened at fixed intervals. The result derived from the above system can also be used as a conservative estimate (upper bound) for the case in which there is no gate between the server and waiting room, i.e. , the line is permitted to transmit the characters arrived during the service interval. The estimate yield better approximation for the heavy than light traffic intensity case. Because under heavy traffic case, the line is usually busy and the characters that arrive during the service interval have to wait and cannot be serviced during the service interval. The maxi¬ mum over design of the buffer system with a single transmission line that permits to transmit characters arrived during service interval is one character.
IV. EXAMPLE
Consider the design of a time -sharing computer system with many remote terminals which employs the Asynchronous Time Division Multi-
g
plexing Technique to transmit data from the central processor to the
66
user terminals (Figure 9). A typical computer -to -user data stream is
shown in Figure 10. Measuring the traffic statistics from several oper- 4
ating systems revealed that the burst interarrival time from central processor to each user can be approximated as exponentially distributed with a mean of 2. 84 seconds; that is, the bursts can be approximated to be generated from a Poisson process with a rate of X = 0. 35 bursts/sec. Further, the burst length can also be approximated as geometrically distributed with a mean c IS, =20 characters. All the terminals are assumed to be independent and to have identical traffic characteristics.
A reasonable and conservative estimate is that 20 per cent of the trans¬ mitted information is to be used for addressing and framing. Under these conditions, suppose a full duplex transmission line that transmits 480 char/sec is used to provide communications from the central proc¬ essor to the 46 terminals, then the traffic intensity p = 1. 2 • 46 *X • S, /p ~ 0. 8.
-8
To achieve an overflow probability of 10 , from Figure 7, we find that the
required buffer size is 1,650 characters. From Figure 8, the expected queuing delay for each burst is 80 character -service times, or 80/480 =
0. 167 seconds.
Suppose now we changed our transmission rate from 480 to 960
char /sec; then the traffic intensity p w 0.4. The corresponding required
•8
buffer size in order to achieve an overflow probability of 10 is 580 char¬ acters, and the delay is 13 character -service times or 14 milliseconds. Thuf;, these results provide insight regarding the trade off between trans¬ mission costs and storage costs as well as the relationship between expected burst queuing delays with transmission rates.
ACKNOWLEDGMENT
The author wishes to thank S. P. Bader of Bell Telephone Labor¬ atories for his programming assistance.
67
'B*jR
■•w r»*n !*nw*^q ^T’JTW^T^T^f ^,PJl
'".;• '| jfW'' ' m '"')/•*• 1 *1
ifffftm
REFERENCES
1. T. G. Birdsall, et. al. , "Analysis of Asynchronous Time Multiplexing of Speech Sources," IRE Trans, on Communications Systems, pp. 390- 397, December 1962.
2. N. M. Dor, "Guide to the Length of Buffer Storage Required for Random (Poisson) Input and Constant Output Rates," IEEE Trans, on Electronic Computer, pp. 683-684, October 1967.
3. W. W. Chu, "Buffer Behavior for Poisson Arrivals and Multiple Synchronous Constant Outputs," IEEE Transaction on Computers,
June 1970.
4. E. Fuchs and P. E. Jackson, "Estimates of Distributions of Random Variables for Certain Computer Communication Traffic Models," Pro¬ ceedings of ACM Symposium on Problems in the Optimization of Data Communications Systems, pp. 201-227, Pine Mountain, Georgia,
October 13-16, 1969.
5. W. M. Gentleman and G. Sande, "Fast Fourier Transforms - For Fun and Profit, " Proc. AFIPS 1966 Fall Joint Computer Conference, Vol. 29, Spartan Books, New York, pp. 563-578.
6. N. U. Prabhu, Queues and Inventories, John Wiley & Sons, Inc. , p. 42, 1965.
7. J. D. C. Little, "A Proof of the Queuing Formula, L = AW," Opns. Res.
9, pp. 383-387, 1961.
'8. W. W. Chu, "A Study of the Technique of Asynchronous Time -Division
Multiplexing for Time -Sharing Computer Communications," Proceedings of Second Hawaii International Conference on System Sciences, pp. 607 - 610, Honolulu, Hawaii, January 22-24, 1969.
69
KEY PHRASES
Queuing Theory
Buffer Design
Time -Sharing Systems
Computer Communications
Asynchronous Time Division Multiplexing
Overflow Probabilities
Queuing Delay
Statistical Multiplexor
Concentrating Multiplexor
70
oetwwiwwBiaawjHw
Figure 1 Figure 2 Figure 3 Figure 4 Figure 5 Figure 6 Figure 7 Figure 8 Figure 9
Figure 10
FIGURE CAPTIONS
Buffer Length Versus Overflow Probabilities, Z- 2 Characters
Buffer Length Versus Overflow Probabilities, i=4 Characters
Buffe ’ Length Versus Overflow Probabilities, Z =10 Characters
Buffer Length Versus Overflow Probabilities, Z =20 Characters
Buffer Length Versus Overflow Probabilities, Z =40 Characters
Buffer Length Versus Overflow Probabilities, i!=60 Characters
*6
Buffer Length Versus Average Burst Length, Pq^= 10 Traffic Intensity Versus Expected Burst Queuing Delay Asynchronous Time Division Multiplexing System for Time -Sharing Computer Communications Asynchronous Time Division Multiplexing Data Stream
2
BUFFER LL'i'GTH (CHARACTERS), N
FIG. / BUFFER LENGTH V3 OVERFl.O'.V F’RO“'/.r.!L!TIES, <! = 2 CHAR AFTER
OVERFLOW PROBABILITY, P0f
£JO 60 CO 100 120 140 160 ICO 200 22 0 240 260 200
BUFFER LENGTH (CHARACTERS), M
FIG. 1 BUFFER LENGT H VS OVERFLOW PROBABILITIES, / « 4 CHARACTERS
74
FLOW PROBABILITY, P0f
FIG..’ BUFFER LENGTH VS OVERFLOW PROBABILITIES, -t = 10 CHARACTERS
OVERFLOW PROBABILITY, P
OVERFLOW PROBABILITY, Pof
FIG. 5 BUFFER LENGTH VS OVERFLOW PROBABILITIES, / =40 CHARACTER
pun rr lc?!CTh ( c :•!.*. rciCTE ns y
BUFFt.’R LENGTH VS OVERFLOW RRORACILITIES, £ = CO CHARACiERS
COMPUTER COMMUNICATION'S
|
ADS |
ADDRESS |
|
E |
F.ND OF MESSAGE |
|
MESSAGE |
FIG. 10 ASYNCHRONOUS TIME DIVISION MULTIPLEXING DATA STREAM
APPENDIX E
SELECTION OF OPTIMAL TRANSMISSION RATE FOR STATISTICAL MULTIPLEXORS
by
Wesley W. Chu
Wrmrmrmm
SELECTION OF OPTIMAL TRANSMISSION RATE FOR STATISTICAL MULTIPLEXORS*
Wesley W. Chu Computer Science Department School of Engineering and Applied Science University of California Los Angeles, California
70-CP-329-COM
Summary
In the design of statistical multiplexors for computer communication networks or time sharing systems, one of the important consider¬ ations is the design trade-off between transmis¬ sion rate and buffer size. For a given traffic arrival rate and required system performance (buffer overflow probability and buffer queuing delay), the higher the transmission rate of the channel, the lower the required buffer size but higher communication cost. Assuming the rela¬ tionships among overflow probability, queuing delay, anj) buffer size are known, a model is developed in this paper to determine the optimal transmission rate for a statistical multiplexing system such that the operating cost (defined as the sum of communication costs and storage costs) is minimum yet also satisfies the required system performance.
Introduction
' In order to reduce communications cost in computer communications systems, the Asynchronous Time Division Multiplexing tech¬ nique has been proposed. ** In designing such a statistical multiplexing system, one of the important ccst trade-off considerations is the selection of optimal transmission rate for the communications channel. 3 Traffic intensity, p, is commonly used to measure the congestion of the line and can be computed as the ratio of the input traffic load, 0, to the transmission rate of the channel, R. For a given 0 (in same unit as R), a higher transmission rate channel yields a lower traffic intensity, and thus requires a smaller buffer size. On the other hand, a lower transmission rate channel yields a higher traffic Intensity and requires a larger buffer size, 2* 3 Thus, there is a trade-off between communica¬ tions cost and buffer storage cost in the design of statistical multiplexors. Assuming the rela¬ tionships among overflow. probability, expected queuing delay due to buffering, traffic intensity, and buffer size are known, and we are given the input traffic load and communication distance d, the problem is to operate the multiplexing
''This research was supported by the Advanced Research Projects Agency of the Department of Defense (DAHC 15-69-C-0285).
system at an optimal traffic intensity. This problem is equivalent to selecting the transmis¬ sion rate of the communication channel such that the operating cost (defined as the sum of trans¬ mission cost and storage cost) is minimized subject to achieving required multiplexing per¬ formance, e. g. , that overflow probability and average queuing delay due to buffering be less than certain values.
In this paper, an analytical model is de¬ veloped to analyze this problem.
v Analysis
The operating cost of a statistical multi¬ plexing system, C, can be separated into two parts - communication cost and storage cost. For a given distance, the communications cost depends upon thc transmission rate of the chan¬ nel. Hence, for a given input traffic load and distance, the transmission cost is related to the traffic intensity of the channel. The higher the traffic intensity, i. e. , the lower the transmis¬ sion rate, the lower the communications cost. Thus, the communications cost per month, Ct(p) is a monotonic decreasing function of p as shown in Figure 1. Further, C|(p) can be easily gen¬ erated from 0 and the channel costs of the set of available transmission rates. Since there is a practical upper limit on the available transmis¬ sion rates, p can never reach zero. We sh;>'!> denote the minimum p as Pmin. To represent Cf(p) as a mathematical expression, the least squares polynomial curve fitting technique3 may be used. i. e. ,
2 in
ct (p) =ao+aip+a2p +... + aip+V>
for Pmin Sp<1 (,)
where a. ■ constant coefficients, i ■ 1, 2, . . . , n. Since only a limited number of transmission ' rates exist or planned, the set of points {(pj, Ct(pj) ) j ■ 1, 2, . . ,}can be determined and used to solve for the aj's in (1) for each distance d.
To achieve a certain probability of overflcv, Pof. at a certain traffic intensity p, the require buffer size, N(p, PQf) is dependent upon the message characteristics and the channel trans¬ mission rate. The quantitative relationships
85
of N(p, P0f) with p and P0f can be obtained from an analysis of a queuing model with a finite waiting room. For example, when the messages can be approximated as Possion ar- livals and the message length is geometrically distributed, the buffer behavior has been ana¬ lyzed in Reference 2. The relationship between buffer size with traffic intensity at a given prob¬ ability of overflow can be obtained. Few typical of such relationships are portrayed in Figure 2. We note that the required buffer size increases with traffic intensity and is a monotonic increas¬ ing function of p. Further, the required buffer hize increases when allowable buffer overflow probability decreases.
The storage cost per month is then equal to the monthly cost* of a unit of storage, Cb, multiplied the required buffer size, N(p, P0f). l. e. , Cs(p) <= Cb • N(p, P0f). To represent N'(p.P0f) as a mathematical expression at a iven overflow probability, we shall again use the least squares polynomial fitting technique. Thus,
csWtcb'iwbA-vra)
forpmin£p<1 (2)
where bj = constant coefficients, i"l, 2, . . . , m.
For a given input traffic load, required buffer overflow probability, and transmission distance, the operating cost is the algebraic sum of (1) and (2). Thus,
C(p) - C s(p) + Ct(p) for pm.n5 p < 1 (3)
D(p) S Da is equivalent to p i p where pma„ is the maximum allowable trafrxc intensity suen that the expecting queuing delay is still less than or equal to the maximum allowable delay. Pmax can be obtained either from the buffer delay characteristic curves** ^ or from the analytical expression of expected delay function. For most multiplexing system, the buffer is designed to allow very small overflow probability - less than lO*4. Thus, using the analytical expression of expected queuing delay derived from infinite waiting room to determine p_ax yields a good approximation. Thus (4) can be further reduced to /
rain C(p) * min(<*0+ o p +... + «, p* ] P P
'or *min ® * “ *m»x where l ■ max[m,n]
(5)
ai+ bj
for OSiSk, k*mln(m,n] 1 > k and n > m i > k and n < m
Let us now study the property of (5). Geo¬ metrically we know that Cs(p) is a monotonic decreasing function of p. Thus the sum of these two functions, C(p) is a convex function of p as shown in Figure 3. The least squares fitting of the functions C8(p) and Ct(p) might Introduce noise in the function, however, if enough terms are used to represent these functions, C(p) can be approximated as a convex function of p. This assures a'unlque optimal traffic intensity, p°, exists that yields minimum operating cost.
Wc wish to minimize C(p) with respect to p .ind subject to the delay requirements; that is,
C = min C(p) « min (Cg(p) + Ct<p) J P P
subject to D(p) £ D for p , S p< 1 (4)
a min
There are many methods that can be used to numerically solve (5) and to obtain p°, such as convex nonlinear programming, 6 geometric programming7 (if all the arj's are positive), or finding the set of p's that satisfy [dC(p)/dp] = 0 and pmin £ p 5 Pmax. P° is the one that mini¬ mizes the cost function (5).
where
D(p) * expected queuing delay of each mes¬ sage due to buffering
D * maximum allowable expected queuing delay of each message
Note that the overflow probability requirement is satisfied automatically as (2) is represented from the corresponding overflow probability.
Since in almost all the queuing models, l)(p) is a monotonlc increasing function of p,
’The monthly cost of a unit of storage can be computed from the life of the system.
The optimal channel transmission rate for the statistical multiplexor, R°, can be computed from p° and input traffic load 0; that is,
R° * 0/p° bits /sec (6)
Discussion of Model
From (3), we noticed that for the case in which the transmission distance between com¬ puters and/or terminals is very short, then the communication cost, compared to the stor¬ age cost, is relatively low.. As a result, the storage cost becomes the dominant factor that
86
Influences the selection of the optimal transmis¬ sion rate. Under thls case, the statistical muti- plexor is said to be storage bound. On the other hand, when the transmission distance is very long, then the transmission cost becomes the dominant factor that affects the selection of op¬ timal channel transmission rate. The multi¬ plexor is then said to be channel bound. Under certain transmission distance, (e.g. Figure 3) both transmission cost and storage cost carry equal weight in the selection of the optimal transmission rate, the multiplexor is then said to be operated under balanced condition.
Although the model introduced in this paper is mainly for a statistical multiplexor that has a single transmission line output, it can be generalized to that of the multiple transmission lines case. C^(p) in (3) should now be viewed as the total transmission cost of the multiple trans¬ mission lines as a function of traffic intensity, Cs(p) is the storage cost of the buffer (with multiple outputs) to achieve a desired level of probability of overflow. For a given system configuration; i.e., the number of output trans¬ mission lines and their transmission rate, based on the above model, the optimal transmission rate and the corresponding operating cost can be determined. We are now not only treat the design tr;' e-off between storage cost and trans¬ mission cost, but also should consider the trade-off between various system configurations such as whether we should use more slower trans¬ mission rate lines or fewer high transmission rate lines. The optimal system configuration is the one that yields minimum operating cost among the set of possible system configurations.
Conclusion
An analytical model has developed to treat the cost trade-off between buffer storage cost and channel transmission cost. The choice of optimal channel transmission rate depends on many parameters, such as the input traffic load, transmission distance, required buffer overflow probability, maximum allowable expected queu¬ ing delay, cost of unit of storage, transmission cost per miles per month, and availability of channel transmission rates. These parameters closely interact with each other. The analytical
formulation of the model can also be solved geometrically, as shown in Figure 3. By properly selecting the channel transmission rate, the statistical multiplexor will operate at optimal traffic intensity and so yields the mini¬ mum operating cost yet satisfying the system performance requirements. The model should provide a useful guide line in selecting the opti¬ mal channel transmission rate for the Asynchronous Time Division Multiplexing systems.
References
1. W. W. Chu, "A Study of Asynchronous Time Division Multiplexing Technique for Com¬ puter Communications," Proceedings of the Second International Conference on System Science, pp. G07-C10, Jain. 22-24, 1960, Honolulu, Hawaii.
2. W. W. Chu, "A Study of Asynchronous Time Division Multiplexing Technique for Time Sharing Computer Systems," Proceedings of FJCC, Vol. 35, pp. 669-678, 1969.
3. W. W. Chu, "Design Considerations of Sta¬ tistical Multiplexors," Proceedings of ACM Symposium on Problems in the Optimization of Data Communication Systems, Pine Mountain, Georgia, pp. 36-60, Oct. 13-16, 1969.
4. R.G. Gould, Comments on "Generalized Cost Expressions for Private-Line Com¬ munications Channels," IEEE Transactions on Communications Technology, Sept. 1965, pp. 374-377.
5. Hamming, Numerical Methods for Scientists and Engineers, McGraw-Hill Book Com¬ pany.
6. G. Hadley, Nonlinear and Dynamic Pro¬ gramming, Addison- Wesley Publishing Co, , Inc., 1964.
7. R.J. Duffin, E.L. Peterson, C.M. Zener, Geometric Programming, John Wiley & Sons, Inc. , 1967.
APPENDIX P
COMPUTER NETWORK STUDIES by
Gary Fultz
89
APPENDIX P
COMPUTER NETWORK STUDIES
In the study of the performance of networks of computers such as the ARPA Network, the basic performance of the total system will be governed, on the lowest level, by the message handling capability of the store-and- farward conmunication network interconnecting the computers . In order to analyze the message handling capability of the network, message routing strategies within the network must be examined. Before routing is examined, one must first be able to model and analyze the network performance either mathematically or via simulation.
From the above requirements, we have determined six areas which should be investigated to determine the conmunication network message handling capability. These areas are:
1. Conmunication network performance measures
2. Store-and-forward conmunication network modelling
3. Message routing techniques
4. Message flow control and acknowledgment procedures
5. Computer network simulation
6. Network topological design
Of these six items, we have actively pursued investigation of the first five items and are now beginning investigation of the sixth. The following dis¬ cussion and presentation of results will, for the most part, assume a fixed network topology with 50 KBPS conmunication links, with IMPS as nodes, and with HOSTS as the sources and sinks of messages .
91
a. _
9*
As Klelnrock pointed out, one of the basic goals In the design of ccnmunication networks Is to
minimize
N X.
T "Y — T
J
capacity assignment routing procedure priority discipline topology
(1)
subject to a cost constraint. Here T is the average message delay, X^ Is the average number of messages per second arriving at channel 1, is the delay sufferred at channel 1, and y is the total arrival rate of messages entering the network from external sources.
Before the minimization of T can be carried out, we must first determine the validity of Eq. (1) in predicting the average message delay for store- and-forward ccnmunication networks and then understand how the minimization parameters effect T.
I. Store -and-Forward Ccrrmunlcatlon Network Performance Measures
We have formulated ccnminication network performance measures which can be related to either mathematical models or to simulation experiments. The measures are:
1. Average message delay for the network
2. Average message delay for a particular source HOST-destination HOST pair
92
8
3. Bounds on the Pr (average message delay > Tq).
4. Node storage requirements.
5. Packet blockage due to finite node storage.
6. How the routing doctrine, queue structures, message prior¬ ities, node storage size, network connectivity, and message blocking effect message throughput in the network.
In order to calculate those parameters which effect the performance measures, we must be able to model the network in order to make it amen¬ able to mathematical analysis.
II. Store-and-Forward Ccnmunlcatlon Network Modelling
Listed below are some of the models we have been considering and the analytical results we have obtained.
A. Average Message Delay Model
The basic problem is to calculate the average message delay as given by Eq. (1). We have assumed a priority system where acknowledgments have the highest priority, singlepacket messages the next lowest priority, and long message, the lowest priority. The traffic matrix entries are given at a design point. We will then consider scaling all entries in the traffic matrix by RE (the effective rate). RE * 1 corresponds to the design point. We will also assume that the mix of short messages and long messages is given by M and 1 - M, respectively.
1. Short Message Model (maximum of one packet each)
Hie equation for the calculation of the average message delay
is given by
93
(2)
T ■
+ )
+ TL, + T
cpu
+
T
cpu
where
wi<Vi
UA 2
\ it + \ r* (1 + V
(l-p. ) (l-p. -Dp )
Ai Ai *i
and
WA Ri Up
is the data rate in line i and is the data rate flowing in the opposite direction of the fully duplexed line i
C - Channel capacity of all lines in bits per sec.
Up ■ E C Packet Length] in bits
n
P ■ Packet coefficient of variation UA ■ Acknowledgment length in bits TL^ ■ Propagation time of line i
And T » The average processing time of a packet by the cpu routine in
cpu
each node.
Figures 1 through 4 show the theoretical and experimental results for T versus RE for four different network configurations. These results show that Eq. (2) is a reasonably accurate prediction of the average message delay.
94
UU«M4>.tU
J
2. Long Message Model
In the long message model, messages can be two through eight packets In length. In addition, files can be composed of many messages. Here we wish to calculate the average message delay. Per file structures, the average message delay is calculated assuming all messages contained in the file are created at the same time. Message reassembly time must also be considered.
The model, denoted as Ml, is given by
' £ + wp1'Ri»Ri) + + Tcpu
+ T_
epu
tm * r ♦ wh1(ri*ri) + *4 + T,
epu
+ T
epu
W:
Tp * Average message delay for single packet messages Tm * Average message delay for long messages and files Ujyj ■ length of a full packet in bits
wP1(Rl'Ri) - jr + PPj !T (1 + CP> + tfo1(1
(1 - pa ) (l - P. - PP )
'i \ *1
(1 - M)^i
MR^
\ " ~
My
.*5
t _
a y a Rj
A + (1 - M)
C
\(Ri»V " I [PA, CA + PP, C (1 + °P) + + C
U - pA - Pp ) (1 - PA - Pp - Pm ) Hi ri rti ri i
99
S2 - krf u + CI ) - 1 r
j L^M ZJ JRi
Rj ■ Node I Input data rate from its host
PT ■ % of Rt destine to node j which flows on line i
2
Uj ■ Ejmessage length] destine to node J from node I on line i
J
0/
CT2 - A ■ Coefficient of variation
J %
RAT ■ Average message reassembly time
In addition to this model, we have considered a second model, denoted as M2, which will not be discussed in detail. Cnly the conputational re¬ sults of M2 will be presented. Table 1 shows the theoretical and experi¬ mental results for the long message case and Table 2 shows the results for the file transmission case.
Prom the tables, we see that Tp is reasonably predicted, but the theoretical predictions for are generally too small. Improved models to predict Tm are currently being developed.
B. Node Storage Sizing
Let us now consider the average storage 3^ required per unit time for each node I in the net and the VARCSj).
For each packet flowing throu#i a node, we detemine the amount of time Ts the packet requires storage (assuming L bits in the packet). For packets arriving at a rate A. per sec. ,
100
TABLE 1
LONG MESSAGE TRANSMISSION MODEL
M « .25 M - 0.0
|
FE |
Model |
Tp(msec) |
TM(msec) |
TM(msec) |
|
1.0 |
M2 |
148.2 |
158.94 |
188.4 |
|
Simulation |
50.9 |
270.19 |
258.2 |
|
|
Ml |
56.6 |
178.9 |
188.4 |
TABLE 2
PILE TRANSMISSION MODEL
|
M - |
.85 |
M - |
.75 |
M - 0 |
||
|
RE |
Model |
Tp(msec) |
TM(sec) |
Tp(msec) |
TM(sec) |
TM(msec) |
|
M2 |
47.3 |
445.2 |
||||
|
.75 |
Simulation |
47.8 |
419.2 |
|||
|
Ml |
60.3 |
466.8 |
||||
|
M2 |
49.6 |
451.9 |
||||
|
.9 |
Simulation |
50.6 |
552.6 |
|||
|
Ml |
67.5 |
488.4 |
||||
|
M2 |
51.6 |
459.9 |
55.1 |
467.9 |
615.8 |
|
|
1.0 |
Simulation |
60.6 |
806.5 |
61.7 |
790.3 |
807.1 |
|
Ml |
73.8 |
514.7 |
84.7 |
537.8 |
615.8 |
101
Tg , with its associated Xj and Lj must be calculated for three separate
J
cases: (a) packets arriving on node Input lines, (b) packets exiting on node output lines, and (c) packets being transferred between the node and Its associated HOST.
Theoretical equations have been derived for 3^ for the single packet message case and seme preliminary hand confutations have shown that the theoretical model and simulation results agree very well. When the analysis for Oq Is completed, these equations will be progranmed and confuted as a function of the effective net data rate HE.
We must extend the model to Include the effect of long messages.
C. For the rest of the performance messages listed In Section I, only a small amount of effort has been expended to date on their calculation. Therefore, no definitive results are worth mentioning at this time.
102
III. Message Routing Techniques
We have classified message routing techniques into three categories:
1. Fixed routing techniques.
2. Local Routing techniques.
a) A node only has information about network congestion and delay from messages passing through it.
b) A node has the same information as (a) above plus it3 queue lengths and has access to its nearest neighbor node delay tables.
3. Global routing techniques.
a) Network routing control center (NRCC) . Hie NRCC calcu¬ lates routing tables for each node in the network.
b) Ideal observer routing. Knowing the events which will occur in the future, calculate the message routing to minimize T. This is a scheduling problem.
Hie analysis problems being considered are:
1. Routing algorithm specification.
2. Routing algorithm performance measures.
a) T (function of routing algorithm).
b) Stability and convergence of the algorithm.
c) Looping phenomenon (packets trapped in loops).
d) Adaptability of the algorithm to network changes.
3. Interrelationship between specific routing algorithms and the
network topology.
103
Rand has extensively investigated the local, Type A, routing algo¬ rithms. To date, we have investigated the fixed routing algorithms and the local. Type B, routing algorithms. Below, we discuss our results in more detail.
Fixed Routing Techniques
1. Evaluation of average message delay. The results of this investi¬ gation were presented in Section II.
2. Fixed routing matrix solution technique.
Problem
N X.
Minimize T(HE) - £ T. (3)
{R.M.} 1-1 Y 1
subject to link capacity constraints ■ C. R.M. is the fixed routing matrix for the network. This problem is essentially a multicommodity flow problem with non-linear cost constraints .
The computational technique for this algorithm will not be given here, but is rather simple and requires few iterations. Figure 5 shows the results of the algorithm. Each curve represents T versus RE for the R.M. that minimized Eq. (3) at a specific value of RE. The lower envelope of all the curves then represents the solution to Eq. (3) for all RE. The only theoretical solution point we knew is Tgp, the solution to any of the shortest path algorithms for RE ■ 0.0.
104
mmmmm
MRCIMRPRMIIiniBNMnMMIIHPniMMIHMVRWMIHniMIHRpiinipn)
RE
Figure S. Minimization of T(RE)
105
wmmm
Caiments on the operation of the algorithm follow. Let TR be the solucion to Eq. (3) for the Kth iteration of the algorithm.
1. Par small RE, the algorithm converges (TK+1 ■ TR).
2. For medium RE, the TK’s oscillate in seme random manner.
By letting K be large, we can find T ■ Min (Tq,!^, ..., TR).
3. For large RE, the algorithm wants more line capacity than is available.
We intend to modify the algorithm to improve its operation.
Local, Type B, Routing Techniques
All of the local routing algorithms operate in a similar manner. A delay table is constructed in each node as shown in Figure 6. The entries Tj(N,K) are the estimated delays to go from node J to node N, exiting the node on line K. The best route would be selected by picking the line number whose row entry is minimum for the selected row (destination) .
We have considered two types of local algorithms. The first is called the periodic updating algorithm and the second is called the asyn¬ chronous algorithm.
Periodic Updating Algorithm Operation
1. Routing is held fixed for K Msec.
2. Then modify the delay tables by the change in the line queue lengths during the K Msec, period.
A
3. Form a vector M which contains the minimum T’s from each row.
4. Transmit the M to all nearest neighbors.
106
NODE OUTPUT LINE NUMBER
107
5. When a node receiving the M's frcm its neighbors, it adds its current queue length plus a delay factor Dp to all entries and places it in the proper column of its delay table.
6. After all M's are received, find the line nunber for each destination which corresponds to the minimum delay estimate for a row.
7. Hold this fixed route selection for the next K Msec.
This algorithm suffers frcm looping and is only stable for Dp > a couple of E[packet lengths] for K ■ 500 Msec. The parameter Dp controls the degree of alternate routing.
Asynchronous Updating Pouting Algorithm Operation
1. Minimum delay route picked on a per packet basis.
2. Delay tables are constantly updated by queue length changes.
3. If delay table entries change by more than a preset threshold, the vector M is formed, and the node's nearest neighbors are informed of the change.
4. If a node receives a vector M, the delay table is updated as in Step 5 of the periodic updating algorithm.
The algorithm's stability is a function of Dp and the threshold setting.
Figure 7 shows the performance of the adaptive routing techniques for the 19-node net shown in Figure 1 and for RE * 1.0. An attempt was
108
I
r*»m«
200 f
100 f-
M
S
E
C
LOOPS NOT SUPPRESSED
LOOPS SUPPRESSED
PERIODIC UPDATING (M = 1.0)
Figure 7. Local, Type B, Routing Algorithm Performance
109
made to suppress looping In the periodic updating algorithm, but did not significantly inprove the performance of the algorithm. We are continuing the investigation of this class of routing algorithms.
IV. Message Flew Control and Acknowledgment Procedures
Strategies must be specified to aid in the control of message flow through the network. These strategies will be coupled into the routing doctrine and models. Seme of the facets which are being considered are:
1. Node input choking.
2. Message priorities.
3. Links down. k. Nodes down.
5. Node storage not available for relay traffic.
6. Information to be carried by acknowledgjnent messages.
7. Classes of messages used only for network control functions.
110
1
APPENDIX G
DYNAMIC STORAGE ALLOCATION FOR BINARY SEARCH TREES IN A TWO-LEVEL MEMORY
by
Richard Muntz and Robert Uzgalis
111
nuntz and Uzgalis
DYNAMIC STORAGE ALLOCATION FCR BINARY SEARCH T%EES IN A TWO-LEVEL MEMORY
Richard Muntz and Robert Uzgalis Departnent of Computer Science,
School of Engineering and Applied Science, University of California, Los Angeles.
Summary
Binary search trees have long been recognized as useful structures for storing and retrieving data. When the tree is too large to be stored in main memory,, the cost of accessing portions of the tree in secondary storage .becomes a critical problem. It is assumed here that transmissions from secondary storage to main memory are accomplished in fixed size units called pages. In this paper we propose an heuristic for allocating storage to the nodes of the search tree so as to minimize the average number of page requests necessary to search the tree. This method of allocation' is compared with a sequential allocation algorithm. Experimental and analytic results are presented.
Introduction
In the binary search trees we consider, each node contains a data item. In many applications the data items to be stored are not all available initially but are received in some arbitrary order. It is this latter case we assume in this paper. It is clear that when the tree is constructed dynamically as the data is received, the structure of the tree is determined by the order in which the data arrives. An example is text analysis in which the data is the word to be stored. The purpose might be to count the number of occurrences of words in the text vocabulary. Although many common words may be placed in the tree initially (viz. *a', 'the') most of the vocabulary will be added to the tree as it is encountered in the text.
When the search tree can be stored in main memory the most important characteristic of the tree is the average number of nodes that must be interrogated to locate a data item. However, when the tree is stored in secondary storage the average number of accesses to secoiidary storage becomes the critical measure of performance. It will be assumed here that secondary storage consists of a sequence of fixed sized blocks called pages. Each access to secondary storage is a request for one page to be
113
Huntz and Uzgalis
transmitted to main memory. The time required to search the tree will be largely a function of the number of distinct pages that are referenced in a search path, i.e. the number of page transitions. The number of pages referenced is determined partially by the method of allocating storage to nodes. Since the tree grows dynamically the method of allocation must be dynamic.
B£scijp.£ifii),o£_Allfi£fltigfl_iashfllgus§
We now describe two methods of allocating storage to nodes as they are added to the tree. The first method, Ssaueptiai Allocation, ignores page boundaries and allocates storage for new nodes in consecutive locations as they are received. This is certainly the most straight forward allocation scheme. Note however that the nodes on a given page are related by locality in the input sequence and not necessarily by locality in the tree.
The second method. Grouped Allocation, explicitly takes page boundaries into consideration. When adding a node to the tree we first locate the node to which the new node will be linked. This node will be the father of the new node in the search tree. If the father node is on a partially filled page then the new node is allocated space on this page. If the father is on a full page then a new page is allocated to the tree and the new node is allocated at the beginning of this page. The first node allocated on a page is called the §££fl_ng3e for that page. Note that, only nodes in the subtree of the seed node will be allocated to this page. It is clear from this description that nodes on the same page will be related by locality in the search tree and intuitively we expect this scheme to result in fewer page transitions.
114
Muntz and Uzgalis
An example is given below to illustrate the two allocation schemes just described.
.S£i!I2£l®
Page .size = 3 nodes
Input sequence 10, 6, 12, 5, 15, 9, 2, 13.
The dotted areas indicate nodes on the sane page. If all nodes are accessed with equal probability the average number of page transitions in a search is 15/8.
Slflll£Sa_Aliocation
i - — - — - 1
Average number of page transitions in a search is 13/8.
115
Buntz and Uzgalis
The grouped allocation scheme will in general result in extra pages allocated for storage of the tree. However, a imple aodification can be made to the algorithm which effectively eliminates this disadvantage. Since this modification would complicate the comparison of the methods unnecessarily, we will first discuss results for the two schemes as described. The modification to the grouped allocation technigue will be dis¬ cussed later.
£<2J!£aiis£J)-2£-All^ti£jOS£lLQi2ges
ABflXfiiS-flodsls
We will need the following definitions and results. The nodes of the binary search tree will be called internal nodes. For every internal node that has a null left (right) link we add an external node as the left (right) successor of that node. In the illustration below the circular nodes are the internal nodes and the sguare nodes are the external nodes.
We define the path _ length to a node (either internal or
external) as the number of internal nodes on the path from the root of the tree to that node. The ayeygflg. internal ...(external), path lepqth is the average path length to an internal (external) node. For example, the root itself has a path length of one. Given that a binary search tree contains N internal nodes, there are N! sequences in which these nodes could have been entered in the tree* Each of these sequences we assume is equally likely. Formulas for the average internal and external path lengths, over all possible input sequences have been derived by Hibbard1 and are given below.
For a binary search tree containing N internal nodes the average internal path length, denoted by jf ( N) , is approximately
I(N) » 1.4 log (H) -1.7
116
liuntz and Ozgalis
For a binary search tree containing _.N internal nodes the average external path length, denoted by J* (N) , is approximately
jp (N) =jt(N)+1 = 1.4 log (N) -0.7 Sequential Allocation
Me have developed the following analysis to estimate the mean number of page transitions necessary to locate a node when the sequential allocation scheme is used, let N be the number of nodes in the tree and let p be the number of nodes in a page. The nodes are assumed to be referenced with the same frequency.
Let r be some positive integer. After rp nodes have been entered in the tree, the range of key values has been partitioned into rp+1 regions. Of the next p nodes to be added to the tree, only those that fall in the same region will be linked together in the tree. For a moderate value of r we would expect very few nodes in the page to be linked together. He will use the approximation that after the first two pages each node that is interrogated on a search path requires a new page reference. This choice was made to simplify the analysis. Clearly this approximation will lead to a somewhat pessimistic estimate of the mean number of page references.
Nodes in the first page require only one page reference in their search paths. Nodes in the second page require two page references in their search paths. The nodes in the other pages require a reference to page one since the root of the tree is in page one. However, a reference to page two may not be necessary. It is shown below that for nodes outside the first two pages an average of approximately three-fourths will have search paths which pass through the second page (i.e. at least one node on the search path is in the second page) . Therefore these nodes have an average of 1.75 page references to pages one and two.
A complete formal proof of this statement would be rather long so we offer the following simplified argument. Consider N boxes labled in order with the N data keys of the search tree. Let the p nodes in the first page be represented by p black balls and the p nodes in the second page be represented by p red balls. Placing these 2p balls in the boxes in some random order, no more than 1 ball to a box, represents the tree after the first two pages are filled. Now consider an empty box (which represents a node that will be outside of pages one and two). He leave it to the reader to show that the path to this n.ode will contain a node from page two if and only if the first filled box to the left or right of this box contains a red ball (i.e. the coxresponding node in page two). Since there are an equal number of red and
117
Muntz and Uzgalis
black balls and they are distributed randomly the probability of the first filled box to the left (or right) containing a red ball is approximately 1/2. Therefore the probability of a red ball in the first filled box in either direction is approximately 3/4.
For that portion of the search path that is outside pages one and two, we assume that each node requires a page reference. Therefore we need to calculate the mean path length for nodes outside the first two pages and then subtract the mean length of the portion of the search path in pages one or two.
Let the mean path length of nodes outside of pages one and two be denoted by L. Then
Hn) -^r(2p) +^L ■ L ■ tpzp >3 !
The mean length that must be subtracted from L is just the mean external path length for a tree with 2p nodes, i.e. X* (2p) . Therefore the average number of page references reguired by nodes outside the first two pages, denoted by a, is
a - 1.75 + L - X’(2p)
“ * U75 t H=2p TO - Xt2p) - T‘(2p) ’ using &'(2p) ■ T(2p) + 1 we get
“ ’0l75 * (PJp C*tK> * *(2p)]
Since we also know the number of page references reguired by nodes' in pages one and two, we can compute the average number of page references for the entire tree (denoted S(N,p)).
■ p+2p+(N+2p)[0.75+,j4j- (X(N)-t(2p)» ’
!S{N,p) - ■ . . jj v " . .
?(N,p) - ^ * ’Q— -5jl + I(N) - I(2p)
?(N,p) ■ 0.75 + ir i,4 iog2 (|j5*)
Grouped allocation
In the grouped allocation technigue each page contains the top portion of a subtree in the search tree. The average internal
118
Muntz and Uz galls
path length in the search tree can fce approximated by1 1.4 log4(N) -1.7. The average external path length within a page is similarly approximated by 1.4 log4(p)-0.7. Therefore a crude estimate of the average number of page transitions in a search path (denoted G(N,p)) is
ff(N. P)
1.4 log2 (N) - 1.7 i74 "log2 (p) - 0.7
These two formulas and experimental results for N * 2048 and various page sizes are illustrated in figure 1.
Modified Group allocation
As mentioned previously the grouped allocation scheme can result in many sparsely filled pages allocated to the search tree. If the total size of the search tree is known or can be estimated the grouped allocation scheme can be modified to limit the number of pages allocated. The method is simply to allocate new pages to seed nodes until there are no more pages available. After this, seed nodes are allocated to partially full pages. The selection of a page in which to plant the seed node is selected so as to distribute them evenly in the partially full pages.
In figure 2 we illustrate the results of an experiment in which the number of pages available was varied from the minimum (i.e. f H/pl ) to an unlimited number of pages. Use of the minimum number of pages to store the tree resulted in a slight increase An page transitions. This seems to indicate that the beneficial effects the method are due to the early stages of allocation. The lowest curve in figure 2 is the minimum average number of page references possible. The formula for this lower bound is discussed below.
Let N be the number of nodes in the search tree. Then there are at least ft/pl pages in which * the tree is stored. Now consider a page tree in which each node corresponds to a page, there are p nodes of the original tree on each page and thus the tree will be a (p+1)-ary tree. The average path length in this page tree is the average number of page transitions required per search. The average path length in the page minimized if it is balanced. A slight variant of a Knuth* gives the average path length in a balanced
tq+V
tree will be
of n * fc/p) nodes as
formula
(p-H)-ary
from
tree
1
r\
i
where
q '*L Logp+1 (pn + 1)J
m
119
Huntz and Uzgalis
It is interesting that our experimental data indicates that the grouped allocation scheme results in only 10 to 20X more page references than this lower bound. This is particularly interest¬ ing since part of the difference is due to the fact that the search tree is not balanced in general.
Further Reduction .of _ Page.. Rg fere nces
It is clear that if all of the search tree is in secondary storage the average number of page references must be greater than or equal to one. From the formula for G(N,p), we see that for p = sgrt(N) the mean number of page references is approxim¬ ately 2. But one of these page references can be eliminated if the first page (i.e. containing the peak of the search tree) is
retained permanently in memory. A buffer of size p is also
necessary to temporarily store pages brought in from secondary storage. Therefore, with a dedicated portion of main memory of size 2p ( or 2 sqrt (N) ) the average number of page faults will
be close to one. For example, if M - 40,000 nodes and p = 200
only IX of the tree or 400 nodes need be stored in main memory to achieve a near minimum of page references.
Conclusion
He have described two methods of dynamic storage allocation
for trees in a paged environment. The grouped allocation
technique which we developed was shown to reduce the average number of page references per search over a wide range of page sizes. With a slight modification to the scheme no extra storage is necessary. With a large search tree it is possible to reduce the number of references to secondary storage to close to one by
keeping one or two percent of the tree in main memory.
This research was supported by the National Science Foundation (GJ-809) and the Department of Defense Advanced Research Projects Agency (DAHC1 5-69-C-0285) . Computing support was provided by UCLA Campus Computing Network. Reproduction in whole or in part is permitted for any purpose of the United States Government.
£§£§!§££§£
1. Hibbard, T. N«, "Some Combinatorial Properties of Certain Trees with Applications to Searching and Sor<. igM, J. ACH 9,
1 (Sept. 1962) pp. 13-28.
2. Knuth, D. E. , The Art of Computer Programming, Vol. . I, Addison- Wesley , 1968, p.401.
120
fluntz and Uzgalis
8 16 32 64 128 256 512
?AGstSiZE. /w kioO€$
Figure 1. Conparison of Sequential and Grouped Allocation
Muntz and Uzgalis
Unclassified
Security Classification
|
DOCUMENT CONTROL DATA ■ R & D { Security classification of titlo, body of abstract and indexing annotation must be entered when the overall report is classified) |
|
|
1. ORIGINATING ACTIVITY (Corporate author) School of Engineering and Applied Science Computer Science Department 90024 405 Hi]gard, University of California, Los Angeles |
2a. REPORT SECURITY CLASSIFICATION Unclassified |
|
2b. GROUP |
|
|
3. REPORT TITLE |
|
|
Computer Network Research |
|
|
«. DESCRIPTIVE NOTES (Type of report and inclusive dates) |
|
|
t> AUTHOR(S) (First name, middle initial, last name) |
|
|
Leonard Kleinrock |
8a. CONTRACT OR GRANT NO.
DAHC-15-69-C-0285
b. PROJECT NO-
7«. TOTAL NO. OF PAGES 176. NO. OF REFS
9a. ORIGINATOR'S REPORT NUMBER(S)
9b. OTHER REPORT NO(S) (Any other numbers that may be assigned this report)
10. DISTRIBUTION STATEMENT
Distribution of this document is unlimited.
12. SPONSORING MILITARY ACTIVITY
13. ABSTRACT
ARPA Semiannual Technical Report, February 15, 1970, to August 15, 1970
1473
(PAGE I
S/N 0101- 807- 6801
Security Classification