The growing scale and complexity of Internet of Things (IoT) networks present critical challenges for maintaining and recovering connectivity, especially in dynamic environments or after large-scale fragmentation caused by disasters. Traditional centralized approaches often face scalability, resilience, and energy efficiency issues. Hyperbolic geometry, which has successfully modeled hierarchical and scale-free structures in large-scale systems such as the Internet's AS topology, offers a promising foundation for addressing these challenges. This paper introduces hyperbolic trees as a novel framework for IoT connectivity management. Nodes are embedded in a hyperbolic plane, and connectivity is maintained or restored through a simple local rule: each node connects to the nearest node with a smaller radial coordinate. This distributed, asynchronous approach allows nodes to autonomously reorganize and recover connectivity without centralized coordination, ensuring scalability and adaptability. We demonstrate that hyperbolic trees provide a robust, energy-efficient solution for both maintaining and recovering IoT network connectivity. Numerical results validate the framework's scalability and effectiveness, highlighting its applicability in scenarios ranging from routine management to disaster recovery. These findings establish hyperbolic trees as a practical and scalable tool for resilient IoT connectivity management in next-generation networks.

Abstract Complex system theory is increasingly applied to develop control protocols for distributed computational and networking resources. The paper deals with the important subproblem of finding complex connected structures having excellent navigability properties using limited computational resources. Recently, the two-dimensional hyperbolic space turned out to be an efficient geometry for generative models of complex networks. The networks generated using the hyperbolic metric space share their basic structural properties (like small diameter or scale-free degree distribution) with several real networks. In the paper, a new model is proposed for generating navigation trees for complex networks embedded in the two-dimensional hyperbolic plane. The generative model is not based on known hyperbolic network models: the trees are not inferred from the existing links of any network; they are generated from scratch instead and based purely on the hyperbolic coordinates of nodes. We show that these hyperbolic trees have scale-free degree distributions and are present to a large extent both in synthetic hyperbolic complex networks and real ones (Internet autonomous system topology, US flight network) embedded in the hyperbolic plane. As the main result, we show that routing on the generated hyperbolic trees is optimal in terms of total memory usage of forwarding tables.

To evaluate the expected availability of a backbone network service, the administrator should consider all possible failure scenarios under the specific service availability model stipulated in the corresponding service-level agreement. Given the increase in natural disasters and malicious attacks with geographically extensive impact, considering only independent single component failures is often insufficient. This paper builds a stochastic model of geographically correlated link failures caused by disasters to estimate the hazards an optical backbone network may be prone to and to understand the complex correlation between possible link failures. We first consider link failures only and later extend our model also to capture node failures. With such a model, one can quickly extract essential information such as the probability of an arbitrary set of network resources to fail simultaneously, the probability of two nodes to be disconnected, the probability of a path to survive a disaster. Furthermore, we introduce standard data structures and a unified terminology on Probabilistic Shared Risk Link Groups (PSRLGs), along with a pre-computation process, which represents the failure probability of a set of resources succinctly. In particular, we generate a quasilinear-sized data structure in polynomial time, which allows the efficient computation of the cumulative failure probability of any set of network elements. Our evaluation is based on carefully pre-processed seismic hazard data matched to real-world optical backbone network topologies.

Routing in large-scale computer networks today is built on hop-by-hop routing: packet headers specify the destination address and routers use internal forwarding tables to map addresses to next-hop ports. In this paper we take a new look at the scalability of this paradigm. We define a new model that reduces forwarding tables to sequential strings, which then lend themselves readily to an information-theoretical analysis. Contrary to previous work, our analysis is not of worst-case nature, but gives verifiable and realizable memory requirement characterizations even when subjected to concrete topologies and routing policies. We formulate the optimal address space design problem as the task to set node addresses in order to minimize certain network-wide entropy-related measures. We derive tight space bounds for many well-known graph families and we propose a simple heuristic to find optimal address spaces for general graphs. Our evaluations suggest that in structured graphs, including most practically important network topologies, significant memory savings can be attained by forwarding table compression over our optimized address spaces. According to our knowledge, our work is the first to bridge the gap between computer network scalability and information-theory.

