Computer Networks

University of Trento Activities in Information and Communications Technology Computer Networks

April 10, 2001

RESEARCH IN ALGORITHMS AND COMPUTER NETWORKS

Alpine Research and Development Laboratory for Networks and Telematics (ARDENT)

Mission The mission of the Alpine Research and Development Laboratory for Networks and Telematics (ARDENT) at the University of Trento (Italy) is to support advanced research in the area of computer networks and telematics, and to encourage the strong partnership between university and industry that is needed to activate collaborations, industrial startup initiatives, and fruitful exchanges of researchers.

The research topics will be expanded in the next years, to include algorithms, system architecture, and applications, in the following areas: •

•

OPTICAL NETWORKS: o Optical Network Technologies and Architectures o IP over WDM o Optical Switching Technologies o Optical Protection and Restoration o Optical WDM, TDM and FDM networks o Optical Resource Provisioning o Fiber to the Desktop MOBILE AND WIRELESS: o Mobile and Wireless Network Technologies and Architectures o Mobile Computing o Next Generation Wireless Networks o Wireless Web and Wireless Internet o Pervasive Computing and Networking o Ad-hoc Networks o Mobile IP

2

Alpine Research and Development Laboratory for Networks and Telematics (ARDENT)

•

•

•

INTERNET: o Internet Multimedia o Voice and Video over IP o Multimedia Systems and Technologies o Resource Allocation o Internet Security and Reliability E-commerce Network Support and Applications GENERAL NETWORK ISSUES: o Network Management and Control o Quality of Service o Network Applications o Network Performance o Networking Standards o Virtual Private Networks o Scalability o Computer Aided Network Design Methodologies and Tools NETWORK SOFTWARE o Object-oriented software engineering o XML o CORBA

Faculty: At present, the Center includes faculty and student researchers from the University of Trento. In the near term the center will have visiting positions for researchers. • • • • • • •

Roberto Battiti, Person in charge of the Laboratory and Professor of Computer Science Alan Bertossi, Professor of Computer Science Imrich Chlamtac, Chairman of the Advisory Board and Kessler Honorary Professor at the University of Trento, Italy Andrea Masini, Professor of Computer Science Cristina Pinotti, Professor of Computer Science Marco Ronchetti, Senior Researcher, Faculty of Science Romeo Rizzi, Researcher, Faculty of Science

Contact Prof. Roberto Battiti Università di Trento Via Sommarive 14 38050 Povo (Trento) – Italy

3

http://rtm.science.unitn.it/~battiti/ , [email protected]

Alpine Research and Development Laboratory for Networks and Telematics (ARDENT)

Competencies Computer and communication networks, given the complexity and the dimensions of concrete systems, are a “frontier” field where different competencies must be integrated. In particular, in many cases there is a need for the application of discrete algorithms with heuristic components, for machine learning and artificial intelligence methods. We briefly list some research topics considered. Additional references can be found in: Wireless networks In previous research works in our group we considered wireless radio networks in which collisions are caused by the time overlap of two or more packet receptions. Collisions are eliminated by assigning orthogonal codes to stations, a problem equivalent to that of coloring graphs associated to the physical network. Upper and lower bounds, optimal solutions obtained by branch and bound and heuristics are proposed and analyzed. Randomized coloring techniques (based on the saturation degree coloring heuristics) have been adopted for the assignment of frequencies in cellular networks, with state of the art results. Greedy, prohibition, and Reactive Search heuristics have been used for the partitioning of graphs, a problem of relevance in the management of very large scale networks. Graph problems of interest in this area are also the maximum clique problem, hypergraph partitioning, matching and clustering. History-sensitive heuristics The optimal solution of many discrete optimization problems, including most of the problems arising in the computer networks arena, requires computing times that grow too rapidly as a function of the problem dimension. It is well known that several problems of great practical significance are NP-complete : it is now considered to be very unlikely that "affordable" algorithms for them will ever be found. Furthermore, we are seeing a growing number of negative results about the possibility to find approximate solutions to many problems. Therefore there is a need for efficient heuristics , i.e., algorithms without a formal guarantee of performance but which can provide one or several good solutions with acceptable running times and memory usage. In particular, our research considers heuristics based on local search complemented by history-sensitive (reactive) mechanisms. History-sensitive methods are used to (i) define the parameters of the basic heuristic algorithm so that it is automatically tuned to the characteristics of a particular problem, (ii) generate appropriate search trajectories with a proper balance of intensification and diversification.

