Order One Network Protocol

The Order One Routing Protocol is an algorithm for computers communicating by digital radio in a mesh network to find each other, and send messages to each other along a reasonably efficient path. It was designed for, and promoted as working with wireless mesh networks.

OORP's designers say it can handle "hundreds of thousands" of nodes, where most other protocols handle hundreds. OORP uses hierarchical algorithms to minimize the total amount of transmissions needed for routing. Routing overhead is limited to less than 5% of node to node bandwidth in any network and does not grow as the network size grows.

The basic idea is that a network organizes itself into a tree. Nodes meet at the root of the tree to establish an initial route. The route then moves away from the root by cutting corners, as ant-trails do. When there are no more corners to cut, a nearly optimum route exists.

Each process can be performed with localized minimal communication, and very small router tables. OORP requires about 150K of memory. A simulated network with 500 nodes transmitting at 200 bytes/second organized itself in about 20 seconds.

As of 2004, OORP was patented or had other significant intellectual property restrictions. See the link below.

Assumptions

Each computer, or "node" of the network has a unique name, at least one network link, and a computer with some capacity to hold a list of neighbors.

Organizing the tree

Conventional hierarchical routing protocols such as HSR or LANMAR create a hierarchy by breaking the network into many small groups. They they create groups of groups, and so on to form the hierarchy. This hierarchy is then used to route data through the network. This approach has a number of inherent flaws:

- Packets need to be routed through cluster heads which cause congestion and hot spots
- Since the set of groups in which a node belongs is used to route packets to a particular node, as that node moves thorough the network it becomes virtually impossible to maintain a continuous flow of data to and from that node.
- If enough nodes are moving, the hierarchy itself will never be able to form and data will be unable to move.

The OrderOne Networks protocol takes a very different approach. It is able to reveal the hierarchy that is present in any network. This hierarchy is a direct reflection of the topology of the network that underlies it. The hierarchy is not used to route data, it is only used to help find the first route between newly connected nodes. This approach removes the problem of cluster-head hot spots and is also very resilient to mobility.

The hierarchy is form by having each node select 'that neighbor node that is the next best step to the most other nodes' as its parent node. This implicitly creates a hierarchy around those nodes that are more stable, with more capacity, closer to the topological center of the network.

Routing

All nodes push a route to themselves up this revealed tree. This ensures that a node looking to establish a connection with another node will be able to find that new route by searching up the revealed tree.

When a node wants to establish a connection to another node, it makes use of this hierarchy to pull the required route information to itself. The protocol then makes use of Dykstra's algorithm to continuously optimize and maintain the route.

As the network moves and changes the path is continuously adjusted.

Advantages

Assuming that some nodes in the network have enough memory to know of all nodes in the network, there is no practical limitation to network size.

Since the control bandwidth fixed at less than 5% regardless of network size, the amount of control bandwidth required will no increase as network size grows. All other routing protocols require more bandwidth as the network size grows and as node mobility increases.

The system works with nodes using small amounts of memory.

The network has a reliable, low-overhead way to establish that a node is not in the network. This is a difficult, valuable property in ad-hoc mesh networks.

Since other routing protocols require more and more bandwidth as network size increases, they are unable to match the scaling capability of the OrderOne Networks protocol that requires only a limited fixed amount of control bandwidth.

Critiques

Central nodes have an extra burden because they need to have enough memory to store information about all nodes in the network. At some number of nodes, the network will therefore cease to scale.

If all the nodes in the network are low capacity nodes the network may be overwhelmed with change. This may limit the maximum scale. However, In virtually all real world networks, the further you move away from the leaf nodes, the more bandwidth is available. For the protocol to function well a node needs to be able to store information about all the nodes that are below it in the hierarchy. A numerical example can help make this clear. If a low bandwidth radio has 9.6Kbit radio, If the protocol was configured to send one packet of 180 bytes every 5 seconds, it would consume 3% of overall network bandwidth. This one packet can contain anywhere from 20-80 route updates. Thus even in very low bandwidth network the protocol is still able to spread alot of route information. If we move up to a 10Mbit connection, the protocol can send (using the same 3% number), between 4,100 and 16,000 route updates may be sent every second. Since the protocol only sends route updates when something changes, except in very extreme cases, it will not be overwhelmed.

The link propagation time establishes a limit on the speed that a network can find its root. This is not a bad problem for a radio protocol operating over short distances, but it might limit application of the protocol to long distances or slower links.

The OrderOne Networks protocol does not include security or authentication. If the network will be subject to attach it is recommended that security and authentication should be used in addition to the OrderOne Networks protocol.

External link

OrderOne Networks - provides as commercial implementations for sale.
AFCEA Signal Magazine Article - An article in Signal Magazine describing the OrderOne Networks protocol.