Abstract:
Next generation very high-speed wireless LANs (WLANs), the physical (PHY) layer rate may reach 600 Mbps. To achieve high efficiency at the medium access control (MAC) layer, some fundamental properties that must be satisfied by any CSMA-/CA-based MAC layers and develop a novel scheme called aggregation with fragment retransmission (AFR). In AFR, multiple packets are aggregated into and transmitted in a single large frame. If errors happen during the transmission, only the corrupted fragments of the large frame are retransmitted. A analysis model is developed to evaluate the throughput and delay performance of AFR over noisy channels. Optimal frame and fragment sizes are calculated using this model. Transmission delays are minimized by using a zero-waiting mechanism which give maximum throughput. We have implemented the AFR scheme in the NS-2 simulator and present detailed results for TCP, VoIP, and HDTV traffic. The AFR scheme described was developed as part of the IEEE 802.11n. The analysis presented here as a proposed schemes in the upcoming 802.11n standard.
Keywords:
802.11, AES, fragmentation, security overhead,802.11n, medium access control (MAC), wireless LAN (WLAN).
Introduction
WIRELESS LANs (WLANs) based on IEEE 802.11 technology are becoming increasingly popular. With theaim of supporting rich multimedia applications such as HDTV (20 Mbps) and DVD (9.8 Mbps), the technology trend is toward increasingly higher bandwidths. Some recent 802.11n proposals seek to support physical (PHY) layer rates of up to 600 Mbps However, higher PHY rates do not necessarily translate into corresponding increases in medium access control (MAC) layer throughput. Indeed, it is well known that the MAC efficiency of 802.11 typically decreases with increasing PHY rates[2]. The reason is that while increasing PHY rates lead to faster transmission of the MAC frame payloads, overhead such as PHY headers and contention time typically do not decrease at the same rate and thus begin to dominate frame transmission times, even under ideal case conditions, the MAC efficiency falls from 42% at a PHY rate of 54 Mbps to only 10% at 432 Mbps. The problem here is a fundamental one for MAC design, namely that, due to cross-layer interactions, the throughput of the current 802.11 MAC does not scale well with increasing PHY rates. With continuing improvements in PHY technology and demand for higher throughput, the MAC scaling behavior is of key importance. While the current focus of 802.11n activity is on achieving 100-Mbps throughput at the MAC layer, still higher target data rates can be expected in the future. To avoid repeated MAC redesigns, one basic question that we seek to answer is whether it is feasible to extend the 802.11 MAC to maintain high MAC efficiency regardless of PHY rates.We answer this in the affirmative. In particular, we identify fundamental properties that mustbe satisfied by any CSMA-/CA-based MAC layers and developa novel scheme called aggregation with fragment retransmission(AFR) that exhibits these properties. In the AFR scheme,multiple packets are aggregated into and transmitted in a singlelarge frame.[2]
If errors occur during the transmission, only the corrupted fragments of the large frame are retransmitted. In this scheme, a new delimitation mechanism allows for higher throughput with less overhead compared to previous designs. We study a fragmentation technique where packets longer than a threshold are divided into fragments before being aggregated. An analytic model is developed to evaluate the throughput and delay of AFR over noisy channels and to compare AFR with competing schemes. Optimal frame and fragment sizes are calculated using this model, and an algorithm for dividing packets into near-optimal fragments is designed.
Higher transmission delays are an unavoidable result of using aggregation to achieve high throughput. In particular, is additional delay necessarily introduced 1) by the need to wait until sufficient packets arrive to allow a large frame to be formed, and 2) for transmission of a large frame? We answer this question in the negative. Specifically, we propose a zero-waiting mechanism where frames are transmitted immediately once the MAC wins a transmission opportunity. In a zero-waiting aggregation scheme, the frame sizes adapt automatically to the PHY rate and the channel state, thereby maximizing the MAC efficiency while minimizing the holding delay. Thirdly, we investigate by simulations the impact of AFR on the performance of realistic applications with diverse demands. We implement the AFR scheme in the network simulator NS-2 and present detailedresults for TCP, VoIP, and HDTV traffic. Results suggest that AFR is a promising MAC technique for very high-speed WLANs. Moreover, AFR is particularly effective for rich multimedia services with high data rates and large packet sizes, which are expected to be key applications in future WLANs.[2]
II. MOTIVATION
A. DCF and Its Inefficiency
Transmission of a frame inevitably carries an overhead,2
which we can consider as additional time . In 802.11,the overhead includes the time required to transmit thePHY header, the time , to transmit the MAC headertheCSMA/CA backoff time , and the time to transmit aMAC ACK (Notation is listed in Table I).In order to clarify the impact caused by the overhead, we define
MAC efficiency as(1)
where is the time required to physically transmit a packet
(i.e., the frame payload) and , as just explained above. As the PHY rate increases, for a fixed packet size , the time to transmit the packet payload decreases. If does not also decrease, then the efficiency as . →0 ,R→∞. As the PHY rate increases, the contention time does not decrease toward zero due to the constraints placed on theminimum slot size by clock synchronization requirements and on DIFS by the need for backward compatibility.
Similarly ,the duration of the PHY header is not expected to decrease with increasing PHY rate owing to backward compatibility and PHY-layer channel equalization requirements [4]. Thus, as the PHY rate is increased, the time to transmit a frame quickly becomes dominated by the fixed overhead associated with the PHY header, contention time, etc. Much work has been done to minimize the contention time component of the overhead by regulating the randomized backoff process (e.g., [16], [49], and [33]) to reduce the number of collisions and idle slots. However,
in very high-speed networks, the MAC efficiency is still intolerable even without these problems. For example, we illustrate in Fig. 1(a) the efficiency in the ideal case where the channel is perfect with neither collisions nor errors [48], hence the overhead of the backoff process is minimized. It can be seen that the efficiency decreases dramatically as the PHY rate increases. In a 216-Mbps WLAN, the efficiency is only about 20%. When the PHY rate increases to 432 Mbps, the efficiency decreases to around 10%.
B. Burst ACK and Block ACK
The Burst ACK and Block ACK schemes have been proposed in the literature for improving efficiency. Burst ACK performs the back off process once for a series of data and ACK frames (see Fig. 7 for details), while Block ACK goes one step further by using a single ACK frame for multiple data frames, thus reducing the number of ACKs and SIFS. In both schemes, the back off time is incurred once for packet transmissions, where is the size of a packet burst. With Burst ACK, the per-packet overhead is approximately +, ,while for Block ACK it is +/M. It can be seenthat the contention overhead and MAC ACK overheadare amortized over multiple packets by these two schemes,therefore improving efficiency.
However, the per-packet PHY header overhead and theMAC header overhead are left untouched. According tothe proposal 802.11n [4] for the future WLANs, it is likely totake at least 44 s to transmit a PHY header (and 48 s when twoantenna radios are used [4]). For comparison, the transmissionduration of a 1024-B frame at a PHY rate of 216 Mbs is 40 s,and at 432 Mbs is 20 s. As the PHY rate is increased, the time totransmit a frame quickly becomes dominated by PHY headers,the MAC efficiency rapidly decreases, and efforts to increasethe system capacity purely by increasing the data rate are thusof limited effectiveness even when Burst ACK or Block ACKare employed.
C. Aggregation Schemes
Aggregation schemes seek to amortize the PHY header overhead across multiple packets. This is achieved by transmitting multiple packets in a single large frame. However, there is a traditional dislike for transmitting large frames in wireless networks since in a noisy channel ,the throughput can fall as larger frames are used [24]. We illustrate this in Fig. 1(b). However, we note that in traditional retransmission schemes, a whole frame is retransmitted even if only one bit is lost. This raises the question of whether it is possible to retransmit only the erroneous part(s) of a frame-if properly designed, such partial retransmission could be expected to improve performance.
This is a key motivation of the work presented here. Although this idea seems simple at first glance, it is actually a radical challenge for PHY and MAC technology. From the PHY viewpoint, the traditional small-packet rule does not hold anymore. The PHY layer has to transmit very large frames and continue decoding even if the BER exceeds some previously unacceptable value. Under these conditions, the size of the largest practical frame is still unknown [4]. From the MAC viewpoint, any retransmission scheme carries an associated signaling overhead and, hence, a tradeoff exists between system efficiency and the granularity of retransmission. Moreover since real traffic is typically bursty/on-off in nature, this raises questions as to the optimal policy for aggregating packets into frames-for example, how much time should the MAC wait for sufficient packets to arrive to form a large frame.
Our previous work on aggregation schemes resulted in a proposal for the forthcoming IEEE 802.11n standard. In [5] and [26], we propose to aggregate multiple packets into a single large frame and, should an error occur, the damaged packets are retransmitted. The present paper substantially extends this previous work (see Section II-D). In parallel with our work, there are other activities in the 802.11n standard working group on this topic (e.g., [4], [6], and [7]). These support similar functionalities to our scheme, with a special delimiter for locating each fragment in a frame. Other related work includes that of Jiet al. [22], where an aggregation technique is used to solve an unfairness problem in WLANs. Jiet al. suggest removing the DIFS, SIFS, and backoffs before a series of packets, and transmitting the packets together in a large PHY layer frame. However, a small PHY header (12 s) is used to identify each packet within a frame. In [23], a two-level (one atMAC, another at PHY) aggregation scheme is proposed that uses a similar delimiter to that in the TGn Sync proposal [4].
III .FUNDAMENTAL CONSIDERATIONS
We highlight in this section the basic requirements that must
be respected by any aggregation schemes that seek to maintain high MAC efficiency as PHY rates increase and introduce the zero-waiting approach to aggregation.
A. MAC Efficiency
The basic requirement for high efficiency is to aggregate packets into large frames so as to spread the cost of fixed overhead across multiple packets. To reduce the overhead associated with transmission errors, each frame is subdivided into fragments, with packets that exceed the fragment size being divided. Fragments are the unit used in the retransmission logic, i.e., damaged fragments rather than the entire frame are retransmitted. The time to transmit a packet is , where is the packet size and is the PHY rate. Hence, the per-packet MAC efficiency is
= .
We can see that scales with 1/R . We show that under certain assumptions, it is indeed possible to maintain a constant MAC efficiency while R is increased. That is, we may decouple MAC efficiency from the PHY rate R. In order to maintain MAC efficiency , we require that the per packet overhead also scales with 1/R . Considering in more detail, we can typically decompose it into the following elements (where r denotes the average number of transmissions before all fragments from this packet are transmitted successfully, and other notation is listed in Table I):
To ensure that scales with 1/R , we require that:
• The number of packets M in a frame should be proportional
toR, that is M=b.Rfor some constant b . This ensures
that the overhead , , , and translateinto a per-packet overhead that scales with R.Since there is only one MAC header and one ACK perframe, when M is proportional toR , there is no fundamentalconstraint on the rate at which MAC headers andACK frames are transmitted. The same is not true for fragmentheaders.
• For a given fragment sizeLfrag , the number of fragments
in a frame 'm' increases with the number of packets M
in a frame, i.e., m=m΄M , where m΄ is the number offragments per packet; we thus have m=m΄.b.R ,when M=b.R Hence, for /M to scale with 1/R, the rateat which fragment headers are transmitted must be chosento be proportional to R, in which case.
• The retransmission time r is constant. For a given packetsize, the number is determined by the bit error rate (BER).The BER itself depends upon the channel signal to noiseratio and the choice of coding. A rate controller is typicallyused to adjust the coding and rate to maintain the BERbelow a target level reflecting application andtransport layer requirements.3 In the following we assumethe use of a rate controller, and thus that rate is adjustedto ensure that the average number of retransmissions remainsapproximately constant.We also note that if BER isnot regulated via rate control, then provided is boundedor is a known function of rate , the scaling analysis canbe extended to include this situation.When the per-packet overhead satisfies these conditions, theper-packet MAC efficiency is (4)
whereL1denotes the size of one fragment header and
a =First, observe that the efficiency is nicely decoupled from thePHY rate R, i.e., the throughput scales with R. Second, as weincrease the factorb , we can see that the efficiency asymptoticallytends to
=(5)
where .p.
That is, the efficiency is fundamentally limited by the numberof fragments per packet and the number of retransmissionsðœ. In particular, if we use a large fragment size correspondingto a small , such large fragments are more likely to be corrupted; we have therefore small and large . On the otherhand, when a packet is divided into many small fragments, corresponding to use of a large , the probability of a fragment being corrupted is low, and we have large but small . To achieve high efficiency, we study in Section V-D a fragmentation technique where packets with sizes exceeding a threshold are divided into fragments to deal with the tradeoff between and .
Comment 1: At high rates in a noisy channel the question of the impact of errors in the received fragment headers arises.
First, we only require that the rate used for sending the fragment headers is proportional to the data rate . Thus, to protect the fragment headers, they may be sent at a relatively low rate (e.g., at half, or less, of the data rate), and in this way we can ensure that the majority of bit errors affect the data payload only. Second, fragment header size (8 B in AFR, see Section IV-A) is minimized to ensure low error probabilities. Third, in the frame we collect the fragment headers together with the MAC header (details in Section IV-A) so that FEC can be more easily employed to enhance robustness.[2]
B. Zero-Waiting
When the channel is lightly loaded to the extent that the DCF is enough, deliberate waiting only leads to higher delays. If the channel is in a heavily loaded condition where backlogged buffers mean the desired numbers of packets to form large frames are always available when transmission opportunities are won, then all waiting schemes are the same. If the channel is in an intermediate situation between these two extremes, waiting for a certain amount of time for packets to accumulate seems reasonable at first glance. Nevertheless, we argue that fundamentally there is no need to wait for packets to accumulate at the MAC layer, and it is sufficient instead to simply start a transmission whenever the MAC wins a transmission opportunity. This zero-waiting mechanism evidently performs well in both lightly and heavily loaded situations. In the intermediate state,4the frame size used adapts to the minimum required to service the offered load. Specifically, when the current level of efficiency is too low for the offered load, a queue backlog will develop, which in turn induces larger frames and increased efficiency. If the incoming traffic subsides, smaller frame sizes will be automatically selected. Evidently, such a policy minimizes holding delay at the MAC layer.
We now show that this opportunistic aggregation policy can also lead to the desired efficiency where it is feasible to do so. Assuming that there are no collisions and errors in the network,5corresponding to , we can write the per frame MAC efficiency as
(6)
Also, E[] = E[q] = . (7)
From (6) and (7 ) we have
As , α→1 we can see that the zero-waiting policy achieves the desired efficiency. consequently maximum throughput is achieved .
IV.THE AFR SCHEME
In this section, we describe in detail the AFR scheme based
on the insight provided by the foregoing analysis.
A. AFR Implementation
Clearly, new data and ACK frame formats are a primary concern in developing a practical AFR scheme. Difficulties for new formats include 1) respecting the constraints on overhead noted previously and 2) ensuring that, in an erroneous transmission, the receiver is able to retrieve the correctly transmitted fragments-this is not straightforward because the sizes of the corrupted fragments may be unknown to the receiver. In our scheme, a MAC frame consists of a frame header and a frame body [see Fig. 2(a)]. In the new MAC header, all the fields of the DCF MAC header remain unchanged, and we add three fields-fragment size, fragment number, and a spare field. The fragment size represents the size of fragment used in the MAC frames. The fragment number represents the number of fragments in the current MAC frame. The spare field is left for future extension and maintaining alignment. The frame body consists of fragment headers, fragment bodies and the corresponding frame check sequences (FCS) .
Fig. 2. Data format in the AFR scheme.
Fig. 3.ACK format in the AFR scheme.
TABLE=II
AN EXAMPLE USAGE OF THE AFR FRAME FORMATS
Packet ID
Packet length
StartPos
offset
Fragment 1
1
1025
0
0
Fragment 1
1
1025
512
1
Fragment 1
1
1025
1024
2
Fragment 1
1
40
1025
0
The fragment header section of the frame body has a variablesize. It includes from 1 to 256 fragment headers, each of whichis protected by a FCS. The length of each fragment header isconstant (8 B) and known to both the sender and the receiver. For the receiver, it knows from where the first fragment header starts and what the fragment header size is, thus it can locate all the fragments in the frame even if some of them are corrupted during the transmission.
Each fragment header is composed of six fields: packet ID (pID), packet length (pLEN), startPos, offset, spare, and FCS. pIDand pLENrepresent the corresponding ID and length of the packet P to which this fragment belongs. startPosis used to indicate the position of the fragment body in this frame, and offset is used to record the position of this fragment in packet P.
The new ACK format is simple; we add a 32-B bitmap in the legacy ACK format. Each bit of the bitmap is used to indicate the correctness of a fragment (see Fig. 3).
To clarify the usage of the new formats, we give an example. Suppose there are two packets ( pkt1and pkt2 ) with lengths of Lp1 =1025B and Lp2 =40B. The frame length is Lf=2048 B and the fragment length isLfrag=512 B.6 Then, AFR divides and into 3 and 1 fragments, respectively, and puts them into the s nding queue. A frame with fragment size of 512 B and fragment number of 4 is constructed. The corresponding fragment headers are shown in Table II. After receiving the frame, the receiver operates as shown in Algorithm 1 to recover the fragments.
Algorithm 1 : Pseudo Code of the receiver's running logic
1
if MAC header is correct then
2
for i = 0 to fragment number - 1 do
3
if Fragment i's header is correct then
4
if packet length < fragment size then
5
fragment i's length = pLEN;
6
else if offset = [pLEN/fragment size]then
7
fragment i's length = pLEN- offset * fragment size;
8
Else
9
fragment i's length = fragment size;
10
end if
11
fragment start position = startPosin the fragment header.
12
check the correctness of the fragment body using the FCS of it.
13
end if
14
record correctness (including fragment header and fragment
body) of the fragments in a data structure called the ACK bitmap.
15
end for
16
construct ACK frame using the ACK bitmap and send it back.
17
update the Rq according to the ACK bitmap.
18
check the Rq and transfer all correctly received packets
upwards, and remove them from the Rq.
19
Else
20
discard this frame and defer an EIFS before next transmission.
21
end if
Comments
1) Frame/Fragment Size: Selection of the maximum frame
size and of the near-optimal fragment size is discussed in
Sections V-C and D.
(2) Fairness: AFR strictly follows the basic principle of the
CSMA/CA. Therefore, the same fairness characteristics hold as in the legacy DCF. Techniques to improve DCF's fairness are all suitable for AFR.
3) Multiple Destinations: Thus far, we have focussed only
on aggregation between a single source-destination pair. This facilitates a clear understanding of the pros and cons of the aggregation itself. In order to support one-to-many aggregation, a broadcast/multicast MAC address should be used and all stations that hear the transmission then check a new receiver-list field in the MAC header that specifies the destination address for each fragment. That is, the only modification in terms of frame format is adding the receiver-list field. However, one-to-many aggregation introduces a number of new issues that we will mention. First, one-to-many aggregation requires consideration of new ACK ing techniques to avoid collisions between ACK transmissions by the multiple receivers. This might be achieved by sequential transmission of ACKs or perhaps by use of advanced PHY layer techniques (coding, multiple antennas) to enable decoding of ACKs that are sent simultaneously (e.g., [18] and [41]). The resulting performance requires detailed study, and these techniques are not proposed for future 802.11n standards[4]. Second, multiple antenna systems are widely considered to be of vital importance for achieving very high transmission rates
[4]. The design of one-to-many aggregation for multiple antenna systems remains an open question that is likely to require tightly coupled cross-layer PHY/MAC design and operation. Third, the channel quality may differ between neighbors, and it might therefore be necessary to use multiple subphysical headers. These new headers clearly would cause extra overhead. Further, rate adaptation, which has become an indispensable functionality of 802.11-based networks, requires further work in the context of one-to-many aggregation.
4) Multirate: In the current WLANs, a commonly used technique to resist channel noise is to lower the PHY rate after measuring a high packet (or bit) error rate, and when the channel state improves, the PHY layer increases its rate accordingly. There are two issues to be addressed if multirateis to be supported in AFR: i) Should we change the frame size with the PHY rate? ii) Should we support one-to-many aggregation where receivers have different channel states? The first issue has been discussed at the end of Section III-B, and the second one is just mentioned.
V1.SIMULATIONS
As a complement to the theoretical analysis in Section V, we have implemented the AFR scheme in the network simulator NS-2 [10], [11]. The network topology that we used is a peer-topeer one where STA sends packets to STA .We report here the simulation results for three types of traffic (TCP, HDTV, and VoIP), all of which follow the requirements of the 802.11n usage model [8].
Metrics
We use the following metrics. Let c denote the number of packets (packet size is Lp ,B) successfully received by all of the STAs, and denote the simulation duration. Let
be the time when the theith packet is put in the interface queue (IFQ) between MAC and its upper layer at the sender. Let denote the time when the ith packet is transferred to its upper layer by the receiver.
• Throughput( =Mbps) : Throughput represents the maximum rate at which the MAC layer can forward packets from senders to receivers. Since in a WLAN, all the STAs share a common medium, this throughput is achieved by the whole system rather than by a single STA.• Peak delay (,,……}wheredenotes the maximum delay among all the packets successfully received by STA i ): Peak delay is the maximum delay experienced by a successfully transmitted packet. This metric is used for HDTV.
• Percentage delay: The metric we use for VoIP is the percentage delay at the application level. It is defined as the
percentage of packets whose delay is greater than a delay upper limit (e.g, at the application layer, the system should
have less than 1% of packets whose delays are greater than
30 ms). At the MAC layer, we use a similar threshold, i.e., less than 1% of packets may have delay greater than 15 ms.
B. TCP Traffic
TCP currently carries the great majority [50] of network traffic and it is therefore important to investigate the support
of the AFR scheme for TCP traffic. Important features of TCP include the fact that traffic is i) elastic, and so achieved
throughput is related to network capacity, and ii) two-way, and while TCP data packets are typically large, TCP ACKs are small packets, so it may be difficult to aggregate enough of them to form a large frame. First, we evaluate AFR performance in a heavily-loaded WLAN with 50 STAs. Each STA performs a large FTP download. The data packet length is 984 B, which yields an IP packet size of 1024 B when TCP and IP header added, TCP SACK functionality is used as this is prevalent in real networks. From Fig. 10(a), we can see that AFR achieves considerable throughput gains (by a factor of between 2 and 3 depending on channel conditions) over DCF. As discussed previously, AFR performance is relatively insensitive to the choice of fragment size in the range 128-256 B, although as might be expected the choice of fragment size becomes more important at higher BERs.
Second, we evaluate AFR performance as the number of STAs is varied from 10 to 80. Fig. 10(b) shows both the AFR and DCF throughput. AFR achieves between 2.5 and 3 times the throughput of DCF over this range of network conditions.
C. HDTV
According to the requirement of the IEEE 802.11n proposal
[8], HDTV should be supported in future WLANs. HDTV has a constant packet size of 1500 B, a sending rate of 19.2-24 Mbps, and a 200-ms peak delay requirement. We investigate AFR HDTV performance with a 432-Mbps PHY data rate. Fig. 11 shows the throughput and delay performance of the AFR and DCF schemes as the number of STAs (and so HDTV flows) is varied. The peak delay constraint of 200 ms is marked on Fig. 11(b). It can be seen that DCF can support only two simultaneous HDTV streams before the delay requirement is violated and the per-flow throughput rapidly falls below the offered load. In contrast, AFR can support up to nine and 10 streams for BER and BER , respectively. That is, the HDTV capacity is increased by a factor of 5 over DCF.
D. VoIP
The third application that we consider is VoIP, which is basically an on/off UDP stream with a peak rate (96 Kbps) and a small packet size (120 B), according to the IEEE 802.11n requirements [8]. VoIP is a challenging application for aggregation schemes because of its on/off nature and small packet sizes. Thus, there may not be enough packets for AFR to aggregate, and the DCF and AFR schemes might be expected to achieve more or less the same performance.
We consider a WLAN with pure VoIP traffic. We use Brady's model [44] of VoIP traffic in which the mean ON and OFF periods are 1500 ms. Our performance requirement is to have less than 1% of packets with delays larger than 15 ms. Table VI shows the percentage of packets with delay exceeding 15 ms for a range of network conditions and numbers of voice calls. It can be seen that AFR's delay percentages are substantially less than the DCF's under all conditions, demonstrating the effectiveness of the AFR scheme, even for traffic with very small packet sizes.
VII: CONCLUSION
To achieve high efficiency for next-generation very high-speed WLANs, new scheme called AFR is developed, in which multiple packets are aggregated into and transmitted
in a single large frame. Only the corrupted fragments are retransmitted instead of retransmitting the whole frame in case of errors. Transmission delays are minimized by using a zero-waiting mechanism where frames are transmitted immediately once the MAC wins a transmission opportunity. Simulation analysis models NS-2are developed to evaluate the throughput and delay performance of AFR over a noisy channel .