In order to evaluate the expected availability of a service, a network administrator should consider all possible failure scenarios under the specific service availability model stipulated in the corresponding service-level agreement. Given the increase in natural disasters and malicious attacks with geographically extensive impact, considering only independent single link failures is often insufficient. In this paper, we build a stochastic model of geographically correlated link failures caused by disasters, in order to estimate the hazards a network may be prone to, and to understand the complex correlation between possible link failures. With such a model, one can quickly extract information, such as the probability of an arbitrary set of links to fail simultaneously, the probability of two nodes to be disconnected, the probability of a path to survive a failure, etc. Furthermore, we introduce a pre-computation process, which enables us to succinctly represent the joint probability distribution of link failures. In particular, we generate, in polynomial time, a quasilinear-sized data structure, with which the joint failure probability of any set of links can be computed efficiently.

Lately, there has been an upsurge of interest in compressed data structures, aiming to pack ever larger quantities of information into constrained memory without sacrificing the efficiency of standard operations, like random access, search, or update. The main goal of this paper is to demonstrate how data compression can benefit the networking community by showing how to squeeze the IP Forwarding Information Base (FIB), the giant table consulted by IP routers to make forwarding decisions, into information-theoretical entropy bounds, with essentially zero cost on longest prefix match and FIB update. First, we adopt the state of the art in compressed data structures, yielding a static entropy-compressed FIB representation with asymptotically optimal lookup. Then, we redesign the venerable prefix tree, used commonly for IP lookup for at least 20 years in IP routers, to also admit entropy bounds and support lookup in optimal time and update in nearly optimal time. Evaluations on a Linux kernel prototype indicate that our compressors encode an FIB comprising more than 440 K prefixes to just about 100-400 kB of memory, with a threefold increase in lookup throughput and no penalty on FIB updates.

Today’s ever-growing networks call for routing schemes with sound theoretical scalability guarantees. In this context, a routing scheme is scalable if the amount of memory needed to implement it grows significantly slower than the network size. Unfortunately, theoretical scalability characterizations only exist for shortest path routing, but for general policy routing that current and future networks increasingly rely on, very little understanding is available. In this paper, we attempt to fill this gap. We define a general framework for policy routing, and we study the theoretical scaling properties of three fundamental policy models within this framework. Our most important contributions are the finding that, contrary to shortest path routing, there exist policies that inherently scale well, and a separation between the class of policies that admit compact routing tables and those that do not. Finally, we ask to what extent memory size can be decreased by allowing paths to contain a certain bounded number of policy violations and, surprisingly, we conclude that most unscalable policies remain unscalable under the relaxed model as well.

Large-scale information dissemination in multicast communications has been increasingly attracting attention, be it through uptake in new services or through recent research efforts. In these, the core issues are supporting increased forwarding speed, avoiding state in the forwarding elements, and scaling in terms of the multicast tree size. This paper addresses all these challenges-which are crucial for any scalable multicast scheme to be successful-by revisiting the idea of in-packet Bloom filters and source routing. As opposed to the traditional in-packet Bloom filter concept, we build our Bloom filter by enclosing limited information about the structure of the tree. Analytical investigation is conducted and approximation formulas are provided for optimal-length Bloom filters, in which we got rid of typical Bloom filter illnesses such as false-positive forwarding. These filters can be used in several multicast implementations, which are demonstrated through a prototype. Thorough simulations are conducted to demonstrate the scalability of the proposed Bloom filters compared to its counterparts.

Lately, there has been an upsurge of interest in compressed data structures, aiming to pack ever larger quantities of information into constrained memory without sacrificing the efficiency of standard operations, like random access, search, or update. The main goal of this paper is to demonstrate how data compression can benefit the networking community, by showing how to squeeze the IP Forwarding Information Base (FIB), the giant table consulted by IP routers to make forwarding decisions, into information-theoretical entropy bounds, with essentially zero cost on longest prefix match and FIB update. First, we adopt the state-of-the-art in compressed data structures, yielding a static entropy-compressed FIB representation with asymptotically optimal lookup. Then, we re-design the venerable prefix tree, used commonly for IP lookup for at least 20 years in IP routers, to also admit entropy bounds and support lookup in optimal time and update in nearly optimal time. Evaluations on a Linux kernel prototype indicate that our compressors encode a FIB comprising more than 440K prefixes to just about 100--400 KBytes of memory, with a threefold increase in lookup throughput and no penalty on FIB updates.

