bluuebunny/crossref_metadata_2025 huggingface dataset:
Diagnosing network disruptions with network-wide analysis
Authors: Huang Yiyi , Feamster Nick , Lakhina Anukool , Xu Jim (Jun)
Published: September 2007

To maintain high availability in the face of changing network conditions, network operators must quickly detect, identify, and react to events that cause network disruptions. One way to accomplish this goal is to monitor routing dynamics, by analyzing routing update streams collected from routers. Existing monitoring approaches typically treat streams of routing updates from different routers as independent signals, and report only the "loud" events (i.e., events that involve large volume of routing messages). In this paper, we examine BGP routing data from all routers in the Abilene backbone for six months and correlate them with a catalog of all known disruptions to its nodes and links. We find that many important events are not loud enough to be detected from a single stream. Instead, they become detectable only when multiple BGP update streams are simultaneously examined. This is because routing updates exhibit
network-wide
dependencies.

This paper proposes using network-wide analysis of routing information to diagnose (i.e., detect and identify) network disruptions. To detect network disruptions, we apply a multivariate analysis technique on dynamic routing information, (i.e., update traffic from all the Abilene routers) and find that this technique can detect every reported disruption to nodes and links within the network with a low rate of false alarms. To identify the type of disruption, we jointly analyze both the network-wide static configuration and details in the dynamic routing updates; we find that our method can correctly explain the scenario that caused the disruption. Although much work remains to make network-wide analysis of routing data operationally practical, our results illustrate the importance and potential of such an approach.
Understanding network delay changes caused by routing events
Authors: Pucha Himabindu , Zhang Ying , Mao Z. Morley , Hu Y. Charlie
Published: September 2007

Network delays and delay variations are two of the most important network performance metrics directly impacting real-time applications such as voice over IP and time-critical financial transactions. This importance is illustrated by past work on understanding the delay constancy of Internet paths and recent work on predicting network delays using virtual coordinate systems. Merely understanding currently observed delays is insufficient, as network performance can degrade not only due to traffic variability but also as a result of routing changes. Unfortunately this latter effect so far has been ignored in understanding and predicting delay related performance metrics of Internet paths. Our work is the first to address this short coming by systematically analyzing changes in network delays and jitter of a diverse and comprehensive set of Internet paths. Using empirical measurements, we illustrate that routing changes can result in roundtrip delay increase of converged paths by more than 1 second. Surprisingly, intradomain routing changes can also cause such large delay increase.

Given these observations, we develop a framework to analyze in detail the impact of routing changes on network delays between end-hosts. Using topology information and properties associated with routing changes, we explain the causes for observed delay fluctuations and more importantly identify routing changes that lead to predictable effects on delay-related metrics. Using our framework, we study the predictability of delay and jitter changes in response to both passively observed interdomain and actively measured intradomain routing changes.
A machine learning approach to TCP throughput prediction
Authors: Mirza Mariyam , Sommers Joel , Barford Paul , Zhu Xiaojin
Published: September 2007

TCP
throughput prediction
is an important capability in wide area overlay and multi-homed networks where multiple paths may exist between data sources and receivers. In this paper we describe a new, lightweight method for TCP throughput prediction that can generate accurate forecasts for a broad range of file sizes and path conditions. Our method is based on Support Vector Regression modeling that uses a combination of prior file transfers and measurements of simple path properties. We calibrate and evaluate the capabilities of our throughput predictor in an extensive set of lab-based experiments where ground truth can be established for path properties using highly accurate passive measurements. We report the performance for our method in the ideal case of using our passive path property measurements over a range of test configurations. Our results show that for bulk transfers in heavy traffic, TCP throughput is predicted within 10% of the actual value 87% of the time, representing nearly a 3-fold improvement in accuracy over prior history-based methods. In the same lab environment, we assess our method using less accurate active probe measurements of path properties, and show that predictions can be made within 10% of the actual value nearly 50% of the time over a range of file sizes and traffic conditions. This result represents approximately a 60% improvement over history-based methods with a much lower impact on end-to-end paths. Finally, we implement our predictor in a tool called
PathPerf
and test it in experiments conducted on wide area paths. The results demonstrate that
PathPerf
predicts TCP through put accurately over a variety of paths.
Sensitivity of PCA for traffic anomaly detection
Authors: Ringberg Haakon , Soule Augustin , Rexford Jennifer , Diot Christophe
Published: September 2007

