Survey on Performance Evaluation Techniques for Medium Access Control Protocols

Ritun Patney, ritun.patney@gmail

Abstract
Medium Access Control (MAC) protocols, in data networks, are responsible for arbitrating access to a shared medium. This survey paper looks into the techniques and metrics used for evaluating these protocols. The most common performance metrics are delay and throughput, though in certain cases, like sensor networks, power consumption might also be an important metric. The paper focuses on three kinds of evaluation techniques: analytical modeling, simulation and practical experiments. The most common technique seems to be analytical modeling. We discuss the methodologies used in some of the papers from the literature.
Keywords: MAC, performance, analytical modeling, simulation, experimentation

Table of Contents

1. Introduction
    1.1 Open Systems Interconnection Model
2. Medium Access Control
    2.1 Aloha
    2.2 CSMA
    2.3 CSMA/CD
    2.4 CSMA/CA
        2.4.1 Hidden Node Problem
    2.5 IEEE 802.11
    2.6 MAC for sensor networks
    2.7 IEEE 802.16
3. Analytical Modeling Techniques of MAC Protocols
4. Simulation Studies
5. Experimentation Studies
6. Conclusion
References

1 Introduction


The paper is organized as follows. In section 1, we discuss the various network layers. In section 2, we look at the common Medium Access Control (MAC) protocols used. The next three sections discuss some of the analytical, simulation, and experimentation techniques used for performance evaluation of MAC protocols.

1.1 Open Systems Interconnection Model


The OSI model [11] is generally referred to as the OSI reference model (Figure 1). It presents an abstract model of network protocol layers and is helpful in the design of network protocols. Every layer provides some functions (interfaces) which are used by the layer above it. This structure is often referred to as a protocol stack.


                      Fig. 1 - OSI protocol stack

System designers working in one layer need not worry about the details of the layer below. This results in the stack being highly modular.

The OSI standard consists of 7 layers:
7. Application Layer - This is where the user applications are run. Some common applications are FTP, HTTP, etc.
6. Presentation Layer - Data in the network can be represented in many different formats. It can differ in the encryption used, MIME encoding, etc. This layer this presents the application layer a uniform interface by hiding these differences.
5. Sessions Layer - It is responsible for creating, maintaining and terminating connections between the local host and a remote host. It supports half-duplex or full duplex operation.
4. Transport Layer - This layer is responsible for providing the transportation of data between the source and the destination. The service can be connection oriented or connectionless. It also performs fragmentation and error control.
3. Network Layer - It is responsible for transferring packets between various networks. It provides for various routing decisions, as well as addressing and internetworking.
2. Data Link Layer - This layer is responsible for delivery of frames to the next hop destination. It also tries to correct any errors introduced by the physical layer. This layer is often divided into two layers: Medium Access Control (MAC) and Logical Link Control (LLC). LLC is responsible for frame synchronization, flow control and error checking. The MAC decides which node gets access to the channel and who transmits when.
1. Physical Layer - It deals with the actual transmission of bits over the medium in the form of electrical signals.

TCP/IP reference model - This is also referred to as the Internet reference model. Compared to the OSI model, it has fewer layers, but it provides an easy fit for real World products. The model defines 4 layers: Application layer, Transport Layer, Internetworking Layer, and the Network Access Layer.

2 Medium Access Control

As discussed previously it is responsible for controlling access to the channel amongst various entities. Its role is important in networks where multiple users can transmit at the same time over the same channel (Ethernet segment, same radio channel, etc.), such as IEEE 802.11, Bluetooth, etc.

Various MAC protocols have been defined in literature that employ different techniques to regulate access. They can be grouped into two categories: distributed and centralized. In the former, each node decides on its own when is the best time for it to transmit such that it is the only one which transmits to avoid collision. These are also referred to as random access protocols. If multiple nodes transmit, then these protocols provide mechanisms to resolve the collision.

