I thought I would spend this portion of the series discussing some of the more detailed parts of the data path. Since the tree and mesh routing is already explained in other articles, I’d like to talk about the other two forwarding methods: broadcasting and the neighbor table.

For those new to the Zigbee spec and trying to implement the broadcast functionality, it can be pretty confusing. At least it was for me when I had to figure it out so hopefully this can help clear some of the haze. Broadcasting plays an important role in Zigbee and is used for many functions. Two of the most prominent are route discovery and group transmissions. Route discovery is the process of locating a path to a destination address whose route is unknown. Zigbee uses a modified form of AODV (Ad-hoc On-demand Distance Vector) which is just fancy terminology for “flood the network with pings until you hit the destination address”. The flooding part occurs by broadcasting route requests and have them propagate through the network until the destination is reached. Group transmissions are a method of transmitting data to all devices within a certain group. A broadcast is used to transmit the data and the frame will be discarded by any members that don’t belong to the group. Along with those functions, there are numerous other smaller functions that utilize broadcasts in both the ZDO (Zigbee Device Object or endpoint 0 on all Zigbee devices) and the ZCL (Zigbee Cluster Library).

To understand broadcasts, it might make sense to discuss some of the different device types a bit. There are three types of Zigbee devices: the coordinator, routers, and end devices. The coordinator is just a router that starts the network. It always has a network address of 0 and mainly performs the function of scanning the network and selecting the channel and ID for the network. A router is a device that has the capability to forward frames and usually, is able to accept child devices. An unfortunate attribute of routers and coordinators in Zigbee is that they’re unable to sleep which is a standard complaint among many people that are investigating using Zigbee for wireless sensor networking. This limitation means that Zigbee routers usually need to be attached to a MAINs power supply.

An end device has no resources to forward frames and can only join and communicate with a parent router. The simplified communication capabilities allow most of the MAC, NWK, and APS management functions to be stripped out and should result in a very small memory footprint. Sleepy end devices are able to be duty-cycled where they sleep most of the time and awaken periodically to poll its parent for any buffered messages. It uses 802.15.4 indirect transmission for the polling, which is discussed in more detail in my 802.15.4 series. Duty cycling the end device allows it to consume very little power, thus increasing the battery life which is one of the most important factors in wireless sensor networking.

So anyways, back to broadcasting. The reason I discussed the device types is because you can target your broadcasts based on the device type. There are four broadcast addresses that can be used depending on your broadcast audience:

Just a note, although low power routers are specified, I haven’t heard of any actual implementations of them yet. Feel free to correct me on this.

Transmitting a network broadcast frame in Zigbee actually sets off a chain of events. If a new broadcast is received, either from another device or from a higher layer, a broadcast transaction record is created. If the frame was received from another device, a copy of the frame is also made and sent up to the next layer for processing.

The broadcast transaction record is used to track the source address and sequence number of the broadcast. These two pieces of information are used to uniquely identify a broadcast frame. This is important because once the broadcast frame is forwarded, all neighbors within earshot will re-send the broadcast frame and you’ll get multiple copies of it. As long as you have the broadcast transaction record, you’ll know that you’ve already received and processed the frame so you can discard the copies.

Broadcast Transaction Record Entry:

The record that was created actually goes into a table called the Broadcast Transaction Table, or BTT. The BTT implements what’s called a passive acknowledgement system, and is used to ensure that all known neighbors have received the broadcast sent by the device. As I mentioned previously, when a broadcast is transmitted, all devices that receive it will broadcast a copy. Each time a copy of the broadcast arrives, the address of the sender will be added to the BTT to mark that it has relayed the broadcast. After a broadcast timeout, if all neighbors haven’t relayed the broadcast, meaning they aren’t present in the BTT, then the original sender will need to do a broadcast retry. This happens until the max retries (usually 3) or all the neighbors show up in the BTT.

Apologies if it might sound a bit confusing. I had to read the broadcast section more than a couple of times and actually wrote some simple simulation programs to gain an understanding of the behavior and the passive ACK mechanism.
 
