Traffic for internet video streaming has been rapidly increasing and is further expected to increase with the higher definition videos and IoT applications, such as 360 degree videos and augmented virtual reality applications. While efficient management of heterogeneous cloud resources to optimize the quality of experience is important, existing work in this problem space often left out important factors. In this paper, we present a model for describing a today’s representative system architecture for video streaming applications, typically composed of a centralized origin server and several CDN sites. Our model comprehensively considers the following factors: limited caching spaces at the CDN sites, allocation of CDN for a video request, choice of different ports from the CDN, and the central storage and bandwidth allocation. With the model, we focus on minimizing a performance metric, stall duration tail probability (SDTP), and present a novel, yet efficient, algorithm to solve the formulated optimization problem. The theoretical bounds with respect to the SDTP metric are also analyzed and presented. Our extensive simulation results demonstrate that the proposed algorithms can significantly improve the SDTP metric, compared to the baseline strategies. Small-scale video streaming system implementation in a real cloud environment further validates our results.

This paper proposes an algorithm to minimize weighted service latency for different classes of tenants (or service classes) in a data center network where erasure-coded files are stored on distributed disks/racks and access requests are scattered across the network. Due to the limited bandwidth available at both top-of-the-rack and aggregation switches, and differentiated service requirements of the tenants, network bandwidth must be apportioned among different intra- and inter-rack data flows for different service classes in line with their traffic statistics. We formulate this problem as weighted queuing and employ a class of probabilistic request scheduling policies to derive a closed-form upper-bound of service latency for erasure-coded storage with arbitrary file access patterns and service time distributions. The result enables us to propose a joint weighted latency (over different service classes) optimization over three entangled “control knobs”: the bandwidth allocation at top-of-the-rack and aggregation switches for different service classes, dynamic scheduling of file requests, and the placement of encoded file chunks (i.e., data locality). The joint optimization is shown to be a mixed-integer problem. We develop an iterative algorithm which decouples and solves the joint optimization as 3 sub-problems, which are either convex or solvable via bipartite matching in polynomial time. The proposed algorithm is prototyped in an open-source, distributed file system, Tahoe, and evaluated on a cloud testbed with 16 separate physical hosts in an OpenStack cluster using Cisco switches. Experiments validate our theoretical latency analysis and show significant latency reduction for diverse file access patterns. The results provide valuable insights on designing low-latency data center networks with erasure coded storage.

The explosive growth of data due to the increasing adoption of cloud technologies in the enterprise has created a strong demand for more flexible, cost-effective, and scalable storage solutions. Many storage systems, however, are not well matched to the workloads they service due to the difficulty of configuring the storage system optimally a priori with only approximate knowledge of the workload characteristics. This paper shows how cloud-based orchestration can be leveraged to create flexible storage solutions that use continuous adaptation to tailor themselves to their target application workloads, and in doing so, provide superior performance, cost, and scalability over traditional fixed designs. To demonstrate this approach, we have built "SuperCell," a Ceph-based distributed storage solution with a recommendation engine for the storage configuration. SuperCell provides storage operators with real-time recommendations on how to reconfigure the storage system to optimize its performance, cost, and efficiency based on statistical storage modeling and data analysis of the actual workload. Using real cloud storage workloads, we experimentally demonstrate that SuperCell reduces the cost of storage systems by up to 48%, while meeting service level agreement (SLA) 99% of the time, a level that any static design fails to meet for the workloads.

A multi-site, distributed storage system deployment is frequently needed for disaster recovery. Traditional master-slave backup/restore solutions have their limitations and cannot meet the high data durability, system availability, and low latency required in many use cases. Software-defined storage (SDS) achieves flexibility, scalability, and cost-effectiveness through disaggregation of storage hardware from software and enables innovations in storage architectures. The open-source SDS Ceph solution can be used to build storage systems with high reliability using a disaster recovery (DR) configuration among multiple sites while maintaining cost-effectiveness. However, using multi-site erasure coding has the potential issue of longer read latency because of communication delays caused by data chunks distributed among multiple sites. This paper proposes location-conscious, multi-site erasure-coded Ceph storage that achieves both high reliability and lower read latency - even for sites that are geographically distant from each other. The investigation was conducted using a Ceph tool to confirm localities with the proposed Ceph CRUSH map, and experiments were conducted to evaluate I/O traffic to validate the proposed hypothesis. Our results show that the proposed location-conscious multi-site erasure-coded storage can be implemented in Ceph with both high reliability and low latency.

