{'fraction_non_alphanumeric': 0.039566250649207574, 'fraction_numerical': 0.0077117990525504025, 'mean_word_length': 4.710947330577027, 'pattern_counts': {'":': 1, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the Complexity of Traffic Traces and Implications

This paper presents a systematic approach to identify and quantify the types of structures featured by packet traces in communication networks. Our approach leverages an information-theoretic methodology, based on iterative randomization and compression of the packet trace, which allows us to systematically remove and measure dimensions of structure in the trace. In particular, we introduce the notion of \emphtrace complexity which approximates the entropy rate of a packet trace. Considering several real-world traces, we show that trace complexity can provide unique insights into the characteristics of various applications. Based on our approach, we also propose a traffic generator model able to produce a synthetic trace that matches the complexity levels of its corresponding real-world trace. Using a case study in the context of datacenters, we show that insights into the structure of packet traces can lead to improved demand-aware network designs: datacenter topologies that are optimized for specific traffic patterns.


INTRODUCTION
Packet traces collected from networking applications, such as datacenter traffic, have been shown to feature much structure: datacenter traffic matrices are sparse and skewed [16,39], exhibit locality [21], and are bursty [77,83]. In other words, packet traces from real world applications are far from arbitrary or random.
Motivated by the existence of such structure, the networking community is currently putting effort into designing protocols and algorithms to optimize different layers of the networking stack to leverage the traffic structure. These efforts include learning-based traffic engineering [70] and video streaming [55], demand-aware and self-adjusting reconfigurable optical networks [14,39,42,57], or self-driving networks [69,76]. For instance, many network optimizations exploit the presence of elephant flows [5]. However, the available structure can differ significantly across applications, and we currently lack a unified approach to measure the structure in traffic traces in a systematic manner, accounting for both non-temporal structures (e.g., how skewed the traffic matrices are) and temporal structures (e.g., how bursty traffic is). The quantification of trace structures and their locality can be very useful; it can shed light on the potential of traffic-aware optimization, and facilitate traffic modeling, benchmarking, and synthesis; these are otherwise difficult to achieve, given the limited amount of traffic data available to researchers today.
Let us illustrate the temporal and non-temporal structures available in a traffic trace with an example. Consider a packet trace from a Machine Learning (ML) application based on a popular convolutional neural network training job, with four GPUs. Figure 1(a) visualizes the trace where each packet in the trace is represented by a unique color corresponding to its (source, destination)-GPU pair. The figure highlights the temporal structure of the trace: the sequence of colors is far from random. Rather, a pattern is revealed, where certain colors are more frequent in some intervals than in others. For comparison, Figure 1(b) shows the same trace, but randomizes the order of the entries in the trace: the randomization removes the temporal structure observed in Figure 1(a). Intuitively, the trace in Figure 1(a) has more temporal structure than the trace in Figure 1(b). However, the frequency distribution of the two traces is the same: summing up the entries over the entire trace file results in the same traffic matrix (TM), shown in Figure 1(c).
The resulting traffic matrix shows structure as well. In this case the traffic matrix is skewed, i.e., some GPU pairs communicate more frequently than others. That is, the traffic matrix loses information about temporal differences, and it features a non-temporal structure. For comparative purposes, consider two synthetic traces shown in Figures 1(d) and (e). Trace (d) is generated uniformly and random and has the least temporal structure compared to (a), while trace (e) is bursty and built from consecutive source-destination requests, and hence has the most temporal structure. Similarly, the traffic matrix in Figure 1(f) captures the non-temporal structure in both (d) and (e), but not the temporal structure. The traffic matrix is almost uniform, and hence has less structure than (c). Temporal complexity Non-temporal complexity Fig. 2. The complexity map of six real traces (colored circles) and four reference points (grey circles at the corners). HAD, WEB, and DB refer to Facebook's Hadoop, web, and database traces [63]. Two corresponding traces from Figure 1, traces (a) and (d), are shown above the map. More details about the traces are provided in Table 2.
model to generate traffic traces that match the complexity of production-level traces, also allowing us to derive theoretical properties of the complexity for stationary processes.
As an empirical contribution, we shed light on the different complexities of 17 different traces, shown in Table 2, including production-level traces (from Facebook [63] and High Performance Computing [29] workloads), NS2 simulation-based traces (pFabric [5]), a Machine Learning workload, as well as synthetically generated traces as reference points (for uniform, skewed, and bursty traffic patterns). We offer several empirical insights into these traces, e.g., on the application-specific structures, on the differences between the structures available at rack-level versus IP-level, or on the differences between the structures of sources versus destinations.
As a contribution to the networking community and in order to facilitate future research in the area, we made available a website trace-collection.net with more resources and data related to this paper. We plan to extend this website further in the future.
The rest of this paper is organized as follows. We present our approach in §2, and report on empirical results in §3. We introduce our model in §4 and discuss our case study in §5. In §6 we extend our initial complexities. After reviewing related work in §7, we conclude the paper in §8.

SYSTEMATIC QUANTIFICATION OF TRAFFIC COMPLEXITY
This section presents our approach to systematically quantify the inherent structures in packet traces. Informally, we are given a packet trace, σ , and, for now, we assume it simply lists the communicating source-destination pairs (e.g., servers or racks) over time. Taking an informationtheoretic perspective, we propose to quantify the complexity of the trace by its empirical entropy, or more precisely, by its (approximate) empirical entropy rate. Entropy and entropy rates are measures of uncertainty: the larger the entropy rate, the more uncertainty about future elements and the more complex the trace. Conversely, when the entropy rate is low, the trace has more structure, is more predictable, and is therefore less complex. We refer to the Appendix A for a brief reminder of formal entropy definitions. Recently, a relationship between the entropy of packet traces and the achievable route lengths in reconfigurable datacenters has been shown [9] (more details will follow in the case study and related work sections).
Let us first define a reference point (i.e., a reference trace) to normalize the complexities of different traces and compare them. We define this as a uniform random trace generated over the identifiers (i.e., the sources and destinations) contained in σ . Intuitively, from an information theoretic perspective, a sequence of identifiers chosen uniformly at random has a maximum (empirical) entropy, and cannot be compressed. In contrast, if a sequence of identifiers is wellstructured and predictable, e.g., a sentence in English, it can be compressed fairly well. The same holds for traffic traces, and we define the normalized trace complexity of a trace σ as the ratio of its complexity over that of a uniform random trace.

Iterative Randomization and Compression
Two main concepts are at the heart of our approach: • Compression to measure the entropy rate: We employ compression of the given packet trace to measure the complexity of the information it contains (i.e., entropy rate). • Randomization to eliminate structure: We systematically randomize different structural dimensions contained in a packet trace, to measure the relative contributions of the different complexity dimensions of the trace as these are compared to the overall trace complexity.
Next, we explain these two concepts more thoroughly. Compression Based Measure of Entropy Rates. Our methodology relies on the idea of using principles of data compression to measure the empirical entropy rate of a traffic trace. Intuitively, the better we can compress a traffic trace σ , the lower its entropy rate and hence its complexity must be. To this end, we assume a compression function C which can be applied to a sequence σ ; we assume σ is a trace file, i.e., a packet trace consisting of source-destination pairs. Since we are primarily interested in the entropy contained in a sequence σ , we assume C(σ ) is simply the size of the compressed file (rather than the compressed file itself). When σ is a random sequence, we take C(σ ) to denote the expected size of the compressed random sequence. To give a concrete example, for our evaluations, we use the 7zip compressor with Lempel-Ziv-Markov chain compression (LZMA) [1]. However, other compression techniques from the LZ family of lossless compression algorithms, such as DEFLATE [28], could also be used. Our experiments with different state-of-the-art compressors show that the variance is fairly low, and does not affect our conclusions.
Of course, we could think of even more sophisticated approaches; for example, we could define the trace complexity via the Kolmogorov complexity. However, while interesting in theory, such complexities are known to be difficult or even impossible to compute [52]. In contrast, lossless compression algorithms, especially LZ, provide a consistent way of estimating the complexity [45,51,81]. Eliminate Structure by Randomization. How much structure is contained in σ ? To answer this question, we propose comparing the complexity of σ to the complexity of another trace, f (σ ) which "is similar to σ ", but for which parts of the structure of σ has been removed. Our key idea is to construct f (σ ) from σ , using randomization to eliminate structure in σ .
As an extreme case we first consider U(σ ), which "is like σ ," but is of maximum possible complexity; i.e., U(σ ) does not contain any structure and has maximal entropy rate. We construct U(σ ) from σ as follows: U(σ ) is defined over the same set of unique communication endpoints (or nodes) Table 1. Example of a trace and its random transformations. Each entry (S,D) represents a source-destination pair. The complexity of the traces increases column-by-column from left to right, while their structure decreases.
arrive order original trace row trans. column trans. pairs trans. uniform trans. σ as σ . However, the communication between these nodes is completely random. For each entry in σ , U(σ ) contains an entry where the source and the destination are chosen independently and uniformly at random from the set of nodes in σ . In other words, U(·) is a function to transform a given trace into its "most complex" counterpart of the same length and number of unique elements. Each unique element (source or destination) in σ can be in any position in U(σ ), uniformly at random. Our approach to eliminate structure using randomization can be refined further. As we go on to show, such refinement will allow us to chart a complexity landscape of traffic traces. While U(σ ) removes any structure in σ , we show that U(σ ) is just one end of the spectrum, and there is a rich range of complexities between σ and U(σ ). In particular, using our methodology, we randomize different dimensions of σ and generate a sequence of transformations of trace σ , that lie between σ and U(σ ). By compressing a sequence σ and its transformation f (σ ) individually and comparing the resulting compressed sizes, we can observe the amount of complexity contained in f (σ ) compared to σ . Table 1 gives an example of a trace σ over the IDs A, B, C, D and E, and the random transformations we discuss later in the section. For now, we simply consider σ in the second column and the uniform transformation, U(σ ), in the last column.
Let us also ignore the other fields in a packet header (e.g., packet size, port numbers, inter-arrival times, etc.) and focus on the order of entries in the trace to capture the temporal complexity of the trace and on source/destination pairs to capture non-temporal complexity.
We now formally define the normalized trace complexity, as well as the temporal and non-temporal complexities of a sequence σ . Normalized Trace Complexity. As discussed earlier, C(·) represents the size of the compressed trace file; the more structure a trace has, the better it can be compressed. We therefore define the normalized trace complexity, Ψ(σ ), as the ratio of the size of the original compressed trace of the original trace, C(σ ) to, and the expected file size of a reference trace with maximal complexity (i.e., maximum entropy) C(U(σ )): Definition 1 (Normalized Trace Complexity). Let σ be a trace and U(σ ) its uniform random transformation. The trace complexity of σ is defined as: . (1) Since Ψ(·) represents the size of a compressed trace file and U(σ ) is maximally complex,Ψ(U(σ )) ≥ Ψ(σ ), and Ψ(σ ) ∈ [0, 1]. 1

Temporal and Non-Temporal Complexity
We now investigate the two main dimensions of complexity: temporal and non-temporal complexity. Both can display interesting locality properties; some pairs may communicate more frequently than others, resulting in spatial (non-temporal) locality, and the communication demand between other pairs may be bursty over time, resulting in temporal locality. Temporal Trace Complexity. We propose to capture the temporal structure in a trace, σ , including its burstiness, by systematically randomizing the original trace to eliminate all temporal relations in the trace and obtain a new trace file Γ(σ ). Intuitively, Γ(σ ) is a trace wherein each communication request is chosen randomly and independently of past requests. Formally, let Γ(σ ) be a temporal transformation, i.e.,transformation that performs a uniform random permutation of the rows (sourcedestination pairs (s t , d t )) of σ , eliminating any time dependency between rows. Therefore, the probability of any pair (s t , d t ) appearing during time t is independent of t and of past elements in σ . Since Γ(σ ) has (on expectation) less structure, we expect that C(σ ) ≤ C(Γ(σ )). Figure 1(b) is an example of a temporal transformation of the trace shown in Figure 1(a). Another example is in Table 1. To measure how much temporal complexity is contained in σ , we normalize it by the complexity of its temporal transformation, Γ(σ ). Formally, Definition 2 (Temporal Trace Complexity). Let σ be a packet trace; then, the normalized temporal trace complexity of σ is: . ( Note that T (σ ) ∈ [0, 1]; the lower this value is, the better σ can be compressed compared to Γ(σ ), indicating a stronger time dependency and therefore a lower temporal complexity. Non-Temporal Trace Complexity. Informally, the complexity remaining after the elimination of temporal complexity is considered non-temporal. That is, non-temporal structure, structure which is unrelated to the order of entries in the trace is unaffected by the transformation Γ(σ ). Correlations such as request frequency and source-destination dependency are conserved; only the order of the source destination pairs is changed. This can be formally defined using our methodology by normalizing Γ(σ ) with U(σ ) which has maximum complexity and no structure: Definition 3 (Non-Temporal Trace Complexity). Let σ be a trace sequence; then, the normalized non-temporal trace complexity of σ is: It directly follows from our definition that: Observation 1. The normalized trace complexity of σ is the multiplication of the temporal and non-temporal complexities. Formally A nice feature of the above methodology is that is allows us to compare traces of different sizes and domains. Each trace is compared only to its own structure and transformations, , thus providing a unified measure across different traces.  The above three complexities are not restricted to pairwise request sequences, and they are well-defined for sequences of single elements as well. Therefore, we later use the temporal and non-temporal complexities of the source-only sequence, denoted as σ s (i.e., the first column of the trace) and the destination-only sequence, denoted as σ d (i.e., the second column of the trace). In §6 we define other types of complexities specific to pairwise communication requests.

THE COMPLEXITY OF REAL TRACES
In this section, we first propose a graphical representation, called the complexity map, to quantify and compare the normalized complexity and the temporal and non-temporal complexities of different traces, using a 2-dimensional plane ( §3.2). We then employ the complexity map to analyze real-world traces ( §3.3).

Datasets
As shown in Table 2, our dataset consists of 17 main traces from five sources; the first three (ML, Facebook, and HPC) are real world traces, and the others (pFabric, reference points) are synthetic, generated from a simulation. Facebook: DB, HAD, and WEB clusters. Our largest dataset describes Facebook datacenter traffic [63]. It comprises three different datacenter cluster traces with more than 300M entries each. We only consider the first 10% of the entries, sorted by increasing timestamp for performance reasons. Each entry contains information about source and destination pods, racks, and IP addresses. The clusters represent different application types: Hadoop (HAD), a Hadoop cluster; web (WEB), servers serveing web traffic; and databases (DB), MySQL servers which store user data and serve SQL queries. As each type has a trace corresponding to two aggregation levels (IP and rack-level), we have a total of six traces. We note, however, that the dataset is highly sampled at the outbound link of only a part of the racks in the datacenter at a rate of 1:30,000 [63]. To account for this, we modify the uniform transformation U(σ ) so that it will generate the source and destination columns individually, each only from the set of IDs found in its respective columns (we note that this only increases the complexity). As in all traces, we uniformly hash all the source (destination) IDs, into 2 log n bits.  NeckBone. These represent different applications and show the communication patterns for 1024 CPUs. Machine learning (ML). This trace was collected by measuring the communication patterns for four GPUs running VGG19, a popular convolutional neural network training job. Each line of the workload has a time-stamp and the amount of data transferred. pFabric [5]. pFabric is a minimalist datacenter transport design. For our evaluation, we generated packet traces by running the NS2 simulation script obtained from the authors of the paper [5], reproducing the "web search workload" scenario at three different load levels, 0.1, 0.5, and 0.8 (higher load means more flows). The pFabric trace is a synthetic trace with a Poisson arrival process. When a flow arrives, the source and destination nodes are chosen uniformly at random from a set of 144 different IDs.

The Complexity Map
We introduce an intuitive graphical representation called a complexity map to visualize temporal and non-temporal complexity on a 2-dimensional plane as demonstrated in Figure 3.
The complexity map allows us to compare the complexity of various traces in our datasets and has a 2-dimensional abstraction where the x-and y-axes represent the temporal and non-temporal complexity dimensions respectively. More specifically, each trace σ is represented as a circle on the map; the location of the circle depends on the temporal and the non-temporal complexity of the trace, i.e., (T (σ ), NT (σ )), and the area of the circle corresponds to the overall complexity of σ , Ψ(σ ), calculated by multiplying the temporal and non-temporal complexities of σ , as described in §2.
Before we analyze traffic traces in more detail, we introduce some additional features of the complexity map and give a concrete example. Reference points. For a better understanding of the complexity map, in addition to the traces themselves, we will sometimes include the following four reference points on the complexity map (see Figure 3): • Uniform: This reference point describes a trace which does not have any structure.
• Bursty: This reference point describes a simple temporal pattern. Specifically, it corresponds to a communication pattern that is perfectly uniform over the IDs; however, the IDs come in short bursts. • Skewed: The skewed reference point describes a simple non-temporal pattern; it features a skewed distribution over the IDs but no bursts over time. • Skewed & bursty: The reference point describes traces that are both bursty and skewed.
In more detail, the Uniform trace, u, is located at (1,1); it has the highest possible complexity (in both dimensions, T (u) = 1 and NT (u) = 1 and in total) and hence has no structure. Both T (u) = 1 and NT (u) = 1 which means that the trace is a uniformly chosen random sequence, and u is "similar" to U(u). The Skewed trace s, is located at (1,0.4); this indicates that it has high temporal complexity, T (s) = 1, and low non-temporal complexity, NT (s) = 0.4. This results if the IDs in the sequence are chosen i.i.d. from the distribution (and hence with high temporal complexity), but are selected from where the distribution is skewed, with low entropy (and hence low non-temporal complexity). In contrast, the Bursty trace, b, located at (0.4,1), has low temporal complexity, T (b) = 0.4, and high non-temporal complexity, NT (b) = 1. Here, the accumulated source-destination pair distribution is uniform, i.e., with high non-temporal complexity, but each request is repeated for some time (i.e., modeling a burst), creating temporal patterns and lower temporal complexity. Last, the Skewed & Bursty trace, located at (0.4, 0.4), has the lowest complexity on the current map and has both temporal and non-temporal structures. Requests are temporally dependent (i.e., with repetitions) but, at the same time, new requests arrive from a skewed distribution. Returning to Figure 1, trace (a) is an example of a Skewed & Bursty trace, trace (b) is a Skewed trace, trace (d) is a Uniform trace and trace (e) is a Bursty trace. All four type of traces can be generated using a Markovian model as we describe in more detail in § 4. Example and intuition. As an example, we consider the two HPC traces, CNS and MultiGrid; see  42. We observe that the complexities of these applications differ. To validate these differences, in Figure 4, we plot the traffic matrix of the CNS and MultiGrid traces in Figure 3, in addition to the uniform reference point. The observation that MultiGrid has less non-temporal complexity than CNS corresponds to the differences in their traffic matrices shown in Figure 4. In particular, we observe that the traffic matrix in Figure 4(a) has less structure than the traffic matrix in 4(b); hence CNS has higher non-temporal complexity than MultiGrid. In contrast, Figure 4(c) shows no structure, hence it has the highest non-temporal complexity in the complexity map in Figure 3. This correspondence nicely illustrates the potential expressiveness of the complexity map.

Analyzing Complexity Maps
We now apply the complexity map to the different traces more systematically to shed light on their characteristics. In what follows, we use our example traces to illustrate the different types of insights yielded by our approach. Takeaway 1: Applications have characteristic structures. A first observation is that different applications have different characteristic structures, on both temporal and non-temporal dimensions. This can already be observed in the Facebook traces; Figure 5(a) shows the complexities of three Facebook clusters, HAD, WEB, and DB, at two aggregation levels, IP and rack. On the IP level, the Hadoop trace is less complex than the DB trace, and on the rack level the WEB trace is less complex than the other traces. Takeaway 2: Aggregation matters. The fact that Facebook traces comprise both IP-to-IP and rack-to-rack traffic allows us to shed further light on the impact of the aggregation level. Is there more or less structure on higher levels of the datacenter? In Figure 5(a), we can observe that at the rack level, there is more temporal complexity, with communication becoming more random. Moreover, WEB and DB have a slightly lower non-temporal complexity on the rack level than their IP-level traces; this suggests that the rack traffic has a higher structure and placement in datacenters is subject to optimization. In the case of HAD, the rack-level complexity is higher than the IP-level complexity, on both temporal and non-temporal dimensions; as we move higher in the network topology, from IP to rack, communication becomes more uniform. Takeaway 3: Sources and destinations behave differently. In Figure 5(b), we plot two Facebook traces, rack-level HAD and IP-level WEB, along with their respective source (only) and destination (only) traces. The results illustrate that even if two pair traces appear to have relatively similar complexities, the behavior of their respective source and destination columns may be very different. The IP traces for the WEB application reveal that the sources have far less temporal complexity than the destinations, arguably explained by the source-based star-like communication pattern of a web server. The lower non-temporal complexity indicates a more skewed popularity distribution of the source web servers (compared to cache destinations which are load-balanced and more uniform). In contrast to the web trace, the high non-temporal complexity of the sources for Hadoop on the rack level shows a rather uniform distribution. However, temporal structure may be leveraged by consecutive communications. The low non-temporal complexity of destinations is likely a result of the outbound sampling of the Facebook trace. Takeaway 4: Evidence of optimization. We note that the Hadoop traffic is skewed towards mainly inner-rack traffic (traffic from a rack to itself) while traffic between racks is more sparse, confirming similar results in the literature [63]. If this pattern is consistent with the rest of the network (since we do not sample from these racks), this means they are under-represented as destinations, causing the distribution to be skewed. The lower inter-rack traffic also indicates optimizations in the resource allocation in the datacenter. These results showcase how inspecting different parts of the trace may lead to different conclusions on the inner workings of a network and introduce different optimization problems. Temporal complexity Non-temporal complexity Temporal complexity Non-temporal complexity Takeaway 5: HPC traces feature a great deal of structure. In Figure 6(a), we plot the complexity results of four high performance computing applications (HPC) taken from [29]. The applications are: CNS, MultiGrid, MOCFE, and NeckBone. Each pair trace is given its own corresponding source and destination trace, as illustrated by Figure 6(a) for MOCFE, a Method of Characteristics for a reactor simulation task [40]. When the map is analyzed, it is apparent the HPC traces have some distinctive common characteristics. All have rather similar temporal complexity, and all traces seem to form a "triangle" between the pair, source and destination complexities. At the bottom is the pair trace, on the upper right is the source trace, and on the upper left is the destination trace. We can clearly see this pattern in the MOCFE trace in Figure 6(a). Furthermore, all pair traces other than CNS seem to cluster around the same region. The reason for CNS' higher non-temporal complexity can be seen in Figures 4(a) and (b). The CNS matrix is less structured than the MultiGrid; in other words, compression can capture non-temporal structure as expected. Interestingly, the source and destination traces individually contain temporal structure (the source has lower complexity), a possible indication that operations proceed in rounds, where, e.g., a source node (CPU) first sends requests to other nodes and then receives answers asynchronously. When we look at the result for any of the source or destination traces, we see the non-temporal complexity is high (close to 1). Thus, the work seems to be uniformly divided among all CPUs. See also the marginal source and destination distributions in Figures 4(a) and (b). Takeaway 6: Characteristics of ML traces. The result in Figure 7(a) comes from a single trace, representing a machine learning task. Combining our complexity map in Figure 7(a) with the graphical representation of the trace timeline and the traffic matrix in Figures 1(a) and (c) gives a unique opportunity to see how the complexity map captures and quantifies the structure. Looking at the result for the pair trace in the complexity map, we see it has both temporal and non-temporal complexity at levels which are similar to HPC. This is mirrored in Figure 1(a), where the timeline clearly shows messages not perfectly interleaved, with some periods dominated by just a few communication pairs (each pair is represented by a different color). In (c), the traffic matrix confirms that traffic is indeed skewed, with some pairs more common than others, as shown by the different heights of the columns. When we consider both the source and destination traces, we see a pattern similar to HPC, i.e., higher non-temporal complexity. But unlike HPC, this complexity is less than 1, indicating that the sources and destinations are not uniformly distributed and do not take equal part in the calculation. Furthermore, both source and destination traces show more temporal complexity than the combined pair trace. This may hint at behavior where a single node takes prominence during a certain part of the trace and is responsible for most communications during this part. A possible example of this behavior is seen in Figure 1(a) where it is apparent that the green pair, while being the overall most frequent pair, is almost entirely confined to the first two thirds of the trace, thereby contributing to the temporal complexity.

Remarks
We conclude with two remarks on the analysis of synthetic traces and the loss of information because of the low-dimensional representation of the trace structure. Structure analysis and validation with synthetic traces. We also conduct an analysis of the pFabric synthetic traces. Figure 7(b) shows that the complexity of a pFabric trace also depends on the load (here, 10%, 50%, and 80% loads are shown): at lower loads, fewer flows are competing, so flows mix to a lesser extent, naturally resulting in a lower temporal complexity, as expected. By design, pFabric should have non-temporal complexity values very close to 1, because the source and destinations are chosen uniformly at random. The source and destination traces in the figure confirm this hypothesis. The temporal complexity of these traces follows the same rule as the pair traces with higher load level traces having higher temporal complexity, as expected. At its core, the pFabric simulation lacks any real non-local non-temporal structure that would appear on traces of any length, since eventually all events are equally likely. Loss of information. Clearly, any low-dimensional representation of high-dimensional data, as is the case for our complexity map, comes with an inherent information loss. In fact, it is easy to come up with two fairly different traces which map to the same location. Nevertheless, we believe the above observations show the potential of our approach in general, and the complexity map specifically, to highlight differences in the temporal and the non-temporal structure of traces. In particular, our results suggest that our approach could be used for the application of "fingerprinting", i.e., identifying applications by their trace complexity characteristics.
In the next sections, we further analyze our approach, showing that it can provide formal guarantees and also serve for traffic generation.

TRAFFIC GENERATION MODEL
One interesting implication of our methodology is that it naturally lends itself to synthetic traffic generators. Another is that it allows us to provide formal guarantees of the complexity of stochastic processes. In the following, we discuss each of these in turn.

The Complexity of Stationary Traces
Our methodology can provide a framework for formal analysis. In the following, we assume that σ is a trace generated by a stationary stochastic process [22]. Then, for long sequences and using an optimal compression algorithm (such as the Lempel-Ziv [81]), we will achieve the compression limit defined by Shannon [22,72,75]: the entropy rate of the process. From this, the normalized complexities of σ can be proved analytically.
Let Z = {Z i } be a stationary stochastic process that generates σ where Z i = {S i , D i } are timeindexed random variables, and S i ∈ S and D i ∈ D are a random source and a random destination at time i, respectively. Since Z is stationary, let π denote the stationary distribution and note that π is a joint distribution over S and D. With a slight abuse of notation, let S and D also denote the random variable of π . Note that S and D may be defined over different domains (IDs) and may be dependent. In addition, Z i may be dependent on a past elements in Z.
A basic measure for the complexity of Z is based on Shannon Entropy and is known as the entropy rate [22], H (Z). The entropy rate of a stochastic process captures the expected number of bits per symbol (i.e., source or destination IDs) that are both necessary and sufficient to describe σ ; or, alternatively, the expected amount of uncertainty in the next symbol given past symbols in the sequence. The smaller the entropy rate, the less complex the sequence (it requires fewer bits to describe/compress it).
We can use the previous definitions of normalized trace complexity of σ and formally relate them to entropy rates when σ is generated by a stationary stochastic process.
Theorem 1 (Normalized Trace Complexities of a Stationary Process). Consider an indexed stationary stochastic trace process Z = {Z t } to generate σ where Z t = {S t , D t } and n = |S ∪ D|. If an optimal compression algorithm C is used, then: (A) The normalized trace complexity of σ is where H (Z) is the entropy rate. (B) The normalized temporal complexity of σ is: where H (S, D) is the joint entropy of the joint stationary distribution π . (C) The normalized non-temporal complexity of σ is: Proof. The proof follows from the following observations: (A) By our construction, σ is a trace sampled from Z, and, therefore, the entropy rate of σ is H (Z) and C(σ ) = H (Z) . Let Z ′ be a maximum entropy random process where Z ′ i are i.i.d. and uniform; therefore, C(U(σ )) = H (Z ′ ). The entropy of any i.i.d. variable is the log of the number of elements; in our case there are n 2 possible pairs to sample from 2 . Therefore, H (Z ′ ) = log|Z ′ | = 2 log n. Finally we can see how the theorem follows directly: (B) Let Z ′′ be a stationary random process where Z ′′ i are i.i.d. and are distributed as π (i.e., like Z, but where the elements Z ′′ i are i.i.d.). Let H (S, D) be the joint entropy of the joint stationary distribution π . The entropy rate of Z ′′ will therefore be H (Z ′′ = H (S, D). In turn, it follows that the entropy rate of Γ(σ ) is also H (S, D), since in Γ(σ ), σ t become i.i.d. with the same stationary distribution as in σ .
(C) Follows from A and B.
Remark. Finally, we emphasize that while in our formal analysis of the model, we assume a stationary distribution, this assumption is sufficient but not necessary. In particular, it is also sufficient if traces are stationary for fixed time intervals. We also note that the possibility of nonstationary traces is another motivation for our compression methodology; our method can hence be applied even if non-stationary traces do not have a well-defined entropy rate.

From Analysis to Synthesis: A Traffic Generative Model
So far we have shown how our approach allows us to quantify and analyze structures in traffic traces. In this section, we initiate the study of models that will allow us to synthesize traffic traces in order to feature the desired temporal and non-temporal complexities. Given the limited amount of publicly available communication traces, such a model could be particularly useful to generate synthetic benchmarks, allowing researchers to compare their algorithms in different settings (e.g., for longer communication traces). Our proposed approach allows us to efficiently generate traces with formal guarantees on their expected complexity for any specific point on the complexity map. It is important to note that for each point on the map, there could be many traces (and models) whose complexity maps to this point. Our model provides one such solution.
We strive for simplicity, so we consider a Markovian model which is a stationary random process with a well-defined entropy rate [22]. The model has two components: temporal and non-temporal; these coincide with the two main types of complexity studied in this work. The non-temporal component is a joint probability traffic matrix, M, which can either be computed from a given trace σ , similar to Figure 1(c), or represent a known distribution (e.g. Zipf) where the entropy depends on the distribution's parameters. The temporal component is achieved by a repeating probability p which is essentially the probability of repeating the last request. To generate a trace, we start by sampling the first pair from M. Then at each step, we add a new pair to the trace: with probability p, we repeat the last pair and with probability 1 − p, we sample a new pair from M. Figure 8 shows a simple flow chart of this model. The Markov chain implied by this model has dim(M) states, where each state, (i, j), represents a possible source-destination pair. Note that there could be up to n 2 such pairs, but there may also be less, depending on the number of non-zero entries in M. The Markov process can be summarized using the following transition matrix P, where m i j ∈ M is the probability for the pair (i, j) in the joint probability M:

20:17
To give a more concise version, set x = (i, j), and y = (k, l) i.e., x and y are the set of indices in M, and x = y iff i = k, j = l. This results in a simpler version: We can now show that the stationary distribution of the model is M.
Claim 1 (Stationary distribution of the model). For any joint probability traffic matrix, M, and repeating probability 0 ≤ p ≤ 1, the stationary distribution of the model is π = M, and the entropy of the joint stationary distribution is H (S, D) = H (π ) = H (M).
Proof. For p < 1, the chain is clearly ergodic and aperiodic, so it has a unique stationary distribution s.t., π = πP. Following the transition matrix P defined in Equation (10), we can construct the set of linear equations which represent the stationary distribution of the model: x π x = 1 and π y = x π x P xy . These can be reduced in the following manner: Using the stationary distribution, we can also prove the entropy rate of the process. Proof. For a stationary Markov process, the entropy rate is H (Z 2 |Z 1 ) [22]. The result follows since for every initial state z 1 , the entropy of the next step is H (p, 1 − p) + pH (0) + (1 − p)H (M) by the entropy decomposition rule [22]. Now we can formally discuss the trace complexity of the model. Assume we want to generate a trace σ with expected normalized complexities that will appear on the complexity map on point (x, y). To do so, we create a traffic matrix M with joint entropy H (M) s.t. H (M) = y · 2 log n. As shown, M is the stationary distribution of the chain, and therefore, by Theorem 1, the non-temporal complexity of the model is:  where p can be computed analytically given a desired x. Figure 9 illustrates the quality of the above traffic generation model in producing synthetic traces for seven example points on the complexity map. First, we used the model to reproduce the four hypothetical points from Figure 2: uniform, skewed, bursty, and skewed & bursty. As a skewed distribution, we use the Zipf distribution with an exponent parameter of 2 3 which leads to a normalized entropy of 0.4 for a trace based on 16 IDs and 256 unique source-destination pairs. For the ML, MultiGrid, and WEB traces, we use their respective normalized accumulated traffic matrices as the joint probability matrix of each. For the corresponding p values, see Table 3. By applying the compression methodology to the synthetic traces generated using our model, we find our empirical traces are relatively close to the original trace files on the complexity map.
The discrepancy in the result possibly stems from the imperfection of real world compressors. While LZ should theoretically reach the entropy rate for infinite strings and windows of infinite length, our sequences and the memory for the sliding window are finite. Furthermore, real world compressors make certain optimizations to reduce runtime at the cost of a worse compression ratio. Nevertheless, when comparing two traces using the same compression method, as we do here, we obtain a good indication of the differences in structure, even if the compressor is not optimal. Moreover, with fine tuning, we can change the parameter setting of the model so that the resulting complexity of the syntactic trace will be identical to the complexity of the original trace. We have not done this in our example so that we can show the imperfection of the compression method. It is interesting to note that the HPC trace seems to stand out as an outlier in Figure 9: it is the only one for which the non-temporal complexity decreases (slightly). But a similar phenomenon appears for the bursty and the uniform traces. The compression algorithm works well under uniform non-temporal distributions, even if they are sparse. The low non-temporal complexity of the HPC trace is a result of the trace being sparse and close to uniform among the participating pairs, as we observe in Figure 4 (b), and not from its being skewed. We conjecture that in this case, it is "easier" for the compression algorithm to work well and for the model to capture better the original trace.

FROM STRUCTURE TO OPTIMIZATION: A CASE STUDY
Metrics to measure the various structures of traffic traces are not only of theoretical interest; they also have implications for network optimization, in that a a traffic trace with much structure indicates a high potential for traffic-aware optimizations. In this section, we provide an example to substantiate our earlier claim that "structure calls for optimization". Specifically, we show that traces (or applications) with lower complexity can potentially gain from a clever network design. Because of space constraints, we will skip many technical details and focus on the main intuition.
Our case study is situated in the context of emerging reconfigurable optical networks: networks whose topologies can be adjusted to meet the demand they serve [8,9,21,34,39,41,42,64,80]. We refer to such networks as self-adjusting networks. For our discussion, we consider a recent self-adjusting network, SASL 2 [11,12]. SASL 2 comes with theoretical guarantees which allow us to tie it to the complexity map and to our generative model. That said, we note that similar claims could also be made for other network proposals, e.g., SplayNets [64].
SASL 2 adaptively reconfigures a datacenter topology to minimize routing costs: the path length between pairwise communicating partners in the trace σ . The algorithm makes a tradeoff between the benefits and costs of reconfigurations. In particular, because of the different time scales of packet transmission and reconfiguration, a network can only be changed after having served a request.
As [12] show, when SASL 2 is used, the expected cost of routing a communication request σ t from a source s t to a destination d t is proportional to the size of the working set of the request, at the time of the request, denoted as W S(σ t ). The working set is a well-known measure of the cost and efficiency of data structures (e.g., binary search trees and skip lists). Informally it tries to capture the number of recent "active" elements in the system. More formally, for a sequence of singleton items x 1 , x 2 , . . . x m , the working set of an item x at time t, W S(x t ) is the number of distinct items requested since the last request to x prior to time t, including x. For pairwise requests, as in a trace σ , the definition is a bit more involved, but if we consider σ to be a sequence s 1 , d 1 , s 2 , d 2 , . . . the working set is well defined for each x t . A data structure has the working set property if its total cost to serve m items is of the order of m t =1 logW S(x t ). It is known that the working set property implies the entropy bound, known also as static optimality [31]; i.e., m t =1 logW S(x t ) = O(mH (X )) where H (X ) is the empirical entropy of the sequence.
Using the above results we can bound the cost of SASL 2 (and similar networks) on a sequence generated by the generative model described in § 4.2.
Claim 3. For any joint probability traffic matrix, M, and repeating probability 0 ≤ p ≤ 1, the expected amortized cost of SASL 2 on a sequence generated by the model in §4.2 is O(p + (1 − p)H (Z )), whereZ is a random variable over the n possible source or destination IDs and with frequencies implied by M.
Proof overview. From [12] we have that SASL 2 has the working set property for σ . From the model, we can conclude that the expected total working set bound will be mp (number of times repeating the last request) plus the working set cost, but limited to the case of sampling a request from M. The latter, in turn, can be shown to be bounded by m(1 − p)H (Z ) using [31].
Consequently, we can state the following:
Corollary 1. The normalized complexity of a trace σ generated by our model captures the ratio of performance improvement in expected route length, to a uniform trace, U(σ ), and to the performance of a demand-oblivious network design on the same trace.
To elaborate: from Theorem 1 and Claim 2 it follows that the complexity of σ will converge to H (p,1−p)+(1−p)H (M ) 2 log n . But this ratio is proportional to the ratio of the amortized costs (i.e., expected path length) of σ to the amortized cost of the uniform trace U(σ ) which is: Note that a uniform trace can also be generated by the model with p = 0 and a uniform matrix M, leading to an expected path length of log n. Interestingly, if we consider any static, bounded degree and demand-oblivious network N , such as Xpander [48] or fat-tree [2], for example, then the average path length on that network N for any σ will be Ω(log n). This means that the improvement ratio of executing σ on SASL 2 to N (which is static and oblivious) will also be proportional to the complexity of σ .
The above corollary provides a strong indication that complexity captures important aspects of the trace structure, and in turn, those aspects can be explored to improve performance.
The example raises many interesting questions. Which types of optimizations and algorithms should we use, given the complexity of a trace? Can certain algorithms work well for initially unknown complexity? We believe the complexity map could ,help answer these questions, as it a partition the complexity spectrum into regions indicating the best algorithms. For example, if we consider the above example of path lengths, we can initially partition the map as shown in Figure 10 where some (extreme) areas are suspected to be optimal for certain algorithms. But the majority of the map deals with bursty & skewed traces, and for these traces, it remains an open question which algorithms are optimal and where. We leave the theoretical and empirical study of these questions for future work.
On the Complexity of Traffic Traces and Implications 20:21

REFINED TYPES OF TRACE COMPLEXITIES
While we focus on temporal and non-temporal complexities in this paper, our method can easily be refined for other sub-types of complexity. For example, we can subdivide the non-temporal complexity into three natural categories: neighborhood complexity, directional complexity, and frequency complexity. See Figure 11. This division adds dimensions to the trace complexity, allowing us to better understand the structure and to differentiate between traces. As mentioned earlier, two traces can have the same temporal and non-temporal complexity. The new complexities may help us distinguish between them.
We begin by introducing two random transformations.
(1) Column transformation, ∆(σ ): This transformation performs a uniformly random shuffle of the destinations in σ , eliminating any dependency between the sources and the destinations (without loss of generality, the transformation can be performed on sources only). (2) Pairs transformation, Λ(σ ): This transformation performs a uniformly random shuffle of each (source, destination) pair in σ independently eliminating any dependency between elements' IDs and their role as sources or destination. Using the above transformations, we can formally define the new complexities. It is important to note that the transformations we defined can be applied to a trace σ in different a order, resulting in different complexities. The order we choose follows a natural order that systematically destroys structure and increases complexity, starting at the original trace σ and ending at the structure-less U(σ ). First, we use the temporal transformation to remove temporal structure. Next, we use the column transformation to remove source-destination dependency. Then, we use pairs transformation to destroy roles (source or destination) of nodes. Last, we use the uniform transformation to reach U(σ ). An example of this order including ∆(σ ) and Λ(σ ) is shown in Table 1. We define our complexities according to this order. Definition 4 (Neighborhood, Directional, and Freqency Trace Complexities Ratios). Let σ be a traffic trace whose entries are of the form σ i = (s i , d i ) . We define: (1) The normalized neighborhood trace complexity of σ as: .
This captures the complexity that results from the dependency between sources and destinations. For example, a given source could have a strong dependency on which set of destinations it communicates with. The column transformation eliminates this dependency. (2) The normalized directional trace complexity of σ is: .
This captures the complexity resulting from the role of elements as sources or destinations. For example the sets of sources and destinations can be of a different size and, in an extreme example disjoint. The pair transformation eliminates this structure. (3) The normalized frequency trace complexity of σ is: This captures the complexity that results from the frequency distribution of elements in the sequence. For example, several elements (sources or destinations) can be much more popular than others. The uniform transformation eliminates this property and ensures a uniform distribution of elements. Each of the above measures captures a different property of the trace, and provides us with universal measures that allow us to compare different traces on the same scale. The choice of which type of complexity to use depends on the use case.
We can also extend Observation 1 and claim: Observation 2. The trace complexity of σ is the multiplication of the temporal and non-temporal complexities, and the non-temporal complexity is the multiplication of the neighborhood, the directional, and the frequency complexities. Formally, We can also extend Theorem 1 and prove: Theorem 2 (Normalized Trace Complexities of a Stationary Process). Consider an indexed stationary stochastic trace process Z = {Z t } to generate σ , where Z t = {S t , D t } and n = |S ∪ D|. If an optimal compression algorithm C is used, then: (A) The normalized neighborhood complexity of σ is: .

RELATED WORK
The study of traffic patterns and the design of models is a popular topic, with high relevance in the networking literature, as it has important implications, e.g., on network planning and provisioning. For example, it has been shown that the best design choice for a datacenter network architecture (in terms of cost/benefit tradeoff) depends on the communication pattern between end hosts [59], but lacking concrete data, researchers often resort to designing networks for the worst case, i.e., an all-to-all traffic matrix [2] which can be overkill when demand exhibits significant locality [27,39].
A well-known example in the literature where measurement studies spurred much research into traffic modeling dates back to the 1990s, when researchers found that, in strong contrast to traditional models relying on Poisson assumptions [50], traffic in local-area and wide-area networks is "self-similar" in that it exhibits variability on a wide range of scales [25,50,53]. Motivated by these results, researchers developed a number of models [58], e.g., related to the heavy-tailed distribution of transferred file sizes, properties of the transport/network layer in the protocol stack, ON/OFF traffic models such as [68], etc. Much modeling research also went into generating disk I/O traces often described by mixing sequential and random accesses [66], More systematically, works on network traffic modeling includes temporal statistical models such as AutoRegressive Integrated Moving Average (ARIMA) [38], Multifractal Wavelets [61], and b-model [74],which are used to describe temporal burstiness. Spatial statistics models for "smooth traffic" often rely on (multivariate) Gaussian distributions [24] and marked point processes [23] are used to model events in time and space.
It is interesting to put our work into the context of this previous work. Like others before us we are studying the temporal structure of traces. But there are several key differences. First, we focus on the source-destination structure/complexity of the traces, not on the accumulative traffic load as in previous models. This leads to an additional dimension in the trace and to new observations. Second, we use the entropy and the entropy rate as the main metrics to quantify the structure. Although not explicitly mentioned, some of the above models can be characterized by their entropy. For example, the self-similar traffic models, e.g., ARIMA, are known to be captured well by their entropy rate [22]. In particular the only source of uncertainty stems from the noise, and the entropy depends on the variance of the Gaussian process. In future work, we plan to add load or packet (flow) size information to the trace; it will also be useful to incorporate some of the above methods, including spectral analysis.
Physical models aim to simulate user behavior; a classic example is the ON/OFF model [15] in web traffic generators where the user's thinking time follows a heavy-tailed distribution. Some interesting work in this area proposes to model multiple dimensions simultaneously, e.g., the spatio-temporal behavior [73].
Motivated by the high potential utility of a traffic matrix for network capacity planning and management, many researchers have studied how to measure and estimate the traffic matrix [56]. A well-known and simple model is the gravity model- [60,62] which assumes the amount of traffic between two nodes is proportional (only) to the product of the total traffic entering or leaving the two nodes. In their interesting work, Zhang et al. [79] show that link load measurements can be used to quickly and accurately infer traffic matrices in IP networks, by enhancing the gravity model (which is guaranteed to be consistent with measured link loads at the network edge but not the interior links) with tomographic methods [20,71]. Tomographic methods have also been applied to the detection of network-level anomalies, e.g., based on Fourier transform and Principal Component Analysis models [78]. However, most of these models revolve around (static) "snapshots" of the communication pattern and do not provide many insights into the evolution over time. We are more interested in the granularity of traffic traces than entire traffic matrices.
In this paper, we are particularly interested in the traffic matrices from in datacenters and their evolution over time. The presence of such structures and models can give important insights into the usefulness of recent reconfigurable networking technologies, e.g., malleable datacenter topologies [12, 13, 21, 34, 36, 39, 41-43, 54, 67, 80] (cf. the recent survey [37]). Underlying all these technologies is the hope of being able to leverage "structure" in demand patterns and, by adapting the network over time accordingly, realizing cheaper and more efficient datacenter networks. In this context, Avin et al. recently established a connection between demand-aware network designs and information theory, showing that achievable routing performance relies on the (conditional) entropy of the demand [9,10,14,64].
Unfortunately, few empirical studies report on traffic patterns in datacenters, and the data available to the research community is severely limited. Many studies rely on simulations [3] or testbeds [32]. The exceptions are often limited to workload traces from a single, large datacenter [16,46], dominated by Web search related traffic. Existing empirical studies, however, all confirm that traffic patterns in datacenters have "low entropy": they feature much (spatial and temporal) locality, i.e., are sparse and skewed [4,39,44,63].
More specifically, empirical studies of datacenter networks show that much traffic is racklocal [16,27], demand is frequently concentrated and bursty [16][17][18]27], packets have bimodal sizes, traffic features ON/OFF behavior [16], and there is a small number of large flows [4]. Some of these properties were recently revisited a large empirical study in Facebook's datacenters [63]: the authors find that their datacenters provide a richer picture. Their traffic is neither rack-local nor all-to-all, demand is wide-spread, uniform, and stable, with rapidly changing, internally bursty heavy hitters, packets are typically small (outside of Hadoop), arrivals are continuous, and there are many concurrent flows.
Finally, we are not the first to use adaptive data compression for complexity analysis, and similar methodologies have been proposed elsewhere, e.g., for email [19] or comment [47] spam filtering, or to estimate neural discharges [7]. Entropy rates [49] have also been investigated intensively in the literature, e.g., for feature selection in machine learning [30]. However, to the best of our knowledge, such approaches have not been considered in the context of network traffic characterization.

CONCLUSION AND DISCUSSION
While many research efforts focus on leveraging the structure of packet traces to design more efficient datacenter networks, the community currently lacks a formal understanding of the amount and types of structures available in traffic traces. This paper takes the first steps towards developing a formal framework and metrics to systematically quantify temporal and non-temporal structures in datacenter workloads.
Indeed, practitioners are often unaware of their application traffic behavior. The sheer volume of traffic, as well as the amount of storage required to store the trace files, hinders datacenter providers to keep detailed profiles of their traffic. Our approach can enable datacenter providers to use trace complexity as a tool to maintain a profile of various applications and plan for datacenter resources accordingly. For instance a typical datacenter switch has 128 ports each port with 100 Gbps. Such a switch will generate 12.8 Tbps data. Collecting this traffic for even 5 minutes puts much pressure on the CPU and can overload the storage servers (5 min of 12.8 Tbps traffic yields 3.8 Pb). As a result, traffic monitoring is almost always off and providers are unaware of the trace complexity of applications.
Clearly, low-dimensional representations of the trace structure such as a 2-dimensional complexity map, inevitably comes with a loss of information, and many different traces end up on the same location in the space. However, these dimensions can be sufficient to capture the essential part of the trace. For example, the non-temporal complexity, i.e., the conditional entropy, of a packet trace, is sufficient to describe accurately the achievable route lengths in a static constant-degree demand-aware networks [9]. It is hence the "right metric" for this application and other aspects of the trace are irrelevant.
That said, a nice feature of our approach is that it can be seen as a framework: we can account for additional dimensions, such as packet arrival times or packet sizes, by systematically using randomization to eliminate structure along these dimensions as well. And indeed, identifying and incorporating such additional dimensions constitutes an interesting avenue for future research. At the same time, as discussed above, adding more dimensions indiscriminately should be avoided: the challenge when applying our framework is not to maximize the number of dimensions but to find a small number of "most valuable dimensions", ie., the dimensions which capture the essential part of the traces for a specific application.
For example, recall again the demand-aware network application discussed above: all traces featuring the same non-temporal complexity (i.e., entropy), no matter how different they are, result in exactly the same expected route lengths (up to constant factors and under sparse demands [9]) in bounded-degree, demand-aware networks. Hence this simple metric is sufficient to accurately characterize what can and cannot be achieved in demand-aware network topologies. Our approach of iteratively randomizing and compressing traces raises the question of the optimal order in which structure is removed. More generally, it will be interesting to explore to what extent our proposed traffic generation model can be used to benchmark future scheduling, congestion control, and reconfigurable datacenter proposals. We also note that while the focus in our paper was on the complexity of traffic traces arising communication networks, our approach is more general and may find interesting applications in other dynamic contexts as well.
To facilitate future research and ensure reproducibility of our results, we made our traces and model publicly available at trace-collection.net. Table 3. The value of p (repetition probability) used in the traces in Figure 9 generated by the models.