13 May 2008

16. All meshed up - Part 2 - Packet network basics

Now we’ve worked out how to get a chunk of data from one place to another without any wires, it’s time to look at how the PicPack packet network actually works. In the next enthralling instalment we’ll get the actual packet network up and running in code.

Okay, so here’s the problem I was trying to solve. How do you get a message to a device on the other side of the house, reliably? The distance (with brick walls) is going to be too great for a given, cheap, RF transceiver to reach, but we’re pretty much guaranteed to have devices in between the two – so could we use those as relays? It would be pretty nice not to have to configure the network (ie, direct exactly how the network gets messages from one place to another) - since the network may change and configuration of little hardware devices is difficult from the other side of the planet.

So what I wanted was effectively a meshed packet network. But there’s a catch. We want to do this as cheaply as possible, not using devices with large chunks of memory, but on something like a 16f88 – 4k instructions, 384 bytes of RAM. Could it be done?

The trick here is working out a way to discover network routes automatically in small amounts of code. My first thought was a method by which nodes could ask their neighbours if they knew about the node we wanted to talk to. And then if they didn’t know, they could ask their neighbours. Once we had the route, we could store it. Great, so now we’re storing a routing table. And how long do we store it before we throw it out and have to rediscover again when something has changed? Timewise, by the time we’ve asked all our neighbours to ask their neigbours about the node I want to send to, collected the responses, sorted them, then sent the message, well, this is all getting complicated and memory intensive, along with the next ice age having kicked off.

Well, it’s all about tradeoffs, as we know from other tutorials. So here’s our strategy. If our destination node is within range, we’ll send it directly. It then sends an acknowledgement so we know it arrived safely. If it’s not within range, we get everyone that can hear us to broadcast the message. Hopefully, it will be in range of them, and we’ll get an acknowledgement back. In fact, we’ll allow up to three “hops” of rebroadcasts before giving up.

This does mean we’re going to have a lot of traffic bouncing around at times. We minimise this by the three hop rule and also by checking to see we haven’t seen this packet recently (if we have, just ignore it). It will also mean that a packet may find its way by several means to the destination address. We cope with this by sending an acknowledge back for the first one, and then acting on the packet. If another copy of the same packet arrives – we realise that the packet has already been received and don’t act on the packet, but we do send another acknowledge back, since this one may have come a second time because the originator didn’t get our first acknowledge.

It all sounds a little complex, but in use you just set your local address and start sending out packets. It’s a good project to show how the various parts of the PicPack we’ve seen so far come together. And despite all this complexity, we have a meshed packet RF network in 3k of code. Not bad. That leaves you with at least another 1k of code to actually do something with those packets.

Next time we'll have a look at the code that gets the packet network up and running.

No comments: