Rather than have a comprehensive structure that is created apriori, have structures that emerge in response to a need - in this case the need to communicate. Such a structure can optimize for the current need. In addition, the fact that the structure already emerges and adapts to the traffic pattern makes it easier to extend it to change and adapt to other conditions, like failures and congestion, as well.
An Emergent Network uses a very simple strategy for building such a system. When a source needs to communicate with a destination, it first searches for the destination by sending out a search message. The search message accumulates knowledge of its paths as it travels. When the destination recieves the search msg, it responds to the first such search message (assuming that since this message arrived first it travelled along the faster path) by sending back a path setup msg along the path the search msg travelled. As the path setup travels back to the source it sets up routing table entries pointing to the destination. in each of the processors through with it travels. One can think of this as ants laying down pheromones from a food source so that subsequent ants can get there. Once a path is set up the source can then use that path for subsequent messages to that destination. Each processors has a limited amount of memory allocated for routing tables - hence every processor is a potential router. A path setup message marks processors it passes through with an entry for the destination. Reuse of a path by messages re-enforces a path. If the table is full the LRU entry is replaced. In this way old paths get forgotten over time in favor of current paths. Broken paths, either because a processor no longer has the routing entry or the next processor does not respond, can be corrected by initiating a limited range search for either processors that know the path to the destination, or for the destination. The search is performed by generating a search wave, which is similar to a bfs tree generated from the source, or like a forest fire that travels radially away from the source. The advantage of using a wave is that it finds close to the shortest path (it may not be the shortest because of asychronicity in messages but it is close) in isolation. When there is congestion along the way, the wave gets dampened in that direction by the messages getting delayed. Hence it also responds to congestion existing in the system. The search message itself adds to congestion therefore one can perform limited range searchs, or if the algorithm has some apriori knowledge of the proximity of the destination that can be incorporated. The emergent communication structure has many desirable propeties. It choses efficient paths that try to minimize the distance travelled between source and destination and chose the path with the fastest time response and therefore less congestion. Also it automatically creates a network structure that is tailored to the application structure by reflecting the communication pattern. Rather then creating a specialized network for each of these applications the emergent network automatically evolves the correct network structure for the problem. |
This picture shows a search wave. The maximum congestion (dark red)
occurs along the end of the search wave.
In this picture the fastest path found avoids the existing area of congestion. |