Understanding how media rhetoric shapes audience engagement is crucial in the attention economy. This study examines how moral-emotional framing by mainstream news channels on YouTube influences user behavior across Korea and the United States. To capture the platform's multimodal nature, combining thumbnail images and video titles, we develop a multimodal moral emotion classifier by fine-tuning a vision–language model. The model is trained on human-annotated multimodal datasets in both languages and applied to approximately 400,000 videos from major news outlets. We analyze three engagement levels (views, likes, and comments), representing increasing degrees of commitment. The results show that other-condemning rhetoric—expressions of moral outrage that criticize others' morality—consistently increases all forms of engagement across cultures, with effect sizes strengthening from passive viewing to active commenting. These findings suggest that moral outrage is a particularly effective emotional strategy, attracting not only attention but also active participation. We discuss concerns about the potential misuse of other-condemning rhetoric, as such practices may deepen polarization by reinforcing in-group/out-group divisions. To facilitate future research and ensure reproducibility, we publicly release our Korean and English multimodal moral emotion classifiers.

How fast and efficiently page faults are handled determines the performance of paging-based memory disaggregation (MD) systems. Recent MD systems employ busy-waiting in page fault handling to avoid costly interrupt handling and context switching. Upon a page fault, they issue a remote fetch request and busy-wait for the completion of the request rather than yield their execution to other tasks. While these attempts succeed to cut the latency of MD systems to microseconds, they suffer from head-of-line (HOL) blocking that leads to high tail latency and causes RDMA network underutilization.

The growth in host resource and network speed is not synchronized, and the status quo of this imbalance from the network speed of 100 ∼ Gbps makes the host resource the bottleneck. We categorize existing body of work to reduce the host burden into the following three approaches: (1) to eliminate payload copy (zero-copy), (2) to utilize special-purpose hardware for payload copy, and (3) to offload protocol to NIC. Each approach, however, has drawbacks. (1) Most zero-copy methods require application modification. Furthermore, the application must ensure its buffer is not modified until network I/O is complete. (2) Copy elimination through special-purpose hardware still uses host memory, consuming considerable memory bandwidth. (3) The protocol offloaded to NIC has limited flexibility.

Memory disaggregation has replaced the landscape of dat-acenters by physically separating compute and memory nodes, achieving improved utilization. As early efforts, kernel paging-based approaches offer transparent virtual memory abstraction for remote memory with paging schemes but suffer from expensive page fault handling. This paper revisits the paging-based approaches and challenges their performance in paging schemes. We posit that the overhead of the paging-based approaches is not a fundamental limitation. We propose DiLOS, a new library operating system (LibOS) specialized for paging-based memory disaggregation. We have revamped the page fault handler to get away with the swap cache and incorporated known techniques in our prefetcher, page manager, and communication module for performance optimization. Furthermore, we provide APIs to augment the LibOS with application semantics. We present two app-aware guides, app-aware prefetching and bandwidth-reducing memory allocator in DiLOS. Through extensive evaluation of microbenchmarks and applications, we demonstrate that DiLOS outperforms the state-of-the-art kernel paging-based system (Fastswap) up to 2.24× and a recent user-level system (AIFM) 1.54× on a real-world data analytic workload.

Memory disaggregation is a new datacenter paradigm separating compute and memory nodes. While memory disaggregation improves memory utilization and scalability, it poses challenges for cloud applications, particularly in terms of high tail latency. Existing memory disaggregation systems focus on optimizing the disaggregation stack, but it does not always guarantee excellent application performance. We review existing memory disaggregation and tail-optimized systems and explain their limitations in this context. We also propose two preliminary solutions: asynchronous page fault handling and a faulty request classifier. The emulation result shows that asynchronous page fault handling reduces tail latencies by 50% compared to synchronous handling.

Intrusive data structures (IDSes) are heavily used in system programming, where achieving high performance is one of the most important design goals. Yet, they are not supported in today's ownership type system that offer memory-safety without garbage collection. Instead, IDSes force programmers to choose either unsafety or runtime overhead. This limitation stems from the implicit assumptions pertaining to the memory layouts and access patterns created by IDSes.

