Recent growth of the Internet in both scale and complexity has imposed a number of difficult challenges on existing measurement techniques and approaches, which are essential for both network management and many ongoing research projects. For any measurement algorithm, achieving both accuracy and scalability is very challenging given hard resource constraints (e.g., bandwidth, delay, physical memory, and CPU speed). My dissertation research tackles this problem by first proposing a novel mechanism called residual sampling, which intentionally introduces a predetermined amount of bias into the measurement process. We show that such biased sampling can be extremely scalable; moreover, we develop residual estimation algorithms that can unbiasedly recover the original information from the sampled data. Utilizing these results, we further develop two versions of the residual sampling mechanism: a continuous version for characterizing the user lifetime distribution in large-scale peer-to-peer networks and a discrete version for monitoring flow statistics (including per-flow counts and the flow size distribution) in high-speed Internet routers. For the former application in P2P networks, this work presents two methods: ResIDual-based Estimator (RIDE), which takes single-point snapshots of the system and assumes systems with stationary arrivals, and Uniform RIDE (U-RIDE), which takes multiple snapshots and adapts to systems with arbitrary (including non-stationary) arrival processes. For the latter application in traffic monitoring, we introduce Discrete RIDE (D-RIDE), which allows one to sample each flow with a geometric random variable. Our numerous simulations and experiments with P2P networks and real Internet traces confirm that these algorithms are able to make accurate estimation about the monitored metrics and simultaneously meet the requirements of hard resource constraints. These results show that residual sampling indeed provides an ideal solution to balancing between accuracy and scalability.

Geophysical research has long been interdisciplinary, with many phenomena on the Earth's surface involving multiple, linked processes that are best understood using a combination of techniques. This is particularly true in the case of grain flows on sand dunes, in which the sedimentary stratification with which geologists are concerned arises from the granular processes investigated by physicists and engineers, and the water permeation that interests hydrologists and soil scientists determines the seismic velocities of concern to exploration geophysicists. In this dissertation, I describe four projects conducted for the degree of Doctor of Philosophy, using a combination of laboratory experimentation, fieldwork, numerical simulation, and mathematical modelling to link avalanching on dunes to its effects on stratification, on the permeation of water, and on seismic surveys. Firstly, I describe experiments on erodible, unbounded, grain piles in a channel, slowly supplied with additional grains, and I demonstrate that the behaviour of the consequent, discrete avalanches alternates between two regimes, typified by their size statistics. Reconciling the `self-organised criticality' that several authors have predicted for such a system with the hysteretic behaviour that others have observed, the system exhibits quasi-periodic, system-spanning avalanches in one regime, while in the other avalanches pass at irregular intervals and have a power-law size distribution. Secondly, I link this power-law size distribution to the strata emplaced by avalanches on bounded grain piles. A low inflow rate of grains into an experimental channel develops a pile, composed of strata in which blue-dyed, coarser grains overlie finer grains. Associating stopped avalanche fronts with the `trapped kinks' described by previous authors, I show that, in sufficiently large grain piles, mean stratum width increases linearly with distance downslope. This implies the possibility of interpreting paleodune height from the strata of aeolian sandstones, and makes predictions for the structure of avalanche-associated strata within active dunes. Thirdly, I discuss investigations of these strata within active, Qatari barchan dunes, using dye-infiltration to image strata in the field and extracting samples across individual strata with sub-centimetre resolution. Downslope increases in mean stratum width are evident, while measurements of particle size distributions demonstrate preferential permeation of water along substrata composed of finer particles, explaining the strata-associated, localised regions of high water content discovered by other work on the same dunes. Finally, I consider the effect of these within-dune variations in water content on seismic surveys for oil and gas. Having used high performance computing to simulate elastic wave propagation in the vicinity of an isolated, barchan sand dune, I demonstrate that such a dune acts as a resonator, absorbing energy from Rayleigh waves and reemitting it over an extensive period of time. I derive and validate a mathematical framework that uses bulk properties of the dune to predict quantitative properties of the emitted waves, and I demonstrate the importance of internal variations in seismic velocity, resulting from variations in water content.