Research activities

Heegaard’s research interest is on QoS evaluation and management in network systems and services. A combination of QoS evaluation methods has been research topics and been applied to evaluate systems and services. Of special interest in simulation has been simulation of systems where the events of importance occur with low frequency. This calls for speed-up techniques and in his thesis (supervisor: Bjarne E. Helvik) Heegaard proposed heuristics to enable importance sampling to be efficiently applied in rare event simulation of well-engineered telecommunication systems. The ideas from rare event simulation and importance sampling form the basis of an efficient technique (with Otto J. Wittner and Bjarne E. Helvik) where ant-based routing is applied for management of virtual connections. Interestingly, the experience from the ant-based technique has initiated a new heuristic (with Werner Sandmann) that simplifies the parameter updates in importance sampling simulations.

In evaluation of the ant-based QoS management scheme, the transient performance after changes in the network conditions is simulated. The changes may be failures caused by attacks, accidents, or technical failures. Scalable analytical models to quantify the survivability have been developed (with Kishor S. Trivedi) to study such transient effects.

The bio-inspired management technique for the virtual connections is a continuation of previously work done for upgrading of access networks where dimensioning rules based on optimization from a genetic algorithm has been successfully applied. QoS management also includes performance studies of different protocols and network systems, and specification of Service Level Agreements (with Telenor colleagues). The latter started a series of work on IP measurement and monitoring methods where a large-scale measurement platform (with Brynjar Viken) were specified and implemented consisting of flexible multipurpose measurement stations. In addition, source models and traffic generators were implemented for test purposes. More than 70 licenses of the GenSyn traffic generator have been issued. The interest in measurements and monitoring techniques is a continuation of measurements done in PBXs recent analysis done of IP telephony and mobile services.

The research activities are conducted mainly as research projects founded by industry (Telenor), Norwegian research council, and EU (IST BISON, Torrent, N3I). Research activities covers evaluation methods; simulation, analytical, and measurements, and (bio-inspired) network management methods. In the following the research activities and main achievements are summarized. In the following more details on the four main areas are given.

1. Simulation application and methodology

Poul Heegaard has a broad experience in application of simulations on different application areas from QoS handling in ATM systems to comparison of railroad signaling systems to be used by the high speed Airport Train at Gardemoen Line. He had also been responsible for giving lectures in courses in basic and advanced simulation methodology since 1995, mainly at NTNU but also as invited lecture at University of Pisa.

His main activity in simulation is though on rare event simulation which is started at his master studies simulating transient dependability properties. This continued at his PhD studies a few years later. The thesis entitled “Efficient simulation of network performance by importance sampling”. The motivation of the work was simulation of the performance of multiplexing of ATM cells with cell loss ratio requirements less than 10^-9. The main contribution of the thesis is the description of a new state dependent biasing of the importance sampling parameters. With this biasing, importance sampling can be applied to multidimensional models, e.g. descriptions of telecommunication networks with balanced utilization of resources. The state dependent biasing removes the unrealistic constraint that the system performance is dominated by single bottleneck. Previous strategies was based on such an assumption which simplifies the biasing significantly. A new, flexible framework was defined for modelling both dependability and traffic aspects of communication networks. The state dependent biasing applies to models described within this framework. Several network examples were defined and their performance evaluated by importance sampling simulations. These experiments served as demonstration of the feasibility of the adaptive biasing.

Another successful application of importance sampling is demonstrated in a trace driven simulation of a multiplex of MPEG coded video streams. Comparisons with stratified sampling and direct simulation show that importance sampling provides a significant speedup.

In later years the state dependent change of measures are applied to performance and dependability evaluation of optical networks. New heuristics are developed, now inspired by the swarm intelligence methods used in activity 4 on bio-inspired management methods. This work was done in close cooperation with Werner Sandmann at the University of Bamberg.

2. Measurements

The measurement activities include measurements on PABX, on IP networks, and from mobile systems. Measurement collection techniques, data analysis, and traffic modeling have been studied.

The PABX at NTNU (former NTH) was upgraded from a Metaconta 10R to a MD110 system. The telephony quality, the terminal, and set of services were upgraded and two series of measurements were conducted; one on the old system and one on the new system. One interesting experience was that it was more difficult to customize measurements on the new equipment, many of the “advanced” services were never used, and that very little inter-university traffic was observed.

