bluuebunny/crossref_metadata_2025 huggingface dataset:
COST SIMULATION AND PERFORMANCE OPTIMIZATION OF WEB-BASED APPLICATIONS ON MOBILE CHANNELS
Authors: BOOK MATTHIAS , GRUHN VOLKER , HÜLDER MALTE , KÖHLER ANDRÉ , KRIEGEL ANDREAS
Published: October 2006

When considering the addition of a mobile presentation channel to an existing web-based application, a key question that has to be answered even before development begins is how the mobile channel's characteristics will impact the user experience and the cost of using the application. If either of these factors is outside acceptable limits, economical considerations may forbid adding the channels, even if it would be feasible from a purely technical perspective. Both of these factors depend considerably on two metrics: The time required to transmit data over the mobile network, and the volume transmitted.

The PETTICOAT method presented in this paper uses the dialog flow model and web server log files of an existing application to identify typical interaction sequences and to compile volume statistics, which are then run through a tool that simulates the volume and time that would be incurred by executing the interaction sequences on a mobile channel. From the simulated volume and time data, we can then calculate the cost of accessing the application on a mobile channel, and derive suitable approaches for optimizing cost and response times.
Symmetry in temporal logic model checking
Authors: Miller Alice , Donaldson Alastair , Calder Muffy
Published: October 2006

Temporal logic model checking involves checking the state-space of a model of a system to determine whether errors can occur in the system. Often this involves checking symmetrically equivalent areas of the state-space. The use of symmetry reduction to increase the efficiency of model checking has inspired a wealth of activity in the area of model checking research. We provide a survey of the associated literature.
Implementing sorting in database systems
Authors: Graefe Goetz
Published: October 2006

Most commercial database systems do (or should) exploit many sorting techniques that are publicly known, but not readily available in the research literature. These techniques improve both sort performance on modern computer systems and the ability to adapt gracefully to resource fluctuations in multiuser operations. This survey collects many of these techniques for easy reference by students, researchers, and product developers. It covers in-memory sorting, disk-based external sorting, and considerations that apply specifically to sorting in database systems.
MYSQ:
Authors: Tokuhisa Satoru , Okubo Susuke , Suguro Ken , Kotabe Taku , Inakage Masa
Published: October 2006

This article is a description of MYSQ, an entertainment system that allows users to create original music video clips (ex:MTV) and share the resulting video with friends via cellular phones. The original movie is original because it is generated using video of the user, combined with video effects that use the user's dance movements as parameters. The MYSQ concept is communication through the process as well as the product of content creation. The MYSQ system can be characterized as: simple operation, multilayered interaction, collaboration, the conversion from player experience to content, and making experience transferable by converting it to media form. This article will then analyze the system with game flow, based on Csikszentmihalyi's FLOW theory, to evaluate the system's entertainment value as a game, and the effectiveness of the characteristics above.
A translational BNF grammar notation (TBNF)
Authors: Mann Paul B
Published: October 2006

BNF grammar notation came into existence about 1960 for the specification of programming languages. It was first used for the automatic generation of parsers about 1972. BNF was later replaced with EBNF offering regular expression notation in the right side of grammar rules. EBNF is powerful, however, it describes only the recognition phase, which is only 1/3 of the process of language translation. The second phase is the construction of an abstract-syntax tree and the third phase is the creation of an instruction code sequence. Some parser generators automate the construction of an AST, but none, that I know of, automate the output of instruction codes. Certainly if these second and third phases are to be automated, a suitable notation is required in the grammar. This paper proposes a notation that permits the construction of the AST in the correct order and the creation of instruction codes. In effect, the complete translation process can be described in the grammar and correct translators generated automatically. A working system has been implemented and tested with good results. The generator is called LRgen and the new grammar notation is called TBNF.
Dusty caches for reference counting garbage collection
Authors: Friedman Scott , Krishnamurthy Praveen , Chamberlain Roger , Cytron Ron K. , Fritts Jason E.
Published: October 2006

Reference counting is a garbage-collection technique that maintains a per-object count of the number of pointers to that object. When the count reaches zero, the object must be dead and can be collected. Although it is cannot detect all garbage on its own, it is well suited for some applications and is implemented typically in conjunction with other methods to increase overall precision. A disadvantage of reference counting is the extra storage traffic that is introduced. In this paper, we describe a new cache write-back policy that can substantially decrease the reference-counting traffic to RAM.We investigate a cache design that takes advantage of temporally silent stores, by remebering the first-fetched value of a cache subblock, so that the subblock need not be written back to RAM unless a different value is present. We present results from experiments that show the effectiveness of this approach, particularly in mitigating the storage traffic due to reference counting.
Analysis of embedded video coder systems
Authors: Bardine Alessandro , Bechini Alessio , Foglia Pierfrancesco , Prete Cosimo Antonio
Published: October 2006