Since the advent of datacenter networking, achieving low latency within the network has been a primary goal. Many congestion control schemes have been proposed in recent years to meet the datacenters' unique performance requirement. The nature of congestion feedback largely governs the behavior of congestion control. In datacenter networks, where round trip times are in hundreds of microseconds, accurate feedback is crucial to achieve both high utilization and low queueing delay. Proposals for datacenter congestion control predominantly leverage explicit congestion notification (ECN) or even explicit in-network feedback to minimize the queuing delay. In this paper, we explore latency-based feedback as an alternative and show its advantages over ECN. Against the common belief that such implicit feedback is noisy and inaccurate, we demonstrate that latency-based implicit feedback is accurate enough to signal a single packet's queuing delay in 10 Gb/s networks. Such high accuracy enables us to design a new congestion control algorithm, DX, that performs fine-grained control to adjust the congestion window just enough to achieve very low queuing delay while attaining full utilization. Our extensive evaluation shows that: 1) the latency measurement accurately reflects the one-way queuing delay in single packet level; 2) the latency feedback can be used to perform practical and fine-grained congestion control in high-speed datacenter networks; and 3) DX outperforms DCTCP with 5.33 times smaller median queueing delay at 1 Gb/s and 1.57 times at 10 Gb/s.

We present the NBA framework, which extends the architecture of the Click modular router to exploit modern hardware, adapts to different hardware configurations, and reaches close to their maximum performance without manual optimization. NBA takes advantages of existing performance-excavating solutions such as batch processing, NUMA-aware memory management, and receive-side scaling with multi-queue network cards. Its abstraction resembles Click but also hides the details of architecture-specific optimization, batch processing that handles the path diversity of individual packets, CPU/GPU load balancing, and complex hardware resource mappings due to multi-core CPUs and multi-queue network cards. We have implemented four sample applications: an IPv4 and an IPv6 router, an IPsec encryption gateway, and an intrusion detection system (IDS) with Aho-Corasik and regular expression matching. The IPv4/IPv6 router performance reaches the line rate on a commodity 80 Gbps machine, and the performances of the IPsec gateway and the IDS reaches above 30 Gbps. We also show that our adaptive CPU/GPU load balancer reaches near-optimal throughput in various combinations of sample applications and traffic conditions.

We present the KENSv2 (KAIST Educational Network System) framework for network protocol implementation. The framework is event-driven to guarantee deterministic behaviour and reproducibility, which in turn delivers ease of debugging and evaluation. Our framework consists of four components: the event generator, the virtual host, the TCP driver and the IP driver. The two drivers are what students have to implement, and we offer to the students the drivers in the binary format for paired testing and debugging. We have developed a test suite that covers three categories of test cases: specification, paired, and logic tests. The framework logs packet transmissions in the PCAP format to allow use of widely available packet analysis tools to inspect logical behaviour of student solutions, such as congestion control. We have designed five step-by-step assignments and evaluated student submissions. With our automated test suite, we have cut down the number of TAs by half for the doubled class size compared to the previous semester, in total 3 TAs with 49 students. We plan to continue using KENSv2 in our undergraduate networking course and expand the test suite.

No abstract available.

In this paper, we study the process of information diffusion in a microblog service developing Galton-Watson with Killing (GWK) model. Microblog services offer a unique approach to online information sharing allowing microblog users to forward messages to others. We describe an information propagation as a discrete GWK process based on Galton-Watson model which models the evolution of family names. Our model explains the interaction between the topology of the social graph and the intrinsic interest of the message. We validate our model on dataset collected from Sina Weibo and Twitter microblog. Sina Weibo is a Chinese microblog web service which reached over 100 million users as for January 2011. Our Sina Weibo dataset contains over 261 thousand tweets which have retweets and 2 million retweets from 500 thousand users. Twitter dataset contains over 1.1 million tweets which have retweets and 3.3 million retweets from 4.3 million users. The results of the validation show that our proposed GWK model fits the information diffusion of microblog service very well in terms of the number of message receivers. We show that our model can be used in generating tweets load and also analyze the relationships between parameters of our model and popularity of the diffused information. To the best of our knowledge, this paper is the first to give a systemic and comprehensive analysis for the information diffusion on microblog services, to be used in tweets-like load generators while still guaranteeing popularity distribution characteristics.

