Physical Sciences and Mathematics Commons^™

Tcp Congestion Avoidance Algorithm Identification (Caai), Peng Yang, Wen Luo, Lisong Xu, Jitender Deogun, Ying Lu

CSE Conference and Workshop Papers

The Internet has recently been evolving from homogeneous congestion control to heterogeneous congestion control. Several years ago, Internet traffic was mainly controlled by the traditional AIMD algorithm, whereas Internet traffic is now controlled by many different TCP algorithms, such as AIMD, BIC, CUBIC, and CTCP. However, there is very little work on the performance and stability study of the Internet with heterogeneous congestion control. One fundamental reason is the lack of the deployment information of different TCP algorithms. In this paper, we first propose a tool called TCP Congestion Avoidance Algorithm Identification (CAAI) for actively identifying the TCP algorithm of …

Adaptive Neighborhood Inverse Consistence As Lookahead For Non-Binary Csps, Robert J. Woodward, Shant K. Karakashian, Berthe Y. Choueiry, Christian Bessiere

CSE Conference and Workshop Papers

Contributions

1.The property Relational Neighborhood Inverse Consistency (RNIC)
2.Characterization of RNIC in relation to previously known properties
3.An efficient algorithm for enforcing RNIC, bounded by degree of the dual graph
4.Three reformulations of the dual graph to address topological limitations of the dual graph
5.An adaptive, automatic selection policy for choosing the appropriate dual graph
6.Empirical evidence on difficult CSP benchmarks

Definition

A Constraint Satisfaction Problem (CSP) is a combinatorial decision problem defined by a set of variables {A,B,C,…}, a set of domain values for these variables, and a set of constraints {R₁,R₂,R₃,…} restricting …

Understanding User Generated Content Characteristics : A Hot-Event Perspective, Miao Wang, Guodong Li, Jie Feng, Lisong Xu, Byrav Ramamurthy, Wei Li, Xiaohong Guan

CSE Conference and Workshop Papers

Nowadays, millions of Internet users watch and upload a large number of videos on User Generated Content (UGC) sites (e.g., Youtube) everyday. Moreover, online videos about hot events, such as breaking news and Olympic games, attract lots of users. In this paper, we study the characteristics of hot-event videos by collecting video traces of the largest UGC site in China for 28 days. We first empirically study statistical properties of such videos and find that hot-event videos contribute a large number of views, even though the total number of hotevent videos is relatively small. In addition, there exist extremely active …

A Reformulation Strategy For Multi-Dimensional Csps: The Case Study Of The Set Game, Amanda Swearngin, Berthe Y. Choueiry, Eugene C. Freuder

CSE Conference and Workshop Papers

In this paper we describe a reformulation strategy for solving multi-dimensional Constraint Satisfaction Problems (CSPs). This strategy operates by iteratively considering, in isolation, each one of the uni-dimensional constraints in the problem. It exploits the approximate symmetries identified on the domain values in order to enforce the selected constraint on the simplified problem. This paper uses the game of SET, a combinatorial card game, to motivate and illustrate our strategy. We propose a multi-dimensional constraint model for SET, and describe a basic constraint solver for finding all solutions of an instance of the game. Then, we introduce an algorithm that …

Solving Difficult Csps With Relational Neighborhood Inverse Consistency, Robert J. Woodward, Shant Karakashian, Berthe Y. Choueiry, Christian Bessiere

CSE Conference and Workshop Papers

•Introduction

•Relational Neighborhood Inverse Consistency

–Property, Algorithm, Improvements

•Reformulating the Dual Graph by

1.Redundancy removal ⟿ property wRNIC

2.Triangulation ⟿ property triRNIC

•Selection strategy: four alternative dual graphs

•Experimental Results

•Conclusion

Reformulating The Dual Graphs Of Csps To Improve The Performance Of Rnic, Robert J. Woodward, Shant Karakashian, Berthe Y. Choueiry, Christian Bessiere

CSE Conference and Workshop Papers

•Introduction

•Relational Neighborhood Inverse Consistency

–Property & algorithm

•Reformulating the Dual Graph by

1.Removing redundant edges, yields property wRNIC

