Daren B. H. Cline

Since inception, DNS has used a TTL-based replication scheme that allows the source (i.e., an authoritative domain server) to control the frequency of record eviction from client caches. Existing studies of DNS predominantly focus on reducing query latency and source bandwidth, both of which are optimized by increasing the cache hit rate. However, this causes less-frequent contacts with the source and results in higher staleness of retrieved records. Given high data-churn rates at certain providers (e.g., dynamic DNS, CDNs) and importance of consistency to their clients, we propose that cache models include the probability of freshness as an integral performance measure. We derive this metric under general update/download processes and present a novel framework for measuring its value using remote observation (i.e., without access to the source or the cache). Besides freshness, our methods can estimate the inter-update distribution of DNS records, cache hit rate, distribution of TTL, and query arrival rate from other clients. Furthermore, these algorithms do not require any changes to the existing infrastructure/protocols.

In this paper, we propose a multilayer inhomogeneous random graph model (MIRG), whose layers may consist of both single-edge and multi-edge graphs. In the single layer case, it has been shown that the regular variation of the weight distribution underlying the inhomogeneous random graph implies the regular variation of the typical degree distribution. We extend this correspondence to the multilayer case by showing that the multivariate regular variation of the weight distribution implies the multivariate regular variation of the asymptotic degree distribution. Furthermore, in certain circumstances, the extremal dependence structure present in the weight distribution will be adopted by the asymptotic degree distribution. By considering the asymptotic degree distribution, a wider class of Chung-Lu and Norros-Reittu graphs may be incorporated into the MIRG layers. Additionally, we prove consistency of the Hill estimator when applied to degrees of the MIRG that have a tail index greater than 1. Simulation results indicate that, in practice, hidden regular variation may be consistently detected from an observed MIRG.

Recent work in OS fingerprinting has focused on overcoming random distortion in network and user features during Internet-scale SYN scans. These classification techniques work under an assumption that all parameters of the profiled network are known a-priori - the likelihood of packet loss, the popularity of each OS, the distribution of network delay, and the probability of user modification to each default TCP/IP header value. However, it is currently unclear how to obtain realistic versions of these parameters for the public Internet and/or customize them to a particular network being analyzed. To address this issue, we derive a non-parametric Expectation-Maximization (EM) estimator, which we call Faulds, for the unknown distributions involved in single-probe OS fingerprinting and demonstrate its significantly higher robustness to noise compared to methods in prior work. We apply Faulds to a new scan of 67M webservers and discuss its findings.

In the age of big data, many graph algorithms are now required to operate in external memory and deliver performance that does not significantly degrade with the scale of the problem. One particular area that frequently deals with graphs larger than RAM is triangle listing, where the algorithms must carefully piece together edges from multiple partitions to detect cycles. In recent literature, two competing proposals (i.e., Pagh and PCF) have emerged; however, neither one is universally better than the other. Since little is known about the I/O cost of PCF or how these methods compare to each other, we undertake an investigation into the properties of these algorithms, model their I/O cost, understand their shortcomings, and shed light on the conditions under which each method defeats the other. This insight leads us to develop a novel framework we call Trigon that surpasses the I/O performance of both previous techniques in all graphs and under all RAM conditions.

Network applications commonly maintain local copies of remote data sources in order to provide caching, indexing, and data-mining services to their clients. Modeling performance of these systems and predicting future updates usually requires knowledge of the inter-update distribution at the source, which can only be estimated through blind sampling - periodic downloads and comparison against previous copies. In this paper, we first introduce a stochastic modeling framework for this problem, where the update and sampling processes are both renewal. We then show that all previous approaches are biased unless the observation rate tends to infinity or the update process is Poisson. To overcome these issues, we propose four new algorithms that achieve various levels of consistency, which depend on the amount of temporal information revealed by the source and capabilities of the download process.

Suppose that {X t } is a Markov chain such as the state space model for a threshold GARCH time series. The regularity assumptions for a drift condition approach to establishing the ergodicity of {X t } typically are ϕ-irreducibility, aperiodicity, and a minorization condition for compact sets. These can be very tedious to verify due to the discontinuous and singular nature of the Markov transition probabilities. We first demonstrate that, for Feller chains, the problem can at least be simplified to focusing on whether the process can reach some neighborhood that satisfies the minorization condition. The results are valid not just for the transition kernels of Markov chains but also for bounded positive kernels, opening the possibility for new ergodic results. More significantly, we show that threshold GARCH time series and related models of interest can often be embedded into Feller chains, allowing us to apply the conclusions above.

Suppose that {X_t} is a Markov chain such as the state space model for a threshold GARCH time series. The regularity assumptions for a drift condition approach to establishing the ergodicity of {X_t} typically are ϕ-irreducibility, aperiodicity, and a minorization condition for compact sets. These can be very tedious to verify due to the discontinuous and singular nature of the Markov transition probabilities. We first demonstrate that, for Feller chains, the problem can at least be simplified to focusing on whether the process can reach some neighborhood that satisfies the minorization condition. The results are valid not just for the transition kernels of Markov chains but also for bounded positive kernels, opening the possibility for new ergodic results. More significantly, we show that threshold GARCH time series and related models of interest can often be embedded into Feller chains, allowing us to apply the conclusions above.

To achieve adequate flow and homogeneous concrete for precast, prestressed members, self-consolidating concrete (SCC) typically has higher paste and lower coarse aggregate volumes than conventional concrete (CC). The lower aggregate content of SCC can affect the shear capacity of concrete systems. This research performed 48 push-off tests to investigate the influence of SCC aggregate and paste volumes on the shear capacity and these results were compared with those obtained from similar CC samples. The variables included coarse aggregate type (river gravel and limestone), three coarse aggregate volumes for the SCC mixtures, and two target 16-h release strengths [34 and 48 MPa (5 and 7 ksi)]. The aggregate type, aggregate volume, and concrete strength were found to have significant effects on the aggregate interlock. Test results were used to propose new aggregate interlock models based on the modified compression field theory adopted in the AASHTO Load and Resistance Factor Design Specifications. More app...

We characterize the Lyapunov exponent and ergodicity of nonlinear stochastic recursion models, including nonlinear AR-GARCH models, in terms of an easily defined, uniformly ergodic process. Properties of this latter process, known as the collapsed process, also determine the existence of moments for the stochastic recursion when it is stationary. As a result, both the stability of a given model and the existence of its moments may be evaluated with relative ease. The method of proof involves piggybacking a Foster-Lyapunov drift condition on certain characteristic behavior of the collapsed process.