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 2000 B/s 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

Each node periodically sends a "hello" message on its links. Its neighbors reply. Each neighbor tells how many neighbors it has, how many connections it has, and who its mama is. The node stores the fastest-responding neighbors with the most links. A node stores as many neighbors as it can, and loses track of less well-connected neighbors.

Each node selects the neighbor with the largest access to links and calls it "mama." Note that "mama" nodes tend to have larger lists, and respond faster, which should indicate a more central node with a better computer and network machinery that can send data more quickly.

When two nodes select each other as mama, that is the top of the local network's hierarchy. In practice, local tops of the hierarchy are established, and then broken as the counts of links propagate farther.

Routing

When a node wants to reach another node and a route does not currently exist, it sends the request to mama. Mama forwards it to its mama, etc. Each node sends its address up the hierarchy. The hierarchy is also used to establish routing information with the more central servers.

When they connect at the root, the routing algorithm then performs Ant colony optimization, that is, it tries to cut corners and find routes that are more optimal. It does this by having each node on the route flood its neighbors with routing requests. Whenever a faster route is found, the unused part of the previous route is erased, and flooding of route requests ceases on that route. This is like the way ants optimize a food-gathering path- they find a path, then begin to cut corners, shortening the path. All control bandwidth is limited to less than 5% of total node to node bandwidth.

The route therefore walks across the mesh into a path that will be a close approximation of the fastest path. The route will also dynamically reorganize as nodes move.

Advantages

The network establishes pretty good routes in real time, and substantially reduces the number of messages sent to keep the network connected, compared to many other protocols. Many of the simpler mesh routing protocols just flood the whole nework with routing information whenever a link changes.

Although routing information is somewhat centralized, the data transfer is decentralized, and should therefore have good performance.

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.

Critiques

Central nodes have an extra burden. At some number of nodes, the network will therefore cease to scale.

The directory algorithm has issues. The nodes must poll for contact requests in order to fix failures of the central nodes. Therefore, this poll time is the upper limit on the time to find another node. To reduce this, the polling algorithm must trade off network congestion at the central nodes, connection latency and the central nodes' memory. The scheme therefore limits the size of the network.

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.

Even though the flooding of routing requests is localized, and limited in time and percent of network bandwidth, it may use more power and bandwidth than an optimized link-state protocol, such as the Hazy Sighted Link State Routing Protocol.

Since the descriptions do not include distributed security and authentication, OORP is subject to spoofing. Attacks could divert and read messages by lying about the address, by establishing a false central hierarchy, or by routing the network through a reader. Denial of service could occur by establishing a false central router, and selectively denying connections, or by suboptimizing the routing.

External link

OrderOne Networks- allegedly includes Java simulations and animations, as well as commercial implementations for sale.