COMPARING AND CLASSIFYING MAC PROTOCOLS

Historically, ALOHA was the first MAC protocol offered for packet radio networks, proposed in Abramson (1970). It is classical free (random) access protocol. Unfortunately, the maximum throughput of this protocol is only 1/2 e . Some two years later, Roberts (1972) offered the well-known slotted ALOHA , which doubles the efficiency of ALOHA. The next fundamental contribution to MAC techniques was made by Kleinrock and Tobagi (1975), who developed several carrier-sense protocols CSMA. In 1969, Markhasin proposed and analyzed some multi-access methods in such classes as slotted and non-slotted ALOHA and CSMA. There also the slotting effect about protocol efficiency increasing was opened and proved for the first time. The majority of other classical free, controlled, and hybrid access methods were also published in the 1970s.

The radio and satellite MAC protocols classification was considered in many publications including Markhasin (1979, 1984), Rubun (1979), Tobagi (1980), Rothhauser and Wild (1977), Peyravi (1999), and Abramson (2000). In this section the idea of the MAC matrix classification of Markhasin (1979) will be extended. This classification table is well suited to the QoS-oriented long-delay MAC requirements.

A MAC Protocol Matrix Classification

A MAC matrix classification is based on two fundamental characteristics of MAC protocols, as illustrated in Table 1:

• media access regulation mechanisms ‚the strings of the matrix, and

• media access time processes ‚the columns of matrix.

According to this classification the (5 ƒ” 4) matrix of MAC protocols , whose elements satisfy a number of conditions, can be described as follows :

• The rows define five media access regulation mechanisms :

  1. centralized controlled access mechanism (CCA),

  2. distributed controlled access mechanism (DCA),

  3. carrier-insensitive free access mechanism (IFA),

  4. carrier-sensitive free access mechanism (SFA),

  5. hybrid access mechanism (HYA), i.e., combined free/ controlled access mechanisms for signaling/data packets.

• The columns define four media access time processes :

  1. stochastic continuous time process (CTP),

  2. stochastic define frame discrete time process (DTP),

  3. stochastic adaptive frame discrete time process (ATP),

  4. fixed (deterministic) discrete time process (FTP).

According to the way MAC instructions are processed we distinguish:

1. serial MAC instructions processing (SIP),

2. parallel MAC instructions processing (PIP),

3. parallel-conveyer MAC instructions processing (CIP),

4. not-used MAC instructions dynamically processing (NIP).

We note here that the completely free ALOHA belongs to subclass NIP; the same holds for the completely determined fixed access methods (without use MAC instruction dynamically).

According to the bandwidth resources normalized costs (4) on MAC we define:

1. Small MAC expense (SME), if v _o 0.02,

2. Moderate MAC expense (MME), if 0.02 v _o 0.10,

3. Large MAC expense (LME), if v _o 0.10.

Comparing MAC Protocols

A comparison in terms of delay characteristics

Table 2 illustrates a possible comparison of MAC protocols in terms of short-delay versus long-delay characteristics. Specifically, a MAC protocol is termed short-delay if the MBD is smaller than 10 bits. The MAC protocol efficiency criterion was defined in equation (2). It stands for the maximum value of the throughput S and by input traffic intensity G variation. The real throughput is defined by the additional limitation to delay D (see Figure 4a) or other parameters of the variations fields as

It is shown in Markhasin (1979, 1984) that the highest short-delay efficiency (see Table 2a) ensures the adaptive protocols with controlled access mechanisms (DCA or CCA), adaptive frame time processes (ATP), and small MAC expenses (SME). The same protocols with parallel-conveyer MAC instruction processing (CIP) ensure the best time barrier overcoming ability .

A comparison in terms of potential efficiency

As we saw, the values of efficiencies of the defined ij -th MAC protocols is dependent on their access mechanisms, time processes, and cost (4) on organizing of multiple access. What is the minimum reachable cost of distributed MAC protocols and what is the maximum reachable efficiency, or potential capacity, of the ideal MAC protocols? Markhasin (1989) noted that the minimum reachable value of these expenses can be defined as entropy of the distributed multiple access processes used the Markov models of the distributed queues. Specifically, he following theoretical results were proved there:

