Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Protocols for wide band satellite systems with a large number of small voice and data users Tan, Xu 1987

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


831-UBC_1987_A7 T37.pdf [ 6.05MB ]
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

Full Text

P R O T O C O L S FOR WIDE B A N D SATELLITE SYSTEMS WITH A L A R G E N U M B E R OF S M A L L VOICE A N D DATA USERS by X U T A N B.Sc, Shanghai Jiao Tong University, China, 1982 A THESIS S U B M I T T E D IN PARTIAL F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E OF M A S T E R O F A P P L I E D S C I E N C E in T H E F A C U L T Y OF 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 UNIVERSITY OF BRITISH C O L U M B I A September, 1987 © X u Tan, 1987 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of 'LLBCTRICAL £A/^JMSSR/Ajq-The University of British Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date OCT- / ? * 7 A B S T R A C T 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 sim-ulations 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 im-plementation 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 ex-hibits desired low delay and high throughput performance characteristics, with satisfactory voice blocking probability, under the worst user population assump-tion, 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 CONTENTS ABSTRACT ii T A B L E OF CONTENTS iii LIST OF FIGURES vi LIST OF TABLES ix ACKNOWLEDGEMENTS x 1 Introduction 1 1.1 Basic Structure of Integrated Wide Band Systems 3 1.1.1 The W B SATNET Structure 4 1.1.2 The SENET Structure 5 1.2 Scope of the Thesis 8 2 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 26 2.3.1 Choice of Parameters 26 2.3.2 Results of Simulations 28 3 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 56 3.3.1 Performance Analysis of the Reservation Protocol 59 3.4 Simulations of the Two Protocols 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) 80 3.5.1 Performance Analysis of ALOHA-II Protocol 81 3.5.2 Effect of Estimation Errors 96 4 Combined Random/Reservat ion Protocol 104 4.1 Mode Switching Information 105 4.2 Reservation Request Transmissions 106 4.3 The Combined Random/Reservation Protocol 107 iv 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 5 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) versus Offered Load a' 19 2-3 Tail Probabilities, Psp = 0.005 21 2-4 Illustration of Voice Correlation and Data Transmissions 23 2-5 (a) Correlation */{k) for pv = 0.5, VAP-I 31 2-5 (b) Slot Distribution Pr{l) for pv = 0.5, VAP-I 31 2-6 (a) Correlation */(k) for pv = 0.5, VAP-II , 32 2-6 (b) Slot Distribution Pr(l) for pv = 0.5, VAP-II 32 2-7 (a) Correlation *f(k) for pv = 1/3, VAP-I 33 2-7 (b) Slot Distribution Pr{l) for pv = 1/3, VAP-I 33 2-8 (a) Correlation *i{k) for pv = 2/3, VAP-I 34 2-8 (b) Slot Distribution Pr{l) for pv = 2/3, VAP-I 34 vi 2-9 Correlation *j(k) and Sf 35 2-10 Slot Distribution Pr(l) and Sf 36 2- 11 Tail Probability Py and Sf 37 3- 1 Illustration of Delayed Rule 44 3-2 Bias and Variance of Maximum Likelihood Estimator gm 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 pd 65 3-7 ALOHA Delay-Throughput Characteristics 68 3-8 (a) (b) Effect of Blocking Conditions 72 3-9 ALOHA Delay versus Kmax 7 4 3-10 ALOHA Delay versus Sf 74 3-11 Reservation Delay-Throughput Characteristics 76 3-12 Output Rate Sout versus g 86 3-13 Sin I Sout and EP's 88 3-14 Illustration of D 2 for VAP-II 94 3-15 Comparison of ALOHA-I and -II 95 3-16 Output Rate Sout and Estimation Error 6(n) 98 3-17 (a) Backlog Delay D q and pd, for pTl = 500 100 3-17 (b) Ex and E2 versus pd, for pTl = 500 100 3-18 (a) Backlog Delay D q and pd, for pT1 = 50 101 vii 3 - 1 8 (b) Ei and E2 versus pd, for A * - 1 = 5 0 1 0 1 4 - 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 CP Performance and User Number Nu 1 2 5 4 - 5 Relationship among Num, Sf and Nu 1 2 7 4 - 6 Trial Number Distribution 1 2 8 vii i LIST OF TABLES 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 A C K N O W L E D G E M E N T S 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 pro-posed 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 dif-ferent 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 re-production 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 net-work, integrated packet voice/data protocols have therefore tended to give prece-dence 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 transmis-sions. 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 trans-missions. 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 4 Frame ( i - l ) I | Frame i Frame (i + 1) | 1 2 1 . 2 ms 1 2 1 . 2 ms 2 1 6 bits ; 2 1 . 2 ms Stream Data Control Subf rame Subf ra me Subf rame A \ * ' Moving Boundary Figure 1-1 Basic Structure of WB SATNET 1.1.1 WB SATNET 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 1 6 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 illus-trated 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 SENET 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 TDMA, as illustrated in figure 1-4. Chapter 1: Introduction S| D C 0 C S l * 8 D C • Frame i Frame i + 1 Frame i + 2 s, HS1 HS2 HSS HS1 HS2 BS3 sl*2 as i HS2 BSS HS = Hoat S - Stream Subframe D - Data Subframe C - Control Subframe Figure 1-2 Illustration of Stream Subframe R E S E R V A T I O N DATA t ^ - R e s e r v a t i o n T r a n s m i t t e d by S o u r c e node - M e s s a g e a r r i v e s F r o m s o u r c e h o s t t t Message d e l i v e r e d to D e s t i n a t i o n h o s t L D e s t i n a t i o n n o d e Rece ives m e s s a g e S o u r c e node t r a n s m i t s messa g e 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 nodes - A l l nodes e n t e r 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 R e s e r v a t i o n s r e c e r v e d By a l l s t a t i o n s Figure 1-3 Illustration of Data Transmission Procedures Chapter 1: Introduction 7 Frame i Fra me i +1 Frame i + 2 . Z L £ 1 m i i i n Frame i Cl C2 C3 C4 Dl | 1 D2 D3 D4 D5 Dl Frame i + 1 Cl C2 C3 C4 D2 D3 D4 D5 Dl D2 Frame i+2 Cl C2 C3 C4 D3 D4 D5 D2 D3 C - On going voice ca l l D - Data transmiss ion , assuming 5 data users Figure 1-4 The SENET structure 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 gen-eral, 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 orig-inal SENET structure, data multiple-access protocol TDMA 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 TDMA. 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 simu-lation 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 sim-ulated. 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 sta-ble 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. Chap te r 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 Connec t i on Protoco ls for Vo ice Packets 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 assign-ment 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 per-formance 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 4 A Frame i + 1 Frame i+2 Find an Empty slot New data a r r i v a l Previously occupied slots New v i r t u a l connections Figure 2-1 (a) Voice Assignment Protocol I V i r t u a l connection established Find an Empty slot ln the next frame L New data a r r i v a l Figure 2-1 (b) Voice Assignment Protocol II Chapter 2: Voice Packet Transmission IS 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 packeti-zation 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 packeti-zation 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 Kc and total channel capacity is C , then Sf = [C/Kc\ (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, Kc is from 16kbps (CVSD 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 Ku band with C = value of Sf is thus possible. 500Mbps has been reported in [11]. A much higher Chapter 2: Voice Packet Transmission 15 2.2.1 Statistics of Voice Utilization Define pv[n) to be the first moment of V(n), i.e., p„(n)=E[v'(n)] =Pr{v{n) = l) Assume that V(n) is ergodic and stationary, then, 1 T pv(n) =Pv = Pr {V(n) = l} = lim — £ V{n) (2-2) n = - T If V(n) is a sample of V{n), n = 0,1, • • • , T , then pv can be estimated by (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 — pv. To estimate the steady state value of pv by (2-3), 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 pv; a sequence of 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 av2, is a„ 2 = E V{n) - {pv}2 = Pv{l ~ Pv) (2-4) The steady state value of pv can be derived from the following voice source and system models. Chapter 2: Voice Packet Transmission 16 T h e voice source model Calls are generated from an ensemble of N individual voice sources, where N —> oo, with the following characteristics: 1. The aggregated number of calls, Nc, generated during the time interval T, obeys a Poisson distribution, i.e., Pr(Nc,T) = i ^ L i Nc = 1,2,." 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 dis-tributed, i.e. if / denotes number of packets in one call, then P r(0 = - M)'"1 / = 0,1,-.. where // is the call completion rate, and its reciprocal pTl is the average 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 model 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. Chapter 2: Voice Packet Transmission 17 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 f A, y = 0 , l,---,5 - l A y = (2-5) l O , j = s. 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 Xa = 0 is that additional voice arrivals after all 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], Py= < f ^ Z ^ L , y = o,i, i=0 (2-7) 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,JPj (2-8) y=i n is also the average number of voice occupied slots in a frame, thus, pv can be obtained as Pv = n/s (2-9) Chapter 2: Voice Packet Transmission 18 substituting (2-7), (2-8) in (2-9) yields, a Pv = -s \ as/s\ t ak/kl (2-10) 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), as/s\ B(s,a) £ ak/k\ k=0 (2-11) (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 pv. Figure 2-2(a) plots B{s,a) versus Sf, for a' = 0.8; figure 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 prob-ability 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 pv < 0.8, pv can be approxi-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 = ^ ( 2 " 1 4 ) bf 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 2 , is given by (2-15) 2 \ ' - 2 D —2 — <7y = 3 Pj ~ n ~ n 3=0 ' _ B{s,a)(s - n) 1-B(s,a) where s = Sf. Chapter 2: Voice Packet Transmission 21 Of more importance is the relative variation rate, APy, defined as APy - {jmaz ~~ Jmin)/Sf such that when 0 < j < jmin and jmax < j < Sf, the (tail) probabilities Pj < Psp, where Psp 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 Sf = 50,100,200 and pv = 1/3,1/2,2/3, Psp = 0.005. It can be noticed that APy decreases with the increase of Sf. Figure 2-3 Tail Probabilities, P3p = 0.005 Changing rate of pv in time is the same as that of j. From (2-5) and (2-6), the arrival rate is A, and the completion rate is p,j. The total changing rate of Chapter 2: Voice Packet Transmission 22 pv for state j, denoted as Apv, is Apv = A + /ij (2-16) maximum Apv and average Apv are thus &Pv max = X + fl-Sf and &Pvave = A + // • n « 2A A typical numerical example of Apv follows: take Tf = 22ms, A = 1.0 call/sec = 0.022 call/frame, pTl = 1.1 minutes = 3000 frames/call, Sf = 100, then n « a = 66 ApVave = 0.022 + 66/3000 = 0.044 change/frame = 1 change/23 frames that means pv will not change for 22 frames on the average. Compared to data arrival rate, which is on the order of 1 arrival in a few slots, pv can be said a 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 F r a m e i L = 6 //// 1 1 1 1 Delayed and Transmi t t ed Data arr ive 1 Data a r r i v a l Tra ns m itted Right away (a) A l l occupied slots aggregated To one side of the frame (b) Occupied slots evenly D i s t r i b u t e d i n the 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)] }' *v2 = Pr{V{n) = l}Pr{V(n + k) = l\V{n) = 1} - pv2 (2-17) Pv{l ~ Pv) _Pr{V{n + k) = l\V{n) = l}-pv I- Pv There are two important special cases: 1) k = Sf, Pr{V(n + k) = l\V{n) = 1} = (2-18) and 7(A:) = ! - - £ -1 - Pv Take \i = 0.0005, pv = 0.5, then 7(fc)| f c = 5 / = 0 . 9 9 9 « 1.0 That means if slot j in frame i is in state 1 (or 0), then slots j in frames (i — 1) and (i + l) are also very likely to be in state 1 (or 0), due to the virtual connection protocol. From (2-17) and (2-18), E \v{n)V{n + Sf)] - pv2  { k~Sf E[v(n)V(n)}-pv* (2-19) V(n)t*V{n + Sf) Vn Chapter 2: Voice Packet Transmission 25 The above is interpreted as: V(n) is (quasi) periodic in the sense of proba-bility, 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 Pr{l) be its probability density function; then there exists an important relationship between P r(0 a "d ^(fc), i.e., l(k)=0 <^=> Pr{V{n + k) = l\V{n) = l} = pv Vn,k ^ 0 Pr(l) = pvl-1(l-Pv) The forward equivalence comes directly from the derivation of geometric distribution; the backward equivalence states the fact that geometric dis-tribution 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 pv, 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 correla-tions are weak* it would be reasonable to assume the independence. Unfortu-nately, 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 Pr(l) in 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 Kc, voice arrival rate X, and voice completion rate p,. The voice assignment protocols VAP-I and VAP-II are also treated as one parameter in the system. Chapter 2: Voice Packet Transmission 27 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 pv (see (2-14)). In order to simulate Apv, average call length pTx should be chosen as close as possible to the real 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 pTl = 3 min-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, pT1 is chosen as 44 seconds in real time, which corresponds to 2000 frames in simulation time, (p, = 0.0005 completion/frame). In the following simulations whenever pv needs to be changed, it is done 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, pv and VAP on voice pattern statistics, respectively. 3 runs of different seeds for 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 Pr{l) for pv = 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) period-icity 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, and fluctuates around 0.1, with maximum ^ (k) « 0.2, for 5 < k < 50* As comparisons, figures 2-6(a) and 2-6(b) show ^(k) and Pr{l) for the same 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 to fc = 50(= S//2), this is because autocorrelation functions are always even functions plus in this case 7(fc) is quasi periodic. Chapter 2: Voice Packet Transmission 29 average *j(k) increases significantly compared to figure 2-5(a); difference between Pr[l) and the geometric distribution is also much larger in figure 2-6 (b) than in 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 pv = 1/3, 2/3, Sf = 50, 200, and 400 cases with VAP-I and -II. Very similar results as above were obtained. 2) pv group Figures 2-7(a) and 2-7(b) show *j(k) and Pr(l) for the same parameters as in figures 2-5 and 2-6, except that pv is lowered to 1/3. No significant change is found in *)(k). Pr(l) is seen to be slightly closer to the geometric distribution than in pv = 0.5 case. pv is then increased to 2/3, *j(k) and Pr[l) are shown in figures 2-8(a) and 2-8(b). Again no significant change in ^(k) can be seen. The PT{1) curve shows slightly more deviation from that of the geometric distribution. Similar results were obtained for VAP-II cases. Chapter 2: Voice Packet Transmission SO 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 these figures suggest 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 Pr(l). For all the four cases, Pr(l) has no significant changes(figure 2-10). The most noticeable changes of voice pattern statistics are changes of Py (figure 2-11). For the same pv, relative variation rate of Py, APy, increases as Sf 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 pv, it can be seen that the major effect of both pv and Sf is on the tail probabilities Py. The smaller Sf is and the larger pv is, the larger APy will be. Besides these major effects, they also 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 pv and/or small Sf are related to relatively high probabilities of block-ing condition occurrence. It is seen in the next chapter that blocking con-dition has significant influence on data performance. Chapter 2: Voice Packet Transmission Figure 2-5(b) Slot Distribution Pr(t) for pv = 0.5, VAP-I C h a p t e r 2: Voice P a c k e t T r a n s m i s s i o n k Figure 2-6(a) Correlation *j(k) for p v = 0.5, VAP-II Chapter 2: Voice Packet Transmission Figure 2-7(b) Slot Distribution Pr(l) for pv = 1/3, VAP-I Chapter 2: Voice Packet Transmission Figure 2-8(b) Slot Dis t r ibu t ion Pr(Z) for pv = 2 /3 , V A P - I Figure 2-9 ^(k) and 5/ Figure 2-10 P r(0 and Sj 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. Reserva-tion protocols are also extensively used in such environments. Combined ran-dom/ 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 sim-ulation 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 mul-tiaccess 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 coordi-nate 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 shar-ing 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 coor-dination (such as TDMA, Polling). The following types of information are commonly used in multiaccess pro-tocols: 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) (3-1) A i 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 mul-tiaccess 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 mul-tiaccess 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 pro-tocols, 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 al-most 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 Chapter 3: Data Packet Transmission 43 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 \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<fm a z].t The delayed transmission repeats the same rule until 2. A transmission delay factor a is defined as (3-2) * 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 probabil i ty a t r a n s m i t L = 4 ZVA V7V7VA \ VA VA New a r r i v a l • With probabil i ty 1-a delay the t r a n s m i s s i o n 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 pat-tern 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 indica-tion 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 Chapter 3: Data Packet Transmission 46 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\ + n2 = n. 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) The m a x i m u m l ike l ihood est imator gm: 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 obser-vations are n\ and n2, (no = n — n\ — n2 is a dependent observation), then the probability distribution is an extension of Binomial distribution, i.e, p(»i,»2) = , u U l T T Pi n iP2 n 2 ( l -Pi- p2)n~n^ (3-3) where Pi = ge~g, P2 = 1 - e~9(l + g) pi is the probability of one arrival in a slot; p2 is the probability of two or more arrivals in a slot. The estimator g is the value of g for which (3-3) is maximized with observations ni and n2. With ni and n2 given, the maximization of (3-3) involves only the expo-nentials Pi n iP2 n 2 (1 - Pi ~ P 2 ) n _ n i " n 2 (3-4) 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\ n%ge~g „ ,„ . — H — , r - n + n2 = 0 (3-5) g T l - e - 9 ( l + g) y } There is no general analytical solution to (3-5), except for some special cases. The following considers two such cases. i) n2 = 0 (3-5) becomes n\ _ ni n = U g= — g n Chapter 3: Data Packet Transmission 48 which is the same as (3-1). ii) n\ = 0, n2 = n 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 im-posed 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 gx, should be used as the value of the estimation gm for this case. The bias and variance of the estimator is h(gm) = 9mP(ni,n2) - g = g~m~- g Var(gm) = gm2p{ni,n2) -g^2 (3-6) Figure 3-2 shows b(gm) and Var(gm) in (3-6), for g = {0.5,1,2.0}, and 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) The a r i thmet i c es t imator 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 gm introduced in the last subsection. However, Chapter 3: Data Packet Transmission 50 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 = n i + 2n 2 (3-7) 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 M-M e = M and its bias and variance are defined as the mean and variance of e, respectively, M - M b(M) = E[e] = E Var(M) = Var[e\ = Var M M-M M (3-8) 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 knowledge. The 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{nun2,M,g) - ^ ^ nun2 _ iyu _ n i _ + n _ n i _ n2)!(/ _ m)\m\ (3-9) where Jo = max(ni + n2 — n,0). 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 = nx + 2n2 + d(g, n) (3-10) 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 — me has zero mean and the same variance as e, i.e. E M-M —U m « M = 0 which implies that the estimator M should be modified according to M-M (M — M • mt) — M M m ' = M The correction term is M • me. Since M is unknown, it is substituted by M • m€, thus, the modified estimator is M= (ni + 2n2) (1 - me) (3-11) where me is given in (3-8). Chapter 3: Data Packet Transmission 52 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 0.07 O I 0.06-i 0.05-Ld 0 . 0 4 J c .9. 0.03-J "o E 0 .02-UJ 0.01 0.00 0-o A O g = 1.0 9 = 2.0 d2= 20 30 40 n 5 0 0.25 O C D •c 0 .20H o > o c o E "to 0.15-0.10-0.05 0.00-f-0 10 20 30 • i 40 50 n Figure 3-3 Bias and Variance of Modified Arithmetic Estimator M Chapter 8: Data Packet Transmission 54 2. The Independence Assumption: 7(fc) =0 VA; ^  0 (chapter 2). Note this implies that Pr(l)=plv-1(l-pv) (3-12) 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 (pv = 0.0 to 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. - random variable L to be number of consecutively voice occupied slots plus - random variable M to be number of data arrivals during the L interval, obeys Poisson distribution; Define: 1 (figure 3-1); - 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 I* Ht)dt (3-13) Let S(/,m) = P r[l successful transmission | given L — l,M = m] = m(l - a / ) m _ 1 a / Let £ be the average of S(l,m) over all values of / and m, then where Thus S = £ m ( l - a i ) » - i a i p p ( / ) M ! l e - 0 ' oo (3-14) 5 = ^2s{l,m)Pr{m\l)Pr{l) (3-15) Z,m P r(m i) = — e m! = E^P-^r'ftwE'(g2i1-i»)r (3-16) / m=l * ' = J2aiGle-a<GlPr(l) 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^. Chapter S: Data Packet Transmission 56 The probability of successful transmission Ps is given by P8 = 5(1 - pv)/G = ^oill(l-pv)e-°»GlPr(l) (3"17) The average retransmission number E is given by E = 1/PS - 1 (3-18) The total delay is given by DA = E{R + Kmax/2) + 1.5 + R (3-19) As a verification, if Pr(l) =6(1 — 1), that is no voice case, from (3-17) and (3-18), E = eG - 1 which is the familiar formula for no voice case. If Pr(l) = (1 — Pv)pv~1 as the result of independence assumption, then from (3-17), CO Ps = «/'e" a' G /(l - PvfPv'1 (3-20) 3.3 Reservat ion P ro t o co l i n the I V D S Systems 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. Chapter S: Data Packet Transmission 57 Frame i SSN = 4 Global Queue - 5 4 3 2 1 © © © 0 © E3 YZYA I V777Z7\ Four Reservations T r a n s m i t t e d D u r i n g The i t h Frame - 1 Delayed to the (> + l)th Frame Updated posit ion (5 -SSN) l h = 1st 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. If fc > 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. Chapter 3: Data Packet Transmission 59 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 DQ, which is the time a request resides in the global queue until the corresponding reserved packet is transmitted, i.e., DR = 2R + Sf/2 + DQ (3-21) Dq 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 Qd denotes the expectation of then Dq for VAP-I is given by (figure 3-5(a)) Qd + 1 Dq = l Under independence assumption, thus 1 - Pv Qd + 1 D q 2(1 - P v ) (3-22) For VAP-II, Dq can be calculated by (see figure 3-5(b)), Qd Dq = pvSf H h (1 - Pv)Sf (3-23) An exact analysis for Qd is given in [18]. The outline is as follows. er S: Data Packet Transmission Queue Q d = 3 P1 - Packet 1, elc P1 ( P 2 ) P 3 zm \ YZWA I vm Figure 3-5(a) Global Queueing Delay Dq for VAP-I XXXX/X/X/X/X/X/X P v S f Figure 3-5(b) Global Queueing Delay Dq for VAP-II Chapter 8: Data Packet Transmission 61 Define g t--= number of data packets in the global queue at the beginning of ith frame; 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 = /,ut- = n}, define the mgf (moment generating function) CO Xn{z) = X) p t i i = l,»i = n}zl (3-25) 1=0 Then L(z), the mgf for qi, can be expressed as a L(z) = Y,X*(z) (3"26) n=0 where s = Sf. It is shown that the following matrix equation holds for the vector X(z) = [Xo(z),Xx(z), • • • ,X8(z)]t, where [ ]f denotes the transpose operation: [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 m n = <f>nmZ~s+n] 0 <m < s, 0 < m < s where <f>mn = P{t>i+i = n\v{ = 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 Dn{z) = ]T [1 - z-^+Vn, 0 < n < 6 Jfe=0 where irkn = 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 Transmission 68 to s 2 (s = Sf throughout the discussion), the above approach may become com-putationally infeasible when Sf is large. In [19], an approximation is proposed. The average data queue length Qd is given as Oi =,. , (3-28) ( l - A j ) ( l - t ; ) ( l - w ) where pd is the normalized data utilization, v and ov2 are the mean and variance of V{, given in (2-12) and (2-15), respectively. u> = i(k)\k=sf a r i d is given in (2-18). The most crucial factor here is h(pd), which is a convex cup function and ranges from 0 to 1. Numerical (simulation) results indicate that h(pd) 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(pd) to be the reciprocal of the normalized queue improvement for M/M/s queueing model, which is given by h ( P i ) " 1 + (.«)- 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 Qd. It was found that with blocking probability 10 - 2 0 < B(s,a) < 10 - 1 0, (3-28) gives good approximation to <3d; with 10 - 1 0 < B(s,a) < 10~5, h(pd) should be modified by using s' in place of s in (3-29), where 1 < s' < s. In these B(s,a) range the approximation (3-28) has the accuracy of ±20%. With B(s,a) > 10~5, the approximation does 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 con-dition [ft - (Sf - Vi)}+ = 0 can be easily satisfied when Sf is large. If the condition is satisfied at the begin-ning 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 pv — 0.5, Sf = 100 and 200. It is seen that Aq is virtually equal to zero in 0 < pd < 0.5 for Sf — 100 and in 0 < pd < 0.6 for Sf = 200. Also shown is Aq for shorter voice length pTl = 200, the range for which Aq is very close to zero is 0 < pj, < 0.6. Based on these observations, the following approximation is taken to eval-uate the queueing delay Dq: express Dq as Dq = D1 + D2 where Z>i is given in (3-22) for VAP-I and in (3-23) for VAP-II, with Qd replaced by d. D2 is used to represent the missing part AQ = Qd — d. Choice of D2 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"^  ( a1 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 pd where r and o1 are the mean and variance of the service time distribution, re-spectively; \ — pd. With the service time distribution given in (3-12), the above becomes Pd{l + Pv) D2 = 2{1 - pv){l - Pi) Simulation results indicate that the above approximation gives the same accuracy as (3-28). Both approximations are reasonable for low and medium pd and pv. Discrepancies become significant when pv is large (> 2/3). Chapter S: Data Packet Transmission 66 The total delay of reservation protocol DR can be expressed as DR = 2R + Sf/2 + DQ (3-30) It can be seen that the queueing delay DQ contributes only an insignificant amount in the total delay, except for very high pv and/or p&. As an example, take Sf = 100, pv = 0.5 and pd — 0.5, DQ = 28.2 slots from the simulation and is 27.5 by the above approximation, which accounts for 1.2% of total delay DR, which is 2478 slots, for R = 12Sf. 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 pv = 0.0 (no voice case), 1/3(low 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 pv in the low(< 1/3) and medium (from 1/2 to 2/3) ranges. Discrepancies between analytic and simulated increase with the increase of pv. 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 pv = 0.5* are the results for simulated independent voice pattern. Compared with pv = 0.5 row which corresponds to VAP-I, the results 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 pv range, indicating that the independence assumption is not valid for 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 pv 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, Sf = 100, Kmax = 120 Pv Pd Simulation Analysis %Difference 0.05 1281.6 1269.7 0.94 0.10 1345.8 1350.7 -0.36 0.0 0.15 1451.5 1448.6 0.20 0.20 1572.7 1574.4 -0.11 0.25 1763.3 1742.9 1.17 0.05 1315.4 1295.0 1.58 0.10 1422.7 1407.0 1.12 1/3 0.15 1571.3 1550.1 1.36 0.20 1765.4 1743.7 1.24 0.25 2027.4 2020.3 0.35 0.05 1332.2 1307.6 1.88 0.10 1480.7 1439.8 2.84 1/2 0.15 1675.4 1609.6 4.09 0.20 1880.9 1847.8 1.79 0.25 2182.1 2207.3 -1.14 0.05 1310.8 1307.6 0.25 0.10 1431.9 1439.8 -0.54 1/2* 0.15 1621.3 1609.6 0.73 0.20 1819.8 1847.8 -1.52 0.25 2214.5 2207.3 0.33 0.05 1407.8 1323.5 6.37 0.10 1539.6 1473.1 4.51 2/3 0.15 1771.6 1677.4 5.61 0.20 2029.4 1974.2 2.80 0.25 2483.5 2442.8 1.67 0.05 1425.3 1337.2 6.59 0.10 1629.6 1504.3 8.33 4/5 0.15 1896.1 1739.7 8.99 0.20 2201.2 2093.2 5.16 0.25 2853.8 2685.1 6.28 0.05 1424.1 1337.2 6.50 0.10 1627.8 1504.3 8.21 4/5t 0.15 1913.9 1739.7 10.01 0.20 2354.3 2093.2 12.47 0.25 3111.5 2685.1 15.88 * Independent voice pattern. fWithout input voice control. Chapter 3: Data Packet Transmission 70 Table 3-2 ALOHA delay-throughput with VAP-II R -- 1200, Sf = 100, Kmax = 120 p» Pd Simulation Analysis /^Difference 0.05 1279.5 1269.7 0.77 0.10 1351.2 1350.7 0.04 0.0 0.15 1460.4 1448.6 0.82 0.20 1565.4 1574.4 -0.57 0.25 1760.9 1742.9 1.04 0.05 1471.4 1295.0 13.62 0.10 1538.3 1407.0 9.33 1/3 0.15 1627.4 1550.1 4.99 0.20 1731.9 1743.7 -0.67 0.25 2085.7 2020.3 3.24 0.05 1501.2 1307.6 14.80 0.10 1641.6 1439.8 14.02 1/2 0.15 1810.7 1609.6 12.49 0.20 1991.3 1847.8 7.77 0.25 2148.1 2207.3 -2.69 0.05 1780.3 1323.5 34.51 0.10 1829.8 1473.1 24.21 2/3 0.15 1941.2 1677.4 15.73 0.20 2109.9 1974.2 6.88 0.25 2524.7 2442.8 3.35 0.05 1772.3 1337.2 32.54 0.10 2063.1 1504.3 37.14 4/5 0.15 2225.6 1739.7 27.93 0.20 2457.9 2093.2 17.42 0.25 3166.9 2685.1 17.95 Chapter 3: Data Packet Transmission 71 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 pv range. During the blocked period, 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 pv = 0.85, together with the corresponding short time average packet delay. 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^ , Sd < Sf, so that at least Sf — Sj, 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 pv — 0.8")" rows show the same system without 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 Slots eooo-c »" c 7000-C i— "o 6000-ion y c 5000-i2 o in O 4000->» o Q 3000 W 2000 Q_ C § 1000 2 9000 8000 A L O H A - I / V A P - I Wi th Input vo i ce con t ro l S,=10O 1 I 1 1 1 1 I 1 1 1 1 I 1 100 200 300 400 Time in Frames 1 1 1 1 1 1 300 400 300 600 700 Time in Frames 900 1000 5 o •a OS fa ?r o> «-$ Go 3 *•*. Co Co *•* • o 3 00 0>) Figure 3-8 Effect of Blocking Conditions 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 dis-crepancy of results between simulation and analysis. It turned out from the simulations that the instantaneous control mecha-nism 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 environ-ment 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 pv = 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 P v, as both are related to the probability of blocking conditions. Figure 3-10 plots simulated data delay versus Sf for pv = 0.5, p,i = 0.1 and 0.2. As long as Sf is in the wide band * Kmax is related to stability. It is shown that for Kmax > KT> where Kj- is related to system parameters such as channel load and user population, the further increase in Kmax 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 ~o to 2 5 0 0 -c >~ o <D Q 2 0 0 0 -% o D D_ C D 1500-a> 2 1000 A L O H A - I / V A P -R=1200 S f=100 P v = 1 / 2 O-10 I ' I ' l / S i m u l a t i o n A n a l y s i s X ' / p d =0.2 p d=0.1 100 2 max 1000 2 3000 Figure 3 -9 ALOHA Delay versus K max 2.5 _D d) Q "D 0) N "o E o 1.5-1-0.5-t 10 A L 0 H A - I / V A P - I R=12S •<max = 120 P¥=1/2 -O- -O--Q-- O --• o-p d =0.2 -o o I ' I ' l I I I I I 100 - a p„ = 0.1 M I M I I I | 4 1000 2 3000 Figure 3-10 ALOHA Delay versus S f 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 pv than if Sf is large. 3.4.2 Simulations for reservation protocol Table 3-3 lists the results for global queueing delay (Total delay DR — 2R) for pv = {0.0,1/3,1/2,2/3, 4/5} with VAP-I. Mean curves are plotted in figure 3-11. These results indicate the range of pv for which the independence assumption and the approximate analysis for 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 pv = 0.5*) and figure 3-11 for the protocol performance on VAP-II voice background. The voice blocking condition occurs for pv > 0.8 which causes the significant increase of the variance of simulation results. The results presented for pv = 0.8 is with the voice input control described in the last subsection. 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, Sf = 100 Pv Pd Simulation Analysis ^Difference 0.10 56.4 55.6 1.52 0.30 66.7 65.7 1.48 0.0 0.50 77.9 76.0 2.44 0.70 89.0 86.7 2.64 0.90 102.8 100.0 2.82 0.10 57.0 55.9 1.94 0.30 66.6 66.2 0.65 1/3 0.50 75.8 76.7 -1.28 0.70 86.7 88.1 -1.58 0.90 102.6 104.7 -2.06 0.10 58.3 56.2 3.74 0.30 69.0 66.6 3.49 1/2 0.50 78.2 77.5 0.88 0.70 88.1 89.5 -1.56 0.90 106.2 109.5 -2.98 0.10 93.2 103.2 -9.73 0.30 104.7 113.6 -7.87 1/2* 0.50 115.9 124.5 -7.39 0.70 142.4 136.5 4.45 0.90 173.6 156.5 10.97 0.10 60.0 57.0 5.33 0.30 68.0 67.6 0.69 2/3 0.50 80.4 79.0 1.29 0.70 99.3 92.3 7.67 0.90 130.1 119.0 9.37 0.10 64.4 58.8 10.05 0.30 74.7 69.5 7.54 4/5 0.50 92.7 82.0 13.31 0.70 115.9 98.0 17.37 0.90 170.2 138.0 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 Inde-pendence 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 over-head 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 back-grounds. On the other hand, ALOHA protocol is affected significantly by difference of voice pattern background (different p'vs, VAP's and blocking, etc). 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, espe-cially 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 Chapter 3: Data Packet Transmission 80 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 t + i is the total number of unoccupied slots in the (i + l)th frame. Suppose the outcome is j, 1 < j < Mj + 1, transmit in the jth unoccupied 4. Collided transmissions repeat the same procedure as above, as well as de-layed transmissions. p is also called delay factor and is defined as slot. (3-31) where g = g(t — R), M = M;+1. Chapter 8: Data Packet Transmission 81 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 nt- the number of packets awaiting transmission at the beginning of the ith. frame. nt- is also called the backlog. Then ni+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. Chapter 8: Data Packet Transmission 82 Since k{ is dependent on Mt- and n,, (3-32) describes a 3-dimensional Markov chain {ra,-, Mi, r,}. The transition probabilities for Mt- is known as (see (2-5) and (2-6)) M-l\Mi = M} — Mfx M\M{ = M} = 1 - A - Mfi M+1\M{ = M} = A The dependency of fc» on 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 sam-ple 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,n, equals to the output of the system, Sout, i.e, Sin — Sout = S where S is the throughput of the system. In the following analysis, the expressions of Sout and Sin, conditioned on Mi and ra,-, are derived; then the above EPA principle is used to evaluate the protocol performance. P{Mi+1 = P{Mi+1 = P{Mi+1 = Chapter 3: Data Packet Transmission 83 1 ) Sout'. 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 and fc, the probability of number of successful transmissions, m, is given by [Appendix] p(m|fc, M, n) = 1 J , / r Y(-l)3 777 w - x , „ TT (3-35) v 1 ' ' m\Mk j-^ ' (M — — m)!(fc - j)! 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) (3_36) k It can be shown that [Appendix] E[m\k,M,n) = fc(l - jj)h~l (3-37) which does not depend on n when fc is given. Chapter S: Data Packet Transmission 84 Combine (3-33), (3-36) and (3-37) « - E ( ; y d - r t - * * ( i - y k=0 v ' v 7 k-l After some algebraic manipulations, By (3-34), (3-39) is m = p n [ p ( 1 ~ ^ f ) + 1 " P r l 1, P = \ M n ' m = < M l 1 - -n n < M n> M n-l n-l n< M n> M (3-38) (3-39) (3-40) The output of the system, Sotlt, is ra S0ut — T T = < M \ - ( M \ n-l , n<M 1 1 n> M (3-41) Define: n M * Thi s definition is slightly different from that i n (3-1). Here the denominator is the number of slots not occupied by voice, while i n (3-1) it is the t o t a l number of slots (occupied as well as occupied by voice) during the observation period. Chapter 3: Data Packet Transmission 85 Then 'out a [ l - - ) , g<l (3-42) Figure 3-12 shows S o u t versus g, for M = 5, 10, 20 and 100. Two important features of Sout are noticed: i) For different M, the difference between S o u t is small. In fact, after M > 10, the difference is negligible. ii) All curves approach e _ 1, when g is large. In fact, e _ 1 is the asymptotic line for all the S o u t curves. From (3-40), when n —>• oo, (3-43) 2) Sin: i) For finite population model and stop-and-wait transmission rule, 5t-n is 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 Sout versus g Chapter 3: Data Packet Transmission 87 product oN is constant and is the aggregated Sin rate, i.e, Sin = aN = constant It is also the 5 1 W 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 Sout and Sin together in figure 3-13 (M = 5); the following can be noticed: i) If Sin < e _ 1, that is region I in figure 3-13, there is only one intersection between Sov,t and S{n, where Sov,t = S{n, that is the EP. Moreover, it is a globally stable EP. ii) In region II of figure 3-13, there are 3 intersections between S0ut a n<l Sin] 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«), Smax, is e _ 1, which is independent of voice fluctuation. This is shown as the following: Chapter 3: Data Packet Transmission Figure 3-13 Sin / Sout and EP's Chapter 8: Data Packet Transmission 89 Define p{M) = Pr{Mi = M} which is given in (2-7), then the maximum throughput in terms of number of packets is rnmax = y^m m a 2(M)p(M) (3-45) M where fnmax(M) is rn~max(M) = lim m(M) n—»oo by (3-40) mm(w(M) = Me - 1 thus (3-45) becomes mmax = M 0e _ 1 (3-46) where Mo is the average number of available slots to data transmissions, from (2-8) and (2-9) M 0 = Sf{l - pv) The normalized throughput is thus e - 1. ii) For S{n < e _ 1> the throughput is closely approximated by S = Sin =S0Ut ± x-Ma{ge-l/M0) (3_ 4 7) where M 0 is the average number of slots available to data transmissions; 9e — ne/M0, where ne represents the EP value of n for M = Mo. This is 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), and (3-39) From (3-34) and n — k = n(l — p) k-m= np{l - [p(l _ -L) + l - p]*"1} f 0, n < M n - k = < (3-48) {n — M, n > M [ n[l - (1 - 1/M)n~1}, n<M k-m = { (3-49) [M[l-{l-l/n)n-1], n>M If the input rate per frame is n,„, then when M < n{n, the backlog n — k increases linearly, while the backlog k — fn is held at its maximum value, which is M(l -e - 1) when available slots returns to M > riin, the excess number of packets in the backlog n — k is cleared; as long as nin < M 0e _ 1 the steady state condition can be reached, i.e, nout — 'nin Chapter 8: Data Packet Transmission 91 or equivalently, S0ut — S{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 5tw, ASin. As long as 5tre is in region I, no matter how large ASin may be, after a finite period of time after ASin disappears, EP is obtained with certainty, and the condition 5t-n = Sout = S prevails. The average throughput is thus well approximated by (3-47). However, the larger ASin 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 Soutp{M, n) (3-50) n,M where p(M,n) = Pr{Mi = M,nt- = rc} (3-47) approximates (3-50) by letting p(M,n) = 8(M — M0,n — ne). From 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 (3-47). Chapter 8: Data Packet Transmission 92 5) Delay Dq: Dq is defined as the delay incurred by a packet due to the delayed transmission and collision retransmission* Conditioned on n and M, Dq{M,n) is Dq{M, * ) = ( = - ^ Sf + ~ "0 ^  + ^  (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 Dq(M,n) = - 5 - 1 (R + K), (n/M-l)Sf + n l-n n < M {R + K), n>M (3-52) and total Dq is Dq = Yl Dq(M> n)Pr{Mi = M, m = n} By the same EP approach about throughput, (3-53) Dq w Dq(M0,ne) 1— ne [R + K), {ne<M0) (3-54) Since ne < M0 for EP, the approximation ignores the term [n/M — l)Sf. * The symbol Dq 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. Chapter 3: Data Packet Transmission 93 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 Sf < (R + K). For Sf « (R + K), such an approximation may cause significant error. Using the notation ge = nE/M0, and note M0 ^> 1, (3-54) is well approxi-mated as Dq = (e9e — 1)(R + K) (3-55) Some Observat ions 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 fluctua-tions, 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 Dq, provided that Sf <C (R + K). 6) The To ta l De lay DTx The total delay of ALOHA-II, Df, consists of the backlogged delay Dq, as dis-cussed above, plus a header delay Dn and propagation delay R, i.e. DT = Dq + Dh + R 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 Dh = D1 + D2 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; D2 is the time between the 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 D2 = i s / ( l + pv) 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 D2 for VAP-II Chapter 3: Data Packet Transmission 95 fO CN (N CN *~ O S|0|2 Ul X0 |8Q ja^ OD,-! U D 8 ^ § Chapter 8: Data Packet Transmission 96 Figure 3-15(a) and figure 3-15 (b) show simulation results of ALOHA-II, assuming perfect estimation. The effect of voice background is explicitly shown using pv as x axis variable. The analytic results for ALOHA-II from (3-55) are the points on y axis (pv=0). Also shown are the curves of ALOHA-I for comparisons. 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 pv, Pd and VAP-II voice pattern background. The values of pv 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 nr be the estimated value and n be the real value of backlogged number at the beginning of an arbitrary frame. The estimation error An is An = nT — n The delay factor p (3-34) now becomes From (3-39), expected number of success, m, becomes, n + An < M n + An > M (3-56) Chapter 3: Data Packet Transmission 97 Let 6(n) be the relative estimation error, i.e, 6(n) = then the case n + An > M in (3-56) becomes -171-1 l + 6(n) I1 n[l + 6{n)] ,n + An > M (3-57) Let / = n[l + 6(n)], then (3-57) becomes m = 1 + 6{n) 1 ,n + An > M (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 = ^7-^-e -T+^T (3-59) n-»oo 1 + ^^ 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 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 dis-tributed between (61,62), — 1 < <5i < 62, where both 6\ and 62 may be dependent on n. p(e|n) = Pr{6(n) = e\n} (3-60) Chapter 3: Data Packet Transmission Figure 3-16 Output Rate Sout and Estimation Error b~(n) Chapter 3: Data Packet Transmission 99 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 in figures 3-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 the figure legends. Figure 3-l7(a) shows mean backlogged delay Dq in frames; For 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 (pv = 0). Figure 3-17(b) gives some insight of how the control mechanism works, where Ex is the expected number of delayed transmissions, and E2 the expected number of collisions. They are defined as Ei = n/k- 1, E2 = k/fn - 1 respectively. From figure 3-17(b), it is seen that E2 is close to that of pure ALOHA curve(®) due to the control mechanism, while Ei increases as pd and * In these simulations, the average voice length yT1 is 500 frames. 15-| 0.0 0.1 0.2 0.3 Pd Figure 3-17 (a) Backlog Delay Dq and pd, for n~l = 500 Chapter 3: Data Packet Transmission 102 pv increase. The pattern that E\ changes with pd is very similar to the excess queue size in the reservation protocol discussed in section 3.3, in that both of them remain near zero when pd is below a certain value, and abruptly increases 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,~x = 50 frames. It is seen that E2 remains basically 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 algo-rithm. 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~9, which is rather flat in the region around g = 1.0. In section 3.2, two examples show the possible implementation of estima-tors. 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, nt-+i, and that at the ith. frame, n^; the total new data arrivals during the ith frame, d^; and the total Chapter 8: Data Packet Transmission 108 retransmissions heard during the ith frame, r ,^ is (a variation of (3-32)) n 1 + i = (n,- - ki) + di + rt- (3-61) (3-61) suggests an algorithm for the estimation of n t + i by 1) Estimation of number of delayed transmissions (n, — ki)est from the previous frame; 2) Estimation of number of arrivals in the previous frame, di>est; 3) Estimation of number of retransmissions heard in the previous frame, ri>est. Both di>est and rt- e.$ can be estimated using the similar methods as in section 3.2. For (rc,- — ki)est, it can be estimated by (n; - ki)est = n , , e 3 t ( l - p) (3-62) where n t j e s t is the estimate of ra,- at the ith. frame, and • I M A p = min ( ,1 V rarest / It is possible that ni>est was an erroneous estimate of nt-. It can be shown, by exhaustive numerical values, that (3-62) always converges, i.e, error (n( t + 1 ) e s 4 — ni+i) < (ni>est — ni), for arbitrary initial value of n,. In the next chapter, a combined random/reservation scheme is studied. ALOHA-II 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 in-troduced 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 _ 1. On the other hand, although the delay for 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 op-eration, 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 Sw i t ch ing In format ion The adaption ability is achieved by exchange of information among the dis-tributed 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 heav-ily 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 ex-pected 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 infor-mation. 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 envi-ronment 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 infor-mation 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 of fixed request 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 re-serving 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 ded-icatedly 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 The Comb ined Random/Rese rva t i on P r o t o co 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 The data access protocol (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, Na; iii) the number of packets on the process of reservation (i.e., request has been sent for them yet reservation grant has not been received) plus the number of packets for which reservation has been granted, Nr. The number of packets which are neither being sent via random access nor on the process of reservation, iV w, is thus Nw = Nt-Na- Nr 1. Upon any new arrival, the user checks the total channel traffic factor g = g(t) against a prespecified threshold, denoted as Gth (node 1). If g < Gth, transmit the packet via ALOHA mode, thus Na is incremented by 1 (node 4) ; if g > Gth, put the new packet in the buffer (add 1 to Nw), then go to 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., Nw. 3. If there is no transmission scheduled via ALOHA, check if there is any Chapter 4- Combined Random/Reservation Protocol 110 A d d 1 to N , Wol1 In t h e u s e r b u f f e r A d d t to N . Walt In t h e u s e r b u f f e r A t t a c h t h e re q u e s t f o r th e N , p o c k e t s A t t a c h t h e r e q u e s t f o r t h e N„ p a c k e t s Figure 4-1 Data Access Protocol Flowchart Chapter 4- Combined Random/Reservation Protocol 111 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 Na = Nr = 0, then schedule a transmission via ALOHA 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, "reser-vation transmission", means that transmissions execute the reservation pro-tocol 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, Nw, to iV r (node 9). All the Nr packets wait in global queue until their sched-uled transmissions (node 9). If upon successful transmission, no request is attached, i.e., Nw = 0 (node 8), then the cycle is completed (STOP). Vo ice Access P r o t o co 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 Nti. If Nti greater than a prespecified threshold Ntr, 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 con-nections. Similarly, it can be blocked by reservation transmissions while reser-vation and ALOHA are in the same system. In order to avoid the blocking condition, a maximal number of voice connections plus reservations accommo-dated in each frame, Stn, is specified, where Sth < Sf. At the beginning of each frame, the following information are available to each user: i) the entries of the voice request queue, and the number in queue, Nv'; ii) the entries of the global data reservation queue and the number in queue, iVr'; iii) the total number of unoccupied slots, Sf — Nv, where Nv is the number of voice occupied slots before 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 Nv (which is incremented by 1 every time a slot is assigned to a new call) in that frame no larger than S^. Mark the correspondent slot as state 1. Chapter 4' Combined Random/Reservation Protocol US If Nv = Stn, the remaining voice requests in the voice global queue are rejected. 2. After all voice requests having been accommodated, transmit the reser-vations in the global queue while keeping the total number of slots being occupied by voice, Nv, plus the number of slots just being used by reser-vation transmissions, i V r f , no larger than Stn, i.e., Nv + 7V r* < Sth- If the sum exceeds Stn, the rest of the reservations are delayed to the beginning of the next frame. In the case where Nv = Sth, 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 — (Nv + N^). Because (7V„ + 7V r ' ) < Sth, SSN > Sf - Sth > 0. It is necessary to mention that the introduction of quantities Nv, i V r f 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, Nv + 7 Y r f < Stk, Sth < Sf, SSN = Sf- (Nv + Nr*) 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 Sys tem Parameters 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 rep-resent typical situations, e.g, pv can be either 0.0 representing no voice case or 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 — max (1,0.05(1-p..) 57) 3- Gth. Since it determines the switching point between ALOHA mode Chapter 4- Combined Random/Reservation Protocol 115 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 Gth to CP will be shown in the simulations in the next section. 4. Sf and number of users in the system, Nu. For low throughput range, the system operates basically in ALOHA mode, thus Sf and Nu will have no significant effect on the performance of CP. For throughput greater than e _ 1, there is a value for the number of users, Num, below which the delay of data packets is minimum. A certain relationship exits between Num and Sf, as will be discussed in the next section. 5. The maximal number of trials for voice setup request transmissions, Ntr. 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 CP 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 _ 1, where the system is frequently switching between the ALOHA mode and reservation mode. For throughput much less than e _ 1, however, the system op-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 « Gthi For low throughput range where g < Gth is always satisfied, the protocol operates 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 > Gth'. For high throughput range where g > Gth is always satisfied, CP can be in Chapter 4: Combined Random/Reservation Protocol 117 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 7VU in the system. There exits a value for the number of users, Num, below which the system will operate (most of the time) in loop i; As Nu increases, the probability that the system enters loop ii increases, for throughput greater than e _ 1. An extreme case is that the number Chapter 4- Combined Random/Reservation Protocol 118 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 _ 1, the chance of successful transmissions is approaching zero and delay approaching infinite, this is the second loop indicated above (for infinite population models). In the throughput range greater than e _ 1, it is desired that most of the packets should be transmitted via reservation mode; i.e, the first loop indicated above. The following derives the asymptotic value of NUM 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 NU, then b = d • NU 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' R-SAI-*)-1 (4_1) where the unit of R is Sf. 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. Chapter 4'- Combined Random/Reservation Protocol 119 the normalized maximum data throughput is 1.0. Re-arrange (4-1), R • Sf • (1 - Pv) b or equivalent ly, Num < R • Sf • (1 - pv) (4-2) (4-2) gives an upper estimate of Num. P r e v i o u s R e s e r v a t i o n i n P r o c e s s P r e v i o u s r e s e r v a t i o n t r a n s m i t t e d ' - w i t h t h e r e q u e s t f o r t h e r e s e r v a t i o n o f 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 Num is obtained as follows. If the normalized maximum data throughput is no greater than e _ 1, then the system will operate in the third 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 — = d < 1, ^ ^ > e - 1 (4-3) Nu ~ ' R • Sf • (1 - P v) ~ 1 ' Chapter 4- Combined Random/Reservation Protocol 120 the right hand side equation reverses the condition that the data throughput is no greater than e _ 1, in order to obtain Num. Simplifying (4-3) gives, Num > e-1 • R • Sf • (1 - P v) (4-4) Combining (4-2) and (4-4) gives, e-1 • R • Sf • (1 - p„) <Num<R-Sr{l-pv) (4-5) 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 signif-icant effect on low throughput range where ALOHA mode dominates. It influ-ences the system on high throughput range as (4-2) and (4-4) indicate, i.e., Sf is proportional to Num. Moreover, (4-2) and (4-4) suggest that Num is proportional to (1 - pv). 3) T r i a l numbers for voice request transmiss ions: If trials are assumed to be independent with probability of success ps, then the distribution of trial numbers Ix is given by Pr[lT = l] = P,{l-p,)'-1 (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 ps is the same as that for data packets transmitted via ALOHA. For g < e _ 1, it is given in section 3.5. For g > e _ 1, an accurate calculation for ps is difficult; as an estimation, it can be noticed that if Nu < Num, the average delay of data packets is about 2.5 times of propagation delay R. Thus, ps can be estimated by ps = 1/2.5 = 0.4 For such ps, calculation of (4-6) suggests that no more than 2% of trials exceed 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 CP Simulations were carried out to obtain the delay-throughput performance curves with different values of Gth as parameters* The relationship among pv, Sf and Num as indicated in (4-5) was verified. The simulated trial number distribution P r[/r] was also obtained. 1 ) Effect of Gth Figure 4-3(a) shows delay versus throughput curves for pv — 0.5, Sf = 100, Nu = 100, Gth = {0.0,0.15,0.35,0.75,1.0}. As can be seen, Gth determines the 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 < pd < 0.32, i.e, ALOHA throughput range). On the other hand, the delay in the 0.32 < pd < 1.0 range increases with the increase of Gth-For 0.0 < Gth < 0.35, the major change of delay is in low pd range. In Gth — 0.0 case, the curve departs from that of ALOHA right at p& = 0.0; in Gth = 0.15 case, departure occurs at p& « 0.15. These curves have larger delay than that of ALOHA. However, for Gth — 0.35, the curve departs from that of ALOHA at pd « 0.32 and the delay is smaller than that of ALOHA, indicating that for pd > 0.32, reservation mode should be partially used instead of pure ALOHA mode. The desirable range of Gth can also be seen from the figure, i.e., the optimal value of Gth is about 0.35. Figure 4-3(b) shows delay versus throughput curves for pv = 0.0, Sf = 100, Nu = 200, Gth = {0.0,0.3,0.7,1.5}. Similar observations can be made on Gth, except that the desirable value of Gth has been doubled to around 0.7. Also noticed is the similarity between figures 4-3(a) and 4-3(b): curves of pv = 0.5 (figure 4-3(a)) correspond to curves of pv = 0.0 (figure 4-3(b)) with Gth doubled. This similarity can be explained by the fact that as pv changes from 0.5 to 0.0, the total channel capacity available to data users doubles. If the total channel traffic factor g were normalized to (1 — pv), Gth would have the same values for pv = 0.5 and pv = 0.0. The similarity between performance with and without voice presence indicates that CP is not susceptible to voice background. The system parameters Sf, Nu and pv for figures 4-3(a) and 4-3(b) are chosen such that the ratio Nu Sf(l - Pv) is identical. The relationship among Sf,Nu and pv is investigated further in the Chapter 4- Combined Random/Reservation Protocol 123 following section. 2) The relationship among Sf, JVU and pv The relationship among Sf, Nu and pv is given in (4-5). In this section, simulation results are shown to verify (4-5). Figure 4-4(a) shows delay versus throughput for pv = 0.5, Sf = 100, Gth — 0.25, Nu = {100,200,300,400,500}. It is seen that low throughput range of Pd (0.0 < Pd < 0.36) is little affected by Nu, since ALOHA performance is not affected by Nu. For pd > l/e, delay increases with the increase of Nu. However, there are significant differences among curves for Nu < 200 and for Nu > 200, this indicates that Num of the system is between 200 and 300, a calculation of Num according to (4-5) gives 220 < Num < 600 thus the simulation results lie between the upper estimate and the lower estimate of Num by (4-5). For Nu below Num, the change of Nu does not change the delay versus throughput performance significantly, e.g, curve for Nu — 100 is very close to that for Nu = 200. Similar results can be seen for pv = 0.0 case from the delay versus through-put curves shown in figure 4-4(b). The simulation shows that Num 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 , , , | . , I . | , M , | I I I I | I I I I | I , I I | I . I I , I . I . | I . . . ! . . . . 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 (b) Pd Figure 4-4 CP Performance and User Number Nu Chapter 4- Combined Random/Reservation Protocol 126 than 400 and (much) below 800. According to (4-5), 440 < Num < 1200 Also noticed is the similarity between the curve for Nu = 400(800), pv = 0.0, shown in figure 4T4(b), and the curve for Nu = 200(400), pv = 0.5, shown in figure 4-4(a). The ratio Nu/(l — pv) is the same for both of them. For Nu greater than Num, delay increases rapidly with the increase of pd. For pj, = 0.75, figure 4-5(a) and figure 4-5(b) normalized delay versus Nu for pv = 0.0 and 0.5, respectively. Effect of Nu can be seen more clearly from these figures. Calculated Num according to (4-5) for each curve is also shown as a comparison. Again the similarity for curves with the same Nu/(1 — pv) ratio, i.e, the curves Sf = (100)200, pv = 0.5 (in figure 4-5(a)) and Sf = 200(400), pv = 0.0 (in figure 4-5(b)) can be seen. 3 ) Trial number distribution Figure 4-6(a) shows trial number distributions (simulated) for pv — 0.0, pd = {0.1,0.3,0.5,0.75}. As pd increases, the trial number increases. The maximal number of trials shown for pg = 0.75 is 6 with frequency 10-5. Figure 4-6(b) shows trial number distribution for pv = 0.5, The maximal number of trials shown for pd = 0.75 is 8 with frequency of 10-5. These results Chapter \: Combined Random/Reservation Protocol 127 Figure 4-5 Relationship among Num, Sf and Nu Figure 4-6 Trial Number Distribution Chapter 4- Combined Random/Reservation Protocol 129 suggest that for practical time requirement of voice connections, random access protocol for setup request transmission is satisfactory. 4.5 Comparison of CP with A L O H A and Reservation 1. For low throughput range 0 < pd < e - 1, with proper choice of Gth, CP gives the same delay versus throughput performance as ALOHA. 2. In throughput range pd > e _ 1, for proper choice of Gth an^ Nu not exceed-ing Num, 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. How-ever, 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 trans-mission 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 pv = 0.5, Sf = 100, Nu = 200 and maximum pd no less than 0.85, at most 10% of average remaining capacity 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 sub-channel 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 in-dependence 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 sig-131 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 _ 1. Furthermore, 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 pro-tocol, the 2-dimensional probability function in (3-50) needs to be derived. 4. Voice packet multiplexing and/or data packet transmission, by taking advan-tage 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 si-lence 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 sta-tion 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 (3-35) 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 Mn. Let n\ denote the number of all the patternsf with no 1-ball boxes:): Let denotes the number of the patterns that have at least k 1-ball boxes, for example, Nx is the number of patterns that has at least one 1-ball box. Then n\ is given by m = Mn - Nx 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 { ^ j A n \ M - l ) n - l > N i since in (M — l)n the ways of getting at least two 1-ball boxes are included. Thus Ni= ^ V ( M - 1 ) W - 1 - / V 2 But N2 is also unknown, the number ^ A n 2 ( M - 2 ) n - 2 > N 2 and should be subtracted by N3,..., etc, thus », = M * - { ( ^ ) A „ ' ( M - ! ) » - ' - {(^JA.\M - 2 ) - 8 - { ( * ) A . ' ( * - S ) - - - ±NL}}} the last number iVx, is NL= (™)AnL(M-±L)n-L * The function An* is defined as Appendix 136 where L = min(M, n). NL does not contain NL+I, since Nj = 0,Vi > L. Thus m =Mn - (^) V ( M - I)""1 + ( ^ ) V ( M - 2)n~2 - (f) An3(M - 3)»"» + • • • ± (^) AnL(M - L)n~L ( A 1 ) =I:(-l)fc(^ )v(^ -^ ),l-* (Al) can also be written as L nx = ^ ( - 1 ) * G ( M , n, k)B(M, n, k) (A2) fc=0 where G(M,n,k) = (^ W B(M,n,fc) ={M-k) n—k Name G(M,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) , , Appendix 1S7 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\ Ankj B(M,n,k) =(M-k)n-kj and L *=o > - ' wo where L = min(M, n/j). An important special case is j = 0, M "o = £ ( - l ) * ( ^ ) ( M - f c ) n (A5) fc=o ^ ' 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. Appendix 138 of patterns containing exactly i 1-ball boxes, denoted by ci(i), is «.(.•) - (^WB-l)'(TV(m-fc)'-' (A6) ^ ' Jfe=0 ^ ' 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 Mn, i.e., (3-35) is obtained after algebraic simplification of (A8). 3. The two-dimensional 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(i0) = (¥). To find c(ii\iQ), it is sufficient to apply (A2) with M substi-Appendix 1S9 tuted by M — io, and G(M-i0,n,k)=(M~l0)Ank B(M - i0, n, k) =c0(0) = n 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)4(T)vE(-i)'(m;*)(m-*-iT-* 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 ! ^ , i[M - (,• + ^ M n -L'' »!j![JWf — (» + — (» + Appendix Let k = i + j, then = M ! n ! f f * ( M - f c ) - -It is easy to show that t i — A ; Substituting (Al l ) into (A10), one obtains (3-37). References [1] T. Bially, A. McLaughlin, and C. Weinstein, "Voice communication in inte-grated 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 Pack-etized 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, "Inte-gration 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 Exper-imental 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 Commu-nications 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 AD-A45455, 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 Time-Constrained 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 Chan-nel: 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 In-tegrated Voice/Data Multiplexers With and Without Speech Activity De-tectors", 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 TDM Sys-tem", IEEE Trans, on Commun., Vol.COM-33, No.12, Dec. 1985. References 144 [20] A. Leon-Garcia, R. Kwong and G. Williams, "Performance Evaluation Meth-ods 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 An-alytic 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 Inte-grated 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, Au-gust 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 Multi-beam Satellite with Integrated Circuit and Packet Switching", Proc. 6th Int. Conf. Digital Satellite Commun., pp.x-27 to x-34, 1983. 


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



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"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items