There Is More to Internet Invariants Than Meets the Eye

The initial empirical studies of observed self-similar scaling in measured Internet traffic were published in [29, 40]. Almost immediately, the focus shifted from quantifying the extent of self-similar scaling in measured traffic traces to trying and answering the question “Why self-similar?” This question was subsequently answered in [55, 14] where the authors provide an empirically-validated physical explanation that leveraged a generative mathematical construct known as the Mandelbrot process (i.e., superposition of IID renewal reward processes with heavy-tailed rewards/durations). This construction identified the ubiquitously observed heavy-tailed nature of individual flows or file transfers that make up the aggregate self-similar packet traffic as root cause for the observed self-similar scaling behavior [40, 55, 14, 2]. Subsequently, this root cause has also been termed the mice-elephant property of Internet traffic - while most flows are small in size and short-lived in time (mice), a few large and long-lasting flows (elephants) are responsible for most of the traffic. Importantly, answering the question “Why self-similar?” with “Because of heavy-tailed flow sizes/file transfers!” triggered a yet more profound question in the form “Why does Internet traffic have the mice-elephant property?”

This question was addressed in large part in [61], where the authors expanded on the theme of HOT which argues that heavy tails are the ubiquitous outcome of robust designs of complex engineered systems and not the result of some phase transition as is promoted by advocates of Self-organized Criticality (SOC) but which lacks engineering relevance and is not supported by existing networking evidence. More precisely, the HOT approach described in [61] considers the case of WWW, the dominant application on the Internet at that time, and treats the layout of a Web site as an optimal design problem where the design objective is assumed to be the minimization of the average file size (which roughly translates into minimizing the latency that the user experiences in downloading files while browsing the Web site), subject to navigability constraints (e.g., the total number of files on the Web site). When formulating and solving Web layout designs as such constrained optimization problems, the authors of [61] report analytic and simulation results that show that the obtained solutions invariably produce heavy-tailed file sizes. This particular reverse-engineering effort then suggests that heavy tails and, in turn, self-similarity, are a permanent and omnipresent feature of Internet traffic, and not an artifice of current applications or user behavior. In fact, as argued in [61], the obtained findings suggest that “[self-similar] traffic has some aspects which are intrinsic to at least the current dominant application, the WWW, and may be even more intrinsic to any application which organizes information for human consumption.”

The insight that the described HOT-based approach provides for recognizing the temporal self-similarity invariant of Internet traffic (or equivalently, its ubiquitous mice-elephant property) as outward sign or observable manifestation of a fundamental underlying robust Internet design principle is profound; the identified design principle calls for applications to organize information for human consumption. Nevertheless, the type of reverse-engineering efforts motivated by this approach have received surprisingly little attention from the community in the last 25 years. A notable exception are related studies that aim at developing a mathematical theory of network architectures by considering “layering” as optimization decomposition (see [13] and references therein). Below, we discuss a number of topics that explicitly concern the design of future networked systems and will require further reverse- or forward-engineering efforts (beyond the scope of this paper) to substantiate our stated hypotheses that are largely informed by our current understanding of the corresponding past reverse-engineering efforts.

To study aspects of the spatial structure of observed IP addresses in measured Internet traffic, we consider datasets such as CAIDA500k that was obtained by using the first $500,000$ unique source IPv4 addresses observed in the CAIDA-dir-A trace [8].³³3We experimented with datasets of different sizes and assembled over different periods of the CAIDA dataset and observed no qualitative differences. To develop intuition about how sets of such observed addresses populate the IP address space, we leverage the geometric interpretation of observed sets of IPv4 addresses either as point sets in the discrete 1D interval $[0,2^{32}-1)$ or in the discrete 2D square $[0,2^{16}-1)\times [0,2^{16}-1).$⁴⁴4A similar exercise can be conducted for IPv6. In Figure 1, we use the well-known Hilbert curve-based visualization method that maps the 1D IPv4 address space into a 2D square-image [9, 25, 47] and has the property that prefixes always appear as squares next to their siblings and within their parents (under the usual CIDR interpretation of bit-wise address prefixes).

In particular, the two rows in Figure 1 show this visualization for the dataset CAIDA500k (Figure 1(a)) and for a set of 500k distinct addresses sampled from a uniform distribution (Uniform500k, Figure 1(b)). The coloring of each square indicates the relative number of actual IP addresses (i.e., /32 prefixes) observed in the corresponding prefix (e.g., red (blue) prefixes contain one or more (no) observed IP addresses). For each row, the first visual shows the IPv4 space at /8 granulairy, and each subsequent visual “zooms-in” on the marked prefix in the previous visual at longer prefix length until individual source addresses (in a particular /24) manifest in the last visual of a row.

