Technical Program
Complementary documentation is available at documentation
|
|
|
|
|
Daily schedule
- 1h30 Morning course (1/2)
- 0h30 Coffee Break
- 1h30 Morning course (2/2)
- 1h00 Lunch (B4 building)
- 1h30 Afternoon course (1/2)
- 0h30 Coffee Break
- 1h30 Afternoon course (2/2)
Course description
Internet routing system and its protocols
Olivier Bonaventure, Université Catholique de Louvain, Belgium
Summary. This course focuses on the foundations of Internet routing system and its protocols.
Short bio. Olivier Bonaventure is currently a professor in the Department of Computing Science and Engineering at Universite catholique de Louvain (UCL), Belgium where he leads the IP Networking Lab. He received a Ph.D. degree from the University of Liege and spent one year at the Alcatel Corporate Research Center in Antwerp. He received the Wernaers and Alcatel prizes awarded by the Belgian National Fund for Scientific Research in 2001 and the USENIX NSDI Community and Opet-textbook from Saylor Fundation (USA) awards in 2012. He is a editor at large of IEEE/ACM Transactions on Networking and was associate editor of IEEE Network Magazine (2006-2010). His current research interests include the evolution of the Internet architecture, routing protocols, and measuring the Internet.
Advances in routing models and algorithms
Dimitri Papadimitriou, Alcatel-Lucent, Belgium
Summary. Prominent research efforts have been conducted over last decades to mitigate the Internet routing system limitations in terms of scalability (memory space consumption local routing tables), adaptation cost, convergence time and stability. Several ad-hoc/incremental improvements addressing the symptoms instead of the root causes have been introduced but none have fundamentally changed the intrinsic properties of the path-vector routing algorithm and more generally stretch-1 shortest path routing. Hence over time, the research community on distributed and adaptive routing algorithmic has investigated several new routing paradigms and proposed various alternatives to circumvent these limits. The resulting algorithms aim at providing a competitive tradeoff between the memory space required to sustain routing table size growth and the computational resources required to sustain the routing exchanges dynamics while maintaining a low-stretch increase of the produced routing paths. The most noticeable routing models are hierarchical routing, geometric routing, stochastic routing, compact routing and many variants of overlay routing, including the recently proposed method relying on the segmentation between the user (identifiers) and network routing space (locators).
This lecture is organized in four main parts. The first part introduces the multi-dimensional problem of adaptive & distributed routing on large-scale topologies (modeled as graphs) and the resulting tradeoffs. This part also develops different routing models including shortest path routing (the distance-vector algorithm, the path-vector algorithm and their variants combining policing and traffic engineering) but also geometric and compact routing. The second part analyzes the relationship between addressing and routing algorithmic and between the Internet topology (and its dynamics) and the exchange/computation algorithms against the routing models listed here above. This analysis explains why some of these algortithms such as geometric routing leads to premises that may provide a suitable alternative for the Internet routing system and why others such as hierarchical routing due to the spatio-temporal properties of the Internet topology are unsuited. The third part of the lecture focuses on recent advances on three classes of routing models and algortihms: geometric routing on hyperbolic spaces, variants of compact routing applied to multicast and new communication/exchange algorithms. The lecture concludes by detailing active research areas and associated algorithmic challenges.
Short bio. Dimitri Papadimitriou is currently a Senior Research Engineer at Alcatel-Lucent Bell, Antwerp, Belgium. He authored numeous peer reviewed papers on routing, recovery, and performance of packet/multi-layer networks as well as more than twenty patents. He is currently leading European activities on Future Internet including the FIRE EULER project. He is also actively involved in standardisation activities of the IRTF and IETF. His current research interests include distributed algorithms for dynamic/adaptive routing, distributed graph algorithms, topology modeling and graph analysis/mining, automated learning methods and techniques for self-adaptive and predictive control of communication networks, dynamic stochastic models and algorithms for multi-agent systems and self-organizing multi-agent systems and complex adaptive systems.
Foundations of algorithmic graph theory
Martin Charles Golumbic, University of Haifa, Israel
Summary. The course presents classical and more recent theory and algorithms in graph theory, in particular, related to intersection graphs and other structured families of graphs. The course covers the first several lectures available at www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory
Short bio. Martin Charles Golumbic is Professor of Computer Science and Director of the Caesarea Edmond Benjamin de Rothschild Institute for Interdisciplinary Applications of Computer Science at the University of Haifa. He has been a Fellow of the Institute of Combinatorics and its Applications since 1995, and was elected as a Fellow of the European Artificial Intelligence society ECCAI in 2005. His current area of research is in combinatorial mathematics interacting with real world problems in computer science and artificial intelligence. Previously he held positions at the Courant Institute of Mathematical Sciences of New York University, Bell Telephone Laboratories, the IBM Israel Scientific Center, and Bar-Ilan University. He has also been a visiting professor at Université de Paris, the Weizmann Institute of Science, Ecole Polytechnique Fédérale de Lausanne, Universidade Federal do Rio de Janeiro, Rutgers University and Columbia University.
Prof. Golumbic is the author of the book Algorithmic Graph Theory and Perfect Graphs, coauthor of a second book Tolerance Graphs. He is the founding Editor-in-Chief of the journal "Annals of Mathematics and Artificial Intelligence" and is or has been a member of the editorial boards of several other journals including "Discrete Applied Mathematics", "Constraints" and "AI Communications". He has been a guest editor of special issues of several journals, the editor of the books "Advances in Artificial Intelligence, Natural Language and Knowledge-based Systems", and "Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications". His most recent book is "Fighting Terror Online: The Convergence of Security, Technology, and the Law", published by Springer-Verlag.
Advances in algorithmic graph theory - Part 1
Yannis Manoussakis, Laboratoire de Recherche en Informatique, France
Summary. The course will cover: 1) Connectivity (45min.), 2) Graph colorings (1h30), and 3) Balance in signed graphs (45min.)
Short bio. Prof. Yannis Manoussakis is a distinguished Professor, and Vice Director of LRI. His research domain covers discrete mathematics and foundations of computer science with emphasis on graph theory, combinatorial optimisation, networks, scheduling technics, design and analysis of combinatorial sequential, random and parallel algorithms. Also interested on digital cinema, broadcast technologies, and internet applications related to education.
Hyperbolicity and Gromov hyperbolic graphs
José M. Rodríguez García, Universidad Carlos III de Madrid, Spain
Summary. One of the geometric properties of graphs underlying large-scale topologies (such as the Internet) is the hyperbolic nature of its topology, useful to enable navigation/routing. The main of goal this course is to understand this branch of graph theory in order to exploit its potential. We will start with an elementary (and brief) introduction on the hyperbolic plane and Gromov hyperbolic graphs (Poincaré model of the hyperbolic plane, different definitions of hyperbolicity, quasi-isometries and quasi-geodesic stability). After that, we will explain the geometric meaning and the connections of several definitions of hyperbolicity. Finally, we will introduce the main tool used in the applications (geodesic stability) and we will give an "elementary" proof in a simple case, which allows to illustrate the behavior of hyperbolic graphs.
Short bio. José M. Rodríguez García is a Professor in the Department of Mathematics at the Universidad Carlos III de Madrid. He received a Ph.D. degree from the Universidad Autonoma de Madrid in 1991. His current research interests include the Riemann's surfaces, Gromov hyperbolic spaces, potential theory, approximation theory, weighted Sobolev spaces, and Sobolev orthogonal polynomials.
Advances in algorithmic graph theory - Part 2
Georges B. Mertzios, Durham University, United Kingdom
Summary. The main goal of this lecture is to highlight the connections of graphs with other topics in discrete mathematics, such as partial orders and geometric intersection models. A further goal is to introduce the audience to the various ways to systematically traverse through a graph, such as by the Lexicographic Breadth First Search (LBFS) and the Lexicographic Depth First Search (LDFS), and to illustrate their computational power in solving hard graph problems. The lecture will be organized as follows: (1) partial orders: Hasse diagrams, transitively orientable graphs, the notion of forcing orientations, implication classes, the transitive orientation algorithm, the maximum clique problem, (2) permutation graphs, trapezoid graphs, simple-triangle graphs: alternative representations using permutations, intersection model, and partial orders, recognition algorithms, (3) tolerance and multitolerance graphs: relations to interval graphs, permutation graphs, trapezoid graphs, and partial orders, efficient algorithms for optimization problems, (4) introduction to systematic graph search, Lex. BFS, Lex. DFS and recent applications of these algorithms in solving combinatorial problems. The first part of the talk will be more devoted to older results and the second part to recent results.
Short bio. George Mertzios is a Lecturer in Computer Science in the School of Engineering and Computing Science at Durham University, United Kingdom. He received his Diploma in Mathematics and Informatics from the Technical University Munich, Germany, and PhD in Computer Science from the RWTH Aachen University, Germany. Previously he has been a researcher at the Department of Computer Science of Technion, Israel Insitute of Technology, and at the Caesarea Rothschild Institute for Computer Science at the University of Haifa, Israel. He was also an Invited Assistant Professor at the Laboratoire Bordelais de Recherche en Informatique (LaBRI), University of Bordeaux/CNRS, France. His current research interests include the design and analysis of efficient algorithms for graph/network optimization problems, computational complexity, foundations of networks, as well as evolutionary graph theory.
Modeling topological and dynamic aspects of evolving small-world/scale-free networks
Francesc Comellas, Universitat Politècnica de Catalunya, Spain
Summary. In this past decade, the study of networks associated with complex systems has received the attention of researchers from many different areas. It has been shown that biological,social and economic networks, communication networks, the WWW and Internet, as well as other artificial systems such as software architecture networks, are far from random and share interesting properties. In most cases, the networks are sparse, have a logarithmic diameter with the number of nodes, have a large clustering (nodes have many mutual neighbors), and their degree distribution usually obeys either a power-law distribution --it is scale-free-- or follows an exponential distribution. Such properties can often be related to a modular or hierarchical structure and organization which is basic for communication and dynamical processes. This hierarchical structure leads in many cases to the existence of nodes with a relatively high degree (or hubs), which play a critical role in the information flow of the system because many of the other nodes send and receive information through them. Hubs are also associated with a low average distance in the network -the network is small-world-. After an extensive initial research work centered mainly on modeling network topological properties, recent approaches using spectral techniques and new labeling methods are helping to understand dynamical processes associated with the networks, including synchronization, routing and diffusion (random walks). For these systems, providing new models with efficient routing protocols is of interest when designing practical communication algorithms in relation to dynamical processes and also to understand the underlying mechanisms that have shaped their particular structure. In this talk we will review several simple deterministic evolving graph models for which it is possible an analytical determination of topological and dynamic parameters that match those of relevant real life networks while allowing also the generation of simple communication algorithms.
Short bio. Francesc Comellas received in 1982 a Ph.D. degree from Universitat Autònoma de Barcelona. In 1985 he joined the Universitat Politècnica de Catalunya–Barcelona Tech, where he holds a position as Professor in Applied Mathematics and since then he has been working with the Research Group on Combinatorics, Graph Theory and Applications (COMBGRAF). During academic years 1988–1989 and 1995–1996, he made research stays at the Informatics Dep. of the Rutherford-Appleton Lab., S.E.R.C., U.K. and the School of Computing Science of Simon Fraser University, Burnaby, Canada. His research interests include theoretical aspects and the use of combinatorial optimization algorithms in relation to the design of optimal topologies and communication strategies for interconnection networks and includes the design and analysis of deterministic models for complex networks and their dynamical aspects. He has more than one hundred research papers in international journals and proceedings (with a reviewing process) and has been the main researcher in twelve research projects (some of them international). He has also supervised five PhD and more than fourty PFC (Master thesis) students.
Geometric routing schemes
Marian Boguñá, University of Barcelona, Spain
Summary. In the age of Information Technology, the Internet has become our primary communication system. One surprising fact about the Internet is that its complex architecture is the result of a self-organized process where individual agents interact locally without any central authority controlling its evolution. This turns the Internet into subject of truly scientific research. The Internet is now facing a serious scalability problem with its routing architecture. To route information packets to a given destination, Internet routers must communicate to maintain a coherent view of the global topology. The constantly increasing size and dynamics of the Internet thus leads to immense and quickly growing communication and information processing overhead, a major bottleneck in routing scalability causing concerns among Internet experts that the existing Internet routing architecture may not sustain even another decade. In our approach to the problem, we assume that the Internet (and other complex networks) lives in a hidden metric space that shapes its topology. Discovery of this hidden metric space can then be used to greedily route information without detailed global knowledge of the network structure or organization. During this course, I will explain all the results that our group has obtained during recent years on this problem. Lectures are organized in four main blocks as follows 1) Realistic models of complex networks embedded in metric spaces, Euclidean vs. Hyperbolic geometry, 2) Topological conditions for optimal/scalable greedy routing strategies, 3) The inverse problem and its associated performance applied to the real Internet topology, and 4) Models of growing networks embedded in metric spaces. Prior knowledge on theory of complex networks, probability theory and some basics in geometry are highly advised.
Short bio. Marian Boguñá is an associate professor at the Departament de Física Fonamental of the Universitat de Barcelona. He graduated in Physics in 1994 and obtained his PhD also in Physics in 1998. In 1999, he moved to the USA to do a postdoctoral stay with Professor George H. Weiss at the National Institutes of Health, Washington DC. After this period, he moved back to Barcelona where, in 2003, he was awarded a Ramón y Cajal fellowship. He got the tenure position at the end of 2008. During this period, he has also spent several months in the USA as invited guest scientist at Indiana University. M. Boguñá has written over 60 publications in major peer reviewed international scientific journals, book chapters, and conference proceedings. Among those, Nature, Nature Physics, Nature Communications, Proceedings of the National Academy of Sciences US, and Physical Review Letters. He was the chair of the international conference BCNeWORKSHOP 2008 Trends and Perspectives in Complex Networks and has served as a program committee member in many international conferences. In January 2008, he obtained the Outstanding Referee award of the American Physical Society. In December 2010, he was awarded as ICREA Academia Professor 2010. Since January 2013 he serves as an editorial board member for Scientific Reports.
Information routing schemes
Georges C. Polyzos, Athens University of Economics and Business, Greece
Summary. The lecture is organised in five sections: 1) Multipoint Communication and Multicast Routing, 2) Information-Centric Networking and the Publish/Subscribe Internetworking (PSI) architecture, 3) LIPSIN, a specific forwarding/routing solution in PSI (using multicast, Bloom filters etc.), 4) DHTs, and 5) H-Pastry (a specific solution using hierarchical DHTs for global rendezvous in PSI).
Short bio. Dr. George C. Polyzos, Professor of Computer Science at the Athens University of Economics and Business (AUEB) since 1999, has founded and is leading the Mobile Multimedia Laboratory. Previously, he was Professor of Computer Science and Engineering at the University of California, San Diego, where he was co-director of the Computer Systems Laboratory, member of the Steering Committee of the UCSD Center for Wireless Communications, and Senior Fellow of the San Diego Supercomputer Center. He received his Diploma in Electrical Engineering from the National Technical University of Athens and his M.A.Sc. in Electrical Engineering and Ph.D. in Computer Science from the University of Toronto. His current research interests include Internet architecture and protocols, mobile multimedia communications, wireless networks, ubiquitous computing, network security, and performance analysis of computer and communications systems. He has been on the program committees of many conferences and workshops and is currently on the Steering Committee of the ACM SIGCOMM Information-Centric Networking workshop and is TPC Co-Chair for ACM SIGCOMM ICN 2013.
Operational research aspects in routing
Paola Festa, University of Naples, Italy
Summary. Data routing requires the solution of thousands of combinatorial optimization problems, most of them computationally intractable. In this course, we will discuss combinatorial optimization issues occurring in routing and will realize why and how in this context combinatorial optimization problems arise. We will the focus on mathematical programming aspects as well as graph and networks models for some routing problems. In more detail, we mathematically formulate these problems as combinatorial optimization problems and review the corresponding literature, discussing some of the techniques that have been used to solve them in practice and their running times.
Short bio. Paola Festa obtained her Ph.D. degree in Operations Research in 2000. She is currently Associate Professor in Operations Research at the University of Napoli Federico II since 2002. Since 1999 she has been frequently Research Scholar and Visiting Professor at several national and international research institutes, including MIT Lab. for Information and Decision Systems (USA), AT&T Labs Research (USA), and University of Florida (USA). Her research spans several fields, including network optimization, shortest paths, hard combinatorial optimization, and computational biology. She is in the Editorial Board of several international journals, including Journal of Global Optimization and Optimization Letters, and is author/coauthor of more than 60 publications appeared in international journals, books, and peer-reviewed conference proceedings.