Detecting anomalous traffic is a crucial part of managing IP networks. In recent years, network-wide anomaly detection based on Principal Component Analysis (PCA) has emerged as a powerful method for detecting a wide variety of anomalies. We show that tuning PCA to operate effectively in practice is difficult and requires more robust techniques than have been presented thus far. We analyze a week of network-wide traffic measurements from two IP backbones (Abilene and Geant) across three different traffic aggregations (ingress routers, OD flows, and input links), and conduct a detailed inspection of the feature time series for each suspected anomaly. Our study identifies and evaluates four main challenges of using PCA to detect traffic anomalies: (i) the false positive rate is very sensitive to small differences in the number of principal components in the normal subspace, (ii) the effectiveness of PCA is sensitive to the level of aggregation of the traffic measurements, (iii) a large anomaly may in advertently pollute the normal subspace, (iv) correctly identifying which flow triggered the anomaly detector is an inherently challenging problem.
Backbone construction in selfish wireless networks
Authors: Lee Seungjoon , Levin Dave , Gopalakrishnan Vijay , Bhattacharjee Bobby
Published: September 2007

We present a protocol to construct routing backbones in wireless networks composed of selfish participants. Backbones are inherently cooperative, so constructing them in selfish environments is particularly difficult; participants want a backbone to exist (soothers relay their packets) but do not want to join the backbone (so they do not have to relay packets for others).

We model the wireless backbone as a public good and use impatience as an incentive for cooperation. To determine if and when to donate to this public good, each participant calculates how patient it should be in obtaining the public good. We quantify patience using the Volunteer's Timing Dilemma (VTD), which we extend to general multihop network settings. Using our generalized VTD analysis, each node individually computes as its dominant strategy the amount of time to wait before joining the backbone. We evaluate our protocol using both simulations and an implementation. Our results show that, even though participants in our system deliberately wait before volunteering, a backbone is formed quickly. Further, the quality of the backbone (such as the size and resulting network lifetime) is comparable to that of existing backbone protocols that assume altruistic behavior.
Scalability of fork/join queueing networks with blocking
Authors: Xia Cathy H. , Liu Zhen , Towsley Don , Lelarge Marc
Published: September 2007

This paper investigates how the through put of a general fork-join queueing network with blocking behaves as the number of nodes increases to infinity while the processing speed and buffer space of each node stay unchanged. The problem is motivated by applications arising from distributed systems and computer networks. One example is large-scale distributed stream processing systems where TCP is used as the transport protocol for data transfer in between processing components. Other examples include reliable multicast in overlay networks, and reliable data transfer in ad hoc networks. Using an analytical approach, the paper establishes bounds on the asymptotic throughput of such a network. For a subclass of networks which are balanced, we obtain sufficient conditions under which the network stays scalable in the sense that the throughput is lower bounded by a positive constant as the network size increases. Necessary conditions of throughput scalability are derived for general networks. The special class of series-parallel networks is then studied in greater detail, where the asymptotic behavior of the throughput is characterized.
Synthetic designs
Authors: Lee Eric S. , Whalen Thom
Published: September 2007

Computer scientists and software engineers seldom rely on using experimental methods despite frequent calls to do so. The problem may lie with the shortcomings of traditional experimental methods. We introduce a new form of experimental designs, synthetic designs, which address these shortcomings. Compared with classical experimental designs (between-subjects, within-subjects, and matched-subjects), synthetic designs can offer substantial reductions in sample sizes, cost, time and effort expended, increased statistical power, and fewer threats to validity (internal, external, and statistical conclusion). This new design is a variation of within-subjects design in which each system user serves in only a single treatment condition. System performance scores for all other treatment conditions are derived synthetically without repeated testing of each subject. This design, though not applicable in all situations, can be used in the development and testing of some computer systems provided that user behavior is unaffected by the version of computer system being used. We justify synthetic designs on three grounds: this design has been used successfully in the development of computerized mug shot systems, showing marked advantages over traditional designs; a detailed comparison with traditional designs showing their advantages on 17 of the 18 criteria considered; and an assessment showing these designs satisfy all the requirements of true experiments (albeit in a novel way).
PBS
Authors: Feng Hanhua , Misra Vishal , Rubenstein Dan
Published: September 2007

Blind scheduling policies schedule tasks without knowledge of the tasks' remaining processing times. Existing blind policies, such as FCFS, PS, and LAS, have proven useful in network and operating system applications, but each policy has a separate, vastly differing description, leading to separate and distinct implementations. This paper presents the design and implementation of a configurable blind scheduler that contains a continuous, tunable parameter. By merely changing the value of this parameter, the scheduler's policy exactly emulates or closely approximates several existing standard policies. Other settings enable policies whose behavior is a hybrid of these standards. We demonstrate the practical benefits of such a
configurable
scheduler by implementing it into the Linux operating system. We show that we can emulate the behavior of Linux's existing, more complex scheduler with a single (hybrid) setting of the parameter. We also show, using synthetic workloads, that the best value for the tunable parameter is not unique, but depends on distribution of the size of tasks arriving to the system. Finally, we use our formulation of the configurable scheduler to contrast the behavior of various blind schedulers by exploring how various properties of the scheduler change as we vary our scheduler's tunable parameter.
Adaptive and scalable comparison scheduling
Authors: Jelenkovic Predrag R. , Kang Xiaozhu , Tan Jian
Published: September 2007

