Research With OPNET: Ad-Hoc, Sensor and Satellite Networks

In our group, we investigate several problems related to the design and management of computing systems in which a multitude of entities interact or compete for accessing a common set of resources, are addressed. In the assumed systems the involved active entities can communicate via fixed or dynamic patterns (this last feature representing mobile systems).

In spite of this generality, it is possible to produce abstract models capturing the essential features shared by such systems, ignoring the unimportant physical details. In particular, we address several specific problems, namely routing, data management, and cooperation enforcement in mobile ad-hoc networks, fault and intrusion tolerance and recovery, packet scheduling, video transcoding for mobile terminals, network performance in grid systems, clock synchronization, formulated on general models of parallel and distributed systems. This allows to apply the obtained results in a wide variety of situations.

Background

Computing systems composed of several interconnected processing entities, either cooperating toward a common goal, or concurrently contending for a common set of resources, are the most common systems presently in use. Such systems range from parallel processing ones, in which the processing entities are tightly coupled, and have free access to common resources, like memory and a global clock, to distributed processing, with no common memory and no common timing. Examples of these systems are massively parallel processing systems, and computer networks, like LAN's and Internet. Recently, a new kind of distributed systems, in which the processing entities can freely move, and continue to operate while moving (the mobile systems) emerged as a viable alternative in many application areas.

All these systems share common features, as well as striking differences, and rely on algorithmic methods for optimal design and convenient management of their operations. In our research project, relevant problems related to the design and management of parallel, distributed and mobile systems, are considered.

Technology alone is not a panacea: when proper actions are not pursued, the system can interrupt its service because of not reported faults. This can be the cause of serious problems for both the system and the users depending on it. Another problem not solved by technology alone is the users' uncontrolled access to the common medium, which may result in a poor utilization of the common resource, causing a degradation of the overall system performance, thus eliminating the benefits of the costly new adopted solutions.

We believe that the realization of high-speed, high performance, cost-effective, reliable and transparent distributed and parallel computing systems requires new approaches, based on sophisticated algorithmic solutions and mathematical tools, like game theory. When such solutions turn out to be impractical, the obtained results can be used as fundamental limits to more practical approaches, and thus contribute to form a foundation of parallel and distributed computing. The research community working in this field has recently indicated the above approach as a very promising one, and the related activity has already produced papers published in the most respected scientific journals, and has witnessed a flowering of new workshops and conferences dedicated to the algorithmic aspects of design and management of parallel and distributed systems. Furthermore, the number of research projects on these subjects that are funded by diverse authorities is growing at a very fast pace. Our purpose is to investigate and experimentally evaluate such approaches, thus following the above research line.

Ongoing research

The research currently pursued by our group can be sketched as follows:

Fault diagnosis and self-diagnosis

