Router software
Wireless networking for the Propeller and CP/M
Dr James Moxham , March 2010
Wireless ‘mesh’ networking is complicated! The simple idea is that you have a number of short range wireless nodes and that messages propagate through the mesh from a source to a destination. Messages can take multiple paths. That is the easy part. The hard part is solving some of the following real world problems:
- Updating the mesh software on each node via the node itself
- Recovering from data clashes
- Limiting the number of error messages so as to not tie up the network
- Optimising for transfer of 1 byte messages and large files through the same network
- Simple debugging of any node from one node or even a remote location
There will always be a better version of the software and most microcontollers are downloaded in fairly structured ways (eg at fixed baud rates, special delays, special break characters, some only via USB) and so it is not easy to reprogram a microcontroller wirelessly from 3km away. This is even more complicated if it is not possible to directly talk to that microcontroller and the data is going via multiple hops within a mesh. There are a number of solutions, and one simple solution is to run an operating system on the microcontroller. The operating system has a number of programs that can be loaded and run. Useful programs are a simple text editor for writing new code, some programming languages and file transfer programs. There again are a number of choices and we have chosen CP/M from the mid 1970’s, mainly because it is simple enough for one individual to truly understand the entire operating system.
CP/M can run on both retro and modern hardware. The Propeller chip has been chosen as it can drive a number of different displays from one chip (TV, VGA, text LCD), can connect to a standard keyboard, can talk to an SD card (for gigabytes of storage) and can drive several serial ports at once.
All computers crash. If you happen to be sitting in front of the computer you just reset it, but that is difficult in a mesh. A computer that has crashed doesn’t know it has crashed, and one solution is to add a watchdog circuit. However, with a wireless mesh, sometimes it is useful to be able to reset a board remotely. This leads to the solution of a tiny data packet sent out via radio that resets a board. It can be sent manually, or it can be sent by nodes that detect one of their friends is not talking. The propeller is a 32 bit processor and a simple reset packet could be 4 bytes, eg #RES
This data packet is not part of the CP/M operating system. It needs to be detected in some way by a software layer running in parallel with CP/M, or perhaps via external hardware (eg a picaxe chip) talking to a legacy CP/M computer.
Special data packets need to be kept to a minimum as it is easier to code programs that are loaded/run/transferred rather than recode the underlying operating system (eg Propeller or CP/M, which does not need to be updated). So, here is a minimal number of special data packets that do things that are not easy to do in the background in CP/M:
#WHO – tells nearby nodes to respond with their names after a random time delay
#RES – reset all nodes within radio range
#BYE – disconnect from a node
#xyz – connect to a node, where xyz is the first three letters of the node’s name eg #ALP or #BET for ALPHA or BETA
Of course, more can be added, but this is a minimal set.
Now we can see who is out there with a #WHO, then open a link, talk to that board, then close the link.
Next we need a way of transferring files. CP/M has many programs for file transfer, and one very useful and simple program is XMODEM. This breaks the file up into packets and sends the packets one at a time. It resends packets that do not go through, has a checksum on the packet and gives up after 10 failed transfers. It was written for unreliable phone connections and so is perfect for the noisy world of radio communications.
So now, we can log into a remote board, run xmodem on the remote board and set it to receive a file, then run xmodem on a local board and send the file. Then disconnect.
This process can be automated, so it is now possible to write a little program with a menu:
Welcome to CP/M networking for the Propeller
My name is GAMMA
Network radio command list #WHO #BYE #RES #ALP #BET #GAM etc
1 - Send file to peer
2 - Receive file from peer
3 - Talk to peer
4 - WHO - search for peers
5 - Reset all nearby boards
9 - Logoff
Enter your choice:
We can even send this program to another node.
Now it gets complicated. Let’s say the entire network has rebooted and there are minimal programs on each node (just xmodem). We need to rebuild the network from scratch. Let’s say we are on node A and we are talking to node B – sending files, running programs etc. This is all quite straightforward. But say we want to do this on node C, and further, node A and C are out of range. So – all data has to go through node B
Node B can run this menu program – we just send it via xmodem. Node B and C can be talking with single or multiple bytes – we shall call these ‘raw’ bytes. But it is difficult to send raw bytes round a network – there is no source or destination, so the next step is to look at packets. For this example, node B and C are talking with raw bytes as we don’t yet have a packet router program on node C, but we do have one on node B (sent via xmodem from node A). So node A and B talk via packets. Node B has a little program that takes raw data and turns it into packets, and vice versa.
Packet protocols
There are many formats for packets. A very simple packet protocol for Picaxe chips is only 9 bytes (picaxes cannot handle more than 14 byte packets)
1 Start Ascii 01 = ^A or Start of Transmission
2 Packet number Random number 0-255
3 Source
4 Destination
5 Command (eg "P" for picaxe)
6 Number of data bytes
7 Byte
8 Checksum (= same as byte)
9 End Ascii 23 = ^W = End of Transmission
But at the same time, longer packets also are useful. Due to software limitations, the propeller can only handle packets up to 64 bytes when running on a compiled program like C or Basic (xmodem is written in assembly so can handle 134 byte packets).
Harold Bower has written a number of very informative papers based around "Cheap LAN" which is a wired RS232 LAN network that has much in common with wireless networks as all nodes are connected to all other nodes and there are no private data channels.
Some minor changes have been made to the packet format to make them more suitable for wireless and to match the tiny picaxe packet format above:
1 Start Ascii 01 = ^A or Start of Transmission
2 Packet number 0-255 random number
3 Source
4 Destination
5 Command (eg "D" for Data)
6 Number of data bytes
7..n-2 Data
n-1 CRC modulo 256 counter adding all the data bytes
n End Ascii 23 = ^W = End of Transmission
Packet routing
All bytes coming in are stored in a buffer, then the individual packets are processed from the buffer and checked for 01 at the beginning and 23 at the end. Find the end by getting the number in position 6 = n and adding n+8. They are then added to a list. Every 30 seconds, search through the list and remove duplicate packets. Then go through the packets left, and see if have already sent these on. If not, then forward on. If yes, then don't forward on. This rule means that each router forwards each packet just once. All data is scrolled on a VGA display and on a 20x4 LCD display. The 30 second resend rule means that each router sends out all packets in a short burst so less chance of data clashes. Routers will not be synchronised so less likelihood of data clashes.
Data types
Howard Bower describes a range of data types, including acknowledge and negative acknowledge packets. The list below is not the total list but would contain;
R = Receive file
T = Transmit file
Z = Disconnect (same as #BYE)
D = Data packet variable length
P = Picaxe data packet (9 bytes)
B = Broadcast
The B packet is the same as a data packet, except that the data is broadcast by the receiving node out to any nodes. Hence the packet header and footer are removed, and the bytes in the Data section might be
DIR<CR><LF>
Which tells the currently logged in board to do a DIR. This way, boards not running a router program can be told to run the router program with
ROUTER<CR><LF>
More to come as this network evolves.
Source code available from moxhamj@internode.on.net