The Shortest Remaining Processing Time (SRPT) scheduling disciplineis optimal and its superior performance, compared with the policies that do not use the knowledge of job sizes, can be quantified using mean-value analysis as well as our new a symptotic distribution allimits for the relatively smaller heavy-tailed jobs. However, the main difficulty in implementing SRPT in large practical systems, e.g., Web servers, is that its complexity grows with the number of jobs in the queue. Hence, in order to lower the complexity, it is natural to approximate SRPT by grouping the arrivals into a fixed (small) number of classes containing jobs of approximately equal size and then serve the classes of smaller jobs with higher priorities.

In this paper, we design a novel adaptive grouping mechanism based on relative size comparison of a newly arriving job to the preceding
m
arrivals. Specifically, if the newly arriving job is smallerthan
k
and larger than
m-k
of the previous
m
jobs, it isrouted into class
k
. The excellent performance of this mechanism,even for a small number of classes
m
+1, is demonstrated using both the asymptotic queueing analysis under heavy tails and extensive simulations. We also discuss refinements of the comparison grouping mechanism that improve the accuracy of job classification at the expense of a small additional complexity.
Optimal capacity planning in stochastic loss networks with time-varying workloads
Authors: Bhadra Sandeep , Lu Yingdong , Squillante Mark S.
Published: September 2007

We consider a capacity planning optimization problem in a general theoretical framework that extends the classical Erlang loss modeland related stochastic loss networks to support time-varying workloads. The time horizon consists of a sequence of coarse time intervals, each of which involves a stochastic loss network under a fixed multi-class workload that can change in a general manner from one interval to the next. The optimization problem consists of determining the capacities for each time interval that maximize a utility function over the entire time horizon, finite or infinite, where rewards gained from servicing customers are offset by penalties associated with deploying capacities in an interval and with changing capacities among intervals. We derive a state-dependent optimal policy within the context of a particular limiting regime of the optimization problem, and we prove this solution to be a symptotically optimal. Then, under fairly mild conditions, we prove that a similar structural property holds for the optimal solution of the original stochastic optimization problem, and we show how the optimal capacities comprising this solution can be efficiently computed.
Flow-level stability of data networks with non-convex and time-varying rate regions
Authors: Liu Jiaping , Proutière Alexandre , Yi Yung , Chiang Mung , Poor H. Vincent
Published: September 2007

In this paper we characterize flow-level stochastic stability for networks with non-convex or time-varying rate regions underresource allocation based on utility maximization. Similar to prior works on flow-level stability, we consider exogenous data arrivals with finite workloads. However, to model many realistic situations, the rate region, which constrains the feasibility of resource allocation, may be either non-convex or time-varying. When the rate region is fixed but non-convex, we derive sufficient and necessary conditions for stability, which coincide when the set of allocated rate vectors has continuous contours. When the rate region is time-varying according to some stationary, ergodic process, we derive the precise stability region. In both cases,the size of the stability region depends on the resource allocation policy, in particular, on the fairness parameter in ∝-fair utility maximization. This is in sharp contrast with the substantial existing literature on stability under fixed and convex rate regions, in which the stability region coincides with the rate region for many utility-based resource allocation schemes, independently of the value of the fairness parameter. We further investigate the tradeoff between fairness and stability when rate region is non-convex or time-varying. Numerical examples of both wired and wireless networks are provided to illustrate the new stability regions and tradeoffs proved in the paper.
Data layouts for object-oriented programs
Authors: Hirzel Martin
Published: September 2007

Object-oriented programs rely heavily on objects and pointers, making them vulnerable to slow downs from cache and TLB misses. The cache and TLB behavior depends on the data layout of objects in memory. There are many possible data layouts with different impacts on performance, but it is not known which perform better. This paper presents a novel framework for evaluating data layouts. The framework both makes implementing many layouts easy, andenables performance measurements of real programs using a product Java virtual machine on stock hardware. This is achieved by sorting objects during copying garbage collection; outside of garbage collection, program performance is solely determined by the data layout that the sort key implements. This paper surveys and evaluates 10 common data layouts with 32 realistic bench mark programs running on 3 different hardware configurations. The results confirm the importance of data layouts for program performance, and show that almost all layouts yield the best performance for some programs and the worst performance for others.
Building high accuracy bloom filters using partitioned hashing
Authors: Hao Fang , Kodialam Murali , Lakshman T. V.
Published: September 2007

