Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A power line local area network : design and implementation Ma, Audivox Hing Ting 1987

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

Item Metadata


831-UBC_1987_A6_7 M22.pdf [ 4.82MB ]
JSON: 831-1.0051920.json
JSON-LD: 831-1.0051920-ld.json
RDF/XML (Pretty): 831-1.0051920-rdf.xml
RDF/JSON: 831-1.0051920-rdf.json
Turtle: 831-1.0051920-turtle.txt
N-Triples: 831-1.0051920-rdf-ntriples.txt
Original Record: 831-1.0051920-source.json
Full Text

Full Text

A POWER LINE LOCAL AREA NETWORK : DESIGN AND IMPLEMENTATION By AUDIVOX HING TING MA B.C.Sc., University of Manitoba, 1985 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in THE FACULTY OF GRADUATE STUDIES (DEPARTMENT OF COMPUTER SCIENCE) We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA October 1987 © Audivox Ma, 1987 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of The University of British Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date j l j . f l frc* t4£7 DE-6(3/81) Abstract This thesis presents the development and implementation of two fundamental com-munication sublayers, medium access and logical link, for a new Local Area Network (LAN) which utilizes the intra-building power distribution circuit as physical transmis-sion medium. This medium provides a low cost means for data communications with a high degree of portability. A low-to-medium data rate and a relatively high error rate are two of the major disadvantages associated with the use of the medium. The Logical Link Control (LLC) protocol adopted is a modified version of the IEEE 802.2 protocol; whereas, the Medium Access Control (MAC) protocol used is a simple hub polling scheme. For efficiency reason, both LLC and MAC sublayers are implemented in the kernel of the UNIX 1 operating system. The schemes used, justifications for the decisions made and their implementations are discussed in details in the thesis. The performance of the power line LAN formed with four Sun workstations 2 using modems with a data rate of 14.4 kilo-bit per second is measured and analyzed. lTJNIX is a trademark of A T ic T Bell laboratories. 2Sun workstation is a trademark of Sun Microsystems. ii Contents Abstract ii Contents iii List of Tables v List of Figures vi Acknowledgement vii 1 Introduction 1 1.1 Motivation and Objectives . . \ 1 1.2 Thesis Summary 3 2 Hardware Configuration 5 2.1 Power Lines as Transmission Medium . 5 2.2 Bus Interface Unit 7 2.2.1 Between modem and modem 7 2.2.2 Between modem and host 9 2.3 Summary and Remarks 12 3 Access and Link Protocols 13 3.1 Review on Medium Access Protocols 14 3.1.1 Contention protocols 14 3.1.2 Non-contention protocols 17 3.2 Link Level Protocol 22 3.3 Description of The Medium Access Control Protocol 24 3.3.1 Hub polling scheme . 24 3.3.2 Data transfer phase . . 27 3.3.3 Error recovery mechanism 29 iii 3.3.4 Invitation phase 32 3.3.5 Modified logical link control 38 4 Implementation Details 43 4.1 A Global View . . 44 4.2 Implementation of the Physical Layer 45 4.2.1 Zilog 8530 SCO driver . . . 46 4.3 Implementation of MAC Sublayer 50 4.4 Implementation of LLC Sublayer 51 4.4.1 Modification and enhancement 52 4.4.2 Interface between LLC and its users . 54 4.4.3 Between LLC and station management unit 58 5 Performance Measurements 60 5.1 Experimental Set-up 60 5.2 Performance of MAC Sublayer 62 5.3 Overall Performance 70 6 Conclusions 82 6.1 Summary 82 6.2 Suggestions for Further Studies . . . . . . . . . . . . . . . . . . . . . . . 84 Bibliography 86 A Finite State Machines in Invitation Phase 88 B Example User Programs Utilizing L L C Services 91 iv List of Tables 3.1 Relationship between A value and collision prob 16 5.1 Mean station join time under different loadings 63 5.2 Mean death detection time under different loadings 66 5.3 Network throughput and delay under different loadings . 69 5.4 Setting number and corresponding parameters values 71 5.5 Measurement with 2 stations and 1 file (21 kbytes) transfer 72 5.6 Measurement with 3 stations and 1 file (21 kbytes) transfer 72 5.7 Measurement with 4 stations and 1 file (21 kbytes) transfer 73 5.8 Measurement with 3 stations, 2 file (21 kbytes) transfers and 1 server . 76 5.9 Measurement with 3 stations, 2 file (21 kbytes) transfers and 2 servers . 77 5.10 Measurement with 4 stations, 3 file (21 kbytes) transfers and 1 server . 78 5.11 Measurement with 4 stations, 3 file (21 kbytes) transfers and 3 servers . 79 v List of Figures 2.1 Bus Interface Unit on Sun 3/50 7 2.2 Timing diagram showing interaction of various signals 11 3.1 Frames used during the data transfer phase and error recovery (CRC excluded) . . 27 3.2 The 5-way handshake protocol . . 32 3.3 Frames used during the invitation phase(CRC excluded) 35 3.4 Figure showing S- and I- PDU format 40 4.1 Figural representation of LLC and MAC implementation 44 4.2 Format of a SDLC frame . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.1 Experimental network setup V 61 A . l Primary's invitation finite state machine (one per unique mailing ad-dress) during invitation phase 89 A.2 New station's joining finite state machine during invitation phase . . . . 90 vi Acknowledgement I would like to thank my supervisor Dr. Son Vuong for his guidance and support in preparation of this thesis. Thanks are also due to Dr. Samuel Chanson who serves as the second reader for this thesis. I would also like to extend my appreciation to the financial support provided by the Computer Science Department at UBC in form of teaching assistantship and a research assistantship from an NSERC Strategic Grant of Dr. Vuong and Dr. Donaldson. Finally, my deepest gratitude to the great effort put in by the key modem designers Mr. Frank Chiu and Mr. Morgan Chan. Without whom this thesis will not be possible. vii Chapter 1 Introduction 1.1 M o t i v a t i o n and Object ives Local area networking is an area that has received much attention as a result of advance-ments in data communication and computer technologies in recent years. Generally, a local area network is characterized by its geographic locality, a high data transmis-sion rate and a low error rate. The last two desirable characteristics are contributed mostly by the fact that a dedicated cable is used as the underlying communication medium. The substantial cost of installing such a cabling system prevents a part of the user community, e.g. home computer user, from sharing the fruit of this technology advancement. To address the need for a low-cost LAN, different approaches [FLAT84,BERM84] have been proposed by various researchers. The communication research group here at UBC has proposed the use of electric power distribution circuit as a communication medium for LAN [GRAC85,VUON85,VUON87]. This approach alleviates not only the 1 CHAPTER 1. INTRODUCTION 2 cost problem since no wiring has to be done, in addition, an easy access to the network is provided. A power line modem and standard wall electricity outlet are used for de-livery and reception of data signal; However, this approach is not without flaws. The electric power distribution circuit is not built nor designed for data communication. Limitations in terms of low-to-medium data transmission rate and high error rate are observed in a power line communication system. Currently, prototype modems oper-ating at 14.4 kbps with an error rate of 10~3 to 10 - 8 are produced by the Electrical Engineering Department at UBC while the Computer Science Department is responsi-ble for producing communication softwares to be used in the power line communication system. To turn this hostile communication channel into a usable and reliable one, com-munication protocols are called for. In view of the available protocols for local area network, a very reliable physical medium is assumed. This assumption is invalid when a power line is used as the physical medium. Work on selecting and implementing the two fundamental communication sublayers in the 3-layer hierarchical communica-tion model for LAN recommended by the IEEE 802 committee namely, Medium Access Control (MAC) and Logical Link Control (LLC), is presented in this thesis. A modified version of the IEEE 802.2 LLC protocol is adopted aiming at increasing the effective throughput of each LLC connection. A hub polling scheme with dynamic address as-signment is implemented as the protocol for MAC sublayer. Furthermore, to examine CHAPTER 1. INTRODUCTION 3 the practicality of using the power line system for computer communications, the se-lected MAC and LLC sublayers are implemented on a network of Sun workstations interconnected by the power line communications system. For efficiency reason, both MAC and LLC sublayers are implemented in the kernel of the UNIX operating system. The performance of this power line LAN is also measured and analyzed. 1.2 Thesis S u m m a r y The rest of the thesis consists of five chapters as follows. Chapter two describes the characteristics of the hardware. This includes the char-acteristics of the power lines and the power line modems. A description of the Bus Interface Unit (BIU) is also included. Chapter three discusses the development of the access and link protocols to be used. Starting with a review on the available standards, various protocols are compared and contrasted in order to come up with suitable protocols. The second part of this chapter concentrates on describing the selected protocols, its suitability and the significance of the modifications made. Chapter four presents the implementation of the selected protocols on Sun 3/50. Implementation difficulties and compromises made are also discussed. Chapter five presents and discusses the results of the performance measurements on the implemented network. Measurements on the efficiency of the MAC implementation CHAPTER 1. INTRODUCTION 4 and the overall implementation are included. Finally, in Chapter six, the practicality using the power line distribution circuit as a communication medium in computer communications are commented upon, followed by suggestions for further work. Chapter 2 Hardware Configuration In the process of selecting appropriate low level protocols to be used in a LAN, char-acteristics of the physical medium should be taken into consideration. It is, therefore, essential to understand the behaviour of power lines. The characteristics of power lines as presented to the MAG sublayer, however, are somewhat dependent on the partic-ular medium access hardware used. This chapter describes the characteristics of the prototype power line modem on which the LAN is developed. 2.1 Power L ines as Transmiss ion M e d i u m As suggested by studies performed in the Electrical Engineering Department at UBC [CHAN85,CHIU85], characteristics of power lines vary in time and from location to location. Primary cause of this variation arises from the various power line loading effects. In general, noise level and attenuation which are the two primary factors responsible for the highly hostile power line communication environment, are found to 5 CHAPTER 2. HARDWARE CONFIGURATION 6 be high and varying. Bit error rate depends on a lot of factors but most of which are related to the use of power equipment. Results from the above mentioned studies suggest that the heavier a power line is loaded, the worse a channel becomes. Also, it is suggested in [GRAC85] that usage of vacuum cleaner and light dimmer tend to significantly increase the background noise level. To give an accurate figure for bit error rate of a power line is nearly impossible since it ranges from a probability of 10 - 3 in a noisy industrial power line to a probability of 10~8 in a quiet residential one. Error pattern also varies with different environment. Both burst and random bit errors can be observed, but burst error seems to be predominant in industrial power lines. However, bit-interleaving and forward error correction technique proposed in [CHIU85], to be utilized in the prototype modem will combat these burst errors to a large extent. The maximum distance covered depends on the attenuation of the power lines which in turns depends on the particular phase of the power distribution circuit as well as the presence of any special circuit protecting expensive power equipment against power surges. As expected, across-phase signal suffers from higher attenuation than in-phase signal. For a 3.0 Vrm3 (volt root mean square) transmitted signal, a distance of 1,000 feet of in-phase power line can be covered with a maximum of 16 communicating modems. Lesser distance can be expected for across-phase signalling. Unlike Ethernet, there is no restriction imposed on the minimum distance separating two communication stations. CHAPTER 2. HARDWARE CONFIGURATION 7 2.2 B u s Interface U n i t Bus Interface Unit (BIU) refers to the interfacing hardware which provides access to the power line bus. As far as the SUN 3/50 is concerned, a Zilog 8530 SCC (Serial Communication Controller) is used to control two RS-232C ports, one of which drives a power line modem as depicted in Figure 2.1. In the following sections, properties of the power line modem, interfacing and interaction between the SCC and modem will be described. Power Line Zilog 8530 SCC K| RS-232C port Figure 2.1: Bus Interface Unit on Sun 3/50 2.2.1 B e t w e e n m o d e m a n d m o d e m Prototype modems currently available employ frequency shift key (FSK) modulation technique to superimpose data onto a 120 kHz radio frequency (RF) carrier to avoid CHAPTER 2. HARDWARE CONFIGURATION 8 interfering with the 60 Hz power signal. To reduce cost and complexity of the modem, half-duplex communication is provided. A maximum data rate of 14.4 kilo-bit per second (kbps) is provided by the modem. Full-duplex channel is not called for in some communication paradigms. Therefore, half-duplex communication channel would be sufficient. However, the fact that it is a half-duplex modem prohibits the medium access sublayer from using CSMA/CD (Carrier Sense Multiple Access / Collision Detection) protocol for reasons presented later; thus limiting the choice of protocols. Broadband signalling is used for exchanging data between modems. Simultaneous modem transmissions onto the channel can be avoided by using a "listen before talk" or carrier sense protocol. Each modem is equipped with an RF carrier detection logic. Whenever there is signal on the channel, the carrier detection logic is activated. Listening modems will refrain from transmitting until the absence of RF carrier is indicated. The time needed to detect the presence/absence of carrier is about 4 ± 1 / 10 ± 2 milliseconds depending on the noise level! This implies a potential collision may occur if two or more modems decide and try to transmit within 4 milliseconds of one another. After a modem has successfully seized the channel, a special code is broadcasted for the purpose of synchronizing receiving modems. The whole process starting from initial channel seizure until the start of first user data transmission takes about 10 ms. As mentioned before, synchronization has to be established between transmitting CHAPTER 2. HARD WARE CONFIG URATION 9 and receiving modems. The receiving logic has to be reset every time a modem has successfully seized the channel. Failure to do so would result in misinterpretation of received data and hence, meaningless data presented to the upper layer. After the disappearance of signal on the channel, the carrier detection logic remains activated for about 10 ms before shutting off, called the carrier detect linger effect. This implies that, if the time elapsed in between two successive transmissions is less than this carrier detect linger time, signal might be received as meaningless data as the second transmission is mistaken as part of the first one. In addition, to ensure that all transmitted messages be received completely by the receiving moderns, the transmitting modem will continue to transmit a RF carrier for some amount of time after the end of data transmission. This time is called the end-of-message extend time which is about 10 to 15 ms. During this time, the transmitter is in an idle state to allow any remaining data in its transmit buffer to be sent out over the channel. 2.2.2 B e t w e e n m o d e m a n d h o s t The modem interfaces with a host computer via a RS-232C link. Both synchronous and asynchronous data transmission are possible between host and modem. The mo-dem provides clock signals for synchronizing both receive and transmit data. Out of the 25-pin RS-232C standard, 6 pins are used when asynchronous data is exchanged; they are : CHAPTER 2. HARDWARE CONFIGURATION 10 A B (GND) ground reference signal. B A (TxD) data signal directed to host. B B (RxD) data signal directed to modem. C A (RTS) request to send directed to host. C B (CTS) clear to send directed to modem as an response to RTS. C F (CD) indication of RF carrier detected. Two additional signals are needed when synchronous data is exchanged; they are : D B (Txclk) clock signal directed to modem for synchronizing data on BA. D D (Rxclk) clock signal directed to modem for synchronizing data on BB. Since the modem is a half-duplex modem, the mode of operation, transmit or re-ceive, is controlled by the attached host via the used of RTS signal. Coupled with CTS and CD signals provided by the modem, status of the modem as well as that of the power line channel can be determined by the host. The interaction between these various signals can best be described using the timing diagram shown in Figure 2.2. The modem is in transmit mode only when the RTS line is asserted by the host and no RF carrier is detected on the power line. At time B when host has decided to send data onto the power line, RTS is asserted. Upon triggered by the falling edge of RTS, the modem transmits immediately if the carrier detect logic is currently deactivated. CTS is asserted by the modem after the synchronization preamble has been sent. This channel access process generally takes 10 milliseconds (i.e. time difference between C CHAPTER 2. HARDWARE CONFIGURATION 11 and B in Figure 2.2). The modem remains in transmit mode as long as RTS is asserted. Data from TxD is modulated and transmitted onto the power lines. The modem will relinquish channel access when RTS is disasserted and expiry of end-of-message extent period (i.e. time difference between D and E in Figure 2.2), CTS will be disasserted as a result. Once RF carrier is detected, the modem is in receive mode. At time A, CD is asserted as result of detecting the presence of RF carrier on the power lines. Modulated signal coming from the power lines is demodulated and appear on the RxD pin directed to the host. A B C D E i RTS CTS CD RxD TxD Time Figure 2.2: Timing diagram showing interaction of various signals CHAPTER 2. HARDWARE CONFIGURATION 12 2.3 S u m m a r y and Remarks In summary, the power line medium is usable in spite of the potentially noisy back-ground. Acceptable error rate was observed and a fairly decent data rate is proved to be achievable. Special properties of the power line modem, carrier sense protocol, syn-chronization between modems, end-of-message extend period and carrier detect linger effect require special attention when selecting and implementing MAC and LLC pro-tocols. Using a modem which is internally wired up in "listen before talk" mode may not be beneficial to upper layer protocols. This feature is redundant to non-contention medium access sublayer; in particular, since modems should have been controlled to avoid collision by the communication protocol. Extra checking done by the modem simply introduces an overhead each time a modem begins a transmission. On the other hand, the feature is an asset to protocol like CSMA which basically executes a "listen before talk" protocol to provide access to medium for upper level protocol. Most of the required job is done by the modem, therefore, only a "light-weighted" MAC sublayer is required. Synchronization problem between modems can be avoided, evidently, by reducing the number of frequent assertion and release of channel. This in turn favours choosing protocol that allows vast amount of data to be transmitted before releasing the channel. All these issues which affect the decision made on choosing appropriate MAC and LLC protocols which will be discussed in detail in Chapter three. Chapter 3 Access and Link Protocols One of the' important decisions to be made in setting up a LAN is the choice of the medium access protocol. The medium access protocol provides a foundation on which other high level protocols are built. The decision is made difficult by the availability of possible medium access protocols each with its own advantages and disadvantages. Choosing a link level protocol, however, is a relatively easier task because the functions and services provided by this layer have been well-defined. They are quite indepen-dent of the underlying medium and medium access protocol used. Available link level protocol can, therefore, be adopted and tailored to adapt to the environment. This chapter is divided into two parts. A review on various available medium access protocols is included in the first halve of the chapter. The second halve concentrates on the description of selected medium access protocol and its suitability on power line communication is discussed. Modifications made to IEEE 802.2 Logical Link Control (LLC) protocol are also described in the second part of this chapter. 13 CHAPTER 3. ACCESS AND LINK PROTOCOLS 14 3.1 R e v i e w on M e d i u m Access Pro toco ls In view of the available medium access protocols, they can be categorized as con-tention and non-contention. By contention, it means that conflict in simultaneous multiple access to physical medium is resolved by a probabilistic arbitration scheme. For non-contention protocols, the conflict is avoided instead of resolved. Generally, contention protocols have a reputation of simplicity and more efficient use of commu-nication bandwidth; where non-contention protocols tend to be more complicated and use up a portion of the available bandwidth for coordinating access right among various stations. The overhead incurred by the coordination in non-contention protocols will be insignificantly small on a heavily loaded network and under this circumstance they out-perform the contention protocols. 3 . 1 . 1 C o n t e n t i o n p r o t o c o l s The bus topology of the power line medium has limited the choice of protocols. The most commonly used contention medium access protocols on a bus medium are based on CSMA (Carrier Sense Multiple Access) which exercises a carrier sense control trying to avoid simultaneous access to the medium. Collisions can still occur and therefore a collision resolution scheme is required which constitutes a major part of the protocol. Effort is also made to avoid simultaneous access, non-persistent and p-persistent are some of the proposed arbitration schemes to serve for this purpose. Further enhance-CHAPTER 3. ACCESS AND LINK PROTOCOLS 15 ment to a pure CSMA protocol is the introduction of ability to monitor the physical medium during transmission. This is commonly known as CSMA/CD (Carrier Sense Multiple Access / Collision Detection) which is the medium access protocol employed by the widely accepted Ethernet LAN. Contention protocols are attractive for their simplicity, however, poor performance is observed when network loading is high; and in the case of CSMA/CD protocol, full-duplex hardware and channel are called for. This requirement adds cost and complexity to the network interface. Having exposed the facts about contention protocols, it is decided that contention protocols are not suitable for power line communication for the following reasons. First of all, consider the 4 ms vulnerable period associated with the modem when potential collisions might happen. Assume that the rate of accessing the physical medium follows Poisson distribution. The probability (Pn(0) °f having exactly n access during a 4ms time interval (t) is given by n! where A is the rate of medium access. A collision happens when two or more access are performed during interval t. The probability (Pn>i(t)) is given by Pn>1(t) = 1-P0(t)-P1(t) = 1 - (1 + t\)e~tx Table 3.1 gives the values of Pn>i[t) using different A values and also compares with CHAPTER 3. ACCESS AND LINK PROTOCOLS 16 the probability P^>x(t) obtained when pure CSMA is applied to a 1km cable with a propagation delay of 5 microseconds (t). It can be seen that even for small A value, the probability of collision is relatively high. For instance, when A = 20, about 20% of the frames transmitted may be garbled due to collisions. Because of the pure CSMA protocol used, these collisions would not be detected until timeouts have occurred. This can cause poor delay and throughput performance at the user level. A (access/sec) Pn>i(t) 10 0.0615 0.0 20 0.1912 0.0 30 0.3373 0.0 40 0.475 0.0 50 0.594 0.0 60 0.6916 0.0 70 0.7689 0.0 80 0.8288 0.0 90 0.8743 0.0 100 0.9084 0.0 1000 1.0 0.000012 Table 3.1: Relationship between A value and collision prob. The limited data rate provided by the power line medium also leads to easy sat-uration of channel. To study this effect, the network is modelled using a M/M/l queuing system. Assume that transmission requests at a station are generated at A frames/second and the service rate is \i frames/second. For a data rate of 14.4 kbps and a frame size of 128 bytes, the value of fi would be 14.0625 frames/sec. The mean CHAPTER 3. ACCESS AND LINK PROTOCOLS 17 number of transmission requests in the system is given by where p = .^ To achieve an equilibrium such that the value of N will not grow un-bounded, the condition A < (i must be satisfied. However, with a small value of ft, the network is saturated rather easily. High network utilization is a direct consequence of this easy saturation property. Study [MCD084] shows that the performance of a CSMA/CD network degrades considerably if network utilization is higher than 40%. In conclusion, contention medium access methods are inappropriate for power line com-munication because of i) a rather long vulnerable period in which unawared collisions can happen ; and ii) the easy saturation property of the medium caused by a low-to-medium data rate presents an undesirable environment for contention protocols. 3 . - 1 . 2 N o n - c o n t e n t i o n p r o t o c o l s For a network that can be saturated with data easily, it is sensible to adopt a non-contention medium access protocol since it performs much better than a contention protocol under heavy workload. A number of non-contention protocols have been proposed. They differ from one another by the way of access right coordination among various network participants. They are reviewed in the next few paragraphs. Protocols proposed by Scholl [SCH076] and Chlamtac [CHLA79] are similar. Both of them are based on a bit-map protocol which controls the access right among stations CHAPTER 3. ACCESS AND. LINK PROTOCOLS 18 by means of bit-slot. Medium access right is granted to each station in a round robin fashion. A station can indicate its intention to transmit data by inserting an 1 into the bit slot when it comes to its turn to transmit. Data can then follow. Stations with no data to send can just let its bit slot to go idle, so that the next station can gain the medium access right after a 1-bit delay. This kind of protocols require an establishment of tight synchronization among stations. A single put-of-sync station will misbehave and ruin the harmony of the network. As seen in the last chapter, synchronization between modems is by itself a problem under noisy environment. Furthermore, a static network with implicit ordering is required since every station has to know exactly how many stations are in the network and its position in the network. Therefore this non-contention protocol is not suitable to be used in the power line LAN. Sterling [STER82] has proposed a scheme to avoid contention by separating the data transfer function from the bus access function. His approach is to provide two channels for concurrent data and signal exchanges. The channel used for signalling is called the C-path while the channel used for data exchange is called the D-path. Each station can be in one of three states: Slave, Monitor and Master. There is only one Master station in the network at any one time. The Master station has control over the D-path. It also has the right to change the state of any station from Monitor to Slave or vice versa. Data exchange can only be done between Master and Slave stations under the supervision of the Master station. A station can enter the Master CHAPTER 3. ACCESS AND LINK PROTOCOLS 19 state only by execution of the scheme. The scheme requires all stations to keep two state variables: BCNT and QCNT representing the total number of bus access requests pending in the network and the number of pending network bus requests when request is made by the station respectively. Value of QCNT is irrelevant for a station which is not actively waiting for bus access. Station will cast out a signal called Bus Access Request (BAR) onto the C-path to broadcast it intention to access the D-path, QCNT is assigned the value of BCNT and access right is granted when QCNT becomes zero. Upon receiving BAR, all stations have to increment the value of their BCNT by 1. BCNT and QCNT values are decremented upon reception of EOF signal from the C-path indicating the current Master has relinquished the ownership of D-path. The success of this arbitration scheme relies on the following assumptions : • arrival rate of BAR follows Poisson distribution, and the probability of having two or more BAR within a sufficiently small time interval approaches zero. • infinite bandwidth is available in C-path and the distance between two stations is zero. • BAR in form of a zero width, finite energy signal is transmitted on the C-path to assert request for D-path. Error recovery relies on the ability to detect collision while transmitting. The scheme proposed is simple and eliminates the needs for fruitless-wait for a turn to transmit. CHAPTER 3. ACCESS AND LINK PROTOCOLS 20 Unfortunately, the assumptions made are not realistic especially for power line com-munication. First of all, a separate C- and D- path cannot be provided by the modem. The process of sending out BAR is time-consuming due to the 10ms channel access time and is vulnerable to collision because of the 4 milliseconds vulnerable period. The lack of a full-duplex communication channel would make the proposed error recovery impossible to implement. Instead of using time or by keeping track of the number of bus access requests on the network, access right can be regulated by circulating a pre-determined bit pattern called a token. The IEEE 802 committee has standardized the token bus protocol (IEEE 802.4) to be used with broadband systems at 1, 5 or 10 Mbps. Since a non-probabilistic approach is taken, as oppose to CSMA/CD, an upper bound to the amount of time wait before each network participant can transmit can be determined. It is particularly important for time-critical control-oriented applications. Each network participant is granted the right to transmit in a round robin fashion by circulating the token. The token passing path is commonly known as a. logical ring. The protocol also allows new stations to dynamically join in and exit from the logical ring. This is a very desirable feature especially for power line communication. The abundant supply of power outlets gives users an easy access to the network, a highly portable and dynamic system can be formed easily with the aid of this feature. This protocol is notorious for its complexity which is stemmed mainly from its decentralize nature. No "global view" of the network CHAPTER 3. ACCESS AND LINK PROTOCOLS 21 is kept by any one single station introduces extra overhead in keeping state information consistent among stations. The potentially noisy and error-prone medium adds more complexity to worsen the situation. Recovery procedure must be executed in order to reinstall state consistency, this process is usually slow and non-deterministic. Consider the following situation. In the IEEE 802.4 protocol, a station is responsible for delivery of token to the next intended station. This is done by monitoring the channel after it has sent out the token. By detecting the presence of electrical signal on the channel, it concludes that the next station has received it. The electrical signal does not necessarily have to be in form of a valid MAC frame. Therefore, random noise on the medium can lead the station to a false conclusion that the intended station has received a token which was garbled during transmission and discarded by the receiving station. Under this situation, the token would have been lost forever unless some recovery measure is taken. In the IEEE 802.4 protocol, every station has to the keep a timer called channel idle timer which is reset every time an electrical signal is received. If the channel idle timer of a station expires, it sends out a claim token frame broadcasting its intention to re-create a new token. To avoid re-creation of multiple tokens, the claim token frame is sent out for a specific number of times with some time interval in between. A token is re-created by a station only when no signal is detected on the channel during the recovery period. This lengthy process is the most common error recovery process expected to execute when the error statistics of the network gets worse. Other CHAPTER 3. ACCESS AND LINK PROTOCOLS 22 functions, e.g. station joining and station excluding from the logical ring, suffer from similar problem which arises from the decentralize nature of the protocol. As shown in the above paragraph, distributed non-contention protocol has a poten-tial state inconsistence problem. To reinstall state consistency, non-deterministic and time-consuming algorithm has to be executed. The number of such reinstallations is expected to grow as the error statistics of the physical medium gets worse. A central-ized non-contention protocol will be a remedy to this problem with a drawback of being less reliable than a distributed system. Depending on the end applications, the use of a centralized medium access protocol would be sufficient. Resource sharing and security monitoring are examples of applications Which have to rely on the aliveness of a single server/monitor. The non-contention hub polling scheme adopted Will be described in Section 3.3. 3.2 L i n k Leve l P r o t o c o l The function of a link level protocol is to provide the following services : flow control, error control, sequence control and setting up / clearing point-to-point or broadcasting communications. In the [IEEE802.2] LLC protocol, the services are made accessible to the upper layer by defining a set of primitives to be operated on a set of Service Access Points (SAPs). The design philosophy of LLC follows closely to that of HDLC (High-level Data Link Control). As a matter of fact, the format of the control field CHAPTER 3. ACCESS AND LINK PROTOCOLS 23 used in a LLC PDU (Protocol Data Unit) is identical to that of HDLC's. By assuming that the underlying physical medium is relatively fast and reliable, a retransmit N continuous automatic repeat request (ARQ) is adopted as a technique for sequencing and error control. This scheme discards all PDUs with unexpected sequence number. All outstanding PDUs are retransmitted upon receiving a retransmit request. It introduces a certain amount of inefficiency because once an out-of-sequence PDU is received, all subsequent PDUs will be discarded until the PDU with expected sequence number is received. For hostile communication medium like the power lines, the overhead incurred by this technique will be substantial. A more appropriate technique to consider would be a selective retransmit ARQ in which all correctly received PDUs are buffered. PDUs are retransmitted only when lost. The major drawbacks to this technique are the buffer storage requirement and the complexity of the protocol. However, for a slow and erroneous channel provided by the power lines, it is worthwhile to implement a more sophisticated protocol to compensate for the slowness of the medium and to utilize the channel more efficiently. To further enhance the selective retransmission technique, requests for retransmission of multiple PDUs should be allowed in a single retransmission request PDU. The current PDU format recommended by IEEE 802 committee lacks the syntax and semantics for requesting the retransmission of several missing PDUs. This is particularly useful in a situation when two modems are out of sync and causes the reception of multiple PDUs as meaningless signal. CHAPTER 3. ACCESS AND LINK PROTOCOLS 24 3.3 Desc r ip t i on of The M e d i u m Access C o n t r o l P r o -toco l To simplify the logic of the MAC protocol and for more efficient utilization of the channel bandwidth, a centralized polling scheme is adopted as the MAC protocol. There are two types of polling schemes, roll call and hub polling. The roll call scheme will be very inefficient because a master station has to poll every slave station and every slave station has to reply to the poll even though it has no pending message to send. If the slave station knows the address of the following station on the poll path, the response to the master is really not necessary. Hub polling takes advantage of the fact that every station knows the address of its successor on the poll path so that the poll can be relayed by slave stations along the poll path. Treating the power line medium as a multidrop line and applying technique used commonly for terminal control, the scheme provides all the advantages of a centralized system, thus, reducing the amount of state information kept by each individual station. This reduces the probability of having state inconsistence among stations which in turns reduces the number of execution of the error recovery algorithm. 3 . 3 . 1 H u b p o l l i n g s c h e m e A hub polling scheme is very similar to a token bus protocol. A special bit pattern called POLL is passed around the logical ring to regulate usage of the bus among CHAPTER 3. ACCESS AND LINK PROTOCOLS 25 members of the logical ring. A network using hub polling scheme consists of one primary station and any number of secondary stations. The primary station differs from a secondary station mainly by the information maintained which in turn affects the ability of a station. The main function of a primary station is to maintain and manage the network. This includes inviting new stations to join in and to restore the "broken" logical ring when a station exits from the ring without notice. State information kept by the primary station are : • global network image - information about the configuration of the logical ring and information about each individual member. Typically, it contains information of how stations are linked to each other to form the ring and how many times a particular station has failed to respond to a POLL. v . • statiori-received^poll - address of last station that is known to have successfully received a POLL. This variable is updated by information on POLL and DATA frames received when monitoring the traffic on the channel. • expected receiver - deduced from the global network image and the variable sta-tionjreceivedjpoll. It defines the station which is expected to receive the POLL as seen by the primary station. Every station records the following state information: CHAPTER 3. ACCESS AND LINK PROTOCOLS 26 • current address - the current address of the station. This address is dynamically assigned by the primary station when station is invited to join the ring. For primary station, the value to this variable is fixed. • successor address - the address of the following station on the logical ring. • current session - contains the value associated with the current polling round. This value is changed every time the POLL has finished circulating the logical ring once. The protocol is made up of two elementary phases and three protocols. The two phases are : • Data Transfer - A POLL is passed from one station of the logical ring to another. Data transfer begins upon reception of the POLL, and is followed by the relay of the POLL to the station's successor. • Invitation - New stations are invited to join the network in this phase. All sec-ondary stations of the ring become passive. The primary and new stations are the only active participants of this phase. Three different protocols are used to govern operation for normal data exchange, invitation to new station and error recovery, respectively. CHAPTER 3. ACCESS AND LINK PROTOCOLS 27 During the invitation phase, invitation protocol is executed by both the primary and new secondary stations which have not yet joined the logical ring. Normal data exchange protocol is executed by all stations in the ring during data transfer phase. Error recovery protocol is executed by the primary station when error situation arises. D A D A T A S A U S E R D A T A 7 8 0 1 5 1 6 2 3 2 4 B i t 0 - 7 : d e s t i n a t i o n a d d r e s s B i t 8 : u n u s e d B i t 9 - 1 5 : D A T A f r a m e t y p e i d e n t i f i e r b i t 1 6 - 2 3 : s o u r c e a d d r e s s B i t 2 4 - . : u s e r d a t a f i e l d D A P O L L 5-5- 15 B i t 0 - 7 : d e s t i n a t i o n a d d r e s s B i t 8 : s e s s i o n b i t B i t 9 - 1 5 : P O L L f r a m e t y p e i d e n t i f i e r D A S E T S C O R 7 8 9 S U C C E S S O R 1 5 1 6 2 3 B i t O - 7 : d e s t i n a t i o n a d d r e s s B i t 8 : s e s s i o n b i t B i t 9 - 1 5 : S E T S C O R f r a m e t y p e i d e n t i f i e r B i t 1 6 - 2 3 : n e w s u c c e s s o r ' s a d d r e s s Figure 3.1: Frames used during the data transfer phase and error recovery (CRC excluded) 3 . 3 . 2 D a t a t r a n s f e r p h a s e In normal data exchange protocol, the primary and secondary stations will be in a state called P JNORMAL and S JNORMAL respectively. There is no state transition in this protocol. The primary station starts a new polling round by first toggling the CHAPTER 3. ACCESS AND LINK PROTOCOLS 28 binary value of its current session state variable. The function of this variable is to distinguish a POLL sent in a polling round from those sent in the next or previous polling rounds. Therefore, a binary value would be sufficient. This value is then copied onto the session bit of the POLL frame (see Figure 3.1) and with DA field filled with the address of. primary station's successor, the frame is sent off to grant medium access to its successor. Upon reception of a POLL frame, a secondary station compares the destination address on the POLL with its current address. It also checks the value of the session bit on the POLL against its session value. If the addresses match and the session values are different, then the POLL is destinated for this station and it is different from the POLL received from the last polling round. The session variable of the station is updated to the current session given on the POLL. Then the station starts transmitting its pending messages. In order to prevent any one station from hogging the system, a timer called POLL holding timer is set once station starts transmitting. A station is required to relinquish the access right when either the POLL holding timer expires or all pending messages have been transmitted. At the end of the data transfer, a POLL frame is transmitted with the destination address field containing the address of the station's successor. The data transfer phase (i.e. polling round) will be terminated after pending mes-sages have been sent following the reception of POLL frame by the primary station. CHAPTER 3. ACCESS AND LINK PROTOCOLS 29 At this time, a state change in the primary station occurs, which leads it into the invitation phase before another POLL (of the next polling round) is sent out. 3.3.3 E r r o r r e c o v e r y m e c h a n i s m During the data transfer phase, a transmitted POLL may be lost. This situation is detected by the primary station when the channel has been idled for certain amount of time. The primary station keeps track of the activeness of the channel by means of a timer called channel idle timer. This timer is reset upon detection of signal (data or noise) on the channel. The expiry of the timer causes the execution of an error recovery protocol. If the POLL is lost or garbled during transmission, the error is recovered easily by the primary station by retransmitting the POLL. Unlike the IEEE 802.4, a station in the polling scheme, is not responsible for the reliable delivery of token. Therefore, the primary station has to retransmit the POLL on a station's behalf if the POLL is lost. The question now becomes which station should the POLL be sent to. The state variable station jreceived-poll and the global network image kept by the primary station are consulted to determine the expected receiver. The primary station assumes that a POLL has been sent out by the station^receivedjpoll and the expected receiver has failed to respond to it. If the expected receiver is found to be the primary station itself, then it just goes on with the data transfer protocol as if a POLL has been received. Otherwise, the primary station has to "remember" that this station has failed CHAPTER 3. ACCESS AND LINK PROTOCOLS 30 to respond to a POLL. This is done by marking the station "idle" in the global image of the network, provided that number of consecutive times that this expected receiver is idle is less than a threshold value, the station following the expected receiver on the logical ring is determined and a POLL is sent out to it. The stationereceived.poll state variable will then be updated as the successor's address of the expected receiver. Again, a POLL frame is not sent if the successor's address of the expected receiver is found to be the primary station's address. Primary station will act as if a POLL is received. If the discontinuity of data transfer phase is caused by the "broken ring" effect, i.e. inability of a ring member to respond to a POLL, usually due to the station's failure or member leaving the ring without notice. In order to restore the "broken ring", the "aliveness" of all members of the ring must be monitored and maintained by the primary station. It is achieved by the introduction of an idle counter, one for each ring member in the global image of the network. This counter keeps track of the consecutive number of times that an associated station has failed to respond to a POLL. The counter for a particular station is reset under one of two conditions which occur during the execution of data transfer protocol: (i) when a DATA frame with its source address equals to the address of that station is received by the primary station, (ii) when the destination address of a received POLL frame equals to the station's successor. In both cases, the station^receive.poll state variable will be set to be the address of the most recent non-idle station. Counters associated with stations whose addresses are inclusively CHAPTER 3. ACCESS AND LINK PROTOCOLS 31 between the old value of station.receive.poll and the new value of station.receive.poll are also reset. A station is considered to be faulty when its associated counter reaches a certain threshold value. Having determined the faulty station, primary station will change its state to P.SETS where a SETSCOR frame is sent to the predecessor of the faulty station. A secondary station upon receiving the SETSCOR frame will change the value of its successor address state variable to the one given on the received frame and sends out a POLL to its new successor. Again, if the primary station happens to be the predecessor of the faulty station, no frame needs to be sent. It is possible for the intended receiver of the SETSCOR frame to be faulty as well. The conclusion is drawn after the SETSCOR has been sent out for a number of times and no signal can be detected on the channel after every transmission of SETSCOR. The exact number of times SETSCOR frames sent is based on the value of the idle counter of the intended station. This algorithm is executed continuously until normal traffic is detected on the channel or in the worst case, primary station becomes the intended receiver of the SETSCOR. The above recovery mechanism relies on the accuracy of variable station.received.poll. The primary station may keep an inaccurate account of which station has last got the POLL if it fails to receive some POLL or DATA frames which were successfully transmitted to the received station. The inconsistency may result in sending POLL to a station more than once in a single polling round and grants the CHAPTER 3. ACCESS AND LINK PROTOCOLS 32 bus access to a station for more than one time per poll round. The value of "session bit" on the POLL frame and the current session value kept by each station guarantees granting of one bus access right to any single station in one polling round. 3 . 3 . 4 I n v i t a t i o n p h a s e Invitation phase is the start-up phase when the primary station is the only station in the network. Invitation phase is also entered after the completion of one polling round provided that the number of stations in the ring is less than a threshold value. All secondary stations which have already joined the ring will ignore frames sent in this phase. Two goals are to be achieved in this phase: (i) invite new stations to join in and, (ii) dynamically assign unique addresses to all newly joined stations. Algorithms to achieve these goals are woven together in a 5-way handshaking protocol as shown in Figure 3.2. The frames used in this protocol are shown in Figure 3.3. As usual, all the frames are ended with a 2-byte Cyclic Redundancy Code (CRC). PRIMARY . NSW STATION Figure 3.2: The 5-way handshake protocol CHAPTER 3. ACCESS AND LINK PROTOCOLS 33 In this protocol, no station is assumed to have a static address besides the primary station. Therefore, whenever a new station wants to join the ring, a random 16-bit address called the mailing address is generated so that primary station can use it to reference a station before a permanent address is assigned. At the start of invitation phase, an I N V I T E frame is broadcasted by the primary station to invite new sta-tions to join the ring. The INVITE frame contains two bytes, giving the address of a primary station and also the window number. The window number is used to reduce the probability of collision when more than one station is ready to join the ring. The 16-bit address space is partitioned into a number of subspaces called windows. Each subspace is identified by a number called the window number. A new station responds only to the INVITE frame when it's mailing address lies in the window specified by the frame. A 4-bit window value is used in this protocol. In fact, the low order 4 bit of the mailing address defines the address subspace in which the mailing address lies. The address space can then be partitioned into a maximum of 16 windows. This is, by no means, the exact number of windows to be partitioned into during an implementation. This should be treated as an implementation parameter which can be tuned to suit the networking needs. A J O I N frame is sent out by new station in response to an INVITE frame. The semantics of the 16-bit mailing address included in the JOIN frame requires some explanations. Since window number has already agreed between the new station and the primary station, the low order 4 bits have lost their significance. Therefore, it CHAPTER 3. ACCESS AND LINK PROTOCOLS 34 can be used for other purposes. The higher order 2 bits will take on some random value to add more randomness to the mailing address. The lower order 2 bits are treated as a sequence number recording the number of times a JOIN frame has been sent by the station using the same mailing address. This is useful, as explained later, in de-tecting duplicate mailing addresses. The primary station acknowledges the reception of JOIN frame by sending.a P_VERF frame. A new (unused) permanent address is drawn from the address pool managed by the primary station and is included in the P_VERF frame. Mailing address is also included in the P_VERF frame for addressing purpose. The S_VERF frame which contains the newly assigned address is sent to the primary station upon reception of P_VERF to acknowledge the fact that the newly assigned address has been received. The invitation phase is made up of a series of the above interactions and finally terminated by sending the SETPSEQ frame for a few times. A SETPSEQ frame is sent by the primary station defining the "position" of newly joined stations in the ring. This is done by including a list of addresses on the frame, the ordering of these addresses defines the position of the corresponding station in the ring. All new stations which have been assigned a new address upon receiving this frame will search for its address on the list. If its address is found then it sets its successor's variable to the address which precedes its assigned address on the list. Otherwise, it considers the attempt to join as a failure, the invitation phase protocol has to be reexecuted by the station again in order to join the ring. CHAPTER 3. ACCESS AND LINK PROTOCOLS 35 P A J O I N M A I L I N G A D D R E S S 0 B i t O 7 8 - 7 : p r i m a r y ' s 9 1 5 a d d r e s s 1 6 3 1 B i t 8 : u n u s e d B i t 9 - 1 5 : J O I N f r a m e t y p e i d e n t i f i e r B i t 1 6 - 3 1 : r a n d o m m a i l i n g a d d r e s s P A I N V I T E W I N D O W # 7 8 9 1 5 1 6 2 3 B i t 0 - 7 : p r i m a r y ' s a d d r e s s B i t 8 : u n u s e d B i t 9 - 1 5 : I N V I T E f r a m e t y p e i d e n t i f i e r B i t 1 6 - 2 3 : w i n d o w n u m b e r o p e n e d f o r j o i n i n g P A S _ V E R F S A 7 8 9 1 5 1 6 2 3 B i t O - 7 : p r i m a r y ' s a d d r e s s B i t 8 : u n u s e d B i t 9 - 1 5 : S _ V E R F f r a m e t y p e i d e n t i f i e r B i t 1 6 - 2 3 : s o u r c e a d d r e s s N E W A D D R P V E R F M A I L I N G A D D R E S S 7 8 9 1 5 1 6 3 1 B i t O - 7 : n e w l y a s s i g n e d a d d r e s s B i t 8 : u n u s e d B i t 9 - 1 5 : P _ V E R F f r a m e t y p e i d e n t i f i e r B i t 1 6 - 3 1 : m a i l i n g a d d r e s s P A S E T P S E Q O L D A D D R N E W A D D R 1 N E W A D D R N 7 8 9 1 5 1 6 2 3 2 4 3 1 B i t O - 7 : p r i m a r y ' s a d d r e s s B i t 8 : c u r r e n t s e s s i o n B i t 9 - 1 5 : S E T P S E Q f r a m e t y p e i d e n t i f i e r B i t 1 6 - 2 3 : o l d s u c c e s s o r o f P A B i t 2 4 - 3 1 : p r e d e c e s s o r o f O L D A D D R B i t 3 2 - 3 9 : p r e d e c e s s o r o f N E W A D D R 1 N E W A D D R N p r e d e c e s s o r o f N E W A D D R N - 1 , n e w s u c c e s s o r o f P A Figure 3.3: Frames used during the invitation phase(CRC excluded) CHAPTER 3. ACCESS AND LINK PROTOCOLS 36 After an INVITE frame has been broadcasted, it is possible that more than one station would have responded to the same frame. An arbitration scheme is obviously required to resolve contention between responding stations. In the invitation protocol, a new station would wait a random amount of time before sending out the JOIN frame. A timer is started after the JOIN frame has been sent. If P_VERF is received before the timer timeouts, it waits for SETPSEQ after sending S_VERF. The timer timeouts if either P_VERF or JOIN has been garbled or collided. It is also possible that the primary station has detected duplicate mailing address and refrained from sending a P-VERF. In any case, a new station will just "toss a coin" (generate a random binary value) to determine whether it should retransmit the JOIN and continue executing the protocol. The station will be in a state of passively monitoring the channel if it decides not to retransmit the JOIN frame. This station can still be able to become a member of the ring if timeout was caused by a garbled PJVERF frame. In this case, the primary station should have retransmitted the P_VERF when no S_VERF is received after certain amount of time has elapsed. The reception of P_VERF will bring the new station back in the state where SETPSEQ is expected. A more complicated situation arises if the random mailing address is not unique. A direct consequence is the assignment of non-unique permanent addresses to new stations. To deal with this situation, a few measures are taken by both the new stations and the primary station. As mentioned before, the low order 4 bits of a mailing address CHAPTER 3. ACCESS AND LINK PROTOCOLS 37 is used to define the window number value. 2 bits also used to add randomness to the mailing address after INVITE has been received. The remaining two bits are used as a sequence number which may starts at either 0 or 1, to be determined randomly by the new station. This sequence number is incremented every time a JOIN frame is sent. Primary will "remember" the sequence number when a JOIN is received. If a JOIN is received with sequence number associated with the same mailing address is equal or less than the one previously received, the primary station will mark the mailing address as invalid. Any further reception of JOIN from the same mailing address is ignored by the primary station. If P_VERF has been sent out before the detection of duplicate mailing address, the primary station can still prevent stations with invalid mailing addresses to join the ring by excluding the assigned address from the SETPSEQ which will be sent out at the end of the invitation phase. New stations can also detect the non-uniqueness of its own mailing address by monitoring the medium. Station with duplicate mailing address can learn that when a JOIN frame with identical mailing address is received, or a P_VERF frame is received with sequence number differs from the one it has just sent. In any case, a new station regenerates a new mailing address when it has detected the non-uniqueness of its mailing address and wait for subsequent INVITE frames in order to join the ring. CHAPTER 3. ACCESS AND LINK PROTOCOLS 38 3 . 3 . 5 M o d i f i e d l o g i c a l l i n k c o n t r o l A modified IEEE 802.2 standard LLC protocol is adopted as the link level protocol for the power line LAN. The functional and the set of primitives provided by the LLC sublayer are well-defined in the IEEE protocol. This enables a clear cut separation between layers in the communication protocol hierarchy. In spite of the great effort put in by the IEEE 802 committee to isolate the function of LLC sublayer from that of the MAC sublayer and the physical medium, LLC sublayer is not totally independent of the underlying layers. Some characteristics of the physical medium must be realized by the LLC to make efficiency use of the resource available. IEEE 802.2 LLC standard has defined two types of operations: • Type I Connectionless. "Datagram',-like service. Unreliable delivery of user information is the characteristic of this service. No state information is kept, hence the lack of error and sequence control. • Type II Connection-Oriented. "Virtual circuit"-like service. User data is ex-changed through the use of connection. Reliable delivery of user data with se-quence and flow control is provided by this service. There are two classes of LLC defined by the IEEE standard. Class I LLC provides only Type I service to its upper layer users, whereas, Class II LLC provides both Type I and Type II services to its upper layer users. Both services provided by LLC are CHAPTER 3. ACCESS AND LINK PROTOCOLS 39 made accessible through a set of Service Access Points (SAPs). To provide upper layer protocol with a full service, a class II LLC is chosen to be im-plemented. Type.I connectionless service is simple and straight forward. Therefore, the IEEE standard is adopted literally without modification. The more extensive Type II service offers error, sequence and flow control. Since it is a connection-oriented service, "connection" has to be established before any user information can be exchanged. Flow controls between peers LLC connections and between LLC and its upper layer protocols has to be exercised. Both peer-to-peef and across layer flow controls are done through the use of a window mechanism. A static size window mechanism is used to regulate the amount of information flow between entities. The link set-up, termination and reset procedures are identical to those recommended by the IEEE 802.2 standard. For error and sequence control, the IEEE 802.2 recommends the "retransmit N" technique where all outstanding (i.e. unacknowledged) protocol data units (PDU) are retransmit-ted whenever an ARQ in form of a R E J PDU is received or when acknowledge timer expires. No buffering of out-of-sequence PDUs is done on the receiving end of a LLC connection. This technique works well if error only occurs occasionally and the window size is small. The effective data throughput for the connection is greatly reduced as the error statistics of the physical medium becomes worse. A "selective retransmis-sion" technique may be more appropriate to be used with the power line medium. The HDL C protocol issued by International Organization for Standardization (ISO) and CHAPTER 3. ACCESS AND LINK PROTOCOLS 40 Advanced Data Communication Control Procedures (ADCCP) issued by the American National Standards Institute (ANSI) allow the use of selective REJECT PDU to force the retransmission of expected PDU. It can be easily seen that the syntax of the PDU has limited it to request for retransmission of one lost PDU only, one lost PDU. first bit deliver to/from M A C sublayer 0 8 15 DSAP SSAP lOxxOOOO P F N ( r ) 0 N ( r v ) ^ ^ ^ ^ ^ S-PDTI format 0 8 1 DSAP SSAP 0 N(s) P F N ( r ) 0 N ( r v ) T - P D U header format Figure 3.4: Figure showing S- and I- PDU format As an enhancement to the IEEE 802.2 protocol, "selective retransmission" is replac-ing the "retransmit N" error and sequence control technique. This should reduce the number of unnecessary retransmissions. A further enhancement to the protocol is the modification made to the format of the Supervisory and Information PDUs (Figure 3 . 4 ) . CHAPTER 3. ACCESS AND LINK PROTOCOLS 41 Since Unnumbered PDUs do not carry any information about the state of the receiving end of the LLC connection, the format of U-PDU can remain unchanged. This modi-fication enables the request for retransmission of multiple PDUs in one single request PDU. Consider the following communication scenario when two power line modems are out of sync. Several consecutive PDUs will be lost. There are two ways that LLC will find out that there are PDUs missing. One way is when an out-of-sequence PDU arrives at the receiving LLC. If the expected sequence number is V(r) and the sequence number of the first out-of-sequence PDU is V(oos), PDU(s) with sequence number V(r) to V(oos)-l is/are lost. In this case the receiving end can count the number of missing PDUs and attaches this information, call it N(rv), onto the R E J PDU together with the usual fields recommended by the IEEE 802.2 protocol., The LLC entity having received the REJ PDU should interpret the PDU as "retransmit N(rv) data PDU(s) starting from N(r)". Another way of detecting lost frames is when acknowledge timer expires. An R R PDU is transmitted to "poll" (with P-bit set) the receiving end for its receiving state. The receiving end can respond to this "poll" with I-PDU or one of RR and RNR depending on the status of the host station with F-bit set. If the N(rv) value is non-zero then N(rv) data PDUs are retransmitted. If the N(rv) value is equal to zero, A L L outstanding data PDUs are retransmitted. Having included this extra byte of information, throughput performance can be improved since retransmission of several data PDUs can be requested with one PDU which would otherwise requires CHAPTER 3. ACCESS AND LINK PROTOCOLS several request PD Us to accomplish the same task. Chapter 4 Implementation Details Both LLC and MAC sublayers are implemented on Sun workstation model 3/50 running SUN UNIX release 3.2. Both sublayers reside in the kernel of a SUN UNIX operating system. The MAC sublayer, being the coordinator of the access right to the physical medium, should be placed at a level closest to the hardware. Failure to do so would result in delay in processing hardware signal. For a better control over the hardware, it is decided to put the MAC sublayer into the kernel. Decision of putting LLC sublayer into the kernel might be a controversy one. LLC sublayer does not have to be kernel-resident. Service requests to the LLC sublayer are not as frequent as that to the MAC sublayer. However, large amount of data will pass through the MAC/LLC interface. If the two sublayers reside in two different address spaces, communication between the two entities can only be done through the use of interprocess communication or via system calls. In any case, data copying and queuing has to be done. If both sublayers reside in the kernel space, interfacing can be done by procedure calls and eliminates overheads 43 CHAPTER 4. IMPLEMENTATION DETAILS 44 incurred by interprocess communication or system calls. The software implementation of the Zilog driver, MAC sublayer and LLC sublayer are coded in language C and are responsible for 800, 2000 and 3000 lines of documented C programs respectively. This chapter exposes the implementation details regarding the development of LLC and MAC sublayers in the UNIX kernel. Interfacing, especially between LLC and its high level user, can be found at later sections of this chapter. 4.1 A G l o b a l V i e w Both MAC and LLC sublayers are implemented as event-driven finite-state machines. The interactions between this two sublayers and the structural organisation of the implementation are outlined in Figure 4.1. The writing of the Zilog 8530 SCO driver L L C p r o c e d u r e c a l l s , — K e r n e l s p a c e L o g i c a l L i n k C o n t r o l p r o c e d u r e c a l l s M e d i u m A c c e s s C o n t r o l p r o c e d u r e X | c a l l s ' — i n t e r r u p t s Z i l o g 8 5 3 0 d r i v e r S e r v i c e A c c e s s P o i n t c o n t r o l i n t e r r u p t s I m o d e m 1 p Z i l o g 8 5 3 0 1 1 R S - 2 3 2 C Figure 4.1: Figural representation of LLC and MAC implementation CHAPTER 4. IMPLEMENTATION DETAILS 45 constitutes a major effort in the implementation of the physical layer. The SCC driver is responsible for the receiving and transmitting of MAC frames to and from the power line modem through the RS-232C port. Communications between the SCC and the MAC implementation are through the use of procedure calls and interrupts. Interactions between the LLC and MAC sublayers are through the use of procedure calls. In fact, there are only two such procedure calls MA J) ATA.indication and MA JDATA.request as recommended by the IEEE 802 standard. The concept of SAP through which LLC services can be accessed is implemented using the UNIX socket abstraction. Service requests and interface calls are mapped onto the set of socket manipulation system calls. 4.2 Imp lementa t ion of the P h y s i c a l Layer Part of the implementation of the physical layer is done in software. A driver is written to control the Zilog 8530 SCC which in turns drives the RS-232C port to which power line modem is attached. In addition to transmitting and receiving MAC frames to and from the hardware, the driver also aids the MAC sublayer in determining the channel idle event. The hardware used in the physical layer can be found in Chapter 2, description of the SCC driver is included in the following subsection. CHAPTER 4. IMPLEMENTATION DETAILS 46 4 . 2 . 1 Z i l o g 8 5 3 0 S C C d r i v e r The RS-232C ports of a Sun workstation are normally used to support teletype (TTY) terminals. Low speed asynchronous communication is done between tty terminal and the Sun workstation. A driver is basically a collection of interrupt service routines. It processes the hardware signal generated by the SCC in order to provide a convenient interface between higher level software and the SCC hardware. Besides of supporting asynchronous communication, the versatile SCC is capable of encoding data in vari-ous forms, checking for validity of an incoming data is done by checking the parity or the cyclic redundancy code(CRC). It can also recognise frames which conform to common standards e.g. the bit-oriented Synchronous Data Link Control (SDLC) and the character-oriented Binary Synchronous Communication (BSC) protocol. It also alleviates tedious and routine tasks like CRC generation and checking, which would, otherwise, be done inefficiently in software. For the purpose of interfacing with a modem which provides both transmit and receive data clock signals and taking advantage of the features offered by the SCC, synchronous communication method is employed. The SCC is set up to operate in SDLC mode which means the driver will recognise frames with SDLC protocol format as shown in Figure 4.2. In fact, the frame formats shown in the previous chapter are designed to be compatible with the SCC. A frame, as seen by the SCC, is delimited CHAPTER 4. IMPLEMENTATION DETAILS 47 by flags with bit pattern 01111110. Data transparency is achieved by bit stuffing at transmitting site and bit destuffing at receiving site. This is done automatically by the SCC. CRC is checked and generated using the CRC-CCITT generating polynomial i 1 6 + i 1 J + i 5 + l . 01111110 Destination Address Source Address Data CRC-16 cyclic redunancy code 01111110 ^ fek- ^ *~ 8-bit 8-bit 8-bit 16-bit ^ w 8-bit Figure 4.2: Format of a SDLC frame The driver is set up to handle interrupts generated when : 1. SCC is ready to transmit another byte or there is at least one byte ready to be delivered to the driver. " : V 2. An A B O R T (seven or more consecutive Is) is received. 3. Error situations like receive overrun (internal receive buffer of the SCC is over-written by data coming in from the modem) or transmit underrun (data is not supplied fast enough so that a "gap" is left in a already transmitting frame). 4. A change of state on CTS and CD lines. The SCC can be programmed to recognise the destination address of an incoming frame, address recognition logic can be activated or deactivated dynamically. When the address recognition logic is activated, frame is delivered to the driver, one byte at a time, when its destination address matches with the one programmed. If the address recognition logic is deactivated, all received data are delivered to the driver. CHAPTER 4. IMPLEMENTATION DETAILS 48 The SCC driver of a primary station would have the feature deactivated because it is part of the function of a primary station to monitor the traffic on the channel. On the contrary, SCC driver of a secondary station would have the feature activated after it has successfully joined the network to avoid unnecessary interrupts. The feature is deactivated before the secondary station has joined the network because the protocol has specified that each joining secondary station must monitor the channel to detect duplicate mailing addresses. Frames are delivered to the MAC sublayer only when they are received correctly. Invalid or incorrectly received frames are discarded by the SCC driver. Since the size of the on-chip receive buffer of the SCC chip is only three bytes. It is the responsibility of the driver to assemble these bytes into a frame and deliver it to the MAC sublayer after its correctness is verified. The series of correctness checks are outlined as follows. First of all, it must be a complete frame which begins with an opening flag and terminated by a closing flag. Frames start with an opening flag and terminated by an ABORT are commonly seen during the end-of-message extend period. During this period, data received are purely random but upon the termination of this period, the modem will assert the RxD line of the RS-232C port so that an ABORT signal can be detected by the SCC. Any data received during this period is discarded. The CRC is another important criterion for determining the validity of a frame. The CRC is calculated "on-the-fly" as data is received by the SCC from the modem. The calculated CRC CHAPTER 4. IMPLEMENTATION DETAILS 49 is checked against the one received which is the last 16 bits of the received frame immediately precedes the closing flag. Indication of the CRC check result is provided to the SCC driver in form of a bit in a specific register. The SCC driver discards the received frame if the CRC test fails. Finally, if there is a receive overrun during the reception of the frame, the previously received data of the same frame together with those received before the closing flag are discarded. All correctly received frames are queued up for later processing by the MAC sublayer. Indication of frames available to the MAC sublayer for processing is done via an interrupt. In fact, a level 3 interrupt is used to that effect. To transmit a frame, MAC passes to the driver, via the use of procedure call, a pointer to a queue of kernel structure called mbuf. This queue of mbufs contains one or more MAC frames. The SCC driver upon receiving the request will execute the handshaking protocol between modem and station as described in Chapter 2. CRC is, again, calculated on-the-fly as data is transmitted. It is inserted into the output stream just before closing flag is released. A point worth mentioning is that in order to prevent receiving modems from going out of sync with the transmitting modem, status of CD is monitored before asserting RTS. If the CD is already disasserted then RTS is asserted as usual. Otherwise, it will wait for a change of state on the CD line and a certain amount of time is elapsed before RTS is asserted to allow time for other modems to reset its receiving logic. CHAPTER 4. IMPLEMENTATION DETAILS 50 There is one additional function performed by the driver. The detection of idleness of the physical medium is most suitably placed in the driver for being the lowest software layer interface with the hardware. The channel idle timer kept by the primary station is reset when data is sent or received. Received data does not have to be a valid MAC frame to reset the timer. If the channel idle timer expires, the MAC sublayer is signalled by a level 1 software interrupt so that the event can be processed. 4.3 Imp lementa t ion of M A C Sublayer MAC protocol for the primary station is different from that of a secondary station. A more complicated protocol for the primary station is expected. In any case, it is implemented as a "finite state machine". Events to this finite state machine are generated either by the driver or by the LLC sublayer. Events generated by the driver are in form of interrupts while events generated by the LLC sublayer are in form of procedure calls. In fact, the LLC sublayer generates a MAJDATA.request to request for data transfer onto the physical medium. In each request, LLC has to supply i) address of mbuf which contains the LLC's protocol data unit (PDU), and ii) destination station address to which the PDU is forwarded. The PDU together with the appropriate MAC header is queued up waiting for transmission. A poll holding time (PHT) similar to the token holding time in IEEE 802.4 is used to guard any one station from hogging the network. This timer is implemented as a counter to eliminate overhead incurred by CHAPTER 4. IMPLEMENTATION DETAILS 51 introduction of a new timer. Knowing the data rate of the modem, time can be easily expressed in terms of number of bytes. Two queues, ready queue and backlog queue, are defined. A counter is used to keep track of the number of bytes of information currently queued up at the ready queue. LLC PDU is queued up at the ready queue only when the sum of the counter and the number of information bytes in PDU is less than a threshold value which is the poll holding time expressed in number of bytes and the backlog queue is empty. PDU is queued up at the backlog queue otherwise. The content of the ready queue is emptied after a bus-granting POLL has been received. Content of the backlog queue is then transferred to the ready queue accordingly. 4.4 Imp lementa t ion of L L C Sublayer Similar to the MAC sublayer, the LLC sublayer is implemented as a finite state machine. It executes a protocol closely follows the one recommended by the IEEE 802 committee. The sources of event generation come from the MAC sublayer, users of the LLC services and the station management unit recommended by the IEEE 802 committee. The value of maintaining the station management unit is to effectively handle some low level events which affect one or more protocol layers. Usually the handling of these events are implementation dependent and do not involve every communication layers, the gap between a clear cut layered protocol architecture and the efficient handling of a low level event at selective high level protocols bypassing some of the intermediate CHAPTER 4. IMPLEMENTATION DETAILS 52 layer(s) is narrowed. 4 . 4 . 1 M o d i f i c a t i o n a n d e n h a n c e m e n t The IEEE 802.2 protocol is implemented except for a few modifications. Modifications apply only to the connection-oriented services since selective retransmission instead of retransmit N error control technique is employed. The syntax and semantics of the LLC PDUs are basically the same as those in IEEE 802.2. An additional field called "retransmit value" (RV) is added onto the information and supervisory PDUs. RV on a received PDU is interpreted as the number of PDUs to be retransmitted. The field is significant and possibly triggers an immediate retransmission of I-PDUs when 1. A response (final bit set) I-PDU or RR S-PDU to a previously sent command PDU (poll bit set) soliciting the receive status of the remote LLC entity; or 2. A REJ S-PDU; or 3. RNR S-PDU but retransmission of I-PDU begins only when remote busy condi-tion is clear. For the receiving LLC entity to compute the RV, a new receive state variable V(OOS) is kept besides V(R) which is the sequence number of the expected I-PDU. V(OOS) contains the sequence number of the first out-of-sequence I-PDU received. If there is no out-of-sequence I-PDU received, it is set to contain the value of V(R). The RV field is CHAPTER 4. IMPLEMENTATION DETAILS 53 computed as the difference between the V(R) and V(OOS) modulus 128 with sequence number ranges from 0 to 127 inclusively. Selective retransmit is not commonly implemented because it may potentially re-quire a large amount of buffers to store all of the out-of-sequence I-PDUs, also an acknowledge timer is associated with each outstanding I-PDU in order that transmis-sion error can be recovered. This incurs a lot of overheads to the operating system to manage a large number of timers. With some enhancements made to the protocol, only one timer is kept without sacrificing the effective throughput of a connection. The use of acknowledge timer is very similar to the original IEEE 802.2 recommendation. The acknowledge timer associates with the "oldest" unacknowledged I-PDU. As the transmit window advances as acknowledgement is received, xthe acknowledge timer is restarted. There is one problem to this approach, consider the following scenario. As-sume that I-PDUs with sequence number 1,2, 3, 4, 5, 6, 7 and 8 have been transmitted and I-PDUs 1, 2 and 6 are garbled. The receiving LLC sends a RE J S-PDU with N(R) = 1 and RV = 2 requesting a retransmission of I-PDUs with sequence number 1 and 2. Consequently, I-PDUs 1 and 2 are received and acknowledgement should be received for I-PDUs from 1 to 5 by the transmitting end. The transmitting end then restarts the acknowledge timer and advances its transmit window. The "oldest" I-PDU is now 6 and has to wait for the expiry of acknowledge timer to discover that the previous transmission is garbled. If one acknowledge timer is associated with each unacknowl-CHAPTER 4. IMPLEMENTATION DETAILS 54 edged I-PDU, the amount of time to wait would be shorter since it is independent of the "oldest" unacknowledged I-PDU. Another effective way of handling this situation is for the receiving LLC to actively request for a retransmission. In the previous scenario, after the receiving LLC has correctly received I-PDUs 1 and 2, it advances its receive window and I-PDUs 1 to 5 will be delivered to upper layer. The V(R) is now 6, but the first out-of-sequence I-PDU is found to be 7. The receiving LLC can request for a retransmission of I-PDU 6 by sending a REJ S-PDU. Therefore, the sending LLC will immediately retransmit the lost I-PDU upon receiving REJ. The above enhancements introduce changes to the syntax and semantics of I-PDU and S-PDU. Only modest modifications are made to the protocol in order to keep it simple and at the same time enhances its function. No additional state is introduced to the original IEEE 802.2 protocol. Only slight variations in state transitions and heuristics from the original protocol are required. 4 . 4 . 2 I n t e r f a c e b e t w e e n L L C a n d i t s u s e r s LLC sublayer is implemented as a part of the UNIX operating system while the LLC services are provided to users who reside out of the operating system's kernel. Interfac-ing between the two involves system calls and change of operation mode. The UNIX socket abstraction is used for the purpose of providing services by LLC to its user. Thus each socket corresponds to a SAP from which connection-oriented and connectionless CHAPTER 4. IMPLEMENTATION DETAILS 55 services can be accessed. Standard service calls provided by the LLC, e.g. set up and tearing down of connection, are mapped onto the set of system calls which are used to manipulate the socket. Standard set of service primitives provided by the LLC sublayer contains the fol-lowing: For connectionless service : L_DATA.request L_DATA.indication For connection-oriented service : L_DATA_CONNECT.request LJDISCONNECT.indication L_DATA_CONNECT.indicate L.DISCONNECT.confirm LJDATA_CONNECT.confirm L_RESET.request L.CONNECT.request LJtESET.indication L.CONNECT.indicate L-RESET.confirm L.CONNECT.confirm L.CONNECTION JFLOWCONTROL.request L_DISCONNECT.request L_GONNECTIONJFLOWCONTROL.indication The socket system call is used to create a SAP for accessing services. One socket can only be used to get access to one type of service (connection-oriented or connection-CHAPTER 4. IMPLEMENTATION DETAILS 56 less). Close system call frees up the previously opened SAP. For connection-oriented services, close also disconnects a LLC connection where applicable. For connectionless service, mapping between service primitives and the UNIX socket manipulation rou-tines is straight forward. System call socket is called to request for an unused SAP. LJDATA.request is mapped onto the sendto system call. There is no direct mapping between L_DATA.indication and the set of socket manipulation system calls. User data from the L_D ATA.indication is queued up for later retrieval. Retrieval is done through the use of recvfrom system call. To relinquish the usage of a SAP, a close system call is used to free the SAP for the use by others. For connection-oriented services, the mapping is a little bit more complicated. The server and client model is generally adopted as the communication paradigm used in link-establishment for the UNIX socket. The server "listens" to a socket which was binded to a well-known address. A new socket will be created for each new connection made and passed to the appropriate handler. This is similar to the ARPANET'S initial connection protocol. The same communication paradigm cannot be adopted fully because the level of abstraction of the socket in this implementation is different from that in the original UNIX socket. The original UNIX socket usually corresponds to a TSAP (Transport service access point) especially for sockets created with TCP/IP as controlling protocol. If the exact same communication paradigm is adopted, an extra level must be added between the socket abstraction and the LLC sublayer. But the CHAPTER 4. IMPLEMENTATION DETAILS 57 idea here is to provide user with a basic and simple to use interface such that higher level layer can be built on. Therefore, the introduction of an extra layer is not de-sirable. Similar to the connectionless service, socket is created by the socket system call. Each socket created utilizing connection-oriented services corresponds to a LLC connection. The link establish procedure follows the server and client model such that socket has to be "listened" for connection request. The accept system call is used for this purpose. L_CONNECT.request is mapped onto the connect system call. While the function of L.CONNECT.confirm is replaced by the return value of the connect system call. Connection is rejected if no accept has been issued by the time connection request reaches the destination or the intended LLC connection is actively communicating with other LLC connection. The major difference between this implementation and the orig-inal UNIX socket is that no new socket is created during link establishment. The same socket is used for "listen" to new connections as well as for future communications. Sys-tem call close triggers the disconnection of the link, thus a LJDISCONNECT.request. L_DISCONNECT.indication is reflected through the return value after calling any one of the socket manipulation system calls. User data transfer is similar to connectionless service. Recvfrom and sendto system calls are used. There is no system call onto which LJRESET.request can be mapped. A new system call is implemented called resetsocket. It provides a means for user to request for a reset to a LLC connection. Result returned by L JlESET.confirm is reflected by the return value of the resetsocket CHAPTER 4. IMPLEMENTATION DETAILS 58 system call. LJtESET. indication is presented to the user through the use of the return value after calling any one of the socket manipulation system calls. Downward flow control request, i.e. L_FLOWCONTROL.request, is not necessary since user receives data from the socket only when it is ready through the use of recvfrom system call. Upward flow control request, i.e. L_FLOWCONTROL.indication, is achieved through the use of the return value after calling sendto system call. Normally the number of bytes sent is returned as a result of the sendto system call. A return code indicating LLC is not ready to receive any data from the user is returned if flow control is ex-ercised. A select system call can be used to determine the sending state of the LLC connection when upward flow control is being exercised. 4 . 4 . 3 B e t w e e n L L C a n d s t a t i o n m a n a g e m e n t u n i t In this implementation, the station management unit handles two events. They are events when station has joined the ring and when station has been excluded from the ring by the primary station. Both of these events are detected by the MAC sublayer. MAC sublayer will signal the station management unit when SETPSEQ frame has been received during the invitation phase or when the station has not received POLL for certain amount of time. LLC will be signalled by the station management unit via procedure calls. When the station has successfully joined the network, LLC will respond by allowing CHAPTER 4. IMPLEMENTATION DETAILS 59 all subsequent socket manipulation system calls. Error code indicating that station has not yet joined the network is returned otherwise. When station is excluded from the ring, the MAC sublayer will respond by clearing the pending message queue and get into a state of waiting to join the network. LLC upon signalled by the station management unit will disallow all subsequent socket manipulation system calls. Also, all active connections will be disconnected. State of all active LLC connections are changed to ADM which is the state when no link has been established. Transmit window will be cleared and buffers used will be freed as a result. It is still, however, up to the user whether he wants to close the socket and free up the SAP. Chapter 5 Performance Measurements This chapter presents the performance measurements for a experimental power line LAN. The performance of the MAC sublayer was accessed individually to expose fea-tures specific to this sublayer, e.g. joining and deletion of a station. The performance results obtained provide some insights as how various MAC level parameters can be set. The performance of LLC sublayer was evaluated by performing a link level file transfer between a number of Sun workstations. The set up of the experimental network is described in next section together with tools used in getting the results. It is then fol-lowed by a presentation and analysis of measurements obtained from the experimental set-up. 5.1 E x p e r i m e n t a l Set-up The experimental network was set up as depicted in Figure ,5.1. The network was consisted of a number of communicating Sun workstations and an IDACOM Protocol 60 CHAPTER 5. PERFORMANCE MEASUREMENTS 61 Secondary Secondary : ; :— D a t a Flow Figure 5.1: Experimental network setup Tester (PT). The Motorola 68000 based PT is capable of capturing communication scenarios onto its RAM and/or floppy disk so that they can be played back for analysis. The PT serves as a tool with useful features for network monitoring and performance analysis. The event time-stamping feature and network throughput analyzer provided have alleviated the need for software "probe" to be inserted into the software under measurement. A more accurate result can then be obtained. In this set up, the PT was operated in a "MONITOR" mode and was placed in between a primary station and its modem. The traffic on the RS-232C link was passively monitored and recorded by the PT. The Sun workstations were interconnected to each other simply by the power distribution circuit via the use of the power line modems. CHAPTER 5. PERFORMANCE MEASUREMENTS 62 5.2 Per fo rmance of M A C Sublayer The MAC sublayer is receiving special attention since it is the fundamental software layer. The success of a local area network has a lot to do with the efficiency of this sublayer. The three major functions performed by this sublayer were evaluated. The station join time, station death detection time and station response time were measured and presented in the next few paragraphs. The performance of the MAC sublayer depends on a number of parameters. The value of some of the parameters should be set to adapt to the traffic and application of the LAN while some of them are rather independent. The channel idle time mentioned in Chapter three is one of those parameters whose value is independent of the end application. The channel idle time specifies the longest time period the physical medium is allowed to stay idle before action is taken by the primary station. Station response time was measured to give insight as how this parameter should be set. The station response time was measured as the time elapsed between the sending of a POLL frame and the reception of a response by the same station. The mean station response time averaged over 20 samples was found to be 25.09ms. This time depends solely on the speed of the hardware and MAC sublayer software. The response time can be broken down as the time for asserting a channel, data transmission data, the propagation delay, end-of-message extend time imposed by the modem and software processing CHAPTER 5. PERFORMANCE MEASUREMENTS 63 time. Since the experimental power line network covered only a limited distance and the POLL frame was only 4 bytes long. Data transmission time and propagation delay were negligible. Time for asserting the channel and the end-of-message extend time were about 4 to 10ms and 10 to 15ms respectively. This implies that it took no more than a few milliseconds for software processing. The 25.09ms response time was obtained with light network traffic as well as light workloads on the Sun workstations. This time is expected to increase as the data traffic on the power line gets busier and/or the workloads on the Sun workstations become heavier. To provide some margin for this potential increase, the channel idle time was set at 80ms. Data (k bits) 1 station 2 stations 3 stations 0 0.81s 1.05s 1.18s 7.2 N/A 3.56s 6.35s 14.4 N/A 4.95s 7.44s 21.6 N/A 7.63s 12.10s Table 5.1: Mean station join time under different loadings The time taken for a station to join the network depended not only on the value set for the channel idle time, it depended also on the number of address subspaces partitioned, the frequency of the invitation and the workload of the data network. The join time of a station was measured as the difference between the time a secondary CHAPTER 5. PERFORMANCE MEASUREMENTS 64 station generated a random address and the time a SETPSEQ frame was received. As mentioned before, the invitation phase was executed before each polling round. For an address space partitioned into 8 subspaces and circulated at a rate of 2 subspaces per invitation phase, the mean station join times averaged over 20 samples were measured under different circumstances and are shown in Table 5.1. The first column of the table gives the number of bits of information to be sent upon reception of POLL frame by each station. The second and subsequent columns give the mean join times measured with different number of stations already in the network with various data traffic. A 0.81s station join time was obtained when primary was the only station in the network. This figure was found to be very close to the expected value. The expected station join time (Ejoin time) was the average between the best case and the worst case. Consider the best case, there would be no time wasted on waiting for the right window to be opened. Therefore, the expected join time should equal to the time involved in executing the 5-way handshake protocol which was 5 x Ttend where Taend was the time needed to send out a MAC frame. Since data transmission time, propagation delay and software processing time were comparatively smallj Taend could be taken as the sum of channel assertion time and end-of-message extend time which was about 22ms. Therefore, it took about 110ms to execute the 5-way handshake protocol. In the worst case, seven windows would have been opened before a station can join the network by executing the 5-way handshaking protocol. In this implementation, 2 INVITE frames CHAPTER 5. PERFORMANCE MEASUREMENTS 65 were sent for each window to invite new stations to join in. There was a 80ms, which was the channel idle time, time separating the sending of successive INVITE frames to allow time for new station to react. Therefore, for the worst case, 14 INVITE frames with unmatch window number might have been received before the INVITE frame with the. right window number came along. The time wasted on waiting was then 14 X (Taend + channel idle time) which was 1428ms. The station join time in the worst case was 1538ms including the time spent on executing the 5-way handshaking protocol. Averaging the best and the worse cases, Ejoin time was found to be 0.824s which was very close to the measured 0.81s station join time. The station join time got worse as the number of stations increased or the amount of information sent became larger. It was observed that when the amount of information was increased from 0 bit to 7,200 bits there was a subtle increase in station join time. It could be accounted for by the extra handshaking done between a station and its modem when data was transmitted. If there was no data pending, INVITE frame and POLL frame were transmitted by primary station and secondary station respectively after receiving a POLL. If there was data pending at the station, transmission of INVITE or POLL frames would follow the transmission of data. To save an assertion to the channel, the INVITE or POLL frames were appended to the end of the data queue and would be transmitted together with the data frames upon successful seizure of the channel. After passing the data queue to the Zilog driver, the station has to prepare CHAPTER 5. PERFORMANCE MEASUREMENTS 66 the data queue for transmission in next polling round before transmitting the POLL or INVITE. However, if the amount of information pending to be sent was too small such that the POLL or INVITE frame could not be added onto the data queue before the end of the data transmission, an extra channel assertion was required. This was the case when only 7,200 bits of information were pending at the station. The effect on the mean station join time caused by the addition of a station on the network cannot be seen clearly from the measured results. However, time wasted on waiting for the right INVITE frame is the major time affecting the mean station join time. Due to the simple and highly regular operations performed by the network stations, addition of a station merely delays the sending of INVITE frames by a rather constant factor. Thus, a linear increase in mean station join time is expected as the size of the network grows. Data (k bits) 2 stations 3 stations 4 stations 0 1.20s 1.30s 1.45s 7.2 1.20s 4.30s 7.25s 14.4 1.20s 7.04s 10.89s 21.6 1.20s 10.56s 20.56s Table 5.2: Mean death detection time under different loadings The time required by the primary station to detect the death of a station was CHAPTER 5. PERFORMANCE MEASUREMENTS 67 measured. The death detection time was measured as the time difference when primary station detected a channel idle when it was the dead station's turn to respond to a POLL frame and when primary station has concluded that the station has died. The primary drew such conclusion only when a station has failed to respond to a POLL frame for N consecutive polling rounds. For N set to 3, the dead station detection time was measured under different network traffic. The results are presented in Table 5.2. The format of the table is basically the same as that of Table 5.1. The first column gives the number of pending bits to be sent by each station upon receiving the POLL frame. The second, third and fourth column of the table give the measurements obtained with different data traffic with 2, 3 and 4 stations in the network respectively. A death detection time of 1.2 seconds was obtained when there were only 2 worksta-tions in the network. This time can be broken down as the time spent on inviting new stations to join the network and the time spent on detecting the absence of response to a POLL frame in the current polling round. Four INVITE frames were sent in each polling round to invite new stations to join in. With channel idle time set at 80ms and N set to be 3. 10 assertions were made to the channel, 8 for sending INVITE frames and 2 for sending POLL frames. With channel assertion time of about 10ms, this accounted for 100ms of the 1.2s death detection time. 10 channel idle events were detected during the death detection process. This was responsible for 800ms of the death detection time. This implies 300ms was spent in software processing and data CHAPTER 5. PERFORMANCE MEASUREMENTS 68 transmission. The end-of-message time did not apply in this case because the primary station was the only station on the network that was actually transmitting frames and this time overlapped completely with the channel idle time. It was also noticed that the death detection time was identical for different workloads when 2 stations were in the network. This was because the primary has refrained from transmitting data if it suspected the only secondary station is dead. Therefore, the number of pending bits in a station is irrelevant under this circumstance. The measured death detection time experienced the same subtle increase when the pending bits increased from 0 to 7,200 as in station join time. It was also noticed that as the workload of the network got heavier, the measured death detection time increase unexpectedly. The fact that primary station has to monitor the traffic of the network introduced a lot of overhead for the primary station to process all the data frames even though they were not desti-nated to it. This increased the software process time. The death detection time can be improved by taking another approach. The primary can keep sending N POLL frame to the suspected station separated by the "channel idle time" interval. If the secondary fails to respond to all of these POLL frames then primary can draw the conclusion im-mediately. This has an advantage of being independent of the current network traffic. However, the time taken for each polling round becomes irregular. Using the current approach has an added advantage of spreading out the death detection process so that the chance of accidentally excluding a station from the network due to a temporary CHAPTER 5. PERFORMANCE MEASUREMENTS 69 poor performance of the physical medium is minimized. Again, the impact on the death detection time caused by the addition of stations in the network is not clearly indicated from the measured results. Despite the increase in software processing time at the primary station when data traffic becomes heavier, the death detection time is expected to grow linearly as the size of the network grows. The duration of each polling round dictates the death detection time to a large extent. It can be seen in Table 5.3 that the duration of polling round grows linearly as the number of network stations increase. Data (sec) 2 stations 3 stations 4 stations Tput(bps) Delay Tput(bps) Delay Tput(bps) Delay 0 0.5 1.0 1.5 322.78 0.38s 10332.29 1.43s 11861.65 2.44s 12455.94 3.48s 351.54 0.40s 11408.64 1.96s 12382.28 3.50s 12893.18 5.04s 364.63 0.42s 11593.66 2.49s 12703.34 4.54s 13071.50 6.62s Table 5.3: Network throughput and delay under different loadings To determine the time to finish each polling round, the time interval elapsed between reception of successive POLL frame was measured and is shown in Table 5.3. Addition of a station added the expected amount of time to the delay measured. The maximum throughput was not achievable due to the time used in waiting during invitation phase. A total of 320ms time was wasted on waiting if there was no new station joining in that polling round. Fortunately, the invitation phase is waived once the number of secondary CHAPTER 5. PERFORMANCE MEASUREMENTS 70 stations has reached a threshold value. More efficient physical channel utilization can then be achieved. 5.3 Ove ra l l Per fo rmance To assess the overall performance of the network, a link level file transfer was per-formed so that both implemented MAC and LLC sublayers and the physical channel can be exercised. Three parameters, poll holding time, maximum frame size and the window size of LLC connection were varied and measurements were taken with various combination of the parameters. Tables 5.5 - 5.11 show results obtained with different parameters settings and communication settings. User level delay, physical channel throughput were measured. User level delay was measured using the UNIX /bin/time utility and the physical channel throughput was measured by the PT's throughput analyzer. The mean queue length showing the average number of frames queued up at the MAC sublayer when a send request was issued by the LLC sublayer was measured. The mean queuing delay was measured in seconds giving the average time waited by a LLC PDU before it Was sent out onto the physical medium. The file transfer took place at user (shell) level where the UNIX socket abstract was used to interface with the LLC sublayer. A server and client model was adopted as the communication paradigm. Two user processes, client and server, were started at user level on different stations. The server listened to a well-known CHAPTER 5. PERFORMANCE MEASUREMENTS 71 Setting Frame size (bytes) Window size (frames) POLL holding time (sec) I 128 16 1.0 II 128 16 1.5 III 128 32 1.0 IV 128 32 1.5 V 256 16 1.0 VI 256 16 1.5 VII 256 32 1.0 VIII 256 32 1.5 IX 512 16 1.0 X 512 16 1.5 XI 512 32 1.0 XII 512 32 1.5 Table 5.4: Setting number and corresponding parameters values address to which the client would connect. After the connection has been established, the client sent the name of the file it wished to access. The server, upon reception of the file name, sent the number of PDUs to be expected to the client followed by the content of the file, /bin/time was used to measured the total time taken by the client process to finish. Therefore, the time measured included the data transmission time as well as the connection set up and tear down time. The file transferred was a 11-page documented C program whose size was 21497 bytes. Results shown in Tables 5.5-5.7 were obtained by transferring this file between a server and a client residing on different machines with 2, 3 and 4 stations in the network respectively. Improvement of a factor CHAPTER 5. PERFORMANCE MEASUREMENTS 72 Setting User level Network Queue length Queuing delay delay (sec) tput(bps) Client Server Client Server I 54.8 3644.55 0 12.46 0.073 1.97 II 56.6 3651.25 0 7.342 0.151 0.31 III 28.4 6591.5 0 19.44 0.11 1.847 IV 28.9 6836.5 0 17.24 0.165 1.197 V 28.2 6333.67 0 11.66 0.169 2.498 VI 28.7 6706.0 0 11.60 0.19 2.407 VII 18.8 9228.0 0 17.31 0.423 2.869 VIII 17.5 10109.6 0 15.69 0.37 2.336 IX 19.3 8972.0 0 9.4 0.482 2.915 X 17.6 11174.0 0 8.625 0.367 2.268 XI 19.2 9099.5 0 15.49 0.523 5.576 XII 16.8 11148.0 0.166 16.61 0.35 5.094 Table 5.5: Measurement with 2 stations and 1 file (21 kbytes) transfer Setting User level Network Queue length Queuing delay delay (sec) tput(bps) Client Server Client Server I 57.6 3822.10 0 12.21 0.079 2.07 II 58.3 3827.33 0 7.058 0.162 0.303 III 28.6 6718.5 0 19.65 0.155 1.85 IV 29.1 6851.5 0 17.39 0.160 1.201 V 28.4 6488.5 0 11.53 0.185 2.547 VI 28.8 6994.0 0 11.30 0.282 2.442 VII 19.0 10424.0 0 16.83 0.311 2.870 VIII 18.8 10996.0 0 15.95 0.425 2.343 IX 19.7 9048.0 0 11.80 0.51 3.532 X 17.7 11209.0 0 8.625 0.42 2.309 XI 19.7 8913.5 0 17.85 0.533 5.848 XII 17.2 11167.0 0.1606 17.22 0.483 5.273 Table 5.6: Measurement with 3 stations and 1 file (21 kbytes) transfer of 2 was observed by increasing the LLC window size from 16 to 32 with frame size CHAPTER 5. PERFORMANCE MEASUREMENTS 73 Setting User level Network Queue length Queuing delay delay (sec) tput(bps) Client Server Client Server I 57.2 3974.4 0 12.45 0.083 2.07 II 56.8 4009.25 0 7.23 0.180 0.33 III 29.1 6689.33 0 19.46 0.170 1.91 IV 28.0 6942.0 0 17.25 0.190 0.99 V 28.3 7030.0 0 11.55 0.13 2.50 VI 27.5 7300.0 0 9.51 0.27 1.38 VII 19.3 10108.0 0 19.39 0.313 3.42 VIII 18.2 10529.0 0 15.72 0.46 2.45 IX 20.2 8930.0 0 11.67 0.27 3.625 X 18.8 10033.0 0 8.29 0.63 2,48 XI 20.4 9134.0 0 18.45 0.55 6.05 XII 17.4 11172.5 0 17.22 0.35 5.35 Table 5.7: Measurement with 4 stations and 1 file (21. kbytes) transfer set at 128 bytes in all 3 tables. However, doubling the LLC window size did not have the same effect neither with frame size of 256 nor with frame size of 512. In this implementation, an RR was sent but every 5 seconds to serve for 2 purposes. To keep the LLC connection "alive" and to piggyback acknowledgement. Therefore, frequency of the RR sent was a potential source of bottleneck hindering the performance of the file transfer. As the amount of outstanding information increased, the effect of the RR sending frequency diminished and the bottleneck has moved from the frequency of RR sending to demand of channel bandwidth. For settings VI to XII, no dramatic changes in user level delay was observed despite the amount of outstanding information has been increased either by doubling the frame size or/and by increasing the window size. CHAPTER 5. PERFORMANCE MEASUREMENTS 74 Only slight improvement was observed when poll holding time was increased from 1 second to 1.5 second. Thus, it was believed that the determining factor in settings I to VI was the frequency of acknowledgement sent whereas poll holding time was the bottleneck for settings VII to XII. For POLL holding time set at 1 second and window size at 32, the user level delay did not reduced as expected when frame size was increased from 256 bytes to 512 bytes. Since POLL holding time was managed in a station by counting the number of bytes allowed to be sent. When POLL holding time was set at 1 second, seven 256-byte frames can be transmitted while only three 512-byte frames could be transmitted. This accounted for 1792 bytes and 1556 bytes respectively, hence, explains the increase in user delay time. It was found by comparing these three tables, when frequency of acknowledgement was the bottleneck of the network, increase in POLL holding time did not always result in reduction of user delay time. Sometimes the user delay time was made worse when POLL holding time was increased. The queuing delay of client gives the average time waited by a client in order to send out acknowledgement. The queuing delay increased as the POLL holding time increased for the same frame size and window size. This has an adverse effect on the user level delay. However, when four stations were in the network showed otherwise. In fact, it displayed a better performance than the other 2 cases when acknowledgement was the bottleneck. It was due to a further separation in communication between server and client. When CHAPTER 5. PERFORMANCE MEASUREMENTS 75 the client has sent acknowledgement, the server LLC needed time to process it which included advancing the send window and sending of next window of LLC I-PDUs. If the access right of the medium is granted right after the reception of the acknowledgement the server would not have time to process it and thus there would not be anything to send. If the reception of POLL and reception of acknowledgement was well separated, one extra polling round can be saved. Therefore, the performance depends also on the placement of the server and client in the network as well. CHAPTER 5. PERFORMANCE MEASUREMENTS 76 Setting User level delay (sec) Network tput(bps) Client I Client II I 57.5 58.0 6874.25 II 57.1 58.6 6881.02 III 38.7 37.9 10169.8 IV 35.1 38.8 10985.5 V 38.2 35.1 10113.33 VI 37.6 37.2 10208.5 VII 37.0 36.7 10360.67 VIII 33.9 33.4 11318.67 IX 37.6 38.3 9767.0 X 32.6 33.1 11409.0 XI 37.6 36.9 10056.33 XII 33.3 32.8 12357.0 Setting Queue length Queuing delay Client I Client II Server Client I Client II Server I 0 0 19.61 0.234 0.642 2.09 II 0 0 9.119 0.179 0.688 0.367 III 0.166 0.1 35.5 0.553 0.9 3.04 IV 0 0 36.73 0.615 0.484 2.14 V 0 0 25.36 0.4224 0.702 4.282 VI 0.1 0 25.26 0.518 0.686 4.139 VII 0 0 45.37 0.546 0.593 8.232 VIII 0 0 42.46 0.653 0.74 7.039 IX 0 0 27.93 0.276 0.482 9.21 X 0 0 22.28 0.638 0.736 6,715 XI 0 0 37;81 0.204 0.554 13.558 XII 0 0 35.41 0.772 0.663 12.059 Table 5.8: Measurement with 3 stations, 2 file (21 kbytes) transfers and 1 server CHAPTER 5. PERFORMANCE MEASUREMENTS 77 Setting User level delay (sec) Network tput(bps) Client I Client II I 56.4 57.7 6885.6 II 56.9 58.2 6888.8 III 33.7 34.0 10382.0 IV 32.9 39.1 11059.67 V 31.8 33.0 11770.5 VI 33.6 34.7 10504.33 VII 31.6 31.9 11767.5 VIII 30.1 39.3 11799.67 IX 32.8 32.6 11395.5 X 29.6 29.5 12574.5 XI 32.0 42.0 11380.5 XII 29.9 31.2 12413.0 Setting Queue length Queuing delay Server I Server II Client Server I Server II Client I 12.78 12.80 0.433 1.821 3.035 0.13 II 6.984 7.520 0.179 0.127 0.5404 0.521 III 19.33 17.91 0.44 2.377 3.056 0.59 IV 17.09 22.13 0.29 2.125 1.37 0.423 V 11.57 10.72 0.389 2.733 3.517 0.434 VI 11.12 30.24 0.211 3.468 2.706 0.447 VII 19.66 10.57 2.0 6.208 6.833 10.28 VIII 19.27 29.40 0.4118 6.022 5.905 0.761 IX 26.98 11.83 .0.3684 8.023 6.951 0.6126 X 9.82 10.78 0.4211 7.046 5.237 0.942 XI 18.51 16.04 0.458 10.87 12.289 0.6125 XII 25.69 17.42 0.5 11.55 9.958 1.0722 Table 5.9: Measurement with 3 stations, 2 file (21 kbytes) transfers and 2 servers To study the behaviour of the network under different traffic patterns, measure-ments were obtained and analyzed by performing file transfers between a few LLC connections at about the same time. Results shown in Table 5.8 were obtained by CHAPTER 5. PERFORMANCE MEASUREMENTS 78 Setting User level delay (sec) Network Client I Client II | Server tput(bps) I 62.0 58.6 59.6 9682.0 II 58.7 62.6 60.0 10092.25 III 57.3 58.2 57.5 10063.8 IV 53.7 53.5 54.9 10883.25 V 59.6 53.2 53.2 10256.5 VI 44.4 46.0 45.4 11127.0 VII 52.1 54.3 56.6 10153.5 VIII 50.5 49.9 49.9 10955.6 IX 56.6 56.7 56.4 9816.25 X 48.4 48.4 44.5 11268.5 XI 61.6 63.0 60.0 10522.5 XII 48.8 49.7 49.0 11155.5 Setting Queue length Queuing delay Client I Client II Client III Server Client I Client II Client III Server I o 0 0 35.18 0.288 0.48 0.779 3.11.6. II 0.18 0 0 21.58 0.56 0.69 0.75 1.62 III 0 0 0.063 67.89 0.632 0.66 0.61 6.46 IV 0.08 0 0.07 55.14 0.83 0.93 0.75 4.53 V 0.8 0 0 39.55 0.576 0.425 0.803 7.09 VI 0.18 0.08 0 33.32 0.66 0.71 0.518 5.85 VII 0.11 0.077 0 71.87 0.47 0.71 0.53 13.87 VIII 0 0 0.091 69.41 0.75 0.62 0.81 11.73 IX 12.07 0.08 0 46.42 0.49 0.47 0.505 15.25 X .0.4 0 0 34.28 0.79 0.65 0.79 10.66 XI 0.22 0 0.08 62.17 0.65 0.49 0.70 22.94 XII 0 0 0 55.91 0.75 0.73 0.78 20.41 Table 5.10: Measurement with 4 stations, 3 file (21 kbytes) transfers and 1 server performing 2 file transfers in a network with 3 stations. One server was present in the network while 2 files were transferred to 2 different client stations at the same time. Results shown in Table 5.9 were taken under similar settings but instead of having CHAPTER 5. PERFORMANCE MEASUREMENTS 79 Setting User level delay ( sec) Network Client I Client II Server tput(bps) I 55.1 57.8 58.4 10154.75 II 57.6 56.9 57.6 11076.5 III 46.7 47,0 46.7 12328.5 IV 43.7 43.9 48.5 12929.0 V 42.3 46.8 47.0 12185.75 VI 42.5 44.7 44.7 12910.75 VII 44.6 44.7 43.9 12224.25 VIII 42.7 43.0 42.9 12043.33 IX 45.3 45.0 45.3 11590.0 X 42:6 42.6 46.6 12703.25 XI 45.0 44.6 45.0 12315.75 XII 43.1 44.0 43.0 12771.0 Setting Queue length Queuing delay Server I Server II Server III Client Server I Server II Server III Client I 12.23 11.8 11.984 0.246 2.778 2.683 2.282 0.492 II 7.27 7.23 7.35 0.86 1.79 0.18 0.97 0.34 III 19.29 21.65 18.28 0.95 4.00 4.015 4.94 1.06 . IV 17.55 17.57 12.42 0.71 2.89 3:38 3.12 0.87 V 12.41 11.58 10.19 0.944 4.42 4.42 4.95 1.094 VI 10.75 10.17 10.52 0.94 3.46 4.077 3.53 1.29 VII 24.84 22.21 21.17 0.97 10.39 10.68 9.43 1.38 VIII .18.26 17.96 21.11 1.00 7.25 8.77 10.85 1.96 IX 15.11 14.21 13.74 0.89 11.28 10.54 11.52 0.93 X 10.21 10.10 10.07 0.85 8.50 8.59 10.45 1.23 XI 17.17 19.64 19.54 0.944 19.34 15.85 18.62 1.25 XII 18.17 17.77 17.96 1.027 15.72 17.45 15.54 2.35 Table 5.11: Measurement with 4 stations, 3 file (21 kbytes) transfers and 3 servers one server serving a few clients at the same time, 2 servers were present on the net-work serving two clients residing on the same station. The next two tables give result obtained with 4 stations in the network with 1 server and 3 servers respectively. CHAPTER 5. PERFORMANCE MEASUREMENTS 80 In settings I and II, no substantial improvement or degradation in user delay time were observed when comparing it with single file transfer. A very slight increase in user delay time was observed which may be accounted for by longer queuing delay since 2 files were transferred. Acknowledgement to outstanding PDU was still the bottleneck which hindered the user delay time performance in these 2 settings. Better performance was observed with more symmetric traffic pattern. By symmetric traffic it means that network traffic are generated equally among the network stations. It is comprehensible because more data can be transmitted in one polling round before the network engaged in invitation phase. The overhead incurred by invitation phase can, thus, be minimized. According to the results obtained, setting X seems to give the best user delay performance for both cases with 3 stations. Increasing the window size resulted in poorer delay performance because more data PDUs were queued up and waited to be transmitted. The demand.for channel bandwidth became greater and so, it became the determining factor of the performance of the network. For file transfer done in the case of 4 stations, setting VI and setting VIII seemed to give the best performance for asymmetric and symmetric traffic respectively. Increasing the window size again resulted in poorer user delay performance. A few observations were made after analyzing the results. First of all, network can be saturated with data easily. In the case when only 3 simultaneous file transfers were performed, the demand for channel bandwidth has become the bottleneck. When CHAPTER 5. PERFORMANCE MEASUREMENTS 81 demand for bandwidth was a bottleneck, increasing the poll holding time from Is to 1.5s improved the user delay performance. By allowing each station to hold the POLL for a longer period of time resulted in increase amount of information flow per polling round before the network engaged in invitation phase. The overhead incurred by the invitation phase is, therefore, significant especially when there is a high demand for channel bandwidth. Chapter 6 Conclusions 6.1 S u m m a r y This thesis has described the design and implementation of the two fundamental sublay-ers in a local area network which utilizes the power distribution circuit as transmission medium. Protocols for both sublayers are devised to take into consideration partic-ular characteristics of the physical medium. Non-contention protocol is selected as a medium access protocol due to the limited bandwidth provided by the physical medium as well as the overhead incurred when accessing the physical channel through the use of hardware. A non-contention hub polling protocol is adopted for its simplicity and for a better control over the entire local area network. Since this is a centralized scheme, it is vulnerable at the poll master's site. The operation of the entire network depends on the aliveness of the poll master. This problem can be solved by performing a leader election [PETE82,FRAN82] upon detection of death of a poll master. Also included in the MAC protocol is a dynamic address assignment scheme. Phys-82 CHAPTER 6. CONCLUSIONS 83 ical address for a station is assigned by the poll master when the former joins the network. In order to refer to a certain station, an association between its logical name and physical name (dynamic address) must be established. In the current implemen-tation, the user is expected to know the physical address when trying to establish a link with a destination site. To improve the usefulness of the network, a name server should be provided. An enhanced IEEE 802.2 protocol is adopted for the LLC sublayer. The retrans-mit N error control technique recommended by the IEEE 802.2 standard is replaced by a selective retransmission technique to reduce the number of unnecessary retrans-missions; Penalty for achieving selective retransmission includes higher memory buffer requirement and an overhead of an extra byte of information in the Supervisory PDU and Information PDU. Both LLC and MAC sublayers are implemented in the kernel of the UNIX operating system to minimize data.copying and interfacing between the two sublayers. Service access points provided by the LLC sublayers are implemented using the UNIX socket abstraction with mappings defined between the set of socket manipulation system calls and services provided by LLC. Measurements obtained indicated that the implemen-tation of the simple hub polling scheme is an efficient one. Out of a typical mean poll response time of 25ms, only a few milliseconds is spent by the MAC software. A fairly good station join time and dead station detection time of 12s and 20s are also obtained CHAPTER 6. CONCLUSIONS 84 even with busy network traffic. This enables the formation of a dynamic network by taking advantage of the portability feature offered by the power line medium. A delay of 16.8s is obtained when measuring the time taken to transfer a 21 kbytes file. The measurements further prove the practicality of the idea of using the power lines as a data transmission medium. 6.2 Suggest ions for Fur ther Studies In spite of the low-to^medium transmission rates provided at a potentially high error rate, the power distribution circuit has proven useful for data communications. For sharing resources that operate at low speeds, the data transmission rate provided by the power line modems may be adequate, e.g. sharing printers which operate typically at 9,600 bps. Also due to the readiness of this medium, it is an ideal candidate for providing an alternate route in a hybrid local area network to improve the reliability of a communication system. Also as a suggestion for further investigation, the invitation phase was observed to incur overhead which can significantly degrade the performance of the network. A more efficient way of inviting new stations to join in the network needs further research. With the basic communication software in place, upper layer protocols or applications can be built such as a printer spooling system, device monitoring system and local area messaging system. Finally, from the experience of using the prototype modems, it is found that the CHAPTER 6. CONCLUSIONS 85 carrier sense protocol which is internally wired up in the modem causes three problems: (i) It becomes unnecessary when non-contention MAC sublayer is employed, (ii) The whole system can be hogged by one single station/modem if it fails to release the physical channel, (iii) A rather long channel access time is a direct consequence of executing this protocol. Removing this feature from the modem logic when using a non-contention MAC protocol would improve the overall performance of the network. Bibliography [BERM84] Bermbach R., Geisse H. & Kappas A., "DATALANE - A low cost local area network," Proceedings, IFIP TC 6 In-Depth symposium on Networks in Office Automation, Sofia, Bulgaria, September 1984. [BUX84] Bux W., "Performance issues in local-area networks," IBM system Jour-nal Vol. 23 No. 4, P.851-74, 1984. [CHAN85] Chan M. H-I., "Communication channel characteristics and behavior of intrabuilding power distribution circuits," M.A.Sc. Thesis, University of British Columbia, September 1985. [CHIU85] Chiu F. K. K., "Data communications using coherent minimun frequency shift keying on intrabuilding polyphase power line networks," M.A.Sc. Thesis, University of British Columbia, December 1985. [CHLA79] Chlamtac L, Franta W. R. & Levin D., "BRAM: The broadcast recong-nizing access method," IEEE Transaction Communications, Vol. COM-27, pp. 1183-1190, August 1979. [FLAT84] Flatman A. V., "CHEAPERNET - A low cost open system LAN," Pro-ceedings, LOCALNET84 Conference, San Diego, USA, October 1984. [FRAN82] Franklin W. R., "On an improved algorithm for decentralized extrema finding in circular configurations of processors," Communications of the ACM, Vol. 25, No. 5, May 1982. [GRAC85] Van Der Gracht P. K. & Donaldson R. W., "Communication using pseduonoise modulation on electric power distribution circuits," IEEE Transactions on Communications, Vol. COM-83, No. 9, September 1985. [IEEE802.2] Standard for Local Area Networks, "IEEE 802.2 Logical Link Control," ISO DIS 8802/5, 1985. 86 BIBLIOGRAPHY 87 [IEEE802.4] Standard for Local Area Networks, "IEEE 802.4 Token-Passing Bus Ac-cess Method" ISO DIS 8802/5, 1985. [MCD084] McDowell J . , "Broadband or baseband; CSMA/CD or Token - What's the difference?," Proceedings, LOCALNET84 Conference, San Diego, USA, pp. 758-762, October 1984. [PETE82] Peterson G. L., "An 0(n log n) unidirectional Algorithm for the circular extrema problem," ACM Transactions on Programming Languages and Systems, Vol. 4, No. .4,'October 1982. [SCH076] Scholl M., "Mulitplexing techniques for data transmission over packet switched radio systems," Ph.D thesis, Computer Science Dept., UCLA, 1976. [STER82] Sterling T. L., Williams R. D. &: Kirtley Jr., "COMONET: An intra-building data link," Proceedings, IFIP TC 6 International In-Depth sym-posium on local networks, April 1982. [TANE81] Tanenbaum A., Computer networks, Prentice-Hall, Inc., Englewbod Cliffs, New Jersey, 1981. [VUON85] Vuong S. T. & Gu H., "A low-cost local area network using electric power lines," Proceedings, ELECTRONICOM, Toronto, Canada, October 1985. [VUON87] Vuong S. T., Ma A. & Gu H., "Design and implementation of the ac-cess and link protocols for a low-cost LAN using electric power lines," Proceedings, GLOBECOM, Tokyo, Japan, November 1987. [ZIL082] Serial communications controller technical manual, Zilog, Inc, Campbell, California, 1982. Appendix A Finite State Machines in Invitation Phase This appendix gives the state transition diagrams for both the primary station and a new station during the invitation phase of the hub polling medium access protocol. Notice that the finite state machine described in Figure A is present in the primary station one per unique mailing address during the invitation phase. 88 APPENDIX A. FINITE STATE MA CHINES IN INVITATION PHASE 89 Figure A . l : Primary's invitation finite state machine (one per unique mailing address) during invitation phase APPENDIX A. FINITE STATE MACHINES IN INVITATION PHASE Figure A.2: New station's joining finite state machine during invitation phase Appendix B Example User Programs Utilizing L L C Services This appendix gives two C programs utilizing the LLC services provided. The content of a .h file which contains the necessary constants and macro is also given in this appendix. The content of /ubc-csgrads/ma/power/802_2/pl_pcol.h is as follows : / * _ — — - — — . . . * pl_pcol.h: s * This file contains the constant and macro used when power line * * */ #define #define #define #define #define #define LAN is called upon. AF_PL 13 /* Power Line Address Family */ PL_DGPC0L 19 /* Power Line Connectionless protocol # */ PL_PC0L 20 ./* Power Line Connection oriented protocol # */ PL_STATION_ADDR PL.SAP BYTE_PER_FR 0 /* subscr. to station address */ 1 /* subscr. to sap address */ 118 /* Max # of bytes per LLC PDU (x-10) */ #define concat_se(s .c) (((s)«4) + (c)«2) 91 APPENDIX B. EXAMPLE USER PROGRAMS UTILIZING LLC SERVICES #define CONST_ADDR(so,DA,s,c) {\ (so)->8a_family = AF_PL; \ (so)->sa_data[PL_STATION_ADDR] = DA; \ (so)->sa_data[PL_SAP] = concat_sc(s,c); \ > • #define ASSIGN_ADDR(so.SA.s) { \ (so)->sa_family = AF_PL; \ (so)->sa_data[PL_STATION_ADDR] = SA; \ (so)->sa_data[PL_SAP] = s; \ > APPENDIX B. EXAMPLE USER PROGRAMS UTILIZING LLC SERVICES 93 The server program is as follows : #include <sys/types.h> #include <sys/stat.h> #include <sys/socket.h> #include <sys/file.h> #include <errno.h> #include <stdio.h> #include "/ubc-csgrads/ma/power/802_2/pl_pcol.h" /*. * This file contains the code for a simple file server who listens to * a "well-known" address. Filename is expected after connection has * been established. It is then followed by the number of frames * expected and then the content of the file. * *•/ main() < int wfd, nfd, sfd; int s, bytes; struct stat f_stat; short num_sent; char c.filename[50]. buf[BYTE_PER_FR] ; if ((s = socket(AF_PL. SOCK_STREAM, PL.PCOL)) < 0) perror("create error"): else { i f (acceptCs. 0. 0) < 0) < perror("accept error"); exit(); > recv(s, filename, 50, 0); if (stat(filename, &f_stat) < 0 II (sfd = open(filename, O.RDONLY)) < 0) < num_sent = 0; sendto(s. imum_sent. 2. 0. 0, 0); APPENDIX B. EXAMPLE USER PROGRAMS UTILIZING LLC SERVICES 94 } else < num_sent = f_stat.st_size / BYTE_PER_FR + (f_stat.st_size I BYTE_PER_FR != 0); sendto(s, &num_sent, 2, 0, 0, 0); wfd = 1 « s; while ((bytes = read(sfd. buf, BYTE_PER_FR, 0)) > 0) resend: if (sendto(s. buf. bytes, 0. 0. 0) < 0) { if (errno == ENOBUFS) < if ((nfd = select(s +1.0, fcwfd. 0, 0)) < 0) { perror("select error"); break; > else { printf ("success select °/0d\n" , nfd); goto resend; > } else •( perror("sendto error"); break; > } > scanf("%c".&c); if (close(s) < 0) perror('*closing error"); APPENDIX B. EXAMPLE USER PROGRAMS UTILIZING LLC SERVICES 95 The client program is as follows: #include <sys/types.h> #include <sys/socket.h> #include <stdio.h> #include <errno.h> #include "/ubc-csgrads/ma/power/802_2/pl_pcol.h" / * - — — " * Usage :-* c l i filename DA sap# conn# > newfilename * Requesting a f i l e "filename" from remote f i l e server and put i t * i n f i l e "newfilename". * : */ main(argc, argv) in t argc; char *argv[]; { int s, bytes; int DA. sap. conn; short num_expected; struct sockaddr addr; char buf[BYTE_PER_FR]; . . i f (argc < 5) {. printf("argument missing\n"); e x i t O ; } i f ((s = socket(AF_PL. SOCK.STREAM, PL.PCOL)) < 0) perrorC'create error") ; else { DA = atoi(argv[2]): sap = atoi(argv[3]): APPENDIX B. EXAMPLE USER PROGRAMS UTILIZING LLC SERVICES 96 conn = atoi(argv[4]); CONST_ADDR(&addr, DA, sap, conn); if (connect(s, fcaddr, 4) < 0) { perrorO'connection error"); exit(); > sendto(s, argv[l], 50, 0. 0, 0); recv(s, taium_expected, 2, 0); while (num_expected— != 0 ktc (bytes = recv(s, buf, BYTE_PER_FR, 0)) > 0) { fwrite(buf, 1, bytes, stdout); > if (close(s) < 0) perror("closing error"); printf("end of program\n"); > > 


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items