Binary encoding for low bandwidth connections?

Question

In my application I have a simple XML formatted file containing structured data. Each data entry has a data type and a value. Something like

<entry>
  <field type="integer">5265</field>
  <field type="float">34.23</field>
  <field type="string">Jorge</field>
</entry>

Now, this formatting allow us to have the data in a human readable form in order to check for various values, as well as performing transformation and reading of the file easily for interoperability.

The problem is we have a very low bandwidth connection (about 1000 bps, yeah, thats bits per second) so XML is no exactly the best format to transmit the data. I'm looking for ways to encode the xml file into a binary equivalent that its more suitable for transmission.

Do you know of any good tutorial on the matter?

Additionally we compress the data before sending (simple GZIP) so I'm a little concerned with losing compression ratio if I go binary. Would the size be affected (when compressing) so badly that it would be a bad idea to try to optimize it in the first place?

Note: This is not premature optimization, it's a requisite. 1000 bps is a really low bandwidth so every byte counts.

Note2: Application is written in c# but any tutorial will do.

Answer 1

You may want to investigate Google Protocol Buffers. They produce far smaller payloads than XML, though not necessarily the smallest payloads possible; whether they're acceptable for your use depends on a lot of factors. They're certainly easier than devising your own scheme from scratch, though.

They've been ported to C#/.NET and seem to work quite well there in my (thus far, somewhat limited) experience. There's a package at that link to integrate somewhat with VS and automatically create C# classes from the .proto files, which is very nice.

Answer 2

Anything which is efficient at converting the plaintext form to binary is likely to make the compression ratio much worse, yes.

However, it could well be that an XML-optimised binary format will be better than the compressed text anyway. Have a look at the various XML Binary formats listed on the Wikipedia page. I have a bit of experience with WBXML, but that's all.

As JeeBee says, a custom binary format is likely to be the most efficient approach, to be honest. You can try to the gzip it, but the results of that will depend on what the data is like in the first place.

And yes, as Skirwan says, Protocol Buffers are a fairly obvious candidate here - but you may want to think about custom floating point representations, depending on what your actual requirements are. If you only need 4SF (and you know the scale) then sending a two byte integer may well be the best bet.

Answer 3

I'd dump (for transmission anyway, you could deconstruct at the sender, and reconstruct at the receiver, in Java you could use a custom Input/OutputStream to do the work neatly) the XML. Go binary with fixed fields - data type, length, data.

Say if you have 8 or fewer datatypes, encode that in three bits. Then the length, e.g., as an 8-bit value (0..255).

Then for each datatype, encode differently.

• Integer/Float: BCD - 4 bits per digit, use 15 as decimal point. Or just the raw bits themselves (might want different datatypes for 8-bit int, 16-bit int, 32-bit int, 64-bit long, 32-bit float, 64-bit double).
• String - can you get away with 7-bit ASCII instead of 8? Etc. All upper-case letters + digits and some punctuation could get you down to 6-bits per character.

You might want to prefix it all with the total number of fields to transmit. And perform a CRC or 8/10 encoding if the transport is lossy, but hopefully that's already handled by the system.

However don't underestimate how well XML text can be compressed. I would certainly do some calculations to check how much compression is being achieved.

Answer 4

The first thing to try is gzip; beyond that, I would try protobuf-net - I can think of a few ways of encoding that quite easily, but it depends how you are building the xml, and whether you mind a bit of code to shim between the two formats. In particular, I can imagine representing the different data-types as either 3 optional fields on the same type, or 3 different subclasses of an abstract contract.

[ProtoContract]
class EntryItem {
    [ProtoMember(1)]
    public int? Int32Value {get;set;}
    [ProtoMember(2)]
    public float? SingleValue {get;set;}
    [ProtoMember(3)]
    public string StringValue {get;set;}
}
[ProtoContract]
class Entry {
    [ProtoMember(1)]
    public List<EntryItem> Items {get; set;}
}

---

With test:

[TestFixture]
public class TestEntries {
    [Test]
    public void ShowSize() {
        Entry e = new Entry {
            Items = new List<EntryItem>{
                new EntryItem { Int32Value = 5265},
                new EntryItem { SingleValue = 34.23F },
                new EntryItem { StringValue = "Jorge" }
            }
        };
        var ms = new MemoryStream();
        Serializer.Serialize(ms, e);
        Console.WriteLine(ms.Length);
        Console.WriteLine(BitConverter.ToString(ms.ToArray()));
    }
}

Results (21 bytes)

0A-03-08-91-29-0A-05-15-85-EB-08-42-0A-07-1A-05-4A-6F-72-67-65

Answer 5

Try using ASN.1. The packed encoding rules should yield a pretty decently compressed form on their own and and the xml encoding rules should yield something equivalent to your existing xml.

Also, consider using 7zip instead of gzip.

Answer 6

I would look into configuring your app to be responsive to smaller XML fragments; in particular ones which are small enough to fit in a single network packet.

Then arrange your data to be transmitted in order of importance to the user so that they can see useful stuff and maybe even start working on it before all the data arrives.

Answer 7

Here's the pickle you're in though: You're compresing things with Gzip. Gzip is horrible on plain text until you hit about the length of the total concatonated works of Dickens or about 1200 lines of code. The overhead of the dictionary and other things Gzip uses for compression.

1Kbps is fine for the task of 7500 chars (it'll take about a minute given optimal conditions, but for <300 chars, you should be fine!) However if you're really that concerned, you're going to want to compress this down for brevity. Here's how I do things of this scale:

T[ype]L[ength][data data data]+

That is, that T represents the TYPE. say 0x01 for INT, 0x02 for STRING, etc. LENGTH is just an int... so 0xFF = 254 chars long, etc. An example datapacket would look like:

0x01 0x01 0x3F 0x01 0x01 0x2D 0x02 0x06 H E L L O 0x00

This says I have an INT, length 1, of value 0x3F, an INT, length 1, of value 0x2D then a STRING, length 6 of a null terminated "HELLO" (Ascii assumed). Learn the wonders that are System.Text.Encoding.Utf8.getBytes and BitConverter and ByteConverter.

for reference see This page to see just how much 1Kbps is. Really, for the size you're dealing with you should bee fine.

Answer 8

Late response -- at least it comes before year's end ;-)

You mentioned Fast Infoset. Did you try it? It should give you the best results in terms of both compactness and performance. Add GZIP compression and the final size will be really small, and you will have avoided the processing penalties of compressing XML. WCF-Xtensions offers a Fast Infoset message encoding and GZIP/DEFLATE/LZMA/PPMs compression too (works on .NET/CF/SL/Azure).