UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Reservation arbitrated access for variable bit rate isochronous traffic transport over dual bus metropolitan… Chan, Henry C. B. 1997

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

Item Metadata

Download

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

Full Text

RESERVATION ARBITRATED ACCESS FOR VARIABLE BIT RATE ISOCHRONOUS TRAFFIC TRANSPORT OVER DUAL BUS METROPOLITAN AREA NETWORKS by HENRY C. B. CHAN B.A., University of Cambridge, England, 1988 M.A., University of Cambridge, England, 1992 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE FACULTY OF GRADUATE STUDIES DEPARTMENT OF ELECTRICAL AND COMPUTER ENGINEERING We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA September, 1997 © Henry C. B. Chan, 1997 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 £/,£C7fc/C/rL h CotfPl/T&Z B^J$)N^B^.\^G\ The University of British Columbia Vancouver, Canada ^ t e SEf TA' 1 1 . DE-6 (2/88) Abstract TEEE 802.6 is an international standard for metropolitan area networks (MANs) based on a dual bus architecture. In addition to its deployment for interconnecting local area networks (LANs), 802.6 MANs can also be used as broadband multiplexers for integrating different types of traffic over broadband integrated services digital networks employing asynchronous transfer mode (ATM/BISDN) and as distributive switches to support wire-less personal communication services. This thesis proposes a novel reservation arbitrated (RA) access protocol for transporting variable bit rate isochronous traffic (VBRIT) such as packet voice and video over dual bus MANs in general and IEEE 802.6 MANs in particular. RA access allows a variable bit rate isochronous source (VBRS) to capture and reserve isochronous channels on a bandwidth dn demand basis yielding substan-tial capacity improvements over pre-arbitrated (PA) access and providing a guaranteed transport service compared to queue-arbitrated (QA) access. To resolve possible access contention in the reservation process, a simple resolution mechanism is proposed where the upstream nodes yield to the downstream nodes during the confirmation stage. Never-theless the contention problem can be completely eliminated under the typical coverage area of a MAN by setting the operation parameters properly. A rich family of RA access protocols can be found based on different methods of acquiring the incremental band-width. In particular, a new cyclic capturing mechanism is proposed to provide fair access service. The performance of RA access is analyzed extensively by analytical methods and computer simulations based on different VBRS models covering voice, video confer-ence and motion video traffic. Three methods: uncontrolled bandwidth sharing, dynamic bandwidth partitioning and dynamic bandwidth sharing and the associated connection ad-mission control (CAC) mechanisms are evaluated for multiplexing heterogeneous VBRIT. A movable boundary integration scheme is proposed to integrate PA, QA and RA traffic efficiently which gives significant capacity improvement over existing integration meth-ods in the 802.6 standard. An important application of RA access is to facilitate the efficient transport of real time traffic over MAN-based personal communication networks and enterprise networks. ii Table of Contents Abstract ii List of Figures viii List of Tables xi Acknowledgment . . x i i Chapter 1 Introduction . 1 1.1 Development of M A N s 1 1.2 I E E E 802.6 M A N s . . . 4 1.3 Serv ice integration over I E E E 802.6 M A N s 6 1.4 Reservat ion protocols for transporting V B R I T 9 1.5 A im and objectives 10 1.6 Organizat ion of the thesis 11 Chapter 2 Overv iew of PA, Q A and R A a c c e s s 13 2.1 PA, Q A and R A a c c e s s 13 2.1.1 PA a c c e s s 13 2.1.2 Bi-state PA access 15 2.1.3 Q A a c c e s s . . . 16 2.1.4 R A a c c e s s 22 2.2 Evaluation of voice traffic capacity 23 2.2.1 PA access 24 2.2.2 Bi-state PA a c c e s s . 25 2.2.3 Q A access 27 2.2.4 R A access 29 i i i 2.3 Multiplexing gain .31 2.4 Summary 33 Chapter 3 1-persistent R A access . 35 3.1 Voice system model and performance criteria 35 3.2 1-persistent R A access protocol 38 3.3 Analyt ical modell ing of 1-persistent capturing mechan ism 43 3.3.1 Average clipping probability 43 3.3.2 Upper bound clipping probability 44 3.3.3 Lower bound clipping probability 45 3.3.4 Probabil ity distribution of number of c l ipped packets 46 3.3.5 Utilization . 48 3.4 D iscuss ions on simulation & analytical results 48 3.4.1 Cl ipping probability . 4 9 3.4.2 Campane l la criteria 50 3.4.3 Utilization 51 3.4.4 Effect of propagation delay on cl ipping probability 52 3.4.5 Simulat ion using a real voice conversat ion . 53 3.5 S u m m a r y . 55 i v Chapter 4 Contention free R A access with cycl ic capturing . 5 6 4.1 Content ion free condition for R A a c c e s s 56 4.2 R A a c c e s s with cycl ic capturing 58 4.2.1 R A slot format 58 4.2.2 Spreading of R A slots . 59 ' 4.2.3 Cyc l ic capturing mechan ism 59 4.2.4 R A a c c e s s controller and protocol operations 60 4.3 Q o S requirements and analytical model ing of R A a c c e s s . 63 4.3.1 Traffic model and assumpt ions 63 4.3.2 P L R 64 4.3.3 Packet delay and delay jitter . . 6 5 4.3.4 Utilization 67 4.3.5 Probability distribution of consecut ive packet loss . 6 8 4.4 Simulat ion and analytical results 71 4.4.1 P L R . 7 2 4.4.2 Packet delay and delay jitter 75 4.4.3 Loss duration performance criteria 78 4.4.4 Utilization . . 78 4.4.5 Capaci ty improvement . . . 81 4.5 A n alternative packet management strategy at a M A N node 82 4.6 Summary 89 V Chapter 5 Simulat ing R A a c c e s s with video source models 90 5.1 Video serv ices and modell ing of v ideo sources . . . . . . . 90 5.2 A R and M V model . 93 5.2.1 A R model 94 5.2.2 M V model 95 5.3 Discuss ion on simulation results . . . . . . . . . . . . . . . . 97 5.3.1 Bit rate trace 98 5.3.2 P L R 102 5.4 . Summary 104 Chapter 6 Integration of heterogeneous V B R I T and connect ion admiss ion control 105 6.1 Introduction and system model 105 6.2 Uncontrol led bandwidth sharing (UBS) 108 6.3 " Dynamic bandwidth partitioning (DBP) 112 6.4 Dynamic bandwidth sharing (DBS) 115 6.5 Compar isons of the integration methods 122 6.6 Integration of voice, A R and M V traffic with D B S 124 6.7 Comb ined D B P - D B S scheme . . . . : 125 6.8 Summary 126 Chapter 7 Integration of PA , Q A and R A traffic 128 7.1 The integration scheme for PA, Q A and R A traffic . . . . 128 7.2 Performance analysis . 132 7.2.1 Simulation models 132 7.2.2 Ideal data a c c e s s delay . 133 vi 7.2.3 Simulat ion results and d iscuss ions 135 7.3 Bandwidth management for integrated PA, Q A and R A traffic 138 7.3.1 PA traffic 139 7.3.2 Q A traffic 139 7.3.3 R A traffic 140 7.4 Summary 141 Chapter 8 Conc lus ions and future research areas 142 8.1 Conc lus ions 142 8.2 Future research areas 144 Bibl iography 146 Appendix A Methods of assigning N s R A slots over a frame of F slots 154 Append ix B A n example to illustrate the a c c e s s delay problem ( n a < N s ) . . 156 Append ix C List of acronyms 157 vii List of Figures Figure 1.1 Appl icat ions of 802.6 M A N s 3 Figure 1.2 D Q D B network configuration 4 Figure 1.3 D Q D B access unit 4 Figure 1.4 The looped bus configuration 5 Figure 1.5 The healing capability of the looped bus configuration 6 Figure 2.1 Max imum voice traffic load for PA a c c e s s . 2 5 Figure 2.2 Max imum voice traffic load for B P A a c c e s s 27 Figure 2.3 Max imum voice traffic load for Q A a c c e s s 29 Figure 2.4 Max imum voice traffic load for F P A a c c e s s 30 Figure 2.5 Max imum voice traffic load for M R A a c c e s s 31 Figure 2.6 Multiplexing gain 32 Figure 3.1 Packet ised Voice Sys tem 35 Figure 3.2 Bi-state voice conversat ion model 36 Figure 3.3 State diagram for R A access 40 Figure 3.4 Upper bound, lower bound and average cl ipping probabilit ies . . 49 Figure 3.5 Percentage of talkspurts having clip durations greater than 50 ms • • • • 50 Figure 3.6 Slot utilization 51 Figure 3.7 Effect of propagation delay on average cl ipping probability (N v =50, N s =25) 52 Figure 3.8 Simulat ion using a real speech signal 54 Figure 4.1 R A a c c e s s controller for contention free operation 61 Figure 4.2 V B R S traffic model 63 Figure 4.3 Mini-source model . 6 4 viii Figure 4.4 P L R of the network by theoretical computat ions (curves) and by simulat ions (points) 73 Figure 4.5 Compar ison of theoretical and simulated P L R relative to station positions 74 Figure 4.6 Mean packet a c c e s s delay (theoretical - curves, simulation -points) 76 Figure 4.7 Standard deviation of packet access delay (theoretical - curves, simulation - points) . 7 7 Figure 4.8 % of reservations with loss durations > LD (theoretical - curves, simulation - points) 79 Figure 4.9 Utilization (theoretical - curves, simulation - points) 80 Figure 4.10 M e a n packet a c c e s s delay for P M S 2 (theoretical - curves, simulation - points) 87 Figure 4.11 Standard deviation of packet a c c e s s delay for P M S 2 (theoretical - curves, simulation - points) . 88 Figure 5.1 Simulat ions with A R model : bit rate trace for the last node . . . 100 Figure 5.2 Simulat ions with M V model : bit rate trace for last node 101 Figure 5.3 P L R of the network for simulating R A a c c e s s with video sources (curves: theoretical computat ions, points: simulations) 103 Figure 5.4 Compar ison of theoretical and simulated P L R relative to station positions for simulating R A access with video sources 104 Figure 6.1 Average P L R for individual V B R I T 111 Figure 6.2 P L R variations across the M A N with voice and V C traffic . . . . 112 Figure 6.3 Average P L R with voice and V C traffic for D B S 120 Figure 6.4 P L R variations across the M A N with voice and V C traffic for D B S 121 I X Figure 6.5 P L R variations across M A N nodes 1-5 for the P R and IR options 122 Figure 6.6 Max imum number of voice cal ls against number of V C cal ls . . 123 Figure 6.7 Compar ison of the P L R with analytical calculat ion for the integration of voice, A R and M V traffic by D B S 124 Figure 6.8 P L R variations across the M A N for the integration of vo ice, A R and M V traffic by D B S 125 Figure 7.1 R A a c c e s s controller for M R A a c c e s s 130 Figure 7.2 Data a c c e s s delay analysis for the slot spreading methods . . 136 Figure 7.3 Data a c c e s s delay variations along the M A N bus 137 Figure A.1 Examp les of the slot spreading methods (The R A slots are marked by "R") 155 J X List of Tables Table 1.1 Types of communicat ion serv ices 7 Table 2.1 D Q D B A C F format 13 Table 2.2 Compar i sons of different a c c e s s methods for transporting V B R I T 34 Table 3.1 Proposed A C F of an R A slot 38 Table 4.1 R A slot format for contention free operation . 58 Table 4.2 Simulat ion parameters for analyzing the performance of R A a c c e s s . 7 1 Table 4.3 Capaci ty improvement for R A a c c e s s . 81 Table 4.4 Compar ison of P M S 1 and P M S 2 86 Table 5.1 Types of video serv ices 91 Table 5.2 M e a n and var iance bit rate of the A R and M V models 98 Table 6.1 Modif ied A C F for D B S \ . 115 Table 6.2 Modif ied Segment Header for D B S 116 Table 6.3 The bit ass ignments for different traffic c l asses 116 Table 7.1 Slot ass ignments for the movable boundary integration scheme 129 Table 7.2 Addit ional simulation parameters for PA, Q A and R A traffic integration . . 132 xi Acknowledgment I would like to express sincere gratitude to Dr. Victor C. M. Leung for his constant guidance and advice in supervising my Ph.D. research and to Dr. R. W. Donaldson for his interest and support in this project. I would also like to thank all members of the examination committee for reviewing my thesis. This research was partially supported by a grant from the Canadian Institute for Telecommunications Research under the NCE program of the Canadian Government, and by a Canadian Natural Sciences and Engineering Research Council Postgraduate Scholarship. Finally I would like to thank my beloved wife, Cindy Chan for her support in my Ph.D. study. xii Chapter 1. Introduction Chapter 1 Introduction 1.1 Development of M A N s The concept of local area networks (LANs) was originated in the 70's for intercon-necting computers into work groups with a typical network size of 5 Km and network speed of 10Mbps. In the late 70's and early 80's, a vast number of LAN protocols were proposed, developed and standardized. In general, these protocols can be classified according to their media access control methods as follows: • Random access — Stations are allowed to transmit packets randomly such that packet collisions or access contention may occur. In case of access contention, affected packets are retransmitted later based on some resolution algorithms e.g. CSMA/CD HI. • Token access — Right of access to the media is controlled by means of tokens e.g. Token ring [2] and token bus [3]. • Scheduling or reservation — Packet transmissions are scheduled in an orderly manner e.g. Fastnet [4]. In the mid-80's, IEEE recognized the need of a metropolitan area network (MAN) standard for interconnecting LANs and other communication systems dispersed over a city area (typically in the range of 50-200Km in diameter) in order to provide integrated communication services such as voice, data and video [5]. Consequently a 802.6 committee was set up to develope such a standard which forms part of a family of the 802.x standards for LANs and MANs. In 1990, the 802.6 committee adopted the Dual Queue Dual Bus (DQDB) as the 802.6 standard [6] for MANs based on the QPSX proposal originated by the University of Western Australia [7, 8]. In terms of the above classifications, DQDB MAN is based on a scheduling mechanism. The objective of the DQDB protocol is to form a distributed queue among the MAN nodes such that 1 • Chapter 1. Introduction packet transmissions can be coordinated in a first come first served (FCFS) manner. A major advantage of the DQDB protocol is that it can provide 100% channel utilization irrespective of the network size and propagation delay whereas this desirable feature cannot be achieved by most of the previous LAN protocols due to contentions and control overheads. Following the adoption of the MAN standard, extensive trial runs had been conducted throughout the world [9, 10, 11, 12, 13, 14]. In 1992, Bellcore launched a commercial Switched Multimegabit Data Service (SMDS) which deployed 802.6 MAN to provide customer, access to SMDS [15]. The original 802.6 standard was also further enhanced via the SMDS specifications. MCI, the second largest carrier in the USA also decided to use DQDB for its country-wide backbone system which will allow it to interconnect the local access and transport areas [9]. 802.6 MAN has also received wide attention in Europe and other parts of the world. For examples, the first MAN in Europe was installed in Denmark for Nordisc A/S (one of the world leaders in biotechnology) in 1991 [9], a pilot MAN service has been introduced in Italy since 1991 [9], British Telecom has been developing a Switched High speed Data Service similar to the SMDS [14], a European SMDS interest group has been formed to work on an European version of the SMDS specification [16], an ESPRIT project has been underway to develope a multi-DQDB MAN solution that is capable of carrying out distributed switching at up to 1.2 Gbit/s [17]. Using the same packet (cell) size as broadband integrated services digital networks employing asynchronous transfer mode (ATM/BISDNs), 802.6 MANs are also expected to function as broadband multiplexers to facilitate the interconnection of various corporate and public networks with the emerging ATM/BISDNs, effectively serving as peripheral gathering networks of end user traffic for transport over ATM/BISDNs [18, 19]. It is commonly believed that the development of MANs is the first arid very important step 2 Chapter 1. Introduction Enterprise network service Broadband multiplexer for BISDN Figure 1.1. Applications of 802.6 M A N s to facilitate the evolution of existing networks into BISDNs. This important networking application of M A N s has been recognized since the early development stage of the M A N standard resulting in the adoption of the A T M cell format for the M A N slots. In addition to being deployed for the above applications, 802.6 M A N s have also been proposed as distributed switches for the third generation mobile communication networks and future wireless personal communication networks (PCNs) [20, 21]. These MAN-based PGNs enable efficient call handoff management and distributed call processing functions, provide connection oriented and connectionless transport facilities, allow priority transport of signaling traffic, and facilitate internetworking with ATM/BISDNs [20, 21, 22, 23]. In summary, the applications of MANs are illustrated in Figure 1.1. While the existing M A N standard has focused on supporting connectionless data traffic, development of efficient transport techniques for connection oriented real-time 3 Chapter 1. Introduction H e a d of b u s A B u s A H e a d of , b u s B B u s B Figure 1.2. DQDB network configuration traffic over MANs is of primary importance because of the vital role of MANs in the above networking applications and the emergence of multimedia communication services. 1.2 IEEE 802.6 M A N s In an IEEE 802.6 MAN [6], communication nodes are connected to two unidirectional slotted buses, called bus A and bus B as shown in Figure 1.2. The physical layer specified in [6] supports a wide range of transmission speeds including but not limited to 34.368 Mbps and 139.264 Mbps (CCITT G.703); 44.736 Mbps (ANSI DS3) and 155.520 Mbps (CCITT G.707-9 SDH). In this thesis, we consider each of the bus running at 155.520 Mbps which is also the commonly used bus speed in the literature. Each node has read and write access to each bus through an access unit as shown in Figure 1.3. Data BUS A/B R e a d Write -x x BUS A/B OR l — • pass i ve or act ive A C C E S S UNIT Figure 1.3. DQDB access unit 4 Chapter 1, Introduction Head of bus A and bus B 0 Start of data flow • End of data flow NODE • NODE t 4 Figure 1,4. The looped bus configuration is written to the bus through a logical or operation between the data from the upstream nodes and the data from the access unit. The read operation allows data to be copied from the bus without effecting the writing operation. The two buses support full duplex communications in opposite directions between any pair of nodes in the network. A special node called the head of bus (HOB) generates 53 byte, time slots continuously at the head end of each bus for access by the downstream nodes. Each slot carries a fixed-length packet or cell, the basic unit of data transfer, consisting of a 1-octet access control field (ACF) for controlling access to the slot, a 4-octet segment header with control information for the segment data, and a 48-octet segment payload carrying the user's data. To enhance the reliability of the network, a looped bus topology (see Figure 1.4) has also been specified in the current standard as an alternative to the above dual bus configuration. In the looped bus configuration, the HOBs are collocated but without an actual data connection. It facilitates fault isolation by closing the data buses through the head point of the loop. Effectively this reconfiguration action moves the HOB functions Chapter 1. Introduction NODE NODE 0 Start of data flow • End of data flow NODE NODE Head of cable break H e a d o f bus A / bus B Figure 1.5. The healing capability of the looped bus configuration to the nodes adjacent to the cable break so that data transmissions can be continued (See Figure 1.5). The 802.6 standard specifies in details a queue-arbitrated (QA) access method employing the DQDB protocol to support asynchronous data transport and outlines a pre-arbitrated (PA) access method to provide isochronous transport service. Other services such as connection oriented data service may also be included in the future version of the standard subject to further study. For QA access, three priority levels have been assigned but the priority protocol is pending further study. A bandwidth balancing method has also been included in the standard for QA access to facilitate the fair sharing of bandwidth in particular during network overload. An overview of PA and QA access and their latest developments will be given in chapter 2. 1.3 Service integration over IEEE 802.6 M A N s Emerging ATM/BISDNs will support four main classes of communication services as shown in Table 1.1 using different protocols for the ATM adaptation layer (AAL) [24]. This list can also be taken as a guide for the traffic classes that should be supported by 802.6 MANs. Class A services are best supported by PA access which emulates the Chapter 1. Introduction Table 1.1. Types of communication services Class A -Constant bit rate (CBR) isochronous traffic B -Variable bit rate (VBR) isochronous traffic C -Connection oriented (CO) data traffic D -Connectionless (CL) data traffic Connection mode Connection oriented Connection oriented Connection oriented Connectionless Data type Streams Streams Packets Packets Bit rate Constant Variable Variable Variable Sender/receiver timing relation Yes Yes No No Example H.261 video VBR voice and video' Fax Electronic mail Transport requirements Require CBR isochronous channels Require VBR isochronous channels Require guaranteed bandwidth but not necessarily isochronous channels Accept best effort service ATM Adaption Layer AAL 1 AAL 2 AAL 3 or 5 AAL 4 or 5 Proposed transport methods in IEEE 802.6 MANs PA access [6] RA access as proposed in this thesis QA access with GBP [25] QA access [6] conventional circuit switching method. QA access are well suited for transporting Class D traffic due to its asynchronous nature. Transport for Class B and Class C traffic are not addressed in the current MAN standard. Meanwhile a guaranteed bandwidth protocol (GBP) [25] has been proposed to work with QA access for supporting connection oriented data traffic (Class C) over IEEE 802.6 MANs. In combination with a traffic shaping mechanism similar to the well known leaky bucket algorithm, this protocol provides a guaranteed bandwidth by allowing users to send multiple packets at the highest priority 7 Chapter 1. Introduction level of the DQDB protocol or QA access. In this thesis, we study the transport of the Class B traffic which is referred as the variable bit rate isochronous traffic (VBRIT) since ideally it requires variable bit rate isochronous.channels. The main disadvantage of transporting VBRIT by PA access is bandwidth wastage as capacity has to be preallocated based on the peak data rate of the traffic sources. This bandwidth wastage can be extremely large if the traffic source is very bursty (i.e., large peak to mean bit rate ratio). To ameliorate the capacity wastage, a bi-state PA scheme [21, 22] has been proposed which turns the PA slots "on" and "off based on the bit rate of the traffic sources so that idle PA slots can be released for QA traffic. However this method still cannot provide statistical multiplexing among VBRIT. While QA access allows full statistical multiplexing for VBRIT, it suffers from access delay variations and access unfairness. Although the access delay of VBRIT can be minimized by transporting this time sensitive traffic at a higher priority level using an enhanced priority mechanism [26], guaranteed access delay and bandwidth cannot be provided. While QA access with GBP [25] can guarantee bandwidth, it still cannot guarantee access delay and provide the required variable bit rate isochronous channels. With the advent of multimedia communication applications such as video conference, video telephony and image data, demand for VBRIT over MANs will become substantial. For example current digital compression and micro-chip technologies are capable of supporting most multimedia applications at nx64Kbps with n typically less than or equal to 30 (i.e. 2Mbps) [27, 28]. Some typical examples are: 64Kbps voice/audio, 2x64Kbps video telephony, 6 x 64Kbps video conference and 24 x 64Kbps MPEG video. It is expected that these applications will create a high-revenue market in the area of personal communications and broadband networking in the near future. For example, the initial phase of the mobile communications programme df RACE in Europe is to develope technologies for supporting various kinds of personal communication services below 2Mbps [29]. Hence . 8 Chapter 1. Introduction an efficient transport mechanism for multiplexing VBRIT over MANs is of priminary importance. 1.4 Reservation protocols for transporting VBRIT Due to the isochronous nature of VBRIT, a reservation based technique should provide a more effective transport solution. In fact the reservation protocols proposed in [30, 31] for voice transport over LANs/MANs can be adapted easily for transporting VBRIT over dual bus MANs. These protocols work in a similar manner where the active voice stations are allowed to make reservations on a reverse channel. Based on the reservations, sufficient slots are reserved for the active voice stations in subsequent frames and each of the active voice station transmits its packet in the first available slot every frame. While these reservation protocols provide bounded access delay, guarantee bandwidth and allow full statistical multiplexing, they have the following limitations: 1. Service is unfair to the downstream voice stations because slots are reserved by a "greedy" approach or 1-persistent type of operation. The unfairness problem results in overdesign for and inefficient use of network bandwidth. 2. Access is not isochronous even after a reservation is secured because all active stations acquire the first available slot in each frame which may vary in different frames. 3. They are not compatible to the slot format of the current MAN standard hence they cannot be implemented easily in the standardized 802.6 MANs in a backward compatible manner. 4. The exact mechanism to support multiple number of VBRSs at a MAN node and to integrate heterogeneous VBRIT over MANs have not been addressed. Meanwhile a reservation protocol called Packet Reservation Multiple Access (PRMA) has been proposed by Goodman et. al. [32] to multiplex voice calls between a base station and dispersed mobile terminals in the future mobile communication networks. PRMA allows an active voice station to capture a voice channel by random access, reserve the 9 Chapter I. Introduction captured channel for the duration of the talkspurt and release the reserved channel at the end of the talkspurt. This protocol has received wide attention because of its capability to enable statistical multiplexing while providing isochronous voice transport service. In fact, an enhanced version of the PRMA has been chosen as the wireless medium access protocol for the RACE project in Europe [29]. The advantages of PRMA for supporting bursty voice traffic has been verified extensively by different performance studies including simulations [32], equilibrium point analysis [33] and Markov chain analysis [34]. This access method can also be used to facilitate voice and data integration [35, 36] and to support video/multimedia traffic [37, 38]. Unfortunately PRMA is designed to work in a centralized architecture hence it cannot be implemented directly in a distributed architecture such as MANs. 1.5 A i m and objectives Motivated by PRMA [32] and the reservation protocols in [30, 39, 31], the aim of this thesis is to develop a reservation arbitrated (RA) access method for transporting VBRIT over dual bus MANs in general and 802.6 MANs in particular. This thesis is based on our work reported in [40, 41, 42, 43, 44, 45, 46, 47, 48]. Our focus is to develop a reservation protocol that can provide variable bit rate isochronous channels and overcome the limitations of the previous reservation protocols for LANs/MANs described in the last section. Our work can also be viewed as the extension of the well known PRMA protocol to a distributed architecture. A typical and important application of our research result is to facilitate the efficient transport of real time traffic over MAN-based personal communication networks [43, 45] and enterprise networks [41]. Specific objectives of this thesis are given as follows: 1. To propose a RA access protocol for transporting VBRIT over dual bus MANs in general and 802.6 MANs in particular. . 10 Chapter 1. Introduction, 2. To analyze the performance of RA access with theoretical methods and computer simulations. 3. To evaluate different methods and associated connection admission control (CAC) mechanisms for multiplexing heterogeneous VBRIT over MANs. 4. To propose and analyze an efficient integration scheme for integrating RA traffic with existing PA and QA traffic. 1.6 Organization of the thesis Chapter 2 gives an overview of the PA and QA access methods and their current developments. The concept of RA access is also introduced. The advantages and disadvantages of PA, QA and RA access for transporting VBRIT are discussed and compared through a voice traffic capacity problem. Chapter 3 introduces the RA access method by analyzing the simplest 1-persistent RA access protocol for transporting bursty voice traffic. System performance is analyzed by both theoretical methods and computer simulations. Simulation results based on a real voice signal are also presented. The numerical analysis establishes the upper and lower bound performance targets that can be achieved by other waste free bandwidth acquisition methods. Chapter 4 proposes a novel contention free RA access scheme with a new bandwidth acquisition method called cyclic capturing. This protocol enhances the 1-persistent RA access scheme in terms of access fairness in particular. Detailed performance studies including packet loss ratio, packet delay, delay jitter, probability distribution of consecutive packet loss and channel utilization are carried out by both theoretical computations and computer simulations using a mini-source model. Chapter 5 extends the performance analysis in chapter 4 by simulating the RA access protocol with two different video source models to further demonstrate its effectiveness for transporting VBRIT. 11 Chapter I. Introduction Chapter 6 presents and evaluates three different methods : uncontrolled bandwidth sharing, dynamic bandwidth partitioning and dynamic bandwidth sharing for RA access to multiplex heterogeneous VBRIT over a MAN. The associated CAC mechanisms are also analyzed and compared. Chapter 7 proposes and analyzes a movable boundary integration scheme for inte-grating PA, QA and RA traffic efficiently over a MAN. It also discusses the bandwidth management strategy for the integrated traffic. Chapter 8 concludes the thesis and outlines future research problems. 12 Chapter 2. Overview of PA, QA and RA access Chapter 2 Overview of PA, QA and RA access PA, QA and RA access represent three fundamental types of transport methods. The aim of this chapter is to give an overview of these transport methods and discuss their advantages and disadvantages for transporting VBRIT. We also evaluate their voice capacities under an integrated voice and data traffic environment. 2.1 PA, QA and RA a c c e s s The IEEE 802.6 MAN standard [6] employs a slot structure that is compatible to the ATM cell format. Each slot is 53 bytes long with a 5-bytes header and a 48-bytes information field. The first bytes in the header constitute the access control field (ACF) as shown in Table 2.1. Two access methods called PA access and QA access have been specified in the MAN standard as discussed below. Table 2.1. DQDB ACF format BUSY SL_TYPE PSR RESERVED REQO REQ1 REQ2 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit 2.1.1 PA access The purpose of PA access is to provide CBR isochronous transport service which emulates conventional circuit switching technique. Each PA slot is indicated by BUSY=1 and SL_TYPE=1 in the ACF. and the proposed frame period is 125 /is. In the original MAN standard [6], a PA slot can be shared by different traffic sources so as to minimize packetization delay (i.e., the required time to generate sufficient data bits for filling the designated positions in the slot payload). For example, a PA slot can accommodate a maximum of 48 64Kbps voice calls with each voice call occupying 1 byte (or octet) in the information field. To provide isochronous channels, the HOBs write the VCIs into the same slots in successive frames. Each individual user identifies its slot within a frame based on the VCI in the PA segment header and access the information field 13 Chapter 2. Overview of PA, QA and RA access according to the preassigned offset position.. Although PA access can provide perfect isochronous transport service, its efficiency is low if the traffic source is bursty. The wastage is due to [22]: (i) information field left empty by completed calls and not yet assigned to new calls, (ii) unassigned information fields in the higher octal positions, and (iii) capacity left vacant when a traffic source is not transmitting at its peak bit rate. To overcome the first wastage problem, a repacking scheme has been proposed in [22]. In this scheme, ongoing calls are reassigned to fill up the empty information fields at the end of each frame in order to reduce the total number of isochronous slots required in the next frame. However its implementation is very complex because VCIs are required to be changed frequently at the end of each frame. In the latest proposal [49], PA access has been modified such that a PA slot is occupied by a single traffic source only. This eliminates the above wastage problem (i) and (ii) and is more consistent with the ATM approach where each ATM cell belongs to a single traffic source to facilitate cell switching. However this change introduces longer packetization .delay especially if the bit rate of the traffic source is low. For example, to transport 64Kbps voice traffic using the original PA method, the packetization delay is 125 /us whereas in the new PA access scheme, the packetization delay is increased to 6ms. We would like to emphasis that the problem of packetization delay is due to the use of a 48 byte pay load in consistent to that of an ATM cell but not the limitation of an access method. Hence all other access methods (e.g. the later QA and RA access) employing the slot-per-call approach suffers the same problem which is inevitable in order to be consistent with the ATM cell format. In fact this problem is well known in the ATM standardization committee. The 48 byte cell payload was chosen as a compromise between the requirement of low packetization delay for isochronous traffic and high transport efficiency for data traffic. We assume that the packetization delay is acceptable 14 Chapter 2. Overview of PA, QA and RA access in this thesis. The frame period of the new PA access method is still 125 fis and the generation of PA slots are in the form m PA slots every n frame. For example, to support 64Kbps voice traffic, 1 PA slot is generated every 48 frames (i.e. 48x125 fis = 6ms) for each voice source. That means as far as a 64Kbps voice source is concerned, the frame period is effectively ypA=6ms. The advantage of using PA access for transporting VBRIT is its capability to, provide perfect isochronous transport service. Moreover call admission control, traffic policing and billing management can be greatly simplified as capacity is allocated based on the peak rate of each call. However it is not efficient in terms of bandwidth utilization because of the mentioned wastage problems. Although the wastage problem (i) and (ii) are eliminated in the new PA access scheme, it is still inefficient if the traffic source is bursty. For example, it is well known that the activity factor for voice is around 40%, so that using PA access for transporting voice results a low bandwidth utilization of 40%. The wastage becomes even more significant for video traffic which has higher peak to average bit rate ratio. 2.1.2 Bi-state PA access To improve the efficiency of PA access for transporting VBRIT, a bi-state PA scheme (BRA) was proposed in [21, 22] to release the unused capacity to the data (QA) traffic. In this scheme, each traffic source uses a whole slot for transmission as the new PA access method. Consider that the bit rates of the VBRS are varied in the form nx64Kbps, the proposed frame period is /RPA=6 ms such that a 64 Kbps VBRS can fill up the 48 bytes information field every frame. To recover the unused capacity among NPA PA slots, \NPA/{4:8 x 8)] active/idle (a/i) slots are used to determine whether a PA slot is still required by the respective VBRS in the next frame. The operation is explained as follows. During call establishment, the HOBs assigns an a/i slot and a corresponding a/i bit position in the a/i slot for each PA slot. The respective VBRS then informs the 15 Chapter 2. Overview of PA, QA and RA access HOBs whether a PA slot is still required in the next frame by setting the appropriate flag (1 required, O:not required) in the corresponding a/i bit position. When a PA slot is not required as indicated by a 0 a/i bit, the HOB turns it to a QA slot. The PA slot wijl be resumed once the respective VBRS requires the slot again by setting a/i=l in the corresponding bit position. Note that when a. PA slot is turned to a Q A slot, the logical connection is still maintained so the original VCI does not need to change. Compared to PA access, BPA access improves bandwidth utilization by releasing unused capacities to the data traffic while maintaining the advantage of isochronous transport service. Effectively this provides best effort service to the Q A traffic through the residue bandwidth of the PA traffic in a manner similar to the A T M available bit rate service. However this method still cannot provide statistical multiplexing capability for the VBRIT which may demand a high percentage of the M A N bandwidth with the advent of various multimedia services. That means BPA access is only useful if data traffic but not VBRIT dominates the M A N traffic otherwise the released capacity may not result significant capacity improvement. Furthermore this method requires the use of a/i slots which reduces the usable bandwidth and increases protocol complexity. 2.1.3 Q A access The purpose of QA access is provide packet switching in a fair and distributive manner. A n idle QA slot is indicated by BUSY=0 and SL_TYPE=0 in the A C F . When a node transmits a QA segment into an idle QA slot, it sets the B U S Y bit to 1. Among the 48 bytes in segment payload, only 44 bytes are the actual information fields. Due to the connectionless nature of QA access, the other 4 bytes (2 bytes header and 2 bytes trailer) are used for various control purposes such as to provide the logical linking between a segment and its corresponding data source by means of the multiplexing identifiers in the 2-byte header [6]. Access to QA slots is governed by the DQDB protocol which purpose is to form a distributed queue such that QA segments arriving in different M A N nodes 16 Chapter 2. Overview of PA, QA and RA access can be served in a manner as close to a FCFS queue as possible: To effect this protocol, three request (REQ) bits are assigned in the A C F for coordinating the Q A segment transmissions. While three REQ bits are assigned in the current standard for providing three priority levels, only one is active because the priority control mechanism for DQDB is pending further study. To implement the DQDB protocol, each node maintains a request counter (RQ_CTR) and a countdown counter (CD_CTR) which purposes are to record the number of outstanding requests from the downstream nodes and the number of outstanding transmission requests from the downstream nodes registered before the arrival of current QA segment, respectively. A node is in the idle state if it has no segment to transmit; otherwise it is in the countdown state. The protocol operation at a M A N node is summarized as follows: 1. In the idle state, the RQ_CTR is incremented by one for each request (i.e., REQ=1 in the ACF) received in the reverse bus, and decremented by one down to a minimum value of zero for each idle QA slot (i.e., BUSY=0 in the ACF) passing to the downstream nodes on the forward bus. 2. Each node stores its incoming QA segments in a buffer. If a Q A segment arrives during the idle state, the node (a) transfers the current value of RQ_CTR to CD_CTR, (b) resets the RQ_CTR to zero, (c) enters countdown state and (d) sets the first available REQ bit in the reverse bus. 3. In the countdown state, the RQ_CTR is incremented by one for each request received in the reverse bus and the CD_CTR is decremented by one down to a minimum value of zero for each empty slot passing to the downstream nodes. 4. When CD_CTR reaches zero in the countdown state, the node is allowed to transmit the first segment in its data buffer. If the data buffer is not empty, the node repeats actions (a)-(d) in step 2 for the next segment; otherwise it returns to the idle state. Note that in the above protocol operation, each node cannot generate a request for a new 17 Chapter 2. Overview of PA, QA and RA access segment until the previous segment has been transmitted. The reason is to provide a round robin service to all M A N nodes independent of their data loads. Unfortunately the DQDB protocol only behaves as a FCFS queue under zero propaga-tion delay and infinite request bandwidth (i.e., the ideal condition) [50]. If this ideal con-dition is not satisfied, unfairness problem occurs in which the access delay and throughput of a node is strongly dependent on its relative position in the M A N bus [51, 52, 53, 54, 55, 56, 57]. The degree of unfairness depends on the network size, propagation delay and message sizes and may become intolerable when data load is high. To alleviate the unfairness problem in particular during network overload, a bandwidth balancing (BWB) mechanism has been included into the current M A N standard based on the proposals in [58, 59] at the expense of bandwidth wastage. It requires each node to maintain a BWB counter (BWB_CTR) which is increased by one for each transmitted segment. When BWB_CTR reaches a pre-defined number called bandwidth balancing modulus (BWB_MOD), it is reset to zero and RQ_CTR is incremented by one to allow an ex-tra empty slot to pass downstream. As this extra slot may not be used by downstream nodes, capacity wastage may. occur. Under network overload, the BWB mechanism can guarantee (after a transient period) a predefined bandwidth ratio to each node by using an appropriate B W B _ M O D value. The transient period can be shortened by choosing a small B W B _ M O D ; however it also increases the capacity wastage. The default B W B _ M O D value as specified in the current standard is eight. Although the BWB mechanism im-proves fairness during network overload, it causes capacity wastage, increases access delay during network underload, reacts slowly to changes of the traffic load (i.e., slow convergence to steady state) and does not work well under multi-priority traffic [50]. Besides the BWB mechanism, many other mechanisms for improving fairness have also been proposed in the literature. The followings are some representative examples. Muk-erherjee and Banerjee proposed three alternative solutions: proportional scheme, FCFS 18 Chapter 2. Overview of PA, QA and RA access . • message queue based DQDB scheme and message queue with proportional assignment scheme to improve the fairness in DQDB M A N s [60]. The first scheme adjusts the B W B _ M O D of a node based on the offered load of the node, the second scheme allows each node to generate multiple requests for all the segments in its buffer and the third scheme is a combination of the first two. An access protection and priority control scheme was proposed in [61] to keep the bandwidth allocation to each node within predefined limits. This is done by limiting the initial CD_CTR values within some preassigned values. A cycle compensation scheme was proposed in [62] to achieve fair bandwidth al-location based on the cycle concept. Normally each node can only transmit one segment per cycle. However if a node misses its turn in a cycle, it will be allowed to transmit more than one segment in subsequent cycles based on a compensation mechanism. A no slot wasting bandwidth balancing mechanism (NSW_BWB) was proposed in [63]. To implement NSW_BWB, one of the reserved bit in the A C F is designated as the TAR bit. The BWB_CTR operation is similar to that in BWB except that when the BWB_CTR of a node reaches its B W B _ M O D value, the node sets the next available TAR bit to one instead of raising its RQ_CTR by one. When a downstream node which has an enqueued segment detects a slot with TAR=1, it resets the TAR bit to zero and generate extra request to the upstream nodes subject to the condition that the rate of resetting TAR bits does not exceed the rate of generating TAR bits to the downstream nodes. Extra counters are used to maintain this condition. NSW_BWB ensures that a slot passed to downstream nodes by the BWB operation is not wasted thus a low B W B _ M O D value can be used to shorten the transient time to reach steady state. To enable the lightly loaded nodes to use the TAR bits more effectively and improve their delay performance, NSW_BWB has been further enhanced in [64, 65] by means of extra counters. Recently other fairer distributed queuing protocols (e.g. [66]) have also been proposed. They have the potential to replace DQDB protocol in future high speed (Giga-bit/s) M A N s . 19 Chapter 2. Overview of PA, QA and RA access Although the current 802.6 standard specifies three priority levels for Q A access, the exact priority control mechanism is pending further study because the original priority protocol only works under ideal condition (i.e., zero propagation delay and infinite request bandwidth) [50]. Under non-ideal conditions, its effectiveness is not guaranteed and in some circumstances lower priority traffic may even have better performance than higher priority traffic (e.g., when a low priority heavy loaded station is located upstream of a high priority lightly loaded station) [54]. To overcome these problems, other priority mechanisms have been proposed in recent years. Following the BWB proposal which is adopted in the current 802.6 standard, Hahne proposed three priority schemes in [67]. However the schemes in sections 5 and 6 of [67] cannot provide the absolute prioritized access and does not work if the BWB mechanism is disabled. Although the priority scheme in section 7 of [67] can overcome the above limitations, its operation requires significant changes to the A C F format. A pre-emptive priority scheme was proposed in [68] to disallow the transmissions of lower priority segments for as long as there are higher priority segments in the network. By using the two reserved bits in the A C F , the proposal requires each node to inform the upstream nodes the highest priority segments in its buffer so that lower priority traffic can be shut off accordingly. However this priority protocol may cause capacity wastage and the important issue of fair bandwidth allocation under multi-priority traffic was not addressed. Karvelas proposed another priority mechanism in [26] which works in conjunction with the bandwidth balancing mechanism NSW_BWB as discussed above. The basic idea is that when a message of K segments arrives, the respective node generates K requests for each lower priority traffic. This causes the lower priority request counters in the upstream nodes to increase by K so that lower priority traffic can be preempted. In combination with the NSW_BWB mechanisms described above, fair bandwidth allocation can also be provided under multi-priority traffic. However its implementation is more complex than the current BWB mechanism. 20 Chapter 2. Overview of PA, QA and RA access While QA access has been designed for transporting connectionless data, it has also been considered for transporting VBRIT due to its simplicity and statistical multiplexing capability. For example, Goodman has examined a QA scheme to transport bursty voice traffic (the most basic type of VBRIT) over M A N s in combination with the P R M A protocol for the third generation mobile communication network [20]. In this case, the frame interval is /QA = 5.5 ms such that a 64 Kbps voice source can fill up the 44 bytes information field in a QA slot every frame. As in PA access, a VCI is allocated to each voice call during call set up, the voice packets are then transported via Q A access with the assigned VCI. Although QA access allows VBRIT to be multiplexed statistically thus optimizing the bandwidth utilization, it cannot guarantee access delay and is subject to access delay variations (time jitters). Moreover the performance of a variable bit rate isochronous source (VBRS) is strongly dependent on its location in the network and may be seriously affected by other traffic due to the unfairness problem of the DQDB protocol. While the current BWB mechanism can improve fairness, it causes capacity wastage and only works under a single priority class of traffic. As it is likely that VBRIT should be transported at a higher priority level than the data traffic, the current BWB mechanism cannot be easily employed. By using adaptive BWB mechanisms (i.e. assigning different B W B _ M O D values to different traffic) [60], the bandwidth distributed to each VBRS can be controlled so that different quality of services may be offered. However it has been found that the GBP [25] generally works better than the adaptive BWB mechanisms in distributing the network bandwidth to users. Unfortunately like the adaptive BWB mechanisms, GBP still cannot guarantee access delay and provide variable bit rate isochronous channels. Similarily while access delay can be minimized by transporting time sensitive VBRIT at a higher priority level using an effective priority mechanism, guaranteed access delay and variable bit rate isochronous transport service still cannot be provided. 21 Chapter 2. Overview of PA, QA and RA access 2.1.4 RA access The aim of R A access is to combine the advantages of PA and Q A access so that isochronous channels can be provided while maintaining statistical multiplexing capability. It works in the same principle as the reservation protocols in [30, 31] except that significant enhancements will be made in this thesis for improving access fairness, providing isochronous service and facilitating the implementation over IEEE 802.6 M A N s . Each R A slot, whose detail format will be discussed in later chapters, is 53 bytes long comprising a 5-byte header and a 48-byte information field. As in PA access, the frame period is f^ = 6ms. Consider that the bit rate of each VBRS varies at nx64Kbps, the basic concept of RA access is explained as follows. When a VBRS X increases its bit rate by 64Kbps, it first captures an available R A slot on the forward bus and then request for a reservation via the reverse bus. Upon receiving the reservation request, the respective HOB reserves the captured slot for VBRS X in subsequent frames as PA access so that isochronous channels can be provided. Note that if propagation delay is large, contentions may occur in which two VBRSs in different M A N nodes try to reserve the same slot. Nevertheless we shall show in chapter 3 that this contention problem can be resolved by a simple resolution mechanism. In fact under the typical coverage area of a M A N , this problem can be eliminated by setting the operation parameters appropriately as shown in chapter 4. When the bit rate is decreased by 64Kbps, VBRS X releases the captured slot. The aim of this thesis is to develop a R A access protocol to realize the above concept in a fair, distributive and efficient manner. For the analysis in this chapter, we assume that such a R A access protocol is available in order to discuss its capacity advantage through numerical analysis in the next section. In general, two types of R A access are realizable: fixed boundary R A (FRA) access and movable boundary R A (MRA) access. In FRA access, the HOB pre-allocates a certain number of R A slots for the VBRSs. When a VBRS acquires a free R A slot, 22 Chapter 2. Overview of PA, QA and RA access it can use the slot for packet transmissions immediately. Although F R A access allows VBRIT to be multiplexed statistically while maintaining isochronous transport service, it does not allow statistical multiplexing between QA and R A traffic. For M R A access, R A and Q A traffic shares the slots on a movable boundary basis. A slot is assigned to the Q A traffic unless it is acquired by the R A traffic. VBRSs still capture and reserve slots based on the R A access protocol but delay the packet transmissions until the slot has been reserved by the HOB. At the expense of additional access delay, M R A access allows statistical multiplexing between the R A and QA traffic while maintaining the advantages of F R A access. We shall develop M R A access in chapter 7.. 2 . 2 Evaluation of voice traffic capacity To facilitate the comparison of the transport mechanisms described in the last section, we consider the following voice traffic capacity problem which is an extension of the analysis in [22]. In the problem, there is a M A N with an available bandwidth of Bt = 200 Mbps (bus A and B) for voice and data integration. Each voice source has a voice activity factor of r=0.4 (i.e., the fraction of time it is in the active state is 0.4). The voice traffic load which is defined as the ratio of the call arrival rate to the call departure rate is A (erlang). The objective of the problem is to evaluate the maximum voice traffic load for each of the transport mechanisms subject to the following constraints: (i) Mean data bandwidth of at least E[5^] is provided. (ii) The voice call blocking probability must be maintained within 0.01. (iii) At any time t, the bandwidth available for the voice traffic on each bus is at least rNv where Nv is the number of voice calls admitted in the network at time t. Note that because of the duplex nature of voice conversations, the effective maximum bandwidth for the voice calls is Bv = Bt/2 = 100 Mbps. 23 Chapter 2. Overview of PA, QA and RA access 2.2.1 PA access As there is no multiplexing between voice and data traffic, bandwidth of E[Bd] must be pre-allocated for the data traffic as QA slots in order to satisfy criteria (i). The remaining number of PA slots available for the voice traffic is then given by NPA = fPAx(Bt-E[Bd])/2 53x8 where [^ J denotes the largest integer less than or equal to x. Define P~1 (Z) as the maximum traffic load which satisfies criteria (ii) given that the maximum number of allowed users is Z. Based on the well-known Erlang B formula (e.g., see page 179 of [69]), the following equation can be found: P-HZY7JIZ\ v — ^ = 0.01 (2.1) j=0 The value of P l(Z) can be evaluated numerically by Newton's method [70]. The maximum voice traffic load for PA access is then given by APA = P-fPAx(Bt-E[Bd})/2 53 x 8 (2.2) Note that as each voice call is assigned an exclusive PA slot on each bus, criteria (iii) is always satisfied. Figure 2.1 shows the maximum voice traffic load for PA access under different Bt. It can be seen that the maximum voice traffic load decreases linearly with respect to the required data bandwidth. 24 Chapter 2. Overview of PA, QA and RA access PA 1800 0.3 0.4 0.5 0.6 0.7 Required data utilization (fraction of Bt) Figure 2.1. Maximum voice traffic load for PA access 2.2.2 Bi-state PA access If the voice traffic load is A and the assigned voice bandwidth is Bv, the average number of voice calls in progress is [22]: NBPA ( 1 (2.3) n=0 CBPA = £ nP{CBPA = n} = A . ^ E A>/j\ 3=0 where NBPA is the maximum number of bi-state RA slots per frame given by \ AN*™/NBPAl V [Bv x /BPA/(5% x 8)J. As A is constrained by criteria (ii), the second term inside the bracket in (2.3) is less than 0.01 hence CBPA is approximately equal to A. The mean utilized bandwidth for bi-state PA, UBPA, is given by [22]: _ = 2 ( 5 3 x 8 ) f r _ + ^ 1 \ = 569Qi A. h 48 x 8 (2.4) 25 Chapter 2. Overview of PA, QA and RA access assuming | CBPA/(^S X 8)] = C BP A/{48 X 8) and substituting r=0.4 (voice activity factor) and CBPA ~ A. Note that the second term inside the bracket in (2.4) is due to the bandwidth consumed by the a/i slots. To provide mean data bandwidth E[Bd] (i.e. criteria (i)), Bt — 56901A > E[Bd]. Combining with criteria (ii) and using the same notation as above, ABPA = Mm(p-1(NBPA),(Bt-E[Bd]/m01)). (2.5) Note that a higher traffic load cannot be achieved by pre-allocating certain band-width ^Bt, 0<7<1, for the data traffic first because the second term in (2.5) becomes ((1 — 7) x Bt — (E[Bf\ — 75<))/56901 which is constant relative to 7; however, the first term may be reduced because less voice bandwidth is available. Hence the best strategy is to allocate all the bandwidth for voice first. This argument is also applicable for QA and M R A access. Note also that criteria (iii) is always satisfied for the same reason as PA access. Figure 2.2 shows the maximum voice traffic load for BPA access under different Bt. As expected, the maximum voice traffic capacity for BPA access does not decrease immediately when E[Bd] exceeds zero. This is because criteria (i) can still be satisfied with the unused PA slots when E[Bd] is small, hence (2.5) is only limited by the first term. 26 Chapter 2. Overview of PA, QA and RA access BPA 18001 1 1 1 1—= 1— Required data utilization (fraction of Bt) Figure 2.2. Maximum voice traffic load for BPA access 2.2.3 Q A access We assume that voice is transported by QA access at a higher priority level than data using a preemptive priority mechanism such that data can only utilize the residual bandwidth of voice. If N Q A is the maximum number of QA slots per frame available for the voice and data traffic given by [Bv x fqA/(53 x 8)J, the maximum number of voice users NMAX that can be supported is NQ^/r = 2 .5NQA in order to satisfy criteria (iii). Here we assume that NMAX =2NQA to account for the unfairness problem of the DQDB protocol. Note that we shall use the same multiplication factor of 2 in R A access to maintain a fair comparison. 27 Chapter 2. Overview of PA, QA and RA access The mean utilized bandwidth for the QA scheme with a traffic load of A erlang is [22]: 2(53 x 8 x r) x CQA = 61673A (2.6) IQA noting the same argument as bi-state PA access that the average number of conversation in progress is CQA ~ A. To maintain a mean data bandwidth of E [ 5 J , Bt — 61673A > E[Bj]. The maximum possible voice traffic load is given by noting that the maximum allowable voice conversations is NMAX = 2NQA-Figure 2.3 shows that as in BPA access the maximum voice traffic capacity for QA access does not drop immediately when E[5^] exceeds zero because the data traffic can still reclaim all of its required bandwidth from the unused voice capacity. Compared to BPA access, QA access allows a higher initial maximum voice traffic load because of its full statistical multiplexing capability. A*QA = Mzn(p-1(2NQA)ABt - £[£ d ] /61673)) (2.7) 28 Chapter 2. Overview of PA, QA and RA access QA 3500 0.3 0.4. 0.5 0.6 0.7 Required data utilization (fraction of Bt) Figure 2.3. Maximum voice traffic load for QA access 2.2.4 R A access For F R A access, it only provides statistical multiplexing for the voice traffic. Hence it is better to pre-allocate the bandwidth E[5j] to the data traffic first and allows the voice calls to multiplex over the remaining bandwidth Bt—E[5^] or NRA R A slots. To maintain a fair comparison to QA access, we also assume that NRA R A slots can only support a maximum of 2NRA voice calls. Hence the maximum voice traffic load is given by: h x (Bt - E[Bd])/2 fRAx{Bt-E[Bd])/2 53x8 A F R A = P-1(2 x 53 x 8 (2.8) Figure 2.4 shows that the maximum voice traffic load for F R A access under different Bt. It can be seen that the shape is the same as that for PA access but it has a higher 29 Chapter 2. Overview of PA, QA and RA access maximum voice traffic load because FRA access allows the voice traffic to multiplex among the available R A slots. Fixed RA 40001 1 1 ~i 1 : r. • Required data utilization (fraction of Bt) Figure 2.4. Maximum voice traffic load for FRA access To find the maximum voice traffic load for M R A access, we repeat the analysis for Q A access by replacing /QA w i t h / ^ . The maximum voice traffic load is then worked out to be: A*MRA = Min(p-1(2NMRA),(Bt- E[Bd}/56533)) (2.9) where NMRA = \BV x / ^ / ( 5 3 x 8)J denotes the maximum number of R A slots available per frame. Note that to be consistent with F R A access and Q A access, NMRA slots can only support a maximum of 2NMRA voice calls. 30 Chapter 2. Overview of PA, QA and RA access Figure 2.5 shows the maximum voice traffic load for M R A access under different Bt. It can be seen that the shape is the same as that for QA access because they both allows full statistical multiplexing. M R A access allows a higher initial maximum voice traffic compared to QA access load because of its lower overhead. Movable RA 40001 1 r - 1 1 1 Required data utilization (fraction of Bt) Figure 2.5. Maximum voice traffic load for M R A access 2.3 Multiplexing gain To facilitate comparison of the voice traffic capacity as found from the last section, we evaluate, based on the results in the last section, the multiplexing gain for each voice transport method which is defined as the ratio of the maximum voice traffic capacity supported by the respective voice transport method relative to that supported by PA access under the same conditions. Figure 2.6 shows the multiplexing gains of the various transport methods for various Bt. It can be seen that the results are very similar indicating that the multiplexing gains are insensitive to the change of Bt. The graph 31 Chapter 2. Overview of PA, QA and RA access shows that FRA, QA and BPA access are preferred under different data traffic loads. When E[Bd] is below 0.2Bt, F R A access provides higher multiplexing gain than BPA and QA access because of its statistical multiplexing capability for voice and lower overhead compared to QA access. When 0.25, < B[Bd] < 0.6Bt, QA access offers higher multiplexing gain than FRA and BPA access. Although it requires a greater overhead per slot, QA access allows statistical multiplexing for both voice and data which gives it better performance. Above E[5^] = 0.6Bt, BPA access provides better performance than F R A and QA access because the unused voice bandwidth can be reclaimed by the data traffic and it has lower traffic overhead than QA access. M R A access allows the highest voice traffic capacity at all data traffic loads at the expense of longer access delay than F R A access as explained earlier. Bt=100Mbps Bt=150Mbps 0 0.5 1 Required data utilization (fraction of Bt) Bt=200Mbps 0 0.5 1 Required data utilization (fraction of Bt) 0 0.5 1 Required data utilization (fraction of Bt) Bt=250Mbps 0 0.5 1 Required data utilization (fraction of Bt) Figure 2.6. Multiplexing gain 32 Chapter 2. Overview of PA, QA and RA access 2.4 Summary An overview of PA and QA access as well as their current developments are presented and the concept of R A access is introduced. The advantages and disadvantages of these access methods for transporting VBRIT are also discussed and a voice capacity problem is analyzed to facilitate the comparison. Based on the discussions in this chapter, the later results in this thesis and the literatures on DQDB, Table 2.2 summarizes the advantages and disadvantages of PA access, QA access, R A access and the reservation protocols in [30, 31] for transporting VBRIT. The comparison indicates the motivation of developing a R A access protocol in this thesis. While PA access is fair, simple and less sensitive to delay and provides perfect isochronous transport service, it is very inefficient in terms of bandwidth utilization. Although a BPA access scheme can be employed to improve the efficiency of PA access by releasing the unused capacity to the QA traffic, it still cannot provide statistical multiplexing capability for VBRIT. The major advantages of Q A access are its simplicity and statistical multiplexing capability. However it is unfair and sensitive to delay and suffers from access delay variations. Although the unfairness problem can be resolved by a BWB mechanism, it causes bandwidth wastage and requires an appropriate setting of the BWB modulus. Meanwhile a GBP has been proposed to work with Q A access to provide guaranteed bandwidth for the connection oriented data traffic. However it still cannot guarantee access delay and provide isochronous channels. To enable statistical multiplexing while providing nearly isochronous service, a number of reservation protocols have been proposed for dual bus L A N s and M A N s . In general, reservation based protocols are also less sensitive to delay due to its reservation nature (see for example the simulation results in chapter 3). However these reservation protocols are unfair and strictly speaking, cannot provide perfect isochronous service as PA access because the positions of the reserved slots may vary in each frame. Motivated by these 33 Chapter 2. Overview of PA, QA and RA access reservation protocols, we shall develope a RA access protocol in this thesis which is fairer and provides better isochronous transport service. Effectively R A access combines the advantages of the above access methods. While this protocol is more complex, we believe that its implementation, which mainly requires additional memory and pointer elements, should be feasible with today's high speed processors. PA access QA access R A access Previous reservation protocols for M A N s Guaranteed isochronous service Yes No Yes, it works as PA access after securing a reservation Only nearly isochronous because the positions of the reserved slots may vary frame by frame Statistical multiplexing No Yes Yes Yes Access fairness Fair Basically unfair Fair with the new cyclic capturing mechanism to be introduced in this thesis Unfair Sensitive to delay Not sensitive to delay Sensitive to delay as access fairness is affected Less sensitive to delay due to its reservation nature Ease of implementation Simple Simple More complex but acceptable Slighly more complex than PA and Q A access Table 2.2. Comparisons of different access methods for transporting VBRIT 34 Chapter 3. 1-persistent RA access Chapter 3 1-persistent RA access In this chapter, we introduce the concept of R A access by considering the 1-persistent R A access protocol (the simplest type of R A access protocol) for transporting bursty voice traffic (the most basic type of VBRIT). This protocol is worthy of study because it forms the basis for other R A access methods and establishes the average, upper bound and lower bound performance targets for other waste free bandwidth acquisition mechanisms. While this protocol works in the same principle as the previous reservation protocols [30, 31] for LANs/MANs, it provides better isochronous transport service. Our work also enhances the previous analysis in [30, 31]. For example, we derive the upper bound and lower bound clipping probability for the greedy bandwidth acquisition method. The aim of the later chapters is to enhance 1-persistent R A access with a better R A access protocol for transporting general VBRIT. 3.1 Voice system model and performance criteria In this section, we first describe the voice system model and the performance criteria for the later analysis. In a packetised voice system (see Figure 3.1), an analogue voice signal is first sampled and converted into a digital signal which is then coded by a Voice Activity Detector Voice Packetizer Talk Silence Talk T a l k > <S i l e n c t < T a l k ^\ ~llll-il 111" Figure 3.1. Packetised Voice System 35 Voice Source Analogue to Digital Convenor Coder ' (e.g. PCM) Chapter 3. 1-persistent RA access voice coder. Typically a voice signal is bandlimited at 4000 Hz (more precisely 3,300 Hz plus some guard bands) and sampled at 8,000 times per second with 8 bits per sample, giving a bit stream of 64Kbps. The resulting bit stream is then packetised and transported over a communication facility. As each party in a voice conversation is not active all the time because of pausing and listening, better transport efficiency can be achieved by suppressing the generation of voice packets during silent periods. This is done by employing a voice activity detector to turn off the voice packetizer when no voice activity is detected. This type of packet voice system has been widely used for example to better utilize expensive trans-oceanic cables using the Time Assigned Speech Interpolation technique [71]. ' . The modelling of the above packet voice system can be dated back to the early work by Brady who investigated the talk-silent (on-off) speech statistics in two way conversations by using a simple fixed threshold speech detector [72]. He proposed to model the probability distribution of a talkspurt by an exponential distribution and that of silent periods by a constant plus exponential distribution [73]. Based on Brady's work, a two state Markovian model is generally used in the literatures for packet voice system analysis [32, 31, 30, 39]. In this bi-state voice model (see Figure 3.2), each voice station alternates between talk (active) and silent (idle) states. The talk and silent periods are independent and exponentially distributed with means of 1//3 = 1.5 s and l/a = 2.25 s, respectively, for a voice activity factor of r = = 40%. 1 - e P * 1 - e a t Figure 3.2. Bi-state voice conversation model 36 Chapter 3. 1-persistent RA access . Due to the symmetry of buses A and B, we shall consider traffic on bus A only. Unless otherwise specified, all simulations in this thesis will also take the same approach in order to shorten simulation time and the HOB A and B are assumed to situate in the first (node 1) and last (node N as shown in Figure 1.2 of chapter 1) M A N nodes, respectively. Throughout this chapter, we assume that there are A^v+l=51 M A N nodes (i.e., N=Nv+l) with one voice station per node each engaged in a call. As node A^+l does not have any packet to send on bus A , there are effectively Nv=50 voice stations. Each voice station is modelled by the above bi-state voice model. During an active period, a voice station generates a 48-byte packet every 6 ms (corresponding to 64Kbps coding). A voice station does not transmit any packet during silent or idle periods. In this chapter, we assume that voice packets generated in the current frame are transmitted in the next frame so that transmissions are synchronized with the frame boundaries. To satisfy this requirement, all generated packets are stored in waiting buffers first. At the beginning of each frame, packets in the waiting buffers are transferred to the transmission buffers. If a packet cannot be transmitted within one frame (i.e.,, it stays in the transmission buffer for more than one frame time), it is discarded or overwritten by a new packet. This approach is commonly used in other packet voice system [31, 32, 39] to provide bounded access delay. In our case, a bounded access delay of 12 ms (i.e., 6 ms frame synchronization delay + 6 ms waiting time for transmission) is provided. To evaluate the system performance, the following performance criteria are used: Clipping probability — Clipping probability, or in general packet loss ratio (PLR), is defined as the fraction of generated packets being discarded with respect to the number of packets generated. Previous research indicates that voice conversation can tolerate a small fraction of packet loss. To maintain acceptable voice quality, the average clipping probability should not exceed 0.01 according to various subjective tests [32, 74]. 37 Chapter 3. 1-persistent RA access Table 3.1. Proposed A C F of an R A slot B U S Y SL_TYPE PSR C A P RES REQO REQ1 REQ2 0 1 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit Clip duration — The effect of consecutive packet losses is subjectively more severe than random packet losses. We define clip duration as the duration of consecutive packet losses. The Campanella criterion [75] for acceptable voice quality under consecutive packet losses specifies that no more than 2 percent of talk spurts should have clip durations greater than 50 ms. Utilization — The efficiency of a protocol is measured by the utilization of the allocated bandwidth, defined here as the fraction of slots actually carrying traffic relative to the total number of slots allocated to carry traffic. For PA access, the utilization would be fairly low, around 40% according to the above voice model. 3.2 1-persistent RA access protocol As mentioned above, we shall consider packet transmissions on bus A only. A new slot type called the R A slot is introduced to complement PA and Q A slots as defined in the IEEE 802.6 standard [6]. R A slots are accessible by all voice stations using the R A access protocol defined below. To ensure compatibility with the IEEE 802.6 standard, R A slots have the same slot structure and bit assignments as the PA and Q A slots except for the (unused) reserved bits in the A C F . We propose to use the reserved condition, SL_TYPE=1, and BUSY=0, to indicate an RA slot, and designate the two reserved (unused) bits in the A C F as the Capture (CAP) bit and Reserve (RES) bit used for R A access control, as shown in Table 3.1. Note that the two bits indicating an R A slot introduces an extra slot processing delay of one bit-duration for each slot passing a node, as it is impossible to distinquish between an idle QA slot and an R A slot until the second (SL_TYPE) bit in the A C F is read. We assume that this processing delay is acceptable and justified by the advantages of R A access. Nevertheless we shall discuss 38 Chapter 3. 1-persistent RA access in chapter 4 that this limitation can be eliminated under the typical coverage area of a M A N . CAP=1 in an R A slot on bus A indicates that the slot has been captured by a voice station transmitting on bus A , and RES=1 in an R A slot on bus B causes HOB A to reserve the corresponding R A slot on bus A in subsequent frames by turning it into a PA slot (BUSY=1, SL_TYPE=1) with the VCI unmarked, so that exact isochronous service can be provided. The proposed frame period is / = 6 ms such that a 48-byte packet generated by 64Kbps voice coding fills up the payload of an RA/PA slot exactly once every frame. The proposed 6 ms (macro) frame can be considered as being made up of 48 125/^ s (micro) frames for compatibility with existing standards [6]. The general framework of R A access can be explained by the state transition diagram in Figure 3.3. A station starting a talkspurt first enters the C A P T U R E state to capture an available R A slot on the forward bus by setting CAP=1 in the A C F of that slot based on some capturing mechanism. After capturing an available slot, it enters the CONFIRM state and requests the reservation on the reverse bus by marking RES=1 in the A C F of the corresponding slot in the reverse bus. If it finds that the reservation is successful, it enters the RESERVE state and uses the slot exclusively; otherwise it enters the R E C A P T U R E state to capture another slot. The process continues until the station has captured and reserved an available slot, or the talkspurt has terminated. In the RESERVE state, the voice station continues to mark the RES bit of the captured slot to 1 to tell the HOB that it still requires the slot. At the end of the talkspurt, when the station's packet buffer is empty, it enters the SILENT state and discontinues the marking of the RES bit so that the slot can be released. In fact, a rich family of RA access methods can be found based on different methods of initial slot acquisition. In this chapter, we consider the 1-persistent capturing method: a station in the CAPTURE state always captures an available R A slot, and refer to it as 1-persistent R A access. Although this capturing mechanism is not fair to the downstream 39 Chapter 3. 1-persistent RA access Figure 3.3. State diagram for R A access stations, it is still worthy of investigation not only because it forms the basis of other capturing methods but also establishes the average, lower bound and upper bound clipping probabilities for other waste-free capturing methods. In later chapters, we shall propose a fairer capturing method. Although 1-persistent R A access is unfair, later simulation results show that very satisfactory service can still be provided to all stations when sufficient R A slots are assigned. Due to propagation delay over the buses, slot contention may occur when several stations attempt to capture the same slot. We consider a simple contention resolution method where the upstream station(s) yield to the station furthest downstream. Each station employs a confirmation counter to track the time interval when slot contention is possible. The protocol of 1-persistent R A access is outlined as follows in terms of the voice station procedures: 1. Enter CAPTURE when talking starts. 2. When a R A slot s arrives with CAP=0, capture the slot by marking CAP=1, writing the corresponding VCI and sending the voice packet in the payload, and enter CONFIRM. If unsuccessful in capturing a slot before the next frame starts, drop packet and repeat this step to send the next voice packet. 40 Chapter 3. 1-persistent RA access 3. After entering CONFIRM, set the confirmation counter to C = \l + RT/f], where / and RT are the frame time and round trip propagation delay over the two buses, respectively, and \x] denotes the smallest integer greater than or equal to x. 4. When the same slot s arrives in each subsequent frames, decrement the counter by 1. If CAP=0, set CAP=1, write the corresponding VCI and transmit the next voice packet in the slot; otherwise (i.e., an upstream station has captured the same slot) transmit the voice packet in the next available slot. 5.. Concurrent to step (4), when slot s* on the reverse bus corresponding to the captured slot s passes by, set RES=1 if RES=0; otherwise (i.e., the RES bit has already been set by another station downstream indicating that yielding is required) reset the counter and enter RECAPTURE to capture another slot by repeating step 2. Note that in general s is not necessarily equal to s*. However for the moment, we assume that s=s*. We shall address their relationship for a contention free R A access protocol under the typical coverage area of a M A N in chapter 4. 6. When the confirmation counter reaches zero (i.e., slot contention is no longer possible), enter RESERVE to use the slot exclusively (i.e., reservation is now guaranteed). Note that once an active voice station enters the RESERVE state, isochronous transport service is provided as PA access. This differs from the previous reservation protocols [30, 31] for LANs/MANs where the position of a reserved slot may vary in each frame. In other words, while 1-persistent R A access works in the same principle as these reservation protocols, it provides better isochronous transport service. 7. Enter the SILENT state when the talkspurt ends and the station's packet buffer is empty. Discontinue the marking of the RES bit so that the slot can be released by HOB by changing it back to an available R A slot (BUSY=0, SL_TYPE=1 and CAP=0). 41 Chapter 3. 1-persistent RA access A station Y starting a talkspurt will go through a transient period in the C O N F I R M state before securing a reservation by entering the RESERVE state. In the transient period, slot contention may occur because (a) due to delay on the forward bus, a downstream station Z may preempt station Y by capturing the same slot, or (b) due to delay on the reverse bus, an upstream station X may still capture the same slot before it is marked by the HOB. When condition (b) occurs, station X will eventually yield the slot to station Y, but before this happens, station Y may (i) overwrite the packet of station X , (ii) drop its packet, or (iii) transmit its packet in another available slot. We prefer option (iii), realized in step (4) in the above procedure, as it minimizes packet loss. Note that during the transient period, although the use of the captured slot is not guaranteed, packets in station Y are not necessarily clipped because they may still be transmitted in other available slots. The confirmation counter ensures that if station Y captures slot s at time t, the reservation is secured at time t + C x / when conditions (a) and (b) can no longer occur. This can be verified by considering the two extreme cases. For condition (a), the worst case occurs at the first station, for which after time t+RT the captured slot would have reached the end of bus, and all slot s passing station Y on the reverse bus will have RES=0. For condition (b), the worst case occurs at the last station, for which after time t + f + RT the reservation would have reached the HOB so that upstream stations will no longer be able to capture slot s. Note that it takes a maximum of one frame to set the RES bit on the reverse bus. Hence the maximum time to assure the reservation is t + / + RT giving the formula for C in step (3) above. After entering the RESERVE state, R A access provides exact isochronous service as in PA access. 42 Chapter 3. 1-persistent RA access 3.3 Analytical modell ing of 1-persistent capturing mechan ism This section presents an approximate analytical model for the bi-state voice system employing R A access with 1-persistent capturing, from which the average, lower bound and,upper bound clipping probabilities are derived. To carry out the analysis, the following assumptions are made: 1. The propagation delay is zero and frames are synchronized on both buses. Hence slot contentions cannot occur, and a slot is immediately reserved when it is captured. Note that the contention free operation can also be achieved under the typical coverage area of a M A N by setting the operation parameters properly as shown in chapter 4. In other words, it is possible to apply the contention free assumption for a typical M A N . 2. State changes (active or idle) only occur at frame boundaries 3. Each voice station may change state at most once at each frame boundary. 4. Talkspurts are much longer than the reservation delays so that a voice station starting a talkspurt can always capture and reserve a slot before the end of the talkspurt. 3.3.1 Average clipping probability The average clipping probability is defined as the fraction of total packet loss relative to the total number of packets generated by all voice stations. For 1-persistent capturing or any waste-free capturing method, (n — Ns)+ = max{0,(n — Ns)} packets will be discarded in a frame when there are n active voice stations and Ns R A slots available per frame. As B(NV, n, r) gives the probability that n of the Nv voice stations are active at any time, where B(X,Y,p) = ( y )pY x (1 - p ) - t h e average clipping probability is given by: 2~2(n-Ns)+ xB(Nv,n,r) £ (n-N3)xB(Nv,n,r) Pca = 71 = 0 n=Ns+l (3.1) E n x B(Nv,n,r) r x AV 71 = 1 43 Chapter 3. 1—persistent RA access Note that in carrying out the above analysis, it is assumed that the system under study is ergodic (i.e., time averages are the same as ensemble' averages). This assumption is in fact widely used (e.g., Bertsekas adopts this assumption throughout his book [69] and states in page 156 of [69] that almost every system in data networks is ergodic). We shall make this common assumption throughout the thesis. Formally, it can be proved that the Markov chains for the bi-state voice station model and the later mini-source model are ergodic because they are irreducible, aperiodic and positive persistent (e.g., see page 483 of [76]). 3.3.2 Upper bound clipping probability In the worst case, which determines the upper bound clipping probability, a voice station starting an active period is always the last one to capture the next slot, i.e., it has to wait until there are less than Ns active voice stations. For 1-persistent capturing, this occurs for the last voice station on the bus. Define Pij as the probability that there will be j active voice stations in the next frame given that there are a total of Nv—l independent voice stations and / of them are active in the current frame. Due to assumptions (2) and (3), the above condition occurs if v of the i active voice stations remain active and j-v of the N-i idle voice stations become active in the next frame, where the lower limit of v is given by the conditions j-v < N-i and v > 0, and the upper limit of v is given by the conditions i-v > 0 and j-v > 0. Therefore, Mm(i,j) / - \ / M — ' \ p - = £ L )(7-„' hiZ*<&°i«-'-'+*- <3-2> *>=Max(0,j-M-iV„) V 7 V J ' where qxy is the probability that the state of a station will become y in the next frame given that its state in the current frame is x, with x,y = t (talk or active) or s (silent or idle). For a frame of period/, qss = exp(-/a), qst = 1 -qss, qtt = exp(-//9), and qts = 1 -qtt where 1/a and \lf3 are the average idle and active periods. 44 Chapter 3. 1-persistent RA access Denote En as the expected number of additional packets the last voice station clips before capturing a slot when there are n active voice stations upstream. Since the last voice station clips one packet per frame until less than Ns voice stations are active, En is given by the following recursive equation: Er. N v - 1 N s - 1 £ Pn,i x (1 + Ei) + £ Pn>l , n > Ns i=Ns i=0 0 , n < Ns (3.3) By expressing the above equations in matrix form ENS PN,,N, PN,,N,+I PNS,NV-I ENS "1" EN,+I PN,+I,N, PN.+I,N.+I ' • • ,PNS+I,NV-I EN,+I 1 — + (3.4) _ENV-I . _PNV-I,NS PNV-I,N,+I • P N V - I , N V - \ _ , E N V - I . _1_ En, n > Ns, can be solved as [ENs ENs+1 . . ENv_i^ 1 — PN.,N, -PNS+I,N, -PN,,N,+I 1-PN.+I,N.+I —PN,,NV-I —PN,+I,NV-I —PN*-I,N. -PNV-I,NS+I 1 — PNV-I,NV-I (3.5) where [X]" 1 and [ X ] r are the inverse and transpose of matrix [X], respectively. The expected number of packets, Q , the last station clips, before capturing a slot is then given by N v - 1 Ci= B(Nv-l,n,r)xEn. n = N s Similar to above, the upper bound clipping probability is (3.6) Pcx = Q x / x (3. (3.7) 3.3.3 Lower bound clipping probability In the best case, which determines the lower bound clipping probability and frames to reserve, a voice station starting an active period can always capture the next available slot. For 1-persistent capturing, this occurs for the first voice station in the network. 45 Chapter 3. 1-persistent RA access Denote Cf as the expected number of packets the first station clips before capturing a slot. Due to assumption (1), if the first station becomes active when there are less than Ns stations active, no packets will be clipped, otherwise one packet per frame will be clipped until one of the active stations becomes idle and releases a reserved.slot. Therefore Nv-1 oo Cf = J2B(NV - 1, n , r ) £ kqS'W ( l - qS') n=N3 k=l T V - i (3-8) = "y1 B(Nv-l,n,r) As the average number of packets generated in each talkspurtis l/(/3f), the clipping probability of the first station is given by Pcf = Cfx(3x f. (3.9) For a general voice station j, its clipping probability PCJ will be between the lower bound and upper bound values as determined above, i.e.j Pc, < Pcj<Pcx . (3.10) It can be seen later that when sufficient RA slots are assigned, the difference between the lower bound and upper bound values will become diminishingly small. That means PCJ converges to Pca . Note that the above analysis also applies to other waste-free capturing methods such as distributed queueing because the best case scenario (i.e., a voice station starting an active period can always capture the next available slot) and the worst case scenario (i.e., a voice station starting an active period is always the last one that can capture the next available slot) are. still valid. Therefore for these waste-free capturing methods, the average clipping probability is still given by (3.1) and the clipping probability is still bounded by (3.10) . 3.3.4 P r o b a b i l i t y d i s t r i b u t i o n o f n u m b e r o f c l i p p e d packe ts To find the number of R A slots required to satisfy the Campanella criteria, we need to obtain the probability distribution of the number of packets being clipped in a talkspurt. 46 Chapter 3. 1-persistent RA access While the exact analysis seems to be difficult, we consider the following approximate model to be validated later by simulation results. It turns out that the approximations are in good agreement with the simulation results when the number of R A slots is large. Consider that when voice station X becomes active in frame k, it joins a first come first served queue for capturing a slot and that the above assumptions (1) - (4) are still valid. Let Nt and Nq denote the numbers of voice stations that are active and waiting in the queue, respectively, when X joins the queue in frame k. Obviously Nq = (Nt — Ns)+ where Ns is the number of R A slots. Pw(Nc\Nt), the probability that X clips Nc packets before capturing a slot (i.e., X captures a slot in the k+Nc+\-th frame) given that there are Nt active stations when X arrives at the queue, is given by ( 1, Nc = 0,Nt<Ns Pw(Nc\Nt)= I ^ N c ~ 1 ^ Q t q + 1 ( l - Q t ) N e - N ' ' - \ Nc>Nq + l,Nt>Ns (3.11) ( 0, otherwise where Qt = ( l (3.11) means that X can capture a slot immediately if there are less than Ns active voice stations when it arrives at the queue, otherwise the number of packets it clips is given by the sum of the numbers of packets clipped by A^+l stations (including X) while each station is at the head of the queue, which probability distribution is given by the iV g+l-fold convolution of the geometrical distribution, G(w) = Qt(l — Qt)w~l, of the number of packets clipped by the station at the head of the queue before it captures a slot. Note that as the minimum number of packets clipped by each station in the queue is one, there are some invalid situations which results in the zero probability in (3.11). Averaging over Nt, the probability that X clips Nc packets before capturing a slot is given by Nv-1 PW(NC)= P(Nc\Nt)B(Nv-l,Nur). (3.12) Nt=0 The probability that station X clips at most Nc packets before capturing a'slot is Nc Pw(<'N.C) = Y,P^N^- (3:13) • 3=0 47 Chapter 3. 1-persistent RA access For evaluation of the Campanella criteria, we need to find the probability that the clip duration is more than 50 ms which corresponds to the clipping 8.3 packets. Assuming that linear interpolation can be used, the required probability is given by 3.3.5 U t i l i z a t i o n When there are n < Ns voice stations active, the utilization is n/Ns, otherwise it is equal to one. Hence the overall average utilization is 3.4 D iscuss ions on simulation & analytical results A simulation program was written in Simscript II.5 [77, 78] to generate results for comparison with the analytical calculations. Note that the simulation model takes into account the effect of propagation delay and slot contention. Unless otherwise specified, the simulation parameters follow the voice system model given above (i.e., 50 transmitting M A N nodes on bus A running at 155 Mbps with one voice station per node each engaged in a call throughout the time period considered). The distance between adjacent nodes is 10 slots and 300,000 frames were sent for each simulation. A l l simulations in this thesis had been run long enough to provide steady state results. Note that running simulations for R A access is very time consuming due to its reservation nature. This is because once a reservation is secured, isochronous service is provided and no packet loss occurs (or the traffic condition is basically unchanged). That means we have to simulate a huge number of talkspurts or active periods in order to obtain steady state results. Therefore it is difficult to run simulations with a very large number of voice sources (or VBRSs in general). We shall employ the analytical expressions to calculate results for these cases. 48 Pw{> 8.3) = 1 - {Pw(< 8) + 0.3 x [Pw(< 9) - Pw(< 8)]}. (3.14) (3.15) Chapter 3. 1-persistent RA access Nevertheless the simulated M A N , with a spanning distance of 500 slots, does cover a realistic city area. Results are presented and discussed below. 3.4.1 Clipping probability Figure 3.4 shows the simulation results of the lower bound (first voice station), average, and upper bound (last voice station) clipping probabilities in comparison with the analytical calculations for Nv = 50. The close agreement between the analytical results and the simulation results in Figure 3.4 lends confidence to the correctness of both models. As expected the last voice station experiences the largest clipping probability; however, the difference in performance between the first and last stations diminishes when the number of R A slots increases, indicating that the fairness problem could be lessened. From the graph, it can be seen that the required number of R A slots for satisfying the clipping probability performance criteria (i.e., all voice stations have clipping probability less than 0.01) is about 50%, 45% and 43% of Nv when Nv is 50, 200 and 500 respectively. 10 p • -v: • o Cu a a, O H U 10 1% Target L i n e A n a . Nv=500 A n a . Nv=^ A n a . Nv=f Sim.Last S im. First S im. Av£ 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 N o . of R A slots per frame (% of N v ) Figure 3.4. Upper bound, lower bound and average clipping probabilities 49 Chapter 3. 1-persistent RA access This corresponds to a multiplexing gain of 2, 2.22 and 2.33 respectively compared to PA access. Therefore as the number of voice stations increases,' the multiplexing gain approaches the ideal target of 1/r = 2.5. 3.4.2 Campanella criteria Figure 3.5 shows the simulation results for the Campanella criteria in comparison with that calculated from (3.14). It indicates that when the number of R A slots is large, the percentage of talkspurts having clip duration of over 50 ms is nearly the same for all stations which converges to that predicted by the ideal model. With about 28 slots (55% Nv), all 50 voice stations can satisfy the Campanella criteria. Consequently 30 R A slots are well sufficient to service 50 voice calls while satisfying both the clipping probability and Campanella criteria, giving a 170% improvement in voice slot utilization over PA access. When Nv is increased to 200 and 500, the percentage of R A slots required to No. of RA slots per frame (% of Nv) Figure 3.5. Percentage of talkspurts having clip durations greater than 50 ms 50 Chapter 3. 1-persistent RA access satisfy the Campanella criteria decreases dramatically and approaches the voice activity factor of 40%. 3.4.3 Utilization Figure 3.6 shows that the simulation results of utilization agree closely with that calculated by (3.15). It further validates the correctness of the simulation model. With 30 R A slots for 50 voice stations, the utilization is about 68% as compared to 40% for PA access. With Nv = 200 and 500, the utilization increases when the percentage of number of R A slot is small but converges to that of Nv = 50 when the percentage is large. This indicates that utilization is apparently independent of the number of voice stations when the percentage of R A slots is large. Nevertheless as the number of voice stations increases, less RA slots are required hence the protocol is more efficient and utilization approaches 100%. a o •a N 100 95 90 85 a 80 -75 70 65 Analytical (Nv=500) Analytical (Nv=200) Analytical (Nv=50) Simulation (Nv=50) * i • i • i . i . i • i J I I I I I L. I . I . I 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 No. of RA slots per frame (% of Nv) Figure 3.6. Slot utilization 51 Chapter 3. 1-persistent RA access 3.4.4 Effect of propagation delay on clipping probability When propagation delay increases, average clipping probability also increases be-cause slots cannot be released immediately at the end of each talkspurt. To perform an approximate analysis, we assume that it is equivalent to increasing each talkspurt by the average delay taken to release a slot. If Ds is the average propagation delay between consecutive voice stations, then the average delay, D to release a slot is given by: 1 Nv £> = — x £ (z x 7J>5 + 0.5 x /) = 0.5 x [Ds x (Nv + 1) + /]. (3.16) i = i The average clipping probability then becomes: Pca = E (n-Ns) x B [ N v , n , ^ ) i=Ns+l V P^'a / Nv E n x B(Nv,n,r) n = l (3.17) where D is the average delay to release a slot as given by (3.16). Figure 3.7 shows the numerical results of (3.17) in comparison with the simulation result with Ns = 25. & 10 •9 o 1-1 OH b0 fl ' & i .& U CD CS > < 10 10 10 c \ Analytical Simulation 0 - •• 0 -9 • 10 100 1000 Delay Between Consecutive Nodes (Slots) 10000 Figure 3.7. Effect of propagation delay on average clipping probability (/Vv=50, Ns=25) 52 Chapter 3. 1-persistent RA access It indicates that (3.17) agrees nicely with simulation results. The graph shows that the average clipping probability stays approximately constant until the total delay exceeds 0.137 s (1000x50x2.73^8). Assuming a signal propagation delay of 5.085^s/Km, this delay corresponds to a distance over 26,000 Km. The spans of M A N ' s in large urban centres are well within this distance. . 3.4.5 Simulation using a real voice conversation To assess the actual quality of a voice conversation transported by R A access, we simulated the transmissions of a real speech signal by the 50th voice station while keeping the other 49 stations to the original voice conversation model. The speech signal was produced by recording 20 s of one side of a telephone conversation. The talkspurt and silent intervals were then determined as follows: (i) "talk" to "silent" transition occurs when the signal amplitude stays within the background noise envelope, which is found by averaging all the positive peak and negative peak background noise voltages during the silent periods, for over 200 ms [73], (ii) "silent" to "talk" transition occurs if the amplitude falls outside the background noise envelope. During the talkspurt periods, the voice signal was sampled at 8000 samples per second with 8 bits per sample giving 64Kbps. 48 samples were then grouped to form one voice packet every 6 ms which was transported by the R A access protocol. The received signal was then re-generated from the successfully received packets. Although there is no voice activity during the silent intervals, it may still be desirable to maintain a certain background noise level for the listener. We assume that this can be done by transmitting an extra frame of noise level at the end of each talkspurt and the receiver repeats it to the listener. In other words, the silent gaps and missing samples are filled with background noise instead of complete silence. The simulation time was 100,000 frames during which the 20 s of speech samples were repeated continuously to find the worst situation (i.e., when the number of clipped packets is largest). Figure 3.8 shows the worst re-generated signal for Ns = 20, 25 & 53 Chapter 3. 1-persistent RA access 30. It is apparent that, when = 20, the speech is totally unrecognizable. When Ns is increased to 25, the quality is greatly improved, however one word was missed. With Ns = 30, very few packets were clipped and no noticeable degradation was found from the re-generated speech signal. This test indicates that 25 slots should be marginally acceptable and 30 slots can provide very satisfactory service which is consistent with the above analysis. Original voice signal Re-generated voice signal (Ns=20) CD T 3 •*—• "5. E CO T3 CD _N "cc E . o -z. 5 10 Samples x 10 Re-generated voice signal (Ns=25): CD -4—' "5. E CO T J CD _N "CO E . 5 10 Samples 5 10 Samples. x 10 Re-generated voice signal (Ns=30) x 10 5 10 Samples x 10 Figure 3.8. Simulation using a real speech signal 54 Chapter 3. 1-persistent RA access 3.5 Summary In this chapter, the concept of R A access is introduced by analyzing the 1-persistent R A access protocol for transporting bursty voice traffic. Fully compatible with the slot format of the IEEE 802.6 standard, R A access is capable of providing nearly isochronous voice transport with bounded access delay, while allowing engineered trade-offs between utilization and clipping probability. Except for some delay jitter and possible clipping at the start of each talkspurt, lossless exact isochronous service is maintained once a reservation is secured. An analytical model for 1-persistent R A access is derived which establishes the average, lower bound and upper bound clipping probabilities for other waste free capturing methods. The analytical and simulation results are further validated by a real voice simulation. It is also found that R A access is not too sensitive to propagation delay unless the delay is unrealistically large, indicating that it can operate without difficulty in a metropolitan area. 55 Chapter 4. Contention free RA access with cyclic capturing Chapter 4 Contention free RA access with cyclic capturing In chapter 3, we introduce R A access with a 1-persistent capturing mechanism which is based on the greedy bandwidth acquisition method considered in other reservation protocols for LANs/MANs [30, 31]. To overcome the unfairness problem of 1-persistent capturing, we propose a new cyclic capturing mechanism in this chapter which is a simple enhancement of 1-persistent capturing. This new capturing method can provide much fairer service even under adverse operating conditions with shortage of bandwidth and high propagation delay. Hence we shall adopt this capturing method for R A access in this thesis. We also show that R A access can be made contention free under the typical coverage area of a M A N by setting the operation parameters properly and discuss how to support multiple number of VBRSs connected to a M A N node. The performance of R A access including PLR, packet delay, delay jitter, probability distribution of consecutive packet loss and channel utilization is analyzed with a theoretical model validated by simulation results. 4.1 Contention free condit ion for R A a c c e s s As discussed previously, access contention (i.e. two VBRSs in different M A N nodes try to reserve the same slot) may occur if propagation delay is large. This conflict can be resolved by the simple contention resolution method proposed in chapter 3, where the upstream VBRS(s) yield to the VBRS furthest downstream. Nevertheless, if the round trip delay RT (in slots) is less than the frame duration (F=2197 slots), contention can be avoided if s* (the slot in the reverse bus that conveys reservation for slot s in the forward bus) is chosen appropriately such that for a slot s captured in frame k, its reservation can reach the respective HOB before the generation of slot s in frame k+l. The explanation is given as follows with all time units expressed in slots. As frames are 56 Chapter 4. Contention free RA access with cyclic capturing repeated periodically, we can just consider the first frame. Suppose that at time tA, slot s and s of frame 1 are generated at node 1 on bus A and node N (last M A N node) on bus B, respectively. Recall that we assume that HOB A and B are situated in node 1 and N respectively. Slot s will have passed all nodes on bus A by the time it reaches the last M A N node N at tA+RT/2. To facilitate the explanation without loss of generality, we assume that s' and RT/2 are integers. At t^+RT/2, slot 5 ' © 4^ will be generated by HOB B on bus B where © denotes modulo F addition. In general, s* = s © ^ © 6 where 6 is an integer greater than or equal to zero. To avoid contention, the reservation conveyed by slot s* for slot s must be received by HOB A before the generation of next slot s at tA+F. This condition can be satisfied if RT < F and <!> is set between 0 and (tA + F)- (tA + 4 f ) = F-KT noting that it takes RT/2 for slot s* to travel from HOB B"to HOB A . Suppose when tA=0, s=l and s =sr, s* should then be chosen such that Sr © ^ < S* < Sr © ^ © (F - RT) Sr © ^ < S* < Sr © (^F - (4.1) for slot 1 or in general RT ( RT\ {s-l)@sr® — <s*<{s-l)@sr@(F- — \ (A.l) for slot s provided that RT < F or round trip delay is less than the frame duration of 6 ms. Typical values of RT for a M A N is 0.25ms — 1ms or about 100-400 slots (dual bus length=50-200Km, propagation delay=5/us/Km) which is much less than the frame duration. Consequently R A access can be made contention free using the above method. For example, consider the worst case round trip propagation delay of 400 slots and sr=0 then s* should be set to satisfy the following inequality (s - 1) © 200 < s* < (s- 1) © 1997 => s © 199 < s* < s © 1996 (4.3) That means even under the worst case propagation delay, s* can still take a very wide range of values and the contention free operation is quite feasible. For the rest of this 57 Chapter 4. Contention free RA access with cyclic capturing thesis, we assume this contention free condition. Nevertheless R A access still works in general when the above contention free condition is not satisfied, in which case the previous contention resolution method can be employed. 4.2 RA a c c e s s with cycl ic capturing In this section, we describe the contention free R A access protocol with cyclic capturing as well as some enhancements to further improve its performance. 4.2.1 RA slot format In chapter 3, we propose to use the reserved condition BUSY=0 and SL_TYPE=1 in the A C F to indicate a RA slot in general. However this introduces an extra one bit slot processing delay in each M A N node. Under the contention free operation, this delay can be eliminated by using the slot format given in Table 4.1. Basically an idle R A slot is a PA slot with CAP=0. If a R A slot is captured or reserved, it effectively becomes a PA slot (i.e., with the same BUSY, SL_TYPE and C A P bits). In the case of a reserved R A slot, the VCI values are left vacant by the HOBs so that the VBRS which has captured the slot can fill in the appropriate values. Note that we cannot use the above slot assignment scheme in the previous R A access protocol with possible access contention because we need to use the conditions {BUSY=1, SL_TYPE=1 and CAP=1 } and {BUSY=1, SL_TYPE=1 and CAP=0} to distinquish whether a R A slot has been or has not been captured by an upstream VBRS respectively during the confirmation stage. Table 4.1. R A slot format for contention free operation Slot type B U S Y SL_TYPE C A P bit V C I values bit bit Idle R A slot 1 1 0 Unmarked Reserved or 1 1 1 Unmarked or marked by captured R A slot the respective M A N node PA slot 1 1 1 Specific value set by the respective HOB 58 Chapter 4. Contention free RA access with cyclic capturing 4.2.2 Spreading of RA slots In this chapter, we assume that there are Ns R A slots within a frame of F slots. The remaining F — Ns slots are consumed by the PA and Q A traffic. To reduce packet access delay, we consider that the RA slots are spreaded evenly within a frame (i.e; consecutive R A slots are separated by d = slots) and each VBRS is allowed to capture a R A slot immediately after its bit rate is increased (i.e. without having to wait until the start of a new frame). By doing so, the previous synchronization delay is eliminated. Note that perfect uniform spreading of RA slots may not be possible as consecutive R A slots must be separated by an integral number of slots. Nevertheless, to facilitate the analysis, we assume that R A slots can be spreaded evenly within a frame. Two methods are proposed in Appendix B for spreading the R A slots as uniformly as possible. 4.2.3 Cyclic capturing mechanism To overcome the unfairness problem of 1-persistent capturing, we propose a new cyclic capturing mechanism which is a simple enhancement of 1-persistent capturing. The basic concept of cyclic capturing is that all VBRSs still capture available R A slots with probability one. When a VBRS Y of node P decreases its bit rate by 64 Kbps in frame k such that a reserved slot s is no longer required, node P releases slot s in frame k immediately by setting CAP=0, and stops marking the RES bit of corresponding slot s* on bus B as before. By doing so, nodes P+l, P+2, P+3, . . . .become the first, second, third, . . . , node that can capture slot s. This prevents the upstream nodes from preempting the downstream nodes from obtaining the reservations all the time. As shown by later simulation results, cyclic capturing provides much fairer service even under adverse operating conditions with shortage of bandwidth and high propagation delay. In addition to 1-persistent capturing and cyclic capturing, we have in fact evaluated other capturing mechanisms (for example, see [47, 48]): 1. /^-persistent capturing — capture an available R A slot with probability p (0 < p < 1) 59 Chapter 4. Contention free RA access with cyclic capturing 2. Distributed capture queue — co-ordinate the capture requests by a distributed queue 3. Preemptive capturing — each node is given some reservation privileges in certain frames such that it can preempt the upstream nodes in obtaining, a reservation; effectively this realizes the virtual configuration that the M A N nodes are connected in a ring and HOB A (slot generator) is shifted around the transmitting M A N nodes frame by frame. While p-persistent capturing can improve fairness by using a low p, it results in slot wastage. It is also difficult to determine a suitable value of p in practice as the number of VBRSs and their characteristics are unknown in a dynamic network. Both distributed capture queue and preemptive capturing improve fairness while ensuring no slot wastage. However they require an additional control bit in the A C F (in addition to the C A P and RES bits). The distributed capture queue is still, unfair especially when the propagation delay is large which is the common problem of distributed queue. We have found that cyclic capturing performs better than all the above methods in terms of ease of implementation, fairness and sensitivity to propagation delay. Hence we do not consider these capturing methods in detail in this thesis but focus on the best cyclic capturing method. 4.2.4 RA access controller and protocol operations To control R A access for a number of VBRSs in a MANnode, packets generated by a VBRS are stored in a transmission buffer (TB) which connects to a R A access controller (AC) as shown in Figure 4.1. Due to the time sensitive nature of VBRIT, it is more effective to drop late packets as mentioned in chapter 3 so that bounded access delay can be provided. In this chapter, packets that cannot be transmitted within a frame time are dropped. To do this, we assume that packets are time stamped and discarded by the A C accordingly. Alternatively the size of each buffer can be varied dynamically based on the bit rate of the corresponding VBRS so that new packets override late packets. 60 Chapter 4. Contention free RA access with cyclic capturing Start of frame k SR CQ B U S A VBRS B U S B s s" VBRS 1 201 1 2 202 0 3 203 0 4 204 2 . SR S s" VBRS 1 201 1 2 202 4 3 203 0 4 204 2 VBRS CQ VBRS End of frame k Figure 4.1. R A access controller for contention free operation To effect the R A access protocol, each A C maintains a capture queue (CQ) to register all capture requests of its VBRSs and a slot register (SR) to record the identity of the local VBRS using each slot. In the SR, VBRS=0 indicates that the respective slot is not currently used by any local VBRS. When a VBRS increases its bit rate by 64 Kbps, it first registers a capture request in the CQ. When RA slot s arrives on the forward bus, the A C takes one of the following actions if the respective condition is true: CAP=0 in slot s and C Q is not empty If the TB of the first VBRS registered in the CQ (say SI) is not empty, set CAP=1 in the A C F of slot.s, write the corresponding V C I in the segment header, send the next packet of S1 in the slot and update the VBRS entry for slot s in SR with SI. If the TB is empty (i.e., this slot cannot be filled due to bit rate decrease), cancel the registration and continue the above actions with the next VBRS registered in the CQ. 61 Chapter 4. Contention free RA access with cyclic capturing V B R S entry for slot s in SR = Y > 0 This identifies slot s as being reserved by VBRS Y . If the TB of VBRS Y is not empty, write the corresponding VCI in the segment header of slot s and transmit the next packet of Y in the slot. If the TB is empty, indicating that this slot is no longer required due to a bit rate decrease, release slot s by setting CAP=0 in slot s to allow its capture by downstream nodes, and set VBRS=0 in the respective SR entry. Actions are also required when slot s*, corresponding to slot s on the forward bus, arrives on the reverse bus, and the VBRS entry for slot s in the SR is Y > 0. In this case, the A C sets RES=1 in slot s* to maintain the reservation. The example in Figure 4.1 illustrates the above R A access protocol. In this example, s* = s © 200. At the beginning of frame k, VBRS 1 and 2 have reserved slots 1 and 4, respectively, and VBRS 4 and 3 each has an unfulfilled capture request in the CQ. During frame k, slot 2 is captured and reserved by VBRS 4, and VBRS 2 has increased its bit rate by 64 Kbps and registered a request with the CQ. Note that slot 3 is still not available because it has been reserved by a VBRS in another M A N node. Note also that the general R A access protocol (i.e. the one with the access contention resolution mechanism as described in chapter 3) can also be incorporated into the R A access controller by including: 1. a state field and a confirm counter field in the SR to record the state and confirm counter value of each slot respectively 2. a recapture queue for registering recapture requests 3. a confirm packet register to register for packets that are preempted due to the contention resolution mechanism so that they can be transmitted in other slots For details of this general R A access protocol, please refer to [47, 48]. As the contention free operation is quite feasible under the typical coverage area of a M A N , we shall focus on contention free R A access in this thesis. 62 Chapter 4. Contention free RA access with cyclic capturing 4.3 Q o S requirements and analytical model ing of R A a c c e s s 4.3.1 Traffic model and assumptions In this chapter we consider that there are 21 M A N nodes with each pair of consecutive nodes separated by 10 slots. Note that this represents the previous worst case propagation delay. Since we only consider traffic on bus A, there are effectively 20 transmitting M A N nodes on bus A . The bit rates of each VBRS are varied at nx64 Kbps (n=0, 1,2, . . . Mi, where Mi corresponds to the maximum bit rate of the /-th VBRS) according to the Markov model given in Figure 4.2. This model is based on the discrete state, continuous time M a ^ ( M - i ) a ( M - k - i ) a ( M - k ) a 2 a a -y \ *> (n = M-1 P 2 P kp ^^(k+1)p (M-1 ) p ^ - ^ M.p Figure 4.2. VBRS traffic model Markov model proposed in [79] for modelling packet video traffic and its effectiveness has been verified in [79] by matching the average bit rate and the autocovariance of the experimental data of a video telephone scene. In the model, bit rate transitions occur only between consecutive levels with exponential transition rates that depends on the current bit rate. We shall analyze and simulate three different sets of M, a and (3 values to represent voice, video telephony (VT) and video conference (VC) traffic. The previous bi-state 64Kbps voice model can be realized by setting M=l , a=0.444 and /?=0.667. For video communications, a and (3 depend on the type of motions as well as the signal compression mechanism. Current signal compression technology is capable of supporting V T at 2x64 Kbps (3 states) and basic V C at 6x64 Kbps (7 states) [27]. Assume that the bit rates in [79] can be converted to 2x64 Kbps (VT) and 6x64 Kbps (VC) in our model using appropriate compression ratios so that a and (3 for V T and V C can be evaluated by using formula (11) in [79], then for VT, M=2,a=2.8 and £=1.1 and for V C , M=6, a=1.8 and (3=2.1. We shall use these parameters for both the analytical calculations and 63 Chapter 4. Contention free RA access with cyclic capturing a Figure 4.3. Mini-source model simulations. Note that we shall also simulate RA access with other video source models in chapter 5. As shown in [79], the steady state bit rate distribution of this model can also be thought of as the aggregate bit rate from M independent mini-sources each alternating between an active state and an idle state as shown in Figure 4.3. The active and idle periods are exponentially distributed with means of V/3 s and 1/a s, respectively for an activity factor, i.e., fraction of time the mini-source is active, r = a/(a + f3). For Nv VBRSs, there are Nm = M x Nv mini-sources. We shall employ this mini-source model for the performance analysis with the following assumptions: 1. A l l mini-sources are independent of each others. 2. Propagation delay is zero. 3. An active mini-source can always capture and reserve a R A slot before the end of each active period. 4. For each mini-source, there is at most one state transition within each frame period/. These assumptions will be justified by comparing the theoretical calculations with later simulation results. 4.3.2 PLR PLR is defined as the fraction of total packet losses relative to the total number of packets generated by a traffic source. As discussed previously, voice can have a PLR of 1% without causing noticeable degradation in voice quality [74]. For video communications, target PLR ranges from 10 — 6 to 10 — 9 depending on the nature of the 64 Chapter 4. Contention free RA access with cyclic capturing video traffic [80]. In this thesis, we assume a target PLR of 1 0 — 6 and 1 0 — 9 for V T and V C , respectively. Based on the analysis in chapter 3, PLR of the network can be found as: ' E {n-Ns)+ x B(Nm,n,r) • £ {n - Ns) x B(Nm,n,r) PLR = = — (4.4) Nm r x Nm E n x B(Nm,n,r) n=l For a fair access protocol, all VBRSs should have the same PLR given by the above expression. 4.3.3 Packet delay and delay jitter VBRIT is particularly sensitive to delay and delay variations (or delay jitters). For voice communications, the constant delay for echo free conversations recommended by CCITT is limited to 25 ms and delay jitters of less than 130ms are generally acceptable [80]. This indicates that the mean packet delay can exceed 25 ms. Here we consider a conservative target of 25 ms. For video communications, the requirements depend on the type of the traffic sources and are more diverse. As a general guideline [80], the packet delay and delay jitters should be limited to 1-10 ms for most video applications. Here we impose a stringent packet delay and delay jitter target of 1 ms for the V T and V C traffic. The objective of the following analysis is to evaluate the mean and standard deviation of packet access delay which is the time taken for a packet to gain access to a R A slot. The standard deviation of packet access delay is a common way of measuring delay jitter. In the following analysis, all time units are expressed in slots. Consider that when a mini source V becomes active at time tactive, there are na active mini sources in the network and denote sx (x=\,2,3,...,Ns) as the xth R A slots passing V between tactive and tactive+F. The mean packet access delay for V, Tpacket is made up by two components: Ppacket = Tresidue ~t~ Preserve (4.5) where Tresidue is the time taken for the arrival of the first R A slot after tactive and Treserve is the effective additional time required to capture the first available R A slot. Note that if V 65 Chapter 4. Contention free RA access with cyclic capturing captures the first slot at tactive + kF.+ Tresidue + tcap where k=0,1,2,3,4..., Treserve = tcap because packets waiting in the TB for over one frame are dropped so that effectively a new capturing cycle starts every tacave + kF until V captures a slot. Obviously the mean of Tresidue, E[Tresidue] is f • To evaluate E[Treserve], we use the following approximations which are justified by later simulation results: 1. If na < Ns, V can capture a R A slot between tactive and tactive+F. To simplify the analysis, we assume that the number of reserved R A slots as seen by the first packet of V is also na which will not change until tactiVe+F. As every slot has equal chance of being reserved, V can capture s\ at time tactive + T r e s i d u e with probability g(l,na) = (Ns — na)/Ns. In general, the probability that V can capture sx at time ^active + ^residue + (x — l)d can be found by the following recursive equation: provided that na < Ns. It means that V cannot capture the first x-\ slots with probability ^1 — £ gihrta)^ but capture the x th slot with probability ^NS~X+I) • By using z transform or verifying the following equation with mathematical induction, the solution for (4.6) is found to be S ( x , „ ? ) = W - „ „ ) ( ^ - ^ ) ( M ) . (4.7) (Please refer to Appendix B for an example of the problem). Therefore min(na+-l-,Ns) \na < Ns] = ^ d x (x - l ) .x g(x,na) (4.8) Note that x < min(na + 1,NS) because if there are na reserved slots, V must be able to capture a slot within na+l slots. 2. If na > Ns, we assume that V cannot capture a slot between tactive a n d tactive+F. In this case it will capture any R A slot with equal chance after tactiVe+F due to symmetry noting that at any time, each reserved RA slot is released with equal probability. 66 Chapter 4. Contention free RA access with cyclic capturing Hence E[Treserve\na > Ns] = + 2d + 3d+ ... + (Ns - l)d} = d x ^ ~ *) ( 4 . 9 ) Therefore, the mean packet access delay for V is given by: Ns-1 Tm = E \Tpacket } =E[Tresidue] + YI P™b{na < Ns)E[Tr eserve\na < N,}+ < 4 1 0 > Y Prob(na > Ns)E[Treserve\na > Ns] na=Ns which yields Ns-l min(na+l,Ns) Tm = g + Y B(Nm ~ X ' r) x S X (x - 1) X flr(x, na) na=0 x = l (4.11) + " | : ' B ( J V . - l , n . , r ) x ' " < ( ^ - 1 ) na=Ns Similarly, the standard deviation of the packet access delay Tsd can be found as follows, ^2 Ns — 1 min(na+l,Ns) Tld=Tv = -+ Y B(Nm-l,n-a,r)x Y d2 x (x - l)2 x g(x,na) na=0 x=l na=Ns b V V (4.12) Note that all packets transmitted by V will experience the same constant' access delay after reserving a slot, so that within the packet stream generated by a mini-source, the access delay variation is essentially zero. Nevertheless, Tsd is still a useful performance indicator of delay jitter when we consider the superposition of packet streams from all the mini-sources of the same VBRS (i.e. ideally all packet streams should be delayed by the same amount such that Tsd = 0). 4.3.4 Utilization Based on the analysis in chapter 3, utilization, the fraction of assigned channels (slots) carrying actual user traffic, is given by: ' Ns-l x Nm U = E N + ^ B(Nm,n,r). (4.13) n=l s n=Ns 67 Chapter 4. Contention free RA access with cyclic capturing 4.3.5 Probability distribution of consecutive packet loss In R A access, packet losses occur in burst before a reservation is obtained. Hence it is of interest to analyze not only PLR but also the duration of consecutive packet loss which is referred as loss duration. In general, we are interested in the following performance criteria: less than x% of reservations has loss duration greater than LD sees. To facilitate the later numerical analysis, we consider the following performance criteria as an example: • Voice: less than 2% of reservations (talkspurts) have loss durations greater than 50 ms (the well known Campanella criteria [74] for voice); • V T / V C : less than 1% of reservations have loss durations greater than 12 ms. The objective of the following analysis is to find the fraction of reservations with loss durations greater than / (/=0,1,2,3..) frames (i.e. the probability that an active mini-source V losses more, than / packets during a reservation). To facilitate the analysis, we make the following assumptions in addition to the previous ones: 1. State changes, slot release, and slot capturing are synchronized at fy (k = 0,1,2,3 , . . . ) . The mini-source V becomes active at to. . 2. If there is no idle R A slot at tQ, V will find that there are q (q=0,1,2,3...) capturing mini-sources (excluding V) at to with probability B(Nm — l,q + Ns,r). 3. If a mini-source is idle at fy, it will become active at fy+i with probability 1 — e~af' independent of other mini-sources. 4. Each reserved slot at fy is released independently at fy+i with probability 1 — . 5. Released slots at fy are captured by all mini-sources with outstanding reservation requests, including those which become active at fy and those with previously unfulfillable requests, with equal probabilities due to the cyclic capturing mechanism or symmetry. 68 Chapter 4. Contention free RA access with cyclic capturing 6. If V captures a slot at fy (k = 1,2,3 , . . . ) , / = k — 1 consecutive packets are lost during that reservation. It is possible to solve the problem with a Markov chain using the number of active mini-sources and mini-sources with reservations at fy as the states. However, the very large number of states make computations impracticable. As indicated by the simulation results, the method presented here is a close approximation that is computationally more efficient. We first consider that there is no available R A slot at to (i.e. at time to, number of active mini-sources excluding V is q + Ns, q > 0) and form a discrete time Markov chain imbedded a fy with states!^} = {C/b} U {^ } where Q denotes the number of capturing mini-sources ( Q = 0,1,2,3,...,Nm—l—Ns) excluding V , and H represents the state in which V has successfully captured a slot. Note that there are q+l outstanding reservation requests just after to including the one made by V , the number of active mini-sources in the network at fy, including V, is Q+A^+l, and Q <N m—l—N s . Our objective is to find the probability that V has entered f2 (the absorbing state) at fy given that there is no available R A slot at tQ. If = <fy, the probability that S^ +l = ck+\ IS given by: Prt(ck+1 \ck) = Y] Prd{dk+l) x Pra(ck+1 - ck + dk+1) x ( 1 — ) , n , \ ck+i + ak+i + 1/ (4.14) where Prd(x) and Pra(y) denote the probabilities that jc.and y mini-sources becomes idle and active, respectively at fy+i, and are given by: Prd(x) = B(N3,x,l-e-M), ; >. (4.15) Pra(y) = B [ N m - l - c k - N a , y , l - e ' ^ ) . Recall that capturing minirsources always stay active. Hence if mini-sources become idle, <fy+i slots are released for capturing at fy+1. Note also that in order to' effect the above transition, V must not capture the released slots. This occurs with probability 69 Chapter 4. Contention free RA access with cyclic capturing 1 - [dk+1/(ck+1 + dk+1 + 1)], as there are ck +- (ck+1 - ck + dk+1) +1 = ck+1 +dk+1 +1 mini-sources including V participating in the capturing process and each of them has equal chance of getting the released slots. The transition probability of entering the absorbing state from any state is then given by { Nm-1-Ns l ~ £ P r ^ ) Sk = ck^ ( 4 1 6 ) i J sk = il By using equations (4.14) and (4.16), a transition probability matrix 0 of size (Nm—Ns+lxNm—Ns+l) can be formed. The m-th row and n-th column of 0 is given by: 0(m,'re) = < { Prt(n\m) 1 < m < Nm - Ns, 1 < n < Nm - Ns, Nm — l — Ns 1 - E Pn(j|m) 1 < m < Nm - Nsn = Nm - iV s + 1, ( 4_ 1 ? ) 1 m = Nm - Ns + l,n = Nm - N.s + 1, 0 otherwise. Define the (1 xNm—Ns+l) initial probability matrix Z with the «th element given by 7/1 ^ _ ( 5 ( ^ - 1 , 1 1 - 1 + % ) n = l , 2 , 3 , . . . , i V m - i V s . l ' j ~ \ 0 . n = Nm-N, + l ( 4 , i 8 ) The first case of (4.18) gives the probability that Co = q ; q = n — 1 and the second case represents that V is not in the absorption state 0, at to. Recall that we are considering the case where there is no idle RA slot at to so there are at least Ns active mini-sources. Denote 0* as the k-th power of matrix 0 and Z x Qk(u) as the «th element (w=l,2,3..JVm—A^+l) of the (lxNm—Ns+l) matrix Z x 0 f c . Assume that when there are available R A slots at to, V can complete a reservation without any packet loss. Note that this is not necessarily true because slots are not assigned in a first come first serve fashion so mini-sources which 70 • ' Chapter 4. Contention free RA access with cyclic capturing becomes active later than V may preempt V to get the available slots. Nevertheless we find from the simulations that this assumption is reasonable unless the number of R A slots is too small. Hence the probability that V does not lose more than / (/=0,1,2,3 . . . ) packets during the reservation (i.e. obtain a reservation at or before fy where k — Z + l ) is : N3-l Prc(< I) = Z x Q l + 1 ( N m - N s + 1)+J2 B(N™ ~ 1^''r)- <4-19) 3=0 Note that the first and second term of (4.19) gives the probability that V can obtain a reservation within the specified time period fy when the number of available R A slots at to is equal to zero, and greater than zero respectively. Hence the fraction of reservation with loss duration greater than / frames is given by: Prc(> l) = l - | z x el+1(Nm - Ns + 1) + J2 B(N™ ~ i 'J 'OJ (4-20)' 4 . 4 Simulation and analytical results A simulation program written in Simscript LT.5 was exercised to compare the per-formance of the R A access protocol with that predicted by the above theoretical model, using the parameters in Table 4.2. Table 4.2. Simulation parameters for analyzing the performance of R A access (i) Bus data rate 155 Mbps (ii) No. of M A N node 21 (iii) No. of transmitting M A N node on bus A 20 (iv) Distance between adjacent node 10 slots (v) Simulation time 200,000 frames Voice V T V C (vi) No. of VBRS per node 2 1 1 (vii) Maximum bit rate (Kbps) 64 2x64 6x64 (viii) OL 0.4 2.8 1.8 (ix), fi 0.6 1.1 2.1 71 Chapter 4. Contention free RA access with cyclic capturing 4.4.1 P L R Figure 4.4 shows the simulation results for the PLR of the network in comparison with theoretical computations from (4.4). To facilitate comparisons, the number of R A slots in the x-axis has been normalized with respect to fx = rNm, the average number of packets generated by all VBRS per frame, giving Nsn=Ns/fi. The graph shows that the simulation results are in good agreement with the theoretical computations. As expected, the PLR drops dramatically when Nsn > 1. Note that Nsn — 1 ensures that the number of R A slots is just sufficient for the average number of packets generated per frame, and is the target for full statistical multiplexing. As the number of VBRS increases, the required Nsn for meeting the target PLR approaches this ideal target. Figure 4.5 shows the PLR variations along the M A N bus for the three different types of VBRSs. Note that for voice, station 2(n-l)+l and VBRS 2n belongs to the same node n, where n=l, . . . ,20. The solid lines give the PLR as calculated by (4.4). It can be seen that R A access is reasonably fair even when the number of R A slots is less than Nsn (i.e., when all VBRS are "starving"), and each VBRS has PLR as predicted by (4.4). 72 Chapter 4. Contention free RA access with cyclic capturing Pi PL, Pi OH 10 10 r-10 10 10 10 -5 : 10 t-io"' 10" -] 10 io"' Voice (o sim, - ana.) Target line ; . Nv= i =1200 \ \Nv=300 I \ r \ i 1 .8 0.9 1 1.1 1.2 1.3 Nsn Video phone (o sim, - ana.) =20 ! Target line : i Nv=600 V y Nv=150 i \ i \ i i 0.9 1 1.1 1.2 1.3 Nsn Video conference (o sim, - ana.) Pi OH Nv=20 Figure 4.4. PLR of the network by theoretical computations (curves) and by simulations (points) 73 Chapter 4. Contention free RA access with cyclic capturing Voice (x 0.94Nsn, o Nsn, + 1.25Nsn) 10 - R 10 10 :v X . - x X y y . , X X Y X X , . X V „ V X X Y V X X X X . . y y y s 0 „ O O O r ) O Q O , O o 0 o c O n c O O , n 0 O c , o O ° n n n c , n O O n O O O u u o ' + + + + + + + + "*"+ '+++ J L J I I I L 9 13 17 21 25 29 33 37 VBRS index —i OH 10 :r 10 10 Video phone (x 0.91Nsn, o Nsn, + 1.08Nsn) y y y y y -e—u o o o—o o o u o o o -e—e—e-+ + + -r + + + + + + + + J _L J I I L 1 3 5 7 9 11 13 15 17 19 VBRS Index Video conference (x 0.90Nsn, o Nsn, + 1.05Nsn) 10 ; -10 ( i o o cr Q O O O O O O ^ O 73 o cr O n O O -4=—± 1 =k- +. +—=F" J ' I ' _|_ 1 3 5 7 9 11 13 15 17 19 VBRS index Figure 4.5. Comparison of theoretical and simulated PLR relative to station positions 74 Chapter 4. Contention free RA access with cyclic capturing 4.4.2 Packet delay and delay jitter Figures 4.6 and 4.7 show the simulation results of the mean and standard deviation of packet access delay in comparison with those calculated from (4.11) and (4.12), respectively. It can be seen that the simulation results are in good agreement with the theoretical calculations. The above theoretical model is almost exact for voice which has only one mini-source per VBRS but is only approximate for V T and V C with M>\ because mini-sources of the same VBRS are not totally independent (e.g., a mini-source entering active state may gain a slot left vacant by another mini-source of the same VBRS entering idle state without having to go through the capturing process). Nevertheless the theoretical calculation provides a good approximation especially when Nsn is large. The shapes of the graphs can be explained as follows. When Nsn is small, an active mini-source has nearly equal probability of reserving any one of the R A slot resulting in Tm « 3 ms and a nearly constant Tsd. When Nsn>l, an active mini-source has a good chance of reserving a slot soon after packet arrival, giving a dramatic decrease in Tm and TS(i a t around Nsn=l. The rate of decrease is sharper when AV is larger due to increased effectiveness of statistical multiplexing. As (4.11) and (4.12) are limited by at least their first term, Tm and Tsd cannot be decreased further by increasing Nsn indefinitely. It is interesting to note that Tsd actually increases slightly (about 1%) at around ^ ,,=1 which becomes more obvious as Nv increases. This is because when Nsn approaches one, more slots become available resulting in slightly higher variations in access delay. Eventually the second term of (4.12) becomes dominant which causes the sharp decrease. The target line for voice has not been shown because it is outside the range of the graph (i.e., the simulation and analytical results are far better than the QoS requirements). For V T / V C , packet delay and delay jitter can be limited to under 1 ms at around Nsn=l. 75 76 Chapter 4. Contention free RA access with cyclic capturing Voice (o sim, - ana.) Nsn Video phone (o sim, - ana.) 2.02 I ; - - • -0.9 . 1 1.1 1.2 . 1.3 Nsn Video conference (o sim, - ana.) 2.02 I - -0.9 1 1.1 1.2 1.3 Nsn Figure 4.7. Standard deviation of packet access delay (theoretical - curves, simulation - points) 77 Chapter 4. Contention free RA access with cyclic capturing 4.4.3 Loss duration performance criteria Figure 4.8 shows the simulation results of percentage of reservations with loss duration greater than 50 ms and 12 ms for voice and VT7VC, respectively, in comparison with the theoretical results calculated from (4.20). Note that the following linear interpolation has been used for voice PTc(> 8.3) = 1 - {PTc{< 8) + 0.3 x [Pie(< 9) - PTc{< 8)]}. ' • (4.21) where 8.3 frames corresponds to 50 ms. The graphs indicate that the simulation results agree closely with the theoretical results, and the percentage of reservations with loss duration greater than the specified values drops sharply at Nsn=l, especially when the number of VBRSs is large. It can also be seen that as the number of VBRSs increases, the Nm required to.satisfy the performance criteria decreases dramatically and approaches the ideal value of one. 4.4.4 Utilization Figure 4.9 shows that the simulation results of utilization agree closely with the theoretical results calculated by (4.13). It also indicates that utilization is apparently dependent only on Nsn when the number of VBRSs is large, especially for Nsn>l. In this case, utilization is close to 100% when Nsn<l and drops almost linearly with Nm when Nsn>l. As the number of VBRSs increases, the required Nsn for providing satisfactory service will approach one as discussed above, hence a nearly 100% utilization can be achieved. 78 Chapter 4. Contention free RA access with cyclic capturing 50 Voice (o sim, - ana., LD=50ms) ° \ \\ GO (—1 40 o lervati 30 <D l-i 20 _ Nv=150—V-\ ^ \ Nv=40 o 10 Nv=500\ \ Target line \ ^ 0 0.9 1.1 Nsn 1.2 1.3 Video phone (o sim, - ana., LD=12ms) c -4—> Nsn a > 40 30 10 Video conference (o sim, - ana., LD=12ms) \ \ \Nv=20 Nv=50 ¥ \ \ N v = 8 0 \ \ Target line 0.9 1 Nsn 1.1 Figure 4.8. % of reservations with loss durations > L D (theoretical - curves, simulation - points) 79 Chapter 4. Contention free RA access with cyclic capturing Voice (o sim, - ana.) 100 95 90 85 Nv=300 80 Nv=*4a^5^ 75 -70 i i i i 1 Video phone (o sim, - ana.) 100 Nv=600 95 90 Nv=150 N v = 2 0 ^ V Util. 85 80 75 70 i i i i i 0.9 1 ' 1.1 1.2 1.3 Nsn Video conference (o sim, - ana.) Nsn Figure 4.9. Utilization (theoretical - curves, simulation - points) 80 Chapter 4. Contention free RA access with cyclic capturing Table 4.3. Capacity improvement for R A access Applic. No. of Target Target Target . (a) Req. (b) Req. Multiplex VBRS PLR T m Tsd R A PA gain bandwidth bandwidth (b)/(a) Voice 1200 le-2 25ms 130ms 31 Mbps 77 Mbps 2.5 V T 600 le-6 1ms 1ms 58 Mbps 77 Mbps 1.3 V C 200 le-9 1ms 1ms 41 Mbps 77 Mbps 1.9 4.4.5 Capacity improvement Based on the above results, Table 4.3 compares the bandwidth requirement of PA and R A access for providing satisfactory service to the above multimedia applications by meeting the stated QoS requirements. It indicates that R A access enables significant capacity improvement compared to PA access. Although QA access should also attain comparable capacity gain, access is not fair and access delay is not guaranteed and subject to variations, so that this access method is not desirable for VBRIT. We have found that the satisfaction of the PLR performance criterion can generally guarantee the satisfaction of all the other performance criteria including the loss duration criterion. Note that given packet, loss ratio PLR, it already guarantees that more than 1 — of the reservations are completed without any packet loss. This can be shown easily by noting that if fraction x of the reservations are completed without any packet lost, the rest (1—x) must have lost at least one packet each, giving a lower bound packet loss ratio of (1 — x) x j3f where •jj is the expected number of packets generated by a mini-source during each active period (or reservation). Hence if the required packet loss ratio is very low, nearly all reservations must be completed without any.packet loss and other performance indicators may become less important. For example with 1//?=1 sec, PLR=\0~9 can already guarantee that more than 99.999983% of the reservations are completed without any packet loss. Consequently PLR may be regarded as the key performance indicator for the VBRIT. It can also be seen from the table that higher capacity improvements (i.e., 81 Chapter 4. Contention free RA access with cyclic capturing higher multiplex gain) can be achieved when the required PLR is higher (e.g. voice) or the traffic source has larger peak to average bit rate (e.g. VC). 4.5 A n alternative packet management strategy at a M A N node Besides the above packet management strategy using a CQ to register the capture requests, we have also investigated an alternative strategy. It does not require the use of a CQ and can further reduce the packet access delay. However as discussed below, its implementation may be difficult especially in high speed networks. For the reason of completeness, this section analyzes this alternative method. In the following discussion, the previous and the alternative packet management strategy will be referred as PMS1 and PMS2 respectively. The basic concept of PMS2 is that A C reserves an idle R A slot if it can be filled with a packet and releases a reserved R A slot if it cannot be filled by the registered VBRS. A l l the VBRSs of a M A N node are connected to a common node buffer (NB), the previous CQ is no longer required and the A C still maintains a SR to record the identity of the local VBRS using each slot. Packets as generated by the VBRSs are stored in the NB in the order of their arrivals. The A C adds a local header including a time stamp and a VBRS identity to each packet entering the NB. This local header is removed before a packet is transmitted into a M A N slot. When a RA slot s arrives on the forward bus, the A C takes one of the following actions if the respective condition is true: CAP=0 in slot s and NB is not empty That means slot s has not been reserved by any VBRS in the M A N . Suppose that the first packet in the NB belongs to VBRS SI, set CAP=1 in the A C F of slot s, write the corresponding VCI for SI in the segment header, send the first packet in the slot and update the VBRS entry for slot s in SR with SI. V B R S entry for slot s in SR = Y>0 This identifies slot s as being reserved by VBRS Y . Write the corresponding VCI in the segment header of slot s and transmit the next packet of Y in the slot. If there is no packet belonging to Y in the N B , indicating that . 8 2 Chapter 4. Contention free RA access with cyclic capturing ' this slot is no longer required due to a bit rate decrease or a better slot in terms of access delay has been reserved for Y , release slot s by setting CAP=0 in slot S to allow its capture by downstream nodes, and set VBRS=0 in the respective SR entry. Besides eliminating the need of a CQ, PMS2 has the following interesting property. Consider that a mini-source V which becomes active at time tactiVe captures/reserves a slot s i at time tactive+81. In a later frame, a slot s2 arriving at time tactiVe+62 where 0< 62 <6l is available for mini-source V. In PMS1, mini-source V still transmits in slot si whereas in PMS2 mini-source V captures slot s2 at tactive+62 and releases slot si at tactive+Sl. Nevertheless as confirmed by simulations, PMS1 and PMS2 have the same PLR. This is because slot s2 is only available if no upstream VBRS requires it, reserved slot si cannot be used by the upstream VBRSs in both PMS1 and PMS2 and although s2 is captured by V, slot s i is released to the downstream VBRSs giving the same number of available R A slots to the downstream VBRSs in the same frame. Consequently PMS2 does not increase or decrease packet losses. Effectively PMS2 allows an active mini-source to keep on acquiring a RA slot which is closer and closer to its packet arrival while maintaining the same reserved bandwidth. Of course, in doing so the desired property of isochronous transport service is sacrificed. It is difficult to analyze the packet access delay of PMS2 even with the mini-source model because, the mini-sources keep on swoting slots. Nevertheless an approximate analysis has been conducted based on the following assumptions in addition to the previous ones. 1. A l l state changes, slot allocations and packet transmissions are synchronized at tk (£=1,2,3....). 2. A mini-source V becomes active at t\ and s\, S2, SNS are the 1st, 2nd, 3rd, ... /Ysth R A slots that passes V after each synchronized instant tk 3. If V becomes idle at tk (£=2,3,4,...), it will not have any packet to send at and after 83 Chapter 4. Contention free RA access with cyclic capturing fy. The probability that the active period of V ends at fy is given by Pend{k) -{k-l)pf _ -kpf (4.22) (i.e. it becomes idle between fy.j and fy). Note that by definition, V cannot become idle at f i . 4. Reserved slots are released independently and the probability that a slot reserved at fy_i is released at fy is given by PTt\ — . 5. To facilitate the later analysis, we assume that V can always acquire a R A slot at the synchronized instant t\ for the first packet transmission. Based on (4.7), the probability that V transmits the first packet in slot sy, (y=l,2,3...Ns) is given by the following lxiVy matrix where n is the number of reserved R A slots at fi = = fj2 B(Nm-l,n,r)g{l,n) ^ B(Nm - 1, n, r)g(2, n) .... B{Nm - l,n,r)g(Ns,n)] n = 0 n=0 n=0 (4.23) This assumption should be reasonable if Nsn is greater than one such that the chance . of having no available R A slot at fi is very small. 6. V transmits the subsequent packets (i.e. the k-th packets, k > 2) at fy using the first available slot. Given that V has reserved slot sn at fy_i, the probability that V transmits the k-th packet in slot sm at fy is given by the following matrix: r = 1 0 Prel (1 - Prel) 0 0 0 0 Prel (l-Prel)Prel (1 ~ Prel? 0 Prel (l-Prel)Prel- (1 ~ Prel f Prel (1 ~ Prel? (4.24) -Prel (1 Prel)Prel (1 Prel) Prel (1 Prel) Prel The above matrix is derived by making the following assumptions: a. If V reserves sn at fy_i and slot sm.becomes available at fy, V will capture/reserve sm at fy if m < n. In case multiple number of slots are available at fy, V acquires 84 Chapter 4. Contention free RA access with cyclic capturing the slot closest to tk (i.e. the one with the smallest ni). Hence the probability that V can get sm at tk is given by the probability that sm but none of s\, S2-.. sm.\ is released at tk which is (1 — P r e / ) m _ 1 P r e / . Note that this assumption is only an estimate because the released slot sm may be acquired by other mini-sources. Nevertheless as found from the simulation, if the number of R A slots is large, the chance of having two mini-sources wanting the same R A slot s (i.e., s is the closest R A slot to both of them) is small making this assumption more realistic, b. V still uses its previously reserved slot sn (i.e. the one reserved at f^-i) if none of the R A slots s\, S2, •••• ,sn.\ is released at tk. This occurs with a probability ( l - P r e l ) " " 1 . Denote PADm(k) as the packet access delay (in slots) experienced by the £-th packet of V which is given by: 0 d 2d 3d PADm{k) = - + ZxT fc-1 X (4.25) .(Ns-l)d. Note that the first term is the residue waiting time and the h-th element (h= 1,2,3, ... ,NS) of the matrix E x r . f c _ 1 gives the probability that V transmits the k-th packet in slot sn resulting a further delay given by the second term. If V becomes idle at tk (£=2,3,4...), the mean packet access delay among the 1st, 2nd .... (£-l)th packets is given by fc-i 3=1 (4.26) Averaging over all possible k (£=2,3,4....) noting that V must not be idle at t\, the mean packet access delay is Tm = Y Pend(k) X Tmk = £ ]T PADm(j) fc-1 (4.27) k=2 k=2 3=1 85 Chapter 4. Contention free RA access with cyclic capturing Similarly, the standard deviation of the packet access delay TSA> can be found as follows, k-i k=2 j=l 2 m (4.28) where PADv(k) = - + ExT k-i x 0 d2 (2d? (3d)' (4.29) Figures 4.10 and 4.11 show the simulation results of the mean and standard deviation of packet access delay of PMS2 in comparison with those calculated from (4.27) and (4.28), respectively using the simulation parameters in Table 4.2. In calculating (4.27) and (4.28), the summations stop after the 50,000 th iterations (i.e. an active period of 50000x6ms=30 s) which should be large enough to obtain very accurate results. It can be seen from the figures that the simulation results agree closely with the analytical calculations when Nsn is large. However as expected, when Nsn is small, the above analysis fails because assumptions (4), (5) and (6) are no longer valid. Table 4.4 compares the mean and standard deviation packet access delay of PMS1 and PMS2 as found from the analytical calculation based on the simulation parameters given in Table 4.2 with Nsn=l.3. It can be seen that PMS2 can further improve the mean and standard deviation packet access delay by about 40%-60%. However PMS2 has some disadvantages: Table 4.4. Comparison of PMS1 and PMS2 Access delay mean (ms) Access delay std. dev. (ms) VBRIT P M S ' l PMS 2 Improve % PMS 1 PMS 2 Improve % Voice 1.16 0.47 59% 1.23 0.66 46% V T 0.57 0.28 51% 0.58 0.37 36% V C 0.34 0.16 53% 0.41 0.23 44% 86 Chapter 4. Contention free RA access with cyclic capturing Figure 4.10. Mean packet access delay for PMS2 (theoretical - curves, simulation - points) 87 Chapter 4. Contention free RA access with cyclic capturing 1.3 > T J 5 5 0.5 0.1 Voice (o sim, - ana.) o o i o o o 1 1 1 1 1 1 o o 1 1 o 0.8 0.9 1 LI 1.2 1.3 1.4 1.5 1.6 1.7 l.S Nsn Video phone (o sim, - ana.) > "3 55 Video conference (o sim, - ana.) > o T3 -4—> Figure 4.11. Standard deviation of packet access delay for PMS2 (theoretical - curves, simulation - points) Chapter 4. Contention free RA access with cyclic capturing 1. Its implementation may be difficult because A C needs to search through all the packets in NB to determine whether a captured slot is still required by the VBRS registered in the SR and the search must be performed in a very, short time (in the order of ^s for a bus speed of 155Mbps and even ns for a bus speed of 655Mbps) for high speed MANs 2. In most cases, A C is required to retrieve a packet in the middle of the NB which complicates buffer management 3. Although buffering time is reduced, PMS2 does not preserve the isochronous property of the transport after successfully capturing a slot. Consequently PMS1 should still be preferred for the practical implementation of R A access. In fact by spreading the R A slots evenly within a frame, PMS1 already provides a well acceptable Tm and Tsd as shown in the above results. 4 . 6 S u m m a r y We have proposed a novel contention free R A access protocol with a new cyclic capturing mechanism and derived a theoretical model for analyzing its performance in detail. Results show that the R A access protocol is fair, allows full statistical multiplexing while providing a nearly isochronous transport service arid yields consistent performance as predicted by the analytical calculations. An alternative packet management strategy has also been proposed and analyzed to further reduce the packet access delay. However it sacrifices the previous isochronous service property and may be difficult to implement in high speed M A N s . Hence the original packet management strategy, which has already achieved a well acceptable packet access delay, should still be preferred. 89 Chapter 5. Simulating RA access with video source models Chapter 5 Simulating RA access with video source models In chapter 4, the performance of RA access has been analyzed by means of a mini-source model. While the mini-source model is well suited to model video conference type pf traffic and facilitates theoretical analysis, it is not suitable for modelling video sources with frequent scene changes (e.g. motion video) [81]. To further demonstrate the effectiveness of R A access for transporting video traffic; we simulate R A access with the autoregressive (AR) video and motion video (MV) model in this chapter which are known to be effective to represent video sources without and with scene changes, respectively. Results confirm that R A access are well suited for transporting video traffic while maintaining efficient bandwidth utilization. 5.1 Video services and modelling of video s o u r c e s As voice and video is expected to account for the majority of the VBRIT in M A N s , PCNs and BISDNs, we focus on video in additional to voice in this thesis. In general a video source generates fv video frames per second with npix pixels per frame and n\,it bits per pixel to represent the digitalized video information. The values of fv, npix and ribit depends on many factors such as resolution, application and screen size as shown in Table 5.1 [80]. As it can be seen from Table 5.1, the raw data rate of a video source ranges from 2 to 800Mbps. Fortunately this raw data rate can be reduced significantly by means of video compression techniques such as intraframe discrete cosine transform coding and interframe motion compensated prediction [82] due to redundancy in video data. In general there are two types of redundancy: • Spatial and temporary redundancy — Pixel values are correlated with their neighbors both within the same frame and across frames. Therefore to a certain extent, the value of a pixel can be estimated based on that of neighboring pixels 90 ' Chapter 5. Simulating RA access with video source models Table 5.1. Types of video services Video service No. of frames per sec. No. of pixels per frame No. of bits per pixel Approx. raw data rate Approx. compressed date rate Low resolution real time video with quarter screen 15 128x120 9 2 Mbps 64 Kbps High resolution real time video with quarter screen 15 128x240 9 4 Mbps 384 Kbps High reolution real time video with full screen 30 128x240 9 8 Mbps 2 Mbps Low resolution non-real time video 10 352x240 9 8 Mbps 384 Kbps VCR-quality server 30 352x240 24 61 Mbps 1 Mbps Studio quality server 30 640x480 24' 221 Mbps 4 Mbps H D T V 30 1,125 lines 24 800 Mbps 60-130 Mbps • Psychovisual redundancy — Human eyes are less sensitive to fine spatial detail and near object edges. Hence some controlled impairments in the compressed pictures caused by bit rate reduction are invisible. As shown in Table 5.1, current video compression techniques are capable of supporting most video services under 1-2 Mbps and high quality broadcast video services between 4 and 130 Mbps. In recent years, these video compression techniques have led to the development of various standards for multimedia applications such as JPEG for still images compression [83], H.261 [84] for video conference compression and M P E G [85] for moving images video compression. In general, video compression is performed by means of differential coding methods which generates VBRIT. Hence ideally we require a 91 Chapter 5. Simulating RA access with video source models transport technique that can provide variable bit rate isochronous channels for supporting compressed video services. Similar to voice, the arrival of video packets are correlated in terms of the amount of information generated per frame. To measure this correlation, the following autoco-variance function is commonly used: C(m) = E[RkRk+m] - (E[R]f (5.1) where denotes the bit rate in the kth video frame, E[.] denotes expectation and E[R] is the mean bit rate among all video frames. In general, there are two types of correlations: short term and long term correlation. Short term correlation corresponds to uniform activities which lasts for a short duration (on the order of a few hundred milliseconds) and decay exponentially with respect to time (i.e. C(m) decays exponentially with m). Typically it occurs within the same video scene causing only small fluctuations in the bit rates. The mini-source model is well suited to capture short term correlation. Long term correlation corresponds to scene changes causing an abrupt increase in bit rate in a very short period of time. However its effect lasts for a relatively long time (on the order of a few seconds). Unfortunately long term correlation cannot be captured by the previous mini-source model. Generally speaking, the effect of long term correlation can , be ignored for video conference applications because scene changes occur infrequently. It is commonly agreed that the autoreggressive (AR) model [79] and the previous mini-source model provide a rather accurate approximation for the bit rates of a video source without scene change (e.g. video conference and video telephone). In particular these two models can fit the autocovariance function C(m) of the experimental data nicely [79]. Although the A R model is popularly used in the literature, it is difficult to analyze theoretically so that it can only be used in simulations. To model video sources with frequent scene changes (e.g. motion video, MPEG), both the long term correlation and the short term correlation have to be captured. There are numerous proposals for modelling 92 Chapter 5. Simulating RA access with video source models this type of video source. Most of them are extensions of the mini-source model and the A R model. Typical examples are given as follows. A simple extension of the previous birth-death Markov process for modelling video sources with frequent scene changes is to include an additional state to represent the scene cut. A l l other states then transits towards this scene cut state with a predefined probability [86]. The previous birth-death Markov model (mini-source model) is generalized in [87] using a two-dimensional Markov chain. In the generalized model, the scene change and the uniform activity are represented by a high and low data rate respectively. The steady state bit rate can also be thought as the superpostion of high level mini-sources and low level mini-sources respectively. [88] extends the multistate state Markov chain model in [89] for video conference traffic to cover general broadcast video traffic such as entertainment television and news. The transition matrix of the Markov chain is computed by means of a special statistical process using different probability distribution (e.g., Pareto, Weibull, etc.) to represent the number of cells per frame. It is found that the choice of the distribution is strongly dependent on the type of video traffic. A discrete-state continuous time Markov process with batch arrivals is proposed in [90] for modelling video sources with scene changes. The uniform activity is represented by the mini-source model while the scene changes are represented by a batch arrival process with constant batch size. In [81], a video source with scene change is modelled by the superposition of two independent A R process to capture the uniform activity and a Markov controlled process to incorporate the effect of scene change. [91] proposes a motion classified A R video source model. The model captures the motion of the video scene by using a first order A R process with time varying parameters controlled by a Markov process. 5.2 A R and MV model To verify the effectiveness of R A access for transporting different types of video traffic, we employ the A R model in [79] and the video model in [81] (referred as motion 93 Chapter 5. Simulating RA access with video source models video (MV) model in this thesis) for the later simulations. We choose these two models because the A R model is a widely used model for video source without scene change and the effectiveness of the M V model for modelling video sources with scene changes has been validated by experimental data obtained from an independent source in [92]. 5.2.1 A R model In a general A R model, the bit rate of a video source during the k-th video frame, Rk (Mbps), is represented by the following h-th order A R process h Rk=Yl amRk-m + blVk (5.2) m=l where am and b are the coefficients, wk is a sequence of independent Gaussian random variables. We consider a first order A R model which is commonly used due to its simplicity [79] i.e. Rk = aiRk_i + bwk (5.3) It is commonly assumed that wk has a mean of rj and variance of 1. By taking the mean and variance of the left and right hand side of (5.3), the steady state mean E[R] and variance Var[R] of the bit rate can be found as: •E[R] = —^—V (5.4) 1 — ai Var[R} = - ^ (5.5) 1 — af Note that the mean and variance of Rk and Rk_i in (5.3) both equal to E[R] and Var[R] respectively. By fitting the mean bit rate and au toco variance function of the experimental data generated by a video phone [79] with those calculated from the A R model, it was found that ai=0.8781, 6=0.1108 and 77=0.572 in [79]. The steady state distribution of R is Gaussian (i.e., normal distribution) with mean E[R] and variance Var[R]. In our model, we consider that the bit rates are quantized at 94 Chapter 5. Simulating RA access with video source models nx64Kbps hence the effective bit rate in the quantized A R model is Rk = [^4] x GAKbps. For a VBRS modelling by a nx64Kbps A R process, the mean (m) and variance (a2) of Rk (i.e. the effective bit rate in our quantized A R model) are given by A \Jn-E[R]\ Jn-1-E[R]\] and where M n2 x n=l Var[R] ) ~ \ Var[R] J (5.7) z 2 e~~du ' (5.8) and Mx 64Kbps is the maximum quantized bit rate. The above equations are derived by noting that the steady state bit rate of the A R model has a normal distribution, hence the probability that Rk = n x GAKbps (i.e. (n — 1) x MKbps < Rk < n x QAKbps) is which is a standard result on normal distribution [70]. Note that when M is large, [i, w E[R] and a2 w Var[R]. 5.2.2 M V model The M V model is based on the video source model proposed in [81]. It captures the source characteristics through the mean, peak and variance of the bit rate as well as the average rate at which scene changes occur. Its effectiveness for modelling video sources with scene changes has been validated by the experimental data presented in [92]. In the model, the bit rate of a video source at the k-th video frame (Mbps) is made up by three components: Rk = Xk + Yk + Zk • (5.10) where Xk = cxXk^+Ak (5.11) 95 Chapter 5. Simulating RA access with video source models Yk = cyYk_1 + Bk (5.12) ZK = KkCk (5.13) Xk and Yk are two independent stationary first order autoregressive processes which purposes are to capture the au toco variance function of the video source bit rate accurately. As the autocovariance function of the experimental data found in [92] shows a sharp and a slow decay at low and high values of frame lag, respectively, at least two autoregressive functions are required for modelling the video source bit rate. cx and cy are two constant coefficients. Ak and Bk are two independent, normally distributed random variables with means \ia and and variances a2a and a\, respectively. Similar to the A R model, the mean and variance of X and Y are given by: E[X\ = - ^ - , Var[X] = - ^ (5.14) i cx i cx E[Y] = - ^ - , Var[Y] = -4-a ^ X Cy 1 L-y The purpose of Zk is to model the extra bits generated at scene changes. In (5.13), Ck is a sequence of independent normally distributed random variables with mean a/2 and standard deviation b/2 and the value of Kk is generated by a three state Markov chain {0,1,2} using the following transition matrix ~1-Pz 0 p z 1 0 0 0 1 0 (5.16) Typically pz has a small value so most of the time, Kk is in state 0. A scene change occurs when Kk changes from state 0 to state 2. The purpose of introducing state 1 is to make the effect of scene change lasts for two video frames. Thus the time between two scene changes is two plus a geometric random variable with mean l/pz. The mean and variance of Z can be found by the analytical calculations in [81]. As Xk, Yk and Zk are independent, the mean E[R] and variance Var[R] of the resultant bit rate R are given by: E[R] = E[X] + E[Y] + E[Z] (5.17) 96 Chapter 5. Simulating RA access with video source models and • ' Var[R] = Var[X] + Var[Y] + Var[Z] _ . (5.18) By fitting the empirical data in [92] including the autocovariance function with those calculated by the model, the choice of parameters are found to be [81]: ^a=0.02, (72=0.04964, fib=0A092, <r62=0.61819, ^=0.998, cy=0.9389, /?z=0.00667, a=W and b=2 As the A R model, the quantized bit rate is given by Rk — [(fft i l x 64if 6ps . Assuming that R has a normal distribution, the mean and variance bit rate of the nx64Kbps M V model can be found by substituting (5.17) and (5.18) in (5.6) and (5.7) respectively similar to above. 5.3 D iscuss ion on simulation results Unless otherwise specified, the simulation parameters follow that given in chapter 4. We shall focus.on evaluating PLR which is the main performance indicator as discussed in chapter 4. We consider that the video frame rate is /v=30 frames per second. In the original A R [79] and M V [81] models, the maximum bit rates are 8.25 Mbps and 30Mbps respectively. Unfortunately it is not possible to use these bit rates in the later simulation model because of very long simulation time. Instead we employ the A R and M V models to generate 6x64Kbps and 24x64Kbps VBRIT respectively. As mentioned before, these bit rates are expected to be popular for many important video communications such as 6x64Kbps for video conference and 24x64Kbps for M P E G and VHS quality video service. The simulated bit rates Rsim are obtained by multiplying the original bit rate R with a scale down factor SDF where SDF is = 21.5 and 2 4 3 x 0 6 x 4 1 x 0 1 6 0 a = 19-5 for the A R and M V model respectively. As all bit rates are scaled down by the same SDF, it is easy to show that E[Rsim] = E[R] x SDF and Var[Rsim] = Var[R] x SDF2. The mean (ju,-) and variance (a2) of Rsqim (i.e. the quantized bit rate of the simulated VBRS) can be found by substituting E[Rsim] and Var[Rs%m] into (5.6) and (5.7) respectively. 97 Chapter 5. Simulating RA access with video source models For the M V simulations, there are ten M A N nodes with one VBRS per M A N node). The distance between two consecutive M A N nodes is 10 slots. To check the correctness of the above formulas, we had simulated the above A R and M V models (i.e., the statistical processes) to obtain 100,000 video frames of bit rates. Based on the simulated bit rates, the mean and variance bit rates are found which are compared to the above analytical calculations as shown in Table 5.2. It can be seen that the simulation results agree nicely with the analytical calculations. We shall use the analytical values in the later analysis. 5.3.1 Bit rate trace Figure 5.1 and 5.2 show the bit rate traces of the video sources at the last M A N node for the A R and M V models respectively. It can be seen that the bit rates of the A R model are more uniform whereas the bit rates of the M V model shows occasional peaks corresponding to scene changes. The graphs indicate that when the normalized number of R A slot per frame Nsn is less than one, the reserved bit rate has difficulty in following the required bit rate especially when the required bit rate is high. When Nsn is increased to above 1, the difference between the required bit rate and reserved bit rate diminishes indicating that very good picture quality can be achieved. The bit rate trace analysis also indicates three main advantages of R A access for transporting video data: Table 5.2. Mean and variance bit rate of the A R and M V models Mean (x 64Kbps) Variance (x 64Kbps)2 Simulation Analytical Simulation Analytical A R 3.31 3.32 1.63 1.62 M V 13.68 13.63 11.60 11.35 98 Chapter 5. Simulating RA access with video source models 1. A video source can adapt its required bit rate to the reserved bit rate during network congestion. This gives more predictable picture quality and minimizes performance degradation. For example, the average bit rate may be lowered by increasing the degree of quantization applied to the discrete cosine transform coefficients in the case of discrete cosine transform coding [82]. 2. To minimize the impact of packet losses, future video system is likely to employ layered video coding methods [82] to distinguish essential video data from the non-essential video data. The former is vital for regenerating the original picture in a recognizable format but the later only improves visual quality. R A access facilitates the realization of layered video coding as deterministic (reserved) channels are available for transporting the essential video data. 3. As video compression is generally performed by means of differential coding between two consecutive frames, picture distortions caused by packet losses in one frame will propagate through subsequent frames. A simple and effective way to minimize the propagation of picture distortions is to refresh the receiver with a reference frame (i.e. a frame that employs only intraframe coding) periodically. With R A access, deterministic channels are available for transporting these reference frames to safeguard their delivery. While QA access should achieve comparable multiplexing gain as R A access, it is difficult to realize the above desirable features. It also suffers from the unfairness problem and cannot provide variable bit rate isochronous channels. Hence R A access should be a more preferable choice for transporting video traffic. 99 Chapter 5. Simulating RA access with video source models Required bit rate 2000 4000 6000 8000 10000 Reserved bit rate (Nsn=0.99) 0 i L_I_I , l _ L 2000 4000 6000 8000 10000 Reserved bit rate (Nsn=0.92) 71—•• ' ' : — • 6 i 0 i L _ l _ l , — ' 2000 4000 6000 8000 10000 Reserved bit rate (Nsn=1.00) 2000 4000 6000 8000 10000 Reserved bit rate (Nsn=1.07) 71 : • • • 6 i nn n 0 I , l _ _ L 2000 4000 6000 8000 10000 Frame number Figure 5.1. Simulations with A R model: bit rate trace for the last node 100 Chapter 5. Simulating RA access with video source Required bit rate 25 0' , , , 2000 4000 6000 8000 10000 Reserved bit rate (Nsn=0.99) 25 Q | , : , , 2000 4000 6000 8000 10000 Reserved bit rate (Nsn=1.03) 25 0 i , _ , 2000 4000 6000 8000 10000 Reserved bit rate (Nsn=0.92) 25 0' ' J • 2000 4000 6000 8000 10000 Reserved bit rate (Nsn=1.00) 25 Q | , , . 1-2000 4000 6000 8000 10000 Reserved bit rate (Nsn=1.07) 25 Q | , , , ; 2000 4000 6000 8000 10000 Frame number Figure 5.2. Simulations with M V model: bit rate trace for last node 101 Chapter 5. Simulating RA access with video source models 5.3.2 P L R Previously we have presented a formula for finding the average PLR based on bino-mial distribution. Here we present a more general method based on normal distribution. Our objective is to determine the PLR among AV homogeneous VBRSs given that the number of R A slots per frame is A^. Denote Xi as the number of packets transmitted by VBRS / in frame j. Let the probability distribution of Xi be Pr{Xi = x{} = Gi(x{) with mean and variance of m and cr2,- respectively. The total number of packets transmitted NV in frame j by all sources is X = £ Xl;. The probability distribution of X is given by i=i the convolution of all Gt(xi), i.e., G(x) = Gi(xi) * £ 2 ( ^ 2 ) * £ 3 ( 2 3 ) * * GNV(XNV). The average PLR can then be found by the following expression: jc (X-N3)XG(X) PLR = X = N s + l (5.19) V_rn £ x x G(x) x=l where Nm is the maximum bit rate among all VBRSs given by MxNv. The denominator gives the average number of packets that cannot be sent per frame because there are only Ns R A slots available and the numerator gives the average number of packets generated per frame. Hence (5.19) can be applied to calculate the average PLR of general VBRIT provided that the bit rate distribution of all sources are known. In this thesis, we assume that NV —• 00 and treat Xi's as continuous variables. These approximations will be validated by later simulation results. By. doing so, X will tend to be normal according to the well-known central limit theorem [70]. Then G(x) can be estimated as G(x) = -=L=e-(x-rf/2a2 • (5.20) NV NV where a2 = £ a2 and \i = £ Average PLR can then be found by putting G(x) i=l i=l into (5.19), i.e., -1 i v m PLR=—==('Yi ( x - N s ) e - ^ 2 ^ 2 ) (5.21) /iV27r(H x = N s + 1 102 Chapter 5. Simulating RA access with video source models Figure 5.3 shows the simulation results for the PLR of the network in comparison with theoretical computations from (5.21). It shows that the simulation results agree closely with that calculated from (5.21). As with the mini-source model, PLR drops dramatically at around Nsn=l which is the target for full statistical multiplexing. As the number of VBRSs increases, the required Nsn to meet the service requirement approaches this ideal target. Figure 5.4 shows the PLR variations along the M A N bus for the A R and M V model in comparison with the PLR calculated from (5.21). As with the mini-source model, reasonably fair service can be provided even when Nsn is small and each VBRS has PLR as predicted by (5.21). ei hi 10 AR (o sim, - ana.) 1 r ' —— r ^ ^ ^ ; ; r ^ N v = 2 0 ! Target line \ Nv=50\ : ' i . Nv=100 \ i i \ 0.9 1.1 MV (o sim, - ana.) oi OH Figure 5.3. PLR of the network for simulating R A access with video sources (curves: theoretical computations, points: simulations) 103 Chapter 5. Simulating RA access with video source models AR (x 0.9Nsn, o Q.99Nsn, + 1.14Nsn) )( X X X X X X X X X x x x — X X X x — x -C i C i n r \ r \ O C i r > n n r > . o O O o o o o 1 3 5 7 9 11 13 15 17 19 VBRS index MV (x 0.88Nsn, o 0.96Nsn, + 1.07Nsn) X X y x x x x ' x •e e e e o ° e ° TC 1"^  1 1 1 * ± + 1 2 3 4 5 6 7 8 9 10 , VBRS Index Figure 5.4. Comparison of theoretical and simulated PLR relative to station positions for simulating R A access with video sources 5.4 Summary The effectiveness of R A access for transporting VBRIT is further verified by simu-lating R A access with two different types of video source models. Besides the desired properties of statistical multiplexing and isochronous service, R A access also provides reserved channels for a video source to adapt its bit rate to the reserved bit rate during network congestion, to implement layered video coding techniques, and to send periodic reference frames to refresh the receiver so as to minimize the propagation of decoding errors. pi OH 10 1 n Pi J OH 10 -2 10 . i n 104 Chapter 6. Integration of heterogeneous VBRIT and connection admission control Chapter 6 Integration of heterogeneous VBRIT and connection admission control In chapter 4, we have considered the transport of homogeneous VBRIT. The pur-pose of this chapter is extend the previous R A access method for integrating heteroge-neous VBRIT over a M A N . Three methods: uncontrolled bandwidth sharing, dynamic bandwidth partitioning and dynamic bandwidth sharing as well as the associated C A C mechanisms are analyzed and compared. 6.1 Introduction and system model With the advent of various multimedia communication services, M A N s are likely to support different types of VBRSs with distinct call characteristics and quality of service (QoS) requirements hence RA access must be capable of integrating heterogeneous VBRIT effectively over MANs. In this thesis, we consider that VBRIT can be divided into Np=3 different classes: VBRITi (low class), VBRIT 2 (middle class) and V B R I T 3 (high class) representing traffic with low, medium and high QoS requirements respectively. Typical examples are voice for VBRITi , video conference for V B R I T 2 and motion video for V B R I T 3 . Unless otherwise specified, we consider the mini-source model as discussed in chapter 4 for the later performance analysis. Each VBRS of VBRTT) (i.e. VBRSy) is characterized by the parameters {Mj, aj, (3j, ReqPLRj} where M /x64Kbps is the maximum bit rate, l/ctj and \lj3j are the average durations of the idle and active periods respectively in the previous mini-source model and ReqPLRj is the maximum required PLR. There. are.NVj VBRS/ in the network with an resultant bit rate distribution given by B3(x) which is the probability that VBRIT ; requires x R A slots in a frame. The mean and variance of Bj(x) is iiy, and o\ respectively. With the mini-source model [79], it can easily be shown that 5 J ( x ) = ( ^ ) r J x ( l - r J ) ^ - 1 (6.1) 105 Chapter 6. Integration of heterogeneous VBRIT and connection admission control where r, = atj/(atj + f3j) and Nmj = NVjMj (i.e. the total number of mini-sources for VBRIT/). HVJ and cx2/. can also be found as: flVj = rjMjNV:J packets/frame (6.2) and 2 °Vj = rj(1 ~ rj)MjNVj packets2/frame (6.3) In this thesis we assume that there is a large number of VBRSs so that Bj(x) has a normal distribution given by: 5 i(x) = - = = = e - ( I - ^ ) 3 / H - (6.4) This also facilitates the later theoretical analysis. Note that in general Bj(x) can also be found exactly by convolution if the bit rate distributions of all VBRSs are known. There are Ns R A slots (see the format in chapter 4) in a frame which are spreaded evenly by the semi-uniform slot spreading method in Appendix B. The purpose of the later analysis is to evaluate three different methods for multiplexing VBRITj , VBRIT2 and VBRIT3 over the R A slots. An important issue for integrating different VBRIT over a M A N is C A C which is defined in CCITT recommendation 1.311 [93] as "the set of actions taken by the network at the call setup phase in order to establish whether a connection can be accepted or rejected". In general a new connection is accepted only if its required QoS can be fulfilled without degrading the QoS of existing connections. In the conventional circuit switching technique, C A C can be performed easily based on the peak bit rate of a call (i.e. deterministic multiplexing). Although this method is simple, it is very inefficient if the traffic sources are bursty such as video. To improve bandwidth utilization, statistical multiplexing instead of deterministic multiplexing will be used in the emerging BISDNs which implementation relies on an effective C A C mechanism. Unfortunately C A C for BISDNs is still an open problem at the present moment. Some representative proposals 106 Chapter 6. Integration of heterogeneous VBRIT and connection admission control are given as follows. A C A C mechanism was proposed in [94] based on the assumption that the aggregate traffic rate has a Gaussian distribution. A call is admitted if the probability that the aggregated bit rate is less than the link capacity remains under a target value. A fast buffer reservation method was proposed in [95] in which a bursty source is characterized by a two state Markovian model. When a source is active, a pre-specified number of buffer slots in the link buffer is reserved for the duration of the active periods. Note that while R A access works in the same principle as this method, they are not the same because R A access and the fast buffer reservation operates in a distributed and a centralized architecture respectively. To decide whether a new connection can be accepted, the excess demand probability which is the probability of requiring more buffer slots than are available is re-calculated based on the new call information. The call is accepted if this probability is smaller than a predefined value; otherwise it is rejected. In [96], a C A C mechanism was proposed based on the concept of equivalent capacity. Again a connection is characterized by a two-state Markov process. By means of a fluid flow model, the total equivalent capacity among all connections are estimated which is the required bandwidth to maintain a desired buffer overflow probability. A new connection is accepted if the total equivalent capacity is less than the link bandwidth. Besides the classical methods, C A C mechanisms based on neural networks and artificial intelligence techniques have also been studied [97, 98]. While the above C A C mechanisms cannot be applied directly for the following analysis, they provide good references for solving the later C A C problem. To facilitate the later analysis, we focus on PLR as the main QoS indicator which is the common approach adopted in other literature on C A C . Effectively V B R I T i , V B R I T 2 and VBRIT 3 can tolerate moderate, low and nearly zero packet losses, respectively. Although access delay and delay jitters are also important for VBRIT, these two QoS requirements can basically be satisfied if the PLR requirement is fulfilled as shown in chapter 4. In fact 107 Chapter 6. Integration of heterogeneous VBRIT and connection admission control access delay can be greatly reduced by spreading the R A slots as evenly as possible and delay jitters is essentially zero once a reservation is secured. To facilitate the discussion, we consider that the bandwidth managers are collocated at the HOBs and all calls are duplex such that the required number of RA slots in bus A and B are the same. Due to symmetry, we assume that all call requests are received and processed by HOB A . Upon a successful call admission, HOB B then assigns the same number of R A slots in bus B accordingly. In mathematical term, a call can only be accepted by HOB A if PLRj < ReqPLRj for all j (6.5) where PLRj is the PLR for VBRIT/ upon accepting the new call. 6.2 Uncontrol led bandwidth sharing (UBS) In UBS, we consider that all classes of VBRIT are multiplexed together by the previous R A access protocol without imposing any control mechanism. Essentially the capture requests are handled in a FCFS manner in each M A N node and R A slots are captured by the cyclic capturing mechanism irrespective of the traffic classes. Based on the analysis in chapter 5, the average PLR among all VBRSs in the network is given by the following expression: j C (x - Ns) x HhNp(x) PLR = x~Ns+l (6.6) £ x x H1}Np(x) where Ha,b(x) = Ba(x) * Ba+^x) * .... * Bb(x) (6.7) Np (the convolution of the respective bit rate distributions) and Nm = £ Nmj. Note that 3 = 1 the definition of Hafi(x) which seems not necessary at present is for later theoretical analysis. As we consider that there are a large number of VBRSs, Haji,(x) tends to have a normal distribution given by H*tb(x) •= —L=e-(x-^l2<> (6.8) 108 Chapter 6. Integration of heterogeneous VBRIT and connection admission control b b where / J 0 ; & = J2 Wj ar>d alb = S av•• Substituting this into (6.6), the average PLR j=a ' j=a becomes: N ; P L R = — ^ = { V ( x - Nsje-^-tfl2*2) (6.9) UV liter2 t = N ^ Nm Np Np where x x Hi^p(x) = 2~2 VVj = and cr = ^2 av.. Note that the following x=l j=i j=i 3 analysis and C A C algorithm can easily be applied for the case where Ha^(x) is found by convolution. A simple C A C method is to admit a call if the average PLR in the network can meet the worst case PLR objective among all classes of VBRIT. However this would result in overdesign for most and inefficient use of network resources. To perform C A C more effectively, we need to evaluate the PLR for individual VBRIT/ instead of their overall average. We have attempted to conduct a Markov chain analysis for this purpose. However it is found that even with two types of VBRIT (say VBRITi and V B R I T 2 ) , the number of possible states is very large which makes an exact analysis very difficult. While it does not seem practical to carry out an exact analysis, it is still of interest to conduct an approximate analysis based on a FCFS model. This is motivated by the fact that R A access has the same PLR performance as a FCFS reservation queue in the case of homogeneous VBRIT. The approximate FCFS analysis is given as follows. We assume that all mini-sources are independent and each active mini-source joins a FCFS reservation queue to acquire/reserve a R A slot. The average number of mini-sources that waits in the queue, 7 V w - i s given by : .Nm Nm iV™ = 5>-Ns)+ x HltNp(x) = £ (x-N,)x H1>Np(x) (6.10) x=0 x=iV3 + l From (6.6), (6.10) can be rewritten as: NM . Nw = PLR x x x HhNP = rtPLR (6.11) x=l As all mini-sources join the same FCFS queue, they should experience the same average waiting time to capture a R A slot which is denoted as Twait. Let \ t denote the rate at 109 Chapter 6. Integration of heterogeneous VBRIT and connection admission control which a mini-source joins the FCFS queue , given by the following expression: ^ g ^ - ^ r ^ ^ ^ r ( 6 J 2 ) Note that 1 — a°+s is" the fraction of time a mini-source of VBRIT/ is idle so that the av-erage rate at which a mini-source of VBRIT/ joins the queue is given by aj ^1 — a ) • By Little's theorem, \tTWqit should also give Nw. Hence Twait can be found by the following expression: _ pPLR J-wait - "jy— (6.1J) As packets waiting more than one frame are dropped, Twait is also the average number of dropped packets by a mini-source of VBRIT/ in one reservation period. Noting that the average number of packets generated by a mini-source of VBRIT/ in each active period or reservation period is \lff3j , the PLR experienced by VBRIT/ should then be given by: PLRj = Twaitf[33 = J ^ P L R (6.14) j=l To evaluate the effectiveness of the above approximate analysis, we have per-formed simulations for the integration of voice (i.e. {1,0.444,0.667,0.01}) and V C (i.e {6,1.8,2.1,10~6} traffic over a M A N based on the mini-source model discussed in chap-ter 4. Unless otherwise specified, the simulation parameters follows that given in Table 4.2. There is one VBRS per node as given below: • Node 1-5 and 11-15: voice • Node 6-10 and 16-20: V C Figure 6.1 shows the simulation results of average PLR for voice and V C traffic in comparison with that estimated by (6.14). In the graphs, the number of R A slots per frame Ns has been normalized with respect to p, (i.e. Nsn = It can be seen that the Ns analytical approximations are close to the simulation results in general. To enable the 110 Chapter 6. Integration of heterogeneous VBRIT and connection admission control o 10 Simulation V C Simulation voice o A 10 -1 Analytical V C -Analytical voice — o 10 0.8 0.9 1.1 1.2 Nsn Figure 6.1. Average PLR for individual VBRIT later C A C analysis for UBS, we assume the use of (6.14) for calculating PLRj. Equation (6.14) also indicates that VBRIT with a longer active period experiences a lower PLR. This is expected because once a VBRS captures/reserves a R A slot, it will keep the slot for the duration of its demand so mini-sources with longer active periods will have relatively less packet losses. Hence voice has a lower PLR than V C because of its longer active period. Figure 6.2 shows the simulation results of the PLR variation across the M A N . It illustrates the desirable result that VBRSs of the same type have the similar PLR irrespective of their positions in the network. In other words, the previous fairness property of R A access remains valid under a heterogeneous VBRIT environment. This further increases the attractiveness of RA access to support multimedia communications over M A N s . Assuming that (6.14) can be used for estimating the PLR of individual VBRIT, call admission can be controlled as follows. Upon receiving a call request for VBRIT,, HOB A updates / J , C X 2 , NVj and Nm based on the new call information and then checks i l l Chapter 6. Integration of heterogeneous VBRIT and connection admission control Voice: 1-5, 11-15 V C : 6-10, 16-20 OH 10 10 Nsn=0.88 Nsn=0.95 Nsn=l ---»--/' A - - - A - - A - - - & - - - A / P - - - Q - - 0 - - - O - - ® \ ' A - - A _ -A - -J I I I L J I I I I I I l__L 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16 17. 18 19 20 MAN node Figure 6.2. PLR variations across the M A N with voice and V C traffic whether (6.5) can still be fulfilled. That means: PLRj = J F I ^ P L R < ReqPLRj for all j (6.15) i=i Substituting (6.9) into (6.15), simplifying and rearranging, the following call admission criteria can be obtained: V2 1 E(* x)e T 0" \k=x+i N, cxjtSjMjNv. (ReqPLRi ReqPLR2 ReqPLRN / 7,—Mini , (6.16) The new call can be admitted if the criteria specified in (6.16) is satisfied. 6.3 Dynamic bandwidth partitioning (DBP) In DBP, VBRIT, is multiplexed over R A slots of type j which is denoted as RAslotj and the number of RAslotj (or the bandwidth partition) NSj changes dynamically based Np on the traffic situation where N3 = 2~2 NSj. To effect this method, each A C includes an i=i additional entry in the SR to map a R A slot to the corresponding traffic class. A VBRS/ 112 Chapter 6. Integration of heterogeneous VBRIT and connection admission control only accesses the RAslotj's specified in the SR. The mappings in the SR are updated by information received from the HOBs as explained below. We assume that all spare capacity in the network is assigned as RAslotj and HOB A maintains a counter SPARE to record the number of spare R A slots (i.e. the difference between the number of R A slots assigned as RAslotj and the actual number of R A slots required by VBRTTjy .). When a call of VBRITj (j < NP) departs such that m RAslotfs becomes redundant, HOB A reassigns m unreserved RAslotj as RAslotj (the spare capacity). To change a RAslotj to a RAslotNp, HOB A first turns it to an idle QA slot (Busy=0, Sl_type=l and CAP=1) with a special VCI VCINP. When this QA slot passes through the M A N nodes, the ACs update their SRs that the respective slot is now a RAslotj with effective from the next frame. To minimize disruptions to existing reservations, HOB A only turns unreserved RAslotj to RAslot]^p (the spare capacity). However it is possible that HOB A cannot find sufficient unreserved RAslotj for the slot conversion because the surplus bandwidth has already been reserved. If this happens, we propose that HOB A keeps on converting unreserved RAslotj to RAslotjy until a timer expires or the slot conversion is completed. If the slot conversion cannot be completed when the timer expires, HOB A then acquires the remaining number of RAslotjp from the appropriate number of reserved RAslotj by turning the slots into QA slots with the special VCI VCINP- This also signals the M A N nodes which have reserved the slots to give up the reservations and recapture other slots. For each successful slot conversion, SPARE is increased by one. Similarily if NSJ (J < NP) is to be increased by m due to a successful call admission, m RAslot^p are converted to RAslotj based on the above slot conversion mechanism. Again each slot to be converted is first changed to an idle Q A slot with VCIj in order to inform the ACs to update the slot type in the SRs. To maximize the slot utilization, we propose that the connectionless QA traffic can still use the special Q A slots with VCIj, j = 1,2, ...,NP treating as if they are QA slots with the connectionless V C I (all 113 Chapter 6. Integration of heterogeneous VBRIT and connection admission control Is). That means a connectionless data source can still transmit data into these special Q A slots by writing the Busy bit to 1 but not altering the V C I fields and when a node receives a busy QA slot with VCIj, j = 1,2, ...,NP, it should process the content of the slot as connectionless data. As VBRIT/ supported by RAslotj is essentially homogeneous, PLRj can be found based on our previous analysis i.e.: £ (x - Naj) x B,ix) x=N3j+l PLR, = — (6.17) 2~2 x x Bj(x) If a normal distribution is assumed for Bj(x), PLRj = -. ] = { {x-Na])e<x-^l2ah) (6.18) When a call of VBRIT/ arrives where j < Np, HOB A first recalculates the minimum number of RAslotj to admit the new call based on the new call information, (6.5) and (6.18). Supposing that RAslotj is to be increased by ANSj, the call can be admitted if ANSj < SPARE. Upon call admission, HOB A decreases SPARE by ANSj and converts the required number of RAslot^p to RAslotj as explained above if j < Np. Obviously if j = Np, no slot conversion is required due to the spare capacity assignment. To calculate ANSj, the following bisection algorithm can be used which is based in part on the method in [70]: 1. Let a\, b\ and CQ be NSj, NSj + Mj and 0 respectively where NSj is the current number of RAslotj. Note that the required number of RAslotj for accepting the new call must be between a\ = NSj and b\ = NSj + Mj which can be used as an initial condition for the bisection algorithm. 2. Compute cn = an+hn and the value of the following function f(cn) = ] = { £ (x-c^e-^-^'^-ReqPLRj (6.19) PViyJlTrOy. x=C„+,l 114 Chapter 6. Integration of heterogeneous VBRIT and connection admission control If \cn\ = \cn-{\ or |/(c„)| < e where e is the tolerance (e.g. ReqPLRj/100), the algorithm stops and NSj + ANSj = |~cn] otherwise go to step 3. 3. Compute f(an). If f(an) x f(cn) < 0, assign a n + i = an; bn+i = cn otherwise assign an+i = cn; bn+i = bn. Then repeat step 2. As NSj + ANS3 is around NSj, the above algorithm can be performed efficiently using the above initial condition. In fact, we have tried it with many situations and found that it can always give the answer within a few iterations indicating that its implementation in a real time environment should be feasible. Similarity when an on-going call departs, the new number of RAslotj can also be found by. the above algorithm. 6.4 D y n a m i c b a n d w i d t h s h a r i n g ( D B S ) The purpose of DBS is to allow all types of VBRSs to share the bandwidth dynamically such that: 1. lower class traffic is transmitted over the residue bandwidth of higher class traffic 2. the admission of a higher class call is constrained to keep the QoS of the lower class calls within the specified PLR target. Essentially all VBRSs still capture available R A slots using the cyclic capturing mecha-nism but VBRSp can preempt a lower class VBRSg, Q < P if no idle R A slot is available. To implement this method, additional bits are heeded in the A C F . We assume that two more control bits can be made available such as by shortening the original twenty bit V C I fields to eighteen bits for serving the three classes of VBRIT. The modified A C F and segment header are shown in Table 6.1 and 6.2 respectively. Effectively the original C A P and RES bits are expanded to {CAP1, CAP2} and {RES1, RES2} respectively to Table .6.1. Modified A C F for DBS B U S Y SL_TYPE PSR CAP1 CAP2 REQUEST bits RES1 RES 2 1 bit 1 bit 1 bit 1 bit 1 bit 3 bits . 1 bit 1 bit 115 Chapter 6. Integration of heterogeneous VBRIT and connection admission control Table 6.2. Modified Segment Header for DBS VCI PAYLOAD . TYPE SEGMENT PRIORITY HCS 18 bits 2 bits 2 bits 8 bits indicate the corresponding traffic class as shown in Table 6.3. For example a slot s with CAP1=1 and CAP2=0 indicates that the slot has been captured/reserved by VBRIT2 and a slot s* with RES 1=1 and RES2=0 indicates that a VBRS2 wants to reserve slot s in the next frame. In general we need 2/o#2 (Np + 1) control bits in the A C F to serve Np. traffic class. A VBRSp (say SI) can capture a R A slot if either one of the following conditions is met: 1. The R A slot is idle (i.e., C A P 1=0, CAP2=0) or 2. There is nb R A slot available in the last frame and the R A slot has been reserved by a VBRSg (say S2) where Q < P. To check the later condition, every M A N node maintains a counter SLTCT to record the nurhber of idle R A slots in the last frame. To implement DBS for multiple number of VBRSs in a M A N node, Np CQ: C Q i , C Q 2 , , CQ^y • are maintained in each node where CQp contains the capture requests for VBRSp. Denote {P\ Pi) as the value of P in binary numbers with P i representing the most significant bit or the first bit. Suppose that there is no idle R A slot in the last frame (i.e. SLTCT=0) and the highest class of non-empty CQ at node Z is CQ/>, an incoming slot s with CAPl=<2i and CAP2=<22) c a n then be preempted by the capture request in Table 6.3. The bit assignments for different traffic classes Class CAP1/RES1 C A P 2 / R E S 2 0 (idle slot) 0 0 1 0 0 2 0 1 3 •1 1 116 Chapter 6. Integration of heterogeneous VBRIT and connection admission control CQp if P > Q. Note that this condition can be checked by the A C of node Z without knowing all the incoming C A P bits as follows: 1. Set n=l. 2. Compare the n-th bits of P and Q: a. n-th bit of P is greater — Note that this step can only be reached if the previous bits (if any) of P are the same as that of Q. Therefore if the n-th bit of P is greater, P must be greater than Q. Hence no further comparison is required and slot s can be preempted by writing the remaining C A P bits with that of P. b. n-th bit of P is smaller — Similar to above , P must be smaller than Q. Hence no further comparison is required as P is smaller than Q and slot s cannot be preempted. c. n-th bits of P and Q are the same — If n = lpg2(Np + 1) meaning that P and Q are equal, let slot s pass, otherwise continue the comparison by adding 1 to n and repeating step 2. Effectively the A C can write the C A P bits on a bit by bit basis because the incoming n-th C A P bit can be modified with the sole knowledge of the incoming m-th C A P bits where m < n.If slot s can be preempted, the next packet of the first VBRS registered in CQp (say SI) will be transferred to the slot accordingly and the SR entry for slot s will be updated with VBRS=S1. Concurrently the RES bits of slot s* (i.e. the corresponding slot in the reverse bus) will be marked equal to P. When HOB A receives the marked RES bits of slot s* (i.e., RESl=Pi and RES2=P2 in the above example), it sets the C A P bits of slot s to P (i.e., CAPl=Pi and CAP2=P 2 in the above example) in subsequent frames. When the M A N node which has reserved slot s finds that the C A P bits of slot s have been changed to P, it gives up the reservation and registers a new request in its CQg for the corresponding VBRS to capture another slot. 117 Chapter 6. Integration of heterogeneous VBRIT arid connection admission control When slot s is no longer required by VBRS S1 starting from frame k due to bit rate decrease, we consider two options for releasing the slot: • Immediate release (IR) option — VBRS SI marks the C A P bits of slot s in frame k to 00 and stops marking the RES bits of slot s* in the reverse bus. • Chain release (CR) option — Instead of setting the C A P bits of slot s directly to 00 by SI, this option allows the previous owners of slot s to reset the C A P bits to 00 progressively through a chain reaction given below: a. When a VBRS captures/preempts a slot, it records the previous C A P bits (i.e. the C A P bits before the slot is captured/preempted) in the SR. b. A VBRS is said to be an owner of slot s if it has reserved but not released slot s. The owner status is also recorded in the respective SR. c. When slot s is released by S1, it resets the C A P and RES bits of the first slot s and s* passing the node respectively to the previous C A P bits as indicated in the SR. d. Step c triggers a chain reaction such that if an owner of slot s finds that the slot has returned to its traffic class, it also releases the slot by resetting the C A P and RES bits accordingly as described in step c above. After doing so, the VBRS ceases to be the owner of slot s. e. During the chain reaction, slot s may still be preempted according to the previous DBS protocol. When slot s is preempted, the chain reaction stops but resume when the slot is released again due to bit rate decrease. Eventually the C A P bits of slot s return to 00. Let us explain the chain release option with an example. Suppose that slot s has been first captured by VBRS X of class 1 then preempted by VBRS Y of class 2 and finally acquired by VBRS Z of class 3. When VBRS Z ho longer requires slot s, the C A P bits of slot s will be set to 2,1,0 by VBRS Z, Y , X respectively provided that it is not preempted by other VBRSs. 118 Chapter 6. Integration of heterogeneous VBRIT and connection admission control The IR option is simpler but it may affect the access fairness of the lower class VBRIT as discovered from the simulations. This is best to explain with an example. Consider that there are three VBRS A , B and C situated in M A N nodes 1,2 and 3 respectively. VBRS A is of class 3 and the other two of class 1. Under DBS, slots captured by VBRS B and C may be preempted by VBRS A. When a slot is released by A (no matter this slot has been previously reserved by VBRS B or C), it is always released to VBRS B first hence VBRS B receives a better QoS. In general, lower class VBRSs closer to higher class VBRSs experience a lower PLR. Nevertheless it is expected that if the number of VBRSs (hence the number of RA slots) is large and call admissions are properly controlled, slot preemption should occur infrequently because higher class VBRSs can often find an idle R A slot when required. Hence the unfairness problem should become less significant. To improve access fairness in general, the CR option can be used because it prevents the lower class VBRSs closer to the higher class VBRSs from getting all the released slots. However its implementation is more complex. We shall analyze both options in the later simulations. We now proceed to determine PLR, based on the assumption that lower class VBRIT can only transmit over the residual bandwidth of the higher class VBRIT. If VBRIT/ requires x slots in frame k with a probability of Bj(x) and the higher class traffic VBRIT/+1, VBRIT/+2, ..... VBRITjy- requires a total of y slots in frame k with a probability of Hj+itNp(y), (Ns — y — x)+ packets of VBRIT/ will be dropped in frame k because packets of VBRIT/ can only transmit over the R A slots not used by VBRIT/+1, VBRIT/+2, VBRTT/y . Therefore M ' ' N 1 v mj uj PLR, = —J2 B>ix) Y,(N*-y- X)+HJ+iMy) (6-2°) r v J x=o y=0 where •Np 0 j = N, v 119 Chapter 6. Integration of heterogeneous VBRIT and connection admission control and HNp+itNp(y) is defined to have a value of 1. Based on (6.20), C A C can be carried out as follows. When a new call of VBRIT/ arrives, HOB A recalculates PLRi where .1 < z < j based on the new call information using (6.20). The call can be accepted if PLRi < ReqPLRl for all i < j (6.22) Note that it is not necessary to recalculate PLRi where i > j because admitting a lower class VBRIT call will not degrade the performance of. the higher class VBRIT. To validate the above analysis, we repeat the previous voice and V C simulation in section 6.2. Figure 6.3 shows the simulation results of average PLR for voice and V C traffic in comparison with that calculated by (6.20). Again the number of R A slots per frame A^ has been normalized with respect to p. (i.e. N3n = ^f-) to ease comparison. It can be seen that the analytical calculations agree closely with the simulation results. Note that unlike the situation in UBS, V C now has a lower PLR than that of voice. It is also found that both the IR and CR options have similar PLR in consistent with the analytical calculations. Figure 6.4 shows the simulation results of the PLR variations across the M A N for both the IR and CR options. It illustrates the desirable results that VBRSs of 0 ; ~ ~ — — - -S__ "~ ~"~ -• ' . ' ~ ~ ^ ^ 8 • Analytical V C Analytical voice _ Simulation VC, CR + Simulation voice, CR * - Simulation VC, IR A - Simulation voice, IR 0 i i ~ \ 8 0.9 1 1.1 1.2 Nsn Figure 6.3. Average PLR with voice and V C traffic for DBS 120 Chapter 6. Integration of heterogeneous VBRIT and connection admission control IR option (Voice: 1-5,11-15 VC: 6-10,16-20) OS -2 J • 10 H | l _ _ H i II II a i i i i \ - - ^ / ' l ' ' A s * - -// \\r i • i i Nsn=0.95 - -Nsn=1.01 - - A — Nsn=1.07 — Nsn=1.14 — I 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 M A N node CR option (Voice: 1-5,11-15 VC: 6-10,16-20) 10 = as -2 J 10 Cu - — — -^-^  4 , - - A - - ^ - -A- —-id II -o--W ",'\ ' / "', / l \ l j s - - x - - x - - x - - * / 'l '/ / m f \ I II r " i X K < \ i - * - * - * - * / I l ' / I l II \& — -o—o—e--*/ i 1 'r • e - i - © - - " - ^ 1 / 1 1 Nsn=0.95 X Nsn=1.01 Nsn=1.07 Nsn=1.14 — A — 0 - - 0 - -i-1 1 I ' i i i i i i i i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 M A N node Figure 6.4. PLR variations across the M A N with voice and V C traffic for DBS the same class have nearly the same PLR irrespective of their positions in the network. However as expected, the IR option is slightly unfair (lower class VBRSs closer to the higher class VBRSs have slightly lower PLR). The unfairness problem can be seen more clearly in the expanded graph in Figure 6.5. While the degree of unfairness seems to be insignificant, the CR option can further improve access fairness at the expense of more complexity in the protocol operation. As mentioned earlier, it is expected that the unfairness problem in the IR option should become even less significant when the number of VBRSs (hence number of RA slot) is increased because the chance of slot preemption is greatly reduced. 121 Chapter 6. Integration of heterogeneous VBRIT and connection admission control o CR (solid line) IR (dashed line) a! ,0-Nsn=0.95 X Nsn=1.01 A Nsn=1.07 O Nsn=1.14 0 MAN node Figure 6.5. PLR variations across M A N nodes 1-5 for the PR and IR options 6.5 Compar isons of the integration methods To compare UBS, D B P and DBS, we consider the integration of V B R n j : voice (i.e. {1,0.444,0.667,0.01}) and VBRIT 2 : V C (i.e {6,1.8,2.1,10 -6}) over a M A N and calculate the maximum number of voice calls NVl that can be supported against the number of V C calls NV2 for each of the above method based on the associated C A C mechanism. The number of RA slots per frame is assumed to be ^=1000. Figure 6.6 shows the variation of NVl with respect to NV2 for the above integration methods. We also show the results for deterministic multiplexing (i.e. PA access) and ideal statistical multiplexing which are calculated based on the peak bit rate and average bit rate of the VBRSs respectively as follows: • Deterministic multiplexing: NVl = Ns — Mi x NV2 • Ideal statistical multiplexing: NVl = ^i±h. x (M2 x x NV2) Note that the former and latter equations give the lower bound (i.e. worst case) and upper bound (i.e. best case) results respectively. It can be seen from Figure 6.6 that all the above methods support significantly more voice calls than deterministic multiplexing (the conventional circuit switching approach). For example, if there are 180 V C calls in the network then no voice call can be accepted based on deterministic multiplexing whereas 122 Chapter 6. Integration of heterogeneous VBRIT and connection admission control -a '3 > < 60 100 140 180 220 260 300 No. of VC sources Figure 6.6. Maximum number of voice calls against number of V C calls UBS, DBP and DBS can still admit 1045, 1092 and 1227 voice calls respectively which is close to the ideal target of 1254. Although UBS is simple to implement, it has the worst performance especially when the available bandwidth is large (i.e., the number of V C calls is small). This is because UBS provides a lower PLR to voice as explained earlier so more bandwidth has to be assigned to the integrated VBRIT in order to maintain the required PLR to V C . Essentially some of the assigned bandwidth is wasted as voice receives a much better QoS than its requirement. At the expense of more processing, DBP performs better than UBS especially when the available bandwidth is large. Nevertheless as the available bandwidth (or number of V C calls) decreases, both UBS and DBP have nearly the same performance. It can be seen from the graph that the performance of DBP is close to the ideal target especially when the available bandwidth is large. The discrepancy is due to the fact that DBP does not allow the sharing of bandwidth among different classes of VBRIT. (i.e., statistical multiplexing is only provided among same type of VBRIT so unused RAslotj cannot be used by other VBRIT,- where i is not equal to j). DBS gives the best performance in consistent with the ideal target. Unfortunately it requires more control bits in the A C F . Assuming that the additional control bits can 123 Chapter 6. Integration of heterogeneous VBRIT and connection admission control be made available, we propose that DBS is the preferred method; otherwise DBP can be used as an alternative providing nearly optimized performance. 6 .6 Integration of voice, A R and MV traffic with D B S To further verify the effectiveness of DBS (with the CR option) for integrating different types of VBRIT, we simulate DBS with the A R and M V models given in chapter 5 in addition to the above mini-source model. In the simulations there are 10 M A N nodes with one VBRS per node as given below: • Node 1,2,7 and 8 — Bi-state voice source (VBRITi) • Node 3 and 4 — M V source (VBRIT 3) • Node 5,6,9 and 10 — A R source (VBRIT 2) Figure 6.7 shows the simulation results of average PLR for individual VBRIT in compar-ison with that calculated by (6.20) based on the normal distribution approximation. As it can be seen from the graph, the analytical calculations agree closely with the simulation results. It is expected that when the number of VBRSs is large, the discrepancy will be further reduced due to the central limit theorem. As the number of VBRSs increase 0 10 -1 10 -2 10 -3 10 oi J 10 -5 10 -6 10 -7 10 0.75 0.85 0.95 . 1.05 1.15 Nsn Figure 6.7. Comparison of the PLR with analytical calculation for the integration of voice, A R and M V traffic by DBS 124 Chapter 6. Integration of heterogeneous VBRIT and connection admission control Pi i—I OH 10 10 10 10 10 o o 0 0 Voice J I MV AR 0 0 Voice 0 o AR Nsn=0.78 X A A Nsn=0.86 • A Nsn=0.93 O Nsn=1.00 0 3 4 5 6 M A N node 10 Figure 6.8. PLR variations across the M A N for the integration of voice, A R and M V traffic by DBS by 30 times (i.e., NVl = 120, NV2 = 120, NV3 = 60) recalling that NVj is the number of VBRS/, the PLR for both the voice and A R VBRIT drops dramatically approaching the ideal statistical multiplexing target. Note that in this case, the PLR of M V (NV3 = 60) is too small to show in the graph indicating that close to PA access service can be pro-vided to the M V . Figure 6.8 shows the simulation results of the PLR variations across the M A N . Again PLR is dependent on the service class but not the positions of the VBRSs in the network which is consistent to the previous simulation results with the mini-source models. 6.7 Combined D B P - D B S scheme Finally we would like to mention that DBS can easily be combined with DBP to provide guaranteed bandwidth for each class of VBRIT while allowing partial bandwidth N P sharing. In this combined DBP-DBS scheme, VBRIT/ is guaranteed to get NSj (2~2 NSj < i=l Ns) RAslotj based on DBP and the remaining NSc = N3 — NSj R A slots are shared i=l based on DBS (i.e. the surplus R A slots as appeared in the previous DBP scheme are assigned such that all types of VBRIT instead of just V B R I T ^ can capture the slots). 125 Chapter 6. Integration of heterogeneous VBRIT and connection admission control Furthermore we propose that VBRIT/ capture the shared R A slots only if there is no idle RAslotj in the last frame which can be checked easily by maintaining a SLTCT/ to record the number of idle RAslotj in each frame. This prevents all types of VBRIT from capturing the idle shared slots concurrently leaving the exclusive RAslotj unused and hence wasted. In general NSJ is a network design parameter. For example it can be set as a fraction of fiVj- In particular by setting NSJ appropriately, the previous DBP and DBS schemes can be realized as follows: • DBP — Set NSJ as the minimum number of R A slots for satisfying the required PLR of VBRIT/ with the surplus R A slots assigned for V B R I T N • DBS — Set NSJ = 0 for all j. In other words, DBP-DBS can be viewed as a generalized version of both DBP and DBS. We now evaluate PLRj for DBP-DBS. Suppose that the current bit rate of VBRIT/ is xx 64Kbps and the aggregated bit rate of higher class VBRIT is yx 64Kbps. Note that the former and later conditions occur with probabilities Bj(x) and Hj+\tN (y) respectively. The number of R A slots (shared and exclusive ones) for VBRIT/ can then be expressed as NSJ + (NSC - y)+ so (N3J + (NSC - y)+ - x"j+ packets of VBRIT/ are dropped in the current frame. Hence PLRj is given by: PLR, = —Y Bj{x) Y, (X + (W.c - V)+ ~ *) Hj+hNM (6-23) x=0 y=0 6.8 Summary Three methods: UBS, DBP and DBS have been proposed for integrating heterogenous VBRIT over a M A N and the associated C A C mechanisms have been discussed and analyzed. Results indicate that all the above methods support significantly more calls than the conventional circuit switching method where C A C is performed based on the peak bit rate of the VBRSs. While UBS is simple to implement, it suffers from the problem 126 Chapter 6. Integration of heterogeneous VBRIT and connection admission control that lower class VBRSs may be provided with a better QoS. This leads to capacity wastage which decreases the number of calls that can be admitted into the network. At the expense of more processing at each M A N node, DBP performs better than UBS and yields performance close to the ideal statistical multiplexing target. Another advantage of using this method is that previous performance analysis in this thesis can still be applied as the traffic supported by each bandwidth partition is essentially homogeneous. However DBP does not allow sharing of bandwidth between different classes of traffic which lowers its performance at certain conditions. At the expense of requiring more control bits in the A C F , DBS allows the dynamic sharing of bandwidth and provides the best performance in consistent with the ideal statistical multiplexing target. Assuming that these control bits can be made available such as by shortening the V C I fields in the M A N slots, DBS is the preferred method otherwise DBP can be used an alternative providing nearly optimized performance. In general DBS and DBP can be combined to provide some guaranteed bandwidth to each traffic class while allowing partial bandwidth sharing. 127 Chapter 7. Integration of PA, QA and RA traffic Chapter 7 Integration of PA, QA and RA traffic In previous chapters, we have considered that VBRIT (which will be referred as R A traffic in this chapter for consistency with PA and QA traffic) are transported over a fixed number of R A slots. In this chapter, we consider how R A traffic can be integrated with existing PA and QA traffic efficiently. We propose a movable boundary service integration scheme which realizes the M R A access concept in chapter 2. A major advantage of this integration scheme is that it facilitates the dynamic sharing of bandwidth while requiring only a simple modification of the previous RA access protocol and basically no change to the existing PA and QA access methods. We also discuss the C A C mechanisms and bandwidth management strategies for the integrated traffic. 7.1 The integration scheme for PA, Q A and R A traffic In general, the simplest method for integrating PA, QA and R A traffic is to assign a fixed amount of bandwidth to each type of the traffic. By doing so, QA and R A traffic can only utilize their pre-allocated bandwidth based on the DQDB protocol [6] and the R A access protocol in chapter 4 respectively. While this integration method is simple to manage, it suffers from bandwidth inefficiency because R A slots not utilized by the R A traffic cannot be used by the QA traffic and vice versa. In this chapter, we propose a movable boundary integration scheme where QA and R A traffic can share their assigned bandwidth dynamically. In the proposed integration scheme, the HOBs generates three types of slots (PA, QA, RA) as shown in Table 7.1. Basically the formats and access methods for PA and Q A slots follows that defined in the current M A N standard [6] except that the newly introduced C A P bit is set to 1 in these slots to disable the R A traffic from capturing them. Essentially PA and QA slots can only be accessed by Class A and Class 128 Chapter 7. Integration of PA, QA and RA traffic C/D BISDN traffic, respectively. R A slots are identified by BUSY=0, SL_TYPE=0 and CAP=0 in the A C F . That means it is effectively a Q A slot with BUSY=0 and SL_TYPE=0 in the A C F . Note that to facilitate the discussion, we consider the general case where there is one C A P bit in each R A slot. The implementation for DBS follows the same principle where the C A P bits are set to all one's for PA and Q A slots and the corresponding traffic class for R A slots. The basic idea of the integration scheme is to allow the Q A traffic to access the R A slots based on the existing DQDB protocol unless a VBRS, say VBRS Y, has captured a RA slot in which case the captured slot will be turned into a reserved R A slot in subsequent frames for isochronous access by VBRS Y only. In general, it may be desirable to assign some permanent Q A slots (BUSY=0, SL_TYPE=0 and CAP=1) to provide some guaranteed bandwidth for the QA traffic as Table 7.1. Slot assignments for the movable boundary integration scheme Slot type B U S Y bit SL_TYPE bit C A P bit VCI values Comments Q A slot 0 0 1 Global V C I value for connetion-less . traffic Slot accessible by QA traffic only. C A P bit set to 1 by the HOB to disallow VBRSs from capturing slot. R A slot 0 0 0 Global VCI value for connetion-less traffic VBRSs allowed to capture but not transmit a packet in this slot. Slot accessible by Q A traffic for packet transmission using DQDB protocol. Reserved R A slot 1 1 1 Unmarked Slot captured in previous frame and reservation has reached HOB. Slot designated reserved R A by HOB for access only by the VBRS which has captured it. PA slot 1 1 1 Specific value set by HOB Slot accessible, only by predetermined PA traffic source identified by VCI value. 129 Chapter 7. Integration of PA, QA .and RA traffic shown in Table 7.1. Unless otherwise specified, we consider the worst case scenario that no permanent QA slot is available such that QA traffic can only transmit in the unused R A slots. This approach resembles the available bit rate (ABR) service in ATM/BISDN where the non-delay sensitive traffic utilizes the residual bandwidth of the time-sensitive traffic for packet transmissions. We consider that there are Ns R A slots per frame which are spreaded by the semi-uniform spreading method given in Appendix B. PA slots then fill up the remaining positions in each frame. As far as the R A access controller is concerned, a virtual TB is added to the TB as shown in Figure 7.1. R A slots are still captured according to the previous R A access protocol but packet transmissions are delayed until the captured slots are turned into reserved R A slots. In the typical coverage area of a M A N , the access delay is increased by one frame time. A packet which is eligible for transmission into a R A slot is first transferred to the corresponding virtual TB for transmission to the captured R A slot in the next frame. Below is a simple example to explain the basic operation. When a VBRS Y Beginning of frame k CQ SR BUS A VBRS CQ BUS B VBRS s s ' VBRS 1 101 4 2 102 0 3 103 0 4 104 3 SR S S' VBRS 1 101 4 2 102 1 3 103 0 4 104 3 End of frame k Figure 7.1. RA access controller for M R A access 130 Chapter 7. Integration of PA, QA and RA traffic captures a slot s in frame k, it transfers the packet into the virtual TB. When the reserved slot s arrives in frame k+l, the packet in the virtual TB is transmitted into the slot and the next packet of VBRS Y is transferred to the virtual TB. To maintain the reservation in subsequent frames, VBRS Y continues to mark the RES bit of slot s* on bus B to 1 as before. When VBRS Y decreases its bit rate by 64 Kbps in frame w such that slot s is no longer required, it releases slot s by setting its C A P bit to zero and stops marking the RES bit of s* on bus B to 1. If a VBRS captures the released slot s in frame w, it also delay its packet transmission until frame w+1 as above noting that slot s still contains the last packet of VBRS Y in frame w. If a released slot s is not captured by another VBRS, HOB A is notified by RES=0 in slot s*, and it then turns slot s back to an idle R A slot eligible for access by QA traffic. While this integration scheme introduces an additional one-frame access delay, it has a number of advantages: 1. Its implementation is independent of the capturing methods and methods for support-ing heterogeneous traffic (i.e. it works for UBS, DBP and DBS). 2. It can be realized by a simple modification of the previous R A access protocol. 3. It basically requires no change to the existing PA and Q A access methods. 4. It retains the previous isochronous transport service property of R A access. 5. It eases bandwidth allocation by giving HOBs full control of the PA, Q A and R A bandwidth while distributing the access control functions to individual M A N nodes. 6. It allows the QA and R A traffic to share the R A slots dynamically in a movable boundary fashion. 7. As far as the VBRSs are concerned, the integration scheme is just the original R A access protocol shifted by one frame so previous performance analysis except access delay is still valid. Due to the above advantages, we focus on analyzing this integration scheme in this thesis. 131 Chapter. 7. Integration of PA, QA and RA traffic 7.2 Performance analysis 7.2.1 Simulation models To analyze the performance of the proposed integration scheme, we compare it with the existing integration method in the 802.6 standard using the common voice and data integration problem. The transport mechanisms are outlined as follows: • Proposed integration scheme — PA access for constant bit rate traffic, Q A access for data and R A access for voice • Existing integration scheme — PA access for constant bit rate traffic/voice and QA access for data Note that the choice of a voice/data integration model also facilitates the later numerical analysis. The purpose of our study is to evaluate the data delay performance with respect to the number of voice stations in the network based on the simulation parameters (i)-(iv) in Table 4.2 and the additional simulation parameters in Table 7.2. For the existing integration scheme, the QA (data) slots are also assumed to be spreaded using the semi-uniform spreading method in Appendix B. In the simulations, fixed size data packets of 53 bytes (including overhead bits) are generated at each M A N node according to a Table 7.2. Additional simulation parameters for PA, QA and R A traffic integration. No. of voice calls Nv Varied as indicated in the results Data arrival process Poisson Data rate per node (Xnode) 12400 packets/s (5.3 Mbps) Total data rate per bus (A) 130208 packets/s (55.2 Mbps) Destinations of the data packets Distributed evenly among downstream nodes Available bandwidth for voice and data per bus 100 Mbps (JV>1412 slots) Simulation time 1 minute 132 Chapter 7. Integration of PA, QA and RA traffic Poisson process with mean \node packets/s. The destinations of the packets are uniformly distributed among the downstream nodes hence the effective Poisson data rate of node i on bus A and B is given by \A(i) = (^Ej)\node and \B(i) = (j^i)Xnode, respectively, where N is the total number of M A N nodes. The aggregate Poisson data rate on each bus is A — N\node/2. We evaluate the data access delay which is the average time taken for a data packet to gain access to an available QA/RA slot. Due to the symmetry of bus A and B, we can just consider bus A . If delay A(i) is the data access delay of node i on bus A , the overall data access delay for node i when both buses are taken into account is: delayAB(i) = _ ^ * delay A(i) + (jj—^ * delay A(N + 1 - i) (7.1) (i=l,2,3, . . . ,A0, noting that node i on bus A is equivalent to node N+l-i on bus B. The N average data access delay is then given by delay AB(i) / N. The target for data access »= i delay is very diverse, depending on the application. In general, interactive applications require a much shorter delay than messaging or file transfer. Regardless of the application, data is not very sensitive to delay variations. An average data access delay in the order of 1-10 ms should generally be acceptable for most applications. 7.2.2 Ideal data access delay The exact analysis of distributed queue statistics is known to be a very difficult problem [50]. It is even more difficult in our case because accessible slots undergo random vacations. Hence computer simulations are employed in the subsequent data delay analysis. While it is not possible to obtain an exact analysis, it is still of interest to compare the performance of a distributed queue with that of a FCFS queue which provides a lower bound data delay for the distributed queue and can be viewed as the ultimate target for Q A access. To facilitate an approximate analysis for a FCFS queue, the following assumptions are made: 133 Chapter 7. Integration of PA, QA and RA traffic 1. A l l data packets transmitted on bus A join a FCFS queue with unlimited buffer space. Note that as bus A and B are symmetrical, we need only consider bus A to obtain the average data access delay for the whole network. 2. Slots, arrives at the FCFS queue at ts, 2ts, 3ts, . . . , where ts = F/Ns slots (i.e., assume uniform spacing between the Ns R A slots). 3. The slot vacations are approximated by a Bernoulli process where an arrived slot can be accessed by the data traffic with probability p where p = (Ns — 0.4 x Nv)/Ns, recalling that Ns is the number of slots available for voice and data integration and each of the Nv voice stations is active 40% of the time. We form a Markov chain imbedded at the time instant ts, 2ts, 3ts, . . . . Define the state space of the Markov chain as the number of packets in the buffer (i.e., {0,1,2,3, . . . }). The transition probability matrix is then given by: "A 0 Ai' A2 , A3 A4 pA0 pA1 + qA0 pA2 + qA1 pA3 + qA2 pA4 + qA3 0 pA0' pAx + qA0 pA2 + qAi pA3 + qA2 0 0 pA0 pAx + qA0 pA2 + qAx 0 0 0 pA0 pA1 + qA0 (7.2) where Ar, (7.3) and q = 1 - p, recalling that A is the aggregate Poisson data rate on bus A . Let irn be the limiting probability that there are n data packets in the buffer at the imbedded instant. Based on (7.2), the following equations can easily be found: { 7r0Ao + vTipAo n = 0 7r 0 A n + Trn+lPA0 + £ iri{PAn_l+1 + qAn-i) n>0 (7-4> i=l Multiplying the left hand side and right hand side of (7.4) by zn and summing up all the terms, we get: Q{*) = pA(z)TT0(l - Z~l) 1 - A(z)(l -p + pz~l) (7.5) 134 Chapter 7. Integration of PA, QA and RA traffic oo oo where Q(z) — ^ -Knzn and A(z) = ^ Anzn. By setting z=\ in (7.5), noting that Q(l)=l and A(l)=l and applying L'hopital's rule, we get 7ro = 1 — (Xts/p), which shows that to maintain stability, p > Xts. The average number of data packets in the buffer can be found by differentiating (7.5) with respect to z, evaluating d ®^ \z=\ by using lkA( dkQ(z)l i u i iv^api^i v ^ v a i u a u u g L'Hopital's rule, and noting that** f[z^\z=i = (Xts)k. By doing so, we get Xts(2 - A t . ) E [ Q ] ~ 2(p-Xts) ( 7 - 6 ) Applying Little theorem and taking into account the average residue waiting time of ts/2 between consecutive slots, the data packet access delay can be found as F\W] - E [ Q ] + t s f - U { 2 ~ X t s ) t s ' (17^ ' E [ W ] - — + 2 ~ t s ~ 2(p-Xts) ~ 2 ( ? - 7 ) To check the correctness of (7.7), we can substitute p=l in (7.7) tb verify that it is the same as the waiting time of a M / D / l queue with vacations, which is the expected result. 7.2.3 Simulation results and discussions Figures 7.2(a) and (b) compare the average data access delays of the existing integration scheme in the 802.6 M A N standard (PA for voice and QA for data) and the proposed integration scheme (RA for voice and QA for data), respectively. It can be seen that the average data access delay for both schemes remains at a very low level until the system becomes unstable. In Figure 7.2(a), the FGFS lower bound is given by (7.7) with p=l. The discrepancy between the simulation result (21 nodes, semi-uniform) and the FCFS lower bound is due to the non-uniform spacing between access slots and the unfairness of the DQDB protocol. It is found that as Nv increases, the simulation results get closer to the FCFS lower bound. To verify the correctness of the simulation model, we have conducted additional simulations with uniform slot spacing and less number of nodes. This is done by changing some parameters of the simulation program without altering its basic structure. With only three nodes (i.e. two transmitting nodes on each bus) and uniform slot spacing, the simulation results are much closer to the theoretical 135 Chapter 7. Integration of PA, QA and RA traffic o 60 > < ca -o CO o CO bb > 10 Figure 7.2a - Voice: PA, Data: QA CD -o CD o TO CS T3 FCFS lower bound Simulation - 1 node, uniform - - A - -Simulation - 2 node, uniform Simulation - 20 node, semi-uniform 400 450 500 550 600 No. of voice calls in progress 10 Figure 7.2b - Voice: RA, Data: Q A -2 10 r -3 10 r -4 10 b 10 FCFS lower bound Simulation - 1 node, uniform Simulation - 2 node, uniform Simulation - 20 node, semi-uniform --_ —©• — _L "1000 1100 1200 1300 1400 No. of voice calls in progress 1500 650 1600 Figure 7.2. Data access delay analysis for the slot spreading methods calculations. In this case, the discrepancy is caused by the unfairness of the DQDB protocol only. As the number of M A N nodes is reduced to two (i.e., one transmitting nodes on each bus), the simulation results match the theoretical calculations as expected, which lends confidence to the correctness of our simulation model. The curves in Figures 7.2(a) and (b) have the same shape. However when the number of transmitting M A N nodes on each bus is reduced to one and uniform slot spacing is used (i.e., the ideal case), the simulation results for the proposed integration scheme do not coincide with the FCFS lower bound due to the Bernoulli approximation employed for slot vacations. Nevertheless the lower bound remains a good approximation over a wide range of Nv in this ideal case. Figure 7.2 shows that the proposed integration scheme can support 1500 voice calls giving a 125% capacity improvement compared to the 632 voice calls 136 Chapter 7. Integration of PA, QA and RA traffic supported by the existing integration approach. As the burstiness of the VBRSs increases (e.g. video), even higher capacity gain can be realized. The FCFS lower bound in Figure 7.2(b) indicates that ideally the maximum number of voice calls that can be accommodated is about 1580; hence the proposed integration scheme is in fact close to optimal. Figure 7.3 shows the data access delay variations along the M A N bus when both bus A and B are taken into account. Due to symmetry, we have simulated bus A only and applied (7.1) to work out the overall data access delay for both buses. The results show that the waiting time profile along the M A N bus changes from a convex shape to a 10 Voice: PA. Data: QA u 10 Nv=620 (Util=98.6%) Nv=600 (Util-96.2%) Nv=550 (Util=90.6%) Nv=400 (Util=77.2%) 2 3 4 5 6 7 9 10 11 12 13 14 15 16 17 18 19 20 21 Node 10 >p 10 Voice: RA, Data: QA Nv=1500 (Util=96.6%) Nv=1412(Util=92.6%) Nv=1300(Util=87.1%) Nv=1000 (Util=76.8%) J I I I I I I L J I I I I I L 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 , Node Figure 7.3. Data access delay variations along the M A N bus 137 Chapter 7. Integration of PA, QA and RA traffic concave shape as the number of voice calls or the data slot utilization (Util. in the graphs) increases. This finding is consistent with the recent studies in [57]. Although DQDB protocol favors nodes with smaller/larger indexes on bus A/B, these nodes also have a higher effective data rate on bus A/B which counteract the access advantage when the data slot utilization is high. The results indicate that data access delay of a M A N node depends not only on its position in the network but also the data loads in other nodes. Nevertheless, although QA access is unfair, data access delay can still be kept within an acceptable level up to a fairly high data slot utilization. This suggests that Q A access should still be useful for transporting non-time sensitive data traffic due to its simplicity. 7.3 Bandwidth management for integrated PA, Q A and R A traffic In this section, we discuss the bandwidth management strategy and C A C mechanisms for the integrated PA, QA and R A traffic. To facilitate the discussion, we assume that the traffic requirement in both bus is symmetrical such that each bus requires the same number of PA, QA and R A slots. Due to this symmetrical condition, we consider that all calls are initiated in bus A and processed by HOB A which is assumed to take up the bandwidth manager functions. For the purpose of bandwidth management and C A C , HOB A maintains a record of the following parameters which will be explained in detail later: • NPA, NQA, NRA and NSPARE —Number of PA, QA, R A and spare slots per frame respectively which are updated following each call admittance and call departure • ^control — Current data rate (in slots/frame) of the call control traffic which will be discussed later • ^co — Average data rate (in slots/frame) among CO data traffic which is updated following the admittance and departure of a CO data call • fi — Average number of RA slots required by the R A traffic per frame which is updated every time a R A call is admitted or departed. Note that NRA — yt is the average number of unused R A slots per frame 138 Chapter 7. Integration of PA, QA and RA traffic . We consider that any spare network capacity is allocated to the R A / Q A traffic as R A slots. Hence NRA — N S P A R E is the actual number of R A slots required by the R A traffic per frame. The proposed bandwidth management strategy and C A C mechanism for each type of traffic are given below: 7.3.1 PA traffic During call set up, the PA traffic source specifies the required number of PA slots per frame. HOB A accepts the call if the spare network capacity is sufficient to meet the requirement. Following a successful call admission, HOB A converts the requested number of spare (RA) slots into PA slots accordingly. 7.3.2 Q A traffic There are three basic types of QA traffic which demands different treatment: • Call control traffic — Due to the time-critical nature of call control traffic, we propose that it is transported by QA access at the highest priority level (level 2) using an extended distributed queue [99]. By doing so, a QA request can be issued as soon as a QA segment is generated. This allows call control traffic to preempt other QA traffic using the original priority protocol proposed for 802.6 M A N s [50]. Furthermore it facilitates network planning and bandwidth management since HOB A can measure ^signal accurately based on the generation rate of the highest priority Q A requests in the reverse bus. While the use of an uncontrolled extended distributed queue may cause severe unfairness problem in some situations (e.g. when the last node has a very long message to transmit, it will acquire all the bandwidth by using up the available request bits), the chance of experiencing these extreme conditions should be negligible as call control traffic typically consists of short messages with data rate well below 155Mbps per bus. • CO data traffic —It is transported by the recently proposed QA (GBP) access [25] at priority level 1. At call set up, the data source specifies the average required 139 Chapter 7. Integration of PA, QA and RA traffic bandwidth and HOB A only admits the call if the assigned Q A bandwidth and the residue R A bandwidth are sufficient to satisfy the bandwidth requirement of the call control traffic and CO data traffic i.e. NQA + NRA ^ n ( j_\ \ n «\ p > {^control + ACO) (/-o) where Xco includes the average bandwidth requirement of the new CO data call. In practice, the network operator may multiply a safety margin factor (e.g. 1.1) to the right hand side of the inequality to avoid driving the network so close to the point of instability. • C L data traffic :—It is transported by QA access at priority 0 using the basic distributed queue. The aim is to provide best effort service through the residue network bandwidth hence service is not guaranteed. To improve fairness, the BWB mechanism can be employed at the expense of bandwidth wastage. The choice of NQA is a network design parameter. While it can be set to zero, it may be desirable to allocate a certain amount of bandwidth for the QA traffic. Some alternatives are given below: (a) Simply set it as a fraction of the network bandwidth (e.g. 10% or about 200 slots) (b) Assign NQA at different time of the day according to the past statistics of the Q A traffic (c) Vary NQA based on measured \controi a n <3 requested Xco so that guaranteed service can be provided for the high priority call control traffic and CO data traffic leaving the C L data traffic for transport over the residue R A bandwidth 7.3.3 R A traffic To integrate different types of R A traffic over the R A slots, the DBS method and the associated C A C mechanism proposed in chapter 6 is employed. We assume that the V C I fields of a R A slot can be shortened to 18 bits to serve three classes of R A traffic (e.g. voice, video conference and motion video traffic) as discussed in chapter 140 Chapter 7. Integration of PA, QA and RA traffic 6. Alternatively the, previous DBP method can be employed. In addition to the C A C mechanism in chapter 6, HOB A only accepts a R A call if the bandwidth requirement of call control traffic and CO data traffic can still be satisfied by the residual R A bandwidth and the assigned QA bandwidth as determined by (7.8) where p in the inequality takes into account the average bandwidth of the new R A call. 7.4 Summary We have proposed an efficient method for integrating PA, Q A and R A traffic over a M A N . At the expense of introducing a one frame access delay to the R A traffic, this integration scheme allows the QA (non-time sensitive) and R A (time-sensitive) traffic to share the available bandwidth dynamically on a movable boundary basis. It only requires a simple modification of the previous RA access protocol and basically no change to the existing PA and QA access methods. System performance has been analyzed by an approximate theoretical model and computer simulations. Results indicate that the integration scheme provides reasonable data access delay while optimizing the number of VBRSs in the network. This results in significant capacity improvements compared to the existing integration method for 802.6 MANs where synchronous and asynchronous traffic are transported by PA (circuit switching) and QA (packet switching) access, respectively. We have also discussed the bandwidth management strategies and C A C mechanisms for the integrated PA, QA and R A traffic. It demonstrates that the integration scheme gives HOBs (bandwidth managers) full control of the PA, QA and R A bandwidth while distributing the access control functions to individual M A N nodes. 141 Chapter 8 Conclusions and future research areas 8.1 C o n c l u s i o n s IEEE 802.6 (DQDB) M A N s are well suited to provide customer access to SMDS, to function as distributive switches for interconnecting base stations in the wireless personal communication networks and to serve as peripheral gathering networks of end user traffic for transport over ATM/BISDN. Therefore the requirement of efficient transport techniques for different types of traffic over 802.6 M A N s is of primary importance. Current IEEE .802.6 standard employs PA access for constant bit rate isochronous traffic transport and Q A access for statistical multiplexing of asynchronous data traffic. However they are not suitable for transporting VBRIT such as V B R voice and video. The main disadvantage of transporting VBRIT by PA access is capacity wastage as bandwidth has to be pre-assigned based on the peak rate. Although QA access enables efficient bandwidth utilization, it suffers from non-guaranteed access delay, access delay variations and the well known unfairness problem. Motivated by the P R M A protocol and other reservation protocols for L A N s / M A N s , we have proposed a R A access method for transporting VBRIT over dual bus M A N s in general and IEEE 802.6 MANs in particular. Our work enhances the previous reservation protocols for LANs/MANs by overcoming their shortcomings (e.g. unfairness) and addressing the transport of both voice and video traffic. R A access allows a traffic source to capture and reserve isochronous channels on a bandwidth on demand basis in a distributive manner. To resolve the general access contention problem in the reservation process, a simple resolution mechanism is proposed where upstream nodes yield to the downstream nodes. R A access gives significant capacity improvements over PA access and provides variable bit rate isochronous channels compared to QA access. It also 142 Chapter 8. Conclusions and future research areas allows a video source to adapt to the reserved bit rate during network congestion and facilitates the implementation of layered video coding techniques We have analyzed the simplest 1-persistent R A access scheme in chapter 3 for transporting bursty voice traffic using theoretical methods, computer simulations and a real voice simulation. While 1-persistent RA access is unfair, it forms the basis for other R A access schemes and the simulation and theoretical results still illustrate the potential advantages of RA access for transporting VBRIT. Furthermore the theoretical analysis establishes the average, upper bound and lower bound clipping probabilities that can be achieved by other waste free capturing methods. To overcome the unfairness problem of 1-persistent capturing, we have proposed a new cyclic capturing method for R A access in chapter 4. Furthermore we have shown that under the typical coverage area of a M A N , R A access can be made contention free by setting the operation parameters properly. By adopting cyclic capturing as the bandwidth acquisition method for R A access, we have presented the detail protocol operation for supporting multiple number of VBRSs connected to a M A N node. Based on a mini-source model suitable for representing voice and video conference traffic, we have also conducted detail performance analysis for R A access using theoretical models and computer simulations. Results indicate that RA access can provide nearly isochronous transport service while enabling efficient bandwidth utilization. The effectiveness of R A access for transporting general VBRIT over MANs has been further verified by simulating R A access with two different video source models in chapter 5. In chapter 6, three different methods: UBS, DBP and DBS have been proposed and compared for R A access to integrate heterogeneous VBRIT over a M A N . The associated connection admission control mechanisms have also been analyzed. Results indicate that at the expense of requiring more control bits in the A C F , DBS is the preferred method which yields performance close to the ideal statistical multiplexing target. Alternatively 143 Chapter 8. Conclusions and future research areas DBP can be used to provide nearly optimized performance. In general DBP and DBS can also be combined to provide guaranteed bandwidth for each priority level of VBRIT while allowing partial bandwidth sharing. To address the integration of PA, QA and R A traffic, a movable boundary integration scheme have been proposed and analyzed in chapter 7. While the proposed method introduces additional access delay, it can be realized by a simple modification of the previous R A access protocol, requires no change to the existing PA and Q A access methods, retains the previous isochronous transport service property of R A access, and allows the non-time sensitive QA traffic to transmit over the residue bandwidth of the time sensitive traffic in a manner similar to the A T M available bit rate services. We have also discussed the bandwidth management strategies and C A C mechanisms for the integrated traffic. An important application of R A access is to facilitate the transport of real time traffic over MAN-based wireless personal communication networks and enterprise networks which we have considered in [41, 43, 45]. For interested readers, the main results of this thesis can also be found in the following papers: [40, 41, 42, 43, 44, 45, 46, 47, 48]. 8.2 Future research areas RA access for other services and as a high speed MAN protocol While we have considered a R A access protocol for transporting VBRIT in this thesis, its principle may also be applied to cover other types of service such as connection oriented data services over M A N s . In general, it may also be developed as a medium access protocol for high speed M A N s . In this case, a M A N node may capture/release slots in a round robin fashion based on the number of data packets in its data buffers. 144 Chapter 8. Conclusions and future research areas RA access for ATM/BISDN It is also an interesting research area to extend R A access for transporting VBRIT over ATM/BISDNs. Basically the bandwidth of each virtual circuit is changed on a bandwidth on demand basis. When a VBRS increases its bitrate, it joins a FCFS queue to capture/reserve the required bandwidth for its virtual circuit. Essentially this aims at enhancing the fast buffer reservation protocol [95] for supporting VBRIT. Development of an adaptive video coding method for RA access As mentioned in the thesis, R A access facilitates the implementation of layered video coding techniques and allows a video source to adapt to the reserved bit rate during network congestion. Taking advantages of these features, it is worthwhile to investigate an adaptive video coding method to work with R A access for providing highly effective video services over M A N s . More advance CAC mechanism It is well known that C A C is a very complex and difficult problem. While we have addressed the issue of C A C for R A access with three different methods, there may be other better mechanisms. Some researchers even think that the problem of C A C may not be solved by classical methods. Instead advance techniques based on neural networks, artificial intelligent, fuzzy logic, etc., may provide more effective solutions [97, 98]. Moreover advance C A C may not just depend on QoS requirements but also on revenue considerations. For example, a call may be rejected because the network operator wants to wait for a higher revenue call. A l l of these are very interesting research areas for further investigations. 145 Bibliography [I] ANSI/IEEE. Carrier sense multiple access with collision detection access method and pysical layer specification, 1988. [2] ANSI/IEEE. Token ring access method and physical layer specifications, 1988. [3] ANSI/IEEE. Token-passing bus access method and physical layer specifications, 1988. [4] J. O. Limb and C. Flores, "Description of Fastnet - an unidirectional local area communication network," Bell Syst. Tech. J., vol. 61, pp. 1413-1440, July. 1982. [5] J. F. Mollenauer, "Standards for Metropolitan Area Networks," IEEE Communica-tion Magazine, vol. 26, pp. 15-19, Apr. 1988. [6] IEEE. IEEE standard for LANs and MANs : Distributed Queue Dual Bus (DQDB) ; subnetwork of a M A N , 802.6, Dec. 1990. . [7] R. M . Newman and J. L . Hullet, "Distributed queueing : A fast and efficent packet access protocol for QPSX," Proc. Int'l Conf. on Computer and Commun., pp. 294— 299, 1986. [8] R. M . Newman, Z. L . Budrikis and J. L . Hullet, "The QPSX M A N , " IEEE Commun. Mag., vol. 26, pp. 20-28, Apr. 1988. [9] G. Trilovszky, "Evolution strategy from metropolitan area networks to broadband ISDN," Proc. SPIE Local and metropolitan area networks, vol. 1975, pp. 104—116, Apr. 1993. [10] F. C. Liu and C. Yuan, "Performance study of national SMDS networks," Proc. IEEE Globecom' 92, pp. 1040-1044, 1992. [II] F. Liu, R. Mizer, M . Rudik and C. Yuan, "SMDS technology test results and issues," Proc. IEEE ICC 93, pp. 661-665, 1993. [12] J. R. Bumbils, "3 M and US West SMDS trial," Proc. Local computer networks 1992, pp. 274-283, 1992. [13] H . Nussbacher, "Lessons learned from a M A N , " Computer Networks and ISDN system, vol. 28, pp. 583-588, 1996. [14] T. J. King, " U K switched high-speed data service (SHDS) trials and experience," Proc. Globecom' 92, pp. 506-510, 1992. 146 Bibliography [15] G. C. Kessler, ISDN, ch.ll. New York, N Y , McGraw-Hill, 2nd edition, 1993. [16] F. Antonelli and E. Perretti, "SMDS service in Europe : a public operator's experience," Proc. SPIE Local and metropolitan area networks, vol. 1975, pp. 82-91, Apr. 1993. [17] R. Vercelli and P. Chiggino, "Build a Gigabit M A N with ETSI/TEEE DQDB Standard Complaint Nodes," Globcom' 93, vol. 2, pp. 1134-1138, Dec. 1993. [18] W. R. Byrne, G. W. R. Luderer, G. Clapp, B. L . Nelson and H . J. Kafka, "Evolution of metropolitan area networks to broadband ISDN," IEEE Comm. Mag., pp. 69-82, Jan. 1991. [19] J. Filipiak, "Shaping internetworking M A N ' s into an evolutionary BISDN," Comput. Networks ISDN SySt., vol. 20, pp. 343-349, 1990. [20] D. J. Goodman, "Cellular packet communications," IEEE Trans, on Commun., vol. 38, pp. 1272-1280, Aug. 1990. [21] A . D. Malyan, L . J. Ng, R. W. Donaldson and V. C. M . Leung, , "Network architecture and signalling for wireless personal communications," IEEE J. Select. Areas in Commun., vol. 11, pp. 830-841, Aug. 1993. [22] V . C. M . Leung, N . Qian, A . D. Malyan and R. W. Donaldson, "Call control and traffic transport for connection oriented high speed wireless personal communica-tions over metropolitan area networks," IEEE J. Select. Areas Commun., vol. 12, pp. 1376-1388, Oct. 1994. [23] K. S. M . Hellstern, G. P. Pollini and D. J. Goodman , "Network protocols for cellular packet switch," IEEE Trans, on Commun., vol. 42, pp. 1235-1244, Feb. 1994. [24] J. B. Kim, T. Suda and M . Yoshimura, "International standardization of B-ISDN," Computer Networks and ISDN System, vol. 27, pp. 5-27, 1994. [25] P. Martini and G. Werschmann, "Connection oriented data service in DQDB -simulation studies of the guaranteed bandwidth protocol," 1993 Int'l Phoenix Conference, pp. 339-345, 1993. [26] D. Karvelas and M . Papamichail, " A n effective priority mechanism for high speed M A N s , " Infocom 1994, pp. 742-749, Jun. 1994. [27] N . Jayant, "Signal Compression : Technology Targets and Research Directions," IEEE J. Select. Areas Commun., vol. 10, pp. 796-828, Jun. 1992. 147 Bibliography [28] B. Ackland, " A video codec chip set for multimedia applications," AT and T Technical Journal, pp. 1-10, Jan. 1993. [29] J. Cosmas, "Overview of the mobile communications programme of R A C E II," IEE Elect, and Commun. Eng. Journal, pp. 155-167, Aug. 1995. [30] J. O. Limb and L . E. Flamm, " A distributed local area network packet protocol for combined voice and data transmission," IEEE J. Select. Areas in Commun., vol. SAC-1, pp. 926-934, Nov. 1983. [31] K. Apostolidis, L . F. Merakos and X. H . Xing, " A reservation protocol for packet voice and data integration in unidirectional bus network," IEEE Trans, on Commun., vol. 41, pp. 478^185, Mar. 1993. [32] D. J. Goodman, R. A . Valenzuela, K. T. Gayliard and B. Ramamurthi, "Packet reservation multiple access for local wireless communications," IEEE Trans, on Commun., vol. 37, pp. 885-890, Aug. 1989. [33] S. Nanda, D. J. Goodman and U . Timor, "Performance of P R M A : A Packet Voice Protocol for Cellular Systems," IEEE Transcations on Vehicular Technology, vol. 40, pp. 584-598, Aug. 1991. [34] S. Jangi and L.F. Merakos, "Performance Analysis of Reservation Random Access Protocols for Wireless Access Networks," IEEE Transactions on Communications, vol. 42, pp. 1223-1234, Apr . 1994.. [35] S. Nanda, "Stability evluation and design of the P R M A joint voice data system," IEEE Transactions on Communications, vol. 42, pp. 2092-2104, May 1994. [36] G. Wu, K. Mukumoto and A . Fukuda, "Analysis of an integrated voice and data transmission system using packet reservation multiple access," IEEE Trans, on . Vech. Tech., vol. 43, pp. 289-297, May 1994. [37] L . Hanzo, R. Stedman, R. Steele and J. C. S. Cheung, " A mobile speech, video and data transceiver scheme," Proc. IEEE Vech. Tech. Conf. 1994, pp. 452^156, 1994. [38] L . Hanzo, J. Streit, R. A . Salami, W: T. Webb, " A low rate voice video personal communicator scheme," IEE Radio receivers and associated systems, pp. 11-16, Sep 1995. [39] B. Mukherjee and J. S. Meditch, "Integrating voice with the pi-persistent protocol for undirectional broadcast bus networks," IEEE Trans, on Commun., vol. 36, .' pp. 1287-1295, Dec. 1988. 148 Bibliography [40] H . C. B. Chan and V. C. M . Leung, "Reservation arbitrated access - A bandwidth on demand protocol for multiplexing variable bit rate isochronous traffic over dual bus metropolitan area networks," Computer Networks and ISDN Systems, accepted for publication, May 1997. [41] H . C. B. Chan and V. C. M . Leung, "Network architecture and traffic transport for integrated wireless communications over enterprise networks," ACM/Baltzer Wireless Networks Journal, accepted for publication, Feb. 1997. [42] H . C. B. Chan and V. C. M . Leung, "Contention free cyclic release reservation arbitrated access for multiplexing real time traffic over dual bus' metropolitan area networks," Proc. IEEE Globecom'96, London, UK, pp. 294-298, Nov. 1996. [43] H . C. B. Chan, V . C. M . Leung and R. W. Donaldson, "Transport method to . integrate multimedia and data personal communication services over MAN-based PCNs," Proc. IEEE ICUPC'96, Boston MA, pp. 686-690, Sep. 1996. [44] H . C. B. Chan and V. C. M . Leung, "Performance analysis of reservation arbitrated access for statistical multiplexing voice traffic over dual bus metropolitan area networks," Proc. Globecom'95, Singapore, pp. 675-679, Nov. 1995. [45] H . C. B. Chan and V. C. M . Leung, "Evaluation of traffic capacity for integrated wireless personal communication over metropolitan area networks," Proc. IEEE PIMRC'95, Toronto, pp. 269-273, Sep. 1995. [46] H . C. B. Chan and V. C. M . Leung, "Reservation arbitrated access for isochronous voice transport over dual bus metropolitan area networks," Proc. IEEE ICC'95, Seattle, WA, pp. 1467-1471, Jun. 1995. [47] H . C. B. Chan and V. C. M . Leung, "Reservation arbitrated access for variable bit rate isochronous traffic transport over dual bus metropolitan area networks," Proc. IEEE Canadian Conference on Electrical and Computer Engineering, St John's, NF, pp. 800-803, May 1997. [48] H . C. B. Chan and V. C. M . Leung, "Preemtpive reservation arbitrated access for transporting variable bit rate isochronous traffic over dual bus metropolitan area networks," Proc. IEEE Pacific Rim Conf. on Communications, Computers and Signal Processing, Victoria, B.C., Aug 1997. [49] IEEE. IEEE Standard for LANs and MANs : Supplements to DQDB Access method and Physical Layer Convergence Procedure (PCLP) for DS-1 based System (Clause 12) and Isochronous Service on a DQDB Subnetwork of a M A N , 1994. [50] B. Mukherjee and C. Bisdikian, " A journey through the DQDB network literature," Performance evaluation, pp. 129-158, 1992. 149 Bibliography [51] P. Martini, "The DQDB protocol what about fairness," Proc. IEEE Globecom' 89, pp. 298-302, Nov. 1989. [52] H . Santoso and S. Fdida, "Protocol evolution and performance analysis of the IEEE 802.6 DQDB M A N , " Proc, EFOC LAN' 90, pp. 226-230, Jun. 1990. [53] K. Sauer and W. Schodl, "Performance aspects of the DQDB protocol," Comput. Networks ISDN SySt., vol. 20, pp. 253-260, 1990. [54] V . Catania, L . Mazzola, A . Puliafito and L . Vita, "Throughput analysis of DQDB in overload condition," Proc. IEEE ICC 91, pp. 741-747, 1991. [55] P. Davids and P. Martini, "Performance of DQDB," Proc. IEEE 9th Int'l conf. on computers and commun., pp. 548-559, 1990. [56] M . Conti, E. Gregori and L. Lenzini, " A methodological approach to an extensive analysis of DQDB performance and fairness," IEEE J. Select. Areas Commun., vol. 9, pp. 76-87, 1 1991. [57] N . S. V. Rao, K. Maly, S. Dharanikota, S. Olariu, L . Zhang,and D. Game, "Average waiting time profiles of uniform DQDB model," Proc. Infocom' 94, pp. 1326-1333, 1994. [58] E. L . Hahne, A . K. Choudhury and N . F. Maxemchuk, "Improving the fairness of DQDB networks," Proc. IEEE Infocom' 90, pp. 175-184, 1990. [59] E. L . Hahne, A . K. Choudhury and N . F. Maxemchuk, "DQDB networks with and without bandwidth balancing," IEEE Trans, on Commun., vol. 40, pp. 1192-1204, Jul. 1992. [60] B. Mukherjee and S. Banerjee, "Alternative strategies for improving the fairness in and an analytical model of the DQDB network," IEEE Trans, on Computers, vol. 42, pp. 151-167, Feb. 1993. [61] J. Filipiak, "Access protection for fairness in a DQDB M A N , " Proc. IEEE ICC 89, pp. 635-639, Jun. 1989. [62] Y . S. Leu and D. H . C. Du, "Cycle compensation protocol: a completely fair protocol for the uni-directional twin bus architecture," Proc. IEEE 15th Conf. on Local Computer Networks, Oct. 1990. [63] D. E. Karvelas and M . Papamichail, "The no slot wasting bandwidth balancing mechanism for dual bus architectures," IEEE J. Select. Areas Commun., vol. 8, pp. 1214-1228, Oct. 1993. 150 Bibliography [64] D. Karvelas and M . Papamichail, "No slot wasting bandwidth balancing with immediate use of TAR bit," Proc. IEEE ICC 94, pp. 741-747, 1991. [65] D. Karvelas and M . Papamichail, "Performance study of the NSW IUT bandwidth balancing mechansim," Proc. IEEE Infocom' 94, pp. 750-757, 1994. [66] M . Kabatepe and K. S. Vastola, "The fair distributed queue (FDQ) protocol for high-speed metropolitan-area networks," IEEE/ACM Trans, on Networking, vol. 4, pp. 331-339, Jun. 1996. [67] E. L . Hahne and N . F. Maxemchuk, "Fair access of multi-priority traffic to DQDB networks," Proc. IEEE Infocom' 91, pp. 889-900, 1991. [68] C. Bisdikian and A. N . Tantawy, " A mechanism for implementing priorities in DQDB subnetworks," Proc. IEEE ICC 91, pp. 1062-1067, 1991. [69] D. Bertsekas and R. Gallager, Data networks. New Jersey, Prentice Hall, 2nd edition, 1992. [70] E. Kreyszig, Advanced engineering mathematics. John Wiley and Sons, Inc., 5th edition, 1983. [71] K. Bullington and J. M . Fraser, "Engineering aspects of TASI," Bell System Technical Journal, vol. 38, pp. 353-364, Mar. 1959.. [72] P. T. Brady, " A statistical analysis of on-off patterns in 16 conversations," Bell Syst. Tech. J., vol. 47, pp. 73-91, Jan. 1968. [73] P. T. Brady, " A model for generating on-off speech patterns in two way conversation," Bell Sys. Tech. J, vol. 48, pp. 2445-2472, Sep. 1969. [74] J. G. Gruber and N . H . Le, "Performance requirements for integrated voice/data networks," IEEE J. Select. Areas in Commun., vol. Sac-1 no.6, pp. 981-1004, Dec. 1983. [75] S. J. Campanella, "Digital speech interpolation," COMSAT Tech. Rev., vol. 6, pp. 127-158, Spring 1976. [76] A . L . Garcia, Probability and random processes for electrical engineering. Addison-Wesley Publishing Company, 2nd edition, 1994. [77] E. C. Russell, "Building Simulation Models with Simscript II.5," CACI Products Company, Oct. 1989. [78] C A C I products company, Simscript II.5 reference handbook. California, C A C I products company, 3rd edition, 1989. 151 Bibliography [79] B. Maglaris, D. Anastassiou, P. Sen, G. Karlson and J. Robbins, "Performance models of statistical multiplexing in packet video communications," IEEE Trans, on Commun., vol. 36, pp. 834-844, Jul. 1988. [80] R. O. Onvural, ATM Networks: Performance Issues. Artech House, 2nd edition, 1994. [81] G. Ramamurthy and B. Sengupta, "Modeling and analysis of a variable bit rate video multiplexer," Infocom' 92, pp. 817-827, 1992. [82] R. Schafer and T. Sikora, "Digital video coding standards and their role in video communications," IEEE Proc, vol. 83, pp. 907-924, Jun. 1995. [83] G. K. Wallace, "The JPEG still picture compression standard," Communications of the ACM, vol. 34, pp. 31^14, Apr. 1991. • [84] M . Liou, "Overview of the p x 64kbps video coding standard," Communications of the ACM, vol. 34, pp. 59-63, Apr. 1991. [85] D. L . Call, " M P E G : A video compression standard for multimedia applications," Communications, of the. ACM, vol. 34, pp. 46-58, Apr. 1991. [86] A . Dagiuklas and M . Ghanbari, "Preventive flow control method for packet video," IEE Proc. - Commun., vol. 143, pp. 98-104, Apr. 1996. [87] P; Sen, B. Maglaris, N : Riki and D. Anastassiou, "Models for Packet Switching for V B R Video Sources," IEEE Journal of Selected Areas in Communication, vol. 7, pp. 865-869, Jun. 1989. [88] D. P. Heyman and T. V . Lakshman, "Source models for V B R broadcast video traffic," IEEE/ACM Trans, on Networking, vol. 4, pp. 40-48, Feb. 1996. [89] D. Heyman, A . Tabatabai and T. Lakshman, "Statistical Analysis and Simulation Study of Video Teleconference Traffic in A T M Networks," IEEE Transcations on Circuit and Systems for Video Technology, vol. 2, pp. 49-59, Mar. 1992. [90] Y . Yasuda, H . Yasuda, N . Ohta and F. Kishino, "Packet video transmission through A T M networks," Proc. Globecom' 89, pp. 876-880, 1989. [91] F. Yegenoglu, B. Jabbari and Y . Q. Zhang, "Motion Classifed Autoaggressive Modelling for Variable Bit Rate Video Traffic," IEEE Transcations on Circuit and Systems for Video Technology, vol. 3, pp. 42-53, Feb. 1993. [92] W. Verbiest and L. Pinnoo, " A variable bit rate codec for asynchronous transfer mode networks," IEEE Journal of Selected Areas in Communication, vol. 7, pp. 761-770, Jun. 1989. 152 Bibliography [93] CCITT. Recommendation 1.311, BISDN general network aspects,. 1990. [94] J. Y . Hui, "Resource allocation for broadband networks," IEEE J. Select. Areas Commun., vol. 6, pp. 1598-1608, Dec. 1988. [95] J. S. Turner, "Managing bandwidth in A T M networks with bursty traffic," IEEE Network Mag., pp. 50-58, Sep. 1992. [96] R. Guerin, H . Ahmadi and M . Naghshineh, "Equivalent capacity and its application to bandwidth allocation in high speed networks," IEEE J. Select. Areas Commun., vol. 7, pp. 968-981, Sep. 1991. [97] T. Necker, T. Renger and H . Kroner, "Bit rate management in A T M systems using recurrent neural networks," Proc. IEEE Globecom' 94, 1994. [98] C. Muller, P. Veitch, E. H . Magill and D. G. Smith, "Emerging AI techniques for network management," Proc. IEEE Globecom' 95, 1995. [99] G. Mercankosk, Z. L . Budrikis and A. Cantoni, "Extended distributed queueing for integrated services," IEEE J. Select. Areas Commun.,. vol. 11, pp. 1193-1201, Oct. 1993. 153 Appendix A: Methods of assigning Ns RA slots over a frame of F slots Appendix A: Methods of assigning Ns RA slots over a frame of F slots Method 1: Grouping This is the simplest method where R A slots are grouped together within a frame (e.g., slots 1 to Ns are R A slots). F Method 2: Nearly uniform spreading Instead of grouping the RA slots together, they can be spreaded by the following method: 1. For the first N\ = (IRA + 1) x Ns—F RA slots, allocate one R A slot per IRA slots -2. For the remaining R A slots, allocate one R A slot per IRA +1 slots. To check the correctness of the method, we can easily verify that the total number of slots assigned by the above steps are:^! x IRA + (Ns — Ni) x (IRA + 1) = F. Define separating distance as the distance in slots between the first bit of the current R A slot and that of the next R A slot (i.e. ideally all R A slots should have the same separating distance of slots). This method ensures that the separating distance of each R A F 7Ts slot is either at most one slot). or F N~s slots (i.e., deviation from uniform spreading is limited to Method 3: Semi-uniform spreading Effectively this enhances method 2 by repositioning the R A slots such that a R A slot with separating distance of F N~3 slots is inserted in between some R A slots with separating distance of F 777 . This prevents a long burst of R A slots with a separating distance of F_ from grouping together. The method is given as follows: 154-Appendix A: Methods of assigning Ns RA slots over a frame of F slots 1. The slot generator maintains two counters CI and C2 which are initialized to F_ Ns JRA = F 2. If C l > 0 and C2< x Ns and 0 respectively at the beginning of each frame. JRA Ns-JRA , allocate one RA slot followed by F 777 - 1 non-RA slots, decrease CI by 1 and add 1 to C2, otherwise allocate one R A slot followed by Ns - 1 non-RA slots and add 1 to C2. 3. Every time C2 reaches , reset it to zero following the current operation. NS^JRA Again the correctness of this method can be verified using the same approach as above. Figure A . 1 gives an example of each the above methods with F and Ns equal to 25 and 7 respectively. It is apparent from the figure that the semi-uniform spreading method allows R A slots to be spreaded out more evenly within a frame. Method 1 R R R R R R R Method 2 R R R R R R R Method 3 Figure A . l . Examples of the slot spreading methods (The R A slots are marked by "R") 155 Appendix B: An example to illustrate the access delay problem (na < Ns) Appendix B: An example to illustrate the access delay problem (na < Ns) Suppose Ns = 4 and na=2. Denote {CAPSl, CAPS2, CAPSz, CAPSi} as 'the C A P bit values of s\, S2, S3 and S4 respectively (i.e. CAPSj = 0 indicating that Sj is available for capturing). The possible combinations are {0011}, {0101}, {0110}, {1001}, {1010} and {1100} each occurring with a probability of 1/6. An active mini-source can capture S} (the first three cases), $2 (the fourth and fifth cases) and S3 (the last case) with probability 3(l/6)=l/2, 2(l/6)=l/3 and 1/6 respectively which can be found by (4.7) as follows: 156 Appendix C: List of acronyms Appendix C: List of acronyms A A L A T M adaption layer A B R Available bit rate A C Access controller A C F Access control field A R Autoregressive A T M Asynchronus transfer mode BISDN Broadband integrated services digital network BPA Bi-state pre-arbitrated BWB Bandwidth balancing BWB_CTR Bandwidth balancing counter BWBJVIOD Bandwidth balancing modulus C A C Connection admission control C A P Capture CBR Constant bit rate CD_CTR Countdown counter C L Connectionless CO Connection oriented CQ Capture queue CR Chain release DBP Dynamic bandwidth partitioning DBS Dynamic bandwidth sharing DQDB Distributed queue dual bus FCFS First come first served F R A Fixed boundary reservation arbitrated GBP Guaranteed bandwidth protocol HOB Head of bus IR Immediate release L A N Local area network M A N Metropolitan area network M R A Movable boundary reservation arbitrated M V Motion video NB Node buffer NSW No slot waste 157 Appendix C: List of acronyms PA Pre-arbitrated P C N Personal communication network PLR Packet loss ratio PMS Packet management strategy P R M A Packet reservation mulitple access O A Queue-arbitrated QoS Quality of service R A Reservation arbitrated REQ Request RES Reserve RQ_CTR Request counter SL_TYPE Slot type " SMDS Switched multimegabit data service SR Slot register UBS Uncontrolled bandwidth sharing VBRIT Variable bit rate isochronous traffic VBRS Variable bit rate isochronous source V C Video conference VCI Virtual circuit identity VT Video telephone 158 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065022/manifest

Comment

Related Items