Erasure codes are widely used in distributed storage systems since they provide space-optimal data redundancy to protect against data loss. Despite recent progress on quantifying average service latency when erasure codes are employed, there is very little work on providing differentiated latency among multiple tenants that may have different latency requirements. This paper proposes a novel framework for providing and optimizing differentiated latency in erasure-coded storage by investigating two policies, weighted queue and priority queue, for scheduling tenant requests. For both policies, we quantify service latency for different tenant classes for homogeneous files with arbitrary placement and service time distributions. We develop an optimization framework that jointly minimizes differentiated latency over three decision spaces: 1) data placement; 2) request scheduling; and 3) resource management. Efficient algorithms harnessing bipartite matching and convex optimization techniques are developed to solve the proposed optimization. Our solution enables elastic service-level agreements to meet heterogeneous application requirements. We further prototype our solution with both queuing models applied in an open-source, cloud storage deployment that simulates three geographically distributed data centers through bandwidth reservations. Experimental results validate our theoretical delay analysis and show significant joint latency reduction for different classes of files, providing valuable insights into service differentiation and elastic quality of service in erasure-coded storage systems.

Modern distributed storage systems often use erasure codes to protect against disk and node failures to increase reliability, while trying to meet the latency requirements of the applications and clients. Storage systems may have caches at the proxy or client ends in order to reduce the latency. In this paper, we consider a novel caching framework with erasure code called functional caching. Functional caching involves using erasure-coded chunks in the cache such that the code formed by the chunks in storage nodes and cache combined are maximal-distance-separable erasure codes. Based on the arrival rates of different files, placement of file chunks on the servers, and the service time distribution of storage servers, an optimal functional caching placement and the access probabilities of the file request from different disks are considered. The proposed algorithm gives significant latency improvement in both simulations and a prototyped solution in an open-source, cloud storage deployment.

The rapid growth of data traffic in storage systems has put a significant burden on the underlying networks of cloud storage systems. Historically, a key solution to relieve this traffic burden is caching [1]. Many companies have adopted erasure-coded storage systems. However, caching for data centers when the files are encoded with an erasure code has not been studied to the best of our knowledge. This paper proposes a new functional caching approach called Sprout that can efficiently capitalize on existing file coding in erasure-coded storage systems. In contrast to exact caching that stores chunks identical to original copies, our functional caching approach forms d new data chunks, which together with the existing n chunks satisfy the property of being an (n + d, k) MDS code. Thus, the file can now be recovered from any out of n + d chunks (rather than k out of n under exact caching), effectively extending coding redundancy, as well system diversity for scheduling file access requests. The proposed functional caching approach saves latency due to more flexibility to obtain k-d chunks from the storage system a very minimal additional computational cost of creating the coded cached chunks. While quantifying service latency erasure-coded storage systems is an open problem, we generalize previous results on probabilistic scheduling policy [2,3] that distributes file requests to cache and storage nodes with optimized probabilities, and derive a closed-form upper bound on mean service latency for the proposed functional caching approach.

Modern distributed storage systems offer large capacity to satisfy the exponentially increasing need of storage space. They often use erasure codes to protect against disk and node failures to increase reliability, while trying to meet the latency requirements of the applications and clients. This paper provides an insightful upper bound on the average service delay of such erasure-coded storage with arbitrary service time distribution and consisting of multiple heterogeneous files. Not only does the result supersede known delay bounds that only work for a single file or homogeneous files, it also enables a novel problem of joint latency and storage cost minimization over three dimensions: selecting the erasure code, placement of encoded chunks, and optimizing scheduling policy. The problem is efficiently solved via the computation of a sequence of convex approximations with provable convergence. We further prototype our solution in an open-source cloud storage deployment over three geographically distributed data centers. Experimental results validate our theoretical delay analysis and show significant latency reduction, providing valuable insights into the proposed latency-cost tradeoff in erasure-coded storage.

