An adaptive path discovery process for routing data packets in a multinode network

摘要

A process for discovering a path from a source node to a destination node through a network by using "collisions" ofrandomly-propagating "feeler" packets (122) originating from both the source node (68) and the destination node (70). A discovered path is reported to the source node (68) by the collision-detecting node where it may be stored and updated responsively to reports of new feeler packet collisions. Paths discovered and reported may be analyzed at either the collision-detecting node or the originating node to remove loops. The random collision-detecting path-discovery procedure reduces the operational traffic overhead associated with other exponentially-proliferating discovery methods. The feeler packets (122) are propagated randomly through the network topology, thereby imposing relatively uniform path-discovery traffic effects in the network. Path discoveries arising from feeler-packet collisions always reflect current network topology and traffic conditions. The origination rate of feeler packets (122) may be adjusted responsively to changes in demand, cost or other parameters. <IMAGE>