Because of the increasing complexity of embedded systems, the related design process is becoming more and more complex and time-consuming. In this setting, the employment of standard tools and methodologies could significantly support designers in reducing time to market as well. In this paper we present our experience in the design space exploration for devices based on H.264 video coders. Despite of the inevitable inaccuracies due to the adoption of a system-level approach, the overall methodology has shown to be suitable to properly point out the most convenient architectural solutions by means of fast, high level simulation.
Developing scientific workflows from heterogeneous services
Authors: Tsalgatidou A. , Athanasopoulos G. , Pantazoglou M. , Pautasso C. , Heinis T. , Grønmo R. , Hoff Hjørdis , Berre Arne-Jørgen , Glittum M. , Topouzidou S.
Published: October 2006

Scientific WorkFlows (SWFs) need to utilize components and applications in order to satisfy the requirements of specific workflow tasks. Technology trends in software development signify a move from component-based to service-oriented approach, therefore SWF will inevitably need appropriate tools to discover and integrate heterogeneous services. In this paper we present the SODIUM platform consisting of a set of languages and tools as well as related middleware, for the development and execution of scientific workflows composed of heterogeneous services.
The Invisible Assistant
Authors: Borriello Gaetano
Published: October 2006

Ubiquitous computing seeks to place computers everywhere around us—into the very fabric of everyday life1—so that our lives are made better. Whether it is improving our job productivity, our ability to stay connected with family and friends, or our entertainment, the goal is to find ways to put technology to work for us by getting all those computers—large and small, visible and invisible—to work together. Since Mark Weiser presented the ubiquitous computing vision in 1991, we have made significant progress in creating faster, smaller, and lower-power computing devices.We have just barely begun, however, to tackle the problem of how we get these devices to interact effectively with us and with each other.
Probabilistic parsing strategies
Authors: Nederhof Mark-Jan , Satta Giorgio
Published: October 2006

We present new results on the relation between purely symbolic context-free parsing strategies and their probabilistic counterparts. Such parsing strategies are seen as constructions of push-down devices from grammars. We show that preservation of probability distribution is possible under two conditions, viz. the correct-prefix property and the property of strong predictiveness. These results generalize existing results in the literature that were obtained by considering parsing strategies in isolation. From our general results, we also derive negative results on so-called generalized LR parsing.
Radial addressing of nanowires
Authors: Savage John E. , Rachlin Eric , DeHon André , Lieber Charles M. , Wu Yue
Published: October 2006

We introduce radial encoding of nanowires (NWs), a new method of differentiating and controlling NWs by a small set of mesoscale wires for use in crossbar memories. We describe methods of controlling these NWs and give efficient manufacturing algorithms. These new encoding and decoding methods do not suffer from the misalignment characteristic of flow-aligned NWs. They achieve comparable effective pitch and resulting memory density with axially encoded NWs, while avoiding potential cases of address ambiguity and simplifying NW preparation. We also explore hybrid axial/radial encodings and show that they offer no net benefit over pure codes.
Comprehending software correctness implies comprehending an intelligence-related limitation
Authors: Charlesworth Arthur
Published: October 2006

This article applies mathematical logic to obtain a rigorous foundation for previous inherently nonrigorous results and also extends those previous results. Roughly speaking, our main theorem states: any agent A that comprehends the correctness-related properties of software
S
also comprehends an intelligence-related limitation of
S
. The theorem treats the output of
S
, if any, as an attempt at solving a halting problem. Previous nonrigorous attempts to obtain similar theorems depend on infallibility assumptions on both the agent and the software. The hypothesis that intelligent agents and intelligent software must be infallible has been widely questioned. In addition, recent work by others has determined that well-known previous attempts use a fallacious form of reasoning; that is, the same form of reasoning can yield paradoxical results. Our main theorem avoids infallibility assumptions on both the agent and the software. In addition, our proof is rigorous, in the sense that in principle one can carry it out in Zermelo-Fraenkel set theory. The software correctness framework considered in the main theorem is that of Hoare logic.
Decentralized energy-conserving and coverage-preserving protocols for wireless sensor networks
Authors: Huang Chi-Fu , Lo Li-Chu , Tseng Yu-Chee , Chen Wen-Tsuen
Published: October 2006

In this article, we propose several decentralized protocols that schedule sensors' active and sleeping periods to prolong the network lifetime while maintain the sensing field sufficiently covered. The proposed protocols are based on a model similar to that of Yan et al. [2003], but improve its results in several senses. First, our approach can significantly reduce the computational complexity incurred, and at the same time achieve better accuracy in determining the coverage of the sensing area. Second, we extend the result such that it can support multilayer coverage of the sensing field. Third, we further enhance it [Yan et al. 2003] by proposing several optimization mechanisms to balance or reduce sensors' energy expenditure.
Using MEMS-based storage in computer systems---device modeling and management
Authors: Hong Bo , Brandt Scott A. , Long Darrell D. E. , Miller Ethan L. , Lin Ying
Published: October 2006

