本末倒置MACAW tries to address the fairness issue in single cell scenarios as depicted in Figure7.In this setup there are3nodes N1,N2,and N3which are trying to transmit data to another node B(base station)in same cell.If the transmission queues of all the nodes are backlogged then most of the times all of them are contending for the channel access.If during the contention all but one pad have relatively high backoff counters then the one with low backoff counter will win the contention.This will result in that node resetting its contention window to the lowest possible window size.This will put the successful node at an advantage over the other nodes since it has now a more than fair chance of winning the contention at later time.This will result in increasing the contention windows of other even further.Note that,in this scenario the implicit assumption is that the other nodes do not perform carrier sense and do not freeze their backoff counters for the duration of transmission.
The observation to be made here is that the backoff counter(or the contention window)of a node does not re?ect the ambient congestion level that exists in the entire network.MACAW advocates sharing of this information by all the nodes in the network.This can be done by including the value of current contention window in every packet that gets transmitted.All other nodes can now update their contention values depending on the latest noti?ed value.Thus,in a network where all nodes are within the reach of each other, after every transmission all nodes have same contention window.
This scheme solves the problem of information sharing but introduces a new problem of oscillating con-tention windows.After every successful transmission,the contention window gets reset to the minimum possible value.If the number of nodes in a network is very high,all nodes would spend a lot of time adjust-ing their contention window to reach an optimal level which would be immediately reset after a successful transmission by any of the nodes.MACAW deals with this oscillation problem by introducing a multiplica-tive increase linear decrease(MILD)backoff algorithm.In this algorithm the backoff window is increased by a multiplicative factor after collision and is decreased by1after success.The multiplicative increase yields a prompt convergence to the backoff window when the contention is high and avoids oscillations by
13
not resetting it to the minimum possible value.
MACAW does not assume that the nodes use carrier sense to avoid collisions.In a single cell network,the fairness problem does not exist if nodes perform carrier sense and freeze their backoff counters for the duration of transmission by other nodes.
MACAW also tries to address the issue of proper de?nition of fairness.If the fairness criteria is de?ned as,“equal channel share for every node,”then there are certain nodes like base stations in infrastructure networks which are at a disadvantage.Consider the setup shown in Figure 8.Here the base station B needs handle streams to nodes N1and N2.Node N3needs to send data to the base station.In this scenarios there are only two nodes which need to access the channel.If the channel access is granted equally to N3and base station then the channel share is not fair from the perspective of streams.MACAW suggests that this problem can be solved by running multiple instances of backoff algorithm each corresponding to a stream.As a matter of fact,this scheme is the basis of traf?c categories in 802.11e.
Estimation based backoff
Zuyuan Fang et al.[15]propose a novel measurement and estimation based scheme to solve the fairness problem in 802.11b networks.The proposal is based on estimating the throughput of all nodes and then computing a fairness index based on this estimation.This fairness index can then be used to adjust the contention window.
The fairness index between any two nodes i and j is computed using the following equation:
fairness index =max {?i,j,min i,j (W i
φj )/max i,j (W i
φj )}(1)
where φi is the prede?ned fair share that a station i should receive and W i is the throughput achieved by node i .The constraints on φi and W i are such that for a total throughput of W :?i φi =1and ?i W i =W
The fairness goal now becomes maximizing the value of fairness index locally.When the fairness index equals 1all nodes obtain the throughput proportional to their share.There are two issues with this approach.First,how to prede?ne the fair share of each node.Second,how to measure the total usage by all nodes.Note that the algorithm should take into account the hidden nodes and node mobility as well.Thus,there cannot be any signaling traf?c between the nodes.
The solution to the ?rst problem is achieved by dividing the nodes into two partitions.In this approach,each node regards all of its neighbors as a single entity with a notion of myself and the others .Now the fair share assumed by each node is φi =0.5.All other nodes also get the remaining share of 0.5.The assumption here is that when all nodes use the same approach,all of them will compete with same fair share.Thus due to the local contention and collisions the long term throughput will achieve fairness.If one wants to provide a stream based fairness,a node can increase its fair share by the proportional amount.That is,if a node has two streams then it treats streams of all other nodes as a single stream and computes its fair share as φi =0.67.
The second problem is solved by snooping on the traf?c in the network.A node can always measure its own traf?c.The traf?c from hidden nodes is deduced by snooping on the CTS and ACK packets sent to those nodes.
Once a node has an estimate of its own traf?c W ei and the traf?c by others W eo it computes the fairness index using the above mentioned equation.After computation of the fairness index it doubles it contention window if it has obtained more than its fair share and halves it if it has not received its fair share.
14
The effectiveness of this approach essentially depends on the approximation of the fair shareφi.if the value ofφi is higher than what it ought to be,the node acts in a greedy fashion and the short term fairness of the channel allocation is affected.For a network with n competing nodes,the share should be1/n.The farther the assumed value(0.5)from1/n,the greedier is the algorithm.This greediness of algorithm,though ensures the long term fairness,affects the short term fairness severely.Moreover,the IEEE802.11b MAC is known to be fair in long term and it is the short term fairness one needs to address.This can be possibly done by estimating the number of nodes in the network.If the estimation of number of nodes is close to the actual number of nodes,the algorithm can work very ef?ciently.
Distributed Fair Scheduling
Nitin Vaidya et al.[17]extend the notion of fairness to include the weight of a?ow for considering its share of the channel.This is in contrast with the prevalent notion of equal share to all nodes or equal share to all?ows.They propose an extension to802.11b DCF to achieve this Distributed Fair Scheduling(DFS) with weighted proportions.The DFS was designed in an attempt to emulate the Self-Clocked Fair Queueing (SCFQ)[18].The DFS is speci?cally tailored for distributed systems like802.11b LANs.
SCFQ is a centralized algorithm for packet scheduling on a link shared by multiple?ows as shown in Figure9.The central coordinator maintains a virtual clock.At any given time t,v(t)indicates the virtual time.Assume that:P k i denotes the k th packet arriving on i th?ow,A k i is the real time of arrival for packet P k i,and L k i represents the size of the packet P k i.For each packet P k i,a start tag S k i and a?nish tag F k i are assigned.The assignment algorithm is as follows:
1.?i F0i=0.
2.Every packet P k i is stamped with start tag S k i using following equation:
S k i=max{v(A k i),F k?1
}.
i
3.A?nish tag for each packet P k i is calculated as:
F k i=S k i+L k i
Figure9:The SCFQ algorithm is used for scheduling packets from multiple input?ows to one output link.The DFS uses this as the basic
model.Figure10:The DFS maps the link in SCFQ to the shared medium and the input?ows to the traf?c from wireless nodes.DFS is thus a distributed version of SCFQ
is mapped to the shared wireless medium and the input?ows are mapped to the?ows from each individual node.
SCFQ is a centralized algorithm.Because of this centralized nature,there is no issue in determining the shortest of the?nish tags of the packets from each queue.But in DFS all queues are distributed.Thus,the selection of next eligible packet for transmission has to be done in a distributed manner.DFS circumvents this problem by choosing the backoff interval proportional to the?nish tag of the packet that is at the front of the?ow.Further,each transmitted packet carries the virtual?nish time of the packet each transmitted packet carries its virtual?nish time with it.This virtual?nish time is used by other nodes to synchronize their virtual clocks.
DFS is implemented as follows:
?Whenever a packet advances to the front of the?ow,its start tag is updated depending on the virtual time at that instance.
?The virtual?nish time for every packet is calculated similar to SCFQ but with a scaling factor for choosing a suitable scale for virtual time.Note that S k i=v(f k i)and from equation(2):
F k i=v(f k i)+scaling factor?
L k i
φi
?(4)?This backoff window B i is further randomized by multiplying it with a random variable with mean1.
On close observation,it becomes apparent that there is no need to maintain a virtual clock as the virtual ?nish time is never used in calculating the backoff interval.After every packet transmission on LAN,all nodes calculate the backoff interval based on the fairness share of each node and the packet size.DFS deals with collisions the same way as802.11b,i.e.,the binary exponential backoff.Thus only?rst backoff interval is chosen depending on the fairness share of the node and is a linear function of packet size and