This paper proposes an approach to minimize service latency in a data center network where erasure-coded files are stored on distributed disks/racks and access requests are scattered across the network. Due to limited bandwidth available at both top-of-the-rack and aggregation switches, network bandwidth must be apportioned among different intra-and inter-rack data flows in line with their traffic statistics. We formulate this problem as weighted queuing and employ a class of probabilistic request scheduling policies to derive a closed-form outer-bound of service latency for erasure-coded storage with arbitrary file access patterns and service time distributions. The result enables us to propose a joint latency optimization over three entangled "control knobs": the bandwidth allocation at top-of-the-rack and aggregation switches, the probabilities for scheduling file requests, and the placement of encoded file chunks, which affects data locality. The joint optimization is shown to be a mixed-integer problem. We develop an iterative algorithm which decouples and solves the joint optimization as three sub-problems, which are either convex or solvable via bipartite matching in polynomial time. The proposed algorithm is prototyped in an open-source, distributed file system, Tahoe, and evaluated on a cloud tested with 16 separate physical hosts in an Open Stack cluster. Experiments validate our theoretical latency analysis and show significant latency reduction for diverse file access patterns. The results provide valuable insight on designing low-latency data center networks with erasure-coded storage.

The effect of coding on content retrieval latency in data center storage system is drawing more and more significant attention these days, and customizing elastic service latency for the tenants is undoubtedly appealing to cloud storage, but it also comes with great technical challenges: due to the lack of analytic latency models for erasure-coded storage, most of the literature is limited to the analysis of average service latency, e.g., [1], [2], having assumptions like homogeneous files, exponential service time distribution [3], fixed erasure codes [4], which is unsuitable for a multi-tenant cloud environment where each tenant has a different latency requirement for accessing files in an erasure-coded, online cloud storage. Optimizing differentiated service delay in an erasure-coded storage system is an open problem. This work considers an erasure-coded storage with multiple tenants and differentiated delay demands, studies two types of service policies, non-preemptive priority queue and weighted queue, quantifying service latency of these policies, propose a novel optimization framework that provides differentiated service latency to meet heterogeneous application requirements in cloud storage.

The reliability of erasure-coded distributed storage systems, as measured by the mean time to data loss (MTTDL), depends on the repair bandwidth of the code. Repair-efficient codes provide reliability values several orders of magnitude better than conventional erasure codes. Current state of the art codes fix the number of helper nodes (nodes participating in repair) a priori. In practice, however, it is desirable to allow the number of helper nodes to be adaptively determined by the network traffic conditions. In this work, we propose an opportunistic repair framework to address this issue. It is shown that there exists a threshold on the storage overhead, below which such an opportunistic approach does not lose any efficiency from the optimal storage-repair-bandwidth tradeoff; i.e. it is possible to construct a code simultaneously optimal for different numbers of helper nodes. We further examine the benefits of such opportunistic codes, and derive the MTTDL improvement for two repair models: one with limited total repair bandwidth and the other with limited individual-node repair bandwidth. In both settings, we show orders of magnitude improvement in MTTDL. Finally, the proposed framework is examined in a network setting where a significant improvement in MTTDL is observed.

The demand for cloud storage is exploding as an ever increasing number of enterprises and consumers are storing and processing their data in the cloud. Hence, distributed object storage solutions (e.g., QFS, Swift, HDFS) are becoming very critical components of any cloud infrastructure. These systems are able to offer good reliability by distributing redundant information across a large number of commodity servers, making it possible to achieve 10 nines and beyond with relative ease. One drawback of these systems is that they are usually designed for deployment within a single data center, where node-to-node latencies are small. Geo-replication (i.e., distributing redundant information across data centers) for most open-source storage systems is, to the best of our knowledge, accomplished by asynchronously mirroring a given deployment. Given that geo-replication is critical for ensuring very high degrees of reliability (e.g., for achieving 16 nines), in this work we evaluate how these storage systems perform when they are directly deployed in a WAN setting. To this end, three popular distributed object stores, namely Quantcast-QFS, Swift and Tahoe-LAFS, are considered and tested in a three-wide data center environment and our findings are reported.

