Dynamic optimization and monitoring in communication networks

Abstract

Communication networks have evolved from specialized, research- and military-oriented transmission systems to large-scale and highly complex interconnections of intelligent devices. Effective operation of such large-scale networks hinges upon real-time allocation of network resources that match the user demands. This thesis contributes towards several key problems encountered in both, monitoring and resource allocation in networks. Volatile operating environments encountered in ad hoc and sensor networks place severe restrictions on the resources (bandwidth and power) available to network nodes. Pertinent approaches have sought to replicate the Internet protocols in ad hoc networks, exacerbating the resource scarcity by ignoring the peculiarities of the underlying wireless interface. The present thesis leverages the ground-breaking idea of network coding to design wireless network protocols. Towards this end, a cross-layer design is pursued, and network codes are optimized jointly with protocols operating at application, medium access control (MAC), and physical (PHY) layers. For wireless fading networks, dual decomposition is utilized to optimally integrate network coding into the protocol stack. Network coding is also introduced for use in Aloha-based MAC, and the resulting non-convex problem is solved via successive convex approximation to realize practical network coding algorithms. Benefits of network coding also extend to QoS-constrained scenarios, such as in real-time and streaming media applications. Modeling constraints on packet deadlines is the key challenge here, and constant-factor approximations are proposed to this end. In sensor networks where the observed data is correlated across nodes, network coding can both compress and communicate the data to a collection agent. An efficient decoding scheme for this network-compressive scheme is developed, yielding network-wide energy savings and increase in the network lifetime. Exhaustive monitoring of large-scale networks may be challenging or even impossible to perform, motivating the need to account for missing measurements. This thesis puts forth the novel concept of dynamic network cartography as tool for inference, tracking, and prediction of the network state. Tapping into the spatio-temporal kriging theory, a dynamic network kriging approach is developed with real-time network-wide prediction capabilities based on latency measurements acquired for a small subset of network paths. Going well beyond state-of-the-art methods, the proposed model captures not only spatio-temporal correlations, but also unmodeled dynamics due to, e.g., congested routers.