MEMS-based storage is an emerging nonvolatile secondary storage technology. It promises high performance, high storage density, and low power consumption. With fundamentally different architectural designs from magnetic disk, MEMS-based storage exhibits unique two-dimensional positioning behaviors and efficient power state transitions. We model these low-level, device-specific properties of MEMS-based storage and present request scheduling algorithms and power management strategies that exploit the full potential of these devices. Our simulations show that MEMS-specific device management policies can significantly improve system performance and reduce power consumption.
On incremental file system development
Authors: Zadok Erez , Iyer Rakesh , Joukov Nikolai , Sivathanu Gopalan , Wright Charles P.
Published: October 2006

Developing file systems from scratch is difficult and error prone. Using layered, or stackable, file systems is a powerful technique to incrementally extend the functionality of existing file systems on commodity OSes at runtime. In this article, we analyze the evolution of layering from historical models to what is found in four different present day commodity OSes: Solaris, FreeBSD, Linux, and Microsoft Windows. We classify layered file systems into five types based on their functionality and identify the requirements that each class imposes on the OS. We then present five major design issues that we encountered during our experience of developing over twenty layered file systems on four OSes. We discuss how we have addressed each of these issues on current OSes, and present insights into useful OS and VFS features that would provide future developers more versatile solutions for incremental file system development.
Fast additions on masked integers
Authors: Adams Michael D. , Wise David S.
Published: October 2006

Suppose the bits of a computer word are partitioned into
d
disjoint sets, each of which is used to represent one of a
d
-tuple of cartesian indices into
d
-dimensional space. Then, regardless of the partition, simple group operations and comparisons can be implemented for each index on a conventional processor in a sequence of two or three register operations.These indexings allow any blocked algorithm from linear algebra to use some non-standard matrix orderings that increase locality and enhance their performance. The underlying implementations were designed for alternating bit postitions to index Morton-ordered matrices, but they apply, as well, to any bit partitioning. A hybrid ordering of the elements of a matrix becomes possible, therefore, with row-/column-major ordering within cache-sized blocks and Morton ordering of those blocks, themselves. So, one can enjoy the temporal locality of nested blocks, as well as compiler optimizations on row- or column-major ordering in base blocks.
A new top-down parsing algorithm to accommodate ambiguity and left recursion in polynomial time
Authors: Frost Richard A. , Hafiz Rahmatullah
Published: October 2006

Top-down backtracking language processors are highly modular, can handle ambiguity, and are easy to implement with clear and maintainable code. However, a widely-held, and incorrect, view is that top-down processors are inherently exponential for ambiguous grammars and cannot accommodate left-recursive productions. It has been known for many years that exponential complexity can be avoided by memoization, and that left-recursive productions can be accommodated through a variety of techniques. However, until now, memoization and techniques for handling left recursion have either been presented independently, or else attempts at their integration have compromised modularity and clarity of the code.
A Gracefully Degrading and Energy-Efficient Modular Router Architecture for On-Chip Networks
Authors: Kim Jongman , Nicopoulos Chrysostomos , Park Dongkook , Narayanan Vijaykrishnan , Yousif Mazin S. , Das Chita R.
Published: October 2006

Packet-based on-chip networks are increasingly being adopted in complex System-on-Chip (SoC) designs supporting numerous homogeneous and heterogeneous functional blocks. These Network-on-Chip (NoC) architectures are required to not only provide ultra-low latency, but also occupy a small footprint and consume as little energy as possible. Further, reliability is rapidly becoming a major challenge in deep sub-micron technologies due to the increased prominence of permanent faults resulting from accelerated aging effects and manufacturing/testing challenges. Towards the goal of designing low-latency, energy efficient and reliable on-chip communication networks, we propose a novel fine-grained modular router architecture. The proposed architecture employs decoupled parallel arbiters and uses smaller crossbars for row and column connections to reduce output port contention probabilities as compared to existing designs. Furthermore, the router employs a new switch allocation technique known as "Mirroring Effect" to reduce arbitration depth and increase concurrency. In addition, the modular design permits graceful degradation of the network in the event of permanent faults and also helps to reduce the dynamic power consumption. Our simulation results indicate that in an 8 × 8 mesh network, the proposed architecture reduces packet latency by 4-40% and power consumption by 6-20% as compared to two existing router architectures. Evaluation using a combined performance, energy and fault-tolerance metric indicates that the proposed architecture provides 35-50% overall improvement compared to the two earlier routers.
A Case for MLP-Aware Cache Replacement
Authors: Qureshi Moinuddin K. , Lynch Daniel N. , Mutlu Onur , Patt Yale N.
Published: October 2006