As the Internet became widespread used activities on passive and active measurement techniques were initiated to evaluate QoS performance of IP routers and services. Accurate, flexible, multipurpose, time-synchronized traffic monitors for instance for one-way delay measurements were developed together with a colleague at Telenor (Brynjar Viken. This flexible monitoring archtechture (e.g. for SLA conformance testing) where development and deployed in a measurement laboratory environment) in a huge pilot Full Service Network experiment. Together with a master student (Jørgen Ryland) a single point, two-way delay estimation principle was developed and implemented. In addition, a framework for IP traffic generation was developed and implemented in Java thanks to colleague in SINTEF (Manyi Lu) and later extended by colleague at Telenor (Per Bjelke). The modeling framework was an extension and modification of the work that was done on the Synthesized Traffic Generator (STG). More information about GenSyn - a Java based traffic generator for synthetic IP traffic, which has currently more than 70 registered licensees.

Recently sets of measurement data of IP telephony and mobile telephony usage have been analyzed and compared with telephony usage patterns observed in Plain Old Telephony Systems (POTS) and used by ITU in their recommendations. Significant changes in the pattern have been observed and most notable changes in the call duration and peak hours of international calls, and in the daily changes in the traffic volume for mobile telephony. The call duration is very sensitive to price scheme. Finally, the daily variation of SMS have different patterns and peaks compared with the daily variation in the mobile call patterns.

3. Analysis

Research on analytical model includes development of traffic algorithms for consecutive resource allocations in context of Ericsson’s MD110 PBX. Approximate methods were developed in cooperation with colleagues at SINTEF (Norvald Stol and Bjarne E. Helvik). At the same time performance studies and different LAN/MAN protocols and of the CPX system were carried out, and dimensioning rules for backbone based PBXs were proposed.

To avoid state space explosion a framework for dependability modeling based on synchronized local state diagrams (SLSD) was designed. Recently, work in quantification of survivability, i.e., the systems ability to continuously deliver services in presence of failures caused by accident, attacks, or technique faults, analytical modeling, has again lead to focus on reducing growth of state space when modeling telecommunication network services. The joint research conducted with Prof. Kishor S. Trivedi at Duke has a space- and time-decomposed CTMC model that enable modeling and quantification of transient performance of huge network systems exposed to a vast variety of failures. The models are motivated by the work on performance evaluation of the ant-based stochastic routing scheme developed for management of virtual connections (see point 4).

4. (Bio-inspired) management and optimization

QoS management in communication networks is non-trivial task where the goal is to have an overall good utilization of the network resources and at the same time provide the best possible quality of service, at least in accordance with the specifications. Heegaard has look into different aspects of this such as traditional performance studies of different protocols and network systems, and specification of Service Level Agreements (with Telenor colleagues). A non-traditional approach was taken to optimize the dimensioning of an upgrade of a Cable TV access network with heterogeneous services and requirements (NP-hard problem). The access network was formalized as a genome and different solutions gradually evaluated over generations through mutations and crossover. The application of a genetic algorithm in access network was efficient and successful because we did not need to find the optimal solution, just find a solution with positive revenue within reasonable time.

Another ongoing major activity is development and evaluation of an on-line, distributed, autonomous, path (or virtual connection) management scheme. The future network will provide a multitude of services with different and potentially conflicting requirements. To meet these meet these requirement and at the same time to be flexible and robust, traditional, off-line, centralized schemes must be reconsidered and alternatives investigated, e.g. methods based on swarm intelligence with mobile agents that explore, map and manage the network in a manner similar to the way insects, e.g. ants and bees, deal with their environment. A distributed, robust and adaptive swarm intelligence system for dealing with path management in communication networks has been developed (Bjarne E. Helvikand Otto J. Wittner). The system is called the Cross Entropy Ant System (CEAS), and is based on increasing the probability of finding a (near) optimal solution by an increasingly focused random search. The Cross Entropy is an optimization methods that assumes finding the optimal solution to be a rare event and hence methods importance sampling applies. The CEAS robustness and adaptivity are demonstrated on a variety of case studies using different management strategies, like: shared backup path protection (SBPP), p-cycles, resource search under QoS constraints and adaptive paths with stochastic routing. Important contributions are work on reducing the overhead of ant-based systems, through elite selection, adaptive updating frequency and information sharing and cooperation. The implementation of CEAS running on small home routers is interesting and demonstrates and visualizes the inner workings of the method.

Publications: FRIDA