2.Triangulation, yields property triRNIC

•Selection strategy: four alternative dual graphs

•Experimental Results

•Conclusion

Refactoring Pipe-Like Mashups For End-User Programmers, Kathryn T. Stolee, Sebastian Elbaum

CSE Conference and Workshop Papers

Mashups are becoming increasingly popular as end users are able to easily access, manipulate, and compose data from many web sources. We have observed, however, that mashups tend to suffer from deficiencies that propagate as mashups are reused. To address these deficiencies, we would like to bring some of the benefits of software engineering techniques to the end users creating these programs. In this work, we focus on identifying code smells indicative of the deficiencies we observed in web mashups programmed in the popular Yahoo! Pipes environment. Through an empirical study, we explore the impact of those smells on end-user …

A Reformulation Strategy For Multi-Dimensional Csps: The Case Study Of The Set Game, Amanda Swearngin, Berthe Y. Choueiry, Robert J. Woodward, Eugene C. Freuder

CSE Conference and Workshop Papers

•General reformulation strategy for CSPs

–Multidimensional CSPs (MD-CSPs)

–Problem reformulation by value interchangeability

–A general reformulation strategy for MD-CSPs

•Game of Set: A new toy problem

–Game, CSP model

–Problem reformulation

–Algorithms & Results

•Conclusions

Reformulating R(*,M)C With Tree Decomposition, Shant Karakashian, Robert J. Woodward, Berthe Y. Choueiry

CSE Conference and Workshop Papers

•Introduction

•R(*,m)C Property & Algorithm

•Exploit Tree Decomposition to

–Avoid useless update & reduce propagation effort

↪ Update queue: PROCESSQ ⟿ PROCESSMQ

↪ The two algorithms yield the same filtering

–Synthesize & add new constraints to improve propagation

↪ Property enforced: R(*,m)C ⟿ T-R(*,m,z)C

↪ The same algorithm yields stronger filtering

•Experimental Results

•Conclusion

Rightsizing Bundle Link Capacities For Energy Savings In The Core Network, Lin Liu, Byrav Ramamurthy

CSE Conference and Workshop Papers

Current core networks are composed of high-end routers which are connected by high-speed fibers. These optical connections are commonly over provisioned and in low utilization. Many of them are combined together to form bundle links or composite links and the component links are referred to as sublinks. These physical sublinks could be SONET connections, Ethernet circuits, wavelengths on a fiber, etc and they could be shut down or brought up independently. Selectively shutting down sublinks during low traffic periods could save a large amount of energy while keeping the network topology unchanged. Based on this concept, we propose a local …

Shhc: A Scalable Hybrid Hash Cluster For Cloud Backup Services In Data Centers, Lei Xu, Jian Hu, Stephen Mkandawire, Hong Jiang

CSE Conference and Workshop Papers

Data deduplication techniques are ideal solutions for reducing both bandwidth and storage space requirements for cloud backup services in data centers. Current data deduplication solutions rely on comparing fingerprints (hash values) of data chunks to identify redundant data and store the fingerprints on a centralized server. This approach limits the overall throughput and concurrency performance in large scale systems. Furthermore, the slow seek time associated with hard disks degrades the performance of hash look up operations which are mainly random I/Os.

In this paper we present a scalable hybrid hash cluster (SHHC) to maintain a low-latency distributed hash table for …

Directed Test Suite Augmentation, Zhihong Xu

CSE Conference and Workshop Papers

Test suite augmentation techniques are used in regression testing to identify code elements affected by changes and to generate test cases to cover those elements. Whereas methods and techniques to find affected elements have been extensively researched in regression testing, how to generate new test cases to cover these elements cost-effectively has rarely been studied. It is known that generating test cases is very expensive, so we want to focus on this second step. We believe that reusing existing test cases will help us achieve this task. This research intends to provide a framework for test suite augmentation techniques that …

Tcp Congestion Avoidance Algorithm Identification, Peng Yang, Wen Luo, Lisong Xu, Jitender S. Deogun, Ying Lu

CSE Conference and Workshop Papers