Large-scale information distribution has been increasingly attracting attention, be it through uptake in new services or through recent research efforts in fields like information-centric networking. The core issue to be addressed is the more efficient distribution of information to a large set of receivers. Avoiding state in the forwarding elements is crucial for any scheme to be successful. This paper addresses this challenge by revisiting the idea of in-packet Bloom filters and source routing. As opposed to the traditional in-packet Bloom filter concept which represent the trees flatly as sets, we build our filter by enclosing limited information about the structure of the tree, namely its stage decomposition, which helps to get rid of typical Bloom filter illnesses as infinite loops and false positive forwarding. Our analytical and simulation results show that by using this information we obtain more succinct tree representation while still maintaining forwarding efficiency.

In this paper we demonstrate an effective way to classify repeated handovers (ping-pongs) in mobile broadband networks. The paper also presents a method that can significantly reduce unwanted ping-pongs in the network. The method combines a sub cell movement detection method and ping-pong detection to decide when it is most effective to apply handover threshold tuning (pinning) without increasing the risk of late or failed handovers. The algorithm was evaluated based on live network measurements.

This paper takes a first step towards generalizing compact routing to arbitrary routing policies that favor a broader set of path attributes beyond path length. Using the formalism of routing algebras we identify the algebraic requirements for a routing policy to be realizable with sublinear size routing tables and we show that a wealth of practical policies can be classified by our results. By generalizing the notion of stretch, we also discover the algebraic validity of compact routing schemes considered so far and we show that there are routing policies for which one cannot expect sublinear scaling even if permitting arbitrary constant stretch.

Research works concerning AS (Autonomous Systems) level Internet topology measurements typically aim at obtaining near-complete maps of the AS structure. In this paper, we take a fundamentally different approach by inspecting several concurrently visible local views of the AS graph stored at individual BGP route servers. We find that each of these views exhibits the characteristic properties of complex graphs having power-law degree distribution, large clustering coefficient and the small world property. As a main contribution, the intersection of these views is investigated to identify the skeleton of the Internet consisting of edges seen by most of the ASes. Our measurements support the surprising claim that this skeleton is a scale-free complex network, having a giant connected component with a dense part in its heart forming the critical AS level core. We identify the edges in the skeleton as critical infrastructure, any changes of which induces an Internet-wide effect with BGP updates propagating to all ASes. Finally, we reinterpret the path inflation metric using the local view approach and show that local path inflation can be very diverse in different ASes.

Network calculus is the result of recent developments in the area of network analysis, providing considerable insight into the behavior of (packet-based) communication networks. The classical approach uses deterministic bounds to describe systems having stochastic properties in nature, offering simple formulation to a set of-otherwise analytically hardly tractable-problems. Eliminating probabilistic nature, however, often leads to-practically hardly usable-loose bounds after quantification. In this paper, we address the problem of extending the network calculus theory to regain the advantage coming from the statistical multiplexing effect, preserving at the same time easy discussion that the original approach provides us. During the main part of the paper we introduce and discuss some important theorems about the novel effective w-arrival and w-service curves. As an example we show how to apply the results to the efficient computation of the workload loss ratio, as an important and widely used quality of service parameter while remaining in the framework and concept of the network calculus.

The estimation of resource usage in network nodes is a basic issue from the point of QoS (quality of service) provisioning. The estimation of the buffer overflow is considered in network elements represented by a service curve property. Existing results (Vojnovic, M. and Le Boudec, J.-Y., IEEE Trans. Commun., 2002; Gulya/spl acute/s, A. et al., IEEE GLOBECOM, 2004), define bounds on buffer overflow for such elements, multiplexing homogeneous and heterogeneous independent regulated inputs. The requirement of independence for the inputs can be reduced by setting up new bounds for the homogeneous case, using a bounding technique which relies only on the limited independence among the inputs (Siegel, A. et al., ACM-SIAM Symp. Discrete Algms, 1993). Beside the presentation of the new bounds, it is shown that they improve existing ones in all cases, and an investigation is given about the independence properties which are required from the input flows.

