Implementation

Transmission Path

Penumbra relies on the new mac80211 wireless stack for Linux, which offers some cool features, like being able to run a wireless device with multiple logical interfaces in different modes simultaneously. So you can be associated on wlan0 and also create a, say, mon0 which you set to monitor mode too.

The Penumbra packet is created in usermode and is injected into a Monitor Mode interface using a PF_PACKET / SOCK_RAW socket or libpcap. At the start of the packet is a radiotap header, this allows the transmission rate and antenna to be selected. Next is the iee80211 header with the MAC addresses set to the special Penumbra ones, 13:22:33:44:55:66; there is nothing in what is transmitted to identify the transmitting station. The payload for the Penumbra packet follows the header. (You can find some example code for this in penumbra-udp.c in the penumbrad ).

We have provided patches to enable generic radiotap packet injection in mac80211 which we hope will be accepted, allowing penumbrad to work on any mac80211 device with a later kernel without patching.

The payload is protected using a 255:223 Reed-Solomon? Forward Error Correction coding. This is capable to correct any 16 symbol errors over each 223 bytes of payload. An extremely cool feature of this coding is that any amount of damage to a symbol (a byte in this case) counts as the same, so for serialized bitstreams like in ieee80211, it can recover from a dropout period of up to 128 bits since that still only damaged 16 bytes. To maximize the benefit of this protection, bulk data packets are limited to 213 bytes of actual payload (and a 10-byte header), giving a 255 byte encoded packet payload so each fragment fits inside a single error correction coding cycle. The Reed-Solomon? coding also means there is no need for a payload CRC.

The packet is then sent out as normal in clear, with all MAC addresses replaced.

Reception Path

Penumbrad listens on a Monitor mode intergace set to promiscuous at the hardware level, so packets not targetted as the receiving MAC address can be seen. Because mac80211 supports monitor mode at the same time as Managed mode, this does not affect normal associations.

When a packet with the 13:22:33:44:55:66 MAC address is seen, the libpcap kernelside filter passes it to penumbrad.

The penumbrad Usermode Daemon then performs the Reed-Solomon? error correction and decoding, and uses the packet fragment according to the higher level filesharing protocol.

Filesharing protocol

The Filesharing protocol works on top of the lower level packet transport described above. Users interact with penumbra only through SSL-encrypted browser sessions.

The originator of a broadcast sends out an "advert" packet for the broadcast describing its category, mimetype and filename. Other stations copy and reissue these small advert packets, making all stations aware of what is available.



The raw material for passing data around is a single short broadcast of a 213-byte "fragment" of data. The fragments are combined into a 4KByte payload "block", which was RSA signed by the originator using a one-time RSA keypair. This 4KByte block is the smallest chunk of data which can be assessed for "correctness" according to the public key from the broadcast advert. The blocks are combined into an ~8MB chunk file, still with their signatures intact, which is used as the unit of storage for a broadcast.



A machine that is interested in a particular broadcast sends out a request for fragments. In return another station can choose to send small "fragments" containing 213 bytes of Reed-Solomon? protected payload. These broadcasts are not acknowledged and can be missed or corrupted, in which case the station that is interested will rebroadcast its request, and the same or another station can reissue the data.



Machines that receive an expression of interest can choose to rebroadcast it, randomly deciding to decrement the "Time To Live" of the request or not. When the TTL reaches zero, it is not rebroadcast any more. This means that requests normally stay within a small radius of machines of the requestor, but can with lower probability "break out" much further.

Since all nodes cache material that they hear being broadcast, when the requests continue to arrive machines closer to the requestor find that they can broadcast the requested data once somebody further away has issued it, so it propogates back to the requestor.

Since now all the intermediate nodes are flush with the data, any further requests from people nearby any of the intermediate nodes are fulfilled very quickly from multiple sources.

Expression of interest packets can target up to 25 different blocks of the same broadcast in one packet, and for each block can specify fragment-by-fragment what they are missing. In this way the requestor can see decent throughput even if the only person with new data is many hops away by "working ahead" on the requests without generating more Expression of Interest packets.

---