The problem with the BTT is that it is not very deterministic. If there are a lot of neighbors, ie: the network is dense, then the broadcast transaction table has the potential to become large, eating into the RAM. Thus there is an option in the Zigbee specification to forgo the broadcast transaction table. The tradeoff is that the device will need to broadcast the frame the maximum amount of retries for any broadcast. At first glance, this would be desirable because you can get rid of the BTT which has an unknown number of entries. However this also means that each broadcast will be retried three times (the default retry number), taking a toll on all devices on the network. Each received frame, whether a duplicate or not, requires RAM since it needs to get to the network layer before it can be checked and discarded. If many devices on the network have no broadcast table, then each broadcast would generate a huge amount of traffic, possibly triggering some devices to run out of memory. So when you see warnings in the software documentation that broadcast transmissions should be used sparingly, they’re usually referring to the fact that a broadcast storm may chew up the available RAM in a node.

Since the mesh and tree routing mechanisms as well as the broadcasts have been covered, it's time to discuss the final method of data forwarding, which is the neighbor table. The neighbor table contains a list of the devices that are within transmission/reception range and provide a convenient single hop transmission to the destination. It is also used during the discovery or rejoin process to see if the joining device was previously a child of the node. According to the specification, the neighbor structure contains both mandatory and optional fields. However in actual usage, the optional fields are required since they will be needed by some of the ZDO functions. Just a little gotcha for those implementing their own stack:

Neighbor Table Entry - Mandatory

Neighbor Table Entry - Optional (Not)

The neighbor table is initially populated during device discovery when a device is searching for a parent to join to get on the network. I’ll discuss the join procedure later when I get into the network management side of things. Anyways, when a device tries to join a network, it will first perform a device discovery where it broadcasts a beacon request. All routers within earshot will respond with a beacon frame containing information about themselves. This information will get stored into the neighbor table. Unfortunately, the spec is a bit light on details about populating the neighbor table after the initial join procedure. In order to keep the table up-to-date, any beacons that are seen should be compared to the neighbor table and added to it if an entry doesn't exist.

Well, that kind of takes care of most of the main points of the network layer’s data path. Within the Zigbee stack, or even the full protocol stack including 802.15.4, I’d say that the network layer data path is the most complex. Next up should be the network management which includes device discovery, joining, leaving, and network maintenance.

TrackBack URI for this entry

Comments (4)

Subscribe to this comment's feed

well explained
written by Ward, May 18, 2009

Apologies if it might sound a bit confusing.

No apologies needed, it was very clear.

report abuse

vote down

vote up

Votes: +1

Neighbor tables
written by Robert Cragie, May 18, 2009

Firstly, you're right about low power router broadcast - the address is a placeholder for possible future implementations.

It might be worth pointing out that a neighbor table entry for network discovery is quite distinct from a neighbor table entry for an 'active' neighbor, i.e. one you are in active communication with, which could be a parent, sibling router or child. So whilst the two have been coalesced in the ZigBee spec., it probably makes more sense to think of them as separate entities.

report abuse

vote down

vote up

Votes: +0

...
written by Akiba, May 18, 2009

Hi Robert.
Thanks for the comments. My understanding of the spec is just based on my interpretation, which required quite a bit of imagination. However I'm a bit confused that there are two distinctions between neighbor entries. The reason I mentioned that the optional fields (for discovery) were not optional is because the ZDO LQI response, which asks you to dump the neighbor tables, requires information like the depth and permit joining fields. Although these fields in the neighbor table are optional in the spec, the ZDO LQI Server handling is mandatory in the Zigbee Residential compliance document. So my interpretation is that these fields are also mandatory. It caused me a lot of head scratching.

Other than that, I pretty much never use the optional fields so the neighbor entries are just used to check if I can do a single hop to the destination.

If my understanding is mistaken, feel free to let me know.

report abuse

vote down

vote up

Votes: +0

...
written by newbie here, May 11, 2011

So I see that the comment list on this blog entry is not active, but wanted to ask a question, just in case.

Wouldn't the re-broadcasting go to an endless loop, if every device rebroadcasts original frame, and the end devices that end up receving rebroadcasts from other devices, broadcast that again. I mean, since end devices need not support BTT?
Or is it so, that the end devices will rebroadcast a frame, only if it is originating from the Coordinator?

report abuse

vote down

vote up

Votes: +0

Show/Hide comment form

Name

Email

Website

Title

Comment

smaller | bigger

Subscribe via email (Registered users only)

I have read and agree to the Terms of Usage.

Add Comment