Theorem 1

If the TDMA system is described by model ideal (potential reachable) queue of kind M/M/1, then the values of minimum reachable expenses on distributed MAC organizing equal

and the potential capacity of the ideal MAC protocol equals

where T _INF is average duration of information's time slot (traffic packet or cell burst), B is bit rate, and H ( k ) is entropy of the packets' duration distribution, for the geometrical distribution

where parameter x = exp( 1/ _INF B ).

 

Theorem 2

If the TDMA system is described by model ideal (potential reachable) queue of kind M/D/1, then the values of minimum reachable expenses on distributed MAC organizing equal

and the potential capacity of the ideal MAC protocol equals

 

A comparison in terms of QoS-provisioning capabilities

Table 3 provides a comparison of MAC protocols in terms of their QoS-provisioning characteristics. The following criteria were assumed:

• for statical QoS control ‚as its characteristics of the controllability, differentiation , and guarantee by the QoS control and bandwidth resources assignment;

• for dynamic QoS control ‚adding to static criteria dynamic efficiency and stability by the dynamic ( on-the-fly ) QoS control and bandwidth assignment.

A comparison in terms of all-IP/ATM capabilities

Table 4 provides a comparison of MAC protocols in terms of their all-IP/ ATM architecture support capabilities. The following criteria were used:

• about economic barrier overcoming ‚as its achievable area sizes of the completely distributed and homogeny broadband ATM bus architecture , which this MAC protocol supported;

• about all-MPLS/ATM ‚as its abilities to the long-delay ATM multifunctional and universal characteristics trough all networks' hierarchy ‚ core , backbone, and access ‚on the base of the common dynamically controlled and adapted ATM MAC protocol high effectively to support.

The best ability to overcome the economic barrier and best compatibility to all-MPLS/ATM requirements ensure the adaptive protocols with DCA, ATP, and SME. Such adaptive method of long-delay multifunctional ATM MAC will be considered in the next section.

The QoS-Oriented Long-Delay ATM MAC Control Technology

The main goal of this section is to investigate QoS-oriented long-delay MFMAC technology, based on TBR-RS protocol developed in Markhasin (1985, 1988, 1996). This technology uses the recurrent M-sequences ( RS ) with the stated goal of effective implementation of the main MAC mechanisms. The TBR-RS protocol used DCA, ATP, and SME. It ensures a completely distributed dynamic control of QoS simultaneously and opens promising possibilities for all-MPLS/ATM wireless architecture.

This proposed MAC method allows obtaining effective solutions to the above-considered barriers problems. According to this method the number of information ATM cells in M -periodical hyperframe is adapted to the current traffic automatically ‚ see Figure 4b, the graph of a function TBR for TBR-RS protocol. The parallel-conveyer processing of MAC instruction (CIP) is used. According to equation (6), the efficiency of this method equals

that is, this method allows one to closely approximate the potential capacity (see equation (11)) of TDMA (up to 0.95, 0.99) and also its normalized MAC cost approach to minimal value (10). The dependence of the access efficiency on the propagation time, which shows itself only as a transport delay, is practically excluded.

QoS-Oriented Long-Delay ATM MAC RS-Token Broadcast Reservation (TBR-RS)

QoS-oriented ATM MAC based on TBR-RS

A broadband long-delay ATM network with a virtual bus topology (passive or active tree, U -like bus, and the like) is considered. Assume that at some time t N _t stations (users) NU _i are active with streams of ATM cells being input into them with the traffic intensities U _ikt . For the i ^th station and k ^th service class, the following required values [ X ] defined by means of equations or upper/lower limits must be provided: peak [ P _ikt ] and mean [ M _ikt ] rates, average delay time [ D _ikt ], loss probability [ R _ikt ], possibly root-mean-square deviations ’ _{[ X ]} from the required values [ X ], X = P, M, D, R , and other service quality indices. The main mechanisms of QoS control are the bandwidth resource Y _it , i = 1, ‚ , N , among the stations and also the priority parameters of k ^th service class.

