江苏七位体彩开奖结果

学霸学习网 这下你爽了

学霸学习网 这下你爽了

- A Comparative Study of Cooperative Algorithms for Wireless Ad Hoc Networks
- A Survey of Channel Assignment Schemes for Wireless Mesh Networks
- A Measurement Study of Path Capacity in 802.11b based Wireless Networks
- Experimental Study of Hidden-node Problem in IEEE802.11 Wireless Networks
- ZigBee-based wireless sensor networks for monitoring animal presence and pasture time in a strip of
- A Performance Study of Deployment Factors in Wireless Mesh Networks
- Achievable Dropping Rates under Variable Frame TDMA Schemes in the presence of Deadlines an
- Moving Schemes for Mobile Sinks in Wireless Sensor Networks
- Bandwidth Estimation Schemes for TCP over Wireless Networks

江苏七位体彩开奖结果 www.jwbw.net Study of Various TDMA Schemes for Wireless Networks in the presence of Deadlines and Overhead.

Cesar Santiva~ez Ioannis Stavrakakis n

Department of Electrical & Computer Engineering Northeastern University Boston, MA 02115, USA

Abstract

The objective of this paper is to determine the minimum system dropping rate (or, equivalently, dropping probability) induced by TDMA schemes supporting time-constrained applications with common maximum cell delay tolerance. Expressions are derived for the induced system dropping rate for various TDMA schemes with di erent overhead and the maximum number of users than can be admitted in the network without violating the maximum dropping rate constrain is determined. Based on these derivations, the optimal (or of largest \capacity") TDMA scheme - among those considered - is determined. The performance limiting factors associated with the suboptimal schemes are identi ed, and the magnitude of their (negative) impact is evaluated. Based on this information it is possible to point to performance improving modi cations which should be pursued to the extend permitted by technological constraints.

This research is supported in part by a Fulbright Scholarship, the National Science Foundation, and the GTE Corporation

1 Introduction

Wireless communications networks, e.g. cellular telephony, have grown in the past two decades to become a sizeable part of the telecommunications market 1]. This rapid growth is due to some highly desirable properties of a tetherless terminal, such as mobility, and has been enabled by advances in DSP technology - which have lead to the reduction in size, power consumption and cost of the mobile units - and the assignment of radio spectrum for public (e.g. PCS) and private (e.g. wireless LAN) wireless networks. Two major wireless networking technologies have emerged: cellular systems (originally designed to support voice applications in a wide area network), and wireless LANs (developed to support computer data applications in a local area network). Currently, these two technologies are converging. Cellular systems have evolved from an analog network (AMPS) to a circuit-switched based digital network (e.g. GSM) and the next generation wireless systems are expected to be multiservice cell-switched based networks. On the other hand, wireless LANs are now expected to provide real-time services such as image, video and possibly voice support. This convergence drives a demand for a single network architecture capable of supporting all aforementioned services in an integrated fashion, which should also be compatible with the xed ATM-based Integrated Services Network. For this reason, it will be natural to consider an ATM-based protocol for the local and broadband wireless network 2, 3] namely Wireless ATM. System architectures to enable \Wireless ATM" (WATM) have already been developed 4, 5, 6]. They employ a Data Link Control (DLC) layer to combat the unreliability of the wireless link, and a Medium Access Control (MAC) protocol to organize the sharing of the multiaccess channel. MACs for WATM have been examined in 4, 7, 8, 9, 10, 11]. They all employ TDMA with on-demand assignment of the transmission resources by a central agent or scheduler. It is believed that a TDMA-based MAC provides the best mix of cost, range, interference and performance 12] . Since the wireless channel is a medium shared by distributed users, its allocation presents some distinct problems from those associated with the allocation of outgoing link resources to arrivals to a xed network node. In the latter case, the scheduler has complete knowledge of the demand for resources as soon as they are generated (occurrence of incoming link arrivals). In addition, scheduling decisions (resource assignments) can be implemented instantaneously, due to the collocation of the scheduler and the workload in the xed node . In a dynamic wireless environment though, the scheduler needs to be communicated by the distributed users of their demands for resources, as well as inform the users of its decision (slot assignment). This communication takes place at discrete points in time 4, 7, 8, 9, 10, 11] and it is not continuous due to communication resource limitations. It is implemented by employing various mechanisms such as a control channel, piggy-backing on information bearing cells and polling procedures; such mechanisms introduce some overhead in the system. A MAC protocol should employ a scheduler in order to allocate resources e ectively by taking 1

into consideration the QoS requirements of the supported applications. A call admission control function is assumed to be employed as well, shaping the set of the supported applications (accepted sessions). In this paper, the QoS is de ned in terms of a maximum tolerable cell delay and dropping probability. A cell is dropped when its maximum tolerable delay is exceeded. Or, equivalently, when its remaining delay tolerance reaches zero and its service is not completed; the remaining delay tolerance is equal to the maximum delay tolerance when the cell is generated and decreases by one in every subsequent slot (cell service time unit). Such QoS parameters are typically associated with real-time applications such as voice and video. The objective in this paper is to determine the minimum system dropping rate (or, equivalently, dropping probability) induced by various TDMA schemes supporting time-constrained applications with common maximum cell delay tolerance. Based on these derivations, the optimal (or of largest \capacity") TDMA scheme - among those considered - will be determined, which is another objective of this study. From the study of these TDMA schemes it will be possible to identify the performance limiting factors associated with the suboptimal schemes, determine the magnitude of their (negative) impact and to point to performance improving modi cations which should be pursued to the extend permitted by technological constraints. In order for the minimum system dropping rate to be induced in a TDMA scheme, the employed scheduler must try to minimize the number of cells dropped per unit time (slot). In the environment with time constrained applications considered here this scheduler will be the one implementing the Shortest Time to Extinction (STE) service discipline; that is, serving cells in the order of increasing remaining delay tolerance and dropping expired (zero delay tolerance) cells. Any attempt to deviate from the STE service discipline - in order to control delay jitter, establish some type of fairness, diversify the induced dropping rate, etc - can only increase the resulting (overall) system dropping rate 13, 14]. For this reason, the STE service discipline will be assumed to be employed by the scheduler in all TDMA schemes considered here, to induce the minimum dropping rate possible. As it will be pointed out later, some deviation from the STE service discipline which does not increase the induced dropping rate is easily recognizable for certain TDMA schemes. Finally, it should be noted that all schemes considered here are work conserving except from the Fixed Frame Length TDMA scheme. The rst TDMA scheme (Section 2) - referred to as the Ideal Continuous Entry TDMA (ICETDMA) scheme - is equivalent to a (centralized) dynamic TDM as it would be employed in a xed network node. No frame structure is present and the scheduler is assumed to have knowledge of all past arrivals at the time when they occur. Thus, cells are considered by the scheduler as soon as they are generated (Continuous Entry) which would not be feasible in a wireless environment (Ideal). The ICE-TDMA scheme (under the STE service discipline employed by the scheduler as indicated earlier ) will be the optimal scheme against which all other - more realistic - schemes will be compared. The cell dropping rate induced by the ICE-TDMA scheme is calculated by deriving 2

a closed form expression, as opposed to developing a numerical solution which is the case under the other TDMA schemes considered in this paper. This study provides insight into the more realistic TDMA schemes in addition to determining the lower bound on the system dropping rate under any TDMA scheme supporting the same set of applications The second TDMA scheme (Section 3) - referred to as the Ideal Variable Frame Length TDMA (IVFL-TDMA) scheme - employs a frame structure of variable length, at the boundaries of which scheduling decisions are taken. A gated-STE service discipline is employed which starts servicing according to the STE service discipline the cells arrived before the beginning of the current frame only, until all such cells are either served or dropped, marking the end of the current frame. The scheduler is assumed to have knowledge of the exact time when past arrivals occurred when scheduling decisions are taken only, as opposed to when these arrivals occur; the latter is the case under the ICE-TDMA scheme. Consequently, the gated-STE service discipline could schedule cells di erently than the STE and, thus, suboptimally. This could be the case if an earlier arriving cell has a remaining delay tolerance greater than that of a later arriving cell at the time the later cell arrives. If such arrivals occur during di erent frames then the gated-STE service discipline would schedule for service the earlier cell rst while the STE service discipline would schedule the later rst. As a result, the performance of the gated-STE service discipline may be suboptimal. As long as always earlier arriving cells have a remaining delay tolerance less than or equal to that of a later arriving cell at the time the later cell arrives, then the scheduling decisions of the STE and gated-STE policies would coincide and the resulting system performance be identical. The above condition holds in the case in which all arrivals have the same maximum delay tolerance which is assumed to be the case in this paper. In view of the above discussion it is evident that the system dropping rate induced under the ICE-TDMA and IVFL-TDMA schemes will be identical. Because of the delay associated with the arrival information availability to and scheduling decisions by the scheduler under the gated-STE service discipline, the IVFL-TDMA scheme is expected to be less exible (and potentially less e ective) in selecting cells to be discarded in order to meet a QoS speci cation requiring service discrimination or fairness, delay jitter control, etc. Despite the fact that the system performance is identical under the ICE-TDMA and IVFLTDMA schemes, there are several reasons justifying the presentation and study of the IVFLTDMA scheme. First, the IVFL-TDMA scheme requires less communications overhead than the ICE-TDMA scheme : one exchange every frame versus every slot, respectively. If a separate communications channel is available and can be utilized for request/assignment exchanges between the users and the scheduler then both the ICE-TDMA and IVFL-TDMA schemes become feasible; more so the IVFL-TDMA though, due to the lesser (more realistic) information exchange overhead. Second, the IVFL-TDMA scheme is a limiting case of (or can be extended to) the Real Variable Frame Length TDMA (RVFL-TDMA) scheme (Section 4), which considers explicitly the 3

request/assignment overhead as it is present in practical (deployed) systems. Thus, the insight gained as well as the analysis developed in the study of the IVFL-TDMA scheme are useful for the study of the RVFL-TDMA Scheme. For the later analysis purposes, an alternate analysis of the IVFL-TDMA scheme is presented in Section 3 despite the fact that it leads to the same numerical results as the di erent approach developed for the study of the ICE-TDMA scheme in Section 2. The third TDMA scheme (Section 4) - referred to as the Real Variable Frame Length TDMA (RVFL-TDMA) scheme - is similar to the IVFL-TDMA scheme, only that a xed amount of time during each frame is utilized for request/assignment exchange between the users and the scheduler and not for cell transmission (frame overhead). The RVFL-TDMA scheme is the most realistic of the three presented so far and has been employed in the wireless system developed in 11] (this system also considers overhead of variable length). In the present study the impact of the overhead is evaluated analytically by deriving tight bounds on the system dropping rate and a number of interesting comparative results are presented. Among the latter, there is a comparison of the performance induced under the RVFL-TDMA scheme and the optimal Real Fixed Frame Length TDMA (RFFL-TDMA) scheme discussed next. The fourth TDMA scheme (Section 5) - referred to as the Real Fixed Frame Length TDMA (RFFL-TDMA) scheme - assumes a xed frame length, a xed part of which is considered to be overhead. Tight bounds on the induced system dropping rate are derived. The case of zero frame overhead - leading to the Ideal Fixed Frame Length TDMA (IFFL-TDMA) scheme - is easily analyzed as a special case of the RFFL-TDMA scheme by setting the frame overhead equal to zero. It should be noted that a Real Fixed Frame Length TDMA (RFFL-TDMA) scheme can be a non work conserving scheme since empty slots may be left in a frame while cells are waiting for service. In a RFFL-TDMA scheme the slots of the xed frame can be preassigned to a speci c application, rendering the exchange of requests/assignments between users and scheduler unnecessary. In this case the frame overhead can be eliminated, leading to the Fixed Frame TDMA (FF-TDMA) scheme, where the scheduler assignments are static (do not vary on-demand). This is basically the TDM scheme employed in the T-1 system for voice transmission. While the FF-TDMA scheme will outperform any other TDMA scheme under proper frame sizing and regular applications (constant tra c type of applications), it would be very ine cient in the presence of variable tra c applications. In the latter environment allocating the time slots dynamically upon demand would improve performance. Since the slots are not reserved, some communications resources will need to be utilized for the request/assignment information exchange between users and scheduler leading to a RFFL-TDMA scheme if some frame overhead is used for this communication. Thus in a dynamic tra c environment in which portion of the time - as opposed to other resource - is expended for the exchange of request/assignment information, the RVFL-TDMA and RFFL-TDMA schemes could be employed. As the results will demonstrate, the induced system dropping rate under the RVFLTDMA scheme is lower than that under the best RFFL-TDMA scheme employing the optimal 4