The Internet has recently been evolving from homogeneous congestion control to heterogeneous congestion control. Several years ago, Internet traffic was mainly controlled by the traditional AIMD algorithm, whereas Internet traffic is now controlled by many different TCP algorithms, such as AIMD, BIC, CUBIC, and CTCP. However, there is very little work on the performance and stability study of the Internet with heterogeneous congestion control. One fundamental reason is the lack of the deployment information of different TCP algorithms. In this paper, we first propose a tool called TCP Congestion Avoidance Algorithm Identification (CAAI) for actively identifying the TCP algorithm of …

Using Property-Based Oracles When Testing Embedded System Applications, Tingting Yu, Ahyoung Sung, Witawas Srisaan, Gregg Rothermel

CSE Conference and Workshop Papers

Embedded systems are becoming increasingly ubiquitous, controlling a wide variety of popular and safety critical devices. Effective testing techniques could improve the dependability of these systems. In prior work we presented an approach for testing embedded systems, focusing on embedded system applications and the tasks that comprise them. In this work we focus on a second but equally important aspect of testing embedded systems; namely, the need to provide observability of system behavior sufficient to allow engineers to detect failures. We present several property-based oracles that can be instantiated in embedded systems through program analysis and instrumentation, and can detect …

Unifying Testing And Analysis Through Behavioral Coverage, Matthew B. Dwyer

CSE Conference and Workshop Papers

The past decades have produced a wide-variety of automated techniques for assessing the correctness of software systems. In practice, when applied to large modern software systems all existing automated program analysis and verification techniques come up short. They might produce false error reports, exhaust available human or computational resources, or be incapable of reasoning about some set of important properties. Whatever their shortcoming, the goal of proving a system correct remains elusive.

Many people believe that, after an initial period of development, software systems are "mostly" correct — systems have much more correct behavior than incorrect behavior. Following this line …

Adaptive Neighborhood Inverse Consistency As Lookahead For Non-Binary Csps, Robert J. Woodward, Shant K. Karakashian, Berthe Y. Choueiry, Christian Bessiere

CSE Conference and Workshop Papers

Freuder and Elfe (1996) introduced Neighborhood Inverse Consistency (NIC) for binary CSPs. In this paper, we introduce RNIC, the extension of NIC to nonbinary CSPs, and describe a practical algorithm for enforcing it. We propose an adaptive strategy to weaken or strengthen this property based on the connectivity of the network. We demonstrate the effectiveness of RNIC as a full lookahead strategy during search for solving difficult benchmark problems.

Reformulating The Dual Graphs Of Csps To Improve The Performance Of Relational Neighborhood Inverse Consistency, Robert J. Woodward, Shant Karakashian, Berthe Y. Choueiry, Christian Bessiere

CSE Conference and Workshop Papers

Freuder and Elfe (1996) introduced Neighborhood Inverse Consistency (NIC) as a new local consistency property for binary Constraint Satisfaction Problems (CSPs). Two advantages of the algorithm for enforcing NIC is that it automatically adapts its filtering power to the local connectivity of the network and has insignificant space overhead. However, studies on binary CSPs have shown that enforcing NIC is not effective on sparse graphs and too costly on dense graphs. In (Woodward et al. 2011), we introduced an algorithm for enforcing Relational Neighborhood Inverse Consistency (RNIC), which is an extension of NIC to non-binary CSPs. In this paper, we …

A Real-Time Rfid Localization Experiment Using Propagation Models, Jason L. Brchan, Lianlin Zhao, Jiaqing Wu

CSE Conference and Workshop Papers

This paper introduces a real-time localization system (RTLS) using efficient multiple propagation models to compensate for the drawback of the received signal strength technique. The RTLS is implemented on an active RFID system and uses received signal strength measurements and reference tags for ranging. The RTLS is implemented purely in software that post processes the received signal strength data from the reader and does not require any additional hardware or any modifications to the RFID reader or tags. The proposed algorithm using multiple propagation models improves the performance of the RTLS. Two-dimensional localization results are given for a four-reader system …

Analysis Of Event Detection Delay In Wireless Sensor Networks, Yunbo Wang, Mehmet C. Vuran, Steve Goddard

CSE Conference and Workshop Papers

