G409 DARPA Progress Report 1998

Survivable Real-Time Network Services


Develop robust heuristic algorithms for the automatic configuration and source authentication of distributed algorithms in very large networks.


When networks with many thousands and even millions of servers and clients become fragmented, some network services, such as authentication and time synchronization, may be lost. Our approach to survivability in such scenarios is based on the ability of the service to continue operation by automatically reconfiguring substitute servers in surviving fragments, then coalescing them with other distributed servers when connectivity is restored.

This work extends the autoconfigure and autokey technology developed in previous work to very large networks that may suffer significant damage due to failures and hostile attack. autoconfigure uses Internet multicasting and crafted algorithms to detect multiple remote servers and configure suitable redundant and diverse client-server configurations. autokey uses backward hashing and public-key signatures to provide secure source authentication with manageable overhead.

Recent Accomplishments

The protocols and algorithms developed previously have shown promise, but have exposed a number of issues that urgently need to be studied, resolves and verified in the context of very large, survivable networks. Specifically, the following problems remain:

  1. The autoconfigure algorithms, while refined, simulated and evaluated, have not yet been completely implemented in the test vehicle, NTP Version 4, and tested under real world conditions. These algorithms must be augmented with additional span limit and implosion resistant mechanisms to be truly effective in damaged networks.
  2. The autokey algorithm has been implemented and tested in small scale; however, testing has revealed a number of problems with the basic Unix sockets paradigm. Resolution of these problems may require a new look and revision of the design and implementation.
  3. In testing, the preliminary autoconfigure/autokey implementation has raised interesting issues of key management quite different from conventional systems, where keys and key-pairs are generated before use and have a generally long lifetime compared to message propagation times. In autokey, keys are generated randomly and used only once, but may need to persist in the key cache if a subsequent message is lost. A significant problem may occur if these keys collide with others as they are generated.

Current Plan

  1. Extend the current autoconfigure model by refining old algorithms and devising new ones to discover and configure new protocol instantiations in very large numbers of hosts and routers. These instantiations will include, but are not limited to time synchronization services and the Internet.
  2. Extend the current autokey security model and authentication scheme to operate with new security features and services, specifically Kerberos, Secure DNS and other ubiquitous services as they become available.
  3. Incorporate the new algorithms in the existing NTP simulator ntpsim and in other simulators as available. Evaluate their performance using network topologies and failure scenarios typical of both Internet and DSI services.
  4. Incorporate the new algorithms in the NTPv4 daemon for Unix, Windows and VMS. Test and evaluate them in the context of DARTnet/CAIRN and attached experiment networks, then in NIST and USNO subnetworks and, eventually, the general Internet population.
  5. Develop the formal specification of NTPv4 as an extension of the current NTPv3 specification RFC-1305 to include the new architecture and protocol models. Update the current SNMP MIB for NTP to include the new features.

Technology Transition

  1. Research findings, including results from analysis and experiment, as well as hardware and software descriptions, will be published in the open scientific literature and on the World Wide Web.
  2. Current status and briefing presentations will be made available on the World Wide Web.
  3. Sources and documentation for designated operating system software deliverables, including the Network Time Protocol Version 4, will be freely available from Internet FTP servers.
  4. Hardware documentation in the form of circuit schematics, PCB artwork and drill templates will be freely available from Internet FTP servers.
  5. Protocol specifications and associated documentation will be published in RFC form for consideration by the IETF standards apparatus.
  6. Research findings will be presented to the DoD and HPCC community in regular meetings sponsored wholly or in part by DARPA.
  7. Assistance will be provided to government agencies of the U.S. and other countries in setting up and operating networks of NTP servers.