bk-2

bk-1

bk

bk+1

bk+2

ak-2

ak-1

ak

ak+1

ak+2

...

t k-2

Q k-2

t k-1

Q k-1

tk

Qk

tk+1 t k+2

Q k+1 Q k+2

...

Figure 1: Arrivals and Departures at ideal continuousentry TDMA scheme. length for the xed frame. A discussion on the applicability and relative (comparative) e ectiveness of the various TDMA schemes studied in Sections 2-5, is presented in Section 6 along with a number of numerical results. The common environment assumed in all TDMA schemes consists of N memoryless timeconstrained applications with identical maximum delay tolerance equal to T time units; the time unit is referred to as the (time) slot and is assumed to be equal to the cell service time. The N users compete for the time resource which is allocated by the scheduler at the scheduling decision times, as indicated earlier.

2 The Ideal Continuous Entry TDMA (ICE-TDMA) Scheme

As indicated earlier, under the ICE-TDMA scheme the time-slots are (re)allocated every time a new cell arrival occurs (continuous-entry scheme). It is assumed that no time is consumed for the users to make their reservation nor for the scheduler to inform the users of its assignments (ideal scheme). Let tk denote the time at the beginning of the k-th time slot. It is assumed that the transmission requests (namely arrivals) and the cell departures occurs at slots boundaries, that is at times ftk g, with k = 0; 1; : : :; +1. Without loss of generality it is also assumed that a cell transmission (if any) is completed at time t? (i.e. the departure process is right-continuous) and that cell arrivals k + (i.e. the arrival process is left-continuous). Figure 1 shows a sequence of such (if any) occur at tk events. Let Qk denote the number of cells in the system at time tk (just after a departure but before the new arrivals); let ak denote the number of arrivals at t+ ; let bk denote the number of cells k ? (0 or 1). If ak cells arrived at t+ then the last of these cells would have to wait departing at time tk k for Qk + ak time slots before its transmission is completed. If this time is greater than T time slots then this cell will not meet its deadline and will be dropped. It is easy to see that the scheduler will drop Qk + ak ? T cells. Note that it is not necessary to drop the last Qk + ak ? T cells but any Qk + ak ? T cells in the bu er at time t+ . This is in contrast to the gated scheme (discussed k later) under which only cells which have not been scheduled for transmission yet can be dropped. The number of cells in the system at time tk+1 (after the last departure but before any new 5

arrivals) is given by:

Qk+1 = minfT; Qk + ak g ? bk+1 = minfT; Qk + ak g ? 1fSystem Busyg

From the above, 0 Qk T ? 1 for any value of k. Since fak g are i.i.d. random variables (because the sources are memoryless) then the process fQk g is a Markov Process with transition matrix < Pij > (i.e. Pij = P fQk+1 = i=Qk = j g), derived in Appendix A.1. Then, the steady state probability distribution of Qk is expressed as a function of T , as shown in Appendix A.2. Using the steady state probability distribution of Qk and the probability distribution of the arrivals, a closed form expression for the dropping rate is derived in Appendix A.3. It turns out that the dropping rate as a function of the maximum delay tolerance T can be described as the quotient between two IIR (In nite Impulse Response) lters as follows (see Appendix A.3) : z (z ?1 dr (T ) = N (Y )(X)]?)] z 1 where, ?1 z 0 z ?1 N (z) = z D(?)z+ 1 ? 1] ; X (z) = Dl(0z) ; Y (z) = 1 ? lz ?1 D(z) 1 ?

D(z) = l0 + (l0 + l1 ? 1)z ?1 + (l0 + l1 + l2 ? 1)z ?2 + : : : + (l0 + l1 + l2 + : : : + ln?1 ? 1)z ?(n?1) l = P fak = g for = 0; : : :; n is the probability of exactly arrivals at any point in time; and P is the mean arrival rate, that is, = n=1 l .

This method is computationally reliable and simple, and there are available several computational tools. The previous expression is valid for di erent values of the mean arrival rate( ), even greater than 1. For the case of interest, when < 1, for large values of the maximum delay tolerance (T ) the dropping rate will depend almost entirely on the dominant pole rd of the above T lter (largest root of D(z )); thus dr (T ) rd where is a constant as explained in Apendix A.3. In the limiting case when = 1, the dominant pole rd = 1 and for large values of T , it follows l dr (T ) 2(T +1) , where l2 is the variance of the distribution of the number of arrivals. Thus a closed-form solution for the dropping rate as a function of the maximum delay tolerance (T ) is found. The same quantity will be derived again by following a di erent procedure in the next section where the IVFL-TDMA scheme is analyzed. Although that procedure is less insightful, it will be employed with minor modi cations in the study of the RVFL-TDMA scheme (considering the frame overhead). The dropping rate computed in Section 3 represents the optimal (minimal) dropping rate that any TDMA scheme can achieve under the same tra c characteristics (set of supported applications).

2

3 The Ideal Variable Frame Length TDMA (IVFL-TDMA) Scheme

The IVFL-TDMA scheme described brie y in Section 1 is analyzed in this section. 6

A scheduler’s decision is made

A scheduler’s decision is made

A scheduler’s decision is made

tk-1

g

...

g tk

...

tg k+1

L k-1

: Arrivals and Departures

Lk

(a) Ideal, Gated, Scheme

A scheduler’s decision is made

A scheduler’s decision is made

A scheduler’s decision is made

DATA ...

Re

In

DATA

Re

In

DATA

Re

In

DATA...

t

g k-1

t

g k

...

t

g k+1

L k-1

Lk

(b) Real, Gated Scheme