Performance loss due to long-latency memory accesses can be reduced by servicing multiple memory accesses concurrently. The notion of generating and servicing long-latency cache misses in parallel is called Memory Level Parallelism (MLP). MLP is not uniform across cache misses - some misses occur in isolation while some occur in parallel with other misses. Isolated misses are more costly on performance than parallel misses. However, traditional cache replacement is not aware of the MLP-dependent cost differential between different misses. Cache replacement, if made MLP-aware, can improve performance by reducing the number of performance-critical isolated misses. This paper makes two key contributions. First, it proposes a framework for MLP-aware cache replacement by using a runtime technique to compute the MLP-based cost for each cache miss. It then describes a simple cache replacement mechanism that takes both MLP-based cost and recency into account. Second, it proposes a novel, low-hardware overhead mechanism called Sampling Based Adaptive Replacement (SBAR), to dynamically choose between an MLP-aware and a traditional replacement policy, depending on which one is more effective at reducing the number of memory related stalls. Evaluations with the SPEC CPU2000 benchmarks show that MLP-aware cache replacement can improve performance by as much as 23%.
Spatial Memory Streaming
Authors: Somogyi Stephen , Wenisch Thomas F. , Ailamaki Anastassia , Falsafi Babak , Moshovos Andreas
Published: October 2006

Prior research indicates that there is much spatial variation in applications' memory access patterns. Modern memory systems, however, use small fixed-size cache blocks and as such cannot exploit the variation. Increasing the block size would not only prohibitively increase pin and interconnect bandwidth demands, but also increase the likelihood of false sharing in shared-memory multiprocessors. In this paper, we show that memory accesses in commercial workloads often exhibit repetitive layouts that span large memory regions (e.g., several kB), and these accesses recur in patterns that are predictable through codebased correlation. We propose Spatial Memory Streaming, a practical on-chip hardware technique that identifies codecorrelated spatial access patterns and streams predicted blocks to the primary cache ahead of demand misses. Using cycle-accurate full-system multiprocessor simulation of commercial and scientific applications, we demonstrate that Spatial Memory Streaming can on average predict 58% of L1 and 65% of off-chip misses, for a mean performance improvement of 37% and at best 307%.
TRAP-Array
Authors: Yang Qing , Xiao Weijun , Ren Jin
Published: October 2006

RAID architectures have been used for more than two decades to recover data upon disk failures. Disk failure is just one of the many causes of damaged data. Data can be damaged by virus attacks, user errors, defective software/firmware, hardware faults, and site failures. The risk of these types of data damage is far greater than disk failure with today's mature disk technology and networked information services. It has therefore become increasingly important for today's disk array to be able to recover data to any point in time when such a failure occurs. This paper presents a new disk array architecture that provides Timely Recovery to Any Point-in-time, referred to as TRAP-Array. TRAP-Array stores not only the data stripe upon a write to the array, but also the time-stamped Exclusive-ORs of successive writes to each data block. By leveraging the Exclusive-OR operations that are performed upon each block write in today's RAID4/5 controllers, TRAP does not incur noticeable performance overhead. More importantly, TRAP is able to recover data very quickly to any point-in-time upon data damage by tracing back the sequence and history of Exclusive-ORs resulting from writes. What is interesting is that TRAP architecture is amazingly space-efficient. We have implemented a prototype TRAP architecture using software at block device level and carried out extensive performance measurements using TPC-C benchmark running on Oracle and Postgress databases, TPC-W running on MySQL database, and file system benchmarks running on Linux and Windows systems. Our experiments demonstrated that TRAP is not only able to recover data to any point-in-time very quickly upon a failure but it also uses less storage space than traditional daily differential backup/snapshot. Compared to the state-of-the-art continuous data protection technologies, TRAP saves disk storage space by one to two orders of magnitude with a simple and a fast encoding algorithm. From an architecture point of view, TRAP-Array opens up another dimension for storage arrays. It is orthogonal and complementary to RAID in the sense that RAID protects data in the dimension along an array of physical disks while TRAP protects data in the dimension along the time sequence.
Efficient algorithms for bichromatic separability
Authors: Agarwal Pankaj K. , Aronov Boris , Koltun Vladlen
Published: October 2006

A closed solid body
separates
one point set from another if it contains the former and the closure of its complement contains the latter. We present a near-linear algorithm for deciding whether two sets of
n
points in ℝ
3
can be separated by a prism, near-quadratic algorithms for separating by a slab or a wedge, and a near-cubic algorithm for separating by a double wedge. The latter three algorithms improve the previous best known results by an order of magnitude, while the prism separability algorithm constitutes an improvement of two orders of magnitude.
Software
Authors: Armour Phillip G.
Published: October 2006

Seeking solid information on the behavior of modern projects.
Personalization in privacy-aware highly dynamic systems
Authors: Sackmann Stefan , Strüker Jens , Accorsi Rafael
Published: October 2006