Emerging applications of wireless sensor networks (WSNs) require real-time event detection to be provided by the network. In a typical event monitoring WSN, multiple reports are generated by several nodes when a physical event occurs, and are then forwarded through multi-hop communication to a sink that detects the event. To improve the event detection reliability, usually timely delivery of a certain number of packets is required. Traditional timing analysis of WSNs are, however, either focused on individual packets or traffic flows from individual nodes. In this paper, a spatio-temporal fluid model is developed to capture the delay characteristics of event …

A Survey Of Deployment Information Of Delay-Based Tcp Congestion Avoidance Algorithm For Transmitting Multimedia Data, Peng Yang, Lisong Xu

CSE Conference and Workshop Papers

Multimedia traffic comprises a significant part of the total Internet traffic. Due to the real-time nature of the multimedia traffic, low queuing delay is critical to many multimedia applications. This requirement makes delay-based TCP congestion avoidance algorithms (or delay-based TCP algorithms for short) a good choice to transmit multimedia data, since they can help keep a low queuing delay in the Internet. However, the Internet traffic is controlled by heterogeneous TCP algorithms and many of them are non-delay-based. Thus, the effort made by the delay-based TCP algorithms to reduce the queuing delay is often offset by the non-delay-based TCP algorithms. …

Experiences With Dynamic Circuit Creation In A Regional Network Testbed, Pragatheeswaran Angu, Byrav Ramamurthy

CSE Conference and Workshop Papers

In this paper we share our experiences of enabling dynamic circuit creation in the GpENI network. GpENI is a network research testbed in the mid-west USA involving several educational institutions. University of Nebraska-Lincoln is involved in provisioning dynamic circuits across the GpENI network among its participating universities. We discuss several options investigated for deploying dynamic circuits over the GpENI network as well as our demonstration experiments at the GENI engineering conferences. UNL has also collaborated with ProtoGENI project of University of Utah and Mid-Atlantic Crossroads (MAX) facility of Washington DC to create interdomain dynamic circuits.

Automatic Generation Of Load Tests, Pingyu Zhang, Sebastian Elbaum, Matthew Dwyer

CSE Conference and Workshop Papers

Load tests aim to validate whether system performance is acceptable under peak conditions. Existing test generation techniques induce load by increasing the size or rate of the input. Ignoring the particular input values, however, may lead to test suites that grossly mischaracterize a system’s performance. To address this limitation we introduce a mixed symbolic execution based approach that is unique in how it 1) favors program paths associated with a performance measure of interest, 2) operates in an iterative-deepening beam-search fashion to discard paths that are unlikely to lead to high-load tests, and 3) generates a test suite of a …

Response Time Analysis Of Hierarchical Scheduling: The Synchronized Deferrable Servers Approach, Haitao Zhu, Steve Goddard, M. Dwyer

CSE Conference and Workshop Papers

Hierarchical scheduling allows reservation of processor bandwidth and the use of different schedulers for different applications on a single platform. We propose a hierarchical scheduling interface called synchronized deferrable servers that can reserve different processor bandwidth on each core, and can combine global and partitioned scheduling on a multicore platform. Significant challenges will arise in the response time analysis of a task set if the tasks are globally scheduled on a multiprocessor platform and the processor bandwidth reserved for the tasks on each processor is different; as a result, existing works on response time analysis for dedicated scheduling on identical …

End-User Programmers And Their Communities: An Artifact-Based Analysis, Kathryn T. Stolee, Sebastian Elbaum, Anita Sarma

CSE Conference and Workshop Papers

End-user programmers outnumber professionals programmers, write software that matters to an increasingly large number of users, and face software engineering challenges that are similar to their professionals counterparts. Yet, we know little about how these end-user programmers create and share artifacts as part of a community. To gain a better understanding of these issues, we perform an artifact-based community analysis of 32,000 mashups from the Yahoo! Pipes repository. We observed that, like with other online communities, there is great deal of attrition but authors that persevere tend to improve over time, creating pipes that are more configurable, diverse, complex, and …

Cost And Reliability Considerations In Designing The Next-Generation Ip Over Wdm Backbone Networks, Byrav Ramamurthy, K. K. Ramakrishnan, Rakesh K. Sinha