Figure 2: Events and quantities of interest for the (a)Ideal, and (b)Real Variable Frame Length TDMA schemes. Let tg denote the instant of the k-th scheduling decision or beginning of the k-th service cycle k (frame); let Lk denote the length of this frame (Lk = tg +1 ? tg ) as shown in Figure 2.a. Without k k loss of generality, the arrival and departure processes are assumed to be right continuous. If no cell is waiting for transmission at time tg , the present service cycle is empty and the next service cycle k begins after one time slot. That is, an empty service cycle has a duration of 1 empty time slot. From the above and since any cell waiting for more than T time slots must be discarded, it follows that 1 Lk T . In the following subsections, the dropping rate is evaluated using the following procedure: First, the conditional expected number of dropped cells in a frame given that the length of the I previous frame is L, namely dr=L(T ), is computed; superscript I stands for ideal. Second, using I the transition probability matrix < Pij >, describing the next frame length given the current one, the steady state frame length probability distribution I is calculated. Finally, the dropping rate i dI (T ) is computed from the following expression: r

I I ELfdr=L(T )g PT=1 I dr=i(T ) i i I (T ) = dr = PT I E fLg i=1 i i

(1)

7

3.1 Conditional expected number of dropped cells, dI=L(T). r

^ Let R(t) denote the cumulative arrivals up to (and including) time t (right continuous). Let Ak?1 ( ) g and tg + , that is, time slots (see Figure 3) denote the number of arrivals between time tk?1 k?1 after the beginning of the previous service cycle: ^ Ak?1 ( ) = R(tk?1 + ) ? R(tk?1 ); 0

Lk?1 :

1

k? ^ Note that since sources are assumed to be memoryless, the evolution of the process fAk?1 ( )gL=0 ^ does not depend on time tk?1 but only on the length of the previous cycle, Lk?1 ; also Ak?1 (0) = 0, since the arrival process is right continuous. ^ At time tg the scheduler considers the Ak?1 (Lk?1 ) cells waiting for transmission, schedules k ^ some of them for transmission (namely Lk ) and drops the rest (namely dr;k ). g + 1 there will have arrived A (1) cells, the last of which will have to wait the ^k?1 At time tk?1 ^ Lk?1 ? 1 time slots remaining for the end of the previous service cycle, plus Ak?1 (1) time slots to ^ complete its transmission. If this time (Ak?1 (1) ? 1 + Lk?1 ) is greater than the maximum delay ^ tolerance T , then Ak?1 (1) ? 1 ? T + Lk?1 cells will be dropped. In general,the number of cells that ^ must be discarded by time tg ?1 + , namely dk ( ), is given by: k

^ ^ ^ dk ( ) = maxf0; 1max Ak?1 ( 0) ? ( 0 + T ? Lk?1 )]g = maxf0; 1max Ak?1 ( 0 ) ? f 0 ]g 0 0

k? ^ where f 0 = 0 + T ? Lk?1 ; 0 0 Lk?1 . An example of the evolution of the process fAk?1 ( )gL=0 and the linear function f is shown in Figure 3. Notice that f represents the maximum number of arrivals up to time which can be transmitted before their deadline expires. It should also be noted that cells may be dropped even if the total number of arrivals over the (k ? 1) ? th service cycle is less than or equal to T . In fact, the number of cells which are dropped (will not meet their k? ^ deadline) is determined by the maximum di erence between fAk?1 ( )gL=0 and f , as indicated in the above equation. ^ ^ ^ Let mk ( ) = 1 max Ak?1 ( 0 ) ? 0 ]. Then dk ( ) can be rewritten as: dk ( ) = maxf0; mk ( ) ? ^ ^ 0 ^ (T ? Lk?1 )g. Notice that dr;k - the total number of cells dropped at tk , that is at the beginning of ^ the k-th service cycle- will be equal to dk (Lk?1 ). Let Aj ( ) , m( ) , dj ( ), and dr;j with j = Lk?1 be the random variables associated with ^ ^ ^ Ak?1 ( ), mk ( ), dk ( ), and dr;k respectively. These random variables do not depend of the time tg ^ k but only on the previous cycle's length Lk?1 described by j . Notice that fAj ( )gj =0 represents a right-continuous, discrete-valued, cumulative arrival process which has initial value zero (Aj (0) = 0), evolves for j time slots, and has independent increments. The probability of arrivals at any given discrete-time (increment) is given by l . For j = Lk?1 , by de nition:

1 1

m( ) = 1max Aj ( 0) ? 0 ] ; dj ( ) = maxf0; m( ) ? (T ? j )g ; dr;j = dj (j ) 0

8

^ Ak-1( τ )

T

^ d r,k

^ Ak-1( τ )

T - L k-1

fτ = τ + T - L k-1

τ

L k-1

Figure 3: Arrivals (waiting cells) during the (k-1)-th service cycle Notice that dr;j denotes the number of cells dropped at the beginning of a service cycle that follows a service cycle of length j ; its probability is given by:

8 < P fdr;j = dg = P fdj (j ) = dg = :

P fm(j ) = T ? j + dg if d 1 P fm(j ) T ? j g if d = 0

Pj ( ) is de ned by:

8 > P fm(j ) = g if > 1 > < Pj ( ) = > P fm(j ) 0g if = 0 > >0 : elsewhere,

It is shown in the Appendix B that Pj ( ) can be computed using the following recurrent formula:

8P > minfn; +1g l Pj ?1 ( + 1 ? ) > if 1 > =0 < Pj ( ) = > l0Pj?1 (0) + l0 Pj?1 (1) + l1Pj?1 (0) if = 0 > >0 : elsewhere

with initial conditions: P0 ( ) = ( ) (i.e. zero always except at P0 (0) = 1). Thus, the conditional expected number of dropped cells at the present frame given the previous I frame length is L (dr=L(T )) is given by:

1 I ^ ^ dr=L (T ) = E fdr;k=Lk?1 = Lg = P+=1 dP fdr;k = d=Lk?1 = Lg = d

+1 X +1 X

=

d=1

dP fm(L) = T ? L + dg =

d=1 +1 X d=1

dP fdr;L = dg

dPL(T ? L + d)

3.2 Service Cycle Length's Probability Distribution

The k ? th cycle length is given by: ^ ^ Lk = Ak?1 (Lk?1 ) ? dk (Lk?1 ) 9

^ Bk-1( τ )

T Lk

fτ = τ + T - L k-1

T - L k-1

^ Bk-1( τ )

τ

L k-1

^ Figure 4: Number of 'surviving' cells Bk?1 ( ) among the cells arrived up to time tg ?1 + . k