Smartphones are excellent mobile sensing platforms, with the microphone in particular being exercised in several audio inference applications. We take smartphone audio inference a step further and demonstrate for the first time that it's possible to accurately estimate the number of people talking in a certain place -- with an average error distance of 1.5 speakers -- through unsupervised machine learning analysis on audio segments captured by the smartphones. Inference occurs transparently to the user and no human intervention is needed to derive the classification model. Our results are based on the design, implementation, and evaluation of a system called Crowd++, involving 120 participants in 10 very different environments. We show that no dedicated external hardware or cumbersome supervised learning approaches are needed but only off-the-shelf smartphones used in a transparent manner. We believe our findings have profound implications in many research fields, including social sensing and personal wellbeing assessment.

The explosive growth of cellular traffic and its highly dynamic nature often make it increasingly expensive or even infeasible for a cellular service provider to provision enough cellular resources to support the peak traffic demands. Some service providers have started exploring various economic incentives, including smart data pricing, to manage network congestion. We present SpeedGate, a smart mobile data pricing testbed that allows a service provider to experiment with different dynamic pricing strategies. SpeedGate maintains persistent VPN connections to smartphones as users roam between different wireless networks (3G, 4G/LTE, WiFi). The maximum available bandwidth per user session can be adjusted according to various data pricing strategies. We report preliminary results on two trials with a total of 29 users for assessing their willingness to pay (WTP) for various speed tiers. Preliminary observations suggest the challenges of QoS guarantees through speed tiers in the field, the limited dynamic range of WTP values from individual users for different speed tiers, and potential opportunities for auction-based dynamic pricing.

We propose a system that makes opportunistic use of mobile computing devices and ad hoc networking to provide a transient storage service to clients in a localized geographical region. The main challenge is to offset the potential data loss caused by node mobility with internode communication. We first argue on the basis of simulation and theory that such a service is feasible, given a sufficiently high density of mobile devices. A distributed communication and storage protocol is then presented for situations where all mobile devices are within communication range of each other, and it is shown through testbed experiments and simulation that the protocol operates correctly and makes efficient use of storage space and communication bandwidth, while maximizing the longevity of stored data.

To address network congestion issues, network providers are seeking to shape consumer's usage behavior through economic incentives such as a tiered pricing scheme and/or restrictions on unlimited data plans. Current pricing schemes, however, do not ad- dress the congestion problem directly: the prices differentiation is based on the data volume consumed by the user in a month whereas the congestion is a consequence of the availability of limited bandwidth resources (consumption speed). Furthermore, users subscribing to a costlier plan receive no real- time (higher bandwidth) priority. This paper pro- poses an alternate pricing plan for wireless networks based on Generalized Second Price (GSP) auctions with the aim of improving welfare. Our simulation- based analysis reveals that such a pricing scheme allows users with higher willingness to pay to secure higher throughput of service, without significantly sacrificing the overall system throughput or fairness.

GeoTV is a project that explores seamless integration of mobile phones, HDTV sets, and computers in the living room to enrich the user experience of existing services. The three- screen service allows a user to navigate a world map on a smart phone to track geo-located media RSS content that matches her personal interests. The user can show a matching video clip on her phone or direct a nearby HDTV set to play the video. In addition, the user can bring up a world map on a nearby computer screen to navigate areas of interest related to the video clip. GeoTV allows all three screens to be used for what they are best for: HDTV for high resolution video, computer screen for browsing a world map, and a smart phone for personalized control at hand to select media of interest.

