PERFORMANCE EVALUATION OF THE MOVABLE-SLOT TDM PROTOCOL

P E R F O R M A N C E EVALUATION OF T H E MOVABLE-SLOT T D M PROTOCOL A N D ITS A P P L I C A T I O N IN M E T R O P O L I T A N A R E A N E T W O R K S by LENNY KWOK-MING HON B . S c , Chinese U n i v e r s i t y of H o n g K o n g , 1985

A THESIS S U B M I T T E D IN P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E OF MASTER OF APPLIED SCIENCE in T H E F A C U L T Y OF G R A D U A T E STUDIES D e p a r t m e n t of E l e c t r i c a l Engineering

W e accept this thesis as conforming to the required standard

T H E UNIVERSITY OF BRITISH COLUMBIA July, 1987 © L e n n y K w o k - M i n g H o n , 1987

In

presenting

degree

at

this

the

thesis in

University of

partial

fulfilment

of

of

department

this or

publication of

thesis for by

his

or

her

representatives.

EneLAP&rii\i

The University of British Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3

DE-6(3/81)

for

an advanced

Library shall make it

agree that permission for extensive

It

this thesis for financial gain shall not

of &iPetrifjO

that the

scholarly purposes may be

permission.

Department

requirements

British Columbia, I agree

freely available for reference and study. I further copying

the

is

granted

by the

understood

that

be allowed without

head of copying

my or

my written

Abstract Movable-slot time-division m u l t i p l e x i n g ( M S T D M )

is a m e d i u m access control

protocol for the integration of voice a n d data i n local area networks. In this thesis, the performance of this protocol is evaluated through m a t h e m a t i c a l analysis a n d s i m u l a t i o n . Its application i n m e t r o p o l i t a n area networks is also studied. For the performance evaluation, a non-preemptive p r i o r i t y queueing model is first proposed for analysing the mean data delay characteristic of the slotted nonpersistent carrier-sense m u l t i p l e access w i t h collision detection ( C S M A / C D )

pro-

tocol. T h e n this a n a l y t i c a l approach is extended to the slotted M S T D M protocol w i t h non-persistent d a t a packet transmission, a n d its mean d a t a delay performance is obtained. N u m e r i c a l results from the analysis are shown a n d discussed. Moreover, s i m u l a t i o n study of the M S T D M protocol is performed. T h r o u g h the s i m u l a t i o n results, the effects of this protocol on the general delay performances of voice a n d data are discussed. It is found that i f first voice packets, w h i c h are generated at the beginning of talkspurts, are given a shorter retransmission delay t h a n d a t a packets, the channel-acquisition delay for voice sources can be reduced w i t h o u t sacrificing the data delay performance significantly. T h e s i m u l a t i o n results are also used to verify the a n a l y t i c a l results. A s the comparisons show, the accuracy of the analysis is high although it is based on a simple approximate m o d e l . For the a p p l i c a t i o n of M S T D M i n m e t r o p o l i t a n area networks, a scheme w h i c h alleviates the distance a n d transmission rate constraints associated w i t h this protocol is described.

T h e approach is to divide the stations i n a large area into

regional groups, each operating i n a different frequency band. E a c h group forms a

ii

sub-network which is part of the metropolitan area network. A n access protocol is proposed for interconnecting these sub-networks. Also a n analysis which finds the o p t i m u m number of sub-networks for interconnection is presented. T h e criterion is to minimize the mean data delay for communications i n a sub-network.

iii

Table of Contents Abstract

1

2

ii

L i s t of Figures

vi

List of Tables

viii

Acknowledgements

ix

Introduction

1

1.1

Background

1

1.2

Objective a n d Outline of the Thesis

5

Performance Analysis of C S M A / C D and MS T D M

8

2.1

CSMA/CD

9

2.1.1

Protocol Description

9

2.1.2

Analytical Model

10

2.1.3

Delay Analysis

12

2.1.4

Numerical Results

14

2.2

2.3

MSTDM

16

2.2.1

Protocol Description

16

2.2.2

Analytical Model

21

2.2.3

Delay Analysis

24

2.2.4

Numerical Results

30

Summary

37

3 Simulation of M S T D M

38

3.1

Description of the Simulation M o d e l

39

3.2

Simulation Results and Discussions

42

iv

3.3

4

Summary

5

6

M S T D M Network for a Metropolitan Area

57

4.1

Homenet Network

58

4.2

Description of the Access Protocol

61

4.2.1

Interconnection

61

4.2.2

O t h e r Related Issues

65

4.3

4.4

O p t i m u m Number of Homenets

66

4.3.1

Analysis

66

4.3.2

Numerical Results

•

Summary

69 73

5 Conclusions

^4

Appendix A

77

Appendix B

80

References

89

v

List of Figures 2.1

Packet transmission using the slotted non-persistent C S M A / C D protocol . 9

2.2

Non-preemptive p r i o r i t y queueing model for C S M A / C D

11

2.3

D a t a delay-throughput characteristics for C S M A / C D (k — 2)

15

2.4

F i r s t voice packet transmission using the slotted non-persistent

MSTDM

protocol

18

2.5

Subsequent voice packet transmission

18

2.6

Packet formats for M S T D M

20

2.7

P e r i o d i c transmission of voice packets and their repositioning when delayed by other transmission

22

2.8

Non-preemptive p r i o r i t y queueing model for M S T D M

23

2.9

R e m a i n i n g transmission time seen by a class 1 arrival

26

2.10 D a t a delay-throughput characteristics for M S T D M (a = 0.0125, k = 3) . . 32 2.11 D a t a delay-throughput characteristics for M S T D M (a = 0.05, k = 2) 2.12 D a t a delay versus fraction of data load for M S T D M (a = 0.0125, k = 3)

33 .35

2.13 D a t a delay versus fraction of data load for M S T D M ( a = 0.05, k = 2) . . . 36

3.1

D e l a y characteristics of data packets when b o t h first voice packets a n d data packets use B E B for retransmission (a — 0.0125, k — 3)

3.2

D e l a y characteristics of voice packets when b o t h first voice packets and data packets use B E B for retransmission (a — 0.0125, k = 3)

3.3

44

Delay characteristics of data packets when b o t h first voice packets a n d d a t a packets use B E B for retransmission (a = 0.05, k = 2)

3.4

43

45

D e l a y characteristics of voice packets when b o t h first voice packets and d a t a packets use B E B for retransmission [a — 0.05, k = 2) vi

46

3.5

Delay characteristics of data packets when first voice packets

rise

LIB and

data packets use B E B for retransmission (a = 0.0125, k = 3) 3.6

49

Delay characteristics of first voice packets when first voice packets use LIB and data packets use B E B for retransmission (a = 0.0125, k = 3) . . . 50

3.7

Delay characteristics of voice packets when first voice packets use LIB and data packets use B E B for retransmission (a = 0.0125, k = 3)

3.8

Delay characteristics of data packets when first voice packets use LIB and data packets use B E B for retransmission (a — 0.05, k — 2)

3.9

51

52

Delay characteristics of first voice packets when first voice packets use LIB and data packets use B E B for retransmission (a — 0.05, k = 2)

53

3.10 Delay characteristics of voice packets when first voice packets use LIB and data packets use B E B for retransmission (a = 0.05, k = 2)

54

4.1

Homenet network on a subsplit cable system

60

4.2

Inter-homenet packet transfer of bursty data

62

4.3

Link set-up for conversation between two stations in different homenets . . 64

4.4

Mean data delay for transmission within homenet as a function of the number of homenets at p = 0

70

v

4.5

Mean data delay for transmission within homenet as a function of the number of homenets at p = 0.2

71

v

4.6

Mean data delay for transmission within homenet as a function of the number of homenets at p = 0.4

72

u

vii

List of Tables B.l

9 5 % Confidence intervals for the C S M A / C D s i m u l a t i o n results shown i n F i g u r e 2.3 (fc = 2)

B.2

80

9 5 % Confidence intervals for the M S T D M s i m u l a t i o n results shown i n F i g u r e 2.10 (a = 0.0125,fc= 3)

B.3

83

9 5 % Confidence intervals for the M S T D M simulation results shown i n F i g u r e 2.11 (a = 0.05, Jfc = 2)

86

viii

Acknowledgements I w o u l d like to t h a n k m y supervisor, D r . H . W . Lee, for his encouragement a n d advice. F i n a n c i a l support from his N S E R C grant N o . A 5 9 8 6 is also gratefully acknowledged.

ix

Chapter 1 Introduction 1.1 The

Background concept of local area networks ( L A N s ) emerged when there was

a dramatic

increase i n the number of small independent computing systems, especially i n the form of microcomputers, as a result of the continuing decline i n the cost of computing hardware. In an establishment, these machines may

be dedicated to perform

specific functions. However, there is a need for t h e m to communicate with each other i n order to exploit the advantages of functionally distributed computing and share the resources effectively. T h i s communications network is regarded as a

LAN

which interconnects locally distributed computing systems.

Generally, a L A N

should satisfy a broad set of requirements such as the ones

listed as below [1]:

• high data rates (typically 1 to 10 Mbps); • geographic distance spanning from one hundred meters to a few kilometers; 1

CHAPTER

1.

INTRODUCTION

2

• a b i l i t y to support a few hundred independent devices; • good reliability; • fair access to the network by all devices; • easy installation of a small system, w i t h graceful growth as the

network

evolves; • ease of reconfiguration and maintenance; and • low cost.

T h e design of L A N s involves two i m p o r t a n t issues w h i c h are the topology of configuration and the coordination of access to the network (or the m e d i u m access control protocol) [2]. T h e y are often closely related to one another. T w o general classes of physical link topologies are the ring and the bus. In the ring topology, the access methods t y p i c a l l y employed are slotted-ring technique [3] and i m p l i c i t tokenpassing [4]. In the bus topology, the more c o m m o n ones are contention technique [5] and explicit token-passing [6]. These protocols provide access by the nodes to the transmission m e d i u m i n a distributed coordination w i t h packet-switched communications.

One of the most successful designs of L A N s , w h i c h attempt to meet the requirements listed above, is the Ethernet [7]. It employs a bus communications channel w h i c h provides a passive broadcast m e d i u m . T h e access protocol used is the carrier-sense m u l t i p l e access w i t h collision detection ( C S M A / C D )

protocol. It

is a contention protocol w h i c h allows a number of users to share a single channel i n a r a n d o m access manner w i t h no central control.

CHAPTER

1.

INTRODUCTION

3

The L A N was primarily designed for data service. However, office automation has necessitated the integration of voice and data into a single L A N . There are two potential advantages of this implementation:

• cost savings gained from the sharing of the transmission and the switching facilities; and • provisions of more sophisticated services to the users.

Yet integrating voice and data creates a new set of communications problems, which are mainly due to their different traffic characteristics. Voice is periodic traffic that requires real-time delivery while data is bursty traffic that can tolerate long delays. Therefore, to make the integration possible, new medium access control protocols have to be applied, which can fulfil the different requirements for both voice and data traffic in L A N s . There have been many new protocols proposed in this research area.

When

applied to a (implicit or explicit) token-passing or a slotted-ring network, they take the advantage of the round-robin approach in the access method, which bounds the channel access delay, to meet the demands of the periodic traffic from voice sources [8] [9]. However, because the channel access delay in contention technique is unbounded, it is not suitable for integrating voice and data. Usually it has to form a hybrid with the reservation scheme to suit this task [10]. Because of the popularity of applying the C S M A / C D protocol in L A N s , typified by the numerous Ethernet installations, it can be a very attractive feature if these C S M A / C D L A N s can be upgraded to provide voice and data services with minimal

CHAPTER

1.

INTRODUCTION

4

changes i n the system. T h e enhancement can be achieved by a p p l y i n g the movableslot t i m e - d i v i s i o n m u l t i p l e x i n g ( M S T D M ) protocol to the network [11] [12].

It is a

simple v a r i a t i o n on C S M A / C D , w h i c h enables voice and d a t a integration i n a rand o m access manner a n d has a n upper b o u n d on voice packet delay. I n this protocol, d a t a sources follow the same set of rules for transmission as i n C S M A / C D . Therefore, i n m i g r a t i n g from a C S M A / C D L A N to a M S T D M L A N , it is not necessary to modify the d a t a stations. N e w voice stations a n d v o i c e / d a t a h y b r i d stations can be added onto the network s i m p l y by t a p p i n g to the passive transmission m e d i u m . A s a result, M S T D M lends itself to be a n attractive protocol for the integration of voice a n d data.