With the rapid growth of data centers, minimizing the queueing delay at network switches has been one of the key challenges. In this work, we analyze the shortcomings of the current TCP algorithm when used in data center networks, and we propose to use latency-based congestion detection and rate-based transfer to achieve ultra-low queueing delay in data centers.

We analyze the dynamics of the behavior known as 'unfollow' in Twitter. We collected daily snapshots of the online relationships of 1.2 million Korean-speaking users for 51 days as well as all of their tweets. We found that Twitter users frequently unfollow. We then discover the major factors, including the reciprocity of the relationships, the duration of a relationship, the followees' informativeness, and the overlap of the relationships, which affect the decision to unfollow. We conduct interview with 22 Korean respondents to supplement the quantitative results.

Many measurement systems have been proposed in recent years to shed light on the internal performance of the Internet. Their common goal is to allow distributed applications to improve end-user experience. A common hurdle they face is the need to deploy yet another measurement infrastructure. In this work, we demonstrate that without any new measurement infrastructure or active probing we obtain composite performance estimates from AS-by-AS segments and the estimates are as good as (or even better than) those from existing estimation methodologies that use on-demand, customized active probing. The main contribution of this paper is an estimation algorithm that breaks down measurement data into segments, identifies relevant segments efficiently, and, by carefully stitching segments together, produces delay and path estimates between any two end points. Fittingly, we call our algorithm path stitching. Our results show remarkably good accuracy: error in delay is below 20 ms in 80% of end-to-end paths.

Commodity-hardware technology has advanced in great leaps in terms of CPU, memory, and I/O bus speeds. Benefiting from the hardware innovation, recent software routers on commodity PC now report about 10 Gbps in packet routing. In this paper we map out expected hurdles and projected speed-ups to reach 100 Gbps in packet routing on a single commodity PC. With careful measurements, we identify two notable bottlenecks for our goal: CPU cycles and I/O bandwidth. For the former, we propose reducing per-packet processing overhead with software-level optimizations and buying extra computing power with GPUs. To improve the I/O bandwidth, we suggest scaling the performance of I/O hubs that limits packet routing speed to well before 50 Gbps.

Measurement-based research benefits greatly from efficient and minimum-effort management of large-scale data and their metadata. Effective data management has become a key in promoting data sharing within our community. During the past decade, a great deal of effort has been devoted to building Internet data archives. Several institutions run repositories where they post metadata of their collections, along with the data themselves, if their size is not prohibitively large. However, these repositories have been developed independently with different user interfaces, which adds complexity when users look for data of relevance scattered all over the Internet.

We present PacketShader, a high-performance software router framework for general packet processing with Graphics Processing Unit (GPU) acceleration. PacketShader exploits the massively-parallel processing power of GPU to address the CPU bottleneck in current software routers. Combined with our high-performance packet I/O engine, PacketShader outperforms existing software routers by more than a factor of four, forwarding 64B IPv4 packets at 39 Gbps on a single commodity PC. We have implemented IPv4 and IPv6 forwarding, OpenFlow switching, and IPsec tunneling to demonstrate the flexibility and performance advantage of PacketShader. The evaluation results show that GPU brings significantly higher throughput over the CPU-only implementation, confirming the effectiveness of GPU for computation and memory-intensive operations in packet processing.

SSL/TLS is a standard protocol for secure Internet communication. Despite its great success, today's SSL deployment is largely limited to security-critical domains. The low adoption rate of SSL is mainly due to high computation overhead on the server side.

