分类： LINUX
2009-05-13 17:36:23
802.11 MAC code in NS-2 (version 2.28)
by (jpr at rice.edu)
Last update: 4-29-05
Note that this document is no longer maintained, as I have stopped work on NS-2 as of 2005. Please do alert me if you find any errors or more up-to-date descriptions of the code.
There are 4 different paths the code can follow:
Overhearing a packet not destined for itself
Packets colliding
Or just jump to the listing of
or a list of the
Transmitting a packet
Roughly takes the following path (when no errors or congestion):
-> -> and -> start
-> -> ->
-> -> started
-> -> -> -> start ->
-> -> ->
-> -> started
-> -> -> -> callback_ -> -> done!
When the first RTS fails:
-> -> and -> start
-> -> -> -> start
-> -> -> -> started
-> ->
the rest is the same as above
Receiving a packet
Roughly takes the following path (when no errors or congestion):
-> started
-> -> -> -> -> start ->
-> -> ->
-> -> started
-> -> -> -> -> start -> uptarget_->recv()
-> -> -> -> start
-> -> <- nothing happens, we're done!
Functions
recv() (DOWN) - Like all connectors, which Mac inherits from, the packet to be sent is received by the recv() function. Because the recv() function is also called when a packet comes from the channel, recv() checks the direction field in the packet header. If the direction is DOWN, meaning the packet came from an upper layer, the packet is then passed on to the send() function.
recv() (UP) – The recv() function is called whenever a packet is received from either an upper or lower layer. If the packet is received from a lower layer – the network interface here, then the first check will be skipped. At this point the phy has just received the first bit of the incoming packet, but the MAC can't do anything with the packet until the whole packet is received. If the packet is received while the MAC is currently transmitting another packet, then the received packet would be ignored – meaning the error flag in the packet's header is set. If the MAC is not currently receiving any packets, then the rx_state_ is changed to RECV and is called. Afterwards, the incoming packet is assigned to pktRx_ and the is started for the txtime() of the packet. If the MAC was already receiving a packet when this packet arrived, it will compare the received power of the new packet with the old packet. If the power of the new packet is smaller than the old packet by at least the capture threshold, the new packet will be ignored (captured) and the function is called. If the power levels of the two packets are too close though, there will be a collision and control will transfer to , which will drop the arriving packet. The original packet won't be dropped until it's reception is complete. Control will return to the MAC whenever the expires, calling recvHandler(), which in turns goes right to .
send() - The send() function first checks the energy model, dropping the packet if the node is currently in sleep mode. It then sets callback_ to the handler passed along with the packet. This is so the handler can be called when the packet's transmission is complete. Next, send() calls and which build the MAC header for the data packet and the RTS packet to go along with the data packet – which are stored in pktTx_ and pktRTS_ respectively. The MAC header for the data packet is then assigned a unique sequence number (with respect to the node).
Next, the MAC checks it's . If the backoff timer is not currently counting down, then the node checks if the channel (medium) is idle, and if so the node will begin to defer. The node checks this using the function is_idle(). As per the 802.11 specs, the node will defer a difs time plus a randomly chosen amount of time in the interval [0, cw_), where cw_ is the current contention window. If the node is already waiting on it's , it will just continue waiting (not resetting the timer). If the medium is detected to be busy, then the node starts it's backoff timer. As of this point, the send() function has finished and control will resume when one of the timers expires, calling either or .
sendDATA() - This function builds the MAC header for the data packet. This involves increasing the size of the packet, setting the type as data, and subtype as data. The packet should now have a complete MAC header attached to it. The function then stores the txtime of the packet, which is computed by the txtime() function. By txtime, we basically mean the size of the packet multiplied by the Data rate. You'll notice (in 2.28 at least), that this calculation is done twice – this first time is just a waste. It's calculated again because a different value for the data rate is used if the packet happens to be a broadcast packet. Also, if the packet is not a broadcast packet, the duration field in the MAC header is computed. By duration, we mean the amount of time this communication still needs the channel after the data packet has been transmitted. For the case of a data packet, this corresponds to the amount of time to transmit an ACK plus a short inter-frame spacing. If the packet happens to be broadcast, this field is set to zero (no ACKs for broadcast packets). Now, the MAC has finished building the MAC header for the packet and finally assigns the internal variable pktTx_ to point to the packet we've been working on. This is essentially a way of storing the packet to be transmitted in a local buffer in the MAC. Now, the code returns to the function.
sendRTS() – This function is in charge of creating an RTS packet with the specified destination in conjunction with the data packet the MAC is trying to send. The first thing it does is check the size of the packet against the RTSThreshold. If the packet is smaller (or is broadcast) then no RTS is sent before the data is transmitted (the RTS/CTS mechanism is not used). In this case, the function simply returns control back to the function. Otherwise, a brand new packet is created (actually done in the first line of the function) and it's fields are set appropriately, i.e. the type is set as a MAC packet. A rts_frame structure is used to fill in the rest of the packet header and the appropriate values are put in the rts fields. The destination field is filled in with the parameter passed to the function and the rf_ta (source?) is filled in with the MAC's address. The duration field is also calculated as the time to transmit a CTS, the data packet (pktTx_) and an ACK (plus 3 sifs). After the RTS has been constructed, the internal state variable pktRTS_ is assigned a pointer to the new RTS. After this, control is returned to the function.
sendCTS() - This function is in charge of creating a CTS packet and pointing pktCTRL_ to it. Everything proceeds straightforwardly, with fields being given obvious values. The duration field is set to be the same as was in the RTS, except minus the txtime of a CTS and a sifs_ time, since that amount of time would have already elapsed once another station decoded the packet. After the creation of the CTS packet is done, pktCTRL_ is pointed to the new packet and control returns to .
sendACK() - This function is responsible for creating an ACK packet to be sent in response to a data packet. The packet is created and all the fields are filled in with the obvious values. The duration field is set to zero indicating to other nodes that once this ACK has completed, they don't need to defer to another communication. Once the packet has been successfully built, pktCTRL_ is pointed to the new ACK and control returns to .
deferHandler() - This function is called when the defer timer has expired. When this happens, this means the node has waited enough time before transmission to lessen the chance of collision and will now attempt to transmit a packet. Accordingly, the first thing the function does is assert that there is either a control, RTS, or data packet waiting to be transmitted. The function then calls , and then makes sure the backoff timer is not currently running. Afterwards, it calls and . If any of these check_ functions returns a value of zero, the defer handler stops, as this indicates that the check_ function has succeeded in transmitting that particular kind of packet. Therefore, the actual packet transmission is handled by one of these check_ functions. At this point, transmission has most likely begun on some kind of packet and control will resume at the expiration of the interface timer, txHandler(), which simply clears the flag tx_active_ to indicate that the phy is not currently transmitting something. Control will resume if another packet is received via : a CTS if an RTS was just sent, a data packet if a CTS was just sent, or an ACK if a data packet was just sent. But control may also resume at the expiration of the send timer, sendHandler(), which immediately calls .
check_pktCTRL() - This function is responsible for transmitting CTS and ACK packets, which would be pointed to by pktCTRL_ . So the first thing the function does is check to see if this variable points to anything. If not, the function returns -1, indicating nothing was transmitted. The function will also return if the transmission state (tx_state_) indicates the MAC is currently transmitting either a CTS or ACK packet, although I don't know why this would occur. The function then performs a switch based on what kind of control packet is ready to be sent, CTS or ACK.
If it's a CTS, the MAC will check the status of the medium using is_idle(). If the channel is busy, the CTS will simply be dropped and pktCTRL_ set to zero. If the channel is idle, the function will, using macros, set the value of the tx_state_ to indicate the MAC is currently transmitting a CTS and then call the function . After this, the function calculates the timeout value – which is how long the MAC should wait before it decides the packet it sent wasn't received successfully. In the case that the control packet is an ACK, the MAC proceeds in the same way, except that it doesn't check the medium. Finally, the function is called with arguments pktCTRL_ and the previously calculated timeout value. At this point, the phy has just begun transmission of the control packet.
check_pktRTS() - This function, like the other two check_ functions, is responsible for transmitting a packet – in this case, an RTS packet. If there is no RTS packet ready to send, i.e. pktRTS_ is null, then the function simply returns with a value of -1, indicating that it did not send a packet. There is an oddly placed switch statement here presumably in order to detect an improperly built RTS packet. Before the RTS is sent, the channel is checked. If it is sensed to be busy, the contention window (cw_) is doubled using the inline function inc_cw() and the backoff timer is started again. The function therefore returns without transmitting a packet if the channel is busy. If the channel is idle, the tx_state_ of the MAC is set to RTS and the function is invoked. Next, the timeout value is calculated so that the MAC will know how long to wait for a CTS to be returned. Finally the function is called with arguments of the RTS packet and timeout value. At this point, the phy has begun transmission of the RTS packet.
check_pktTx() - This function, like the other two check_ functions, is responsible for transmitting a packet – in this case, the actual data packet. If there is no data packet waiting to be sent (pktTx_ is null), then the function returns with a value of -1, indicating that nothing was transmitted. Again, an oddly chosen switch statement is used to catch an improperly built data packet. If the channel is sensed to be busy, is called. This means that despite the RTS/CTS exchange, another node is using the channel (possibly due to mobility), or RTS is not being used – in which case the sendRTS function will do nothing. Additionally, the contention window (cw_) is doubled using the inline function inc_cw() and then the backoff timer is started so that the MAC will remain idle until the other node has completed transmission. If the channel is idle, the tx_state_ is set to MAC_SEND and the function is invoked. The timeout value is calculated in two ways, depending on whether or not the data packet is broadcast. If not, the timeout is how long the MAC should wait before it decides an ACK wasn't received. If the packet is broadcast, the timeout is simply the transmission time of the packet because no ACKs will be sent in conjunction with a broadcast packet. Finally, the function is invoked with arguments of the data packet and the calculated timeout value. At this point, the data packet has begun transmission.
checkBackoffTimer() - This inline function performs two checks. First, if the medium is idle and the backoff timer is currently paused, it will resume the timer.
The second check is if the medium is not idle and the backoff timer is currently running (busy and not paused), then it will pause the timer. This corresponds to the fact that the MAC only counts down it's backoff timer while the channel is idle. As per the specs, the timer should not be running while the channel is being used by another node.
transmit() – This function takes two arguments, a packet and a timeout value. It sets a flag variable, tx_active_, to one to indicate that the MAC is currently transmitting a packet. The function then performs a check because if it is an ACK being transmitted then it is possible that the node could be receiving a packet, in which case that packet would be missed. This next block checks if the MAC is currently receiving a packet and that it is an ACK being transmitted, and if so, marks the packet being received as having errors. Next, the packet is actually passed down to the network interface (WirelessPhy class) which is pointed to by downtarget_. Actually, only a copy of the packet is sent down in case there needs to be a retransmission. Finally, two timers are started – the send timer is started with the timeout value, which will alert the MAC that the transmission probably failed. Also, the (mhIF_) is started with the txtime() of the packet – when this timer expires, the MAC will know that the phy has completed the transmission of the packet.
send_timer() - This function is called at the expiration of the , mhSend_. This timer expires after amount of time calculated as timeout in the corresponding check_ function – the expiration of this timer means slightly different things depending on which kind of packet was sent. In a switch statement, the MAC checks the value of tx_state_ to find out the kind of packet that was most recently sent and then handles each packet differently. If the last packet sent was an RTS, the expiration of the timer means a CTS wasn't received, presumably because the RTS collided or the receiving node is deferring. The MAC responds by attempting to retransmit the RTS in the function .
If the last packet sent was a CTS packet, the expiration of the timer means that no data packet was received. This is an infrequent event occurring if the CTS packet collided or if the data packet was in error. The MAC handles this by simply resetting itself to an idle state. This involves freeing the CTS packet stored in pktCTRL_.
If the last packet sent was a data packet, the expiration of the timer means that an ACK was not received. The MAC handles this situation by calling .
Finally, if the last packet sent was an ACK, the expiration of the timer simply means that the ACK has been transmitted, as no response is expected from an ACK. The MAC frees the ACK packet pointed to by pktCTRL_ .
After each case has been handled and a packet has possibly been prepared for retransmission, the function is given control. If a packet is going to be retransmitted, the backoff timer has already been started with an increased contention window.
RetransmitRTS() - This function is called in response to a CTS not being received after an RTS was sent. First, the function does some stat collecting, recording this as a failed RTS, and the short retry count (ssrc_) is incremented. The short retry count is maintained so the MAC knows when to give up on this packet and drop it, which happens when ssrc_ reaches the value of ShortRetryLimit in the MAC MIB. The drop is handled by called the discard() function on the RTS packet and resetting the pktRTS_ pointer to zero. Then the data packet is also dropped by calling the same discard() function. The ssrc_ is reset to zero and the contention window is reset to it's initial value. Otherwise, the same RTS pointed to by pktRTS_ is kept, but a retry field in the RTS is incremented. Because of the contention avoidance mechanism, the contention window is doubled and then the backoff timer is started using this new contention window. This means control will eventually return to .
- This function is called when an ACK is not received in response to a data packet being sent. If the data packet was a broadcast packet, an ACK shouldn't be expected and so the data packet is treated as being successfully transmitted and so is freed and the congestion window reset. The backoff counter is started though, I'm not really sure why. Two separate retry counts are maintained depending on whether or not an RTS is being used for this data packet. If an RTS is not being used, the short retry limit is used, otherwise the long retry limit is used as a threshold. If the retry count has exceeded the threshold, then the data packet is discarded using the discard() function and the retry count and congestion window are reset. If the retry count has not been exceeded, the data packet is prepared for retransmission by incrementing a retry field in the mac header, doubling the congestion window, and then starting the backoff timer. This means control will eventually return to .
- This function is called when the MAC is getting ready to send a packet but needs to set some timers. If a control packet (CTS or ACK) is waiting to be sent, this function simply starts the defer time for a sifs_ amount of time. This is because a node is supposed to wait a brief period of time before transmitting. If an RTS packet is waiting to be sent, then the MAC makes sure the backoff timer isn't currently busy – if it is, then the MAC will wait to start the defer timer. If the backoff timer isn't busy the defer timer is started for a random time in the interval [0,cw_) plus a difs_ time. If a data packet is next to be sent, and MAC isn't currently backing off, then the defer timer is started for the data packet. If an RTS wasn't used for this packet, then the defer timer is set for a random value in the interval [0,cw_] plus a difs_ time, but if an RTS was used, the MAC will only defer for a sifs_ time. This is because if an RTS was used, then the channel has already been reserved for this MAC and it shouldn't need to worry about collisions.
If there are no packets waiting to be sent, but the callback_ is defined, then it is handled, corresponding to a successfully completed packet transmission. Finally, the tx_state_ is set to idle. Control will return back to the MAC when the defer timer has expired, - or back to the function that called it, like one of the recvP functions.
capture() - This function is called when a second packet is received while the MAC is currently receiving another packet, but the second packet is weak enough so that the phy can ignore it. The important thing this function does is update the NAV so that carrier sense will know that the channel is still busy after it has finished receiving it's packet. Capture also discards the captured packet.
collision() - The collision handler first checks the rx_state_ variable and sets it to MAC_COLL in case this is the first collision during the current packet. If a third packet collides, rx_state_ will already be MAC_COLL. Then, the MAC calculates how much longer the new packet will last and how much longer the old packet will last. If the new packet will last longer, then the MAC makes the new packet pktRx_ and resets the receive timer, mhRecv_. In this case the old packet is discarded here, but if the old packet will last longer then the new packet is simply discarded and pktTx_ doesn't change. So at the end of this function, the colliding packet that would have completed first has been discarded and rx_state_ is set to MAC_COLL.
recv_timer() - This is the handler, called when mhRecv_ expires (though indirectly though RecvHandler). The expiration of the receive timer means that a packet has been fully received and can now be acted upon. First, the MAC checks to see if it's currently transmitting a packet by checking the flag, tx_active_. If so, the MAC wouldn't not have even heard the packet so it is just discarded (without updating NAV). Next, the rx_state_ is checked to see if there was a collision during this packet, i.e. rx_state_ equals MAC_COLL. If so, then pktRx_ is the colliding packet that lasted longest and now needs to be discarded. The NAV is also set for an eifs_ time, which is the amount of time the MAC must wait after a collision. The MAC then checks the packet for errors, and discards the packet if any were detected. Again, the NAV is set for eifs_ time after the error packet is finished being received. The next check the MAC performs is if the packet is actually destined for itself – if not, the MAC updates the NAV for the value in the duration field in the MAC header (not necessary just the txtime of the packet). This is of course so that the MAC doesn't attempt to transmit while other nodes are using the channel. The next check consists of sending the packet to any taps if it is a data packet – essentially sending the packet to anybody wanting to listen in promiscuous mode. The next check involves the adaptive fidelity algorithm and basically keeping track of the nodes within radio range of the node. And finally, the last check performed is address filtering, where all packets that are not destined for the current node are discarded. The NAV would have already been updated so there's no need to do anything else with the packet.
Now the MAC decides what to do based on what kind of packet it just received. If the packet is of MAC_Type_Management, it's simply dropped. If it's an RTS packet, is called, if CTS or ACK, then or is called. And not surprisingly, if it's a data packet, then is called. After this, pktRx_ is set to zero and control to given to .
recvRTS() - This function is called by recv_timer after a full RTS packet has been received. If the tx_state_ is not idle, then the packet wouldn't have been heard, so it's simply discarded. Also, if the MAC is currently responding to another node (pktCTRL_ is nonzero) then the RTS will be ignored. This happens for example, if the node already heard an RTS from another node is waiting to send a CTS back. Otherwise, the MAC is in a state such that it can receive a packet, so it prepares to send a CTS by calling . Next, the MAC stops the defer time and calls - which will restart the defer timer for the appropriate amount of time. Control then returns to .
recvCTS() - This function is called by the recv_timer after a full CTS packet has been received, meaning the MAC can now send it's data. Since the MAC has no use for the RTS packet it just transmitted, it's freed and pktRTS_ is set to zero. The send timer is stopped, although I'm not exactly sure why it would be running. Control then goes straight to , which sets the defer timer, and then control finally returns back to .
recvACK() - This function is called by the recv_timer after a full ACK packet has been received, indicating a successful data transmission. First, the MAC checks that it really did just sent a data packet (tx_state == MAC_SEND) and discards the ACK if it didn't. The MAC now knows that it just succesfully transmitted it's data packet, so it frees pktTx_ and sets it to zero. The send timer is also stopped, but again, I don't know why. The MAC then resets the appropriate retry count, short if an RTS wasn't used, long if it was. Also, the congestion window is reset and the MAC starts its backoff timer so it won't just immediately send again. Control then goes to and then back to . In tx_resume(), since there are no packets ready to send, the callback will be invoked, effectively telling the interface queue to send down another packet for transmission.
recvDATA() - This function is called by the recv_timer after a full data packet has been received, indicating that this node just successfully received a data packet. First, the MAC strips the MAC header from the packet, getting it ready to be sent to the upper layers. If the data packet wasn't broadcast, RTS packets are being used, and tx_state_ indicates that the last packet the MAC sent was a CTS, then that CTS (pktCTRL_) is cleaned up (freed and pktCTRL_ set to zero). And again, the send timer is stopped. If the MAC didn't just send a CTS when it should have, the data packet is dropped because events didn't happen in the right order and the function returns. Otherwise, the data packet was received correctly and the MAC prepares to send an ACK by calling and then to start the defer timer appropriately. If a CTS was not sent (because there was no corresponding RTS), then the MAC checks pktCTRL_. If there is a control packet there, the MAC will drop the data packet because there is no room to buffer an ACK packet (the ACK would go in pktCTRL_). Otherwise, is called to create an ACK packet to send. In this case, if the send timer isn't currently counting down, is called to start the defer timer.
Next, the MAC updates it's sequence number cache – if the packet is unicast only. The packet is checked to make sure the source node will fit in the cache – it is possible for the cache to have been configured with an incorrect size, i.e. less than the total number of nodes in the system. Then the sequence number of the packet just received is compared with the most recently received sequence number and if they match, the data packet is discarded as it is a duplicate (same packet received twice). If the source node is not in the cache (cache is too small), some warnings are printed out.
The data packet is then passed to the uptarget_ - the layer above the MAC (usually link-layer). This means the data packet has been fully received by the node and it's on it's way up the protocol stack.
rx_resume() - This simple function is called after recv_timer has completed. All it does is set the rx_state_ to idle and then invoke .
backoffHandler() - This function is called whenever the backoff timer expires. This function first checks to see whether there is a control packet (CTS or ACK) waiting to be sent. If so, it makes sure that the MAC is either sending the packet or deferring before sending the packet. If there was no control packet, is called. If there was no RTS packet, then is called. This means, that at the expiration of the backoff timer, an RTS or a data packet will be transmitted if either is waiting. I think this should only happen on RTS or data retransmissions.
- Handler for that simply clears a flag in the MAC to indicate that the radio is no longer active.
- The command() function is a TCL hook for all the classes in ns-2 which allows C++ functions to be called from a TCL script. The arguments for command() are effectively the same as for the main function is basic C programs, with argc and argv containing the command given to the object. In the 802.11 MAC, this function is not often used, at least in my experience. If none of the commands match those specific to the 802.11 MAC, then the command() function of the parent class is called.
– The interface timer keeps tracks of how long the interface will be in transmit mode. This is only the time when the interface is actively transmitting bits into the air. The handler for this timer is . Probably the simplest timer used by the MAC layer.
NavTimer – Started at the reception of a packet for the length of time indicated in the duration field of the MAC header. Calls navHandler() on expiration.
– Started when the first bit of a packet is received and set for the length of time the packet will require to be completely received. This timer is needed because in simulation the entire packet is available as soon as the first bit arrives, but the MAC should not access the packet until it would have been completely received in reality. In the case of a packet collision, the receive timer is reset to expire at the end of the last colliding packet. The timer indirectly calls on expiration by calling recvHandler() first.
– Indicates the time by which an ACK/CTS should have been received. The TxTimer (mhSend_) is started when a packet is transmitted by the function. Each type of packet has an expected response, for example, an RTS packet expects a CTS packet to follow. The timer is therefore stopped when a CTS, data, or ACK packet is received. The timer is not started on transmission of an ACK packet as there is no response expected. On expiration, is called indirectly by first calling the (ahem, worthless) function sendHandler().
–
–
BeaconTimer – Not used.