4

Alpine Research and Development Laboratory for Networks and Telematics (ARDENT)

Experimental algorithmics As a general framework, we are convinced of the relevance of empirical verification and tuning of algorithms , a subject whose importance is being recognized by a growing number of researchers in the CS community, both to assess the relevance or limitations of theoretical models and to create bridges toward applications in different domains. The study of methodological issues and the use of experimental techniques in algorithm research is also becoming known as Experimental Algorithmics . Neural networks / pattern recognition The functionality of a system for pattern recognition, signal processing, or control tasks can be obtained either by an exhaustive specification of its architecture and parameters, or by a partial specification and a subsequent training (optimization) phase. In this second case, one can obtain easier and faster system development, better performance, easy incorporation of subsequent changes in the environment. Sub-symbolic (inductive) machine learning requires efficient and effective optimization algorithm for the learning phase (optimization is necessary for machine learning and pattern recognition, although it is clearly non sufficient: statistical issues related to generalization, feature extraction, architecture are also crucial). Algorithms and data structures. Computational complexity. Parallel, distributed, and VLSI systems. The advent of very large scale integration technology (VLSI) and the decline in the cost of the hardware have made it possible to build economical computers composed of many processors (even hundreds or thousands, indeed), which are capable of working together in parallel to solve the same problem. Such processors may vary from general-purpose computers connected through a network to special-purpose units capable of solving a single problem only. The research project considers both the resolution of specific problems arising in the design and management of parallel computers, and the parallel resolution of applicative problems which have already been solved by sequential computers. Algorithmic techniques are used for evaluating the computational complexity of the problems: when possible, efficient algorithms which find optimal solutions are given; alternatively, formal proofs of the inherent intractability of the problems are shown. The efficiency of the proposed algorithms is evaluated either in the serial RAM model, or in the parallel PRAM one, or in the VLSI model, by considering the time complexity, the number of processors used, and the area required to implement the algorithm by means of a VLSI circuit.

5

Alpine Research and Development Laboratory for Networks and Telematics (ARDENT) Research Themes •

•

•

•

VLSI algorithms for combinatorial problems. Parallel algorithms are designed for solving basic combinatorial problems of computer science (e.g. string matching, scheduling, linear programming). Task and processor scheduling in real-time. Sequential algorithms are designed for assigning tasks to processors of a multiprocessor system so as to optimize processor utilizaton. Parallel string matching. Parallel algorithms are designed for the exact and approximate stringmatching problems including particular "don't cares" characters which can match strings of arbitrary length. Fault-tolerance in parallel, distributed and VLSI systems. Computational problems are studied which have to be solved in parallel, distributed, and VLSI systems even in the presence of processors failures. In particular, distributed systems with replicated resources are considered.

Previous Projects In addition to research we were involved in projects oriented toward applications, including some research and development initiatives for industrial companies. -

Development of computer vision systems for three-dimensional measurements of mechanical parts (company in the automotive sector), 1995-97.

-

Development of quality control system based on machine learning for a new production facility (company in the automotive sector), 1998-99.

-

Special Initiative ``RTS'' of the INFN – Italian Institute for Nuclear Physics (development of algorithms and dedicated VLSI for innovative neural network algorithms) 1994-1996.

-

Special Project 1995-96 ``Algorithms and Software for Optimization, and models of complex systems'' University of Trento.

-

Project MURST 40% ``Algorithm complexity and design of information systems'' 1996-1997.

-

ESPRIT Special Action on Microelectronics, project NEUR-IC, 1996-97, in collaboration with IRST and SIPAR S.p.A..

-

Project ``Multimedia per Apprendimento Interattivo a Distanza - Multimedia for Interactive Distance Learning'' (MAID), funded by Provincia Autonoma di Trento, 1997-98.

-

Agreement Provincia Autonoma di Trento -- CNR ``Advanced Applications of Computer Science”, Project ``Test, diagnosis and fault tolerance in VLSI circuits'' (1997-2000).

-

Project MURST 40\% ``Resource allocation in computer networks”, from 1999, running.

-

Project with Centro Ricerche FIAT, Applied Computer Vision, 2001-2003, running.

-

Project with Centro Ricerche FIAT, Webstat, in the final approval phase,

2001

6

Alpine Research and Development Laboratory for Networks and Telematics (ARDENT) Brief Curricula Prof. Roberto Battiti