The stark visual difference apparent between Figure 1(a) and Figure 1(b) illustrates the complex intrinsic “cluster-within-cluster” structure of real-world IP addresses, a telltale sign of multifractal scaling identified in previous work [26, 27, 5, 34]. In the case of CAIDA500k (Figure 1(a)), the zoom-in’s for the intermediate stages look qualitatively similar (with the exception of artifacts in the first and last visuals due to known reserved blocks of IPs and discreteness effects, respectively) and exhibit visually apparent cluster-within-cluster behavior with no “typical” cluster size (e.g., in terms of their area or their number of addresses as indicated by color). In the case of Uniform500k (Figure 1(b)), we also observe qualitatively similar-looking zoom-ins across the different visuals, but the appearance of the zoom-ins is noticeably less “intermittent” – the cluster-within-cluster behavior is more regular and allows for discerning a high degree of uniformity (in terms of color) and homogeneity (with respect to cluster size).

While the presented evidence in § 3.1 is only pictorial in nature and concerns only a single dataset of observed IP addresses from one real-world traffic trace, the analysis reported in [34] uses newly developed robust statistical techniques to rigorously show that this pictoral evidence is indeed consistent with statistical multifractal scaling and holds across a wide range of different past and present real-world Internet traffic traces. In fact, the results of this comprehensive empirical study support our main observation that the obtained evidence in favor of a multifractal structure of observed IP addresses in measured network traffic is not limited to a specific time, type of traffic, or vantage point within the Internet, thus confirming multifractal IP address structure to be an invariant of measured Internet traffic.

Given its ubiquitous presence, we next seek to explain the underlying processes through which such multifractal scaling comes about in these observations. To this end, we advance the hypothesis this new Internet traffic invariant arises through the combination of a conservative cascade process (initially proposed in [5, 48]) that captures how IP address spaces are divided up and allocated (§ 3.3 - 3.4) and a process that accounts for the uncertainty of encountering allocations associated with different types of organizations or Internet stakeholders depending on where in the Internet traffic is measured (§ 3.5).

A conservative cascade is a random cascade model where at each recursive step, a given “mass” (defined here as the number of distinct observed addresses) associated with parent prefixes is divided between child sub-prefixes. Under the CIDR interpretation of IP address “prefixes”, this cascade forms a binary tree with (i) the “mass” associated with each non-leaf node corresponding to the number of IP addresses observed in each particular prefix, (ii) leaves with unit mass corresponding to observed IP addresses (i.e., /32s), and (iii) the number of recursive steps taken as prefix length or level in the tree. The splitting of mass between parent and child nodes is governed by a random variable denoted $W$ and called the cascade’s generator, where $W$ has a particular dependence structure that forces “mass” to be conserved at each step of the cascade.

To formalize this view of the IP address space, consider the bit-level representation of a $/l$ address prefix $x=⟨x_1,x_2,\mathrm{\dots },x_l⟩$ where $x_i\in \{0,1\}$ for $1\le i\le l$. The conservative cascade model with generator $W$ (where $W$ takes values in $[0,1)$, has mean 1/2 and is symmetric about its mean) is a set of random variables $\{W_{l,j}:l>0$ and $1\le j\le 2^l\}$ where (i) the $W_{l,j}$’s between different levels $l$ are independent and identically distributed, and $W_{l,j}$ determines how much “mass” is split to the $j$-th child prefix at level $l$, and (ii) the $W_{l,j}$’s at level $l$ conserve “mass”, that is they have a dependence structure given by $W_{l,j+1}=1-W_{l,j}$ for odd $j$’s.⁵⁵5Note that because of the properties of $W$, $W_{l,j+1}=1-W_{l,j}$ are identically distributed as $W$. If the total “mass” is given by $Z$, then (by independence of the $W_{l,j}$’s between different levels $l$) the measure or “mass” of a given $x$ at level $l$ is

where $j_i=1+{\sum }_{1\le k\le i}{x}_k{2}^{i-k}$ specifies the prefixes at levels $i\le l$ that contain $x$ (i.e., the path from $x$ to the root of the binary tree). To illustrate, Figure 2 shows a simplified view of the first four levels and the “mass” of a particular /4 prefix.