Packet scheduling in distributed systems
On-line and off-line packet scheduling in single-hop multichannel communication systems (like High Speed Switches, Optical networks, wireless LAN's, etc.), and in connected single-hop multichannel communication systems, both for real-time and not real-time traffic.

Scheduling of BSP- and LogP-like computations for distributed computing systems

Clock Synchronization

Network monitoring for network aware applications

Video Transcoding

Web Caching
Optimization of web caching systems. Memory saving and routing in web caches clusters, with and without fault tolerance.

Integrating LEO Satellite Constellations into InternetBackbone
Investigating the use of LEO satellite constellations for solving the new challenges posed on Internet: guaranteed services and ubiquitous access.

Trading Efficiency and Intrusion Tolerance
Byzantine failures, and their approximate solution: relationship between approximation and time complexity.

Wireless Networks
Routing algorithms, dependable data storage and retrieval, failure recovery, cooperation enforcement, video transcoding.

Wireless Sensor Networks
Data management, network and transport protocols, energy efficiency, cross layer optimization.

Participation to national and international projects

The members of this group are involved in the following national and international projects:

• National Project IS-MANET on "Infrastructures for Mobile ad-hoc Networks"
• National Project on "Resource Allocation in Wireless Networks"
• EEC Project "ALCOM"
• EEC Network of Excellence "ARACNE"
• ECC Network of Excellence "SatNEx-II"
• ECC Network of Excellence "INTERMEDIA"

Short term plans and expected results

We shall study message and packet scheduling, as well as network monitoring results production. These two problems are very relevant for achieving high performances and easy of programming in distributed systems.

In particular, we shall propose new models for representing and studying these problems, investigate their computational complexity, propose optimal algorithms and fast sub-optimal heuristics, study the properties of such algorithms and heuristics, and implement them. Specifically:

• about scheduling problems, we shall investigate optimal message scheduling in single-hop, multichannel communication systems. In particular, we shall investigate message and packet scheduling problems with the objective of minimizing the makespan, or schedule length. Several different traffic and system features will be considered. First, on-demand scheduling will be studied. This problem require that the messages presented to the system by the users are scheduled immediately, without waiting for a large number of requests to come, before computing the schedule for all of them at once. This problem is gaining increasing importance, and can also be applied to mobile communication in ad hoc single hop systems. Another feature that will be considered is real time constraint. Real time scheduling arises in all time sensitive applications, like multimedia, process control, and new applications like monitoring in health care, and stock exchange informations. Both periodic and sporadic traffic will be considered. Besides, a different cost function, namely jitter, will be investigated. Jitter is specially relevant when dealing with multimedia (voice and video) traffic, since delay fluctuations cannot be tolerated by such applications, while the loss of some packet is not prejudicial to system correct working. Special emphasis will be given to experimental evaluation of the proposed algorithms. Finally, we shall study scheduling of interconnected single-hop systems. In this case, scheduling and routing must be solved at once, since they influence each other: an optimal routing can overload intermediate systems, thus leading to very long schedules. On the other hand, an optimal schedule needs a load balancing, which could be achieved at the expenses of unacceptably long paths. LEO's satellite constellations, like the IRIDIUM system, fall into this category of distributed systems.
• Trading Efficiency and Intrusion Tolerance Our everyday life depends on the correct working of critical distributed systems like air traffic control, power plant control, but also stock market, government services, just to cite few. At the same time, attacks to such systems are becoming more and more frequent. The problem has been investigated since many years, and has been modeled as Byzantine failures. Many techniques have been proposed for solving such problems. However, such techniques do not take into account the computational effort they require, thus making them unattractive for practical use. In this research, we shall look for new techniques that solve the problem with a certain degree of approximation, but require little computational effort, so to be attractive also for applications require low power consumption, like mobile ad-hoc networks.
• Web Caching We investigate the impact of novel routing and storing schemes on the overall performance of web caching clusters. In particular, we shall study compact routing and storing of documents in web caches so to save time and memory when the system is operational. A comparison with known proposals, like Oceanstore, will be performed.
• Integrating of LEO satellite constellations and Internet Backbone The integration of LEO satellite constellations and Internet is a novel and very promising research area. The purpose of using LEO satellites for Internet traffic is manyfold: reduce the congestion, improve the quality of service, allow a better connection of mobile users by providing a global planet coverage. Besides, this should be the testbed for interplanetary Internet, namely the computer network that in the future will connect all the processing equipment that humans send on planets other than the earth (mars, for instance). This is a novel research area and many problems must be investigated. To cite few, medium access control proper routing and load balancing, congestion control. We shall focus on these problems giving solutions that take into account the special features of LEO satellites: high latency, low communication quality, low on board memory and processing power.
• Wireless Ad Hoc Networks Major issues in mobile, ad hoc networks are how to implement routing in such a dynamic context and how to guarantee consistency, integrity and confidentiality of the global information. Existing solutions for wired networks or personal communication networks can hardly be adapted to these networks due to different constraints/requirements in terms of energy, mobility, memory and processing capacity. Furthermore, a typical problem of ad-hoc networks is the cooperation enforcement in networks of heterogeneous users. One of the most important problems when dealing with mobile terminals is power awareness. Energy conserving habits can suggest to users of multi-hop networks to refrain from forwarding messages toward the final destination. If such a behaviour spreads in the network, no message will be forwarded, and so no communication will take place. The final and fatal consequence of this is network disruption.
• Wireless Sensor Networks The activity on wireless sensor network is focused on the network, transport and application layers. At the network layer our main aim is to design/develop routing strategies based on virtual coordinates and geographic routing. This allows for path discovery strategies which are only based on unicast messages which, compared to flooding-based strategies, reduce the energy consumption of the sensors. A second objective is related to the design of a transport and application layers which allow the user to program the sensor network as if it was a database, using SQL queries. The user SQL queries are parsed and optimized in order to produce a query execution plan which is optimal with respect to the sensor network constraints and which minimizes energy consumption.
• Video transcoding: Video transcoding for mobile terminals in cellular networks will be investigated. In particular, we shall concentrate on the problem of avoiding still frames in moving pictures when the communication channel has a dynamic bandwidth. This problem shall arise in next generation cellular systems, like UMTS, which adopts a CDMA channel access protocol, with variable channel bandwidth. Fast processing of frames are in order for avoiding still pictures and guaranteeing acceptable video quality at the same time.

Long term plans

On a longer horizon we shall investigate the scheduling problem known as call control. This is a special kind of on demand scheduling, in which some requests can be refused. Such a refusal can be necessary in order to maintain a good quality of service for other ongoing communications, and is specially important in mobile ad-hoc systems. Besides, multicasting will be considered also.

Long term issues in mobile networks include the following points:

- design and implementation of an a mobile ad hoc networks based on commercial laptops/palms equipped with wireless interfaces 802.11/bluetooth;

- interconnection of ad hoc networks with existing satellite and/or wired networks;

- design and implementation of protocols to support data storage and retrieval, enforce cooperation and ensure information confidentiality and dependability.

- design and implement a complete system (covering all the layers between network and application and based on existing physical and MAC layers) for data management in sensor network.

- Finally, we plan to investigate video transcoding techniques based on frame skipping where the decision taken on what frame to skip is derived by probabilistic arguments instead of deterministic ones. Besides, buffer occupancy results (on the average) will be sought.