New Models and Algorithms for Future Networks

Abstract

In future networks, transmission and switching capacity will dominate processing capacity. In this paper we investigate the way in which distributed algorithms should be changed in order to operate efficiently in this new environment. We introduce a class of new models for distributed algorithms which make explicit the difference between switching and processing. Based on these new models we define new message and time complexity measures which, we believe, capture the costs in many high-speed networks more accurately then traditional measures. In order to explore the consequences of the new models, we examine three problems in distributed computation. For the problem of maintaining network topology we devise a broadcast algorithm which takes O (n) messages and O (log n) time for a single broadcast in the new measure. For the problem of leader election we present a simple algorithm that uses O(n) messages and O (n) time. The third problem, distributed computation of a “globally sensitive” function, demonstrates some important features and tradeoffs in the new models and emphasizes and differences with the traditional network model. The results of this paper influenced later research, as well as the design of IBM Networking Broadband Services (NBBS). © 1995 IEEE