L A N s are l i m i t e d by their geographic distance. T h e y can work well over a distance of a few kilometers. However, as they elongate, problems such as performance degradation and decline i n reliability occur [13]. Solving the distance l i m i t a t i o n p r o b l e m can increase the attractiveness of the office information system so that office branches located at distant locations i n a m e t r o p o l i t a n area can become part of the network a n d c a n share information of voice a n d d a t a [14-17]. M o r e o v e r , different companies can participate i n the same m e t r o p o l i t a n area network ( M A N ) and exchange information w i t h each other, i n a d d i t i o n to c o m m u n i c a t i n g w i t h i n their own premises through the M A N . If the M A N supporting voice a n d data services can be expanded to the community, the local telephone subscriber loops can even be replaced b y the network. Besides, new and advanced services such as home b a n k i n g a n d home shopping c a n be provided i n cooperation w i t h the b a n k i n g and merchandising companies. However, back to the p r o b l e m addressed at the beginning, we first have to solve the distance constraint associated w i t h the networks before these

CHAPTER

1.

INTRODUCTION

5

new concepts c a n be put into realization. T h e i n t r o d u c t i o n above has briefly reviewed the evolution from L A N s p r o v i d i n g data-only service to M A N supporting voice a n d data integration. In the following parts of the thesis, attention is focused on the M S T D M protocol. T h e performance of this protocol is evaluated through m a t h e m a t i c a l analysis a n d s i m u l a t i o n , for its a p p l i c a t i o n i n L A N s [18-20]. T h e method of a p p l y i n g the protocol to the M A N s , w h i c h have the potentialities to provide the services as described i n the previous paragraph, is also studied [21]. Because of the s u i t a b i l i t y of the a n a l y t i c a l m o d e l a n d the close relationship between C S M A / C D a n d M S T D M , a m i n o r part of the thesis is devoted to the performance analysis of the C S M A / C D protocol.

1.2

Objective and Outline of the Thesis

T h e r e have been some analyses on the performance of C S M A / C D i n the literature, e.g. [22], [23] and [24]. In the first part of C h a p t e r 2, a non-preemptive p r i o r i t y queueing m o d e l is proposed for analysing the mean delay-throughput performance of the slotted non-persistent C S M A / C D protocol. T h i s a n a l y t i c a l m o d e l presents a simpler way of performance evaluation t h a n the previous works. W e shall see later that a l t h o u g h it is a simple approximate model, it provides very p r o m i s i n g explicit results w h i c h are verified by simulation. U n l i k e C S M A / C D , there has been no a n a l y t i c a l result of the d a t a delay performance of M S T D M before. In the second part of C h a p t e r 2, a queueing model, w h i c h is similar to the one for C S M A / C D , is formulated for analysing the mean delay-throughput characteristic of data packets for the slotted M S T D M protocol

CHAPTER

1.

INTRODUCTION

6

with non-persistent data packet transmission. Numerical results are obtained from the analysis and compared with simulation results. The comparisons show that the analytical model proposed yields accurate results for the data delay performance of MSTDM.

The M S T D M protocol can be considered as a more general case of the C S M A / C D protocol, which allows the integration of voice and data. Without voice, M S T D M degenerates to C S M A / C D . The purposes of including the performance analysis of C S M A / C D here are twofold.

One is to look into the data delay performance of

this more 'specific' protocol directly in our new approach. Another is to show the accuracy of this modeling approach before we apply it to analyse the M S T D M protocol. The analysis of M S T D M gives only the mean of data delay, but not its higher moments as well as any information on voice delay characteristics.

In order to

have a thorough understanding on the characteristics of M S T D M and to provide a means for verifying the delay analysis in Chapter 2, simulation was performed for this protocol. Since the first voice packet generated at the beginning of a talkspurt from an active voice source uses C S M A / C D as a data packet in the M S T D M system, we may give the former a shorter retransmission delay than the latter so as to reduce the channel-acquisition time for voice sources, as explained in Section 2.2.1. In the simulation studies, the same as well as different retransmission scheduling algorithms were applied to data packets and first voice packets. In each case, the effects of the M S T D M protocol on the delay performances of data packets, first

CHAPTER

1.

INTRODUCTION

7

voice packets a n d subsequent voice packets were obtained i n terms of the mean and the standard deviation of their delay. C h a p t e r 3 shows the s i m u l a t i o n model, the s i m u l a t i o n results a n d the discussions. Because M S T D M is a bus contention p r o t o c o l , its efficiency decreases inversely w i t h the transmission rate a n d the channel length. T h e p r o t o c o l works well o n local area networks where the distance between the stations at the two ends is typically less t h a n a few kilometers a n d the bit rate is i n the order of 1 to 10 M b p s . W h e n it is applied to a m e t r o p o l i t a n area network w i t h a distance being a n order of magnitude longer, the transmission rate should be decreased by a n order of magnitude i n order to m a i n t a i n the same efficiency. However, this is incapable of p r o v i d i n g adequate d a t a a n d voice services to such a large c o m m u n i t y of users. In C h a p t e r 4, a scheme w h i c h was proposed i n [16] to enable the

MSTDM

protocol to be applied efficiently to a large network is described. T h e approach is to divide the system into a number of broadband local area networks called homenets. However, the method for inter-homenet communications is not clearly examined i n [16]. I n this thesis, we enhance the scheme by proposing an access protocol for the interconnection of homenets.

It facilitates the communications between

i n different homenets for b o t h voice and d a t a services.

stations

T h e issues about traffic

control and addressing are also mentioned. Moreover, based on the a n a l y t i c a l results obtained for M S T D M i n C h a p t e r 2, we find the o p t i m u m number of homenets for interconnection, w h i c h minimizes the mean data delay w i t h i n homenet.

F i n a l l y , C h a p t e r 5 contains the conclusions w h i c h review the major results of the research work.

Chapter 2 Performance Analysis of CSMA/CD and MSTDM In this chapter, a non-preemptive p r i o r i t y queueing m o d e l is first proposed for the performance evaluation of the slotted non-persistent C S M A / C D p r o t o c o l . T h e n it is extended to a more 'general' v o i c e / d a t a model for the M S T D M p r o t o c o l , a v a r i ation on C S M A / C D , w h i c h enables voice a n d data integration i n a r a n d o m access manner w i t h a n upper b o u n d on voice packet delay. F o r each of the two protocols, the analysis yields explicit results for the mean delay-throughput characteristics of data packets. N u m e r i c a l results are presented and discussed. A s comparisons w i t h s i m u l a t i o n results show, the accuracy of the analysis is h i g h although it is based on a simple approximate m o d e l .

8

CHAPTER 2. PERFORMANCE ANALYSIS OF CSMA/CD AND MSTDM

other transmission

successful packet transmission

collision

i

i

i

I

I

9

i

i

I

I

I

l

I

1

I

I

I

I

(> one arrival)

F i g u r e 2.1: Packet transmission using the slotted non-persistent C S M A / C D protocol.

2.1

CSMA/CD

2.1.1

Protocol Description

T h e slotted non-persistent C S M A / C D protocol is considered here. I n this protocol, the time axis is (mini-)slotted w i t h slot size equal to the end-to-end channel propagation delay (r second). Transmission can only be started at the beginning of a slot. A l l d a t a sources are synchronized to follow this restriction. W h e n a data source has a packet ready for transmission, it senses the channel and proceeds as follows (also see F i g u r e 2.1).

1. If the channel is sensed idle, it initiates transmission of the packet. 2. If a collision is detected d u r i n g transmission, the transmission is aborted and the packet is scheduled for retransmission at some later time w h i c h is deter-

CHAPTER

2.

PERFORMANCE

ANALYSIS

OF CSMA/CD

AND MSTDM

10

m i n e d b y a retransmission scheduling scheme. T h e n the d a t a source repeats the a l g o r i t h m . 3. If the channel is sensed busy, the data source reschedules the transmission of the packet to some later t i m e using the retransmission scheduling scheme and repeats the a l g o r i t h m .

2.1.2

Analytical Model

We assume, i n the following, that the number of d a t a sources i n our C S M A / C D system is infinite a n d they collectively form an independent Poisson source w i t h a n aggregate mean packet arrival rate of A2 packets/second. Moreover, the system is stable so that the input rate of d a t a packets is equal to the output rate. T h e r e are two types of events that h a p p e n i n the channel. T h e y are (successful) d a t a packet transmission and d a t a packet collision. W e attempt to consider t h e m as two independent processes and we t e r m packet collision as transmission of collision packet. B y means of a suitable retransmission scheduling scheme [25], we assume that the p r o b a b i l i t y of successful transmission i n a contention slot is m a i n t a i n e d to be constant, w h i c h is independent of the number of packets i n the system. constant p r o b a b i l i t y is denoted by a factor l/v.

This

Therefore, the mean arrival rate of

collision packets is Ax = {y — 1)A packets/second. 2

If T is so small i n the C S M A / C D system that the d u r a t i o n of a collision can be neglected, we c a n approximate the system by the M / G / l queue because the arrival of d a t a packets is Poisson.

A s we now consider packet transmission a n d packet

collision as two independent processes, we attempt to m o d e l each of t h e m w i t h the

CHAPTER

2.

PERFORMANCE

ANALYSIS

OF CSMA/CD

AND MSTDM

11

F i g u r e 2.2: Non-preemptive p r i o r i t y queueing m o d e l for C S M A / C D .

M / G / l queue a n d they together form a non-preemptive p r i o r i t y queueing system (as shown i n F i g u r e 2.2) i n w h i c h collision packets have a higher p r i o r i t y of transmission t h a n d a t a packets. T h e mean a r r i v a l rate of the former is A i packets/second whereas t h a t of the latter is A2 packets/second. A s the a n a l y t i c a l m o d e l is prioritized, (successful) data packet transmission cannot occur while collision packet is present, w h i c h implies collision of data packets i n the system. However, the model is non-preemptive so t h a t a d a t a packet w i l l be t r a n s m i t t e d u n t i l completion i f it can acquire the channel successfully, i.e. no collision occurs at the beginning of the transmission. U n d e r a stable c o n d i t i o n of the m o d e l , the r a t i o of the number of d a t a packet transmissions to the t o t a l of the two types of channel events is \Jv on the average.

In the next section, we shall use this m o d e l to find the delay-throughput performance of the slotted non-persistent C S M A / C D protocol.

CHAPTER

2.1.3

2.

PERFORMANCE

ANALYSIS

OF CSMA/CD

AND MSTDM

12

Delay Analysis

For the M / G / l m o d e l w i t h two non-preemptive priorities like the one shown i n F i g u r e 2.2, we denote the packets i n the higher p r i o r i t y queue as the class 1 packets a n d the ones i n the lower p r i o r i t y queue as the class 2 packets.

T h e lengths of

class 1 packet a n d class 2 packet are respectively rhi a n d ra , w h i c h m a y be r a n d o m 2

variables of any d i s t r i b u t i o n i n second.

T h e mean w a i t i n g time ( W ) of class 2 2

packets i n this model (see A p p e n d i x A ) is given b y

2(1 — A m ) ( l — Xiffii — A m ) 1

where m~i a n d m

2

1

2

2

are the mean lengths of class 1 packets and class 2 packets

respectively, a n d m j a n d m

2

are the second moments.

T o model the C S M A / C D protocol, we assume the length of collision packets, i.e. the collision recovery time, is a m u l t i p l e of the end-to-end channel propagation delay T. Therefore, m i — mi

—

kr

(2-2)

where k is a n integer. Because of propagation delay, the channel w i l l not be sensed idle right after a packet has been successfully transmitted. T h u s , the length of class 2 packet is longer t h a n the actual length of data packet by some propagation delay. W e assume the difference is one end-to-end channel propagation delay. Therefore, m

2

= m +

T

(2.3)

where m is the length of data packet a n d is assumed to be a m u l t i p l e of r . A s the channel is slotted, a packet has a n additional w a i t i n g time of half a slot, i.e. r / 2 , on

CHAPTER

2. PERFORMANCE

ANALYSIS

OF CSMA/CD

AND

MSTDM

13

the average. T h i s factor is not characterized by our a n a l y t i c a l m o d e l . T o make the correction, we have to add the t e r m r / 2 to the mean w a i t i n g t i m e of data packets i n (2.1).

T h e mean delay of data packets is defined as the s u m of the mean packet w a i t i n g t i m e a n d the mean packet transmission time. F o r simplicity, here we let the length of d a t a packets be constant, i.e. m = m. U s i n g (2.1) to (2.3) and replacing A i w i t h — l ) , we o b t a i n the normalized mean delay (D ) n

of d a t a packets after d i v i d i n g