The growing importance of operations such as packet-content inspection, packet classification based on non-IP headers, maintaining flow-state, etc. has led to increased interest in the networking applications of Bloom filters. This is because Bloom filters provide a relatively easy method for hardware implementation of set-membership queries. However, the tradeoff is that Bloom filters only provide a probabilistic test and membership queries can result in false positives. Ideally, we would like this false positive probability to be very low. The main contribution of this paper is a method for significantly reducing this false positive probability in comparison to existing schemes. This is done by developing a
partitioned hashing
method which results in a choice of hash functions that set far fewer bits in the Bloom filter bit vector than would be the case otherwise. This lower fill factor of the bit vector translates to a much lower false positive probability. We show experimentally that this improved choice can result in as much as a ten-fold increase in accuracy over standard Bloom filters. We also show that the scheme performs much better than other proposed schemes for improving Bloom filters.
An analysis of latent sector errors in disk drives
Authors: Bairavasundaram Lakshmi N. , Goodson Garth R. , Pasupathy Shankar , Schindler Jiri
Published: September 2007

The reliability measures in today's disk drive-based storage systems focus predominantly on protecting against complete disk failures. Previous disk reliability studies have analyzed empirical data in an attempt to better understand and predict disk failure rates. Yet, very little is known about the incidence of latent sector errors i.e., errors that go undetected until the corresponding disk sectors are accessed.

Our study analyzes data collected from production storage systems over 32 months across 1.53 million disks (both nearline and enterprise class). We analyze factors that impact latent sector errors, observe trends, and explore their implications on the design of reliability mechanisms in storage systems. To the best of our knowledge, this is the first study of such large scale our sample size is at least anorder of magnitude larger than previously published studies and the first one to focus specifically on latent sector errors and their implications on the design and reliability of storage systems.
Distributed link scheduling with constant overhead
Authors: Sanghavi Sujay , Bui Loc , Srikant R.
Published: September 2007

This paper proposes a new class of simple, distributed algorithms for scheduling in wireless networks. The algorithms generate new schedules in a distributed manner via simple local changes to existing schedules. The class is parameterized by integers
k
\geq 1. We show that algorithm
k
of our class achieves
k
/(
k
+2) of the capacity region, for every
k
\geq 1. .

The algorithms have small and constant worst-case overheads: in particular, algorithm
k
generates a new schedule using (a) time less than 4
k
+2 round-trip times between neighboring nodes in the network, and (b) at most three control transmissions by any given node, for any
k
. The control signals are explicitly specified, and face the same interference effects as normal data transmissions. Our class of distributed wireless scheduling algorithms are the first ones guaranteed to achieve any fixed fraction of the capacity region while using small and constant overheads that do not scale with network size. The parameter
k
explicitly captures the tradeoff between control overhead and scheduler throughput performance and provides a tuning knob protocol designers can use to harness this trade-off in practice.
Theoretical bounds on control-plane self-monitoring in routing protocols
Authors: Rajendran Raj Kumar , Misra Vishal , Rubenstein Dan
Published: September 2007

The distributed routing protocols in use today promise to operate correctly only if all nodes implement the protocol faithfully. A small insignificant set of nodes have, in the past, brought an entire network to a standstill by reporting incorrect route information. The damage caused by these erroneous reports, in some instances, could have been contained since incorrect route reports sometimes reveal themselves as inconsistencies in the state-information of correctly functioning nodes. By checking for such inconsitencies and taking preventive action, such as disregarding selected route-reports, a correctly functioning node could have limited the damage caused by the malfunctioning nodes.

Our theoretical study attempts to understand when a correctly functioning node can, by analysing its routing-state, detect that some node is misimplementing route selection. We present a methodology, called Strong-Detection that helps answer the question. We then apply Strong-Detection to three classes of routing protocols: distance-vector, path-vector, and link-state. For each class, we derive low-complexity self-monitoring algorithms that take as input the routing state and output whether any detectable anomalies exist. We then use these algorithms to compare and contrast the self-monitoring power ofthese different classes of protocols in relation to the complexity of the irrouting-state.
Oblivious routing for fat-tree based system area networks with uncertain traffic demands
Authors: Yuan Xin , Nienaber Wickus , Duan Zhenhai , Melhem Rami
Published: September 2007

