In many cases, there is a need to manage a local addressing realm from a manager site located outside the realm. A particular important example is the case of NM service providers who provide network management services from a remote site. Such providers may have many customers, each using the same private address space. When all these networks are to be managed from a single management station, address collision may occur. One way to overcome address collision is to use network address translation (NAT). The problem is that many network management applications use IP address information at the application level. Therefore, in order to work correctly, these NM applications should be aware of NAT. However, most commonly used NM applications are unaware of NAT and are most likely to remain so in the near future (due to the large investment involved). This paper describes a design and implementation of a solution that is transparent to the network management application (but not to the user), and does not require a general reconfiguration of a large portion of the network. It converts conflicting addresses into non-conflicting addresses by combining NAT and SNMP payload translation, and allows multiple private networks to be managed on a single management platform.

In many cases, data networks need to be monitored to ensure that they stay within acceptable parameters. The monitoring consists of measuring properties of the network, and of inferring an aggregate predicate from these measurements. In many cases it is too complex, or too expensive, to conduct explicit monitoring at all times. In these cases, information (integrity constraints) on the evolution of the network status can often allow us to use past measurements to infer the future behavior, thus reducing the monitoring cost. We provide a formal description of the problem of monitoring rapidly changing data, which we call the monitoring problem. We then classify this problem in terms of the integrity constraints that govern the evolution of the environment, and propose different algorithms for each of these classes. For the most restricted case, we can find a greedy algorithm which is optimal, while for the more general cases, we use competitive analysis and show that optimal worst and average case cost measuring algorithms exist. We then present heuristics for low-cost low-complexity measuring algorithms. We believe that the results of this paper can serve as a framework for further studies.

Event correlation is a key functionality of a network management system that is used to determine the root cause of faults in a network, and to filter out redundant and spurious events. A number of event correlation systems have been proposed. The event correlation systems generally combine causal and temporal correlation models with the topology of a network. The power and robustness of the models used and the algorithms developed vary from system to system. However, in the absence of a simple, uniform, and precise presentation of the event-correlation problem, it is impossible to compare their relative power or even analyze them for their properties. In general, causal and temporal-based correlation models have not been rigorously presented or thoroughly investigated. In this paper we formalize the concepts of causal and temporal correlation using a single conceptual framework. We characterize various properties of the framework. We can characterize existing systems based on the formal properties of our framework, and we consider one system as an illustrative example.

Many rapidly-changing environments need to be monitored to ensure that they stay within acceptable parameters. The monitoring consists of measuring properties of the environment, and of inferring an aggregate predicate from these measurements. In many cases it is too complex, or too expensive to conduct explicit monitoring at all times. In these cases, information (integrity constraints) on the evolution of this environment can often allow us to use past measurements to infer the future behavior, thus reducing the monitoring cost. We provide a formal description of the problem of monitoring rapidly-changing data, which we call the monitoring problem. We then classify this problem in terms of the integrity constraints that govern the evolution of the environment, and propose different algorithms for each of these classes. For the most restricted case, we can find a greedy algorithm which is optimal, while for the more general cases we use competitive analysis and show that optimal worst- and average-case cost measurement algorithms exist. We then present heuristics for low-cost low-complexity measurement algorithms. We believe that the results of this paper can serve as a framework for further studies.

An important aspect of network management is fault management-determining, locating, isolating and correcting faults in the network. The paper deals with the algorithms for detecting faults, i.e., behavior of the network different from specifications. It is important for communication networks to detect faults "in-process" i.e., while the network is in its normal operation. Thus, we detect faults by examining the input-output behavior without forcing the system to specialized inputs explicitly for testing. Such testing is commonly called passive testing. We model the network as a finite state machine and develop procedures for passive testing including the required data structure, efficient implementations and the complexity of our procedures. We start with fully observable and deterministic machines and then study more realistic models: partially observable and nondeterministic machines. We also discuss extensions to communicating finite state machines and machines extended with parameters and variables. We apply our techniques to management of a signaling network operating under the Signaling System 7 (SS7) and report experimental results, which show the feasibility of applying passive testing to practical systems.

Network management is an increasingly important area of research dealing with continuously evolving artificial complex systems. We look at the important network management process of provisioning, which involves all activities to implement changes to the network. Typical provisioning activities include addition or deletion of customers and network elements, growth of the network, and load balancing. We present a new method for specifying and analyzing provisioning workflow. Our method is based on representing workflow by finite state machines augmented with the notion of attribute sets. Such a representation allows us to study important properties of the workflow, and analyze it to detect inefficiencies. We also provide an example of the application of this technique to a trunk provisioning workflow.

Consideration is given to the layout of bounded fan-in and fan-out prefix computation graphs in VLSI, and it is shown that the area requirements of such graphs exhibit this interesting property. A small constant factor reduction in time of computation from 2 log eta to log eta increases the area required to embed an eta node prefix computation graph significantly from O( eta log eta ) to Omega ( eta /sup 2/). The area requirements are also given. This behavior is an example of an extreme area-time tradeoff in VLSI. Since prefix computation also models the carry computation in a carry look-ahead adder, the same behavior is observed in the area requirements of a near-minimum computation time carry look-ahead adder. The authors also present circuits which meet the derived lower bounds for all values of T between log eta and 2 log eta .>