In the centralized version, a node is responsible for deciding who can access the channel, and the duration for which that node has control over the channel. The centralized node is generally referred to as a base station (BS). There are two ways to provide access to other nodes. One is in a round-robin fashion. Here the BS would poll every node periodically to find if it has data to transmit or not. The other can be a Request-Grant mechanism wherein the nodes contend to send channel access requests to the base station. The BS then allocates a time slot for every node from which it would have received the request. The next section details out some of the commonly used MAC protocols.

2.1 Aloha

Aloha [1] [14] is based on the principle that if you have data to send, send it. If there is a collision then the protocol resends the data at a latter time. This leads to degraded channel utilization since multiple nodes may transmit at the same time. An improvement of this protocol is the slotted Aloha, as discussed in the next section. The finite state machine for this protocol is given in figure 2.


                     Fig. 2 - State Transition Diagram of Aloha

Slotted Aloha [17] is an extension of basic Aloha in which time is divided into discrete time slots. A node can only transmit at the beginning of these time slots. This helps in reducing collisions.

2.2 CSMA

This stands for Carrier Sense Multiple Access with Collision Detection. In CSMA, before transmitting, nodes listen for other traffic on the same shared medium. If they sense another node is transmitting, they withhold their transmission. Once the other node's transmission has finished, the waiting node may proceed to transmit. However, this still leaves a probability that multiple nodes may sense the channel idle and start transmitting simultaneously.

2.3 CSMA/CD

CSMA with Collision Detection (CD) [15] refers to the ability of the node to detect if and when a collision occurs. When this happens, the transmitting node immediately stops its transmission. It then calculates a random backoff time t, after which it tries to re-transmit its frame. Since multiple nodes each choose a different t, this technique helps sort the problem of collisions. This protocol is used in 802.3 networks.

2.4 CSMA/CA

Wireless networks do not employ CSMA/CD but employ CSMA/CA (Collision Avoidance) [16]. The reason is that in the former the collision is detected at the transmitter. However in wireless networks, it is important to detect collisions at the receiver side due to the hidden node problem.

2.4.1 Hidden Node Problem

Assume node A in figure 3 wants to transmit to B. Also, node C wants to transmit to B. Node A does carrier sensing and decides the medium is free and starts its transmission to B. The transmission from node A can reach node C but it can not reach node C. Hence when C does carrier sensing, it also assumes the channel to be idle and starts transmitting for B. This causes a collision to occur at B. Authors in [4] propose solving this problem by the use of a two-way handshake. It requires the exchange of Request to Transmit (RTS) and Clear to Transmit (CTS) packets between the sender and the receiver. The sender first transmits a RTS and awaits a CTS packet before continuing with the transmission of data packets. RTS and CTS packets alert all other nodes in the range of A and B that a transmission is going to occur. Furthermore, they also contain the duration of the transmission hence no other nodes which have heard these RTS/CTS packets should attempt to transmit in this duration.



                 Fig. 3 - The circles show the communication ranges of the nodes at the centers.

2.5 IEEE 802.11

This standard [13] specifies the Distributed Coordination Function (DCF) which is based on CSMA/CA. A transmitter must wait for a channel to be idle for Distributed InterFrame Space (DIFS) amount of time before it can start to transmit. If the channel is sensed busy, either immediately or during the DIFS, it backs off its transmission by a random amount of time to avoid collisions. The time after the DIFS period is slotted and a node is allowed to transmit only at the start of a time slot.

The backoff scheme is exponential. The backoff time is uniformly chosen in the range (0, W), where W is the contention window (CW). W is variable in nature and its initial value (the first time a node has to backoff) is CWmin. Each time a node has to backoff for the same frame after the first backoff, it doubles the contention window. There is a CWmax, beyond which the window is not incremented.


                Fig. 4 - Distributed Coordination Function (DCF) with 4 stations

DCF (Figure 4) uses ACKs sent by the destination to judge whether a frame was successfully received or not. A maximum of 8 retries are allowed after which the frame is dropped from the interface queue.

Point Coordination Function (PCF) - This is a centralized MAC protocol which works over DCF. The BS polls mobile nodes (MN) periodically. To ensure PCF traffic has priority over the DCF traffic, the BS waits for Point InterFrame Space (PIFS) amount of time for the channel to be idle before transmitting, where PIFS less than DCFS.