Fat-tree based system area networks have been widely adopted in high performance computing clusters. In such systems, the routing is often deterministic and the traffic demand is usually uncertain and changing. In this paper, we study routing performance on fat-tree based system area networks with deterministic routing under the assumption that the traffic demand is uncertain. The performance of a routing algorithm under uncertain traffic demands is characterized by theoblivious performanceratio that bounds the relative performance of the routing algorithm and the optimal routing algorithm for any given traffic demand. We consider both single path routing where the traffic between each source-destination pair follows one path, and multi-path routing where multiple paths can be used for the traffic between a source-destination pair. We derive lower bounds of the oblivious performance ratio of any single path routing scheme for fat-tree topologies and develop single path oblivious routing schemes that achieve the optimal oblivious performance ratio for commonly used fat-tree topologies. These oblivious routing schemes provide the best performance guarantees among all single path routing algorithms under uncertain traffic demands. For multi-path routing, we show that it is possible to obtain a scheme that is optimal for any traffic demand (an oblivious performance ratio of 1) on the fat-tree topology. These results quantitatively demonstrate that single path routing cannot guarantee high routing performance while multi-path routing is very effective in balancing network loads on the fat-tree topology.
GRE encapsulated multicast probing
Authors: Gu Yu , Breslau Lee , Duffield Nick G. , Sen Subhabrata
Published: September 2007

We develop techniques for estimating one-way loss from a measurement host to network routers which exploit commonly implemented features on commercial routers and do not require any new router capabilities. The work addressesthe problem of scalably performing one-way loss measurements across specific network paths.
When is service really denied?
Authors: Mirkovic Jelena , Hussain Alefiya , Willson Brett , Fahmy Sonia , Yao Wei-Min , Reiher Peter , Schwab Stephen , Thomas Roshan
Published: September 2007

Denial-of-service (DoS) research community lacks accurate metrics to evaluate an attack's impact on network services, its severity and the effectiveness of a potential defense. We propose several DoS impact metrics that measure the quality of service experienced by end users during an attack, and compare these measurements to application-specific thresholds. Our metrics are ideal for testbed experimentation, since necessary traffic parameters are extracted from packet traces gathered during an experiment.
Comparative characterization of SPEC CPU2000 and CPU2006 on Itanium® architecture
Authors: Kejariwal Arun , Hoflehner Gerolf F. , Desai Darshan , Lavery Daniel M. , Nicolau Alexandru , Veidenbaum Alexander V.
Published: September 2007

Recently SPEC1 released the next generation of its CPU benchmark, widely used by compiler writers and architects for measuring processor performance. This calls for characterization of the applications in SPEC CPU2006 to guide the design of future microprocessors. In addition, it necessitates assessing the change in the characteristics of the applications from one suite to another. Although similar studies using the retired SPEC CPU benchmark suites have been done in the past, to the best of our knowledge, a thorough characterization of CPU2006 and its comparison with CPU2000 has not been done so far. In this paper, we present the above; specifically, we analyze IPC (instructions per cycle), L1, L2 data cache misses and branch prediction, especially in CPU2006.
Analyzing commercial processor performance numbers for predicting performance of applications of interest
Authors: Hoste Kenneth , Eeckhout Lieven , Blockeel Hendrik
Published: September 2007

Current practice in benchmarking commercial computer systems is to run a number of industry-standard benchmarks and to report performance numbers. The huge amount of machines and the large number of benchmarks for which performance numbers are published make it hard to observe clear performance trends though. In addition, these performance numbers for specific benchmarks do not provide insight into how applications of interest that are not part of the benchmark suite would perform on those machines.

In this work we build a methodology for analyzing published commercial machine performance data sets. We apply statistical data analysis techniques, more in particular principal components analysis and cluster analysis, to reduce the amount of information to a manageable amount to facilitate its understanding. Visualizing SPEC CPU2000 performance numbers for 26 benchmarks and 1000+ machines in just a few graphs gives insight into how commercial machines compare against each other.In this work we build a methodology for analyzing published commercial machine performance data sets. We apply statistical data analysis techniques, more in particular principal components analysis and cluster analysis, to reduce the amount of information to a manageable amount to facilitate its understanding. Visualizing SPEC CPU2000 performance numbers for 26 benchmarks and 1000+ machines in just a few graphs gives insight into how commercial machines compare against each other.

In addition, we provide a way of relating inherent program behavior to these performance numbers so that insights can be gained into how the observed performance trends relate to the behavioral characteristics of computer programs. This results in a methodology for the ubiquitous benchmarking problem of predicting performance of an application of interest based on its similarities with the benchmarks in a published industry-standard benchmark suite.
Pong
Authors: Deng Leiwen , Kuzmanovic Aleksandar
Published: September 2007

The ability to accurately detect congestion events in the Internet and reveal their spatial (
i.e.
, where they happen?) and temporal (
i.e.
, how frequently they occur and how long they last?) properties would significantly improve our understanding of how the Internet operates. In this paper we present
Pong
, a novel measurement tool capable of effectively diagnosing congestion events over short (
e.g.
, ~100ms or longer) time-scales, and simultaneously locating congested points within a single hop on an end-to-end path at the granularity of a single link.