Enabling novel ways to personalize the relationship with customers without sacrificing their privacy.
A compressor for effective archiving, retrieval, and updating of XML documents
Authors: Min Jun-Ki , Park Myung-Jae , Chung Chin-Wan
Published: October 2006

Like HTML, many XML documents are resident on native file systems. Since XML data is irregular and verbose, the disk space and the network bandwidth are wasted. To overcome the verbosity problem, research on compressors for XML data has been conducted. Some XML compressors do not support querying compressed data, while other XML compressors which support querying compressed data blindly encode tags and data values using predefined encoding methods. Existing XML compressors do not provide the facility for updates on compressed XML data.In this article, we propose XPRESS, an XML compressor which supports direct updates and efficient evaluations of queries on compressed XML data. XPRESS adopts a novel encoding method called
reverse arithmetic encoding
, which encodes label paths of XML data and applies diverse encoding methods depending on the types of data values. Experimental results with real-life data sets show that XPRESS achieves significant improvements on query performance for compressed XML data and reasonable compression ratios. On average, the query performance of XPRESS is 2.13 times better than that of an existing XML compressor, and the compression ratio of XPRESS is about 71%. Additionally, we demonstrate the efficiency of the updates performed directly on compressed XML data.
Performance and overhead of semantic cache management
Authors: Jónsson Björn Þór , Arinbjarnar María , Þórsson Bjarnsteinn , Franklin Michael J. , Srivastava Divesh
Published: October 2006

The emergence of query-based online data services and e-commerce applications has prompted much recent research on data caching. This article studies
semantic caching
, a caching architecture for such applications, that caches the results of selection queries. The primary contribution of this article is to revisit the performance and overhead of semantic caching using a modern database server and modern hardware. Initially, the performance study focuses on simple workloads and demonstrates several benefits of semantic caching, including low overhead, insensitivity to the physical layout of the database, reduced network traffic, and the ability to answer some queries without contacting the server. With moderately complex workloads, careful coding of remainder queries is required to maintain efficient query processing at the server. Using very complex workloads, we demonstrate that semantic caching works well in a range of applications, especially in network-constrained environments.
The Linux implementation of a log-structured file system
Authors: Konishi Ryusuke , Amagai Yoshiji , Sato Koji , Hifumi Hisashi , Kihara Seiji , Moriai Satoshi
Published: October 2006

Toward enhancing the reliability of the Linux file system, we are developing a new log-structured file system (NILFS) for the Linux operating system. Instead of overwriting existing blocks, NILFS appends consistent sets of modified or newly created blocks continuously into segmented disk regions. This writing method allows NILFS to achieve faster recovery time and higher write performance. The address of the block that is written to changes for each write, which makes it difficult to apply modern file system technologies such as B-tree structures. To permit such writing on the Linux kernel basis, NILFS has its own write mechanism that handles data and meta data as one unit and allows them to be relocated. This paper presents the design and implementation of NILFS focussing on the write mechanism.
Bridging the gap
Authors: Patel Jay A. , Gupta Indranil
Published: October 2006

The last few years have seen a burgeoning of p2p designs, but also a worrisome push back and skeptical resistance against much of this research (and development). We propose a new research direction that seeks to find common ground between the purely centralized architecture and the p2p systems. We propose a new class of systems called
"P2P-izers"
, which incentivize existing centralized infrastructures to utilize p2p solutions. A P2P-izer ensures that p2p technologies compliment existing centralized solutions. Finally, we show the feasibility of this direction by experimentally quantifying the advantages of a simple proof of concept P2P-izer solution for website hosting.
Suicide for the common good
Authors: Clulow Jolyon , Moore Tyler
Published: October 2006

We consider the problem of credential revocation in self-organizing systems. In the absence of a common trusted authority, reaching a decision is slow, expensive and prone to manipulation. We propose a radical, new strategy---
suicide for the common good
---which drastically simplifies the decision-making process and revocation orders. Our mechanism is fully decentralized, incurs low communication and storage overhead, enables fast removal of misbehaving nodes, and is ideally suited to highly mobile networks.
InteMon
Authors: Hoke Evan , Sun Jimeng , Strunk John D. , Ganger Gregory R. , Faloutsos Christos
Published: October 2006

Modern data centers have a large number of components that must be monitored, including servers, switches/routers, and environmental control systems. This paper describes InteMon, a prototype monitoring and mining system for data centers. It uses the SNMP protocol to monitor a new data center at Carnegie Mellon. It stores the monitoring data in a MySQL database, allowing visualization of the time-series data using a JSP web-based frontend interface for system administrators. What sets InteMon apart from other cluster monitoring systems is its ability to automatically analyze correlations in the monitoring data in real time and alert administrators of potential anomalies. It uses efficient, state of the art stream mining methods to report broken correlations among input streams. It also uses these methods to intelligently compress historical data and avoid the need for administrators to configure threshold-based monitoring bands.
Epidemic-based approaches for reliable multicast in mobile ad hoc networks
Authors: Özkasap Öznur , Genç Zülküf , Atsan Emre
Published: October 2006