Recent Internet access speeds have made it possible even for home users to reach and use previously unavailable bandwidth consuming (e.g. video on demand) services. However, the rapid spread of these applications is hindered by the lack of QoS guarantees in packet networks. In this article a QoS architecture is presented which have been designed for access networks and applies a logical overlay network to make network management tasks easier. The novelty of the architecture lies in the application of two key procedures adopted for dimensioning logical channels between edge nodes and mapping them to the physical routes. The upper load thresholds of the applied logical channels are also determined, which may form the basis of a more sophisticated call admission control policy.

In the widely studied and powerful bufferless fluid flow multiplexing model (bffm), important QoS measures are often considered such as saturation probability and workload loss ratio. When regulated traffic are multiplexed into a buffer, similar QoS measures can also be identified such as buffer overflow probability and buffer workload loss ratio. In this paper, we set up a family of closed-form bounds which can be applied for QoS measures arising in both multiplexing models. The bounds have been compared based on numerical investigations.

The paper is concerned with continuously operating optimization neural networks with lossy dynamics. As the main feature of the neural model time-varying nature of neuron activation functions is introduced. The model presented is general in the sense that it covers the cases of neural networks for combinatorial optimization (Hopfield-like networks) and neural models for optimization problems with continuous decision variables (i.e., Kennedy and Chua's neural network). Besides the rigorous stability analysis of the proposed neural network it is also highlighted the importance of the lossy dynamics, it is shown how to derive lossy versions of improved Hopfield neural models from it and explored the relations to other optimization neural systems.

The paper deals with analog neural networks which can be used for solving nonlinear constrained optimization tasks using the penalty function approach. The neural model developed can be regarded as asymptotically exact dynamic solver in a sense that the equilibrium state represents a solution which can be arbitrarily close to that of the original constrained optimization task. Although it is a quite natural requirement, generally it can be fulfilled only with infinitely large penalty multipliers. The neural network presented provides another way for generating solutions arbitrarily close to the exact one at finite penalty multipliers. The usefulness of the optimization neural network presented is also illustrated by numerical examples.

In this paper we set up a family of conservative upper bounds for QoS measures applicable in QoS guaranteed packet-based communication networks. The bounds are distribution free that is they depend only on the number of traffic sources, the peak rates of the flows and the mean arrival intensity of the aggregated traffic stream. No other information on the traffic distribution is required. The bounds have been developed under the well known bufferless fluid flow multiplexing (bffm) modeling framework, nevertheless, an important property is also discussed in the paper, namely they can also be applicable to the buffered statistical multiplexer case when the input flows are regulated. The performances of the bounds are analyzed and comparative numerical investigations are also presented in both multiplexing models.

The paper is concerned with the approximation of equivalent capacity in the context of bufferless fluid flow multiplexing (BFFM) based on parsimonious characterization of traffic flows, i.e., only the number of flows, the peak arrival rates and the aggregate mean arrival rate are assumed to be known. In bufferless statistical multiplexing, a main stream of research investigates the phenomenon that the combined arrival rate of flows multiplexed on a transmission link exceeds the total link capacity. In the widely studied BFFM model, important QoS measures are often considered, such as saturation probability and workload loss ratio, and, based on these measures, the corresponding minimum transmission capacity required by the flow aggregate. New and direct estimators for the equivalent capacity are presented and compared to previously developed ones; their significance in call admission control is also highlighted. To that end we also perform different approximations of the probability generating functions of the rate distribution of the aggregate flow; they are often essential parts of QoS measure estimates.

This paper is concerned with the saturation probability of aggregate traffic data arrival rate on a communication link. This performance metric also referred to as the tail distribution of aggregate traffic is essential in traffic control and management algorithms of high speed networks including future QoS Internet. In this paper, efficient closed form upper bounds have been derived for the saturation probability when very little information is available on the aggregate traffic. The performance of these estimators is also investigated via numerical examples.

In teletraffic theory an important and useful performance measure is the tail distribution of aggregate traffic. Generally it is very hard and computationally expensive to determine the exact distribution of the aggregate traffic, even if we know the exact distribution of each traffic source. therefore, efficient estimators should be developed. In the paper, we show simple estimators which are based on Hoeffding's (1963) statistical inequalities for tail distribution. The estimators to be presented are very simple, they use only limited information on the traffic characteristics. the properties of these bounds are performed and are also compared by the accuracy and the regions of parameters where they overperform each other. Finally, we present a possibly tighter upper bounds for the tail distribution using more accurate approximations.