the mean delay b y m a n d it is given by [ f c W ^ - l ) + ( l + a) ] 2

P d

2[1 - kp a{u - 1)]{1 - p [l + a + ka{u - 1)]}

n

d

d

where Pd = A m is the data throughput and a = r/m 2

a

2

,

'

{

}

is the n o r m a l i z e d end-to-end

channel propagation delay. N o t e that as a goes to zero, (2.4) can be a p p r o x i m a t e d by the M / D / l delay equation (see e.g. [26]) w h i c h is given by

B

" =

1 +

2(T^)-

2 5

T o find the m a x i m u m d a t a throughput that the C S M A / C D system c a n achieve, we have, f r o m our queueing m o d e l , that Aimx + A m 2

2

< 1

(2.6)

if the system is stable. T h i s implies that for the C S M A / C D system,

P d

< l + a[k{v-l)

+ l) •

'

(2

7)

If retransmission is o p t i m i z e d b y means of a suitable adaptive retransmission sched u l i n g scheme, the p r o b a b i l i t y of successful transmission i n a contention slot is

CHAPTER

2.

l / e , i.e. \jv

PERFORMANCE

ANALYSIS

OF CSMA/CD

AND

MSTDM

14

= l / e , w h i c h is the m a x i m u m for the slotted r a n d o m access protocol

[22] [25]. Therefore, substituting u = e into (2.7), we have

P d

2.1.4

< 1 + a[k(e-

1) + 1] •

( 2

-

8 )

Numerical Results

We use (2.4) to o b t a i n the mean delay-throughput characteristics for data packets of constant length.

In the following examples, the collision recovery time is

twice the end-to-end channel propagation delay, i.e. k — 2. A l s o we assume that retransmission is o p t i m i z e d so that we have v = e. F i g u r e 2.3 shows the a n a l y t i c a l results together w i t h the s i m u l a t i o n results for a=0.001, 0.01, 0.05, 0.1 a n d 0.2 respectively.

W e see from the figure that the

curves obtained from b o t h methods are very close to one another for each value of a.

T h e results show that the performance of the C S M A / C D protocol declines

w i t h a being increased.

F r o m light to m e d i u m load (relative to the m a x i m u m

throughput achievable for a particular a) of data traffic, the m e a n delay of d a t a packets is quite small. However, it increases r a p i d l y as the traffic becomes heavy. T h i s is a well-known characteristic for the performance of d a t a packets using r a n d o m access protocol for transmission. Moreover, the m a x i m u m throughput that can be achieved increases w i t h a being reduced because less channel capacity is wasted i n collisions a n d removals of signal propagation after successful packet transmissions. W h e n a is equal to 0.001, the delay curve of the C S M A / C D p r o t o c o l is almost identical to the one obtained from the M / D / l delay equation i n (2.5).

O u r s i m u l a t i o n model for the slotted non-persistent C S M A / C D assumes a n i n -

CHAPTER

2. PERFORMANCE

I

1

I

ANALYSIS OF CSMA/CD

AND MSTDM

L

D = a-0.001

Data throughput

Figure 2.3: Data delay-throughput characteristics for C S M A / C D (k = 2).

15

CHAPTER

2. PERFORMANCE

ANALYSIS

OF CSMA/CD

AND MSTDM

16

finite p o p u l a t i o n of d a t a sources w h i c h collectively form a n independent Poisson source. T o o b t a i n the s i m u l a t i o n results shown i n F i g u r e 2.3, we assume the length of d a t a packets is constant and it takes the time of one end-to-end channel propagat i o n delay to have the effects of signal propagation removed from the channel after a successful packet transmission. T h e adaptive retransmission scheduling a l g o r i t h m t h a t we use i n the simulation is b i n a r y exponential backoff. A s comparisons w i t h the s i m u l a t i o n results show, the accuracy of our analysis turns out to be h i g h a l t h o u g h it is based on a simple queueing model. T h e 95% confidence intervals for the C S M A / C D s i m u l a t i o n results shown i n F i g u r e 2.3 are listed i n A p p e n d i x B . l , together w i t h the a n a l y t i c a l results for easy comparisons.

2.2

M S T D M

2.2.1

Protocol Description

Speech from a n active voice source consists of alternating intervals of talkspurt and silence. D u r i n g talkspurt, voice packets are generated from digitized voice; however, there are none i n a silent period. T h e M S T D M protocol enables voice and d a t a i n tegration i n a r a n d o m access manner [11][12]. A s it is a v a r i a t i o n on C S M A / C D , d a t a packets are treated exactly the same i n this protocol as i n C S M A / C D . M o r e over, the first voice packet generated at the beginning of a talkspurt from a n active voice source follows the C S M A / C D protocol as a d a t a packet.

W e consider here

the slotted non-persistent M S T D M w h i c h has the same set of rules for b o t h data packets and first voice packets as those given i n section 2.1.1

CHAPTER

2.

PERFORMANCE

ANALYSIS

OF CSMA/CD

AND MSTDM

17

W h e n speech energy is detected at the beginning of a talkspurt, transmission of the first voice packet is activated as soon as voice bits of the first voice sample arrive. D e p e n d i n g o n the w a i t i n g time of this packet, there is a variable number of voice bits i n i t . Y e t there is a m a x i m u m number of voice bits, say S, that c a n be placed i n the packet, because the packets generated b y voice sources are constrained to have a fixed length as explained later. If there are more t h a n S voice bits coded when the channel is acquired, only the last S bits are t r a n s m i t t e d a n d the earlier ones are discarded; thus, the speech at the beginning is clipped. However, we shall see i n the next chapter that we can give first voice packets a shorter retransmission delay t h a n d a t a packets i n order to reduce the channel-acquisition t i m e for voice sources. I n this way, the chance of voice bits being discarded is considerably decreased, yet the performance of data packets is not deteriorated significantly.

After a voice source has successfully transmitted its first packet, it plans on t r a n s m i t t i n g its next packet i n a fixed time T w h i c h is its p e r i o d of transmission (Figure 2.4). W i t h i n a period, new voice bits arrive a n d fill up the data area of the voice packet. Subsequent voice packets i n a talkspurt after the first one follow a subset of the C S M A / C D rules. W h e n a voice source has a packet (other t h a n the first one i n a talkspurt) ready for transmission, it senses the channel a n d proceeds as follows (also see F i g u r e 2.5).

1. If the channel is sensed idle, it initiates transmission of the packet w i t h o u t listening to the channel. 2. If the channel is sensed busy, the voice source refrains from transmission and keeps o n listening to the channel. W h e n the channel becomes idle, it initiates

CHAPTER 2. PERFORMANCE

other transmission

i

i

A

collision

successful first voice packet transmission

V//

//A 1\

ANALYSIS OF CSMA/CD AND MSTDM

1\

18

second voice packet transmission 1 1 1 1

1

1

••• •

1

1\

(> one arrival)

Figure 2.4: First voice packet transmission using the slotted non-persistent M S T D M protocol.

other transmission

voice packet transmission

Figure 2.5: Subsequent voice packet transmission.

CHAPTER

2. PERFORMANCE

ANALYSIS

OF CSMA/CD

AND MSTDM

19

transmission of the packet w i t h o u t listening to the channel.

(Note that the rules above represent the 1-persistent C S M A w i t h o u t collision detection protocol.) For the slotted M S T D M , a l l voice sources are synchronized to start transmission only at the beginning of a slot as d a t a sources. In the following, we call the subsequent voice packets i n a talkspurt after the first one simply as voice packets and that first one as the first voice packet. We find that a voice packet m a y experience collision w i t h d a t a packet(s) a n d / o r first voice packet(s) i n the vulnerable interval. Moreover, e x t r a voice bits keep on a r r i v i n g d u r i n g the w a i t i n g t i m e of a voice packet, w h i c h cannot be carried i n the d a t a area of the packet. T o overcome these problems, voice packets have a specific packet format w h i c h is s h o w n i n F i g u r e 2.6, together w i t h the format of d a t a packets for comparison. It consists of a preempt area, a header area, a d a t a area and an overflow area. W h e n a voice source initiates transmission of a voice packet, it places a signal (which forms the preempt area of the packet) on the transmission m e d i a b u t does not send information d u r i n g the vulnerable interval. T h i s interval is long enough for d a t a sources as well as voice sources t r a n s m i t t i n g their first voice packets to detect a collision, stop t r a n s m i t t i n g , and have the effects of their transmission removed from the channel before the voice source begins t r a n s m i t t i n g useful data. A s first voice packets use C S M A / C D , they do not have a preempt area.

If we restrict the length of d a t a packets to be equal to or less t h a n that of voice packets, the m a x i m u m w a i t i n g time incurred by a voice source is never greater t h a n one voice packet transmission t i m e after it has successfully t r a n s m i t t e d the first

CHAPTER

2.

preempt area

PERFORMANCE

packet header

ANALYSIS

OF CSMA/CD

AND MSTDM

data area

20

overflow area

(a) voice packet

(b) data packet

F i g u r e 2.6: Packet formats for M S T D M .

voice packet i n a t a l k s p u r t . A s voice bits arrive continuously, the overflow area is used for a c c o m m o d a t i n g those voice bits w h i c h arrive while a voice source is w a i t i n g for transmission, a n d it is long enough to carry a l l of the e x t r a voice bits while a voice source is delayed b y as m u c h as one voice packet transmission time.

The

voice source loses the privilege of not listening while t r a n s m i t t i n g after a talkspurt is over. I n the next talkspurt after a silent p e r i o d , the first voice packet has to be t r a n s m i t t e d according to the whole set of the C S M A / C D rules. A l s o , collision a m o n g voice packets never occurs because voice sources p l a n on t r a n s m i t t i n g their next packet one p e r i o d after they have successfully acquired the channel. F o r the transmission of the subsequent voice packets i n a talkspurt after the first one, a d a t a source cannot delay a voice source enough to make it collide w i t h

CHAPTER

2.

PERFORMANCE

ANALYSIS

OF CSMA/CD

AND MSTDM

21

another voice source. F i g u r e 2.7 shows the s i t u a t i o n w h e n the periodic transmission of voice packets is delayed by a d a t a source. W e see that voice sources appear to acquire T D M slots for transmission. Y e t these periodic slots are repositioned w h e n other transmissions interfere w i t h them. T h a t is w h y it is called movable-slot T D M protocol.

2.2.2

Analytical Model

In the following, the phrase ' d a t a packets' includes b o t h actual d a t a packets a n d first voice packets. W e assume the former and the latter have the same retransmission delay d i s t r i b u t i o n so that they behave w i t h o u t any difference from each other i n the system. There are three types of events i n the M S T D M channel. T h e y are voice packet transmission, (data) packet collision and (successful) data packet transmission. We k n o w from the p r o t o c o l description that collision of voice packet w i t h data packet has no effect on the voice packet transmission because useful information is not sent i n the preempt area of voice packet. T h u s , a voice source t r a n s m i t t i n g voice packet is oblivious of d a t a packet transmission a n d once the channel becomes idle, a ready voice source c a n acquire the channel successfully. Voice packet transmission has, therefore, the highest p r i o r i t y of acquiring the channel among the three types of channel events, but it is non-preemptive as voice sources listen before t r a n s m i t t i n g . F r o m section 2, we see that the performance of data packets for C S M A / C D can be a p p r o x i m a t e l y analysed by a non-preemptive p r i o r i t y queueing m o d e l . Here we attempt to extend this model to include voice packets for f o r m u l a t i n g an approx-

CHAPTER

2. PERFORMANCE

ANALYSIS OF CSMA/CD

AND MSTDM

22



class 1 a r r i v a l

F i g u r e 2.9: R e m a i n i n g transmission time seen by a class 1 arrival.

m e a n d u r a t i o n is l / A i because the interarrival time is exponentially distributed. T h e mean number of class 1 arrivals at the queue is, by expectation, given b y

1

A

(2.9)

x

T h u s , the throughput of class 1 packets is A j r o i / ( l + AiVK ) . x

Define Pi -

Ajmi

-, pi = A m , ps — A m .

i + AiWy

2

2

3

3

(2.10)

W e are next going to find the mean w a i t i n g times of class 1, 2 and 3 packets i n the queues, w h i c h are respectively denoted by V 7 , H 1

/ 2

and

W. 3

Class 1

A s s u m e there is a class 1 a r r i v a l while another class 1 packet is being transmitted as shown i n F i g u r e 2.9. L e t Y\ denote the remaining transmission time seen b y the

CHAPTER 2. PERFORMANCE

ANALYSIS OF CSMA/CD AND MSTDM

26