We present a classification of epidemic-based approaches utilized in the context of mobile ad hoc networks (MANET) with a focus on reliable multicast protocols. We provide a brief description of the other approaches to reliable multicasting in MANETs as well. Then, we describe our protocol, namely EraMobile, offering Epidemic-based Reliable and Adaptive Multicast for Mobile ad hoc networks. EraMobile's target is group applications requiring high-level of reliability and the protocol aims to provide fully reliable multicast data delivery with minimal network overhead even in the adverse network conditions. EraMobile utilizes an epidemic-based method in multicast operation to cope with dynamic and unpredictable topology changes arising from the mobility. Our epidemic mechanism does not require the maintenance of any tree- or mesh-like structure for multicasting. It also needs neither having global or partial view of the network nor having information of neighboring nodes and group members. Besides, it substantially minimizes the overhead incurred by eliminating redundant data transmissions. Another distinguishing feature of EraMobile is its capability of adapting to varying node densities in order to provide reliable data delivery in both sparse networks, where the network connectivity is prone to interruptions, and dense networks, where congestion is likely to occur. EraMobile is shown to achieve fully reliable multicast data delivery studied through extensive simulations by outperforming the other protocols compared, especially in terms of both packet delivery ratio and overhead efficiency.
Ad hoc extensibility and access control
Authors: Erlingsson Úlfar , MacCormick John
Published: October 2006

General-purpose, commercial software platforms are increasingly used as system building blocks, even for dependable systems. One reason for their generality, usefulness, and popular adoption is that these software platforms can evolve through
ad hoc extensions:
behavior tweaks outside the scope of supported platform interfaces. Unfortunately, such use of internal platform implementation details is fundamentally incompatible with security and reliability. Even so, platforms that exclude ad hoc extensions---for instance, by enforcing full isolation and strict interfaces---will, most likely, either have their security enforcement circumvented or be relegated to a niche market. In this paper, we identify ad hoc extensions as well as the economic and technical factors surrounding their existence. Subsequently, we propose the enforcement of novel access-control policies for reconciling ad hoc extensibility with security and reliability.
Jigsaw
Authors: Cheng Yu-Chung , Bellardo John , Benkö Péter , Snoeren Alex C. , Voelker Geoffrey M. , Savage Stefan
Published: October 2006

The combination of unlicensed spectrum, cheap wireless interfaces and the inherent convenience of untethered computing have made 802.11 based networks ubiquitous in the enterprise. Modern universities, corporate campuses and government offices routinely de-ploy scores of access points to blanket their sites with wireless Internet access. However, while the fine-grained behavior of the 802.11 protocol itself has been well studied, our understanding of how large 802.11 networks behave in their full empirical complex-ity is surprisingly limited. In this paper, we present a system called Jigsaw that uses multiple monitors to provide a single unified view of all physical, link, network and transport-layer activity on an 802.11 network. To drive this analysis, we have deployed an infrastructure of over 150 radio monitors that simultaneously capture all 802.11b and 802.11g activity in a large university building (1M+ cubic feet). We describe the challenges posed by both the scale and ambiguity inherent in such an architecture, and explain the algorithms and inference techniques we developed to address them. Finally, using a 24-hour distributed trace containing more than 1.5 billion events, we use Jigsaw's global cross-layer viewpoint to isolate performance artifacts, both explicit, such as management inefficiencies, and implicit, such as co-channel interference. We believe this is the first analysis combining this scale and level of detail for a production 802.11 network.
Building an AS-topology model that captures route diversity
Authors: Mühlbauer Wolfgang , Feldmann Anja , Maennel Olaf , Roughan Matthew , Uhlig Steve
Published: October 2006

An understanding of the topological structure of the Internet is needed for quite a number of networking tasks, e. g., making decisions about peering relationships, choice of upstream providers, inter-domain traffic engineering. One essential component of these tasks is the ability to predict routes in the Internet. However, the Internet is composed of a large number of independent autonomous systems (ASes) resulting in complex interactions, and until now no model of the Internet has succeeded in producing predictions of acceptable accuracy.We demonstrate that there are two limitations of prior models: (i) they have all assumed that an Autonomous System (AS) is an atomic structure - it is not, and (ii) models have tended to oversimplify the relationships between ASes. Our approach uses multiple quasi-routers to capture route diversity within the ASes, and is deliberately agnostic regarding the types of relationships between ASes. The resulting model ensures that its routing is consistent with the observed routes. Exploiting a large number of observation points, we show that our model provides accurate predictions for unobserved routes, a first step towards developing structural mod-els of the Internet that enable real applications.
Modeling adoptability of secure BGP protocol
Authors: Chan Haowen , Dash Debabrata , Perrig Adrian , Zhang Hui
Published: October 2006