In this paper, we propose a methodology to predict the popularity of online contents. More precisely, rather than trying to infer the popularity of a content itself, we infer the likelihood that a content will be popular. Our approach is rooted in survival analysis where predicting the precise lifetime of an individual is very hard and almost impossible but predicting the likelihood of one's survival longer than a threshold or another individual is possible. We position ourselves in the standpoint of an external observer who has to infer the popularity of a content only using publicly observable metrics, such as the lifetime of a thread, the number of comments, and the number of views. Our goal is to infer these observable metrics, using a set of explanatory factors, such as the number of comments and the number of links in the first hours after the content publication, which are observable by the external observer. We use a Cox proportional hazard regression model that divides the distribution function of the observable popularity metric into two components: (a) one that can be explained by the given set of explanatory factors (called risk factors) and(b) a baseline distribution function that integrates all the factors not taken into account. To validate our proposed approach, we use data sets from two different online discussion forums: dpreview.com, one of the largest online discussion groups providing news and discussion forums about all kinds of digital cameras, and myspace.com, one of the representative online social networking services. On these two data sets we model two different popularity metrics, the lifetime of threads and the number of comments, and show that our approach can predict the lifetime of threads from Dpreview (Myspace) by observing a thread during the first 5~6 days (24 hours, respectively) and the number of comments of Dpreview threads by observing a thread during first 2~3 days.

Twitter, a microblogging service less than three years old, commands more than 41 million users as of July 2009 and is growing fast. Twitter users tweet about any topic within the 140-character limit and follow others to receive their tweets. The goal of this paper is to study the topological characteristics of Twitter and its power as a new medium of information sharing.

Twitter offers an explicit mechanism to facilitate information diffusion and has emerged as a new medium for communication. Many approaches to find influentials have been proposed, but they do not consider the temporal order of information adoption. In this work, we propose a novel method to find influentials by considering both the link structure and the temporal order of information adoption in Twitter. Our method finds distinct influentials who are not discovered by other methods.

Online social networks pose significant challenges to computer scientists, physicists, and sociologists alike, for their massive size, fast evolution, and uncharted potential for social computing. One particular problem that has interested us is community identification. Many algorithms based on various metrics have been proposed for communities in networks [18, 24], but a few algorithms scale to very large networks. Three recent community identification algorithms, namely CNM [16], Wakita [59], and Louvain [10], stand out for their scalability to a few millions of nodes. All of them use modularity as the metric of optimization. However, all three algorithms produce inconsistent communities every time the ordering of nodes to the algorithms changes.

Massively distributed applications are popular in today's Internet. To improve the end-user experience, they require constantly updated information about the network-internal performance characteristics, such as RTT, effective bandwidth, IP hop count, and loss rate. Knowledge of network-internal characteristics allow distributed applications to solve commonly encountered problems, such as nearest neighbor discovery, leader node selection, and optimal distribution tree organization. Today's Internet does not provide any such information, and applications and new services resort often perform their own measurement to obtain necessary information.

For half a century, television has been a dominant and pervasive mass media, driving many technological advances. Despite its widespread usage and importance to emerging applications, the ingrained TV viewing habits are not completely understood. This was primarily due to the difficulty of instrumenting monitoring devices at individual homes at a large scale. The recent boom of Internet TV (IPTV) has enabled us to monitor the user behavior and network usage of an entire network. Such analysis can provide a clearer picture of how people watch TV and how the underlying networks and systems can better adapt to future challenges. In this paper, we present the first analysis of IPTV workloads based on network traces from one of the world's largest IPTV systems. Our dataset captures the channel change activities of 250,000 households over a six month period. We characterize the properties of viewing sessions, channel popularity dynamics, geographical locality, and channel switching behaviors. We discuss implications of our findings on networks and systems, including the support needed for fast channel changes. Our data analysis of an operational IPTV system has important implications on not only existing and future IPTV systems, but also the design of the open Internet TV distribution systems such as Joost and BBC's iPlayer that distribute television on the wider Internet.

Online social networking services are among the most popular Internet services according to Alexa.com and have become a key feature in many Internet services. Users interact through various features of online social networking services: making friend relationships, sharing their photos, and writing comments. These friend relationships are expected to become a key to many other features in web services, such as recommendation engines, security measures, online search, and personalization issues. However, we have very limited knowledge on how much interaction actually takes place over friend relationships declared online. A friend relationship only marks the beginning of online interaction.