Recent advances in P2P technology have made it a viable alternative for the delivery of rich media by both content and service providers. However, to better understand and utilize P2P technologies in building a scalable media distribution platform, the nature of the underlying network must be taken into consideration. Although many P2P simulations have been conducted previously, very few were evaluated on a real P2P testbed with the properties of the physical network in mind. In this paper, we describe VP2P, a virtual machine-based P2P testbed, which supports P2P studies with the consideration of typical service provider networks. We use four fully equipped MacPro's to emulate 32 peers in the current implementation. Experiments of three P2P algorithms for video on demand (VoD) services: BitTorrent, Toast, and Zebra, were run on the testbed. We discuss the rationales behind the hardware and software architecture of VP2P, report our results, and conclude with lessons learned and future directions for VM-based testbeds.

P2P file transfers and streaming have already seen a tremendous growth in Internet applications. With the rapid growth of IPTV, the need to efficiently disseminate large volumes of Video-on-Demand (VoD) content has prompted IPTV service providers to consider peer-assisted VoD content delivery. This paper describes Zebroid, a VoD solution that uses IPTV operational data on an on-going basis to determine how to pre-position popular contents in customer set-top boxes during idle hours to allow these peers to assist the VoD server in content delivery during peak hours. Latest VoD request distribution, set-top box availability, and capacity data on network components are all taken into consideration in determining the parameters used in the striping algorithm of Zebroid. We show both by simulation and emulation on a realistic IPTV testbed that the VoD server load can be significantly reduced by more than 50-80% during peak hours by using Zebroid.

This paper investigates a novel concept of providing seamless control and portability of an IPTV viewing session. A solution employing a middleware system, a secure hardware token and a cell phone are used to demonstrate how an IPTV session can be securely controlled remotely and moved between multiple viewing stations. We have built a prototype of the system and demonstrated its flexible features. Depending on the user's protocol of choice, most remote control operations from a mobile device took less than 5 seconds to execute. An interesting capability of previewing content of other channels via the user's device while still continuing to watch the program on the viewing station differentiates it from today's IPTV offers. Finally for mobile content delivery, we address the problem of dynamic device profile selection and content adaptation using a classification algorithm to match the best content alternative destined for a mobile.

The Web is rapidly moving towards a platform for mass collaboration in content production and consumption from three screens: computers, mobile phones, and TVs. While there has been a surge of interests in making Web content accessible from mobile devices, there is a significant lack of progress when it comes to making the web experience suitable for viewing on a television. Towards this end, we describe a novel concept, namely GeoTV, where we explore a framework by which web content can be presented or pushed in a meaningful manner to create an entertainment experience for the TV audience. Fresh content on a variety of topics, people, and places is being created and made available on the Web at breathtaking speed. Navigating fresh content effectively on TV demands a new browsing paradigm that requires fewer mouse clicks or user interactions from the remote control. Novel geospatial and temporal browsing techniques are provided in GeoTV that allow users the capability of aggregating and navigating RSS-enabled content in a timely, personalized and automatic manner for viewing in an IPTV environment. This poster is an extension of our previous work on GeoTracker that utilizes both a geospatial representation and a temporal (chronological) presentation to help users spot the most relevant updates quickly within the context of a Web-enabled environment. We demonstrate 1) the usability of such a tool that greatly enhances a user.s ability in locating and browsing videos based on his or her geographical interests and 2) various innovative interface designs for showing RSS-enabled information in an IPTV environment.

The Web is rapidly moving towards a platform for mass collaboration in content production and consumption. Fresh content on a variety of topics, people, and places is being created and made available on the Web at breathtaking speed. Navigating the content effectively not only requires techniques such as aggregating various RSS-enabled feeds, but it also demands a new browsing paradigm. In this paper, we present novel geospatial and temporal browsing techniques that provide users with the capability of aggregating and navigating RSS-enabled content in a timely, personalized and automatic manner. In particular, we describe a system called GeoTracker that utilizes both a geospatial representation and a temporal (chronological) presentation to help users spot the most relevant updates quickly. Within the context of this work, we provide a middleware engine that supports intelligent aggregation and dissemination of RSS feeds with personalization to desktops and mobile devices. We study the navigation capabilities of this system on two kinds of data sets, namely, 2006 World Cup soccer data collected over two months and breaking news items that occur every day. We also demonstrate that the application of such technologies to the video search results returned by YouTube and Google greatly enhances a user.s ability in locating and browsing videos based on his or her geographical interests. Finally, we demonstrate that the location inference performance of GeoTracker compares well against machine learning techniques used in the natural language processing/information retrieval community. Despite its algorithm simplicity, it preserves high recall percentages.

