Order One Network Protocol
Encyclopedia
The OrderOne MANET Routing Protocol is an algorithm
for computer
s 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 network
s.
OON's designers say it can handle thousands of nodes, where most other protocols handle less than a hundred. OON uses hierarchical algorithms to minimize the total amount of transmissions needed for routing. Routing overhead is limited to between 1% to 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. This route is continuously maintained.
Each process can be performed with localized minimal communication, and very small router tables. OORP requires about 200K 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.
At the top, one or two nodes are unable to find nodes better-connected than themselves, and therefore become parents of the entire network.
The hierarchy-formation algorithm does not need a complex routing algorithm or large amounts of communication.
The commercial protocol uses Dijkstra's algorithm
to continuously optimize and maintain the route. As the network moves and changes, the path is continually adjusted.
Since the control bandwidth is defined to be less than 5% regardless of network size, the amount of control bandwidth required is not supposed to increase as network size grows.
The system can use nodes with 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.
Most routing protocols scale either by reducing proactive link-state routing information or reactively driving routing by connection requests. OORP mixes the proactive and reactive methods. Properly configured, an OORP net can scale to 100,000's of nodes and can often achieve reasonable performance even though it limits routing bandwidth to 5%.
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 farther away from the edge nodes the more the bandwidth grows.
These critiques may have no practical effect. For example, consider a low bandwidth 9.6Kbit/second 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 up to 80 route updates. Thus even in very low bandwidth network the protocol is still able to spread a lot of route information. Given a 10Mbit connection, 3% of the bandwidth is 4,100 to 16,000 route updates per second. Since the protocol only sends route updates for changes, it is rarely overwhelmed.
Public proposals for OON do not include security or authentication. Security and authentication may provided by the Integrator of the protocol. Typical security measures include encryption or signing or the protocol packets and incrementing counters to prevent replay attacks.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for computer
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
s communicating by digital radio
Digital radio
Digital radio has several meanings:1. Today the most common meaning is digital radio broadcasting technologies, such as the digital audio broadcasting system, also known as Eureka 147. In these systems, the analog audio signal is digitized into zeros and ones, compressed using formats such as...
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 network
Wireless mesh network
A wireless mesh network is a communications network made up of radio nodes organized in a mesh topology. Wireless mesh networks often consist of mesh clients, mesh routers and gateways.The mesh clients are often laptops, cell phones and other wireless devices while the mesh routers forward traffic...
s.
OON's designers say it can handle thousands of nodes, where most other protocols handle less than a hundred. OON uses hierarchical algorithms to minimize the total amount of transmissions needed for routing. Routing overhead is limited to between 1% to 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. This route is continuously maintained.
Each process can be performed with localized minimal communication, and very small router tables. OORP requires about 200K 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
The network nodes form a hierarchy by having each node select a parent. The parent is a neighbor node that is the next best step to the most other nodes. This method creates a hierarchy around nodes that are more likely to be present, and which have more capacity, and which are closer to the topological center of the network. The memory limitations of a small node are reflected in its small routing table, which automatically prevents it from being a preferred central node.At the top, one or two nodes are unable to find nodes better-connected than themselves, and therefore become parents of the entire network.
The hierarchy-formation algorithm does not need a complex routing algorithm or large amounts of communication.
Routing
All nodes push a route to themselves to the root of the tree. A node wanting a connection can therefore push a request to the root of the tree, and always find a route.The commercial protocol uses Dijkstra's algorithm
Dijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
to continuously optimize and maintain the route. As the network moves and changes, the path is continually 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 is defined to be less than 5% regardless of network size, the amount of control bandwidth required is not supposed to increase as network size grows.
The system can use nodes with 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.
Most routing protocols scale either by reducing proactive link-state routing information or reactively driving routing by connection requests. OORP mixes the proactive and reactive methods. Properly configured, an OORP net can scale to 100,000's of nodes and can often achieve reasonable performance even though it limits routing bandwidth to 5%.
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 farther away from the edge nodes the more the bandwidth grows.
These critiques may have no practical effect. For example, consider a low bandwidth 9.6Kbit/second 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 up to 80 route updates. Thus even in very low bandwidth network the protocol is still able to spread a lot of route information. Given a 10Mbit connection, 3% of the bandwidth is 4,100 to 16,000 route updates per second. Since the protocol only sends route updates for changes, it is rarely overwhelmed.
Public proposals for OON do not include security or authentication. Security and authentication may provided by the Integrator of the protocol. Typical security measures include encryption or signing or the protocol packets and incrementing counters to prevent replay attacks.
See also
- DSRDynamic Source Routing'Dynamic Source Routing' is a routing protocol for wireless mesh networks. It is similar to AODV in that it forms a route on-demand when a transmitting computer requests one...
, AODV and OLSR are public-domain mesh network protocols. - The Ad hoc routing protocol listAd hoc routing protocol listAn ad-hoc routing protocol is a convention, or standard, that controls how nodes decide which way to route packets between computing devices in a mobile ad hoc network ....
describes more protocols. - Dijkstra's algorithmDijkstra's algorithmDijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
External links
- Fortress Technologies - A licensee of OrderOne Networks
- Navy Assessment - An independent test conducted by the Navy
- OrderOne Networks - provides commercial implementations for sale.
- AFCEA Signal Magazine Article - An article in Signal Magazine describing the OrderOne Networks protocol.