2.6 MAC for sensor networks

Sensor-MAC (S-MAC) [10] - It has been designed for sensor networks where energy consumption is a major criteria. In S-MAC, a node sleeps for a certain period of time and is awake for a certain period of time. These periods repeat in cycles and the total time is the time taken to complete one cycle. Otherwise the protocol is very similar to the DCF protocol as described above as it uses RTS/CTS for hidden terminals, RTS/CTS/DATA/ACK cycle, randomized backoff time and carrier sensing. The basis of this protocol is not to overhear frames which are not destined for it. It does this by going to sleep. A node co-operates with its neighbors so as it knows when it can sleep and when it should be in the listening mode. Similar variants of these protocols exist: Timeout (T-MAC), and Berkeley (B-MAC).

2.7 IEEE 802.16

This is a standard for Metropolitan Area Networks (MAN). The network consists of a Base Station (BS) [12] and several Subscriber Stations (SS). A BS and multiple SS form a cell with a point to multipoint structure. The BS controls access to the air interface in its cell. Time is divided into frames and each frame consists of a downlink frame and an uplink frame. Access in the uplink frame is controlled by the BS and assigned according to a scheduling algorithm.

3 Analytical Modeling Techniques for MAC Protocols

In [9], authors analyze Time Division Multiple Access (TDMA) channels for transmitting data messages. Stations are assumed to have a fixed TDMA channel and the data messages arrive at the station with a Poisson distribution. The buffer capacity for queuing is considered unlimited. A packet is assumed to be the amount of data that can be transmitted in a TDMA slot. A message is thus broken down into packets. Firstly, the steady state probability generating function for the queue size is found. From this, a model for the delay is obtained. Assume there are M slots, each with a duration of T. Every station is idle for (M-1)T/M time before it can send another packet. The analysis follows a single server queue example with the arrivals at the rate of messages per second. The service time is a random variable having its value between T/M and (T + T/M). The expected message delay is found to be

L is the number of packets in a message which is a random variable given by a probability density function with L1 and L2 being the first and the second moments.

Bianchi [5] analyses the DCF of IEEE 802.l1. It is assumed that there are no hidden terminals in the network and is operating under a saturation condition (every node has a packet to transmit at all times). The paper first proposes a Markov model to find the probability that a station transmits in a randomly chosen slot. Markov chain model for the backoff window size is show in the Figure 5. The probability found is


where,
p = conditional collision probability
W = Contention window


Fig. 5 - Markovian Model for backoff window. p is the probability with which each packet collides and is a constant and independent

The next part of the analysis deals with finding an expression for the throughput. S is the normalized system throughput which is the fraction of the time the channel is used to transmit payload bits. S is expressed as,




So far, no access mechanism has been taken into consideration. To do so, the author calculates E[P], Ts, Tc, and in terms of SIFS, DIFS, and (the propagation delay). The values are for Ts and Tc when RTS and CTS is considered are given below.
Ts = RTS + SIFS + + CTS + SIFS + + H + E[P] + SIFS + + ACK + DIFS +
Tc = RTS + DIFS +
H is the packet header and equals the physical layer and the MAC layer headers.

In [6], the authors analyze the 802.11 protocol using an approach based on system approximation. Here, the protocol's statistical characteristics are analyzed and then approximated by an appropriate distribution. Then a queuing model is constructed. Firstly, a general model which assumes there are k stations wanting to transmit on a shared medium is assumed that uses a MAC protocol s to access the medium. Out of k, i stations are saturated (always have traffic to send). The authors use a M/M/1/k model to analyze the protocol and measure some performance metrics. The state of the queue represents the number of active stations. The authors assume that the service time under any number of saturated nodes is exponential. This however may not be appropriate in all cases for which the authors propose using a pH [19] distribution like Erlang. To find the delay performance, the authors use the saturation throughput developed by Bianchi. The service rate can be calculated by S(i)/td where td is the mean duration of the payload transmission. Simulations are used to find the service time distribution and a Cumalative Distribution Function (CDF) is obtained. The protocol parameters used are given in table. Using the same parameters and k=50, and the balance equations, the authors plot numerical results.

