Reducing Routing Overhead in a Growing DDN

The Defense Data Network (DDN), based on ARPANET technology, is expanding rapidly. One segment of the DDN, the MILNET, will include 250 packet switching nodes by the end of 1987 and as many as 700 by 1991. One obstacle that must be overcome to allow this growth is the overhead associated with the current ARPANET dynamic routing mechanism. Both link utilization due to routing updates and routing computational load are roughly proportional to network size. This paper presents three approaches to reducing routing overhead and includes both modifications to the existing routing scheme and a design for a hierarchical extension.