P R O T O C O L S F O R WIDE B A N D S A T E L L I T E S Y S T E M S W I T H A L A R G E N U M B E R OF S M A L L V O I C E A N D D A T A USERS by XU TAN B . S c , Shanghai Jiao Tong University, China, 1982 A THESIS S U B M I T T E D IN P A R T I A L F U L F I L L M E N T O F T H E REQUIREMENTS FOR T H E D E G R E E OF M A S T E R OF APPLIED SCIENCE in T H E F A C U L T Y O F G R A D U A T E STUDIES Department of Electrical Engineering We accept this thesis as conforming to the required standard T H E U N I V E R S I T Y O F BRITISH C O L U M B I A September, 1987 © X u Tan, 1987 In presenting degree this thesis in partial fulfilment of the requirements at the University of British Columbia, I agree freely available for reference and study. I further copying of this department or that the Library shall make it agree that permission for extensive thesis for scholarly purposes may be granted by his or her representatives. for an advanced It is by the head understood that of my copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of 'LLBCTRICAL The University of British Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date OCT- / ? * 7 £A/^JMSSR/Ajq- ABSTRACT Multiaccess protocols for integrated voice and data transmissions over satellite channels are studied, based on the SENET(slotted envelope network) structure. The satellite system is characterized as a wide band system with a large number of geographically distributed small voice and data users. Performance evaluations of commonly used protocols, i.e., ALOHA and reservation protocols, are first conducted, both analytically and by simulations. The effect of different voice backgrounds on data access protocols are shown explicitly. Based on these results, a control algorithm is proposed. Analyses and simulations show that ALOHA protocol incorporated with such a control mechanism is globally stable under the integrated environment; moreover, the performance deterioration due to voice backgrounds is dramatically reduced. The actual implementation aspects of the control algorithm are considered. An extension of the above results leads to a combined random/reservation protocol. Simulation and analysis results show that the combined protocol exhibits desired low delay and high throughput performance characteristics, with satisfactory voice blocking probability, under the worst user population assumption, i.e., all the voice sources and data sources are independent of each other — reflecting the nature of small earth station environment. The absence of the need for mini-slot structure lends ease and simplicity to the implementation of the combined protocol. ii T A B L E OF C O N T E N T S ABSTRACT 1 ii T A B L E OF C O N T E N T S iii LIST OF FIGURES vi LIST OF T A B L E S ix ACKNOWLEDGEMENTS x Introduction 1 1.1 Basic Structure of Integrated Wide Band Systems 3 1.1.1 The W B S A T N E T Structure 4 1.1.2 The S E N E T Structure 5 1.2 Scope of the Thesis 2 8 Voice Packet Transmission 10 2.1 Virtual Connections Protocol for Voice Packets 10 2.2 Voice Pattern Statistics 14 2.2.1 Statistics of Voice Utilization 15 2.2.2 State Correlation of Voice Occupied Slots 22 iii 2.3 Simulations of Voice Pattern Structure 3 2.3.1 Choice of Parameters 26 2.3.2 Results of Simulations 28 D a t a Packet Transmission 38 3.1 Multiaccess Protocols in the IVDS Systems 39 3.2 ALOHA Protocol in the IVDS Systems 43 3.2.1 Acquisition of V(n) 45 3.2.2 Estimation of g{t) 45 3.2.3 Performance Analysis of ALOHA Protocol 52 3.3 Reservation Protocol in the IVDS Systems 3.3.1 Performance Analysis of the Reservation Protocol 3.4 Simulations of the Two Protocols 56 59 66 3.4.1 Simulations of the ALOHA Protocol 66 3.4.2 Simulations of the Reservation Protocol 75 3.5 ALOHA Protocol (The Second Version) 4 26 80 3.5.1 Performance Analysis of ALOHA-II Protocol 81 3.5.2 Effect of Estimation Errors 96 Combined Random/Reservation Protocol 104 4.1 Mode Switching Information 105 4.2 Reservation Request Transmissions 106 4.3 The Combined Random/Reservation Protocol 107 iv 5 4.3.1 Protocol Description 108 4.3.2 System Parameters for CP 114 4.3.3 Asymptotic Analysis of CP 115 4.4 Simulations of CP 121 4.5 Comparison of CP with ALOHA and Reservation Protocols 129 Conclusions and Further Studies 131 Appendix 134 References 141 v LIST OF FIGURES 1-1 Basic Structure of WB SATNET 4 1-2 Illustration of Stream Subframe 6 1-3 Illustration of Data Transmission Procedures 6 1- 4 The SENET Structure 7 2- 1 (a) Voice Assignment Protocol I 12 2-1 (b) Voice Assignment Protocol II 12 2-2 (a) Blocking Probability B(s, a) versus Sf 19 2-2 (b) Blocking Probability B(s,a) 19 2-3 Tail Probabilities, P 2-4 Illustration of Voice Correlation and Data Transmissions 23 2-5 (a) Correlation */{k) for p = 0.5, VAP-I 31 2-5 (b) Slot Distribution P {l) for p = 0.5, VAP-I 31 2-6 (a) Correlation */(k) for p = 0.5, VAP-II 2-6 (b) Slot Distribution P (l) for p = 0.5, VAP-II 32 2-7 (a) Correlation *f(k) for p = 1/3, VAP-I 33 2-7 (b) Slot Distribution P {l) for p = 1/3, VAP-I 33 2-8 (a) Correlation *i{k) for p = 2/3, VAP-I 34 2-8 (b) Slot Distribution P {l) for p = 2/3, VAP-I 34 sp versus Offered Load a' = 0.005 21 v r v v r v v v r v r v vi , 32 2-9 Correlation *j(k) and Sf 35 2-10 Slot Distribution P (l) and Sf 36 r 2- 11 Tail Probability Py and S 37 3- 1 Illustration of Delayed Rule 44 3-2 Bias and Variance of Maximum Likelihood Estimator g 49 3-3 Bias and Variance of Modified Arithmetic Estimator M 53 3-4 Illustration of the Reservation Protocol 57 3-5 (a) Global Queueing Delay D q for VAP-I 60 3-5 (b) Global Queueing Delay D q for VAP-II 60 3-6 Excess Queue Size Aq versus p 65 3-7 ALOHA Delay-Throughput Characteristics 68 3-8 (a) (b) Effect of Blocking Conditions 72 3-9 ALOHA Delay versus K 7 3-10 ALOHA Delay versus Sf 74 3-11 Reservation Delay-Throughput Characteristics 76 3-12 Output Rate S t versus g 86 3-13 S 3-14 Illustration of D 3-15 Comparison of ALOHA-I and -II 95 3-16 Output Rate S t and Estimation Error 6(n) 98 3-17 (a) Backlog Delay D 3-17 (b) E and E versus p , for pT = 500 100 3-18 (a) Backlog Delay D 101 f m d ou in I Sout and EP's 2 88 for VAP-II 94 ou and p , for pT = 500 l q d l x 4 max 2 d and p , for pT = 50 1 q d vii 100 3 - 1 8 (b) Ei and E versus p , for A * 2 4 -1 d - 1 = 50 1 0 1 Data Access Protocol Flowchart 1 1 0 4 - 2 Illustration of Continuous Reservation 1 1 9 4 - 3 CP Delay-Throughput Characteristics 1 2 4 4-4 1 2 5 1 2 7 1 2 8 CP Performance and User Number N 4 - 5 Relationship among N , um Sf and N u 4 - 6 Trial Number Distribution viii u LIST O F T A B L E S 3-1 ALOHA Delay-Throughput with VAP-I 69 3-2 ALOHA Delay-Throughput with VAP-II 70 3-3 Reservation Delay-Throughput with VAP-I 77 ix ACKNOWLEDGEMENTS I with to thank my supervisor, Dr. H. W. Lee, for his encouragement and suggestions throughout the research. The financial support from Shanghai Jiao Tong University and from the research grant of Dr. H. W. Lee are gratefully acknowledged. x Chapter 1 Introduction The integrated transmission of heterogeneous types of information has been proposed as an important solution to the ever growing demand upon communication systems. In particular, extensive studies and experiments have been conducted in integrated voice/data transmissions. The integration of digitized voice with data in a common packet-switched system offers potential cost savings through sharing of switching and transmission resources, as well as enhanced services for users who require access to both voice and data communications[l-4]. Of vital importance here is the design of an efficient link level protocol for integrated voice/data transmissions. This is complicated, however, by the significant differences between voice traffic and data traffic. Statistically, the former is characterized by smoothly continuous, or so called "streamlike", flow in time; while the latter is characterized as "bursty", that is, short spurts of activities interspersed with relatively long idle periods. The streamlike traffic can be accommodated by circuit-switched networks; while bursty traffic can only be handled efficiently by packet-switched networks. In order for these two different types of traffic to be compatible in the same network, the transmission of streamlike traffic is packetized, i.e., the continuous stream of traffic is divided into a sequence of fixed sized packets before they are transmitted. In general, an integrated network is packet-switched in which the streamlike traffic is handled 1 Chapter 1: Introduction 2 by virtual connection protocols. Experiments with packetized voice transmission show that satisfactory reproduction of speech at the receiver requires short packet end-to-end delay and small interpacket delay disparity. It is estimated that the end-to-end delay should be less than 150-350 ms and interpacket delay disparity should be less than 5-10 ms [5]. Because of stringent delay requirements placed by voice users on the network, integrated packet voice/data protocols have therefore tended to give precedence to voice packets and to insert data packets into any remaining network capacity after the voice requirements are fulfilled [4]. Current areas of research in integrated voice/data transmissions fall into the following categories: 1. Utilization of voice transmission silence periods for data packet transmissions. It is estimated that over 45% of time of a speech is silence period. 2. Data transmission via remaining channel capacity not used by voice transmissions. 3. Combinations of 1 and 2. The present thesis is concerned with type 2 integration of voice and data transmissions. The environment under study is a global beam satellite system. There are a "large" number of geographically distributed, independent "small" data and voice users wishing to communicate with each other over the satellite Chapter 1: Introduction 3 channel. By a "large" number is meant anywhere from several tens to a few thousands, and by "small" user is meant each user would generate no more than one telephone call and/or interactive data connection.! The satellite channel is the sole communication medium among all the users. A satellite channel provides excellent one hop connectivity among a large number of geographically distributed users. However, its one way propagation delay of 270 ms has been found a major difficulty in devising an efficient protocol for integrated voice/data transmissions. 1.1 Basic Structure of Integrated Wide Band Systems In order to support many voice calls simultaneously with reasonably small call blocking probability, an integrated voice/data(IVD*) system is implemented in a wide band satellite system (details are given in Chapter 2). Numerous protocols have been proposed for wide band IVDS systems, with experiments reported in [4, 6, 7, 8, 9]. Two representative protocols are of interest here and are described briefly as follows. f In the consideration of implementations, such users usually have small antennas and are supported by multibeam satellite systems, which is not the topic of study of this thesis. The global beam system here can be viewed as one coverage zone in a multibeam system. See chapter 5 for further notes and references. * "IVD" will stand for "integrated voice/data" in the following of the thesis. Furthermore, "IVDS" will stand for "integrated voice/data satellite" (systems). Chapter 1: Introduction I 4 Frame ( i - l ) 21.2 ms Frame i | 1 21.2 2 1 6 ms bits Data Subf ra me Stream Subf r a m e A \ ' | ; Frame (i + 1) 21.2 1 ms Control Subf r a m e * Moving Boundary Figure 1-1 Basic Structure of WB SATNET 1.1.1 W B S A T N E T Structure This is the protocol used in the first experimental wide band integrated satellite network (WB SATNET, [6]). In the WB SATNET, time is partitioned into fixed size frames of approximately 21.2 ms corresponding to 2 16 bits at a channel data rate of 3.088 Mbps. Each frame is further partitioned into several subframes. In the steady state, the frame structure is shown in figure 1-1. The stream subframe in figure 1-1 supports the streamtype traffic, i.e. voice traffic. Stream transmission is characterized by periodic frame-to-frame recurrence of channel allocation, i.e., a dedicated portion of channel time in stream subframe is assigned to an ongoing voice user (station), as shown in Chapter 1: Introduction 5 figure 1-2, for the length of the call; this dedicated assignment is refered to as virtual circuit or virtual connection. The setup of virtual connections is via the reservation transmitted during control subframe. The stream subframe may be null if there is no voice traffic present. The data subframe and control subframe support data transmission by a reservation protocol. Control subframe is divided into N fixed-size slots, each slot can be used to transmit a reservation for data packet or voice connection. The assignment of the N control slots to network stations can be either fixed: each station is assigned a dedicated slot within the control subframe; or contention based: the N slots are shared on a slotted ALOHA contention basis by all stations. Data are transmitted in data subframe. The basic procedures are illustrated in figure 1-3. Delay for a data packet is 2 round trip propagation delay of approximately 0.54s plus the global queueing delay. 1.1.2 The S E N E T Structure Under the SENET structure (Slotted Envelop Network, [7]), the channel time is partitioned into fixed size frames; each frame is further partitioned into a number of fixed size slots; the size of one slot is equal to the transmission time of one voice or data packet. Virtual connections are also used for voice calls. Data packets are transmitted in the remaining slots in a frame. In the original SENET, data access protocol is T D M A , as illustrated in figure 1-4. Chapter 1: Introduction S| D C Frame i s, 0 C S l*8 Frame i + 1 D C • Frame i + 2 HS1 HS2 HSS HS1 HS2 BS3 HS = Hoat S - Stream Subframe D - Data S u b f r a m e s asi l*2 HS2 C - Control Subframe BSS Figure 1-2 Illustration of Stream Subframe RESERVATION DATA t t ^-Reservation T r a n s m i t t e d by S o u r c e node L -Message a r r i v e s From source host t Message d e l i v e r e d to Destination host D e s t i n a t i o n node Receives message Source node t r a n s m i t s message L - R e s e r v a t i o n s c h e d u l e d by a l l n o d e s - A l l nodes enter r e s e r v a t i o n i n t o G l o b a l q u e u e (FIFO) o r d e r i n g Reservations recerved By a l l s t a t i o n s Figure 1-3 Illustration of Data Transmission Procedures 7 Chapter 1: Introduction Frame i Fra me i +1 .ZL Cl C2 | C2 D2 D3 D4 D5 D3 D4 D5 Dl D4 D5 C3 D2 Cl Frame i+2 C3 i i i n C4 Dl 1 Cl Frame i + 1 m £ 1 Dl Frame i Frame i + 2 C2 D3 C3 C - On going voice c a l l D - Data t r a n s m i s s i o n , a s s u m i n g 5 data users Figure 1-4 The SENET structure D2 C4 C4 D2 D3 Chapter 1: Introduction 8 In the SENET structure, there is no boundary between voice portion and data portion, thus making it distinctive from WB SATNET structure. In general, a higher degree of integration can be achieved by using SENET than WB SATNET structure. The performance analysis, however, tends to be much more complicated for the former than the latter, due to the entanglement between voice and data transmissions. 1.2 Scope of the Thesis In this thesis, IVD protocols are studied under SENET structure. In the original SENET structure, data multiple-access protocol T D M A was used. It is well-known, however, that TDMA does not give satisfactory performance under bursty and large user population environment. There exist many multiple-access protocols with superior performance to T D M A . The large propagation delay of satellite channels, however, precludes use of schemes such as CSMA, polling, etc, since they only perform well when propagation delay is a small fraction of packet transmission time. In a long propagation delay environment, simple random access scheme has found to be effective. Reservation scheme is another alternative to cope with the long propagation delay. Combined random/reservation schemes have also been proposed which transfer from one mode (random access) to another (reservation) according to the channel load. Under IVD environment, these protocols, namely random access and reser- Chapter 1: Introduction 9 vation, are studied; performance is evaluated analytically and compared to simulation results. A combined random/reservation scheme is proposed, which differs from most known combined random/reservation schemes in that it does not have to partition the channel time into mini-slot structures. Chapter two begins with investigation of statistical properties of SENET structure. In Chapter three, ALOHA and reservation protocols are analyzed and simulated. In order to derive the analytic results, an independence assumption is made, which is shown to be valid for low and medium range of voice traffic intensity and for certain voice assignment protocols. A control algorithm is introduced in Chapter three. It is shown that ALOHA protocol incorporated with such a control mechanism is globally stable in the IVD environment, even for infinite number of users. Based on the results of chapter three, the combined random/reservation protocol is proposed and simulated in chapter four. Analytic and simulation results show a preference on the combined protocol to non-combined ones. Chapter five concludes the thesis with suggestions for further studies. Chapter 2 Voice Packet Transmission Voice packet transmission protocol will be discussed in this chapter. Emphasis is placed on the study of statistical properties of voice pattern structure as a basis for the forthcoming chapters. 2.1 V i r t u a l C o n n e c t i o n P r o t o c o l s for V o i c e P a c k e t s Because of the streamlike property and the delay requirement of voice packets, a virtual connection or circuit for an ongoing voice call is both reasonable and desirable. The basic procedure for establishing a virtual connection is described as follows: The channel time is divided into frames, and each frame is further divided into fixed number of slots (SENET structure, see figure 1-4). The length of each frame in time will be denoted as Tf, and number of slots in a frame, called frame size, will be denoted as Sf in the sequel. Reservation protocol is used to exchange setup information of a virtual call connection. Whenever a station wants to call, it sends a request to the controller or, in a distributed control network, to all the other stations. (The transmission 10 Chapter 2: Voice Packet Transmission 11 of request will be discussed in chapter four.) After the request being heard by the controller or all the stations in the network, including the sender, on first come first served basis, the following actions will be taken: 1. One empty slot in the current frame is assigned to the call; this slot is assigned to the same call for the succesive frames until the completion of the call, (virtual connection). 2. If no empty slot is found (among all slots in the current frame), the call is rejected, (blocked) In the case where there is more than one slot available, the slot assignment to the new call can be done according to certain predetermined rules. For example: Immediate Assignment: The empty slot immediately following the slot in which the request arrives is assigned to the new call;(figure 2-1 (a)) The begin-of-frame Assignment: Slot assignments take place only at the beginning of each frame; empty slots will be assigned to new calls in the order of left (earlier in time) to right (figure 2-l(b)). There is little difference between two assignments as far as the voice performance is concerned. However, because of the order in which they make use of empty slots, the resultant voice pattern* will differ, which have significant effects on data performance, as will be discussed in chapter 3. will be discussed in section 2.2 Chapter 2: Voice Packet Transmission V i r t u a l connection established Frame i Frame i + 1 Frame i+2 4 A P r e v i o u s l y occupied slots F i n d an Empty slot New v i r t u a l c o n n e c t i o n s New data a r r i v a l Figure 2-1 (a) Voice Assignment Protocol I Virtual connection established F i n d an Empty slot l n the next f r a m e L New data a r r i v a l Figure 2-1 (b) Voice Assignment Protocol II IS Chapter 2: Voice Packet Transmission In the subsequent discussions throughout the thesis, for the convenience of notation, let the immediate assignment protocol be called "voice assignment protocol I", abbreviated as VAP-I, and the begin-of-frame assignment protocol be called "voice assignment protocol II", abbreviated as VAP-II. The two important SENET structure parameters Tf (frame length) and Sf (frame size) are determined as follows. Since an ongoing voice call transmits one voice packet per frame, the frame length is equal to voice packet size in time. In order to minimize both the packetization delay at the transmitter and the perceptual effect of lost packet anomalies at the receiver, packets should be as short as possible. Experience with lost packet anomalies indicates that individual packets should contain no more than 50 ms of speech[10]; ideally, packets should be even shorter to minimize packetization delay. On the other hand, in order to maintain high channel utilization, it would be desirable to keep the number of speech bits per packet as large as possible relative to the overhead which must accompany each packet. In WB SATNET(see section 1.1.1.), frame length was chosen as 21.2 ms. Typically, the frame length Tf is between 10 to 30 ms in a wide band network when considering the tradeoffs mentioned above. Frame size Sf is numerically equal to the maximal number of voice calls supported by the network simultaneously. It depends on the voice coding rate and channel capacity. If coding rate is K and total channel capacity is C , then c S = f [C/K \ c (2-1) Chapter 2: Voice Packet Transmission where the symbol [ J denotes the truncation function which gives the integer part of a real number. Equation (2-1) assumes that the portion of total channel capacity C used for controlling and synchronization, etc, is negligible. Theoretically, the larger Sf is, the smaller the call blocking probability will be* In practice, the maximum Sf is bounded by the total channel capacity (bandwidth) C. For a wideband voice packet network, K is from 16kbps (CVSD c coding) to 64 kbps (PCM coding), and C from 3 Mbps to 6 Mbps (commercial C band), thus Sf is from 50 to 400.+ In a satellite channel, the single hop propagation delay of 270 ms, denoted as R, corresponds to roughly 12 times the frame length Tf. 2.2 Voice Pattern Statistics Slots occupied by voice virtual connections form a pattern (see figure 2-1 for example), which will be referred to as voice pattern in this thesis. As each slot can be in either one of two states, i.e., occupied or unoccupied, if the occupied state is assigned value 1 and unoccupied state value 0, the pattern structure can be modelled as a 2-valued random process in slot time n, denoted as V(n). Since the voice pattern serves as the background for data transmissions, some of its statistics, which have significant effects on data performance, are discussed here. * will be discussed in section 2.2. f Experiments on K u value of Sf is thus possible. band with C = 500Mbps has been reported in [11]. A much higher 15 Chapter 2: Voice Packet Transmission 2.2.1 Statistics of Voice Utilization Define p [n) to be the first moment of V(n), i.e., v p„(n)=E[v'(n)] =P {v{n) r = l) Assume that V(n) is ergodic and stationary, then, p (n) = v 1 = P {V(n) = l} = lim — £ Pv T r (2-2) V{n) n=-T If V(n) is a sample of V{n), n = 0,1, • • • , T , then p can be estimated by v (2-3) n=0 By definition, p„ is the voice utilization, which is the portion of total channel capacity occupied by voice calls. The portion of remaining capacity available to data transmissions is 1 — p . To estimate the steady state value of p by (2-3), v v T should be chosen long enough in order to average out the fluctuations. On the other hand, a small value of T gives short time average p ; a sequence of v short time average p„'s can serve as a measure of changing rate and extent of fluctuation of voice utilization, especially when T is chosen as Sf. The variance of V[n), denoted as a , is 2 v a „ = E V{n) 2 - {p } v 2 = Pv{l ~ Pv) (2-4) The steady state value of p can be derived from the following voice source v and system models. Chapter 2: Voice Packet Transmission 16 T h e voice source m o d e l Calls are generated from an ensemble of N individual voice sources, where N —> oo, with the following characteristics: 1. The aggregated number of calls, N , generated during the time interval T , c obeys a Poisson distribution, i.e., Pr(N ,T) = i ^ L i N = 1,2,." c c where A is call arrival rate. (Typical value of A for a large satellite network would be in the order of a few calls per minute). 2. The calls are packetized. The length of each call is geometrically distributed, i.e. if / denotes number of packets in one call, then P (0 = r - M)'" 1 / = 0,1,-.. where // is the call completion rate, and its reciprocal pT is the average l number of packets in one call. For packet size of 20 to 30 ms, fj, -1 is of the order of several ten thousand (packets). T h e system m o d e l The analysis of virtual connection of voice transmissions is equivalent to that of circuit switched telephone systems, which are modelled as an M/M/s blocked customer removed (M/M/s b.c.r) queueing system. In the sense of providing virtual connections, slot size Sf is equivalent to the server number s. 17 Chapter 2: Voice Packet Transmission If state j of the M/M/s b.c.r system is defined as the number of 1's in a frame (equal to the number of voice occupied slots), then state transition rate Ay from state j to j + 1 is A = f A, y = 0,l,---,5-l lO, j = s. (2-5) y from state j to j — 1 is A*y = i/* J = 1.2, (2-6) where A and p, are the call arrival rate and the call completion rate, respectively; s is equal to Sf. The meaning of X = 0 is that additional voice arrivals after all a s(= Sf) slots are occupied are blocked and removed. The state probability Py for an M/M/s b.c.r system is given by [12], f ^ Z ^ L , y = o,i, Py= < (2-7) i=0 0, j>s. Note A and \i appear in (2-7) only through the ratio X/fi, which is the offered load in the terminology of queueing theory, denoted as a. (2-7) is also known as truncated Poisson distribution. The average number of busy servers n can be calculated as 8 n = Y,JP (2-8) j y=i n is also the average number of voice occupied slots in a frame, thus, p can be v obtained as Pv = n/s (2-9) 18 Chapter 2: Voice Packet Transmission substituting (2-7), (2-8) in (2-9) yields, \ Pv = a s a /s\ s t (2-10) a /kl k where s = Sf, a — X/p,. The blocking probability of voice calls is recognized as Pj for j = s = S/, which is the probability that a customer finds all the s servers are busy, or equivalently, a call arrival finds all the Sf slots in a frame are occupied, denoted as B(s,a), a /s\ s B(s,a) £ (2-11) a /k\ k k=0 (2-11) is well known as the Erlang loss formula [12]. Combining (2-9), (2-10) and (2-11) gives, n = a(l - B(s,a)) (2-12) which suggests that n can also be seen as the carried load of the system. For convenience, define the normalized offered load a' = a/Sf, the normalized carried load n/Sf is just p . Figure 2-2(a) plots B{s,a) versus Sf, for a' = 0.8; figure v 2-2(b) plots B(s,a) versus a' for Sf = 25, 50, 100 and 150, respectively. As seen from the figures, the larger Sf is, the smaller the blocking probability will be. This can be easily understood by the statistic averaging effect of a large number of cooperating servers. Formula (2-11) also justifies the use of a wide band system which can provide a large number of virtual connections simultaneously. Calculations of (2-11) suggests that for Sf > 50, the blocking probability B(s, a) will be less than 0.02 for normalized offered load a' < 0.8. In Chapter 2: Voice Packet Transmission 19 Chapter 2: Voice Packet Transmission 20 such case where B(s,a) is very small, the offered load is approximately equal to the carried load, as can be seen from (2-12). Thus, in a wide band system (Sf > 50) for p < 0.8, p can be approxiv v mately calculated by Pv = -V (2-13) Generally speaking, if blocking probability is negligible, in steady state, the flow balance condition gives, flow in rate = flow out rate A = np,, n =— that is * = f = bf ^ ( 2 " 1 4 ) p,bf which is the same as (2-13). (2-14) is true regardless of distributions of arrival and call length processes. It is important to point out that, in a wide band system, although the blocking probability can be neglected for voice calls, it plays an important role in data performance, this is to be discussed in chapter 3. The variance of slot occupancy j, denoted as cry , is given by 2 2 <7y where s = Sf. \ = ' -2 D 3 Pj ~ 3=0 —2 n ~ — n ' _ B{s,a)(s - n) 1-B(s,a) (2-15) Chapter 2: Voice Packet Transmission 21 Of more importance is the relative variation rate, APy, defined as APy such that when 0 < j < j i and j m n where P sp - {jmaz ~~ Jmin)/Sf max < j < Sf, the (tail) probabilities Pj < P , sp is a pre-specified value. To data transmissions, these tail probabilities indicate directly the availability of slots. Figure 2-3 plots Pj (j = 0,1, • • •, Sf) for S = 50,100,200 and p = 1/3,1/2,2/3, P f v sp = 0.005. It can be noticed that APy decreases with the increase of Sf. Figure 2-3 Tail Probabilities, P 3p = 0.005 Changing rate of p in time is the same as that of j. From (2-5) and (2-6), v the arrival rate is A, and the completion rate is p,j. The total changing rate of 22 Chapter 2: Voice Packet Transmission p for state j, denoted as Ap , is v v Ap = A + /ij (2-16) v maximum Ap and average Ap are thus v v &Pv max = X + fl-Sf and &Pvave = A + // • n « 2A A typical numerical example of Ap follows: take Tf = 22ms, A = 1.0 v call/sec = 0.022 call/frame, pT = 1.1 minutes = 3000 frames/call, Sf = 100, l then n « a = 66 Ap Vave = 0.022 + 66/3000 = 0.044 change/frame = 1 change/23 frames that means p will not change for 22 frames on the average. Compared to data v arrival rate, which is on the order of 1 arrival in a few slots, p can be said a v very slowly time varying process. 2.2.2 State Correlation of Voice Occupied Slots One of the complexities in evaluating the effect of voice pattern background on data performance arises from the fact that, even for the backgrounds of the same voice utilization, different distributions of voice occupied slots produce significant difference in data packet performance. This can be illustrated using two extreme cases(figure 2-4). Chapter 2: Voice Packet Transmission 28 Frame i L=6 // / / 1 11 1 Delayed and Transmitted Data a r r i v e 1 (a) A l l o c c u p i e d s l o t s a g g r e g a t e d To one s i d e of t h e f r a m e Data a r r i v a l Tra ns m itted Right away (b) O c c u p i e d s l o t s e v e n l y Distributed i nthe frame Figure 2-4 Illustration of Voice Correlations and Data Transmissions In general, states of slots (state 1, occupied by a voice virtual connection; state 0, not occupied) are not completely randomly distributed, indicating that there exists correlations among states of slots. Define i(k) to be the correlation coefficient for states of slots k slots apart, Chapter 2: Voice Packet Transmission then E [ ^ ( n ) F ( n + Jfc)] - J E [y (n)] *v = }' 2 Pr{V{n) = l}P {V(n + k) = l\V{n) = r 1} - p (2-17) 2 v Pv{l ~ Pv) _P {V{n r + k) = l\V{n) = I- l}-p v Pv T h e r e are two important special cases: 1) k = S, f P {V(n + k) = l\V{n) = r 1} = (2-18) and 7 (A:) = ! - - £ 1 - Pv Take \i = 0.0005, p v = 0.5, then 7 (fc)| fc=5/ = 0.999 « 1.0 T h a t means if slot j i n frame i is i n state 1 (or 0), then slots j i n frames (i — 1) a n d (i + l) are also very likely to be i n state 1 (or 0), due to the virtual connection protocol. F r o m (2-17) and (2-18), E \v{n)V{n + S )] - p f { k ~ Sf 2 v E[v(n)V(n)}-p * (2-19) v V(n)t*V{n + S) f Vn 25 Chapter 2: Voice Packet Transmission The above is interpreted as: V(n) is (quasi) periodic in the sense of probability, with period Sf, the (quasi) periodicity of V(n) determines that i(k) is also (quasi) periodic with the same period Sf. 2) Define random variable L to be the number of consecutively occupied slots plus 1, as shown in Figure 2-4, and P {l) be its probability density function; r then there exists an important relationship between P r (0 " d ^(fc), i.e., a l(k)=0 <^=> P {V{n + k) = l\V{n) = l} = p r P (l) = r v Vn,k ^ 0 p - (l- ) l v 1 Pv The forward equivalence comes directly from the derivation of geometric distribution; the backward equivalence states the fact that geometric distribution is memory less. For an arbitrary k, however, the correlation among slots is much harder to predict. It is related to many factors such as frame size Sf, voice utilization p , v and in particular, voice assignment protocols (VAP-I and VAP-II). In the next chapter where analysis of data performance is carried out, the independence of states of the slots is assumed, i.e., ^(k) = 0, VA: ^ 0. The assumption is necessary for the performance evaluations to be mathematically tractable. The question is how strongly the slots are correlated. If the correlations are weak* it would be reasonable to assume the independence. Unfortunately, the question is very difficult to answer analytically. As the correlations are important factors on data performance, they will be obtained by the simulations * Except at fc = nSf, where n is an integer. With Sf in the wide band range, these "spikes" are sparsely spaced. Chapter 2: Voice Packet Transmission 26 in the next section. Since V{n) is assumed to be stationary and ergodic, Tf(fc) = E[V{n)V(n + k)} = lim ±- £ V(n)V(n + k) (2-21) n=-T which can be estimated as 1 M-k M-k V(n)V{n + k) (2-22) where V(n),n — 1,2, • • •, M, denotes a sample of voice pattern process V{n). 2.3 Simulations of Voice Pattern Structure Voice arrival, virtual connection and voice completion processes were simulated. Samples of simulated V(n) are used to obtain the estimates of i(k) and P (l) in r this section. 2.3.1 Choice of Parameters Basic parameters relevant to the discussion here include frame length Tf, frame size Sf, channel capacity C, voice coding rate K , voice arrival rate X, and voice c completion rate p,. The voice assignment protocols VAP-I and VAP-II are also treated as one parameter in the system. 27 Chapter 2: Voice Packet Transmission The ranges of parameters used in the simulations are as follows: 1. frame length Tf. 22ms (typically 10-30 ms); 2. frame size Sf: from 50 to 400 slots per frame. The length of a slot in time unit is thus 0.44(= 22/50) ms to 0.055(= 22/400) ms. Because a slot is the entity with the smallest time unit in the system, the length of a slot is selected as the time unit of the simulation. Since frame length Tf is fixed as 22 ms, the increase or decrease of Sf means a corresponding increase or decrease in total channel capacity C (see (2-1)); 3. Voice arrival rate A and completion rate p,: their ratio normalized to Sf determines the voice utilization p (see (2-14)). In order to simulate Ap , v v average call length pT should be chosen as close as possible to the real x situations, which is typically about a few minutes. However, an actual calculation suggests that the real time parameter is an enormously large number in the simulation time units of frames and slots. Take pT = 3 minl utes for example, the call length in frames is 3mi x 60 X 1000/22ms = 8181 frames, if Sf is 100, the call length in slots is 818100 slots, a simulation of very long length has to be carried out in order to get any useful information. In considering the tradeoffs between the reliability of simulation and cost of simulation, pT is chosen as 44 seconds in real time, which corresponds 1 to 2000 frames in simulation time, (p, = 0.0005 completion/frame). In the following simulations whenever p needs to be changed, it is done v by varying A while fixing p, = 0.0005 completion/frame. Chapter 2: Voice Packet Transmission 28 2.3.2 Results of Simulations The simulation results are presented in 3 groups to demonstrate the effects of Sf, p and VAP on voice pattern statistics, respectively. 3 runs of different seeds for v random number generators were carried out for each result. Results presented here are the means of 3 runs. The standard deviation of the 3 runs is within 5-10% of the mean, unless otherwise noted. 1) V A P group Figures 2-5(a) and 2-5(b) show the estimates of 7(fc) and P {l) for p r v = 0.5, Sf = 100, VAP-I. In figure 2-5(b), the geometric distribution is shown as dotted curve as comparison with simulated curve(solid). The following can be noticed in the figures: 1) In figure 2-5(a), slots of 100 slots(=Sy) apart are strongly correlated with *l(k) « 1.0 (the calculated value is 0.999, see (2-18)). The (quasi) periodicity of V(n) is reflected by that of ^(k), with period equal to Sf. 2) *j(k) decreases with the increase of A;, for 0 < k < 5, andfluctuatesaround 0.1, with maximum ^(k) « 0.2, for 5 < k < 50* As comparisons,figures2-6(a) and 2-6(b) show ^(k) and P {l) for the same r Pv and Sf, except that VAP-I is changed to VAP-II. As seen from figure 2-6(a), * *y(fc) is shown to be symmetric tofc= 50(= S//2), this is because autocorrelation functions are always even functions plus in this case 7(fc) is quasi periodic. 29 Chapter 2: Voice Packet Transmission average *j(k) increases significantly compared to figure 2-5(a); difference between P [l) and the geometric distribution is also much larger in figure 2-6 (b) than in r figure 2-5(b). These results indicate that VAP has a strong influence on i(k). For VAP-I, it seems reasonable if ^(fc) is assumed to be 0; whereas it would be nonrealistic to make the assumption for VAP-II. Simulations were also run for p = 1/3, 2/3, Sf = 50, 200, and 400 cases v with VAP-I and -II. Very similar results as above were obtained. 2) p v group Figures 2-7(a) and 2-7(b) show *j(k) and P (l) for the same parameters as in r figures 2-5 and 2-6, except that p is lowered to 1/3. No significant change is v found in *)(k). P (l) is seen to be slightly closer to the geometric distribution r than in p = 0.5 case. v p is then increased to 2/3, *j(k) and P [l) are shown infigures2-8(a) and v r 2-8(b). Again no significant change in ^(k) can be seen. The P {1) curve shows T slightly more deviation from that of the geometric distribution. Similar results were obtained for VAP-II cases. Chapter 2: Voice Packet SO Transmission 3) Sf group Simulation results are shown in figures 2-9, 2-10 and 2-11 for Sf = 10, 25, 50 and 200. Inspections of thesefiguressuggest that Sf has effect on correlations, with smallest correlation for Sf = 200 and largest for Sf = 10 (figure 2-9). The differences are not significant, however. Similar situation can be seen for P (l). r For all the four cases, P (l) has no significant changes(figure 2-10). r The most noticeable changes of voice pattern statistics are changes of Py (figure 2-11). For the same p , relative variation rate of Py, APy, increases as Sf v decreases. As a consequence, the probability of blocking condition occurrence in small Sf case (Sf — 10, for example) is much more noticeable than Sf > 50, i.e., the wide band range. Compared to the effect of p , it can be seen that the major v effect of both p and Sf is on the tail probabilities Py. The smaller Sf is and v the larger p is, the larger APy will be. Besides these major effects, they also v influence correlation slightly. From the above simulation results, the following conclusions can be reached: 1. It is a reasonably good approximation to assume the independence of the slot states for VAP-I, while this is not true for VAP-II. 2. High p and/or small Sf are related to relatively high probabilities of blockv ing condition occurrence. It is seen in the next chapter that blocking condition has significant influence on data performance. Chapter 2: Voice Packet Transmission Figure 2-5(b) Slot Distribution P (t) r for p = 0.5, V A P - I v C h a p t e r 2: Voice Packet Transmission k Figure 2-6(a) Correlation *j(k) for p = 0.5, VAP-II v Chapter 2: Voice Packet Transmission Figure 2-7(b) Slot Distribution P (l) r for p v = 1/3, V A P - I Chapter 2: Voice Packet Transmission F i g u r e 2-8(b) Slot D i s t r i b u t i o n P (Z) for p = 2 / 3 , V A P - I r v Figure 2-9 ^(k) and 5/ Figure 2-10 P ( 0 and Sj r Figure 2-11 Pj and Sf Chapter 3 Data Packet Transmission Extensive work has been done in recent years in devising multiaccess protocols suitable to a variety of communication environments. A good summary can be found in numerous literature, such as [13,14]. A satellite channel is a multiaccess broadcast environment characterized by long propagation delay of approximately 270 ms for a single hop. In such an environment, random access protocols, i.e., ALOHA protocols are found to be suitable because of their insensitivities to long propagation delay. Reservation protocols are also extensively used in such environments. Combined random/ reservation protocols extract the merits from both protocols, at the expense of increased protocol complexities. In this chapter, ALOHA protocol and reservation protocol are modified to the IVD environment. Approximate analyses are made and compared to the simulation results. With voice being integrated into the system, the effect of slowly time varying availability of channel capacity on the performance of these data multiaccess protocols is shown by these results. A combined random/reservation protocol will be studied in chapter 4. 38 Chapter 3: Data Packet Transmission 39 3.1 Multiaccess Protocols in the IVDS Systems A distributed multiaccess environment is defined as: 1. a number of geographically distributed stations (users) wish to communicate by transmitting messages via a single communication channel shared by all stations; 2. the channel is the sole means of communication among the stations; 3. only a single message can be successfully transmitted over the channel at any given time. If two or more messages are simultaneously transmitted over the channel, these messages interfere (collide) with each other and none of them will be correctly received by the stations for which they were destined. The multiaccess environment is also known as a broadcast channel since a message sent by one station can be heard by all the other stations. A satellite communication channel with distributed earth stations is a multiaccess environment. In the multiaccess environment, certain coordination is necessary among the stations in order for them to share the channel. Several issues complicate the problem of channel sharing. First, since the stations are distributed, they must either explicitly or implicitly communicate to each other if they wish to coordinate channel sharing. However, there is only a single communication channel, coordination among the users about channel sharing necessarily requires use of Chapter S: Data Packet Transmission 40 the channel itself. Second, since the stations are distributed, they can never instantaneously know the present status of other stations in the environment; information about other stations is always at least as old as the amount of time required for a message to propagate from one station to another. This problem is especially important for a satellite multiaccess environment with a 270 ms long propagation delay. A distributed algorithm by which the stations are coordinated in the sharing of the channel is known as a multiaccess protocol. Multiaccess protocols can be classified by the extent of coordination they exercise [14], ranging from weak coordination (such as ALOHA) to strong coordination (such as T D M A , Polling). The following types of information are commonly used in multiaccess protocols: 1. Predetermined rules known to each station when it begins operation; an example is the transmission rules specified in the multiaccess protocols. These predetermined rules will not be changed by individual users during the operation. 2. Global information obtained by each station by listening to the channel; An important example of global information is the instantaneous total channel traffic factor, denoted as g(t), which is the short time average of the ratio Chapter 8: Data Packet Transmission 41 of total transmissions to the channel capacity, i.e., Total transmissions in time interval^, £ + At) Ai (3-1) Only delayed version g(t — R) of g(t) can be obtained by individual users because of the propagation delay R. In an IVD system, the voice pattern structure is another example of global information. 3. Local information known only to a single station; One example of local information is the queue length of individual users. Local information can be transformed into global information by transmission activities. Based on these information, each station estimates the channel status and schedules its transmission activities accordingly. The designed purpose of a multiaccess protocol is such that the overall probability of successful transmission is maximized, so that the desired low-delay high-throughput characteristics is realized. The propagation delay R plays a very important role in the design of multiaccess protocols. In the environments where propagation delay is insignificant compared to the transmission time of a message, such as in a local area network, many protocols are proposed (e.g. CSMA, polling) which give performance close to that of the so called perfect scheduling, — the performance upper bound of multiaccess protocol which is only achievable in a non-distributed environment, i.e., R = 0 environment [13]. In the environment where R is comparable or even larger than the transmission time of a message, such as in a satellite channel, the increase of the delay of information exchange impairs the coordination ability of Chapter 3: Data Packet Transmission 42 these protocols. The consequence is that these protocols, though sophisticatedly designed, give no better performance than the simple and little coordinated protocols, e.g., the ALOHA protocol [14]. Because of this reason, ALOHA protocol has been one of the major protocols used in satellite channel. However, the almost complete lack of coordination of stations in ALOHA protocols results in a maximum of only 36% of the channel capacity usable. For the applications where higher throughput is concerned, reservation protocol is used which provides up to 90% of channel utilization. The increased throughput, however, is achieved at the expense of increased delay, since in a reservation protocol, delay is at least 2 times of propagation delay R no matter how small the throughput may be. Many combined random/reservation protocols have been proposed. They are intended to have the advantages of both random protocol (low delay) and reservation protocol (high utilization). The problem associated with combined protocols are usually the implementation complexities and reliabilities versus the advantage of the protocols. Up to date, for the long propagation delay environment, there has been no single protocol that gives overall satisfactory performance. On top of the long propagation delay in a satellite channel, the integration of voice into the system introduces fluctuations of channel capacity available to data users. The slowly changing voice background makes it more difficult to transmit data efficiently than if only the reduced channel capacity were available to data users with no voice presence (no fluctuations). In the following sections, ALOHA protocol and reservation protocol are modified to the IVD environment, so that no conflict between voice transmission 43 Chapter 3: Data Packet Transmission and data transmission will occur; and their performance are studied. 3.2 ALOHA Protocol in the rVDS System Since available slots are interleaved with voice connections, data arrivals during voice occupied slots have to delay their transmission. A natural extension of slotted A L O H A protocol is defined as follows: 1. Each user remembers the voice pattern V(n) in the previous frame; By listening to the channel, it also estimates the instantaneous total channel traffic factor g{t), defined in (3-1) with A i = Sy; the estimate is denoted 2. A transmission delay factor a is defined as (3-2) \9l J where / is the length of consecutively voice occupied slots plus 1, e.g. in figure 3-1, / = 4. 3. Upon a new arrival of data packet, with probability a, transmit in the next available slot (e.g, 7th slot in figure 3-1); with probability 1 — a, delay the transmission K slots, where K is a random variable uniformly distributed between [l,i<f * maz ].t The delayed transmission repeats the same rule until The problems involved with acquisition of V(n) and g will be discussed in the following subsections. t Kmax is about one to two times of frame size Sf. see footnote on page 73. Chapter 3: Data Packet Transmission 44 With p r o b a b i l i t y a t r a n s m i t L =4 ZVA V7V7VA \ VA VA New a r r i v a l • With p r o b a b i l i t y 1-a the t r a n s m i s s i o n delay Figure 3-1 Illustration of Delayed Rule it is transmitted. 4. If there is a collision, delay the collided transmission K slots where K is the same as above. Note a collision can only be known R time later, where R is usually more than 10 times of frame size (see Chapter two). During this time interval R, newly arrived packets repeat the same rules as above, i.e, selective repeat ARQ is used4 The following are the discussions involved with V(n) and g used in the protocol. X Those packets whose acknowledgement has not yet received are buffered. Potentially a large buffer is required, this is assumed to be always satisfied. Chapter 3: Data Packet Transmission 45 3.2.1 Acquisition of V(n) Because of the propagation delay R, the voice pattern structure on the ground is different from that in the sky. In the above description, present voice pattern structure was supposed to be known, this actually means the ground voice pattern recorded by every station. Whenever a new voice virtual connection is established, each station marks the corresponding slot occupied, thus, there will be no conflict between data transmissions and voice virtual connections. Due to R, however, the termination of a virtual connection can not be known instantaneously. Suppose in the header of each voice packet, there is an indication whether it is the last packet. This information will not propagate to the other stations until R later. During this time period R, all the other stations assume the virtual connection is still there and no one attempts to transmit in that particular slot, thus a portion of capacity corresponding to the time R is wasted. Since the average call length is much longer than the propagation delay R, however, the actual percentage of the wasted capacity is relatively small. As an example, take average call length to be 60 second, the percentage of unused capacity then is equal to 0.27s/60s and is less than 0.5%. Thus it is considered negligible here. Of course, this portion can be reused, as well as the silence period in speech; the topics will be briefly discussed in the last chapter. 3.2.2 Estimation of ~g(i) Two problems are involved with acquisition of g(t). First, the earliest available information about channel status is at time t — R; consequently, the available estimation of g(t) is the delayed version of g(t — R). The validity of the use 46 Chapter 3: Data Packet Transmission of such a delayed quantity in coordinating transmission activities relies on the following 2 facts: l) The load placed on the channel will not change significantly during time R\ 2) The voice pattern is very slowly time-varying and does not change much during R* The second problem arises from the fact that due to collision, the exact number of transmissions in (t,t + Sf) can not be obtained. For a time interval T, the following 3 types of information are available to each user: l) the number of slots in which no transmissions were attempted, no; 2) the number of slots in which exactly 1 transmission was attempted, ri\\ and 3) the.number of slots in which two or more transmissions were attempted, n^. If there are total of n slots in the time interval T, then no + n\ + n = n. 2 Based on these outcomes of transmission activities during T, an estimator for g(t) can be constructed. The following are the discussions of 2 estimators of g(t), with different suitable situations. 1) T h e m a x i m u m l i k e l i h o o d e s t i m a t o r g : m Under quite general conditions, the maximum likelihood estimator can be shown to be most efficient (minimum variance) in an asymptotic sense (that is, as the sample size approaches infinity). However, the estimator may be biased for small sample sizes. Later on in section 3.5, another estimation algorithm will be studied; the algorithm is designed particularly to minimize the effect of propagation delay R. Chapter 8: Data Packet Transmission 4? Assume that data arrivals obey Poisson distribution and that the average arrival rate in a slot is g, which is the parameter under estimation. If the observations are n\ and n , (no = n — n\ — n is a dependent observation), then the 2 2 probability distribution is an extension of Binomial distribution, i.e, p(»i,»2) = , U l P i P 2 ( l -Pin2 ni u TT p)~^ n 2 n (3-3) where Pi = ge~ , g P2 = 1 - e~ (l + g) 9 pi is the probability of one arrival in a slot; p is the probability of two or more 2 arrivals in a slot. The estimator g is the value of g for which (3-3) is maximized with observations ni and n . 2 With ni and n given, the maximization of (3-3) involves only the expo2 nentials Pi P2 ni n2 (1 - Pi ~ P 2 ) n _ n i " (3-4) n 2 Take the logarithm of (3-4) and differentiate with respect to g, and set the result to zero, the following maximization equation is obtained n\ — H g T n%ge~ —, g „ r - n+ n = 0 ,„ l - e - 9 ( l + g) . (3-5) 2 y } There is no general analytical solution to (3-5), except for some special cases. The following considers two such cases. i) n = 0 2 (3-5) becomes n\ _ n = U g ni g= — n 48 Chapter 3: Data Packet Transmission which is the same as (3-1). ii) n\ = 0, n = n 2 nge o 1 - e-a(l + g) The solution that maximizes (3-3) is gr —»• oo. This actually indicates that the maximum likelihood estimator is disabled. A regularity condition must be imposed so that g will converge. This regularity condition is usually the a priori knowledge of g. For instance, in an actual network, g will never exceed certain maximum value, say 5 (i.e, g < 5). This maximum value, denoted as g , should x be used as the value of the estimation g for this case. m The bias and variance of the estimator is (g ) = 9mP(ni,n ) Var(g ) = g p{ni,n ) h m 2 - g = g~m~- g (3-6) m 2 m 2 -g^ 2 Figure 3-2 shows b(g ) and Var(g ) in (3-6), for g = {0.5,1,2.0}, and m m n = {1 —• 50}. It is seen that both bias and variance decrease with the increase of n. At n > 30, the estimation errors for g < 1.0 are virtually negligible. 2) T h e a r i t h m e t i c e s t i m a t o r M It is often desirable to estimate the number of transmissions, M , during time interval T (in which there are n slots). The slowly time-varying channel load can be estimated by the estimator g m introduced in the last subsection. However, Chapter 3: Data Packet 50 Transmission the change of M is much faster and is in a much wider range than channel load g. (Theoretically M can change from 0 to infinity). By using the similar method, a maximum likelihood estimator for M can be constructed. However, in terms of actual implementation complexity, a simpler arithmetic estimator M is proposed, i.e. M = ni + 2n (3-7) 2 It is based on the idea that if g is not very large (< 1.0), the probability of 3 or more transmissions in a slot is small. (3-7) assumes that in any collision slot there is only 2 transmissions involved, thus M is an under-biased estimator for M. Since M can vary in a wide range, the estimator error is defined in terms of a relative error factor e e = M-M M and its bias and variance are defined as the mean and variance of e, respectively, b(M) = E[e] = E M - M M (3-8) Var(M) = Var[e\ = Var M-M M To evaluate (3-8), it is assumed that data arrivals obey Poisson distribution, with arrival rate g per slot. In the estimation of M , g is the a priori The knowledge. distribution of n\, n<i with M given, is not the same as (3-3), since slot occupancies are related. If each of the M transmissions is equally likely in any Chapter 8: Data Packet Transmission 51 one of the n slots, then the distribution function is given by [Appendix], p{n n ,M,g) - ^ u 2 ^ n u _ iyu _ n2 n _ i + n _ n i _ )!(/ _ n2 )\ \ m m (3-9) where Jo = max(ni + n — n,0). 2 The calculations of (3-8) suggest that, although the variance decreases, the bias increases with the increase of n (equivalently, the length of observation period). It is therefore necessary to modify M as follows M = n + 2n + d(g, n) x (3-10) 2 where d(g, n) is chosen to offset the increase of bias with n. Denote the bias m , which is given in (3-8), then the variable e — m has € e zero mean and the same variance as e, i.e. E M-M —U m « = 0 M which implies that the estimator M should be modified according to M-M (M — M • m ) — M M t M m ' = The correction term is M • m . Since M is unknown, it is substituted by M • m , e € thus, the modified estimator is M= (ni + 2n ) (1 - m ) 2 where m is given in (3-8). e e (3-11) 52 Chapter 3: Data Packet Transmission Figure 3-3 shows the bias and variance of M (modified). In the range 0 < gr < 1.0, the estimator has small bias and variance. The bias still increases with n, but at a very slow rate after n > 20. Estimation is an important and independent topic. Instead of going into detailed discussion of it, the above 2 algorithms serve as the examples which show the possibility of acquiring g(t) by estimation to a satisfactory accuracy. In section 3.5, another algorithm will be proposed which shows the possibility of minimizing the effect of propagation delay R. Based on these examples, it is assumed in the following simulations and analysis that g(t) can be obtained free of error. The effect of estimation error of g(t) is studied in section 3.5. 3.2.3 Performance Analysis of A L O H A Protocol There are basically 2 analytic approaches to ALOHA protocol, i.e., the steady state approach by Abramson [16] and dynamic Markovian process approach by Kleinrock et al [17]. In this section, the former approach is used. The following assumptions are made: 1. Infinite population model is used for the analysis. The data packet arrival process is Poisson. It has been proven that for number of users larger than 10, the performance of infinite population model is very close to that of a corresponding finite population model. Chapter S: Data Packet Transmission 0.08 w O I 0.07 0- 0.06-i 0.05- Ld 0.04 .9. 0.03-J c o J A g = 1.0 O 9 = 2.0 "o E 0.02- UJ 0.01 d2= 0.00 20 30 40 50 n 0.25 O C D •c o > o c o E 0.20H 0.150.10- 0.05 "to 0.00-f0 10 20 • i 30 40 50 n Figure 3-3 Bias and Variance of Modified Arithmetic Estimator M 54 Chapter 8: Data Packet Transmission 2. The Independence Assumption: 7(fc) =0 VA; ^ 0 (chapter 2). Note this implies that (3-12) P (l)=p - (l-p ) l r 1 v v where / is the length of consecutively occupied slots plus 1. The results in chapter two (the last section) suggest that the independence assumption is reasonable for low and medium voice utilization (p = 0.0 to v approximately 0.7) and VAP-I. 3. Two general assumptions for all analysis and simulations in this thesis: a) The size of packets is of the fixed length of 1 (slot); b) Transmission/reception errors are caused only by packet collisions; those caused by channel noise, etc, are negligible. Define: - random variable L to be number of consecutively voice occupied slots plus 1 (figure 3-1); - random variable M to be number of data arrivals during the L interval, obeys Poisson distribution; - variable a/ to be delayed transmission factor as defined in (3-2) with the difference that g(t) is replaced by steady state average total channel traffic Chapter 8: Data Packet Transmission 55 factor G, defined as G = W)= Jim Ht)dt I* (3-13) Let S(/,m) = P [l successful transmission | given L — l,M = m] r = m(l - a / ) m _ 1 (3-14) a/ Let £ be the average of S(l,m) over all values of / and m, then 5 = ^2s{l,m)P {m\l)P {l) Z,m r (3-15) r where P (m i) = r —e m! Thus S = £ m ( l - )»-i p (/)M!l -0' a i a i e p oo = E^P-^r'ftwE' 2i -i» / = (g m=l 1 * )r ' - (3 16) J2 Gle- < P (l) a ai Gl r Define the normalized data utilization, pd, as number of slots used by data transmissions number of slots available to data transmissions then since in every L — I slots, (/ — 1) slots are occupied by voice and one slot is available to data, S is numerically equal to the normalized data utilization p^. 56 Chapter S: Data Packet Transmission The probability of successful transmission P is given by s P = 5(1 - p )/G 8 v = ^o l(l-p )e-°» P (l) (" ) Gl il v 3 r 17 The average retransmission number E is given by E = 1/P - 1 (3-18) S The total delay is given by D = E{R + K ax/2) + 1.5 + R A m (3-19) As a verification, if P (l) =6(1 — 1), that is no voice case, from (3-17) and r (3-18), E = e - 1 G which is the familiar formula for no voice case. If P (l) = (1 — Pv)p ~ as the result of independence assumption, then from 1 r v (3-17), CO P = s «/'e" ' (l - PvfPv' a G/ 1 (- ) 3 20 3.3 R e s e r v a t i o n P r o t o c o l i n t h e I V D S S y s t e m s Under voice pattern structure, reservation protocols can be straightforwardly applied, with the adaption that reserved transmissions are only scheduled in the slots not being occupied by voice connections. 57 Chapter S: Data Packet Transmission Frame i SSN = 4 © © © 0 YZYA E3 I © V777Z7\ Four R e s e r v a t i o n s Transmitted During The i Frame t h Global Queue - 5 4 3 2 1 - 1 Delayed to the (> + l)th Frame Updated p o s i t i o n ( 5 - S S N ) = 1st l h Figure 3-4 Illustration of the Reservation Protocol As in the pure data environment, there are many variations of reservation protocols depending on how the request packets are transmitted. In the ideal reservation protocol, it is assumed that a hypothetical dedicated subchannel for request transmissions exists and the subchannel is error free and collision free. This reservation protocol is assumed here. The problem of request packet transmission will be discussed in chapter 4. The following is the protocol description: Chapter 8: Data Packet Transmission 58 1. Whenever a new packet arrives, send a request via the request subchannel. When the echo of the request is heard, enter the request into the global queue; 2. Wait until the beginning of the next frame. Suppose this is the ith frame, and suppose the request is in the fcth position in the global queue at the beginning of the ith. frame, and the total number of slots not being occupied by voice in the ith frame is SSN, where 0 < SSN < Sf. If k < SSN, transmit the packet corresponding to the request in the fcth unoccupied slot. Iffc> SSN, delay to the beginning of the (i+ l)th frame; repeat the procedure 2. The updated position of the request at the beginning of the (i + l)th frame is (fc — SSN)th, since SSN requests ahead of it have been transmitted during the ith. frame. An illustration is given in figure 3-4. In the above protocol, transmissions take place only at the beginning of each frame, instead of transmissions for each request at the time of its arrival at the head of the global queue. The difference between the two is that the total delay of the former is Sf/2 slots larger than that of latter, because in the former, the time from a request enters the queue to the beginning of the following frame is on the average Sf/2. However, since the basic overhead of reservation protocol 2R is more than 20 times larger than Sf/2, the difference will be considered negligible in the IVD environment under discussion. 59 Chapter 3: Data Packet Transmission 3.3.1 Performance Analysis of the Reservation Protocol The total delay of reservation protocol DR consists of the 2R + Sf/2 overhead plus the queueing time D , which is the time a request resides in the global queue Q until the corresponding reserved packet is transmitted, i.e., D D q R = 2R + Sf/2 + D (3-21) Q is different for VAP-I and VAP-II. It is noted however, that the total number of reservations in the global queue at the beginning of the ith. frame, denoted as qi, is the same for VAP-I and VAP-II. If Q denotes the expectation d of then D for VAP-I is given by (figure 3-5(a)) q D = l Qd + 1 q Under independence assumption, 1 - Pv thus Qd + D q 2(1 - 1 Pv ) (3-22) For VAP-II, D can be calculated by (see figure 3-5(b)), q D = p Sf H q v h Qd (1 - Pv)Sf An exact analysis for Q is given in [18]. The outline is as follows. d (3-23) er S: Data Packet Transmission Queue Q d = 3 P1 - P a c k e t 1, e l c P1 (P2)P3 zm \ YZWA I vm Figure 3-5(a) Global Queueing Delay D for VAP-I q XXXX/X/X/X/X/X/X Pv f S Figure 3-5(b) Global Queueing Delay D for VAP-II q 61 Chapter 8: Data Packet Transmission Define g --= number of data packets in the global queue at the beginning of ith frame; t V{ = number of slots occupied by voice in the ith. frame; di i + = number of data packet arrivals during the ith. frame. Then the distribution of g,- in the steady state is derived using the moment generating function (mgf) approach. For the data queue size qi the following relationship holds between adjacent frames, Qi+i = [Qi ~ (* ~ Vi)} + di+i (3-24) + where [fc]+ = max(0,fc),s = Sf. The sequence {qi,Vi} is a two-dimensional Markov chain. For the steady state joint probabilities P{qi = /,u - = n}, define t the mgf (moment generating function) CO X {z) n = X) t i i = l,»i = n}z 1=0 p l (3-25) Then L(z), the mgf for qi, can be expressed as a L(z) = Y, *( ) n=0 X z (" ) 3 26 where s = Sf. It is shown that the following matrix equation holds for the vector X(z) = [Xo(z),Xx(z), • • • ,X (z)] , t 8 where [ ] denotes the transpose operation: f [I - G(z)k(z)]X.(z) = G{z)B{z) (3-27) Chapter 3: Data Packet Transmission 62 where G(z) is the mgf of d^; with Poisson data arrival process, G(z) = exp[-gs(l - z)\ where g is the average arrival rate, 5 = Sf. The (s + l)(s + 1) elements of A(z) are given by A where <f> mn = <f>nmZ~ ] 0 <m s+n m n = P{t>i+i = n\v{ = < s, 0 < m < s m} and is given in (2-5) and (2-6). The (s + 1) elements of the vector B(z) are given by B(z) = ftl){z) where matrix $ = [<t>mn], D(z) is an (s + 1) vector, given by D {z) = ]T [1 - z-^+Vn, 0 < n < 6 n Jfe=0 where irk n = P{qi = k,V{ = n.}, which are (s + l)(s/2) unknown boundary probabilities. It can be shown that the equation det[J- G{z)k(z)\ = 0 has exactly (s + l)(s/2) roots on and inside the unit circle [18]. Once the roots are found, a set of (s + l)(s/2) linear simultaneous equations ensue from (3-27) which are solved to determine x^'s. Then (3-27) can be solved for X(z), and Qd is determined by using the relationship Q d ~ -dz- = U l where L(z) is given in (3-26). Since the number of unknown boundary probabilities {iXknj is proportional Chapter 8: Data Packet 68 Transmission to s (s = Sf throughout the discussion), the above approach may become com2 putationally infeasible when Sf is large. In [19], an approximation is proposed. The average data queue length Q d Oi =,. is given as , (l-Aj)(l-t;)(l-w) where pd is the normalized data utilization, v and o (3-28) are the mean and variance 2 v of V{, given in (2-12) and (2-15), respectively. u> = i(k)\k=s ar f i d is given in (2-18). The most crucial factor here is h(p ), which is a convex cup function and d ranges from 0 to 1. Numerical (simulation) results indicate that h(p ) d is heavily dependent on the values of s and N, where N is the number of voice sources. In the Poisson arrival case, N —>• oo. The choice of /i(/9<f) is highly empirical. For the special case s = N, [19] recommends h(p ) d normalized queue improvement for M/M/s " h ( P i ) 1 queueing model, which is given by (.«)- + to be the reciprocal of the h ~ ( 1 When applying the approximation to the reservation protocol under study here, it is found that the validity of the approximation is heavily dependent on the voice statistics, especially the voice blocking probability. For Sf in the wide band range, blocking probability B(s,a) was shown to be negligible for voice arrivals in chapter 2. But this is not true for the evaluation of Q . d blocking probability 1 0 to <3d; with 1 0 -10 -20 < B(s,a) < B(s,a) It was found that with < 10 , (3-28) gives good approximation -10 < 10~ , h(p ) 5 d should be modified by using s' in place of s in (3-29), where 1 < s' < s. In these B(s,a) (3-28) has the accuracy of ±20%. With B(s,a) range the approximation > 10~ , the approximation does 5 not apply. The special case 5 = TY considered in [19] corresponds to B(s,a) = 0. Chapter 3: Data Packet Transmission 64 Although the exact solution according to (3-27) may be computationally infeasible for Sf in the wide band range, it is noticed from (3-24) that the condition [ft - (S - )} + f Vi =0 can be easily satisfied when Sf is large. If the condition is satisfied at the beginning of every frame, then the queue size is simply the same as the average data arrivals in a frame, i.e. Qd = d Figure 3-6 shows the excess queue size Aq = (Q& — d)/d for p — 0.5, v Sf = 100 and 200. It is seen that Aq is virtually equal to zero in 0 < p < 0.5 for d Sf — 100 and in 0 < p < 0.6 for Sf = 200. Also shown is Aq for shorter voice d length pT = 200, the range for which Aq is very close to zero is 0 < pj, < 0.6. l Based on these observations, the following approximation is taken to evaluate the queueing delay D : express D as q q D =D + D q 1 2 where Z>i is given in (3-22) for VAP-I and in (3-23) for VAP-II, with Q replaced d by d. D is used to represent the missing part A Q = Q — d. Choice of D 2 d 2 is empirical. Here it is chosen as the delay of M / G / l queue with geometric service time distribution, this corresponds to the distribution of the length of voice consecutively occupied slots under the independence assumption. Hence Z?2 is given by A 7"^ ( a 1 The right hand side is the well-known expression for M / G / l queueing delay, Chapter 3: Data Packet Transmission 65 Figure 3-6 Excess Queue Size Aq versus p d where r and o are the mean and variance of the service time distribution, re1 spectively; \ — p . With the service time distribution given in (3-12), the above d becomes D 2 = Pd{l + Pv) 2{1 - p ){l v Pi ) Simulation results indicate that the above approximation gives the same accuracy as (3-28). Both approximations are reasonable for low and medium p d and p . Discrepancies become significant when p is large (> 2/3). v v Chapter S: Data Packet Transmission 66 The total delay of reservation protocol DR can be expressed as D R = 2R + S /2 + D Q f (3-30) It can be seen that the queueing delay D contributes only an insignificant Q amount in the total delay, except for very high p and/or p&. As an example, v take Sf = 100, p = 0.5 and pd — 0.5, D = 28.2 slots from the simulation and Q v is 27.5 by the above approximation, which accounts for 1.2% of total delay DR, which is 2478 slots, for R = 12S . f 3.4 Simulations of the two protocols A difficulty in the simulation of IVD system is due to the disparity in the time scales for voice arrival rate and data arrival rate. Voice call interarrival time is in the order of minutes or seconds while data interarrival time is in the order of slots. To run a simulation that is statistically significant in terms of the number of voice calls processed, the number of data packets that are processed will be in the order of a hundred million. This results in very long simulation time and expensive computing cost. Because of the limitation, most results in this section represent means of 9 runs of different random generator seeds. The standard deviations of the means are within 5% of the means unless otherwise specified. 3.4.1 Simulations for A L O H A protocol Simulation results are shown in Table 3-1 for p = 0.0 (no voice case), 1/3(low v Chapter 3: Data Packet Transmission 67 voice case), l/2(medium voice), 2/3(high voice) and 4/5(very high voice case), with VAP-I. Figure 3-7 plots the curves of mean packet delay with analytic results as comparison. In general, it can be seen that the analysis gives reasonable accuracies of the real (simulated) delay-throughput characteristics, especially for p in the low(< v 1/3) and medium (from 1/2 to 2/3) ranges. Discrepancies between analytic and simulated increase with the increase of p . v The following factors contribute to the discrepancy between analytic and simulated results: 1) Independence of voice pattern: As the analysis is done under independence assumption, it is expected to have certain discrepancy between the analytic and simulated results. As a check, simulation was run for the simulated independent voice pattern. In Table 3-1, rows corresponding to p = 0.5* are the results for simulated independent voice v pattern. Compared with p = 0.5 row which corresponds to VAP-I, the results v of simulated independent voice pattern coincides with that of analysis very well. For VAP-II voice pattern background, simulation results are shown in Table 3-2. The differences between analytic and simulated results are significant even for small p range, indicating that the independence assumption is not valid for v VAP-II voice pattern. Table 3-1 and 3-2 also suggest that ALOHA performance deteriorates significantly on aggregatively distributed voice pattern compared to the more evenly distributed pattern with exactly the same p v statistics. Cor- Chapter 3: Data Packet Transmission Figure 3-7 ALOHA Delay-Throughput Characteristics er 8: Data Packet Transmission Table 3-1 ALOHA delay-throughput with VAP-I R = 1200, S = 100, K f max = 120 Pv Pd Simulation Analysis %Difference 0.0 0.05 0.10 0.15 0.20 0.25 1281.6 1345.8 1451.5 1572.7 1763.3 1269.7 1350.7 1448.6 1574.4 1742.9 0.94 -0.36 0.20 -0.11 1.17 1/3 0.05 0.10 0.15 0.20 0.25 1315.4 1422.7 1571.3 1765.4 2027.4 1295.0 1407.0 1550.1 1743.7 2020.3 1.58 1.12 1.36 1.24 0.35 1/2 0.05 0.10 0.15 0.20 0.25 1332.2 1480.7 1675.4 1880.9 2182.1 1307.6 1439.8 1609.6 1847.8 2207.3 1.88 2.84 4.09 1.79 -1.14 1/2* 0.05 0.10 0.15 0.20 0.25 1310.8 1431.9 1621.3 1819.8 2214.5 1307.6 1439.8 1609.6 1847.8 2207.3 0.25 -0.54 0.73 -1.52 0.33 2/3 0.05 0.10 0.15 0.20 0.25 1407.8 1539.6 1771.6 2029.4 2483.5 1323.5 1473.1 1677.4 1974.2 2442.8 6.37 4.51 5.61 2.80 1.67 4/5 0.05 0.10 0.15 0.20 0.25 1425.3 1629.6 1896.1 2201.2 2853.8 1337.2 1504.3 1739.7 2093.2 2685.1 6.59 8.33 8.99 5.16 6.28 0.05 0.10 0.15 0.20 0.25 1424.1 1627.8 1913.9 2354.3 3111.5 1337.2 1504.3 1739.7 2093.2 2685.1 6.50 8.21 10.01 12.47 15.88 4/5t * Independent voice pattern. fWithout input voice control. Chapter 3: Data Packet Transmission 70 Table 3-2 ALOHA delay-throughput with VAP-II R -- 1200, S = 100, K f max = 120 p» Pd Simulation Analysis /^Difference 0.0 0.05 0.10 0.15 0.20 0.25 1279.5 1351.2 1460.4 1565.4 1760.9 1269.7 1350.7 1448.6 1574.4 1742.9 0.77 0.04 0.82 -0.57 1.04 1/3 0.05 0.10 0.15 0.20 0.25 1471.4 1538.3 1627.4 1731.9 2085.7 1295.0 1407.0 1550.1 1743.7 2020.3 13.62 9.33 4.99 -0.67 3.24 1/2 0.05 0.10 0.15 0.20 0.25 1501.2 1641.6 1810.7 1991.3 2148.1 1307.6 1439.8 1609.6 1847.8 2207.3 14.80 14.02 12.49 7.77 -2.69 2/3 0.05 0.10 0.15 0.20 0.25 1780.3 1829.8 1941.2 2109.9 2524.7 1323.5 1473.1 1677.4 1974.2 2442.8 34.51 24.21 15.73 6.88 3.35 4/5 0.05 0.10 0.15 0.20 0.25 1772.3 2063.1 2225.6 2457.9 3166.9 1337.2 1504.3 1739.7 2093.2 2685.1 32.54 37.14 27.93 17.42 17.95 71 Chapter 3: Data Packet Transmission relation of voice pattern is an important factor in the performance of ALOHA protocols in an IVD environment. 2) Effect of blocking condition: Blocking condition occurs in high p range. During the blocked period, v no data packet can be transmitted. As new packets are continuously arriving, the total channel traffic grows rapidly during the period and the system is very likely to be driven into unstable region [17]. This will result in large increase in the average packet delay. Figure 3-8 (a) shows the fluctuation of available slots to data transmission in each frame for a randomly sampled period of time, for p = 0.85, together with the corresponding short time average packet delay. v Effect of blocking condition can be seen very clearly in the picture. In order to avoid the occurrence of blocking condition, voice input control mechanism should be implemented, i.e., the number of voice connections in any given frame should be limited to a number 5^, S < Sf, so that at least Sf — Sj, d slots are always available to data transmissions. Figure 3-8(b) shows the same system of Figure 3-8 (a) with voice input control. The improvement on data performance is dramatic, while it has little adverse effect on voice performance, (see Chapter 2 equation (2-11) and figure 2-2). In Table 3-1, data shown are those with the input voice control introduced as above. As comparison, data in p — 0.8")" rows show the same system without v input voice control4 X Since the variance of the delays for high p„ range without input voice control is large, these data can vary significantly. 9000 5 o •a 9000 Slots ALOHA-I/VAP-I eooo- 8000 c »" c C i— OS W i t h Input v o i c e c o n t r o l S,=10O 7000- fa ion "o 6000y c i2 o in O ?r o> «- 5000- $ 4000- Go >» o Q 3000 W 3 *•*. Co Co *•* • o 3 2000 Q_ C § 2 1000 1 I 1 1 1 1 100 I I 200 300 1 1 1 1 1 1 400 Time in Frames 300 1 1 1 1 1 400 300 600 700 Time in Frames 900 1000 0>) 00 Figure 3-8 Effect of B l o c k i n g C o n d i t i o n s 3 Chapter 8: Data Packet Transmission 78 3) The total channel traffic factor: Average G is used in the steady state performance analysis while in the simulation instantaneous g(t — R) is used. This can also contribute to the discrepancy of results between simulation and analysis. It turned out from the simulations that the instantaneous control mechanism of g(t — R) is indispensable. The system is likely to go into unstable state because of combined fluctuation of voice background and data arrival, if g(t — R) is replaced by average G. The stability of ALOHA protocol in the IVD environment is an important measure of performance. In section 3.5, some interesting results about stability will be derived. 4) Effects of other system parameters: ) a Kmax'- figure 3-9 shows simulated data delay versus K m a , x for p = v 1/2, pa = 0.1 and 0.2. Dashed curves show corresponding analysis. As in the pure data case, K m a x has little effect on ALOHA perfor- mance. * b) Sfi As can be seen from chapter 2, effect of small Sf should be similar to that of high , as both are related to the probability of P v blocking conditions. Figure 3-10 plots simulated data delay versus Sf for p = 0.5, p,i = 0.1 and 0.2. As long as Sf is in the wide band v * K max is related to stability. It is shown that for K max > KT> where Kj- is related to system parameters such as channel load and user population, the further increase in K max has insignifi- cant effect on ALOHA performance, this is especially so if additional transmission/retransmission control mechanisms are used. Chapter S: Data Packet Transmission 3000 ALOHA-I/VAP- R=1200 ~o to c S =100 2500- / f P =1/2 / v >~ o <D Q 2000- % o D D_ C D a> X' Simulation O- p =0.2 d Analysis 1500- p =0.1 d 2 1000 I ' I ' l 10 100 2 1000 2 3000 max Figure 3 - 9 ALOHA Delay versus K max AL0HA-I/VAP-I R=12S 2.5 •<max = 120 _D d) Q "D 0) P =1/2 "o -O- ¥ N E 1.5- o p =0.2 -O- -O- -Q- -• d o -o o- -a p „ = 0.1 1- 0.5-t 10 I ' I ' l I III I 100 M I M 4 I I I | 1000 Figure 3-10 ALOHA Delay versus S f 2 3000 Chapter S: Data Packet Transmission 75 range (> 50), there is little difference on data performance. For very small Sf, delay increases as blocking condition is more likely to occur for the same p than if Sf is large. v 3.4.2 Simulations for reservation protocol Table 3-3 lists the results for global queueing delay (Total delay DR — 2R) for p = {0.0,1/3,1/2,2/3, 4/5} with VAP-I. v Mean curves are plotted infigure3-11. These results indicate the range of p for which the independence assumption and the approximate analysis for v reservation protocol are valid, together with the accuracies of the approximations. As in ALOHA protocol, effect of voice pattern structure is shown in Table 3-3 (rows of p = 0.5*) andfigure3-11 for the protocol performance on VAP-II v voice background. The voice blocking condition occurs for p > 0.8 which causes v the significant increase of the variance of simulation results. The results presented for p = 0.8 is with the voice input control described in the last subsection. v Some Observations 1) Performance analysis of multiaccess protocols in the IVD systems: From the simulation results of ALOHA and reservation protocol, it is seen that Independence Assumption is valid for voice patterns of strong random na- er 5: Data Packet Transmission Table 3-3 Reservation Delay-Throughput with VAP-I R1200, S = 100 f Pv Pd Simulation Analysis ^Difference 0.0 0.10 0.30 0.50 0.70 0.90 56.4 66.7 77.9 89.0 102.8 55.6 65.7 76.0 86.7 100.0 1.52 1.48 2.44 2.64 2.82 1/3 0.10 0.30 0.50 0.70 0.90 57.0 66.6 75.8 86.7 102.6 55.9 66.2 76.7 88.1 104.7 1.94 0.65 -1.28 -1.58 -2.06 1/2 0.10 0.30 0.50 0.70 0.90 58.3 69.0 78.2 88.1 106.2 56.2 66.6 77.5 89.5 109.5 3.74 3.49 0.88 -1.56 -2.98 1/2* 0.10 0.30 0.50 0.70 0.90 93.2 104.7 115.9 142.4 173.6 103.2 113.6 124.5 136.5 156.5 -9.73 -7.87 -7.39 4.45 10.97 2/3 0.10 0.30 0.50 0.70 0.90 60.0 68.0 80.4 99.3 130.1 57.0 67.6 79.0 92.3 119.0 5.33 0.69 1.29 7.67 9.37 4/5 0.10 0.30 0.50 0.70 0.90 64.4 74.7 92.7 115.9 170.2 58.8 69.5 82.0 98.0 138.0 10.05 7.54 13.31 17.37 23.21 * with VAP-II Chapter 8: Data Packet Transmission 78 ture such as generated by VAP-I. However, the assumption does not hold with VAP-II. It was seen in Chapter 2 that VAP-II voice pattern tends to have strong correlations. It can be intuitively generalized that for other voice assignment protocols of strong predetermined nature (for example, a protocol which assigns empty slots to new voice calls from the center of the current frame), the Independence Assumption will not hold. It was shown in Chapter 2 that voice pattern background is a very slowly time varying process compared to the time scale of data activities. Based on this, a Fixed Pattern Assumption can be applied to the analysis of voice patterns of strong predetermined nature. The basic idea is to assume that the voice pattern is fixed, and delay for each fixed pattern is calculated; the total delay will then be a weighted sum of those of all possible patterns with weighting factors being probabilities of occurrence of each possible pattern. Two major difficulties are associated with this approach: the first, it is easily seen that the number of all possible patterns increases at a factorial rate, with the increase of Sf. Thus, for Sf in the wide band range, the complexity of computation could be expected; the second problem is that there are a number of patterns for which average data input rate is larger than the output rate, thus no steady state solution exits for these patterns. When dealing with these situations, generally speaking the method of fluid approximation is used* 2) Performance degradation of multiaccess protocols in the IVD systems: It is axiomatic in queueing theory that the performance of a system worsens Such an approach was reported in [20], yielding a reasonable result for high pd range, but is rather inaccurate for low pd range. The analysis was done on reservation protocols. Chapter S: Data Packet Transmission 79 as the system becomes more "irregular". Thus the performance in an integrated system can be no better, and in general will be worse, than that of a system in which it is allocated the same fixed capacity. This is shown by the analytic and simulation results of ALOHA and reservation protocols in the last section and this section. In the distributed IVD environment, the difference of reservation protocol on different voice pattern background is small, since the 2R plus half Sf overhead contributes the most to the total delay. Consequently, the total delay is not affected significantly by voice utilization. The effect of blocking condition on reservation performance is also smaller than that on ALOHA performance. It does not seem important to distinguish among different voice pattern backgrounds. On the other hand, ALOHA protocol is affected significantly by difference of voice pattern background (different p' s, VAP's and blocking, etc). v Comparison of ALOHA performance with reservation performance leads to an important observation: with the introduction of voice pattern background into IVD system, data access protocols of little coordination deteriorates significantly while data access protocols of strong coordination are not as much affected. Since the natural extension of ALOHA protocol for pure data enviroment shows undesired performance deterioration in an integrated environment, especially for VAP-II voice pattern background, another version of ALOHA protocol is proposed in the following section. The basic idea is, by incorporating certain extent of coordination into random nature of ALOHA protocol, it could be less 80 Chapter 3: Data Packet Transmission susceptible to the fluctuation of voice pattern background, so that an improved performance in the IVD environment is expected. 3.5 A L O H A protocol (The Second Version) The protocol description is as follows: 1. Any new arrival during ith. frame postpones the transmission until the beginning of the (* + l)th frame. 2. At the beginning of the (i + l)th frame, with probability p, delay the transmission further to the beginning of the (i+2)th frame; with probability 1 Pi go to the next step. — 3. Choose a number randomly with equal probability from among 1 to M,- i, + where M i is the total number of unoccupied slots in the (i + l)th frame. t + Suppose the outcome is j, 1 < j < M j , transmit in the jth unoccupied +1 slot. 4. Collided transmissions repeat the same procedure as above, as well as delayed transmissions. p is also called delay factor and is defined as (3-31) where g = g(t — R), M = M; . +1 81 Chapter 8: Data Packet Transmission Because the unoccupied slot in which data transmission is to take place is chosen randomly and evenly from among all unoccupied slots, the positions of these unoccupied slots should have no influence on the slot be chosen; as a consequence, the performance of the protocol should not be affected by the distribution of voice occupied (or unoccupied) slots (VAP-I or -II, for example); moreover, it is shown in the following subsection that with the control in step 2, the effect of fluctuation of voice connections can be greatly reduced. For the convenience of notation, let the ALOHA protocol described in section 3.2 be called ALOHA-I, and in this section ALOHA-II. 3.5.1 Performance Analysis of ALOHA-II Let Mi be the number of slots available to data transmissions, and n - the number t of packets awaiting transmission at the beginning of the ith. frame. n - is also t called the backlog. Then n i+1 = (rn - ki) + di + n (3-32) where ki - number of packets attempted transmissions (step 3 in the protocol); di - number of new packet arrivals during the ith. frame; r,- - number of retransmissions from the previous collisions. 82 Chapter 8: Data Packet Transmission Since k{ is dependent on M- and n,, (3-32) describes a 3-dimensional t Markov chain {ra,-, Mi, r,}. The transition probabilities for M- is known as (see t (2-5) and (2-6)) P{M i+1 = M} — Mfx = M-l\Mi P{M i+1 = M\M P{M i+1 = M+1\M The dependency offc»on { = M} = 1 - A - Mfi { = M} = A and Mi complicates the analysis, which is further complicated by the feedback introduced by the control in step 2. The term also complicates the analysis. In the following analysis, the equilibrium point analysis (EPA) and fluid approximation approach is used. To make the analysis tractable, it is assumed tentatively that the estimation of g is perfect (zero bias and variance for any sample size). The results thus obtained are modified later by taking the estimation error into account. The basic principle of EPA is that at EP (equilibrium point), the input to the system, 5, , equals to the output of the system, S t, i.e, ou n Sin — Sout = S where S is the throughput of the system. In the following analysis, the expressions of S t and Si , conditioned on ou n Mi andra,-,are derived; then the above EPA principle is used to evaluate the protocol performance. 83 Chapter 3: Data Packet Transmission 1) S t'. ou Given Mi = M, n» = n, the probability of number of attempted transmissions, k, (all the subscripts are dropped from now on), is given by p(k\M,n)= (2)p*(l-P)""* ( 3 3 3 ) where p = min (J^-, lj (3-34) the same as (3-31). Given M, n andfc,the probability of number of successful transmissions, m, is given by [Appendix] p(m|fc, M, n) = ' ' v 1 1 ,/r m\M J k 777 w x , „ TT ' (M — — m)!(fc - j)! Y(-l) j-^ 3 (3-35) v ; The average number of success, m, given M and n, is m = E[m\M, n) = ]T E[m\k, M, n]p(k\M, n) k ( 3_36 ) It can be shown that [Appendix] E[m\k,M,n) =fc(l- jj) ~ which does not depend on n whenfcis given. h l (3-37) 84 Chapter S: Data Packet Transmission Combine (3-33), (3-36) and (3-37) «-E(;yd-rt-**(i-y k=0 v ' v k-l (3-38) 7 After some algebraic manipulations, m = p n [ p ( 1 ~ ^ f ) + " 1 P r (3-39) l By (3-34), n < M 1, P = \ M n> M n' (3-39) is n-l n< M m =< (3-40) n-l M l 1- n n> M The output of the system, S t, is otl n-l ra S ut — T T M = < 0 Define , \ - ( M \ n<M (3-41) 1 n> 1 M : n M * T h i s d e f i n i t i o n is s l i g h t l y different f r o m t h a t i n (3-1). H e r e the d e n o m i n a t o r is t h e n u m b e r of slots n o t o c c u p i e d b y voice, w h i l e i n (3-1) i t is the t o t a l n u m b e r of slots ( o c c u p i e d as w e l l as o c c u p i e d b y voice) d u r i n g t h e o b s e r v a t i o n p e r i o d . 85 Chapter 3: Data Packet Transmission Then a [ l - - ) , g<l (3-42) 'out Figure 3-12 shows S t versus g, for M = 5, 10, 20 and 100. Two important o u features of Sout are noticed: i) For different M, the difference between S t is small. In fact, after M > 10, o u the difference is negligible. ii) All curves approach e , when g is large. In fact, e _1 _ 1 is the asymptotic line for all the S t curves. From (3-40), when n —>• oo, o u (3-43) 2) S : in i) For finite population model and stop-and-wait transmission rule, 5 - is t n given by S i n = o { N - n) (3-44) where N is the size of population; o is the probability that a user has a packet to transmit; and n is the backlogged number of users. ii) For infinite population model, o in (3-44) goes to infinitesimal and the Chapter S: Data Packet Transmission Figure 3-12 Output Rate S t versus g ou 87 Chapter 3: Data Packet Transmission product oN is constant and is the aggregated Si rate, i.e, n Si = aN = constant n It is also the 5 1W for a finite population if the transmission rule is selective repeat, as is the case for both ALOHA-I and ALOHA-II. 3) Equilibrium point and stability: Putting S t and Si ou n together in figure 3-13 ( M = 5); the following can be noticed: i) If S in < e , that is region I in figure 3-13, there is only one intersection _1 between S ,t and S{ , where S ,t = S{ , that is the EP. Moreover, it is a ov n ov n globally stable EP. ii) In region II of figure 3-13, there are 3 intersections between S ut <l Si ] an 0 n except point A, which is a locally stable EP, the rest are unstable EP's. Region II is unstable. 4) Throughput S and voice fluctuation: i) The maximum channel throughput normalized to <S/(1 — p«), S , max is e , _1 which is independent of voice fluctuation. This is shown as the following: Chapter 3: Data Packet Transmission Figure 3-13 S in / S out and EP's 89 Chapter 8: Data Packet Transmission Define p{M) = P {Mi = M} r which is given in (2-7), then the maximum throughput in terms of number of packets is rn = y^m max ma2 (M)p(M) (3-45) M where fn (M) is max rn~max(M) = lim m(M) n—»oo by (3-40) m w(M) = M e - 1 m( thus (3-45) becomes m = M e max (3-46) _ 1 0 where Mo is the average number of available slots to data transmissions, from (2-8) and (2-9) M 0 = S {l - p ) v f The normalized throughput is thus e . -1 ii) For S{ < > the throughput is closely approximated by e_1 n S = Si n =S t 0U ± where M a e 0 (3_ ) 47 is the average number of slots available to data transmissions; 0 9e — n /M , e x-M {g -l/M ) 0 where n represents the EP value of n for M = Mo. This is e shown as the following: Chapter S: Data Packet Transmission 90 The number n — k represents the delayed transmissions per frame; and k — m the number of collided packets after attempting transmissions. Given M and n, the averages are n — k and k — rn, where k = E[k\n], fn = £7[m|n] respectively. From (3-33), n —k = n(l — p) and (3-39) k-m= np{l - [p(l _ -L) + l - p]*" } 1 From (3-34) f 0, n- k= < n < M {n — M, (3-48) n > M and [ n[l - (1 - 1/M) ~ }, n<M [M[l-{l-l/n) - ], n>M n k-m = { n 1 1 (3-49) If the input rate per frame is n,„, then when M < n{ , the backlog n — k n increases linearly, while the backlog k — fn is held at its maximum value, which is M(l -e when available slots returns to M > rii , - 1 ) the excess number of packets in the n backlog n — k is cleared; as long as n in < M e _ 1 0 the steady state condition can be reached, i.e, n out — 'nin 91 Chapter 8: Data Packet Transmission or equivalently, S ut — S{ 0 n the same as (3-47). Another point of view, when considering the effect of the fluctuation of M is the following: The variation of M can be equivalent to a perturbation in 5 , tw ASi . As long as 5 n tre is in region I, no matter how large ASi n finite period of time after ASi n may be, after a disappears, EP is obtained with certainty, and the condition 5 - = S t = S prevails. The average throughput is thus well t n ou approximated by (3-47). However, the larger ASi n is, the longer it will take the system return to the EP. It is thus expected that the fluctuation of M will cause the increase of the variance of throughput S. The exact value of S is S=J2 (3-50) Soutp{M, n) n,M where p(M,n) = P {Mi = M,n - = rc} r t (3-47) approximates (3-50) by letting p(M,n) = 8(M — M ,n — n ). From 0 e previous literatures[21,22], it has been concluded that for a globally stable EP, such an approximation is accurate. Simulations in the next subsection well confirm the approximation of (347). 92 Chapter 8: Data Packet Transmission 5) Delay D : q D q is defined as the delay incurred by a packet due to the delayed transmission and collision retransmission* Conditioned on n and M, D {M,n) is q ~ "0 ^ ^ + D {M, * ) = ( = - ^ f S + q " (3 51) where R is the propagation delay; K is the retransmission delay; R + K ~> Sf] k = E[k\n], rn = E[m\n]. By (3-33), (3-39), (3-48) and (3-49), l-n - - 5 D (M,n) 1 n < M (R + K), (3-52) = q (n/M-l)S l-n + f n {R + K), n>M and total D is q D q = Yl q( > D M )Pr{Mi n (3-53) = M, m = n} By the same EP approach about throughput, D q w D (M ,n ) q 0 e 1— ne [R + K), {n <M ) e (3-54) 0 Since n < M for EP, the approximation ignores the term [n/M — l)Sf. e 0 * The symbol D is used here in the same context as in section 3.3, yet the quantity it represents is different from that in section 3.3. q 93 Chapter 3: Data Packet Transmission However, it is true that because of voice fluctuation, the condition n > M is satisfied easily when M < MQ. The justification of the approximation of (3-53) by (3-54) is due to the fact that S < (R + K). For S « (R + K), such an f f approximation may cause significant error. Using the notation g = n /M , e E and note M ^> 1, (3-54) is well approxi- 0 0 mated as D = (e — 1)(R + K) (3-55) 9e q Some Observations 1) From (3-46), the normalized maximum throughput is little affected by voice fluctuations. 2) From (3-47), the normalized throughput is little affected by voice fluctuations, but the variance of that increases as the result of voice fluctuations. 3) From (3-54), very similar conclusion as in item 2 above is reached for delay D, q provided that S <C (R + K). f 6) T h e T o t a l D e l a y D x T The total delay of ALOHA-II, Df, consists of the backlogged delay D , as disq cussed above, plus a header delay D and propagation delay R, i.e. n D T = D + D + R q h Chapter 3: Data Packet Transmission 94 where the header delay D^ is the time difference between a packet arrival and its first transmission activity, which can be either a transmission trial or a delayed transmission. L \ can be further decomposed into D h = D + D 1 2 where D\ is the delay from the time of arrival of a packet to the beginning of the next frame, which equals to Sf /2 on the average; D is the time between the 2 beginning of the frame and the actual transmission of the packet, which equals to Sf/2 on the average for VAP-I. For VAP-II it is given by D 2 = is/(l + p ) v as illustrated in Figure 3-14. Since Sf is one twelfth of R, the contribution of Dh to total delay DT is insignificant. Figure 3-14 Illustration of D for VAP-II 2 Chapter 3: Data Packet Transmission fO CN (N CN 95 *~ O S|0|2 Ul X0|8Q ja^OD,-! U D 8 ^ § 96 Chapter 8: Data Packet Transmission Figure 3-15(a) andfigure3-15 (b) show simulation results of ALOHA-II, assuming perfect estimation. The effect of voice background is explicitly shown using p as x axis variable. The analytic results for ALOHA-II from (3-55) are the v points on y axis (p =0). Also shown are the curves of ALOHA-I for comparisons. v It can be seen that ALOHA-II does not change with voice pattern background as much as ALOHA-I. Its advantage over ALOHA-I is most clearly seen in the medium and high p , Pd and VAP-II voice pattern background. The values of p v v at the intersections of ALOHA-I and ALOHA-II indicate the boundaries beyond which ALOHA-II is preferred, and vice versa. 3.5.2 Effect of Estimation Error Let n be the estimated value and n be the real value of backlogged number at r the beginning of an arbitrary frame. The estimation error A n is An = n — n T The delay factor p (3-34) now becomes From (3-39), expected number of success, m, becomes, n + An < M (3-56) n + An > M 97 Chapter 3: Data Packet Transmission Let 6(n) be the relative estimation error, i.e, 6(n) = then the case n + A n > M in (3-56) becomes -171-1 l + 6(n) I 1 ,n + A n > M n[l + 6{n)] (3-57) Let / = n[l + 6(n)], then (3-57) becomes m = 1 ,n + A n > M 1 + 6{n) (3-58) Figure 3-16 illustrates (3-56) for M = 5, 6(n) = ±0.3, ±0.5 and ±0.7. The asymptotic value of m, when n —• oo, is lim fn = n-»oo ^7-^-e +^T -T 1 + (3-59) ^^n) where 5(n) = ±0.3, ±0.5 and ±0.7. Maximum value of (3-59) is obtained at 6(n) = 0.0 and is e . _1 In general, however, 6(n) is a random variable. Given n, its probability distribution function is defined as p(e|n) = P {6(n) = e\n} r (3-60) assuming that the probability distribution exists. Finding function p(e|n) is difficult. A few approximations can be used. For instance, one can assume, if 6(n) is not too large, that 6(n) is uniformly distributed between (61,62), on n. — 1 < <5i < 62, where both 6\ and 62 may be dependent Chapter 3: Data Packet Transmission Figure 3-16 Output Rate S out and Estimation Error b~(n) 99 Chapter 3: Data Packet Transmission On the other hand, (3-59) gives a general picture of how the performance can be affected by estimation error 8(n). In particular, it can be seen from figure 3-16 that a positive estimation error, which corresponds to a positively biased estimator, does not shrink the boundary of the globally stable region I (figure 3-13) as much as a negative error, which corresponds to a negatively biased estimator. (3-59) becomes 0 if 6(n) = —1, which corresponds to the case where no control mechanism is used. Simulation results of estimation error are shown infigures3-17 and 3-18.* The estimator error 6(n) is assumed to be uniformly distributed in [a, b] and independent of n, where a and 6 are given as the first and the second number in thefigurelegends. Figure 3-l7(a) shows mean backlogged delay D in frames; For q various estimation errors, the differences are small. It is noticed that unbiased estimator of error range [-0.3,0.3] (curve marked 'o') gives almost the same results as an underbiased estimator of halved error range [-0.3,0.0] (curves marked ' A ' ) , and an overbiased estimator of halved error range [0.0, 0.3] (curves marked V ) . The curves marked '©' correspond to ALOHA delay-throughput curve for pure data environment (p = 0). v Figure 3-17(b) gives some insight of how the control mechanism works, where E is the expected number of delayed transmissions, and E the expected x 2 number of collisions. They are defined as Ei = n/k- 1, E 2 = k/fn - 1 respectively. From figure 3-17(b), it is seen that E 2 is close to that of pure ALOHA curve(®) due to the control mechanism, while Ei increases as p and d * In these simulations, the average voice length yT 1 is 500 frames. 15-| 0.0 0.1 0.2 0.3 Pd Figure 3-17 (a) Backlog Delay D and pd, for n~ l q = 500 102 Chapter 3: Data Packet Transmission p increase. The pattern that E\ changes with p is very similar to the excess v d queue size in the reservation protocol discussed in section 3.3, in that both of them remain near zero when p is below a certain value, and abruptly increases d after that value (which is about 0.25 in figure 3-17(b)). Figure 3-18(a) and (b) show the same system with p,~ = 50 frames. It is seen that E remains basically x 2 unchanged while E\ has been significantly reduced. In this sense, E\ makes a good analogue to the excess queue size in the reservation protocol (see figure 3-6). The actual probability distribution of 8(n) depends on the estimation algorithm. The above simulations, on the other hand, indicate that ALOHA-II does not require a very accurate estimation of n. This can be explained by the S-G curve: s = ge~ , which is rather flat in the region around g = 1.0. 9 In section 3.2, two examples show the possible implementation of estimators. In the following, an algorithm is proposed which minimizes the effect of propagation delay R. First it is realized that a randomized retransmission for collided packets is unneccessary, since the delayed transmission control mechanism serves perfectly the purpose of controlling new transmissions as well as retransmissions (there is actually no distinction between the two). As a result, any collided packet can start retransmission, according to the protocol description, as soon as the collision is heard after one propagation delay R. The relationship among the backlogged number at the beginning of the (i + l)th frame, n-+i, and that at the t ith. frame, n^; the total new data arrivals during the ith frame, d^; and the total 108 Chapter 8: Data Packet Transmission retransmissions heard during the ith frame, r^, is (a variation of (3-32)) n 1 + i = (n,- - ki) + di + r - (3-61) t (3-61) suggests an algorithm for the estimation of n i by t + 1) Estimation of number of delayed transmissions (n, — ki) t from the previous es frame; 2) Estimation of number of arrivals in the previous frame, di t; >es 3) Estimation of number of retransmissions heard in the previous frame, Both di t >es ri . >est and r - .$ can be estimated using the similar methods as in t e section 3.2. For (rc,- — ki) t, it can be estimated by es (n; - ki) where n tjes est = n,, e3t ( l - p) (3-62) t is the estimate ofra,-at the ith. frame, and •I A ,1 p = min ( M V rarest / It is possible that ni t >es was an erroneous estimate of n -. It can be shown, by t exhaustive numerical values, that (3-62) always converges, i.e, error ( n ( ni i) + t+1 ) es4 — < (ni t — ni), for arbitrary initial value of n,. >es In the next chapter, a combined random/reservation scheme is studied. A L O H A - I I will be assumed throughout the discussions. Chapter 4 Combined Random/Reservation Protocol It has been shown in the previous chapter that, with the control algorithm introduced in section 3.5, ALOHA protocol can be used in an IVD environment, giving performance close to that in the pure data case. Delay of less than 2R can be achieved, with guaranteed stability. However, the maximum throughput of the protocol is still limited to e . On the other hand, although the delay for _1 reservation protocol is larger than 2R, its throughput can be extended to almost 1.0. It is generally true that there does not exit a single multiaccess protocol that performs better than all the others over the entire range of system throughput. Although some characteristics of a system are unlikely to change during the operation, it is certain that the load placed upon the system will be time varying. An adaptive strategy for choosing an access protocol suitable to the varying need is desired, so that optimality is maintained at all times. In order to extract the merits of low delay of the ALOHA protocol and high throughput of reservation protocol, while avoiding the disadvantages of them, many combined random/reservation protocols have been proposed in the pure data environment. In this chapter, a combined random/reservation protocol is proposed and studied under the IVDS environment. 104 Chapter 4- Combined Random/Reservation Protocol 105 4.1 M o d e S w i t c h i n g I n f o r m a t i o n The adaption ability is achieved by exchange of information among the distributed decision makers. The type and amount of information required by an adaptive strategy, as well as the implementation of the information acquisition mechanism, are among the most crucial factors in determining the performance and robustness of the strategy. Local information and global information or a combination of both can be used in order to accomplish adaptivity of protocol switching according to the system status. One example of local information is the length of user queue. If the queue length is smaller than some prespecified threshold, random access protocol is selected. With the increase of channel load, more collisions will occur which increases the length of user queue. Once the queue length is larger than the threshold, access mode is switched to reservation protocol. An important example of global information, which was used repeatedly in the previous chapter, is the total channel traffic factor g(t). If the channel is lightly loaded, g{t) will be small most of the time, which indicates that ALOHA access protocol can be most suitably used. On the other hand, in the heavily loaded condition, g(t) is large most of the time, indicating that reservation protocol is prefered. As global information provides an overview of the system status, it is expected to be a better candidate than local information in achieving the adaptivity Chapter 4' Combined Random/Reservation Protocol 106 of access protocol selections. The disadvantage with global information is that acquisition of global information is much more difficult than that of local information. Since the instantaneous total traffic factor g(t) is used in the control of ALOHA protocol discussed in the last chapter, it is natural to extend its use as the mode switching information as well. 4.2 Reservation Request Transmissions In chapter 2, it was assumed that requests for setup of voice virtual connections were transmitted via a dedicated subchannel. In chapter 3, the same assumption was made on the transmission of reservation requests. For the multiaccess environment where there is only one channel available, the implementation of request transmissions requires that a certain portion of channel capacity be reserved as the subchannel, e.g., a subframe can be reserved for exchange of control information in each frame, as in the WB SATNET system. Due to this requirement, the actual achievable channel utilization for reservation protocol is smaller than what was seen in chapter 3 where a free hypothetical subchannel was available. As the portion of channel capacity reserved for request transmission is kept as small as possible, the maximum rate at which requests can be sent is limited. In the case offixedrequest subchannel assignment, this limitation implies that the maximal number of users a reservation protocol can actually support is also limited. In the case of random request subchannel assignment, the maximum rate of request transmission, with any specified probability of success, is limited by the capacity reserved to the request subchannel. Chapter ^: Combined Random/Reservation Protocol 107 The request subchannel in SENET structure can be implemented by reserving a number of slots in each frame and partition the slots further into the mini-slots, each mini-slot is of the length of a request packet plus the guard times which can no longer be neglected since guard time is comparable with the size of request packets. The mini-slots can be assigned to each individual user dedicatedly if the number of users is not large, or on ALOHA contention basis if the number of users is large, since the minimal size of mini-slots is limited by the guard times and implementation difficulties of synchronizations. (The size of request packet is usually very small). Combined random/reservation protocols provide a natural way of request transmission, i.e., attaching the request packets to the data packets transmitted via random access mode, this method is also called piggybacking. Since no extra guard times and synchronization mechanism are necessary, piggybacking causes very little increase of channel load and implementation costs. Moreover, since no partition of mini-slots is necessary, the access protocol can be much simpler than the case where mini-slots are used. 4.3 T h e C o m b i n e d R a n d o m / R e s e r v a t i o n P r o t o c o l The basic idea is to make use of the instantaneous channel traffic factor g(t) on deciding one of the 2 access modes: random access and reservation access, both have been discussed in chapter 3. The requests of reservation are sent by attaching to the packet currently being transmitted, which can either be a random transmission or a pre-reserved Chapter 4- Combined Random/Reservation Protocol 108 transmission. The protocol is assumed to operate under the simplest and worst user population case, i.e, each user generates one voice traffic and/or data traffic. Data traffic and voice traffic are assumed to be independent of each other even if they are from the same user. In a more general case where data traffic and voice traffic are not independent, it is possible to improve the performance of the proposed protocol by incorporating several known methods, e.g, by making use of voice silence period for data transmissions, or reservation request transmission by attaching to the voice packet in virtual connections, if there is one. On the other hand, the voice setup request transmissions can also be sent via data packets in transmission. Some of these topics will be discussed in Chapter 5. Since voice traffic and data traffic are assumed to be independent of each other, the setup transmission of voice virtual connection is via random access mode. It will be shown later in section 4.3.3 that required blocking probability can be easily satisfied. 4.3.1 Protocol Description The protocol is described as follows: first, the data access part; then the voice access part; and finally the interactions between them. Chapter 4: Combined Random/Reservation Protocol 109 T h e d a t a access p r o t o c o l (figure 4-1) Each user keeps a record of its present transmissions. The record includes: i) the number of total packets in the buffer of the user, Nt; ii) the number of packets being transmitted via random access mode yet the acknowledgement has to wait to come, N ; iii) the number of packets on the process of reservation (i.e., a request has been sent for them yet reservation grant has not been received) plus the number of packets for which reservation has been granted, N . r The number of packets which are neither being sent via random access nor on the process of reservation, iV , is thus w N w = N -N t a N r 1. Upon any new arrival, the user checks the total channel traffic factor g = g(t) against a prespecified threshold, denoted as G h (node 1). If g < Gth, t transmit the packet via ALOHA mode, thus N is incremented by 1 (node a 4) ; if g > Gth, put the new packet in the buffer (add 1 to N ), then go to w the next step (node 2). 2. (node 2) If there is any packet scheduled to be sent via ALOHA mode (the schedule is due to retransmissions), wait until the transmission of the packet (node 6), then attach a piggybacking request to that packet (node 5) . The request consists of two pieces of information: the identity of the user (station) and the number of packets awaiting for reservation, i.e., N . w 3. If there is no transmission scheduled via ALOHA, check if there is any Chapter 4- Combined Random/Reservation Protocol A d d 1 to N , Wol1 In t h e user buffer Attach the re q u e s t f o r the N , p o c k e t s 110 A d d t to N . W a l t In t h e user buffer Attach the request for the N„ p a c k e t s Figure 4-1 D a t a Access Protocol Flowchart 111 Chapter 4- Combined Random/Reservation Protocol packet being reserved (node 3); if yes, wait (node 14) until the transmissions of these reserved packets and attach the request piggybacked to the reserved packets (node 11). 4. If there is neither transmission scheduled via random access nor granted reservation, i.e., if N = N = 0, then schedule a transmission via ALOHA a r at the time (back to node 4). The node 4, "ALOHA transmission", means that transmissions follow the ALOHA protocol described in the last chapter. Similarly, node 10, "reservation transmission", means that transmissions execute the reservation protocol described in the last chapter. 5. Whenever a transmission is successful either via ALOHA or reservation (node 7), add the number of packets requesting for reservation, N , to w iV (node 9). All the N packets wait in global queue until their schedr r uled transmissions (node 9). If upon successful transmission, no request is attached, i.e., N = 0 (node 8), then the cycle is completed (STOP). w Voice Access P r o t o c o l 1. Whenever a new call arrives, send a request via ALOHA mode. 2. If the transmission of the request is successful, the voice request is entered in a global voice request queue. The voice global queue is given higher priority to the data reservation queue and is served by assigning an empty Chapter 4- Combined Random/Reservation Protocol US slot and a virtual connection in that slot to the requested call. If no empty slot is found, the call is rejected. 3. If the request transmission is collided, add 1 to the total number of trials of request transmission N i. If N i greater than a prespecified threshold Ntr, t t the call is rejected; otherwise, schedule a retransmission as in the ALOHA access protocol. Interactions: As is seen in the last chapter, ALOHA transmissions can be blocked by voice connections. Similarly, it can be blocked by reservation transmissions while reservation and ALOHA are in the same system. In order to avoid the blocking condition, a maximal number of voice connections plus reservations accommodated in each frame, St , is specified, where S h < Sf. At the beginning of each n t frame, the following information are available to each user: i) the entries of the voice request queue, and the number in queue, N '; ii) the entries of the global v data reservation queue and the number in queue, iV '; iii) the total number of r unoccupied slots, Sf — N , where N is the number of voice occupied slots before v v updating. According to these information, the following actions will be taken: 1. An empty slot is assigned to a voice request if there is any while keeping the total number of voice connections N (which is incremented by 1 every v time a slot is assigned to a new call) in that frame no larger than S^. Mark the correspondent slot as state 1. US Chapter 4' Combined Random/Reservation Protocol If N v = S , the remaining voice requests in the voice global queue are tn rejected. 2. After all voice requests having been accommodated, transmit the reservations in the global queue while keeping the total number of slots being occupied by voice, N , plus the number of slots just being used by reserv vation transmissions, i V , no larger than S , i.e., N + 7V * < Sth- If the f tn r v r sum exceeds S , the rest of the reservations are delayed to the beginning tn of the next frame. In the case where N = Sth, v a u the reservations are delayed to the beginning of the next frame. 3. Finally, for each user attempting ALOHA transmissions, choose randomly and uniformly 1 slot among SSN remaining slots, where SSN = Sf — (N v + N^). Because (7V„ + 7V ') < S , SSN > S - S r th f th > 0. It is necessary to mention that the introduction of quantities N , i V v f r and Sth does not imply the partitioning of slot regions among voice occupied slots, reservation slots and slots for ALOHA, for any slot can be occupied by voice, reservation or used for ALOHA transmission. However, a record is kept for the number of each type of slots used, and the following relationship among them is maintained, N v + 7Y f r < S, tk Sth < S , f SSN = Sf (N v + N *) r In the remaining of the thesis, the abbreviation CP will stand for the Chapter 4- Combined Random/Reservation Protocol 114 "combined protocol". 4.3.2 S y s t e m P a r a m e t e r s for C P The following list basic system parameters and their effects to the combined protocol(CP). 1. Voice utilization and voice pattern distribution. Since both the ALOHA protocol and the reservation protocol are insensitive to the voice utilization and voice pattern distribution, the performance of CP is expected to be insensitive to the 2 system parameters. For discussions following, these 2 system parameters will be chosen to represent typical situations, e.g, p can be either 0.0 representing no voice case or v 0.5 representing voice case. 2. Sfh. It can influence" the performance of CP, especially for high voice utilization and data utilization range. It does not have significant effect for voice utilization and data utilization of low and medium range. An intuitive choice of 5^ is made by reserving at least 5% of the total capacity or at least 1 slot to the data transmissions, whichever is smaller, i.e, Sth — Sf 3- G . th — max (1,0.05(1-p..) 57) Since it determines the switching point between ALOHA mode 115 Chapter 4- Combined Random/Reservation Protocol and reservation mode, it is an important parameter in CP. The range of Gth c a n be estimated as follows: since g larger than 1 is not desired for ALOHA protocol, it should be between 0.0 and 1.0. The effect of G h to t CP will be shown in the simulations in the next section. 4. Sf and number of users in the system, N . u For low throughput range, the system operates basically in ALOHA mode, thus Sf and N u will have no significant effect on the performance of CP. For throughput greater than e , there is a value for the number of users, _1 N , um below which the delay of data packets is minimum. A certain relationship exits between N um and Sf, as will be discussed in the next section. 5. The maximal number of trials for voice setup request transmissions, Nt . r Ntr • R is the maximum waiting time a caller would incur before he knows whether his call will be connected or blocked, it is discussed in the next section. 4.3.3 Asymptotic Analysis of C P Due to the introduction of mode switching parameter Gth, a detailed and ac- curate analysis for CP is difficult, especially at the throughput range around e , where the system is frequently switching between the ALOHA mode and _1 reservation mode. For throughput much less than e , however, the system op_1 erates basically in ALOHA mode; while for throughput much higher than e , _1 the system operates most of the time in reservation mode. As both ALOHA Chapter 4: Combined Random/Reservation Protocol 116 and reservation modes have been studied in the previous chapter, an asymptotic analysis for CP, which gives a good indication of the performance of CP, can be readily obtained. 1) Q « Gi th For low throughput range where g < G h is always satisfied, the protocol operates t in the loop > • 7 (successful transmission) 0 — • 1 —> A — • 5 — • 12 — • 13 in figure 4-1, which is the ALOHA mode; thus for very low throughput range, the performance of CP is very close to that of ALOHA. 2) g > G '. th For high throughput range where g > G h is always satisfied, CP can be in t Chapter 4 : 117 Combined Random/Reservation Protocol i) the loop I >STOP 0 — • 1 —> 2 — • 3 —> 14 — • 11 — • 7 —> 8 —> 9 — • 10 which is the desired piggybacking reservation mode; or ii) the loop > 7 (enter reservation mode) 0 — • 1 — • 2 — • 3 —> 4 —> 5 —> 12 — ^ 13 which is the random transmission and reservation mode; or iii) the entire loop of figure 4-1 except the ALOHA mode for g < Gth, determined by the total number of users 7V in the system. There exits a value U for the number of users, N , below which the system will operate (most of the um time) in loop i; As N increases, the probability that the system enters loop ii u increases, for throughput greater than e . An extreme case is that the number _1 118 Chapter 4- Combined Random/Reservation Protocol of users in the system is infinite. For finite aggregative total channel throughput, the throughput for any individual user (assuming load is offered evenly from all the users) is infinitesimally small. That in turn means that no user can have more than one packet at any time, thus no packet can be transmitted via reservation. As all packets are transmitted via ALOHA and total channel load is greater than e , the chance of successful transmissions is approaching zero and _1 delay approaching infinite, this is the second loop indicated above (for infinite population models). In the throughput range greater than e , it is desired that _1 most of the packets should be transmitted via reservation mode; i.e, the first loop indicated above. The following derives the asymptotic value of N UM under symmetric load assumption,* i.e., the aggregative load to the system, denoted as D, is generated evenly from among all users. If the individual data arrival rate is d, the total number of the users in the system is N , then U b =d • N U In order to keep the system in the first loop, there should be at least one packet arriving during the period in which the previous packets are in the process of reservations (figure 4-2), i.e., K ' = II1 where the unit of R is Sf. R-SAI-*)- 1 (4_1) The left hand side equation in (4-1) represents the average number of arrivals during time R for each user evenly; d > 1 represents the continuous reservation condition, the right hand side equation assumes that * This assumption is realistic for a large number of small users. 119 Chapter 4'- Combined Random/Reservation Protocol the normalized maximum data throughput is 1.0. Re-arrange (4-1), R • S • (1 - ) f Pv b or equivalent ly, N um < R • S • (1 - p ) f (4-2) v (4-2) gives an upper estimate of N . um Previous Reservation in Process Previous reservation transmitted '-with the request for the r e s e r v a t i o n of t h e n e w a r r i v a l a t t a c h e d Figure 4-2 Illustration of Continuous Reservation A lower estimate of N um is obtained as follows. If the normalized maximum data throughput is no greater than e , then the system will operate in the third _1 loop and will always (even if the continuous reservation condition, i.e., d > 1, is not satisfied) be able to enter the first loop, thus — N u = d < 1, ^ ^> e ~ ' R • S • (1 - ) ~ f Pv - 1 1 (4-3) ' Chapter 4- Combined Random/Reservation Protocol 120 the right hand side equation reverses the condition that the data throughput is no greater than e , in order to obtain N . _1 um N Simplifying (4-3) gives, > e- • R • S • (1 - ) (4-4) 1 um f Pv Combining (4-2) and (4-4) gives, e- • R • S • (1 - p„) <N <R-S {l-p ) (4-5) 1 f um r v Average delay for system operating in the first loop is that of reservation protocol discussed in the previous chapter, plus R/2, as illustrated in figure 4-2. The effect of Sf on CP is also seen from (4-2) and (4-4). Sf has no significant effect on low throughput range where ALOHA mode dominates. It influences the system on high throughput range as (4-2) and (4-4) indicate, i.e., Sf is proportional to N . um Moreover, (4-2) and (4-4) suggest that N um is proportional to (1 - p ). v 3) T r i a l n u m b e r s f o r voice request t r a n s m i s s i o n s : If trials are assumed to be independent with probability of success p , then the s distribution of trial numbers Ix is given by Pr[l = l] = P,{l-p,)'- 1 T (4-6) As voice arrival rate is much smaller than data arrival rate, the contribution of voice request transmissions to the total traffic of random access is actually Chapter 4- Combined Random/Reservation Protocol 121 negligible. Moreover, since voice request transmissions follow the same ALOHA protocol as data packets do, probability p is the same as that for data packets s transmitted via ALOHA. For g < e , it is given in section 3.5. For g > e , an _1 _1 accurate calculation for p is difficult; as an estimation, it can be noticed that if s N < Num, the average delay of data packets is about 2.5 times of propagation u delay R. Thus, p can be estimated by s p = 1/2.5 = 0.4 s For such p , calculation of (4-6) suggests that no more than 2% of trials exceed s 10 times, and virtually no trial numbers is larger than 20 (20 X R = 5.4 seconds), which should be acceptable for most applications. 4.4 Simulations for C P Simulations were carried out to obtain the delay-throughput performance curves with different values of G h as parameters* The relationship among p , Sf and t N v as indicated in (4-5) was verified. The simulated trial number distribution um P [/r] was also obtained. r 1 ) Effect of Gth Figure 4-3(a) shows delay versus throughput curves for p — 0.5, Sf = 100, v N = 100, G h = {0.0,0.15,0.35,0.75,1.0}. As can be seen, G h determines the u t t point at which the system switches from ALOHA mode to reservation mode. * The estimation of g is assumed to be perfect. Chapter 4' Combined Random/Reservation Protocol 122 For Gth > 0.35, change on Gth actually has no effect on low pd range (0.0 < p < 0.32, i.e, ALOHA throughput range). On the other hand, the delay d in the 0.32 < p < 1.0 range increases with the increase of Gthd For 0.0 < Gth < 0.35, the major change of delay is in low pd range. In G h — 0.0 case, the curve departs from that of ALOHA right at p& = 0.0; in t G h = 0.15 case, departure occurs at p& « 0.15. These curves have larger delay t than that of ALOHA. However, for Gth — 0.35, the curve departs from that of ALOHA at p « 0.32 and the delay is smaller than that of ALOHA, indicating d that for pd > 0.32, reservation mode should be partially used instead of pure ALOHA mode. The desirable range of G h can also be seen from the figure, i.e., t the optimal value of G h is about 0.35. t Figure 4-3(b) shows delay versus throughput curves for p = 0.0, Sf = 100, v N u = 200, Gth = {0.0,0.3,0.7,1.5}. Similar observations can be made on G h, t except that the desirable value of G h has been doubled to around 0.7. Also t noticed is the similarity between figures 4-3(a) and 4-3(b): curves of p = 0.5 v (figure 4-3(a)) correspond to curves of p = 0.0 (figure 4-3(b)) with G h doubled. v t This similarity can be explained by the fact that as p changes from 0.5 to 0.0, v the total channel capacity available to data users doubles. If the total channel traffic factor g were normalized to (1 — p ), G h would have the same values for v t p = 0.5 and p = 0.0. The similarity between performance with and without v v voice presence indicates that CP is not susceptible to voice background. The system parameters Sf, N and p for figures 4-3(a) and 4-3(b) are chosen such u v that the ratio N u Sf(l - Pv) is identical. The relationship among Sf,N and p is investigated further in the u v 123 Chapter 4- Combined Random/Reservation Protocol following section. 2) T h e relationship among Sf, JV and p U v The relationship among Sf, N and p is given in (4-5). In this section, simulation u v results are shown to verify (4-5). Figure 4-4(a) shows delay versus throughput for p = 0.5, Sf = 100, Gth — v 0.25, N u = {100,200,300,400,500}. It is seen that low throughput range of Pd (0.0 < Pd < 0.36) is little affected by N , since ALOHA performance is not u affected by N . For pd > l/e, delay increases with the increase of N . However, u u there are significant differences among curves for N < 200 and for N > 200, u this indicates that N N um u of the system is between 200 and 300, a calculation of according to (4-5) gives um 220 < N um < 600 thus the simulation results lie between the upper estimate and the lower estimate of N um by (4-5). For N below N , the change of N does not change the delay versus u um u throughput performance significantly, e.g, curve for N u — 100 is very close to that for N = 200. u Similar results can be seen for p = 0.0 case from the delay versus throughv put curves shown in figure 4-4(b). The simulation shows that N um is greater Chapter 4- Combined Random/Reservation Protocol Figure 4 - 3 CP Delay-Throughput Characteristics Chapter 4'- Combined Random/Reservation Protocol 125 5400 5400 1200 | I , , , | . 0 0.1 , I . | , 0.2 M , | I I 0.3 I I|II I| ,II| I 0.4 I 0.5 I 0.6 . I I,I.I. 0.7 | I . 0.8 . ! . 0.9 . . . 1 Pd (b) Figure 4-4 CP Performance and User Number N . u Chapter 4- Combined Random/Reservation Protocol 126 than 400 and (much) below 800. According to (4-5), 440 < N um < 1200 Also noticed is the similarity between the curve for N u = 400(800), p = v 0.0, shown in figure 4 4(b), and the curve for N = 200(400), p = 0.5, shown in u T v figure 4-4(a). The ratio N /(l — p ) is the same for both of them. v u For N u greater than N , um delay increases rapidly with the increase of p . d For pj, = 0.75, figure 4-5(a) and figure 4-5(b) normalized delay versus N for u p = 0.0 and 0.5, respectively. Effect of N can be seen more clearly from these v u figures. Calculated N according to (4-5) for each curve is also shown as a um comparison. Again the similarity for curves with the same N /(1 — p ) ratio, i.e, the v u curves S = (100)200, p = 0.5 (infigure4-5(a)) and S = 200(400), p = 0.0 f v f v (in figure 4-5(b)) can be seen. 3 ) Trial number distribution Figure 4-6(a) shows trial number distributions (simulated) for p — 0.0, p = v d {0.1,0.3,0.5,0.75}. As p increases, the trial number increases. The maximal d number of trials shown for pg = 0.75 is 6 with frequency 10 . -5 Figure 4-6(b) shows trial number distribution for p = 0.5, The maximal v number of trials shown for p = 0.75 is 8 with frequency of 10 . These results -5 d Chapter \: Combined Random/Reservation Protocol Figure 4-5 Relationship among N , um 127 Sf and N u Figure 4-6 Trial Number Distribution 129 Chapter 4- Combined Random/Reservation Protocol suggest that for practical time requirement of voice connections, random access protocol for setup request transmission is satisfactory. 4.5 Comparison of C P with A L O H A and Reservation 1. For low throughput range 0 < p < e , with proper choice of G h, CP gives -1 d t the same delay versus throughput performance as ALOHA. 2. In throughput range p > e , for proper choice of Gth ^ an _1 d ing N , um N not exceedu delay of CP is 0.5 x R larger than that of the reservation protocol in which a freely available subchannel for request transmission is assumed. However, actual implementable reservation protocols have larger delay and smaller utilization than such a hypothetical reservation protocol. The maximal number of users supported by an implementable reservation protocol is also limited. The comparisons between reservation protocols using subchannels for request transmission and CP can be made in terms of overhead delay, maximal number of users supported by the system (for delay not exceeding certain specified value), and complexity of implementation. As an example, if a minislotted reservation protocol is to operate under SENET structure for p = 0.5, Sf = 100, N = 200 v u and maximum p no less than 0.85, at most 10% of average remaining capacity d can be used for subchannel request transmissions, i.e., 0.1 x 0.5 x 100 = 5 slots, or 1.1 ms in real time units; if minislots are to be assigned to each user dedicatedly, 200 minislots have to be used, the resulting length of each minislot will be less than l.lms/200 = 5.5/zs, including guard times. On the other hand, if minislots are assigned on a contention basis, the average delay for request transmissions may as well be larger than 1.5 times of R due to collisions, especially in high Chapter 4-' Combined Random/Reservation Protocol ISO Pd range. Thus the delay and the throughput of CP is comparable to those of minislotted reservation protocols. The advantage of CP in terms of complexity of implementation over subchannel oriented reservation protocols is obvious, since no additional partitions of channel time is necessary in CP. Chapter 5 Conclusions and Further Studies The major conclusions are summarized as follows: 1. The state correlation function, defined in (2-17), is heavily influenced by voice assignment protocols. Two voice assignment protocols, i.e., random assignment(VAP-I) and left to right assignment(VAP-II) are studied. The independence assumption(p.26) produces good approximations for performance analysis of ALOHA and reservation protocols studied in chapter 3, under the voice background generated by VAP-I. 2. The performance of both ALOHA and reservation protocols deteriorates in the IVD environment, due to the channel capacity fluctuations caused by voice connections. However, the deterioration of the former is much more severe than the latter. Under IVD environment, it is indicated, by simulation results in section 3.4 and analysis in section 3.5, that an adaptive control mechanism is indispensable for ALOHA type protocols. If they are to be used in an such environment, more coordinations are needed in the protocol definitions. 3. Based on the above observation, ALOHA-II is proposed and studied. Under the assumption that estimation of backlog number is perfect, the protocol sig131 Chapter 5: Conclusions and Further Studies 182 nificantly reduces the effect of voice background fluctuation; as a consequence, the protocol stability is guaranteed for throughput under e . Furthermore, _1 if the estimation error is given, the upper boundary of the stable region can be estimated by (3-59). An estimation algorithm, which is aimed at reducing the effect of propagation delay R, is proposed in section 3.5. 4. A natural extension of the results from chapter 3 is the combined protocol in chapter 4. Asymptotic analysis gives a good estimation of the user number, under which minimum delay can be achieved when throughput is larger than The future work can be conducted in the following areas: 1. The performance evaluation of ALOHA-I protocol under VAP-II type voice background needs further studies. 2. The properties of the algorithm for estimating the number of backlog users, proposed in section 3.5, are worth further studies. 3. For a complete performance evaluation of ALOHA-II and the combined protocol, the 2-dimensional probability function in (3-50) needs to be derived. 4. Voice packet multiplexing and/or data packet transmission, by taking advantage of voice silence period, can provide potentially more than 30% increase in channel utilization, due to the fact that up to 50% of a voice connection is silence period. Furthermore, voice multiplexing by taking advantage of silence period reduces frame-to-frame correlations, since the durations of talkspurts Chapter 5: Conclusions and Further Studies ISS and silence periods are much shorter than that of voice connections. It is known that [4,18,19] data performance improves as the voice frame-to-frame correlation weakens. In satellite systems, a hybrid voice multiplexing and random access protocol, which is particularly suitable for small users, has been reported in [23]. This is an important topic of further studies. 5. Onboard processing and multibeam satellites are the future trends of satellite systems [24-26]. They are essential for supporting users with small earth station antennas, such as mobile users. IVD protocols under such environments require further studies. Appendix In this appendix, the 1-dimensional and 2-dimensional distributions given in (335) and (3-9) are derived* Since the transmission of n packets in M slots can be equivalent to placing n balls randomly in M boxes, such model and terms are used. The expectation of 1-dimensional distribution given in (3-37) is also derived. 1. The basic formula Consider the model of placing n ordered balls randomly in M boxes. The total number of ways to do so is given by M . n patternsf with no 1-ball boxes:): Let Let n\ denote the number of all the denotes the number of the patterns that have at least k 1-ball boxes, for example, N is the number of patterns that has x at least one 1-ball box. Then n\ is given by m = M - N n x The 1-dimensional distribution is also given in [15]. A more general approach is used in this appendix to derive 2-dimensional (and in principle multi-dimensional) distributions as well as 1-dimensional distributions. f A pattern has one to one correspondence to a way of placing n balls in M boxes. X A y-ball box is a box containing j balls. 134 Appendix Ni is unknown, but it is easy to see that one way of getting at least one 1-ball box is to choose one ball from the n ordered balls randomly and place it in the M boxes randomly; there are* ( > • ways to do so. In each of them, the remaining m — 1 boxes and n — 1 balls have (M — l ) n _ 1 patterns. But the product {^jA \M-l) - >Ni n l n since in ( M — l) the ways of getting at least two 1-ball boxes are included. n Thus Ni= ^V(M-1) - -/V W 1 2 But N is also unknown, the number 2 ^A (M-2) 2 n n - 2 >N 2 and should be subtracted by N3,..., etc, thus », = M * - { ( ^ ) A „ ' ( M - ! ) » - ' - {(^JA.\M - { ( * ) A . ' ( * - S ) - - ±N }}} - L the last number iVx, is N= L * The function An* is defined as (™)A (M-±L) L n - 2 ) - n L 8 136 Appendix where L = min(M, n). NL does not contain NL+I, since Nj = 0,Vi > L. Thus m =M - (^) V ( M - I)"" + ( ^ ) V ( M - 2) ~ n 1 - (f) A (M 3 n n - 3)»"» + • • • ± (^) A (M L n 2 - L) ~ n L ( A 1 ) =I:(-)(^)v(^-^)-* l fc ,l (Al) can also be written as L n = ^ ( - 1 ) * G ( M , n, k)B(M, n, k) x (A2) fc=0 where G(M,n,k) B(M,n,fc) Name G(M,n,k) = (^W ={M-k) n—k the weighting function and B(M, n, k) the sample func- tion. The above results does not depend on particular forms of G(M, n,k) and B(M,n,k), thus (A2) is applicable to many similar problems. For example, if the order of the n balls does not matter, then G(M,n,k) , , 1S7 Appendix and corresponding n\ is * L k=0 In order to obtain ny, G(M, n, k) and B(M, n,k) are modified as 'M\ B(M,n,k) A kj n =(M-k) n kj and L >- *=o ' wo where L = min(M, n/j). A n important special case is j = 0, M "o = £ ( - l ) * ( ^ ) ( M - f c ) fc=o ^ n (A5) ' 2. The one-dimensional distribution Choose * balls and place in i boxes, there are different ways of doing so. In each case, in the remaining M — i boxes and n — i balls, the total number of patterns that do not contain 1-ball box, ni, is given in (Al) with M being substituted by Af - «' and n by n — i; thus the total number * This expression is not used in the thesis. 138 Appendix of patterns containing exactly i 1-ball boxes, denoted by ci(i), is «.(.•) - (^WB-l)'(TV(m-fc)'-' ^ ' Jfe=0 ^ (A6) ' where m = M — i, I = n — i, L = min(m,I). In general, cy(i), the number of exactly i ./-ball boxes, is given by where m = M — t, I = n — ij, L = min(m,//y). If all the possible patterns are equally likely, the probability of exactly i j-ball boxes, pi(i), is given by (A6) divided by M , i.e., n (3-35) is obtained after algebraic simplification of (A8). 3. T h e t w o - d i m e n s i o n a l d i s t r i b u t i o n Denote c(*o,t'i) the number of patterns each has io empty boxes and i\ 1-ball boxes. Then c(»o,«i) = c(io)c{h\io) where c(i ) = (¥). To find c(ii\i ), it is sufficient to apply (A2) with M substi0 Q 1S9 Appendix tuted by M — io, and G(M-i ,n,k)=( ~ )A M 0 l0 k n B(M - i , n, k) =c (0) = n 0 0 0 where no is given in (A5) with M substituted by M — io, which means the sample function in the remaining M — io boxes should not contain patterns with empty boxes. It follows that C(I'O)H) = c(i0)c(ii\io) \*o/\ »i / (A9) EH) (T)vE(-i)'( ;*)(m-*-iT-* 4 m where m = M — io — i\, I = n — i\, L = min(m, /). (3-9) is obtained by combining (A9) with Poisson distribution and simplification. 4. The expectation of (A8) Let the expectation be min(M,»i) By (A6) and (A8), M!n! ^ ^ M n , i[M - (,• + - '' »!j![JWf — (» + L — (» + Appendix Let k = i + j, then ti—A; = M!n! f f * It is easy to show that Substituting ( A l l ) into (A10), one obtains (3-37). (M-fc)- - References [1] T. Bially, A. McLaughlin, and C. Weinstein, "Voice communication in integrated digital voice and data networks", IEEE Trans. Commun., Vol.COM- 28, pp. 1478-1490, Sept. 1980. [2] I. Gitman and H. Frank, "Economic analysis of integrated voice and data networks: A case study", Proc. IEEE, Vol. 66, pp.1549-1570, Nov. 1978. [3] D. Johnson and C. Weinstein, "A user interface using recognition of LPC speech transmitted over the ARPANET", EASCON Rec, Sept. 1977. [4] C. Weinstein and J. Forgie, "Experience with Speech Communication in Packet Networks", IEEE Journal on selected areas in commun., Vol.SAC-1, No.6, pp.963-980, Dec. 1983. [5] G. Coviello, O. Lake, and G. Redinbo, "System Design Implications of Packetized Voice", Proc. Int. Conf. Commun., Chicago, IL., pp.38.3-4 to 38.3-53, June 1977. [6] G. Falk, J. Groff, W. Milliken, M. Nodine, S. Blumenthal, W. Edmond, "Integration of Voice and Data in the Wideband Packet Satellite Network", IEEE 141 References Journal on Selected Areas in Commun., Vol.SAC-1, No.6, pp.1076-1083, Dec. 1983. [7] G. Coviello and P. Vena, "Integration of Circuit/Packet Switching by SENET (Slotted Envelope Network) Concept", Proc. Nat. Telecommun. Conf., pp.42.12-42.17, Dec. 1975. [8] C. Weinstein and H. Heggestad, "Multiplexing of Packet Speech on an Experimental Wideband Satellite Network", Proc. AIAA 9th Commun. Satellite Syst. Conf., San Diego, CA., March 1982. [9] H. Heggestad and C. Weinstein, "Experiments in Voice and Data Communications on a Wideband Satellite/Terrestrial Internetwork System", Conf. Rec. Int. Conf. Commun., Boston, MA., June 1983. [10] J. Forgie, "Network Speech Implications of Packetized Speech", Annu. Rep. Defense Commun. Agency, MIT Lincoln Lab., Lexington, MA., DTIC ADA45455, Sept. 30, 1976. [11] A. Rustako, G. Vannucci, C. Woodworth, "An Experimental Scanning Spot Beam Satellite System Implementing 600 Mbps TDMA", Bell Lab. report., 1982. [12] R. Syski, Introduction to Congestion Theory in Telephone Systems, North Holland, Amsterdam, 1986. References [13] F. Tobagi, "Multiaccess Protocols in Packet Communication Systems", IEEE Trans. Commun., Vol.COM-28, No.4, April 1980. [14] J. Kurose, M. Schwartz, and Y. Yemini, "Multiaccess Protocols and TimeConstrained Communication", Computing Surveys, Vol.16, No.1, pp.43-70, March 1984. [15] W. Feller, An Introduction to Probability Theory and Its Applications, pp.112, Vol.1, John Wiley &: Sons, Inc., 1968. [16] N. Abramson, "The ALOHA System - Another Alternative for Computer Communications", 1970 Fall Joint Comput. Conf., AFIPS Conf. Proc, Vol.37, Montvale, NJ, AFIPS Press, 1970, pp.281-285. [17] L. Kleinrock and S. Lam, "Packet Switching in a Multiaccess Broadcast Channel: Performance Evaluation", IEEE Trans. Commun., Vol.COM-23, No.4, pp.410-423, April 1975. [18] K. Sriram, P. Varshney, J. Shanthikumar, "Discrete-Time Analysis of Integrated Voice/Data Multiplexers With and Without Speech Activity Detectors", IEEE Journal on Selected Areas in Commun., Vol.SAC-1, No.6, pp.1124-1132, Dec. 1983. [19] S. Li and J. Mark, "Performance of Voice/Data Integration on a T D M tem", IEEE Trans, on Commun., Vol.COM-33, No.12, Dec. 1985. Sys- References 144 [20] A. Leon-Garcia, R. Kwong and G. Williams, "Performance Evaluation Methods for an Integrated Voice/Data Link", IEEE Trans, on Commun., Vol. COM-30, No.8, pp.1848-1857, August 1982. [21] A. Fukuda and S. Tasaka, "The Equilibrium Point Analysis - A Unified Analytic Tool for Packet Broadcast Networks", IEEE Proc, pp.33.4.1-33.4.8, 1983. [22] S. Tasaka, Performance Analysis of Multiple Access Protocols, The MIT Press, Cambridge, MA., 1986. [23] H. Lee and J. Xu, "A Hybrid Scheme of TASI and Random Access for Integrated Voice and Data Transmission over a Satellite Channel", Pacific Rim Conference Record, June 1987. [24] H. Lee, Hybrid Random/Reservation Access Protocols for Communication Satellites, CCNG Report No.E-117, Dept. of EE, Univ. of Waterloo, August 1983. [25] P. Jain, "Onboard Processing in Future Satellite Communication Systems", Journal of Telecommunication Networks, pp.139-151, Computer Science Press, Inc., 1983. [26] A. Frank and T. Stern, "Onboard Demand Scheduling of a SS/TDMA Multibeam Satellite with Integrated Circuit and Packet Switching", Proc. 6th Int. Conf. Digital Satellite Commun., pp.x-27 to x-34, 1983.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Protocols for wide band satellite systems with a large...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Protocols for wide band satellite systems with a large number of small voice and data users Tan, Xu 1987
pdf
Page Metadata
Item Metadata
Title | Protocols for wide band satellite systems with a large number of small voice and data users |
Creator |
Tan, Xu |
Publisher | University of British Columbia |
Date Issued | 1987 |
Description | Multiaccess protocols for integrated voice and data transmissions over satellite channels are studied, based on the SENET(slotted envelope network) structure. The satellite system is characterized as a wide band system with a large number of geographically distributed small voice and data users. Performance evaluations of commonly used protocols, i.e., ALOHA and reservation protocols, are first conducted, both analytically and by simulations. The effect of different voice backgrounds on data access protocols are shown explicitly. Based on these results, a control algorithm is proposed. Analyses and simulations show that ALOHA protocol incorporated with such a control mechanism is globally stable under the integrated environment; moreover, the performance deterioration due to voice backgrounds is dramatically reduced. The actual implementation aspects of the control algorithm are considered. An extension of the above results leads to a combined random/reservation protocol. Simulation and analysis results show that the combined protocol exhibits desired low delay and high throughput performance characteristics, with satisfactory voice blocking probability, under the worst user population assumption, i.e., all the voice sources and data sources are independent of each other — reflecting the nature of small earth station environment. The absence of the need for mini-slot structure lends ease and simplicity to the implementation of the combined protocol. |
Subject |
Computer network protocols Artificial satellites in telecommunication Packet switching (Data transmission) |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-07-21 |
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.0065622 |
URI | http://hdl.handle.net/2429/26745 |
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_1987_A7 T37.pdf [ 6.05MB ]
- Metadata
- JSON: 831-1.0065622.json
- JSON-LD: 831-1.0065622-ld.json
- RDF/XML (Pretty): 831-1.0065622-rdf.xml
- RDF/JSON: 831-1.0065622-rdf.json
- Turtle: 831-1.0065622-turtle.txt
- N-Triples: 831-1.0065622-rdf-ntriples.txt
- Original Record: 831-1.0065622-source.json
- Full Text
- 831-1.0065622-fulltext.txt
- Citation
- 831-1.0065622.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-0065622/manifest