User Generated Content (UGC) is re-shaping the way people watch video and TV, with millions of video producers and consumers. In particular, UGC sites are creating new viewing patterns and social interactions, empowering users to be more creative, and developing new business opportunities. To better understand the impact of UGC systems, we have analyzed YouTube, the world's largest UGC VoD system. Based on a large amount of data collected, we provide an in-depth study of YouTube and other similar UGC systems. In particular, we study the popularity life-cycle of videos, the intrinsic statistical properties of requests and their relationship with video age, and the level of content aliasing or of illegal content in the system. We also provide insights on the potential for more efficient UGC VoD systems (e.g. utilizing P2P techniques or making better use of caching). Finally, we discuss the opportunities to leverage the latent demand for niche videos that are not reached today due to information filtering effects or other system scarcity distortions. Overall, we believe that the results presented in this paper are crucial in understanding UGC systems and can provide valuable information to ISPs, site administrators, and content owners with major commercial and technical implications.

Social networking services are a fast-growing business in the Internet. However, it is unknown if online relationships and their growth patterns are the same as in real-life social networks. In this paper, we compare the structures of three online social networking services: Cyworld, MySpace, and orkut, each with more than 10 million users, respectively. We have access to complete data of Cyworld's ilchon (friend) relationships and analyze its degree distribution, clustering property, degree correlation, and evolution over time. We also use Cyworld data to evaluate the validity of snowball sampling method, which we use to crawl and obtain partial network topologies of MySpace and orkut. Cyworld, the oldest of the three, demonstrates a changing scaling behavior over time in degree distribution. The latest Cyworld data's degree distribution exhibits a multi-scaling behavior, while those of MySpace and orkut have simple scaling behaviors with different exponents. Very interestingly, each of the two e ponents corresponds to the different segments in Cyworld's degree distribution. Certain online social networking services encourage online activities that cannot be easily copied in real life; we show that they deviate from close-knit online social networks which show a similar degree correlation pattern to real-life social networks.

The distribution of broadcast TV across large provider networks has become a highly topical subject as satellite distribution capacity exhausts and competitive pressures increase. In a typical IPTV architecture, broadcast TV is distributed from two sources (for redundancy) to multiple destinations. The aim of this paper is to examine how IPTV can be reliably and cost effectively supported in wavelength division multiplexed (WDM) networks. WDM networks have evolved to mesh topologies and recently to support multicast, which is particularly valuable in reducing the network cost in broadcast TV applications. Our goal is to find two trees with a minimal total cost such that we have two physically (or Shared Risk Link Group (SRLG)) diverse paths to each of the destinations - one from each of the sources. Any two links that belong to a common SRLG are subject to a single point of failure, be it a channel or wavelength failure, a fiber cut, or a complete conduit cut. We first show that our path protection routing problem is NP-complete. We then propose an Integer Programming (IP) formulation for this problem. Using real network topology data, we show that the real networks are amenable to the IP problem formulation and yield optimal solutions.

Abstract — To increase reliability and robustness of missioncritical services in the face of routing changes, it is often desirable and beneficial to take advantage of path diversity provided by the network topology. One way of achieving this inside a single Autonomous System (AS) is to use two paths between every Origin-Destination (OD) pair. One path is the default path defined by the intra-domain routing protocol; the other path is defined as an overlay path that passes through a strategically placed relay node. The key question then is how to place such relay nodes inside an AS, which is the focus of this paper. We propose two heuristic algorithms to find the positions of relay nodes such that every OD pair has an overlay path, going through a relay node, that is disjoint from the default path. When it is not possible to find completely disjoint overlay paths, we allow overlay paths to have overlapped links with default paths. Since overlapped links diminish the robustness of overlay paths against a single point of failure, we introduce the notion of penalty for partially disjoint paths. We apply our algorithms on three different types of topology data – real, inferred, and synthetic – and show that our algorithms find relay nodes of close-to-minimum penalty. Using daily topology snapshots and network event log, we also show that our choices for relay nodes are relatively insensitive to network dynamics; which is very important for a placement algorithm to be viable and practical. Index Terms — Routing protocols, Overlay networks, Path diversity. I.

Point-to-point delay is an important network performance measure as well as a key parameter in SLAs. We study how to measure and report delay in a concise and meaningful way for an ISP, and how to monitor it efficiently. We analyze various measurement intervals and potential metric definitions. We find that reporting high quantiles (between 0.95 and 0.99)every 10-30 minutes as the most effective way to summarize the delay in an ISP. We then propose an active probing scheme to estimate a high quantile with bounded error. We show that only a small number of probes are sufficient to provide an accurate estimate. We validate the proposed delay monitoring technique on real data collected on the Sprint IP backbone network.

We perform a detailed analysis of point-to-point packet delay in an operational tier-1 network. The point-to-point delay is the time between a packet entering a router in one PoP (an ingress point) and its leaving a router in another PoP (an egress point). It measures the one-way delay experienced by packets from an ingress point to an egress point across an ISP's network and provides the most basic information regarding the delay performance of the ISP's network. Using packet traces captured in the operational network, we obtain precise point-to-point packet delay measurements and analyze the various factors affecting them. Through a simple, step-by-step, systematic methodology and careful data analysis, we identify the major network factors that contribute to point-to-point packet delay and characterize their effect on the network delay performance. Our findings are: 1) delay distributions vary greatly in shape, depending on the path and link utilization; 2) after constant factors dependent only on the path and packet size are removed, the 99th percentile variable delay remains under 1 ms over several hops and under link utilization below 90% on a bottleneck; 3) a very small number of packets experience very large delay in short bursts.

Routing loops are caused by inconsistencies in the routing state of the network. Although undesirable from this aspect, they can provide insight into the routing dynamics that caused them. In this work we present a methodology that utilizes a priori knowledge of loops to study the correlation between routing loops and routing events that could have caused them. We apply our technique to associate route changes with packet loops detected in actual traffic traces collected from the Sprint Backbone. Our study shows that a strong correlation exists between loops and changes in the BGP routing state while the link state protocols ISIS is seldom responsible for such events. Our analysis also identifies factors that influence the distribution of loop path lengths as well as the effectiveness of our detection techniques.

The small-time (sub-seconds) scaling behaviors of Internet backbone traffic, based on traces collected from OC3/12/48 links in a tier-1 ISP is studied. We observe that for a majority of these traces, the (second-order) scaling exponents at small time scales (1 ms - 100 ms) are fairly close to 0.5, indicating that traffic fluctuations at these time scales are (nearly) uncorrelated. In addition, the traces manifest mostly monofractal behaviors at small time scales. The objective of the paper is to understand the potential causes or factors that influence the small-time scalings of Internet backbone traffic via empirical data analysis. We analyze the traffic composition of the traces along two dimensions - flow size and flow density. Our study uncovers dense flows (i.e., flows with bursts of densely clustered packets) as the correlation-causing factor in small time scales, and reveals that the traffic composition in terms of proportions of dense vs. sparse flows plays a major role in influencing the small-time scalings of aggregate traffic.

We measure and analyze the single-hop packet delay through operational routers in the Sprint Internet protocol (IP) backbone network. After presenting our delay measurements through a single router for OC-3 and OC-12 link speeds, we propose a methodology to identify the factors contributing to single-hop delay. In addition to packet processing, transmission, and queueing delay at the output link, we observe the presence of very large delays that cannot be explained within the context of a first-in first-out output queue model. We isolate and analyze these outliers. Results indicate that there is very little queueing taking place in Sprint's backbone. As link speeds increase, transmission delay decreases and the dominant part of single-hop delay is packet processing time. We show that if a packet is received and transmitted on the same linecard, it experiences less than 20 μs of delay. If the packet is transmitted across the switch fabric, its delay doubles in magnitude. We observe that processing due to IP options results in single-hop delays in the order of milliseconds. Milliseconds of delay may also be experienced by packets that do not carry IP options. We attribute those delays to router idiosyncratic behavior that affects less than 1% of the packets. Finally, we show that the queueing delay distribution is long-tailed and can be approximated with a Weibull distribution with the scale parameter a=0.5 and the shape parameter b=0.6 to 0.82.

Real-world traffic traces are crucial for Internet research, but only a very small percentage of traces collected are made public. One major reason why traffic trace owners hesitate to make the traces publicly available is the concern that confidential and private information may be inferred from the trace. We focus on the problem of anonymizing IP addresses in a trace. More specifically, we are interested in prefix-preserving anonymization in which the prefix relationship among IP addresses is preserved in the anonymized trace, making such a trace usable in situations where prefix relationships are important. The goal of our work is two fold. First, we develop a cryptography-based, prefix-preserving anonymization technique that is provably as secure as the existing well-known TCPdpriv scheme, and unlike TCPdpriv, provides consistent prefix-preservation in large scale distributed setting. Second, we evaluate the security properties inherent in all prefix-preserving IP address anonymization schemes (including TCPdpriv). Through the analysis of Internet backbone traffic traces, we investigate the effect of some types of attacks on the security of any prefix-preserving anonymization algorithm. We also derive results for the optimum manner in which an attack should proceed, which provides a bound on the effectiveness of attacks in general.

Routing loops are caused by inconsistencies in routing state among a set of routers. They occur in perfectly engineered networks, and have a detrimental effect on performance. They impact end-to-end performance through increased packet loss and delay for packets caught in the loop, and through increased link utilization and corresponding delay and jitter for packets that traverse the link but are not caught in the loop.Using packet traces from a tier-1 ISP backbone, we first explain how routing loops manifest in packet traces. We characterize routing loops in terms of the packet types caught in the loop, the loop sizes, and the loop durations. Finally, we analyze the impact of routing loops on network performance in terms of loss and delay.

We measure and analyze the single-hop packet delay through operational routers in a backbone IP network. First we present our delay measurements through a single router. Then we identify step-by-step the factors contributing to single-hop delay. In addition to packet processing, transmission, and queueing delays, we identify the presence of very large delays due to non-work-conserving router behavior. We use a simple output queue model to separate those delay components. Our step-by-step methodology used to ohtain the pure queueing delay is easily applicable to any single-hop delay measurements. After obtaining the queueing delay, we analyze the tail of its distribution, and find that it is long tailed and fits a Weihull distrihution with the scale parameter, a = 0.5, and the shape parameter, b = 0.58 to 0.6. The measured average queueing delay is larger than predicted by M/M/l, M/G/l, and FBM models when the link utilization is below 70%, but its absolute value is quite small.

Packet delay and loss traces are frequently used by network engineers, as well as network applications, to analyze network performance. The clocks on the end-systems used to measure the delays, however, are not always synchronized, and this lack of synchronization reduces the accuracy of these measurements. Therefore, estimating and removing relative skews and offsets from delay measurements between sender and receiver clocks are critical to the accurate assessment and analysis of network performance. We introduce a linear programming-based algorithm to estimate the clock skew in network delay measurements and compare it with three other algorithms. We show that our algorithm has a time complexity of O(N), leaves the delay after the skew removal positive, and is robust in the sense that the error margin of the skew estimate is independent of the magnitude of the skew. We use traces of real Internet delay measurements to assess the algorithm, and compare its performance to that of three other algorithms. Furthermore, we show through simulation that our algorithm is unbiased, and that the sample variance of the skew estimate is better (smaller) than existing algorithms.

Understanding and modelling packet loss in the Internet is especially relevant for the design and analysis of delay-sensitive multimedia applications. We present analysis of 128 hours of end-to-end unicast and multicast packet loss measurement. From these we selected 76 hours of stationary traces for further analysis. We consider the dependence as seen in the autocorrelation function of the original loss data as well as the dependence between good run lengths and loss run lengths. The correlation timescale is found to be 1000 ms or less. We evaluate the accuracy of three models of increasing complexity: the Bernoulli model, the 2-state Markov chain model and the k-th order Markov chain model. Out of the 38 trace segments considered, the Bernoulli model was found to be accurate for 7 segments, and the 2-state model was found to be accurate for 10 segments. A Markov chain model of order 2 or greater was found to be necessary to accurately model the rest of the segments. For the case of adaptive applications which track loss, we address two issues of on-line loss estimation: the required memory size and whether to use exponential smoothing or a sliding window average to estimate average loss rate. We find that a large memory size is necessary and that the sliding window average provides a more accurate estimate for the same effective memory size.