Despite the existence of several secure BGP routing protocols, there has been little progress to date on actual adoption. Although feasibility for widespread adoption remains the greatest hurdle for BGP security, there has been little quantitative research into what properties contribute the most to the adoptability of a security scheme. In this paper, we provide a model for assessing the adoptability of a secure BGP routing protocol. We perform this evaluation by simulating incentives compatible adoption decisions of ISPs on the Internet under a variety of assumptions. Our results include: (a) the existence of a sharp threshold, where, if the cost of adoption is below the threshold, complete adoption takes place, while almost no adoption takes place above the threshold; (b) under a strong attacker model, adding a single hop of path authentication to origin authentication yields similar adoptability characteristics as a full path security scheme; (c) under a weaker attacker model, adding full path authentication (e.g., via S-BGP [9]) significantly improves the adoptability of BGP security over weaker path security schemes such as soBGP [16]. These results provide insight into the development of more adoptable secure BGP protocols and demonstrate the importance of studying adoptability of protocols.
Policy-based routing with non-strict preferences
Authors: Chau Chi-kin
Published: October 2006

Traditional studies of routing problems often assumed strict preferences on paths, by eliminating ambiguity in path comparisons, or imposing a priori deterministic tie-breaking. Such an assumption is outpaced by today's common practice of non-deterministic,multi-path routing, which is crucial to traffic engineering, QoS routing, multicasting and virtual private networking. A pair of paths may be incomparable or equally preferred. In the presence of ambiguous preferences at pairs, or even multiple collections of paths, a challenge is to ensure robustness in the complex and sophisticated situations of policy-based routing where heterogeneous routing policies are allowed among routing systems. This paper presents an extensive study of policy-based routing with non-strict preferences, deriving sufficient conditions that ensure the existence, optimality and asynchronous convergence of stable routings.
Planet scale software updates
Authors: Gkantsidis Christos , Karagiannis Thomas , VojnoviC Milan
Published: October 2006

Fast and effective distribution of software updates (a.k.a. patches) to millions of Internet users has evolved into a critical task over the last years. In this paper, we characterize "Windows Update", one of the largest update services in the world, with the aim to draw general guidelines on how to best design and architect a fast and effective planet-scale patch dissemination system. To this end, we analyze an extensive set of data traces collected over the period of a year, consisting of billions of queries from over 300 million computers. Based on empirical observations and analytical results, we identify interesting properties of today's update traffic and user behavior.Building on this analysis, we consider alternative patch delivery strategies such as caching and peer-to-peer and evaluate their performance. We identify key factors that determine the effectiveness of these schemes in reducing the server workload and the network traffic, and in speeding-up the patch delivery. Most of our findings are invariant properties induced by either user behavior or architectural characteristics of today's Internet, and thus apply to the general problem of Internet-wide dissemination of software updates.
Avoiding coincidental correctness in boundary value analysis
Authors: Hierons R. M.
Published: October 2006

In partition analysis we divide the input domain to form subdomains on which the system's behaviour should be uniform. Boundary value analysis produces test inputs near each subdomain's boundaries to find failures caused by incorrect implementation of the boundaries. However, boundary value analysis can be adversely affected by coincidental correctness---the system produces the expected output, but for the wrong reason. This article shows how boundary value analysis can be adapted in order to reduce the likelihood of coincidental correctness. The main contribution is to cases of automated test data generation in which we cannot rely on the expertise of a tester.
HOTTest
Authors: Sinha Avik , Smidts Carol
Published: October 2006

Model-based testing is an effective black-box test generation technique for applications. Existing model-based testing techniques, however, fail to capture implicit domain-specific properties, as they overtly rely on software artifacts such as design documents, requirement specifications, etc., for completeness of the test model. This article presents a technique, HOTTest, which uses a strongly typed domain-specific language to model the system under test. This allows extraction of type-related system invariants, which can be related to various domain-specific properties of the application. Thus, using HOTTest, it is possible to automatically extract and embed domain-specific requirements into the test models. In this article we describe HOTTest, its principles and methodology, and how it is possible to relate domain-specific properties to specific type constraints. HOTTest is described using the example of HaskellDB, which is a Haskell-based embedded domain-specific language for relational databases. We present an example application of the technique and compare the results to some other commonly used Model-based test automation techniques like ASML-based testing, UML-based testing, and EFSM-based testing.
A study of the difficulties of novice programmers
Authors: Lahtinen Essi , Ala-Mutka Kirsti , Järvinen Hannu-Matti
Published: October 2006