a r r i v i n g class 1 packet. N o w , e

-Ai(m -t/)('^ _ 1

P r o b [Yi < y|packet length = m i ] =

_ _

g-Aiy\

A i m i

(2.11)

a n d its p r o b a b i l i t y density function is f(y|packet length = m i ) =

_ _ e

A i m i

•

(2.12)

Thus, Yi

=

/ Jo

yf(y|packet length = m i ) dy mi

1 -

e-*i i

(2.13)

Xi '

m

S i m i l a r l y , the mean remaining transmission times of class 2 and class 3 packets seen by a class 1 a r r i v a l (which successfully goes into queue 1) are, respectively, TT

m

1 Ai

2

1 - e~ ^ x

(2.14)

and ^3 = — 1 - e-^ *

• Ai

m

(2.15) v

1

T h u s , the mean w a i t i n g time of class 1 packets is given b y W

1

= piFi + pY 2

2

+ pY 3

3

.

(2.16)

F r o m (2.16), we have, after some manipulations, {Wi.) - fiWt + -y = 0 2

where =

X m\ 2

X ml 3

_ 1

(2.17)

CHAPTER

AT

PERFORMANCE

ANALYSIS

r ^ r — j-

1 / 7 =

2.

A m 2

+

2

+

A m A 3

3

1-e-Aimx

OF CSMA/CD

+

AND MSTDM

\ m\

A m|

2

Ai(l-e-

27

A i m 2

)

+ Ai(l -

3

e-

A

i

3)

m

(2.19)

F r o m (2.17), we have (2.20)

Wi =

Class 2

We have, by expectation, that the mean w a i t i n g time of class 2 packets is given by (see e.g. [26]) W

2

=

mean remaining transmission time seen by the class 2 arrival + mean transmission time for the packets i n peer and higher p r i o r i t y classes, w h i c h have already been i n the queues at the class 2 a r r i v a l + mean transmission time for the packets i n higher p r i o r i t y class, w h i c h arrive d u r i n g the w a i t i n g time of the class 2 packet .

(2-21)

T h i s implies

^ 2

2

psms

^

2

^

X Wm 1

*

'

i

t

1 + AiWi

where iV- represents the mean number of class i packets i n queue i for i=l, t

B y L i t t l e ' s F o r m u l a , we have

V

'

2 or 3.

CHAPTER

2.

PERFORMANCE

ANALYSIS

N o t e that the t e r m XiW rrii/(l

+ ^1^1)

2

OF CSMA/CD

AND MSTDM

28

(2.22) is a n a p p r o x i m a t i o n for the t h i r d

m

component of W i n (2.21), since the arrival d i s t r i b u t i o n of class 1 packets (those 2

w h i c h get into queue 1 successfully) is not P o i s s o n because of the blocking.

To

simplify the analysis, we assume the a r r i v a l is Poisson w i t h mean A i / ( 1 + Ait-V^) here. F r o m (2.22), we have

(1 + A ^ ) ( l - A m ) - Airrn 1

1

2

V

;

2

where

Class 3

S i m i l a r to class 2, the mean w a i t i n g t i m e of class 3 packets is given b y pm

pxmi

m

W

3

2

pm

2

3

= —^— + -j-

J^—

3

XiW^rm

+ — ^ — + 2^ Nirrii +

i

+

^—

— + XWm 2

3

2

(2.26)

where by L i t t l e ' s F o r m u l a , N

3

= XW 3

.

3

(2.27)

After some manipulations, we have, from (2.26), W

3

=

$

+ ™0 + X m W {i

+

2

(1 + A W ) ( 1 - A m 1

1

2

2

2

+ XiWj)

2

^

2g

- A m ) - Aimi 3

3

R e c a l l that W denotes the mean w a i t i n g time of d a t a packets for the M S T D M 3

protocol. T o be specific for modeling the performance measure, we have to incorporate the system characteristics into the equations we have obtained above. F o r M S T D M , the length of data packets cannot be longer t h a n that of voice packets. In

CHAPTER

2.

PERFORMANCE

ANALYSIS

OF

CSMA/CD

AND

MSTDM

29

our model, as d a t a packets represent a m i x t u r e of actual d a t a packets a n d first voice packets, the assumption of constant packet length, w h i c h is made at the beginning of this section, has i m p l i c i t l y set the length of d a t a packets to be equal to that of voice packets because first voice packets and voice packets are of the same fixed length. Here we denote their length b y m w h i c h is assumed to be a m u l t i p l e of the end-to-end channel propagation delay r .

Define \3rr1,

Pd

=

p

v

(2.30)

A m x

A ra Pv

where W

(2.29)

the d a t a throughput

Pv

x

=

1 + X1W1

pW

1+

v

,

is the normalized value of Wi w.r.t. ra; a n d V F

ln

(2.31)

the voice t h r o u g h p u t

ln

2 n

and W

Sn

have the

similar meaning i n the following. U s i n g the same assumptions a n d symbols we have made for C S M A / C D i n section 2.1.3, we have

(2.32) where

Jfc a (i/-1) 2

Pn = Pd

2

1 _ -kap e

In

=

+

(1 + a) 1 _

v

^\l Pv I

— {1 + p [l + a + ka{v - 1)}} d

-(l+a)p

e

+ a + ^[l Pv

+ a + 2

1+0[

Pd

ka{u-l)] k a {v-l) 2

2

p

ln

-

1 _

v

ln

v

(1 + a )

+

-kap

v

$n + PvW {l (1 + p W )[l

(2.33)

Pv

v

(1 + tt) 1 - e-( )^

W 2n

2

+ a +

ka{u -

l)p ] d

-(l+a)h

n

p {l v

(2.34)

e

$) -

2

+ a)

(2.35)

CHAPTER

2.

PERFORMANCE

ANALYSIS

OF CSMA/CD

AND MSTDM

30

where 1 \ p (l

+ a)>

2 \l +

faW

v

W

=

®n + PvW^jl Pv

2

d

+

ln

(2.36)

k a (is-l)} 2

2

ln

+ a + $n) + koi{u - l) W {l

(1 + W ){l

3 n

+ p [(l + a)

Pd

+ p„^

2n

- p [l + a + ka{u - 1)]} d

Pv

(l

+ a)

l n

)

(2.37)

W e have mentioned before that because the channel is slotted, a packet has an a d d i t i o n a l w a i t i n g t i m e of half a slot on the average. W e neglected this factor i n our analysis. T h u s , we have to a d d the t e r m r / 2 to the mean w a i t i n g t i m e of data packets i n (2.37). Therefore, the normalized mean delay of d a t a packets is, after some m a n i p u l a t i o n s , given b y

D

n

= 1 + W

Sn

+

(2.38)

|

W e notice that i n (2.38), the normalized mean d a t a delay D

n

terms of p

d

and p . v

T o compute the voice throughput p

v

a n d p„, we first use (2.32) to find W . in

corresponds.

2.2.4

Numerical Results

d

v

from given values of p

d

T h e n we can take (2.31) a n d the value of

W i n just obtained to calculate the voice throughput p p and p

is expressed i n

v

to w h i c h the given pair of

In the following numerical results, we assume that retransmission of data packets is o p t i m i z e d by means of a suitable adaptive retransmission scheduling scheme so that the p r o b a b i l i t y of success i n contending for an empty slot among d a t a sources

CHAPTER

2.

PERFORMANCE

ANALYSIS

OF CSMA/CD

AND MSTDM

31

is l / e , i.e. v = e. I n F i g u r e 2.10 and F i g u r e 2.11, we plot the d a t a delay-throughput characteristics at various values of p using numerical results as well as s i m u l a t i o n v

results.

T h e values of the system parameters used i n F i g u r e 2.10 are a=0.0125

and k=S whereas they are respectively 0.05 a n d 2 i n Figure 2.11. F r o m the figures, we observe that the data delay-throughput characteristic for M S T D M displays the same trend as that for C S M A / C D . A l s o , the delay performance declines apparently when the voice throughput p i n the channel increases. v

T h i s is obvious because voice packets occupy part of the channel capacity for transmission.

W i t h a higher voice throughput, the m a x i m u m of the d a t a throughput

that can be achieved is reduced relatively. W h e n voice t h r o u g h p u t decreases, the d a t a delay curve approaches that of C S M A / C D as expected. I n our s i m u l a t i o n model for the slotted M S T D M protocol, we assume there is an infinite p o p u l a t i o n of d a t a sources w h i c h collectively form a n independent Poisson source. T h e number of voice sources is, on the other h a n d , finite and we assume all of t h e m are active. B y v a r y i n g the number of voice sources, we can change the level of voice throughput i n our system.

A s we have done for the analysis,

the first voice packets are considered as part of the d a t a packets i n the simulation. The

actual d a t a packets have the same length as the packets generated by voice

sources. Moreover, it takes the time of one end-to-end channel propagation delay to have the effects of signal propagation removed from the channel after a packet transmission.

T h e adaptive retransmission scheduling a l g o r i t h m used is b i n a r y

exponential backoff w h i c h is applied to b o t h d a t a packets and first voice packets. A more detailed description of the simulation model is given i n the next chapter. T h e 95% confidence intervals for the M S T D M s i m u l a t i o n results shown i n F i g u r e 2.10

CHAPTER

2. PERFORMANCE

ANALYSIS

0.4

0.S

OF CSMA/CD

AND MSTDM

32

0.6

Data throughput

F i g u r e 2.10: D a t a delay-throughput characteristics for M S T D M k = 3).