I ^ ^ and since Ak?1 (Lk?1 ) and dk (Lk?1 ) are correlated, it is not easy to compute Pij = P fLk = k? ^ i=Lk?1 = j g from the above equation. The process fBk?1 ( )gL=0 with generic representation ^ fBj ( )gj =0 (with j = Lk?1) will be considered. Bk?1 ( ) represents the number of `surviving' (i.e. neither dropped nor assigned for transmission yet) cells among the cells arrived up to time tg ?1 + . k Thus, for the variable frame length case:

1

^ ^ ^ Bk?1 ( ) = Ak?1 ( ) ? dk ( ) and Bj ( ) = Aj ( ) ? dj ( )

k? ^ An example of the evolution of fBk?1 ( )gL=0 is shown in Figure 4. This evolution can be interpreted as if the cells that will have to be dropped, are being discarded as soon as this is realized, that is, each time Bk?1 ( ) tends to become greater than the line f = T ? Lk?1 + . It follows:

1

Lk

^ = Bk?1 (Lk?1 )

I Pij = P fLk = i=Lk?1 = j g

8 < =: 8 < =:

^ P fBk?1 (Lk?1 ) = i=Lk?1 = j g if i 2 ^ P fBk?1 (Lk?1 ) = 1 or 0=Lk?1 = j g if i = 1 P fBj (j ) = ig if i 2 P fBj (j ) = 1g + P fBj (j ) = 0g if i = 1

Let PB j (i; T ) = P fBj ( ) = i=maximum delay tolarance = T g, then the following recurrent formulas holds:

8P < n=0 l PB j (i ? ; T ) ?1 j (i; T ) = PB : Pn=1 (Pn= l )PB j ?1 (i ?

if i < T ? j + ; T ) if i = T ? j +

with the initial conditions:

8 < j PB0 (i; T ) = : 1 if i = 0 0 elsewhere

10

The rst equation holds since no cell is dropped in the actual time slot ( ) when i < T ? j + ; thus, Bj ( ) = Bj ( ? 1) + a , where a is the number of cells arriving at time (as before l = P fa = g). The second equation holds since cells may be dropped when i = T ? j + . Thus, given that Bj ( ? 1) = x, then if (and only if) a T ? j + ? x then Bj ( ) = T ? j + . I From the above recurrent equations Pij may be calculated as,

8 < I Pij = :

and then the steady state probability distribution of the service cycle length, I = P fLk = ig, can i be computed. I Finally, the dropping rate drI (T ) is computed from dr=L(T ) and I by using equation (1). i Alternatively, equation (4) could be used (see Appendix D.1) but it may be numerically unreliable.

PBjj (i; T ) if i 2 j (1; T ) + PB j (0; T ) if i = 1 PBj j

4 The Real Variable Frame Length TDMA (RVFL-TDMA) Scheme

The RVFL-TDMA scheme is analyzed in this section (see Figure 2.b). The only di erence between this scheme and the previous one (Section 3) is the consideration of the frame overhead. In this real scheme, the rst Re time slots at the beginning of every service cycle are consumed by the user's transmission requests; these Re time slots are referred to as the reservation period. The next In time slots are used by the scheduler to inform the users of its decisions (slot assignments) and are referred to as the information period. It is assumed that both Re and In are xed and independent of the tra c load. The k-th service cycle begins at time tg ? Re, when the scheduler begins to receive the previous k service cycle's arrival information of each user. At time tg the scheduler has all the required k information, takes its scheduling decision and informs the users during the next In time slots. At time tg + In the user's data transmissions (receptions) begin. k Let tg denote the time at which the j-th user completes the transmission of its request for k;j slots of the k ? th frame, that is, provides to the scheduler information regarding its arrivals over the (k ? 1) ? th frame; tg ? Re tg tg . Clearly, this request will be based on user information (to k k;j k be transmitted) which is generated before tg . By assuming that this request (at tg ) represents k;j k;j all the information generated by user j until tg or tg ? Re, the auxiliary systems L and U are k k constructed. That is, the following key assumptions are made regarding the content of the requests from all users, leading to systems L and U :

Under the auxiliary system L, a cell arriving over the interval < tg ; tg > will be considered k;j k for service during the k ? th service cycle. Under the real scheme this cell will be considered for 11

L : At time tg the scheduler knows about all arrivals up to time tg . k k U : At time tg the scheduler knows only about the arrivals up to time tg ? Re. k k

service in the the (k + 1) ? th service cycle. Clearly, the cell delay under the real scheme will be shaped by an additional service cycle length (Re + In+ data) compared to that under system L. Thus, the auxiliary system L outperforms the real system. A similar argument between the real system and auxiliary system U regarding cells generated over < tg ? Re; tg > establishes that the k k;j real scheme outperforms the auxiliary system U. Let the superscripts I; R; L; U indicate a quantity associated with the IVFL-TDMA scheme, RVFL-TDMA scheme, auxiliary system L and auxiliary system U, respectively. In view of the above discussion it is easy to establish that: dI < dL dR dU . r r r r The auxiliary systems L and U will be studied to calculate tight (as it will be shown) bounds on the performance induced by the real, variable frame length, gated scheme.

4.1 Computation of dL r

Since the maximum delay tolerance is T, the service of the last cell served over the k ? th service cycle must be completed by tg + T . Thus, the maximum length of a busy (at least one served) k g + T ? (tg ? Re). Due to the overhead, the length of an empty frame will frame will be equal to tk k be equal to Re + In. Thus, Re + In Lk Re + T for any k. ^ Let Ak?1 ( ), for 0 Lk?1 represents the number of cell arrivals (generations) over g (as before, Section 3); such arrivals will be considered for service consecutive slots following tk?1 ^ during the k ? th frame (see Figure 2.b). Clearly, Ak?1 (Lk?1 ) represents all the arrivals (between tg?1 and tg ) to be considered for service during the k ? th frame. k k ^ Since Ak?1 ( ) cells have arrived at time tg ?1 + , then the last of these cells will have to wait k Lk?1 ? Re ? time slots (the remaining time for the end of the (k-1)-th service cycle) plus the ^ overhead period (Re + In time slots) plus Ak?1 ( ) time slots, in order to complete its transmission. ^ Clearly, if this time (Ak?1 ( ) ? + Lk?1 + In) is greater that T time slots some cells will be dropped. Thus, the number of cells arrived over < tg ?1 ; tg ?1 + > which must be discarded is given by: k k ^k ^ dL( ) = maxf0; 1max Ak?1 ( ) ? ( + T ? In ? Lk?1 )]g 0 ^ = maxf0; 1max Ak?1 ( ) ? ( + T 0 ? Lk?1 )]g; 0 where T 0 = T ? In. For Lk?1 T 0 this expression is the same to the one obtained in Section 3.1. The results of Section 3 for the conditional dropping rate and the frame length are still valid here. I Let dr=j (T ), be the conditional expected number of dropped cells in the present frame given that the previous frame length was j , for the IVFL-TDMA scheme with maximum delay tolerance equal to T time slots, as computed in Section 3.1; let PB j (i; T ) be the probability that i cells survived among those arrived over consecutive slots following the time by which all past arrivals had already been considered, given that the maximum number of surviving cells up to this time is equal to + T ? j as computed in Section 3.2. Two cases need to be considered : Case 1 : Re + In j = Lk?1 T 0 = T ? In. 12

^ ^ Processes Ak?1 ( ) and Bk?1 ( ) (de ned in Section 3.2) evolve as processes Aj ( ) and Bj ( ) with maximum delay tolerance T 0 = T ? In, respectively. Taking into consideration that Lk = ^ Bk?1 (Lk?1 ) + Re + In the following \adjustments" to the quantities derived in Section 3 lead to the corresponding quantities associated with the auxiliary system L:

L I L dr=j (T ) = dr=j (T ? I ) and Pij = PBjj (i ? Re ? In; T ? In) L L where dr=j (T ) and Pij denote the conditional expected number of dropped cells in the present frame given that the length of the previous frame is j , and the probability that the present frame length is i given that the previous frame length is j , respectively. Case 2 : T 0 = T ? In < j = Lk?1 Re + T . The cells arriving at the rst j ? T 0 time slots of frame (k ? 1) ? th will be discarded; for the ^ ^ remaining T 0 time slots, Ak?1 ( 0 ) and Bk?1 ( 0) will evolve as processes Aj ( 0) and Bj ( 0) with maximum delay tolerance T 0 and length j 0 = T 0. Then: L I L T ?In dr=j (T ) = (j ? T + In) + dr=T ?In (T ? In) and Pij = PBT ?In (i ? Re ? In; T ? In)

where denotes the mean number of arrivals per slot. Finally,

be used (see Appendix D.2), but it may be numerically unreliable.

PRe+T L L Re+In d (T ) (2) = j =PR+T j r=j L j =R+I j j L where L = P fLk = i at system L g and it is computed from Pij . Alternatively, equation (5) could i

dL (T ) r

4.2 Computation of drU

In the auxiliary system L, arrivals over the overhead period Re + In are treated di erently. The arrivals over Re are served in the immediate service cycle while arrivals over In are served one service cycle later. In the auxiliary system U all arrivals over Re + In are served later. Thus, the auxiliary system U can be viewed as equivalent to an auxiliary system L with parameters Re0 = 0 and In0 = Re + In. It is easy to establish that the performance of system U can be derived from the performance of the corresponding L system with delay tolerance reduced by Re. That is, Re0 = Re, In0 = In, and T 0 = T ? R and nally:

drU (T ) = dL (T ? Re) r

13

5 The Real Fixed Frame Length TDMA (RFFL-TDMA) Scheme

Consider the RVFL-TDMA scheme in which the frame length Lk is not variable (on-demand) but xed and equal to Lf time slots. As before, two auxiliary systems are de ned:

FL : At time tg the scheduler knows about all arrivals up to time tg . k k FU : At time tg the scheduler knows only about the arrivals up to time tg ? Re k k

Let the superscripts FL; FR, and FU indicate a quantity associated with the auxiliary system FL, RFFL-TDMA scheme, and auxiliary system FU, respectively. Similarly to Section 4, it is easy to establish that: dFL dFR dFU . r r r The auxiliary systems FL and FU will be studied to calculate tight bounds on the performance induced by the RFFL-TDMA scheme.

5.1 Computation of dFL(T) r

An approach similar to the one used before to compute the dropping rate of the IVFL-TDMA scheme is employed here. The complete procedure is explained in Appendix C.

5.2 Computation of dFU r

Using an argument similar to the one used in Section 4.2, it can be claimed that the system FU can be viewed as equivalent to an auxiliary system FL with parameters Re0 = 0 and In0 = Re + In. Thus, It is easy to establish that the performance of system FU can be derived from the performance of the corresponding FL system with delay tolerance reduced by Re. That is Re0 = Re, In0 = In, and T 0 = T ? R and nally,

drFU (T ) = dFL (T ? Re) r

6 Numerical Results and Discussion

In this section the performance of the various TDMA schemes presented in this paper is investigated by employing the analytical studies presented in the previous sections. In addition to evaluating the impact of the key parameters - such as the maximum delay tolerance T , the number of applications N , the length of frame overhead, etc. - some of the results point to the performance advantage of certain schemes over others. The lower and upper bounds on the dropping rate induced under a RVFL-TDMA scheme supporting N=6 Bernoulli users are calculated by employing the auxiliary systems L and U and using the expressions derived in Section 4; the per user tra c rate is equal to 0.15. The results are presented in Figure 5 as a function of the maximum delay tolerance T and for various values 14

10

0

Dropping Rate (dr)

10

?2

10

?4

Re

=3

Re

, In

=2

=1

Re

10

?6

, In

=1

=1

, In

Re

10

?8

=1

=1

, In

=0

Re

U Systems L Systems

=0

, In

=0

10

?10

10

?12

0

10

20

30

40

50

60

70

80

90

Figure 5: Dropping rate bounds under the RVFL-TDMA scheme versus maximum delay tolerance (T) for various values of (Re; In); total tra c rate is = 0:9 . of (Re; In). For the (small) values of the frame overhead (Re + In) considered turns out that the bounds are very tight, suggesting that the results under the auxiliary system L (lower bound) can serve as a good approximation on the exact dropping rate. The results suggest that a small increase in the length of the frame overhead results in a signi cant increase in the dropping rate. Thus it may be worth trying to reduce the length of the frame overhead by employing mechanisms such as piggy-backing and arrival time estimation. Figure 6 depicts the lower bound on the dropping rate under the RVFL-TDMA scheme under di erent tra c con gurations. The results are shown as a function of T and for various values of (Re; In) = (ov; 0) - ov is short for overhead. Figure 6-(a) is derived for a set of N = 6 Bernoulli users with per user rate of 0.15 (total rate = 0:9); Figure 6-(b) is derived for a set of N = 5 Bernoulli users with per user rate of 0.20 ( = 1:0); Figure 6-(c) is derived for a set of N = 4 Bernoulli users with per user rate of 0.20 ( = 0:8); Figure 6-(d) is derived for a set of N = 50 Bernoulli users with per user rate of 0.016 ( = 0:8). From the values in Figure 6 (in log scale) the exponential decay of the dropping rate can be observed for large T. This is the case not only under zero frame overhead (as expected from Section 2) but also in the presence of frame overhead. By considering the results in Figure 6-(c) and Figure 6-(d) for small frame overhead length it can be concluded that the induced dropping rate for N = 50 users (Figure 6-(d)) is signi cantly greater than that for N = 4 users (Figure 6-(c)), although = 0:8 in both cases. This di erence may be attributed to the larger variance of the tra c for N = 50 and decreases as the frame overhead increases. Thus, the burstiness (variance) of the tra c in addition to the rate may impact signi cantly on the induced dropping rate. The maximum number of users that can be supported under the RVFL-TDMA scheme can be determined by considering the results in Figure 7, presenting the dropping rate as a function of the number N of supported Bernoulli users and for various values of (Re; In) = (overhead; 0); 15

Τ

100

(a) 6 users, λ = 0.90

dropping rate

10

0

(b) 5 users, λ = 1.0

10

0

10

?5

10

?10

ov = 2 =1 ov =0

ov . ov = 3

.

.

dropping rate

10

?1

.. . ov = 1

10

?2

ov = 0

0 20 40 60 80

10

?15

0

20

40

60

80

T

100

T

100

dropping rate

10

?5

dropping rate

10

0

(c) 4 users, λ = 0.80

10

0

(d) 50 users, λ = 0.80

10

?5

10

?10

10

?15

ov

?20

ov = 0

ov . = = 2 1

80

.

.

10

?10

10

?15

ov

ov = 2 = 1 = 0

80

ov

.

..

10

0

20

40

60

100

10

?20

0

20

40

60

100

T

T

Figure 6: Dropping rate versus maximum delay tolerance (T) for di erent con gurations of the RVFL-TDMA scheme. note that for a given (frame) overhead length, setting Re = overhead and In = 0 will yield the lowest dropping rate for the particular TDMA scheme. The results shown in Figure 7 quantify the (negative) impact of the frame overhead on the system utilization when a certain level of QoS (dropping rate) is to be delivered; the per user rate is 0:01 and the maximum delay tolerance is 100 time slots. If a speci c cell loss probability (as opposed to system dropping rate) is desired, then the cell loss probability can be derived as the ration of the system dropping rate and total arrival rate ( = 0:01N ). For example, for a maximum cell loss probability of 10?12, reducing the frame overhead length from 4 to 0 will allow to increase the number of supported users from N 78 to N 87, an increase of approximately equal to 11.5%. The (system) dropping rate under the RFFL-TDMA scheme is shown in Figure 8 as a function of the ( xed) frame length Lf ; the frame overhead is given by (Re = 2; In = 0) and T = 100. Figures 8-(a) and 8-(b) are obtained for N = 4 ( = 0:8) and N = 5 ( = 1:0) users, respectively; the per Bernoulli user rate is 0.2. Since the bounds on the dropping rate derived from the auxiliary systems FL and FU (Section 5) are very tight, only the lower bound is plotted. It can be observed that for a given set of supported applications there exists an optimal ( xed) frame length (namely Lf ) minimizing the induced dropping rate. This optimal frame length is, in general, di erent for a di erent set of supported applications, as illustrated in Figure 8. It should be noted that all results 16

dr vs

10

0

# of users

dropping rate (dr)

10

?2

10

?4

10

?6

10

?8

10

?10

ov

h er

10

?12

10

?14

10

?16

75

80

ov er ov he er ad he = ov ad 3 er = he 2 ad ov = er 1 he ad = 0

ea

85 90

d

=

4

95

100

# of users

Figure 7: Dropping rate versus number of users for the RVFL-TDMA scheme; maximum delay tolerance T = 100 time slots.

(a) λ=0.8, Total Overhead=2 10

0

(b) λ=1.0, Total Overhead=2 10

0

Dropping Rate (dr)

10

?5

Dropping Rate (dr)

10

?1

10

?10

* dr min

* drmin 10

?15

0

10

20

30 L*

f

40

50 Frame Length

60

70

80

90

100

10

?2

0

10

20

30

40

50 Frame Length

60

70 L*

f

80

90

100

Figure 8: Dropping rate versus frame length ( xed) for the RFFL-TDMA scheme; maximum delay tolerance T = 100 time slots. under the RFFL-TDMA scheme presented below are obtained for the optimal value of the ( xed) frame length Lf . The dropping rate under the RFFL-TDMA scheme employing the optimal frame length Lf is plotted in Figure 9 as a function of T and the values of the frame overhead (Re; In) = (1; 0) and (Re; In) = (2; 0). The results are shown in Figure 9-(a) and Figure 9-(b) for N = 4 ( = 0:8) and N = 5 ( = 1:0) Bernoulli users, respectively. Note that the case of zero frame overhead is not considered since in this case Lf = 1 and the resulting TDMA scheme becomes equivalent to the ICE-TDMA scheme. Results from Figures 9 and 6 are plotted together in Figure 10 to illustrate the improved performance induced by a variable frame (RVFL-TDMA) scheme compared to that of a xed frame (RFFL-TDMA) scheme. Figure 11 shows the dropping rate as a function of the number 17

(a) 4 Users, λ = 0.8

(b) 5 Users, λ = 1.0

10 0

dropping rate

10

0

10

-2

10

-4

10

-6

10

-8

dropping rate

e ov ea rh d

10 -1

ove ove

10

-10

rhe

e ov ea rh d

ad

=2

= 2

10

-12

rhe

= 1

10

-14

ad

=1

80 100

10

-16 10 0 20 40 60 80 100

-2 0 20 40 60

T

T

Figure 9: Dropping rate versus maximum delay tolerance (T) for the RFFL-TDMA scheme.

( a ) 4 users, λ = 0.8 10

0

( b ) 5 users, λ = 1.0 10

Dropping Rate

0

10

Dropping Rate

?5

10

?10

ove

ov

rhe

ad

=2

10

?1

10

?15

RVFL-TDMA RFFL-TDMA

ov

erh

ove

ea d= 2

rhe

ad

erh

=1

overhe

ad = 2

overhead overhead

=2

ea

d=

1

?2

RVFL-TDMA

overhead

RFFL-TDMA

=1

=1

10

?20

10

0

10

20

30

40

50

60

70

80

90

100

0

10

20

30

40

50

60

70

80

90

100

T

T

Figure 10: Dropping rate under RVFL-TDMA and RFFL-TDMA schemes versus maximum delay tolerance (T). of users under both the RVFL-TDMA scheme (results also shown in Figure 7) and the RFFLTDMA scheme. This gure illustrates the (positive) impact that allowing the frame length to vary on demand (instead of being xed) has on the maximum number of admitted users, when a certain level of QoS is to be delivered. As before (Figure 7), the users are Bernoulli with a per user rate of 0.01, the maximum delay tolerance is 100 time slots, and (Re; In) = (overhead; 0) (with overhead = 1; 2; 3). It can be noted that the gap between the schemes increases if the frame overhead length is increased or the required dropping rate is reduced (higher Quality of Service). When it is required to deliver a dropping rate of at most 10?16 , using the RVFL-TDMA scheme instead of the RFFL-TDMA scheme (for the same overhead) will increase the number of admitted users by up to a 10%. This gain decreases when the induced dropping rate is allowed to increase. When the required dropping rate is around 10?4 the di erence in the number of admitted users under both schemes will be around 3%. These gures ( Figures 10 and 11 ) quantify an important result of this paper. 18

10

?4

dr

10

?6

RVFL-TDMA RFFL-TDMA

10

?8

10

?10

10

?12

ad

=3

2

3

he

d=

Ov

he

ea

ad

er

he

erh

ea

d= erh

ad

10

Ov

er

Ov

10

?16 70

Ov

75

Ov

80

Ov

erh

85

ea d=

er

=

?14

=

1

2

1

90

95

Figure 11: Dropping rate under RVFL-TDMA and RFFL-TDMA schemes versus number of users; maximum delay tolerance T = 100 time slots. The relative performance of various TDMA schemes is shown in Figure 12 under various tra c environments: N = 6 Bernoulli users each of rate 0.15 ( = 0:9) are considered in case (a) and N = 5 Bernoulli users each of rate 0.20 ( = 1:0) are considered in case (b). N = 8 (N = 10) bursty users with total rate of = 0:8 ( = 1:0) are considered in case (c) (case (d)). A bursty user generates 0 or 10 cells per slot with corresponding probabilities 0.99 and 0.01, resulting in a rate of 0.1 cells/slot. Results are presented under the FF-TDMA scheme with Lf = N , the IVFL-TDMA (or ICE-TDMA) scheme and various RVFLk -TDMA schemes, where k represents the total overhead. The IVFL-TDMA scheme is the RVFLk -TDMA Scheme with k = 0 (no overhead). The FF-TDMA scheme with Lf = N models a TDMA scheme which allocates one slot to each user; no overhead is present since no communication between the users and the scheduler is necessary (similar to the TDM scheme used in the T-1 system for voice transmission). The results under this FF-TDMA scheme can be obtained by calculating the dropping rate for each user from the study of an FL system with parameters Lf = N; Re = N ? 1 and In = 0 and adding the results for all users. That is, each user may be viewed as being alone in a RFFL-TDMA scheme with overhead Re = N ? 1; In = 0. The IVFL-TDMA (ICE-TDMA) scheme - RVFLk -TDMA scheme with k = 0 - is the optimal scheme yielding the minimum possible system dropping rate. No slots are wasted under the IVFLTDMA (ICE-TDMA) scheme (no pre-allocation of slots) while user/scheduler information exchange is assumed without any overhead (k = 0). 19

No of users

0 10

(a) 6 users, λ = 0.9, regular

FF-TDMA RVFLk -TDMA

0 10

(b) 5 users, λ = 1.0, regular

FF-TDMA RVFLk -TDMA

dr

?5 10

dr

?1 10

k=5 k=6 k=0

?2 10

k=1 k=0

?10 10

50

100

150

T

200

?3 10

0

50

100

150

T

200

0 10

(c) 8 users, λ = 0.8, bursty

0 10

(d) 10 users, λ = 1.0, bursty

dr

k=8 k=0

FF-TDMA RVFLk -TDMA ?5 10 0 50 100 150

dr

?1 10

k=10 k=0

FF-TDMA RVFLk -TDMA 0 50 100 150

T

200

?2 10

T

200

Figure 12: Dropping rate (dr) versus maximum delay tolerance (T) under the FF-TDMA, RVFLk TDMA, and ICE-TDMA schemes for di erent tra c environments. The RVFLN -TDMA scheme (i.e. k = N ) considered in this gure assumes a contention-free request reservation scheme which utilizes Re = N full slots per frame. That is, each user has its own full slot for reservations; In = 0. Typically, it is expected that minislots (as opposed to slots) would be assigned to users for reservations yielding to a much smaller value of Re. The results under RVFLk -TDMA schemes are obtained by employing the auxiliary system L analyzed in Section 4. The results shown in Figure 12 demonstrate behavior anticipated from the insight and discussions presented in this paper. No scheme outperforms the IVFL-TDMA (ICE-TDMA) scheme under any system con guration. Under bursty tra c the FF-TDMA scheme is the poorest under all values of and T considered. Under the (less bursty, or more regular) Bernoulli tra c and rate = 1 the FF-TDMA scheme outperforms some of the RVFLk -TDMA schemes (for k 2), while for lower rates ( = 0:9) the FF-TDMA scheme is outperformed by the RVFLk -TDMA scheme for small k and/or large values of T .

7 Conclusions

A closed form expression was developed for the lower bound for the induced system dropping rate in a multiaccess TDMA networksupporting users with a common maximum delay tolerance. This 20

lower bound (result obtained for the ICE-TDMA and IVFL-TDMA schemes) depends only on the tra c characteristics. For various schemes that can be implemented in a TDMA network (IVFL-TDMA, RVFLTDMA and FF-TDMA) expressions were developed to compute tight bounds for the induced system dropping rate in each case. For the RVFL-TDMA scheme, it was found that for moderate arrival rates (less than 1 cells/slot) the frame overhead length has a signi cant impact on the achievable dropping rate. Thus, more e ort should be made to try to reduce this overhead length. A comparison between RVFL-TDMA and RFFL-TDMA schemes shows that for the same amount of overhead, the RFFL-TDMA scheme signi cantly increases the induced system dropping rate, degrading the performance. A comparison between the RVFL-TDMA with contention free reservation period and the FFTDMA shows that no one scheme outperforms the other in all cases; the formulas developed in this paper can be used to identify the best one for a particular case. Both schemes are far from the optimal, so there is room for signi cant improvement using techniques as for example piggy-backing of arrival information, or arrival times estimation.

21

Appendix

A Closed-form expression for the cell dropping rate as a function of the maximum delay tolerance under the ICE-TDMA Scheme

A.1 Computation of Pij :

Let ak be the number of cells arrived at Tk+ as explained in Section 2. Let l = P fak = g for = 0; : : :; n where n < T and l is assumed to be independent of k. The following cases are considered: Case 1 : (i = 0). If j 2 it is impossible that i = 0. If j = 1, since the system is busy, the only possibility is that ak = 0 . If j = 0 two possibilities exist, depending on whether there was one arrival (system busy) or zero (system empty).

8 >0 > if j 2 > < Pij = > l0 if j = 1 > > : l0 + l1 if j = 0

Case 2 : (1 i T ? 2). The system is busy so Pij = P fak = i + 1 ? j g = li+1?j .

8 < Pij = : li+1?j if j i + 1 0 elsewhere

Case 3 : (i = T ? 1). Here it is possible to have had j + ak ? T discarded cells. Thus, Pij = P fj + ak T g.

Pij = > > :

8 >0 > <

n X

d=T ?j

if 0 j < T ? n ? 1 ld if T ? n j

Thus, the T x T transition matrix is obtained:

22

< Pij >

2 l +l 6 0 1 6 l2 6 6 . 6 . 6 . 6 6 l 6 n 6 6 0 6 6 . 6 . 6 . 6 6 6 = 6 0 6 6 6 6 6 6 6 6 6 6 6 6 6 6 0 6 6 6 4

l0 l1

l0

. . .

0

0

:::

. . .

::: l0

0

ln?1 ln?2 : : : l0 ln ln?1 ln?2 : : :

0

:::

. . .

ln ln?1 ln?2 : : : l0 l1

. . .

::: :::

0 0 . . . 0 0 . . .

0

:::

0

ln

ln?1 ln

+

+ : : : ... +

ln

3 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 5

A.2 Computation of

to analyze the qualitative behavior of the system, a di erent approach can be followed. Let x = (1; x1; x2; : : :; xT ?1)t be a solution to equation Px = x. Then it is obvious that P ? = y x ) where y (T ) = T=01 xj . j T To compute x the rst T ? 1 equations are solved (the last one is redundant):

(

(steady state probability distribution): can be easily computed from the equation P = . But, since a closed form solution is desirable

0 0 . . . 0 0 . . . 0

= = = = = = =

(l0 + l1 ? 1)1 + l0x1 l2x0 + (l1 ? 1)x1 + l0 x2 . . . ln x0 + ln?1 x1 + : : : + (l1 ? 1)xn?1 + l0xn ln x1 + ln?1 x2 + : : : + (l1 ? 1)xn + l0xn+1 . . . ln xT ?(n+1) + : : : + (l1 ? 1)xT ?2 + l0xT ?1

From the above, the following are obtained: x = 1 ? l 0 ? l1

1

x2

. . .

x = (1 ? l1)l 1 ? l2x0 0 . = . .

l0

23

. . = . xi =

xi = (1 ? l1)xi?1 ? l2xi?2l ? : : : ? li?1 x1 ? li x0

0

if 2 i n if n i T ? 1

. . . (1 ? l1)xi?1 ? l2xi?2 ? : : : ? ln?1 xi?(n?1) ? ln xi?n

Let x(i) be an auxiliary sequence de ned as follows:

l0

Then it is easy to see that xi = x(i) for 0 i T ? 1. Taking the one sided Z-transform of x(i) in the previous equation : 0 + (l 1 + 1 1) ?1 X (z) = l + (l ? 1)lz ?1 +0lxz ?2 l+ ? z?z + : : : + l z?n l3 3 0 1 2 n

x(i) = 0 for i < 0 x(0) = 1 x(1) = 1 ? ll0 ? l1 0 (1 ? l1 )x(i ? 1) ? l2x(i ? 2) ? : : : ? ln?1 x(i ? (n ? 1)) ? ln x(i ? n) x(i) = l

0

for i 2

where

? ?1 = l + (l ? 1)z ?1 +l0l(1 ?2 z l )z ?3 + : : : + l z ?n = Dl(0z ) 0 1 2z + 3 n

D(z) = l0 + (l0 + l1 ? 1)z ?1 + (l0 + l1 + l2 ? 1)z ?2 + : : : + (l0 + l1 + l2 + : : : + ln?1 ? 1)z ?(n?1)

and from this expression x(i) and x are easily computed. P To compute yT the auxiliary sequence y (i) = ii?1 x(i0) is used. It is clear that yT = y (T ). 0 =0 Also y (i) = x(i ? 1) + y (i ? 1) for all i 1 and zero elsewhere; so taking the Z-transform :

Y (z) = z ?1 Y (z) + z ?1 X (z) 0z ?1 Y (z) = (1 ? lz ?1 )D(z)

Thus Y (z ), yT and are obtained.

A.3 Dropping rate dr (cells/time-slot).

dr (T ) = E f# cells dropped at t+ g = k

= Where u =

n?u X j =1 n?1 n?u XX u=1 j =1 n?1 X j =1

jP f j cells dropped at t+ g = k

Pn?1 u=1 u T ?u

n?1 X

j =1 i=j +1

j

n X

li

T +j ?i

jlu+j T ?u

=

jlu+j , and since (i) = yx((Ti)) :

24

? 1) + 2x(T ? 2) + : : : + n?1x(T ? (n ? 1)) = s(T ) y(T ) y(T ) The Z-transform of s(T ) is S (z ) = N (z )X (z ), where N (z ) = ( 1 z ?1 + 2 z ?2 + 3 z ?3 + : : : + n?1 z ?(n?1) ). Finally the dropping rate is given by:

dr (T ) =

1x(T

Thus a closed form solution is found. This method is computationally reliable and simple. It is reduced to the calculation of the impulse response of two In nite Impulse Response (IIR) lters. It provides for not only a quantitative evaluation of the dropping rate, but also describes its qualitative behavior by considering the poles of the lters. The following observations can be made regarding the roots of D(z ) for l0 + l1 < 1 :

N (z) N (z)X (z)]?1 = l0 D(z) dr (T ) = Y (z)]?1 Y (z)]?1

h

i?1

i) Since all the coe

cients of D(z ) are negative except for l0, then for every z0 2 C , Re D(z0)] D(jz0j) with equality only if z0 2 R+ . The sets C and R+ represent the set of complex numbers and the set of positive real numbers, respectively; the functions Re :] and j:j represent the real part of a complex number and its absolute value, respectively. Thus, D(r) has one and

ii) For every r 2 R+ the function D(r) is real and strictly increasing. iii) If r ! 0+ then D(r) ! ?1; and if r ! +1 then D(r) ! l0 > 0.

only one real positive root, namely rd .

iv) For any root ri of D(z) di

erent than rd , jrij < rd . Proof: Consider there is a root di erent than rd such that jrij rd . From iii) ri is not real positive, so applying i) as inequality (equality only holds for real positive numbers) : Re D(ri)] > D(jrij) D(rd ) = 0. The last two equalities came from ii) and iii) respectively. Finally, there is a contradiction because D(ri) is suppose to be equal to zero, but its real part is greater than zero. Thus, the initial assumption that there exists a root ri of D(z ) such that jrij rd is false.2

From all the above, it is concluded that the dominant pole of both lters will be rd (real and positive). P Let be the mean arrival rate: = n=0 l . Three cases could be considered: Case 1 : ( > 1). D(1) = 1 ? < 0 and if r ! +1 then D(r) ! l0 > 0 then for continuity there exist some 1 < rd such that D(rd) = 0. This means that the dominant pole for N (z )X (z ) and Y (z) will be rd > 1; and for T large enough (so that the other poles' contributions can be ignored) T they both will behave as exponential functions (that is rd ). Their quotient (the dropping rate) will tend to a constant value. Thus, for > 1 it is expected that the dropping rate will begin at dr (1) = l0 + ? 1 and will decrease to dr(T ) ? 1 when T ! +1. 25

Case 2 : ( = 1). Since for = 1, S (z ) = l0 =(z ? 1) and s(T ) = l0 for T 1 and zero otherwise. Thus the dropping rate only depends on Y (z ). In this case Y (z ) is equal to:

?1 z N (z) = z D(?)z+ 1 ? 1] 1 ?

Finally,

z ?2 l0 Y (z) = (1 ? z ?1 )2 N (z) Then, for T large enough, y (T ) 1 (T + 1) and then dr T +1 with 1 = Nl(1) and 2 = N (1) = P E fak g?E fak g E fak g?1 = 2 = 2l ; where l2 = n=0 ( ? 1)2lu is the variance of the arrival distribution. 2

2 0 2 2 2

2(T + 1) Case 3 : ( < 1). D(0+) ! ?1, D(1) = 1 ? > 0 then the only real root of D(z ) (the dominant pole) will be rd < 1. The closer to 1, the closer rd to 1. As explained before, all the other roots of D(z ) have absolute values less than 1, then for T large enough yT limz!1 (1 ? z ?1 )Y (z ) = l0=D(1) = l0=(1 ? ). Then,

dr (T )

l

2

dr (T )

T rd

Where is a constant equal to = (1 ? ) limz!ri (1 ? riz ?1 ) N (z )=D(z )]. Thus, the dropping rate as a function of T and the tra c characteristics (l ) has been calculated and its qualitative behavior has been analyzed.

B Computation of the function P ( )

j

Since fAj ( )gj =0 is a cumulative arrival process (see Section 3.1) with independent increments, Aj ( 0 ) = A1(1) + Aj?1 ( 0 ? 1) for 1 0 j . Let 00 be equal to 0 ? 1. Then:

Aj ( max A ( 1 0 j j

By employing the above,

0) ? 0 = 0) ? 0 =

Aj?1 ( 00) ? 00] + A1 (1) ? 1; and A1 (1) ? 1 + 0 max?1 Aj?1 ( 00) ? 00: 00 j

m(j ) = A1 (1) ? 1 + maxf0; 1 max?1 Aj?1 ( 00) ? 00g = A1(1) ? 1 + maxf0; 1 max?1 Aj ( 00) ? 00g 00 j 00 j m(j ) = A1(1) ? 1 + maxf0; m(j ? 1)g

thus,

P fm(j ) = g =

n X

=0

P fA1 (1) = gP fmaxf0; m(j ? 1)g = + 1 ? g

26

and since P fmaxf0; m(j ? 1)g = 0 g = Pj ?1 ( 0 ), then

P fm(j ) = g =

Finally,

8 > > > < Pj ( ) = > > > : 8 > > > < = > > > :

n X

=0

P fA1 (1) = gPj?1 ( + 1 ? )

elsewhere Pminfn; +1g l Pj?1 ( + 1 ? ) if 1 =0 l0Pj?1 (0) + l0 Pj?1 (1) + l1Pj?1 (0) if = 0 0 elsewhere (i.e. zero always except at P0 (0) = 1) are

P fm(j ) = g if 1 P fm(j ) = 0g + P fm(j ) = ?1g if = 0

0

This recurrent formula and the fact that P0 ( ) = used to calculate Pj ( ) and then dI (T ). r=j

C Dropping Rate under the FL system

^ ^ Let Ak ( ) and Bk ( ) be de ned as before (Sections 3, and 4). Note that since in a RFFL-TDMA ^ Scheme there may be `remaining' cells from the previous services cycles, the initial value of Bk ( ) may not be zero as before but equal to:

