[Thali-talk] How big are our discovery announcements?

[Yaron Goland]

Executive Summary: The question came up of how big our discovery announcements need to be. The minimum size is 592 bytes but in practice we would like to support double or triple that. This is a problem because the effective bandwidth on KitKat is 88*(1-0.33) = 58 Bytes and Lollipop is 915*(1-0.33) = 613 Bytes.

Long Winded Version:

So we have ran into a (largely expected) issue that Wi-Fi Direct discovery using mDNS has pretty limited sizes. Jukka's research (which will be summarized in a blog article soon) shows that with his KitKat devices he can only send 88 bytes but can receive without complications up to 920 bytes. Lollipop (to make a long story short) can send/receive up to 915 bytes. So let's say the max is around 915 bytes.

Except.... Those aren't really bytes. They are characters. Specifically, ASCII characters. Remember, this is mDNS and DNS is an ASCII protocol (they have provisions for transporting Unicode but that is done by using a Unicode->ASCII transform called puny code). So when we think of sizing we have to remember that we will have to uuencode our bytes to transport them over ASCII. That typically has 33% penalty. So it means that KitKat can really only advertise 88*(1-0.33) = 58 bytes and Lollipop 915*(1-0.33) = 613 Bytes.

So this begs the question - how many bytes does Thali need?

This is a harder question than it sounds because, in order to protect user privacy, we don't advertise a user's ID. Instead what we advertise are a set of beacons where each beacon is an encrypted package such that only the intended receiver of the beacon can figure it is for them and who it is from. To make this work at any reasonable size we had to use Elliptic Curve cryptography. For security reasons we use 256 bit keys.

Our "basic" discovery announcement has a pre-amble containing an ephemeral key and an expiration. The pre-amble is 88 + 8 = 96 bytes long.

Each beacon is currently 48 bytes long.

But. (You knew there was a but, right?)

The current design, available here<http://thaliproject.org/presenceprotocolforopportunisticsynching>, doesn't account yet for the length of the high bandwidth P2P transport ID. This is needed to switch from the discovery channel (Wi-Fi Direct for Android and BLE for iOS) to the high bandwidth P2P transport channel (Bluetooth for Android and Multi-Peer Connectivity Framework for iOS).

Bluetooth IDs are, I believe, UUIDs and iOS allows you to pick your own IDs, for which we will use UUIDs to ensure uniqueness. A UUID is 16 bytes. In theory we should probably encrypt the UUID but I'm not clear that this would actually buy us much. So for the moment I'm going to assume we send it in the clear.

But wait, there's more! We also need to send a version ID

To that means our discovery announcement sizes are 96 + 16 + N*48 where N is the number of beacons we are advertising.

You can't go around synching with tons of people using modern phones with their limited batteries. So I have picked, out of thin air, the number 10 as the likely number of peers someone would be actively synching with at any one time. Remember, we aren't building some kind of arbitrary mesh routing infrastructure where one would potentially be talking to many more people than that. Such meshes are just not going to work with modern phone batteries.

So our announcement size would be 96 + 16 + 10*48 = 592 bytes.

So this would be our smallest acceptable size. But in practice it would be good if we could advertise 2 or 3 times that.

I could live with declaring victory right now on Lollipop but obviously we have a serious issue with KitKat. And I'm trying hard not to think about Jelly Bean either. Right now Jukka is going to go experiment with the UPNP discovery option on Wi-Fi Direct on the off chance that this might allow larger data sizes on KitKat. If we can get to the equivalent size of mDNS on Lollipop then we can live with it for now. But otherwise we are going to have to do something. The most "obvious" something would be to advertise a hash of the discovery string. When a client sees a discovery hash it doesn't recognize then it will have to connect over Bluetooth to pull in the whole value. If it sees the same value advertised it doesn't need to get it again.

               Thanks,

                              Yaron

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://pairlist10.pair.net/pipermail/thali-talk/attachments/20150625/ab2ca2d0/attachment.html>