received the Laurea degree in Physics from the University of Trento, Italy, in 1985 and was awarded a Ph. D. in Computation and Neural Systems by the California Institute of Technology (Caltech), USA in 1990. He has been a consultant in the area of parallel computing and pattern recognition and since 1991 he has been with the Faculty of Science at the University of Trento, Italy, where he became full professor in Computer Science in 2000. His main research interests have been heuristic algorithms for combinatorial problems, in particular reactive algorithms for maximum-clique, satisfiability, coloring. Recently he is setting up new research initiatives in the area of computer networks and telematics. Research topics include: resource allocation in networks, code assignment in wireless networks and cellular networks, Web computing, routing and wavelength assignment in optical networks. R. Battiti is a member of the IEEE and ACM.

URL:

http://rtm.science.unitn.it/~battiti/

Prof. Alan Albert Bertossi

was born in London, England. He received the Laurea degree in Computer Science from the University of Pisa, Italy, in 1979. Afterwards, he worked as a System Programmer and Designer. From 1983 through 1994 he was with the Department of Computer Science, University of Pisa, as a Research Associate first and later as an Associate Professor. Since 1995 he has been with the Department of Mathematics, University of Trento, as a Professor of Computer Science. His main research interests are the design and analysis of algorithms for combinatorial problems, as well as the computational aspects of parallel, VLSI, distributed, real-time, and fault-tolerant systems.

URL:

http://rtm.science.unitn.it/~bertossi/

Prof. Imrich Chlamtac joined the Faculty of Science at Trento University in 2000 as “Guglielmo Marconi” Honorary Chaired Professor. He is consulting for setting up new research activities in the area of computer networks and telecommunications. Imrich Chlamtac holds a Ph.D. in Computer Science from the University of Minnesota (1979). He received his B.Sci. and M.Sci. degrees in mathematics awarded with Highest Distinction from Tel Aviv University (1977). Since January 1997 he holds the Distinguished Chair in Telecommunications at the University of Texas at Dallas, and is the Founding Director of CATSS, the Center for Advanced Telecommunications Systems and Services. Dr. Chlamtac was recruited by UTD to manage telecommunications related activities at the University, to meet the challenges and opportunities offered by the growth of the Telecom Corridor in Dallas, at present the largest concentration of telecommunications research and development area in the world. Prior to joining UTD, Dr. Chlamtac was on faculty at Technion-The Israel Institute of Technology and the University of Massachusetts at Amherst. He is the co-founder and past President of BCN, a company specializing in R&D and system integration of telecommunications and multimedia systems and services. For his work on channel access protocols Dr. Chlamtac was elected Fellow of the IEEE in 1993. In 1996 he was elected Fellow of the ACM for introducing the concept of lightpaths for all-optical communication and wavelength routing in WDM networks, which serve as basis for prevailing industry standards.

URL: http://www.utdallas.edu/~chlamtac/ 7

Alpine Research and Development Laboratory for Networks and Telematics (ARDENT)

Dr. Romeo Rizzi

born in 1967, he received the Laurea degree in Electronics by the "Politecnico di Milano" in 1991, and in 1997 received a Ph.D. in Computational Mathematics and Informatics by the University of Padova. After that, he has held post-doc and other temporary positions by research centers like CWI (Amsterdam), BRICS (Aarhus), and IRST (Trento). In March 2001, he became Assistant Research Professor by the Faculty of Science at the University of Trento. He is fond of Combinatorial Optimization and Algorithms and has a background in Operations Research.

URL: http://www-math.science.unitn.it/~rrizzi Prof. M. Cristina Pinotti

received her degree in computer science from Univerity of Pisa in 1986. From 1987 up to 2000, she has been with National Council of Research (CNR) in Pisa. She is presently an associate professor at University of Trento. She had visiting positions at University of North Texas, Denton (TX) in 1994 and 1995, and at Old Dominion University, Norfolk (VA) in 1997 and 1998. Her current research is in the areas of wireless networking and mobile computing. Previously, she worked in the areas of parallel computing studying in particular VLSI hardware architectures for special problems, definition and implementation of parallel data structures and organization of data on parallel memory systems. She has served as a member of program committee for several conferences.

8