FL ^ Bk (0) = maxf0; Bk?1(Lf ) + Re + In ? Lf g

^ ^ Note that Bk (0) is completely de ned by Bk?1 (0) and the arrivals during the (k ? 1) ? th ^ service cycle. Since the arrivals are assumed to be memoryless, fBk (0)g is a discrete Markov chain with transition probabilities

FL ^ ^ Pij = P fBk (0) = i=Bk?1 (0) = j g

The number of cells waiting for slot assignment slots into the (k-1)-th service cycle is equal ^ to the sum of the Bk?1 (0) cells remaining at the beginning of the previous service cycle plus the ^ Ak?1 ( ) new arrivals. The number of surviving cells slots into the (k ? 1) ? th service cycle, ^ Bk?1 ( ), will not be limited by a line of the type f = + T ? Lk?1 as before (section 3.2, Figure 4), but by a more complex one, as computed below and shown in Figure 13. Let f FL denote the maximum possible number of surviving cells up to time . If f FL is expressed as follows

f FL = (Lf ? Re ? In) +

where is an integer and 1 Lf ? Re ? In, then it is clear that the last of these f FL cells would be served at the (k + ) ? th service cycle. In order for this cell to be completely served 27

fL

FL

f

β=0

β=1

L f - In-Re

β=1