In the mathematical literature, conservative cascades are usually treated in the limit as $l\to \mathrm{\infty }$ where the “mass” associated with each branch is a real number and the tree structure shown in Figure 2 is understood as representing dyadic partitions of an interval such as the unit interval $[0,1)$ on the real line [17, 46]. Under certain technical conditions, these limiting objects can be shown to define multifractals (more precisely, multifractal measures) that can be described in terms of well-defined theoretical properties such as the fractal dimension of their support [37, 42] or their multifractal spectrum. However, as we will see in § 3.6, the finite discreteness of IP addresses requires several non-trivial modifications to this traditional view, including the need to focus on “pre-limit” behavior and work with finite approximations of objects that exist and are defined as mathematical limits.

A key point of potential confusion here is that although the conservative cascade model implies the evolution of a process over time, the sets of IP addresses that we seek to analyze in this work are based on fixed “snapshots” frozen in time. To rectify this confusion, we consider the conservative cascade as representing the cumulative actions of all address allocation and assignment events leading up to the particular moment when the observed snapshot was captured. Although the real-world allocation processes modeled by the conservative cascade and discussed in the next section do inherently evolve over time, from the perspective of a particular snapshot, they concern a fixed history that determines the particular probability distribution influencing which addresses end up appearing in the snapshot (i.e., based on which prefixes have been allocated, assigned, and advertised at some point in the past).

Despite the apparent correspondence between the CIDR prefix organization of IP addresses and a baseline conservative cascade model, to leverage this model to explain the processes behind observed multifractal scaling, we must connect the model to real-world Internet-related processes. We make this connection through the following two observations: Observation 1 (§ 3.4.1): The hierarchical organization of networks (reflected in address allocations) leads to a non-trivial number of explicit and implicit cascade levels (more than three, less than 32 for IPv4 or 128 for IPv6). Observation 2 (§ 3.4.2): The lack of distinctive prefix lengths of blocks of allocated addresses requires the bit-by-bit CIDR-based cascade construction.

To demonstrate that the conservative cascade of IP address allocation inevitably features imperfect balance between children (i.e., the support of the distribution of $W$ does not consist of the single point 1/2) – and hence the inevitability of multifractal scaling of observed IP addresses – we show through a simple first-principles argument that particular vantage points will observe different allocations with different weights.¹⁰¹⁰10[33] presents empirical evidence for a similar argument, though they do not aim to characterize observed address structure as considered in our work. Assuming for simplicity bidirectional traffic (for the unidirectional case, recall from the comment at the end of Section 1 that we focus on IP addresses associated heterogeneous sets of hosts, applications, and services), this argument unfolds through the following three steps.

1. 1.

   Consider a particular arbitrary network X. X is assigned addresses and uses them for different purposes. Given the common client-server architecture, we can group these purposes as being client-oriented (associated with initiating connections) or server-oriented (associated with accepting connections from clients).

2. 2.

   Different networks have different balances of clients and servers. Since the cascade process of allocation lacks a “preferred” prefix length of allocations (i.e., there exists no “typical” size of prefix allocation), the “client weight” (respectively “server weight”) is clustered across the address space, thus implying that there is not a uniform or homogeneous mix of clients and servers w.r.t. the address space.

3. 3.

   When we observe traffic at a particular vantage point, whether or not we see addresses assigned to X depends on X’s client/server balance and the position of the vantage point within the Internet. If the vantage point is near a server-heavy region, it is more likely to see X if X is client-heavy. On the other hand, if the vantage point is near a client-heavy region, it is more likely to see X if X is server-heavy. In this way, the client-server weight of the address space translates directly into the “number of addresses per prefix” weight considered in our conservative cascade model (with the position of the vantage point balancing between client weight and server weight).

For example, consider the simplified scenario shown in Figure 7 where three networks, X, Y, and Z use the same number of addresses, but have different numbers of servers and clients exchanging traffic through the Internet. Suppose also that each client independently selects one of the five servers uniformly at random and communicates only with that server. The probability¹¹¹¹11Given by simple composition of the complement and union probability rules and independence between clients. that traffic is exchanged between addresses in two different networks $i,j\in \{\text{X},\text{Y},\text{Z}\}$ is given by $P(i\leftrightarrow j)=(1-{(1-s_j/{\sum }_k{s}_k)}^{c_i})+(1-{(1-s_i/{\sum }_k{s}_k)}^{c_j})-(1-{(1-s_j/{\sum }_k{s}_k)}^{c_i})\cdot (1-{(1-s_i/{\sum }_k{s}_k)}^{c_j})$ where $s_k$ is the number of servers and $c_k$ is the number of clients in network $k\in \{\text{X},\text{Y},\text{Z}\}$. By plugging in the numbers of clients and servers shown in Figure 7, it can be seen that because of different server-client composition, the probability of seeing an address from network Y is high ($\sim$0.95) at network X and significantly lower ($\sim$0.74) at network Z.