This paper studies the conditions under which P2P sharing can increase the capacity of IPTV services over FTTN networks. For a typical FTTN network, our study shows a) P2P sharing is not beneficial when the total traffic in a local video office is low; b) P2P sharing increases the load on FTTN switches and routers in local video offices; c) P2P sharing is the most beneficial when the network bottleneck is experienced in the southbound segment of a local video office (equivalently a northbound segment of an FTTN switch); and d) sharing among all FTTN serving communities is not needed when network congestion problems are solved by using some other technologies such as program pre-caching or replication. Based on the analytical results, design for IPTV services which monitors FTTN network conditions and decides when and how to share videos among peers to maximize the service capacity. Simulations and bounds both validate the potential benefits of the MediaGrid IPTV service platform.

An electronic payment system ideally should provide security, anonymity, fairness, transferability and scalability. Existing payment schemes often lack either anonymity or scalability. In this paper we propose WhoPay, a peer-topeer payment system that provides all the above properties. For anonymity, we represent coins with public keys; for scalability, we distribute coin transfer load across all peers, rather than rely on a central entity such as the broker. This basic version of WhoPay is as secure and scalable as existing peer-to-peer payment schemes, while providing a much higher level of user anonymity. We also introduce the idea of real-time double spending detection by making use of distributed hash tables (DHT). Simulation results show that the majority of the system load is handled by the peers under typical peer availability, indicating that WhoPay should scale well.

Media consumers who are overwhelmed by multitudinous news content demand a system that would sift through tens or hundreds of broadcast TV channels on a daily basis to capture the most important clips that match users' interests and deliver these personalized clips for easy viewing on a typical TV or home PC. In this paper, we present a personal media alert system that extracts video segments for the interested users. In addition, alerts with pointers to content stored on the home server can be sent to mobile users who are authorized to access the content at home. To make content sharing feasible and scalable, we also propose a P2P payment scheme that would allow a consumer to have access to media clips aggregated on other consumers' personal media systems

We present a system for automatic monitoring and timely dissemination of multimedia information to a range or mobile information appliances based on each user's interest profile. Multimedia processing algorithms detect and isolate relevant video segments from over twenty television broadcast programs based on a collection or words and phrases specified by the user. Content repurposing techniques are then used to convert the information into a form that is suitable for delivery to the user's mobile devices. Alerts are sent using a number of application messaging and network access protocols including email, short message service (SMS), multimedia messaging service (MMS), voice, session initiation protocol (SIP), fax, and pager protocols. The system is evaluated with respect to performance and user experiences. The MediaAlert system provides an effective and low-cost solution for the timely generation of alerts containing personal, business, and security information.

In this paper we address the research issues in providing personalized multimedia services, which enable a mobile user to remotely record video programs, control cameras, and request the delivery of pre-recorded or live video content to his or her own mobile device. We describe a mobile service platform that authenticates users who send service requests from various mobile devices, transcodes video content based on user and device profiles, and authorizes the delivery of content from a media server to the proper client device. The media server adapts automatically to the fluctuations of the wireless channel conditions for reasonable viewing on the client device. The mobile service platform essentially manages the control path, while the media server handles the actual content delivery. We discuss various aspects of the integration and report our successful experiments conducted on wireless LAN and CDPD networks.