FL

In+Re

f0

^ Bk-1(0)

^ Bk-1( τ )

fτ

FL

Lf

τ

^ Figure 13: Number of 'surviving' cells Bk?1 ( ) among the cells arrived up to time tg ?1 + for the k RFFL-TDMA scheme. it will have to wait the Lf ? Re ? time slots necessary to end the (k-1)-th service cycle plus the (1 + )(Re + In) slots of overhead periods plus f FL time slots. This time must be less than T time slots, resulting in the following condition :

Lf +

+ T ? Lf ? In and must be assigned the

Since f FL is the maximum possible number of surviving cells, maximum possible values, therefore : $ % + T ? Lf ? In ? 1 =

Lf = minf + T ? (1 + )Lf ? In; Lf ? Re ? Ing Where bxc represents the greater integer lower than or equal to x. The rst equation holds since is at least 1. The second equation holds since is (by de nition) at most Lf ? Re ? In. These equations de ne f FL as a non decreasing sequence that alternates periods of unit increments (for Lf ? Re ? In time slots) with periods of non increments (for Re + In time slots), and so on. Let is 1 (0) if the function f FL has represent the amount of increment of the sequence f FL . increased (not increased) at time , that is, = f FL ? f FL1 (see Figure 13). ? FL (T ), the following procedure is used: First, the steady To evaluate the dropping rate dr FL ^ state probability distribution function of fBk (0)g, namely FL is calculated. Second, dr=B the B conditional expected number of cells dropped at the beginning of the present frame (k ? th) given ^ that the number of surviving cell (Bk?1 (0)) at the beginning of the previous frame ((k ? 1) ? th) is equal to B is calculated. Third, the dropping rate is computed from the following expression: Pf F L FL FL B =0 dr=B B FL (T ) = (3) dr Lf

