|Wireless simulations and message reference counting in OMNeT++ 3.2|
|Monday, 08 August 2005 11:15|
OMNeT++ 3.2 will implement reference counting of encapsulated messages, which has the potential of bringing dramatic performance improvement especially for wireless simulations. Reference counting means the following: when you duplicate a message that contains an encapsulated message, then instead of duplicating the encapsulated message as well, the two messages will hold a pointer to the same encapsulated message. Similarly, when you create 100 copies of the original message, then all of them will hold a pointer to the same encapsulated message instance -- saving the creation and copying of 100 encapsulated messages (or 200, if the encapsulated message also contains another encapsulated message).
Decapsulation will however cause the message to be copied (because decapsulation will allow the code to can change data in the message object, delete it etc, so it can no longer be shared). That is, if all 100 messages get decapsulated, then those 100 messages we spared at duplication will eventually be created during decapsulation -- so we haven't gained anything. The potential performance gain occurs when most of those messages get deleted without ever being decapsulated. That's exactly the case with wireless simulations -- you'll see that there, reference counting may reduce the total number of messages created/deleted by 50% or even much more.
Let us consider wireless simulations in the INET Framework, say, hosts exhanging UDP packets over 802.11 (ad-hoc mode). The INET Framework uses the lower layers of the Mobility Framework, so you'll see hosts sending AirFrames when you run the simulation. AirFrames represent the physical characteristics of the frame (frequency, power, etc). AirFrames encapsulate 802.11 frames (Mac80211Pkt), 802.11 frames encapsulate IPDatagrams, IPDatagrams encapsulate UDPPackets, and finally UDPPackets encapsulate the payload which might be a cMessage. This is altogether 5 levels of encapsulation.
When a host transmits an AirFrame, it will send a copy to every other host within interference range. Each host individually evaluates the physical layer model, and decides (based on the signal-noise ratio) whether the frame is receivable. If not, the AirFrame is discarded. Then the 802.11 frame gets decapsulated from the AirFrame, and the 6-byte MAC address is checked. If the MAC address doesn't match (and it's not broadcast etc), the frame is discarded. Otherwise the IPDatagram gets decapsulated from it and sent up to the IP layer.
What does this mean in practice? Without reference counting, all copies of AirFrames have their own copies of all the higher-layer protocol headers as well. That is, if there are 100 hosts in range, altogether 5x100=500 message objects are created, most of which gets deleted without ever being looked at, because the corresponding AirFrame gets discarded in the physical layer (bit errors or collision) or in the MAC layer (wrong MAC address). If we use reference counting, then all 100 AirFrames will refer to the same 802.11 frame object as encapsulated message, that is, we'll have 104 objects altogether (100 AirFrames, plus 1 of 802.11, IPDatagram, UDPPacket, payload message). Let us assume that out of the 100 recipients, only 83 are able to receive the frame correctly, the rest discards it due to physical layer errors. Those 83 recipients will decapsulate the 802.11 frame, resulting in 82 additional copies of the 802.11 frame message object being created. However, only one host will have a matching MAC address, the rest discard the frame -- so no extra copies of IPDatagram and higher layer messages are created. Thus, we end up with 104+82 = 186 messages used for the transmission, instead of the original 500 -- which is a 62% gain!
To get the full picture, we have to take into account the ACKs as well (where isn't that much saving because, being just an AirFrame plus a 802.11 ACK frame it doesn't have several levels of encapsulation), but the overall number of messages is still about half the original. A real simulation experiment (with INET's MobileAdhoc/80211 example network and 100 hosts) showed 718,275 messages being created, as opposed to 1,393,125 without reference counting -- a 48.44% saving. Profiling of simulations (e.g. using the graphical KCachegrind) show that message creation is responsible for a massive part of the runtime overhead, so reference counting can be a very significant performance improvement factor.