Most current routing protocols are based on path computation algorithms in graphs (e.g., Dijkstra, Bellman-Ford, etc.). These algorithms have been studied for a long time and are very well understood, both in a centralized and distributed context, as long as they are applied to a network having a single communication protocol. The problem becomes more complex in the multi-protocol case, where there is a possibility of encapsulation of some network protocols into others, therefore inducing nested tunnels. The classic algorithms cited above no longer work in this case because they cannot manage the protocol encapsulations and the corresponding protocol stacks. In this work, we propose a highly parallelizable algorithm that takes into account protocol encapsulations as well as protocol conversions in order to compute shortest paths in a multi-protocol network. To achieve this computation efficiently, we study the transitive closure between subpaths (i.e., the concatenation of two subpaths to obtain a longer one) in the case where each subpath induces a protocol stack, and thus tunnels. Leveraging on Software-Defined Networks with a controller having a highly parallel architecture enables us to compute the routing tables of all nodes in a very efficient way. Experimentation results on both random and realistic topologies show that our algorithm outperforms the previous solutions proposed in the literature.

Metarouting models routing protocols in the form of an algebraic structure called routing algebra. It aims to help designing or validating routing protocols. Most research work on routing algebras have been applied to routing protocols used in networks having a single addressing and forwarding protocol. In this context, some of the basic algebraic structures used are semirings. In this paper, we define a new algebraic structure for dealing with networks containing multiple forwarding protocols, which may induce many (and possibly nested) tunnels. We widely generalize the semiring structure for modeling the routing problem with automatic tunneling. We define a new model of routing algebra with tunneling. It is defined as a semi-direct product of two structures, the well-know shortest paths algebra and a new proposed valid paths algebra. We show that it has a fixed point and we prove the iterative convergence to the optimal solution of the valid shortest paths problem.

In a network, a tunnel is a part of a path where a protocol is encapsulated in another one. A tunnel starts with an encapsulation and ends with the corresponding decapsulation. Several tunnels can be nested at some stage, forming a protocol stack. Tunneling is very important nowadays and it is involved in several tasks: IPv4/IPv6 transition, VPNs, security (IPsec, onion routing), etc. However, tunnel establishment is mainly performed manually or by script, which present obvious scalability issues. Some works attempt to automate a part of the process (e.g., TSP, ISATAP, etc.). However, the determination of the tunnel(s) endpoints is not fully automated, especially in the case of an arbitrary number of nested tunnels. The lack of routing protocols performing automatic tunneling is due to the unavailability of path computation algorithms taking into account encapsulations and decapsulations. There is a polynomial centralized algorithm to perform the task. However, to the best of our knowledge, no fully distributed path computation algorithm is known. Here, we propose the first fully distributed algorithm for path computation with automatic tunneling, i.e., taking into account encapsulation, decapsulation and conversion of protocols. Our algorithm is a generalization of the distributed Bellman-Ford algorithm, where the distance vector is replaced by a protocol stack vector. This allows to know how to route a packet with some protocol stack. We prove that the messages size of our algorithm is polynomial, even if the shortest path can be of exponential length. We also prove that the algorithm converges after a polynomial number of steps in a synchronized setting. We adapt our algorithm into aproto-protocol for routing with automatic tunneling and we show its efficiency through simulations.

Carrier-grade networks comprise several layers where different protocols coexist. Nowadays, most of these networks have different control planes to manage routing on different layers, leading to a suboptimal use of the network resources and to additional operational costs. However, some routers are able to encapsulate, decapsulate, and convert protocols, and act as a liaison between these layers. A unified control plane would be useful to optimize the use of the network resources and to automate the routing configurations. Software-defined networking-based architectures offer an opportunity to design such a control plane. One of the most important problems to deal with in this design is the path computation process. Classical path computation algorithms cannot resolve the problem, as they do not take into account encapsulations and conversions of protocols. In this paper, we propose algorithms to solve this problem and study several cases. If there is no bandwidth constraint, we propose a polynomial algorithm that computes the optimal path. We also give lower and upper bounds on the optimal path length. On the other hand, we show that the problem is NP-hard if there is a bandwidth constraint (or other quality-of-service parameters), even if there is only two protocols and in a symmetric graph. We study the complexity and the scalability of our algorithms and evaluate their performances on real and random topologies. The results show that they are faster than the previous ones proposed in the literature. These algorithms can also have important applications in automatic tunneling.

Understanding how people interact with the web is key for a variety of applications, e.g., from the design of effective web pages to the definition of successful online marketing campaigns. Browsing behavior has been traditionally represented and studied by means of clickstreams , i.e., graphs whose vertices are web pages, and edges are the paths followed by users. Obtaining large and representative data to extract clickstreams is, however, challenging. The evolution of the web questions whether browsing behavior is changing and, by consequence, whether properties of clickstreams are changing. This article presents a longitudinal study of clickstreams from 2013 to 2016. We evaluate an anonymized dataset of HTTP traces captured in a large ISP, where thousands of households are connected. We first propose a methodology to identify actual URLs requested by users from the massive set of requests automatically fired by browsers when rendering web pages. Then, we characterize web usage patterns and clickstreams, taking into account both the temporal evolution and the impact of the device used to explore the web. Our analyses precisely quantify various aspects of clickstreams and uncover interesting patterns, such as the typical short paths followed by people while navigating the web, the fast increasing trend in browsing from mobile devices, and the different roles of search engines and social networks in promoting content. Finally, we contribute a dataset of anonymized clickstreams to the community to foster new studies.1

Real-time interactive communications, such as videoconferencing, have strong QoS requirements. Adapting such communications to network dynamics needs network management capabilities that traditional networks cannot provide. Recently, SDN has shown to be a potential solution for solving these network adaptation challenges. In a companion paper written by our team, we have proposed a videoconferencing system using SVC multicast trees built over an SDN network. This system minimizes the overall bandwidth consumption and provides the highest possible QoS to the users although it is not adaptable to network dynamics happening over the lifetime of the communication. In this paper, we complement our system, by providing efficient algorithms able to modify the connections between the participants during a videoconference in order to timely react to network changes. The simulation results confirm the efficiency of our solution in terms of time processing and bandwidth savings.

Carrier-grade networks comprise several layers where different protocols coexist. Nowadays, most of these networks have different control planes to manage routing on different layers, leading to a suboptimal use of the network resources and additional operational costs. However, some routers are able to encapsulate, decapsulate and convert protocols and act as a liaison between these layers. A unified control plane would be useful to optimize the use of the network resources and automate the routing configurations. Software-Defined Networking (SDN) based architectures, such as OpenFlow, offer a chance to design such a control plane. One of the most important problems to deal with in this design is the path computation process. Classical path computation algorithms cannot resolve the problem as they do not take into account encapsulations and conversions of protocols. In this paper, we propose algorithms to solve this problem and study several cases: Path computation without bandwidth constraint, under bandwidth constraint and under other Quality of Service constraints. We study the complexity and the scalability of our algorithms and evaluate their performances on real topologies. The results show that they outperform the previous ones proposed in the literature.