4 Simulation Studies

Simulation studies on MAC protocols generally involve more time but are generally preferred over experimental studies especially in the wireless world. This is because experimental studies in wireless networks involve a lot of cost. Furthemore, it is not always feasible to have a large scale testbed required for full experimentation.

In [7], authors simulate the performance of 802.16 protocol. Each Subscriber Station (SS) uses a Poisson traffic source and the packet size is varied. The throughput and channel utilization has been plotted with varying offered load. The simulation parameters used are as in the table. However, the simulation particulars are missing in the paper. Particularly, the authors do not mention anything on the simulator used, or how long the simulations are run.

Meaning Value (802.16)
Number of SS 20
Preamble (Beacon) 3 us
Each MAP 5 us
Downlink DATA 8 us
Register Contention 1 us
Contention Period Number of active stations
Average data packet size Each traffic 100~200 bytes
Fixed Frame size 1 ms
PHY rate 50 Mbps


In [8], authors provide an analytical model for the delay performance of multi-channel MAC in point to multipoint wireless networks under Poisson traffic. For the model, M orthogonal channels are assumed, with each node having a single transceiver. However the base station can communicate on multiple channels simultaneously. Let TA = length of contention interval; TD = length of data transmission interval in a frame; TF = Frame size. Hence, TF = TD+TA. During the contention period all nodes send contention requests on the same channel. Once the contention is over, nodes can shift to the channels which they were assigned during contention. Let SA = number of contention slots. The authors then derive the probability of successful contention for a channel m and find an expression for the average delay. This is given by




The model is also validated using simulations. The simulator used is ns-2. Three orthogonal channels having a capacity of 10Mbps, contention slot 0.2 ms, and data slot time 0.5ms is simulated. Average service time with TF=5ms and arrival rate = 20 packets/s is compared with the analytical model. The two graphs are found to be highly close.

5 Experimentation Studies

In [18], authors conduct experimental studies on a 802.11b wireless network. The measured metric is throughput and the number of VoIP calls that can be made. The experimental setup is as follows. They used 8 machines running Windows 2000. These worked as SS and associated themselves to a 802.11 AP. The wired part, to which the AP is also connected, contains PCs which serve as the sink for the workload. The throughput was measured in terms of sent payload at layer 4. A program which generated UDP packets at regular intervals was used. In the first set of experiments, a single machine was used to transmit the UDP packets. They found that the maximal achievable payload data rate is 6.1 Mbps, for packet sizes of 1472 bytes (after the MAC header, it becomes 1500 bytes, which is the maximum ethernet payload).

The next experiment the authors perform is by running multiple UDP clients on multiple machines. For two multiple senders, it is found the aggregate achievable throughput increases slightly more than in the case of a single sender. For 2 clients, the aggregate throughput increases to 6.4 Mbps. For 3, the throughput further increases to 6.5 Mbps. However, it does not increase any further. Moreover, for every number of multiple UDP programs, all clients share the bandwidth proportionately.

The authors further calculate the number of VoIP calls that can be supported in the network. The codec used for voice calls sent packets every 10ms. Each millisecond of audio is encoded into 8 bytes of data. The quality of the call was monitored through measurements of loss, jitter, and round trip time. It is found that for the first 6 calls, the quality of all connections was fine with 0% loss, RTT 5ms, and jitter around 7ms. These are ranges below than the critical values for a VoIP call. However, adding another call to the network starts to degrade the quality of the voice calls. Hence, the paper concludes that the maximum number of voice calls that can be supported with the particular codec are 6.

6 Conclusion

The paper presents some widely used techniques in the evaluation of MAC protocols. It looks into 3 techniques: analytical modeling, simulations, and experimentation. For analytical modeling, markov chain models seem to be common. In simulations, softwares like ns-2, and opnet are widely used. Less experimental analysis is present for MAC protocols, but it generally involves using commercial tools to measure various metrics like jitter, throughput, and latency.

