How to develop a new protocol

Today a not-so-small post about protocol development.

One of the recurring themes in the ns-3 users group is:
"How do I develop [my own, a new, a modification] [routing, scheduling, MAC, etc.] protocol."

There are many possible answers, depending on the case, but basically the root is always the same. When you reach the point of asking this, you have done a mistake in your development process.

I'll limit the scope of this post to a subset of the above possibilities. However, I'll try to be as generic as possible, in order to fit also the other cases.
Let's assume the question is:

"How do I develop a new routing protocol."

and let's assume you want to use ns-3. Because this blog is about ns-3, mainly.

In order to write a new routing protocol (any protocol, indeed), the following steps are required:

1. Requirement analysis
2. Protocol Design
3. Development
4. Test

Usually you'll want to iterate through these steps (at least through 2-4), much like in agile programming.

Let's see what one should expect from each phase.

Requirement analysis

The requirement analysis should fix what are your goals, the nodes capabilities and so on. Don't ever say "it's obvious". Requirements are never obvious. Check RFC 5826 for a routing requirement document example.

Protocol Design

This is the phase where you write down your protocol. Remember that you have to write (at least) THREE things:

1. Format - how the packet is made, the length of each field, the encoding, etc.
2. Syntax - what's the meaning of the data carried by the packet (again, it's not "obvious")
3. Semantic - what's the behaviour of a node upon receiving a packet, what, when and why a packet have to be sent.

A lot of people forget one of these elements, basically making it impossible to implement the idea.

One very important thing: remember the data. Data are not "known", they must be measured. A node doesn't know the channel quality, it measures the channel quality. If you plan to use something in your protocol, make sure to be able to measure it !
I've seen far too many "scientific" papers with this mistake. A success, for the authors. A fail, for the reviewers. A shame, for the scientific community.

Summarising:

• Collect data and extract measures from data.
• Send the measures to other nodes when something happens.
• React upon receiving a message.

Development

If you reach this stage, and your design was done in the right way, it's simply a matter of coding.

The format: define a new set of headers (or data packets) carrying your informations. Remember that measures will have to be device-independent. As an example, suppose you want to send "3.14". You will not send a double in the packet, you'll send a given number of bits representing "3.14". There are a number of ways to do this, just choose the one that suits you.

The syntax: it's how you write and read the packets. What's the meaning of each field. In ns-3 terms, it's the Serialize and Deserialize functions.

The semantic: open some sockets to receive the messages from other nodes, open some sockets to send the packets to other nodes (they could as well be the same ones), and write the logic of each function.

Testing

Once everything is done, remember to test your shiny new protocol. I'd strongly suggest to write specific tests to check all the functionalities, especially the error cases. You know, shit happens, so better to check that your protocol gracefully recover from it.

ns-3 specific tricks

This is quite specific to ns-3, but any simulation (or real) system will have something similar.

Let's not forget that we was talking about a routing protocol. Thus, it's logical that the protocol semantic will build a routing table. Not a big issue. Usually a routing table is little more than: 1) destination (e.g., 2001:db8:f00d:cafe::/60), 2) next hop (e.g., fe80::21b:63ff:fef0:6acd), 3) interface, 4) prefix to use (if necessary).

The routing table will be used in two places: RouteOutput and RouteInput.

• RouteOutput: the obvious one. It's called when a packet is being sent.
• RouteInput: the not-so-obvious one. It's called when the packet is received, to decide if it has to be forwarded or it's for the node itself.

Indeed, RouteInput is the real "routing" one: it decides if the packet has to be forwarded, what outgoing interface has to be used in the forwarding, etc.

RouteOutput "simply" finds out the optimal routing when a packet is sent from the local node.

When a packet is created and sent, it will pass thru multiple RouteOutput (yes, more than once, thanks to UDP, IP, etc.), then from RouteInput (once for each router is passes thru and once for the destination node).

Suggestions to understand all this? Find a "simple" routing protocol and study its specification and the implementation.

Example: RIPng for IPv6 (RFC 2080). It's short, simple and well written. The implementation for ns-3 is expected to be available starting from ns-3.20.