Dependable Routing for Cellular and Ad hoc Networks

This dissertation addresses an expedient set of research challenges in the area of cellular and ad hoc networks. In particular, we discuss the dependability—that is, the consistency of performance and behavior—of the routing system within such networks. Our restless, mobile society has inspired diverse fields of research in the area of computer communication networks. The results manifest in recent advances in the area of wireless and mobile communications, with cellular networks being an exemplar of success. Despite the fact of its supremacy in fixed networks, the Internet has not yet caught up in the mobile domain. We argue that next generation networks should overcome the dichotomy between the aforementioned networks and decide to focus our attention to the role of the routing system. We select cellular networks (closed to subscribers and based on infrastructure) and ad hoc networks (open/public and infrastructureless) to represent our objects of research. In Part I of the dissertation, we define the concept of routing dependability and identify the most important characteristics that influence this concept for the aforementioned networking paradigms. A mobility/workload model that captures the macroscopic effects of mobility for metropolitan areas is formulated and instantiated. Our results show that the effects of mobility acting upon the routing system cannot be neglected if we move towards smaller cell sizes and integration of hot spots in cellular systems. To cope with the observed mobility-induced traffic dynamics, we develop and evaluate architectures and algorithms in Part II of our work. In particular, we argue to broaden the scope of the routing domain towards the radio access tier of cellular networks ("smart edge"). In a first step, we break up today’s mainly hierarchically and treestructured cellular networks and introduce a meshed network topology, which adds flexibility to deploy distributed network control mechanisms. A comparative performance analysis of state-of-the-art routing protocols shows the feasibility of such control mechanisms for basic resource management in the surveyed networks. In a second step, a novel system architecture is designed that augments concepts from variable topology networks to cellular architectures. We also develop a routing algorithm to take advantage of the achieved flexibility. As a proof of concept, the algorithm is implemented and a simulation study is performed to obtain deeper insights in the algorithm’s operation. Our results show significant performance gains compared with current state-of-the-art algorithms. Ad hoc networks are effected by mobility as well. Moreover, they are built upon the premise of node cooperation. In Part III of this dissertation, we challenge such cooperation. Therefore, we analytically investigate the effects impaired by node misbehavior and contribute a model of the route acquisition process that includes different classes of node misbehavior. The model is formulated analytically and validated by means of an experimental analysis. Subsequently, an extensive simulation study is conducted to investigate the dependability trade-off between node mobility, routing protocol performance optimizations, and node misbehavior. Our results show clearly the performance degradation of the routing system, leading to network frailty for an increasing number of misbehaving nodes or increasing mobility, respectively