0

28

C.1 Computation of

FL i

^ ^ Let PB FL (i; j ) = P fBk?1 ( ) = i=Bk?1 (0) = j g similar as before (section 3.2); then it follows:

8P > n=0 l PB FL1 (i ? ; j ) > > ? <P FL (i; j ) = n (Pn l )PB FL (i ? PB = ?1 =0 > > >0 :

if i < f FL ; j ) if i = f FL elsewhere

with the initial conditions:

8 < 1 if i = j FL PB0 (i; j ) = : 0 elsewhere

FL Using this recurrent formula, PBLf (i; j ) is computed and then:

8 < PB FL (i + L ? Re ? In) if i 1 FL f Pij = : PLfL?Re?In f FL 0 PBLf (i ; j ) if i = 0 i0

FL FL FL ^ The matrix < Pij > with dimensions f0 x f0 is used to compute FL = P fBk (0) = B g. B FL C.2 Computation of dr=B FL A similar approach to the one followed in section 3.1 and appendix B is employed to compute dr=Q. Let the auxiliary quantity mFL ( ) be rede ned as: ^k

mFL ( ) = ^k

Lf ?

FL ^ ^ max L f Ak?1 ( 0) ? Ak?1 (Lf ? )] ? f FL ? fLf ? ]g 0 0 f

