Abstract

The science of complexity theory, whose fundamentals have been developed over many decades, is poised to provide a new perspective to computer science and to computer networking in particular. An understanding of complexity theory will enable better system performance and add novel features as well as better security. A network of communicating nodes, each linked to its nearest neighbor and attempting to optimize performance based upon as local information in order to reduce overhead, is a tangible realization of a complex system. We examine how the tradeoff between computation and communication can be made in such a complex environment using Active Networking and Kolmogorov Complexity. We begin with a very brief overview of complexity theory and computer networking; a basic definition of complexity known as Kolmogorov Complexity is explained. Such information theoretic pioneers as Andre Kolmogorov, Raymond Solomonoff, and Gregory Chaitin developed Kolmogorov Complexity. In fact, Kolmogorov Complexity and Algorithmic Information Theory are sometimes referred to as Kolmogorov-Chaitin Complexity. The advantages and disadvantages of Kolmogorov Complexity are discussed, including its incomputable nature. The design of algorithms to obtain computable estimates of Kolmogorov Complexity is explored, as well as additional applications of Kolmogorov Complexity for communication networking. Once the concept of Kolmogorov Complexity is presented, we apply complexity theory, and Kolmogorov Complexity in particular, to active networks. Active networks form an ideal environment in which to study the effects of tradeoffs 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. There are interesting relationships between Kolmogorov Complexity, prediction, compression and model size used in a particular predictive management system known as Active Virtual Network Management Prediction (AVNMP)