Pong
(
i
) uses queuing delay as indicative of congestion, and (
ii
) strategically combines end-to-end probes with those targeted to intermediate nodes. Moreover, it (
iii
) achieves high sampling frequency by sending probes to all intermediate nodes, including uncongested ones, (
iv
) dramatically improves spatial detection granularity (
i.e.
, from path segments to individual links), by using short-term congestion history, (
v
) considerably enhances the measurement quality by adjusting the probing methodology (
e.g.
, send 4-, 3-, or 2-packet probes) based on the observed path topology, and (
vi
) deterministically detects moments of its own inaccuracy. We conduct a large-scale measurement study on over 23,000 Internet paths and present their spatial-temporal properties as inferred by
Pong
.
Serious fun in computer science
Authors: Curzon Paul
Published: September 2007

Computer Science has been in crisis for several years. Interest in studying it has dropped dramatically. We can wring our hands, or we can do something about it. Computer Science needs to engage with pure outreach: selling the subject (for free). Our approach has been to do this by just going out and having innovative fun. This is more effective than selling specific courses or institutions. CS is after all a naturally exciting, innovative and thought-provoking subject (Oh, and by the way there are good jobs at the end too).

We see it as a Renaissance subject (so who cares what it's called or which variation the future depends on). It sits in a unique position, centrally connected to all of the sciences, arts and humanities. We are passionate about science generally, so we go out and spread that enthusiasm about it all.

What have we been doing? There is cs4fn (www.cs4fn.org) a website and magazine that we've been writing for the sheer enjoyment of it; Sodarace (www.sodarace.net) where over 130 000 registered humans and computers compete in an online Olympics; Brain Academy (www.brainacademy.qmul.ac.uk), the Compute-Ability competition with career enhancing prizes; research talks for kids on Artificial Intelligence, women in technology, disability and mutant super-hero powers (actually its about search algorithms) and so on; a Computer Science Magic show (you have to promise not to tell anyone the secrets); and exhibits at the Royal Society Summer Exhibition on mathematical illusions and their link to computer science (www.cs4fn.org/illusions). We build brains that play Snap from rope and toilet roll, and introduce a piece of paper more intelligent than anyone in the room. Kids act out Turing Tests (can you tell the human from the robot?), and we challenge them to solve puzzles with CS twists. We do real research too of course: a spin-out of our EPSRC funded research project on Human Error and Interactive Systems includes an online SpaceInvaders game-experiment (www.cs4fn.org/humanerror) the data from which helps us understand the causes of human error: can you consistently avoid making the mistake that will blow up your ship and lose all your points?.

What age group should we be targeting? Sixth formers? A major issue is that school ICT, vital as it is, gives a poor impression of how being a computer scientist is about being an innovative, creative, computational thinker. By the sixth form it is too late. It is the younger kids we have to get the message to. An early experiment has been teaching a version of a graduate level course on usability evaluation to primary school kids (www.cs4fn.org/manorside). They proved to be very innovative and "amazing", "will stay in my mind forever", "I want to teach others in the school what we did" were some of their comments.

Our approach works: teachers, industry and the International Review of ICT have commended us & and we have seen an increase in undergraduate applications of over 130% in 2 years. Not bad when we are just having fun: serious fun.
Pilot summer camps in computing for middle school girls
Authors: Doerschuk Peggy , Liu Jiangjiang , Mann Judith
Published: September 2007

It is a well-known fact that women are under-represented in computing, and that trend has been worsening. In recent years, very few entering female freshmen have expressed an interest in computer science. Research has shown that girls lose interest in computing at an early age. If we are to fill the pipeline with women we must reach out to girls to remove the hurdles and dispel the misconceptions that turn them away from computing. This paper describes our experience in conducting pilot summer camps in computing for middle school girls. It covers the whole process, from conception through assessment, including how we worked with local schools to organize and devise the content of the camps, and how the camps were funded, conducted, advertised and assessed. We include lessons learned from this experience to benefit those who want to implement such camps. Other organizations can use the information in this paper to guide them in developing similar programs.
Introducing network programming into a CS1 course
Authors: Goldwasser Michael H. , Letscher David
Published: September 2007

Incorporating advanced programming concepts into an introductory programming course has to be done carefully to avoid overwhelming the students. We describe our experiences doing network programming in a CS1 course taught in Python. The simplicity of the built-in libraries allowed a fair amount of networking to be introduced in a week-long module of the course. In this short time we had the students writing both multithreaded clients and servers.
Breadth-first CS 1 for scientists
Authors: Dodds Zachary , Alvarado Christine , Kuenning Geoff , Libeskind-Hadas Ran
Published: September 2007

This paper describes an introductory CS course designed to provide future scientists with a one-semester overview of the discipline. The course takes a breadth-first approach that leverages its students' interest and experience in science, mathematics, and engineering. In contrast to many other styles of CS 1, this course does not presume that its students will study more computer science, but it does seek to prepare them should they choose to do so. In addition to describing the curriculum and resources, we summarize our preliminary assessments of this course and a comparison with the more traditional, imperative-first introduction it replaced. The data thus far suggest that this CS
for Scientists
course improves our students' understanding of CS, its applications, and practice.
Towards a curriculum for electronic textiles in the high school classroom
Authors: Buechley Leah , Eisenberg Mike , Elumeze Nwanua
Published: September 2007

This paper proposes a curriculum for a high school e-textile course-a curriculum rooted in our experiences in developing an e-textile construction kit and in holding several courses and workshops with these materials. The paper briefly describes the e-textile kit and reports on our teaching experiences, reflecting on the relationship between the evolving tools and curriculum and our user experiences.
Teaching operating systems with ruby
Authors: Sheehan Robert J.
Published: September 2007

Dynamic languages have regained enormous popularity in recent years. One of the principal dynamic programming languages, Ruby, has been used as the language for assignment work and the presentation of concepts in an introductory Operating Systems course. This was a strange choice for a systems course but there were several good reasons for the choice including the ease with which Ruby provides access to Unix commands and system calls. After some initial problems, the change has been very successful and demonstrates that even in the core courses of a Computer Science curriculum dynamic programming languages have benefits.
ProofChecker
Authors: Stallmann Matthias F. , Balik Suzanne P. , Rodman Robert D. , Bahram Sina , Grace Michael C. , High Susan D.
Published: September 2007

ProofChecker is a graphical program based on the notion of formal correctness proofs that allows students, both sighted and visually impaired, to draw a deterministic finite automaton (DFA) and determine whether or not it correctly recognizes a given language. Sighted students use the mouse and graphical controls to draw and manipulate the DFA. Keyboard shortcuts, together with the use of a screen reader to voice the accessible descriptions provided by the program, allow visually impaired students to do the same.

Because the states of a DFA partition thelanguage over its alphabet into equivalence classes, each state has a language associated with it. Conditions that describe the language of each state are entered by the student in the form of conditional expressions with function calls and/or regular expressions. A brute-force approach is then used to check that each state's condition correctly describes all of the strings in its language and that none of the strings in a state's language meet the condition for another state. Feedback is provided that either confirms that the DFA correctly meets thegiven conditions or alerts the student to a mismatch between the conditions and the DFA.

A student's DFA can be saved in an XML file and submitted for grading. An automated checking tool, known as ProofGrader, can be used to compare a student's DFA with the correct DFA for a given language, thus greatly speeding up the grading of student assignments.
Learning by game-building
Authors: Korte Laura , Anderson Stuart , Pain Helen , Good Judith
Published: September 2007

This paper describes an innovative method for teaching modelling skills in theoretical computer science (e.g. finite state automata, Turing machines). Students acquire a new modelling skill by completing a game-building assignment in which there is a direct and transparent mapping between the game that the student is building and the model in the framework they are trying to master. Through this constructionist approach, the student not only learns by doing, which potentially contributes to understanding, but there is also a significant element of personalization and choice present, which has the potential to increase both motivation and performance.
Increasing interaction and support in the formal languages and automata theory course
Authors: Rodger Susan H. , Lim Jinghui , Reading Stephen
Published: September 2007

The introduction of educational software such as JFLAP into the course Formal Languages and Automata (FLA) has created a learning environment with automatic feedback on theoretical topics. In this paper we show how we further increase the interaction in the FLA course with the expansion of additional theoretical topics in JFLAP, and how we have added grading support into JFLAP for instructors.
Interface-based programming assignments and automatic grading of java programs
Authors: Helmick Michael T.
Published: September 2007

AutoGrader
is a framework developed at Miami University for the automatic grading of student programming assignments written in the Java programming language.
AutoGrader
leverages the abstract concept of interfaces, as implemented by the Java
interface
language construct, in both the assignment and grading of programming assignments. The use of interfaces reinforces the role of procedural abstraction in object-oriented programming and allows for a common API to all student code. This common API then enables automatic grading of program functionality.
AutoGrader
provides a simple instructor API and enables the automatic testing of student code through the Java languagefeatures of
interfaces
and
reflection
.
AutoGrader
alsosupports static code analysis using PMD [4] to detect possible bugs, dead code, suboptimal, and overcomplicated code. While AutoGrader is written in and only handles Java programs, this style of automated grading is adaptable to any language that supports (or can mimic) named interfaces and/or abstract functions and that also supports runtime reflection.
A source code linearization technique for detecting plagiarized programs
Authors: Ji Jeong-Hoon , Woo Gyun , Cho Hwan-Gue
Published: September 2007

It is very important to detect plagiarized programs in the field of computer science education. Therefore, many tools and algorithms have been developed for this purpose. Generally, these tools are operated in two phases. In phase 1, a program plagiarism detecting tool generates an intermediate representation from a given program set. The intermediate representation should reflect the structural characterization of the program. Most tools use the parse tree or token sequence by intermediate representation. In phase 2, the program looks for plagiarized material and evaluates the similarity of two programs. It is helpful to announce the plagiarized metarials between two programs to the instructor. In this paper, we present the static tracing method in order to improve program plagiarism detection accuracy. The static tracing method statically executes a program at the syntax-level and then extracts predefined keywords according to the order of the executed functions. The result of experiment proves this method can detect plagiarism more effectively than the previously released plagiarism detecting method.
Remote and local delivery of cisco education for the vision-impaired
Authors: Armstrong Helen , Murray Iain
Published: September 2007

Vision-impaired students face tremendous obstacles in their quest to access learning materials delivered in web-based and other electronic formats. The predominance of visual prompts, use of flash and animation and the inability of screen reading applications to interpret images all contribute to make much of the current e-learning materials associated with computing studies inaccessible by blind or vision-impaired students. This paper describes a university research project undertaken to improve the accessibility of Cisco e-learning materials for vision-impaired computing students.allThe network architecture which supports the delivery of the Cisco courses to both local and remote vision-impaired students is also presented.
Using screen readers to reinforce web accessibility education
Authors: Freire André Pimenta , de Mattos Fortes Renata Pontin , Barroso Paiva Debora Maria , Santos Turine Marcelo Augusto
Published: September 2007

This paper discusses an approach for Web accessibility education tacking advantage of short introductory courses. In this approach, screen readers were used toallimmerse students in the problems experienced by blind users while using the Web. Experimental results from an evaluation exercise carried out by students showedallthat the use ofallscreen readers was helpful to better understand and to reinforce the concepts of Web accessibility.
Teaching data structures to students who are blind
Authors: Calder Matt , Cohen Robert F. , Lanzoni Jessica , Landry Neal , Skaff Joelle
Published: September 2007

We present our work in assisting students who are blind to understand fundamental data structures. We have developed a system called PLUMB EXTRA
3
(EXploring data sTRuctures using Audible Algorithm Animation) that conveys an algorithm animation using audio cues and speech. This extends our earlier work on presenting graphs to users who are blind.
VERKKOKE
Authors: Alstes Anton , Lindqvist Janne
Published: September 2007

We present an Online Teaching Environment (OTE) that supports "learning by doing" philosophy in teaching telecommunications software and routing. "Learning by doing" is achieved by giving students a programming assignment that introduces them to socket programming and gives them the opportunity to practice implementing simplified routing protocols. The OTE creates individual assignments for students, accepts solution submissions via the Internet, and, finally, checks the assignments automatically. The system also notifies the students of possible mistakes in their solutions, so they can learn from their mistakes, fix them and resubmit the corrected solutions. The teacher needs only to start the system when the course begins and verify the assignment results when students have finished their work.

The OTE is compatible with modern learning management systems through its adherence to the SharableContent Object Reference Model (SCORM) specification. The OTE supports intricate and realistic programming assignments through representative topology generation and sophisticated network simulation.
Visualizing berkeley socket calls in students' programs
Authors: Brown Christian , McDonald Chris
Published: September 2007

The Berkeley Sockets API is a library of functions, macros, and data structures enabling a program to initiate and manage network communication between two or more processes on the same machine, or across a network of machines. The API is the main mechanism by which programs communicate with the operating system's TCP/IP stack and thereby with almost all Internet services and programs.

Socket programming opens a new realm of development for Computer Science students as they are able to create programs that can communicate via the Internet. However, while learning, students frequently misuse the sockets API or have difficulty understanding where run-time and logic errors in their code occur.

Students learning about sockets are typically presented with a series of static diagrams in textbooks that increase in complexity with each progression. These diagrams may not allow the reader to easily comprehend the transition between each step, nor understand which functions in the API perform the events. Space constraints in textbooks often limit a sequence of diagrams to two or three, whereas over 10 calls to the sockets API are often necessary to initiate and undertake communication. Surprisingly, there are no effective tools or general techniques for debugging students' socket programs.

In this paper we present a software solution to visualize the execution of students' programmed interactions with the Berkeley Sockets API. The tool accepts the source code of two or more networking programs and compiles them in such a way that, at run-time, their calls to the socket API and related functions are displayed, together with an annotation of activity and error conditions. The program is not simply a static simulator - it provides a means to visualize the network events in actual student developed program.