Alpine Research and Development Laboratory for Networks and Telematics (ARDENT) Selected Recent Publications R. Battiti, A. Bertossi and M. Brunato. Cellular channel assignment: a new localized and distributed strategy Mobile Networks , in press, 2001. R. Battiti, A. Bertossi and D. Cavallaro. A randomized saturation degree heuristic for channel assignment in cellular radio networks IEEE Transactions on Vehicular Technology , in press, 2001. Roberto Battiti, Alan A. Bertossi, Mauro Brunato. Distributed Saturation Degree Methods For Code Assignment In Multihop Radio Networks Workshop su Sistemi Distribuiti: Algoritmi, Architetture e Linguaggi (WSDAAL2000) Ischia (Napoli). 18-20 Settembre 2000. Roberto Battiti, Alan A. Bertossi, Mauro Brunato. Distributed Code Assignment in Multihop Radio Networks: Object-Oriented Software Simulations 2000 International Conference on Software, Telecommunications and Computer Networks (SoftCom2000) Split (October 10), Rijeka (October 11), Trieste (October 12), and Venice (October 13), 2000. R. Battiti and A. Bertossi. Greedy, Prohibition, and Reactive Heuristics for Graph-Partitioning IEEE Transactions on Computers , Vol. 48, Number 4, April 1999, pp.361-385. Bertossi A. A. and Mei A., Constant time dynamic programming on directed reconfigurable networks, IEEE transactions on parallel and distributed systems, 2000, Vol. 11. Bertossi A. A. and Mancini L. and Rossini F., Fault-tolerant rate-monotonic first-fit scheduling in hard-real-time systems combining active and passive task replication, IEEE transactions on parallel and distributed systems, 1999, Vol. 10. R. Battiti and M. Protasi. Reactive local search for the maximum clique problem. Algorithmica , 2000, in press. R. Battiti, A. A. Bertossi, and M. A. Bonuccelli. Assigning codes in wireless networks: bounds and scaling properties. Wireless Networks , Vol. 5 (1999) pp. 195-209. R. Battiti, A. Bertossi and D. Cavallaro. A randomized saturation degree heuristic for channel assignment in cellular radio networks Proceedings Quarto Workshop su Sistemi Distribuiti: Algoritmi, Architetture e Linguaggi (WSDAAL'99) , Fonte Cerreto, l'Aquila, Italy, Sep 13-15, 1999, pp. 96-101. R. Battiti and M. Protasi. Approximate Algorithms and Heuristics for MAX-SAT Handbook of Combinatorial Optimization, Vol 1, 1998, 77-148, Kluwer Academic Publishers. R. Battiti, A. A. Bertossi, and R. Rizzi. Randomized Greedy Algorithms for the Hypergraph Partitioning Problem Randomization Methods in Algorithm Design Edited by: Panos Pardalos, Sanguthevar Rajasekaran, and Jose Rolim DIMACS Series in Discrete Mathematics and Theoretical Computer Science Vol. 43, 21--35, American Mathematical Society, 1998 R. Battiti, A. A. Bertossi, and M. Brunato. Cellular channel assignment: comparing and simplifying heuristics Proceedings of the IEEE/AMC WorkshopDial M for Mobility, (Discrete algorithms and methods for mobile computing and communications) Budapest, Oct 1, 1997

9

Alpine Research and Development Laboratory for Networks and Telematics (ARDENT) R. Battiti and A. Bertossi. Differential Greedy for the 0--1 Equicut Problem Network Design: Connectivity and Facilites Location Edited by D.Z. Du and P.M. Pardalos, American Mathematical Society. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol 40, pp. 3--21, 1998. R. Battiti and M. Protasi. Reactive Search, a history-sensitive heuristic for MAX-SAT ACM Journal of Experimental Algorithmics, Vol. 2, Paper 2, 1997. R. Battiti and M. Protasi. Reactive Local Search techniques for the Maximum k-Conjunctive Constraint Satisfaction Problem. Discrete Applied Mathematics , 96-97 (1999), pp. 3--27. Battiti R. and Tecchiolli G., Training Neural Nets with the Reactive Tabu Search, IEEE transactions on neural networks, 1995, Vol. 6, No. 5. S. Olariu, M.C. Pinotti, L. Wilson, Greedy Algorithms for Tracking Mobile Users in Special Mobility Graphs, Discrete Applied Mathematics, in press, 2001. S. Olariu, M.C. Pinotti, S.Q. Zheng, An Optimal hardware-Algorithm for Sorting Using a Fixed-Size Parallel Sorting Device, IEEE Transactions on Computers, Vol. 49, n. 12, 2000, pp. 1310--1314.

Additional online publications available at: http://rtm.science.unitn.it/~battiti/battiti-publications.html

10