Two types of ATM blocks are introduced as illustrated in Figure 5: control mini-blocks (CB) and information blocks (IB). The control mini-blocks contain a 16-bit preamble PLP_C and an 8-bit access control field MAC_C, including an address bit a _j and the request r _ik of the i ^th station for a block transmission from some number n _k = 0, 1, ‚ , [ n _kt ] of ATM cells of the k ^th service class. The information blocks include a preamble PLP_I, a field LLC_ I _j , and a variable number n _kt of ATM cells.

Figure 5: Adaptive RS-addressing and format of the ATM cells

The RS-token broadcast reservation protocol described in Markhasin (1985, 1988) is used for completely distributed MAC. It is executed in a parallel, decentralized way and on a parity basis by each activated network station. Based on the requests r _ik listened to in the broadcast channel, each station divides the time axis using the common deterministic algorithm of parallel request processing into equidistant time intervals [ t _j , t _{j +1} ), j = 1, ‚ , M, M = 2 ⁿ 1 within the RS period, which contain a control mini-block (CB _j ) and, if there is information, an information block (IB _j ), labeled by the identifiers.

Main RS-based MAC mechanisms

Quasi-random M -subsequences A _j = A _{j ( m 1)} , a _{j ( m 2)} , ‚ , a _j of length m, m ° n , serve as identifiers (as seen in Figure 5). The identifiers A _j are ordered into a logical ring by a recurrent law in such a way that shifted by one position the bits of contiguous identifiers coincide save, excluded the first bit a _{j m} of the preceding and the last bit a _j of the succeeding identifier on the ring. The latter plays the role of address bits a _j in the address fields of the control mini-blocks, and the current values A _j are recognized by accumulation address bits a _j (RS self-synchronization).

Some number m _it ° [ Y _it ] of "personal" identifiers A _jit defined by

for passing of requests r _ik in proportion to the required bandwidth resource value [ Y _it ] is dynamically assigned to the i ^th station on a decentralized basis. Subset (15) is the dynamic address of the i ^th physical channel. The procedures of proportional dynamic division of the identifier set { A _j } into i ^th subsets { A _jit } and the recognition of the latter (adaptive addressing procedure of Markhasin, 1988) are easily implemented with the help of special keys ‚station names U _it . The station names U _it which as suggested in Markhasin (1988) can be encoded by optimum non-uniform codes on the basis of the normalized values [ Y _it ] of the required resources by the Shannon-Fano method. The functions of processing the requests of the stations for bandwidth resources Y _it and U _it name encoding are assigned to the network administrator.

To support the required k ^th service classes, the mechanism of priority segments [( j l _kt ), j ) is used, M ° l _Kt ° ‚ ° l _kt ° ‚ ° l _{2 t} ° l _{1 t} = 0.

Thus, in case of ATM, low-cost, effective, and reliable mechanisms of positional addressing with respect to A _j and control can be constructed .

All activated stations process in parallel the requests listened to "down" the broadcast channel using a single deterministic algorithm of completely distributed access control, whose space-time diagram is shown in Figure 6.

Figure 6: Space-time diagram of long-delay TBR-RS MAC with parallel processing

In so doing, they monitor in parallel the current values of the RS-addresses A _jt and the unified system time, distribute time intervals with respect to requests, calculate the address A _{jt + z} and the start time t _{jt + z} of the closest unoccupied interval, and control the presence at the priority segments [( jt l _kt ), jt ] of at least a single request for k -th class information transmission. Having recognized a personal address A _jit , the i ^th station passes a request r _ikt if it has a cell ready for transmission or the negative request r _{i ƒ t} otherwise .

If there are no requests of higher priority at the priority segments [( jt l _kt ), jt ), k < k _it then to serve the request r _ikt each station, including the i ^th , allocates equidistantly the closest unoccupied interval [ t _{jt + z} , t _{jt + z +1} ), satisfying the condition t _{jt + z} t _jt ° t _p . Otherwise all stations block in a coordinated manner the low priority request r _ikt and the i ^th station repeats the request at the closest interval marked with its personal address (15).