To quantify how well the imperfectly balanced conservative cascade model described above fits real-world observed sets of IP addresses, we develop an approach to fitting the distribution of the cascade generator $W$ to observed addresses.

The basic approach to such fitting involves computing first the empirical “weights” given by $w_{l,j}={\mu }_l(x_1,\mathrm{\dots },x_j)/{\mu }_{l-1}(x_1,\mathrm{\dots },x_{j-1})$ and then estimating the distribution of $W$ by considering the $w_{l,j}$’s to be i.i.d. observations of $W$.

To illustrate the challenges of this approach, we compute the $w_{l,j}$’s for the CAIDA500k dataset and show their distribution for three example prefix lengths (i.e., $l=8,16,24$) in Figure 8. Although the $w_{l,j}$’s are clearly symmetric (i.e., mean 1/2), they also have two features that complicate the fitting task. First, the shape of the distribution depends strongly on $l$ and second, there are strong modes that begin to appear at 0.0 and 1.0 for longer prefix lengths.

The conservative cascade model that explains why observed sets of IP addresses exhibit multifractal scaling has several important implications.

• $\mathrm{■}$

  Even if every single address in the address space is actively allocated, the traffic traversing particular Internet vantage points will still exhibit multifractal scaling similar to that observed in Figure 1(a). This follows because the allocation cascade described in § 3.4 has no distinct prefix lengths, and the observation process described in § 3.5 implies that the weights $W_{l,j}$ are non-deterministic and dependent on the location of the vantage point in the Internet graph relative to different types of hosts.

• $\mathrm{■}$

  Because we observe similar allocation policy and communication patterns for both IPv4 and IPv6, the conservative cascade model applies equally to both cases regardless of their relative densities (i.e., extreme density of IPv4 address space utilization vs. extreme sparseness of IPv6 address space utilization).

• $\mathrm{■}$

  The dependence of the cascade weights on vantage point location (§ 3.5) implies that the structure of IP addresses captured by the conservative cascade depends directly on the vantage point itself and hence can be used as a digest or “fingerprint” of communication patterns at that vantage point.

• $\mathrm{■}$

  The method of fitting the distribution of the generator $W$ (§ 3.6) implies an efficient approach to generate synthetic sets of IP addresses that closely mimic those encountered in measured Internet traffic, enabling verification and evaluation of existing and future technologies [34, 48].

The IP address allocation processes analyzed in Section 3 resulted from decades of applied experience and fundamental insights into address allocation procedure design. These efforts trace back to the pioneering work of John Postel and resulted, among other achievements, in the inception of the Internet Assigned Numbers Authority (IANA) that is responsible for the global coordination of the Internet protocol addressing systems [20]. To understand why conservative cascade-like processes appear to underlie real-world address allocations, we apply the HOT perspective to distill the Internet address allocation problem in terms of several networking objectives and constraints and propose a generic allocation procedure that directly seeks to satisfy these objectives and constraints in the face of uncertainty in the environment. Based on empirical simulation, we show that our HOT-inspired procedure effectively balances the competing goals of maximizing address space utilization while minimizing address space fragmentation and yields allocation size distributions that exhibit heavy-tailed characteristics, irrespective of the precise nature of how uncertainty is quantified (e.g., the distribution of addresses requested by the different Internet stakeholders can be light-tailed or heavy-tailed).

Our HOT-inspired initial generic cascade-based design procedure for Internet address allocation suggests that the kind of cascade structures observed in real-world allocation data (described in Section 3) arise as a result of optimization efforts that try to maximize the number of addresses allocated and minimize fragmentation in the face of uncertain demand from client organizations. Put differently, the ubiquitous multifractal scaling behavior of sets of observed IP addresses in measured Internet traffic can thus be recognized as an outward sign of an underlying (and at best only implicitly pursued) design effort for Internet address allocation that is made explicit by our proposed cascade-based procedure that manifests as a solution of a concrete constrained optimization problem. Below, we briefly comment on implications of this finding for future research efforts.