Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Design and performance analysis of intrabuilding power line carrier sense multiple access data networks Onunga, John Ogutu 1989

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

Item Metadata

Download

Media
831-UBC_1989_A1 O57.pdf [ 8.7MB ]
Metadata
JSON: 831-1.0098211.json
JSON-LD: 831-1.0098211-ld.json
RDF/XML (Pretty): 831-1.0098211-rdf.xml
RDF/JSON: 831-1.0098211-rdf.json
Turtle: 831-1.0098211-turtle.txt
N-Triples: 831-1.0098211-rdf-ntriples.txt
Original Record: 831-1.0098211-source.json
Full Text
831-1.0098211-fulltext.txt
Citation
831-1.0098211.ris

Full Text

DESIGN A N D P E R F O R M A N C E ANALYSIS OF INTRABUILDING POWER LINE CARRIER SENSE MULTIPLE ACCESS DATA N E T W O R K S By John Ogutu Onunga B. Sc. (Electrical Engineering) University of Nairobi, 1979 M. Sc. (Electrical Engineering) University of Nairobi, 1982 A THESIS SUBMITTED IN T H E REQUIREMENTS D O C T O R OF PARTIAL FULFILLMENT OF FOR T H E D E G R E E OF PHILOSOPHY in T H E FACULTY OF G R A D U A T E STUDIES ELECTRICAL ENGINEERING We accept this thesis as conforming to the required standard T H E UNIVERSITY OF BRITISH COLUMBIA May 1989 © John Ogutu Onunga, 1989 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. a Department of H U S < J { l > C * U . • e ^ C r f t S S g f t l t t C r The University of British Columbia Vancouver, Canada DE-6 (2/88) Abstract The search for cost-effective, and flexible means of connecting computers in a lo-calized community has received considerable attention, during the last few decades. Intrabuilding power lines (IPL) provide a readily available and easily accessed net-work for data communications within buildings. In this thesis, a new generation of low-cost computer networks using carrier sense multiple access with priority ac-knowledgement (CSMA/PA) on intrabuilding power lines has been designed, anal-ysed, implemented and tested. The communication characteristics of IPL channels are summarized, and found to suffer from highly variable, ever-changing and unpredictable signal-to-noise ratio and bit error rates. CSMA is an efficient and reasonably simple means for decentralized control of access to a shared communication channel. The advantages of CSMA/PA relative to those of polling and token passing access protocols are discussed. The design and implementation of an operational five-node IPL network using CSMA/PA is described. Choice of the best data link packet length is determined from through-put measurements to approximate 1000 bits. The performance of a finite 'user CSMA/PA is analysed based on power line channel characteristics which include high and variable channel error rates, large detection delays and significant effects of acknowledgement traffic. The analysis is generally applicable to noisy channels where messages and acknowledgements share a communication bandwidth. Delay-throughput performance measurements are obtained from an actual noisy five-node intrabuilding power line network operating at transmission rates ranging ii from 1.2 - 9.6 kbit/s and shows excellent agreement with analytical results. IPL net-work performance deteriorates rapidly with increasing channel errors and changes with electrical loading over time. An adaptive automatic- repeat request (ARQ) switching scheme has been proposed and shown to be very effective in improving IPL network performance whenever the channels are in a poor quality state, while preserving the maximum achievable performance when the channels are in a good quality state. The use of such an ARQ switching scheme with FEC and proper routing algorithms provide the most effective foundation of realizing efficient and reliable intrabuilding power line computer networks. iii Table of Contents Abstract ii List of Tables viii List of Figures ix Acknowledgements xiv 1 INTRODUCTION 1 1.1 Motivation 1 1.2 Previous Work 2 1.3 Design Choice for Medium Access Protocol 4 1.4 Scope of the Thesis 5 2 P O W E R LINES AS C O M M U N I C A T I O N C H A N N E L S 7 2.1 Introduction • 7" 2.2 Intrabuilding Power-Line Circuits 7 2.3 Sources of Errors on Power Lines 9 2.4 Power Line Communication Channel Types 10 2.5 Summary 14 3 IPL C S M A / P A N E T W O R K DESIGN 22 3.1 Introduction 22 3.2 Design Specifications 23 iv 3.3 Physical Layer 23 3.4 LLC Sublayer 25 3.4.1 Flow Control 27 3.4.2 Error Control 28 3.5 MAC Sublayer 29 3.5.1 The CSMA/PA Protocol 29 3.5.2 Relative Vulnerable Period 30 3.5.3 Data Link Protocol 31 3.5.4 Data Link Layer Packet Length 32 3.6 Summary 34 4 I M P L E M E N T A T I O N OF IPL C S M A / P A 41 4.1 Introduction 41 4.2 Hardware Implementation 42 4.2.1 Physical Layer 42 4.2.2 LLC and MAC Sublayers . . . 43 4.2.2.1 Host - Protocol Board Interface 44 4.2.2.2 Protocol Board - Modem Interface 44 4.3 Software Implementation 45 4.3.1 M6854-Handler 45 4.3.2 Logical-Link-Controller . 46 4.3.3 Medium-Access-Manager 47 4.3.4 Data-Link-Driver 47 4.3.5 Frame Transmission 48 4.3.6 Frame Reception 49 4.4 Implemented IPL Networks 49 v 4.5 Summary . 50 5 ANALYSIS OF FINITE USER IPL C S M A / P A 56 5.1 Introduction . 56 5.2 Analytic Model 57 5.3 Analysis 59 5.4 Performance Measures 64 5.5 Network PKTER Determination 66 5.6 Discussion of Analytical Results 68 5.7 Summary 69 6 IPL N E T W O R K S P E R F O R M A N C E E V A L U A T I O N 74 6.1 Introduction 74 6.2 Measurement Techniques 74 6.3 Analytical vs. Measured Results 76 6.3.1 Throughput - Offered Load Performance 76 6.3.2 Delay - Throughput Performance 77 6.4 Summary • 78 7 P E R F O R M A N C E I M P R O V E M E N T STRATEGIES 96 7.1 Introduction 96 7.2 Existing ARQ-Based Performance Enhancement Schemes 97 7.3 Packetized Data Transmission on Power Lines 99 7.4 Proposed ARQ Enhancement Scheme • • • • 7.4.1 Good State (G) 101 7.4.2 Bad State (B) . . . . 101 7.4.3 Decoding with Code Combining 102 vi 7.5 Throughput Efficiency Analysis of TS-ARQ . . . . . 102 7.6 Implementation of TS-ARQ 108 7.7 Verification of Network Performance Improvement 110 7.8 Improvements in Power Line Modem Technology 113 7.9 Summary 113 8 S U M M A R Y A N D CONCLUSIONS 137 8.1 Principal Contributions . . 137 8.2 Design and Implementation of IPL CSMA/PA LAN 138 8.2.1 Design and Implementation 138 8.2.2 Cost Estimates for IPL LAN nodes . . . . . . . . . . . . . . . 139 8.3 Analysis of Finite User CSMA/PA . . . . . . . . . . . . . . . . . . . 140 8.4 Network Performance Measurements 141 8.5 Performance Improvement of IPL LANs . . . . . . . . . . . . . . . . 142 8.6 Implications for Intrabuilding Communications . 143 8.7 Remarks on Future Research . . 145 Bibliography 149 Appendices 156 A M6854 Handler 156 B Logical Link Controller 164 C Medium Access Manager 169 D Data Link Driver 174 vii List of Tables 3.1 PSK/SS modem parameters: Detection delay = 10 ms 3.2 FSK modem parameters: Detection delay = 6 ms. . . 5.1 NETWORK TIMING PARAMETERS (slot size = 10 ms) 5.2 MEASURED BER AND PKTER FOR NETWORK 1 5.3 MEASURED BER AND PKTER FOR NETWORK 2 6.1 Maximum throughput for networks 1 and 2 77 7.1 Point-point throughput efficiency improvements with Sastry's scheme. 107 7.2 Throughput efficiency comparisons for a poor quality link, N = 3; SW TS-ARQ and conventional SW ARQ . . . 112 7.3 Network performance comparisons: SW TS-ARQ and conventional SW ARQ . 112 7.4 Power Line Modems Performance Values 113 35 36 68 70 71 viii List of Figures 2.1 Power line wiring schemes in buildings, (a) Residential power deliv-ery scheme, (b) Commercial/industrial three-phase power delivery scheme 16 2.2 Signal attenuation versus frequency, (a) Industrial building, daytime. IS-short distance, in-phase channel; I-longer, but unknown distance, in-phase channel; A l , A2 - across-phase channels, (b) Industrial building, nighttime, (c) Residential apartment buildings. IL - in-phase channel, low-rise building; OL - opposite-phase channel, low-rise building; ISH - short in-phase channel, high-rise building; IH -in-phase channel, high-rise; OH - opposite-phase channel, high-rise (after [13]) 17 2.3 Received signals on fairly good quality channels. Horizontal scale, 50 ms/div; vertical scale, 2 V/div 18 2.4 Received signals on fairly poor quality channels. Horizontal scale, 2 ms/div; vertical scale, 1 V/div. (a) Impulse noise without signal, (b) Strongly attenuated signal with impulse noise and 120-Hz fades. . . 19 2.5 Measured bit error rate (BER) over a 16-hour period, (a) 2.4 Kbit/s (b) 9.6 kbit/s. . . 20 2.6 Measured packet error rate (PKTER) over a 16-hour period, (a) 2.4 kbit/s (b) 9.6 Kbit/s 21 3.1 IEEE 802 reference model . 24 ix 3.2 Timing diagrams (a) Modem timing (b) RTS, CTS and DCD signals 26 3.3 HDLC packet structure 31 3.4 Throughput efficiency vs packet length, 1.2 Kbps data rate, (a) Fairly good channel (b) Poor quality channel 37 3.5 Throughput efficiency vs packet length, 2.4 Kbps data rate, (a) Fairly good channel (b) Poor quality channel 38 3.6 Throughput efficiency vs packet length, 4.8 Kbps data rate, (a) Fairly good channel (b) Poor quality channel 39 3.7 Throughput efficiency vs packet length, 9.6 Kbps data rate, (a) Fairly good channel (b) Poor quality channel 40 4.1 Power line network node 42 4.2 Address Decoding 51 4.3 Protocol board schematic: CPU and decoding diagram . . . . . . . . 52 4.4 Protocol board schematic: Memories and Protocol Controller diagram 53 4.5 IPL CSMA/PA high level flowchart 54 4.6 Power line network with five nodes 55 5.1 Slotted finite user nonpersistent CSMA/PA channel analytic model . 59 5.2 Throughput - offered load curves in finite population slotted Non-persistent CSMA/PA channel, (a) Network 1 (b) Network 2 . . . . . 72 5.3 Delay - throughput curves in finite population slotted Nonpersistent CSMA/PA channel, (a) Network 1 (b) Network 2 73 6.1 Nonpersistent IPL CSMA/PA: S vs G at 1.2 kbit/s for network 1 . . 80 6.2 Nonpersistent IPL CSMA/PA: D vs S at 1.2 kbit/s for network 1 . . 81 6.3 Nonpersistent IPL CSMA/PA: S vs G at 2.4 kbit/s for network 1 . . 82 x 6.4 Nonpersistent IPL CSMA/PA: D vs S at 2.4 kbit/s for network 1 . . 83 6.5 Nonpersistent IPL CSMA/PA: S vs G at 4.8 kbit/s for network 1 • • 84 6.6 Nonpersistent IPL CSMA/PA: D vs S at 4.8 kbit/s for network 1 . . 85 6.7 Nonpersistent IPL CSMA/PA: S vs G at 9.6 kbit/s for network 1 . . 86 6.8 Nonpersistent IPL CSMA/PA: D vs S at 9.6 kbit/s for network 1 . . 87 6.9 Nonpersistent IPL CSMA/PA: S vs G at 1.2 kbit/s for network 2 . . 88 6.10 Nonpersistent IPL CSMA/PA: D vs S at 1.2 kbit/s for network 2 . . 89 6.11 Nonpersistent IPL CSMA/PA: S vs G at 2.4 kbit/s for network 2 . . 90 6.12 Nonpersistent IPL CSMA/PA: D vs S at 2.4 kbit/s for network 2 . . 91 6.13 Nonpersistent IPL CSMA/PA: S vs G at 4.8 kbit/s for network 2 . . 92 6.14 Nonpersistent IPL CSMA/PA: D vs S at 4.8 kbit/s for network 2 . . 93 6.15 Nonpersistent IPL CSMA/PA: S vs G at 9.6 kbit/s for network 2 . . 94 6.16 Nonpersistent IPL CSMA/PA: D vs S at 9.6 kbit/s for network 2 . . 95 7.1 TS-ARQ packet control field 109 7.2 TS-ARQ algorithm flowchart 116 7.3 TS-ARQ algorithm state diagram 117 7.4 F and P vs. p; code-combining using majority voting 118 7.5 Throughput efficiency TIGB VS p, n; RT = 100 118 7.6 Throughput efficiency T)GB VS p, n; RT = 500 119 7.7 Throughput efficiency TJGB VS p, n; RT = 1000 119 7.8 Throughput efficiency rjGB vs p, n; RT = 2000 120 7.9 Throughput efficiency rjGB vs p, n; RT = 5000 120 7.10 Throughput efficiency r\GB vs p, n; RT = 10000 121 7.11 Effects of RT/n values and code-combining on throughput efficiency (»?GB); N = 3 . . . . 121 xi 7.12 Effects of RT/n values and code-combining on throughput efficiency: {VGB)\ N = 5 122 7.13 Effects of RTfn values and code-combining on throughput efficiency {T]GB); N = 7 122 7.14 Effects of RT/n values and code-combining on throughput efficiency [rfB)i N = 3 123 7.15 Effects of RT In values and code-combining on throughput efficiency {I?B)5 N = 5 . . . , 123 7.16 Effects of RT/n values and code-combining on throughput efficiency {t}B);N = 7 124 7.17 Effects of RT values on Sastry's throughput efficiency; RT = 100 . 124 7.18 Effects of RT values on Sastry's throughput efficiency; RT = 10000 125 7.19 Variation of Sastry's throughput efficiency with the retransmitted packet copies N 125 7.20 Comparison of throughput efficiency for TS-ARQ and Sastry's ARQ at 1.2 kbit/s 126 7.21 Comparison of throughput efficiency for TS-ARQ and Sastry's ARQ at 2.4 kbit/s 126 7.22 Comparison of throughput efficiency for TS-ARQ and Sastry's ARQ at 4.8 kbit/s 127 7.23 Comparison of throughput efficiency for TS-ARQ and Sastry's ARQ at 9.6 kbit/s . 127 7.24 Measured throughput efficiency rj vs. N for a SW TS-ARQ on a typical poor quality link 128 7.25 IPL CSMA/PA using TS-ARQ: S vs G at 1.2 kbit/s for network 2. Curve I: TS-ARQ; curve II: conventional SW ARQ . . 129 xii 7.26 IPL CSMA/PA using TS-ARQ: D vs S at 1.2 kbit/s for network 2. Curve I: TS-ARQ; curve II: conventional SW ARQ 130 7.27 IPL CSMA/PA using TS-ARQ: S vs G at 2.4 kbit/s for network 2. Curve I: TS-ARQ; curve II: conventional SW ARQ 131 7.28 IPL CSMA/PA using TS-ARQ: D vs S at 2.4 kbit/s for network 2. Curve I: TS-ARQ; curve II: conventional SW ARQ 132 7.29 IPL CSMA/PA using TS-ARQ: S vs G at 4.8 kbit/s for network 2. Curve I: TS-ARQ; curve II: conventional SW ARQ 133 7.30 IPL CSMA/PA using TS-ARQ: D vs S at 4.8 kbit/s for network 2. Curve I: TS-ARQ; curve II: conventional SW ARQ 134 7.31 IPL CSMA/PA using TS-ARQ: S vs G at 9.6 kbit/s for network 2. Curve I: TS-ARQ; curve II: conventional SW ARQ 135 7.32 IPL CSMA/PA using TS-ARQ: D vs S at 9.6 kbit/s for network 2. Curve I: TS-ARQ; curve II: conventional SW ARQ 136 8.1 Typical integration of IPL LANs into existing computer networks . . 148 xiii Acknowledgements I would like to express my deep gratitude to my research supervisor Dr. R.W. Donaldson for his guidance and encouragement throughout the course of this re-search. His dedication is sincerely appreciated. I am very greatful to Mr. Wesly Mundy for making available the PSK spread spectrum modems and Mr. Ronald Jeffery for his technical and laboratory assistance in completing this thesis. I am indebted to the Canadian Commonwealth Scholarship and Fellowship Ad-ministration for financially supporting my studies at UBC. Finally, I would like to thank my family, Risper and Odhiambo, for their en-couragement and support throughout the course of my studies at UBC. xiv Chapter 1 INTRODUCTION 1.1 Motivation There is ever an increasing demand for intrabuilding local area networks (LANs) for various applications including office automation, building environmental man-agement, energy-use monitoring and control, security and fire-alarm monitoring, electronic messaging, computer communications and point-of-sale networking. Be-cause they are virtually universal in building coverage and easily accessed via stan-dard wall plugs, intrabuilding electric power distribution circuits are potentially useful for local area networking. Their use obviates the need for specialized wiring which can be costly to install, unattractive to view and restrictive in the location of equipment served by the network. Power lines were not designed for data communications and suffer from high and unpredictable variations in impedance, signal attenuation and noise [1,2]. These transmission impairments impose severe limitations on data transmission speed for power line networks. As a result only very low speed (60 - 1200 bps) power line net-works for basic remote control and monitoring functions have been reported in the past. Recently, considerable effort has been devoted to developing medium speed (1.2 - 19.2 kbit/s) power line modems, [11,12], and to determining the communi-cation characteristics of intrabuilding power line (IPL) channels, including their impairments and bit-error probability performance [13,14], The development of 1 power line modems with enhanced data rates has increased the need for medium speed power line networks capable of supporting personal computer communications and other applications [28]. There is now a need for an in depth study, including design, analysis, implemen-tation and testing of medium access protocols suitable for intrabuilding power line networks in the 1.2 - 19.2 kbit/s range. The results of such a study is the subject of this thesis. 1.2 Previous Work Electric power distribution lines have been used by the power industry for com-munication purposes including remote meter reading, load management and other applications [7]. In addition, several very low speed (60 - 1200 bps) commercial power line networks are available for use. However, these networks are used only for basic monitoring functions and remote control applications. The BSR X-10 power line network [20] uses a polling scheme between a centralized unit (master) and a maximum of 255 light/appliance modules (slaves) at 120 bps. BSR X-10 does not use any forward-error-correction (FEC) or automatic-repeat-request (ARQ) to combat channel errors and costs approximately CAN$50 for each command unit and CAN$25 for each remote module. The NONWIRE power line network [21] is similar to BSR X-10 in design but employs a positive acknowledgement driven ARQ scheme at 1200 bps and costs CANS 1000 per master or slave. The EXpertNet sys-tem [22] is similar to NONWIRE and BSR X-10 at the protocol level. Its modem's data rate is 700 bps and costs between US$100 to US$200 per modem. Existing power line networks have been used only for very low speed applications that do not involve enquiry/response regimes. For enquiry/response applications, 2 throughput as well as delay are important, and polling is not necessarily the pre-ferred medium access protocol. The overhead associated with polling can signifi-cantly increase response time on power line networks. Efficient LAN protocols have been reported in the past that can be employed whenever message throughput and delay are of significant importance. These include CSMA/CD, token bus and token ring. Token bus is expensive to implement while token ring is restricted to use with ring topologies. CSMA and its versions have been studied extensively by many au-thors [54] - [65]. Tobagi and Kleinrock [57] and Elsanadidi et al [63] have analysed CSMA with priority acknowledgement (PA), a version of CSMA that appears to be particularly well suited for noisy channels requiring the use of ARQ error control schemes. The work by Tobagi and Kleinrock [55] considers the problem of hidden terminals in packet switched radio channels and proposed a busy tone solution. Power line networks can suffer from possible hidden terminals problems because of high and variable signal attenuation and noise. However, busy tone requires the use of a separate channel and is therefore unattractive for power line channels, with their limited bandwidth (~ 100 - 150 kHz). As well, there is no assurance that the tone would reach all network stations. Repeaters proposed by Lytle and Strom [23] could be used on power line net-works, to facilitate communication between stations served by links with poor signal-to-noise characteristics. Capacitive coupling could be used across the distribution transformer phases and between primary and secondary in some instances; how-ever, when high noise levels, long signal paths, and high line loading exist, this type of coupling is not adequate. An active repeater located across the distribu-tion transformer phases could be employed to combat the large signal-to-noise ratio degradation across these distribution transformers; however, regulatory approval would then be required. 3 1.3 Design Choice for Medium Access Protocol Power line channels have a bus/tree topological broadcast structure. Suitable access protocols for such LANs include polling, CSMA/CD and token bus. The following realities bear on the choice of protocol. (i) Implementation costs for power line LANs should be low. The advantage of these networks is the availability of the communication lines at zero incre-mental cost. The inherent communication capabilities of power line links are variable and limited, and high cost modems, protocol hardware and software are hard to justify. (ii) In many applications, terminals would exhibit bursty and highly variable traffic profiles which would change over time. (iii) Frequent addition and removal of terminals would be common in many appli-cations. (iv) Because of the variability of communication signal attenuation and noise char-acteristics of IPL networks, all network stations may not be able to receive transmissions from all other stations at all times. One solution to this problem is to install repeaters to facilitate communication between otherwise isolated stations [23]. (v) To simplify modem hardware implementation and because of bandwidth limita-tions, it is advantageous for messages and acknowledgements to co-operatively share the same frequency spectrum. (vi) It is shown in section 3.5.2 that the relative vulnerable period associated with CSMA on intrabuilding power lines is usually low [24]. This is essential for high throughput efficiency. The above factors indicate that CSMA/PA [57] to be a suitable choice of medium access control protocol for power line LANs for many applications. Polling can be inexpensive to implement, particularly in software, and would be well suited for selected applications only [46]. Polling can be inefficient under light or highly asymmetrical terminal loads, or when polling lists must be updated frequently as network terminals are added and removed. Further, the potentially high probability of central station failure discredits pure polling as the protocol of choice for power line networking. Token passing [10] is efficient under heavy symmetric loads, but can be expensive to implement. Serious problems could occur with lost tokens on noisy, unreliable network paths [28]. CSMA is efficient except under very heavy network traffic loads, readily accommodates addition and deletion of terminals, and is particularly efficient for many low duty cycle, bursty terminals. CSMA readily accommodates use of repeaters to effect transmission between two terminals hidden from each other [23]. A primary advantage of CSMA/PA is its potentially low implementation cost and the high system reliability achievable even in noisy environments. Collision detection (CD) enhances the performance of CSMA [25]. On power line networks the variation in received signal and noise levels make collision detection difficult and unreliable. In a noisy environment it is easy for noise to be mistakenly regarded as the beginning of a transmission from a station. 1.4 Scope of the Thesis The primary goal of this thesis is to consider design issues involved in selecting a medium access protocol for power line LANs, to design, implement and test 5 CSMA/PA and to analyse, measure and describe the throughput and delay perfor-mance of CSMA/PA for an operational network. In chapter 2, power line communication channel characteristics are summarized. The design of CSMA/PA protocol for IPL networks including the choice of link-level packet length is considered in chapter 3. A length of approximately 1000 bits is found to be appropriate. In chapter 4, the architecture for implementing this protocol is described. Chapter 5 presents the analysis of CSMA/PA that includes the effect of channel errors on both message and acknowledgement packets, user population size and modem detection and synchronization delay. In chapter 6, delay-throughput performance is measured at 1.2, 2.4, 4.8 and 9.6 kbit/s using spread spectrum modems and compared to earlier analytical results. Excellent agreement is observed between the two sets of results. The variability of communication signal attenuation and noise characteristics as well as the need for modem synchronization with every transmitted packet severely degrades power line data networks' performance on poor quality links. In chapter 7, an adaptive automatic repeat request (ARQ) error control technique is proposed to combat such performance degradations, while maintaining high throughput ef-ficiency on good links. The technique is analysed and implemented, and found to significantly enhance delay-throughput performance. Chapter 8 includes a summary of the research results as well as suggestions for future research. 6 Chapter 2 P O W E R L I N E S A S C O M M U N I C A T I O N C H A N N E L S 2.1 Introduction The performance of power line data networks is dependent on the power line modems used, the characteristics of power line channels, and the network access protocol employed. Poor quality power line channel characteristics degrade the maximum achievable CSMA/PA delay-throughput performance. In this chapter, power line wiring schemes in buildings and communication char-acteristics are summarized. Noise patterns as well as bit and packet error rates on typical power line communication channels are also presented. 2.2 Intrabuilding Power-Line Circuits Figs. 2.1(a) and 2.1(b) diagram power line wiring schemes in buildings. Residential houses or apartment units are typically supplied from a distribution transformer powered by one of the three distribution phases at voltage levels ranging from 10 to 50 kV. The distribution side of the distribution transformer in Fig. 2.1(a) delivers split-single- phase power to residential circuits panels from which power is delivered to electrical loads via intrabuilding branch circuits [4]. The neutral wire is normally grounded at the service panel and is therefore common to all electrical loads. The hot wire directly connects all loads on any phase. Indirect connection of loads between phases is provided by capacitive coupling across the distribution 7 transformer secondary, or across loads such as electric water heaters which connect across phases [15] (see Fig. 2.1). General residential branch circuits consist of a 120-V line and a neutral line; these circuits deliver power to light loads, some of which may be controlled by one or two switches. Each large appliance is individually supplied by special dedicated branch circuits. Hot-water tanks, which typically draw 3 kW at 240 V, are con-nected directly across the 120-V supply lines, as are heating elements in electric ranges and in clothes dryers. The dryer motor, as well as dryer and range lamps and timers, is normally connected between the 120-V line and neutral. Refrigera-tors, home freezers, dishwashers, garbage disposals, and forced-air motor drivers all have their own individual branch circuits consisting of a 120-V line and neutral. Commercial and industrial buildings are typically supplied with three-phase power as indicated in Fig. 2.1(b). In large buildings, several distribution trans-formers may be used, with each providing power to a specific part of the building. Standard branch circuits consisting of a 120-V and neutral line supply standard electric loads. Larger loads are supplied by circuits that deliver either single-phase or pbly-phase power [4]. Electrical loads provide signal transmission paths from one phase to another. These paths are in addition to the path provided by inherent capacitive or other [3] coupling across the transformer secondary. Loads may also provide signal trans-mission paths between a 120-V line and the neutral line, and will attenuate com-munication signal transmissions between two points, even if these are on the same 120-V. Loads may also provide multiple signal transmission paths between two nodes. Although propagation delay in IPL networks is negligibly small, it is possible that a signal could interfere with itself repeatedly arriving at its intended destination 8 having travelled by paths of different lengths [56]. Communication signals above about 20 kHz do not pass through distribution transformers [9]. A transformer isolates that portion of an intrabuilding power line LAN which it serves from LANs served by other transformers. Interconnection of these LANs, for communication purposes, would be by a separate backbone cable or radio network as shown in Fig. 8.1. In large buildings, separate distribution transformers supply each floor or group of floors, thereby partitioning a building into several, separate LANs. Impedance on power line is known to approximate 10 f2, but varies with electrical loading, increases with frequency, and becomes increasingly inductive as frequency increases [5,6]. 2.3 Sources of Errors on Power Lines The main causes of channel errors on power lines are signal attenuation, impulse noise and narrow band signal fades. Fading and impulse noise occurring on power line channels tend to be periodic [13,42]. Because electrical loading changes over time, signal attenuation between any pair of network points also varies over time: such variations can exceed 20 dB (power) over a 24-hour period [13]. Attenuation between any two points is frequency dependent, and increases with frequency. Attenuation between different pairs of points is different at any given moment by up to 40 dB. Signal attenuation from power line loads would be particularly high on long transmission paths with many loads between the transmitter and the receiver. Finally, attenuation can exhibit short-time periodic variations at 120 Hz or even at 6 Hz. Power line noise includes both background and impulse components. Noise is caused primarily by electrical loads [2]. Periodic impulse noise is nearly always 9 present on power lines and is the major cause of channel errors [13]. Periodic power line noise at 120, 240, or 360 Hz is caused by loads such as SCRs which operate in synchronism with the 60-Hz power waveform. Single event impulse noise results from thermostat switching, lightening and switching of power factor correction ca-pacitor banks. Periodic impulse noise which is non-synchronous with the 60-Hz power waveform arises from television receivers and electronic clocks. Noise is also produced by non-synchronous loads such as electric drills with dc motors. Back-ground and impulse noise levels vary over time and with point of observation. Noise power levels tend to decrease as frequency increases at approximately 30 dB/decade [3,5], This decrease in noise level occurs because noise as well as wanted signals suf-fer increased attenuation with frequency. Noise sources nearest to a receiver are the primary cause of bit-errors. Power line fading is normally periodic with frequency at twice the 60-Hz power voltage frequency or its submultiples and varies with time due to the time variation of the electrical load profile. Periodic 6 Hz and 120 Hz signal fades can occur, prob-ably due to impedance modulation; these cause periodic degradation in received signal to noise ratio which in turn causes periodic burst errors in digital transmis-sions. Severe periodic signal fades are rare, but when they occur, they cause large numbers of periodic burst errors. 2.4 Power Line Communication Channel Types In general, power line network links can be regarded as being of either fair or poor quality. The primary determinant of quality is signal attenuation between two points. Attenuation depends primarily on the physical wiring design and network electrical loads. 10 Fair quality power line channels are generally characterized by low signal at-tenuation (below approximately 20 dB), while poor channels exhibit high signal attenuation (above approximately 20 dB). The attenuation for both fair and poor channels can also vary over time because of variations in electrical loading. Periodic impulse noise is nearly always present on fair and poor links and is a major cause of channels errors. Periodic signal fades can, and do occur on fair and on poor links. Severe channel fades are rare, but can occur primarily on poor channels. Because of low attenuation on fair links, channel errors do not necessarily occur periodically at each impulse or fading points, except whenever the signal-to-noise ratio drops below a predetermined threshold level. Reliable packet transmission is therefore generally possible on fair channels. High signal attenuation on poor links can prevent network nodes from 'hearing' each other. This hidden terminal problem is one of the major causes of performance degradation on power line networks with poor channels. Transmissions between nodes that can barely 'hear' each other are further degraded by the ever present periodic impulse noise or signal fades. Transmission of normal length packets on poor links is often difficult, and is virtually impossible during severe signal fades. Fig. 2.2 shows signal attenuation vs. frequency, as reported in [13]. Each curve in Fig. 2.2 represents attenuation as measured between two specific network points during a time interval of approximately 0.5 h. For easy reference, we denote signal transmission as in- phase (I) when the transmitter and receiver use the same 120 V power line. Across-phase transmission (A) indicates that the transmitter and receiver use different three-phase 120 V power lines. Opposite-phase transmission (O) applies when the transmitter and receiver use different 120 V split single- phase power lines. The daytime measurements in Fig. 2.2(a) show that in-phase attenuation over 11 a short 10 m distance (denoted by IS) is relatively flat and is less than 5 dB over most of the frequency range considered. Over longer unknown distances, typically between 20 and 300 m, the attenuation varies from 25 dB for frequencies below 60 kHz to 50 dB at 200 kHz. Comparison of curve I to curves A l and A2 shows that across-phase transmission did not always result in larger attenuations than in-phase transmission; A l and A2 denote transmission from phase fa and fa and from fa to fa, respectively. Fig. 2.2(b) shows results for the same building at night. The same transmitter and receiver locations were used in the night as in the day. At any specific frequency, attenuation between two network points varies by up to 20 dB from day to night because of network load changes. Results for the residential apartment buildings, taken during 6-8 pm, appear in Fig. 2.2(c). Above 50 kHz, attenuation in the low-rise building is less than in the high-rise, even when low-rise transmissions go to opposite phase. Above 140 kHz in the high-rise, opposite-phase transmission shows several decibels less attenua-tion than in-phase transmission. Other results, not shown here, demonstrate the substantial effects of specific loads on signal attenuation. For example, energiz-ing an electric range, which connects directly across the two split phases, reduced attenuation between phases by 34 dB. The signal and noise patterns in Figs. 2.3 and 2.4 are based on measurements taken in the electrical engineering building at the University of British Columbia. They show signal attenuation and noise patterns from typical fair and poor channels. Fig. 2.3 shows a received signal vs. time, over a one-half sec. interval on a fairly good quality channel. One sees 120 Hz spikes as well as periodic 6 Hz fades. Fig. 2.4(a) shows impulse noise in the absence of a transmitted signal on a poor quality channel. Some of the spikes are 8 V, peak-to-peak, and are as large in voltage as the signal in Fig. 2.3. A recent paper describes the amplitude, width 12 and interarrival distributions of power line noise impulses, as well as simple means to reduce their harmful effects on transmitted data [16]. Large variations in received signal-to-noise ratio as well as in BER can occur over time for transmissions between two network points. These variations can result from changes in the signal level, the noise level or both, at the receiving site. Fig. 2.5 shows BER for transmissions between two different node pairs, as measured over a 16-hour period. The vertical bars indicate the measurement standard deviation. The fairly good channel is typical of what is available in our electrical engineering building. The poor quality channel is one of a few for which the bit error rate is unusually high. Fig. 2.5 shows BER variations up to three orders of magnitude between some network node pairs, over the 16-hour period. Over all network node pairs, even wider BER variations were observed. The results in Figs. 2.5 and 2.6 were obtained using a direct sequence PSK spread spectrum modem. Each point in Figs. 2.5 and 2.6 represents an average obtained by transmitting data alternately, in each direction, between two network points for several minutes until at least 100 bit errors were counted. Bit and packet error rates were measured at the same time, using a Hewlett Packard Data Error Analyser, Model 1645A. The HP Data Error Analyzer stops counting channel errors momentarily whenever clock slips (phase hits) or drop-outs (loss of synchronization) occurs, as these conditions can easily invalidate bit error rate measurements. Stream data is divided by HP 1645A into 1000-bit blocks for packet error rate measure-ments. Fig. 2.6 shows measured PKTER for 1000-bit packets without error correction. Also shown, for comparison purposes, are PKTER's which would result if the bit errors occurred randomly. The fact that measured PKTER is less than the calcu-lated value indicates that bit errors tend to occur in bursts as observed in [13] and 13 this author [42]. 2.5 Summary In this chapter, intrabuilding power line wiring schemes, signal paths and power line channel communication characteristics have been summarized. The following general conclusions can be drawn from the characteristics of intrabuilding power line channels. 1. Single-phase signal transmission paths for communication purposes are provided by power lines, and by loads connected to 120-V supply line and the neutral conductor. 2. Across-phase signal transmission paths are provided by loads connected across different phases or by high-pass filter (capacitive) couplings across the trans-former secondary. 3. Loads can attenuate communication signals between two points even if these points are on the same 120-V phase. 4. A transformer isolates that portion of an intrabuilding power line LAN which it serves from LANs served from other transformers, since communication signals above a few kHz can not pass through distribution transformers. 5. Attenuation between any two points is frequency dependent, tends to increase with frequency and varies over time due to variations in electrical loading. Such variation can exceed 20 dB over a 24-hour period. 6. Attenuation between different pairs of points is different at any given moment by up to 40 dB. 14 7. Periodic impulse noise is nearly always present on power lines and is a major cause of channel errors. 8. Periodic 6 Hz and 120 Hz signal fades can occur on power lines. 9. Measured PKTER shows that bit errors occur in bursts on power lines. 10. Power line channels can be regarded as either fair or poor links, depending on attenuation characteristics determined by the electrical wiring scheme and electrical loading. 11. The hidden terminal problem arising from high signal attenuation on poor links is one of the major causes of performance degradation on power line data networks. High channel error rates on IPL network channels impose severe limitations on power line data transmission rates. Appropriate power line modem designs and reliable network protocols must be employed to realize high performance IPL data networks. 15 DISTRIBUTION TRANSFORMER 25 KV POWER LINE TO RESIDENCE B 120V /o! NEUTRAL 120 V /1B0 POWER LINES BRANCH CIRCUITS -BRANCH CIRCUITS (b) Figure 2.1: Power line wiring schemes in buildings, (a) Residential power delivery scheme, (b) Commercial/industrial three-phase power delivery scheme. 10. FREQUENCY (KHz) (b) Or FREOUENCV (KHz) (c) Figure 2.2: Signal attenuation versus frequency, (a) Industrial building, daytime. IS-short distance, in-phase channel; I-longer, but unknown distance, in-phase chan-nel; A l , A2 - across-phase channels, (b) Industrial building, nighttime, (c) Resi-dential apartment buildings. IL - in-phase channel, low-rise building; OL - oppo-site-phase channel, low-rise building; ISH - short in-phase channel, high-rise build-ing; IH - in-phase channel, high-rise; OH - opposite-phase channel, high-rise (after [13])-17 short 6-Hz fades 120-Hz spikes (a) long 6-Hz fades 120-Hz spikes Figure 2.3: Received signals on fairly good quality channels. Horizontal scale, 50 ms/div; vertical scale, 2 V/div. 18 (a) (b) Figure 2.4: Received signals on fairly poor quality channels. Horizontal scale, 2 ms/div; vertical scale, 1 V/div. (a) Impulse noise without signal, (b) Strongly attenuated signal with impulse noise and 120-Hz fades. 19 1x10° 1x1 tr1 a 1x10* m o I 1x10"3 O w Hi . ar 1x10-* m 1x10-* IxlO-* A — i T ' • ; BER at 2.4 kbit/s Fair channel Poor channel 4.0 6.0 8.0 10.0 1 2.0 1 4.0 16.0 1 8.0 20.0 22.0 Time of Day (hours) (a) 1x10° 1x10"1 |r E 1x102 \r 0C 1x10 O fc U l 1x10^  CD IxlO"5 r» -1x10* 1 ' 1 r i • i ' i • i ^ * K "V... BER at 9.6 kbit/s Fairchannel Poor channel 1 4.0 6.0 8.0 10.0 12.0 14.0 16.0 18.0 20.0 22.0 Time of Day (hours) (b) Figure 2.5: Measured bit error rate (BER) over a 16-hour period, (a) 2.4 Kbit/s (b) 9.6 kbit/s. 20 1x101 r ^1x10° -UJ "1x10' 1 CO 111 I 1x10-' 1x10-' 1x10^  i 1 r -i 1 . 1 1 1 1 1 1 1 r J I.-. ! • PKTER at 2.4 kbiVs Fair channel — Poor channel • , • Random error model values J , I i I i 1 , l_ 4.0 6.0 8.0 10.0 12.0 14.0 16.0 Time of Day (hours) _L 18.0 20.0 22.0 (a) 1x101 r . 1 r-^1x10° r DC CO rx 2 1U IxlO"1 r 1x102 o 8. IxlO"3 1x10W I 1 r i 1 r • •m 1 PKTER at 9.6 kbit/s Fair channel Poor channel • , • Random error model values _L - I I L . I L . 4.0 6.0 8.0 10.0 12.0 14.0 16.0 18.0 20.0 22.0 Time of Day (hours) (b) Figure 2.6: Measured packet error rate (PKTER) over a 16-hour period, (a) 2.4 kbit/s (b) 9.6 Kbit/s. 21 Chapter 3 IPL C S M A / P A N E T W O R K D E S I G N 3.1 Introduction An initial step in the design of broadcast computer networks involves coarse evalua-tion of optimum operating values of design parameters such as channel bandwidth, effective propagation delay, number of bits per packet, and relative vulnerable pe-riod. As well careful selection of network control procedures to optimize perfor-mance and maintain a high degree of system reliability with minimal implementa-tion cost is essential. Power line channel characteristics impose severe limitations on the IPL LANs' design parameters. Existing LAN protocols must be modified accordingly to suit IPL LANs. This chapter explores the design issues involved in tailoring IEEE/std 802 LAN protocol for power line networking. In particular, we consider a systematic selection of IPL network parameters as well as the design of CSMA/PA medium access control protocol. We also consider the associated flow and error control procedures at the logical-link-control (LLC) level. Only the interface services between the LLC sublayer and the lower network layers that are likely to be affected by the medium access methodology or physical layer used are considered in this design. 22 3.2 Design Specifications A medium speed (1.2 - 19.2 kbit/s) intrabuilding power line LAN using broad-band signalling to combat power line noise is desired. The network implementation must be simple, economical and reliable, while maintaining acceptable delay-vs-throughput performance indices under changing numbers and locations of termi-nals, and under varying traffic levels. To date, a marketable cheap thin ethernet for IBM PC/XT/AT network using commercially-available BNC "T" -type coaxial cable connectors and RG58 coaxial cable in a daisy chain costs approximately $350 (U.S.A. dollars) per station [26]. This amount does not include the cost of the RG58 coaxial cable and BNC connectors. Also excluded is the labor and material cost of installing cable conduits or trays, which can sometimes exceed $15,000 (U.S.A. dollars) per building. Radio LANs could be less expensive; however, radio involves licensing and interference. The finished IPL network should cost much less than $300 per station, and must be an industry standard to enable end users to easily interconnect network elements from various manufactures. Following the IEEE 802 standards, a three-layered hierarchical protocol struc-ture comprising the physical layer, medium access control (MAC) sublayer and the logical link control (LLC) sublayer shown in Fig. 3.1, was adopted for design purposes [27]. These last two sublayers constitute the data link layer in the OSI seven-layer model [27]. 3.3 Physical Layer The physical layer included a FSK modem (4.8 - 19.2 kbit/s) and PSK/SS (1.2 - 9.6 kbit/s) modem. These transmit and receive raw data between peer MAC entities, on intrabuilding power lines. The physical layer protocol provides synchronization 23 H I G H E R L A Y E R S service access points M M ) -L O G I C A L L I N K C O N T R O L S U B L A Y E R D A T A L I N K L A Y E R M E D I U M A C C E S S C O N T R O L S U B L A Y E R P H Y S I C A L L A Y E R Figure 3.1: IEEE 802 reference model 24 between the MAC sublayer and modems by exchanging request-to- send (RTS), clear-to-send (CTS) and data-carrier-detect (DCD) signals. Fig. 3.2 shows modem timing and modem-MAC synchronization signals. Be-cause of high power line noise levels, a power line modem needs time, initially, to determine whether it is receiving noise or a wanted signal. The vulnerable period (detection-delay) of 6-10 ms is the time needed by the modem to listen to and determine whether or not the channel is idle. The actual transmitter-to-receiver propagation delay is a few microseconds, and is negligible in comparison with this listening time. The data-carrier-detect (DCD) linger is the time needed by a re-ceiving modem to determine that transmission has stopped. DCD linger necessarily varies between 5-20 ms depending on the noise level at the receiver. 3.4 L L C Sublayer The LLC sublayer constitutes the higher sublayer of the data link layer (see Fig. 3.1) and is common to the various medium access methods that are defined and supported by the IEEE/std 802 activity. IEEE 802 defines two types of data link control services namely: (i) data-link-connectionless service that offers no flow or error control (assumes these services are provided by higher layers), and (ii) data-link-connection-oriented service that supports sequential delivery of protocol data units (PDUs) and a comprehensive set of data link layer error recovery techniques. Based on these definitions LLCs further define two types of services: (i) type I - does not require a data-link connection establishment prior to any exchange of PDUs and does not use acknowledgements, and (ii) type 2 - requires a data link connection establishment prior to any exchange of PDUs and uses acknowledgements. Type 2 data-link-connection-oriented service has been selected here. This service enables 25 N5 Oq" C <-i n CO jo H B 5 OP O B B 5 Oq 3 O H CO P> a a. a o a 01 dq ' 3 T R A N S M I T T E R I D L E T I M E T X 1 I 1 / D C D P R E A M B L E A C K T X D C D L I N G E R T I M E L I N G E R RTS CTS D C D , RTS S E N T R X M O D E M S | B E G I N T R A C K I N G C T S ( D C D A C T I V E ) G R A N T E D I I (a) V P 6- 10 ms D C D L I N G E R 5-20 ms 20.5 ms 7 ms F S K P S K (b) Figure 3.2: Timing diagrams (a) Modem timing (b) RTS, CTS and DCD signals the simple and reliable flow and error control schemes required to combat power line channel errors to be implemented in the LLC sublayer. Only the interface services to the MAC sublayer required to provide error-free transmission between a local and peer LLC sublayer entities (i.e. flow and error control services) have been considered for implementation. Our LLC sublayer pro-vides a modified version of the flow and error control procedures specified by IEEE 802.2 type 2 LLC protocol, in order to support the CSMA/PA protocol and error control schemes required to simplify design and maintain high system reliability on noisy channels with high bit error rates. 3.4.1 Flow Control Flow control is a technique for assuring that a transmitter does not flood a re-ceiving station with data. Flow control is usually implemented by sliding window protocols in which a single acknowledgement (ACK) is required for n frames. The window size, n, determines the protocol efficiency, complexity and buffer require-ments. IEEE 802.2 type 2 standard provides flow control by go-back-N sliding window protocol with a window size equal to 128. Stop-and- wait (SW) is the sim-plest form of sliding window protocol with window size equal to 1. SW flow control was used here because it is an appropriate protocol for half-duplex transmissions supported by power line modems, is easy to implement and can enable reasonably high information throughput. To ensure high throughput, the transmitter idle time must be small compared to the packet transmission time, as is evident from the SW protocol efficiency given below [30,31]: r, = , icn/ * - (3.1) 27 In ( 3.1) Pc is the probability that the transmitter receives an ACK packet following a collision-free transmission of an information packet, R is the bit transmission rate, n is the total number of bits in an information packet, k is the number of data bits in information packet and T is the transmitter idle time i.e. the time during a transmission cycle when the channel is not available to carry information packets (see Fig. 3.2a). 3.4.2 Error Control An extremely reliable error control scheme is required to combat the large signal-to-nbise ratio degradations which occur on power lines. Error control can be achieved by using either forward-error-correction (FEC) or automatic- repeat-request (ARQ), or both. ARQ is particularly simple, reliable and relatively insensitive to the kinds of errors that occur on actual channels. The performance potential of ARQ on noisy channels is well known. Various ARQ schemes have been proposed and im-plemented: the best known are the stop-and- wait, go-back-N and selective-repeat-request ARQ schemes. IEEE 802.2 type 2 standard provides error control using go-back-N ARQ. Positive acknowledgement driven SW ARQ was selected to achieve cost effective network implementation and high system reliability. In principle, enough redun-dancy is included in the transmitted packet to allow the receiver to detect most channel errors. Positive acknowledgements are used to indicate packet acceptance by the receiver. No ACK packets are returned to the transmitter whenever er-rors are detected in the information packet. In such cases the transmitter times out and retransmission occurs. Following IEEE 802.3 standards, the maximum at-tempt limit, when channel errors or packet collisions are excessive, has been set to 16. Further attempts above this limit would be routed through a repeater [23], 28 rescheduled until a later time or abandoned. 3.5 M A C Sublayer The purpose of a MAC sublayer is to allocate the multiaccess medium among the various network nodes, at any given time. The CSMA/PA protocol used to achieve this allocation is a version of CSMA in which ACK packets share the same channel as information packets. These ACK packets are subject to channel errors. 3.5.1 The C S M A / P A Protocol CSMA/PA is a version of CSMA in which there is cooperation between transmit-ters. One result of such co-operation is that information packets do not interfere with ACK packets. IEEE 802 standard supports CSMA/CD (802.3) as one of its standards for medium access control. On power lines, collision detection is not possible for reasons given in section 1.3. CSMA/PA on the other hand enables eco-nomical realization of networks requiring the use of ACKs and is particularly well suited for use on noisy channels with limited bandwidth. The protocol operates as follows: (i) If the channel is sensed idle then: a) If the packet to be transmitted is an information packet then, the station transmits the packet d seconds (d denotes detection delay) later if and only if the channel is still idle. b) If the packet to be transmitted is an ACK frame then the station transmits the packet immediately without incurring the d seconds delay. 29 (ii) If the channel is sensed busy then the station follows the protocol in question (nonpersistent, 1-persistent or p- persistent), repeating step (i) whenever the channel is sensed idle. The above protocol clearly gives acknowledgements priority over data packets. Such a strategy avoids collision between acknowledgements and data, thereby re-ducing channel idle time to maintain a high SW protocol efficiency. It is assumed here that all transmissions are addressed to a single station. In those applications where one station sends to a plurality of stations, some means would be required to arbitrate channel access for the ACK packets originating from the various receiving stations. 3.5.2 Relative Vulnerable Period Efficient CSMA operation on power line LANs is critically dependent on whether or not the ratio of detection delay to packet transmission time, a (relative vulnerable period), is much less than 1; a = ^ (3.2) The relative vulnerable period for various optimum packet lengths achievable on power line is shown in tables 3.1 and 3.2 for PSK/SS and FSK power line modems, respectively. It is seen that only for relatively high data rates on poor quality channels is the relative vulnerable period potentially too large [40] - [42]. Efforts to develop faster and reliable power line modems with lower detection delays continue. Recently developed differential PSK (DPSK) and PSK modems in the Department of Electrical Engineering, University of British Columbia, have detection delays between 1-4 ms. Lower detection delays will improve CSMA/PA performance by further reducing the relative vulnerable period. 30 F L A G A D D R E S S C O N T R O L D A T A F C S F L A G Figure 3.3: HDLC packet structure 3.5.3 Data Link Protocol The high-level data link control (HDLC) bit oriented frame structure shown in Fig. 3.3 was selected for the MAC sublayer. The frame starts with an opening flag and ends with a closing flag. A preamble of 56 bits is automatically transmitted by power line modems at the beginning of transmission of every frame. Between the opening and closing flags, a frame contains address, control, information (optional) and frame check sequence fields. The flag fields delimit frames with the unique binary pattern 01111110. All active stations continuously monitor for the flag sequence, to synchronize on the start of a frame. Since the HDLC frame allows arbitrary bit patterns, bit stuffing is used to avoid flags occurring in the non-flag part of the frame. The transmitter inserts an extra 0 bit after each occurrence of five l's in the frame (with the exception of the flag fields). At the receiver, after detecting a starting flag, the receiver monitors the bit stream. When a pattern of five l's appear, the sixth bit is examined. If this bit is 0 , it is deleted. If the sixth bit is a 1 and the seventh bit is a 0, the combination is accepted as a flag. The 8 bits following the opening flag are the address field. The address field can be extended such that the address length is a multiple of seven bits. The eighth bit in each octet is 1 or 0 according to whether or not it is the last octet of the address 31 field. The single octet address 11111111 is interpreted as the all-station addresses. The extendable 8 bits following the address field is the control field. The infor-mation in control field differentiates information from ACK packets. The data field is a multiple of 8-bits and is present only in information frames. The frame check sequence (FCS) is applied to the remaining bits of the frame, exclusive of the flags. The universal 16-bit CRC-CCITT generated by X 1 6 + X 1 2 + X 5 + 1 has been used to implement the SW ARQ scheme [28]. The 16-bit CRC-CCITT guarantees the detection of any error pattern in an n-bit block, with the following characteristics: odd number of random errors, double random errors, 2 pairs of adjacent random errors, error burst up to 16 bits, 99.997% of bursts up to 17 bits and 99.998% of bursts up to 18 bits or longer [31] - [33]. The undetected error probability is therefore assumed to be negligible throughout this thesis. 3.5.4 Data Link Layer Packet Length One of the most important parameters in the design of data link layer protocols is the length of the information packets. Arguments like those in [50] show that throughput efficiency r\ is given by ( 3.3) below as well as by ( 3.1). k 77 ~ E(n + RT0Ut) + {n + na + RI) ( " ' In ( 3.3) na and n denote the number of bits in ACK and information packets respectively, E is the mean number of retransmissions of an information packet, Tout is the transmitter time out period, / is the time prior to and following transmission of information and ACK packets; J therefore includes preamble, CSMA access delay and DCD linger. For random error channels with bit error probability p, the optimum packet 32 length n0 is as follows [50] H + RT P (3.4) where p is the bit error probability, T is the transmitter idle time, and H is the number of header bits including flags, address, control and frame check sequence (Note that T = / + na/R). The term H + RT in equation ( 3.4) represents the number of bits per block of actual data used for addressing, checksum, flags and required idle time. The optimum packet length represents a compromise between a high retransmission probability resulting from channel errors, and low efficiency resulting from an unreasonably small fraction of the channel capacity being devoted to the transmission of actual data bits. It has also been shown that small devia-tions from the optimum packet length do not seriously degrade throughput from its maximum obtainable value, which is [50] Tables 3.1 and 3.2 show values of n0 calculated for various p values, using the values of T observed for our power line modems. The n0 value increases as R increases and as p decreases. On actual power line channels, errors tend to occur in bursts and periodically, probability varies over a wide range, and the optimum packet length would have to be based on some appropriate weighting over the range of error probabilities encountered. Rather than undertake the difficult task of analytically determining the best packet length for the data link layer, the throughput efficiency vs. packet length on various links was measured. For each packet length and each pair of transmission and reception points, packets were transmitted as on point-to-point link (i.e. no CSMA contention). The value of E in equation ( 3.3) was determined for (l-2Hp){l-py/n?i (3.5) unless special precautions are taken to randomize errors [14]. As well, the bit error 33 each successful transmission, and n was calculated. This procedure was repeated 20 times, over a period of approximately 15 minutes, to yield an averaged throughput efficiency represented on a graph in Figs. 3.4 - 3.7. All measurement results shown were taken on weekdays during normal working hours, when bit error rates are typically at their worst levels. Results presented here are for PSK/SS modem. The vertical bars denote measurement standard deviation. The "ideal channel" curve in Figs. 3.4 - 3.7 is applicable in the absence of any channel errors. This curve is calculated using the known values for the parameters in equations ( 3.1) and ( 3.3), with Pe and E = 0. The measured results fall below the ideal channel curve, because of packet retransmissions resulting from channel errors. The damaging effect of errors on throughput efficiency is evident, particularly on the poor channel at 9.6 kbit/s, where the efficiency is well below ten percent for all packet lengths. Figs. 3.4 - 3.7 indicate that packet lengths in excess of 1000 bits do not yield much of an increase in throughput efficiency [40] - [42]. For 1000 bit packets this efficiency is approximately 75 percent in the absence of channel errors, and degrades as retransmissions increase. Across-phase transmissions do not necessarily lead to throughput values below those which result when a transmitter and a receiver are on the same power phase. The coupling mechanisms noted earlier (see Fig. 2.1) are effective in providing across-phase signal transmission. 3.6 Summary The task of designing a LAN involves a systematic selection of the LAN's param-eters as well as its protocol control procedures, to meet some desired performance 34 requirements. Power line channels have impairments not found in other LAN me-dia. These impairments can cause large modem detection delays and imply the need for relatively short data link packet lengths. The IEEE 802 standard has been employed to design IPL LANs with modifications listed below. 1. CSMA/PA medium access control is proposed instead of CSMA/CD to maintain high system reliability and to minimize cost. 2. SW flow control instead of go-back-N is suggested to simplify network design. 3. SW ARQ error control instead of go-back-N ARQ simplifies network design and indicates high system reliability. The vulnerable period on power lines is typically 10 ms. However, efficient CSMA/PA operation can be achieved since the relative vulnerable period is usually less than unity for the data rates considered here (1.2 - 19.2 kbit/s). Continuing power line modem development work indicates the possibility of realizing modems with reduced detection delays that would further improve CSMA/PA performance. Point-to-point measurements on power lines indicate that packet lengths in excess of 1000 bits do not yield an increase in throughput efficiency. 35 Table 3.1: SS/PSK modem parameters: Detection delay = 10 ms. ii! (Kbps) T(ms) P Optimum packet lengths a 1.2 127 10"5 3,682 bits 0.0033 10"4 1,164 bits 0.0103 10"s 368 bits 0.0362 10"2 116 bits 0.103 2.4 103 10"5 4,298 bits 0.0056 10"4 1,359 bits 0.018 lO"3 430 bits 0.056 lO"2 136 bits 0.176 4.8 82 10"5 6,705 bits 0.0073 lO"4 2,121 bits 0.023 10~3 671 bits 0.073 10~2 212 bits 0.227 9.6 60 10"8 7,949 bits 0.012 lO"4 2,514 bits 0.038 10"3 795 bits 0.121 lO"2 252 bits 0.381 Table 3.2: FSK modem parameters: Detection delay = 6 ms. R (Kbps) T(ms) P Optimum packet lengths a 4.8 72 10~6 4,800 bits 0.006 10"4 1,518 bits 0.019 10"3 480 bits 0.060 10"2 152 bits 0.194 7.2 68 10~6 5,477 bits 0.008 lO"4 1,732 bits 0.025 10"3 548 bits 0.079 lO"2 173 bits 0.250 9.6 66 10"5 6,119 bits 0.009 lO"4 1,935 bits 0.030 10"3 612 bits 0.094 10"2 193 bits 0.298 19.2 63 10"8 8,139 bits 0.014 10"4 2,574 bits 0.045 i 10"3 814 bits 0.142 10"2 257 bits 0.448 36 u c « o a. JC O ) 3 O i 1 1 1 r "i 1 r — Ideal channel .... Fair channel 1.2 kbit/s J L J L 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 1.3 1.4 1.5 Packet Length (Kbits) (a) c a o w S a. £ O ) 3 O 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 1 J I I / I -0" — Ideal channel .... Poor channel 1.2 kbit/s \nl J L •-4-4 _L 1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 1.3 1.4 1.5 Packet Length (Kbits) (b) Figure 3.4: Throughput efficiency vs packet length, 1.2 Kbps data rate, (a) Fairly good channel (b) Poor quality channel 37 "i 1 1 r o c a u Ui •5 D> 3 O — Ideal channel .... Fair channel 2.4 kb'rt/s 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 1.3 1.4 1.5 Packet Length (Kbits) (a) Figure 3.5: Throughput efficiency vs packet length, 2.4 Kbps data rate, (a) Fairly good channel (b) Poor quality channel 38 Packet Length (Kbits) (a) T i i i i i i i 1 1 r Packet Length (Kbits) (b) Figure 3.6: Throughput efficiency vs packet length, 4.8 Kbps data rate, (a) Fairly good channel (b) Poor quality channel 39 Figure 3.7: Throughput efficiency vs packet length, 9.6 Kbps data rate, (a) Fairly good channel (b) Poor quality channel 40 Chapter 4 I M P L E M E N T A T I O N O F IPL C S M A / P A 4.1 Introduction The basic goal of every implementation is to realize a system that functions as required and is reliable, easy to maintain, and cost effective. Normally, simplic-ity of implementation is the key to the attainment of this goal. VLSI LAN con-troller chips simplify LAN implementations and increase their processing speeds. However, only widely accepted LAN standards are commercially available in VLSI technology. For instance, the Intel 82586 LAN coprocessor and Motorola's 68590 LAN controller implement the IEEE 802.3 10Base5 (CSMA/CD- Ethernet) LAN, with timing specifications not possible on power line channels. The use of a gen-eral purpose data-link-driver chip provides the only viable approach to achieving a simple IPL LAN implementation! The Motorola 68B54 is a flexible, hardware programmable data-link-controller chip that can be tailored by a designer to suit a variety of applications including CSMA/PA. The design of IPL CSMA/PA LAN was performed in chapter 3 by careful se-lection of given IPL network parameter values and protocol procedures, to simplify implementation and maximize network performance. In this chapter, the architec-ture of our CSMA/PA implementation is described. Each power line network node consisted of a PSK/SS modem and a protocol board as shown in Fig. 4.1. This architecture facilitated easy implementation of several host independent IPL LAN 41 H O S T T E R M I N A L O R C O M P U T E R Figure 4.1: Power line network node nodes that could be used for network performance measurements. 4.2 Hardware Implementation 4.2.1 Physical Layer The physical layer consisted of a PSK/SS power line modem. These modems use direct sequence spread spectrum NRZ pseudo random code signal to multiply the baseband data signal. This product then PSK modulates a carrier. The modem can transmit at data rates of 1.2, 2.4, 4.8 and 9.6 kbit/s, at 38.4 or 115 kHz carrier and 19.2 code (chip) rate. Spread spectrum is useful at data rates below 4.8 kbit/s to combat narrow band signal fades or peaks in the noise spectral density, to allow data rates vs. error rate trade-offs without changing the transmitted signal bandwidth and to enable multiplexing [1]. At data rates above 4.8 kbit/s, the signal bandwidth of conventional PSK or FSK is normally high enough to overcome narrowband impairments. Frame synchronization and modem bit and carrier synchronizations were achieved at the physical level using flags and preamble sequences, respectively. P R O T O C O L I N T E R F A C E U N I T ( P I U ) P O W E R L N E M O D E M 42 Fast code synchronization of the PSK/SS modem was achieved using 60-Hz zero-crossings [l]. 4.2.2 L L C and M A C Sublayers Both the LLC flow and error control services and the MAC sublayer have been implemented on the protocol board. Software has been traded off for hardware to increase the protocol execution speed at a slightly increased cost [34] - [36]. The MC68B54, an Advanced Data Link Control (ADLC) chip, under control by the 8-bit MC68B09 microprocessor, forms the heart of the power line protocol board. This ADLC chip greatly facilitated the design and speed performance of the protocol board. A 74LS139 dual two-to-four decoder was used to select a 16Kx8 EPROM (27128A), a 32Kx8 static RAM (HM62256P), a MC68B40 programmable timer module (PTM), a S6551 asynchronous communication interface adapter (ACIA) or the ADLC chip. The EPROM uses 14 address lines, Aq - AI3, to address its 16K bytes. Similarly the RAM uses 14 address lines, A0 - A13, to address its 16K bytes and is enabled during read and write cycles, with gating to convert the R/W control signal from the CPU to the RD and WR pair required by the HM62256P RAM. The EPROM contains initialization system vectors and routines as well as the protocol software, and was put in the upper 16K of memory ($C000 - $FFFF) because power-on reset starts the processor at location $FFFE and $FFFF [37]. The protocol board address decoding is shown in Fig. 4.2. An interrupt-driven I/O scheme was used to provide efficient asynchronous data transfer between the PTM, ACIA and ADLC I/O devices in real-time. The PTM and ACIA chips' interrupt request lines were connected together via a "wired-OR" arrangement to the interrupt request (IRQ) processor line, while the fast interrupt request line (FLRQ) was used by the ADLC chip as shown in the protocol board's 43 schematic diagram in Fig. 4.3. The timer chip was programmed to provide external clock interrupts every 1 ms for protocol timing purposes. 4.2.2.1 Host - Protocol Board Interface Standard RS-232 interfacing was used between the host terminal or computer and the protocol board, which includes the S6651 ACIA chip operating asynchronously to transfer data over the RS-232 interface. A 1489 and a 1488 level converting chip provided conversion between TTL (+5V) and RS-232 (±12V) levels. The asynchronous data transfer between the ACIA and processor was carried out one character (8 bits + 1 stop bit) at a time by interrupts. 4.2.2.2 Protocol Board - Modem Interface The ADLC chip provided the interface between the protocol board and the power line modem. This chip transmits and receives data in HDLC frame format similar to that shown in Fig. 3.3. The frame includes flags, address, control, optional data and FCS fields. The chip performs bit-stuffing and automatically appends flags and FCS fields to frames. The frame check sequence implemented in ADLC uses the 16-bit CRC-CCITT polynomial X 1 6 + Xn + X5 + 1 [37]. Both the transmitter and receiver polynomial registers are initialized to "l's" prior to calculation of the FCS. The transmitter calculates the FCS on all bits of the address, control and data fields and transmits the complement of the resulting remainder as FCS. The receiver performs a similar computation on all bits of address, control, data and received FCS fields and compares the result to F0B8, and if they match, the frame valid status bit is set in the status register. Otherwise the the error status bit is set. The protocol software stored in EPROM memory and executed by the 68B09 microprocessor works with the ADLC chip's hardware error detection capability 44 to implement efficient and reliable SW flow and error control. Synchronization between the ADLC chip and modems was accomplished by RTS, CTS and DCD signals. 4.3 Software Implementation The IPL LANs' software was written in ' C high level language and compiled by the MS-DOS Introl ' C cross-compiler for an IBM PC/XT/AT. ' C offers a better direct control over the microprocessor's architectural features, while the Introl ' C cross-compiler generates a highly optimized and efficient machine code. The software was partitioned into four modules to achieve separation of generic capabilities and ap-plications as follows: (1) a low level module called M6854-handler interacts directly with the ADLC chip, (2) a high level module called logical-link-controller (LLC) provides IPL LAN flow and error control, (3) a medium-access-manager (MAM) module allocates power line channel to various network nodes and (4) a data-link-driver (DLD) provides a menu driven human interface via asynchronous terminal or host computer for network measurement purposes. A high level flowchart of the protocol is shown in Fig. 4.5. The four modules are described in the following sections. Program listing of major routines are shown in the appendices. 4.3.1 M6854-Handler This module contains the lowest level software for the power line modem control system. The handler's routines accept strings of bits from the higher level software (MAM) and sends them to the modem via the ADLC chip. They also receive strings of bits from the modems, buffer these bit strings, and present them to the MAM. Receiving is done using interrupts (background), transmitting is done 45 without interrupts (foreground). The M6854-Handler maintains two linked lists of receive buffer descriptors (RBDs). Each RBD is associated with a receive buffer and contains all the information about that receive buffer as well as a pointer to the next RBD on the list [38,39]. Free and complete RBD lists are maintained for empty and received frames, respectively. To conserve memory, only 6 RBDs are allocated at initialization time. Received frames whose RBDs are in the complete RBD list must therefore be served immediately and returned to the free RBD list. 4.3.2 Logical-Link-Controller IEEE 802.2 defines the functions provided by the LLC sublayer as follows. 1. Initiation of control signal interchange. 2. Organization of data flow. 3. Interpretation of protocol data unit (PDU) and generation of appropriate PDUs' response. 4. Actions regarding error control and error recovery. Type 2 LLC procedures use asynchronous balanced operation mode (ABM) which consists of data-link connection, information transfer, resetting and disconnection phases. A typical type 2 LLC service sequence requires the originating LLC to establish a connection with a remote LLC by sending a timed out connection com-mand request to the remote LLC prior to any transfer of PDUs. Upon reception of an acknowledgement, the LLC service sequence enters data transfer phase. Type 2 LLC service has been used to enable simple and reliable flow and error control schemes be implemented in the LLC sublayer. The logical-link-controller 46 module performs flow and error control by using SW with predetermined packet lengths and timed out transmission and retransmissions, respectively. Whenever the ACK timeout clock expires, the retxn-mgmt routine delays for an integer multiple of slot time before retransmitting the packet. Rx-error-mgmt provides performance improvement by utilizing errored packets as described in chapter 7. 4.3.3 Medium-Access-Manager The functions defined and provided by IEEE 802.3 MAC sublayer include 1. Framing/deframing. 2. Error checking. 3. Acquiring the right to use the underlying physical medium. The medium-access-manager module contains routines required to perform func-tions pertaining to framing and deframing of data packets, error checking and medium allocation. The tx-link-mgmt function is at the heart of medium allo-cation. The scheduling of retransmissions is determined by the backoff function which randomizes the time of the beginning of each retransmission. The correlation between the random numbers generated by any two stations at any given time is minimized by seeding each nodes' random number generator with its own source address. MAM routines are described in sections 4.3.5 and 4.3.6. 4.3.4 Data-Link-Driver Network measurements require that every node monitors the reception of complete packets, and be available to generate and transmit packets at all times. To meet 47 these requirements the data-link-driver (DLD) module was written that continu-ously checks received packets and immediately sends acknowledgements for suc-cessfully received packets. The DLD also monitors keyboard inputs, generates new packets and transmit new and rescheduled packets. At initialization time, DLD calls init-6854 which initializes the ADLC chip and sets up the data structures. 4.3.5 Frame Transmission At the beginning of a transmission process, the DLD module calls choose-dst to randomly choose a destination address. The DLD then calls tx-frame which uses tx-frame-encap to construct the frame from the chosen destination address, control information and the user data in the transmit buffer. Next, tx-link- mgmt is called to perform the actual transmission. The tx-link-mgmt monitors the DCD signal provided by the modem via the ADLC chip and avoids contention by deferring to passing traffic. If a valid frame is received, deferring is aborted in order to return an ACK. Once the channel is detected idle, priority accesss is used to give priority to acknowledgement packets. If the channel is still idle at the end of this priority delay, send-bits is called to send out the frame bytes to the ADLC. Prior to passing packets to the modems, the ADLC chip adds flags and FCS, and deletes these upon reception of frames from the modem. Send-bits sends a buffer out to the ADLC and returns a status indicator back to the calling program. The status indicator is zero if transmission is successful, and non-zero otherwise. The routine starts by activating RTS, then waits for CTS. If CTS does not become valid in a predetermined length of time, the routine returns CTS timeout error. Otherwise it starts sending data bytes to the ADLC. With each data byte sent, the routine checks CTS lost and transmission underrun bits in the ADLC chip, and returns the appropriate code whenever any of these conditions 48 occur. The trajismission of the last bit of the data field causes the ADLC chip to automatically transmit FCS field and append a closing flag. 4.3.6 Frame Reception The ADLC chip continuously searches for flags. When a flag is detected, the ADLC chip establishes frame synchronization to the flag timing. Thereafter the isr-6854 interrupt service routine reads in characters asynchronously from ADLC chip at a rate determined by the power line modems. The first byte causes get- new-rbd to obtain a new RBD from the free RBD list and mark it active. De- stuffing and CRC check is automatically done under ADLC as the frame is received. At the end of a frame reception (whether reception is complete or aborted), put-complete-rbd is called to update the active RBD's status information (time of reception and completion status). Next, DLD calls get-rbd which returns a pointer to the oldest RBD in the system. If the RBD's frame is valid, an acknowledgement is returned to the sender immediately, otherwise the sender times out and retransmits. 4.4 Implemented IPL Networks We implemented two intrabuilding power line local area networks, each with five nodes as illustrated in Fig. 4.6, for performance testing purposes. Network 1 consisted of fairly good lines while network 2 was carefully chosen to include some poor quality lines. The networks were located in the electrical engineering building at the University of British Columbia. The 70,000 sq. ft. building itself has four floors and is powered from a single, three-phase distribution transformer. Electrical loads include office equipment, numerous computers, machine shop equipment and 49 air-conditioning fan motors. Details of how such buildings are wired, as well as their signal attenuation and noise properties have been presented elsewhere [7,8] and will not be repeated here. The two lines between every network nodes in Fig. 4.6 represent the different BER in the forward and feedback channels on power line. 4.5 Summary Simplicity of implementation is the key to realizing of a reliable, easy to maintain and cost effective system. Microprocessor based system implementation was used to obtain better performance at lower cost and simpler construction than by use of discrete logic chips. The MC68B54 ADLC chip simplified the design and en-hanced protocol execution speed. The 2 MHz ADLC chip used can handle parallel 8-bit data transfers at a maximum of 1.5 Mbit/s. However, the software overhead of the interrupt handling routines reduces this ADLC maximum data rate to ap-proximately 140 kbit/s. This is therefore the maximum data rate the implemented protocol board can handle. The software was written in ' C high level language and was partitioned into M6854-handler, logical-link-controller, medium-access-manager and data-link- driver modules. The modular software design used allows future extensions or modifica-tions to affect only individual modules [53]. An IPL LAN with five nodes was implemented for performance testing purposes. Internal host computer based protocol board implementations may be less ex-pensive than what we used. However, these would have required the dedicated use of several computers during measurements. With external implementation, terminals as well as computers can be used for measurements. 50 memor 1 dec . ADDRESS BUS Oder DEVICES ADDRESS RANGE SIZE (BYTES) Enbte Selct TO MEMORY DEVICES A15 A14 A13 A12 A11 A10 A9 A8 A7 A6 A5 A4 A3 A2 A1 AO 1 1 X X X X X X X X X X x x X X ROM 0 C000 - FFFF 16K 1 0 x X X X X X X X X X X X X X RAM 0 8000 - BFFF 16K IO dec oder Enable Select ' TO IO DEVICES 0 X X 1 1 X X X X X X X X X X X PTM 1800 - 1FFF 2K 0 X X 1 0 x X X X X x x X X X X ADLC 1000 - 17FF 2K 0 X X 0 1 X X X x x x x x x x x ACIA 0800 - OFFF 2K 0 X X 0 0 X x x X X X X x x X x SPARE 0000 - 07FF 2K Figure 4.2: Address Decoding Figure 4.3: Protocol board schematic: CPU and decoding diagram 52 Cn CO TO C >-» to o e-t-o O o_ cr o cn B o X" c a P> o c-t-o r> o o 3 >-* St 5' era + 5 V 3 TRANSMIT BiTS RECEIVE INTERRUPTS Figure 4.5: IPL CSMA/PA high level flowchart 54 Node Power Line Link i Pab (Bit error probability from a to b) Pba (Bit error probabilty from b to a) (a) (b) Figure 4.6: Power line network with five nodes 55 Chapter 5 ANALYSIS OF FINITE USER IPL C S M A / P A 5.1 Introduction Many versions of CSMA have been proposed and analysed since the pioneering work on the CSMA protocol by Kleinrock and Tobagi [67]. Most of these studies have, however, been based on some or all of the following assumptions: infinite number of users, error-free transmission, negligible modem detection delay and zero-cost acknowledgements. These assumptions lead to results which are useful for some applications but inappropriate for others. For example, local area networks (LANs) which use intrabuilding power lines or mobile radio networks fail to satisfy some or all of these assumptions. Infinite population models are easier to analyse because of their memoryless property - each station has at most one packet at any time, and the transmission of each packet is independent of the others in the network [66]. Most previous authors who have analysed networks with high channel error rates or included acknowl-edgement traffic have resorted to infinite population models to facilitate analysis. Studies that have taken acknowledgement traffic into consideration [54,63] have assumed infinite population and error free channels. Finite population models are difficult to analyse because packets that have not been transmitted must be queued by individual users. In the analysis of CSMA LANs with buffered users, a problem of great interest is how to account for the 56 statistical dependence among the user queues (interference of user queues) in the network. Classical queueing theory does not provide closed form solutions to the queueing problem. As a result, previous studies involving interacting queues prob-lem have resorted to approximate techniques. Tobagi and et al. have used approx-imate technique to analyse CSMA with finite user populations [55,57]. However, they did not consider channel errors or acknowledgement traffic. In this chapter and in recent papers by this author [43,45], we analyse the per-formance of CSMA/PA having finite number of users. Our contribution involves the development of an analytical approach to determine the effects of channel errors and acknowledgement traffic on performance. First, we obtain expressions for delay and message throughput which include the effects of number of users, detection delay and packet error probability. Next, measurements on actual intrabuilding power line networks are used to estimate packet error probability on various net-work links. These estimates are then used with our analytical results to calculate message throughput and delay performance. Measured delay and throughput per-formance for an operational five- node intrabuilding power line LAN are compared with calculated values in chapter 6, to verify our analytical approach. 5.2 Analytic Model Power line channels exhibit periodic fading and noise statistics that are different from those for mobile radio networks. The channels have high bit error rates on both the forward and backward directions resulting in large detection times. The protocol requires the use of acknowledgements to combat channel errors. We shall therefore assume: 1. Noisy and fading transmission channels. 57 2. Finite number of users. 3. Message packets of fixed duration. 4. Acknowledgements (ACKs) of fixed duration. 5. Message and ACK packets subject to channel transmission errors. 6. Message retransmission delay geometrically distributed with mean value l/w (slots). We consider a system of M users. Each user is either backlogged (a packet in its buffer) or thinking (empty buffer). A user whose message transmission was unsuccessful due to collision or channel errors or was blocked because of a busy channel is backlogged. A backlogged user cannot generate a packet for transmission and can switch to thinking state only after successfully transmitting its buffered packet. Following the model adopted in [55], a slotted version of nonpersistent CSMA/PA is considered here. The time axis is (mini-) slotted with a d sec. slot size, where d is the detection delay. Packet transmission requires T slots. All terminals are synchronized to start transmission only at the beginning of a slot. It is assumed that the cycles (busy and idle periods) evolve as an imbedded Markov chain with "imbedded" slots coinciding with the first slot of each idle period. Fig. 5.1 shows the analytical model. The length of a successful information transmission period is equal T + 2 slots. The term T + 2 accounts for (i) the initial d sec. delay introduced by the priority scheme, (ii) packet transmission time and (iii) the detection delay incurred by the packet (included in the information transmission period, since it is only d sec. after completion of the transmission that the channel is sensed idle). Similarly the length of an ACK transmission period is w + 1 slots 58 EMBEDDED POINTS • I (slots) IDLE PERIOD T + 2 (slots) INFO TRANSMISSION PERIOD w + 1 (slots) ACK TRANSMISSION PERIOD T + ijJ + 3 (slots) BUSY PERIOD CYCLE (slots) Figure 5.1: Slotted finite user nonpersistent CSMA/PA channel analytic model (time required to wait for positive acknowledgement following a successful packet transmission). The cycle is extended by w +1 slots when transmission is successful. If packet transmission is unsuccessful because of either channel errors (in the forward or feedback channel) or collision, the sender times out before retransmitting the packet. Unsuccessful busy periods are therefore extended by Tout +1 slots (time-out period). 5.3 Analysis To obtain the channel backlog (queued packets) per cycle, we sum the channel back-logs at the beginning of every slot. We assume that the backlog (Nt) in every slot forms a discrete-time semi-Markov process which depends only on the immediately 59 previous state. Define: i = The number of backlogged users in the current slot. k = The number of backlogged users in the next slot. Nt = The number of backlogged users at the beginning of slot t. te = Initial slot number in a cycle. Nte = The state of the system at the first slot (time te). a = The probability that a user in thinking state generates a packet. v = The probability that a user in backlogged state resenses the channel. PIA = Link packet error probability. Pu is the probability that a packet is accepted by a receiver and an ACK is successfully returned on a link. Pntw = The average of {PIA} over all network links. / = The length of the idle period (in slots). T = The packet transmission time (in slots). u = The time (in slots) required by the transmitter to wait for a positive ac-knowledgement when a packet is successfully transmitted. Tout — The transmitter timeout period (in slots). This is the time required for the transmitter to decide that there is no acknowledgement coming because of unsuccessful packet transmission. Tout is set just above u. 60 I + T + UJ + 3 = The length of a cycle (in slots), for succesful transmission. We first obtain the number of backlogged packets for each user in a cycle. By definition, no terminal is ready during the interval [te,te + 1 — 2]; however, at least one terminal is ready during the interval [te,te + I — 1] (a ready terminal has either a new or backlogged packet). All terminals which become ready at te + I—1 will sense the channel idle and will initiate ACK priority delay followed by packet transmission at the beginning of slot te + I. Given that Nte+i-i = i, the probability that some terminal is not ready to send at the beginning of slot te + I is (1 — i/)'(l — a)M~\ For t 6 [te + J - 1, te + I] Define the one-step transition matrix between slot te + I — 1 and te + I, given that transmission activity starts at slot te + I and is successful, with elements s,k = Pr[Nte+i = k and transmission is successful / Nte+i-i = i], for i = 0, 1, 2, ... . It follows that 0 ( l - g p ' M l - y ) ' ' - ' ! 1 - ( 1 - I / ) ' ( 1 - < T ) M - « for k < i for k = i l - f l - i / W l - t r ) * * - . - I O r AC X T J. for k > i + 1 Similarly, given that transmission activity starts at slot te + I and is unsuccessful, the one-step transition matrix between slot [te + I — l] and [te + I] denoted by fa for i = 0, 1, 2 is fik = Pr[iVte+j = k and transmission is unsuccessful / Nte+r-i = i]. Define k k\{n - k)\ 61 Then 0 for k < i ( 1 - ( T ) m - [ 1 - ( 1 - I / ) ' - » V ( 1 - » / ) ' - 1 1 for k = i fik = ' l-{l-v)'(l-a)M-' for k = i + 1 i - ( i - i / )«( i - tT )w-« for k > i' + 1 For t e [te + I, te + I + T + u + 2] Terminals that become ready in slot te+I—1 will start priority delay in slot te+I. No delay is incurred in checking the channel because modems listen continously to the channel while not transmitting. Ready packets in slot te + I will find the channel idle initially, but will be blocked from transmitting at the end of their priority delay. Therefore all ready terminals in the transmission interval [te + I, te +1 + T + u + 2] will effectively sense the channel busy and will be blocked from transmitting. These terminals remain backlogged if already backlogged, or switch to the backlogged state if they were in the thinking state. The one-step transition matrix, Q = between successive slots in the interval [te + I, te +1 + T + u + 2] (the transmission interval), for i = 1, 2, is tj,-* = Pr[iVt = k/Nt^i = t], where If matrix J represents a decreases of 1, following a successful transmission, then 0 for k < i M - i (1 - a)M~k(Tk-i for k > i (\ k - i J 1 for A; = t - 1 Jik = \ 0 otherwise 62 The system state (Nte) constitutes an imbedded Markov chain with transition matrix P . The one-step transition matrix between consecutive imbedded points has elements Pnk = Pr[Nte+i+T+w+2 = k/Nte = n\. Matrix P is therefore the product of all previously considered single-slot transition matrices in a cycle. Acknowledgement traffic causes the cycle times for a successful and unsuccessful transmissions to be different. If the transmission is successful, the busy period has a length T + w + 3; if transmission is unsuccessful, the length of the busy period is T + Tout + 3. The transition matrix P is therefore given by P = S Q T + U + 3 J + P Q T + T O U T + 3 (5.1) Given M (finite), a and u, our finite Markov chain is ergodic and a stationary probability distribution exists. We denote the latter by n=[7ro, . . . T T J , . . . 7 T M ] , where OTJ = lim Pr[Nte = j] te—*oo Moreover since the states are recurrent nonnull (time to return to a state is finite), the set [TTJ] of our ergodic Markov chain is a stationary probability distribution and the quantities fly are uniquely determined [6] from 1 = Z)~o ^ a n < * = S,~o or simply by solving the system equation n = I I P Let Ps be the probability that a packet does not suffer collisions or channel errors (ie. no channel errors in the information and ACK packets) in which case packet transmission is successful. Given that the system state Nte = i, P3 is given by P - (1 ~ P^){M - *>(! ~ o)"*-1^ - uY + iu{l - vy-^l - a)M-* 1 - ( 1 - * / ) < ( ! - < T ) W - " 63 Idle period duration distribution Given that Nte = i, the probability that no terminals become ready during slot t is c5,- = (1 — f)'(l — a)M~%. The probability that the idle period = k is Pr[I = k/Nte = i] = (1 — e5,-)e5*-1. The average idle period is therefore given by oo k-l / = ( i - * ) E * 4 k=0 = 1/(1-*) 5.4 Performance Measures Define: N = Total channel backlog averaged over time. TV is therefore the average ratio of the sum of backlogs over all slots in the period to the length (in slots) of that period. N has units of packets. L = Number of cycles required for a channel to be considered in steady state. TCiL = Expected number of cycles such that the backlog = x at the imbedded points Nu. X r = = The r-step transition probability matrix of the process up to the rth slot following the start of the transmission of the packet (i.e. over the busy period). X r = (S + F)Q r 64 If A(i) denotes the sum of backlogs over the busy period, then T+w+2 M. T+Tout+2 M = E Ei(SQr]y + E E W f o r = 0 j=i r=0 j= i and hence M T+w+2 T-t-T 0 u t +2 ^•) = E i [ s E Q R + F E Qrlu ; = « ' r=0 r=0 The total backlog sum is M 1 j ; ^ [ _ i T . - + A(0] «=o * The total length of the period (in slots) of L cycles is E 7 - + 1 + p * M r + w + 2) +11 - ^(0)(r + r o u t + 2)] Taking the ratio of the total sum of backlogs to the length of the period of L cycles and letting L approach infinity yields N = S5o*<[iJi7» + A(0J E^o T.-(I=^ + 1 + P.(*){T + u> + 2) + (1 - P.(»))(T + T o u t + 2)] The average channel throughput, S, is the ratio of the time the channel is carrying successful transmissions in a cycle, averaged over all cycles, to the cycle length. Thus S = SgottififflT ; E£0Mjh; + 1 + p*(0(r + w + 2) + (i - p.(0)(r + Tout + 2)] 1 " ; From Little's formula, the mean packet delay D is A T Z> = ^ (5.3) It is clear that the expression for the transition matrix P in equation ( 5.1) corre-sponds to GSMA without acknowledgements if the initial priority slot is subtracted from the information transmission period (T+2) and the round trip delay lengths w+1 and T0iit+1 that extend the cycle in acknowledging SW-ARQ environment are set to 0 . Under these conditions, T + w + 2 and T + Tout + 2 are reduced to T. 65 5.5 Network P K T E R Determination Calculation of TV and D using the above analysis requires knowledge of the packet error rate. It is known from previous work that errors on intrabuilding power line networks tend to occur in bursts [13]. Consequently, PKTER cannot be deter-mined from the BER but instead must be measured. Use of BER to determine PKTER, on the assumption of a random error channel normally used to obtain block error probabilities on memory less channels where errors occur independently, leads to pessimistic PKTER estimates [42]. Several studies have been undertaken to obtain block error probabilities for channels with burst errors in the past [68] -[88]. However the wide time variation and unpredictable nature of channel errors on power lines makes it extremely difficult to obtain an accurate model for PKTER. Measurements offer the most reliable means of obtaining PKTERs on power line links. Packet error rates were measured from the two five-node IPL networks described in section 4.4. Network 1 consisted of fairly good lines while network 2 was carefully chosen to included some poor quality lines. For both networks two of the nodes were on phase <j>\ of the power line network, another two nodes on fa and the third was on fa. Thus, both in- phase and across-phase transmission occurred regularly during network operation. The modem used was a direct sequence PSK spread spectrum modem transmitting 3 V rms at a 38.4 kHz carrier frequency, 19.2 kbit/s code rate and 1.2, 2.4, 4.8 or 9.6 kbit/s data rate. All measurements were taken during normal working hours when bit error rates are at their highest levels. Each measurement was started at 10 am and lasted for 1 - 2 hours. A Hewlett-Packard 1645A Data Error Analyser was used to generate 211 — 1 bit pseudorandom sequences. Received data were demodulated with a receiving power line modem 66 then fed into an IBM PC from where BER and PKTER measurements were made. Tables 5.2 and 5.3 show some measured values for PKTER as well as BER. The BER values shown represent averages over two transmission directions. In general, the measured values were different for the forward and reverse directions, on each link. To obtain PKTER entries for each link in tables 5.2 and 5.3, packet error probabilities for information {Pinfo) and ACK (Paek) packets were estimated on ev-ery link's forward and reverse directions, respectively. Link packet error probability (Px,,) for each link was then computed as follows: PL% = Pinfo "f" Ptek PinfoPack The last line, denoted MEAN and STD DEV, represents the average and standard deviation respectively, over all links in the network. The MEAN value constitute our estimates of P n t w . PKTER increases with data rate, as expected, and is higher, at any given rate, for Network 2 than for Network 1. At 4.8 kbit/s and above, PKTER is close to one on most links, for both networks. At low data rates the effects of impulse noise (which is the major cause of channel errors) is relatively small since the energy per bit is relatively high and reliable performance can be achieved at low transmitted power levels. As the transmission speed increases BER increases because noise impulse durations approach that of a data bit. Unlike stream data transmission, packetized data transmission requires modems to synchronize at the beginning of every packet. This increases the probability of synchronization failure and is worse on channels with high and varying noise characteristics such as power lines. Our measurements on power lines indicate that approximately 40% of the total unsuccessfully transmitted packets is due to synchronization failure. 67 Table 5.1: NETWORK TIMING PARAMETERS (slot size = 10 ms) DATA RATE 1.2 kbit/s 2.4 kbit/s 4.8 kbit/s 9.6 kbit/s r 0.9133 sec. (91 slots) 0.4567 sec. (46 slots) 0.2283 sec. (23 slots) 0.1142 sec. (11 slots) w 0.13 sec. (13 slots) 0.09 sec. (9 slots) 0.07 sec. (7 slots) 0.05 sec. (5 slots) Tout 0.14 sec. (14 slots) 0.10 sec. (10 slots) 0.08 sec. (8 slots) 0.06 sec. (6 slots) 5.6 Discussion of Analytical Results Table 5.1 shows measured values for T, u and Tout at the various data rates em-ployed. All three quantities decrease, of course, as the data rate increases. Through-out we have used u = 0.02, which gives a reasonable high throughput and low delay. Delay and throughput results based on measured estimates for P n t w were determined and are shown in Figs. 5.2 and 5.3. In calculating N and D computational diffi-culties did not occur since our system has relatively small values for M and T (M = 5 and T < 91). For large M and T values (M > 100), computational difficulties can occur. For both networks, delay is reduced at any throughput level S as bit error rate R increases, provided R < 4.8 kbit/s. As R increases to 9.6 kbit/s, however, delay increases for all S values for both networks. PKTER and the relative vulnerable period increase with R and eventually become the major delay components. Similarly, throughput S at any offered load G increases with R until R = 4.8 kbit/s, S decreases below its value at i2=4.8 kbit/s, at any G value, because of an excessive number of retransmissions (see Fig. 5.2). 68 5.7 Summary In this chapter, an analytical model for finite user nonpersistent CSMA/PA has been formulated. Expressions for average channel backlog, mean packet delay and channel throughput are derived, based on measured PKTERs. The analysis is based on noisy and fading transmission channels, finite number of users, message packets of fixed duration, ACKs of fixed duration, message and ACK packets subject to channel errors, and geometrically distributed retransmission delay. PKTERs were measured between five-node intrabuilding power line network links. PKTER increases with data rate, as expected, and is higher at any given rate, for Network 2 than for Network 1. These PKTER estimates were then used with obtained analytical results to calculate message throughput and delay performance. Numerical results are presented for a five-node network where the effects of channel errors and acknowledgement traffic on throughput - delay performance are examined. Measured and calculated results are compared in chapter 6 and show excellent agreement. Previous work [65] has shown that the maximum throughput values are not dependent on M as long as M > 5. 69 Table 5.2: MEASURED BER AND PKTER FOR NETWORK 1 LINK DATA RATE 1.2 kbit/s 2.4 kbit/s 4.8 kbit/s 9.6 kbit/s BER / PKTER BER / PKTER BER / PKTER BER / PKTER A - B 5.74 *10~4 2.55 * 10_1 1.38 * IO - 3 7.59 * IO"1 2.08 * IO"3 8.68 * IO - 1 2.42 * IO"3 8.99 * IO - 1 A - C 8.52 * IO - 6 8.28 * IO - 3 1.52 * 10~4 9.46*10-2 8.75 *IO - 4 1.21 * IO"1 1.96 * IO - 3 8.10 * IO - 1 A - D 2.57 * IO"3 7.89 * 10"1 4.06 *IO - 3 8.49 * IO"1 8.96 * IO"3 8.81 * IO - 1 5.63 * 10~2 9.41 * IO"1 A - E 5.26 * IO"6 2.40 * 10~3 8.85 * IO - 5 8.20 * IO - 2 2.94 * IO"4 1.83 * IO"1 1.37 * IO - 3 7.98 * IO"1 B - C 4.12 *IO"6 1.20* IO - 3 6.31 * IO - 5 5.40 * 10~2 1.07 * IO"4 9.83 * 10~2 2.56 * IO - 3 6.92 * IO"1 B - D 2.14 * IO"3 6.64 * IO - 1 3.89 * IO - 3 9.70 *IO"1 4.27 * IO"3 9.85 * IO"1 9.64 * IO - 3 9.98 * IO - 1 B - E 9.34 * IO"6 4.60 * IO"3 1.06 * IO - 4 9.80 *10"2 7.51 * IO"4 3.98 * IO"1 2.43 * IO"3 7.83 * IO"1 C - D 9.52 * IO"6 3.10 *IO - 3 7.68 * 10~5 7.53 * IO - 2 4.88 * IO"4 2.84 * IO - 1 1.27 * 10~3 8.96 * IO - 1 C - E 8.69 *10"B 5.40* 10~2 1.74 *IO - 3 4.08 * IO - 1 2.77 * IO"3 7.34 * IO"1 4.33 * IO"3 8.78 * IO - 1 D - E 1.85 * 10~4 8.60 *IO - 2 2.38 * IO - 3 6.41 * IO"1 3.14 * IO"3 8.86 * IO"1 6.22 * IO"3 9.64 * IO - 1 MEAN 5.99 * 10~4 1.87 * IO - 1 1.39 * 10~3 4.03 *IO"1 2.37 * IO"3 5.43 * IO"1 8.85 * IO"3 8.66 * IO - 1 STD DEV 9.77 * IO"4 2.96 * IO"1 1.59 * 10 - 3 3.69 *IO - 1 2.70 * 10~3 3.60 * IO"1 1.69 * IO"2 9.41 * IO"2 70 Table 5.3: MEASURED BER AND PKTER FOR NETWORK 2 LINK DATA RATE 1.2 kbit/s 2.4 kbit/s 4.8 kbit/s 9.6 kbit/s BER / PKTER BER / PKTER BER / PKTER BER / PKTER A - B 1.16 * 10 - 3 7.02 *10"1 1.62 * 10"3 8.04 *10"1 1.93 * 10~3 8.17 *10"1 2.71 * 10"3 9.33 * n r 1 A - C 1.88 * 10~4 9.84 * l O - 2 8.93 * 10"4 5.92 * 10_1 9.35 * 10 - 4 6.32 * 10"1 2.50 * 10"3 8.79 * 10"1 A - D 2.66 * 10 - 2 9.90 * 10"1 2.76 *10"2 9.95 * 10_1 2.95 * 10~2 9.97 * 10_1 9.26 * 10"2 9.99 * l O - 1 A - E 2.12 *10~3 8.54 * 10"1 2.57* 10"3 8.92 * 10_1 2.76 *10"2 9.12 *10"1 3.52 * 10~2 9.97 * 10"1 B - C 9.61 * 10 - 5 8.94 * 10"2 2.96 * 10"4 2.26 * lO"1 7.12 * 10~4 5.36 * 10"1 1.56 * l O - 2 6.45 * lO"1 B - D 2.84 * 10 - 3 9.24 * lO"1 2.97 * 10"3 9.51 * 10"1 9.06 * 10~3 9.93 * 10"1 6.62 * 10~2 9.99 * 10"1 B - E 1.98 * 10"3 8.41 * 10"1 2.21 * 10"3 8.47 * 10"1 2.73 *10~3 8.51 * 10"1 2.68 * l O - 2 9.14 * 10"1 C - D 2.65 *10"3 9.08 * 10"1 2.85 * 10~3 9.23 * 10_1 4.01 * 10~3 9.77 * 10_1 5.17 *10"2 -9.84 * 10_1 C - E 2.49 * 10 - 3 8.70 *10"1 2.58 * 10"3 8.99 * lO"1 3.07 * 10"3 9.17 * 10"1 4.02 * 10~2 9.66 * 10_1 D - E 2.73 *lO" 3 9.12 * 10"1 2.88 * 10 - 3 9.37 * 10"1 3.31 * 10"3 9.66 *10"1 5.83 * 10~2 9.84 * n r 1 MEAN 4.33 *10~3 7.19 * 10"1 4.65 *10 - 3 8.07 * 10"1 8.29 * 10"3 8.59 * 10_1 3.92 * 10~2 9.30 * 10"1 STD DEV 7.89 * 10 - 3 3.38 *10"1 8.12 * 10"3 2.33 * lO"1 1.09 * 10~2 1.59 * 10 - 1 2.89 * 10"2 1.08 * 10"1 71 500 4.8 kbit/s 2.4 h brt/s 9.6 kbit/s 1.2 kbit/s 1.0 2.0 Offered Load - G (packets/T slots) (b) 3.0 Figure 5.2: Throughput - offered load curves in finite population slotted Nonper-sistent CSMA/PA channel, (a) Network 1 (b) Network 2 72 Figure 5.3: Delay - throughput curves in finite population slotted Nonpersistent CSMA/PA channel, (a) Network 1 (b) Network 2 73 Chapter 6 IPL N E T W O R K S P E R F O R M A N C E E V A L U A T I O N 6.1 Introduction Modeling, and analysis are necessary for network performance prediction. To test our analytical performance results, measurements were taken from two five- node IPL local area networks. The performance analysis of IPL data networks using CSMA/PA was carried out in chapter 5 based on estimates of PKTER measured from various IPL network links. In this chapter, measured delay and throughput performance for an operational IPL LAN are presented and compared with calcu-lated values, to verify our analytical approach. First, we describe network mea-surement procedures. Next, measured throughput vs. offered load and delay vs. throughput for two five-node IPL data LANs using nonpersistent CSMA/PA are presented and compared to analytical results obtained in chapter 5 for transmission rates ranging from 1.2 - 9.6 kbit/s. 6.2 Measurement Techniques Measurements were taken from the two intrabuilding power line local area networks described in sections 4.4 and 5.5. The results presented here were obtained using a direct sequence PSK spread spectrum modem transmitting 3 V rms at a 38.4 kHz carrier frequency, 19.2 kbit/s code rate and 1.2, 2.4, 4.8 or 9.6 kbit/s data rate. All measurements were taken during week day working hours, as this is the time 74 when bit error rate on power line circuits are typically at their highest levels. Each measurement session started at 10 am and lasted for between 1 and 2 hours. For measurement of throughput and delay for each network, each of the five nodes generated one-fifth of the total network traffic. Packets were generated only when there were no packets queued in the transmit buffer. The intervals 1 between packet generation were geometrically distributed with mean 1/tr slots. Packet inter-arrival times were generated prior to throughput - delay measurements. Information and ACK packets were 1096 and 56 bits long, respectively. Each measurement period consisted of every station successfully transmitting 100 packets to one of four different randomly chosen destinations. Following each measurement period for a given interarrival time and data rate, the offered load (G/M), throughput S/M (ratio of time channel is carrying useful traffic to the total experiment time) and the total packet delay D were recorded from each node. The total offered load G (aM/a), network throughput S and mean packet delay D were then obtained from the sum and mean of the individual nodal quantities, respectively. Three separate measurement results (G, S and D) were obtained on three different working days at similar times. These quantities were then averaged and used to obtain a single point on the S vs. G and D vs. S curves. There are approximately 10 points per curve resulting in 3000 (100 transmissions per point per day x 10 points per curve) transmissions by each station per curve. Packet delay D was measured from the arrival of a new packet to the receipt of an ACK. 1Mean interarrival time = (l/tr) x slot-size ms. 75 6.3 Analytical vs. Measured Results The measured throughput vs. offered load and delay vs. throughput appear in Figs. 6.1 - 6.16. The vertical lines represent the standard deviation of the measurements. The mean values are represented by circles, and are joined by dashed lines. Each point on a curve is based on a 1500 successful transmissions. Also plotted for comparison purposes are analytical results obtained earlier. The smooth curves represented by solid lines were determined using the measured PKTER values and the equations developed in chapter 5. Analytical results were obtained with the probability of packet generation v = 0.02, which gives a reasonably high throughput and low delay. As can be seen from these Figs. 6.1 - 6.16, the agreement between the measured and analytical results is excellent. 6.3.1 Throughput - Offered Load Performance The curves in Figs. 6.1, 6.3, 6.5, 6.7, 6.9, 6.11, 6.13 and 6.15, which show throughput (S) vs. offered load (G), indicate that S increases with G initially, then levels off to a constant maximum value Smax. The values of Smax in packets/T slots are shown in Table 6.1, and are seen to decrease as the data rate R increases. However, when measured in bit/s, SmaX increases with R until R=4.S kbit/s, then decreases at R=9.6 kbit/s. As noted in chapter 5, the relative vulnerable period, 'a', and the retransmission probability both increase with R, and eventually cause the throughput to fall. 76 Table 6.1: Maximum throughput for networks 1 and 2 NETWORK BIT RATE {R) MAXIMUM THROUGHPUT {Smax) (kbit/s) packets/T slots bit/s 1 1.2 0.623 747 1 2.4 0.424 1018 1 4.8 0.263 1262 1 9.6 0.062 595 2 1.2 0.217 260 2 2.4 0.131 314 2 4.8 0.082 393 2 9.6 0.029 278 6.3.2 Delay - Throughput Performance Figures 6.2, 6.4, 6.6 and 6.8 which pertain to Network 1, show a characteristic "knee" region, where any increase in throughput causes a large increase in delay. This sharp increase is caused primarily by the time needed to acquire channel access. The large number of retransmissions on the poor quality links in network 2 reduces throughput and increases delay, even at low throughput levels when contention is minimal. Part (a) of the D - S plots for networks 1 and 2 show that mean delay increases at any achievable throughput level, as R increases. This increase occurs because the fixed delays increase relative to packet transmission time as R increases and because the packet retransmission probability also increases. Part (b) of the D - S plots for networks 1 and 2 show delay vs throughput in bits/s. As R increases while not exceeding 4.8 kbit/s, the actual delay at any achievable throughput value is reduced. However, increasing R from 4.8 to 9.6 kbit/s leads to an increase in delay at any achievable throughput level. Again, the 77 primary cause is the poor quality links, for which the retransmission rate becomes unusually high as R increases above 4.8 kbit/s. In both networks 1 and 2, BER variation for the various links shown in Fig. 2.5 caused link delay to vary by a factor of two or more, at throughput levels below the "knee" on the delay vs throughput curve. Over time, the BER on individual links varied, as did the delay and throughput on each link. On most links, acceptable delays are obtained at throughput levels below the knee region. Fig. 6.2(b), 6.4(b) and 6.6(b) of network 1 show that there is a lower bound on packet delay of approximately 1.5, 1.3 and 1.2 seconds for 1.2, 2.4 and 4.8 kbit/s data rates respectively. Earlier work [65] indicates that a minimum of 5 terminals are needed to deter-mine the maximum achievable network throughput. For our system, this maximum is nearly 1.3 kbit/s at 4.8 kbit/s data rate. The corresponding delay at 1 kbit/s throughput is approximately 2.4 sec. 6.4 Summary Measured throughput vs. offered load and delay vs. throughput for two five- node intrabuilding power line LANs using nonpersistent CSMA/PA have been presented and compared to analytical performance results. Transmission rates ranged from 1.2 - 9.6 kbit/s. In general, the agreement between the measured and analytical results is excellent. The following general conclusions can be drawn from the observed results. 1. S increases with G initially then levels off to a constant maximum value Smax. 2. Smax in bit/s increases with R on power line networks until the relative vulnerable period and retransmission probability, which also increases with R on power 78 line, causes Smax to decrease. For our system Smax in bit/s increased with. R until i?=4.8 kbit/s, then decreased at R=9.6 kbit/s. 3. Mean packet delay relative to packet length increases at any S value as R in-creases. Fixed delays increase relative to packet transmission time as R in-creases and packet retransmissions also increase. 4. There is a lower bound on packet delays of approximately 1.5, 1.3 and 1.2 sec. for 1.2, 2.4 and 4.8 kbit/s data rates respectively. 5. The maximum achievable IPL network throughput obtained with our PSK/SS power line modems is approximately 1.3 kbit/s at 4.8 kbit/s data rate. The corresponding delay at 1 kbit/s throughput is approximately 2.4 sec. 6. The close agreement between our analytical and measured results indicates that our analytical approach would be useful in predicting delay and throughput performance in other CSMA/PA networks with noisy links. 79 Users c= 5 BER = 4.1 x 10"6 -2.6x 10"3 o V • : 1.2 Kbps 0.02 _L 2.0 3.0 4.0 5.0 Offered Load - G (packets/T slots) (a) 6.0 7.0 Figure 6.1: Nonpersistent IPL CSMA/PA: S vs G at 1.2 kbit/s for network 1 80 3 • l r— Users = 5 1 ' I i - r I -BER = 4.1 x 10-2.6x10 A o - 1.2 Kbps / / 1 V = 0.02 -< / -1 i i i.O 0.1 0.2 0.3 0.4 0.5 0.6 Throughput - S (packets/T slots) (a) Throughput - S (bit/sec.) (b) Figure 6.2: Nonpersistent IPL CSMA/PA: D vs S at 1.2 kbit/s for network 1 81 1400 1200 g 1000 I e eoo o. en 3 O 600 400 200 . - 0 Users = 5 BER-6.3x 10* -4.1 x 10 3 . 2.4 Kbps 0.02 1.0 2.0 3.0 Offered Load - G (packets/T slots) (b) 4.0 Figure 6.3: Nonpersistent IPL CSMA/PA: S vs G at 2.4 kbit/s for network 1 82 83 e • 3 a. • C O ) 3 O 1800 1600 1400 1200 1000 800 600 400 200 Users - 5 BER -1.1 x lO^-S.Qx 10"3 o - 4.8 Kbps l/m 0.02 1.0 2.0 3.0 Offered Load • G (packets/T slots) 4.0 (b) Figure 6.5: Nonpersistent IPL CSMA/PA: S vs G at 4.8 kbit/s for network 1 84 Figure 6.6: Nonpersistent IPL CSMA/PA: D vs S at 4.8 kbit/s for network 1 85 Offered Load - G (packets/T slots) (a) Figure 6.7: Nonpersistent IPL CSMA/PA: S vs G at 9.6 kbit/s for network 1 86 700 Throughput • S (bit/sec.) Fi t ire 6.8: Nonpersistent IPL CSMA/PA: D vs S at 9.6 kbit/s for network 1 87 o co O) o ( 0 (0 3 O . f O ) 3 O 2.0 3.0 4.0 5.0 Offered Load • G (packets/T slots) (a) 6.0 7.0 CO cn 3 O 350 300 , Users - 5 BER-9.6 x 10"* o - 1.2 Kbps V - 0.02 •2.7x 10 _L 2.0 3.0 4.0 5.0 Offered Load - G (packets/T slots) (b) 6.0 7.0 Figure 6.9: Nonpersistent IPL CSMA/PA: S vs G at 1.2 kbit/s for network 2 88 Figure 6.10: Nonpersistent IPL CSMA/PA: D vs S at 1.2 kbit/s for network 2 89 C O o C O t C O C O u C O 3 Q . £ O ) 3 O 1.0 1.5 2.0 2.5 Offered Load - G (packets/T slots) (a) Figure 6.11: Nonpersistent IPL CSMA/PA: S vs G at 2.4 kbit/s for network 2 90 Figure 6.12: Nonpersistent IPL CSMA/PA: D vs S at 2.4 kbit/s for network 2 91 3 Q . £ a o 0.04 -0.02 'o Users = 5 BER = 7.1 X10"" o = 4.8 Kbps V - 0.02 J I •2.9 x 10 .0 0.5 1.0 1.5 2.0 2.5 Offered Load - G (packets/T slots) (a) 3.0 3.5 Z (A i a. £ o> 3 O 500 400 -300 -200 -100 -1.0 1.5 2.0 2.5 Offered Load - G (packets/T slots) 3.5 (b) Figure 6.13: Nonpersistent IPL CSMA/PA: S vs G at 4.8 kbit/s for network 2 92 Figure 6.14: Nonpersistent IPL CSMA/PA: D vs S at 4.8 kbit/s for network 2 93 350 e to • a. CD 3 O 300 250 200 150 100 50 8o f -Users - 5 BER-2.5 x 10"3 -9.3x 10"2 o - 9.6 Kbps V - 0.02 1.0 2.0 3.0 Offered Load - G (packets/T slots) (b) 4.0 Figure 6.15: Nonpersistent IPL CSMA/PA: S vs G at 9.6 kbit/s for network 2 94 Figure 6.16: Nonpersistent IPL CSMA/PA: D vs S at 9.6 kbit/s for network 2 95 Chapter 7 P E R F O R M A N C E I M P R O V E M E N T S T R A T E G I E S 7.1 Introduction Power line network performance deteriorates rapidly with increasing channel error rates. This statement is evident from measurement results obtained from networks 1 and 2. For example the maximum achievable throughput of IPL CSMA/PA falls from 1248 bit/s in Fig. 6.5 to 384 bit/s in Fig. 6.13 at 4.8 kbit/s transmission rates. Several methods have been proposed for improving performance under high channel error rates. Suitable techniques that can be employed to improve IPL network performance include forward error correction, use of network repeaters, reduction of modem data rates and improved ARQ schemes. FEC is particularly effective on channels with relatively high channel error rates such as power line and mobile radio channels [13,85,77]. Chan and Donaldson have recently investigated the use of a combination of interleaving and error correction using convolutional coding to combat channel errors on power lines [16,17,18]. Re-peaters can facilitate communication between frequently isolated power line network nodes during periods of high error rates; however repeater installation may require skilled personnel, or detailed knowledge of network wiring and loading, or both. Modem data rate reduction can be used to improve performance under high chan-nel error rates, so long as some logic is included in the receiver that enables it to adaptively switch to the reduced data rate. A nontrivial problem is to co- ordinate 96 data rate adjustments among transceivers. Conventional ARQ schemes are simple and enable information throughput to adjust easily and automatically to commu-nication channel quality. At high channel error rates, improved ARQ schemes have been shown to be effective in maintaining reasonably high throughput efficiency [79,80,84,90,91]. In this chapter and in a recent paper by this author [44], the use of an effective and novel SW ARQ scheme to improve IPL network performance is proposed and evaluated. 7.2 Existing ARQ-Based Performance Enhancement Schemes During the past several years, many improved ARQ schemes for use on noisy chan-nels have been proposed and analysed [77] - [92]. Sastry [78] proposed a technique intended to improve the efficiency of SW ARQ schemes on channels with large round-trip delay, by having a block repeated N times following a retransmission request. Arazi [79] describes a procedure of reducing the number of bits in re-transmissions by using a code capable of detecting an error burst of length m and requesting retransmission only for the bits whose parity check failed. Sindhu [80] proposes a scheme designed to reduce the mean number of retransmissions by apply-ing repetition redundancy error correction on copies of erroneously received blocks. In Moris's SW-ARQ version-2 [81], M successive message blocks are sent before the receiver either positively acknowledges the received message or identifies individ-ual blocks for retransmission, thereby sharing acknowledgement overheads among all M packets. Turney's SRT-ARQ [83] partitions a block into mini-blocks then attaches check-sum to each mini-block. At the receiver retransmission is requested only for those mini-blocks whose parity check failed. In [84], Weldon proposes an efficient selective-repeat ARQ scheme for use in systems with limited receive buffer 97 capacity. The basic idea is to increase the number of copies of a data packet to be sent at each successive retransmission request so as to minimize the average number of repeats. Wang and Lin [86] have proposed sending the information section of the packet first and a parity section later only if the information section is not received correctly. In [89], Chase has suggested a way of combining all the received copies of a packet in order to improve ARQ systems' reliability and throughput at very high channel error rates. Moeneclaey et al. [90] improved on Sastry's SW ARQ scheme by having the sender transmit, and if necessary retransmit, an optimized number of copies before stopping and waiting for acknowledgement. Kallel and Haccoun [91] have exploited the idea of code combining with ARQ in conjunction with convolu-tional coding and sequential decoding to maintain an efficient communication over noisy channels. Kallel and Leung [92] improved on Weldon's selective-repeat ARQ scheme by appropriately combining the erroneously received copies of data blocks. Thus far, it has been shown that under constant channel conditions, transmis-sion of an optimized number of multiple packet copies with possible code combining improves performance under high channel error rates. On power lines, channel con-ditions change over time, and the number of multiple packet copies which maximize performance changes accordingly. Failure to vary this number with channel condi-tions can seriously impair throughput and delay performance. Thus, if each packet is transmitted in N copies to combat high noise or interference levels or deep signal fading, the throughput would be approximately 1/N of its obtainable value when the channel becomes clear. As shown later, transmission of a single packet copy on a poor quality channel can reduce the throughput to a small fraction of the level obtainable using multiple packet copies. 98 7.3 Packetized Data Transmission on Power Lines Packetized data transmission requires modems to synchronize at the beginning of every packet. In noisy environments, synchronization failures can and do occur. Our measurements on power lines have shown that approximately 40% of all un-successful packet transmissions result from synchronization failures. The remaining 60% results from cyclic-redundancy-check (CRC) errors. Usually only a few bytes of a packet is received whenever loss of synchronization occurs. On power lines, channel errors occur both in the forward and feedback channels, and therefore af-fect both data and acknowledgement packets. Power line modems have moderate turn ON/OFF times which can reduce the throughput of SW ARQ scheme under high channel error rates [78]. Packet error rate varies widely over time and among links because of the wide variations in signal attenuation and noise characteristics. Flags, address and control information are frequently destroyed by channel errors, when channel quality is poor. Link fade durations can span several minutes or even hours. The above discussion leads to the following conclusions regarding potential per-formance improvement strategies for power line networks: 1. Sending a sequence of packets between modem turn ON/OFF times to reduce overhead effects of power line modem detection times may not improve per-formance much, since synchronization loss will result in loss of all packets.sent between the modem's turn ON/OFF times. 2. Transmission of NAKs whenever CRC errors occur is not reliable because the source address of the forward transmission is often destroyed. 3. Both message and acknowledgement packets should be protected from channel 99 errors. 4. Whenever a channel is in good condition its capacity should not be wasted. Per-formance improvement requires a novel scheme that combats channel errors whenever they are present on a link, but which does not degrade throughput performance when the channel is in good condition. 5. Sending error-correcting check bits whenever a retransmission is requested is at-tractive, however this scheme may not be very effective when synchronization loss probability is high. 6. Packets should not necessarily be discarded based on CRC alone. Whenever channel errors destroy the closing flag, the preceding bits in a long packet are sometimes correct even though the CRC may fail. 7. Sending a finite number (N) of retransmissions of the requested packet contin-uously before stopping and waiting for acknowledgement could be effective against synchronization loss and could improve throughput efficiency by re-ducing the effect of power line modems' turn ON/OFF times. 8. The relatively long duration of any link attenuation level suggests that once N in 7. above is selected, that value should be maintained until link quality changes. An adaptive error control scheme is required that improves IPL network per-formance on any poor quality power line channel, while preserving the maximum achievable throughput and delay performance when the channel is good. 100 7.4 Proposed A R Q Enhancement Scheme Basically, the proposed scheme employs an adaptive, two-state (TS) switching strat-egy. The receiver uses acknowledgements or lack thereof to estimate the channel state. When the channel is good, a single packet is sent. When channel quality degrades, multiple packet copies are sent and code combined at the receiver. The algorithm is particularly appropriate for channels which remain in a given state over the transmission time of many packets. The flowchart and state diagram of our TS-ARQ algorithm are illustrated in Figs. 7.2 and 7.3, respectively. To combat channel errors in the feedback channel several copies of any ACK are sent when the channel is in state B. 7.4.1 Good State (G) In state G, the transmitter sends packets using conventional SW ARQ scheme, that is, it sends a single packet and then waits for a positive acknowledgement (ACK). The system remains in state G so long as an ACK is received within a predetermined time-out period. Following time-out (i.e. no ACK received), the system switches to state B. 7.4.2 Bad State (B) In state B, N copies of a packet are sent in succession. The receiver performs CRC on the packets as they arrive, and returns an ACK upon CRC confirmation for at least one packet copy. If CRC does not check for any of the N packets, respective bits are code combined using a chosen strategy. CRC confirmation on the resulting code-combined packet causes an ACK to be returned. Otherwise, the transmitter times out and resends N copies of the same packet. The system returns to state 101 G upon the transmitter's receipt of ACKs from two consecutive multiple packet transmissions. The system moves to state B immediately following an unsuccessful transmis-sion in state G. Return to state G requires two consecutive and successful multiple-packet retransmissions in state B, to provide some reasonable assurance that the channel quality has improved over some sustainable time period. While in state B, whenever a receiver gets an error free packet it sends a finite number of ACKs. Acknowledgement packets are short, and are therefore transmitted twice only, when-ever the channel is in state B. 7.4.3 Decoding with Code Combining Code combining is a technique for combining any number of repeated packets en-coded with a rate-i2 code (R < 1), in order to obtain a more powerful error-correcting code [91]. One cost is a reduced code rate. In code combining, instead of discarding all erroneous copies and waiting for copies which contain no bit errors, a bit-by-bit majority voting rule on the i copies received is used at the receiver for decoding. The effective code rate for N transmitted copies is R/N bits/symbol. 7.5 Throughput Efficiency Analysis of TS-ARQ Consider transmissions which originate with the system in state B. In such case, the first and any subsequent packet transmissions will be sent in N copies. Use of an approach similar to that of Sastry [78] yields the throughput efficiency rjB as follows: lN + RT/n}(l + EB) V-1' Symbols in ( 7.1) and in ( 7.2) - ( 7.4) below, are denned as follows: 102 k - number of information bits in a packet. n - packet length in bits. R - bit transmission rate. T - Transmitter idle time (ie. time when the transmitter is not sending information bits). EB(EGB) - expected number of retransmissions when initial transmission originates in state B(G). N - number of copies sent in a multiple packet transmission. P - probability of an unsuccessful packet transmission. F - probability that CRC check fails on a code-combined packet. If packet transmission originates in state G but is initially unsuccessful, state B ensues. The throughput nGB in. this case is identical to Sastry's result [78]: „ = AhM (ro) 1 + {RT/n) + [N + RT/n}EGB 1 Given k/n, RT/n and EB or E G B , one can determine the best value for N from ( 7.1) or ( 7.2), that maximizes throughput efficiency. To determine EB or E G B note that under multiple retransmissions, errors will be detected if both individual packet copies as well as the code-combined packet do not result in CRC confirmation. The expected number of retransmissions (EGB) in ( 7.2) can be obtained as follows: The probability that the first packet transmission is successful is given by Pr[l] = l - P 103 The probability that exactly 1 + N transmissions are required for transmission to be successful after the first N retransmitted copies is as follows: Pr[l + N} = P.(l - FPN) Similarly the probability that exactly 1 + 2N, 1 + 3iV and 1 + jN transmissions are required for transmission to be successful after the second, third and jth N retransmitted copies, respectively, is as follows: Pr[l + 2N] = P.F{1-FPN) Pr[l + 3JV] = P.P 2(l - FPN) Pr[l + jN] = PP ;' _ 1(1 - FPN) The expected number of retransmissions is therefore given by E G B = P(l - FPN) + 2PP(1 - FPN) + 3PP2(1 - FPN) +... + j P P J _ 1 ( l - FPN) + ... = P(l - PP")[1 + 2P + 3P2 + ... + jP J ' _ 1 + ...] = p(i-pp")[f;yp''- 1] Hence EQB in ( 7.2) is given by ( 7.3) below, which reduces to Sastry's [78] result in the absence of code combining when F = 1. In ( 7.3) and ( 7.4) below, FPN denotes the probability that CRC fails on each of the N individual packet copies and following code combining. Note that F is actually the probability of code combining failure given that CRC has failed on the N individual packet copies. On poor links, P is close to one, and FPN F. 104 Similarly, EB in ( 7.1) is given by EB = {FPN){1 - FPN) + 2{FPN)2{1 - FPN) + ... + j{FPN)j{l - FPN) + FPN (7.4) 1 - FPN When N = 1, conventional ARQ results, EQB = EB and TJGB — VB-On random error channels, one can relate F and P when code combining with majority voting is used. Let p be the bit error probability. The bit error probability pm{N) after majority voting is given by [29,92] pm(N) = J~ 1 \ J J < i J ( , N odd \ 3 J N [N/2 [p(l - p)]Nl* , JV even m j\{N-j)\ (7.5) (7.6) F = -pM(N)]N (7.7) So long as p < 1/2, F < P for iV > 3. Fig. 7.4 shows PN and F vs. p for various values of N. The case N = 1 corresponds to a single packet transmission, where F = 1. A range of p values exists where F -C PN, in which case code combining is very beneficial. For example, at p = 10"3, P 3 =^  3 x 10 - 1 while F 3 x 10~3. Code combining using majority voting reduces the packet error probability by two orders of magnitude. Retransmission frequency EQB in ( 7.3) is reduced from 0.96 to 0.67, while EB in ( 7.4) is reduced from 0.43 to 9.0 x 10 - 4. 105 Figs. 7.5 - 7.10 show rjB and n G B , respectively, vs. p, for 0.10 < (RT/n) < 1 0 . 0 . A random error channel is assumed. With nr N and p fixed, nB and T]GB decrease as RT increases as indicated by ( 7.2) and ( 7.3). As p increases with RT and n held constant, the value of N which maximizes throughput efficiency also increases. As p decreases while N, n and RT remain fixed, throughput efficiency approaches an asymtotic value which is obtained from ( 7.2) or ( 7.3) with EB — EQB = 0 . This asymtotic value is less for nGB than rjB, in accordance with ( 7.8) below: H 7 - N + {RT/n) ' { p - * 0 ) ( 7 - 8 ) Figs. 7.11 - 7.16 show more clearly the effects of RT/n and code combining on throughput efficiency. As expected, r)aB and nB increases as RT/n is reduced. The effectiveness of code combining in maintaining throughput efficiency as channel quality degrades is evident. As can be seen from these figures N = 3, is suitable for the range 10 - 3 < p < 10 - 2 which is the value range encountered in our actual system. In the absence of code combining F = 1, and E G B in equation ( 7.3) reduces to P/( l - PN) given by Sastry [78]. From Figs. 7.17 and 7.18, it is evident that at low values of RT, there is little to be gained by Sastry's multiple retransmission scheme (which does not use code combining). However, the value of N which max-imizes Sastry's throughput efficiency (77,) increases at high values of RT. Multiple retransmissions result in large throughput efficiency improvements only when the propagation delay between the transmitter and receiver is large compared to the duration of one data packet, as for the satellite channels considered by Sastry [78]. For our system the values of RT ranges between 228 - 634, and as can be seen from Fig. 7.19 and table 7.1, any improvements in throughput efficiency gained by retransmission of several copies (without code combining) are small. 106 Table 7.1: Point-point throughput efficiency improvements with Sastry's scheme. DATA RATE (kbit/s) P THROUGHPUT EFFICIENCY SW (i = 1) Max. rjsastry Improvement 1.2 7.02 x 10 - 1 0.220 0.220 (i = 1) 0% 2.4 8.04 x 10"1 0.127 0.129 (t = 2) 1.6% 4.8 8.17 x IO"1 0.081 0.088 (i = 3) 8.6% 9.6 9.33 x 10_1 0.031 0.039 (» = 4) 25.8% On burst-error channels, it is difficult if not impossible to relate F and P analyt-ically. Eqn's ( 7.1) - ( 7.4) remain in effect, but P and F are no longer determined using ( 7.5) - ( 7.7) inclusive. Unless a suitable mathematical description of the channel is available, En and EQB must be obtained either by direct measurement, or by measurement of F and P and use of ( 7.3) or ( 7.4). Throughput efficiency depends on packet error probability P, and not on bit error probability p directly. Given P, Fig. 7.4 may be used to obtain a corresponding random-error value for p which can then be used with Figs. 7.11 - 7.16 to determine throughput efficiency in the absence of code combining. If errors on individual bits used in majority voting to obtain pm(iV) in ( 7.5) are statistically independent, then Figs. 7.4 - 7.16, inclusive, may also be used to obtain F even if the channel is not random error, provided the bit error probability is known. The independence assumption would be reasonable in many cases; even if adjacent bits in an n-bit block exhibit error dependencies, errors separated by n bits may be independent. To determine the overall throughput efficiency rj of a network with different links in different states, one could use ( 7.9) below for each link, where PG{PB) - probability that packet transmission starts and remains in state G(B). 107 PGB - probability that packet transmission starts in state G and concludes in state B. r]a - throughput efficiency when packet transmission starts and remains in state G. V = VGPG + TIBPB + TJGBPGB (7.9) 7.6 Implementation of T S - A R Q The proposed TS-ARQ (two-state ARQ) error control scheme employs easy to im-plement SW-ARQ both in the good and poor states. In state B the transmitter maintains a sequence window (modulo 16) in the control field (see Fig. 7.1) which the transmitter increments each time it wants to transmit one or multiple packets. Thus sequence windows of multiple packets have the same sequence numbers. Se-quence numbers of multiple packets together with source address information enable receiving nodes to identify new and copy packets, by comparing the stored sequence number and source address of the most recently received packet with that of the packet currently being received. Another bit (state-bit) in the control field informs the receiver whether the channel is in poor state (send two ACKs) or good state (send one ACK). To simplify implementation under actual network operation, majority voting is carried out on only the 3 copies transmitted per retransmission request. All pre-viously stored noisy packets are discarded whenever the beginning of the reception of a new packet is detected, following an ACK or timeout. Storing errored packets for later combination with other noisy packets would increase significantly the re-quired receive buffers because of the many nodes that transmit to a given node in a network. 108 PACKET TYPE STATE BIT 1 I I SEQUENCE WINDOW I I Figure 7.1: TS-ARQ packet control field In state B longer packets can be received whenever the closing flag is destroyed by channel errors. Errored packets with packet lengths greater than or equal to normal packet length (133 bytes) are stored. If three similar errored packet copies are received, bit-by-bit majority voting is performed on them. That is, the corre-sponding bits of the three noisy packets are compared by the receiver's software. The received bit is interpreted to represent a "0" or a "1" if more than half the bits in the three copies are "0's" or "l's" respectively. If parity check still fails after code combining, the errored packets are discarded. The current system state is obtained from the number of retransmissions of the immediately previous packet transmission. The system stores the number of retransmissions of a packet in a variable named last-retxns, at the end of every successful transmission. At the beginning of transmission of a new or rescheduled packet, the transmitter checks this variable. If last-retxns is 0, then the system stays in state G if it was already in state G, or changes to state G if it was in state B. If the variable is greater than 0, then the system stays in state B if it was already in state B, or changes to state G if it was in state B. 109 7.7 Verification of Network Performance Improvement Measurements were taken from Network 2 described in sections 4.4 and 5.5 to verify IPL network performance improvement obtainable with the TS-ARQ. Network 2 was chosen to enable reasonable improvement to be obtained, since the TS-ARQ preserves the maximum achievable network performance when power line channels are in good condition. Measurements were taken using the same techniques and conditions used to obtain the performance results presented in chapter 6. Probabilities p and P were estimated from measurements. Averaged over all ten network links, PKTER varied from 7.2 x IO - 1 at 1.2 kbit/s data rate to 9.3 x IO - 1 at 9.6 kbit/s. These error rates indicate N = 3 as the appropriate number of copies for our SW TS-ARQ scheme (see Figs. 7.4 - 7.16 inclusive). Figs. 7.20 - 7.23 compares TS-ARQ throughput efficiency for N - 3 with throughput 77, for Sastry's [78] scheme for a typical poor quality link. Values of RT = 228 and 634, and P = 0.702 and 0.933, were observed for this link at 1.2 and 9.6 kbit/s, respectively. Since F < 1, it follows from ( 7.2) and ( 7.3) that nGB < n„ for all values of N. Whether or not rjB < na depends on P. For low P values, nB < na, since Sastry's initial single transmission would be successful with high probability. For P above some threshold, the first single transmission would have low probability of success, and it would be better to transmit this packet N times at the outset and use code combining. Figs. 7.20 - 7.23 show nB > na for all N values at R = 9.6 kbit/s and for 3 < N < 6 at R = 1.2 kbit/s. Fig. 7.24 shows the measured throughput efficiency 77 vs. N, measured at various data rates R, for a typical poor quality link. In Fig. 7.24, 77 includes an average of 77c;, rjos and 77^  as defined in ( 7.9). Note that 77 was measured directly, without 110 first measuring the individual quantities in ( 7.9). For all R values tested, N = 3 maximized n. The percent increase in rj, in bit/s increases with R and is largest for R=9.6 kbit/s. At this rate, rj increases by 338 percent, for N = 3, from approximately 300 to 1300 kbit/s. Table 7.2 compares throughput efficiency results for SW TS-ARQ with those for conventional SW ARQ (G-ARQ). Network performance results appear in Figs. 7.25 - 7.32, inclusive and in Table 7.3. Figs. 7.25, 7.27, 7.29, 7.31 show measured throughput S (packets/T slots or bit/s) vs. offered load G (packets/T slots), for both C-ARQ and TS-ARQ. The solid curves are from calculated values presented in chapter 6, while the dotted curves are used to join measured data points. Results are for 1.2, 2.4, 4.8 and 9.6 kbit/s. Standard deviations are shown using vertical bars. For both C-ARQ and TS-ARQ, 5 increases initially as G increases and then re-mains at a fixed level. Such behaviour is characteristic of a finite number of network stations. For almost all G values, TS-ARQ is seen to yield a higher throughput than C-ARQ. Figs. 7.26, 7.28, 7.30 and 7.32 show delay D vs. throughput S for i2=1.2, 2.4, 4.8 and 9.6 kbit/s, averaged over the network. For most values, using TS-ARQ reduces D. Table 7.3 summarizes the maximum observed network throughput value Smax and minimum delay D„in, for C-ARQ and TS-ARQ. Also shown is the percent gain in throughput of TS-ARQ relative to C-ARQ, and the delay of C-ARQ relative to that of TS-ARQ. Significant network performance gains are observed, particularly at R = 9.6 kbit/s, where throughput and delay differences can reach values of 197 percent and 1233 percent, respectively. I l l Table 7.2: Throughput efficiency comparisons for a poor quality link, N = 3; SW TS-ARQ and conventional SW ARQ DATA RATE (kbit/s) PKTER P C-ARQ (bit/s) TS-ARQ (bit/s) GAIN {%) 1.2 7.02 X 10"1 264 313 19 2.4 8.04 x 10"1 341 540 58 4.8 8.17 x 10"1 389 854 132 9.6 9.33 x 10"1 298 1306 338 Table 7.3: Network performance comparisons: SW TS-ARQ and conventional SW ARQ Data Rate (kbit/s) SmaX (bit/s) Dmin (s) C-ARQ TS-ARQ GAIN(%) C-ARQ TS-ARQ GAIN(%) 1.2 261 300 15 38 29 31 2.4 314 480 53 37 20 85 4.8 394 768 93 34 15 127 9.6 278 826 197 40 3 1233 112 Table 7.4: Power Line Modems Performance Values. Performance (fairly poor link) FSK (1.2 - 19.2) (kbps) PSK/SS (1.2 - 9.6) (kbps) PSK (9.6 kbps) DPSK (1.2 - 57.6) (kbps) BER (9.6 kbps) lO"3 - lO"8 lO"2 - 10"6 10"4 - 10~8 10~4 - 10~8 Detection Delay (ms) 6 - 8 6- 10 3-4 1 - 2 DCD Linger (ms) 7- 20 5 - 20 3 - 4 1 - 2 7.8 Improvements in Power Line Modem Technology Work to develop state-of-the-art power line modems continues. The objective is to realize faster and more reliable modems with better performance characteristics. To date, four types of power line modems have been developed at the Department of Electrical Engineering, University of British Columbia. These include a FSK (1.2 -19.2 kbps) modem, a PSK/SS (1.2 - 9.6 kbps) modem, and the recently completed DPSK (1.2 - 57.6 kbps) and PSK (9.6 kbps) modems. The performance and cost of these modems vary depending on the design philos-ophy employed. As can be seen from table 7.4, the DPSK modem has the shortest detection delay and DCD linger, followed by the PSK modem. These improve-ments in modem technology will further improve channel throughput and reduce mean packet delay on IPL data networks. 7.9 Summary An adaptive two-state ARQ scheme has been proposed, implemented and shown to be very effective in improving IPL network performance. The scheme employs both conventional and enhanced SW ARQ schemes which are easy to implement, 113 easily accommodate the CSMA/PA medium access protocol and preserve the max-imum achievable IPL network performance when power line channels are in good condition. Code combining on packet copies is used to reduce packet retransmission probability. Throughput performance has been calculated for SW TS-ARQ and was found to outperform Sastry's [78] ARQ algorithm as well as conventional SW ARQ. Delay and throughput performance for SW TS-ARQ was measured on individual links, as well as on a five-station local area network (LAN) operating on noisy intrabuilding power lines. The LAN included some poor quality links. The following general conclusions can be drawn from the work described in this chapter. 1. High BER, moderate power line modem turn ON/OFF times and high synchro-nization failure rate when power line channels are in poor state motivate the use of multiple retransmissions. 2. Multiple retransmissions increase the chances of a retransmitted packet's suc-cessful transmission and enable receivers to combine noisy packets to improve efficiency. 3. Code combining using majority voting reduces the packet error probability by two orders of magnitude. Retransmission frequency EGB in ( 7.3) is reduced from 0.96 to 0.67, while EB in ( 7.4) is reduced from 0.43 to 9.0 x IO - 4 . 4. With n, N and p fixed, n B and rfaB decrease as RT increases as indicated by ( 7.2) and ( 7.3). As p increases with R T and n held constant, the value of N which maximizes throughput efficiency also increases. 5. PKTER was estimated from measurements. Averaged over all ten Network 2 114 links, PKTER varied from 7.2 x 10_1 at 1.2 kbit/s data rate to 9.3 x 10 _ 1 at 9.6 kbit/s. These error rates indicate N = 3 as the appropriate number of copies for our SW TS- ARQ scheme (see Figs. 7.4 - 7.16 inclusive). 6. For all values of R, measured TS-ARQ throughput efficiency n vs. N indicated that N = 3 maximized n. The percent increase in n, in bit/s increases with R and is largest for i2=9.6 kbit/s. At this rate, n increases by 338 percent, for JV = 3, from approximately 300 to 1300 kbit/s. 7. Measured throughput S (packets/T slots or bit/s) vs. offered load G (packets/T slots), for both C-ARQ and TS-ARQ show that for both C-ARQ and TS-ARQ, S increases initially as G increases and then remains at a fixed level. For most G values, TS-ARQ is seen to yield a higher throughput than C-ARQ. 8. Significant network performance gains are observed using TS-ARQ, particularly at R = 9.6 kbit/s, where throughput and delay differences can reach values of 197 percent and 1233 percent, respectively, using PSK/SS power line modems. 9. The TS-ARQ scheme could be used, with or without interleaving and FEC cod-ing, to provide an inexpensive and effective means of improving performance of intrabuilding power line data networks. The improvements provided by the proposed TS-ARQ scheme are quite general and could therefore be applied to other data communication systems with noisy and slowly varying signal-to-noise ratio. 115 START RTX = 0 STOP YES SEND SINGLE PACKET RTX = 0 NO RTX = 1 SEND 3 COPIES ure 7.2: TS-ARQ algorithm flowchart 116 G ^ GOOD STATE L. J single packet transmission followed by a timeout BAD STATE two most recent multi-packet transmissions were successful most recent transmission v single packet as successful transmit < ine packet | most recent or second most recent multiple-packet transmission was unsuccessful transmit 3 packet copies Figure 7.3: TS-ARQ algorithm state diagram Figure 7.4: F and P vs. p; code-combining using majority voting 118 Figure 7.6: Throughput efficiency r\GB vs p, n; R T = 500 Bit Error Rate (p) Figure 7.7: Throughput efficiency rjGB vs p, n; RT = 1000 119 Bit Error Rate (p) Figure 7.8: Throughput efficiency rjGB vs p, n; RT = 2000 0.0 1x10 1x10 1x10-Bit Error Rate (p) 1x10 -' 1x10 1 Figure 7.9: Throughput efficiency T)GB vs p, n; RT = 5000 120 CD to sr >> U c 0 ) o U J 3 O ) 3 O 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.0 1x10' 1 1 1 1 1 — i 1 1 — r — | 1 1 1 — 1 — | 1 1 r — r -with code combining without code combining - V RT/n = 0.1 ^ _ _ R T 7 n . = 1.0 -\ — ^ V . V s . N - \ X . — X N . * " ^ v > \ v • . RT/n = 10 X v O N 1x10-* 1x10"J Bit Error Rate (p) 1x10-' 1x10-Figure 7.11: Effects of RT/n values and code-combining on throughput efficiency {VGB)\ N = 3 121 C5 o e 0> UJ cn 3 O - i — i 1 r — i — i — I 1 i i — r 0.0 1x10 with code combining without code combining 1x10 1x10- J 1x10' 2 Bit Error Rate (p) 1x10 _ 1 Figure 7.12: Effects of RT/n values and code-combining on throughput efficiency (*?GB); N = 5 •so sr >. O c a> o UJ •+* 3 a. JZ cn 3 O - l 1 l I 1 1 1—1—I 1 1 1 — i — 1 1 1 i — r 0.0 1x10 • with code combining without code combining 1x10 1x10 Bit Error Rate (p) 1x10"' 1x10-1 Figure 7.13: Effects of RT/n values and code-combining on throughput efficiency {TIGB);N = 7. 122 U c • o 5= HI O) 3 o 0.4 ' 1 1 i i i—i—| 1 1 — i i | 1 <—i—i— with code combining 0.35 _ without code combining 0.3 RT/n = 0.1 0.25 RT/n = 1.0 \ 0.2 - \ \ \ \ — \ \ \ \ \ \ \ \ 0.15 x x \ \ -\ \ \ \ 0.1 RT/n = 10 V \ \ \ V \ \ \ _ 0.05 0.0 1x10 " N , ^ S \ S / \ IxlO"4 1x10"3 1x10-2 1x10 Bit Error Rate (p) Figure 7.14: Effects of RT/n values and code-combining on throughput efficiency (t?B); N = 3 > . O c _a> u +-> 3 a. £ o> 3 O 0.28 0.24 0.2 - RT/n = 0.1 0.16 0.12 0.08 - RT/n = 10 0.04 0.0 1x10 RT/n = 1.0 • with code combining without code combining 1x10" 1x10-3 1x10"2 Bit Error Rate (p) 1x10" Figure 7.15: Effects of RT/n values and code-combining on throughput efficiency (*?B);iV = 5 123 w £ , >. u c w jo UJ 3 O . £ cn 3 O 0.18 0.16 0.14 0.12 0.1 0.08 0.06 0.04 0.02 0.0 1x10 RT/n - 0.1 i I I I RT/n = 1.0 RT/n = 10 • with code combining without code combining V. 1x10-" 1x10"J Bit Error Rate (p) 1x10 -' 1x10-Figure 7.16: Effects of RT/n values and code-combining on throughput efficiency >» o c o £ 3 Q . JZ cn 3 O i i i i | i I I I 0.0 1x10 1x10 1 x 1 0 J 1x10"' Bit Error Rate (p) 1x10-Figure 7.17: Effects of RT values on Sastry's throughput efficiency; RT = 100 124 0.1 0.08 0.06 ->• o c 9 o 3= 111 •5 0.04 Q . f cn 3 O .c 0.02 i 1 1 i 1 1 1 1 1 1 1 1 . . 1 0.0 1x10 _J 1 N =5, 7 1x10 1x10"' 1x10"' IxlO" 1 Bit Error Rate (p) Figure 7.18: Effects of RT values on Sastry's throughput efficiency; RT = 10000 0.3 CO n CO & 0.2 o c o 3 Q . f cn 3 o 0.1 0.0 T 1 1 I 1 1 1 1 1 1 1 1 1.2 kbit/s - / 2.4 kbit/s -/ 4.B kbit/s . — 9 . 6 kbit/s 1 1 1 1 1 I I I I 1 1 I ! 1 J 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Number of Copies (N) Figure 7.19: Variation of Sastry's throughput efficiency with the retransmitted packet copies N. 125 u. c £ -w 5 at 3 O 0.4 0.3 0.2 o:ih I I 1 1 1 I . I I I 1 1 1 1 1 1 Sastry's scheme — — ' T I G B -I I I 1 I i i I I i i I i i i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Number of Copies (N) Figure 7.20: Comparison of throughput efficiency for TS-ARQ and Sastry's ARQ at 1.2 kbit/s. 0.3 u c 0 ) o 3 CL x: O) 3 O 0.2 0.1 I I 1 1 1 1 I 1 1 1 1 1 1 1 1 / / 1 Sastry's scheme 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Number of Copies (N) Figure 7.21: Comparison of throughput efficiency for TS-ARQ and Sastry's ARQ at 2.4 kbit/s. 126 0.3 u c a o UJ S a. J: en 3 O 0.2 0.1 h 0.0 1 1 "1 "1' ^ -Ha 1 1 1 1 1 1 1 1 1 / / \ // ^ Sastry's scheme - / 1 1 i i i i i i i i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Number of Copies (N) Figure 7.22: Comparison of throughput efficiency for TS-ARQ and Sastry's ARQ at 4.8 kbit/s. 0.3 o c a> UJ S cn 3 O 0.0 "i—i—r "i i i i i i i i r J L J I L 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Number of Copies (N) Figure 7.23: Comparison of throughput efficiency for TS-ARQ and Sastry's ARQ at 9.6 kbit/s. 127 0.0 200.0 r-_L 4 5 6 Number of Copies (N) (b) Figure 7.24: Measured throughput efficiency n vs. N for a SW TS-ARQ on a typical poor quality link. 128 0.3 CO o CO % u ( 0 (0 3 Q . f CD 3 O n I I Users = 5 BER = 9.6 x 10' 5 - 2 . 7 x 10' 2 o = 1.2 Kbps U = 0.02 2.0 3.0 4.0 5.0 Offered Load - G (packets/T slots) (a) 6.0 7.0 CO (0 3 a. JZ cn 3 O —..^  , (* II Users - 5 BER = 9.6 x 10"1 o = 1.2 Kbps 1 ,= 0.02 •2 .7x 10"' 5.0 6.0 7.0 3.0 4.0 Offered Load - G (packets/T slots) (b) Figure 7.25: IPL CSMA/PA using TS-ARQ: S vs G at 1.2 kbit/s for network Curve I: TS-ARQ; curve II: conventional SW ARQ 129 130 w o ( 0 0 ) O CS V) 3 Q . £ 3 O 0.28 0.24 0.2 0.16 0.12 0.08 0.04 & - " I I 1 > I r=-5 Users = 5 BER = 2 . 9 x 1 0 ^ - 2 . 8 x 1 0 " 2 o = 2.4 Kbps V - 0.02 _ i I • 2.0 Offered Load - G (packets/T slots) (a) 3.0 i £ C O 3 O . £ O ! 3 O 672 576 I < t . . . — — -j . . . . I I © - - • I ~-6 Users = 5 BER = 2.9 x 10^-2 .8 x 10* o • 2.4 Kbps l /= 0.02 2.0 Offered Load - G (packets/T slots) (b) 3.0 Figure 7.27: IPL CSMA/PA using TS-ARQ: S vs G at 2.4 kbit/s for network 2. Curve I: TS-ARQ; curve II: conventional SW ARQ 131 s O M Q a a a 160 140 120 100 80 60 40 20 0. Users •= 5 BER = 2.9x10"" -2.8x10"2 o - 2.4 Kbps V m 0.02 96 144 192 240 .288 336 384 432 480 528 Throughput - S (bit/sec.) (b) Figure 7.28: IPL CSMA/PA using TS-ARQ: D vs S at 2.4 kbit/s for network 2. Curve I: TS-ARQ; curve II: conventional SW ARQ 132 CO o to *— « u ( 0 Q . C O 3 O 0.22 0.2 0.18 0.16 0.14 0.12 0.1 0.08 0.06 0.04 0.02 ° 0 I ! I I ft Users = 5 BER = 7.1 x 10 -2.9x 10 o = 4.8 Kbps V = 0.02 , 1.0 1.5 2.0 2.5 Offered Load - G (packets/T slots) (a) 3.0 3.5 to £ _ C O I 3 Q -JZ o i 3 O 1000 -900 800 700 -600 -500 -400 300 -200 k 100 I I . » Users = 5 BER = 7.1 x10" o = 4.8 Kbps V = 0.02 _ l _ I -2.9x 10 1.5 2.0 2.5 3.0 3.5 Offered Load - G (packets/T slots) (b) Figure 7.29: IPL CSMA/PA using TS-ARQ: S vs G at 4.8 kbit/s for network 2. Curve I: TS-ARQ; curve II: conventional SW ARQ 133 Figure 7.30: IPL CSMA/PA using TS-ARQ: D vs S at 4.8 kbit/s for network 2. Curve I: TS-ARQ; curve II: conventional SW ARQ 134 -~. 0.1 o CO % 0.08 o> o ( 0 § 0.06 3 Q . cn 3 O 0.04 0.02 I I BER = 2.5 x 10" 3 -9 .3x 10' 2 o = 9.6 Kbps J i I i Users = 5 u= 0.02 1.0 2.0 3.0 Offered Load - G (packets/T slot) (a) 4.0 J3, </> i 3 CL cn 3 s 1200 1000 £ 800 600 400 200 t.. I I BER = 2.5 x 1 0 ' 3 - 9 . 3 x 10*2 Users = 5 o m 9.6 Kbps J i U= 0.02 _i I 1.0 2.0 3.0 Offered Load • G (packets/T slots) (b) 4.0 Figure 7.31: IPL CSMA/PA using TS-ARQ: S vs G at 9.6 kbit/s for network Curve I: TS-ARQ; curve II: conventional SW ARQ 135 Z 4 U I 1 T" 1 1 1 I I 200 _ || if Users = 5 -ll 7 BER = 2.5 x 10"3 - 9.3 x 10'2 160 0 - 9.6 Kbps -V= 0.02 I I J 120 TJ tf 80 if tf -40 -n i t J . \ _ 4 .3 . 0 96 192 288 384 480 576 672 768 864 Throughput - S (bit/sec.) (b) Figure 7.32: IPL CSMA/PA using TS-ARQ: D vs S at 9.6 kbit/s for network 2. Curve I: TS-ARQ; curve II: conventional SW ARQ 136 Chapter 8 S U M M A R Y A N D CONCLUSIONS 8.1 Principal Contributions Intrabuilding electric power distribution circuits are potentially useful for local area networking. IPL LANs offer a flexible and cost-effective alternative to conventional LANs which use costly and restrictive specialized wiring. However, power lines were not designed for data communication and suffer from high and unpredictable varia-tions in impedance, signal attenuation and noise. Power line network attenuation is frequency dependent and varies with electrical loading over time. Communication signal and noise levels are highly variable and unpredictable. In general, power line network links can be considered as either fair or poor depending on their signal attenuation which is determined by the actual physical power line wiring scheme. Appropriate power line modems and network protocols must be employed to realize high performance IPL data networks. In this thesis, a new generation of low-cost computer networks using CSMA/PA on intrabuilding power lines have been designed, analysed, implemented and tested. Based on high, variable and unpredictable variations of BER on power lines over time and among links, it has been demonstrated that an inexpensive two-state ARQ error-control scheme can be used effectively to improve significantly power line data network performance. The achievements of this thesis can be divided into four areas: (l) Design and 137 cost-effective implementation of reliable IPL CSMA/PA LANs; (2) analysis of finite user CSMA/PA on noisy channels; (3) performance measurement of five-node power line networks; and (4) performance improvement of CSMA/PA LANs having poor quality links, by use of a simple two-state ARQ algorithm. 8.2 Design and Implementation of LPL C S M A / P A L A N 8.2.1 Design and Implementation An operational five-node LAN using intrabuilding power line networks has been designed, implemented and tested. The LAN employs a CSMA/PA medium access protocol because it is simple to implement, efficient under many lightly loaded bursty terminals and would accommodate the use of repeaters to effect transmission between terminals hidden from each other. Acknowledgements are required in order to maintain high system reliability on noisy power line channels. CSMA/PA simplifies power line modem design by en-abling message and acknowledgement packets to effectively share the same commu-nication bandwidth. Furthermore, although the vulnerable period using PSK/SS modems was found to approximate 10 ms, efficient CSMA/PA operation can still be achieved since the relative vulnerable period is normally much less than unity for the data rates employed. Continued work on power line modem design has recently resulted in modems with reduced detection delays (1-2 ms) which would further reduce the relative vulnerable period. Novel design techniques have been used to simplify IPL network implementa-tion and to achieve high system reliability. The LAN design employed IEEE 802 standards with several modifications, including the use of CSMA/PA instead of 138 CSMA/CD as the medium access scheme, SW data flow control instead of go-back-N, and SW ARQ error control in place of a go-back-N ARQ. SW proved to be relatively easy to implement. Because the transmitter idle time is small compared to the packet transmission time, reasonably high information throughput resulted for the data rates considered. VLSI LAN controller chips were used to simplify LAN implementation considerably. The MC68B54 ADLC chip was used to simplify the design and to enhance the speed and performance of the protocol. Data-link packet length was determined by point-to-point throughput measurements. A length of approximately 1000 bits was found to maximize throughput. 8.2.2 Cost Estimates for IPL L A N nodes IPL LAN nodes consist of power line modems and protocol controllers. Modem costs vary considerably depending on the design requirements and philosophy. Of the four power line modems developed at the department of Electrical Engineering University of British Columbia, PSK/SS is the most expensive because of the extra circuitry required to implement the spread spectrum function. In general, power line modems consist of several regular and repetitive circuits that are amenable to VLSI design [93]. With VLSI implementation, the cost of DPSK and PSK modems which are currently valued at approximately $20 and $70 in single quantities are likely to be approximately $10 and $50, respectively. The implementation of power line network nodes can be either internal, or ex-ternal to a host computer. The choice of the method used depends on the desired compatibilities among the various computers on the network, implementation costs and application environment. Internal implementation can be achieved easily by realizing both the power line modem (except the line coupling networks) and the 139 protocol controller on an IBM PC plug-in board, in which case the IBM PCs' micro-processor would perform protocol processing. Internal implementation is the most cost effective; however, only IBM PCs or those computers whose plug-in cards have been implemented could be used on the network in such case. External implementation requires an external processor to be included with the protocol controller and power line modems. The on board processor could be used for protocol processing as well as modem timing recovery and other associated control functions. External implementation allows terminals and computers from different vendors (IBM PCs, Sun Workstations, Apple Macintoshes, Amigas etc) to be connected to an IPL computer network at slightly higher cost. Using internal implementation, the cost of a power line network node using DPSK modem will be between $100 and $200. With external implementation this figure is likely to be between $200 and $300. 8.3 Analysis of Finite User C S M A / P A To date, no known analysis exists for finite user CSMA/PA. Most versions of CSMA studied since the original work by Kleinrock and Tobagi [54] are based on infinite user population, error-free transmissions, negligible modem detection delay and zero-cost acknowledgements. These assumptions are inappropriate for noisy chan-nels such as IPL networks or mobile radio networks. In this thesis, we have analysed CSMA/PA having a finite number of users in noisy environments. Our contribu-tion involves the development of an analytical approach to determine the effects of channel errors and acknowledgement traffic on performance, as well as calculation and presentation of network delay vs. throughput. First, we obtained expressions for delay and message throughput which include 140 the effects of number of users, detection delay and packet error probability. Next, measurements on actual intrabuilding power line networks were used to estimate packet error probability on various network links. These estimates were then used with our analytical results to calculate message throughput and delay performance. The close agreement between our analytical results and those subsequently mea-sured indicates that our analytical approach would be useful in predicting delay and throughput performance on other CSMA/PA networks with noisy links. 8.4 Network Performance Measurements Measured throughput vs. offered load and delay vs. throughput of two five- node IPL LANs using nonpersistent CSMA/PA were obtained. Extensive measurement results were accumulated using a semi-automated test suite, on two separate net-works, for transmission data rates ranging from 1.2 - 9.6 kbit/s. Network 1 consisted of fairly good quality links while network 2 was carefully selected to include some poor quality links. The results confirm that the maximum achievable throughput, in bit/s, increases initially with data rate R as offered load is increased, then decreases because of increases in both the relative vulnerable period and the retransmission probability. The mean packet delay increases at any throughput S as R increases because fixed delays increase relative to packet transmission time as R increases and because packet retransmissions also increase. The maximum achievable IPL network throughput obtained with the PSK/SS power line modems is nearly 1.3 kbit/s at 4.8 kbit/s data rate. The corresponding delay at 1 kbit/s throughput is approximately 2.4 sec. 141 8.5 Performance Improvement of IPL L A N s The variability of communication signal attenuation and noise characteristics on power lines cause large variations in received signal-to-noise ratio as well as in BER over time and among network links. Link fade durations can span several minutes or even hours. Suitable improved ARQ schemes that transmit optimized number of multiple packet copies with possible code combining have been shown to be effective in improving performance of noisy links under constant channel conditions. On power lines, channel conditions change over time, and the number of multiple packet copies which maximize performance changes accordingly. Failure to vary this number with channel conditions can seriously impair throughput and delay performance. A new two-state ARQ (TS-ARQ) algorithm has been proposed, which uses chan-nel state estimation to determine whether single or multiple copies of a packet should be sent. The scheme employs both conventional and enhanced SW ARQ schemes which are easy to implement and easily accommodate the CSMA/PA medium access protocol. It could also be implemented by go-back-N or selective-repeat ARQ. Code combining on packet copies is used to reduce packet retransmission probability. The scheme improves IPL networks performance considerably when the channels are in a bad state, and preserves the maximum achievable performance when the channels are in a good state. To obtain the optimized number of packet copies N that maximizes performance, PKTER was estimated from measurements. Averaged over all ten Network 2 links, PKTER varied from 7.2 x 10 - 1 at 1.2 kbit/s data rate to 9.3 x 1CT1 at 9.6 kbit/s. These error rates indicate N = 3 as the appropriate number of copies for our SW TS-ARQ scheme (see Figs. 7.4 - 7.16 inclusive). 142 Throughput performance was calculated for SW TS-ARQ and found to out-perform Sastry's [78] ARQ algorithm as well as conventional SW ARQ. Delay and throughput performance for SW TS-ARQ was measured on individual links, as well as on a five-station local area network (LAN) operating on noisy intrabuilding power lines. Network 2 which included some poor quality links was used. Performance improvement over that obtained for conventional SW ARQ is significant. Over 300 percent improvement in throughput efficiency is observed at 9.6 kbit/s transmis-sion rate on a typical bad link. Such improvement enables a LAN with some poor quality links to provide acceptable overall performance. Without use of TS-ARQ the network could be unusable, for practical purposes. Significant network performance gains are observed, particularly at R = 9.6 kbit/s, where throughput and delay differences can reach values of 197 percent and 1233 percent, respectively, using PSK/SS power line modems. The improvements provided by the proposed TS-ARQ scheme are quite general and could therefore be applied to other data communication systems with noisy and slowly varying signal-to-noise ratio. 8.6 Implications for Intrabuilding Communications The results presented here indicate that for many medium-speed intrabuilding com-munication applications involving PC's and dumb terminals, data throughput and delays for power line LANs would be acceptable. Consider electronic messaging. A typical message might consist of 10 lines of 80 characters per line. A network consist-ing of 100 PC's transmitting 800-character message/hr. would require a throughput of 3.2 x 106 bits/hr. or 889 bits/s, assuming 8 bits/character. At 4.8 kbit/s, Fig. 16(b) indicates the delay per 1000-bit packet to be close to 1 sec. which would 143 be acceptable. On a (rarely occurring) poor quality channel, the delay could be considerably longer. Transfer of large files, such as medical images with 1000 x 1000 pels at 8 bits/pel, would require [8 xl06/4800]/60 m 27.8 min, excluding any information packet over-heads, acknowledgements, and access delays. Such a delay would normally be un-acceptable, but could be reduced, perhaps by a factor of ten, by source coding techniques applied to the images and by increasing the data rate to 9.6 kbit/s. The delay at a 0.60 throughput efficiency would be (27.8/0.6)/20 =: 2.3 sec, which would be acceptable. However, if several PC-based terminals were to access an image database, waiting times would become excessive even if the search for and coding of one image file paralleled the transmission of another and the display of a third. The acceptability of a power line LAN for such an application would depend critically on availability on available funds for LAN's, traffic loads, and allowable limits on waiting time. It would seem that power line LANs are viable alternatives to intrabuilding radio networks and networks consisting of standard dial-up telephone links. The latter typically support data rates up to 4.8 kbit/s, although conditioned lines enable higher rates. The bit error rate variation for telephone links is typically less than that of power line LANs. However, in Canada, power line outlet plugs occur every 12 feet of wall space by law while telephone jacks do not; equipment portability for power line LANs is higher than for telephone networks. Packet radio networks suffer from many of the same impairments a power line including varying levels of attenuation and interference [94]. Data rates for packet radio are typically 9.6 kbit/s although higher data rates are possible, depending on bandwidth, noise and interference [94]. Power line LANs could interconnect with other networks as shown in Fig. 8.1, 144 in which low and high speed LANs fall into separate application specific hierar-chical levels. Electronic mail, for example, could be delivered to a network node serving a rooftop antenna for communication via satellite with distant locations. In large buildings, with power supplied from several distribution transformers, the separate LANs could be interconnected with each other and the rooftop antenna by a backbone cable or radio network. 8.T Remarks on Future Research Additional research on power line networking remains to be completed. High sig-nal attenuation on power line links may prevent some network nodes from 'hearing' each other. This hidden terminal problem is one of the major causes of performance degradation on power line networks with poor links. The use of either strategically or randomly selected network repeater location sites to overcome the hidden termi-nal problem is of much interest. Associated with this is the development of efficient automated, adaptive routing strategies. A potential solution incorporating power line network nodes as repeaters suggested in [19] should be explored. Error rates on power lines exhibit large variations over time, primarily because of electrical load variations. Use of the proposed two-state ARQ error control scheme to help offset code efficiency reductions and coding delay associated with interleav-ing and FEC merits further investigation. The idea is to use just enough FEC, so that TS-ARQ scheme together with FEC will enable good delay vs. throughput per-formance when power line channels are of poor quality, and enable FEC algorithm to be switched off whenever the channels are in good condition. This will reduce the coding delay associated with interleaving and FEC when the channels are of good quality. As more data becomes available, development of a viable PKTER model 145 that takes the periodic nature of power line channel errors into consideration is of much interest, and would facilitate design of efficient FEC schemes. In implementing and analysing the performance of CSMA/PA it was tacitly assumed that data packets are sent from one transmitting station to one receiver. In broadcast mode, one station sends to a plurality of stations. Work remains to be done to arbitrate channel access for the ACK packets originating from the various receiving stations. Some problems arise when SW ARQ is used in broadcast mode. Of major concern is the increase in delay and reduction in throughput that would result when a broadcast packet is acknowledged by each receiving station. A potential solution proposed by this author is to modify the CSMA/PA protocol so that no acknowledgement is required in broadcast mode. A protocol would be used that enables receiving nodes to request retransmission of broadcast packets not received. The protocol would operate as follows. Every packet to be transmitted would contain a broadcast sequence number window. These broadcast sequence numbers are incremented only when a broadcast packet is sent. Every node on the network periodically transmits a null broadcast packet containing only broadcast sequence numbers, unless they have normal packets (packets intended for single receivers) or actual broadcast packets to send. In normal or broadcast transmission modes, broadcast sequence numbers are transmitted in the normal or broadcast packets. Each node maintains a list of all stations on the network including a certain number of broadcast sequence numbers already transmitted by each station. All stations on the network must continuously check every broadcast sequence number of every packet on the network, even if these packets are not addressed to them, to determine whether they have missed any broadcast packets. When a node detects that it missed a broadcast packet, it requests that packet to be retransmitted. Request 146 vectors are treated like ordinary information packets and must therefore contend for the channel. Power line communication is potentially an active area for further research and product development. All of the various power line communication components such as modems, FEC codecs and networking protocols which have been developed separately, could be integrated into a single entity. Considerable work remains to be done at the higher layer network protocols. User application and access protocols such as file-transfer-protocol (FTP), simple-mail-transfer-protocol (SMTP), virtual-terminal-protocol (VTP) and others need to be implemented on top of the LLC sublayer to provide the various networking services such as file transfer, electronic mail and news, remote login and resource sharing. Where available, transmission-control-protocol/internet-protocol (TCP/IP) protocol suite could be used to reap maximum benefits from TCP/IP together with its TELNET (terminal access) and SLIP (serial line internet protocol) services. 147 MAIN-FRAME COMPUTER NATIONAL / INTERNATIONAL COMPUTER NETWORK GATEWAY BROADBAND EXTENDED ETHERNET BRIDGE FILE-SERVER VOICE-DATA PBX WORKSTATION COMPUTER HIGH SPEED ETHERNET BRIDGE PC PC BRIDGE PC PC PC PC PC PC LOW SPEED IPL LAN LOW SPEED IPL LAN Figure 8.1: Typical integration of IPL LANs into existing computer networks 148 Bibliography P. K. van der Gracht and R. W. Donaldson, "Communication using pseudonoise modulation on electric power distribution circuits," IEEE Trans. Commun., vol. COM-33, pp. 964 - 974, sept. 1985. J.B. O'Neal, Jr. "The residential power circuit as a communication medium," IEEE Trans. Consumer. Electron., vol. CE-32, pp. 567 - 577, Aug. 1986. R.M. Vines, H.J. Trussel, L.J. Gales and J.B. O'Neal, Jr. "Noise on residential power distribution circuits," IEEE Trans. Electromagnet. Compat., vol. EMC-26, pp. 161 - 168, Nov. 1984. Canadian Electrical code - Part 1, Rexdale, Ont. Canada. A.A. Smith, "Power line noise survey," IEEE Trans. Electromagnet. Compat., vol. EMC-14, pp. 31 - 32, Feb. 1982. R.M. Vines, H.J. Trussel, K.C. Shuey and J.B. O'Neal, Jr. "Impedance of the residential power distribution circuit," IEEE Trans. Electromagnet. Compat., vol. EMC-27, pp. 6 - 12, Feb. 1985. A.C.M. Chen, "Automated power distribution," IEEE Spectrum, pp. 55 - 60, April 1982. J.A. Maleck and J.R. Engstrong, "R.F. impedance of United States and Euro-pean power lines," IEEE Trans. Electromagnet. Compat., vol. EMC-18, pp. 36 - 38, Feb. 1976. D.A. Douglass, "Potential transformer accuracy at 60 Hz voltages above and below rating and at frequencies above 60 Hz," IEEE Trans. Power Apparat. Syst., vol. PAS-100, pp. 1370 - 1375, March. 1981. A.C. Weaver and D.W. Buttler, "A Fault Tolerant Network Protocol for Real-Time Communications," IEEE Trans. Industrial Electron., vol. IE-33, pp. 207 - 211, August 1986. W. Mundy, "Spread spectrum power line modem design and construction," Private Communication, 1986. F.K.K. Chiu, "Data transmission using coherent minimum frequency shift key-ing on intrabuilding Polyphase Power line networks," M.A.Sc. Thesis, Dept. of Electrical Eng. University of British Columbia, Canada, December, 1985. M.H.L. Chan and R.W. Donaldson, "Attenuation of communication signals on residential and commercial intrabuilding power-distribution circuits," IEEE Trans. Electromagnet. Compat., vol. EMC-28, pp. 220 - 230, Nov. 1986. 149 [14] M.H.L. Chan, F.F.K Chiu and R.W. Donaldson, "Signalling and error con-trol for data communications on intrabuilding power distribution circuits," in Canadian Developments in Telecommunications: An Overview of Significant Contributions, T.L. McPhail and D.C. Coll, Eds. Calgary, Alta. U. Calgary Press, 1986, pp. 165 - 212. [15] M.H.L. Chan and R.W. Donaldson, "Local area networking on intrabuilding electric power distribution circuits - Physical layer considerations," in Proc. IEEE Pacific Rim Conf. Commun. Comput. and Signal Processing., Victoria B.C., Canada, June 1987, pp. 109 - 116. [16] M.H.L. Chan and R.W. Donaldson, "Amplitude, width and interarrival dis-tributions for noise impulse, on intrabuilding power line communication net-works," IEEE Trans. Electromagnet. Compat., vol. EMC-31, pp. 320 - 323, Aug. 1989. [17] M.H.L. Chan and R.W. Donaldson, "FEC coding for data communication on intrabuilding electric power lines," to be submitted to IEEE Trans. Commun. for publication. [18] M.H.L. Chan and R.W. Donaldson, " Convolutional coding for data communi-cation on intrabuilding electric power lines," presented at Canadian Informa-tion Theory Workshop, Victoria, B.C., May 29-31, 1989. [19] M.H.L. Chan, "Channel characterization and forward error correction coding for data communications on intrabuilding electric power lines," Ph.D. Thesis, Electrical Engineering Department, University of British Columbia, Vancouver, Canada, April 1989. [20] BSR X-10 Owners Manual, BSR (Canada) Ltd. [21] Nonwire Multidrop Network Users Guide, Cyplex Division, Controlonics Cor-poration, MA, USA. [22] Powerlan TM, Expertnets, Acton, MA, USA. [23] R. Lytle and S. Strom, "A new carrier current protocol utilizing an active repeater for consumer and industrial applications," IEEE Trans. Consumer. Electron., vol. CE-31, pp. 700 - 705, Nov. 1985. [24] D. Bertsekas and R. Gallanger, Data networks. New Jesey: Printice-Hall, 1985. [25] M. Schwartz, Telecommunication networks: protocols modelling and analysis, Reading MA: Addison Wesley, 1987. [26] Ethernet adapter user installation guide, Western Digital Corporation, 1987. [27] ANSI/IEEE I Draft International Standards - Local Area Networks, Logical Link Control (802.2); Carrier Sense Multiple Access with Collision Detection (802.3); Token-Passing Bus Access Method (802.4); Token Ring Access Method (802.5). New York IEEE Press, 1985. 150 [28] W.Stalling, Data and computer cornrnunications, New York: MacMillan, 1985. [29] H. Taub and D.L. Schilling, Principles of communication systems. New York: MacGraw-Hill, 1986. [30] J.M. Wozencraft and I.M. Jacobs, Principles of communication engineering. New York: Wiley 1965, pp. 456. [31] S. Lin and D.T. Costello, Error control coding: fundamentals and applications, Englewood Cliffs, NJ: Prentice-Hall, 1983. [32] Puzman and Poriek, Communication control in computer networks, 1980. [33] Tohru Fujiwara, Tadao Kasami, Atsushi Kitai and Shu Lin. "On the undetected error probability for shortened hamming codes," IEEE Trans. Commun., vol. 33, pp. 570 - 574, June 1985. [34] Kenneth L. Short, Microprocessor and programmed logic, New Jersey: Prentice-Hall, 1981. [35] N.A. Alexandridis, Microprocessors system design concepts, Computer Science Press, 1984. [36] P. Howitz and W. Hill, The art of electronics, Cambridge University Press, 1987. [37] Motorola 8-bit microprocessor and peripheral data book, Motorola Inc. 1983. [38] Intel microcommunications handbook, Intel Corporation, 1985. [39] A.S.Tanenbaum, Operating systems design and implementation, New Jersey, Prentice-Hall, 1987. [40] J.O. Onunga and R.W. Donaldson, "Performance of CSMA with priority ac-knowledgements on intrabuilding power line local area networks," in IEEE WESCANEX 88 Digital Commun. Conf. Proc, Saskatoon, Saskatchwewan, pp. 30 - 37, May 1988. [41] J.O. Onunga and R.W. Donaldson, "Distribution Line communications using CSMA access control with priority acknowledgements on intrabuilding power line local area networks," IEEE Trans. Power Delivery, vol. 4, pp. 878 - 886, April 1989. [42] J.O. Onunga and R.W. Donaldson, "Personal computer communications on intrabuilding power line LANs using CSMA with priority acknowledgement," IEEE Trans. J. Selected Areas in Commun., vol. SAC-7, pp. 180 - 191, Feb 1989. 151 [43] J.O. Onunga and R.W. Donaldson, "Analysis of carrier sense multiple access with priority acknowledgements (CSMA/PA) on noisy two-way channels with finite user population," in Proc. IEEE Pacific Rim Conf. Commun. Comput. , and Signal Processing. , Victoria B.C., Canada, June 1989, pp. 5-11. [44] J.O. Onunga and R.W. Donaldson, "A simple two-state ARQ strategy for throughput and delay enhancement on channels with slowly varying signal-to-noise ratio," submitted for publication, June 1989. [45] J.O. Onunga and R.W. Donaldson, "Performance analysis of CSMA with pri-ority acknowledgements (CSMA/PA) on noisy data networks with finite user population," submitted for publication, July 1989. [46] S.T. Vuong and A.H.T. Ma, "A low-cost and portable local area network for interconnecting PC's using electric power lines," IEEE Trans. J. Selected Areas in Commun., vol. SAC-7, pp. 192 - 201 Feb 1989. [47] H.Oschner, "Data transmission on low voltage power distribution lines using spread spectrum techniques," in Proc. Canada Commun. Power, Montreal, P.Q., Canada, Oct. 1980, pp. 236 - 239. [48] D.I. Hariton and P.F.Patterson, "Low-cost modem IC plugs into powerlines, ignores noise," Electronic Design, 1986, pp. 114 - 124, Oct. 1986. [49] M. Tokoro, T. Nakagawa and K. Tamaru, "Implementation of prototype ac-knowledging ethernet," Dept. of Electrical Eng. Keino University, Yokohama 223, Japan, April 1979. [50] A.S.Tanenbaum, Computer networks, Englewood Cliffs, NJ: Prentice-Hall, 1981. [51] Victoria C. Marney-Petix, Networking and data transmission, Reston Virginia: Prentice-Hall, 1986. [52] MF9 microcomputer std bus user manual, Matrix corporation, Raleigh, 1985. [53] M.L. Shooman, Software Engineering, Japan: Mcgraw- Hill, 1983. [54] L. Kleinrock and F.A. Tobagi, "Packet switching in radio channels: Part I -carrier sense multiple-access and their throughput-delay characteristics," IEEE Trans. Commun., vol. COM-23, pp. 1400 - 1461, Dec. 1975. [55] F. A. Tobagi and L. Kleinrock, "Packet switching in radio channels: Part II -the hidden terminal problem in carrier sense multiple access and the busy - tone solution," IEEE Trans. Commun., vol. COM- 23, pp. 1417 - 1423, December 1975. [56] R. M. Metcalfe and D. R. Boggs, "Ethernet: Distributed Packet Switching for Local Computer Networks," Commun. of the ACM, vol.19, pp. 395 - 404, July 1976. 152 [57] F.A. Tobagi and L. Kleinrock, "The effect of acknowledgement traffic on the capacity of packet switching in radio," IEEE Trans. Commun., vol. COM-26, pp. 815 - 826, June 1978. [58] F.A. Tobagi and L. Kleinrock, "Packet switching in radio channels: Part IV -stability considerations and dynamic control in carrier sense multiple-access," IEEE Trans. Commun., vol. COM-25, pp. 1103 - 1119, Oct. 1977. [59] F.A. Tobagi and V.B. Hunt, "Performance analysis of carrier sense multiple-access with collision detection," Computer Networks vol. 4, pp. 245 - 259, 1980. [60] F. A. Tobagi, M Gerla, R. Peebles and E.G. Manning, "Modeling and mea-surement techniques in packet communication networks," IEEE Proceedings, vol. 66, pp. 1423 - 1447, Nov. 1978. [61] F. A. Tobagi, "Analysis of a Two-Hop Centralized Packet Radio Network - Part II: Carrier Sense Multiple Access," IEEE Trans., Commun., vol. COM-28, pp. 208 - 216, Feb. 1980. [62] S.S. Lam, "A Carrier Multiple Access Protocol for Local Networks," Dept. of Computer Sciences, University of Texas, Austin, Texas, October, 1979. [63] M.Y. Elsanadidi and W. Chu, "Study of acknowledgement schemes in star multiaccess network," IEEE Trans. Commun., vol. COM- 30, pp. 1657 - 1666, July 1982. [64] V.C.M. Leung and R. W. Donaldson, "Effects of Channel Errors on the Delay-Throughput Performance and Capacity of ALOHA Multiple Access Systems," IEEE Trans., Commun., Vol. Com. - 34, pp. 497 - 501, May 1986. [65] H. Takagi and L. Kleinrock, "Throughput analysis for persistent CSMA sys-tems," IEEE Trans. Commun., vol. COM-33, pp. 627 - 638, July 1985. [66] J.F. Hayes, Modelling and analysis of computer communication networks, New York: Plenum, 1984. [67] L. Kleinrock, Queueing Systems - Volume 1:, John Wiley and Sons Inc., NY, 1975. [68] E.N. Gilbert, "Capacity of a burst-noise channel," Bell syst. Tech. J., vol. 39, pp. 1253-1265, Sept. 1960. [69] R.L. Townsend and R.N. Watts, "Effective error control data communication over the switched telephone networks," Bell syst. Tech. J., vol. 43, pp. 2611-2639, Nov. 1964. [70] E.O. Elliot, "A model of the switched telephone network for data communica-tions," Bell syst. Tech. J., vol. 44, pp. 89-109, Jan. 1965. [71] M. Muntner and J.K. Wolf, "Predicted performance of error- control techniques over real channels," IEEE Trans. Inform. Theory, vol. IT-14, pp. 640 - 650 sept. 1968. 153 [72] J.P.A. Adoul, "Error intervals and cluster density in channel modelling," IEEE Trans. Inform. Theory, vol., IT-20, pp. 125 - 129 Jan. 1974. [73] E.O. Elliot, "Estimates of error rates for codes on burst noise," Bell syst. Tech. J., vol. 42, pp. 1977-1996, Sept. 1963. [74] A. H. Haddad et al, "Markov gap models for real communication channels," IEEE Trans. Commun., vol. COM-23 pp. 1189 - 1197 Nov. 1975. [75] J.P.A. Adoul, B.D. Fritchman and L.N. Kanal, "A critical statistics for channels with memory," IEEE Trans. Inform. Theory, vol. IT-18 pp. 133 - 141 Jan. 1972. [76] K. Otani, K. Daikoku and H. Omori, "Burst error performance encountered in digital land mobile radio channels," IEEE Trans. Commun. , vol. COM-30, pp. 250 - 258, Nov. 1981. [77] R.J. Benice and A.H. Frey Jr., "Comparison of error control techniques," IEEE Trans. Commun., vol. COM-12, December 1964. [78] A. R. K. Sastry, "Improving automatic repeat-request (ARQ) performance on satellite channels under high error rate conditions," IEEE Trans. Commun., vol. COM-23, pp. 435 - 439 April 1975. [79] B. Arazi, "Improving throughput of an ARQ stop-and-wait scheme for burst noise channels," IEEE Trans. Commun., vol. COM-24, pp. 661 - 663 June 1976. [80] P. S. Sindhu, "Retransmission error control with memory," IEEE Trans. Com-mun., vol. COM-25, pp. 473 - 479 May 1977. [81] J.M. Moris, "On another go-back-N ARQ technique for high error rate condi-tions," IEEE Trans. Commun., vol. COM-26, pp. 187 - 189 Jan. 1978. [82] S. Lin and P. S. Yu, "An effective error control scheme for satellite communi-cation," IEEE Trans. Commun., vol. COM-28, pp. 395 - 401 March 1980. [83] P. F. Turney, "An improved stop-and-wait ARQ logic for data transmission in mobile radio systems," IEEE Trans. Commun., vol. COM- 29, pp. 68 - 71 Jan. 1981. [84] E.J. Weldon, "An improved selective-repeat ARQ strategy," IEEE Trans. Com-mun., vol. COM-30, pp. 480 - 486 March 1982. [85] C.S.K. Leung and A. Lam, "Forward error correction for an ARQ Scheme ," IEEE Trans. Commun., vol. COM-29, pp. 1514 - 1519, Oct. 1981. [86] Y.M. Wang and S. Lin, "Modified selective-repeat type-II hybrid ARQ system and its performance analysis," IEEE Trans. Commun., vol. COM-31, pp. 593 - 608, May 1983. [87] R.A. Comroe and D.J. Costello Jr. , "ARQ schemes for data transmission in mobile radio systems," IEEE Trans. Vehicular Technol., vol. VT-33, pp. 88 -97, August 1984. 154 [88] R. Sinha. and S. C. Gupta, "Perfomance evaluation of a protocol for packet radio network in mobile computer communications," IEEE Trans. Vehicular Technol, vol. VT-33, pp. 250 - 258, September 1984. [89] D. Chase, "Code combining - a maximum-likihood decoding approach for com-bining an arbitrary number of noisy packets," IEEE Trans. Commun., vol. COM-33, pp. 385 - 393 May 1985. [90] M. Moenaclaey et al, "Throughput optimization for a generalized stop-and-wait ARQ scheme," IEEE Trans. Commun., vol. COM- 34, pp. 205 - 207 Feb. 1986. [91] S. Kallel and D. Haccoun , "Sequential decoding with ARQ and code com-bining: A robust hybrid FEC/ARQ system," IEEE Trans. Commun., vol. COM-36, pp. 773 - 780 July 1988. [92] S. Kallel and C. Leung, "An efficient ARQ system for mobile communications," 89th IEEE Vehicular Technology Conference, pp 677 - 681, April 1989. [93] N. Weste and X. Eshraghiam, Principles of CSMOS VLSI Design, New Jersey: Addison Wesley, 1985. [94] D.C. Cox, "Universal digital portable radio communications," Proc. IEEE, vol. 75, pp. 436 - 477, April 1987. 155 Appendix A M6854 Handler * M 6 8 5 4 . C * «(C 3$C 3|C *(C 5|C Sfc «f( 3|C 3|C 3|C «(C 3|C 3|C 3^C ^ ^ ^ ^ ^ ^ ^ *^ ^ 4^  * ^ ^t* ^ ^ ^ ^ 4^  *^  ^ ^ ^ *^  4^  *^  ^ ^ *^  *^  ^ ^ *^  ^ ^ * * This module accepts s tr ings of b i t s from the higher l e v e l software * and sends them to the modem v i a the MC6854 Advanced Data Link * Contro l l er chip (ADLC). It also receives s tr ings of b i t s from the * modem, buffer these b i t s t r ings , and present them to the higher * l e v e l software. * / #include "stdio.h" #define DEBUG 0 / * set to 1 for debug output * / #define NOTB(b) ("(b) k OxFF) #if defined (_ TURBOC ) / * define c r l f O i f i n TURBOC * / void c r l f O { putcharl'Nn') ; > #endif / * the fo l lowing structure maps the reg is ters of the MC6854 chip * / s truct M6854 { unsigned char CR1; unsigned char CR2; unsigned char DATA; unsigned char LAST.DATA; >; #define SRI CR1 #define SR2 CR2 #define CR3 CR2 #define CR4 LAST.DATA #define A6854 0x1000 / * address of MC6854 on protoco l board * / #define ADLC (*(struct M6854 *) A6854) / * define b i t s i n the MC6854 contro l reg is ters * / #define TX_RS_BIT 0x80 #define RX_RS BIT 0x40 #define DISCONTINUE 0x20 #define RIE 0x02 / * receive interrupt enable * / #define TIE 0x04 / * transmit interrupt enable * / #define RTS.BIT 0x80 #define CLR_TX_STAT_BIT 0x40 #define CLR_RX_STAT_BIT 0x20 #define IRQ BIT 0x80 #define TDRA.BIT 0x40 #define TXU BIT 0x20 #define CTS.BIT 0x10 156 #define S2RQ BIT 0x02 #define RDA.BIT 0x01 #define RDA2 BIT 0x80 #define 0VRN_BIT 0x40 #define DCD.BIT 0x20 #define ERR BIT 0x10 #define RX_ABT_BIT 0x08 #define RX_IDLE_BIT 0x04 #define FV_BIT 0x02 #define AP.BIT 0x01 / * receive arbort b i t * / / * receive i d l e b i t * / / * frame v a l i d b i t * / / * address present b i t * / / * define return codes for the send routine * / #define OK 0 #define CTS_TIMEOUT_ERR -1 #define TXU ERR -2 #define CTS LOST_ERR -3 #define ALREADY ON 1 #define ALREADYlOFF 2 / * return code for f a i l e d memory a l l o c a t i o n c a l l * / #define ALLOC.ERR -1 #"7,01000000") #7,01000000") / * define some processor spec i f i c macros * / #if defined(__CC09__) #define FIRQ_0N asm (" andcc #define FIRQ_0FF asm (" orcc #else #define FIRQ ON #define FIRQ OFF #endif #if defined(__CC09__) extern void (*_firqhan)(); #else vo id (*_firqhan)(); #endif / * memory images of the 6854 contro l reg is ters * / unsigned char C R l i ; unsigned char CR2i; unsigned char CR3i; unsigned char CR4i; #define TB SIZE #define RB.SIZE typedef char typedef char / * #def #define #define #define #define #define #define #define #define ines f o r values FREE ACTIVE COMPLETE.OK COMPLETE.CRC RX_IDLE_FLAG RX_ABT_FLAG DCD_LOST_FLAG RX_OVRN_FLAG 128 / * default transmit buffer s ize * / 128 / * default transmit buffer s ize * / TB [J; RB []; for RBD.status * / 0 / * unused * / 1 / * current ly rece iv ing to t h i s buffer * / 2 / * buffer has received a complete frame * / 3 / * as above with a CRC error i n d i c a t i o n * / 4 / * rx i d l e received during reception * / 5 / * rx abort received during reception * / 6 / * c a r r i e r detect was los t during recptn * / 7 / * an rx overrun occured during recptn * / 157 #define RX_BUFFER_OVRN 8 / * incoming packet exceeded buffer s ize * / / * b i t de f in i t i ons for completion reject f l a g (see init_6854) * / #define IGNORE MASK(status) (1 « #define C0MPLETE_0K_IGN0RE IGNORE #define COMPLETE_CRC_IGNORE IGNORE, #define RX_IDLE_FLAG_IGNORE IGNORE #define RX.ABT FLAG.IGNORE IGNORE #define DCD.LOST FLAG.IGNORE IGNORE #define RX.OVRN FLAG IGNORE IGNORE #define RX.BUFFER OVRN IGNORE IGNORE (status-2)) _MASK(COMPLETE_OK) .MASK(COMPLETE.CRC) _MASK(RX_IDLE_FLAG) MASK(RX ABT.FLAG) _MASK(DCD_LOST_FLAG) MASK(RX OVRN.FLAG) MASK(RX.BUFFER.OVRN) / * the above status f lags char *status_desc[] = { "complete "dcd los t overflow" typedef s truct _RBD •( s truct _RBD * l i n k ; unsigned in t bu f . s i z e ; RB *buf_ptr; unsigned int n.bytes; unsigned i n t addr . len; char status; unsigned long rx. t ime; > RBD; i n words * / "free", "active", "complete (ok)", (crc)", "rx i d l e f l ag" , "rx abort f lag" , f l ag" , "rx overrun f l ag" , "rx buffer >: / * pointer to next rbd on a l i s t * / / * s ize of the character buffer (bytes) * / / * pointer to character buffer * / / * number of characters i n the buffer * / / * number of address bytes i n the buffer * / / * status ind icator for the buffer * / / * time of reception of buffer informtn * / RBD * f r e e _ l i s t , *complete_list , *active; unsigned buf_size; unsigned cts_timeout; unsigned ignore.mask; / * mask of completion condtns to ignore * / vo id include_m6854() O void -C f a t a l (char *s) / * Function which pr in t s an error message and res tar t the system * / f f lush(s tdout) ; puts(s ) ; f f lush(s tdout) ; #if defined(__CC09__) asm(" jmp [$fffe]"); #else exit (99); #endif i n t i dcd_active(void) / * Function which returns the status of DCD s igna l * / return (ADLC.SR2 * DCD.BIT) ? 0 : 1; vo id get_free_rbd(void) 158 •c / * Function that gets a new RBD from the free l i s t , f i l l s i n i t ' s f i e l d s , and makes act ive point to i t . At present, i t w i l l be a f a t a l error i f no rbd's are free . * / #define OLD 0 i f ( f r e e . l i s t == NULL) { / * no free buffers l e f t * / #if OLD f a t a l ( " \ n f a t a l error : No free RBD's\n"); #else i f (complete_list == NULL) fatal("\nNo RBD's anywhere\n"); / * remove an RBD from the complete l i s t * / act ive = complete_list; complete_list = complete_list -> l i n k ; > else { #endif act ive = f r e e _ l i s t ; / * remove an RBD from the free l i s t * / f r e e _ l i s t = f r e e _ l i s t -> l i n k ; act ive -> l i n k = NULL; / * f i l l i t i n * / act ive -> n_bytes = 0 ; act ive -> addr_len = 0 ; act ive -> status = ACTIVE; vo id put_complete rbd(char stat) •C / * Function that time stamps the active rbd and moves i t to the completed l i s t , i f completion status i s not ignored. * / i f (ignore.mask kk IGNORE_MASK(stat)) { act ive -> rx_time = get t imeO; / * time stamp * / act ive -> status = stat; / * f i l l i n completion status * / / * place at beginning of l i s t * / act ive -> l i n k = complete_list; complete_list = act ive; > act ive = NULL; vo id free_rbd (RBD *r) / * Function that returns the given rbd to the pool of free rbd ' s . * / char oldcc; r -> status = FREE; oldcc = _setcc(0x50); r -> l i n k = f r e e _ l i s t ; f r e e _ l i s t = r ; _setcc(oldcc); RBD *al loc_rbd (void) 159 / * Function that a l locates a receive buffer of the given s ize from the dynamic memory heap and returns a pointer to i t . It returns ALL0C_ERR i f memory a l l o c a t i o n f a i l s . * / RBD *p; i f C(p = (RBD *) sbrk(sizeof (RBD))) == (RBD *) -1) return (RBD *) NULL; i f ((p -> b u f . p t r = (RB *) sbrk(buf_size)) == (RB *) -1) return (RBD *) NULL; p -> buf_size = buf_size; return p; vo id isr_6854() ' / * This i s the interrupt service routine for the 6854. It i s responsible for reading i n characters . updating rbd status information, and a l l oca t ing new rbd's (current_rbd) when a complete frame has been rece ived .* / #if DEBUG p u t s C ' i : "); showbyte(ADLC.SRI); putchar(' ' ) ; showbyte(ADLC.SR2); c r l f ( ) ; #endif i f (ADLC.SRI ft IRQ.BIT) { i f (ADLC.SRI tt RDA.BIT) { i f (active == NULL) get_free_rbd(); i f (active ->n_bytes < buf_size) (*(active ->buf_ptr))[active->n_bytes++] = ADLC.DATA; else { / * buffer overflow * / ADLC.CR1 • C R l i I DISCONTINUE; put_complete_rbd(RX_BUFFER_OVRN); else i f (ADLC.SRI * S2RQ_BIT) < i f (ADLC.SR2 & AP.BIT) < i f (active == NULL) get_free_rbd(); i f (active->n_bytes < buf_size) { (*(active->buf_ptr))[active->n_bytes++] = ADLC.DATA; act ive -> addr_len++; else < / * buffer overflow * / ADLC.CR1 - C R l i I DISCONTINUE; put_complete_rbd(RX_BUFFER_OVRN); > J else i f (ADLC.SR2 & RX_IDLE_BIT) < ADLC.CR2 - CR2i I CLR_RX_STAT_BIT; i f (active != NULL) { ADLC.CR1 = C R l i I DISCONTINUE; 160 put_complete_rbd(RX_IDLE_FLAG); else i f (ADLC.SR2 & ERR_BIT) < ADLC.CR2 = CR2i I CLR RX.STAT BIT; i f (active != NULL) { i f (ADLC.SRI b RDA_BIT) (*(active->buf ptr))[active->n_bytes++] : ADLC.DATA; put_complete_rbd(COMPLETE_CRC); } > else i f (ADLC.SR2 & FV BIT) < ADLC.CR2 = CR2i I CLR_RX_STAT_BIT; i f (active != NULL) { i f (ADLC.SRI & RDA.BIT) (*(active->buf_ptr))[active->n_bytes++] ADLC.DATA; put_complete_rbd(COMPLETE_OK); > } else i f (ADLC.SR2 & DCD BIT) { ADLC.CR2 = CR2i I CLR_RX_STAT BIT; i f (active != NULL) { ADLC.CR1 = C R l i I DISCONTINUE; put_complete_rbd(DCD_LOST_FLAG); > > else i f (ADLC.SR2 ft OVRN_BIT) { ADLC.CR2 « CR2i I CLR RX STAT BIT; i f (active != NULL) < ADLC.CR1 = C R l i I DISCONTINUE; put_complete_rbd(RX_OVRN_FLAG); > > else i f (ADLC.SR2 & RX_ABT_BIT) { ADLC.CR2 = CR2i I CLR_RX_STAT BIT; i f (active != NULL) { ADLC.CR1 = C R l i I DISCONTINUE; put_complete_rbd(RX ABT FLAG); > } > return; i n t init_6854 (unsigned n_buffers, unsigned buf fer_s ize , unsigned cts_time, unsigned ignore_msk) / * This funct ion i n i t i a l i z e s the MC6854 chip and sets up the data structures for the system. A b i t mask spec i f ies which of the rbd completion status conditions w i l l cause the rbd to be stored on the complete l i s t . B i t posi t ions correspond to completion status values according to the mapping given i n the #define sect ion above. * / 161 unsigned i n t i ; RBD *p; FIRQ.OFF; _f irqhan = isr_6854; / * reset tx and rx , ac = 1 * / ADLC.CR1 = C R l i = OxCl; /*11000001*/ / * d t r on, test o f f , non-loop, f l a g detect status of f , 11 i d l e , no addr extend, no contro l f i e l d extend, no l o g i c a l c n t l f i e l d */. ADLC.CR3 = CR3i = 0x80; /*10000000*/ / * NRZ, no abort extend, 8 b i t rx and tx word length, double f l ag mode FF * / ADLC.CR4 = CR4i = OxlF; /*00011111*/ / * ac = 0 * / ADLC.CR1 = C R l i = OxCO; / * r t s o f f , c l r tx and rx status, tdra staus se lec t , mark i d l e , 1 byte, pse * / ADLC.CR2 = CR2i = 0x61; /*01100001*/ / * enable tx , enable rx , don't enable rx i n t e r r u p t , ac = 0 * / ADLC.CR1 = C R l i = 0x02; /*00000010*/ act ive = f r e e _ l i s t = complete_list = NULL; buf_size = buffer_s ize; cts_timeout = cts_time; ignore_mask = ignore_msk; / * a l locate receive buffers and buffer descriptors dynamically * / for ( i = 0; i < n_buffers; i++) { i f ( (p = a l l o c . r b d O ) == NULL) return ALL0C_ERR; free_rbd(p); FIRQ.ON; return OK; in t send_bits (char *data, unsigned in t n) i / * This funct ion sends a packet out to the MC6854. Timeout gives the number of t i c k s (0.064ms) to wait f or CTS to be granted, i f CTS i s not granted within t h i s time a CTS TIMEOUT error i s returned. */ unsigned long tout; char done; / * assert RTS * / ADLC.CR2 = CLR_TX_STAT_BIT I (CR2i |= RTSJ3IT) ; / * read the timer * / tout = gettimeO + cts_timeout; / * wait f or CTS or timeout expired * / f o r ( ; ; ) < i f (!(ADLC.SRI & CTS.BIT)) break; i f (gettimeO >= tout) { ADLC.CR2 = CR2i tt= NOTB(RTS.BIT) ; 162 return CTS_TIMEOUT_ERR; > / * now CTS has been granted, put the data out to the device * / done = (n == 0); while (Idone) { / * wait for TDRA or TXU or CTS los t * / i f (ADLC.SRI ft TDRA.BIT) { i f (n == 1) < ADLC.LAST_DATA = *data; done = 1; else i ADLC.DATA = *data++; n - ; } else i f (ADLC.SRI ft TXU BIT) { ADLC.CR2 = CLR TX.STAT BIT I (CR2i &= NOTB(RTS_BIT)); return TXU.ERR; else i f (ADLC.SRI ft CTS.BIT) { ADLC.CR2 = CLR TX_STAT BIT I (CR2i &= N0TB(RTS BIT)); return CTS_LOST_ERR; > / * wait f or f i n a l TDRA to give RTS some extra time * / while (!(ADLC.SRI ft TDRA_BIT)) ; / * a l l done, turn off RTS and return * / ADLC.CR2 = CR2i &= NOTB(RTS_BIT); return OK; RBD *get_rbd (void) < / * This funct ion returns a pointer to the oldest rbd i n the system (or NULL i f a l l rbd's are empty), and removes the returned RBD from the complete l i s t . * / RBD *p, *q; char o ldcc; oldcc = _setcc(0x50); / * i n t r r p t s off while manplating l i s t head*/ p = complete_l ist; i f (p == NULL I I p -> l i n k • » NULL) < complete_list = NULL; _setcc(oldcc); return p; > _setcc(oldcc); / * restore interrupt masks * / while(p->link->link != NULL) p = p->link; q = p -> l i n k ; p->link - NULL; return q; 163 Appendix B Logical Link Controller /******************************************************************** * L L C . C * *********************************************** * * This module provides IPL LANs' flow and error control services. * Improved error control scheme is achieved by multiple packet copies * retransmissions and code combining. */ #include "stdio.h" #include "mam.h" time_val waiting_time; void llc_tx_data(int data_len, char src) /* This function creates data information of length data_len in the information data field of the transmit buffer (TB) */ char *p; int i ; p = txbuf.data; /* set p to data start addr */ for(i=0; i < data.len; i++) *p++ = ( (i % 60) ? src : ' \ r ' ); > void llc_rx_data(RBD *p) i /* Function that prints received messages on a screen. */ char *q; u_int n; q = p->buf_ptr->data; /* set q to data start address */ if( p->buf_ptr->cntl fr STATEBIT.MASK ) n = p->n_bytes - 5; else n = p->n_bytes - 3; crlf (); while( n— ) { if(*q == '\ r-) pUts( "\n" ); else putchar(*q); q + + ; > > typedef unsigned int crc_type; /* This is the ccitt-crc generator polynomial less it's msb and bit 164 reversed * / #define POLY (0x8408U) void bytecrc(crc type *crc , unsigned char ch, unsigned n) i / * Function that modifies *crc to to account for adding the n l sb ' s of ch. 0<=n<=8. * / char q; crc_type x; while (n—) { x = *crc; q = x " ch; *crc » = 1; i f (q k 1) *crc * - POLY; ch » = 1; > crc_type blockcrc (unsigned char *p, unsigned long n) / * Function that calculates the c c i t t - c r c on a block of data. It ca lculates the crc for a block of n b i t s stored at p * / crc_type v a l ; unsigned todo; / * i n i t i a l i z e crc to a l l ones *./ v a l = OxFFFF; / * ca lculate crc on a l l b i t s i n the b i t s t r i n g * / todo = n k 7; / * number of b i t s to do at end * / n >>= 3; • / * n = number of whole byte to do * / while (n—) bytecrc (AWal, *p++, 8) ; i f (todo) bytecrc (fcval, *p, todo) ; return v a l ; vo id append_crc(char *q , in t m) { / * Function that appends the complement of computed crc on a m-bytes information (Address, contro l and data) i n q and places the r e s u l t i n g 2-bytes crc i n a data packet's c r c - f i e l d * / unsigned i n t c r c ; / * append l ' s complement of crc to data f i e l d * / crc = "blockcrc(q, m*8); q += m; *q++ = crc k OxFF; / * crc i s unsigned integer 16 b i t s * / *q = (crc » 8) k OxFF; / * *q i s char 8 b i t s * / 165 i n t check_crc(RBD *p, in t m) •C / * Function that checks crc on m-bytes received b i t s i n a packet stored at p, inc luding the appended c r c . It returns GOOD or N0_G00D depending on the r e s u l t . * / unsigned i n t crc ; crc = blockcrc((char *)(p->buf_ptr), m*8); i f (crc == 0xF0B8) return GOOD; else return NO.GOOD; vo id retxn_mgmt(char dest, char s r c , in t d l e n , in t tx_type, RBD •C / * Function that retransmits three copies of a packet whenever timeout occurs. Before retransmitt ing the copies i t backs off random number of s l o t s . * / in t no_txns; i f ( retxns < MAX.RETXNS ) { i f ( tx . type == TOUT.TX ) { retxns++; backoff( ) ; no_txns = 3; tx_frame(dest. s r c , d_len+5, no_txns, p , I_FRAME, 1); else { p r i n t f ( "\nRetxns to s tat ion %c exceeded ! " , dest ); exceeded**; retxns = last_txns = 0; retxns_exceeded = 1; > > i n t recognize_addr(RBD *p) / * Function that checks whether a received frame i s addressed to t h i s s ta t ion then returns an appropriate status * / i f ( p->buf_ptr->dest == txbuf . src ) return GOOD; e lse return NO_GOOD; vo id rx_handler(RBD *p) < / * This funct ion i d e n t i f i e s the dest inat ion , type and sequence of received packet stored at p. It then sends ACK i f the frame i s not a copy, or c a l l s ack_handler() to compute necessary transmission s t a t i s t i c s , i f the packet i s an ACK. * / in t bytes = 3; / * f i r s t , check i f i t ' s for t h i s s ta t ion * / i f ( recognize_addr(p) == GOOD ) < 166 /* then check if it 's an information frame */ if((p->buf_ptr->cntl k TYPE_MASK) == I.FRAME ) { /* check to see i f it 's a copy */ if( (p->buf_ptr->src == last_src) kk ((p->buf_ptr->cntl & SEQ_MASK) == last.seq) ); /* the frame was: for this station, information, and a copy... do nothing */ else { •/* the frame was: for this station, information, and not a copy... send ack */ free_errpkts(); tx_frame(p->buf_ptr->src, txbuf.src, bytes, 1, p, S.FRAME. 0); if(print_msg) llc_rx_data(p); > /* update the last src and seq variables to reflect this frame */ last_src - p->buf_ptr->src; last.seq = (p->buf_ptr->cntl k SEQ_MASK); > else { /* frame is ack, previous transmision successful */ if((p->buf_ptr->src == last_src) kk ((p->buf_ptr->cntl & SEQ.MASK) == last_seq); /* the frame is for this station, ACK, and a copy, do nothing */ else { /* the frame is for this station, ACK, and not a copy */ ack_handler(); last.src = p->buf_ptr->src; last.seq = (p->buf_ptr->cntl k SEQ_MASK); > } free_rbd(p); } void majority.vote(int n, char *ql, char *q2, char *q3, char *result) /* This function accepts 3 copies of the same data (possibly with errrors) pointed to by q l , q2, and q3. Each packet consists of n bytes. It then f i l l s in the data in *resuit with the majority decision of the three copies. */ while(n—) { •result = (*ql k *q2) I (*q2 k *q3) I (*q3 k *ql); result++; ql++; q2++; q3++; > } void free_errpkts(void) < /* Function that discards previously stored errored packets */ 167 while(err_pkts > 0) free_rbd(r[--err_pkts]); > void rx_error_mgmt(RBD *p, int data_len) < /* This function stores received errored packets pointed to by p. Whenever three copies of a packet are received it performes majority voting, then checks CRC again. If CRC is ok, i t sends ACK, else the three copies are discarded. */ if(p->n_bytes >= data_len+5) < r[err_pkts++] = p; if(err_pkts == 3) { majority_vote(data_len+5, (char *)r[0] , (char *)r[l], (char *)r[2], (char *)r[2]); if(check_crc(r[2], data_len+5) == GOOD) rx_handler(r[2]); else free_errpkts(); } } else { #if DEBUG ?rintf( "\nError, status = %sn. status_desc[p->status] ); free_rbd(p); > > 168 Appendix C Medium Access Manager /******************************************************************** * M A M . C * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * This module contains routines required to perform functions * perta in ing to data encapsulation, framing, addressing and medium * a l l o c a t i o n . */ #include #include "stdio.h" "mam.h" #define #define #define #define #define GOOD N0_G00D PER.TICK BYTE SECS 0 1 0.064 8 1000.0 / * interrupt every 0.064 ms * / / * b i t s per byte * / / * define data structures * / #define DATA.SIZE 200 #define SCHED SIZE 120 #define NR_RBDS 6 #define CRC.SIZE 2 typedef s truct PACKET < char dest; char src ; char c n t l : char datat DATA.SIZE ]; char crc [ CRC_SIZE ]; }PACKET; PACKET txbuf, rxbuf; typedef s truct _RBD { s truct _RBD * l ink; u_int buf s ize ; PACKET *buf_ptr; u_int n_bytes; u_int addr_len; char status; time_val , rx_time; >RBD; / * 200 bytes * / / * 120 bytes * / / * 2 bytes * / / * dest inat ion address f i e l d * / / * source address f i e l d * / / * contro l information f i e l d * / / * data information f i e l d * / / * crc f i e l d 2 bytes * / RBD *get_rbd(), *prcd_pkt, *r[NR_RBDS]; 169 RBD *get_rbd(void); vo id free_rbd(RBD *p); typedef s truct _STAT { in t packets; in t qued_pkts; in t txed_pkts; in t tot_retxns; in t data_len; double tot_pkt_delay; time_val exp_start_time; time_val exp_stop_time; in t sched.tbl[SCHED }STAT; / * t o t a l number of generated packets * / / * number of qued packets * / / * number of transmitted packets * / / * t o t a l number of retransmissions * / / * information data length i n bytes * / / * t o t a l packet delay * / / * experiment s tar t time * / / * experiment stop time * / .SIZE]; / * a r r i v a l times sched table * / STAT s; / * HDLC contro l f i e l d * / #define I.FRAME #define S.FRAME #define TYPE MASK #define SEQ MASK #define STATEBIT.MASK 0x00 0x80 0x80 OxOF 0x40 / * transmission variables * / #define CTS OUT 400 #define MEAN_V_PERI0D 10 #define HEADER 7 #define MAX RETXNS 16 #define BACKOFF 200 / * information frame type * / / * ACK frame type * / / * channel s ta t e -b i t mask * / / * 400 ms * / / * 10 ms * / / * 7 bytes * / / * maximum retransmissions * / / * 200 ms * / / * macro type de f in i t ions * / #define CLEAR SCREEN "\xlB[2J\xlB[1;1H" / * ANSI c l ear screen * / #define NOTB(b) ("(b) k OxFF) / * macro to invert a b i t * / t ime_val waiting_time, beg_timeout; vo id tx_frame_encap(char dest, char s r c , in t bytes, i n t type, int retxmit) / * Function that appends dest, src addresses and contro l information to data i n TB. * / txbuf.dest = dest; txbuf . src = src ; i f ( s e q == OxOF) seq = 0x00; i f (re txmit ) t x b u f . c n t l = (type I seq I STATEBIT_MASK); / * s ta t e -b i t ON * / Q X S O t x b u f . c n t l = (type I seq) k (NOTB(STATEBIT_MASK)); / * OFF * / seq += 0x01; / * pass to append_crc() a char pointer set to PACKET.dest * / i f ( re txmit ) append.crc((char *)&txbuf, bytes - CRC_SIZE); 170 void priority() •C /* Function that delays for a slot time duration in order to give priority to ACK packets */ unsigned long time, temp; time = gettimeO ; temp = (MEAN_V_PERIOD / PER.TICK); while( gettimeO < time + temp ); > void backoff() { /* This function runs the backoff clock when a retransmission occurs to randomize the beginning of the retransmission */ unsigned long time, temp; time = gettimeO ; temp • ( (rand(BACKOFF)) / PER.TICK ); while( gettimeO < time + temp ); int deference(char src, RBD *p) /* This function runs the deference clock while monitoring received frames. If a valid frame for the station is received without error, i t arborts defering in order to send back acknowledgement. */ unsigned long time, temp; int tx_status - GOOD; time = gettimeO; temp = (rand(mean_retxn_delay) / PER.TICK ); while( gettimeO < time + temp ) •( if( (p = get.rbdO) != NULL) { prcd_pkt = p; if(p->buf_ptr->dest == src) < tx.status = N0_G00D; break; else { free_rbd(p); prcd_pkt = NULL; > > > return tx_status; > int tx_link_mgmt(int bytes, char src, int type, int no_txns, RBD *p) /* This function avoids contention with other traffic on the channel 171 by monitroing DCD signal and defering to passing traffic. It gives ACK packets priority and returns a transmission status that indicates whether a transmission is successful or not. */ int tx_status = NO.GOOD, k = 0. i , N0_ACKS = 2; if(type != I.FRAME) { /* ack frame, send i t without delay */ for(;;) < if( !dcd_active() ) { /* Is channel idle ? */ if( p->buf_ptr->cntl & STATEBIT.MASK ) < for(i=0; i<N0_ACKS; i++) tx_status = send_bits(fctxbuf, bytes); else tx_status = send_bits(&txbuf, bytes); break; /* break, since acks must be sent fast */ > > else < /* info frame, proceed with normal CSMA mode */ for(;;) { if( !dcd_active() ) { / * is channel idle ? */ priorityO ; /* give priority to acks.*/ if( ! dcd_active() ) { /* if s t i l l idle, transmit */ waiting_time = gettimeO - arrival_time; while(no_txns--) { if((tx_status = send_bits(&txbuf.bytes)) == GOOD) k++; if(no_txns != 0) for(i=0; i<100; i++); if(k>0) { beg_timeout = gettimeO; ack_t_out = gettimeO + ACK_0UT; wait_ack = 1; break; else if((tx_status = deference(src,p)) == N0_G00D) ^ break; else if((tx_status = deference(src,p)) == N0_G00D) break; > J return tx_status; > void tx_frame(char dest, char src, int bytes, int n, RBD *p, int type, int status) /* This function checks whether frame is INFO or ACK then calls tx_frame_encap() to construct the frame. Next tx_link_mgmt() is called to perform the actual transmission. If transmission is unsuccessful tx_successful is set */ 172 i f ( type == I_FRAME) tx_frame_encap(deat, s r c . bytes, I_FRAME, status); else tx_frame_encap(dest, s r c , bytes, S_FRAME, s tatus); i f ( (tx_link_mgmt(bytes, s r c , type, n . p) == NO_GOOD) kic (type == I_FRAME) ) send_successful = NO_GOOD; else i f ( type == I_FRAME) send_successful = GOOD; } void rx_frame(RBD *p) i / * This funct ion checks CRC status of a received frame. If CRC i s ok, i t c a l l s rx_handler() to ident i fy the packet and send ACK, e lse i t c a l l s rx err mgmtO to t ry and recover the noisy packet. * / i f (p->status == COMPLETE.OK) rx_handler(p); e lse rx_error_mgmt(p, s .data_len); prcd.pkt » NULL; 173 Appendix D Data Link Driver /****************************************^ * D L D . C * *********************************************** * * This module continously checks received packets and passes them to * MAC sublayer. It also monitors keyboard inputs , generates and * transmits new and rescheduled packets. */ #include "stdio.h" #include "mam.h" char ins ta l l_address ( in t number_of_stns) / * Function which seeds a station's random number generator with i t s own s ta t ion address. It returns the station's address. * / char src ; do { puts("\n \n lnsta l l source s ta t ion address , (A /B/C/D/E) : "); putchar(src = getchO); y while( src >= number_of_stns + 'A ' ); puts("\n"); / * seed random number generator with s ta t ion address * / srandC (u_int) src ) ; srand( rand(10000) ) ; re turn(src ) ; > i n t speed(void) i / * Function which i n s t a l l s and returns a station's baud rate . * / in t baud_rate; puts( "\n\nGive speed: " ); scanf( "%d n, &baud_rate ); switch (baud_rate) { case 9600* ACK.OUT = (60/PER.TICK); / * 60 ms * / break; case 4800* ACK.OUT « (80/PER.TICK); / * 80 ms * / break; case 2400: ACK.OUT = (100/PER.TICK); / * 100 ms */ break; 174 case 1200: ACK_0UT = (140/PER_TICK); / * 140 ms * / break; } return baud_rate; > double iatime(void) / * Function which returns the p r o b a b i l i t y of a packet generation * / double sigma; puts( "\n\nEnter PROB. OF PACKET GENERATION: "); scanf( "%lf", fcsigma ); return sigma; > void print.message(void) < / * Function which controls whether received messages are pr inted on screen. * / char c; puts( "\n\nDo you want to p r i n t received messages (Y/N) ? : "); putchar(c = g e t c h O ) ; i f ( c == 'Y' ) print_msg = 1; else print_msg = 0; puts( "\n" ); > char choose_dst(int number_of_stns) / * Function which randomly chooses on of number of_stations stations * / char c; c = rand(number_of_stns -1) + ' A ' ; return( (c >= txbuf .src) ? c+1 : c )'; vo id sched_packets(double sigma) < / * Function which computes and returns the next packet a r r i v a l time * / in t i , *q; q = s .sched_tbl; for(i=0; i<SCHED_SIZE; i++) *q++ = geo.rand(sigma); } void mainQ 175 * The main rout ine , i t i n t i a l i z e s the ADLC ch ip , then i n s t a l l s the system. It also generates new packets, transmits and retransmits packets, gets received packets and monitors keyboard inputs . * / double data_tx_time, sigma; char ins ta l l_address ( ) , choose_dst(), dest, c; in t number_of_stns, baud_rate, *q , no_txns = 1; RBD *p; double nu = 0.02; / * INITIALIZE THE 6854 CHIP * / i f ( init_6854(NR.RBDS, s izeof (rxbuf) . CTS.OUT, 1) != GOOD) f a t a l ( " I n i t i a l i z a t i o n f a i l e d " ); / * INSTALL SYSTEM * / puts( CLEAR.SCREEN ) ; puts (" \n \n \n === POWER-LINE SERVICE NETWORK ===") puts( "\n version 9-05-88"); puts( " \n \n \n \n \n \n" ) ; puts( "\n\nGive number of s tat ions: " ); scanf( "7,d", &number_of _stns ) ; txbuf . src = install_address(number_of_stns); baud_rate = speed(); TRIALS = simJLengthO ; s .data_len = data_length(); sigma = i a t i m e O ; sched_packets(sigma); dest = choose_dst(number_of_stns); l l c_tx_data(s .data_len , t x b u f . s r c ) ; i n i t _ v a r i a b l e s ( ) ; print_msg = 0, last_seq = t x b u f . c n t l = seq = 0x00; ommands: info_tx_time = (double)(s.data_len + HEADER) * BYTE / (double)baud_rate; data_tx_time = (double) s .data_len * BYTE / (double)baud_rate; s.exp_start_time = 0, las t_src = txbuf . src ; puts ("\nEnter a command, type 'H* for help -> "); f o r ( ; ; ) { i f ( ( ge t t imeO >= n e x t . a r r i v a l ) kk (s.txed_pkts < TRIALS) kk (s.qued.pkts == 0) kk (s.exp_start_time > 0 ) H next_arr iva l = ge t t imeO; next_arr iva l += (*q++ / PER_TICK); s.packets++; s.qued_pkts++; arr iva l_t ime = ge t t imeO; } / * check i f any frame has been received * / i f ( prcd.pkt != NULL ) rx_frame(prcd.pkt); else i f ( (p = g e t . r b d O ) != NULL ) rx_frame(p); else { / * check, and transmit packets * / i f ( (s .qued_pkts > 0) kk (!wait_ack) kk (s.exp_start_time > 0 ) K 176 if((tx_successful == G O O D ) I retxns_exceeded) i tx.successful -= N O _ G O O D ; retxns_exceeded = 0; _^  dest = choose_dst (number_of _stns); i f ( (last.retxns == 0) kk (!retxn_pending) ) tx_frame(dest, txbuf.src, s.data_len + 3, no_txns, p, I . F R A M E . 0 ) ; else retxn_mgmt(dest, txbuf.src, s.data len, NEW T X , > > i f ( wait_ack kk (s.exp_start_time > 0) ) { i f ( gettimeO > ack_t_out ) { wait_ack =0; retxn_pending = 1; retxn_mgmt(dest, txbuf.src, s.data len, T O U T T X , p); > > i f ( kbhit(stdin) > 0 ) < c = getchO ; switch(c) { case 'H': print_help(); goto commands; case ' T ' : init_variables(); /* generate 1st pkt, schedule next pkt */ s.packets++; s.qued_pkts++; q = s.sched.tbl; next_arrival = gettimeO; next_arrival += (*q++ / P E R _ T I C K ) ; s .exp_start_time = gettimeO; break; case ' S ' : baud_rate = speed(); goto commands; case * D ' : s.data_len = data_length(); goto commands; case ' I * : sigma = iatimeO ; sched_packets(sigma); goto commands; case ' R ' : print_results(data_tx_time,baud_rate,s.data_len, sigma); goto commands; case *M': print_message(); goto commands; case ' L ' : T R I A L S '• sim_length(); goto commands; 177 case 'A*: txbuf . src = install_address(number_of_stns); goto commands; default : puts( "\nUnknown command\n" ); goto commands; 178 PUBLICATIONS J.O. Onunga and R.W. Donaldson, "Performance of CSMA with priority acknowledge-ments on intrabuilding power line local area networks," in IEEE WESCANEX 88  Digital Commun. Conf. Proc, Saskatoon, Saskatchwewan, pp. 30 - 37, May 1988. J.O. Onunga and R.W. Donaldson, "Distribution Line communications using CSMA access control with priority acknowledgements on intrabuilding power line local area networks," IEEE Trans. Power Delivery, vol. 4, pp. 878 - 886, April 1989. J.O. Onunga and R.W. Donaldson, "Personal computer communications on intrabuild-ing power line LANs using CSMA with priority acknowledgement," IEEE Trans.  J. Selected Areas in Commun., vol. SAC-7, pp. 180 - 191, Feb 1989. J.O. Onunga and R.W. Donaldson, "Analysis of carrier sense multiple access with priority acknowledgements (CSMA/PA) on noisy two-way channels with finite user population," in Proc. IEEE Pacific Rim Conf. Commun. Comput. , and Signal  Processing. , Victoria B.C., Canada, June 1989, in press. J.O. Onunga and R.W. Donaldson, "A simple two-state ARQ strategy for throughput and delay enhancement on channels with slowly varying signal- to-noise ratio," submitted for publication, June 1989. J.O. Onunga and R.W. Donaldson, "Performance analysis of CSMA with priority ac-knowledgements (CSMA/PA) on noisy data networks with finite user population," submitted for publication, July 1989. 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0098211/manifest

Comment

Related Items