MULTIPLEXING SCHEMES AND ARQ PROTOCOLSFOR MULTIPLE-RECEIVER SYSTEMSbyRichard CamBASc (Engineering Physics), University of British Columbia, 1986MASc (Physics), University of British Columbia, 1989A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDoctor of PhilosophyinTHE FACULTY OF GRADUATE STUDIESDEPARTMENT OF ELECTRICAL ENGINEERINGWe accept this thesis as conformingto the required standardTHE UNIVERSITY OF BRITISH COLUMBIAOctober 1994© Richard Cam, 1994In presenting this thesis in partial fulfilment of the requirements for an advanceddegree at the University of British Columbia, I agree that the Library shall make itfreely available for reference and study. I further agree that permission for extensivecopying of this thesis for scholarly purposes may be granted by the head of mydepartment or by his or her representatives. It is understood that copying orpublication of this thesis for financial gain shall not be allowed without my writtenpermission.(Signature)Department of Electrical EngineeringThe University of British ColumbiaVancouver, CanadaDate 14 October 1994DE-6 (2/88)AbstractThe throughput performances of some multiplexing and ARQ schemes are evaluated for amultiple-receiver system in which the quality of the channels varies over time. Packetized dataare sent to the receivers from a server (transmitter), which uses a multiplexing scheme to assignbandwidth, as well as an ARQ protocol for error control. Two multiplexing schemes, round-robin multiplexing and an adaptive scheme, are considered. In round-robin multiplexing,each receiver is served periodically. With the adaptive scheme, the transmitter selects at eachslot, the receiver whose channel quality is judged to have the highest probability of successfuldata packet reception. These multiplexing schemes are evaluated in conjunction with thethree standard ARQ schemes, stop-and-wait, go-back-N, and ideal selective repeat ARQ. Thethroughput analysis takes into account the effects of feedback errors and imperfect channelstate estimates.A scheme for reducing the unfavorable effects of feedback errors on the performance ofcontinuous ARQ protocols is proposed and analyzed for a point-to-point stationary channel.In this scheme, the transmitter may not immediately retransmit a packet that has timedout but whose status is unknown due to lost feedback. Instead, the transmitter may delayretransmission for up to a given number of slots (the “retransmission delay parameter”),sending new packets in the mean time while waiting for successfully received feedback. Theanalysis considers the case where complete information of the receiver state is fed back tothe transmitter. Under this assumption, it is shown that the effects of feedback errors canbe greatly reduced when the retransmission delay parameter is optimized. This scheme isextended to the multiple-receiver system as well.Also discussed is a procedure for maximizing the effective data transmission rate of anARQ system under certain bandwidth and power constraints. The procedure provides ameans for jointly optimizing system design parameters such as the packet length, as well ascoding and modulation schemes. The principles behind this procedure may also be usefulfor evaluating and optimizing the data transmission rate performance of the multiple-receiversystem.IITable of ContentsAbstract iiList of Tables viiList of Figures viiiGlossary xiAcknowledgment xiv1 Introduction 11.1 Preliminaries 21.1.1 Reliable Data Communication 21.1.2 FEC and ARQ 31.1.3 Point-to-Multipoint ARQ . .... . . . . . . . . . . . 61J.4 Multiplexing and Multicast Systems 71.2 A Brief Summary of Related Work 81.2.1 Analysis. 91.2.2 Systems 91.2.3 Multi-copy Transmission 101.2.4 Type-I HARQ 101.2.5 Type-lI HARQ 111.2.6 Code Combining 111.2.7 Optimum Packet Length 121.2.8 Point-to-multipoint ARQ . . . . . . . . 121,3 Summary of Contributions . 13Ill2 Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 152.1 Introduction . 152.2 A Buffer-Constrained Model for ARQ Protocols ........ .... 162.3 The Feedback Chamiel . . . . . ...., ,,,,,...., 172.4 A “Postponed Retransmission” Variation for Continuous ARQ Protocols 202.5 Throughput Analysis 222.6 Numerical Results 262.7 Summary and Concluding Remarks 473 A Unified Approach to Data Transmission Rate Analysis for ARQ Systems 483.1 Introduction 483.2 System Model 503.3 Data Transmission Rate Analysis 513.3.1 Preliminary Calculations . . . . 513.3.2 Synchronization Issues and Modulation Schemes 533.3.3 Packet Error Probabifity with Convolutional Coding 553.3.4 Packet Error Probabifity with Reed-Solomon Codes 553.3.5 ARQ and Data Transmission Rate 563.4 Numerical Results 573.5 Concluding Remarks 644 Multiplexed ARQ: Throughput Analysis, Part I 654.1 Introduction 654.2 System Model 674.3 Throughput Calculation 714.3.1 Round-Robin Multiplexing . . . . 724.3.1.1 ISRARQ 724.3,1.2 GBNARQ 72iv4.3.1.3 SWARQ. 774.3.2 Adaptive Multiplexing 794,3,2,1 TSR ARQ 794.3.2.2 GBN ARQ 804.3.2.3 SW ARQ 845 Multiplexed ARQ: Throughput Analysis, Part II 865,1 Introduction . . .. 865.2 Extension of Throughput Analysis 875.2.1 Round-Robin Multiplexing 885.2.2 Adaptive Multiplexing 905.3 Reduced State Space Analysis 925.3.1 Round-Robin Multiplexing 955.3.1.1 m = 1’ 955.3.1.2 m = 2’...........,...............,.,.,....... 955.3.1.3 m = 3, . ,.......,......,,.,,,..,,., 965.3.1.4 m = 4: . . . 965.3.2 Adaptive Multiplexing 965.3.2.1 m = 965.3.2.2 m = 2’ 975.3.2.3 m = 3’ 975.3.2.4 m = 4’ 986 Multiplexed ARQ: Numerical Results 996.1 Introduction 996.2 Throughput Performance Comparisons 1016.3 Concluding Remarks . ...... 115V7 Concluding Remarks 116A Conditions for Continuous-Mode Half-Duplex Transmission over a Direct Link 118A.1 Introduction 118A.2 Analysis. 118B Packet Synchronization Analysis 120B.l Model 120B,2 Analysis 121B,3 Numerical Results 122B.4 Concludthg Remarks 122C Representation and Analysis of the Complete Multiple-Channel State Space 124C.1 Size of State Space 124C.2 Indexing the States 126C.3 State Transition, State Estimation Error, and Selection Probabifity Calculations . 127D Derivation of the “g” Function 129E Analysis of an Equivalent Reduced Semi-Markov Process 130E.1 Introduction 130E.2 Analysis 131E.2. 1 Transition Probabifities 131E.2.2 Average Number of “Successes” 131E.2.3 Average Number of Times “Selected” 133E.3 Concluding Remarks 134Bibliography 135vi2.12.22.32.4List of Tables• . 2737373846469494ISRARQ. • 103106106107Throughput of SW ARQ, N = 10, , . .Optimal values of w for GBN ARQ, N = 10.Optimal values of w for GBN ARQ, N = 100Comparison between calculated throughputs for GBN ARQ from Eqn. (2.2) andfrom Eqns. (21)-(27) of, N = 10.2.5 Comparison between calculated throughputs for GBN ARQ from Eqn. (2.2) andfrom Eqns. (21)-(27) of, N = 1002.6 TSR-limit values of w for SR ARQ, N = 102.7 ISR-limit values of w for SR ARQ, N = 1002.8 TSR-limit values of q for SR ARQ, N = 102.9 ISR-limit values of q for SR ARQ, N = 1005.1 Stage mapping for round-robin multiplexing.. • • . . . . .5.2 Stage mapping for adaptive multiplexing . . .6.1 Retransmission and resequencing buffer sizes used in simulations for6.2 Optimal and quasi-optimal values of w for GBN ARQ in Channel 1..........6.3 Optimal and quasi-optimal values of w for GBN ARQ in Channel 2..,....,..6.4 Optimal and quasi-optimal values of w for GBN ARQ in Channel 3384545viiList of Figures1.1 Block diagram of an ARQsystem.31.2 Channel delay, N 51.3 Point-to-multipoint system 71.4 General multicast system 82.1 Buffer capacities required for some ARQ protocols 182.2 Samples of protocol operation for the PR scheme (N = 4, w = 2) 212.3 Samples of packets lost when an FOP is received in error . 242.4 Redundant packet counted among N — 1 packets lost due to buffer overflow (N = 3,. 242.5 Throughput performance of GBN ARQ for N = 10, FF,1 0.01 302.6 Throughput performance. of GBN ARQ for N = 10, Pp’,1 = 0.02 312.7 Throughput performance of GBN ARQ for N = 10, PF,1 = 0.05 322.8 Throughput performance of GBN ARQ for N = 10, FF1 = 0.1 332.9 Throughput performance of GBN ARQ for N = 10, FF2 = 0.0,0,3, and 0.5 342.10 Throughput curves for GBN ARQ, N = 100, FF1 = 0.001 352.11 Throughput curves for GBN ARQ, N = 100, PF,2 = 0.0,0.3, and 0.5 362.12 Throughput curves for SR ARQ, N = 10, FF1 = 0.05 . 402.13 Throughput curves for SR ARQ, N = 10, PF,i = 0.1 412.14 Throughput curves for SR ARQ, N = 10, PF,1 = 0.2 422.15 Throughput curves for SR ARQ, N = 10, PF1 = 0.4 432.16 Throughput curves for SR ARQ, N = 10, PF,2 = 0.0,0.1,0.2, and 0.5 443.1 Plot of highest values of o as a function of W1 for FDP with GBN ARQ andconvolutional coding 603.2 Plot of highest values of c as a function of W1 for FDP with GBN ARQ and RScoding . 61vu’3.3 Plot of highest values of a as a function of D1 for TDP with GBN ARQ andconvolutional 623.4 Plot of highest values of a as a function of D1 for TDP with GBN ARQ and RScoding. . . . . . . . .. 634.1 Block diagram of multiplexing system............ 664.2 Markov chain for four channel states. . 684.3 State diagram of semi-Markov process for round-robin multiplexing with go-back-NARQ. 744.4 Timing diagram for -r2 in the semi-Markov process for round-robin multiplexingwith go-back-N ARQ 754.5 State diagram of semi-Markov process for round—robin multiplexing withstop—and—wait ARQ 784.6 State diagram of semi-Markov process for adaptive multiplexing with go-back-NARQ 814.7 State diagram of semi-Markov process for adaptive multiplexing withstop—and—wait ARQ. . . . . . . . 845.1 State diagram of the semi-Markov process for round-robin multiplexing with GBNARQandw>0 905.2 State diagram of the semi-Markov process for adaptive multiplexing and GBN ARQwithw>0 935.3 State diagram of reduced state space representation 946.1 Throughput performance of ISR ARQ under round-robin and adaptivemultiplexing 1056.2 Throughput performance of GBN ARQ with w = 0, for Channel 1, underround-robin and adaptive multiplexing 1086.3 Throughput performance of GBN ARQ with w = 0, for Channel 2, underround-robin and adaptive multiplexing 1096.4 Throughput performance of GBN ARQ with w = 0, for Channel 3, underround-robin and adaptive multiplexing 1106.5 Throughput performance of GBN ARQ using quasi-optimal w, for Channel 1, underround-robin and adaptive multiplexing 111ix6.6 Throughput performance of GBN ARQ using quasi-optimal w, for Channel 2, underround-robin and adaptive multiplexing............. ...... 1126.7 Throughput performance of GBN ARQ using quasi-optimal w, for Channel 3, underround-robin and adaptive multiplexing. . 1136.8 Throughput performance of SW ARQ under round-robin and adaptive114B.1 Probabifity of successful packet sync as a function of h for various channel SNRs 123C,l (C.2) evaluated for different values of K and J 125E.1 Original semi-Markov process 132E.2 Equivalent semi-Markov process with reduced number of states 133xGlossaryABBREVIATIONSSome abbreviations used in the thesis are:A AdaptiveACK AcknowledgmentARQ Automatic Repeat RequestBCH Bose, Chaudhuri, Hocquenghem (code)FAX FacsimileFDP Frequency Domain PartitioningFEC Forward Error CorrectionFOP First Outstanding PacketFSK Frequency Shift KeyingGBN Go-Back-NHARQ Hybrid ARQHDLC High-level Data Link ControlHF High FrequencyISR Ideal Selective RepeatMCD Multiple Copy DecodingMACK Negative AcknowledgmentPR Postponed RetransmissionPSK Phase Shift KeyingQPSK Quaternary Phase Shift KeyingRR Round RobinRS Reed-Solomon (code)SNR Signal to Noise RatioSR Selective RepeatTDMA Time Division Multiple AccessTDP Time Domain PartitioningSYMBOLSThe common symbols used in this thesis are defined below.a Information data transmission rate.xiAverage number of packet transmissions per successfully transmittedpacket.7 Ratio of energy per symbol to noise power spectral density.yij Probability that the channel is actually in state j, given that it isestimated to be in state i,7’ Effective received signal-to-noise power ratio.6jj Kronecker delta function.Probability that the channel is estimated to be in state i, given that it isactually in state j.State of marked channel when complete channel state is c.Throughput efficiency of ARQ protocol.Probability that the receiver’s observation of the joint state N slots ago isestimated to be i, given that it is actually j.Probabifity of finding the channel in state j.Probabifity that the channel is estimated to be in state j.Tm, Tb Time spent in mode m; time spent in given state if the next state enteredis b., ‘2 Bit packing efficiency, in bits per second per Hz, of modulation schemeused over forward, feedback channel.Event that the channel is selected.Wi , Bit transmission rate over forward, feedback channeLB1 Size of retransmission buffer. In Chapter 3, length of blank time onforward channel.B2 Size of resequencing buffer. In Chapter 3, length of blank time onfeedback channel.D1,D2 Length of packet data field on forward, feedback channel.Probabifity that the transmitted packet is in joint channel state i, giventhat the channel N slots ago is estimated to have been in joint state j.Ji, J2 Number channel states in forward, feedback channel.K Number of channels.L1,L2 Total packet length on forward, feedback channel.xiiN Round-trip delay, measured in packets, from the start of packettransmission to when the corresponding acknowledgment is expected.Bit error probability.FE Symbol error probability.FF,1, FF,2 Post-decoding packet error probability over forward, feedback channel.pCi) pCi) Post-decoding packet error probability over forward, feedback channel,given that the channel is in state j.p1(i) Probability that the transmitted packet is received in error and is notFredundant, given that it is in channel state j.Pj Channel state transition probability.(N) N-step channel state transition probability.i3p(c) Probability that the transmitted packet is redundant given that theRchannel is in state c.Psync Probabifity of successful packet synchronization.Probabffity that a transmitted packet is successfully received and is notSredundant, given that it is in channel state i.q Number of levels in Weldon’s ARQ scheme.Qij Channel state transition probability corresponding to reversed Markovchain.Smallest time interval between successive start-of-transmission times fordata packets.Tij,im or Tik,1mn System (joint channel-protocol) state transition probabffity.Td Round-trip propagation delay over channel.U System (joint channel-protocol) state.w Retransmission delay parameter, measured in slots.Retransmission delay parameter, measured in service cycle periods.W Total frequency bandwidth available for both the forward and feedbackchannels.W1,W2 Frequency bandwidth of forward, feedback channel.XliAcknowledgmentThe format of this thesis is based on the Master’s thesis of Victor Wong, who gratefullyacknowledges the assistance of William Cheung in the formatting of his thesis.I would like to thank my fellow colleagues, for all their help and their company. Whileit would take too much space to list the names of all these people, four individuals deservespecial mention for generously imparting their vast knowledge of the UNIX operating systemand the various software packages that were needed to get the job done. Ed Casas and RonJeffery helped me get through many obstacles at the start of the program. Fortunately for me,I have always been able to count on their veritable successors, Dimitri Bouras and WilliamCheung, for continued assistance after their departure from the department. Finally, I wouldlike to thank my advisor, Prof. Cyril Leung, for the high quality and optimum quantity ofhis supervision.The research work for this thesis was supported in part by an NSERC operating grant, aScience Council of B.C. GREAT Award, and by a University of B.C. Graduate Fellowship.xivChapter 1 IntroductionThe primary subject of this thesis deals with the analysis and evaluation of multiplexingand automatic repeat request (ARQ) schemes in multiple-receiver systems with time-varyingchannels. In addition, two other issues on ARQ are also examined. Briefly, these relate toerrors in the feedback channel and a “unified” procedure for taking into account some of thedesign trade-offs in an ARQ system.The multiple-receiver system under consideration consists of a transmitter that sends datato several receivers. The quality of the communication channel between the transmitter andeach receiver changes over time and depends to a certain extent on the past channel quality.This kind of channel can offer some interesting possibifities in a multicast system, where dataintended for particular groups of receivers are sent from a central transmitter. A multiplexeris used to select which group is to be served at a given time. Now if the channel quality ofeach receiver varies over time, then the multiplexer may be able to improve its transmissionefficiency by an adaptive receiver selection scheme that is biased towards serving higher qualityover lower quality channels, Such an adaptive scheme is examined in this thesis for a specialcase of the multicast system, a multiple point-to-point system, where each group containsonly one receiver. The applications under consideration are presumed to require that thetransmitted data be received without error and in the correct sequence. This requirement isaccomplished through the use of an ARQ protocol.The effect of feedback channel errors on ARQ protocol performance is an issue that has notreceived much attention in the published research literature. It is well known that feedbackerrors will reduce the protocol’s throughput, but the nature and extent of this effect needs to beclarified in greater detail. Analytic and simulation results are presented, giving a quantitativeand qualitative characterization of feedback errors under certain assumptions. A modificationfor reducing the throughput loss due to feedback errors is proposed. It is applicable in generalto any continuous ARQ protocol.IChapter 1. Introduction 2The design of an ARQ protocol can require decisions on performance and resourcerequirement trade-offs between different design parameters such as the packet length, as wellas coding and modulation schemes. Of interest is the design of ‘good’ ARQ protocols underpower and bandwidth constraints. A description is given of a procedure for taking into accountthese various parameters, from which the resulting information data bit transmission rate canbe calculated, This transmission rate may be viewed as a measure of the “capacity” of an ARQsystem. It can be maximized for certain parameter values, subject to given constraints.Some basic concepts and commonly used terms are discussed in the next section, followedby a section on previous research work in the area, and finally by a section that summarizesthe contributions of this thesis, and describes how the rest of the thesis is organized.Li Preliminaries1.1.1 Reliable Data CommunicationA communication system can be viewed in its simplest form as consisting of a transmitter,a receiver, and a channel over which the transmitter sends information (data) to the receiver.Invariably, the original transmitted data will be corrupted by the channel (because of physicalcharacteristics such as noise and bandwidth limitations, among others) and consequently, maybe received in error. For applications such as voice (telephony), FAX and video transmission,there typically is some latitude in the amount of corruption to the received data which wouldstill be subjectively considered acceptable. However, there are other applications, such as filetransfer, where the transmitted data must be received without error. For these applications,the communication system must be able to transmit data ‘reliably’ in order to serve a usefulpurpose. As this thesis is concerned with reliable data transmission, “data” without any furtherqualification will, henceforth, refer to the type with stringent error control requirements.In practice, data transmission cannot ever be completely error-free since there is alwaysthe possibifity, however miniscule, that the received data can contain undetected errors. Thereason for the occurrence of undetected errors is treated in coding theory (e.g., [1, 2]); issuesChapter 1. Introduction 3Figure 1.1 Block diagram of an ARQ system.in that area are beyond the scope of this thesis. Hence, the term “error” will be used to denoteonly a “detected error”, unless qualified otherwise.10t2 FEC and ARQAn error control system can be organized into two general classes depending on whetheror not the transmitter retransmits data that have been received in error. In the first class ofsystems, there is no retransmission, and consequently, some form of error correction coding istypically used to reduce the number of errors in the received data to an acceptable level. Hence,it is commonly referred to as Forward Error Correction (FEC), although it can be thought of asencompassing applications where error correction coding may not be used if the data error raterequirements can already be met without the use of coding. In the second class, the transmittermakes use of information fed back from the receiver to correct detected errors by resending datareceived in error. The received data is not released to the application at hand until all errorshave been corrected. This class is referred to as Automatic Repeat Request (ARQ), reflectingthe iterative procedure wherein the receiver essentially requests retransmissions of corrupteddata. An ARQ system utilizes two channels between the transmitter and the receiver, one overwhich the transmitter sends data to the receiver, and another for feedback from the receiver.These are referred to as the forward and feedback channels respectively. A block diagramof a general ARQ communication system is shown in Fig. 1.1. In both FEC and ARQ, thetransmitted data must also be delivered to the final destination in the correct order.Incoming Data Delivered Data/ARQ SystemChapter 1 Introduction 4It should be noted that a feedback channel can also be used for purposes other thanfor sending retransmission requests. Channel quality information can also be sent over thefeedback channel, as is done with the adaptive multiplexing scheme (in this thesis) for time-varying channels. Another application that makes similar use of the feedback channel is anadaptive FEC scheme [3], where the transmitter changes the error-correcting capability inaccordance with the perceived channel quality.In general, data to be transmitted are usually divided into contiguous blocks which aresent out block-by-block. This is done for reasons as may arise for example, from practicalconsiderations in multiple-access, multiplexing, and networked environments. For purposes oferror-control, and with ARQ in particular, this division is done to facilitate the retransmissionof data received in error. Each data block is encapsulated by a number of fields to form a“packet”. Each packet must contain fields for numbering the sequence of packets and forparity bits of the error-detection code so that the data can be delivered (‘released’ from thereceiver) without error and in the correct sequence. There may also be fields for other usessuch as packet synchronization and addressing. Transmission time is usually divided intouniform intervals called “slots”, each of which can accomodate one packet.ARQ protocols fall into three general classes: stop-and-wait (SW), go-back-N (GBN), andselective-repeat (SR) [111. The basic operations of these protocols are typically described as follows. First, the round-trip channel propagation delay, N, is defined as the time, measured inpackets, between the start of a packet’s transmission and receipt of its corresponding acknowledgment (e.g., as shown in Fig. 1.2 for the case of N = 4). In SW ARQ, the transmitter sendsone data packet over the channel and waits for the arrival of its corresponding acknowledgment, which the receiver sends after the packet has been received and processed. A positiveacknowledgment (ACK) is sent if the packet is or has already been received without error.Otherwise, a negative acknowledgment (NACK) is sent back. The transmitter then eitherretransmits the packet if an ACK was not received, or transmits the next packet otherwise.In GBN and SR ARQ, the transmitter continues to send the next packets in its transmission1 Also called send-and-wait, reject, and selective-reject respectively.Chapter 1. Introduction 5Receiversequence while waiting for the receiver’s acknowledgments to return. For this reason, theyare called “continuous” ARQ protocols. With these protocols, it is possible for later packets (with ‘higher’ sequence numbers) to be correctly received ahead of earlier packets in thetransmission sequence (i.e., received “out-of-sequence”). With GBN ARQ, NACKs are sentfor these out-of-sequence packets. Hence, whenever a leading packet is received in error, thetransmitter has to resend not only the leading (or “first outstanding”) packet (FOP), but alsothe next N — 1 packets. With SR ARQ, the receiver has a resequencing buffer for storingout-of-sequence but correctly received packets before they can be released to the destinationin the correct order. ACKs are returned for each of these packets. If however, there is nospace for storing an incoming out-of-sequence packet in the buffer (a condition called “bufferoverflow”), that packet is lost and a NACK is sent back. Hence, the transmitter resends onlypackets that are received in error or are lost due to buffer overflow. In this thesis, a datapacket is said to be “completed” if it has been either released from the receiver or bufferedand pending release from the resequencing buffer (i.e., there is no need to retransmit it). Atransmitted packet that has not yet been completed is said to be “outstanding”.The decision as to whether FEC or ARQ is used typically depends on constraints imposedby the application. In general, one wants a communication system to deliver data as reliablyand as efficiently as possible. This would usually point to the use of an ARQ protocol.However, for applications such as real-time voice/video and some aspects of deep spacedata-collection telemetry, the retransmission iterations involved with ARQ may result inunacceptably long or uncertain time delays in the delivered data, In such cases, one is forcedN=4Figure 1.2 Channel delay, N.TransmitterChapter 1. Introduction 6to use FEC and to design the system so that data is delivered at some “acceptable” error rate.FEC can also be used in conjunction with ARQ, resulting in what is called a hybrid ARQ(HARQ) protocol, where error correction is used to reduce the number of retransmissions.There are two common types of HARQ, namely, Type I and Type II. With Type I HARQ,parity bits for error-correction are sent with the (re)transmitted packet. With Type II HARQ, thepacket is transmitted first without error correction, and parity bits are sent during subsequentretransmissions. Obviously, there can be combinations between these two types.t1,3 Point-to-Multipoint ARQThe discussion so far has described an ARQ system where one transmitter sends datato one receiver. Such an arrangement is usually called a “point-to-point” system. Another,more general, arrangement consists of one transmitter which broadcasts to several receivers(as shown in Fig. 1.3), where the requirements of error control and sequential delivery of datanow extend to all receivers. This is called a “broadcast” or “point-to-multipoint” system.Each receiver processes received packets and sends back acknowledgments in the same wayas in a point-to-point system. However, the transmitter’s operation changes somewhat onaccount of the multiple receivers. For each outstanding packet, an ACK is expected from eachreceiver. For any transmitted packet, a receiver is said to be “outstanding” if its correspondingACK has not yet been received. The acknowledgment status of outstanding packets for eachreceiver is stored by the transmitter in an “ack-outstanding list”. The retransmission proceduredepends on what information is stored in the ack-outstanding list. Suppose the list can storeacknowledgment status information from all receivers for the first m outstanding packets,o m N. Then ACKs are expected from only the outstanding receivers for the first mpackets, and from all receivers for retransmissions of the remaining packets (because theiracknowledgment status is not known), “Memoryless”, “limited memory” and “full memory”systems are terms used respectively for the cases where m = 0 (an ack-outstanding list is notused), 0 < m < N, and m = N.Chapter 1. Introduction 71,1.4 Multiplexing and Multicast SystemsThe “point-to-multipoint” system itself can be generalized into a “multicast” system,where multiple “point-to-multipoint” ARQ sessions operate in parallel among sets of multiplereceivers. Each set, or “multicast group”, can consist of anywhere from one receiver to all thereceivers in the system. More than one multicast group can be active at any given time anda receiver may also belong to more than one active group (i.e., the groups may overlap eachother). A general multicast configuration is shown in Fig. 1.4. ARQ transactions operateindependently between groups. A multiplexer is used to allocate system bandwidth amongmulticast groups if several of them are operating simultaneously. Bandwidth allocation isReceiversI•I•...,I.0•e•ii. II•Figure 1.3 Point-to-multipoint system.Chapter 1. Introduction 8typically done either in the frequency domain (e.g., each group is assigned a frequency band)or in the time domain (e.g., packet transmission time is divided into slots, which are assignedin a particular way so that there is transmission to no more than one group at any given slot).1,2 A Brief Summary of Related WorkARQ systems have been the subject of research for a long time. The following discussionis a summary of some of the preceding work. It serves as a starting point for identifying bothnew topics to examine as well as issues which have not yet been adequately addressed.ReceiversIEMulticast Group—Figure 1.4 General multicast system.Chapter 1. Introduction 9The basic concept of ARQ is so simple that it must have arisen with the advent of datacommunications, For example, HF teleprinter systems employing ARQ were used since thelate 1930’s [2]. An early survey of ARQ schemes appears in [4].1,2.1 AnalysisThe performance of the standard ARQ protocols has been examined in a number of papers.Queueing statistics for standard GBN and ideal selective repeat (ISR) ARQ are analyzed in[5, 6]. Some design issues for SR ARQ protocols are discussed in [7], while the throughputperformance of a finite-buffer SR ARQ scheme has been investigated in [8]. Analysis of theresequencing buffer occupancy and delay (for SR ARQ) can be found in [9—11], Recently, signalflow graphs have been used to analyze the throughput and delay of ARQ protocols [12].Analysis of multi-channel ARQ protocols can be found in [11, 13]. In a multi-channelsystem, packets are sent over parallel ARQ channels. ARQ protocols are typically analyzed forequilibrium conditions that extend over an infinite duration. Also of interest is the performanceof ARQ protocols over the period when a finite number of packets are to be completed [12, 14].Other assumptions that are often made include error-free feedback channels and a stationary,uncorrelated channel error process. A review of the previous work done on error-free feedbackchannels is given in Chapter 2, Non-stationary errors are typically modeled by a Markovprocess over a set of channel states which correspond to either a bit error (or packet error)probability [15—17], or the packet error events themselves [18, 19]. Other approaches haveused a Rayleigh fading channel model [20] or line-gap functions [16].1.2.2 SystemsWhen ARQ is used over packet-switched networks, transmitted packets may have totravel through several nodes between the source and destination. Some papers that haveevaluated ARQ protocols in these enviroments include [21—23]. A new window protocol foracknowledging groups of packets is proposed in [24]. ARQ schemes designed for use in halfduplex transmission environments have also been analyzed [25]. In [261, the performance ofSR ARQ is evaluated for the IEEE 802.2 Type-2 logical link protocol. Other issues related toChapter 1. Introduction 10networking can be found in [27]. ARQ protocols have also been analyzed for multiplexed [28]as well as TDMA [29] environments.1.2.3 Multi-copy TransmissionMany schemes for improving the performance of ARQ protocols have been proposed. Inone general method, the transmitter sends multiple copies of the same packet pre-emptivelyinstead of sending only one copy of each packet and waiting for the acknowledgment. Sastry[301 has examined the use of multiple-copy transmission for SW ARQ, and has proposed amodification to GBN ARQ, where the FOP is sent repeatedly (i.e., ‘stutter’ mode) when it hasto be retransmitted. Another modification to GBN ARQ makes use of some buffering capacityat the receiver [31], Towsley [32] has analyzed the performance of a stutter GBN protocol in asystem where new packets enter according to an arrival process. The last transmitted packet issent repeatedly when the queue is idle (i.e., while there are no incoming packets to transmit)and when there are no packets to retransmit.The earliest paper to propose a non-stutter multiple-copy scheme appears to be [331, whichconsiders the case of GBN ARQ. An adaptive multiple-copy scheme for finite-buffer SR ARQwas proposed by Weldon [34] in order to reduce the number of packets lost due to bufferoverflow. Further results on its analysis and optimization have been done in [35, 361. Therehave been earlier variations to SR ARQ, which avoid buffer overflow by switching to stuttertransmission or GBN ARQ operation when buffer overflow is imminent [37]. Multiple-copyARQ schemes are also discussed in [38—40].Copies of packets received in error can also be combined in order to reduce the numberof unsuccessfully decoded packets. This method is usually referred to as “code combining”,“memory ARQ” or “multiple copy decoding” (MCD), and may also be used in conjunctionwith soft-decision decoding. Some papers that discuss this approach include [41—51].1,2.4 Type-I HARQVirtually any kind of error-correction code can be used to implement a type-I HARQprotocol. Some of these schemes have been described in a number of papers. Majority-logicChapter 1. Introduction 11decoding of convolutional codes can be used for high-speed implementations at the expenseof coding gain [52]. This approach can also be used with a packet combining scheme [53].Adaptive type-I HARQ schemes have been proposed for both RS [54, 551 and puncturedconvolutional codes [31. An adaptive scheme that uses concatenation with multiple-copytransmission and soft-decision decoding has been proposed in [51],The amount of coding used for error correction can also be adjusted by using estimatesof the channel quality rather than basing it on the number of retransmissions. This approachhas been used in conjunction with both RS [54, 55] and convolutional codes [3].1.2.5 Type-Il HARQA number of type-Il HARQ schemes have been proposed. In [56], two schemes arediscussed, one involving the use of convolutional codes; in the other, a packet is divided intosub-blocks, each of which is encoded with an rate-i /2 code that has a Reed-Muller structure.Lin and Yu [571 have proposed a class of half-rate invertible codes suitable for HARQ. In [58],a class of linear codes suitable for parity retransmission was proposed. The same decoderstructure is used for decoding codewords formed from successively catenated parity bits. Theuse of this scheme for non-stationary channels has been analyzed in [59]. A similar concept,wherein Hamming codes are used in a ‘cascaded’ manner to encode sub-blocks comprisingthe data frame, is proposed in [60].One way of using the more standard coding schemes for adaptive parity retransmissionis to use some form of concatenation as described in [611 for extended BCH and Hammingcodes. Another way is to send in the first transmission only a subset of the parity bits from theoriginal code along with the information bits (i.e., the codeword is ‘punctured’), and to sendthe remaining parity bits in subsequent retransmissions [62, 63]. Such a procedure can be usedif the bits are punctured such that the code is “rate-compatible”. The use of this approach hasbeen subsequently discussed in [641 (for convolutional codes) and [651 (for RS codes).1,2,6 Code CombiningThe use of maximum-likelihood and soft-decision decoding for code combining has beenChapter 1. Introduction 12discussed in [45]. Code combining can also be used in conjunction with sequential decodingof convolutional codes [661. In [67], a partial-retransmission variation is described, wheresub-blocks of the encoded sequence are sent and combined with the received packet. Somecombining schemes have been considered for use in both type-I and type-Il HARQ withViterbi decoding of convolutional codes [68—72]. Type-Il HARQ schemes based on the use ofpunctured convolutional codes have been proposed in [64, 72—74].It should be noted that multiple-copy transmission schemes can be viewed as implementations of a repetition code. In that sense, it could be argued that they can be viewed as type-IHARQ schemes. Likewise, any scheme where the receiver combines retransmitted packetscould be viewed as a type-Il HARQ protocol, since the retransmitted packets could be considered as parity bits of a repetition code.1.2.7 Optimum Packet LengthThe packet length is a parameter that can affect the performance of ARQ systems. In[75], the optimum packet size that minimizes the expected amount of transmission timerequired to complete a message (counting retransmissions as well as acknowledgments) isdetermined after taking into account factors such as the message length distribution, channelerror characteristics, as well as overhead in the data and acknowledgment packets. Anoptimization along similar lines is also given in [76]. With HARQ, there is a trade-off betweenimproved error-correcting capability and overhead from parity bits. This issue has beenexamined for the case of BCH codes in [77]. Some adaptive schemes that change the packetlength according to prevailing channel conditions have also been proposed [78, 79].1.2.8 Point-to-multipoint ARQPoint-to-multipoint ARQ protocols have been the subject of fairly recent research work.A number of protocols for broadcast applications have been proposed and analyzed. Someschemes use a batched acknowledgment technique, where packets are grouped into frames,and acknowledgments are sent back for each received frame, each of which identifies whichpackets in the frame have been received correctly. These have been proposed in [80] and [81]Chapter El. Introduction 13for broadcast SW and GBN ARQ respectively. Two full-memory GBN ARQ protocols were proposed by Mase [82] for satellite applications. One scheme uses end-to-end acknowledgments(between ground stations), while another uses a tandem arrangement, where ARQ is used onboth the uplink as well as the downlink. In [83], the GBN ARQ protocol is examined for different amounts of memory in the transmitter’s ack-outstanding list. Memoryless and full-memorysystems are also discussed in [84] for both GBN and ISR ARQ. A broadcast ARQ scheme inwhich ACKs are not sent back [851 has been proposed for use in mobile radio environmentswhere receivers may be subject to deep fades due to shadowing, as well as in multiple-accessfeedback channels where collisions can occur among the receivers’ acknowledgments.Multiple-copy transmission of packets can also be used to improve the performance ofGBN ARQ for point-to-multipoint channels [86—88]. Broadcast versions of Weldon’s SR ARQscheme have been examined in [89, 90, 361. Delay and occupancy statistics at the resequencingbuffer for multiple receiver ISR ARQ systems are analyzed in [91]. Ammar [92] has proposeda scheme for improving the throughput of broadcast ARQ protocols by splitting the receiversinto multicast groups. HARQ schemes for broadcast applications have also been considered.These schemes involve the use of convolutional codes [901 as well as concatenated codes(using shortened Hamming codes) [17].1.3 Summary of ContributionsNew results presented in this thesis include the following:1. A simple method for reducing the deleterious effects of feedback errors on the throughputperformance of continuous ARQ protocols by using complete receiver state informationfeedback and by modifying the transmitter’s retransmission procedure.2. An analytic procedure for the unified treatment of trade-offs in various design options(e.g., modulation and coding schemes).3. Throughput analysis of multiplexing and ARQ schemes for non-stationary, multiple pointto-point systems with time-varying error processes. The effects of state-estimation errorsand feedback errors have also been included in the analysis. Furthermore, the modified reChapter 1, Introduction 14transmission procedure in item 1 is also extended to this system. An adaptive multiplexingscheme is proposed. This scheme is optimal when used with TSR ARQ.The remainder of this thesis is structured based on the items listed above. The morefundamental issues are addressed first, with feedback errors in Chapter 2, and the unifieddesign procedure in Chapter 3. Following these, the throughput of the multiplexed system isanalyzed in Chapters 4 and 5. The corresponding numerical results are discussed in Chapter6. Some general concluding remarks are then given in Chapter 7.Chapter 2 Some Aspects of ARQ ThroughputPerformance in the Presenceof Feedback ErrorsThis chapter discusses the effect of feedback errors in a stationary point-to-point channelunder some feedback information assumptions. It is shown that the deleterious effects offeedback errors on the throughput of continuous ARQ protocols can be greatly reduced by asimple modification in the retransmission operation, provided that the “complete state” of thereceiver is sent back with each acknowledgment.2.1 IntroductionIn many papers that analyze the performance of ARQ protocols, the feedback channel isassumed to be error-free (e.g., [30—32, 15, 37, 57, 34, 35, 39, 38, 18, 86, 68, 69, 90, 71, 73]).This assumption is typically made in order to simplify the analysis or the presentation ofresults. Some recent papers have included the effect of feedback errors in the performanceanalysis. As a first approximation, an ACK or NACK received in error is treated as thougha NACK was received. Hence, a data packet sent over the forward channel is considered tohave been successfully transmitted only if its corresponding acknowledgment is also receivedwithout error. This assumption was used in [19], and is referred to as the “simple productapproximation” in this thesis. In [12], a modified GBN ARQ protocol2 is considered, wherethe receiver sends back a sequence number, i, along with the ACK or NACK to indicaterespectively that all packets up to and including the ith or (i — 1)th packet have been correctlyreceived. The information contained in the acknowledgment can be used to update the statusof a previously transmitted packet whose acknowledgment was lost. It is assumed in thesetwo papers that an error in the feedback channel can only erase an ACK or NACK. In [59], adifferent feedback error process is considered, where an error changes an ACK into a NACK,or vice versa (i.e., the error is not detected). When a NACK is received as an ACK, a data2 As implemented in HDLC.15Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 16packet may be lost unless the transmitter realizes the error and retransmits the packet. Onthe other hand, an ACK incorrectly received as a NACK will cause a “spurious” or redundantretransmission of a correctly received packet.This chapter expounds on some aspects of feedback errors mentioned in [931. A modelfor ARQ protocols is developed and the nature of the feedback error process is examined inSections 2.2 and 2.3. Following this, a modification to the standard GBN and SR ARQ protocolsis proposed, analyzed, and compared with other schemes in Sections 2.4, 2.5 and 2.6.In this study, the following assumptions are made.1. Each acknowledgment packet contains error-detection bits such that it can be assumedthat all errors in the feedback channel are detected. Hence, feedback errors can only eraseacknowledgments.2. Packet errors in the forward and feedback channels occur independently within eachchannel as well as between the channels. The error rates for both channels are assumedto be stationary.3. New packets are always available to be sent out by the transmitter.2,2 A Buffer-Constrained Model for ARQ ProtocolsThe feasibffity of an ARQ protocol is constrained by both its processing complexity as wellas the available packet buffer capacities at the transmitter and receiver. The issue of processingcomplexity is difficult to quantify concisely, and may depend on the state of computingtechnology as well as on implementation issues and the desired data transfer rate. Hence,the following discussion will focus on the buffer capacity requirements of an ARQ protocol.At the transmitter, a retransmission buffer is used for storing outstanding (i.e., transmittedbut unacknowledged) packets for possible retransmission. At the receiver, a resequencingbuffer is used for storing packets that have been successfully decoded but still cannot bereleased in the correct order until other packets ahead in the sequence are successfully received.If processing complexity is not considered, the three basic ARQ protocols (SW, GBN, and SR)can be classified by the available buffer capacities. Let B1 and B2 denote respectively theChapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 17retransmission and resequencing buffer capacities (measured in packets). Suppose B1 = 1and B2 = 0. As a consequence of the restriction on B1, the transmitter cannot have morethan one outstanding packet at any given time. Hence, the transmitter has to stop (fromsending the next packet) and wait for the receiver’s feedback (in response to the transmittedpacket) before either retransmitting the packet or sending the next one. This is the operationof SW ARQ, Now suppose that B2 = U but B1 = N, where N is the propagation delay ofthe channel, measured in packets, from the start of packet transmission to the point when thecorresponding acknowledgment is expected to have been received and processed. As a resultof increasing B1 from 1 to N packets, the transmitter can now send the next N — 1 packets (inthe transmission sequence) during the intervening time before receiving the acknowledgmentfor the leading packet. If the leading packet is not successfully received, the next N — 1 packetscannot be released by the receiver even if they have been received without errors because theywould not be in the correct order. Moreover, they will have to be dropped because there isno space for holding them. Hence, all N packets have to be retransmitted whenever a leadingpacket is received in error, resulting in GBN ARQ. By using a resequencing buffer (B2 > 0), thenumber of dropped packets can be reduced, resulting in an attendant reduction in the numberof retransmissions. This leads to the SR ARQ protocol, where successfully received but out-of-sequence packets need not be retransmitted if they can be stored in the resequencing bufferbefore being released in the correct order. Buffer capacities for the three protocols are depictedin Fig. 2.1. The TSR ARQ protocol is the limiting case as B2 —* cc. In TSR ARQ, resequencingbuffer overflow does not occur (as there is always space for buffering packets), so that onlypackets received in error are retransmitted. There has been some interest in the analysis offinite-buffer SR ARQ protocols [34, 35, 42], By using Weldon’s bound [341 however, it can beshown that in many cases, the throughput attainable under TSR ARQ can be approached veryclosely by using SR ARQ with a resequencing buffer that is not enormously large.2.3 The Feedback ChannelThe feedback channel provides a means by which the receiver can send information backChapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 18Chann&Transmitter ReceiverForwardL Retransmission: Feedback ResequencngI ARQ SystemISWARQ[EELZNLIEIE IGBNARQSR ARQ liiiFigure 2.1 Buffer capacities required for some ARQ protocols.for use by the transmitter. For example, the information may take the form of acknowledgmentpackets to inform the transmitter of the completion status of transmitted data packets. Basedon this information, the transmitter attempts to deduce the receiver’s state, and adjusts itstransmission sequence accordingly. There are many possible acknowledgment schemes. Forthe purposes of analysis, these schemes can be differentiated on the basis of the amount andfrequency of the information sent back.Before proceeding further, some clarification of the terminology needs to be made. Consider a system where data packets are also being transmitted in the opposite direction. Thefeedback may be sent either separately, or “piggy-backed” over the data packets. In eithercase, the same physical charmel is used for sending both data packets and acknowledgments,Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 19leading to a possible ambiguity as to what exactly constitutes a forward or feedback channel.Throughout this thesis, the “forward” and “feedback” channels refer to conceptual constructsused for modeling and analysis. They do not necessarily refer precisely to correspondingphysical channels; it could very well be the case that the forward and feedback channels couldbe viewed as sharing a common physical channel.In most papers on ARQ, the receiver is assumed to send back an ACK or a NACK ineach slot to indicate whether or not the packet transmitted N slots earlier was successfullyreceived (referred to as “ACK I NACK feedback” in this thesis). The information fed back bya given acknowledgment generally pertains only to the corresponding received packet. Withcontinuous ARQ protocols, only limited information about other packets can be gleaned froma given ACK or NACK. For example, suppose that the resequencing buffer is managed suchthat space is reserved for the first B2 packets following the first outstanding packet (FOP). Itthen follows that an ACK to a given packet implies that all packets more than B2 positionsearlier in the sequence must also have been completed. In the absence of such informationobtained through indirect means, a packet whose acknowledgment is lost due to feedbackerrors will have to be retransmitted, at the risk of being wasted as it may in fact have alreadybeen received correctly.Some form of error-correction coding can be used to reduce the feedback error rate andhence, reduce the number of wasted retransmissions. Another scheme, which can also be usedin conjunction with coding, is to send more information back with each acknowledgment. Ofinterest here is a “complete feedback” scheme where each acknowledgment contains completereceiver state information. In the context of an ARQ protocol, the complete state of the receiverconsists of the FOP and the contents of its resequencing buffer. For SW ARQ, there is onlyone outstanding packet at any given slot. Hence, the complete state can be encoded in abinary valued message that indicates ‘transmit (new packet)’ or ‘retransmit’ (i.e., an ACK ora NACK), as there is no ambiguity in the sequence number. For GBN ARQ, the completestate is contained in the sequence number of the FOP, whereas for SR ARQ, the state of theresequencing buffer also has to be included. The modified GBN protocol [12] mentioned inChapter 2, Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 20Section 2.1 is an example of a GBN ARQ protocol with complete receiver state feedback. Notethat with ACK NACK feedback, the transmitter can attempt to deduce the complete receiverstate from the history of successfully received acknowledgments, but this may not always bepossible if the feedback channel can introduce errors,In the case where the complete receiver state is sent back with each acknowledgment, errorsin the feedback channel reduce the throughput performance of ARQ protocols by lengtheningthe time during which the transmitter is uncertain of the outcome of a transmitted packet.In other words, the propagation delay is effectively increased. The performance of an ARQsystem cannot improve with longer propagation delays. This is easily seen in both continuousand non-continuous (SW) ARQ. In the case of SW ARQ, consider the case where the receiverhas just successfully received a packet. The transmitter cannot proceed to send the nextpacket until it receives the corresponding ACK from the receiver. If that ACK is received inerror, then the transmitter must wait longer for a subsequent, correctly received ACK.3Withcontinuous ARQ, packets that have been received in error should be retransmitted as soon aspossible in order to reduce congestion in the resequencing buffer. However, the transmitter’sresponse time is physically limited by the propagation delay. Lost acknowledgments onlyincrease the length of time during which the transmitter must second-guess the outcomeof its transmissions. If it decides to retransmit a packet, it risks a wasted (i.e., redundant)transmission if the packet was in fact successfully completed. On the other hand, if it decidesto send a new packet when an earlier packet was in fact received in error, it may run the riskof buffer overflow, or increase the number of buffered packets, which in turn, increases therisk of buffer overflow in the future.2.4 A 11Postponed Retransmission” Variation forContinuous ARQ ProtocolsThe trade-off between possible packet waste with either a retransmission or a new packettransmission (when acknowledgments are lost) suggests that the throughput performance ofIn the case of unsuccessful data packet reception, it does not matter whether or not the corresponding NACK is received inerror; the transmitter wifi time out and resend the packet anyway.Chapter 2 Some Aspects of AR Q Throughput Performance in the Presence of Feedback Errors 21ReceiverX received n errorFigure 2.2 Samples of protocol operation for the PR scheme (N = 4, w 2).continuous ARQ protocols with complete receiver state feedback may be improved by delayingpacket retransmission when feedback errors occur. Instead of retransmitting a timed-outpacket immediately, the transmitter sends new packets in the meantime while waiting for asuccessfully received acknowledgment during the next in slots. A given packet is retransmittedonly either in response to corresponding feedback information successfully received duringthat interval, or after feedback errors occur on w or more consecutive slots starting from the slotwhen its acknowledgment times out. This scheme is referred to in this thesis as the “postponedretransmission” (PR) variation; in is referred to as the retransmission delay parameter. ThePR scheme has been alluded to in [12], which contains the throughput and delay analysis ofa variation to standard GBN ARQ for avoiding deadlocks (in the protocol operation) causedby feedback errors, Likewise, a simulation study of GBN and ISR ARQ with fixed time-outperiods (greater than N), as used for mobile radio applications, is presented in [201. Examplesof the PR scheme for N = 4 and in = 2 are depicted in Fig. 2.2. The resequencing buffer sizeTransmtterReceNerReceiverChapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 22must be increased to B1 = N + w in order to accomodate the increased maximum numberof outstanding packets. The case where w = 0 corresponds to the ‘standard’ ARQ operation,where packets are retransmitted immediately after timing out.Such a scheme with w> 0 might be suitable for GBN and finite-buffer SR ARQ if feedbackerrors occur much more frequently than errors in the forward channel. With TSR ARQ, thereis no possibffity for resequencing buffer overflow, so the transmitter can avoid reduiidantretransmissions by continuing to send new packets until an error-free acknowledgment arrives.In principle, TSR ARQ will not be affected by feedback errors in the limit as w — oo so long asthe feedback error rate is Tess than unity. However, under the assumption of complete receiverstate feedback, the amount of information transmitted in each acknowledgment is unboundedbecause the resequencing buffer occupancy can be infinitely large.2.5 Throughput AnalysisThe throughput, i, is given by l/i3, where /9 is the average number of packet transmissionsper successful packet completion (including redundant transmissions). Expressions for /9 arederived in this section for some ARQ protocols, under the assumption that the completereceiver state information is contained in each acknowledgment.For SW ARQ, the following variation is considered, where the transmitter repeatedlysends copies of the packet over the channel (i.e., ‘stutters’) until it knows that the packet hasbeen completed. This variation is considered since it results in improved throughput overthe standard SW protocol with no additional loss except for more transmitter power usage.Let Pp’,1 and Pp’,2 denote respectively the post-decoding packet error rates in the forward andfeedback channels. The average number of transmissions is given by00 00,(1— PF,1)PF,2 1)iJrF1i=1 F,2 i=O (2.1)—FF,1 PF,2—1v+ +1—Pp’ i—PF2where the first term gives the minimum number of slots needed to transmit a single packet,while the second and third terms count the number of additional transmissions due respecChapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 23tively to data packet errors and to feedback channel errors after the data packet has beenreceived correctly.With GBN ARQ, the analysis is complicated by the occurrence of redundant packettransmissions, but a reasonably good approximation can be derived as follows. For any givenpacket, is calculated by counting all receptions from the first instance when the packet isreceived as an FOP, and adding to that a fraction of any redundant packet received arisingfrom consecutive feedback errors that occur on acknowledgments sent after its completion.Consider a given packet at the point when it has become the FOP. It is received for thefirst time since becoming an FOP. Each time it is received in error, at least N — 1 of the nextpackets in sequence are lost because any additional, new packet sent as a result of consecutivefeedback errors4 will also be lost. Let Y denote the approximate average number of theseadditional new packets. For each unsuccessful reception of the FOP, N — 1 + Y packets are lostand the FOP is retransmitted (see Fig. 2.3 for the case of N = 4 and w = 3). Now supposethat the FOP has just been completed. Redundant retransmissions will occur only after itscorresponding acknowledgment and the next w — 1 acknowledgments are received in error, atwhich point, there will have been N — 1 + w outstanding packets. Any of these packets couldbe an FOP and those redundant packets will already be counted among the lost packets if oneof these packets is received in error. An example is shown in Fig. 2.4 for the case of N = 3 andw = 1. These redundant packets do not have to be counted unless all of the next N — 1 + wpackets are successfully received consecutively after the given FOP is completed. Let Z denotethe approximate average number of redundant retransmissions counted as part of the FOP’stransmissions when this condition is satisfied. The first redundant retransmission is counted asa whole, but only half of the second retransmission is counted because it occurs when the next(i.e., second) packet’s acknowledgment is received in error. Likewise, only a third of the thirdretransmission is counted. This continues until the (N + w — 1 )th retransmission, after whichonly 1/(N + w)th of each retransmission is counted, since the retransmissions cycle back again,starting with the given FOP. (At any given time, there can be no more than N + w outstanding“ Which can occur when w> 0.Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 24ReceiverX received in errorFigure 2.3 Samples of packets lost when an FOP is received in error.X received in errorFigure 2.4 Redundant packet counted among N — 1packets lost due to buffer overflow (N = 3, w = 1).packets.) The mathematical expression that summarizes these arguments is then given byGBN11(N)F,l(Y)+”+ (1 + FFl + Pl +. — PF,l)ZPF,l(N + Y) + (1 — p)N+WZ(2.2)ReceiverReceiverReceiverTransmitter=1+1— PF,1Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 25where7 r n2 nwI =FF,2+FF,2+”+rF,2(2.3)=FF,2L 1\ —rF,2/andN+w-1 pw+i pN+2wF,2+P2 (24)i (N+w)(1—PF)’The forward and feedback packet error rates in the simple product approximation, P,1 andare given by= 1 — (1— PF,1)(1 — PF,2) (2.5)and= 0. (2.6)For TSR ARQ, the existence of redundant transmissions also makes an exact analysissomewhat complicated. However, a fairly good approximation that improves with increasingw is given byISR‘—F,i(2.7)where Z is given by (2.4). For finite-buffer SR ARQ, an approximate expression for thethroughput can be obtained through the use of Weldon’s bound. A description of Weldon’sadaptive SR ARQ protocol can be found in [34, 35, 90]. In this protocol, the resequencingbuffer size is given by B2 = q(N — 1), where q 0 is an integer. Consider the case wherethe feedback channel is error-free. The throughput is lowerbounded by assuming that thenumber of buffered packets grows by N — 1 each time an FOP is received in error. This isan upper bound on the buffer occupancy “growth rate” because not all of the next N — 1transmissions will consist of new packets; some of them could be retransmissions of otherpackets received in error. As a consequence of the upper bound, the resequencing buffer isconsidered to be full after the qth retransmission. Thereafter, buffer overflow is assumed tooccur on subsequent unsuccessful retransmissions. An approximate expression for 3 that takesinto account redundant transmissions due to feedback errors can be obtained by consideringChapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 26two cases, depending on whether the given packet is completed before or after buffer overflowoccurs. If buffer overflow occurs before the packet is completed, the protocol is assumed tobehave like GBN ARQ, and the result obtained previously for GBN can be used to count thenumber of subsequently transmitted packets. On the other hand, if the packet is completedbefore buffer overflow occurs, then the expression for Z can be used to count the number ofredundant retransmissions. The approximation is expressed asq—1 q—1WSR1+Z,1+GBN+(1_PF1) F),1 Z(28)1_pq /F,1 pqi p z1—F,1’GBN — F,1It is useful mainly for calculating approximate values for B1 and B2 that would be requiredin order for the throughput to approach that of ISR ARQ. Note that the case where q = 0corresponds to GBN ARQ, while the limit as q —* corresponds to ISR ARQ. When FF,2 = 0,this expression reduces to that given in [34, 35] for the case of single-copy transmission (i.e.,using the same notation in those papers, n = 1, i = 1,. . . , q).2.6 Numerical ResultsThroughput values of SW ARQ, calculated using (2.1), for N = 10 and different combinations of FF,i and FF,2, are given in Table 2,1g. The throughput of SW ARQ is affected mostlyby the channel delay. Because of the way in which the protocol operates, its throughput cannever exceed 1/N, As can be seen, the forward and feedback packet error rates in the rangeFor mobile radio applications where the channel is subjected to Rayleigh fading at an average carrier-to-noise ratio of 15dB, the bit error rate with noncoherent FSK is approximately 0.03 [94]. Therefore, with no coding, packet error rates of 0.1 orhigher are not unreasonable. Furthermore, the packet error rate may tend to be higher in the feedback direction than in theforward direction if the transmitter’s power is much greater than the receiver’s transmission power, as may be the case with abase station sending packets to a mobile receiver.Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 27shown have only a marginal effect on throughput performance.FF2FF10.0 0.01 0,02 0.05 0.1 0.20.0 — 0.1 0.1 0.099 0.099 0.0980.01 0.1 0.1 0.1 0.099 0.099 0.0970.02 0.1 0.1 0.1 0.099 0.099 0.0970.05 0.099 0.099 0.099 0.099 0.098 0.0970.1 0.099 0.099 0.099 0.098 0.098 0.0970.2 0.098 0.097 0.097 0.097 0.097 0.095Table 2.1 Throughput of SW ARQ, N 10.The performance characteristics of GBN ARQ are shown in two sets of plots for N = 10and N = 100, For all simulations in this chapter, confidence intervals at the 99% level wereevaluated for all data points, but for the sake of clarity, are omitted unless they appreciablyexceed the height of the data points’ markers. In Figs. 2.5 through 2.8, the throughputs forN = 10 are plotted as a function of FF,2 for PF,1 = 0.01,0.02,0.05 and 0.1. Theoretical resultsobtained from (2.2) are shown for w = 0, 1,4 and for the optimum value of w (that minimizes(2.2) for channel parameters at the given data point). Also shown is the throughput given bythe simple product approximation. Corresponding results from simulations are given for bothACK I NACK and complete feedback. From the graphs, it can be seen that the simple productapproximation is overly pessimistic when compared to results obtained from simulations (forACK I NACK feedback and w = 0). By contrast, (2.2) shows fairly good agreement withcorresponding simulation results for small to moderately high feedback error rates. Largerdeviations can be seen at higher feedback error rates for small values of w (e.g., w = 0 andw = 1). For w = 0, the throughput for ACK NACK feedback is only slightly less thanthat for complete feedback. With ACK NACK feedback, it appears that some throughputimprovement is possible from the use of w > 0 over w = 0 if Pp,1 is not large (e.g., Figs. 2.5and 2.6). For larger values of FF1, there is more to gain from retransmitting without furtherChapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 28delay (Le., w = 0) than from trying to obtain more information from ACK NACK feedbackwhile running the risk of losing more packets due to buffer overflow (e.g., Figs. 2.7 and 2.8).Fig. 2,9 compares the throughput performance as a function of Pj for N = 10 andPF,2 = 0.0, 0.3 and 0.5. It can be seen from the graph that if complete feedback is used withthe optimal w’s, the throughput for FF,2 = 0.3 and 0.5 is only slightly less than that for an error-free feedback channel (PF,2 = 0). On the other hand, there can be a substantial throughputreduction for w = 0. The theoretical results are in good agreement with those obtained bysimulation for optimal w, but not for w = 0 at high feedback error rates. As shown before,the throughputs given by the simple product approximation are much too conservative. Theoptimal w’s for complete feedback are not expected to be optimal for ACK I NACK feedback,and this can be clearly seen where the corresponding throughput for ACK NACK feedbackis less than that for w = 0. Optimal values of w (in the sense of maximizing (2.2)) are givenin Table 2.2.The performance characteristics for GBN ARQ at N = 100 are qualitatively similar tothose at N = 10, as can be seen in Figs. 2.10 and 2.11. Corresponding optimal values ofw are given in Table 2.3. Fig. 2.11 also shows that when the optimal w’s are used, there isvirtually no reduction in throughput at high feedback error rates from that for an error-freefeedback channel.Lu and Chang [12] have also analyzed GBN ARQ with complete feedback. It shouldbe noted that their analysis may not be exact (and the paper does not indicate whether ornot that is indeed the case). Their methodology (based on signal flow graphs) produced arather complicated expression for the throughput, even after simplifications were made bysetting PF,1 = P2.6 At any rate, numerical results obtained from the expressions given intheir paper are shown in Tables 2.4 and 2.5 for N = 10 and 100, along with correspondingresults from simulations and (2.2). As can be seen in the tables, there could be a problem withtheir calculation. For w = 0, their calculation appears to give results that are too conservative,6 Chuang [201 has noted that the use of signal flow graphs for an exact throughput analysis (of an ARQ protocol) can becomevery tedious when the feedback channel can introduce errors,Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 29whereas for w > 0, there appear to be clearly erroneous values where the throughputs aregreater than 1. It is quite possible that the source of the errors could be either the constructedsignal flow graph or simply a typographical error in the throughput expression, rather thanfrom the methodology itself. Their paper discusses only the methodology along with someapplications, and does not present any numerical data, On the other hand, the theoreticalresults obtained using (2.2) are in good agreement with those obtained from simulations. Itcan also be seen from the tables that the throughput hardly changes between the differentvalues of w. This appears to be the case whenever the value of FF,1 becomes comparable toor exceeds PF,2.Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedbaclc Errors 3010.9 EEEEx+“Ux +O8 — \ +-x_\NN \ Xfl7 N \N\\+N.\\0.60.5 -0,4 -0.3- CRSIFB (w=4) (theo.)CRSI FB (w=1) (theo) — - — - — - — -CRSI FB (w=0) (theo.) -CRSI FB (opt. w) (theo.) — — — -02 ACKNACK FB (w=4) (sim.) +ACKINACKFB (w=1) (sim.) -ACKINACK FB (w=0) (sim.)ACKINACK PB (opt. w) (sim.)CRSI FB (w=4) (sim.)0 1 - CRSI FB (w=1) (sim.)CRSI FB (w=0) (sim.) <>CRSI PB (opt. w) (sim.) 0simple product approx.0hill I102 1o1Feedback Channel Packet Error RateFigure 2.5 Throughput performance of GBN ARQ for N = 10, Pp’,i = 0.01.Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 3110.90.8 -x + -.-0.7—\\ -\0.6 \\NX \0.5 -x0.40.3complete feedback (w=4) (theo.)complete feedback (w=1) (theo.) — - — - — - —-:complete feedback (w=0) (theo.)-complete feedback (opt. w) (theo.) — — — -02 ACKINACK feedback (w=4) (sim.) +• ACKINACK feedback (w=1) (sim.) —ACKINACK feedback (w=0) (sim.)ACKINACK feedback (opt. w) (sim.) xcomplete feedback (w=4) (sim.) D0 1 complete feedback (w=l) (sim.)complete feedback (w=0) (sim.)complete feedback (opt. w) (slim) 0simple product caic,0I 11111 I102 101Feedback Channel Packet Error RateFigure 2.6 Throughput performance of GBN ARQ for N = 10, = 0.02.Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 320.7xxxxxcomplete feedback (w=4) (theo.)complete feedback (w=1) (theo.) — - — - — - — -:complete feedback (w=0) (theo.)complete feedback (opt. w) (theo.)ACKINACK feedback (w=4) (slim) +ACKINACK feedback (w=1) (sim.) —ACKINACK feedback (w=0) (sim.)ACKINACK feedback (opt. w) (sim.) xcomplete feedback (w=4) (slim) Licomplete feedback (w=1) (slim)complete feedback (w=0) (slim)complete feedback (opt. w) (sim.)simple product caic.I I IFeedback Channel Packet Error Rate— —.-x,.,. j+‘..+j0.60.50,4 -0.3 -0.20.1 -00102 10’Figure 2.7 Throughput performance of GBN ARQ for N = 10, FF,i = 0.05.Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 330.5- --—.x —+0,4-x + —x +0.3-x0.2 -CRSIFB (w=4) (theo,)CRSIFB(w=1)(theo.)CRSIFB(w0)(theo.) -CRSIFB (opt. w) (theo.) — — -ACKINACK FB (w=4) (sim.) +ACKINACKFB (w=l) (sim.) -ACKINACK FB (w=0) (sim.)0.1- ACKINACK FB (opt. w) (sim.)CRSI FB (w=4) (sim.) UCRSI FB (w=1) (sim.) ACRSI FB (w=0) (sim.)CRSI FB (opt. w) (sim.) 0simple product approx.0I 11111 I102 10_iFeedback Channel Packet Error RateFigure 2.8 Throughput performance of GBN ARQ for N = 10, PF,1 = 0.1.Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 341 (N)ACK FB (BKER = 0.5) (w=0) (sim.) -CRSI FB (w=0) (sim.) •+ (N)ACK FB (opt. w) (slim.)CRSI FB (opt. w) (slim)o 9 - x CRSI FB (w=0) (theo.) — - — - —+ ‘ CRSIFB (opt. w) (theo.)simple product approx.‘(N)ACK FB (BKER = 0.3) (w=0) (sim.) <>CRSI FB (w=0) (sim.) •o -(N)ACK FB (opt. w) (slim) ++ CRSI FB (opt. w) (sim.) A•CRSI FB (w=0) (theo.)• CRSIFB(opt.w)(theo.)•simple product approx. — - —o 7 - - --.. CRSI FB (error-free) (sim.) 0--S.,. . CRSI FB (theo.) —IX +\•0.6__\•\::- \‘•\0.5 - \. ‘;..\\x \ \,\\ ,.+ \,\\0.4-+‘\EEi0 102 10’ 100Forward Channel Packet Error RateFigure 2.9 Throughput performance of GBN ARQ for N = 10, FF2 = 0.0, 0.3, and 0.5.Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 3510,9Nv.8NN\\4U.! \\.\\ +0.6 \\0.50.4- CRSIFB (w=4) (theo.)CRSIFB (w=1)(theo,)CRSIFB(w0)(theo,) -CRSI FB (opt. w) (theo.) — — — -03 ACKANACK FB (w=4) (slim) +ACKINACK FB (w=1) (sum) -ACKINACK FB (w=0) (sim.)ACKINACK FB (opt. w) (slim)CRSI FB (w=4) (slim) Li0 2 - CRSI FB (w=1) (sim,)CRSI FB (w=0) (sim.)CRSI FB (opt. w) (slim) 0simple product approx.0.1 -0 I I I102 10’Feedback Channel Packet Error RateFigure 2.10 Throughput curves for GBN ARQ, N 100, FF1 = 0.001.Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 361(N)ACK FB (BKER 0.5) (w=0) (sim,)CRSI FB (w=0) (slim)CRSI PB (opt. w) (slim)09(N)ACK FB (opt. w) (sim.)CRSIFB(w=0)(theo.)CRSIFB (opt. w) (theo.)simple product approx.0.8-(N)ACK PB (BKER = 0.3) (w=0) (sim.) K>CRSI FB (w=0) (slim)I (N)ACK PB (opt. w) (sim.) +CRSI PB (opt. w) (sim.) ACRSIFB (w=0) (theo.)CR51 FB (opt. w) (theo.)simple product approx. — - — - -CRSI FB (error-free) (sim.) 0CRSI PB (theo,)N0,6- •I0.5 T\‘s0.4 1sss\S0,30.20.10I ii iii0 102 10_iForward Channel Packet Error RateFigure 2.11 Throughput curves for GBN ARQ, N = 100, FF2 = 0.0, 0.3, and 0.5.Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 37FF2FF1‘ 0.0 0.01 0.02 0.05 0.1 0.2 0.3 0.4 0.50.001 0 7 9 13 16 23 30 40 520,002 0 7 9 12 15 23 30 39 550.005 0 7 9 12 15 22 30 39 550.01 0 7 9 12 15 22 30 40 520.02 0 8 9 11 16 22 29 39 510.05 0 7 8 11 15 21 27 36 420.1 0 7 8 11 12 12 11 10 100.2 0 0 0 0 0 0 0 0 00.3 0 0 0 0 0 0 0 0 00.4 0 0 0 0 0 0 0 0 00.5 0 0 0 0 0 0 0 0 0Table 2.2 Optimal values of w for GBN ARQ, N = 10.FF2FF1‘ 0.0 0.01 0.02 0.05 0.1 0.2 0.3 0.4 0.50.001 0 7 9 12 16 22 31 41 520.002 0 7 9 11 16 22 30 39 520.005 0 7 9 11 15 22 30 39 530.01 0 7 9 11 15 22 28 36 510.02 0 7 8 11 14 20 27 36 450.05 0 0 0 0 0 0 0 0 00.1 0 0 0 0 0 0 0 0 00.2 0 0 0 0 0 0 0 0 0Table 2.3 Optimal values of w for GBN ARQ, N = 100.Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 38w=0 w=1 w=2 w=3 w4FF1Eqn. Eqn. Eqn. Eqn. Eqn.Sim. [12] Sim. [12] Sim. [121 Sim. [12] Sim. [12]PF,2(2.2) (2.2) (2.2) (2.2) (2.2)0.01 0.900 0.901 0.773 0.908 0.908 2.331 0.908 0.908 3.946 0.908 0.908 5.652 0.908 0.908 7.4160.02 0.818 0.819 0.628 0.829 0.830 2.175 0.829 0.830 3.742 0.829 0.830 5.405 0.829 0.830 7.1310.05 0.641 0.642 0.395 0.652 0.653 1.774 0.653 0.654 3,212 0.653 0.654 4.744 0.653 0.654 6.3560.1 0.464 0.465 0.236 0.468 0.470 1.284 0.469 0.471 2.516 0.470 0.471 3.840 0.470 0.471 5.2560.2 0.283 0.283 0.119 0.276 0.281 0.715 0.280 0.281 1.562 0.280 0.281 2.516 0.281 0.281 3.5620.3 0.189 0.189 0.071 0.179 0.185 0.428 0.182 0.183 0.981 0.183 0.183 1.636 0.183 0.183 2.3710.4 0.130 0.130 0.045 0.119 0.126 0,268 0.122 0.124 0.623 0.122 0.124 1.058 0.123 0.123 1.5560.5 0.090 0.091 0.028 0.080 0.087 0.170 0.082 0.085 0.395 0.082 0.084 0.676 0.083 0.084 1.000Table 2.4 Comparison between calculated throughputs for CBNARQ from Eqn. (2.2) and from Eqns. (21)-(27) of [121, N = 10.w=O w=1 w=4PF,1,Eqn. Eqn. Eqn.Sim. [121 Sim. [121 Sim. [12]PF,2(2.2) (2.2) (2.2)0.01 0.497 0.497 0.249 0.497 0.497 1.477 0.497 0.497 5.6200.02 0.327 0.329 0.141 0.327 0.329 1.037 0.327 0.329 4.4620.05 0.158 0.160 0.060 0.158 0.160 0.516 0.159 0.160 2,7150.1 0.083 0.083 0.029 0.082 0.082 0.250 0.083 0.082 1.5410.2 0.038 0.038 0.013 0.037 0.038 0.100 0.038 0.038 0.695Table 2.5 Comparison between calculated throughputs for GBNARQ from Eqn. (2.2) and from Eqns. (21)-(27) of [121, N = 100,Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 39The throughput characteristics for SR ARQ for N = 10 are shown in Figs. 2.12 through2.16, Similar plots for N = 100 appear qualitatively similar and are not shown for the sakeof brevity. Values of w and q for which the throughput (given through 2.8) is within 99.9%of that achievable by ISR ARQ (referred to as the “ISR limit” values) are given in Tables 2.6to 2.9 for N = 10 and 100. Simulations were used to confirm the results and are shownfor N = 10, The simulations for w = 0, 1 and 4 were done with B2 = 50. In Figs. 2.12through 2.15, the throughput is plotted as a function of PF,2 for PF,1 = 0.05,0.1,0.2 and 0.4.From the figures, it can be seen that the throughput performance for SR ARQ with completefeedback improves with increasing w. With w = 4, the throughput is already very close to thatachievable by ISR ARQ in the parameter range shown. On the other hand, the throughputwith ACK NACK feedback remains virtually unchanged across the corresponding values ofw. The theoretical results for complete feedback are in good agreement with those obtainedthrough simulations when PF,2 is small, but show noticeable deviations when FF,2 becomeslarger. These deviations appear to decrease with increasing w (cf. w = 4). For small values ofPF,i, the simple product approximation appears to give good throughput estimates for the caseof ACK I NACK feedback. In Fig. 2.16, the throughput performance is plotted as a function ofPF,1 for PF,2 = 0.0, 0.1,0.2 and 0.5, Simulation results are shown for both the TSR limit andw = 0, along with theoretical calculations for TSR ARQ and the simple product approximation.The throughput for the case of w = 0 with ACK I NACK feedback is greatly reduced as FF2increases. On the other hand, it is possible for the throughput with complete feedback toapproach that of TSR ARQ if appropriate (e.g., TSR limit) values for B2 and w are used. Thesimple product approximation gives a good throughput estimate for ACK I NACK feedbackwith w = 0 for small Pp’,1 and PF,2.Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 401S..5.’0.9 -\\\\\\\\0.8-\\\\\\\\\\\ \.\\0,7 - \ “CRSI FB (w=4) (theo.)CRSIFB (w=1) (theo,)-CRSI FB (w=0) (theo.)J.U CRSI FB (ISR) (theo.)ACKINACK FB (w=4) (sim.) +ACKINACK FB (w=1) (sirn.)ACKINACKFB (w=0) (slim)CRSI FB (w=4) (sim.) DCRSI FB (w=1) (sim.)CRSI FB (w=0) (slim)CRSI FB (ISR limit) (sim,) 00.5 simple product approx.0.4 I I I I I102 10_iFeedback Channel Packet Error Rate\Figure 2.12 Throughput curves for SR ARQ, N = 10, PF,1 = 0.05.Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 4110.9\•SS0.8-‘5\\\\\\ \.0.7- \complete feedback (w=4) (theo.)complete feedback (w= 1) (theo.)complete feedback (w=0) (theo,)complete feedback (TSR) (theo.)ACKINACK feedback (w=4) (sim,) +ACKINACK feedback (w=l) (sim.) xACKINACK feedback (w=0) (sim.)complete feedback (w=4) (sim,) Ccomplete feedback (w=1) (sim,)complete feedback (w=0) (slim) •complete feedback (ISR limit) (sim,) 00.5 simple product calc,0.4 I I102 10’Feedback Chaimel Packet Error RateFigure 2.13 Throughput curves for SR ARQ, N = 10, FF1 = 0.1.Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 4210.90.8 ——-—-—---—..--..--- .--... -‘S5—-e\‘-5’- 5’0.7-C -‘\“\ \\\ \.\\\\0,6 ‘complete feedback (w=4) (theo.)complete feedback (w= 1) (theo.)complete feedback (w=0) (theo.)complete feedback (ISR) (theo.)ACKINACK feedback (w=4) (sim.) +ACKINACK feedback (w=l) (sim.) xACKINACK feedback (w=0) (sim.)0.5- complete feedback (w=4) (sirn.)complete feedback (w=l) (sim.)complete feedback (w=0) (sim.)complete feedback (ISR limit) (sim.) 0simple product caic.0.4 I I I I102 10’Feedback Channel Packet Error Rate\Figure 2.14 Throughput curves for SR ARQ, N = 10, FF1 = 0.2.Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 430.70.6— — —------------\t0.5-\.\\\\0.4 -CRSIFB (w=4)(theo,)CRSI FB (w=1) (theo,)CRSI FB (w0) (theo.)CRSI FB (ISR) (theo.)ACKINACK FB (w=4) (sim.) +ACKINACK FB (w=1) (sim.)0.3 - ACKINACK FB (w=0) (sim.)CRST FB (w=4) (sim.) UCRSI FB (w=1) (sim,)CRSI FB (w=0) (sim,) eCR51 FB (TSR limit) (sim.) 0simple product approx.0.2 I I I I I102 10_iFeedback Channel Packet Error Rate\Figure 2.15 Throughput curves for SR ARQ, N = 10, FF1 = 0.4.Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors10.9 ------------ - NN440.8 - -0.3N\\\\_\\\\ \+\\ \ \\_\\\\Forward Channel Packet Error Rate0.7 -0.60.50.40.20.10\ACKINACK FB (FB error rate = 0.5) (w=0) (sim.)CRSI FB (FB error rate = 0.5) (TSR limit) (sim.)ACKINACK FB (PB error rate = 0,2) (w=0) (sim.)CRSI PB (PB error rate = 0,2) (TSR limit) (sim.)ACKINACK PB (PB error rate = 0.1) (w=0) (sim.)CRSI PB (PB error rate = 0,1) (TSR limit) (sim.)CRSI FB (error-free) (ISR limit) (sim.)CRSI PB (error-free) (TSR) (theo.)simple product approx. (error-rate = 0.5)simple product approx. (error-rate = 0.2)simple product approx. (error-rate = 0.1)xEl+.0102 10’Figure 2.16 Throughput curves for SR ARQ, N = 10, Pp,2 = 0.0, 0.1, 0.2, and 0.5.Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 45FF2FF10.0 0,01 0.02 0.05 0.1 0.2 0.3 0.4 0.50.01 0 1 2 3 4 5 8 11 160.02 0 1 1 2 3 4 5 7 100.05 0 1 1 2 3 4 5 7 100.1 0 1 2 2 3 5 7 9 130.2 0 1 1 2 3 4 6 8 100.3 0 1 1 2 2 4 5 7 100.4 0 1 1 2 2 4 5 7 100.5 0 1 1 2 2 4 5 7 9Table 2.6 TSR-limit values of w for SR ARQ, N = 10,___________PF,2FF10.0 0.01 0.02 0.05 0.1 0.2 0.3 0.4 0.50.01 0 1 1 2 3 4 5 7 100.02 0 1 2 2 3 5 7 9 120.05 0 1 1 2 3 4 6 8 110.1 0 1 2 2 3 5 7 10 130.2 0 1 1 2 2 4 5 7 100,3 0 1 1 2 2 4 5 7 100,4 0 2 2 3 4 7 10 7 90.5 0 1 1 2 3 4 5 7 10Table 2.7 TSR-limit values of w for SR ARQ, N = 100.Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 46___________PF,2FF10.0 0.01 0.02 0.05 0.1 0.2 0.3 0.4 0.50.01 1 1 1 1 1 1 1 1 10.02 2 2 2 2 2 2 2 2 20.05 3 3 3 3 3 3 3 3 30.1 3 3 3 3 3 3 3 3 30.2 5 5 5 5 5 5 5 5 50.3 7 7 7 7 7 7 7 7 70.4 9 9 9 9 9 9 9 9 90.5 12 12 12 12 12 12 12 12 12Table 2.8 TSR-limit values of q for SR ARQ, N = 10,FF2FF10.0 0.01 0.02 0.05 0.1 0.2 0.3 0.4 0.50.01 2 2 2 2 2 2 2 2 20.02 2 2 2 2 2 2 2 2 20.05 3 3 3 3 3 3 3 3 30.1 4 4 4 4 4 4 4 4 40.2 7 7 7 7 7 7 7 7 70.3 9 9 9 9 9 9 9 9 90.4 11 11 11 11 11 11 11 12 120.5 15 15 15 15 15 15 15 15 15Table 2.9 TSR-limit values of q for SR ARQ, N = 100.Chapter 2. Some Aspects of ARQ Throughput Performance in the Presence of Feedback Errors 472.7 Summary and Concluding RemarksThe results of this chapter show that the adverse effects of feedback errors on the through-puts of GBN and SR ARQ protocols can be greatly reduced if the PR scheme is used witha suitable value for w. This scheme works best when complete receiver state information issent in each acknowledgment, which typically is not an unreasonable burden for the case ofGBN ARQ since the information is contained in the sequence number of the FOP. However,this may not be the case with SR ARQ if the resequencing buffer size becomes very large.In practice, it may then be feasible to send back only some subset of the receiver state at atime, In such circumstances, it would be interesting to investigate the effect of subset size andselection on throughput performance.Chapter 3 A Unified Approach to Data TransmissionRate Analysis for ARQ SystemsThis chapter discusses ARQ protocol performance, as measured by the effective databit transmission rate delivered by the communication link to the end user. It contains anexpanded version of the material discussed in [93]. A unified treatment is given for a numberof parameters, including bandwidth and power constraints, as well as optimization of thepacket length and code selection (from a set of error-correction codes). Results from Chapter2 are used to evaluate the ARQ throughput.3,1 IntroductionIn general, many factors need to be considered in the design of a data communicationlink. These include choices of suitable coding and modulation schemes, as well as the ARQprotocol itself. As far as efficient communications is concerned, the primary goal is to designa system that has the highest transmission rate possible given the feasible choices and theconstraints at hand. To accomplish this goal in a systematic manner, the characteristics ofdifferent components in the system need to be considered altogether. For example, the choiceof a modulation scheme affects the symbol error and symbol transmission rates. Codingschemes for error correction, along with the packet length, both have an effect on the resultingpacket error rate and on the fraction of overhead per packet. The packet length and the symboltransmission rate will, in turn, affect the channel delay of the ARQ protocol (i.e., the delay,measured in packets). Both the channel delay and packet error rates (in the forward andfeedback channels) will have an effect on the throughput of the ARQ protocol. Finally, thedata link’s transmission rate, as measured by the amount of error-free data delivered per unittime, will depend on not only the symbol transmission rate, but also on the packet utilizationefficiencies as measured by both the ARQ throughput and the amount of overhead per packet.These interdependencies point to the need for a systematic procedure that considers as many48Chapter 3. A Unified Approach to Data Transmission Rate Analysis for ARQ Systems 49design parameters as possible in one unified and coherent treatment. Such a procedure wouldbe particularly useful when a large number of designs are being evaluated.The unified approach (as discussed in this chapter) can provide at least these two followingbenefits.1. More accurate performance analysis. ARQ protocols are typically analyzed under certainsimplifying assumptions. Usually, the feedback channel is assumed to be error-free whilebandwidth requirements for sending acknowledgments are ignored. These assumptionsare useful for simplifying the analysis as well as the presentation of results. However,there may be cases in which a more accurate analysis is desirable, such as mobile radioapplications, where those assumptions may no longer be valid.2. Simplified and organized design of efficient ARQ protocols. Using mobile communicationsagain as an example, current trends point to increased traffic levels (leading to largerbandwidth requirements), and more portability, which imposes more severe transmitpower constraints. Hence, it is more likely than not that the demand for more efficienterror-control schemes will increase in the future. The design of efficient ARQ schemesinevitably involves engineering decisions on trade-offs from gains and losses betweendifferent parameters. It would be useful to have a design procedure that can take allthe trade-offs into consideration, preferably in a manner where decisions could be madeautomatically in an optimization program.It will be seen later on that the design procedure leads to an optimization of, among otherparameters, the length of data packets transmitted over the forward channel. The problem ofdetermining the optimal packet length for an ARQ system has been discussed in a number ofpapers. In [75, 76], the problem of finding the packet length that minimizes the time wastedin retransmissions and acknowledgment delay is considered for a variety of ARQ protocolsand system characteristics. In [77], the optimization problem is discussed in the context ofa stop-and-wait ARQ protocol with the use of BCH codes for error correction. The packetlength optimization problem in this chapter differs from what has already been done in thatChapter 3. A Unified Approach to Data Transmission Rate Analysis for ARQ Systems 50other parameters are being jointly optimized while taking into account a more general set ofconstraints.A description of the model and assumptions is given in Section 3.2, followed by theperformance analysis in Section 3.3. Numerical examples to illustrate applications of the designprocedure are then given in Section 3.4, which also discusses the results of the optimizations.Finally, some concluding remarks are given in Section 3.5.In this chapter, only fairly standard modulation, coding and ARQ schemes will beconsidered so as to keep the focus on the methodology.3.2 System ModelConsider a data communication system subject to the following constraints:1. A fixed bandwidth, W, to be shared by both the forward and feedback channels,2. A fixed amount of transmission power at the transmitter and receiver.3. A round-trip propagation delay, Tpd. defined as the total propagation time in the forwardand feedback channels (excluding packet transmission times).The system is to be used to provide error-free and sequential transmission of packetized datato a receiver. Each packet contains a data field as well as a fixed amount of overhead. Anacknowledgment packet is sent back by the receiver for each received data packet. Availableto the designer are a family of ARQ, modulation and error-control coding schemes. For eachdesign, the bandwidths assigned to the forward and feedback channels are chosen such thatthe average data bit transmission rate7, ct, is maximized.Two bandwidth allocation schemes are considered. In the first scheme, the bandwidth Wis partitioned between the forward and feedback channels, which operate in full-duplex mode.In the second scheme, the bandwidth is shared by both channels in the time domain, wherethe transmitter and receiver operate in half-duplex mode. These schemes will be referred toas frequency-domain and time-domain partitioning (FDP and TDP) respectively.for a transmission system that operates as a continously busy serverChapter 3. A Unified Approach to Data Transmission Rate Analysis for ARQ Systems 513,3 Data Transmission Rate AnalysisDetails of the partitioning schemes as well as some modulation and coding schemes aredescribed in this section. Some analytic results are obtained, and these are then combinedwith the throughput analysis of Chapter 2 to give an expression for a.3.3.1 Preliminary CalculationsThe convention in this chapter is to use a subscript of 1 or 2 to indicate that a givenparameter refers to the forward or to the feedback channel respectively.The transmission power constraints are expressed here indirectly, in terms of an equivalentreceived signal-to-noise power ratio (ER-SNR), which is computed by considering the noisepower over the total bandwidth W. It is given by, Si= NW’ (3.1)where Si is the received signal power and N0 is the noise power spectral density. In otherwords, the amount of transmission power is that which would produce-y for the noise andpropagation characteristics at hand.For FDP, the total bandwidth of one ARQ link, W, is partitioned into two bands of widthsW1 and W2, where W1 + W2 = W. Hence, the received SNR for a given W and -y is W/W.Each modulation scheme has a bit-packing efficiency, ç, which gives the number of bits persecond that can be transmitted per Hz. For a given amount of bandwidth, the bit transmissionrate, w, isI W , FDP=Wj ,TDP. (3.2)Note that although w. for TDP is higher than that for FDP, data and acknowledgment packettransmissions will have to be time multiplexed, whereas that is not required with FDP. Let= 2k denote the size of the symbol set, where k is the number of bits per symbol. Thenthe symbol transmission rate, w,, of an M--ary modulation scheme is then given by w = w/k.The ratio of the received symbol energy to the noise power spectral density is given as follows,179,FDp=N0 =-ye, TDP,Chapter 3. A Unified Approach to Data Transmission Rate Analysis for ARQ Systems 52Each packet is assumed to consist of a synchronization sequence, some header/trailer overhead(for addressing, sequence numbering, protocol control, and error-detection code), a data field,and a ‘blank’ time, denoted respectively by s, ILj, D and B. The term B is included to allowfor a tolerance margin between packets, so as to accomodate small variations in the propagationdelay, as well as other implementation issues such as the transmitter’s turn-on/turn-off time.Furthermore, with TDP under certain conditions (as discussed in Appendix A), continuouspacket transmission between the forward and feedback channels may be restricted to certainvalues of the total data and acknowledgment packet length. For certain design combinations,it may not be possible to construct a packet with a fixed data field such that the lengthrestriction is satisfied exactly. In such cases, B is extended to lengthen the packet so asto allow continuous transmission, if it is desirable to do so (i.e., better performance overnon-continuous transmission). The header/trailer and data fields are encoded by an error-correction code of rate R. If a convolutional code is used, then 6 tail bits are appended, thenumber of which is equal to the memory order of the code. The total packet length, includingthe blank time, can be expressed as= +H +D ++ B, (3.4)where the encoded part of the packet, L — — B (measured in bits), is assumed to berounded up to the nearest integer multiple of k.For TDP, the ARQ protocol must operate in such a way that the receiver is not sendingacknowledgments while the transmitter’s data packets are being received. Conversely, thetransmitter should not be sending data packets while the receiver’s acknowledgments arebeing received. If the ARQ protocol is to transmit packets continuously under TDP, L1 andL2 must be chosen so that collisions do not occur at either the transmitter or receiver. It isshown in Appendix A that, for a direct point-to-point link, this occurs whenTpd = mLtot, (3.5)Chapter 3. A Unified Approach to Data Transmission Rate Analysis for ARQ Systems 53where Lt0t = L1 + L2 and m is a positive integer. For TDP, the smallest time interval betweensuccessive start-of-transmission times for data packets is given byf Ltot Tpd = mLtotT LO + Tpd. otherwise, (3.6)where the first and second cases correspond to continuous and non-continuous transmissionmodes respectively. For FDP, T = L1. Note also that if FDP is used, and an acknowledgmentis sent back for each received data packet, then the system must be designed such that theacknowledgment transmission rate is not less than the data packet transmission rate.3.3.2 Synchronization Issues and Modulation SchemesThe issue of synchronization is of great importance in any data transmission system sincethe meaning of the entities being received, be they bits or packets, can only be derived whenthe receiver knows their positions in time. Synchronization problems occur at different levelsin the communications hierarchy [95—971. If a coherent demodulation scheme is being used,then carrier synchronization has to be considered. Furthermore, bit (symbol) synchronizationis required for the demodulated baseband data symbol sequence. Packet synchronization mustalso be accomplished in order for the receiver to be able to successfully identify the differentconstituent fields from the symbol sequence. Further up in the hierarchy, there are networksynchronization issues as well.A comprehensive treatment of synchronization is beyond the scope of this thesis. Nevertheless, some elements of this broad issue are discussed here and considered to a limitedextent because acquisition of synchronization affects system performance independent of otherparameters such the packet length and error-correction coding. Henceforth, some simplifying assumptions are made for the sake of brevity; in practice, these can be replaced by moresophisticated models or by empirical data. First, it is assumed that there is perfect carriersynchronization, so that one can use expressions for bit and symbol error probabilities thattake only the channel noise into account. At low SNR’s however, the increasingly frequentloss of carrier synchronization can have a deleterious effect on the symbol error probabffity[98]. Second, bit synchronization is assumed to be successfully acquired within the packet’sChapter 3. A Unified Approach to Data Transmission Rate Analysis for ARQ Systems 54synchronization sequence, and maintained continuously while the rest of the packet is beingreceived, Third, packet synchronization is assumed to be performed after bit synchronizationis declared (cf. “DCD first” method [991). A simple expression for the probabifity of successfulpacket synchronization, Psync. is derived in Appendix B.Let P, i = 1,2, denote the probability that a packet is unsuccessfully decoded, withoutconsideration of packet synchronization issues. An expression for the probability of unsuccessful packet decoding, PF, that also takes into account packet synchronization, but assumesthat the outcomes of synchronization and (post-synchronization) packet decoding are independent, is then given byPF=1—Psync(1—P). (3.7)It is assumed that the packets are interleaved such that symbol errors within any givenpacket are uncorrelated. For the case where modulation and error-correction coding areperformed separately, Pfr can be computed for the given code from the symbol or biterror probabifities (FE or Pb) of the modulation scheme [98]. For example, the bit errorprobabffities of some common binary modulation schemes, assuming perfect carrier andsymbol synchronization, are listed as follows.— f Q (/‘) , coherently-detected PSK—3.8, noncoherently-detected FSK,where-y = Es/No. For QAM with a square constellation,2(1-L’) [()27] (39)where L is the number of amplitude levels in one dimension, and assuming that a Gray codeis used to assign a sequence of log2 L bits to an L—ary symbol. Note that this formula reducesto the case of QPSK for L = 2. Symbol error probabilities for some non-binary modulationschemes are given below.FE 2Q (/si) , coherently detected M-ary PSK— M (310)FE = ( l)i () e ,noncoherently detected M-ary FSK,Chapter 3 A Unified Approach to Data Transmission Rate Analysis for ARQ Systems 55where the corresponding bit error probabilities can be computed [98] by using= M/2, M-ary FSKFE M — 1 (3.11)1 EM , M-ary PSK (FE << 1).og23.3.3 Packet Error Probability with Convolutional CodingOnly the case of hard-decision Viterbi decoding will be considered, If a convolutionalcode is used for error-correction, Fj is upperbounded byP < 1 — (1 evt)1, (3.12)where evt is the error event probabffity of Viterbi decoding and 1 is the number of trellislevels. For a code of rate b/V. 1 = (L — s — B)/V. evt is bounded [100] byevt (3.13)d=dfreewhere dfree is the free distance and {ad} is the weight spectrum of the code. Fd is theprobability that a wrong path at distance d is selected and is given by Pmaj(d)i where()pii _p)3,dodd3Fmaj(d) ()pi(i_p)d_i (3.14)3—p)]2,d even.3.3.4 Packet Error Probability with Reed-Solomon CodesReed-Solomon (RS) codes are a subclass of nonbinary BCH codes [2]. For any (n, k) RScode, the minimum distance d is given by d = n — k + 1, where m is the block length and lvis the number of information symbols (or characters) per block. Codes with this property arecalled maximum-distance-separable or MDS codes. Assuming bounded-distance decoding, up tot symbol errors can be corrected in each RS block, where=[d;1j = [m;kj. (3.15)Let q denote the size of the RS character set. If g M-ary modulated symbols are packed intoeach RS character, then q = M, The block length, n, is q — 1 characters long, but smallerChapter 3. A Unified Approach to Data Transmission Rate Analysis for ARQ Systems 56values can be obtained by shortening the code8, in which case d remains unchanged. Let Pde,Pge and Fe denote respectively the error probabilities of the RS block, the RS symbol, and theconstituent modulated symbol. Then, for a t-error correcting RS code,de()- [ () Pe(1 - Pge)j (3.16)wherePge=l-(lPe)2. (3.17)The H + D bits in each packet are encoded into L (u, k) RS blocks, where= [j, (3.18)and L is the total number of RS information symbols to be encoded. It is given byH+D 1log2M (3.19)gThe remaining bits (less than k RS symbols long), if there are any, are encoded in a shortened,(m — (k — k’), k’) code, where k’ = — L0k, This is the case when Lg mod k 0. The packetlength (in bits) resulting from this encoding scheme isL —s + Lang log2 M + B, Lg mod k = 0 (3 20)s + (L0n + [n — (k — k’)])glog2M + B, otherwise,while the corresponding packet error probability is given by= f 1 — (1 — de()) , Ls mod k = 0 (3.21)1 — (i— Fde(n)) [i— de( — (k — , otherwise.3.3.5 ARQ and Data Transmission RateFor the three standard ARQ protocols (SW, GBN, TSR), the number of packets thatcan be transmitted before an acknowledgment is expected is denoted by N. For FDP,N= E (Tp + L2) /Li1 + l which counts the transmission time for a given packet and theelapsed number of transmitted packets before its corresponding acknowledgment is completelyTypically done by setting a selected number of information symbols to zero in the encoding procedure. These symbols neednot be transmitted and are substituted back in during decoding.Chapter 3. A Unified Approach to Data Transmission Rate Analysis for ARQ Systems 57received. In non-continuous mode TDP, the transmitter has to wait for the correspondingacknowledgment to its transmitted packet to arrive before it can transmit again. Withcontinuous mode TDP on the other hand, the additional number of packets which can betransmitted after sending a given packet, in the span of the round-trip propagation delay, ism, as can be seen from (3.5). Hence, N = 1 or m + 1 with non-continuous or continuoustransmissions respectively.For any ARQ protocol with throughput , the average data bit transmission rate, o, isthen given by— D11 L1 — D11L 1 C Cwhere Di/Li gives the proportion of data bits per packet and Li/Ta is the duty cycle betweensuccessive packet transmissions.3.4 Numerical ResultsThe optimization procedure used in this section depends on whether FDP or TDP is used.In either case, 2, H1, H2 and D2 are fixed at certain assumed values. Naturally, D1 mustbe at least one bit long. The optimization is performed for a given combination of ARQ andmodulation schemes.With FDP, the optimization proceeds by searching over combinations of Wi and W2. Foreach of these allocations, the corresponding values for wj and yj are computed, and D1 is thensearched over a range of values. For each value of B1, the error-correction codes for the dataand acknowledgment packets are selected by choosing the combination that maximizes c whilenot causing the resulting data packet transmission rate, wi/Li, to exceed the acknowledgmentrate, w2/L. B1 and B2 are set to certain fixed minimum values.With TDP, the optimization search covers a range of values of B1. For each B1, the error-correction codes are searched. Then for each code combination (for the forward and feedbackchannels), B1 is selected as follows. First, it is set to a given minimum value, and the resultingc is computed. If continuous transmission is not possible (i.e., the data and acknowledgementChapter 3. A Unified Approach to Data Transmission Rate Analysis for ARQ Systems 58packets will overlap past a certain error margin), then it is set to the next (longer) value thatallows continuous transmission, and a is recomputed. The value of B1 corresponding to thehigher value of a is then selected for the particular value of D1 and the given code combination.As an example, consider the optimization of a design based on GBN ARQ and QPSKmodulation under the following assumptions. The values for W and Tpd are 100 kHz and0.5 seconds respectively, while the lengths of the packet’s synchronization, overhead andminimum blank time are s1 2 = 80 bits, H1 = H2 = 80 bits and B1 B2 = 0.01 secondsrespectively. D2 is assumed to be 16 bits long. The performance of this system is evaluatedfor-y = —1,0, 1,2,3,5 and 7 dB, with -y always set 3 dB lower than -y The use of puncturedconvolutional codes as well as shortened RS codes will be examined here. For the case ofconvolutional coding, the codes are selected from a family of memory-order m = 6 puncturedconvolutional codes of rates 2/3, 3/4, 4/5, 5/6, 6/7 and 7/8, derived from a rate-1/2 code.The weight spectra for these codes can be found in [1011 and [1021. With RS coding, codesobtained from using g 1 through 4 are considered. For each resulting q—ary code, the valuesof n that are searched are q — 1, 3(q — 1)/4 and (q — 1)/2. For each n, the correspondingvalues searched for k are 3n/4, 7n/8 and n. Each (n, k) code can be viewed as a shortened(q — l,k + (q — 1)—n) code.For FDP, W1 was searched over [5,95] kHz in 5 kHz increments, and at 1 kHz increments insections near a maximum or where large changes in a occur. D1 was searched over [100, 10000]in 100 bit increments for both FDP and TDP. A practical value of = 1.5 was assumed [1031.The optimizations for both FDP and TDP also searched the retransmission delay parameter,w, from w = 0 through 8 in increments of 2. For these values, the dependence of a on Wi andD1 for FDP and TDP can be seen in Figs. 3.1 and 3.3 respectively for the case of convolutionalcodes, and in Figs. 3.2 and 3.4 for RS codes.It can be seen for the case of FDP that the value of a can be characterized roughly by anincrease followed by a decrease, with increasing W1. At high SNRs (i.e., -y = 3 to 7 dB), aAs might be the case when the transmitter power is much higher than the receiver’s transmission power (e.g., a base stationsending data to a mobile unit).Chapter 3. A Unified Approach to Data Transmission Rate Analysis for ARQ Systems 59increases with W1 up to a point where W2 is not large enough to allow a sufficiently powerfulcode to be used to keep FF2 small; at a certain point, W2 can become so small that theacknowledgment transmission rate can no longer keep up with the data packet transmissionrate, At lower SNRs, the reduction in a at higher values of Wi occurs primarily because 71decreases as a result of the increasing bit transmission rate, and the error correction codes inthe searched range are unable to compensate for the higher bit error rates. With convolutionalcoding, it can be seen in Fig. 3.1 that some curves contain two maxima. In the neighborhood ofthe first maximum (at the smaller W1), a rate-2/3 code was selected for the data packet, whereasaround the second maximum (at the higher W1), a rate-l/2 code was selected. It appears thatthe rate-2/3 code initially provides some improvement in a until the bit error rate becomestoo high. At that point, a rate-1/2 code is not immediately selected because the overhead fromits additional parity bits cannot be sufficiently compensated for by the reduced packet errorprobabifity. Hence, the rate-2/3 code is used until the rate-l/2 code is selected, after which aincreases up to the second maximum. For FDP in general, it is difficult to characterize furtherthe behavior of a with Wi in simple terms because of counter-acting effects from the forwardchannel’s bit transmission and bit error rates, both of which increase with W1.For TDP, sawtooth patterns can be seen in both Figs. 3.3 and 3.4. For the data usedin this example, continuous transmission results in higher data transmission rates than non-continuous transmission. As D1 increases, L1 is adjusted (through B1) so that continuoustransmission is maintained. At certain values of D1, the use of a small value for B1 is notsufficient enough to make L1 satisfy the condition for continuous transmission (3.5); a muchlarger value of B1 is required. The sudden and large increase in overhead (from B1) causes acorresponding decrease in the value of a, although a would still be higher than if the systemwere to operate in non-continuous mode. In Fig. 3.3, smaller sharp declines in a can be seenfor-y = 5 dB, and -y = 7 dB. This behavior coincides with a change in the selected code froma lower- to a higher-rate code to accomodate the increased D1 without having to drasticallylengthen L1. The reduced overhead in parity bits is offset by a higher data packet error ratethat lowers the throughput. This can sometimes result in a lower value of a.Chapter 3. A Unified Approach to Data Transmission Rate Analysis for ARQ Systems12060IC/-17! //1//I /•01K/ ...a-’02/ /id/_WIForward Channel Bandwidth (kHz)Figure 3.1 Plot of highest values of c as a function ofWi for FDP with GBN ARQ and convolutional coding.fwdSNR=7dBfwdSNR=5dBfwdSNR=3dBfwdSNR=2dBfwdSNR= 1dBfwdSNR=OdBfwdSNR=-ldBfbck SNR = 4dBfbckSNR=2dBfbckSNR=OdBfbck SNR= -1dBfbck SNR = -2dBfbck SNR= -3dBfbck SNR = -4dB/,0—---3-------a-----A---S0’5’‘..-,0.& ø_,“ /100806040200A’/A-“A-ATh\\A\\A\/\\0 20 40 60 80 100IChapter 3. A Unified Approach to Data Transmission Rate Analysis for ARQ Systems 61fwd SNR = 7dB fbck SNR = 4dBfwdSNR=5dB fbckSNR=2dBfwdSNR= 3dB fbckSNR=OdBfwdSNR=2dB fbck SNR.= -1dBfwd SNR = 1dB fbck SNR = -2dBfwdSNR=OdB fbck SNR= -3dBfwdSNR=-ldB fbckSNR=-4dB-----0-------B------A-----.--1201008060402000\\N20 40 60 80Forward Channel Bandwidth (kBz)Figure 3.2 Plot of highest values of c as a functionof Wi for FDP with GBN ARQ and RB coding.100WiChapter 3. A Unified Approach to Data Transmission Rate Analysis for ARQ Systems 62120100806040200Length of Data Field (kbits)Figure 3.3 Plot of highest values of a as a function ofD1 for TDP with GBN ARQ and convolutional coding.Chapter 3. A Unified Approach to Data Transmission Rate Analysis for ARQ Systems 63C120100806040200Length of Data Field (kbits)Figure 3.4 Plot of highest values of c as a functionof D1 for TDP with GBN ARQ and RS coding.Chapter 3. A Unified Approach to Data Transmission Rate Analysis for ARQ Systems 643,5 Concluding RemarksA procedure for designing efficient ARQ protocols under joint bandwidth and powerconstraints has been described in this chapter. It is an attempt to provide a more unifiedapproach to ARQ system design by taking into account a number of factors that could affectsystem performance, such as the effects of errors and bandwidth allocations on both theforward and feedback channels, and the use of particular modulation and coding schemes.The procedure is relatively easy to implement on a computer for use as a tool in optimizingsystem design.Chapter 4 Multiplexed ARQ: ThroughputAnalysis, Part IIn this chapter, a model is developed for a slotted time division multiplexing system usedto assign transmissions over a set of time-varying channels. Two schemes, a “round-robin”and an adaptive multiplexing scheme, are studied for three standard ARQ protocols (stop-and-wait, go-back-N, and ideal selective repeat). In round-robin multiplexing, transmissionslots are assigned periodically to each channel. With the adaptive scheme, the multiplexerselects at each time slot, the channel whose state has the lowest retransmission probability. Thethroughputs of the three ARQ protocols under these multiplexing schemes are analyzed in thischapter. For GBN ARQ, the analysis will focus only on the case where the retransmission delayparameter (Chapter 2), w, is zero. This corresponds to the usual retransmission procedure,where a packet is retransmitted immediately after it times out. When w > 0, the transmittermay wait up to w additional slots before retransmitting a timed-out packet. This case isanalyzed in Chapter 5. Numerical results for these multiplexing and ARQ schemes, includingGBN ARQ with w = 0 and w> 0, are presented in Chapter 6.41 IntroductionThe performance of FEC/ARQ communication systems under non—stationary channelconditions has been previously examined in a number of papers. In [181, the throughputfor go-back-N (GBN) ARQ is derived for the case where packet error events are modeledby a Markov process. That analysis has recently been extended in [19] to include the effectsof feedback errors (using what amounts to the simple product approximation) and selectiverepeat ARQ. Vucetic [31 has discussed the use of punctured convolutional codes for adaptiveFEC and ARQ over a channel whose bit error rate varies over time. In [72], the throughputsof some HARQ schemes are evaluated for the case of a two-state Markov chain where a biterror rate is assigned to each state. The throughput performance of a multiplexing system65Chapter 4. Multiplexed ARQ: Throughput Analysis, Part I 66Receiver1Receiver* 2Channel K-]CerChannel KReceiverKis analyzed in the context of a time-varying channel model similar to that used in [15]. Thischapter contains an expanded treatment of the material discussed in [104].Consider a data communication system in which a slotted time-division multiplexer servesa number of users (receivers). An ARQ protocol is used for error control with each receiver,as shown in Fig. 4.1. One example might be a base station sending data packets over aradio channel shared by a number of mobile users. Each packet is destined for a particularmobile and the communication channel to each mobile is subject to differing time-varyingattenuation levels which change slowly over several packet lengths. A simple multiplexermight serve the users in a cyclic “round-robin” fashion. However, if there are significantvariations in the quality of the channels, it may be possible to improve efficiency by using anadaptive multiplexer that serves in each time-slot that user whose channel is judged to be theChannel]ARQARQChannel 2feedback channelforward channelSelectorARQARQFigure 4.1 Block diagram of multiplexing system.Chapter 4. Multiplexed ARQ: Throughput Analysis, Part 1 67best (with ties broken by random selection10). A comparison of the throughput performanceis given for these two multiplexing schemes, as used in conjunction with SW, CBN and ISRARQ. The effects of imperfect channel estimates and feedback chaimel errors are also includedin the analysis.4.2 System ModelThe system consists of a multiplexer that controls the transmission of data packets to Kreceivers. For each receiver, an ARQ protocol is used for error control. It is assumed that eachreceiver always has a new packet available for transmission. The quality of the communicationchannel between the transmitter and a given receiver is quantized into Ji and J2 states in theforward and feedback directions respectively. Both forward and feedback state spaces (S1and 52) are combined into a joint state description defined as follows. The joint state space,5, containing J states, is formed by taking elements from the product state space 51 x 52(of size J1 J2). A packet is said to be transmitted in the joint state (1, m) if it is receivedin forward channel state 1, and if the feedback channel is in state m at the time slot whenthe corresponding acknowledgment is expected. The forward and feedback channel statesdepend on a number of factors. In general, the effects of these factors will not only vary overtime, but may also occur at different times because of the propagation delay in. the forwardand feedback directions. For example, the propagation path from transmitter to receiver willchange as the pair move relative to each other. Furthermore, their new positions may alsocontain local sources of interference. In order to simplify the channel model, a discrete-timeMarkov process is used to describe the variations of the joint channel state over time, wherestate transitions occur at the beginning of each slot, and the lumped effects of those factorsare contained in the transition probability matrix,‘ii ‘l2i 2 P2j, (4.1)Fj Fj2 Pjj10 One variation not considered here is for ties to be broken by selecting the transmitter which has not been selected the longesttime, This scheme would tend to reduce the number of in-ifight packets.Chapter 4. Multiplexed ARQ: Throughput Analysis, Part I 68where P1, denotes the probabifity that the joint state in the next slot is j given that the statein the present slot is i. An example for J = 4 states is shown in Fig. 4.2. The quality ofthe channel in any state i = (1, rn), 1 E {1, 2,. . . , J1}, m E {1, 2,. .. , J2}, is associated witha post-decoding probability of unsuccessful packet reception in the forward and feedbackdirections. For each channel state i = 1,. .. , J, these probabffities are denoted by P and Prespectively. The stationary distribution [105] of the joint channel states, ir = (l’i,r2,. . . ,can be determined by solving(4.2)subject toir1 + 2 + + j = 1. (4.3)It is assumed that state transitions and the outcomes of transmissions on channels fordifferent receivers are statistically independent. However, there could be some correlationbetween the forward and feedback channel states of any given receiver. The propagationdelay over each and every channel, defined as the time, in packets, between the start of aFigure 4.2 Markov chain for four channel states.Chapter 4. Multiplexed ARQ: Throughput Analysis, Part 1 69packet transmission and the expected reception time of its corresponding acknowledgment,is denoted by N.In the case of the adaptive multiplexer, estimates of the states for each of the K channels areassumed to be available. These estimates could be derived from each receiver’s observationsof its forward channel (e.g., received signal strength), as well as through the multiplexer’sobservations of the feedback channels. At each time slot, these observations are mapped tothe corresponding channel states. The forward channel state information of each receiver issent back at each time slot over its feedback channel. Let so and o denote respectively theactual and the multiplexer’s estimate of the receiver’s observation of the joint state N slotsago. At each slot, the multiplexer has o for each channel. In general, so may not be availableto the multiplexer because of errors in the channel observations and in the corresponding statemappings. Furthermore, channel state information from the receivers may be lost at certainslots due to errors in the feedback channel. The treatment of these additional factors requiresa more detailed description and analysis of the channel as well as the estimation scheme itself.In order to simplify the model, the effects of these factors are assumed to be contained in aparameter denoted by jj = Pr {o = i so = j}. The estimated state of a given channel for thecurrent slot can be viewed as an N—step prediction of the channel state, s, given.o. Let s anddenote the actual and the multiplexer’s estimate of the channel state for the current slot. Theestimation error is denoted by Ejj = Pr {. = i s = j}, and can be calculated as follows. Letyjj denote the converse probability, Pr {s = I = i}. The long-run distribution of the stateestimates, ft, is given by(4.4)Pr {so = j} = 7r3, while Pr { = i = j} is derived below. Using Bayes’s rule, the estimationerror is given by= (4.5)7rwhere= Pr {s= j = i,so = k} . Pr {so = k = i} (4,6a)Chapter 4. Multiplexed ARQ: Throughput Analysis, Part I 70= Pr{s =j s = k}.Pr{so = k = i} (4.6b)== k = (4.6c)where iY denotes the N—step transition probabifity from state k to state j. In (4.6b), the factthat . depends only on s has been used. Using Bayes’s rule,Pr{so = k = i} = Pr{ = i iso = k}. (4.7)wherePr { = i s = k}=Pr { = i s = k, o = (4.8a)(4.8b)= (4,8c)The step in (4.8b) follows from the fact that depends only on o, F, and N. The matrix Hdepends on the estimation (prediction) algorithm used by the multiplexer. Let wj denote amember of the set of most likely states that a packet would be in if it were transmitted to agiven receiver in the next slot, i.e.,wjE{t:F>FViE{S}}=M. (4.9)If the multiplexer chooses its estimate at random from M, then = 6,/IMI.In general, the receiver could send feedback each time a packet is successfully decoded, orat fixed or even random time intervals. It is assumed in the ensuing analysis that for adaptivemultiplexing with K > 1, the receiver does not know a priori the slots containing its datapackets, and that it sends feedback only when a packet is successfully decoded, For K = 1,and with round-robin multiplexing in general, each receiver is assumed to know the slot towhich it has been assigned for the duration of the ARQ transaction, and to send feedback atChapter 4. Multiplexed ARQ: Throughput Analysis, Part 1 71fixed time intervals equal to the service cycle period of the multiplexer. For both schemes,the feedback contains the complete state information of the receiver (as discussed in Chapter2 and [93]),4,3 Throughput CalculationThe throughput, r,i, is defined as the long-mn fraction of data packet transmissions whichare released from the receivers’ buffers. As discussed in Chapter 2, the throughputs of SW andGBN ARQ can be reduced by errors in the feedback channel. However, the effects of theseerrors on continuous ARQ protocols can be mitigated by using postponed retransmission. Thisvariation is examined for GBN ARQ in Chapter 5. On the other hand, the throughput of TSRARQ is essentially unaffected by feedback errors because the transmitter can always chooseto send a new packet instead of retransmitting a timed-out packet whose completion statusis not yet known. A procedure for estimating TSR-limit values of the parameter w and theresequencing buffer size for SR ARQ is given in Chapter 6.For SW ARQ, the stutter variation is considered, where the transmitter sends repeatsof the outstanding packet in the intervening slots during which it has been selected beforean acknowledgment is expected. Under either round-robin or adaptive multiplexing, theselected transmitter sends a new packet if it knows that the previously transmitted packethas been successfully received. Otherwise, it resends the previously transmitted packet. Withstandard SW ARQ, the transmitter waits for the previously transmitted packet to time outbefore resending it (if necessary).In the throughput analysis of an ARQ protocol, a packet transmission is considered‘wasted’ if it cannot contribute to the successful completion of any packet, regardless ofwhether or not it is successfully received. For the case of GBN ARQ, following an unsuccessfully decoded first outstanding packet (FOP)1’ to a receiver, any transmission to that receiverin the next N — 1 slots is considered as having been ‘wasted’. On the other hand, in the caseof SW ARQ, following the first successfully decoded copy, any transmission to that receiver11 Chapter 1.Chapter 4. Multiplexed ARQ: Throughput Analysis, Part I 72in the next N — 1 slots is considered as having been ‘wasted’, since the transmitter wouldhave moved on to the next packet if it could have known immediately the outcomes of itstransmissions. In either case, the system is defined as being ‘blocked’ during these intervalswhen packet transmissions are wasted.The throughput can be calculated either directly, by considering the system (multiplexer)as a whole, or by observing the operation of one “marked” channel (transmitter-receiver pair),calculating its throughput, and arguing from the symmetry of the channels that it will alsobe the system throughput. For ISR ARQ with adaptive multiplexing, the direct calculationis simpler. With GBN and SW ARQ, a marked channel is observed, and the throughput isobtained by modeling its behavior as a semi-Markov process, from which the mean probabifityof successful transmission can be computed.4.3.1 Round-Robin MultiplexingWith this multiplexing scheme, the channels are selected in turn, with each channel servedonce every K slots.4.3.1.1 ISR ARQIn this protocol, it is assumed that each transmitter does not retransmit packets whosecompletion status is unknown (as a result of feedback errors). The throughput analysis thenreduces to the case without feedback errors (so long as the average PF,2 is less than 1). Sincethe probability of finding the selected channel in state j is the same as the long-run proportionof time that the channel spends in state j, the throughput is given by1R,ISR=(1—(4.10)where {7r1,7r2,. . .,lrj} are obtained from (4.2).4.3.1.2 GBN ARQThe analysis of this protocol is complicated by the presence of feedback errors when theycause redundant transmissions of data packets which have afready been correctly received.These redundant packets are different from the other data packets in that they should alwaysChapter 4. Multiplexed ARQ: Throughput Analysis, Part I 73be counted as ‘wasted’ transmissions in the throughput calculation, and that unsuccessfultransmissions of these packets do not cause buffer overflow at the receiver, An exact analysisappears to be complicated, but a reasonably accurate approximation can be obtained by notingthat redundant transmissions cannot occur during the first N slots after the start of (receiver)buffer overflow. This is because the information sent back to the transmitter about the stateof the receiver remains unchanged during that interval; regardless of whether or not feedbackerrors have occurred, the transmitter will retransmit the FOP and succeeding packets in theretransmission sequence. If the feedback is successfully received, the transmitter will know thatbuffer overflow has occurred, and it will retransmit accordingly. If feedback is not successfullyreceived, the previously transmitted packets will time out and be retransmitted anyway. Nowsuppose that buffer overflow does not reoccur beyond the first N slots after the last occurrenceof buffer overflow (i.e. some packets have been successfully received and feedback for thosepackets should have arrived at the transmitter). If the corresponding feedback for those packetsare not received before they time out, then they will be retransmitted even though they havein fact been successfully received.The throughput is given by the proportion of time in which packets are successfullytransmitted over those slots where the channel is selected. This proportion of time is computedby constructing a semi-Markov process that models both the behavior of the protocol as well asthe states of the channel. The transmitter can be in one of three possible “modes” at any givenpoint in time — “blocked” (during which packets are lost due to buffer overflow), “active”(when the channel is selected and is not “blocked”), and “idle” (when it is neither selectednor “blocked”). To identify the point in time where redundant retransmissions can occur,the active and idle modes are grouped into stages. Each of these stages consists of an activeand idle mode, representing the service cycle time of the multiplexer, where the channel isselected once every K slots. Redundant retransmissions can occur after the system has movedthrough of these stages (representing the first N slots after the last occurrence of bufferoverflow). Thereafter, redundant packets must be identified; these should not be counted assuccessfully transmitted packets.Chapter 4. Multiplexed ARQ: Throughput Analysis, Part I 74m=1m=Os1s=OFigure 4.3 State diagram of semi-Markov processfor round-robin multiplexing with go-back-N ARQ.A block diagram of the semi-Markov process is shown in Fig. 4.3. The joint channel-receiver state is labeled by a tuple, (s, m,j), where s is the stage number, m = 0, 1,2 is themode number corresponding to the idle, active and blocked modes respectively, and j is thechannel state. Each stage is composed of one or two modes, which correspond to the receiver’smode of operation. In each mode, there are J joint channel states. None of the transmittedpackets are redundant in stages 1 through F1• To make the state indexing consistent, stagenumbers are also assigned to both the blocked mode (s = 0) as well as the active mode whereredundant retransmissions can occur= [1 + 1).The time spent in mode m, Tm, is given byI K —1, m = 0Tm = 1, m= 1 (4.11)I K[.] - 1, m = 2where the values for m = 0 and 1 are obtained by noting that the multiplexer selects thechannel once every K slots. For m = 2, the protocol is in stage 0, and for convenience, thes=21KChapter 4. Multiplexed ARQ: Throughput Analysis, Part 1 75K____ ____________________________time1 N-i4 -.K K K4 timeN-i4r2Figure 4.4 Timing diagram for r2 in the semi-Markovprocess for round-robin multiplexing with go-back-N ARQ,time spent includes not only the period of buffer overflow (N — 1), but also any remainingtime before the transmitter is selected again by the multiplexer, as shown in Fig. 4,4.The transition probabifities between the states of the embedded Markov chain are givenas follows(T2)s=O,m=2,t=l,n=1PPjj,s=1,...,F1;m=1,t=s,n=oTsmi,nj s=1,..,];m=o,t=s+1,n=1 (4.12)FPj, s= [] + 1,m = 1,t = O,n = 2s= [] +1,m= l,t= E1,n=00, otherwise,where is the probability that the transmitted packet has been received in error and isnot redundant. It is computed as follows. Note first that the semi-Markov model does notcontain states which identify when redundant retransmissions will occur, but only when theymay occur. These states were not included so as to reduce the size of the state space. At theChapter 4. Multiplexed ARQ: Throughput Analysis, Part I 76point where such retransmissions can occur, the transmitted packet will not be redundant ifthe corresponding feedback for the packet sent T2 + 1 slots ago is not lost.Letting i) denote the probabffity that the transmitted packet is redundant given that thechannel is in state i,p1(i) (i — p))p. (4.13)The converse probability, P, that a packet is successfully transmitted and is not redundant,is given by(1 — p)) (i — (4J4)LetQ = (4.15)denote the transition probability of the reversed Markov chain [1051 of the channel states, Then- (i) (1 - p(i))Q2+1) (4.16)where Q2+l) is the probabifity that the channel was in state j + 1 slots ago, given that itcurrently is in state i. P) can also be expressed asgj (K F1 , K, (4.17)where g(N’, s’, w) is discussed further in Appendix D. By comparing (4.16) and (4.17), it canbe seen thatgij (K Ei K, o) p(J)Q2+1) (4.18)a result which can be confirmed by the analysis in the appendix.The long-run proportion of time spent in state (s, m, i), Pr {U = (s, m, i)}, can then becalculated from the stationary distribution of the embedded Markov chain (computed from(4.12)) and Tm [105]. Let Ji denote the event that the channel is selected. Since each channelChapter 4. Multiplexed ARQ: Throughput Analysis, Part I 77is selected every K slots, Pr {‘IJ} = 1/K. The throughput is then given by??RR,GBN = Pr { successful transmission I , U} Pr {U l}s,m ,i= Pr{ successfultransmission I ‘1,U} .Pr{U}/Pr{’IJ}s,1,iri . (4.19)= (i — Pr{U = (s,l,i)} .Ks=1 =1+PPr{U=KE1+l,i,i)}.K.For K = 1, the analysis proceeds in the same manner, except that there is no idle mode (i.e.,the single transmitter is always selected at each slot). In the case where there are no feedbackerrors (P = 0 , V i), the exact throughput is obtained,4.3,1.3 SW ARQThe same approach used for analyzing the throughput of GBN ARQ is taken here, withappropriate changes to the state assignments that reflect the behavior of SW ARQ. At any pointin time, the system is in one of several modes. Once a packet has been successfully transmitted,the system enters a “blocked” mode (see Section 4.3) and stays there for N — 1 slots pius anyadditional remaining slots before being selected (in fact, for T2 slots, as discussed in the case forGBN ARQ). The mode to which the system enters upon leaving the blocked mode dependson the status of the feedback corresponding to the successfully transmitted packet. If thefeedback is lost, the system stays for K slots in a “pending” mode, which represents theadditional amount of time that the system has to wait for the next feedback update. The next(new) packet cannot be transmitted so long as the transmitter cannot be sure of whether ornot the previous packet was successfully received. Hence, the system re-enters the “pending”mode each time feedback information is lost. If the feedback is successfully received, thesystem enters the “active” mode, during which it transmits a new packet. If the receiversuccessfully receives that packet, the system enters a “blocked” mode again. Otherwise, itenters an “idle” mode and stays there for K — 1 slots before re-entering the “active” mode.The “idle” mode represents the intervening time before the channel is selected again, whenthe system is neither blocked nor “pending”.Chapter 4. Multiplexed ARQ: Throughput Analysis. Part I 78m=1Figure 4.5 State diagram of semi-Markov process forround—robin multiplexing with stop—and—wait ARQ,The semi-Markov process is shown in Fig. 4.5, where m denotes the mode number. Modes1,. . . , J correspond to ‘blocked’ modes. If a packet is successfully transmitted while in jointchannel state j, it will enter the jth blocked mode (m = j). Modes J +1, J + 2 and 0 correspondto the active (selected), idle and ‘pending’ modes respectively. A tuple, (m, i), is used to labelthe combined protocol-channel state corresponding to mode m and joint channel state i. Them=Jm=J+1m=J÷2Chapter 4. Multiplexed ARQ: Throughput Analysis, Part I 79transition probabffities for the embedded Markov chain (for K > 1) are given bym=1,.,J,m=J+12)p(rn)m=1,.,J,n=Om=n=0= T) (i — m = 0, n = J + i (4.20)m=J+1,n=jPjjP, m=J+1,n=J+2FT0), m=J+2,n=J+l0, otherwise,where r0, T1 and r2 are given by (4.11), and r3 = K. For K = 1, there is no idle mode and(i) . .Tmi,nj PF1 for m = n = J + 1. Now that the transition probabthties as well as the timespent in each mode have been specified, the long-run proportion of time spent in any givencombined state, Pr {U = (m, i)}, can be calculated. The throughput is then given byRR,SW = Pr { successful transmission I ‘li, U} Pr {U I I’}m,(4.21)=(i — Pr{U = (J + 1,i)} K.4.3.2 Adaptive MultiplexingThis subsection discusses the multiplexing scheme which selects at each slot, the receiverwith the lowest forward channel decoding error probabffity for the given estimated channelstate. Other possibffities can be considered for finite-buffer ARQ protocols, whose throughputswill also depend on other parameters such as the quality of the feedback channel and thenumber of in-flight packets that may be lost due to buffer overflow; these parameters couldalso be included in the channel selection procedure.4.3.2.1 ISR ARQAs in the case with round-robin multiplexing, the throughput is essentially unaffected byfeedback errors so long as an appropriate value for w is used, along with a correspondinglylarger retransmission buffer size. The average conditional throughput given . = i is given by= Pr {successful transmission . = i}=(l-F)Pr{s=jI=i}. (4.22)Chapter 4. Multiplexed ARQ: Throughput Analysis, Part 1 80In any given slot, the adaptive multiplexer will transmit to a user whose estimated channelstate has the highest average throughput (as given by (4.22)). This results in an optimal channelselection policy. Suppose the estimated states are arranged in order of non-decreasing averageconditional throughput as {m1,m2,.. . , mj}, i.e.,(mi) <(rn2) <<(mj) (4.23)The probabffity that the best estimated state among K independent channels is m is given bypj = (Pr{ mj})K — (Pr{ < mji})K, (4.24)where the cumulative probabilities can be computed from (4.4). The throughput of themultiplexer for TSR ARQ is then1A,ISR= (4.25)4.3.2.2 GBN ARQThe state space here is slightly different from that used for round-robin multiplexing.First of all, the modes in which the system operates are no longer explicitly identified, but aresubsumed into the “stages”, each of which contain J joint channel states. A state transitiondiagram is given in Fig. 4,6. As before, the zeroth stage (s = 0) represents the blockedmode. The next N stages (S = 1,.. . , N) represent the first N slots after the buffer overflowperiod. They correspond to the situation where the system is not blocked and when redundantretransmissions (resulting from feedback errors) cannot occur; at stage s = N + 1 however,redundant retransmissions may occur. In stages s = 1 through N + 1, the system can be either“active” or “idle”, depending on whether or not the channel is selected. From any of theseN + 1 stages, the system enters the blocked mode (s = 0) whenever a non—redundant packetis received in error. The amount of time spent in each stage is given by = N — 1 slots forthe zeroth stage and 1 slot for the other stages.The probability that the marked channel is selected depends on the estimated states ofall the channels at that time slot. Its calculation is complicated by dependencies between theChapter 4. Multiplexed ARQ: Throughput Analysis, Part I 81sOstates of the protocol and the channel. An exact analysis of the selection probability requiresa calculation over the state space of all the channels in the system, the size of which may bequite large, depending on K and J (see Appendix C). Alternatively, one could approximatethis analysis by looking only at the states of the marked channel. The combined (protocol-channel) state is labeled by (s, c), where s is the stage, and c is the ‘channel state’, defined asthe states of all the channels if the exact analysis is used, or as the state of the marked channelin the approximate analysis. In both state space representations, the throughput is given byA,GBN = Pr { successful transmission U} Pr {U I li}s,cwhere=(i — r) .Pr{U = (s,c) I } + Pr{U = (N + l,c) Ip1(c) (i — p(c)” (i —S R1 Fl)(4.26)(4.27)C is the state of the marked channel for ‘channel state’ c (i.e., if c is the complete channel state(including the states of all the channels in the system), then ( gives the state of the markedchannel; on the other hand, for the approximate channel state space analysis that considersonly the state of the marked channel, then Cc c). As in the case of round-robin multiplexing,s=1 s=2 s=N s=N-i-1Figure 4.6 State diagram of semi-Markov processfor adaptive multiplexing with go-back-N ARQ.Chapter 4. Multiplexed ARQ: Throughput Analysis, Part I 82I’ denotes the event where the channel is selected. Using Bayes’s rule,Pr{U = (s,e) I= Pr{ I U== (4.28)From the symmetry of the system, it is clear that over a long period of time, each channelwill be selected for an equal proportion of time. Hence, Pr {} = 1/K, as in the case ofround-robin multiplexing. Pr { U} is the long-mn proportion of time in combined state U.Pr {‘I’ I U = (s, c)} = Pr {‘1 c} only if c contains the complete channel state. If c contains onlya partial description of the channels’ states, then Pr { I c} becomes an approximation sincethe rest of the state description is implied in s. Under the single-channel approximation,Pr{ I c = i} = Pr{ê = j I c = i}Pr{ I = = i}= Pr{ê= j I c = i}Pr{W = j}j=iK—i(4.29)= Pr{= j I c = i} (K_i) Pr{ê = j}kpr{ < }K_1_k= ZEij(K_1)Pr{ê<j}K_1_klDerivations using the complete state description, of the terms Pr {‘ I c}, qj and Pj, are givenin Appendix C.For both single-channel and complete state representations, the transition probabifitiesbetween the combined states are given bys=O,t=1Pr{ I s = 1,.. .,N;t = 0= {i — Pr{ c}P]Pcd, S = 1,. ..,N;t= s + 1 (4.30)Pr{Ic}PPd, s=N+l,t=0(l_Pr{jc}P)Pd, s=N+l,t=s0, otherwise,wherep1(c) (1 — p))p). (4.31)Pr {U} can then be computed from (4.30) and the specified length of time spent in each ofthe stages.Chapter 4. Multiplexed ARQ: Throughput Analysis, Part I 83As in the case of round-robin multiplexing, the state description of the system does notexplicitly identify events where redundant retransmissions will occur as a result of feedbackerrors. Likewise, the probability that the transmitted packet is redundant has to be obtainedindirectly. If the transmitter is selected immediately upon entering stage s = N + 1, then theprobabffity that the transmission is redundant, may be approximated byP gcd(N,l,O), (4.32)where the parameters for adaptive multiplexing are substituted into g(•). Further details canbe found in Appendix D; for the given parameter values,gcd(N,1,O) = I d}P), (4.33)where Q is the N-step transition probabifity of the reversed Markov chain (as discussedpreviously under round-robin multiplexing). In general however, the transmitter may not beselected at all times while it is in stage s = N + 1; it may not be selected immediately uponentering that stage, and furthermore, several slots may elapse between successive selections.Some mechanism is needed for taking into account the increased likelihood of a redundantretransmission as a result of successfully received packets which time out (due to feedbackerrors) during those intervening slots when the transmitter is not selected. This is accomplishedby modifying F to take the following form,gc(N, 1, 0) + (4.34)where= ZQcb(1 — Pr{ I + F)] , i K (435)1 0 , otherwise.F accounts for a (K — 1)-slot time window into the past, starting from the last elapsed slot,summing (approximately) the probabifity that a packet times out as a result of a feedback error,during a slot when the transmitter was not selected. The window size was chosen empiricallyto provide a consistently close agreement between the throughputs obtained theoretically andthrough simulations.Chapter 4. Multiplexed ARQ: Throughput Analysis, Part 1 84m=2m=1Figure 4.7 State diagram of semi-Markov process foradaptive multiplexing with stop—and—wait ARQ.4.3.2.3 SW ARQThe analysis given below applies to the case where K > 1 (where an acknowledgmentis not sent if the corresponding data packet is received in error). For K = 1, the throughputis given by (4.21).At any point in time, the transmitter is either in a “blocked” or “unblocked” mode. Theblocked mode corresponds to the interval when the transmitter could have sent new packetsover the channel if it had known a priori that its last packet transmission was successful. In theunblocked mode, it may or may not be selected. The same issues with regard to the complete orsingle—channel state descriptions also apply to SW ARQ under adaptive multiplexing withoutfurther modification from that discussed earlier for GBN ARQ, A state diagram is given inFig. 4.7. The combined system state is denoted by (m, c), where the unblocked and blockedmodes are denoted respectively by m = 1 and 2, and c is the channel state. The time spentin (m, c) is given by Tm, where Ti = 1 and = N 1. Finally, the transition probabifitiesare given as follows.p(T2)m=2,n=lTmc,nd= Pr{ c}(l — ph)) (i — m = l,n = 2 (4.36)[1_Pr{c}(1_F)(1_F)].F, m=m=l0, otherwise,Chapter 4. Multiplexed ARQ: Throughput Analysis, Part I 85where Pr {l’ I c} is the same as that for GBN ARQ under adaptive multiplexing. As before,Pr {U} can be calculated from (4.36) and rn• The throughput is then given byA,SW = Pr {successful transmission JJ U} . Pr {U Im ,c—Pr{ I U = (l,c)}Pr{U = (4.37)—— -F,i ) F,2 J Pr{}where Pr { ‘I’ } = 1 / K. If the complete channel state description is used, Pr { I’ I U } = Pr { ‘I’ I c}.Otherwise, Pr { I c} gives an approximation.Chapter 5 Multiplexed ARQ: ThroughputAnalysis, Part NIn this chapter, the GBN ARQ protocol is analyzed for the case where the retransmissiondelay parameter, w, is greater than zero. A straightforward extension of the analysis techniquein Chapter 4 is shown first, after which a method for reducing the number of states is presented.5.1 IntroductionIn Chapter 4, the throughput for GBN ARQ under both round-robin and adaptive multiplexing was analyzed for the case of w = 0. It was shown in Chapter 2, that the throughput ofcontinuous point-to-point ARQ protocols could be improved if an appropriate value for w waschosen for the prevailing forward and feedback packet error rates. In fact, for a fairly widerange of channel conditions, the improvement was such that the throughput approached thevalue attainable for the case of an error-free feedback channel. This leads one naturally to seeif a similar improvement might be possible with time-varying channels as well as multiplexedsystems.Some clarifying points need to be mentioned about the postponed retransmission concept,as it applies to multiplexing systems over time-varying channels. First, the optimal valuefor w may itself vary over time iii accordance with the prevailing channel conditions. Itis reasonable to expect this to be the case especially if the channel quality remains quasi-stationary over an extended period of time, but can change drastically from one period to thenext. Furthermore, feedback may no longer be sent contiguously to any given transmitter ina multiplexed system. Under round-robin multiplexing, as discussed in Chapter 4, feedbackinformation was assumed to be sent back to the transmitter at fixed intervals equal to theservice cycle period of the multiplexer. With adaptive multiplexing on the other hand, thereceiver was assumed to send feedback information whenever a data packet was successfullyreceived. These assumptions are carried over into this chapter.86Chapter 5. Multiplexed ARQ: Throughput Analysis, Part II 87In a multiple receiver system, the original meaning of w (in a point-to-point system) is leftunchanged (i.e., w is the maximum number of additional slots that the transmitter waits forfeedback information before retransmitting a timed-out packet, regardless of whether or notthose slots contain feedback sent by the receiver). For round-robin multiplexing, the parameterw’ is used to denote w expressed in units of service cycle periods, i.e.,W = W’K, (5.1)In this chapter, a simplified system is considered, with a fixed value of ‘w selected for the all(time-varying) channel conditions.With ISR ARQ, it was assumed in Chapter 4 that ‘w was chosen to be large enough suchthat the effects of feedback errors could be ignored. A corresponding (fixed) value of ‘w fortime-varying channels can be obtained by computing the value of ‘w for each channel condition,assuming the channel to be stationary, and choosing the highest ‘w. There is no throughputperformance loss from using a higher value of w in the other channel conditions where asmaller value would suffice. This procedure however, may not be generally applicable toGBN ARQ. Here, the optimal value of w for a given channel error condition involves a tradeoff between redundant retransmissions and additional packets lost due to buffer overflow. Ifis higher than its optimum value, then there are fewer redundant retransmissions, but atthe expense of more packets lost when buffer overflow occurs. The converse case happenswhen W is lower than optimal.In Section 5.2, the throughput is analyzed by extending the technique used in Chapter4. The state space of this approach, however, also increases with W and can become acomputational burden when w becomes sufficiently large enough. Hence, an alternativeprocedure that uses a smaller state space is developed in Section 5.3. The notation and conceptsin Chapter 4 carry over into this chapter and are not explained again.5.2 Extension of Throughput AnalysisFor both round-robin and adaptive multiplexing, the general analytic procedure remainsessentially unchanged from that described in Chapter 4. The main differences lie in modiChapter 5. Multiplexed ARQ: Throughput Analysis, Part II 88fications to the state space and transitions among the states so as to reflect changes in theprotocol’s operation.5.2.1 Round-Robin MultiplexingA state transition diagram is shown in Fig. 5.1. The system is not blocked in stages= 1 through EN/K1 + w’ + 1. If w’ > 0, the transmitter will continue to transmit up tow’ additional new packets (when successive feedback errors occur) before retransmitting theFOP. Accordingly, redundant transmissions do not occur in stages s = 1 through [N/K1 + w’,but may occur in stage s = EN/K1 + W’ + 1. If a data packet is received in error in any ofthese stages, the system enters either stage s = 0 if the corresponding feedback is successfullyreceived, or stage s = EN/11 + w’ + 2 if it is lost. The transmitter does not begin retransmittingimmediately after the FOP times out, but continues to send new packets while waitingfor feedback information. When feedback is successfully received during this interval, thetransmitter begins retransmitting, starting from the FOP.Stages .s = [N/K1 + W’ + 2 through s = EN/K1 + 2W’ + 1 represent additional servicecycle periods during which the system remains blocked. Transitions into any of these stagescorrespond to events which will cause the transmitter to delay retransmission (N slots later,sending new packets instead while waiting for feedback information to arrive). When feedbackis successfully received, the transmitter realizes that buffer overflow has occurred and beginsretransmitting, starting from the FOP. Likewise, when feedback has not been received after viservice periods, then the transmitter will begin retransmitting anyway. Transitions from thesestages to .s = 0 correspond to events which will cause the transmitter to start retransmittingpackets (N slots hence). The system is blocked in these stages, as well as stage = 0. However,the active and idle modes (m = 1 and m = 0) are used in stages s = IN/K1 + vi + 2 throughs = EN/K1 + 2W’ + 1 to denote respectively when the transmitter is selected and the intervalbefore it is selected again.Chapter 5. Multiplexed ARQ: Throughput Analysis, Part II 89The transition probabifities are given as follows.P(T2) s = O,m = 2,t = 1,n = 1s=1,...,F1+w’;m=1,t=o,n=2PPFij, s=1,...,F1+w’;m=1,t=F1+w’+2,n=os=1,...,F1 +w’;m=l,t=s,n=Os = 1,..., + w’;m = O,t = s + 1,n 18= +w’+1,m=1,t=O,n=2Tsmi,tnj =s = 1,...,[1 +w’+l;m= i,t= F1 +w’+2,n=O(i_ S= + w’ + 1,m = 1,t = + w’,n = 0Tø)8= +w’+2,...,f1 +2w’+1,m=0;t=s,n=1PFj, 8= +w’+2,...,F1 +2w’,m=l;t=s+l,m=O(i —= + w’ + 2,..., + 2w’, m = 1; t = 0, n = 2s=Ff1+2w’+1,m=1;t=0,n=20, otherwise,(5.2)where(i_ (53)and1—gjj (i K, ‘). (5,4)These terms have been derived before in Section 4.3.1.2; the only difference being that w’ > 0.The time spent in each state, T, is the same as in the previous chapter. From P and r, theproportion of time spent in each state, Pr { U}, can be determined. The throughput can thenbe calculated as follows.RR,GBN = Pr { successful transmission I ‘, U} . Pr{U IS ,m ,t= Pr{ successful transmission I P,U} . Pr{U}/Pr{’1’}j (5.5)= (i—1) Pr{U = K, 1,i)} . K+PPr{U= KEi +w’+11i)} .K,wherep1(i) (i - p(i)) ( - p(i)) (5.6)Chapter 5. Multiplexed ARQ: Throughput Analysis, Part II 90m=1m=OrNls=[-.]+w’+3 s=j-+w’+2Figure 5.1 State diagram of the semi-Markov process forround-robin multiplexing with CBN ARQ and w > 0.5.22 Adaptive Multiplexingm=1m=Os=1 s=2j s=[-]+w’+i+ WIThe modifications to the state space for w = 0 are analogous to what was done earlierChapter 5. Multiplexed ARQ: Throughput Analysis, Part II 91in the case of round-robin multiplexing. A state transition diagram is shown in Fig. 5.2. Thesystem is not blocked in stages 1 through N + w + 1, of which redundant transmissions cannotoccur during the first N + w stages, but may occur in stage N + w +1. Stages N + w + 2 throughN + 2w + 1 correspond to the extended period of buffer overflow when the retransmissionprocedure delayed because of feedback errors. The system is blocked in these stages, as well asin .s = 0. Corresponding transition probabilities are given as follows. Note first that if K = 1,then an acknowledgment is sent in every slot, whereas if K > 1, then an acknowledgment issent only whenever a data packet has been successfully received. Hence, for K = 1,p(m)s=0;t=1Pr{ I c}P(1 — s = 1,.. .,N + w;t 0Pr { c}PPPd, s = 1,. . . , N + w; t = N + w + 2[i_ Pr{ I c}F]Pd, s = 1,,..,N + w;t =Pr{ e}P(1_P)PCd s=N+w+1t=OT3,td Pr { I = N + w + 1; t = $ + 1 (5.7)(l—Pr{c}P)Pd.[l—Prc(1_P)jPcd s=N+w+2,...,N+2w;t=s+1Pr{WIc}(1—F)PCd, s=N+w+2,...,N+2w;t=0Fcd, s=N+2w+l;t=00, otherwise,(5.9)and(5.10)while for K > 1,p(To)cdPr{[1 —Pr{ IPr{ IT3,td (i — Pr{ I[i_ Pr{ c}(i — (1_F,1 )Pr{’I1 I e}(i — pr;)) (1— P))Pd,Fcd,0,where.9 = 0;t = 1s=1,,,.,N+w;t=N+w+2s=1,...,N+w;t=s+ls = N+w+ 1;t= s + 1s=N+w+1;t=ss=N+w+2 N+2w;t=s+1s=N+w+2,...,N+2w;t=0s = N + 2w+ l;t = 0otherwise,(5.8)— (gd(N, 1, w) + F1))] (c)F,1F(i) { Q(1 — Pr { b}) [9bd(N 1, w) + , i K0 , otherwise.Chapter 5. Multiplexed ARQ: Throughput Analysis, Part II 92The throughput is then given byA,GBN = Pr { successful transmission ‘II’, U} Pr{U ‘I’}N+w= (i — Pr {U = (s, c) I } + p) Pr{U = (N + w + 1, c) I(5.11)wherep1(c)— ( 1, w) + 1))] (i — (5J2)The derivations and resulting forms of (5.9), (5.10) and (5.12) are similar to those of (4.13),(4.35) and (4.14) respectively, differing only in the use of g(N, 1, w)12 where w is now greaterthan zero.5.3 Reduced State Space AnalysisIt can be seen from Figs. 5.1 and 5.2 that some stages share some common characteristics.For example, the exit probabilities in stages 1 through N/K1 + w” in Fig. 5.1 are identical.Other similarities appear in stages EN/K1 + w’ + 2 through FN/K1 + 2w’ + 1 in Fig. 5.1, aswell as in stages 1 through N + w and stages N + w + 2 through N + 1 + 2w in Fig. 5.2.Moreover, it can also be seen that in each of these groups of stages, the system enters onlythrough one stage; once inside, it either moves to another stage within the group or leavesthe group. These characteristics can be exploited to combine the stages in each group togetherinto a single “mode”, each of which contains J channel states. The resulting state space forboth round-robin and adaptive multiplexing is composed of four “modes”, as shown in Fig.5.3. In this representation, the system state is denoted by a tuple, (m,j), where j = 1,.. . , J isthe channel state and m = 1,.. . , 4 is the mode, which is assigned as follows. The mode m = 1collects together all stages where the system is not blocked and where redundant packets arenot transmitted. In mode m = 2, the system is not blocked, but redundant retransmissionscan occur. Modes m = 3 and 4 correspond to blocked states, where m = 4 corresponds tostage s = 0 and m = 3 collects together all the stages corresponding to the extended buffer2 Discussed further in Appendix D.Chapter 5. Multiplexed ARQ: Throughput Analysis, Part II 93Figure 5.2 State diagram of the semi-Markov processfor adaptive multiplexing and GBN ARQ with w > 0.overflow interval. The stage mappings for round-robin and adaptive multiplexing are givenin Tables 5.1 and 5.2 respectively.The throughput is equal to the long-run proportion of slots containing successful transmissions considering only the slots during which the transmitter is selected. Let denote theprobabifity that the system enters (m, i) (i.e., the probabifity of being in (m, i) in the embeddedMarkov chain). Furthermore, let and u2 denote respectively the number of slots, in m, i),where the transmitter is selected by the multiplexer, and where a transmission is successful.s=N+1+2ws=N+2ws=N+w+3s=N+w+2s=Os=1 s=2 s=N+w sN+w+1Chapter 5. Multiplexed ARQ: Throughput Analysis, Part II 94Figure 5.3 State diagram of reduced state space representation.Mode (in reduced state space) Stages (in extended analysis)1 1 N1‘IK mW2 F1+w’+1F1 +w’+2,,,.,F1 +2w’+l4 0Table 5.1 Stage mapping for round-robin multiplexing.Mode (in reduced state space) Stages (in extended analysis)12 N+w+13 N+w+2,,,.,N+1+2w4 0Table 5.2 Stage mapping for adaptive multiplexing.The throughput can then be expressed in the following form,2 Jm=1 j=1Jm=1 3=1The F correspond to the stationary distribution of the embedded Markov chain, whichcan be obtained by solving the system of linear equations specified by the transition probability(5.13)Chapter 5. Multiplexed ARQ: Throughput Analysis, Part II 95matrix T, where Tmi,nj denotes the transition probabffity from (m,i) to (n,j). Tmi,nj P1(b),while = cj and 4V = /3, where P’(b), a and /3 are discussed hi Appendix E. Theseparameters depend, in turn, on other parameters (discussed in the same appendix) whichdepend on the multiplexing scheme and the mode of the system. The particulars of therequisite parameters are specified in Sections 5.3.1 and 5.3.2 for round-robin and adaptivemultiplexing respectively.5.3.1 Round-Robin MultiplexingFor the analysis in Appendix B, the probability term Pr{4’ I i} = lV j,m = 1,.. .,4.5.3.1.1 m = 1:n = 4= P.(2), = (5.14)P(3), n = 20,B = 3, D = IN/K1 + , u(s) = i —b=0= (i_r), b= 1 (5.15)(3) p(3) —F,1 F,2’ —0, b=3,0, b=0b=l= p(i)p(i) b — 2 (5.16)F,1 F,2’ —b=3,and rb=K,b=0,...,3.5.3.1.2 m = 2:= B = 3, D = 1, u() ==1, b = 0 (5.17)0, otherwise,0, b=0p1(i) (i — p(i)) b = 1TI’(3) Fvb = p1(i) p(j)F F,2’ —1_pi) b=3,and = K, b=Chapter 5. Multiplexed ARQ: Throughput Analysis, Part II 965.3.t3 m = 3:= {PI(l) n=4 (5.19)0, otherwise,B=1,D=w,U()=P2’F,2’ —Vb{F(3)b U= (i_r), b= 1, (5.20)10, b—_U (5,21)b j1, b=1,and Tb = K, b = 0,1.5.3,1.4 m = 4:T4= { F(1), n = 0 (5.22)0, otherwise,B = 1, D = max { 1( — K)/K, o}, u3 = 1,v Ii, b=0 (5.23)b=1,qj) 1 0, b = 0 (5.24)b=1,and Tb = K, b = 0,1.5.3.2 Adaptive MultiplexingUnder adaptive multiplexing, the expressions for Tmi,nj take the same form as in the caseof round-robin multiplexing, but with different parameter values as given below.5.3.2.1 m = 1:IfK=1,I1_hi b=0v(j)lPr{j}(1—O,b=1 (5.25)Pr{ j}PF, b = 20, b=3,Chapter 5. Multiplexed ARQ: Throughput Analysis, Part II 97and { 0, b=0Pr{ j}P(1 - r), b = 1=Pr{ j}PP, b = 2 (5.26)l-Pr{Wj}P, b3.If K > 1,Ii— Pr{ }p(i) oF,fl= Pr{ j}P, b = 2 (5.27)10, b=1,3,and (0, b=0,1i)—) Pr{ j}F, b = 2 (528)1 —Pr{ j}P b— 3.F,1’ —5.3.2.2 m = 2:1(j)B=3,D=1,Tb=1forb=1,..,,3,U(3)=Pr{lj}P ,andv(j){1,b=0 (5.29)— 0, otherwise,If K = 1, { 0, b=0Pr{ j}pi)(1_p), b=1(5.30)= Pr { j}p’(2) p(i) b = 2F F,2’1— Pr{ }p3) 6 = 3,while if K > 1,(0, 6=0,1= Pr{ I }pi), 6 = 2 (5.31)11— Pr{W Ni}F’ L‘5.3.2.3 m = 3:B = 1, D = W, Tb = 1, b = 0,1, andI() 10, 6=0 (5.32)b=1.If K = 1, then = Pr{ Ij}F, and11— Pr{ I j}(1 — p(i)’\ 6 = 0F,2J’ (5.33)Pr{Ij}(1_P), 6=1.On the other hand, if K> 1, then () = Pr{ I j}[1 — (i — ()‘ 1 ri andF,1} F,2}j’I1—Pr{ Ii}(1—Fi)(1—Fi) 6=0=j Pr{ j}(1 — (i)N 1 — 6 = 1, (5.34)Chapter 5. Multiplexed ARQ: Throughput Analysis, Part II 985.3.2.4 m = 4:B = 1, D = N — 1, ut’) = Pr{ I i}Ii, b=O (5.35)b=1,— I 0, b = 0 (5.36)b=1,and Tb = 1, b = 0, 1.Chapter 6 Multiplexed ARQ: Numerical ResultsIn this chapter, some numerical results based on the analysis in Chapters 4 and 5 arepresented and discussed,6,1 IntroductionFor all of the examples shown in this chapter, J1 = J2 = 2, and J = 4. The joint channelstate, (1, m), is assumed to depend on factors such as the relative position (and the resultingpropagation paths) between the transmitter and receiver, as well as on local conditions (e.g.,sources of local interference) at either end of the communication link. One way of modelingtransitions between joint channel states is to assume that the fOrward and feedback channelstates are independent Markov processes, with transition probabffities Pei(1) and Pfm(2)respectively. Under this assumption, the transition probabffity between joint channel stateswould be given byPej,im = Pel(l)Pfm(2). (6.1)For the examples in this chapter, the joint state transition probability is modeled in a moregeneral form that includes a combination of some dependency between the forward andfeedback channels, as well as an independent term for the feedback channel. The transitionprobabilities are obtained as follows. First, the forward channel is modeled as a Markovprocess with transition probabilities Fel (1), e, 1 = 1,.. . , J1. Some form of reciprocity is assumedbetween the instantaneous forward and feedback channels states, wherein the feedback channelstate tends to be “similar” to the forward channel state (e.g., the feedback channel will tend tobe “good” when the forward channel is in a “good” state, and conversely when the forwardchannel is in a “bad” state). However, the joint channel state (1, m) defines m not as thesimultaneous feedback state at the slot when the data packet is received (in forward channelstate 1), but rather when the corresponding acknowledgment is expected. Assuming perfectreciprocity, the feedback state component rn is therefore the forward state 1, N/2 slots in the99Chapter 6. Multiplexed ARQ: Numerical Results 100future. To account for imperfect reciprocity, the feedback component is assumed to be arrivedat by a two-step process, the first of which assumes perfect reciprocity, followed by a randomdisturbance that moves the intermediate state arrived at from the first step to its final state m.Hence, the joint state transition probability is given as follows.Pef,lm Pr{(l,m) (e,f)}= Pr{(i,rn,rn’) (e,f)}= Pr {m, rn’ 1, e, f} Pr {l e’ (6.2)= Pr{m I m’,l,e,f}Pr{m’ jl,e,f}Pr{l e,f}= Pr{m m’}Pr{m’ I l}Pr{l Iwhere Pr {m I m’} represents the random disturbance and is given by m’m, Pr {l e} =(FN/21) . . .Pei(l), and Pr {m l} lrn’ (1), where the ceiling function is included as an integerapproximation to N/2 when N is not evenly divisible by 2. Alternatively, Pr {m’ I l} mightbe expressed in the following form,Pr {m’ l} = p(LN/2i)() + (6.3)At any rate, the joint transition probabifities would likely be obtained empirically in practice,through field measurements; the preceding discussion is used primarily to try to obtainplausible values for Pef,lmFor convenience, the joint state (1, m) is mapped onto a one-dimensional index i, i1,. . . , J, given by i = (1 — l)J1 + m. F(1) is assumed to be given as follows,(0,98 0.024)— 0.005 0.995 ‘ (6.Assuming that(0.7 0.3N0.3 0.7)’ (6.5)the resulting joint channel state transition probabifity matrix for N = 10 is then given by0.649 0.331 0.00619 0.0138— 0.649 0.331 0.00619 0.0138 6 6)0.00331 0.00169 0.308 0.6870.00331 0.00169 0.308 0.687Chapter 6. Multiplexed ARQ: Numerical Results 101The multiplexer’s state estimation matrix, , is assumed to contain/ 0.91 0.03 DM3 0.03— 0.005 0.985 0.005 0.005— 0.03 0.03 0.91 0.03 (6.7)\0,005 0.005 0.005 0.985to reflect the case where better state estimates are made when the feedback channel is in statem = 2 rather than m = 1, and where incorrect estimates are assumed to be equally likely. FromF, , N, and H (discussed in Chapter 4), the corresponding state estimation error matrix, ,is then given by0.79 0,0 0.0 0.21— 0.79 0.0 0.0 0.21— 0.067 0.0 0.0 0.933 ‘ (6.8)0.067 0.0 0.0 0.933The packet error rates over the forward channel are chosen to be = (0.8, 0.1)for ISR ARQ, and (0.1,0.02) for both GBN and SW ARQ. Feedback packet errorrates for TSR ARQ are chosen to be = (0.4,0.05). For GBN and SW ARQ, threesets of values are investigated:((0.2,0.04), “Channel 1”=(0.1,0.02), “Channel 2” (6.9)1(0.01,0.02), “Channel 3”,where the “channel” labels identify which set is being referred to in later discussions.6.2 Throughput Performance ComparisonsIn this section, both analytic and simulation results are presented for various ARQ andmultiplexing schemes. Confidence intervals at the 99% level are usually miniscule, typicallydiffering only in the third decimal place. In such cases, they are omitted and only the meanvalues are shown as data point markers. The theoretical values are connected by straight linesegments to show the performance trend.The throughput performance of TSR ARQ in conjunction with the two multiplexingschemes is shown in Fig. 6.1. Equations (4.10) and (4.25) were used to calculate the theoreticalthroughput values for round-robin and adaptive multiplexing. Results from simulations areshown as point markers. It can be seen that the throughput with the adaptive scheme improvesChapter 6. Multiplexed ARQ: Numerical Results 102with the number of receivers, taperirg off after about 4 receivers in this case. On the otherhand, the throughput with round-robin multiplexing does not change with the number ofreceivers.Finite retransmission and resequencing buffer sizes were assumed in the simulation program. For each scheme, the following procedure was used to estimate the sizes of thesebuffers and the retransmission delay parameter that would be required for the throughput toapproach the value achieved by TSR ARQ. First, the probability distribution, Pr {s= j I J}, ofjoint channel states, is determined for those slots when the charmel is selected. For round-robin multiplexing, Pr {.s= j I} = irs, where the ir are given by the stationary distributionof channel states (Section 4.2). For the adaptive scheme, the distribution is given by1Pr{s=j}Pr{s=j}s_j—Pr{W s=j}.ir7— 1/Kwhere Pr {‘I’ s j} is given by (4.29). For each joint channel state s, the corresponding valuesof the retransmission delay and “level” parameters, w(s) and q(s), were computed such thatthe resulting throughput (as given through (2.8)) would be within 99.9% of that for TSR ARQ.Average values of these parameters are given by= w(s) Pr {s(6.11)= q(s)Pr{s IThe retransmission and resequencing buffer sizes, B1 and B2, are then set respectively toN + Ic’w and (N — 1), both rounded to the nearest integer, where N is the round-trippropagation delay (Chapter 1). This is analogous to Weldon’s scheme, even though the channeldelay “seen” by a transmitter will, on average, be less than N as a result of multiplexingwhen K > 1. The retransmission delay parameter w used in the simulations is given by KT(rounded to the nearest integer), to reflect the fact that each transmitter is selected every Kslots in round-robin multiplexing, and on average, every K slots with the adaptive scheme.The resulting values for B1 and B2, as used in the simulations, are given in Table 6.1.The throughput performance for GBN ARQ with w = 0 is shown in Figs. 6,2, 6.3 and 6.4,for channels 1,2 and 3 respectively. Corresponding optimal and quasi-optimal values for wChapter 6. Multiplexed ARQ: Numerical Results 103Round-Robin AdaptiveKB1 B2 B1 B21 15 90 15 812 20 90 29 523 25 90 35 454 30 90 43 435 35 90 51 436 40 90 59 437 45 90 67 438 50 90 75 439 55 90 83 4310 60 90 91 43Table 6.1 Retransmission and resequencing buffer sizes used in simulations for ISR ARQ.(using (5.13)) are given in Tables 6.2, 6.3 and 6.4, for channels 1, 2 and 3. A “quasi-optimal”value here means the smallest value of w such that the resulting calculated throughput is atleast 99% of the value obtained when the optimum w is used. Throughput values computedusing the approximate channel state space were used in the optimization search. For K 5, thethroughputs were recomputed using the complete channel state space at the (quasi-)optimalpoints. At these points and for w = 0, the throughputs obtained from using the approximatestate space were found to be only slightly higher than the corresponding values from usingthe complete state space, less than 1% higher at K = 2, and decreasing with (increasing) K toroughly 0.1% higher by K = 5. Theoretical throughput values using the complete state spaceare given for K 5 while corresponding values using the approximate state space are givenfor K > 5, where the computing time and memory requirements become prohibitive with thecomplete state space analysis for the system parameters at hand.As expected, simulation results for the case where optimal values of w are used are onlyslightly higher than those for the quasi-optimal case, differing typically by only 0.001. Hence,only the results for the quasi-optimal values are shown in Figs. 6.5, 6.6 and 6.7, for “channels”1,2 and 3. Curves corresponding to the simple product approximation (using (2.5) and (2.6))and the assumption of an error-free feedback channel are also shown.Chapter 6. Multiplexed ARQ: Numerical Results 104It can be seen from the figures that some throughput improvement is possible withthe adaptive scheme over round-robin multiplexing when w = 0. However, round-robinmultiplexing is better than the adaptive scheme when quasi-optimal values of w are used.Note also that the theoretical results tend to underestimate the simulation data slightly forw = 0, and match up with the simulations very closely in the quasi-optimal case. It canbe seen in Figs. 6.2, 6.3, 6.5 and 6.6, that the simple product approximation tends to grosslyunderestimate the achievable throughput. Conversely, from the same figures, the assumptionof an error-free feedback channel leads to overestimation of the throughput. It is only whenthe feedback error rate becomes very small (compared to the forward error rate), as can be seenin Figs. 6.4 and 6.7, that these simplifying assumptions lead to more acceptable throughputestimates.The throughput results for SW ARQ are shown in Fig. 6.8. As in the case with GBN ARQ,the computing time and memory requirements for throughput calculations using the completechannel state space become increasingly prohibitive with large values of K. Likewise, thethroughputs were computed using the complete channel state space for K 5 and withthe approximate state space for K > 5. The throughput values obtained from using theapproximate state space are slightly higher than corresponding values using the completestate space, typically around 1.7% higher at K = 2, and decreasing with increasing K to about0.6% higher by K = 5. It can be seen from the figure that the theoretical values (calculatedusing (4.21) and (4.37) for round-robin and adaptive multiplexing) are in good agreement withthe simulation results, and that round-robin multiplexing is better than adaptive multiplexing.Chapter 6. Multiplexed ARQ: Numerical Results 1050.9/0.8RR(theo,)RR(sim.)A(theo,)A(sim.)07 I I I I I I0 1 2 3 4 5 6 7 8 9 10Number of ReceiversFigure 6.1 Throughput performance of ISR ARQunder round-robin and adaptive multiplexing.Chapter 6. Multiplexed ARQ: Numerical Results 106Round-Robin AdaptiveKQuasi-optimal Optimal Quasi-optimal Optimal1 2 16 2 162 4 94 4 63 6 144 7 104 8 232 9 145 10 215 12 186 12 354 14 217 14 665 16 248 16 440 19 289 18 144 21 3510 20 610 24 40Table 6,2 Optimal and quasi-optimal values of w for GBN ARQ in Channel 1.Round-Robin AdaptiveKQuasi-optimal Optimal Quasi-optimal Optimal1 2 13 2 132 4 118 2 33 6 108 3 64 8 188 4 85 10 290 5 96 12 426 6 127 14 665 7 128 16 544 8 169 18 324 8 1510 20 710 9 20Table 6.3 Optimal and quasi-optimal values of w for GBN ARQ in Channel 2.Chapter 6. Multiplexed ARQ: Numerical Results 107Round-Robin AdaptiveKQuasi-optimal Optimal Quasi-optimal Optimal1 1 6 1 62 2 136 0 03 3 117 0 04 4 244 0 05 5 305 0 06 6 420 0 07 7 637 0 08 8 544 0 09 9 90 0 010 10 410 0 0Table 6A Optimal and quasi-optimal values of w for CBN ARQ in Channel 3.Chapter 6. Multiplexed ARQ: Numerical Results 1081/—--;;.0,9 / 0- / — 0/ — 0___________________________/ — 0C C C C C/ V /,//,/ /0.8 i i _—//////d /0.7,17// A (sim.) 00.6 RR (sim,) C/ A (theo.)// RR (theo.) — — — -A (product approx.)a: RR (product approx.) — - — - -A (no feedback errors) — - — - — - — -RR (no feedback errors) -0.5a:/70.4 I I I I I I I0 1 2 3 4 5 6 7 8 9 10Number of ReceiversFigure 6.2 Throughput performance of GBN ARQ with w = 0, forChannel 1, under round-robin and adaptive multiplexing._u_ _u_—u_ —1------ _---r - — -A(sim.)RR (sum)A (theo.)RR (theo.)A (product approx.)RR (product approx.)A (no feedback errors)RR (no feedback errors)Figure 6.3 Throughput performance of GBN ARQ with w = 0, forChannel 2, under round-robin and adaptive multiplexing.Chapter 6. Multiplexed ARQ: Numerical Results1109//// -9---,,‘V0.90,80.70.60.50.4I//(/UI I I I I0 1 2 3 4 5 6 7 8 9 10Number of ReceiversChapter 6. Multiplexed ARQ: Numerical Results 11010.90.80.60.50.40Number of ReceiversFigure 6.4 Throughput performance of GBN ARQ with w = 0, forChannel 3, under round-robin and adaptive multiplexing.VV-V/p/A(siim)RR (s.)A (theo.)RR (theo.)A (product approx.)RR (product approx.)A (no feedback errors)RR (no feedback errors)D1 2 3 4 5 6 7 8 9 10Chapter 6. Multiplexed ARQ: Numerical Results 11_i14-— :- :- — — — —p- —— — —0.9/7 III0.8//I’I-1/U.,2-‘/ A (sim.)0.6- /,‘ RR(sim.) U,,‘ A(theo.)/1 P.R (theo.) —— — -/ A (product approx.)I: P.R (product approx.) — - — - -/: A (no feedback errors)— - — - —- — -P.R (no feedback errors)-0.5II0.4 I I I I I I I0 1 2 3 4 5 6 7 8 9 10Number of ReceiversFigure 6.5 Throughput performance of GBN ARQ using quasi-optimalw, for Channel 1, under round-robin and adaptive multiplexing.Chapter 6. Multiplexed ARQ: Numerical ResultsNumber of Receivers9 10112Figure 6.6 Throughput performance of GBN ARQ using quasi-optimalw, for Channel 2, under round-robin and adaptive multiplexing.10,90.8------—--/0.6 A(siim)RR (sim.)A (theo.)P.R (theo.)A (product approx.)P.R (product approx.)A (no feedback errors)RR (no feedback errors)0.5El0.40 1 2 3 4 5 6 7 8Chapter 6. Multiplexed ARQ: Numerical Results 11310,90.80.70.60.50.40Number of ReceiversFigure 6.7 Throughput performance of GBN ARQ using quasi-optimalw, for Channel 3, under round-robin and adaptive multiplexing.VA(sim.)RR (slim)A (theo.)RR (theo.)A (product approx.)RR (product approx.)A (no feedback errors)RR (no feedback errors)1 2 3 4 5 6 7 8 9 10Chapter 6. Multiplexed ARQ: Numerical Results 1140,40.30.20.1Figure 6.8 Throughput performance of SW ARQunder round-robin and adaptive multiplexing.10.90.80.70.60.50Number of ReceiversChapter 6. Multiplexed ARQ: Numerical Results 1156.3 Concluding RemarksThe adaptive multiplexing scheme tends to show greatest improvement in throughputperformance over round-robin multiplexing when it is used with ISR ARQ. The amount ofimprovement will depend on the packet error rates in each state, the distribution of channelstates, as well as on the accuracy of the channel state estimates. Throughput improvementwith the adaptive scheme will be reduced under the following circumstances.1. Little difference between the throughputs achievable at each channel state.2. Low occupancy probabilities in “worse” channel states (i.e., states which result in lowerthroughput).3. Large state estimation errors. These errors increase with N, as well as with larger transitionprobabifities between channel states.For GBN ARQ, the improvement from using the adaptive scheme is less and in fact, itsperformance can be worse than that of round-robin multiplexing, particularly when (quasi-)optimal values for w are used. This is due in part to assumptions on when the receiver stateinformation is fed back to the transmitter. With round-robin multiplexing, feedback is sentperiodically, whereas with the adaptive scheme for K > 1, feedback is sent only when a datapacket is successfully received. For SW ARQ, round-robin multiplexing generally tends toperform better than the adaptive scheme. In general, this decreasing order of improvement isnot too surprising because the adaptive scheme takes only packet decoding failure probabilities(over the forward channel) into account; these are the only factors that can affect the throughputof TSR ARQ, whereas the throughputs of GBN ARQ and especially SW ARQ, depend also onthe channel delay “seen” by the transmitter (i.e., as manifested in the number of in—ffightpackets).Chapter 7 Concluding RemarksThis thesis has addressed a number of issues in the area of ARQ communication systems.The effect of errors in the feedback channel of an ARQ system was discussed in Chapter 2.It was shown that under certain circumstances, the detrimental effects of feedback errors onthe throughput performance could be greatly mitigated by a postponed retransmission delayscheme. This scheme involves only a relatively simple modification to the ARQ protocol.The throughputs of some ARQ protocols were analyzed for the case where complete stateinformation is sent over a feedback channel which can introduce errors. An exact expressionfor the throughput of stutter SW ARQ was given. Approximate expressions were found for thethroughputs of GBN, TSR and SR ARQ, including the corresponding postponed retransmissionvariants; the approximations appear to be robust, giving good agreement with simulationresults over a wide range of channel conditions. These throughput expressions can be usedin the data transmission rate analysis of Chapter 3 with a greater degree of confidence thanexpressions such as those based on the simple product approximation, which tend to greatlyunderestimate the throughput at high feedback error rates.In Chapters 4 through 6, the throughput performances of some ARQ protocols, as usedunder round-robin multiplexing and an adaptive multiplexing scheme, were evaluated for amultiple-receiver system with time-varying charmels. A model was developed and analyzed,taking into account issues such as errors in the feedback channel and in the channel stateestimates. Furthermore, the postponed retransmission scheme from Chapter 2 was alsoexamined in the context of this system, and similar throughput performance improvementswere found. The adaptive scheme is optimal for the case of ideal selective repeat ARQ, wherethe corresponding throughput can be considerably greater than what can be achieved underround-robin multiplexing. The analysis technique (of using a semi-Markov process) may alsobe useful for analyzing ARQ protocols in applications where packets are not sent contiguously,as may be the case in multiple-access systems.116Chapter 7. Concluding Remarks 117Possible areas for future research work stemming from the results of this thesis includethe following:1. Implications of bandwidth requirements for sending back channel state information inthe case of the adaptive scheme; data transmission rate issues. The groundwork hasalready been done for point-to-point stationary channels in Chapter 3, which discussesa procedure for optimizing the data transmission rate of an ARQ protocol under certainsystem constraints.2. Design and analysis of more efficient adaptive multiplexing schemes for GBN and SWARQ,3. A performance comparison between adaptive coding and adaptive multiplexing schemes.4. Queueing performance evaluation.5. Extension of the analytic results to bidirectional data transmission systems.Appendix AConditions for Continuous-ModeHalf-Duplex Transmission Over a Direct LinkIn this appendix, it is shown for a half-duplex transmission scheme, that continuous-modetransmission is possible only for certain packet lengths.A.1 IntroductionConsider a half-duplex data link connecting two nodes, where each node can transmit orreceive but cannot do both at the same time. Each node always alternates between packettransmission and reception, as would be the case with an ARQ protocol where data andacknowledgment packets are transmitted continually at regular intervals. Continuous-modetransmission refers to the case where multiple packets can be transmitted in either directionover the link without colliding into each other at either node. Conversely, with noncontinuousmode transmission, there cannot be more than one packet over the link at any given time; onenode transmits while the other waits to receive the packet, after which it transmits (in theother direction). Suppose the nodes transmit fixed-length packets, though the lengths maydiffer in the two directions. It will be shown that, in order for continuous-mode transmissionto be feasible, the packet lengths must satisfy a constraint that depends on the propagationdelay of the link.A.2 AnalysisFor convenience, the two directions are labelled with subscripts of 1 or 2. Let D1 denotethe propagation delay in one direction, excluding the packet transmission time. The totaldelay, Dtot, is equal to D1 + D2. The time required to transmit a packet is given by T, andthe time axis is divided into slots of length T1 + T2. Each node transmits and receives apacket in each slot. In general, Dt0t = m(Ti + T2) for some m > 0. Without loss of generality,suppose a packet is transmitted in direction 1 at time t = 0. The other node receives the packetcompletely at time t = D1 + T1, and transmits its packet immediately afterwards, which in118Appendix A. Conditions for Continuous-Mode Half-Duplex Transmission over a Direct Link 119turn arrives at the first node at time t D1 + T1 + D2. The first node begins transmission againat times t = T +T2,2(T1 +T2),3(T1 + T2) In order to avoid collisions between incomingand outgoing packets, the incoming packet must not arrive until just after an outgoing packethas been transmitted (i.e., not until time t mod (T1 + T2) = T1). This leads to the followingconstraint,(D1 + T1 + D2) mod (T1 + T2) = T1, (AJ)which can be simplified as follows.(m(Ti + T2) + T1) mod (T1 + T2) = T1(m+1)Ti+mT2-[m(T1+T2)+T1J(T T) T1Ti+T2m(Ti +T2) = [m(Ti+T2)+T1j(T +T2)(A.2)m= Lm+T+Tj,which shows that m must be an integer.The preceding discussion can be applied to the second node, which starts transmitting attime t’ = o in its time frame. In this case, the incoming packets should arrive at times t’ suchthat t’ mod (Ti + T2) = T2, leading to a constraint similar to that for the first node,(D1 + 712 + D2) mod (T1 + T2) = 722, (A.3)which simplifies tom = [m + T1 + Ti’ (A.4)thus showing the same requirement that m must be an integer.Hence, the propagation delay Dt0t must be a positive integer multiple of the slot timeCT1 + T2).Appendix B. Packet Synchronization Analysis 120Appendix BPacket Synchronization AnalysisIn this appendix, an approximate expression for the probability of successful packetsynchronization is derived under certain simplifying assumptions.B,1 ModelConsider a packet that contains a field of B bits for synchronization, the first B/2 of whichare used for bit synchronization (bit sync), while the last B/2 bits contain the marker usedfor packet synchronization (packet sync). This packet is transmitted over a binary symmetricchannel with bit error probability p. The receiver attempts bit synchronization first. Afterit is acquired, the receiver then searches for the marker. This procedure is done on eachincoming packet with the assumption here that timing information from previous packetsis not available. Furthermore, it is assumed that bit synchronization is always successfullyacquired, and that this occurs most of the time approximately half-way through the bit syncsequence (i.e., by about B/4 bits), although in general, it can occur anywhere in the bit syncsequence. The receiver then checks the next sequence of B/2 bits and declares packet syncif the distance (the number of differing bit positions between the marker and the sequence)does not exceed a specified error tolerance (i.e., maximum distance) of h bits. Otherwise, thesearch shifts forward by one bit and the corresponding sequence of B/2 bits is checked. It isassumed that the synchronization process is halted and that the packet is discarded if packetsync is not declared after B/2 attempts. A non-zero error tolerance enables packet sync tobe declared when a sequence is aligned with the marker but contains errors. While a highervalue for the error tolerance increases the chances of successfully acquiring the marker in spiteof bit errors, it also increases the chances of false acquisition, where packet sync is erroneouslydeclared after processing a sequence not containing the marker, but which mimics it, differingin h or fewer bit positions.Appendix B. Packet Synchronization Analysis 121B2 AnalysisThe derivation for the probability of successful packet sync essentially follows that donein [961 for the probabffity of “correct acquisition in one pass through a frame of time” (8), but withsome changes to reflect the particular model discussed above.The probability, FFA, of false acquisition due to an arbitrary random sequence that mimicsa marker M bits long is given byh MPFA=(B.1)Conversely, the probabifity, PTA, of true acquisition (when the sequence containing the markeris recognized as such) is given byPTA = ((i _)M_t (B.2)“•‘Suppose the receiver begins looking for synchronization approximately D bits before completely overlapping the marker. Let a(i) denote the event that synchronization is declared onthe ith sequence, and /3(i) denote the event that synchronization is declared at any time prior tothe ith sequence. The probability, Psync of successful packet sync can then be approximatedas follows.Psync Pr {/3(D)} Pr {a(D)= [1- Pr{/3(D)}]Pr{a(D)= [1_Pr{U (i)}] Pr {(D) I (B.3)-Pr{(i)}] Pr {(D) I[1 — (D— 1)PFA]PTA,where Pr{c(i)} FFA (for i < D) and Pr {(n) I /3(D)} Pr{cx(D)} = PTA were used inthe last step. The expression corresponding to the parameters of the model is obtained bysetting D to B/4 and M to B/2. It can be seen that the optimal value of h will depend onp. all other parameter values held constant.Appendix B. Packet Synchronization Analysis 122B.,3 Numerical ResultsThe probabffity of successful packet sync is plotted as a function of h for different SNRsin Fig. B.1. Corresponding values of p are calculated for QPSK over an AWGN channel. Thecurves show that the optimal value of h depends on the SNR and, as might be expected,decreases with increasing SNRS. It can also be seen for the given analysis and assumptions,that packet sync is almost always acquired at high SNRS and becomes markedly less likelyto occur only at very low SNRs.BA Concluding RemarksThis appendix has presented an approximate analysis of a simple model for the probabffityof successful packet synchronization. Its primary purpose lies not so much in detailed quantitative results, but mainly in showing situations where frequent loss of packet synchronizationcan seriously degrade the chances of successful packet decoding, regardless of the amountof error-correction coding. In practice, it is likely that one would have to use more accurateresults obtained from detailed analysis or empirical data.Appendix B. Packet Synchronization Analysis10.90.8123/I if 7/ /7/SNR=8dB — --- - -SNR=6dB — —a —SNR=4dB —-—-0--—-.SNR=2dB -c----SNR0dB ———+-——-SNR=-2dB — - &— - -SNR=-4dB — —e — -SNR = -6dB0.7I/I/0,6/IIIIIII1*I0.5///IIIII/IIIIII0.4I0.30.20.105h15Figure B.1 Probability of successful packet syncas a function of h for various channel SNRs.Appendix C. Representation and Analysis of the Complete Multiple-Channel State Space 124Appendix CRepresentation and Analysis of theComplete Multiple-Channel State SpaceIn this appendix, the state transition, estimation and channel selection probabffities arederived for the complete channel state space representation in the case of adaptive multiplexingwith either GBN or SW ARQ.At any given time, each of the K channels in the multiplexing system is in one of Jpossible states. The probabifity, Pr {W c = u}, that the marked channel is selected, given thatthe system (of K channels) is in state u, is used in the throughput analysis in Chapters 4and 5. An approximation to this probabifity was derived in Chapter 5. To obtain an exactexpression of this probabifity for the adaptive multiplexing scheme, the state of the markedchannel as well as the number of channels in each of the J states must be specified. Thisis the information required in the “complete channel state space representation”; since onlythe conditional selection probability is being calculated, there is no need to specify the exactstate that each channel is in.This appendix begins with a derivation of the size of the state space, which is usedto develop a scheme that maps the state vector (of the complete representation) onto ascalar. The mapping allows existing computing routines developed for calculations with theapproximate state space representation to be re-used without further modification. The systemstate transition and state estimation probabifities are then derived. These probabilities arerequired to compute the probability that the marked channel is selected, whose derivation isgiven afterwards.C.1 Size of State SpaceLet f(k, j) denote the number of states for a system with k channels, each of which isin one of j channel states. For j = 1, all of the k channels are in the same state. Hence,f(k, 1) = 1. For j > 1, the number of states can be calculated by first noting that if exactly k — iAppendix C. Representation and Analysis of the Complete Multiple-Channel State Space 125channels are in a particular state, then each of the remaining i channels can only be in oneof the other j — 1 channel states. If the number of states is known for each i = 0,. . . , Iv, thenthe total number can be obtained by summing over the values of i. This leads to a recursivecomputing procedure as follows.f(k,1)= lv kf(k,2)=Zf(i,l)=k+lf(k,3) = f(2) = 1±2+ +k+1 = (k+1+2) (C.1)f(k,j) = f(i,j - 1).The total number of states, considering both the state of the marked channel as well as thedistribution of the other channels’ states, is then given byf(K— 1,J)J, (C.2)Corresponding values of (C.2) for some values of K and J are given in Table C.1.JK1 2 3 4 5 6 7 81 1 2 3 4 5 6 7 82 1 4 9 16 25 36 49 643 1 6 18 40 75 126 196 2884 1 8 30 80 175 336 588 9605 1 10 45 140 350 756 1470 26406 1 12 63 224 630 1512 3234 63367 1 14 84 336 1050 2772 6468 137288 1 16 108 480 1650 4752 12012 274569 1 18 135 660 2475 7722 21021 5148010 1 20 165 880 3575 12012 35035 91520Figure C.1 (C,2) evaluated for different values of K and J.Appendix C. Representation and Analysis of the Complete Multiple-Channel State Space 126C.2 Indexing the StatesThe system state can be expressed as a vector of the following form(s,k1,k2., j), (C.3)where s is the state of the marked channel, and k gives the number of chanrels in state i.This vector is subject to the following constraints,ki+k2++kj=K1<s<J(C.4)0 k K, V jk 1.The vector can be mapped onto a contiguous scalar, ii = 1,. . ., f(K — 1, J) J, as follows. Thekey observation here is to note that there are f(K — 1, J) ways of arranging the K — 1 channels(other than the marked channel). Imagine the range of n as being partitioned into J sections,each of size f(K— 1, J). Suppose these sections are indexed from 0 to J — 1. The vector(s, k1,k2, . . . , kj) then belongs to the (s — l)th sector. To find its position within this sector,a similar partitioning procedure is applied recursively, starting from k1 to k. For example,suppose there are i channels in state 1. If .s = 1, then there are f(K — i, J — 1) ways in whichthe remaining K — i channels can be arranged among the remaining J — 1 states. On the otherhand, ifs > 1, then one channel (i.e., the marked channel) is in state s, and the number ofways of arranging the remaining channels is f(K— i — 1, J — 1). If s = 1, there are K of thesesubsections (corresponding to i = 1,. .., K), while if s > 1, there are K + 1 subsections (becausethere is an additional subsection corresponding to i = 0). The vector then belongs to the k1thsubsection. This procedure is applied recursively to find the position within this and smallersubsections. The final position can be viewed as the next higher position (i.e., one higher) afterAppendix C. Representation and Analysis of the Complete Multiple-Channel State Space 127adding up the sizes of all of the lower sections and subsections. It can be expressed as follows,s—i k1—i k2—im = 1 + f(K — 1,J)+ f(I( — i—g19J 1)+ f(K — — i —g2,J— 2)=12k_1—1+ + f(K — k1 — — ... — i—gj-i, 1) (C.5)= 1 +(s — 1)f(K—where— IHj=>f(K_mji_i_gj,J-j), (C.6)=ljand._f0,js—i , ow.10 ,j = 0m=. (C.7)m_ + k3, 1 <j < Jfo, jsC.3 State Transition, State Estimation Error, andSelection Probability CalculationsThe transition probability from an initial system state u, to the another state w, can becomputed by splitting the state transition into two steps. Suppose the marked channel is instate i at system state u, and in state j when the system is in state w. Then the transition canbe viewed as a two-step process consisting of a first step, where the marked channel’s statechanges from i to j, followed by a second step, where all the other channels change statesaccordingly so as to reach state w. Let v’ denote the intermediate state reached after the firststep. The transition probabffity is then given byA= Pr{w I u}= Pr{w I v’,u}Pr{v’ u} (C.8)= Pr {w I v’, u}Pi,whereu = (uo,ui,.. .,iJ_i,uJ) = (i,ki,k2,. . .,kj1,kj)w = (in0= j, inj, in2, . . ., wj_, wj) (C.9)v’=(vo,vi,...,vj_i)=(j,ki,k2Appendix C. Representation and Analysis of the Complete Multiple-Channel State Space 128andPr{w v’,u}= (C.1O)wherev=(v1,v2,...,vJ)= (CJ1)andp V1+V2+”+VJ+6w0J=W0, otherwise= () () ( ) (C12)i=(i1,i2,,iJ),i1+i2+...+iJ+Wj=wj,j=1,_.,J—l.The vector v corresponds to the distribution of channel states at u, but with one less channelin state i (corresponding to the marked channel). In other words, it includes only the channelswhich can change states in the second step of the system state transition. Each probabifityterm j = 1, . ., J, sums the contributions from channels in v that change states suchthat the number of channels in state j is exactly wj.Let e denote the state estimation error probabffity, that the system is estimated to bein state w, given that it is in state u, It can be computed in the same manner as shown forbut using e.ij instead of Pij. This follows because the estimated state can be viewed asa transition from the “true” system state, but using a different transition probability matrix.The conditional probability that the marked channel is selected is then given byPr{ c = u} = ZPr{111 I = w,c= u}Pr{ê = c = u}= >Pr{P I ê = W}Euw (C.13)EuwwAppendix D. Derivation of the “g” Function 129Appendix DDerivation of the “g” FunctionIn this appendix, the function gd(N’, s’, w) is derived. This function is used for computingthe probabifity, P, that a transmitted packet is redundant, given that it is in state c. Let the“step size” s’ denote the interval between slots where the transmitter may be selected. Atransmission is assumed to be redundant if the following events have occurred:1. A packet is transmitted N’ + s’w slots ago.2. The corresponding feedback to that packet is lost.3. Feedback is not successfully received in the next s’w slots.Under these assumptions, F is given by the corresponding joint probabffity of these events.Now suppose that to these events, another event is added — that the channel was in stated, N’ slots ago. The function g(.) is an estimate of the entire joint probability thus described,assuming each event to be independent from all the others. Hence,p(c) gd(N’,s’,w), (D.l)wherecd (N’, s’, w) Q/G° (s’), (D.2)andG(s)[1 — Pr { I d} (i—i = 0,. . . , w — 1(D.3)I Pr{V d}PF2, i =For round-robin multiplexing, g(.) is called in such a way that the calculation is done overslots where the transmitter is selected (e.g., (4.17)). Hence, in this case, Pr {‘1 d} 1 V d.Appendix E. Analysis of an E’uivalent Reduced Semi-Markov Process 130Appendix EAnalysis of an EquivalentReduced Semi-Markov ProcessIn this appendix, a group of states comprising a semi-Markov process is reduced to anequivalent representation with one group of states. The transition probabilities, as well as theaverage number of “selections” and “successes”, are derived for this equivalent semi-Markovprocess.El IntroductionConsider the semi-Markov chain shown in Fig. E.1 where, as in Chapter 5, each boxcontains a collection of J states and is referred to as a “stage”. Transitions can occur fromany state in one stage to any state in the next stage. The system can enter this chain of stagesonly through the first stage, and may move through zero or more succeeding stages beforedeparting the chain to one of B exit stages. There are D stages in the chain.Let (s,j) denote the jth state in the sth stage. The transition probabifities in this system,from (m,i) to (n,j>, are given as follows.I VP,rn=1,...,D—1;n=D+kTmi,nj = m = n = D + k (E.1)1VP,m=1,.,.,D—1;n=m+1,() ,(i)where Pj is the transition probability from state z to state j, while Vk and V , k = 1,. .. , Bare transition probabilities to stage D + k from the ith state in stages 1,. . ., D — 1 and Drespectively. v is the corresponding transition probabffity between stages in the chain. Thelength of time spent in each stage depends only on the next stage that the system will enter,and is denoted by r, where k = 1,. . ., B if the system exits to stage D + k, and where k = 0if the system enters the next stage in the chain.This representation is reduced to a single stage containing J states, as shown in Fig. E.2,where for each state i, the transition probabffity to state j in exit stage D + b, Pj(b), is tobe determined. Also to be determined are the average number of times that “selection” andAppendix E. Analysis of an Equivalent Reduced Semi-Markov Process 131“success” events occur before the system exits the chain. These parameters are denoted by/3 and cx respectively. At any stage in the chain, a “success” occurs with probabifity U(s) inthe jth state. In this particular system, a “selection” always occurs whenever the system exitsbefore entering the last stage of the chain, or when a “success” occurs; in all other cases, itmay or may not occur.E.2 AnalysisE.2.1 Transition ProbabilitiesThe probability, f(b), that the system exits to (D + b,j), given that it entered the chainin state i in the reduced representation, can be calculated as follows. Let Zj,b(l) denote theprobabffity of exiting into (D + b,j), given that the system is in (1, i). Then P’(b) =which can be computed recursively in the following manner.Z,b(l) = + i) + 1) , 1 = D — 1,. . 1.(E.2)E.2.2 Average Number of “Successes”The average number of “success” events, j, that occur before the system exits, given thatit starts from state I (at the first stage), can be computed as follows. Let Y3(l) denote therandom variable for the cumulative number of successes, starting from state j in the lth stage.It can easily be verffied to have the following distribution. For 1 = D,I u(i), Yj(D) = 1fY(D)(II)= ii — Yj(D) = 0. (E.3)For 1 = 1,...,D — 1,j(j)p(ro) (l) = 1 + Yk(l + 1)f(i)(Y)= [v) — u(s)] o) (l) = Yk(l + 1) (E.4)Yj(1)=O.The expected value for I = D, E[Yj(D)], is given byE[Y(D)] = f()(E.5)=Appendix E. Analysis of an Equivalent Reduced Semi-Markov Process 132Figure El Original semi-Markov process.Appendix E. Analysis of an Equivalent Reduced Semi-Markov Process 133For 1 = 1, . . . , D — 1, E[Yj(l)] can be calculated by using the following result, that E[Y] =E[E[YJX]], where X and Y are random variables, Hence,E{Yj(l)] = + E[Yk(l + 1)]) + [V(i) — u(i)] F0)E[Ya(l + 1)] + ok=1 k=1 (E.6)= + (1 + 1)].Then c = E[Yj(l)].E.2,3 Average Number of Times “Selected”To compute the average number of times that a selection occurs, the same proceduredone with cj in the preceding section is used, but with different probability distributions.Is=D+2s=D÷1Figure E.2 Equivalent semi-Markov process with reduced number of states.Appendix E. Analysis of an Equivalent Reduced Semi-Markov Process 134Let S(l) be the random variable for the cumulative number of times that a selection occurs,starting from the jth state in the lth level. Its probability distribution is given as follows.First, let Pr {IJ I i} denote the probability that a selection occurs, given that the system is instate j. For 1 = D,fPr{ j}, S(D)= 1fsD)(s) = i — Pr { j}, S(D) = o. (E.7)For 1 = 1,...,D —1,S3(l) = 1 + S(l + 1)fs(1)(Y)=— u(i)] S(l) = Sk(l + 1) (E.8)= 1.The expected values of S(l) are then given byE[S(D)j = Pr {W I i} (E.9)andE[S(l)] = + V p(ro)E{s (1 + 1)] +k=1 b1 (E.1O)= ±(r+ 1)] + 1 —from which ,13j = E[S(1)].E.3 Concluding RemarksThe preceding analysis can also be readily generalized to the case where the stage and statetransition probabilities (V and F), as well as the time spent in each stage (T), can depend onwhich stage the system is in. The recursive procedure remains essentially unchanged, exceptfor additional indexes in V, P and r, to identify the stage within the chain.Bibliography 135Bibliography[1] S. Lin and D. Costello, Jr., Error Control Coding: Fundamentals and Applications. EnglewoodCliffs, N.J.: Prentice-Hall, Inc., 1983.[2] A. M. Michelson and A. H. Levesque, Error Control Techniques for Digital Communication.J. Wiley, 1985,[3] B. Vucetic, “An adaptive coding scheme for time-varying channels,” IEEE Transactions onCommunications, vol. 39, pp. 653—663, May 1991.[4] H. 0. Burton and D. D. Suffivan, “Errors and error control,” Proceedings of the IEEE,vol. 60, pp. 1293—1301, Nov. 1972.[51 A. G. Konheim, “A queueing analysis of two ARQ protocols,” IEEE Transactions onCommunications, vol. COM-28, pp. 1004—1014, July 1980.[6] M. B. Anagnostou and B. N. Protonotarios, “Performance analysis of the selective repeatARQ protocol,” IEEE Transactions on Communications, vol. COM-34, pp. 127—135, Feb. 1986.[7] M. C. Easton, “Design choices for selective-repeat retransmission protocols,” IEEE Transactions on Communications, vol. COM-29, pp. 944—953, July 1981.[8] P. S. Yu and S. Lin, “An efficient selective-repeat ARQ scheme for satellite channels andits throughput analysis,” IEEE Transactions on Communications, vol. COM-29, pp. 353—363,Mar. 1981.[9] Z. Rosberg and N. Shacham, “Resequencing delay and buffer occupancy under theselective-repeat ARQ,” IEEE Transactions on Information Theory, vol. 35, pp. 166—173, Jan.1989.[10] Z. Rosberg and M. Sidi, “Selective-repeat ARQ: the joint distribution of the transmitterand the receiver resequencing buffer occupancies,” IEEE Transactions on Communications,vol. 38, pp. 1430—1438, Sept. 1990,[11] N. Shacham and B. C. Shin, “A selective-repeat-ARQ protocol for parallel channels andits resequencing analysis,” IEEE Transactions on Communications, vol. 40, pp. 773—782, Apr.1992.[12] D-L. Lu and J-F. Chang, “Analysis of ARQ protocols via signal flow graphs,” IEEETransactions on Communications, voL 37, pp. 245—251, Mar. 1989.[13] J-F. Chang and T-H. Yang, “Multichannel ARQ protocols,” IEEE Transactions on Communications, vol. 41, pp. 592—598, Apr. 1993.Bibliography 136[141 G. R. Pieris and G. H. Sasaki, “Performance of the go-back-infinity protocol undercorrelated packet losses,” IEEE Transactions on Communications, vol. 41, pp. 660—663, May1993.[15] D. Towsley, “A statistical analysis of ARQ protocols operating in a nonindependent errorenvironment,” IEEE Transactions on Communications, vol. COM-29, pp. 971—981, July 1981.[16] D-L. Lu and J-F. Chang, “Performance of ARQ protocols in nonindependent channelerrors,” IEEE Transactions on Communications, vol. 41, pp. 721—730, May 1993.[17] R. H. Deng, “Hybrid ARQ schemes for point-to-multipoint communication over nonstationary broadcast channels,” IEEE Transactions on Communications, vol. 41, pp. 1379—1387,Sept. 1993.[18] C. H. C. Leung, et al, “The throughput efficiency of the Go-Back-N ARQ scheme underMarkov and related error structures,” IEEE Transactions on Communications, vol. 36, pp. 231—234, Feb. 1988.[19] S. R. Kim and C. K. Un, “Throughput analysis for two ARQ schemes using combinedtransition matrix,” IEEE Transactions on Communications, vol. 40, pp. 1679—1683, Nov. 1992.[20] J. C.-I. Chuang, “Comparison of two ARQ protocols in a Rayleigh fading channel,”Proceedings of the 40th IEEE Vehicular Technology Conference, Orlando, Florida, U.S.A., pp. 571—575, 1990.[21] T. Suda and N. Watanabe, “Evaluation of error recovery schemes for a high-speed packetswitched network: link-by-link versus edge-to-edge schemes,” Proceedings of the 7th AnnualJoint Conference of the IEEE Computer and Communications Societies, New Orleans, Louisiana,U.S.A., pp. 722—731, 1988.[22] A. Bhargava, et al, “Performance comparison of error control schemes in high speedcomputer communication networks,” Proceedings of the 7th Annual Joint Conference of theIEEE Computer and Communications Societies, New Orleans, Louisiana, U.S.A., pp. 694—703,1988.[23] Y. Cho and C. Un, “Window flow control with error-checking scheme in quasi-cut-throughswitching network with noisy channels,” IEEE Transactions on Communications, vol. 39,pp. 394—397, Mar. 1991.[24] G. M. Brown, et al, “Block acknowledgment: redesigning the window protocol,” IEEETransactions on Communications, vol. 39, pp. 524—531, Apr. 1991.[25] Y, Ishibashi and A, Iwabuchi, “Performance evaluation of adaptive ARQ schemes overhalf duplex transmission line,” Proceedings of the 8th Annual Joint Conference of the IEEEComputer and Communications Societies, Ottawa, Ontario, Canada, pp. 564—573, 1989.Bibliography 137[26] B. W. Biersack, “Performance of the IEEE 802.2 Type-2 Logical Link Protocol with selectiveretransmission,” IEEE Transactions on Communications, vol. 41, pp. 291—294, Feb. 1993.[27] B. T. Doshi, et al, “Error and flow control performance of a high speed protocol,” IEEETransactions on Communications, vol. 41, pp. 707—720, May 1993.[28] D. Towsley and J. Wolf, “On the statistical analysis of queue lengths and waiting timesfor statistical multiplexers with ARQ retransmission schemes,” IEEE Transactions onCommunications, vol. COM-27, pp. 693—702, Apr. 1979.[29] B. H. Saeki and I. Rubin, “An analysis of a TDMA channel using stop-and-wait, block, andselect-and-repeat ARQ error control,” IEEE Transactions on Communications, vol. COM-30,pp. 1162—1173, May 1982.[30] A. R. K. Sastry, “Improving automatic repeat-request (ARQ) performance on satellitechannels under high error rate conditions,” IEEE Transactions on Communications, vol. COM23, pp. 436—439, Apr. 1975.[31] J. M. Morris, “On another go-back-N ARQ technique for high error rate conditions,” IEEETransactions on Communications, vol. COM-26, pp. 187—189, Jan. 1978.[32] D. Towsley, “The stutter Go Back-N ARQ protocol,” IEEE Transactions on Communications,vol. COM-27, pp. 869—875,. June 1979,[33] N. D. Birrell, “Pre-emptive retransmission for communication over noisy channels,” lEEProceedings, Part F, vol. 128, pp. 393—400, Nov. 1981.[34] E. J. Weldon, Jr., “An improved selective-repeat ARQ strategy,” IEEE Transactions onCommunications, vol. COM-30, pp. 480—486, Mar. 1982.[35] Y. Chang and C. Leung, “On Weldon’s ARQ Strategy,” IEEE Transactions on Communications, vol. COM-32, pp. 297—300, Mar. 1984,[36] S. Ram Chandran and S. Lin, “Selective-repeat-ARQ schemes for broadcast links,” IEEETransactions on Communications, vol. 40, pp. 12—19, Jan. 1992.[37] M. J. Miller and S. Lin, “The analysis of some selective-repeat ARQ schemes with finitereceiver buffer,” IEEE Transactions on Communications, vol. COM-29, pp. 1307—1315, Sept.1981.[38] M. Moeneclaey, et al, “Throughput optimization for a generalized stop-and-wait ARQscheme,” IEEE Transactions on Communications, vol. COM-34, pp. 205—207, Feb. 1986.[39] H. Bruneel and M. Moeneclaey, “On the throughput performance of some continuous ARQstrategies with repeated transmissions,” IEEE Transactions on Communications, vol. COM34, pp. 244—249, Mar. 1986.Bibliography 138[401 Y. Hayashida, et al, “Delay performance of a continuous ARQ system with copy-transmissions,” Proceedings of the 7th Annual Joint Conference of the IEEE Computer andCommunications Societies, New Orleans, Louisiana, U.S.A., pp. 714—721, 1988.[41] C. Benelli, “A new method for the integration of modulation and channel coding in anARQ protocol,” IEEE Transactions on Communications, vol. 40, pp. 1594—1606, Oct. 1992.[42] C. Benelli, “Some ARQ protocols with finite receiver buffer,” IEEE Transactions onCommunications, vol. 41, pp. 513—523, Apr. 1993.[43] P. S. Sindhu, “Retransmission error control with memory,” IEEE Transactions on Communications, vol. COM-25, pp. 473—479, May 1977.[44] C. Benelli, “An ARQ scheme with memory and soft error detectors,” IEEE Transactions onCommunications, vol. COM-33, pp. 285—288, Mar. 1985.[45] D. Chase, “Code combining: a maximum-likelthood decoding approach for combining anarbitrary number of noisy packets,” IEEE Transactions on Communications, vol. COM-33,pp. 385—393, May 1985.[46] J. J. Metzner and D. Chang, “Efficient selective repeat ARQ strategies for very noisy andfluctuating channels,” IEEE Transactions on Communications, vol. COM-33, pp. 409—416,May 1985,[47] C. Lau and C. Leung, “Performance analysis of a memory ARQ scheme with soft decisiondetectors,” IEEE Transactions on Communications, vol. COM-34, pp. 827—832, Aug. 1986.[48] R. Fantacci, “Performance evaluation of efficient continuous ARQ protocols,” IEEETransactions on Communications, voL 38, pp. 773—781, June 1990.[49] R. Fantacci, “Performance evaluation of some ARQ schemes using efficient modulationtechniques and noncoherent detection,” IEEE Transactions on Communications, vol. 39,pp. 445—451, Mar. 1991.[50] R. Fantacci, “Performance evaluation of some efficient stop-and-wait techniques,” IEEETransactions on Communications, vol. 40, pp. 1665—1669, Nov. 1992.[51] G. Benelli, “New ARQ protocols using concatenated codes,” IEEE Transactions onCommunications, vol. 41, pp. 1013—1019, July 1993.[52] S. B. Wicker, “An error control technique for high data rate communication networks,”Proceedings of the 8th Annual Joint Conference of the IEEE Computer and CommunicationsSocieties, Ottawa, Ontario, Canada, pp. 594—601, 1989.[53] S. B. Wicker, “Adaptive rate error control through the use of diversity combining andmajority-logic decoding in a hybrid-ARQ protocol,” IEEE Transactions on Communications,vol. 39, pp. 380—385, Mar, 1991.Bibliography 139[54] A. Shiozaki, et al, “A hybrid ARQ scheme with adaptive forward error correction forsatellite communications,” IEEE Transactions on Communications, vol. 39, pp. 482—484, Apr.1991.[55] M. B. Pursley and S. D. Sandberg, “Variable-rate hybrid ARQ for meteor-burst communications,” IEEE Transactions on Communications, vol. 40, pp. 60—73, Jan. 1992.[56] J. J. Metzner, “Improvements in block-retransmission schemes,” IEEE Transactions onCommunications, vol. COM-27, pp. 524—532, Feb. 1979,[57] S. Lin and P. S. Yu, “A hybrid ARQ scheme with parity retransmission for error controlof satellite channels,” IEEE Transactions on Communications, vol. COM-30, pp. 1701—1719,July 1982.[58] H. Krishna and S. D. Morgera, “A new error control scheme for hybrid ARQ systems,”IEEE Transactions on Communications, vol. COM-35, pp. 981—990, Oct. 1987.[59] V. K. Oduol and S. D. Morgera, “Performance evaluation of the generalized Type-Ilhybrid ARQ scheme with noisy feedback on Markov channels,” IEEE Transactions onCommunications, vol. 41, pp. 32—40, Jan. 1993.[60] M. A. Kousa and M. Rahman, “An adaptive error control system using hybrid ARQschemes,” IEEE Transactions on Communications, vol. 39, pp. 1049—1057, July 1991.[61] M-C. Lin and M-Y, Guu, “The performance analysis of a concatenated ARQ scheme usingparity retransmissions,” IEEE Transactions on Communications, vol. 39, pp. 1869—1874, Dec.1991.[62] D. M. Mandelbaum, “An adaptive-feedback coding scheme using incremental redundancy,” IEEE Transactions on Information Theory, pp. 388—389, May 1974.[63] J. Hagenauer, “Rate-compatible punctured convolutional codes (RCPC codes) and theirapplications,” IEEE Transactions on Communications, vol. 36, pp. 389—400, Apr. 1988.[64] S. Kallel and D. Haccoun, “Generalized Type II hybrid ARQ scheme using puncturedconvolutional coding,” IEEE Transactions on Communications, vol. COM-38, pp. 1938—1946,Nov. 1990.[65] M. B. Pursley and S. D. Sandberg, “Incremental-redundancy transmission for meteor-burstcommunications,” IEEE Transactions on Communications, vol. 39, pp. 689—702, May 1991.[66] S. Kallel and D. Haccoun, “Sequential decoding with ARQ and code combining: a robusthybrid FEC/ARQ system,” IEEE Transactions on Communications, vol. COM-36, pp. 773—780, July 1988.[67] S. Kallel and D. Haccoun, “Sequential decoding with an efficient partial retransmissionARQ strategy,” IEEE Transactions on Communications, vol. 39, pp. 208—213, Feb. 1991.Bibliography 140[681 S. Kallel and C. Leung, “An efficient ARQ system for mobile communications,” Proceedingsof the 39th IEEE Vehicular Technology Conference, San Francisco, California, U.S.A., pp. 677—681, 1989.[69] S. Kallel and C. Leung, “Type II ARQ schemes with multiple copy decoding for mobilecommunications,” Proceedings of the 40th IEEE Vehicular Technology Conference, Orlando,Florida, U.S.A., pp. 349—353, 1990,[70] S. Kallel, “Analysis of a Type II hybrid ARQ scheme with code combining,” IEEETransactions on Communications, vol. COM-38, pp. 1133—1337, Aug. 1990.[71] S. Kallel and C. Leung, “Efficient ARQ schemes with multiple copy decoding,” IEEETransactions on Communications, vol. COM-40, pp. 642—650, Mar. 1992.[72] S. Kallel, “Analysis of memory and incremental redundancy ARQ schemes over anonstationary channel,” IEEE Transactions on Communications, vol. 40, pp. 1474—1480, Sept.1992.[73] S. Kallel and C. Leung, “Adaptive incremental redundancy selective-repeat ARQ schemefor finite buffer receivers,” lEE Electronics Letters, vol. 28, pp. 664—665, Mar. 1992.[74] 5. Kallel, “Sequential decoding with an efficient incremental redundancy ARQ scheme,”IEEE Transactions on Communications, vol. 40, pp. 1588—1593, Oct. 1992.[75] W. W. Chu, “Optimal message block size for computer communications with errordetection and retransmission strategies,” IEEE Transactions on Communications, vol. COM22, pp. 1516—1525, Oct. 1974.[76] J. M. Morris, “Optimal blocklengths for ARQ error control schemes,” IEEE Transactions onCommunications, vol. COM-27, pp. 488—493, Feb. 1979.[77] C. Leung and A. Lam, “Forward error correction for an ARQ scheme,” IEEE Transactionson Communications, vol. COM-29, pp. 1514—1519, Oct. 1981.[78] K. J. Guth and T. T. Ha, “An adaptive stop-and-wait ARQ strategy for mobile datacommunications,” Proceedings of the 40th IEEE Vehicular Technology Conference, Orlando,Florida, U.S.A., pp. 656—661, 1990.[79] J. A. C. Martins and J. de C. Alves, “ARQ protocols with adaptive block size performbetter over a wide range of bit error rates,” IEEE Transactions on Communications, vol. 38,pp. 737—739, June 1990.[80] 5. B. Cab and M. C. Easton, “A broadcast protocol for file transfers to multiple sites,”IEEE Transactions on Communications, vol. COM-29, pp. 1701—1707, Nov. 1981.[81] D. Towsley, “An analysis of a point-to-multipoint channel using a go-back-N error controlprotocol,” IEEE Transactions on Communications, vol. COM-33, pp. 282—285, Mar. 1985.Bibliography 141[82] K. Mase, et al, “Go-back-N ARQ schemes for point-to-multipoint satellite communications,” IEEE Transactions on Communications, vol. COM-31, pp. 583—589, Apr. 1983.[83] I. S. Gopal and J. M. Jaffe, “Point-to-multipoint communication over broadcast links,” IEEETransactions on Communications, voL COM-32, pp. 1034—1044, Sept. 1984.[84] K. Sabnani and M. Schwartz, “Multidestination protocols for satellite broadcast channels,”IEEE Transactions on Communications, vol. COM-33, pp. 232—240, Mar. 1985.[85] Y. Yamauchi, “Reliable multicast over the mobile packet radio channel,” Proceedings of the40th IEEE Vehicular Technology Conference, Orlando, Florida, U.S.A., pp. 366—371, 1989.[86] J. L. Wang and J. A. Silvester, “Optimal adaptive ARQ protocols for point-to-multipointcommunication,” Proceedings of the 7th Annual Joint Conference of the IEEE Computer andCommunications Societies, New Orleans, Louisiana, U.S.A., pp. 704—713, 1988.[871 J. L. Wang and J. A. Silvester, “Delay minimization of the adaptive go-back-N ARQprotocols for point-to-multipoint communication,” Proceedings of the 8th Annual JointConference of the IEEE Computer and Communications Societies, Ottawa, Ontario, Canada,pp. 584—593, 1989.[88] J. L. Wang and J. A. Silvester, “Optimal adaptive multireceiver ARQ protocols,” IEEETransactions on Communications, vol. 41, pp. 1816—1829, Dec. 1993,[89] D. Towsley and S. Mithal, “A selective repeat ARQ protocol for a point to multipointchannel,” Proceedings of the 6th Annual Joint Conference of the IEEE Computer andCommunications Societies, San Francisco, California, U.S.A., pp. 521—526, 1987.[90] R. Cam, C. Leung and S. Kallel, “Efficient ARQ Schemes for Point-to-Multipoint Communication,” Proceedings of the IEEE International Conference on Communications, Denver,Colorado, U.S.A., June 1991.[91] N. Shacham and D. Towsley, “Resequencing delay and buffer occupancy in selective repeatARQ with multiple receivers,” IEEE Transactions on Communications, vol. 39, pp. 928—937,June 1991.[92] M. Amniar, “Improving the throughput of point-to-multipoint ARQ protocols throughdestination set splitting,” Proc. IEEE INFOCOM, Florence, Italy, 1992.[93] R. Cam and C. Leung, “Analysis and optimization of ARQ protocols for imperfect feedbackchannels,” Proceedings of the 43rd IEEE Vehicular Technology Conference, Secaucus, New Jersey,U.S.A., May 1993.[94] G. Arredondo, et al, “Voice and data transmission,” The Bell System Technical Journal,vol. 58, pp. 97—122, Jan, 1979.Bibliography 142[951 L. B. Franks, “Carrier and bit synchronization in data communication- a tutorial review,”IEEE Transactions on Communications, vol. COM-28, pp. 1107—1121, Aug. 1980.[96] R. A. Scholtz, “Frame synchronization techniques,” IEEE Transactions on Communications,vol. COM-28, pp. 1204—1213, Aug. 1980.[97] J. C. Luetchford, et al, “Synchronization of a digital network,” IEEE Transactions onCommunications, vol. COM-28, pp. 1285—1290, Aug. 1980.[98] B. Skiar, Digital Communications: Fundamentals and Applications. Prentice Hall, 1988.[99] P. F. Driessen, “Performance of frame synchronization in packet transmission using biterasure information,” IEEE Transactions on Communications, vol. 39, pp. 567—573, Apr. 1991.[100] A. J. Viterbi, “Convolutional codes and their performance in communication systems,”IEEE Transactions on Communications, vol. COM-19, pp. 751—772, Oct. 1971.[101] J. Conan, “The weight spectra of some short low-rate convolutional codes,” IEEETransactions on Communications, vol. COM-32, pp. 1050—1053, Sept. 1984.[102] G. Begin, D. Haccoun and C. Paquiri, “Further results on high-rate punctured convolutionalcodes for Viterbi and sequential decoding,” IEEE Transactions on Communications, vol. 38,pp. 1922—1928, Nov. 1990.[103] L. C. Palmer, et al, “Synchronization for QPSK transmission via communications satellites,”IEEE Transactions on Communications, vol. COM-28, pp. 1302—1314, Aug. 1980.[1041 R. Cam and C. Leung, “Throughput analysis of two multiplexing schemes for ARQprotocols in time-varying channels,” Proceedings of the 43rd IEEE Vehicular TechnologyConference, Secaucus, New Jersey, U.S.A., May 1993.[105] S. Ross, Introduction to Probability Models, 4th ed. San Diego: Academic Press, 1989.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Multiplexing schemes and ARQ protocols for multiple-receiver...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Multiplexing schemes and ARQ protocols for multiple-receiver systems Cam, Richard 1994
pdf
Page Metadata
Item Metadata
Title | Multiplexing schemes and ARQ protocols for multiple-receiver systems |
Creator |
Cam, Richard |
Date Issued | 1994 |
Description | The throughput performances of some multiplexing and ARQ schemes are evaluated for a multiple-receiver system in which the quality of the channels varies over time. Packetized data are sent to the receivers from a server (transmitter), which uses a multiplexing scheme to assign bandwidth, as well as an ARQ protocol for error control. Two multiplexing schemes, round-robin multiplexing and an adaptive scheme, are considered. In round-robin multiplexing, each receiver is served periodically. With the adaptive scheme, the transmitter selects at each slot, the receiver whose channel quality is judged to have the highest probability of successful data packet reception. These multiplexing schemes are evaluated in conjunction with the three standard ARQ schemes, stop-and-wait, go-back-N, and ideal selective repeat ARQ. The throughput analysis takes into account the effects of feedback errors and imperfect channel state estimates. A scheme for reducing the unfavorable effects of feedback errors on the performance of continuous ARQ protocols is proposed and analyzed for a point-to-point stationary channel. In this scheme, the transmitter may not immediately retransmit a packet that has timed out but whose status is unknown due to lost feedback. Instead, the transmitter may delay retransmission for up to a given number of slots (the “retransmission delay parameter”), sending new packets in the mean time while waiting for successfully received feedback. The analysis considers the case where complete information of the receiver state is fed back to the transmitter. Under this assumption, it is shown that the effects of feedback errors can be greatly reduced when the retransmission delay parameter is optimized. This scheme is extended to the multiple-receiver system as well. Also discussed is a procedure for maximizing the effective data transmission rate of an ARQ system under certain bandwidth and power constraints. The procedure provides a means for jointly optimizing system design parameters such as the packet length, as well as coding and modulation schemes. The principles behind this procedure may also be useful for evaluating and optimizing the data transmission rate performance of the multiple-receiver system. |
Extent | 4523149 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-04-08 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0065218 |
URI | http://hdl.handle.net/2429/6992 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 1994-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_1994-953209.pdf [ 4.31MB ]
- Metadata
- JSON: 831-1.0065218.json
- JSON-LD: 831-1.0065218-ld.json
- RDF/XML (Pretty): 831-1.0065218-rdf.xml
- RDF/JSON: 831-1.0065218-rdf.json
- Turtle: 831-1.0065218-turtle.txt
- N-Triples: 831-1.0065218-rdf-ntriples.txt
- Original Record: 831-1.0065218-source.json
- Full Text
- 831-1.0065218-fulltext.txt
- Citation
- 831-1.0065218.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065218/manifest