CSE Conference and Workshop Papers

To accommodate the increasing demands for bandwidth, Internet Service Providers (ISPs) have deployed higher speed links and reconfigurable optical add drop multiplexers (ROADMs) in their backbone networks. To address the reliability challenges due to failures and planned outages, ISPs typically use two backbone routers at each central office in a dual home configuration. Thus at the IP layer, redundant backbone routers as well as redundant transport equipment to interconnect them are deployed to provide reliability through node and path diversity. However, adding such redundant resources increases the overall cost of the network. Hence, a fundamental redesign of the backbone network …

Diagnosis Of Multiple Scan-Chain Faults In The Presence Of System Logic Defects, Zhen Chen, Sharad C. Seth, Dong Xiang, Bhargab B. Bhattacharya

CSE Conference and Workshop Papers

We present a combined hardware-software based approach to scan-chain diagnosis, when the outcome of a test may be affected by system faults occurring in the logic outside of the scan chain. For the hardware component we adopt the double-tree scan (DTS) chain architecture, which has previously been shown to be effective in reducing power, volume, and application time of tests for stuck-at and delay faults. We develop a version of flush test which can resolve a multiple fault in a DTS chain to a small number of suspect candidates. Further resolution to a unique multiple fault is enabled by the …

Multi-Dimensional Models Facilitate Automatic Reformulation: The Case Study Of The Set Game, Amanda Swearngin, Berthe Y. Choueiry, Eugene C. Freuder

CSE Conference and Workshop Papers

In this paper we describe a reformulation strategy for solving multidimensional Constraint Satisfaction Problems (CSPs). This strategy operates by iteratively considering, in isolation, each one of the uni-dimensional constraints in the problem, and exploits the approximate symmetries induced by the selected constraint on the domains in order to enforce this constraint on the simplified problem. We use the game of SET, a combinatorial card game, as a toy problem to motivate our strategy and to explain and illustrate its operation. However, we believe that our approach is applicable to more complex domains of scientific and industrial importance, and deserves more …

A Reformulation Strategy For Multi-Dimensional Csps: The Case Study Of The Set Game, Amanda Swearngin, Berthe Y. Choueiry, Eugene C. Freuder

CSE Conference and Workshop Papers

•General reformulation strategy for CSPs

–Multidimensional CSPs (MD-CSPs)

–Problem reformulation by value interchangeability

–A general reformulation strategy for MD-CSPs

•Game of Set: A new toy problem

–Game, CSP model

–Problem reformulation

–Algorithms & Results

•Conclusions

Solving Difficult Csps With Relational Neighborhood Inverse Consistency, Robert J. Woodward, Shant Karakashian, Berthe Y. Choueiry, Christian Bessiere

CSE Conference and Workshop Papers

Freuder and Elfe (1996) introduced Neighborhood Inverse Consistency (NIC) as a strong local consistency property for binary CSPs. While enforcing NIC can significantly filter the variables domains, the proposed algorithm is too costly to be used on dense graphs or for lookahead during search. In this paper, we introduce and characterize Relational Neighborhood Inverse Consistency (RNIC) as a local consistency property that operates on the dual graph of a non-binary CSP. We describe and characterize a practical algorithm for enforcing it. We argue that defining RNIC on the dual graph unveils unsuspected opportunities to reduce the computational cost of our …

Reformulating R(*;M)C With Tree Decomposition, Shant Karakashian, Robert J. Woodward, Berthe Y. Choueiry

CSE Conference and Workshop Papers

Local consistency properties and algorithms for enforcing them are central to the success of Constraint Processing. Recently, we have demonstrated the importance of higher levels of consistency and the effectiveness of their algorithms for solving difficult problems (Karakashian et al. 2010; Woodward et al. 2011). In this paper, we introduce two reformulation techniques for improving the effectiveness of our algorithm for the relational consistency property R(*;m)C (Karakashian et al. 2010). Both techniques exploit a tree decomposition of the constraint network of a Constraint Satisfaction Problem (CSP), which is a tree embedding of the network. Our first reformulation technique …