Zigbee 2007 (Residential) has two methods of routing: mesh routing and tree routing. Although most people talk about the mesh routing capability of Zigbee, not too many people know much about the tree routing. There's actually a good reason that it isn't discussed much and I'll get into that later. However I do receive the occasional question on how Zigbee tree routing works. Mostly, its from people that want to run Zigbee using the 802.15.4 beacon mode since tree routing is the only routing method supported in this case.
In order to understand tree routing, its first important to understand the underlying principle which is how addresses are allocated. Once that is understood, the routing becomes trivial.
Tree Address Allocation
Tree routing works by routing frames based on the addresses of the routers in the network. In order to do this, the routers that join need to have their addresses allocated in a special way. Although the address allocation scheme can be summarized in a handy little algorithm called CSkip, which can be found in the Zigbee spec, it's probably best to explain qualitatively how it works.
Actually, the allocation scheme isn't very sophisticated. You start off with an address space that is calculated based on the maximum number of routers per device (Rm), max children (routers + end devices) per device (Cm), and max depth (Dm) of the network. To make things simple, lets just take the case where the "max children = max routers" which means that all the children will be routers and no end devices are allowed on the network. The simplification just makes it easier to calculate the address space.
Based on the information above, we can calculate the size of the address space, since it will be the same as the maximum number of devices on the network. In other words, each device gets one address. As an example, let's say that the maximum number of routers that can be joined to a device is two, the maximum number of children for a device is 2 (hence all children are routers), and the max depth of the network is two. In Zigbee speak, this would be labeled (Rm=2, Cm=2, Dm=2). This would give us a network that looks like this:
From the picture, you can see that the maximum number of devices would be 7, hence the address space will span from 0 to 6. Also I purposely drew it in a tree structure (in this case binary tree) for purposes that you can see below.
The next issue is how to divide up the addresses between the devices. Although it makes sense to allocate the addresses based on a first-come first-serve strategy, that wouldn't give us any routing information. Thus the addresses are given out based on a tree hierarchy, which incidentally, is where the name comes from. Here is how the addresses would look for each device:
All of these addresses are fixed for the position in the tree that a device occupies. You can see that the numbers progress sequentially from top to bottom and left to right as you follow the flow of the tree. Hence the 1st address which corresponds to the first device on the network will be 0. This corresponds to the coordinator and the coordinator's address will always be zero in a tree address allocation scheme. The first device that joins the coordinator will have an address of 1 and it's children will have 2 and 3. The second device that joins the coordinator will have an address of 4 and its children will be 5 and 6.
In more abstract terms, when the coordinator starts the network with the given parameters, then its address space will span from 0 to 6. It takes the '0' address for itself and then splits the remaining addresses among the routers that can join to it. In our case, the first router that joins gets the first half of the space and the second router that joins gets the second half. The following illustration demonstrates how the addresses are split up based on depth. The boxes in blue are the addresses that get taken by the device that owns the space.
Of course this allocation is only based on our simple test case with a maximum of 2 routers and a max depth of 2. Here's how the address is allocated if we change our parameters so we have a maximum of 3 routers and 3 children. We can't have more routers than total children since each router is considered a child. The depth is kept the same.
In case you're wondering how I came up with the total address space, its actually quite simple. For the case with 2 routers, 2 children, and a network 2 deep, the total space is:
Total Space = 2^2 + 2^1 +2^0 = 7
For the case with 3 routers, 3 children, and 2 deep:
Total Space =3^2 + 3^1 + 3^0 = 13
If the number of children equals the number of routers, you can calculate the total number of devices from the following:
And for the general case where the number of children is not equal to the number of routers (ie: end devices also exist) the max number of devices and hence the max value of the address space is:
where Cm = Max End Devices
That's basically how the tree address allocation works for Zigbee. Now that we know how the addresses are doled out, it will be easier to see how they are used for routing.
How Tree Routing Works
If I didn't lose you on the address allocation scheme, then the routing should be a piece of cake. Now that we've established that each device has its own address space based on its depth, then we can determine how to route a frame based on its destination address. There are only two directions a frame can go in tree routing: up the tree or down the tree. If the destination address is within the device's address space, it should be routed down. Otherwise, it will be routed up.
Here's an example of a frame originating from device 2 with a destination address of 6. Each of the arrows are based on comparing the destination address with the device's address space (except the horizontal one which I just used to show the flow). If the destination address lies outside the device's address space, the frame gets routed up. Otherwise it gets routed down.
That's pretty much all there is to tree routing. It is heavily dependent on the addresses of each device and if you understand how addresses are allocated and the concept of each device having its own address space, then understanding how the frames get routed is pretty simple.
The Problems with Tree Routing
Tree routing is a clever and simple way of routing frames without a complex mechanism like AODV or some of the other routing algorithms out there. The big benefit is that it doesn't require tables so you can use tree routing in networks where the devices are very contrained on resources, ie: memory. However there is a fatal flaw in tree routing that renders it almost completely useless in a real world network.
The big problem is that this routing mechanism is fundamentally unreliable because the addresses are static. The position in the tree hierarchy of a device is set once that device joins the network and receives its address and afterwards, it's fairly inflexible to any changes to the network structure. So if a device joins the network and fails or moves out of range, then it will also take out all the devices underneath it in the hierarchy. It is possible to recover from this situation if all of the devices are able to rejoin the network with another parent successfully, however this can be a painful and error-prone process and potentially involve many devices.
Another fatal flaw is that there is no way to recover if the coordinator fails. It is the single point of failure for this routing method. In mesh routing, if the coordinator fails, things are still okay because from a mesh point of view, the coordinator is just another router in the routing tables.
However in tree routing, the coordinator is the vertex of the tree, where all frames must pass if the destination device is not located on the same branch as the source device. If the coordinator fails, then all the main branches become isolated and your network is pretty much useless. Currently, there's no place in the Zigbee spec (that I'm aware of) that describes how to recover from this failure.
From a reliability standpoint, tree routing is fairly dangerous. In fact, it was probably dangerous enough that the Zigbee Alliance decided to remove tree routing and addressing in the Zigbee Pro spec and I suspect that in the future, it may get taken out of Zigbee completely. In the FreakZ stack, tree routing is supported, but it's the frame forwarding method of last resort if all other methods fail.
Well, I hope this little blurb on tree routing was helpful. I don't really mean to knock on the algorithm since I think its pretty clever, but unless the Zigbee spec can address some of its reliability flaws, I would consider it dangerous to use. I guess what I'm implying in this article is that Zigbee shouldn't be used in beacon mode.
How do you like them apples...