Novel critical phenomena in optimization driven processes on networks

The work presented in this Ph.D thesis was developed in the context of complex network theory, from a statistical physics standpoint. We examine two distinct problems in this research field, taking a special interest in their respective critical properties. In both cases, the emergence of criticality is driven by a local optimization dynamics. Firstly, a recently introduced class of percolation problems that attracted a significant amount of attention from the scientific community, and was quickly followed up by an abundance of other works. Percolation transitions were believed to be continuous, until, recently, an 'explosive' percolation problem was reported to undergo a discontinuous transition, in [93]. The system's evolution is driven by a metropolis-like algorithm, apparently producing a discontinuous jump on the giant component's size at the percolation threshold. This finding was subsequently supported by number of other experimental studies [96, 97, 98, 99, 100, 101]. However, in [1] we have proved that the explosive percolation transition is actually continuous. The discontinuity which was observed in the evolution of the giant component's relative size is explained by the unusual smallness of the corresponding critical exponent, combined with the finiteness of the systems considered in experiments. Therefore, the size of the jump vanishes as the system's size goes to infinity. Additionally, we provide the complete theoretical description of the critical properties for a generalized version of the explosive percolation model [2], as well as a method [3] for a precise calculation of percolation's critical properties from numerical data (useful when exact results are not available). Secondly, we study a network flow optimization model, where the dynamics consists of consecutive mergings and splittings of currents flowing in the network. The current conservation constraint does not impose any particular criterion for the split of current among channels outgoing nodes, allowing us to introduce an asymmetrical rule, observed in several real systems. We solved analytically the dynamic equations describing this model in the high and low current regimes. The solutions found are compared with numerical results, for the two regimes, showing an excellent agreement. Surprisingly, in the low current regime, this model exhibits some features usually associated with continuous phase transitions.

Context-based wireless mesh networks

In the modern society, new devices, applications and technologies, with sophisticated capabilities, are converging in the same network infrastructure. Users are also increasingly demanding in personal preferences and expectations, desiring Internet connectivity anytime and everywhere. These aspects have triggered many research efforts, since the current Internet is reaching a breaking point trying to provide enough flexibility for users and profits for operators, while dealing with the complex requirements raised by the recent evolution. Fully aligned with the future Internet research, many solutions have been proposed to enhance the current Internet-based architectures and protocols, in order to become context-aware, that is, to be dynamically adapted to the change of the information characterizing any network entity. In this sense, the presented Thesis proposes a new architecture that allows to create several networks with different characteristics according to their context, on the top of a single Wireless Mesh Network (WMN), which infrastructure and protocols are very flexible and self-adaptable. More specifically, this Thesis models the context of users, which can span from their security, cost and mobility preferences, devices’ capabilities or services’ quality requirements, in order to turn a WMN into a set of logical networks. Each logical network is configured to meet a set of user context needs (for instance, support of high mobility and low security). To implement this user-centric architecture, this Thesis uses the network virtualization, which has often been advocated as a mean to deploy independent network architectures and services towards the future Internet, while allowing a dynamic resource management. This way, network virtualization can allow a flexible and programmable configuration of a WMN, in order to be shared by multiple logical networks (or virtual networks - VNs). Moreover, the high level of isolation introduced by network virtualization can be used to differentiate the protocols and mechanisms of each context-aware VN. This architecture raises several challenges to control and manage the VNs on-demand, in response to user and WMN dynamics. In this context, we target the mechanisms to: (i) discover and select the VN to assign to an user; (ii) create, adapt and remove the VN topologies and routes. We also explore how the rate of variation of the user context requirements can be considered to improve the performance and reduce the complexity of the VN control and management. Finally, due to the scalability limitations of centralized control solutions, we propose a mechanism to distribute the control functionalities along the architectural entities, which can cooperate to control and manage the VNs in a distributed way.

Decentralizing IP mobility management in future networks

The massive adoption of sophisticated mobile devices and applications led to the increase of mobile data in the last decade, which it is expected to continue. This increase of mobile data negatively impacts the network planning and dimension, since core networks are heavy centralized. Mobile operators are investigating atten network architectures that distribute the responsibility of providing connectivity and mobility, in order to improve the network scalability and performance. Moreover, service providers are moving the content servers closer to the user, in order to ensure high availability and performance of content delivery. Besides the e orts to overcome the explosion of mobile data, current mobility management models are heavy centralized to ensure reachability and session continuity to the users connected to the network. Nowadays, deployed architectures have a small number of centralized mobility anchors managing the mobile data and the mobility context of millions of users, which introduces issues related to performance and scalability that require costly network mechanisms. The mobility management needs to be rethought out-of-the box to cope with atten network architectures and distributed content servers closer to the user, which is the purpose of the work developed in this Thesis. The Thesis starts with a characterization of mobility management into well-de ned functional blocks, their interaction and potential grouping. The decentralized mobility management is studied through analytical models and simulations, in which di erent mobility approaches distinctly distribute the mobility management functionalities through the network. The outcome of this study showed that decentralized mobility management brings advantages. Hence, it was proposed a novel distributed and dynamic mobility management approach, which is exhaustively evaluated through analytical models, simulations and testbed experiments. The proposed approach is also integrated with seamless horizontal handover mechanisms, as well as evaluated in vehicular environments. The mobility mechanisms are also speci ed for multihomed scenarios, in order to provide data o oading with IP mobility from cellular to other access networks. In the pursuing of the optimized mobile routing path, a novel network-based strategy for localized mobility is addressed, in which a replication binding system is deployed in the mobility anchors distributed through the access routers and gateways. Finally, we go further in the mobility anchoring subject, presenting a context-aware adaptive IP mobility anchoring model that dynamically assigns the mobility anchors that provide the optimized routing path to a session, based on the user and network context. The integration of dynamic and distributed concepts in the mobility management, such as context-aware adaptive mobility anchoring and dynamic mobility support, allow the optimization of network resources and the improvement of user experience. The overall outcome demonstrates that decentralized mobility management is a promising direction, hence, its ideas should be taken into account by mobile operators in the deployment of future networks.

Forwarding and security in vehicular networks

The growing research in vehicular network solutions provided the rise of interaction in these highly dynamic environments in the market. The developed architectures do not usually focus, however, in security aspects. Common security strategies designed for the Internet require IP. Since nodes' addresses in a vehicular network are too dynamic, such solutions would require cumbersome negotiations, which would make them unsuitable to these environments. The objective of this dissertation is to develop, and test a scalable, lightweight, layer 3 security protocol for vehicular networks, in which nodes of the network are able to set up long-term security associations with a Home Network, avoiding session renegotiations due to lack of connectivity and reduce the protocol stacking. This protocol allows to provide security independent of the nodes (vehicles) position, of its addressing and of the established path to access the Internet, allowing the mobility of vehicles and of its active sessions seamlessly without communication failures.