Programming is related to several fields of technology, and many university students are studying the basics of it. Unfortunately, they often face difficulties already on the basic courses. This work studies the difficulties in learning programming in order to support developing learning materials for basic programming courses. The difficulties have to be recognized to be able to aid learning and teaching in an effective way.An international survey of opinions was organized for more than 500 students and teachers. This paper analyses the results of the survey. The survey provides information of the difficulties experienced and perceived when learning and teaching programming. The survey results also provide basis for recommendations for developing learning materials and approaches.
Student interviews as a tool for assessment and learning in a systems analysis and design course
Authors: Dick Martin
Published: October 2006

This paper examines the use of student interviews as a means of assessment for systems analysis and design assignments and as a means of providing feedback to students on their performance in the assignment. It uses student feedback from 510 student surveys gathered from Semester 1 2001 to Semester 2 2003 to assess the opinion of students on the use of interviews and describes the lessons learnt about this form of assessment.
The (relative) importance of software design criteria
Authors: Chen Tzu-Yi , Cooper Stephen , McCartney Robert , Schwartzman Leslie
Published: October 2006

We study how the relative values placed on a variety of software design criteria differs between beginning students, advanced students, and educators. We also consider how these values change depending on the specific design situation. Statistical analysis of data collectedfrom over 300 subjects reveals relatively small differences between the two student populations and significant differences between educators and students. In addition to often valuing different criteria, educators also value criteria more consistently across the design situations.
Software behaviour understanding Supported by dynamic visualization and role-play
Authors: Jiménez-Díaz Guillermo , Gómez-Albarrán Mercedes , Gómez-Martin Marco A. , González-Calero Pedro A.
Published: October 2006

Visualization techniques are commonly used in computer science, particularly for understanding the interactions intrinsic in the object-oriented paradigm. The visualization effectiveness improves if the student takes an active role during the learning process. In this paper we propose an active learning approach that lies in using role-play simulations in a virtual 3D environment.
Game programming in introductory courses with direct state manipulation
Authors: Kölling Michael , Henriksen Poul
Published: October 2006

While the introduction of object-oriented programming slowly moves down the age groups - starting from advanced university courses, to introductory courses, and now into high schools - many attempts are being made to make object-oriented programming introduction less abstract and theoretical. Visualisation and interaction techniques are being applied in an attempt to give students engaging and concrete experiences with objects. Recently, the
greenfoot
environment has been proposed as another step in this development. In this paper, we describe new functionality in the greenfoot environment, especially the addition of user interaction programming via direct state manipulation. Direct state manipulation provides very low overhead graphical I/O handling at a level that makes it feasible to guide students to simple graphical game programming within a few weeks, while concentrating on fundamental object-oriented concepts in the structure of the program.
Providing students universal access to a centralized, graphical computing environment
Authors: Goldwasser Michael H. , Letscher David
Published: October 2006

We investigate the use of a thin-client based configuration in providing students with universal access to a centralized, graphical computing environment. The primary goal is to enable students to work effectively from arbitrary locations and computing platforms, while always interacting with the consistent environment seen in tightly controlled labs.
An analysis of patterns of debugging among novice computer science students
Authors: Ahmadzadeh Marzieh , Elliman Dave , Higgins Colin
Published: October 2006

The process by which students learn to program is a major issue in computer science educational research. Programming is a fundamental part of the computer science curriculum, but one which is often problematic. It seems to be difficult to find an effective method of teaching that is suitable for all students. In this research we tried to gain insights into ways of improving our teaching by a careful examination of students' mistakes. The compiler errors that were generated by their programs together with the pattern that was observed in their debugging activities formed the basis of this research. We discovered that many students with a good understanding of programming do not acquire the skills to debug programs effectively, and this is a major impediment to their producing working code of any complexity. Skill at debugging seems to increase a programmer's confidence and we suggest that more emphasis be placed on debugging skills in the teaching of programming.
The effect of integrating an Iconic programming notation into CS1
Authors: Cilliers Charmain , Calitz André , Greyling Jéan
Published: October 2006

Increasing pressure from national government to improve throughput at South African tertiary education institutions presents challenges to educators of CS1 courses. In response, educators must adopt effective methods and strategies that encourage students to be successful in such courses. An approach that seeks to increase and maintain satisfactory throughput is the modification of the teaching model in these courses by adjusting presentation techniques. This paper reports on a study into the effect of integrating an experimental iconic programming notation and associated development environment with existing conventional textual technological support in the teaching model of a CS1 course. The paper reports on the comparison of the performance achievement of students using only conventional textual technological support with that of students using the integrated iconic and conventional textual technological support. The findings suggest strong evidence that the performance achievement of students in a CS1 course improves significantly with the inclusion of iconic technological support in the teaching model. Considerably more students using the integrated form of technological support are in fact successful in the CS1 course when compared with their counterparts who use conventional textual technological support only.