Home arrow Blog arrow Zigbee arrow Zigbee Tree Routing - How It Works and Why It Sucks
Zigbee Tree Routing - How It Works and Why It Sucks | Print |
Written by Akiba   
Sunday, 11 January 2009

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:

Basic Tree Network

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:

Basic Tree Network with Addresses

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.

Address Allocation

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. 

Address Allocation - 3 Routers

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.

Zigbee Tree Routing

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...

Hits: 30522
Comments (2)Add Comment
written by Duckyduck, May 13, 2009
Hmmm, you're spot on here I think. Another big drawback is that devices "can't leave", that means the address assigned to the device is assigned forever. Because of this a network can get stuck (don't allow any new associations) even if there's no active device in the network anymore (has (physical) left/dead).
So the leave function is dangerous in Tree like systems.

What I wonder is that you mention that you use tree routing as last resort if anything else fails. But imho that's not possible when you make a PRO stack because of the random address assignment in PRO?

Thanks again!
report abuse
vote down
vote up
Votes: +1
written by Akiba, May 13, 2009
My stack hasn't been modified for Pro. I was initially targeting Zigbee 2007 Residential which would have been the quickest route to certification. However after discussing it with other Zigbee members, I found that Pro is the defacto standard and nobody really uses Residential anymore. So it looks like I'm going to need to convert the stack if I want to get it certified. Of course, the unfortunate thing is that Zigbee also announced they're moving to IP which means that the lifetime of my Pro stack will probably be pretty short before it needs to get changed again. Ahhhh...the trials and tribulations of stack design.
report abuse
vote down
vote up
Votes: +2

Write comment


Discuss (2 posts)
Zigbee Tree Routing - How It Works and Why It Sucks
Jun 23 2009 09:55:06

Re:Zigbee Tree Routing - How It Works and Why It Sucks
Jun 23 2009 15:41:55
Unfortunately, I am completely illiterate in NS2. However if you have any questions on the protocol, feel free to ask.

< Prev   Next >