Then, it is straightforward to show that the number of dropped cells at tg is equal to: k ^r;k ^ dFL = maxf0; mFL(Lf ) + Bk?1 (0) ? f0FL g; ^k and also

mFL ( ) = maxf0; mFL( ? 1) + aLf ? +1 ? ^k ^k

Lf ? +1 g

FL FL ^ ^ where aLf ? +1 = Ak?1 (Lf ? + 1) ? Ak?1 (Lf ? ), and Lf ? +1 = fLf ? +1 ? fLf ? represent the number of cell arrivals and the amount of increment of the sequence f FL at time tg ?1 + Lf ? + 1, k respectively. Let PjFL ( ) = P fmFL (j ) = g ; then the following recurrent formula holds: ^k

8P > n=0 l P FL ( + j ? ) > if 1 > j ?1 < FL ( ) = Pj > l0Pj ?1 ( j ? 1) + l0Pj ?1 ( j ) + l1Pj ?1 ( j ? 1) if = 0 > > :0 elsewhere

29

with initial conditions:

8 < P0FL (i) = : 1 if i = 0 0 elsewhere

and where j = Lf ?j +1 ; or similarly: 8 < 0 if T ? In ? 1 ? ( 0)Lf j=: 1 elsewhere FL Then, dr=B can be computed as follows:

FL dr=B =

+1 X

j T + Re ? ( 0)Lf for some 0 integer

^r;k ^ E fdFL=Bk?1 (0) = Bg

d=1

=

+1 X

=

d:P fmFL (Lf ) = d + f0FL ? Bg = ^k

FL dr=B

d=1 +1 X

^r;k ^ d:P fdFL = d=Bk?1 (0) = Bg

FL d:PLf (d + f0FL ? B)

Finally, the dropping rate is computed from using equation (3). Alternatively, equation (6) could be used (see Appendix D.3) but it may be numerically unreliable.

d=1 and FL B

D Alternative expression for the dropping rate

The following subsections introduce some expressions to compute the dropping rate under the IVFL-TDMA scheme, auxiliary system L, and auxiliary system FL based in the values of I , L , i i and FL respectively. These equations require lesser computation e ort than equations (1), (2) i and (3) because they do not require the computation of dI , dL , nor dFL. However, a major r=i r=i r=i drawback in the use of these equation is that, in general, they are not numerically reliable (require the substraction of two quantities that are too close to each other). For this reason they were not used for the derivation of the numerical results.

D.1 IVFL-TDMA scheme

The following expression may also be used for the calculation of dI (T ): r where E fLk g and are the expected frame length and number of arrivals per time-slot (arrival rate), respectively; Pe is the probability that a frame is empty and it is given by:

Pe dI (T ) = E fL g ? (1 ? ) r k

(4)

Pe = P fnext service cycle is emptyg

= =

T X i=1 T X i=1

P f0 arrivals at k-th cycle/ Lk = igP fLk = ig

(l0)i I i 30

Proof : Since cells are either dropped or served, the Utilization(U), the dropping rate (dr ) and the arrival rate ( ) are related by: U + dr = . Also, since the system is either busy or empty, and the empty rate is equal to Pe =E fLkg: U + Pe =E fLk g = 1. Combining these two equations gives the above expression for dr :2

D.2 RVFL-TDMA scheme

The following expression may also be used for the calculation of dL (T ): r dL (T ) = Re + In ? (1 ? )

r

E fLk g

(5)

where E fLk g and are the expected frame length and number of arrivals per time-slot (arrival rate), respectively; Re and In are the length of the Reservation and Information periods. Proof : Since cells are either dropped or served, the Utilization(U), the dropping rate (dr ) and the arrival rate ( ) are related by: U + dr = . Also, since a slot is user either to reservation, information, or cells transmission, then : U + Re+In = 1. Combining these two equations gives the E fLk g above expression for dr :2

D.3 RFFL-TDMA scheme

The following expression may also be used for the calculation of dFL (T ): r dFL (T ) = Re + In + Se ? (1 ? )

r

Lf

(6)

where Lf and are the frame length and number of arrivals per time-slot (arrival rate), respectively; Re and In are the length of the Reservation and Information periods. Se is the expected number of empty time slots in a frame and it is given by:

Se = E fnumber of empty time slotsg

= =

Lf ?Re?In?1 X i=0 Lf ?Re?In?1 X i=0

^ (Lf ? Re ? In ? i)P fBk?1 (0) = ig (Lf ? Re ? In ? i) FL i

Proof : Since cells are either dropped or served, the Utilization(U), the dropping rate (dr ) and the arrival rate ( ) are related by: U + dr = . Also, since a slot is user either to reservation, In information, cells transmission, or is empty; then : U + Re+Lf +Se = 1. Combining these two equations gives the above expression for dr :2

31

References

1] D. C. Cox, \Wireless Network Access for Personal Communications", IEEE Comm. Mag., 30(12), pp. 96-115, Dec. 1992. 2] I.M. Leslie et al., \ATM Everywhere"" , IEEE Networks, pp 40-46, March 1993. 3] B. Walke et al. , \Wireless ATM: Air Interface and Network Protocols of the Mobile Broadband System", IEEE Personal Communications Mag., 3(4), pp. 50-56, August 1996. 4] D. Raychaudhuri and N. Wilson. \ATM-Based Transport Architecture for Multiservices Wireless Personal Communication Network". IEEE Journal of Selected Areas Communications, 12(8):1401-1414, October 1994. 5] K.Y. Eng, M. Karol, and M. Veeraraghavan. \A Wireless Broadband Ad-Hoc ATM Local Area Network". ACM Wireless Networks Journal, 1(2), December 1995. 6] P. Mermelstien, A. Jalali, and H. Leib. \Integrating Services on Wireless Multiple Access Networks". In Proceedings of ICC, pages 863-867, March 1993. 7] D. Petras et al. \MAC Protocol for Wireless ATM: Contention Free versus Contention Based Transmission reservation Request". In proceedings of PIMRC, Taipei, Taiwan, October 1996. 8] M. Karol, Z. Liu, and K. Eng. \An E cient Demand-Assignment Multiple Access Protocol for Wireless Packet (ATM) Networks". Wireless Networks, 1(4):267-279, December 1995. 9] A. Mahmoud, D. Falconer, and S. Mahmoud. \A Multiple Access Scheme for Wireless Access to a Broadband ATM LAN Based on Polling and Sectored Antennas". IEEE Journal of Selected Areas Communications, 14(4), May 1996. 10] C. Chang, K. Chen, and M. You. \Guaranteed Quality of Service Wireless Access to ATM networks". In ICC, Dallas, Tx. June 1996. 11] N. Passas, L. Merakos, and D. Skyrianoglou. \MAC Protocol and Tra c Scheduling for Wireless ATM Networks". To appear in ACM Mobile Networks and Applications Journal, special issue on Wireless LANs, 1998. 12] D. Bantz and F. Baucho. \Wireless LAN Design Alternatives". IEEE Networks Magazine, 8(2):43-53, March-April 1994. 13] S.S. Panwar et. al., \Optimal Scheduling Policies for a Class of Queues with Customer Deadlines to the Beginning of Service" , Journal of the ACM, pp. 832-844, 1988. 14] G. Chen, I. Stavrakakis.\ATM Tra c Management with Diversi ed Loss and Delay Requirements ". In Infocom, San Francisco, California. March 1996.

32

All rights reserved Powered by 江苏七位体彩开奖结果 江苏七位体彩开奖结果 www.jwbw.net

copyright ©right 2010-2021。

文档资料库内容来自网络，如有侵犯请联系客服。[email protected]

copyright ©right 2010-2021。

文档资料库内容来自网络，如有侵犯请联系客服。[email protected]