(a

= 0.0125,

CHAPTER

2.

I

PERFORMANCE

1

1

ANALYSIS OF CSMA/CD AND MSTDM

1

I

I

33

L

analysis simulation

>>

a T J

C 2

0.000 0.045 0.146 0.292 0.439 0.586 0.0

0.1

0.2

0.3

0.4

0.5

0.6

Data throughput

T—" 0.7

0.8

i o.o

F i g u r e 2.11: D a t a delay-throughput characteristics for M S T D M (a = 0.05, k = 2).

1.0

CHAPTER

2.

PERFORMANCE

ANALYSIS

OF CSMA/CD

AND MSTDM

34

a n d F i g u r e 2.11 are listed i n A p p e n d i x B . 2 , together w i t h the a n a l y t i c a l results for easy comparisons. F i n a l l y , we see from the figures that the curves obtained from the analysis a n d the s i m u l a t i o n m a t c h very well w i t h each other. T h i s shows that our analysis gives very good approximate results for the d a t a delay performance of the M S T D M protocol. P u t t i n g the delay-throughput characteristics (from the n u m e r i c a l results) i n F i g ure 2.10 a n d F i g u r e 2.11 i n another form, we have F i g u r e 2.12 a n d F i g u r e 2.13. T h e y show the d a t a delay versus the fraction of d a t a load at constant channel throughput (sum of the throughputs of voice and data) for the two sets of parameters. T h e r e are some interesting points noted on these curves. W e see from F i g u r e 2.12 that the d a t a delay is reduced as the fraction of d a t a load increases.

This

is because i f the fraction of the load generated b y voice sources decreases (or the fraction of d a t a load increases), the number of sources w h i c h have a higher p r i o r i t y of transmission t h a n d a t a sources decreases. A s a result, the delay experienced b y d a t a sources decreases. In F i g u r e 2.13, the d a t a delay also shows the same characteristic at low channel throughput, but the decrease is c o m p a r a t i v e l y smaller. A s the channel throughput becomes rather high, it changes from decrease to increase. T h e reason for this is that w h e n the load of channel traffic is heavy a n d collisions of d a t a packets waste a significant p o r t i o n of the channel capacity (the collision recovery t i m e is 1/10 of the packet transmission t i m e i n F i g u r e 2.13 whereas i t is only 3/80 i n F i g u r e 2.12), the increase i n the number of d a t a collisions counteracts the effect of h a v i n g fewer number of voice sources as the fraction of d a t a load i n creases. Therefore, the increase i n the d a t a delay is a result of the increased-channel contention.

CHAPTER

2.

PERFORMANCE

ANALYSIS

OF CSMA/CD

AND MSTDM

35

Figure 2.12: Data delay versus fraction of data load for M S T D M ( a = 0.0125, fc = 3).

CHAPTER

2.

PERFORMANCE

ANALYSIS

OF CSMA/CD

AND

MSTDM

F i g u r e 2.13: D a t a delay versus fraction of d a t a load for M S T D M (a = 0.05, A; =

CHAPTER 2. PERFORMANCE ANALYSIS OF CSMA/CD AND MSTDM

2.3

37

Summary

We have proposed a non-preemptive p r i o r i t y queueing m o d e l for evaluating the m e a n delay-throughput performance of the slotted non-persistent C S M A / C D protocol. T h i s a n a l y t i c a l approach has also served as a stepping stone for formulating a similar approximate model for the M S T D M protocol. T h e analysis here is the first piece of w o r k done o n the data delay performance of M S T D M a n d yields explicit results for the mean data delay-throughput characteristics. F o r each analysis of the two protocols, numerical results have been presented a n d discussed. A s comparisons w i t h s i m u l a t i o n results show, the accuracy of the analysis is h i g h although it is based on a simple approximate model.

Chapter 3 Simulation of MSTDM The analysis in the previous chapter provides a method for evaluating the mean delay-throughput performance of data packets for M S T D M . However, it does not give the higher moments of data delay as well as any information on voice delay characteristics. To gain a deeper understanding on the characteristics of M S T D M , simulation was done extensively to evaluate the delay performance of voice and data for this protocol. In this chapter, we first present the simulation model for the M S T D M protocol which is described in Section 2.2.1. Then we show the simulation results and discuss the delay characteristics of both voice and data. Moreover, we find that if we give the first voice packet generated at the beginning of a talkspurt a shorter retransmission delay than data packet, we can considerably reduce the channel-acquisition delay for voice sources without sacrificing the data delay performance significantly.

38

CHAPTER

3.1

3. SIMULATION OF MSTDM

39

Description of the Simulation Model

In our s i m u l a t i o n m o d e l for the M S T D M protocol, we assume there is a n infinite p o p u l a t i o n of d a t a sources w h i c h collectively form a n independent Poisson source. T h e number of voice sources is, on the other hand, finite and we assume all of t h e m are engaged i n t a l k i n g activities. B y v a r y i n g the number of voice sources i n the M S T D M simulator, we can change the level of the throughput of voice packets . 1

T h e durations of the talkspurt and the silent period are assumed to be exponentially distributed [27] w i t h means 1 sec and 1.4 sec respectively. T h e period of transmission for voice sources is 28 msec. Therefore, first voice packets contribute to 2.8% of the total number of packets generated by voice sources. T h e coding rate for speech is 64 K b p s . T h u s , the number of voice bits w h i c h arrive i n 28 msec is 1792. T h i s is the size of the d a t a area of voice packet. Including the space required for preempt area, packet header and overflow area, we let the voice packet length be 2000 bits. T h e channel transmission rate i n our system is assumed to be 10 M b p s a n d so the transmission time of a voice packet is 200 /zsec. T h e number of voice bits w h i c h arrive i n the interval of one voice packet transmission time is 12.8 bits. T h e size of the overflow area is, therefore, 13 bits. In this s i m u l a t i o n , we assume d a t a packets have a fixed length w h i c h is the same as that of first voice packets and voice packets.

A s the slotted M S T D M protocol is considered here, we assume the time axis is d i v i d e d into slots. T h e size of a slot is equal to the end-to-end channel propagation If we set the number of voice sources to be zero, the M S T D M simulator will become a C S M A / C D one. We do this to run simulation for the C S M A / C D protocol. The results obtained are used for verifying the analytical results in Section 2.1.4 1

CHAPTER

3.

SIMULATION

OF

40

MSTDM

delay. Since transmission c a n only be started at the beginning of a slot, the packet transmission t i m e is assumed to be a m u l t i p l e number of slots i n our simulator.

MSTDM

Because of the effect of signal propagation, the channel w i l l not be

sensed idle right after a packet has been completely transmitted.

W e assume it

takes the t i m e of one slot to have this effect removed from the channel for each packet transmission. Moreover, when data packets a n d / o r first voice packets have a collision, the t i m e t h a t it takes for the channel to recover from busy state to idle state is a m u l t i p l e number of slots. There are two parameters that specify the simulated system. T h e first is the normalized end-to-end channel propagation delay (a) w h i c h is defined as the quotient of the end-to-end channel propagation delay divided b y the packet transmission time. A n o t h e r parameter is the normalized collision recovery time w h i c h is given by kct, where A; is the number of slots required to recover from a collision. A s data packets a n d first voice packets m a y experience collision i n the vulnerable interval, they have to be retransmitted according to a retry scheme. In our s i m u l a t i o n studies, we have attempted to apply the same as well as different retry schemes to data packets a n d first voice packets.

In the first case, we use the binary exponential backoff ( B E B ) a l g o r i t h m to schedule retransmission for b o t h of them. In our B E B , if a packet has just experienced its C t h collision, it w i l l be t r a n s m i t t e d at the point R slots from the time the source senses the channel idle, where R is picked up uniformly from the interval {0, 2' — 1 } slots a n d i=rmn{C,

8 } . If the channel is busy at the t i m e of retransmis-

sion, the rescheduling procedure above w i l l be repeated at the same interval for the selection of retransmission time. Note that i f a packet has suffered eight collisions or

CHAPTER

3.

SIMULATION

OF

41

MSTDM

more, the retransmission interval w i l l still r e m a i n at 255 slots u n t i l it is successfully transmitted. In the second case, we use the B E B a l g o r i t h m for d a t a packets a n d the linear incremental backoff ( L I B ) a l g o r i t h m [28] for first voice packets. L I B implies that the retransmission time is picked up uniformly from the interval {0,

C} slots,

where C is the number of collisions a packet has suffered. F o r other details, L I B is the same as B E B . B u t we do not put a n upper l i m i t on the retransmission interval for L I B . W e notice t h a t the retransmission delay i n L I B should be m u c h shorter t h a n that i n B E B on the average.

T h e M S T D M simulator is implemented i n the high-level language ' C . O u r prime objective of r u n n i n g the simulator is to evaluate the delay performances of the three types of packets. W e have r u n the simulator for two pairs of system parameters.

The

first pair are a = 0.0125 a n d k = 3 whereas another pair are a = 0.05 and k = 2. If the speed of signal propagation i n the channel is assumed to be t w o - t h i r d of that of light, the first a implies a slot size of 2.5 jusec w h i c h corresponds to a channel length of 500 m a n d the other is 10 fisec, a channel length of 2 K m . F o r each of the two simulated systems, we have applied the same as well as different retry schemes to d a t a packets a n d first voice packets as described above. B y c o m p a r i n g these two cases of retransmission scheduling, we can find out the effects on the delays of first voice packets a n d d a t a packets i f the former is given a shorter retransmission delay t h a n the latter.

A time span of about five minutes i n the real M S T D M system is simulated for each r u n . We believe that this is sufficient for obtaining reasonable statistical results

CHAPTER

3.

SIMULATION

OF

42

MSTDM

for our performance evaluation. T h e s i m u l a t i o n results obtained verify this c l a i m as they show definite trends consistently.

3.2

Simulation Results and Discussions

In the following, when data packets and first voice packets adopt the B E B a l g o r i t h m for retransmission, the w o r d ' d a t a ' is used to include b o t h of them. T h i s is because if the former a n d the latter have the same retransmission delay d i s t r i b u t i o n , they w i l l behave w i t h o u t any difference from each other i n the system. However, when d a t a packets use B E B a n d first voice packets use L I B , we have to m e n t i o n t h e m distinctly. In the s i m u l a t i o n , the delay performances of the three types of packets were respectively obtained i n terms of the mean and the standard d e v i a t i o n of their delay. T h e packet delay i n the following figures is i n the unit of packet transmission t i m e and the throughput is i n the unit of packet per packet transmission time.

F i g u r e 3.1 t h r o u g h F i g u r e 3.4 show the s i m u l a t i o n results for the two sets of system parameters w h e n b o t h data packets a n d first voice packets use the B E B a l g o r i t h m . T h e mean a n d the standard deviation of packet delay versus the data throughput are plotted at constant voice throughput (p ) for data packets a n d voice v

packets i n each simulated s y s t e m . 2

F r o m F i g u r e 3.1 and F i g u r e 3.3, we see that the data delay performance declines apparently w h e n the voice throughput p i n the channel increases. T h i s is obvious v

because voice packets occupy part of the channel capacity for transmission and The mean data delay of the simulation results obtained in this case has been used to verify the analysis on the performance of M S T D M in Chapter 2. 2

CHAPTER

3.

SIMULATION

OF

43

MSTDM

1

1

1

1

'

TJ

s

a •a c

• = p- 0.000 o = p- 0.044 " = p- 0.147 • = p - 0.293 x =p- 0.437 o = p- 0.585 » = £ - 0.738 0.4

0.9

0.8

Data throughput

(a) M e a n d a t a delay

04

0.5

o.e

Data throughput

(b) S t a n d a r d d e v i a t i o n of d a t a delay

F i g u r e 3.1: Delay characteristics of d a t a packets w h e n b o t h first voice packets and d a t a packets use B E B for retransmission ( a = 0.0125, k = 3)

CHAPTER

3. SIMULATION

OF

MSTDM

0.4

0.5

44

00

Data throughput

(a) M e a n voice delay

So

>2 •O

rt •O 2

2 tn

a o A • x o

0.4

05

= p= p= p=p= p= p-

0.044 0.147 0.293 0.437 0.585 0.738

0.6

Data throughput

(b) S t a n d a r d deviation of voice delay

F i g u r e 3.2: D e l a y characteristics of voice packets w h e n b o t h first voice packets and d a t a packets use B E B for retransmission ( a = 0.0125, k = 3)

CHAPTER

3.

SIMULATION

OF

45

MSTDM

0.4

0.5

0.6

Data throughput

(a) M e a n d a t a delay

4) T3„

•o C

D = p- 0.000 ° = p- 0.045 a = p - 0.146 * = p - 0.293 « = p - 0.439 • = p - 0.586 0.4

0.3

0.6

Data throughput

(b) S t a n d a r d deviation of d a t a delay

F i g u r e 3.3: D e l a y characteristics of d a t a packets when b o t h first voice packets and d a t a packets use B E B for retransmission (a = 0.05, k = 2)

CHAPTER

3.

SIMULATION

OF

46

MSTDM

o = p - 0.045 o = p - 0.146 A = p - 0.292 • = p - 0.439 * = p - 0.586 0.3

0.4

0.5

0.6

Data throughput

0.7

(a) M e a n voice delay

•a 6

a

•a • • = po = p4 =p* =p»= p0.4

05

0.045 0.146 0.292 0.439 0.586

0.8

Data throughput

(b) S t a n d a r d deviation of voice delay

F i g u r e 3.4: D e l a y characteristics of voice packets w h e n b o t h first voice packets and d a t a packets use B E B for retransmission ( a = 0.05, k = 2)

CHAPTER

3.

SIMULATION

OF

47

MSTDM

have a higher p r i o r i t y of transmission t h a n d a t a packets.

W i t h a higher voice

t h r o u g h p u t , the m a x i m u m of the data throughput that can be achieved is reduced relatively. F r o m light to m e d i u m load of d a t a traffic (relative to the m a x i m u m d a t a throughput achievable), the mean and the standard d e v i a t i o n of d a t a delay are quite small except at heavy load of voice traffic. However, they increases r a p i d l y w h e n the d a t a throughput is high. T h i s is a well-known characteristic for the performance of d a t a packets using r a n d o m access protocol for transmission. C o m p a r i n g the curves i n F i g u r e 3.1 and F i g u r e 3.3, we find that the delay performance is better for a = 0.0125 a n d k = 3 t h a n for a = 0.05 and k = 2. T h i s is because collisions of d a t a packets a n d removals of signal propagation after packet transmissions waste a more significant p o r t i o n of the channel capacity i n the latter case. N o t e that w h e n the voice throughput is zero, the curves i n F i g u r e 3.1 a n d F i g u r e 3.3 show the d a t a delay performance of the slotted non-persistent C S M A / C D protocol.

I n F i g u r e 3.2 a n d F i g u r e 3.4, we show the voice delay performance. W e see that the m e a n delay of voice packets increases almost linearly w i t h the d a t a throughput w h e n we keep the voice throughput constant.

A t the same channel throughput

(sum of the throughputs of voice a n d data), the voice delay is m u c h smaller w h e n the channel is d o m i n a t e d b y voice load t h a n by d a t a load.

T h e reason is that

voice packet transmissions do not interfere w i t h each other as they are periodic a n d separable.

O n the other h a n d , d a t a packet transmissions are bursty a n d so

they m a y interfere w i t h the periodic transmissions of voice sources. Therefore, the overflow area i n voice packets is more utilized w h e n the d a t a throughput becomes higher. Y e t we observe from the results that the mean w a i t i n g time of voice packets

CHAPTER

3.

SIMULATION

OF

MSTDM

48

is well below one packet transmission time i n a l l cases of our simulation. F o r the standard d e v i a t i o n of voice delay, we find that it increases r a p i d l y w i t h the data throughput at the beginning, b u t its characteristics become leveled or even d r o p p i n g slightly at high d a t a throughput. T h i s is i n sharp contrast to the standard deviation characteristics of d a t a delay. It is because d a t a delay is unbounded while there is a n upper l i m i t of one packet transmission time on voice packet w a i t i n g time.

W h e n B E B is used for d a t a packets and L I B for first voice packets, the simulation results for the two sets of system parameters are shown from F i g u r e 3.5 to F i g u r e 3.10. In this case, we have separate figures for d a t a packets, first voice packets a n d voice packets. T h e characteristics of the packet delay versus the throughput of d a t a plus first voice packets are plotted. C o m p a r i n g the curves i n F i g u r e 3.5 and F i g u r e 3.8 w i t h the ones i n F i g u r e 3.1 and F i g u r e 3.3, we see that the d a t a delay performance is nearly unaffected w h e n first voice packets are given a shorter retransmission delay t h a n d a t a packets, except at very high voice throughput. T h e reason for this is that the load of first voice packets is light i n the channel as there is only one first voice packet i n each talkspurt. T h e y represent 2.8% of the t o t a l number of packets generated by voice sources i n the simulation. Therefore, as comparison w i t h the previous case shows, giving first voice packets a faster retransmission does not deteriorate the d a t a delay performance significantly unless the channel is highly utilized by voice sources, i.e. the s i t u a t i o n where the channel is congested and the load of first voice packets is larger t h a n or comparable to that of d a t a packets.

However, by doing so, we can improve the delay performance of first voice pack-

CHAPTER

3.

SIMULATION

OF

49

MSTDM

-fcs.

•e e

02

0.3

0.4

05

0.6

D = po = po = p• = p* = po = p" = p-

0.000 0.045 0.147 0.293 0.439 0.583 0.734

p-

0.000 0.045 0.147 0.293 0.439 0.583 0.734

0.7

Throughput of data plus first voice packets

(a) M e a n delay of d a t a packets

a

5 •o

>*3.

•a •o u

«B TJ

C

5

03

0.4

05

0.S

07

Throughput of data plus first voice packets

(b) S t a n d a r d d e v i a t i o n of d a t a packet delay

F i g u r e 3.5: Delay characteristics of d a t a packets w h e n first voice packets use L I B and d a t a packets use B E B for retransmission ( a = 0.0125, k = 3)

CHAPTER

3.

SIMULATION

OF

MSTDM

50

(b) S t a n d a r d deviation of first voice packet delay

F i g u r e 3.6: D e l a y characteristics of first voice packets when first voice packets use L I B a n d d a t a packets use B E B for retransmission (a = 0.0125, k = 3)

CHAPTER

3. SIMULATION OF MSTDM

51

>

o = p - 0.045 o = p - 0.147 a = p- 0.293 • = p - 0.439 « = p- 0.583 o = p- 0.734 2

0.3

0.4

0.3

0.6

07

Throughput of data plus first voice packets

(a) M e a n delay of voice packets

•v

T3

• = p- 0.045 o = p - 0.147 « = p - 0.293 * = p - 0.439 x = p - 0.583 « = p - 0.734

c

0.3

0.4

0.3

0.6

0.7

Throughput of data plus first voice packets oo

(b) Standard deviation of voice packet delay

F i g u r e 3.7: Delay characteristics of voice packets when first voice packets use L I B a n d data packets use B E B for retransmission ( a = 0.0125, k = 3)

52

CHAPTER 3. SIMULATION OF MSTDM

•

•o e

• = p- o.ooo

o = p- 0.044 4 =p0.147 * = p- 0.292 « = p- 0.444 o = p- 0.586 2

0.3

0.4

0.3

0.8

07

Throughput of data plus first voice packets

(a) M e a n delay of d a t a packets

o c o

*3 (d

Pb. T)

TJ fc. •O

Us•v c S

a = p- 0.044 o = p - 0.147 » = p - 0.292 • = p - 0.444 x = p - 0.586

tn a

0.3

0.4

OS

0.8

0.7

Throughput of data plus first voice packets

(b) S t a n d a r d deviation of voice packet delay F i g u r e 3.10: D e l a y characteristics of voice packets w h e n first voice packets use L I B and d a t a packets use B E B for retransmission ( a = 0.05, k = 2)

CHAPTER

3.

SIMULATION

OF

MSTDM

55

ets considerably. T h i s can be seen by comparing F i g u r e 3.6 and F i g u r e 3.9 w i t h F i g u r e 3.1 and F i g u r e 3.3. N o t e that the d a t a delay i n F i g u r e 3.1 and F i g u r e 3.3 also refers to the delay of first voice packets as mentioned at the beginning of this section.

T h e comparisons show that the delay of first voice packets grows more

slowly and more steadily w i t h the increase of d a t a load i n the channel w h e n they have a shorter retransmission delay t h a n d a t a packets. Therefore, although b o t h first voice packets and d a t a packets use C S M A / C D , the former can be transmitted i n a shorter time t h a n the latter on the average. T h i s gain is more remarkable when d a t a load occupies a considerable p o r t i o n of the channel capacity.

We k n o w from the protocol description that the first voice packet needs to be t r a n s m i t t e d w i t h i n one period of voice transmission if the speech at the beginning of a talkspurt is not to be c l i p p e d . In our M S T D M simulator, the packet transmission time is 200 /^sec (at a channel transmission rate of 10 M b p s ) and the p e r i o d of voice transmission is 28 msec.

F r o m the simulation results, we see that the first voice

packet delay is just i n the order of millisecond even at h i g h channel throughput w h e n b o t h d a t a packets and first voice packets adopt the B E B a l g o r i t h m for retransmission. T h i s delay should be well below 28 msec most of the time. Therefore, it may not be needed to give a faster retransmission for first voice packets although it can still help m i n i m i z e the chance of voice bits being discarded w i t h o u t affecting the d a t a delay performance significantly.

However, i f the channel transmission rate is lowered to 1 M b p s , the packet transmission time w i l l become 2 msec. T h e n the first voice packet delay just mentioned above w i l l correspondingly increase b y 10 times going from the order of millisecond to ten milliseconds. B u t it can be considerably decreased if first voice packets use

CHAPTER

3.

SIMULATION

OF

MSTDM

56

L I B a n d d a t a packets use B E B . In this case, it is, therefore, very favourable to have a shorter retransmission delay for first voice packets i n order to reduce the channel-acquisition time for voice sources. T h i s can prevent the speech from being clipped w i t h only little adverse effect on the d a t a delay performance. F i n a l l y , we notice that the delay characteristics of voice packets i n F i g u r e 3.7 a n d F i g u r e 3.10 are almost identical to the ones i n F i g u r e 3.2 and F i g u r e 3.4. T h i s shows that their performance remains unchanged no matter first voice packets and d a t a packets have the same or different retry schemes.

3.3

Summary

W e have presented the performance evaluation of the M S T D M p r o t o c o l using s i m u l a t i o n . T h e effects of this protocol on the delay performances of d a t a packets, first voice packets a n d subsequent voice packets have been shown and discussed respectively i n terms of the mean a n d the standard d e v i a t i o n of their delay. Moreover, we find that i f first voice packets are given a shorter retransmission delay t h a n d a t a packets, the channel-acquisition delay for voice sources can be considerably reduced w i t h o u t sacrificing the d a t a delay performance significantly.

Chapter 4 M S T D M Network for a Metropolitan Area

The

M S T D M protocol supports b o t h voice a n d data traffic i n a local area net-

work.

However, its efficiency decreases inversely w i t h the transmission rate and

the channel length because of its bus contention nature. In this chapter, a scheme w h i c h alleviates the distance and transmission rate constraints associated w i t h this protocol is introduced [16]. T h e approach is to divide a network spanning a large area into a number of sub-networks called homenets, for i m p r o v i n g the M S T D M protocol efficiency. T h e n we propose a n access protocol for the interconnection of homenets. It facilitates the communications between stations i n different homenets for b o t h voice a n d d a t a services. F i n a l l y , we find the o p t i m u m number of homenets, i n t o w h i c h a large area should be partitioned, to m i n i m i z e the mean delay of data packets w i t h i n homenet.

57

CHAPTER 4. MSTDM NETWORK FOR A METROPOLITAN

4.1

AREA

58

Homenet Network

A s we see i n the previous two chapters, the performance of the M S T D M protocol deteriorates w i t h the increase of a w h i c h is defined as the ratio of the end-to-end channel propagation delay to the packet transmission time. T h e protocol does not even work i f cc is greater t h a n one. These characteristics are, i n general, v a l i d for any bus contention protocol w i t h carrier sensing property [13]. In a n M S T D M system, the preempt area of voice packets does not carry any information. Its length depends on the m a x i m u m time that it takes for data sources a n d voice sources t r a n s m i t t i n g first voice packets to recover from a collision. Since the m a x i m u m collision recovery time increases w i t h the end-to-end propagation delay, the fraction of the voice packet, w h i c h carries useful data, is small when a is large. A s a result, the efficiency of the M S T D M protocol w i l l be low if it is directly applied to a network w h i c h spans a large area a n d has a h i g h transmission rate.

In order to solve this problem, we have to alleviate the distance and transmission rate constraints associated w i t h the M S T D M protocol. T h e homenet approach presented here is to divide the stations i n a network covering a large area, for example a m e t r o p o l i t a n area, into regional groups so that the end-to-end channel propagation delay applied to each region is reduced [16] [29] [30].

T h e communications channel

w i t h a h i g h t o t a l b i t rate is also d i v i d e d , a n d a fraction of the capacity is assigned to each regional group. Stations i n a region only transmit i n the fraction of the capacity assigned to their group. T h i s decreases the transmission rate of the stations, compared w i t h the case when the t o t a l channel capacity is available to them. T h e overall effect is that the ratio of the end-to-end channel propagation delay i n each

CHAPTER

4.

MSTDM

NETWORK

FOR A METROPOLITAN

AREA

59

region to the packet transmission time is considerably decreased. E a c h group forms a local area network called homenet, using the M S T D M protocol. T h e p h y s i c a l m e d i u m can be a conventional subsplit cable system, for example a C A T V network w h i c h can be found under the ground of m a n y m e t r o p o l i t a n areas [31].

T h e transmission of signal is uni-directional i n broadband. F i g u r e 4.1 shows

a network w i t h three homenets on a subsplit cable system. T h e stations i n each homenet t r a n s m i t i n frequency b a n d / point i n each homenet.

0

i n upstream.

There is a local reflection

A t the reflection point, the upstream frequency b a n d /

0

is prevented from propagating to adjacent homenet by means of notch filter. It is also translated into the downstream frequency band / „ i n homenet n, where n is a n index for one of the homenets i n the network. E a c h station has one frequency agile receiver (or more). T h e stations i n homenet n receive packets for communications w i t h i n homenet by listening to / „ , w h i c h is their homenet frequency. Usually, a stat i o n listens to its homenet frequency a l l the time unless it is informed to s w i t c h to another frequency. Moreover, the upstream frequency b a n d fo is translated i n t o frequency b a n d / # „ at the reflection point of homenet n, and f

Dn

propagates towards

the head end of the whole network, w h i c h is the root of a subsplit cable system. A t the head e n d , / p 1

n

is converted to f

n

w h i c h is carried throughout the network,

Besides the frequency translation operations, a variety of user services can be incorporated in the head end. Analog video can be broadcasted from the head end to every station in the network in a different frequency band like a C A T V system. A head-end station identical to the ones used at the user nodes can be implemented to perform the functions of an interactive data base providing different kinds of information to its customers. Another head-end station can act as a switching processor for establishing voice links with sources outside the network. A user sends a data packet to this processor giving the number to be called. It then processes the call and connects the user's voice path to the outside line. Similarly, a station at the head end can function as a gate-way which is responsible for data communications with the outside networks. If necessary, the stations providing services at the head end can have receivers listening to all homenet frequencies at the same time and can form a homenet of their own. 1

C H A P T E R 4.

M S T D M

N E T W O R K F O R A M E T R O P O L I T A N

A R E A

two N o t c h filter bands / o a n d f$

O

local reflection point

^

head end

F i g u r e 4.1: Homenet network on a subsplit cable system.

60

CHAPTER

4. MSTDM

NETWORK

except homenet n where the f

n

FOR A METROPOLITAN

AREA

61

transmitted f r o m the head end is notch filtered at

the reflection point to prevent collision with the /„ localized within homenet n.

T h r o u g h this configuration, the connectivity between stations in the network is complete. Once a packet has been successfully transmitted in a homenet, it c a n be received anywhere in the whole network. In this way, a station i n homenet k, for example, c a n receive packets sent from homenet / by listening to frequency b a n d fi, instead of its homenet frequency. Therefore, the link for inter-homenet packet transfer is set up. T h i s homenet approach restricts the contention for channel acquisition to be localized among stations within homenet, no matter the transmission is for intra- or inter-homenet packet transfer. T h e result is a significant improvement in protocol efficiency.

4.2 A

Description of the Access Protocol

station has to know to which frequency it should listen for getting a n inter-

homenet packet addressd to it. In this section, we propose a n access protocol for inter-homenet communications.

T h i s access protocol makes use of a monitor which

is implemented i n each homenet and basically performs the function of a store-andforward node.

4.2.1

Interconnection

T h e monitor i n each homenet has receivers listening to all homenet frequencies at the same time. It accepts those packets which are sent from other homenets to the

CHAPTER

4.

MSTDM

NETWORK

FOR A METROPOLITAN

monitor M

s t a t i o n A\

62

AREA

station B

2

2

homenet 2

homenet 1

F i g u r e 4.2: Inter-homenet packet transfer of bursty data.

stations i n its homenet. It keeps the packets unchanged a n d delivers t h e m to their destinations as a store-and-forward node. F o r example, station A\ i n homenet 1 wants to send a d a t a packet to station B

2

i n homenet 2. W h e n the transmission is successful, the m o n i t o r (M ) i n homenet 2 2

detects this packet i n frequency b a n d fy. Recognizing the destination address belongs to one of the stations w i t h i n its homenet, M i n the buffer. T h e n M

2

2

receives the packet and stores it

transmits the packet to B

following the M S T D M protocol

2

i n the same way as other stations i n homenet 2. F i n a l l y B

2

receives the packet i n

frequency b a n d / , its homenet frequency. T h e operation of this packet transfer is 2

depicted i n F i g u r e 4.2.

T h i s access protocol is suitable for handling bursty d a t a traffic for inter-homenet communications. Y e t , for voice packet transmission, we can eliminate the m o n i t o r

CHAPTER

4. MSTDM

NETWORK

FOR A METROPOLITAN

from being involved after the i n i t i a l set-up as shown i n F i g u r e 4.3. communications between Ai a n d B

2

a conversation w i t h B . 2

So A\ sends a call-connection request packet to B . 2

2

2

W e use the

as an example again. N o w A\ wants to have

packet is carried through the network to B ing B

63

AREA

This

b y the method just mentioned. A s s u m -

accepts the connection, it sends a call-confirmation packet back to Ai a n d

its receiver is switched to listen to fi. After receiving the confirmation, Ai switches to listen to

f. 2

N o w Ai a n d B

2

receive voice packets i n another's homenet frequency as if they

were resided i n another's homenet . T h r o u g h the setting of an i n d i c a t i o n b i t i n the 2

packet header, the monitors i n b o t h homenet 1 and homenet 2 k n o w that the packets sending between Ai a n d B

2

are received by t h e m directly. Therefore, the monitors

do not accept these packets. T h e connection remains throughout the conversation u n t i l one side disconnects the link by a clear-connection request. T h e n Ai a n d B r e t u r n to their homenet frequencies.

2

I n this way, no a d d i t i o n a l delay is created

on top of that due to the M S T D M protocol for voice packet transmission. T h u s , M S T D M works well even for inter-homenet voice traffic. T h i s k i n d of connection between stations i n different homenets is also suitable for long file transfer, w h i c h can avoid the extra d a t a delay caused when the m o n i t o r is involved for every single packet transfer. However, the connection is likely to be one-way i n this case. If a station wants to have additional connections simultaneously, it has to be equipped w i t h more t h a n one receiver. If Ai wants to talk to somebody outside the network, B will be one of the functional units of the head-end switching processor described before. These functional units are switching nodes which process the calls and connect the users' voice paths to the outside lines. In this example, the .outgoing signal from Ai is carried in frequency band fi to the switching node B , and the incoming signal from the outside world is transmitted from B to Ai in frequency band f - At the initial set-up, the number to be called is included in .Ai's call-connection request packet. 2

2

2

2

2

CHAPTER

4. MSTDM

NETWORK

FOR A METROPOLITAN

AREA

64

fi

homenet 1

homenet 2

(a) Call-connection request

B

Mi

2

0, a n d

rci+U

=

Ki+1,2

=

nn

— 1 +

i2

+

n

ai 2

an

•

(A.l)

T h e (i + l ) s t departure epoch is class 2 for rc,- > 0 when the i t h departure leaves 2

77

APPENDIX

78

A.

the system devoid of class 1 packet. Then

».-+i,2

=

n

- 1+ o

i2

22

(A.2)

•

When the ith departure leaves the system empty, with probability A i / A ,

^.+1,2

=

«21

( - ) A

3

where A = Ai + A , and with probability A / A , 2

2

rc.-+i,2 =

«22 •

(A.4)

Define p = Aim"i + A m . 2

(A-5)

2

Then for the following 3 disjoint events in the queue dynamics, we have Prob [na = 0 and n

= 0] = 1 —"p= P

i2

Prob [ n > 0] = A ^ / A = P a

Prob [n = 0 and n tl

0

x

> 0] = A ^ / A = P .

i2

2

2

(A.6)

Conditioning on the 3 events to calculate the two-dimensional probability generating functions of

and n,+i , we have |2

E[Z ' ' Z "''+ ' ] = n,

+1

1

1

1

2

2

P { (A /A)E[Z 0

1

a i l 1

( A / A ) E [Z?*Z?*\n 2

Z ° |n = n 2 1

2

ix

t l

i2

= 0] +

= n,- = 0] } + 2

APPENDIX

79

A.

P E[Z 1

n 1

'

1 _ 1 + a i l

Z "'

2 + a 2 1

2

P E [Z^ Z? ~ \n i2

1+a22

2

a

|n

a

> 0] +

= 0, n

S o l v i n g (A.7) b y differentiating w.r.t. Z\ a n d Z

2i

i2

> 0] .

(A.7)

a n d after some manipulations,

we o b t a i n —

,

+ Am ] 2 p ( l — Aimi)(l — Aimi — A m ) 2

X [\im\ 2

2

2

2

where n

2 2

2

is the mean number of class 2 packets i n the system given that one

of t h e m is beginning transmission.

T h e average number of class 2 packets w h i c h

arrive d u r i n g the w a i t i n g time of the one being t r a n s m i t t e d is n

2 2

— 1. Since packets

a r r i v i n g to a n empty system suffer no queueing delay, the mean w a i t i n g time (W ) 2

of class 2 packets is given b y

W

2

= (p/A )(n 2

22

- 1)

by Little's Formula.

S u b s t i t u t i n g (A.8) into ( A . 9 ) , we o b t a i n

W = 2

_AimT+A mf ^_ 2(1 — A m )(l — Ximi — A m ) 2

1

w h i c h is (2.1).

1

2

2

(A.9)

Appendix B B.l

Tables of the C S M A / C D Simulation Results

Table B . l : 95% Confidence intervals for the C S M A / C D s i m u l a t i o n results shown i n F i g u r e 2.3 (k = 2). (a) a = 0.001 (b) a = 0.01 (c) a = 0.05 (d) a = 0.1 (e) a = 0.2

D a t a throughput 0.010 0.101 0.201 0.300 0.401 0.500 0.603 0.702 0.801 0.851 0.900 0.911 0.921 0.928

M e a n d a t a delay 1.005 1.059 1.128 1.214 1.340 1.496 1.767 2.195 3.067 3.896 5.588 6.314 7.259 7.872

95% Confidence interval (1.004, 1.007) (1.057, 1.061) (1.124, 1.131) (1.210, 1.218) (1.331, 1.349) (1.480, 1.512) (1.746, 1.788) (2.149, 2.241) (3.021, 3.112) (3.742, 4.049) (5.388, 5.789) (5.901, 6.727) (6.868, 7.650) (7.249, 8.495)

B . l (a)

80

Analytical mean 1.006 1.057 1.127 1.216 1.337 1.505 1.768 2.197 3.062 3.934 5.719 6.410 7.206 7.896

APPENDIX

B.

D a t a throughput 0.010 0.100 0.301 0.501 0.702 0.801 0.840 0.862 0.877 0.899

81

M e a n d a t a delay 1.009 1.064 1.231 1.553 2.404 3.620 4.714 5.575 6.505 9.158

95% Confidence interval (1.009, 1.010) (1.062, 1.066) (1.226, 1.237) (1.545, 1.561) (2.367, 2.442) (3.547, 3.692) (4.392, 5.036) (5.316, 5.834) (6.172, 6.837) (8.643, 9.673)

A n a l y t i c a l mean 1.010 1.062 1.231 1.551 2.381 3.574 4.588 5.552 6.512 8.800

B . l (b)

D a t a throughput 0.010 0.100 0.300 0.400 0.501 0.599 0.701 0.757

M e a n data delay 1.030 1.093 1.313 1.512 1.838 2.477 4.214 7.512

95% Confidence interval (1.029, 1.030) (1.091, 1.096) (1.303, 1.322) (1.507, 1.518) (1.816, 1.860) (2.428, 2.526) (4.024, 4.403) (7.155, 7.870)

B . l (c)

A n a l y t i c a l mean 1.031 1.090 1.305 1.495 1.817 2.420 4.136 7.493

APPENDIX

B.

D a t a throughput 0.010 0.100 0.300 0.400 0.502 0.550 0.570 0.580 0.601 0.605 0.614 0.626

82

M e a n data delay 1.055 1.133 1.445 1.799 2.503 3.303 3.682 4.104 4.828 5.139 5.589 6.460

95% Confidence interval (1.053, 1.057) (1.130, 1.137) (1.431, 1.459) (1.776, 1.823) (2.451, 2.556) (3.196, 3.410) (3.544, 3.821) (3.937, 4.271) (4.700, 4.956) (4.804, 5.473) (5.394, 5.785) (6.012, 6.908)

A n a l y t i c a l mean 1.057 1.128 1.428 1.753 2.461 3.150 3.612 3.908 4.706 4.904 5.424 6.358

B . l (d)

D a t a throughput 0.010 0.100 0.198 0.300 0.400 0.421 0.440 0.461 0.470 0.480

M e a n data delay 1.108 1.227 1.442 1.877 3.061 3.592 4.369 5.800 6.577 7.735

95% Confidence interval (1.105, 1.110) (1.221, 1.233) (1.430, 1.455) (1.855, 1.900) (3.000, 3.123) (3.491, 3.694) (4.185, 4.553) (5.346, 6.253) (6.250, 6.903) (7.347, 8.123)

B . l (e)

A n a l y t i c a l mean 1.109 1.214 1.415 1.850 3.030 3.574 4.300 5.531 6.361 7.620

APPENDIX

B.2

B.

83

Tables of the M S T D M Simulation Results

Table B.2: 95% Confidence intervals for the M S T D M s i m u l a t i o n results shown i n

F i g u r e 2.10 (a = 0.0125, k = 3). (a)

p =0 v

(b) p = 0.044 (c) p = 0.147 (d) p„ = 0.293 (e) p = 0.437 (f) p„ = 0.585 (g) = 0.738 v

v

v

Pv

D a t a throughput

M e a n d a t a delay

0.010 0.100 0.301 0.501 0.698 0.801 0.850 0.867 0.878

1.011 1.066 1.238 1.586 2.534 4.160 6.034 7.578 9.300

95% Confidence interval

(1.010, 1.011) (1.064, 1.068) (1.233, 1.244) (1.579, 1.593) (2.480, 2.588) (4.017, 4.302) (5.799, 6.270) (7.334, 7.822) (8.367, 10.234)

A n a l y t i c a l mean

1.011 1.064 1.239 1.584 2.518 4.157 6.439 8.135 9.855

B.2 (a)

D a t a throughput

M e a n d a t a delay

0.011 0.101 0.301 0.501 0.701 0.801 0.821 0.831

1.039 1.101 1.308 1.738 3.055 5.785 7.617 8.861

95% Confidence interval

(1.036, (1.099, (1.303, (1.730, (2.999, (5.676, (7.376, (8.345,

B.2 (b)

1.041) 1.102) 1.314) 1.746) 3.112) 5.893) 7.859) 9.377)

A n a l y t i c a l mean

1.038 1.100 1.306 1.739 3.100 6.049 8.045 9.279

APPENDIX

B.

84

D a t a throughput

M e a n data delay

9 5 % Confidence interval

A n a l y t i c a l mean

0.014

1.121

(1.116, 1.126)

1.119

0.104

1.218

(1.214, 1.222)

1.210

0.205

1.353

(1.349, 1.357)

1.343

0.305

1.537

(1.531, 1.542)

1.529

0.405

1.829

(1.813, 1.844)

1.827

0.505

2.292

(2.267, 2.316)

2.309

0.603

3.236

(3.200, 3.271)

3.313

0.705

6.395

(6.079, 6.711)

6.742

0.724

8.574

(7.906, 9.243)

8.760

0.733

9.184

(8.734, 9.634)

9.781

B.2 ( ) C

D a t a throughput

M e a n data delay

9 5 % Confidence interval

A n a l y t i c a l mean

0.019

1.309

(1.301, 1.317)

1.316

0.108

1.486

(1.470, 1.502)

1.467

0.209

1.762

(1.740, 1.784)

1.740

0.309

2.156

(2.101, 2.211)

2.143

0.409

2.772

(2.750, 2.794)

2.829

0.507

4.445

(4.294, 4.595)

4.662

0.567

7.160

(6.811, 7.510)

7.372

0.579

8.693

(7.653, 9.733)

8.538

B.2 (d)

APPENDIX

B.

D a t a throughput 0.023 0.112 0.213 0.313 0.412 0.422

85

M e a n d a t a delay 1.681 2.039 2.524 3.637 6.988 8.414

95% Confidence interval (1.641, 1.721) (2.013, 2.065) (2.486, 2.562) (3.546, 3.727) (6.379, 7.597) (7.214, 9.614)

A n a l y t i c a l mean 1.658 1.985 2.528 3.713 6.956 7.931

B . 2 (e)

D a t a throughput 0.027 0.117 0.217 0.266 0.277

M e a n d a t a delay 2.530 3.211 5.116 7.357 8.553

95% Confidence interval (2.489, 2.571) (3.135, 3.285) (4.882, 5.349) (6.503, 8.210) (7.601, 9.506)

A n a l y t i c a l mean 2.404 3.126 5.229 7.151 8.102

B . 2 (f)

D a t a throughput 0.031 0.071 0.091

M e a n d a t a delay 4.937 5.647 7.209

95% Confidence interval (4.845, 5.029) (5.601, 6.023) (6.474, 7.944)

B-2 (g)

A n a l y t i c a l mean 4.503 5.367 6.303

APPENDIX

B.

86

Table B.3: 95% Confidence intervals for the M S T D M s i m u l a t i o n results shown i n F i g u r e 2.11 (a = 0.05, k = 2). (a) p = 0 v

(b) p = 0.045 (c) = 0.146 (d) p = 0.292 (e) p = 0.439 (f) p = 0.586 u

P v

v

v

v

D a t a throughput

M e a n data delay

0.010 0.100 0.300 0.400 0.501 0.599 0.701 0.757

1.030 1.093 1.313 1.512 1.838 2.477 4.214 7.512

95% Confidence interval

(1.029, (1.091, (1.303, (1.507, (1.816, (2.428, (4.024, (7.155,

1.030) 1.096) 1.322) 1.518) 1.860) 2.526) 4.403) 7.870)

A n a l y t i c a l mean

1.031 1.090 1.305 1.495 1.817 2.420 4.136 7.493

B.3 (a)

D a t a throughput

M e a n data delay

0.011 0.102 0.302 0.402 0.501 0.600 0.702 0.720

1.062 1.132 1.403 1.652 2.083 2.977 6.576 8.589

95% Confidence interval

(1.058, (1.131, (1.399, (1.645, (2.069, (2.967, (6.390, (8.197,

B.3 (b)

1.066) 1.132) 1.407) 1.659) 2.097) 2.988) 6.761) 8.982)

A n a l y t i c a l mean

1.059 1.129 1.391 1.633 2.053 2.930 6.317 8.219

APPENDIX

B.

D a t a throughput 0.014 0.104 0.204 0.305 0.404 0.505 0.603 0.624

87

M e a n d a t a delay 1.155 1.269 1.433 1.699 2.152 3.054

95% Confidence interval (1.147, 1.162) (1.260, 1.278) (1.426, 1.439) (1.681, 1.717) (2.131, 2.174) (3.007, 3.101)

A n a l y t i c a l mean 1.149 1.252 1.415 1.673 2.137 3.030

6.206 8.171

(5.979, 6.432) (7.965, 8.378)

6.234 8.030

95% Confidence interval (1.371, 1.420) (1.574, 1.631) (1.930, 1.982) (2.479, 2.546) (3.748, 3.978) (5.435, 6.237) (6.198, 7.081) (8.233, 9.670)

A n a l y t i c a l mean 1.373 1.559 1.912 2.529 3.912 5.738 6.884 9.064

B . 3 (c)

D a t a throughput 0.018 0.108 0.208 0.308 0.408 0.458 0.478 0.499

M e a n d a t a delay 1.395 1.602 1.956 2.513 3.863 5.836 6.640 8.952

B . 3 (d)

APPENDIX

B.

D a t a throughput 0.022 0.113 0.213 0.312 0.332 0.353

88

M e a n d a t a delay 1.824 2.304 3.123 5.336 6.447 7.957

95% Confidence interval (1.786, 1.863) (2.263, 2.346) (3.027, 3.218) (5.195, 5.478) (6.182, 6.712) (7.458, 8.456)

A n a l y t i c a l mean 1.747 2.193 3.085 5.571 6.589 7.922

B . 3 (e)

D a t a throughput 0.027 0.067 0.117 0.166 0.187 0.207

M e a n d a t a delay 2.897 3.353 4.102 5.231 6.368 7.247

95% Confidence interval (2.848, 2.945) (3.242, 3.464) (3.957, 4.248) (4.897, 5.565) (6.110, 6.625) (6.962, 7.533)

B . 3 (f)

A n a l y t i c a l mean 2.678 3.133 3.922 5.118 6.072 7.155

89

References

[1] J . F . Shoch, Y . K . D a l a i , D . D . Redell and R . C . C r a n e , " E v o l u t i o n of the E t h ernet local computer network," IEEE Comput., pp. 39-55, A u g . 1983. [2] D . D . C l a r k , K . T . P o g r a n , and D . P . Reed, " A n i n t r o d u c t i o n to local area networks," Proc. IEEE, v o l . 66, pp. 1497-1517, N o v . 1978. [3] A . H o p p e r , " D a t a ring at computer laboratory, U n i v e r s i t y of C a m b r i d g e , " i n Computer Science and Technology: Local Area Network. W a s h i n g t o n , D C : N a t . B u r . Stand., N B S Special P u b . 500-31, pp. 11-16, 1977. [4] R . C . D i x o n , N . C . Strole and J . D . M a r k o v , " A token-ring network for local d a t a communications," IBM Syst. J . , v o l . 22, pp. 47-62, 1983. [5] L . K l e i n r o c k and F . A . T o b a g i , "Packet switching i n radio channels: P a r t I — C a r r i e r sense multiple-access modes and their throughput-delay

characteris-

tics," IEEE Trans. Commun., v o l . C O M - 2 3 , pp. 1400-1416, Dec. 1975. [6] J . O . L i m b and C . Flores, " D e s c r i p t i o n of Fasnet — A unidirectional localarea communications network," Bell Syst. Tech. J., v o l . 61, pp. 1413-1440, Sept. 1982. [7] R . M . Metcalfe and D . R . Boggs, "Ethernet: D i s t r i b u t e d packet switching for local computer networks," Commun. Ass.

Comput. Mach., v o l . 19, pp. 3 9 5 -

404, J u l y 1976. [8] O . C . Ibe and D . T . G i b s o n , "Protocols for integrated voice and d a t a local area networks," IEEE Commun. Magazine, v o l . 24, pp. 30-36, J u l y 1986.

90

REFERENCES

[9] J . O . Limb and L . E . Flamm, "A distributed local area network packet protocol for combined voice and data transmission," IEEE J. Selected Areas Commun., vol. SAC-1, pp. 926-934, Nov. 1983. [10] R . K . Goel and A . K . Elkakeem, "A hybrid F A R A / C S M A - C D protocol for voice-data integration," Comput. Networks and ISDN Syst., vol. 9, pp. 223240, 1985. [11] N . F . Maxemchuk, "A variation on C S M A / C D that yields movable T D M slots in integrated voice/data local networks," Bell Syst. Tech. J., vol. 61, pp. 1527-1551, Sept. 1982. [12] N . F . Maxemchuk, "Some characteristics of movable slot T D M , " in Proc. 8th Conf. Local Comput. Networks, Minneapolis, M N , Oct. 1983. [13] W . Stallings, "Local network performances," IEEE

Commun.

Magazine,

vol. 22, Feb. 1984. [14] R . W . Klessig, "Overview of metropolitan area networks," IEEE

Commun.

Magazine, vol. 24, pp. 9-15, Jan. 1986. [15] D . T . Sze, "A metropolitan area network," IEEE J. Selected Areas Commun., vol. SAC-3, pp. 815-824, Nov. 1985. [16] N . F . Maxemchuk and A . N . Netravali, "Voice and data on a C A T V network," IEEE J. Selected Areas Commun., vol. SAC-3, pp. 300-311, Mar. 1985. [17] T . P . McGarty and G . J . Clancy, "Cable-based metro area networks," IEEE J. Selected Areas Commun., vol. SAC-1, Nov. 1983.

91

REFERENCES

[18] L . K . H o n a n d H . W . Lee "Performance analysis of the C S M A / C D a n d movableslot T D M protocols," i n Proc. Int. Conf. Commun., Seattle, W A . , June 1987. [19] L . K . H o n a n d H . W . Lee " A n approximate method for the delay analysis of C S M A / C D a n d its variation, M S T D M , " submitted to IEEE Trans. Commun. for p u b l i c a t i o n . [20] L . K . H o n a n d H . W . Lee, " S i m u l a t i o n studies of the movable-slot T D M protocol," i n Proc. IEEE/ACM

Symp. Simulation of Comput. Networks, C o l o r a d o

Springs, C O . , A u g . 1987. [21] L . K . H o n a n d H . W . L e e , "Interconnection of movable-slot T D M local area networks," i n Proc. of the IEEE Pacific Rim Conf. Commun. Comput. and Signal Processing, V i c t o r i a , B C , June 1987. [22] S.S. L a m , " A carrier sense m u l t i p l e access protocol for local networks," Comput. Networks, v o l . 4, p p . 21-32, F e b . 1980. [23] F . A . T o b a g i a n d V . B . H u n t , "Performance analysis of carrier sense multiple access w i t h collision detection," Comput. Networks, v o l . 4, p p . 245-259, O c t . N o v . 1980. [24] E . J . C o y l e a n d B . L i u , " A m a t r i x representation of C S M A / C D

networks,"

IEEE Trans. Commun., v o l . C O M - 3 3 , p p . 53-64, J a n . 1985. [25] S.S. L a m a n d L . K l e i n r o c k , "Packet switching i n a multiaccess broadcast channel: D y n a m i c control procedures," IEEE Trans, commun., v o l . C O M - 2 3 , pp. 891-904, Sept. 1975.

92

REFERENCES

[26] L . K l e i n r o c k , Queueing Systems, Vol. 1 & Vol. 2. N e w Y o r k : J o h n W i l e y , 1975. [27] C . J . Weinstein, "Fractional speech loss a n d talker a c t i v i t y m o d e l for T A S I and for packet-switched speech," IEEE Trans, commum., v o l . C O M - 2 6 , p p . 1253-1257, A u g . 1978. [28] J . M o u r a , J . F i e l d a n d J . W o n g , " E v a l u a t i o n of collision control algorithms i n Ethernet," i n Proc. of the 6th Data Commun. Symp., 1979

[29] A . N . N e t r a v a l i a n d Z . L . B u d r i k i s , " A broadband local area network," Bell Syst. Tech. J., v o l . 64, p p . 2449-2465, Dec. 1985. [30] M . H a t a m i a n a n d E . G . B o w e n , "Homenet:

A broadband

voice/data/video

network o n C A T V systems," Bell Syst. Tech. J., v o l . 64, p p . 347-367, F e b , 1985. [31] A . S . T a y l o r , " C h a r a c t e r i z a t i o n of cable T V networks as the transmission med i a for data," IEEE J. Selected Areas Commun., v o l . S A C - 3 , M a r c h 1985. [32] J . F . Hayes, Modeling &z Analysis of Computer Communications Networks. P l e n u m Press, 1983.