Order One Network Protocol

From Wikipedia, the free encyclopedia

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.

Contents

[edit] 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.

[edit] 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 is unusual, interesting and efficient because it does not need a complex routing algorithm or large amounts of communication.

[edit] 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 protocol uses Dijkstra's algorithm to continuously optimize and maintain the route. As the network moves and changes, the path is continually adjusted. To reduce routing bandwidth, updates are sent using a fisheye optimization that reduces the probability of transmitting an update to farther nodes.

[edit] 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 not 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 link-state routing information or driving routing by connection requests. OORP instead scales to 100,000's of nodes and can often achieve reasonable performance even though it limits routing bandwidth to 5%.

[edit] 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, farther away from the central nodes, the bandwidth grows.

For example, 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 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.

The link propagation time establishes a limit on the speed that a network can find its root. This could limit application of the protocol to long distances or slower links.

OORP does not include security or authentication. If the network will be subject to attack it is recommended that security and authentication should be used in addition to OORP.

[edit] See also

[edit] External links