Accession Number:



Imperishable Networks: Complexity Theory and Communication Networking-Bridging the Gap Between Algorithmic Information Theory and Communication Networking

Descriptive Note:

Final technical rept. Jun 2001-Dec 2002

Corporate Author:


Report Date:


Pagination or Media Count:



The most significant result from this project has been experimental validation that complexity plays a critical role in information assurance and can be broadly applied as the basis for security analysis and fault tolerant network design. Complexity Theory is a large and rapidly evolving science. As progress is made in various topics of Complexity Theory, the individual topics will help to re-enforce each other. Our goal has been to reduce the requirement and dependence upon detailed a priori information about known attacks and detect novel attacks by computing vulnerability and detecting anomalous behavior based upon an inherent, fundamental property of information itself, namely, its complexity and sophistication. Results of complexity measures applied to network protocols, processes, and information have been presented and related to Information Assurance and network fault tolerance. Active networks form an ideal environment in which to study the effects of trade-offs in algorithmic and static information representation because an active packet consists of both code and static data. The code can contain the protocol or a compressed form of the data to be transported. If the code is the protocol, then information about the complexity of the protocol can be gleaned from the active packet code. An active packet that has been reduced to the length of the best estimate of the Kolmogorov Complexity of the information it transmits will be called the minimum size active packet. There are interesting relationships between Kolmogorov Complexity, prediction, compression and the model size used in the Active Virtual Network Management Prediction AVNMP mechanism. These relationships are throughout this report.

Subject Categories:

  • Computer Programming and Software
  • Computer Systems
  • Radio Communications

Distribution Statement: