687466
Placing Relay Nodes for Intra-Domain Path Diversity
Meeyoung Cha and Sue Moon are supported by Korea 
Science and Engineering Foundation through Advanced Information 
Technology Research Center (AITrc). Chong-Dae Park 
is supported by Brain Korea 21 Project through the school 
of information technology in KAIST. Part of this work was 
done while Meeyoung Cha was visiting DIMACS (Center for 
Discrete Mathematics and Theoretical Computer Science). We 
thank Joel Gottlieb for help with ISP data, and Lun Li for 
providing the HOT topology used in our simulation. We thank 
Jennifer Rexford and anonymous reviewers for providing us 
valuable comments.
8164368
Detection and analysis of routing loops in packet traces
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.
13506842
Small-time scaling behavior of Internet backbone traffic
We perform an extensive wavelet analysis of Internet backbone traffic traces to observe and understand the causes of small-time scaling phenomena present in them. We observe that for a majority of the traces, the second-order scaling exponents at small time scales (1-100ms) are fairly close to 0.5, indicating that traffic fluctuations at these time scales are nearly uncorrelated. Some traces, however, do exhibit moderately large scaling exponents (~0.7) at small time scales. In addition, the traces manifest mostly monofractal behaviors at small time scales. To identify the network causes of the observed scaling behavior, we analyze the flow composition of the traffic along two dimensions-flow byte contribution and flow density. Our study points to the dense flows (i.e., flows with 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. Since queuing inside routers is influenced by traffic fluctuations at small time-scales, our observations and results have important implications for networking modeling, service provisioning and traffic engineering.
74834
Estimation and removal of clock skew from network delay measurements
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.
5965700
Analysis of topological characteristics of huge online social networking services
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.
148323
Analysis of point-to-point packet delay in an operational network
In this paper 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
15969885
Optimistic register coalescing
Graph-coloring register allocators eliminate copies by coalescing the source and target nodes of a copy if they do not interfere in the interference graph. Coalescing, however, can be harmful to the colorability of the graph because it tends to yield a graph with nodes of higher degrees. Unlike aggressive coalescing, which coalesces any pair of noninterfering copy-related nodes, conservative coalescing or iterated coalescing perform safe coalescing that preserves the colorability. Unfortunately, these heuristics give up coalescing too early, losing many opportunities for coalescing that would turn out to be safe. Moreover, they ignore the fact that coalescing may even improve the colorability of the graph by reducing the degree of neighbor nodes that are interfering with both the source and target nodes being coalesced. This article proposes a new heuristic called optimistic coalescing which optimistically performs aggressive coalescing, thus exploiting the positive impact of coalescing aggressively, but when a coalesced node is to be spilled, it is split back into separate nodes. Since there is a better chance of coloring one of those splits, we can reduce the overall spill amount.
32135793
Split-Path Enhanced Pipeline Scheduling
Software pipelining increases the loop execution throughput by overlapping the execution of successive iterations in a pipelined fashion. For loops with control flows, however, software pipelining is not straightforward because we need to consider the overlap of more than one execution path. Modulo scheduling simply transforms them into straightline loops through if-conversion which, in effect, achieves a fixed, worst-case initiation interval (/spl par/) among all paths. On the other hand, all-path pipelining (APP) and enhanced pipeline scheduling (EPS) can achieve a variable /spl par/ depending on the path that is taken at execution time. Unfortunately, APP concentrates only on the overlap within the same path, entirely losing the overlap between different paths, whereas EPS attempts to overlap all paths together, failing to produce a tight schedule for each individual path, especially when resource constraints are tight. In this paper, we propose a new approach to EPS called split-path EPS (SP-EPS), which first splits each individual path via tail duplication and then performs EPS in a way to guarantee a tight schedule for each path, while producing a competitive cross-path schedule. We also extend SP-EPS to outer loops such that frequent paths that bypass the inner loop are split and then scheduled by SP-EPS. Our experimental results on nontrivial integer benchmarks show that SP-EPS can achieve as much as a geometric mean of 10 percent speedup over EPS when innermost loops are scheduled by SP-EPS, while it can achieve a geometric mean of 11.9 percent speedup when outer loops are also scheduled by SP-EPS.
2527806
Knowledge representation for product design using Techspecs Concept Ontology
Sharing and reusing product design information can help reduce cost and time when developing new products and facilitate good product family design. An appropriate representation scheme for components and products is important to share and reuse this information effectively. The objective in this research is to develop a method for representing components and products using an ontology based on the Techspecs Concept Ontology (TCO), which consists of functionality, assembly, and product technical specifications. We use a device ontology for representing the behavior, functionality, and relationships of products and their components. This concept enables better understanding of the representation of the products and components and improves the process of searching for components satisfying customer needs and functional requirements. We demonstrate TCO development using a case study involving a family of power tools. Future work involving the use of TCO to capture semantics associated with components and products to represent knowledge for use with agents is also discussed.
3191125
Optimistic register coalescing
Graph-coloring register allocators eliminate copies by coalescing the source and target node of a copy if they do not interfere in the interference graph. Coalescing is, however, known to be harmful to the colorability of the graph because it tends to yield a graph with nodes of higher degrees. Unlike aggressive coalescing which coalesces any pair of non-interfering copy-related nodes, conservative coalescing or iterated coalescing perform safe coalescing that preserves the colorability. Unfortunately, these heuristics give up coalescing too early, losing many opportunities of coalescing that would turn out to be safe. Moreover, they ignore the fact that coalescing may even improve the colorability of the graph by reducing the degree of neighbor nodes that are interfering with both the source and target nodes being coalesced. This paper proposes a new heuristic called optimistic coalescing which optimistically performs aggressive coalescing, thus fully exploiting the positive impact of coalescing, yet when a coalesced node is to be spilled, it is split back into separate nodes; there as a better chance of coloring one of them which reduces the overall spill cost.