Dynamic Control Problem of Traffic and QoS

The dynamic control problem manifests itself, on the one hand, in an abrupt increase in terms of requirements to dynamic operation, accuracy, adaptability, and effectiveness of the control of the traffic parameters and service quality; on the other hand, in an abrupt complication of control tasks . A multifunctional longdelay ATM network is considered. Assume that at some time t N _t ATM s tations NU _i are active with streams of ATM cells being input into them with the traffic intensities , C is channel capacity. For each i ^th station and k ^th service class the following required values [ X ] defined by means of optimal value or upper/lower limits must be provided: peak [ P _ikt ] and mean [ M _ik ] rates, average delay time [ D _ik ], loss probability [ R _ik ], possibly root-mean-square deviations s _{[ X ]} from the required values [ X ], where X = P, M, D, R , and other service quality indices.

The above-described TBR-RS adaptive multiple access method opens up new possibilities for this dynamic control problem. The same mechanisms of adaptable RS-addressing (15) are used then for dynamic QoS control as for MAC. The suggested method gives an opportunity to ensure a proportional dynamic control of the bandwidth resources with a dynamic bandwidth utilization up to 0.75, 0.85. The dynamic control strategy can be constructed on a centralized as well as on a decentralized game basis. An example of a centralized control strategy is the task of weighted average delay minimization.

Let the traffic intensities G _ikt and the dependencies X _ikt ( Y _t , L _t ) of the indices X = D, P, M, R on the vectors Y _t = ( Y _{1 t} , ‚ , Y _it , ‚ , Y _Nt ) of the values of the reserved resources and the priority segments parameters L _t = ( l _{1 t} , ‚ , l _kt , ‚ , l _Kt ) are given. For a given interval t ‚² < t < t ‚² ‚² such legitimate values of the vectors Y _t and L _t must be found that minimize the weighted with certain weights h _ikt delay time:

with constraints of the form: D _ikt ( Y _t , L _t ) ° [ D _ikt ], R _ikt ( Y _t , L _t ) ° R _ikt , P _ikt ( Y _t , L _t ) ° [ P _ikt ], M _ikt ( Y _t , L _t ) ° [ M _ikt ], i = 1, ‚ , N _t , k = 1, ‚ , K _t .

In the decentralized strategy the control actions, the reserved resources Y _it , are generated on game basis by the users and are implemented by the network administrator with the help of a dynamic RS-addressing mechanism.

Next, we address the resource reservation game task proposed by Markhasin (1996). Assume that some measure of the k ^th class information cost per unit time H [ G _k , W _k ( Y )] as a function of its traffic intensity G _k and the vector of its delivery quality indices W _k ( Y ) = ( D _k ( Y ), R _k ( Y ), P _k ( Y ), M _k ( Y )), and also the tariffs per unit time for the resources T _Y and traffic T _Gk are given. Assume further that the i ^th users can keep track of the statistical estimates (averages) of the traffic intensity G _ikt and service quality W _ikt (Y _it ) with a given band resource value Y _it .

Some i ^th , i {1, 2, ‚ , N _t }, user must reserve for a given interval t ‚² < t < t ‚² ‚² such a legitimate bandwidth resource value Y _it that maximizes his "gain":

The users try to maximize their "gain" (17) by reserving resources Y _it and varying traffic intensities G _ikt (making "bets" Y _it and G _ikt ). Such procedures are simulated by noncooperative dynamic N -person games .

By changing the tariffs for resources T _Y and traffic T _Gk the network administrator can in his turn engage in playing with the users to maximize his own "gain":

The conditions (17) and (18) ensure self-regulation of the input traffics G _ikt , required parameters of the traffic and service quality [ W _ikt ] = ([ D _ikt ], [ R _ikt ], [ P _ikt ], [ M _ikt ]) and bandwidth resources Y _it for the k ^th class of information, the i ^th user and time interval [ t ‚² , t ‚² ‚² ).