MEAN DELAY ANALYSIS FOR UNIDIRECTIONAL BROADCAST STRUCTURES by JOSEPH WAI MING PANG B.A.Sc, The University of British Columbia, ]983 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES Department of Electrical Engineering We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA © Joseph Wai Ming Pang, 1985 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of ElbfTrllCAl „ H^l^^lA^ The University of British Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date Abstract Unidirectional broadcast structures constitute a class of high performance local network architectures. They are very flexible and well suited for fiber optic implementation. The access methods used in these networks are often based on certain implicit token-passing mechanisms to provide superior delay-vs-throughput characteristics. The performance of these unidirectional broadcast protocols is evaluated in this thesis via a study on the classical token-ring system. Emphasis is placed on the analysis of mean delay-vs-throughput performance for the gated exhaustive service discipline under asymmetric traffic. The analysis involves examination of the statistical behaviour of interacting queues. A number of exact results are derived and based on these results, a very good approximation for the average delays is developed. The approximation agrees closely with exact numerical solutions over a wide range of system parameters. The implications of the approximation are also discussed. ii TABLE OF CONTENTS Page 1. INTRODUCTION 1 1.1 High-performance Local Area Networks 1 1.2 Objectives 2 1.3 Previous Work 3 1.4 Outline 4 2. DEVELOPMENT OF THE LAN SYSTEM MODEL • ... 6 2.1 Description of D-net and Its Communication Protocol 6 2.2 Comparison of D-net with Token-Ring Systems 10 2.3 System Model and Parameters 11 2.4 Definitions of System Random Variables 15 2.5 Comments on the Relations between System Random Variables.... 17 3. FORMULATION OF THE SYSTEM EQUATIONS 19 3.1 Imbedded Markov Chain Formulation3.2 Moment Calculations 22 3.3 Approaches to the Solutions of the Basic Equations 23 3.4 Existence and Uniqueness of Solutions to the Basic Equations 24 3.5 Comments Regarding Solutions of the Basic Equations 26 iii TABLE OF CONTENTS (cont'd) Page 4. SOME EXACT ANALYTIC RESULTS 28 4.1 Overview of Results4.2 Expected Cycle Time , 28 4.3 Simplification of the Forcing Matrix B 31 4.4 The Jacobian Matrix A 33 4.5 An Auxilliary Result 5 4.6 A Difference Equation for the Second Joint Moments of Terminal Service Times 37 4.7 Solution for the Symmetric Case 45 5. MEAN DELAY ANALYSIS 47 5.1 Relationship between Mean Message Delays and Service Time Moments 47 5.2 A Fundamental Relation for {v^ } 50 5.3 An Approximation for (vii } 2 5.4 Comments on the Approximation for {v^ } 54 5.5 Comparison of Approximation and Exact Numerical Results for {v^ } 56 5.6 Delay-vs-Throughput Results 65 5.7 Finite Buffering and Non-exhaustive Services 7 9 iv TABLE OF CONTENTS (cont'd) Page 6. CONCLUDING REMARKS 82 6.1 Summary of the Results 86.2 Suggestions for Further Work .' 83 REFERENCES 86 APPENDIX: Eigenvalues of the Jacobian Matrix A 89 v LIST OF FIGURES Page 2.1 Architecture of D-net 7 2.2 Trains of Packets on D-net2.3 The Star-coupled Version of D-net 9 2.4 The Open-ring Version of D-net2.5 Schematics for the Single-server Multi-queue Model 12 5.1a E versus p for N=8 and 1 single large user 59 max 5.1b E versus p for N=8 and 1 single large user 59 avg 5.2a E versus p for N=8 and 1 single small user 60 max K 5.2b E versus p for N=8 and 1 single small user 60 avg 5.3a E versus p for N=8 and 2 clusters of identical users 61 max 5.3b E versus p for N=8 and 2 clusters of identical users 61 avg 5.4a E versus p for N=16 and 1 single large user 62 max 5.4b E versus p for N=16 and 1 single large user 62 avg 5.5a E versus p for N=16 and 1 single small user 63 max r ° 5.5b E versus p for N=16 and 1 single small user 63 avg 5.6a E versus p for N=16 and 2 clusters of identical users 64 max 5.6b E versus p for N=16 and 2 clusters of identical users 64 avg 5.7a v^ versus p for N=8, 1 single large user and t^Pj2 70 5.7 b var(vi;l) versus p for N=8, 1 single large user and ti=P^2' • • • 70 5.8a VJJ versus p for N=8, 1 single large user and t^P^ 7 1 5.8b var(v ) versus p for N=8, 1 single large user and ^i=Pi 7 1 5.9a v ± versus p for N=8, 1 single large user and t^l 7 2 5.9b var(v ) versus p for N=8, 1 single large user and t^l 7 2 vi LIST OF FIGURES (cont'd) Page 5. 10a versus p for N=8, 1 single small user and t^ = p. 2 7 3 5. 10b var(v^) versus p for N=8, 1 single small user and Ci=Pi 2 7 3 5. 11a v.. versus p for N=8, 1 single small user and t^=p^ 74 5. lib var(v^) versus p for N=8, 1 single small user and 74 5. 12a v.. versus p for ii N=8, 1 single small user and t^ = l. 75 5. 12b var(v..) versus n p for N=8, 1 single small user and t.-l. l 75 5. 13a v.. versus p for li N=8, 2 clusters of identical users and 76 5. 13b >-s/ var(v..) versus ii p for N=8, 2 clusters of Identical users and t -o 2 76 zi pi 5. 14a. v.. versus p for ii N=8, 2 clusters of identical users and 77 5. 14b varfv..) versus ii p for N=8, 2 clusters of identical users and 77 1 Pl 5. 15a v.. versus p for N=8, 2 clusters of identical users and t.-l. 78 ii l 5. 15b varfVj.) versus ii p for N=8, 2 clusters of identical users and 78 A.l Right-half plane semicircle 93 vii ACKNOWLEDGEMENTS I would like to acknowledge my appreciation to Dr. R.W. Donaldson for his encouragement and supervision throughout the course of this research.. I would also like to thank Dr. H.W. Lee for his many valuable suggestions. Thanks are due to Ms. Charlotte Stevenson for typing the manuscript. Finally, financial support from an NSERC postgraduate scholarship is gratefully acknowledged. viii 1 1. INTRODUCTION. 1.1 High-performance Local Area Networks. The demand for local communication resources continues to grow very rapidly. Today, local area networks (LANs) operating at a few Mbit/s can still satisfy most current needs but the situation is likely to change in the near future. The advent of superfast microcomputers, the evolution of new system architectures (e.g. distributed processing) and the Integration of data intensive services (e.g. interactive graphics, tele-conferencing) all lead to ever higher bandwidth requirements. Even with sophisticated bandwidth compression techniques, the bandwidth of the conventional co-axial cable will not be adequate for many applications in the future. Optical fiber emerges as the most promising candidate for implementing ft the high-performance LANs needed in the future. The most impressive feature of optical fiber is its enormous information-carrying capacity; the theoretical limit is well above 100 Gbps-km. Several Gbps-km can be achieved using current technology. As the technique of wavelength-division multiplexing matures, the bandwidth of an optical fiber will increase many-fold. Thus, not only can optical fiber satisfy the bandwidth requirements of LANs in the foreseeable future, it will also provide great flexibility for growth in the long term. Other desirable features such as immunity to electromagnetic interference, high channel security, low signal, loss, small size, light weight, etc all make optical fiber very attractive for LAN applications. Nevertheless, limitations on current fiber optics technology do impose constraints on LAN system designs ([5-7]). For example, 2 the very high insertion loss of current optical taps has led designers to consider point-to-point configurations such as rings or stars instead of linear bus structures. Furthermore, bidirectional transmission on a single optical fiber also faces considerable difficulty due to the minute fiber core size and crosstalk between source and detector. To overcome the technological difficulties with fiber optics, a number of new network schemes have been developed ([8-13]). Among these, the unidirectional broadcast structures (UBSs) with conflict-free schedulings appear to be most suitable for very high data rate applications. The access protocols used in these UBSs resemble the conventional token-passing on a ring which provides superior delay-throughput characteristics. However, these networks avoid the major pitfalls associated with the token-ring. As a result, UBSs have received much attention lately. A typical UBS called D-net will be described in Chapter 2, together with its interesting properties. 1.2 Objectives. The primary goal of this thesis is to investigate the performances of UBSs by studying the classical token-passing protocol. The performance index will be the average message delay at each node. Unfortunately, a rigorous delay analysis under the most general conditions is very difficult. To provide mathematical tractability, a number of reasonable assumptions are made to simplify the problem. Attention is focused on the gated exhaustive service discipline because it can be analyzed mathematically and also provides insight to the performance analysis of the more practical non-exhaustive service schemes. 3 1.3 Previous Work. The problem of establishing the queueing characteristics of a token-ring system has been studied by many authors in the last two decades under various titles (e.g. polling, traffic control, cyclic queues). The long history of this problem indicates both its importance and its intractability. So far, no solutions are available to the general problem, whether exact or approximate, analytic or algorithmic. Thus, we have to use less reliable and hard-to-interpret results obtained from simulations or actual network measurements to study the queueing behaviour of many practical token-ring systems. Nevertheless, rigorous analyses have been carried out for some special although unrealistic cases. It is the hope of many researchers that these analyses can shed some light on the behaviour of more practical systems. A good summary of the more recent work on token-ring analysis can be found in [29]. With few exceptions, most of the previous work dealt with the gated and the non-gated exhaustive service disciplines with infinite buffering and Poisson arrivals. The special case with only two nodes in the system was studied in [19-21] and exact explicit delay results were obtained. Generalizations to an arbitrary number of nodes were investigated in [22-29J. Moment generating functions of cycle time, queue length and delay distributions have been obtained in [22-26]. Unfortunately, these are not closed-form solutions that facilitate easy evaluation of delay moments. Attempts have been made to derive explicit analytic expressions for the average delays but they were successful for the symmetric case only ([25-27]). For the general asymmetric case, only numerical algorithms 4 ([27-29]) and approximate solutions ([30-33]) are available. Most of the approximations given in the literature are based on rather heuristic arguments and hence their regions of validity are unclear. In general, these approximations break down at very heavy network loadings or under highly asymmetric terminal traffic. Numerical algorithms have the advantage of generating exact results but they cannot readily show the effects of simultaneous changes in the system parameters. An asymmetric token-ring has an enormous parameter space (the set of all possible combinations of parameters) and hence resists analysis by numerical methods. Nevertheless, exact numerical results can serve as absolute references for validating approximations and simulations. The more general cases of non-exhaustive service disciplines and finite buffering are much more difficult to deal with, as evidenced by the lack of previous work in this area. An approximate treatment of non-exhaustive service disciplines can be found in [34]. Non-exhaustive service disciplines on a two-node system were analyzed in [35]. The system with single-buffer nodes (interactive-user model) was investigated in [38] based on the work from [36-37 ]. 1.4 Outline. In Chapter 2, a typical UBS called D-net is described to show the resemblance of the UBSs and token-ring systems. Then the queueing model and relevant system parameters are formulated- A number of important random variables are defined and their relationships are discussed. 5 In Chapter 3, the queueing problem is solved by the "method of Imbedded Markov Chain. The imbedded chain being considered is the joint terminal service times in a service cycle. A recursive functional equation is derived for the moment generating function of the imbedded chain at steady state. Differentiations of this basic functional equation yield recursive linear equations for the first and second order moments. The existence and uniqueness of solutions to these linear equations are also established. In Chapter 4, a number of results are derived concerning the solutions of joint moments of the terminal service times. A simple difference equation which has not been reported before is presented. This equation provides the basis for a very good approximation. In Chapter 5, the relationships between average message delays and the normalized cycle time variances are given. A fundamental relation among the delays, dictated by Kleinrock's conservation law, is also derived. An approximate solution is then developed, followed by a comparison with exact numerical results. In the conclusion, a summary of results is given with suggestions for future research. 6 2. DEVELOPMENT OF THE LAN SYSTEM MODEL. 2.1 Description of D-net and its Communication Protocol. Unidirectional broadcast structures may be different in topology and in many other aspects but their basic operations are very similar. A typical UBS called D-net is described to illustrate the basic communication protocol commonly used for UBSs. Fig. 2.1 shows the architecture of D-net. The network consists of an inbound and an outbound channel. All traffic flows unidirectionally from the outbound channel to the inbound channel. There are N stations in the network, numbered in the order shown in the figure. Each station has three taps: the receiver (R-)tap, the sensor (S-)tap and the transmitter (T-)tap. The R-taps are connected to the inbound channel to receive any broadcast messages. The S-taps and the T-taps are connected to the outbound channel as shown in Fig. 2.1; they are used to sense upstream traffic and to transmit broadcast messages, respectively. The black ball is called the locomotive generator and it has only the R-tap and the T-tap. To transmit, a station first waits until it senses upstream traffic at its S-tap. The station then looks for the end-of-carrier (EOC). The EOC event is defined as the cessation of signal at the S-tap. It is assumed that it takes t, seconds to detect this event. After detection of EOC, the d station starts transmitting its own packets. While transmitting, a station may sense more incoming upstream traffic through its S-tap. In this case, the station aborts its transmission and waits for the next EOC. Otherwise, the station finishes its transmission. This basic operation will be repeated. Basically, a station sees a 'train' of packets separated by t. INBDUMD LDCDMDTIVE GENERATOR 7^ R T R R T S © © T S T T R • • • ® i T •*• OUTBOUND Fig. 2.1 Architecture of D-net. LDCDMDTIVE HX+t, Fig. 2.2 Trains of packets on D-net. 8 seconds on the channel and each station attaches its packets to the end of this train. The train thus grows in size as it passes through a station with ready packets. The locomotive generator is used to transmit a short burst called the locomotive to head the train of packets. Without the locomotive generator, the network will stall because no stations will contend for the channel unless there is some traffic. To keep the network 'alive' all the time, the locomotive generator generates a locomotive each time it sees the end-of-train (EOT) at its R-tap. The EOT event signifies the end of a cycle. It is detected when a silence period of 2t^ seconds after cessation of signal is noted at the R-tap of the locomotive generator. If normal operation prevails, the traffic on the unidirectional channel will consist of trains of packets separated by 2(T + t^) seconds shown in Fig. 2.2 where i is the propagation delay on either the inbound or the outbound channel and 2t^ is the time needed to detect EOT. It is noted that the D-net unidirectional bus described here is not suitable for fiber optic implementation because of the difficulties with current optical tap technology (e.g. high signal loss). Two modifications of the basic D-net structure are given in [12] to overcome these technological difficulties. The star coupled version of D-net shown in Fig. 2.3 is suggested to enable the insertion loss of R-taps to be lumped in the coupler so that each station receives approximately the same signal power. The open-ring version shown in Fig. 2.A can be used to avoid the distributed insertion loss at the T-taps. Since each node is active in the open-ring D-net, bypass circuits must be Incorporated in case of a node failure. 9 STAR CDUPLER LOCOMDTIVE GENERATOR Fig. 2.3 The Star-coupled Version of D-net. T T R LOCOMOTIVE GENERATOR T R T R T S © © T S R © T v.. s T Fig. 2.A The Open-ring Version of D-net. 10 2.2 Comparison of D-net with Token-Ring Systems. By taking advantage of the inherent ordering of the network nodes, the D-net protocol provides orderly network access similar to that of token-passing on a ring. As long as the EOC detection time in D-net is comparable to the token detection time in a token-ring, the two networks will have essentially the same delay performance. From the training sequence of D-net, we may regard the switching overheads as being lumped in the inter-round silence period of 2(x + t_) seconds. One advantage of D-net over d the conventional distributed token-ring is that the impact of the inter-round overhead can be reduced by interleaving the locomotives. To do this, the locomotive generator must anticipate the length of each train and generate the locomotive not by detecting EOT but by precise timing. However, interleaving locomotives is advantageous only when the inter-round overhead is a significant portion of the cycle time (train + overhead). Calculations based on typical parameters suggest that the interleaving of locomotives is perhaps overskilled for many LAN applications. A more attractive way to reduce the ratio of overhead to cycle time is to allow statistical variations of the station access times according to the network loading, for example by not restricting service to a single packet per node per cycle. The gated exhaustive service discipline under investigation in this thesis is one example of this approach. The reliability issues surrounding the D-net protocol and token-ring are also different. One observes that the D-net protocol is not completely distributed. The locomotive generator can be regarded as a central 11 controller whose failure will stall the network. Fortunately, the locomotive generator is a simple device so it can be made redundant with little additional cost. Nevertheless, the D-net protocol avoids the major pitfalls in token-passing such as lost tokens or duplicate tokens. If a locomotive is lost because of channel errors, the locomotive generator will simply time out and generate another locomotive. Considering the complexity of error detection and recovery mechanisms of conventional token-passing, the D-net protocol represents a major improvement over token-passing. Another reliability issue is related to the control passing mechanism in the D-net protocol. Recall that each station attempts to transmit immediately after detecting EOC and aborts its transmission as soon as it detects any incoming traffic at its S-tap. Since it takes a finite amount of time to detect incoming traffic, there will be collisions of a very short duration (time needed to detect incoming traffic) at the beginning of each packet. It is assumed that each packet is headed by a preamble portion for bit synchronization and the collisions mentioned above will not affect the synchronizability of the preamble portion. 2.3 System Model and Parameters. As we have seen, the basic operation of D-net is identical to the token-ring except for the switching overheads from one station to another. For this reason, the performances of D-net and all other similar UBSs will be studied in this thesis as if they were token-ring systems. Fig. 2.5 shows the schematics of the single-server multi-queue model suitable for the analysis of the token-ring system. N queues, numbered from 1 to N, are 12 QUEUE 2 • N • SERVER CYCLIC SCHEDULER Fig. 2.5 Schematics for the Single-server Multi-queue Model. 13 attended by a single server in a cyclic order. Further, time is divided into contiguous slots of fixed duration. All time quantities are measured in terms of this fundamental unit. A number of parameters are needed to specify the queueing system, in order to pose a well-defined problem involving dependent queues. These parameters will be discussed in the following paragraphs. Message arrivals. Poisson message arrival is perhaps the most popular assumption in queueing analysis. A slightly more general type of arrival will be considered here. Messages arriving at a queue within a time slot will be registered at the end of that slot. The number of message arrivals at queue i in one slot is random and its distribution is characterized by the moment generating function (MGF) 1 ct^s). Arrivals within different time slots are assumed to be independent and the same assumption is made for arrivals at different queues. By letting the slot interval become vanishingly small while keeping the message arrival rate constant, one obtains Poisson message arrivals as a special case of the general independent slot arrivals considered here. Other arrival statistics can also be reasonably approximated by choosing the appropriate slot size and the MGFs Message lengths. Message lengths are assumed random with general distributions described by MGFs (p\(s)}. Although generally distributed, the 1 The MGF of a random variable X is defined as F(s) = E[exp(sX)]. length of a message must be an integral multiple of the slot interval. Moreover, message lengths are assumed to be independent of the message arrivals and also independent among different queues. Service discipline. The service discipline in a multi-queue system includes specifications of the service schedule, order-of-service at each queue and the number of messages to be served from each queue in a service cycle. In a token-ring system, queues are inherently served in a cyclic order (service schedule). Further, a first-come-first-serve discipline will be assumed at each queue (order-of-service). Thus, the service disciplines in this thesis will usually refer to the number of messages served from each queue in a cycle. Various service disciplines are possible; they can be gated or non-gated, exhaustive or non-exhaustive. For gated service disci plines, all messages arriving at a queue after commencement of service at that queue will not be served in that service cycle. Services not gated are called non-gated. The terms 'exhaustive' and 'non-exhaustive' are self-explanatory. In practice, almost all service disciplines are non-exhaustive in nature to avoid the possibility of very long cycles. Unfortunately, the rigorous analysis of non-exhaustive service disciplines appear to be insurmountably difficult. As a result, attention will be focused on the gated exhaustive discipline for mathematical tractability. As well, most non-exhaustive schemes can be approximated by the gated exhaustive scheme for' low traffic levels. For the gated exhaustive discipline, all messages buffered at a queue when service starts at that queue will be served in that particular cycle while messages arrived during service will be left in the queue until the next cycle. This is different from the truly exhaus-15 tive (non-gated exhaustive) discipline where queues are served till empty in each cycle. The non-gated exhaustive scheme will not be considered here. Interested readers can refer to [22-29] for more detail. Switching overheads. There is a generally distributed switching overhead from queue i to the next queue characterized by the MGF co^(s). Similar to the message length, the switching overhead must be an integral multiple of the slot interval. Also, all switching overheads* are assumed to be independent of each other. The D-net, with constant switching overheads, is an example. Buffering. Infinite buffering will be assumed throughout this thesis. This is a reasonable assumption as long as the blocking probability is small. In summary, the system under consideration is a single-server N-queue system. Time is divided into fixed contiguous slots. Queues are served cyclically under a gated exhaustive discipline and a first-corae-first-serve order-of-service. Infinite buffering is assumed at each queue. General independent time slot message arrivals are assumed with slot arrivals characterized by the MGF a^(s) at queue i. Messages arriving at queue i have generally distributed lengths decribed by the MGF 8i(s). The switching overhead from queue i to the next queue Is also generally distributed with MGF (^(s). 2.4 Definitions of System Random Variables. To formulate the mathematial queueing problem, a number of random variables need to be defined. Let 16 (k) = kth cycle time of queue i, i.e. the time between successive scan instants (instant when service starts) of queue i. (k) = the number of messages buffered at queue i at its scan instant in the kth cyclic service of that queue. (k) = the number of messages arrived at queue i during the kth cycle of queue i. (k) = the number of messages served from queue i in the kth cycle of queue i. (k) = the switching overhead from queue i to the next queue in the kth cycle of queue i. (k) T\ = the terminal service time of queue i in the kth cycle of queue i, i.e. time for the server to serve queue i and to switch to the next queue. All the above random variables assume non-negative integer values. According to the definitions, a number of relationships can be written as follows: (k) (k) Z. = X. for gated exhaustive service (2.1) 7 (k) • K, = I L. }*> + W.^; (2.3i fa 1.3 C.<k> = I T.(k) +rT.(k+1) (2.4c (k) \W = 1 M. <k) (2.5) 1 j=l 1,J where (k) L . = length of the jth message buffered at queue i at its scan i»J instant in the kth cyclic service of queue i. (k) Mi j = number of messages arrived at queue i in the jth slot of the kth cycle of queue i. (k) (k) The variables M, . and L. . are two sets of independent and identically i,J i.J distributed (i.i.d.) random variables whose statistics are described by the MGFs a^(s) and B^(s) respectively. When the lower index exceeds the upper index in any summation, the summation is defined as zero. This convention will be adopted throughout this thesis. 2.5 Comments on the Relations between System Random Variables. Equations (2.1)-(2.5) represent the most basic relations between the system random variables for the gated exhaustive service discipline. For other service disciplines, equations (2.2)-(2.5) still hold but (2.1) has to be modified. For example, if queues are served according to the gated non-exhaustive scheme with queue i allowed to be served up to p^ messages in each cyclic service, then (2.1) will become Pi Z.^J = I I(X,V*' > j) (2.6) 1 j-1 1 where I( •) is the indicator function2. By definition, Z ^ < X ^ for all gated disciplines. Moreover, there is often a deterministic relation betwen (k) (k) Zj and Xj like (2.1) and (2.6) but there are prominent exceptions such as the non-gated exhaustive case. One notices that equations (2.1)-(2.5) are recursive in nature. Given „ (k) w (k) „ (k) v . „ (k) „ (k) „ (k) ,„ (k) , » •••» XJJ » we can obtain , Z2 , •••> Z^j and , T2(k), .... TN(k) using (2.1) and (2.3). Then we can obtain C and X2(k+1) from (2.4), (2.5) and (2.2). Clearly, X2(k+1\ X3(k+1), ... can be derived successively in this manner. Thus, (2.1)-(2.5) completely characterize the evolution of the system. We shall use these equations to solve our queueing problem by the method of imbedded Markov chain in the next chapter. 2 The indicator function I(•) is defined to be 1 if the statement within brackets is true and 0 otherwise. 19 3. FORMULATION OF THE SYSTEM EQUATIONS. 3.1 Imbedded Markov Chain Formulation. The imbedded Markov chain we consider here is the joint random variable of all the terminal service times in a cycle. If we define T^k^ = (T^k\ . .., TK^), then T^ will be the imbedded chain. The steady state statistics of T*^k^ can be obtained using moment generating functions. Let P(s) where s = (S}» s2> s^) be the MGF of the random vector T^k^ as k approaches infinity. Then we can write P(s) = I exp(s • t) I p(t|u) p(u) (3.1) t u where t = (tls t2, tN), u = (uls u2, UJ^J) N s • t = ) st = dot (scalar) product, , n n n=l p(u) = lim Prob(?(k) = u) , p(t*|u) = Prob(?<k+1) - tV(k) = u). Interchanging the order of summation yields P(s) = I p(u) I exp(s* • t) p(t|u) (3.2) u t The transition probabilities can be expressed by N 'p(tlu) « n q(t |c ) (3-3) , n 1 n n=l 20 where q(t |c ) = Prob(T (k+1) = t |C (k) = c ) , n ' n n' n N n-1 c n .L 3 .L, j Thus, the summation over t in (3.2) can be written as N I exp(s • t) p(t|u) = n exp(sntn) q(tn|cn) ) -> n=l t t n N-1 = n {I exP(sntn)q(tn|cn) ) I exp(sN tN)q(tJcN) (3.A) n=1 Cn S Let L and 11^ be random variables having distributions of message lengths and arrivals in a slot respectively at queue N. Then the summation over t in (3.4) can be evaluated as I exP(sNtN)q(tNlCN) fcN -Etexp^T^)^ -cK] z (k+1) = E[exp(sNLN) N | CN(k) = cN] E[exP(sNWN(k+1))] by (2.3) = E[exP(YK(k) Xn8N(sN))|CN(k) = cN ] o^) by (2.1) and (2.2) = E[(exp(MK J!nBN(sN)))CN] ^.(sN) by (2.5) = exp(cN too^CtoSjjCSy))) o^,(sN) = exP(cN W) ^(Bn) (3-5) where ^(s) = i!naN(toBN(s)). 21 Substitution of (3.5) into (3.4) gives N-l I exp(s-t)p(t|u) = n [I exp(sntn)q(tn|cn) ] exp(c'N %(sN)) «^(sN) •+• n=l t n t N-2 = n [I exP(sntn)q(tn|cn)] I exP(sN_1tN_1)q(tN_1|cN_1)exp(cN S^)) ^(s^ n=1 'n Vl N-2 = n [I exp(sntn)q(tn|cn)] I exp((sN.1+ysN)) W^N-l lcN-l> n=1 Cn CN-1 . exp((cN-tN_1) SN(8N)) uiN(sN) N-2 = n [I exp(sntn)q(tn|cn)] exp[cN_1 Vl(W W > ^ Vl(SN-l + n=l t n . exp((cN-tN_1) ysN)) (^(SJP (3.6) The last step is done by noticing (c - tN_ ) is independent of t^_1 and by using the same summing technique used to derive (3.5). Continuing in this fashion, we can write N N N _> I exp(s-t)P(t|u) = n exp((I u ) Gn(s)) n u>n( sn+Hn(s)) ->• n=l i=n J n=l t J N N ^ = n exp(u F (s) ) n u (s +H (s)) r n n , n n n n=l n=l N = exp(u'F>(s)) n Wn(sn+Hn(s)) (3.7) n=l where Gn(h = Sn(sn+Hn(l)) (3.7aN H (s) = I G.(s'), !L.(s) = 0 (3.7b). k=rrrl Fn(J) = I Gk(l) = FN(J) - Hn(J) (3.7c) k-1 F(s) = (F,(s), F2(s), .... FN(s>)) 22 Substitution of (3.7) into (3.2) gives N P(s) = [ II con(sn + Hn(s))] P(?(s)) (3.8) n=l Eqn. (3.8) is a recursive functional equation that allows us to solve for P(s) . We shall attempt to calculate the first and the second order moments •*( k) of T with k-*00 in the next section. Before leaving this section, we notice that exactly the same procedure can be used to derive the MGF of the joint terminal service times for the time continuous system with Poisson message arrivals. The results will be exactly the same except that all time quantities are expressed in seconds and the arrival MGFs (ct\(s)} are replaced by {exp( X^ (exp( s)-l))} where X^ is the message arrival rate at queue i. 3.2 Moment calculations. To calculate the moments of the joint terminal service times, it is convenient to take natural logarithm of both sides of (3.8) and write N P(s) = I 2n(sn + Hn(s)) + P(F(s)) (3.9) n=l where P(s) = AnP(s) , to (s) = Jlno) (s) n n By differentiating (3.9), we can get the central moment (and hence the moments) of the joint terminal service times. Differentiation of (3.9) once and evaluation at s = 0 gives & N - oF. N o(s.+H.) » - J *L J + I ft ^ J (3.10) 23 All derivatives will be evaluated at the origin unless stated otherwise. A second differentiation yields o~ N N ,* 5F 5F N ~ d2F 52P = y y S2P k ™ I y &P k ^ L Ao Ao Ao Ao A dSi5sj k-1 *=1 5skdSA &Si &Sj k-1 dSk &SiaSj + y 5(sk+Hk) 5(sk^Hk) k-1 i j i j Eqns. (3.10) and (3.11) can be readily expressed in matrix form as follows: v = Av + b (3.12) V = AVAT + B (3.13where -+ T -> T v = (vlf v2, vN) , b = (blt b2, bN) , Vi = 5s" • bi ~.\ UJ 5s . • V = [v. .] , v. . = ° , ijJ ij as1asj aF. A = taijJ•aij=^• ^k 5s., as . i J 3.3 Approaches to the Solutions of the Basic Equations. There are two approaches to obtaining solutions of (3.12) and (3.13). The first approach is to recognize that (3.12) is a set of N linear equations 24 5P of N unknowns-g-^— with the forcing terms . Then we notice that (3.13) represents another set of linear equations of N(N+l)/2 unknowns {v. ,} (v..=v..) with forcing terms {b, .}; these {b..} are obtained from the solution of (3.12). Hence, we can solve (3.12) and (3.13) by standard techniques for solving systems of linear equations. Naturally, the questions regarding existence and uniqueness of the solutions to both set of equations arise. These questions can be answered by explicit series solutions using the second approach discussed later. The ultimate goal is to solve (3.12) and (3.13) explicitly in closed form. Unfortunately, no such solutions are available for (3.13) except for the symmetric case or for N=2. The second approach is somewhat numerical in nature. We notice that both (3.12) and (3.13) represent recursive relations that allow iterative numerical solutions. A new estimate can be calculated from the immediately previous estimate using the right hand side of (3.12) and similarly for (3.13). If the iterative procedure converges, then we can obtain a solution. The main results obtained following this line of thought can be summarized in Theorem 3.1 in the next section. 3.4 Existence and Uniqueness of Solutions to the Basic Equations. Theorem 3.1; If the utilization of the system satisfies p < 1, then unique CO solutions exist for both (3.12) and (3.13) and they are given by v = £ A b k=0 00 T k k and V = ^ A B(A ) respectively. k=0 25 Indeed, the theorem can be extended to all higher order derivatives of P(s) but we will restrict our attention to the first two orders of moments. The proof of Theorem 3.1 relies heavily on a result proved in the Appendix stating that if p < 1, then all the eigenvalues of A have magnitudes less than unity. We prove Theorem 3.1 using this result. Proof of Theorem 3.1: We diagonalize A by A = TAT"1 (3.14) where A is a diagonal matrix with elements equal to the eigenvalues Xp X2» X^ of A, and T contains the corresponding column eigenvectors. Using this diagonalization, we can write I A b = I rAkr_1b = ix I AV"^ k=0 k=0 k=0 and lAkB(Ak)T=I rAkr_1B( r"1 k=0 k=0 = rd AkcAk)rT k=0 where c = p-V"1)1 - lClJj. (3.15) (3-16) Now \\ A = k=0 I K Ki=j) k=0 1 and £ AKCAK k=0 I c,.XkXk k=0 lj 1 J Both series exist if |X.| < 1 for all i and this Is guaranteed if p < 1 OO oo X Therefore I A b and I A*B (A* ) both exist if p < 1 and substitution of k=0 k=0 these series into (3.12) and (3.13) will verify that they are indeed solutions to the equations. Hence the existence of the solutions to (3.12) and to (3.13) has been established. To establish the uniqueness of those solutions , we let v and u be solutions to (3.12) and write v = Av + D (3.17 ) u = Au + b (3.18) Subtraction gives (v - u) = A(v - u) (3.19) which implies (v - u) = Ak(v - u) for all k (3.20) but Ak(v - u) = TA^r *(v - u) •+ 0 as k •*• » so v = u. Similar arguments establish the uniqueness of the solution to (3.13). 3.5 Comments Regarding Solutions of the Basic Equations. The series solutions given in Theorem 3.1 are useful in establishing existence and uniqueness, but they do not shed light on the explicit closed-form solutions. Even for numerical solutions', one will follow the iterative procedures given by (3.12) and (3.13) instead of calculating the series in Theorem 3.1 term by term. In fact, a very nice numerical procedure was developed in [28-29]. However, it is desirable to have analytic results that 27 display the effects of changes in system parameters. In the next chapter, we shall derive a number of exact analytic results. 28 4. SOME EXACT ANALYTIC RESULTS. 4.1 Overview of Results. A number of exact analytic results are available regarding the solutions to (3.12) and (3.13). First of all, (3.12) can be solved explicitly in closed form by considering the average cycle time. The solution to (3.12) allows us to simplify the forcing matrix B in (3.13). Next, we explore the structures of the matrices A and B in (3.13). A simple difference equation relating the unknowns {v^j) is derived by exploiting the structures of A and B. This difference equation has not been reported before and It will form the basis of the mean delay approximation to be presented in the next chapter. 4.2 Expected Cycle Time. From equation (2.4), we observe that the expected cycle time at steady state is equal to the sum of all expected terminal service times. This means the average cycle time is independent of the queue. Using this fact, we can compute the average cycle time and obtain other results as well. We state these results precisely by the following Lemma. Lemma 4.1: The expected cycle time of queue i at steady state is independent of i and it is given by (4.1) 29 ~ p. EW 5P _ ^ , _ i 5s. 1 Moreover, = Pl EC + EW1 = -i— + EW1 (A.2) l where EC = average cycle time, EW^ = Uj' (o) = expected overhead from queue i to the next queue, N EW = \\ EW. = total expected overhead, j-1 2 p^ = S^'(o) = utilization of queue i, N p = 1 p. - system utilization, j-l J Proof of Lemma A.l: From (2.A), we can write N „ x i-1 lim EC.^ = lim E[ I T\*> + £ T^'] k-**> 1 k-Kt. j=i J j = l J N / V. X -i m^ -sir «-3) 1=1 J Equation (A.3) states that the average cycle time of queue i at steady state is independent of i and we denote this quantity by EC. From (3.10), we have 30 Next, we notice from (3.7a) and (3.7b) that Gj,' G3, and Hj, H2, are all independent of s ^ and from (3.7 c) that F^ = G^ + G2+ •••+ G^, therefore oF. oG1 S(s . + H.) ^ = IT, - and 'as, 3 = I(^=1) N 1 3-1 3 From the definitions of 3. and S., we have i l a.' = a.' 8.' = (average arrivals in a slot x average message length in slots) at q ue ue i Thus, S.' - <*>.' = EW. i i ] /s N " °P V 0P J. 1711 " PlA TT. + EWl 5s i -. . uo . 1 3=1 3 = p ]EC + Ew~i (4.5) Similar results can be obtained for all other queues so (4.5) can be rewritten as -g-= p. EC + EW, (4.6) 0Sj i I Summation of (4.6) over all i gives EC = pEC + EW *=> EC =1^- (4.7) L-p Combination of (4.3), (4.6) and (4.7) gives (4.1)-(4.2) 31 We remark here that (4.1)-(4.2) are very general results that can be obtained by considering equations (2.2)-(2.5) only without assuming any particular service discipline. One also notices that we did not solve (3.12) directly to obtain (4.2). Instead, we exploited the cyclic symmetry of the system to get (4.6) and (4.7), which are much simpler than (3.12). This readily demonstrates the importance of cyclic symmetry In our problem. 4.3 Simplification of the Forcing Matrix B. The solution to (3.12) given by (4.2) can be used to simplify the elements in matrix B to a considerable extent. This is stated in Lemma 4.2. Lemma 4 .2 The elements {b^.. } of the matrix B in (3.12) can be simplified as N o(s + H ) o(6. + H ) biJ " [ K 5s, 5s. ] EC <*'8> J k=l i j where 0). Ci = V + EC 2 varMj varL^ varW^ Pi (TH^J2 + Pi EL^~ + "EC (4'8a) EMj = average message arrivals at queue i in a slot, varMj = variance of message arrivals at queue i in a slot, EL^ = average message length at queue i, varLj = variance of message length at queue i, varWi = variance of switching overhead from queue i to the next queue; for the time continuous system with Poisson arrivals, 32 * .. . i ri = ai + -EC varWj = EMj ELj2 + -gg— (A.8b) ELj2 = second moment of the message length at queue i. Proof of Lemma A.2: From the definition of {b^^ } given in (3.13), we have Y R a? *\ . . a2(sk + V . . .. a(sk + Hk> 5<sk + V ij , ^, ^ 5s, Bs, 3s . ^ 5s, 5s , 5s, 5s. J k=l "k i j i j i j and substitution of (A.2) gives N 52F 52(s, + H ) bi3 " H(VEC+ V)-5TB¥T+ V 5s as J k=l l j I j + V L 5s. ] <*-9> i J From (3.7 a)-(3.7c), we have F. + H, = F. = G, + G~ + ... + G., a i N L 2 N and therefore a2Fk a2(sk + \) = \ EC "aiT^T + "k SiT^T ! i J i J a2Fk a2FN a2sk i J i J i J a2F a2H i J i 3 (A.10) 33 Summation of (4.10) over all k and substitution into (4.9) give 32F N o2H, bii= (pEC + EW> lis-oin - A VEC ii y os,5s . , S Tc 5s.5s . i J k=l I j N 5(sk + Hfc) 5(sk + Hk) +, ^, ^k 6s. 5s. k=l l j pr » r a\ . , a\ , Nv-.. &<8k4flk> rA 1M = EC J t-as-ss-" \ arsr^r^ —ar aT" <A-n> k=l i j l j k=l i j From (3.7 a), we have a\ . .. 9(sk + V 5(sk + V . , &2(sk + V as. as. K. as. as. \ as, as. i 1 i J i J and substitution into (4.11) gives pr » ,. ^ V 5<sk + V a<sk + V ij = k=l ^ ^ ^ = EC ? a(sk + V a(sk + V . , ^, k 5s., as. k=l i j 4.4 The Jacobian Matrix A. To study the Jacobian matrix A, we have to look into the properties of the functions {F^, {G^ and {H^. The functions {G±} and {li\ } are defined iteratively by (3.7a) and (3.7 b). We start with and calculate GN from H then we obtain HN_1 from G^, then G from then from G^ and G^., and the iteration goes on. After we have obained Gp G2, G^ and Hj, H2, ...i 1^ we compute F^ by summing {Gi> over all i and then Fi by (F^ - 1L). These are the basic steps we follow to calculate the elements in A. 34 Lemma 4.3: The Jacobian matrix A in (3.13) can be expressed as A = [u0-u1|u0-u2|u0-u3| ... | u0 - UJJ] where u0 = Pi (l+Pl)P2 (l+p1)(l+p2)p3 (V(l + Pk))PN ->• » ul = N-l 0 0 0 P2 (1+P2)P3 (l + p2)(l + p3)P4 N-l ( n d+Pk))PN k=2 k W o" 0 , u2 (4.12) 0 0 P3 (1+P3)P4 N-l ( n (i+Pk))PN k=3 Proof of Lemma 4.3: From (3.7a)-(3.7c) , we have dG . S(s . + H .) oH 3 _ £ » J 3 _ osj ai ~ 9Si J i dF . 6T dH. 1 m N 1 (4.15) dSj QSj oSj Eqns. (4.13) and (4.14) imply 35 SB. , 5H. i J 1 J 5FN and _ = (i + dH + P1I(i=D j > 1 (4.16a) (4.16b) It can be seen that u. . = (1 + p.)u. + p.e. (4.17) ->• where e. is the ith unit column vector. 3 The iterative relations given by (4.16a) - (4.16b) and (4.17) are identical and since u^, = 0 = [ -g^- ], we conclude that i "i= t -sr ^and uo= t -sr 1 (4-18) J i i Clearly, (4.18) and (4.15) imply the result given in Lemma 4.3 4.5 An Auxilliary Result. We derive an auxilliary result before the derivation of the difference equation relating the unknowns ^v^j} *n tne ne*t section. Lemma 4.4: Let = -z— and I(«) be the indicator function defined earlier in i 5si ' Chapter 2. Then (bi+li+l 2 " [~^T 11+1 ~T~ ^7 11 J a 2 1 a 1 36 Ji+l )t.) + 2t P) I(i-l)] KN 2 i i al (A.19) Proof of Lemma A.4: oH. From the structure of given by (A. 18), we have i as1+1 = Pl asi ai±i^!l j < i < N (^-20) ai asi From (A.8), N a(sk-r Hk) 2 b« •EC jitk[—^T"] i-1 oH. 2 oli = *C [ I tk(-g?) +tj (v *-0fork >1) (A.21) k=l i 1 Thus, a 2 (Vim —r bii} ai i oH, 2 i-1 a oH 2 a 2 °H- ai+l2 -EC ^i -ar— + Vi —r 'i] i+1 at a. 2 = -[t1+1+ (Pl+1--^)tl] ai Using the same results from (A.18) and (A.8), we have 37 d(s + H ) bii=ECti—al" <4-23> Thus, fai+l ai+l2 3i . ^ ^~a~r bn+i —r ^7 11 J 1 a^ 1 _ ai+l , _ ai+l ^ ibli+l ~ blij - lili EC t r _ ll±i i!l + - aj+i aHi i ~ ai 1 asi+i ai ^i+i ai 981 2 a? = -EC t. (—) I(i=l) i < N (A.24) 1 al Combination of (A.2A) and (A.22) give (A.19) A.6 A Difference Equation for the Second Joint Moments of Terminal Service Times. It is difficult, if not impossible, to solve (3.13) in closed form. Analytic solutions are available for the symmetric case and for N=2 only. For the symmetric case, (3.13) can be solved quite easily by arguments based on symmetry i.e. v. . = v . . and v . . = v. ,, .... In fact, v . . is i ndependent ii 33 iJ i+k J+k iJ of i and j so long as i t j for the symmetric case. The algebra involved for the very simple case of N=2 is already very tedious and the solution in this case suggests that there is little hope in the search for a simple formula for the general asymmetric case. Numerical techniques and heuristic approximations were developed but their difficulties have already been discussed in Chapter 1. Here, we derive a simple difference equation 38 relating the unknowns ^vjj)* Although this equation does not allow us to solve (3.13) analytically, it represents a big improvement over existing analytic results. Lemma A .5 : The unknowns {v. .}, modified from {vJ . }, satisfy the following ij ij relation: <DHDV+ PiDV+ PjDH><V 'i ti+l = -2 — I(j-i) + -=-=• I(j = i < j < N (A.25) pi pi+l where v ij p.p .EC 1 J i * j v = { (A.25a) 1 ,Vii . ^ Ci P ,2 var Cj = variance of cycle time of queue i at steady state, D = the forward difference operator in the first index, H = the forward difference operator in the second index; that is W • vij - Vi y Vv<V = DvDH(v1:J) = v. . - vlj+1 - vi+1. + v1+1J+1 . Proof of Lemma A.5: We define r. to be the ith row vector of the matrix [ u11u2|u31...|i^J , 39 ^IN • - T = as in Lemma 4.4 and 1 = (1, 1, 1) . Using these definitions, i we can write the ith row vector of A as ~ Th611 from (3.13), we have v.. = (a.fT - r.T)V(a.f - r,) + b.. ii l ii i ii = a.2fTvf - 2a.fTVr. + r.TVr. + b.. (4.26) l l l l l ii and vu = (a^1 - r1T)V(a1f - r^) + = fTvf - a1?TVr + bu (v = 0) (4.27) Elimination of l^Vr^ using (4.26) and (4.27) gives a. T a. (v - 2 — v,.) = -a. 2f vf + r7Vr. + (b. . - 2 — b..) (4.28) v ii a li.' l ii ii a^ li' Replacement of i by i+1 in (4.28) gives <'i+li+l " 2 if1 Vli+1> " -ai+l2fTvf + r1+lV*i+l+<bl+li+l " 2 af\i+l> i < N (4.29) Elimination of ?TV? using (4.28) and (4.29) gives 3 3 ^ 3 (vi+li+l - 2 I— vli+l> T <V^ " ^7 1 a. * 1 l 3 ^ 3 3 ^ 3 •*• T + i+1 -• „ i+1 . , i+1 ,u 9 1 K i = ri+l Vri+1 T Vri+(bi+li-rl"2 T. bli+l} ^ i* aT a. 1 a. * 1 l i a 2 = r.^VrV, --i±^Lr.TVr. + b. . i < N (4.30) 1+1 1+1 oil 11 a. * l where AO 2 \i = <Vi i+i"2 TT bW - ~r (bii"2bii} 1 ^ 1 a 2 a 2 = EC [t^ + (p1+1 t±) + 2^^) I(i = l)] i<N (A.30a) V 1 Eqn. (A.30a) is obtained by Lemma A.A. Now, T a 2 ri+lVri+l T ri a. z l N N OR. dH0 a. . 2 dH, dH . Y Y r 1+1 k A -I =,^. // as,,, as... 2 ^ os- J Vk* k=l A=l i+1 l+l a^ i l i i dH. dH 0 a. . , 2 dH. dH 0 dH . = y * i±l_k *]v (v^-Oforj)!) k=l W dSi+l 3si+l a^2 i i i i-1 dH i-1 dH dH^ dH, dH, _ y K I + y i * + i i \ii dsi+i dsi+iVkl xii ^i+i asi+iViiL ^i+i ^i+i Vil by (A.20) 5H. i-1 SHk dH. 2 = 2 *^Ti Ji ^I+T Vkl + ("^+T)Vli i-1 a b\ = 2pi+i ^ir^rv^i+iSiby (4-2o) k=l i i g = 27IL±I Pi+1 'i^i + Pi+12 Vii (A.31) Substitution of (A.31) into (A.30) gives ai+l . ai+l2 (vi+n+i - 2 7— vn+i> r (vii " T: VII} 1 a/ 1 i a. = 2 IT1 pi+irl v*i + pi+iSi + bii 1 < N (A'32) Al The next step is crucial in this proof. We notice that all the variables in (A.32) are functions of {p^} and {t^}. By cyclic symmetry, eqn. (A.32) should hold if we perform a cyclic shift of indices i.e. replace p by p^+2.» p^ by p^ and similarly for {t^}. We denote this cyclic shift of indices by the operator CS(»). We further notice that CS(V • vi+ij+i 1»J<N (4-33) CS(p.) = pi+1 i < N and CS^) = P]_ (A.34) CS(t.) = t.^. i < N and CS(t. ) = t. (4.35) cL cl Csf -iii ) = -ii2- i < N-l (4.36ai ai+l With these in mind, we perform the cyclic shift of indices on (A. 32) and £,et 2 (v, + 9,+9 " 2 CS v ) - !i+L^ (v - 2 CS 1 ai+l - 2 — Pi+2CS<VVeV + P"i+2vl+li+l + CS(bii) 1 < h~l (4<37) ai+l i+2 •*• T..+ , . 2 Replacement of i by i+1 in (A.32) gives ai+2 \ ai+22 , „ ai+l (vi+2i+2 " 2 a— Vli+2) : (vi+li+l ~ 2 — Vli+1} 1 a. *• i+1 - 2 — P,„ r^/ve* + R,„V1U1 + b~ +1 i < N-l (4.38) ai+l i+2 i+1 i+1 Ki+2 i+li+1 i+li+1 Noticing that CS(b'ii) = ^ for KKN-1, we can subtract (A. 37) from (A.38) and get 1 1 a 2 ! 1 42 " 2 Pi+2(rVlTveVl " 1< i < N-l (4.39) Now, -> T + T •* ri+l Vei+1 - cs(ri Vei> i dl^ 1-1 oH^. = E li— Vki+1 ~ CS ( I IT vki) k-1 1+1 k-1 1 Y V aHk+i " k-i ^i+iVki+1" kii asi+iVk+11+1 i 5H, i 5H^ v. = y v - y k= OH k-1 ^1+1 kl+1 k=2 5S1+1 kl+1 1 v. &si+l 11+1 1+1 v, . i < N (4.40) 1+Pl li+1 Moreover, a, a CS f—) = -iii 1 < N (4.41) VV a2 Substitution of (4.40) and (4.41) into (4.39) gives ,Vli+2 V2i+2^ ^ , ai+2 rVli+l V2i+1 , -^2^ a7)+2ai+2 7^ ^ = 2a „~v1JM 1 < i < N-l (4.42) i+2 1+p li+1 Simplification of (4.42) gives 43 (l+Pl+P1+1)v11+1 - d + P1+1)v2l+1 - d+P!)v11+2 + v21+2 = 0 1 < i < N-l (4.43) (l-rp1-rp.)vli - d+Pl)v21 - <1+Pl)v11+1 4 v21+1 = 0 2 < 1 < N (4.44) Similar calculations can be done for i = 1 and i = 2 and the results are very similar except for the residual terms on the right hand side of the equation. The results are c2 (1 + Pl+P2)v12 - (l + p2) v22 - (1+Pj)v13 + v23 =— (4.45) t. (l+2Pl)vn - (H-Pl)v21 - (1+Pl)v12 + v22 = -2 — (4.46) Combination of (4.44), (4.45) and (4.46) gives <DHDV + PlDV + PjDH^lj £1 C2 = _2 _i i(j=l) + _£ I(j=2) j<N (4.47) pl p2 Cyclic shift of indices on (4.47) yields (4.25). var Cj We would also like to show v.. =—57— given in eqn. (4.25a). From i i fcL (4.26), we have vn = a^fvt + bn = P. 2?TVl" + t, EC. Thus v EC = tTvt 44 ' A A asidsj N N o = I I [ a^--&-P-^-] i=l j=l &SidSj &Si d3j = lim I f {EIT.^T.^] - E[T<k)]E[T <k>]} k*» i-i j=l 1 J 2 N 2 (k) = lim{ E[( f T <k)) ] -(E[ £ 'T ^]) } k+» i-l i-i = lim var var Cn => v 11 EC var C. => vii = -Tc- <4'48> Lemma 4.5 is a major contribution of this thesis. No such simple result relating the joint moments of terminal service times has been reported before. Eqn. (4.25) is a two dimensional linear but spatially variant difference equation. It can be solved up to N arbitrary constants. To see this, we rewrite (4.25) as -H^ij^Vij^i+ij+i^p— ^=i+1> <4'49a> *ij+l = ( l+2p, . _ i fci It H^vil + !¥- v1+u+1] + ~ i-J (4.49b) Using (4.49b), we can express vii+^ including CS(vN_^N) in terms of the diagonal elements. Then we can use (4.49a) to express other off-diagonal elements and their cyclic-shifted counterparts in terms of the diagonal elements in a successive manner. Thus, we can assign N arbitrary values to 45 the diagonal elements and generate a solution to (4.25). In other words, (4.25) is not a complete set of equations that characterize a unique solution. However, we can use (4.48) to generate N equations relating v to other off-diagonal elements. This suggests a new numerical algorithm for solving (3.13). We start with a guess of the diagonal elements, compute all other off-diagonal elements by (4.49a) and (4.49b), update the diagonal elements by (4.48) and repeat the same procedure. The criteria for convergence of this numerical procedure has not been established but experiments have shown that not only does the procedure converge for p < 1, it also converges much faster than the algorithm given in [29]. Eqn. (4.25) is not only useful for numerical solutions, it can also be used to solve (3.13) explicitly for special cases and to obtain approximate solution for the general case. In the next section, we use (4.25) to solve (3.13) for the symmtric case. An approximation based on (4.25) will be presented in the next chapter. 4.7 Solution for the Symmetric Case. As remarked earlier, (3.13) can be solved easily for the symmetric case. We do this in the following Lemma. Lemma 4 .6 If p and tj are independent of i, then the solution of (3.13) is given by (in terms of v. .) 46 where r. . - . w -i T + T-I -Ki*j) (4.50) ij (l+Pi)(l-p) 1 + Pi Pi p = Np±, t = Nti. = v. Proof of Lemma 4.6: By symmetry, vn = v22 ... .NN-From (4.49b), we have 1 li Vi o = vOQ= • . . = v.. 1X = v. . + -r— (4. 51) 12 23 N-1N ii 1+Pi Pi From (4.49a), we have , t. ^ ""^ 1 1 IJ 24 N-2N ii 1+p Successive calculations using (4.49a) show that v. . = v.. + ~ ' i * j (4.53) ij n 1+p. p. Furthermore, v = ±- fTvf 11 EC N N N t. l = y y p. p. v.. + y t. iii jii PIPJ ^ i^ 1 = N(p12yn+t1) + N(N-l)Pl2(v11+I^--^) -P^ll-^ A Vll d+Pl)(l-p) Combination of (4.53) and (4.54) gives (4.50). (4.54) 47 5. MEAN DELAY ANALYSIS. 5.1 Relationship between Mean Message Delays and Service Time Moments. As remarked in Chapter 1, our goal is to analyze the mean message delays on a token-ring. In the last chapter, we concentrated on the solution for the second joint moments of the terminal service times, because there is an intimate relationship between the mean message delays and these moments. This relationship is stated in Lemma 5.1. Lemma 5.1: The mean queueing delay (excluding service) of a message' at queue i is given by ED_(slot; = j (1+pi)(~i. + Ec) +^ { i EL1 - 1) (5.1) i for the discrete time slot system and ED.(Poisson) "I d+PiXv^ + EC) (5.2) for the continuous time system with Poisson arrivals. All quantities in (5.1) and (5.2) are defined earlier in Chapter 4, EC in Lemma 4.1, var M , EM^ and EL^ in Lemma 4.2 and v^ in Lemma 4.5. Recall that the delay in a discrete time slot system is measured in slots whereas the delay in a time continuous system is measured in seconds. Thus, the quantities in (5.1) and (5.2) may have different numerical values even if they represent the same thing. This is important for system conversions such as treating the time continuous system as a limiting case of the discrete time slot system. 48 Proof of Lemma 5.1; The derivation of eqn. (5.1) can be found in [27] but we shall include it here to make this thesis self-contained. Physically, the average mesage delay at a queue on a token ring is the ratio of the sum of all message delays over many cycles to the number of messages served in the same period of time. Let N be the number of cycles T we measure the message delays, ED^ be the expected total message delays in a cycle and EZ^ be the expected number of messages served in a cycle. Then the average message delay ED^ is given by T T N ED ED EDi = IT EZ"- = EZ~ <5-3> c i i T Quantities ED^ and EZj are independent of the cycle because we are only interested in the steady state. For this reason, all superscripts k denoting the kth cycle will be dropped. From (2.1), (2.2) and (2.5), we have EZ = EYj = EC± EMj (5.4) T The quantity ED., is more difficult to calculate. We sum all the message in a typical cycle and let p Cj = previous cycle, P Mj ^ = number of messages arrived in the jth slot of the previous cycle, Zj = number of messages served in the current cycle, r L. . = the length of the jth message being served in the current cycle. 1 > 3 49 The delay of a message consists of two parts: waiting time for the beginning of current service cycle and the sum of service times of messages buffered up front of the queue. By separating these components, we can see that the total delay is given by Z-C -1 TrP P r r C D. = I (C - j) M+ I L (5.5) 1 j-1 1 1,2 j-1 k-1 1} Taking expectation of (5.5) gives ED = Z[\ cJ(cJ-l)EM1 +4 Z^zJ-UELj (5.6) Since Z therefore = E[cJ EM2 + Cj(Cj-l)(EM1)2 - C^EMj = E[Cj(var K± + CjCEM^)2- EM^ ] (5.7) Substitution of (5.7) into (5.6) yields the following after some simplification: EC. EM i (5.8) Substitution of (5.8) and (5.4) into (5.3) gives (5.1). 50 Eqn. (5.2) can be derived from (5.1) as a special limiting case. To do this, we first let the number of message arrivals in a slot be Poisson. Then the term (var - EM^) becomes zero. Next, we let the time slot go to zero while keeping the absolute value (in seconds) of the cycle time fixed. Thus, the constant (- -ijj) effectively disappears from (5.1) and (5.1) Is converted to (5.2) with the units changed from time slots to seconds. 5.2 A Fundamental Relation for {v^}-Eqns. (5.1) and (5.2) show that v^ is an important element of the mean message delays. In fact, it is the only unknown appearing in the mean delay expressions. Therefore, it is helpful to have as much information on {v„ } as possible. Based on Kleinrock's conservation law [15], a simple relation for (VJJ } can be derived. This is stated in Lemma 5.2. Lemma 5.2: The unknowns ^v^j^ satisfy the following equation: j/i^i^ii " T^p (5'9> where N p = 1 p = total system utilization, 1 = 1 1 N t = I *i • i=l Proof of Lemma 5.2: Let us call the general time slot system we are considering System A and denote its parameters with superscript A. We now artificially construct System B with parameters superscripted by B from the following specifications: (i) System B is time continuous with Poisson arrivals, It is important to realize that System B is realizable i.e. no overspecifications or inconsistencies in the parameters. Since the numerical values of {v^} depend only on {p^} and {t^}, we ~ A ~ 3 ' - 3 conclude that v^^ is equal to v^^ for all i numerically. Furthermore, v is independent of the fixed overhead W^, which is the only overhead in System B. Thus, if we let EW^ go to zero, the mean delay at each queue in System B will 1 B ~ B B be given by (I4p^) v^. With EW^=0, System B is now a work conserving system i.e. the server will not be Idle so long as there is a customer in the system. We are now ready to apply the conservation law. Kleinrock's conservation law states that in a work conserving multi-queue system, the intensity weighted mean of the average delays of all the queues is independent of the way the queues are served. The law also states that for any M/G/l system with no preemption, the intensity weighted mean of the average delays is given by (ii) P (iii) var j=l where N . EL. 2 We notice from (A.8b) that 2 B Zi = Pi B E^!) EL' B Substitution of (5.11) into (5.10a) shows o A 2 Ci 2 1 1=1 and therefore N p I 1=1 p Therefore, N p 1»; B i 1 1 B ~2 Z 1-PB r 1 1 , B. ~B i-1 p N 1 B B 1-p r B/I_L B ~ B p t -» 2, P1(1+P1)V =JI— ii B. B B 1=1 * * 1-p Replacing the superscripts B by A gives the desired result. (5.10a) (5.11) (5.12) (5.13) (5.14) 5.3 An Approximation for {v^j}. To obtain exact solutions for {VJJ}> (3.13) or equivalent equations must be solved. We cannot provide a closed-form analytic solution. However, a very good approximation based on Lemma 4.5 can be derived. We start by considering the difference (v22 - v^). From (4.26) or (4.27), we have 1 *T (5.15) and 53 v22 = — CS(?TV1) ' (5.16) where CS(») Is the cyclic shift operator defined in Sec. 4.6. Subtraction gives (v22 - vn) =^ (CS(fTV?) - 1TV1) N-l N = Ect.^CS(V-.=^lj] - 2 [jIiCS(p.pNv.N) -l^ Plp. vx.] = 2 [^PxP^S^.^-^p.p.v,.] = 2P1 ^ Pj+JCS^N>-^lj+J <5'l7> Now, assuming that the total utilization is low, all the coefficients appearing in (4.49a)-(4.49b) can be essentially replaced by unity and thus 'i+l Vij * Vi+lj + Vi+lj+l " p^; I(j=i+1) 1 < J v..+1 - { (5.18) 1 ~ Zi i (vii+ vi+n+i) +T: 1 = J Successive calculations of the off-diagonal elements using (5-18) gives v~ij 4<*ii + v + -pf 4<J (5-19) Substitution of (5.19) Into (5.17) gives (v22-vn) - 2Pl Y PJ+1[CS£ (Vj^) + 1*) (vn+v.+1.+1) - Ii ] N_1 C4+1 t7 54 N-l tl N-l = 2pi [^ Vi ^ PJ+I] = 2Pl [ (t-t^ -ll (p- Pl)] Pi t = 2pt (— - —) (5.20) •P By cyclic symmetry •P Using (5.21), the left hand side of (5.9) can be computed as follows: ^i+ii+i" v~ii * 2pt £"7^ (5>21) N N i-1 p. t. I Pid + Pi^ji - I PjCl+Pj) [vn + 2pt I ) ] i=l 1=1 j=l N N i-1 p. t. = i p (i+p ) v + 2Pt i j Pi(i+Pi) (-^-r1 ) <5'22> i-1 i-1 j=l p Thus, (5.9) can be used to calculate as *u te t TV 2PT I ^ pi(1+pi) ("S1--^ )] / I pi<1+pi> (5-23> p i-1 j-1 H i-1 By cyclic shifting of indices, we can compute ^22' v33' '*'» VNN* Unfortunately, the double sum In (5.23) cannot be simplified for general cases so we have to leave it as it is. 5.4 Comments on the Approximation for {v^}* It is important to establish or have some indication on the region of validity of our approximation given by (5.21) and (5.23). Clearly, our approximation is exact for the symmetric case. From the low-traffic assumption we made to establish (5.18), our approximation should also be very 55 good at low traffic levels. Although (5.21) is not exact, it suggests that the differences among (v^ } are small compared with the actual values of {v^ } at very high traffic levels (p •*• 1). With this assumption and using Lemma 5.2, we can write N 'ii K ~l-p ' J1Pi(1 + Pi> (3'24) for p close to unity. This matches the dominant term in (5.23). Thus, we expect (5.23) to work well at high traffic levels as well. As a matter of fact, comparisons with exact numerical results have shown that the approximation given by (5.21) and (5.23) is very good over a very wide range of the parameters (Pj) a"d {t^}•. These comparisons will be discussed in the next section. A nimber of interesting properties of {v^^} can be deduced from (5.21) and (5.23). Eqn. (5.23) shows that v^ consists of two parts. The first part is a hyperbolic function independent of i that grows unbounded as p •+ 1. The other part is the position dependent part given by a double sum. Eqn. (5.23) is also linear in t^, which conforms with the linearity of the exact equation (3.13) with respect to t^. Eqn. (5.21) gives a somewhat different flavour about }; it shows the relation of v^^' s between adjacent queues. For example, (5.21) suggests that a queue 'suffers' if the preceding queue has a large fraction of the total utilization but 'benefits' if that preceding queue has a large t^. If t^ is directly proportional to Pi, (5.21) predicts that v^ is approximately independent of i. This special case corresponds to the time continuous system with Poisson message arrivals, fixed overheads and a constant message length for the whole system. 5.5 Comparison of Approximation and Exact Numerical Results for {v^}* In this section, we compare the approximations given by (5.21) and (5.23) with exact numerical results. The biggest problem in the comparison is the search for representative cases, because we cannot possibly do the comparison for all conceivable combinations of parameters. Besides the number of queues N in the system, the parameters needed to solve (3.13) are (Pj) and {tj}. These parameters cannot take on arbitrary values. First of all, they are all positive. Secondly, the total utilization p of the system should be less than unity. Even with these restrictions, the parameter space is still unmanageably large. Since the approximation is exact for the symmetric case, we certainly should look into highly asymmetric cases. Furthermore, we notice from (4.8a) that var Mj var L. var W^ This suggests that t^ can be very roughly regarded as a linear combination of var M. - var L. var W. o iii p. , Pj, 1 if the normalized variances j , —gj- and —— do not vary 1 (EM.) i l appreciably among the queues. For this reason, we shall look into cases for tja Pj2, t^ <* p^ and t^ « 1. With these considerations in mind, we do the comparisons for all possible combinations of the following parameters: (i) N = 8, 16. (ii) t± cc ?2t p^ i, !/p^ l/p^. 57 (iii) 0.01 < p < 0.99 with steps of 0.01. (iv) 1 large user with utilization 100 times that of other identical users, 1 small user with utilization 0.01 times that of other identical users, 2 clusters of identical users with utilization ratio of 1:5. In each case, the relative errors (absolute value) between the approximation and the exact numerical solution are computed for all queues; then the maximum and the average of these relative errors among the queues are plotted against the total utilization. There are five curves, labelled from 1 to 5, in each graph. Curve 1 corresponds to the case of t^ « P±^' 2 to t^ « p^, 3 to t^ « 1, 4 to tj <* 1/Pj, 5 to tj « 1/pj2. The plots are shown at the end of this section. Some of the curves in these plots are too close to be labelled separately so they will be labelled as a group. As expected, our approximation works well under very light and very heavy traffic, as shown In the plots. The plots also show that the approximation is very good for t <= p 2, t <* p , t « 1 as well as for all i i i i i cases of a single large user. When t^, <* 1/p^ or t^ <* 1/p^2, the maximum relative errors at medium system utilizations of 0.7-0.8 can be as high as 12%. Fortunately, these are rather unrealistic cases. For example, in the D-net protocol, var W^ = 0 and so from )(4.8a) var M var ti = pi2 TEMTT2 + pi ~EL7~ • Therefore, t tends to be small if p^ is small and this contradicts the inverse relations given by t. « 1/p, and t. * 1/p, 2. Even with these 58 unrealistic system parameters, our approximation can still give reasonably accurate results (errors of about 10%). For more realistic parameters, our approximation is excellent (errors of 1 to 2%). Thus, it is not unreasonable to treat our approximation as though it were exact for many applications. .5.1b E versus p for N=8 and 1 single large user, avg 60 61 Fig. 5.3a E versus p for N=8 and 2 clusters of Identical users. & max 6. 0 -=j . 5.3b E versus p for N=8 and 2 clusters of Identical users, avg Fig. 5.4a E versus p for N=16 and 1 single large user, avg 63 64 Fig. 5.6b E versus p for N=16 and 2 clusters of identical users. 65 5.6 Delay-vs-Throughput Results. Eqns. (5.1) and (5.2) show the relation between average message delays and the unknowns {v ^ } while eqns. (5.21) and (5.23) give approximate expressions for ^VJJ}* By combining all these equations, we can obtain an approximate solution for the average message delays. We copy (5.1), (5.2), (5.21) and (5.23) here for easy reference: .... var M. - EM. ED (slot) = 1 (l-^Kv^ 4 EC) +j ( iE^-l) (5.1) i ^(Poisson) .1^)^ +EC) (5.2WI-V^T) (5'21) -ii • [£-P- X X pi(i+p^ {^-^)] ' U(i+Pi> 1=1 J=l i=l There are a nunber of special cases worth attention. (5.23) We first consider the case where v^ is independent or approximately independent of i. With this assumption and using Lemma 5.2, we get (5.24). We can rewrite (5.24) as N v. . --r^- / (1 + I p,2/p) (5.25) 11 1_P i=i 1 Substitution of (5.25) into (5.1) and (5.2) gives / -, i T].t i var M. - EM ED(slot) ml^^+l ( EL^-1 ) (5.26) i and TI t (Poisson) Bj i new (5>27) i 2 1-p where 66 N ? n. = (1+P.) / (1 + I P./p), 1 i=l tnew = t + EWd+j^ p2/p). The first term on the right hand side of eqn. (5.26) is the queueing delay of an»M/G/l single-queue system with appropriate parameters. The second term is due to the non-Poisson nature of the arrivals, which can be positive or negative. The third term arises because all message arrivals are registered at the end of a time slot. For the time continuous system with Poisson arrivals, the last two terms vanish, as noted earlier. For very heavy system traffic (p+1), v is approximately independent of i, as remarked earlier. Thus, (5.26) and (5.27) are valid for this case. Moreover, the hyperbolic term dominates the right hand side of (5.26). Therefore (slot) _ 1 T1itnew , EDi (5,28) and •n t (Poisson) „ 1 'i new (5.29) i 2 1-p Eqns. (5.28) and (5.29) show that the average delays for both slot and Poisson arrivals are approximately proportional to (1+p^) as p •*• 1. This in turn implies that if a system has a user with utilization close to unity, the delay suffered by this user is roughly twice the delay suffered by other users. For very low system traffic (p •*• 0), (5.21) implies is 67 approximately independent of i. Thus, (5.26) and (5.27) are again valid in this case. Furthermore, 1 T1itnew 1 j \"p - j (t + EW) (5.30) By making the reasonable assumptions that var •* 0 as EM^ •*• 0 and var Lj > 0 as EL^ •*• 0, we can further approximate t for p •* 0 by i N 1 V TT Var W /COIN EC lml var wiw -sr (5-31) where N EW = I EW i-1 N varW = 1 varW.. i-1 1 Therefore, varM — EM EDi(slot) . 1 (varW + ^ + 1 ( i__i ^ and £ (Poisson) 1 (varW + £W) (5 l 2 v EW ' If var W = 0, then (Poisson) m 1 EW (5>34) Eqn. (5.34) is intuitively clear but (5.33) shows a more subtle result if var W * 0. For the time slot system, more information is needed on the arrival statistics in order to simplify (5.32) any further. For the system with a single dominant user, that is, p^ and t^ for the dominant user are much greater than p^'s and t^s for the other users, eqn. 68 (5.21) again implies that are approximately Independent of I. Thus, (5.26) and (5.27) are valid in this case. Furthermore, 1 ^i t new 1 t + EW(l + p) 2 iTp~ 2 1=^ for the dominant user and 1 Vnew 1 1+Pi t + EW(l + p) , _(5.36) for all other users. For the system with N-l identical users and a single small user, that Is, p, and t. for the small user are much less than p.'s and t.'s for the i l ri i other users, eqn. (5.21) implies once more that v ^ is approximately independent of i. As a result, (5.26) and (5.27) are valid. Furthermore 1 Vnew _1 1 t+EW(l+p/(N-l)) 5 . 2 1-p " 2 1+p/(N-l) 1-p 1 ; for the small user and 1 Vnew 1 t+EW(l+P/(N-l)) ,. 2 i-p 2 ——r^p (5,38) for the other identical users. For tj * p^, eqn. (5.21) again implies that v.... is approximately independent of i so eqn. (5.26) and (5.27) are again valid. For the system with clusters of identical users, eqn. (5.21) shows that v^i's obey a linear relationship within each cluster. This linear relationship in turn shows that the delays given by (5.1) and (5.2) are linear within each cluster of identical users. 69 In most of the special cases considered so far, v^^ is approximately independent of i. This is verified for the following combinations of parameters: (i) N-8. (ii) t4 = pj, Pi, 1. (iii) 0.01 < p < 0.99 with steps of 0.01. (iv) 1 large user with utilization 100 times that of other identical users, 1 small user with utilization 0.01 times that of other identical users. 2 clusters of identical users with utilization ratio of 1:5. There are two plots for all combinations of (iii) and (iv). The first plot consists of the exact numerical solution for {v^ } versus p (8 curves) and the second plot consists of the normalized variance of iVj. j } versus p. The normalized variance of ) is defined as var<*ii> =^2 \ <'ii-»>2 (5'39) Nm 1=1 where 1 N ~ 70 71 Fig. 5.3a v.. versus p for N=8, 1 single large user and tj-P^ ,r t V ) 110' 32. C -H 24. C -H 1 6. G e. o —j 0 0 ~| ll.l|riiTT7MMlM,.IMI|imMN.|IUlllm|l Il'l"111""!"M|IMIIMII|Mllllin|l,llin 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.S 1.0 Fig. 5.8b var(vljL) versus p for N=8, 1 single large user and t^p^ 72 73 7 4 0. Fig. 75 Fig. 5.12a v.. versus p for N=8, 1 single small user and t =1. 76 Fig. 5.13a v.. versus p for N=8, 2 clusters of identical users and tj-p.2. vortV ) 110"') 6.0-3 Fig. 5.15a v.. versus p for N=8, 2 clusters of identical users and ti=l. 79 5.7 Finite Buffering and Non-exhaustive Services. We have assumed infinite buffering and gated exhaustive service throughout this thesis. Nevertheless, we can use our results to approximate the more realistic cases of finite buffering and non-exhaustive services. We start by considering the finite buffering case. Two kinds of buffer designs are possible, message buffering and slot buffering. As their names imply, a message is the fundamental unit in message buffering and a slot of a message is the basic unit in slot buffering. While slot buffering appears to be more efficient in terms of memory requirements, message buffering allows for hierarchical buffer management. We shall consider message buffering here. Let us modify the infinite buffering system we have considered to a finite buffering system with n^ message buffers at queue i. As long as the blocking probability is small, we can approximate the finite buffering system by the infinite buffering system. We further approximate the blocking probability at queue i by (block) „ 11b prob(x00 > ) (5.A0) This approximation is based on the assumption that the queue length is a local maximum at the scan instants. From (2.1) - (2.5) and previous analysis, we have EX, = EM. EC (5.41) i l and var = var Y^ = var M± EC + (EM^) EC^ = var H± EC + var C± (Eti±)2 + (EM1)2(EC)2 = [var H + (EM1)2(vii + EC)] EC (5.42) where all variables are defined earlier. The blocking probability given by (5.40) can be bounded using (5.41), (5.42) and Chebyshev's inequality which states that °x2 Prob(|X-m | > 6) < (5.43) X 6Z where X is any random variable, is the mean of X and aY2 is the variance of X. By choosing n^ large enough, we can limit ^(b-*-ock) to an acceptable level. No tice that {n^} depends on (p^) and { t^} . Thus, we cannot choose a fixed set {n^} to keep {u^k^oc,c)} small for all loading conditions. In fact, n^ grows unbounded as p + 1. The problem of approximating non-exhaustive services by the gated exhaustive service scheme is similar to the approximation for finite buffering. Let us consider the general gated non-exhaustive service where up to p^ messages are served in each cyclic service of queue I. Let v^ be the probability that the scan queue length (number of messages buffered at the scan instant) at queue I is greater than p^. As long as v^ is small for all i, we can approximate the gated non-exhaustive service reasonably well by the gated exhaustive service. We further assume that can be approximated by 81 v± » 11m Prob (X v J> p ) (5.44) k-*= Again, can be bounded using (5.41), (5.42) and (5.43). By choosing the appropriate ip^} and {t^ }, we can limit within the desired level. Thus, we can obtain a region of loading conditions under which the gated non-exhaustive service can be approximated by the gated exhaustive service. In general, for a sufficiently small p, the gated non-exhaustive service can always be approximated by the gated exhaustive service. For heavy traffic, one can use various heavy traffic approximations; see for example [15]. For intermediate traffic, interpolation techniques could be used. 82 6. CONCLUDING REMARKS. 6.1 Summary of the Results. Recently, applications of fiber optics to LANs and the development of UBSs have intensified interest in the performance analysis of token-ring systems. As a first step, the average message delays in a general asymmetric token-ring under gated exhaustive service discipline have been investigated in this thesis. Although the gated exhaustive service discipline is a special case, it provides insights and low-traffic approximations for most non-exhaustive service schemes. The approach used in this thesis is to formulate and solve the imbedded Markov chain of the joint terminal service times. Recursive linear equations are derived for the first and second joint moments of the imbedded chain. The existence and uniqueness of solutions to these equations are also established. A number of results concerning the solutions are also derived. Among these, the simple difference equation relating the second joint moments of the terminal service times is a significant contribution of this thesis. Such simple results have never been reported before. Based on equation (4.25), a very good approximation given by (5.21) and (5.23) is derived. This approximation is exact for the symmetric case and it works very well over a wide range of system parameters for the asymmetric case. Even under very unusual circumstances, the relative errors in the approximation are still acceptable (~10%). Some delay-vs-throughput results based on the approximation are also discussed. 83 6.2 Suggestions for Further Work. The performance analysis of a general token-ring is a very difficult problem. In this thesis, a special case has been investigated but the ultimate goal is to solve the general problem. Thus, future work in this area should concentrate on the generalizations of the work in this thesis. Emphasis has been placed on the average message delay as a performance measure. This can be generalized to include the delay variance. The delay variance is of considerable interest in many applications such as packetized voice and interactive terminal conversations. In our model, the delay variances depend on the third joint moments of the terminal service times. The analysis will involve a third differentiation of the basic functional equation (3.9) and the solutions of (3.12) and (3.13) to set up the necessary equations for the third joint moments. The problem is to examine the solution of those moments. Generalizations to even higher moments are possible but they tend to be difficult and less useful for practical purposes. Although the arrival model used in this thesis appears to be very general, it is still inadequate for many practical situations. For example, our arrival model does not accommodate deterministic arrivals in voice applications and dependent arrivals in functional distributed computing. Thus, generalizations on the arrival model is desirable. Perhaps the most interesting generalizations are associated with the service discipline. First of all, we have assumed the cyclic service schedule in this thesis. In other words, each queue has a cyclic priority which cannot be interrupted by other queues. In a general polling system, 84 many possible priority assignments are possible. Even in- a token-ring, the basic protocol can be modified to accommodate various priority schedulings. The assignment of priorities, static or dynamic, is a design parameter which deserves further attention. Secondly, generalization of the gated exhaustive service discipline to the more general non-exhaustive schemes would be very useful. This is because non-exhaustive service schemes can be implemented very easily on a token-ring. Unfortunately, the rigorous analysis of non-exhaustive service schemes appears to be very difficult. Very often, one should contend with approximate approaches. One approximate approach is to note that most non-exhaustive schemes can be approximated by the gated exhaustive service discipline at low traffic levels; for heavy traffic, one can use various heavy-traffic approximations, see for example [15]. Thus, the difficult case occurs when traffic is between the two extremes. One further generalization can be made on the service discipline. We (k) notice that in all 'static' service disciplines, can be derived (k) directly from (e.g. the relation given by eqn. (2.1)). One can generalize this dependence. For example, In the D-net protocol, each station can detect the length of a train fairly easily and estimate the current (k) (k) network loading, and then the station can determine not only from X^ but also from previous network loading estimates. Such elaborate service disciplines may not be justified for many LAN applications but we cannot be sure until we have done the analysis. 85 There are some relatively less urgent matters, for example, finite buffering, dependent switching overheads, and time-variant system parameters whose effects could also be examined-86 References [I] A.S. Tanenbaum, Computer Networks, Prentice-Hall, Inc., 1981. [2] W. Stallings, Local Networks: An Introduction, New York: MacMillan, 1984. [3] D.D. Clark, K.T. Pogran, and D.P. Reed, "An Introduction to Local Area Networks," Proc IEEE, vol. 66, no. 11, pp. 1497-1517 , Nov. 1978. [4] R.M. Metcalfe and D.R. Boggs, "Ethernet: Distributed Packet Switching for Local Computer Networks," Commun. Ass. Comput. Mach., vol. 19, pp. 395-404, 1976. [5] S.D. Personick, "Review of Fundamentals of Optical Fiber Systems," IEEE J. Selec Areas Commun., SAC-1, no. 3, pp. 37 3-380, Apr. 1983. [6] N.L. Rhodes, "Interaction of Network Design and Fiber Optic Component Design in Local Area Networks," IEEE J. Select. Areas Commun., SAC-1, no. 3, pp. 489-492, Apr. 1983. [7] M.R. Finley, Jr., "Optical Fibers in Local Area Networks," IEEE Communications Magazine, vol. 22, no. 8, pp. 22-35, Aug. 1984. [8] E.G. Rawson and R.M. Metcalfe, "Fibernet: Multimode Optical Fibers for Local Computer Networks," IEEE Trans. Commun., COM. 26, no. 7, pp. 983-990, July 1978. [9] R.V. Schmidt, E.G. Rawson, R.E. Norton, Jr., S.B. Jackson, and M.D. Bailey, "Fibernet II: A Fiber Optic Ethernet," IEEE J. Select. Areas Commun., SAC-1, no. 5, pp. 702-710, Nov. 1983. [10] E.S. Lee and P.I.P. Boulton, "The Principles and Performance of Hubnet: A 50Mbit/s Glass Fiber Local Area Network," IEEE J. Select. Areas Commun. SAC-1, no. 5, pp. 711-720, Nov. 1983. [II] F.A. Tobagi, F. Borgonovo, and L. Fratta, "Expressnet: A High-Performance Integrated-Services Local Area Network," IEEE J. Select. Areas Commun., SAC-1, no. 5, pp. 898-912, Nov. 1983. [12] C.-W. Tseng and B.-U. Chen, "D-Net, A New Scheme for High Data Rate Optical Local Area Networks," IEEE J. Select. Areas Commun., SAC-1, no. 53, pp. 493-499, Apr. 1983. [13] J.0. Limb and C. Flores, "Description of Fasnet: A Unidirectional Local Area Communications Network," Bell Syst. Tech. J. vol. 61, no. 7, Part I, pp. 1413-1440, Sep. 1982. [14] L. Kleinrock, Queueing Systems, Vol. 1: Theory, New York: Wiley, 197 5. L. Kleinrock, Queueing Systems, Vol. 2: Computer Applications, New York: Wiley, 197 6. H. Kobayashi and A.G. Konheim, "Queueing Models for Computer Communications System Analysis," IEEE Trans. Commun., COM-25, no. 1, pp. 2-28, Jan. 1977. W. Bux, "Local-Area Subnetworks: A Performance Comparison," IEEE Trans. Commun., COM-29, no. 10, pp. 1465-1473, Oct. 1981. W. Stallings, "Local Network Performance," IEEE Communications Magazine, vol. 22, no. 2, pp. 27-36, Feb. 1984. L. Takacs, "Two Queues Attended by a Single Server," Oper. Res., vol. 16, no. 3, pp. 639-650, 1968. B. Avi-Itzhak, W.L. Maxwell, and L.W. Miller, "Queueing with Alternating Priorities," Oper. Res., vol. 13, no. 2, pp. 306-318, 1965. M. Eisenberg, "Two Queues with Changeover Times," Oper. Res., vol. 19, pp. 386-401, 197 1. R.B. Cooper and G. Murray, "Queues Served in Cyclic Order," Bell Syst. Tech. J., vol. 48, no. 3, ppv675-689, Mar. 1969. R.B. Cooper, "Queues Served in Cyclic Order: Waiting Times," Bell Syst. Tech. J., vol. 49, no. 3, pp. 399-413, Mar. 1970. M. Eisenberg, "Queues with Periodic Service and Changeover Time," Oper Res., vol. 20, pp. 440-451, 1972. A.G. Konheim and B. Meister, "Waiting Lines and Times in a System with Polling," J. Ass. Comput. Mach., vol. 21, pp. 470-490, 1974. G.B. Swartz, "Polling in a Loop System," J. Ass. Comput. Mach., vol. 27, pp. 42-59, 1980. I. Rubin and L.F.M. DeMoraes, "Message Delay Analysis for Polling and Token Multiple-Access Schemes for Local Communication Networks," IEEE J. Selec. Areas Commun., SAC-1, no. 5, pp. 935-946, Nov. 1983. Y. Aminetzah, "An Exact Approach to the Polling System," Ph.D. dissertation, McGill Univ., Montreal, P.Q., Canada, Mar. 1975. M.J. Ferguson and Y.J. Aminetzah, "Exact Results for Nonsymmetric Toke Ring Systems," IEEE Trans. Commun., COM-33, no. 3, pp. 223-231, Mar. 1985. 88 [30] R.T. Carsten, E.E. Newhall, and M.J.M. Posner, "A Simplified Analysis of Scan Times in an Asymmetric Newhall Loop with Exhaustive Service," IEEE Trans. Commun., COM-25, no. 9, pp. 951-957, Sep. 1977. [31] W. Bux and H.L. Truong, "Token-ring Performance: Mean Delay Approximation," in Proc. 10th Int. Teletraffic Cong., June 1983, pp. 3.3.3.1-3.3.3-7. [32] M. Leibowitz, "An Approximate Method for Treating a Class of Multiqueue Problems," IBM J. Res. Develop., vol. 5, pp. 204-209, 1961. [33] S. Halfin, "An Approximate Method for Calculating Delays for a Family of Cyclic Type Queues," Bell Syst. Tech. J., vol. 54, no. 10, pp. 17 33-17 54, Dec. 197 5. [34] P.J. Kuehn, "Multiqueue Systems with Nonexhaustive Cyclic Service," Bell Syst. Tech. J., vol. 58, no. 3, pp. 671-698, Mar. 1979. [35] S.S. Nair, "Alternating Priority Queues with Non-Zero Switch Rule," Comp. and Opns. Res., vol. 3, pp. 337-346, 197 6. [36] C. Mack, T. Murphy, and N.L. Webb, "The Efficiency of N Machines Unidirectionally Patrolled by One Operative when Walking Time and Repair Times are Constants," J. Royal Stat. Soc, ser. B, no. 19, pp. 166-172, 1957 . [37] A.R. Kaye, "Analysis, of a distributed control loop for data transmission," in Proc Symp. Comput. Commun. Networks Teletraffic, Polytech. Inst., Brooklyn, NY, Apr. 197 2. [38] F.A. Tobagi and M. Fine, "Performance of Unidirectional Broadcast Local Area Networks: Expressnet and Fasnet," IEEE J. Select. Areas Commun., SAC-1, no. 5, pp. 913-925, Nov. 1983. 89 APPENDIX: Eigenvalues of the Jacobian Matrix A. A number of results regarding the eigenvalues of the Jacobian Matrix A are proved in this Appendix. Lemma A.l: The characterstic equation |A—rI[ = 0 of the matrix A is given by Q(r) = { n [(l+p.)r - p.] - rN+1} / (1-r) = 0 1=1 (A.l) Proof of Lemma A.l: From the structure of A given by Lemma 4.3, we claim that A can be written as follows: (A.2) A " TNTN-1' .T^DR where Ti • h-l 0 0 pipi'"pi 1 0 0 0 h 1^ = k x k identity matrix, D = J2 . R = 1 1 .... 1 1 o • • . i To see this, we successively compute T^D, T^TjD, .... TN^-]/--1!0 AND 8et TNTN-r*'TlD = [pA+^\P2^2+e2^--'^^+t^] (A'3) 90 where and e^ are defined in Lemma 4.3. Then we notice that 2 N TNTN-1'"T1DR = lPl<V*l>l J,^\+\^''-l\^\+\^ <A'4> k=l k=l N and uj[_1 = I \(\ + e^.) (A.5) k=i Thus, TNVr"TiDR = IV"IIV"2I'--IV"N] • A* The determinant |A— r11 can now be computed as follows: |A - rl| = | TDR - rl| - |T| |D - rT"1^1 | |R| (A.6) where T = T T _.. .T.. N N-l 1 We notice that |T| = |R| =1 so |A - rl| = |D - rT-1R-1| = |D - rTj"1^"1...^"^"1! (A.7) The inverses of T^' s and R can be expressed by 1 -1 1 -1 -1 0 Using these to calculate T^R-1, T^jT^1*"1 » * * *' ^^i^ '' ^N1**"1 xk-l 0 0 -Pk-V-'-Pk I 0 0 0 IN-k successively, we have 91 .'. D - rT~1R~1 pir+pr(1+pi)r P2r p3r -1 -1 -p2 l+p2 -1 0 3 "P-1+P3 . N * . -1 1+p. N P2"(l+P2)r P3-(1+P3)r PNr (A.8) —I (A.9) The determinant of the above matrix can be split into a sum of determinants of two matrices and U2 where Ul = plr p2r P2~(1+P2)r P3-(1+P3)r PNr pN"(1+pN)r and U2 " p1-(l+p1)r p2-(l+p2)r PN-(1+pN)r Clearly, 92 |u2| = nJPl - d+Pl)r] (A.10) Factorizing Pj from each row of 1^ and then from the first column, we have N (A.11) |uj = ( n P ) |u | 1 i-i 1 -where U3 = 1-r 1-r r 77 l-(l+i )r r l-(l+-7-)r r PN-1 1-r 1-(1+ -i-)r pN -I Replacement of the first column by subtracting from It the sum of all other columns yield U4 " r 1-(1+ ~)r p3 r pN-l 1 1-(1+ - )r J-pN JN —I (A.12) where |U,| = |U | 93 Clearly, N . N |U | = n [1 - (1 + —)r] + (-if n (-^-) (A.13) i-1 Mi 1=1 Pi Using (A.10)-(A.13) and after some algebra, we have |A-rl| = luj + |U2| = T^ <-DN 1 " [ d+P^r-p.] - r^1} (A.13) 1=1 11 N Since the factor (-1) is unimportant in the characteristic equation, we arrive at (A.l) Notice that the characteristic polynomial Q(r) is indeed of degree N N N+l because IT [ (1+p. )r-p. ]-r is divisible by (1-r). Also, Q(r) does not 1=1 ii depend on the specific order of the queues, that is, shuffle of the queue positions will not affect Q(r). Lemma A.2: N Let p = 1 p, be the system utilization and p < 1. Then there exists < 1 = 1 positive real root of the characteristic equation Q(r) = 0 and it is bounded by p. Proof of Lemma A.2: N N+l Let f(r) = II [(1+P.)r - p ] and g(r) = r 1=1 Clearly, f(l) = 1 = g(l) 94 N • and f (1) = I p + N < N+l = g'(1). 1=1 Therefore, there exist e > 0, which can be arbitrarily small, such that f(l-e) > g(l-e). Pi Next, we notice that f(r) = 0 has exactly N real roots at r = ^ , all Pi lying between zero and one. Let t be the maximum of -r-— , then J 6 max 1+pj f(t ) = 0 < g(t ). max max Since t < 1, we can choose e such that t < (l-e)» From the max x inequalities shown above, there must exist a real root of Q(r) = f(r) - g(r) = 0 between t and (1-e). In fact, there is only one real root of Q(r) = 0 between t and (1-e) because f(r) and g(r) are both max monotonic in that region. We shall call this root r ° max To show r < p, we look at (Jin f(r) - An g(r)) on the interval max [t ,1). 1 max N Jui f(r) - Jui g(r) = I An[ (1+p )r-p ] - (N+l) An r 1=1 N = I An[l - (1+p )(l-r)] - (N+l)An(l-(l-r)). 1=1 Let 6 = 1-r and expand the logarithmic function in Taylor's series at r=l to obtain An f(r) - An g(r) N - (1+p ) 6 - 6k = -I I 1 + (N+D I — i=l k-l k k-1 95 N . .k = I [(N+l) - I (1 + Pl)k]f k-1 i-1 = I [(N+i) -1 (i +1 Pj)]^ k-1 1=1 j-1 J N k . *k = I [1 - I I {)) P?]£ k-1 1=1 j-1 3 1 k , N . -k k=l j-1 J i=l 1 K k . N . ,k k-1 j-1 J 1=1 1 * N . ck = I [I - (1 + I Pl)k+ l]f k-1 1=1 1 -I 2 -r - X k-1 k-1 = -2An(l-6) + An(l-(l+p)6). Setting r = 1 - 6 = p, we have An f(p) - in g(p) > -2An p + An p2 = 0. Therefore, f(P) > g(p). Since p > t , we can deduce that t < r < p. max max max Lemma A.3 All the eigenvalues of A, real or complex, have magnitudes less than or equal to r if p < 1. ^ max 96 Proof of Lemma A.3: We prove Lemma A.3 using the famous Rouche's Theorem in complex analysis which states the following: If f(z) and g(z) are analytic in a closed region on the complex plane with a simply connected boundary C and if |f(z)| > |g(z)| on C, then f(z), f(z) + g(z), f(z) - g(z) all have the same number of zeros inside C Let us consider a semicircle on the right half complex plane with centre at the origin and radius R = r + E < 1 with E > 0 shown in ° max Fig. A.l. Fig. A.l Right-half plane semicircle. 97 N N+1 We let f(z) = II [ (1+p, )z - p ] and g(z) = z . On C. , 1=1 1 1 N |f(z)| = n |(i+p.)z - P,| i=i 1 N = n |(l+p )R(cos9 + jsinB) - p | (j2="l) 1=1 1 N 1/2 = II [(1+p )R2 + p2 - 2(l+p )p Rcose] 1=1 N 1/= n [((1+p )R - p )2 + 2(l+p )p R(l-cos9)] 1=1 1 N > n |(i+P.)R - p I 1=1 = f(R) > g(R) - feU) I-On C^, z = jy and |f(z)| = n [(i+Pl)2y2+Pl2]1/2 > yN > yN+1 = |g(z)| 1=1 1 1 By Rouche's Theorem, f(z) and f(z) - g(z) have the same number of zeros inside C. Clearly, f(z) has exactly N real zeros inside C so f(z) - g(z) should also have N zeros inside C. We already know that the (N+l)th zero of f(z) - g(z) is at z = 1. Thus Q(z) = (f(z) - g(z))/(l-z) = 0 has all N zeros inside C. Therefore, all eigenvalues of A have magnitudes less than R = r + £• Since e can be arbitrarily small, we can deduce that all eigenvalues of A have magnitudes less than or equal to r . Moreover, r < p < 1 shows c ^ max max that A has eigenvalues of magnitudes less than unity.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Mean delay analysis for unidirectional broadcast structures
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Mean delay analysis for unidirectional broadcast structures Pang, Joseph Wai Ming 1985-05-28
pdf
Page Metadata
Item Metadata
Title | Mean delay analysis for unidirectional broadcast structures |
Creator |
Pang, Joseph Wai Ming |
Publisher | University of British Columbia |
Date Issued | 1985 |
Description | Unidirectional broadcast structures constitute a class of high performance local network architectures. They are very flexible and well suited for fiber optic implementation. The access methods used in these networks are often based on certain implicit token-passing mechanisms to provide superior delay-vs-throughput characteristics. The performance of these unidirectional broadcast protocols is evaluated in this thesis via a study on the classical token-ring system. Emphasis is placed on the analysis of mean delay-vs-throughput performance for the gated exhaustive service discipline under asymmetric traffic. The analysis involves examination of the statistical behaviour of interacting queues. A number of exact results are derived and based on these results, a very good approximation for the average delays is developed. The approximation agrees closely with exact numerical solutions over a wide range of system parameters. The implications of the approximation are also discussed. |
Subject |
Local area networks (Computer networks) |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-05-28 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0096210 |
URI | http://hdl.handle.net/2429/25104 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-UBC_1985_A7 P35.pdf [ 3.88MB ]
- Metadata
- JSON: 831-1.0096210.json
- JSON-LD: 831-1.0096210-ld.json
- RDF/XML (Pretty): 831-1.0096210-rdf.xml
- RDF/JSON: 831-1.0096210-rdf.json
- Turtle: 831-1.0096210-turtle.txt
- N-Triples: 831-1.0096210-rdf-ntriples.txt
- Original Record: 831-1.0096210-source.json
- Full Text
- 831-1.0096210-fulltext.txt
- Citation
- 831-1.0096210.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0096210/manifest