Article Free Access Share on CHIME: customizable hyperlink insertion and maintenance engine for software engineering environments Authors: P. Devanbu Dept. of Computer Science, University of California, Davis, CA Dept. of Computer Science, University of California, Davis, CAView Profile , Y.-F. Chen AT&T Labs-Research, 190, Park Drive, Florham Park, NJ AT&T Labs-Research, 190, Park Drive, Florham Park, NJView Profile , E. Gansner AT&T Labs-Research, 190, Park Drive, Florham Park, NJ AT&T Labs-Research, 190, Park Drive, Florham Park, NJView Profile , H. Müller Dept. Of Computer Science, University of Victoria, Victoria, BC Dept. Of Computer Science, University of Victoria, Victoria, BCView Profile , J. Martin Dept. Of Computer Science, University of Victoria, Victoria, BC Dept. Of Computer Science, University of Victoria, Victoria, BCView Profile Authors Info & Claims ICSE '99: Proceedings of the 21st international conference on Software engineeringMay 1999 Pages 473–482https://doi.org/10.1145/302405.302679Published:16 May 1999Publication History 17citation305DownloadsMetricsTotal Citations17Total Downloads305Last 12 Months20Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Software systems are typically modified in order to extend or change their functionality, improve their performance, port them to different platforms, and so on. For developers, it is crucial to understand the structure of a system before attempting to modify it. The structure of a system, however, may not be apparent to new developers, because the design documentation is non-existent or, worse, inconsistent with the implementation. This problem could be alleviated if developers were somehow able to produce high-level system decomposition descriptions from the low-level structures present in the source code. We have developed a clustering tool called Bunch that creates a system decomposition automatically by treating clustering as an optimization problem. The paper describes the extensions made to Bunch in response to feedback we received from users. The most important extension, in terms of the quality of results and execution efficiency, is a feature that enables the integration of designer knowledge about the system structure into an otherwise fully automatic clustering process. We use a case study to show how our new features simplified the task of extracting the subsystem structure of a medium size program, while exposing an interesting design flaw in the process.

A software repository provides a central information source for understanding and reengineering code in a software project. Complex reverse engineering tools can be built by analyzing information stored in the repository without reparsing the original source code. The most critical design aspect of a repository is its data model, which directly affects how effectively the repository supports various analysis tasks. This paper focuses on the design rationales behind a data model for a C++ software repository that supports reachability analysis and dead code detection at the declaration level. These two tasks are frequently needed in large software projects to help remove excess software baggage, select regression tests and support software reuse studies. The language complexity introduced by class inheritance, friendship, and template instantiation in C++ requires a carefully designed model to catch all necessary dependencies for correct reachability analysis. We examine the major design decisions and their consequences in our model and illustrate how future software repositories can be evaluated for completeness at a selected abstraction level. Examples are given to illustrate how our model also supports variants of reachability analysis: impact analysis, class visibility analysis, and dead code detection. Finally, we discuss the implementation and experience of our analysis tools on a few C++ software projects.

Programmers frequently have to retrieve and link information from various software documents to accomplish a maintenance task. Ciao is a graph-based navigator that helps programmers query and browse structural connections embedded in different software and document repositories. A repository consists of a collection of source documents with an associated database that describes their structure. Ciao supports repositories organized in an architecture style called Aero, which exploits the duality between a class of entity-relationship (ER) databases and directed attributed graphs (DAG). Database queries and graph analysis operators in Aero are plug-compatible because they all take an ER database and produce yet another ER database by default. Various presentation filters generate graph views, source views, and relational views from any compatible ER database. The architecture promotes the construction of successively more complex operators using a notion of virtual database pipelines. Ciao has been instantiated for C and C++ program databases, and program difference databases. The latter allows programmers to explore program structure changes by browsing and expanding graphs that highlight changed, deleted, and added entities and relationships. The unifying ER model under ciao also allows users to navigate different software repositories and make necessary connections. We have linked program difference databases and modification request (MR) databases so that users can investigate the connections between MRs and affected entities. Ciao has been applied to several large communications software projects and we report experiences and lessons learned from these applications.

A system for analyzing program structures is described. The system extracts relational information from C programs according to a conceptual model and stores the information in a database. It is shown how several interesting software tasks can be performed by using the relational views. These tasks include generation of graphical views, subsystem extraction, program layering, dead code elimination and binding analysis.>