References

1. "OSI Model", http://en.wikipedia.org/wiki/OSI_model
2. "TCP IP Stack", http://en.wikipedia.org/wiki/TCP/IP_model
3. "ALOHA", http://en.wikipedia.org/wiki/ALOHAnet
4. V. Bharghavan, A. Demers, S. Shenker, et. al. "MACAW: A Media Access Protocol for Wireless LANs", SIGCOMM Symposium on Communications Architectures and Protocols, Sept. 1994.
5. G. Bianchi, "Performance Analysis of the IEEE 802.11 Distributed Coordination Function", IEEE Journal on Selected Areas in Communications, Vol. 18, No. 3, March 2000.
6. C. H. Foh, and M. Zukerman, "Performance Analysis of the IEEE 802.11 MAC Protocol", Proceedings of Next Generation Wireless Networks, European Wireless 2002, Italy, Feb. 2002.
7. D. H. Cho, J. H. Song, M. S. Kim, K. J. Han, "Performance Analysis of the IEEE 802.16 Wireless Metropolitan Area Network".
8. R. Iyengar, V. Sharma, et. al, "Analysis of Contention Based Multi-channel Wireless MAC for Point to Multipoint Networks".
9. S. S. Lam, "Delay Analysis of a time division multiple access (TDMA) channel", IEEE Trans. on Communications, vol. 25, pp. 1489-1494, Dec. 1977.
10. W. Ye, J. Heidemann and D. Estrin, "Medium Access Control with Coordinated, Adaptive Sleeping for Wireless Sensor Networks", IEEE/ACM Transactions on Networking, June 2004.
11. A. S. Tanenbaum, "Computer Networks", Fourth Edition, Pearson Education, 2003.
12. C. Eklund, R. B. Marks, S. Ponnuswamy, et. al., "WirelessMAN: Inside the IEEE 802.16 Standard for Wireless Metropolitan Area Networks", Standards Information Network, IEEE Press, 2006.
13. IEEE Standard for Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, Nov. 1997, P802.11.
14. N. Abramson, "The Aloha System - Another alternative for Computer Communications", Proc. Fall Joint Comp. Conf. AFIPS, pp.37, 1970.
15. S. S. Lam, "A Carrier Sense Multiple Access Protocol for Local Networks", Computer Networks, vol. 4, pp. 21-32, 1980.
16. V. Bhargavan, A. Demers, S. Shenker, et. al., "MACAW: A Media Access Protocol for Wireless LANs", Proc. ACM SIGCOMM 1994, pp. 212-225, 1994.
17. L. G. Roberts, "Aloha Packet System with and without Slots and Capture", ASS Note 8, Stanford Research Institute, Advanced Research Projects Agency, Network Information Center, 1972.
18. S. Garg, and M. Kappes, "An Experimental Study of Throughput for UDP and VoIP Traffic in IEEE 802.11b Networks", WCNC 2003, March' 03, vol. 3, pp. 1748-1753.
19. "Definition of pH Distribution", http://www.cs.cmu.edu/~osogami/thesis/html/node40.html


Acronyms

BS - Base Station
CA - Collision Avoidance
CD - Collision Detection
CDF - Cumalative Distribution Function
CSMA - Collision Sense Multiple Access
CTS - Clear to Send
CW - Contention Window
DCF - Distributed Coordination Function
DIFS - Distributed InterFrame Spacing
FTP - File Transfer Protocol
HTTP - Hyper Text Transfer Protocol
LLC - Logical Link Control
MAC - Medium Access Control
Mbps - Megabis per second
MIME - Multipurpose Internet Mail Extensions
OSI - Open Systems Interconnection
PCF - Point Coordination Function
PIFS - Point InterFrame Spacing
RTS - Request to Send
SS - Subscriber Station
TDMA - Time Division Multiple Access
VoIP - Voice over Internet Protocol
This report is available on-line at http://www.cse.wustl.edu/~jain/cse567-06/mac_perf.htm
List of other reports in this series
Back to Raj Jain's home page