Routing Breakthrough Promises Larger Wireless Nets

The Wi-Fi revolution increasingly depends on ad hoc mesh networks to provide smooth connectivity to nodes in motion. Currently, these handy devices only achieve connectivity within a "bubble" established by a centralized RF transmitter. Ad hoc networking would extend that fixed coverage by allowing transmissions to hop from one device to another until a centralized RF node is reached. But they require a complex routing algorithm that adds overhead.

A new wireless-network-routing approach, based on a method called high-speed path propagation (HSPP), posits a solution to those scaling problems. In the approach, devised at Order One Networks Inc. (Toronto), the network overhead associated with routing and addressing does not mushroom as the number of nodes increases. That opens up the possibility for indefinitely large networks.

"The dirty little secret of ad hoc networking is that you can't scale beyond a thousand nodes," said David Davies, a partner with the company. The problem occurs with virtually all current routing protocols for wireless networks.

The reason is the need for a node to query the entire network before it sends a message to some other node. Called flooding, that operation becomes more cumbersome as the number of nodes in the network increases.

Ad hoc networks are used for mobile wireless applications where no fixed network infrastructure exists. Data hops from a source node to neighbors within range; those nodes then forward the data to their neighbors. Since the network topology is constantly changing, establishing a path requires a node to know the location of all nodes in the network, resulting in flooding. But that operation places a large administrative overhead on the nodes that is particularly burdensome for battery-powered mobile devices."All routing methods for ad hoc networks are based on the assumption that you need a global view of the network to establish a path," said Davies.

"Our breakthrough came from the realization that it is possible to establish a path with partial knowledge," he said.

Two nodes that need to communicate establish a core group of nodes that will allow them to create a communications path between them. The core need not be very large, and it will not scale up as the number of nodes increases. The core can also change as nodes move or are added or deleted.

Once the core and propagation path have been established, the nodes in the path indulge in limited flooding of nearby nodes to find the shortest communications path between them. That optimal path is the HSPP. The technique could be applied to a network of any number of nodes without increasing the overhead of the routing algorithm.

The technique might help to realize current plans for extending the Internet to a much more fine-grained level by deploying large numbers of small-scale sensors called motes. Such nodes are very simple and could be used for environmental monitoring, scientific studies or to connect many devices in office buildings and homes."Pervasive networks are 'anything, everywhere' networks," said Davies. "Every 'thing' of interest to us can become a node or can have a node attached to it or embedded in it. Network participants will be you and me, our watches, cell phones, PDAs, automobiles, electrical appliances, motors, lights, roads, animals, clothing, eyeglasses, books, buildings, and on and on. Anything and everything can be part of the network."

Using the HSPP path method, such an all-encompassing network could operate smoothly, no matter how large it was, leading to Davies' concept of "pervasive networking"-instant connectivity anywhere in the world from any point in the environment.