bluuebunny/crossref_metadata_2025 huggingface dataset:
Towards a discipline of real-time programming
Authors: Wirth N.
Published: October 2004

Programming is divided into three major categories with increasing complexity of reasoning in program validation: sequential programming,
multi
-programming, and
real-time
programming. By adhering to a strict programming
discipline
and by using a suitable high-level
language
molded after this discipline, we may drastically reduce the complexity of reasoning about concurrency and execution time constraints. This may be the only practical way to make real-time systems analytically verifyable and ultimately reliable. A possible discipline is outlined and expressed in terms of the language
Modula
.
Single-user capabilities in interprocess communication
Authors: Russell Stephen
Published: October 2004

Many distributed operating systems use interprocess communication (IPC) and data transfer schemes which are optimised for a particular architecture: the workstation/server model. In this model, client processes have full control over data transfer. This paper argues that server controlled data transfer is better suited to systems with a hierarchy of servers distributed across a collection of machines. The system proposed integrates a set of IPC primitives, for the exchange of control information, and a capability system for secure data transfer.
Epidemic algorithms for replicated database maintenance
Authors: Demers Alan , Greene Dan , Houser Carl , Irish Wes , Larson John , Shenker Scott , Sturgis Howard , Swinehart Dan , Terry Doug
Published: October 2004

When a database is replicated at many sites, maintaining mutual consistency among the sites in the face of updates is a significant problem. This paper describes several randomized algorithms for distributing updates and driving the replicas toward consistency. The algorithms are very simple and require few guarantees from the underlying communication system, yet they ensure that the effect of every update is eventually reflected in all replicas. The cost and performance of the algorithms are tuned by choosing appropriate distributions in the randomization step. The algorithms are closely analogous to epidemics, and the epidemiology literature aids in understanding their behavior. One of the algorithms has been implemented in the Clearinghouse servers of the Xerox Corporate Internet. solving long-standing problems of high traffic and database inconsistency.
Device management in TURNING PLUS
Authors: Holt R. C.
Published: October 2004

TURING PLUS is a general purpose programming language that is well suited to systems applications such as operating systems, network controllers and embedded software. This note briefly explains how device management is efficiently handled in TURING PLUS using a specialize version of monitors.
The DUNIX distributed operating system
Authors: Litman Ami
Published: October 2004

DUNIX is an operating system that integrates several computers, connected by a packet switching network, into a single UNIX machine. As far as the users and their software can tell, the system is a single large computer running UNIX. This illusion is created by cooperation of the computers' kernels. The kernels' mode of operation is novel. The software is procedure call oriented. The code that implements a specific system call (e.g., open) does not know whether the object in question (the file) is local or remote. That uniformity makes the kernel small and easy to maintain. The system behaves gracefully under subcomponents' failures. Users which do not have objects (files, processes, tty, etc) in a given computer are not disturbed when that computer crashes. The system administrator may switch a disk from a "dead" computer to a healthy one, and remount the disk under the original path-name. After the switch, users may access files in that disk via the same old names. DUNIX exhibits surprisingly high performance. For a compilation benchmark, DUNIX is faster than 4.2 BSD, even if in the DUNIX case all the files in question are remote. Currently, in Bell Communications Research we have an installation running DUNIX over five DEC VAX computers connected by an Ethernet. This installation speaks TCP/IP and is on the Internet network.
Implications of fragmentation dynamic routing for internet datagram authentication
Authors: Tsudik Gene
Published: October 2004

With the recent growth of internets, large networks connecting heterogeneous entities, access control is an issue no longer confined to individual hosts. Recent literature suggests that authentication may have to be performed in gateways as well as on an end-to-end basis. In this paper we discuss the implications of fragmentation and dynamic routing on gateway-level authentication in packet-switched networks like DARPA Internet. Two algorithms are presented that permit fragmentation and dynamic routing to some extent, while allowing the gateways to authenticate successive packets belonging to authorized connections.
Timer description in CCS (Milner), LOTOS (ISO) and timed LOTOS (Quemada-Fernandez). A case analysis
Authors: T'Hooft G.
Published: October 2004

The Calculus of Communicating Systems (CCS) devised by Milner is an algebraic calculus designed to describe and analyze the behaviour of different systems running in parallel. It has generated a lot of variants, amongst which we find the Language of Temporal Ordering Specification (LOTOS) of ISO, which is more precisely used in the domain of data communication protocol specifications. Recently, Quemada and Fernandez proposed the introduction of time in LOTOS (what we call Timed LOTOS henceforth). We specify in CCS, LOTOS and Timed LOTOS a simple handshake protocol with a one shot sender, a one shot receiver and two unidirectional channels with a capacity of one message and the possibility of loosing this message. For each of these specifications, we calculate the corresponding semantics, which show their properties such as the deadlock freeness and the livelock freeness. By the way, we also compare their relative power with respect to timer description. The conclusion is that none of these models is well suited for the description of timers and time out mechanisms. The reason of this is analyzed.
Using the re-export paradigm to build composable Ada software components
Authors: Bardin Bryce M. , Thompson Christopher J.
Published: October 2004

In the construction of reusable software components, transitive composability of parameterized abstractions is important for achieving the functionality desired. We have argued in a previous paper (
"Composable Ada Software Components and the Re-Export Paradigm"
, which was published in a preceding issue of Ada Letters) that the paradigm we call

"re-export"

is the best technique for building robust, composable components in Ada which come close to meeting our standards for software quality. That paper discusses in detail the techniques which Ada provides that are appropriate for composing abstractions using re-export and the difficulties which are encountered in their construction. Because we do not have the space to recapitulate here, our previous paper must be read to provide the necessary context for understanding this one.A concrete example of re-export is presented here in which we attempt to design an abstraction using composable components. After analyzing the successes and shortcomings of this example, we conclude by presenting our view of the current realities of composition in Ada and outlining the general requirements for effective composition of software in Ada.
The algorithms capture approach to Ada transition
Authors: Wood David P.
Published: October 2004

The mandate for the use of the Ada language in Department of Defense software systems, as well as the growing interest in Ada that exists in the commercial software industry, has created the need for planned, systematic transition paths from existing programs to Ada programs. The demands that Ada places on the life-cycle development of software increases the need for careful planning in any Ada transition effort. At the same time, the desire to derive Ada systems from an existing non-Ada baseline also increases the need for careful control of the transition process. This paper examines the general issues behind such a transition, and describes a transition process geared toward maximizing the benefit of the use of the Ada language, while maintaining a tightly-controlled link with existing systems.
An Ada implementation of Marsaglia's universal random number generator
Authors: Harmon Marion G.
Published: October 2004

A useful feature found in most programing languages, but missing from Ada, is a standard predefined (pseudo) random number generator. In this article we present an Ada implementation a "universal" (i.e., portable) random number generator developed by George Marsaglia. This implementation generates real numbers with 24-bit fractions, uniform on the interval (0,1). We also show a sample program along with the resulting random numbers that were generated by executing that program on a Sun workstation under UNIX.
Planar NAE3SAT is in P
Authors: Moret B. M. E.
Published: October 2004

Lichtenstein proposed the use of a "planar" version of 3SAT as a departure point for proofs of
NP
-completeness that would at once prove the general graph problem as well as its restriction to planar graphs to be
NP
-complete. Dyer and Frieze later proved that Planar lin3SAT is also
NP
-complete. Of the three standard versions of 3SAT, only NAE3SAT remained open. We provide a very simple reduction from NAE3SAT to Simple MaxCut, which respects Lichtenstein's conditions; since it is known that the planar version of (Simple) MaxCut is in P, so is the planar version of NAE3SAT, thereby setting the question (if in a somewhat unexpected way).
Using LATEX
Authors: Trickey H.
Published: October 2004

This note explains how to use a IAT
E
X style that produces a good approximation to the style used in SIAM journals. The note is itself an example of the siam style in action.
Complexity theory
Authors: Hemaspaandra Lane A.
Published: October 2004

We present high-level technical summaries of five recent results on the computational complexity of the shortest lattice vector problem.
Untrusted hosts and confidentiality
Authors: Zdancewic Steve , Zheng Lantian , Nystrom Nathaniel , Myers Andrew C.
Published: October 2004

This paper presents secure program partitioning, a language-based technique for protecting confidential data during computation in distributed systems containing mutually untrusted hosts. Confidentiality and integrity policies can be expressed by annotating programs with security types that constrain information flow; these programs can then be partitioned automatically to run securely on heterogeneously trusted hosts. The resulting communicating subprograms collectively implement the original program, yet the system as a whole satisfies the security requirements of participating principals without requiring a universally trusted host machine. The experience in applying this methodology and the performance of the resulting distributed code suggest that this is a promising way to obtain secure distributed computation.
BASE
Authors: Rodrigues Rodrigo , Castro Miguel , Liskov Barbara
Published: October 2004

Software errors are a major cause of outages and they are increasingly exploited in malicious attacks. Byzantine fault tolerance allows replicated systems to mask some software errors but it is expensive to deploy. This paper describes a replication technique, BASE, which uses abstraction to reduce the cost of Byzantine fault tolerance and to improve its ability to mask software errors. BASE reduces cost because it enables reuse of off-the-shelf service implementations. It improves availability because each replica can be repaired periodically using an abstract view of the state stored by correct replicas, and because each replica can run distinct or non-deterministic service implementations, which reduces the probability of common mode failures. We built an NFS service where each replica can run a different off-the-shelf file system implementation, and an object-oriented database where the replicas ran the same, non-deterministic implementation. These examples suggest that our technique can be used in practice --- in both cases, the implementation required only a modest amount of new code, and our performance results indicate that the replicated services perform comparably to the implementations that they reuse.
Bugs as deviant behavior
Authors: Engler Dawson , Chen David Yu , Hallem Seth , Chou Andy , Chelf Benjamin
Published: October 2004

A major obstacle to finding program errors in a real system is knowing what correctness rules the system must obey. These rules are often undocumented or specified in an ad hoc manner. This paper demonstrates techniques that automatically extract such checking information from the source code itself, rather than the programmer, thereby avoiding the need for a priori knowledge of system rules.The cornerstone of our approach is inferring programmer "beliefs" that we then cross-check for contradictions. Beliefs are facts implied by code: a dereference of a pointer, p, implies a belief that p is non-null, a call to "unlock(1)" implies that 1 was locked, etc. For beliefs we know the programmer must hold, such as the pointer dereference above, we immediately flag contradictions as errors. For beliefs that the programmer may hold, we can assume these beliefs hold and use a statistical analysis to rank the resulting errors from most to least likely. For example, a call to "spin_lock" followed once by a call to "spin_unlock" implies that the programmer may have paired these calls by coincidence. If the pairing happens 999 out of 1000 times, though, then it is probably a valid belief and the sole deviation a probable error. The key feature of this approach is that it requires no a priori knowledge of truth:
if two beliefs contradict, we know that one is an error without knowing what the correct belief is
.Conceptually, our checkers extract beliefs by tailoring rule "templates" to a system --- for example, finding all functions that fit the rule template "
a
must be paired with
b
." We have developed six checkers that follow this conceptual framework. They find hundreds of bugs in real systems such as Linux and OpenBSD. From our experience, they give a dramatic reduction in the manual effort needed to check a large system. Compared to our previous work [9], these template checkers find ten to one hundred times more rule instances and derive properties we found impractical to specify manually.
An empirical study of operating systems errors
Authors: Chou Andy , Yang Junfeng , Chelf Benjamin , Hallem Seth , Engler Dawson
Published: October 2004

We present a study of operating system errors found by automatic, static, compiler analysis applied to the Linux and OpenBSD kernels. Our approach differs from previous studies that consider errors found by manual inspection of logs, testing, and surveys because static analysis is applied uniformly to the entire kernel source, though our approach necessarily considers a less comprehensive variety of errors than previous studies. In addition, automation allows us to track errors over multiple versions of the kernel source to estimate how long errors remain in the system before they are fixed.We found that device drivers have error rates up to three to seven times higher than the rest of the kernel. We found that the largest quartile of functions have error rates two to six times higher than the smallest quartile. We found that the newest quartile of files have error rates up to twice that of the oldest quartile, which provides evidence that code "hardens" over time. Finally, we found that bugs remain in the Linux kernel an average of 1.8 years before being fixed.
Managing energy and server resources in hosting centers
Authors: Chase Jeffrey S. , Anderson Darrell C. , Thakar Prachi N. , Vahdat Amin M. , Doyle Ronald P.
Published: October 2004

Internet hosting centers serve multiple service sites from a common hardware base. This paper presents the design and implementation of an architecture for resource management in a hosting center operating system, with an emphasis onenergyas a driving resource management issue for large server clusters. The goals are to provision server resources for co-hosted services in a way that automatically adapts to offered load, improve the energy efficiency of server clusters by dynamically resizing the active server set, and respond to power supply disruptions or thermal events by degrading service in accordance with negotiated Service Level Agreements (SLAs).Our system is based on an economic approach to managing shared server resources, in which services "bid" for resources as a function of delivered performance. The system continuously monitors load and plans resource allotments by estimating the value of their effects on service performance. A greedy resource allocation algorithm adjusts resource prices to balance supply and demand, allocating resources to their most efficient use. A reconfigurable server switching infrastructure directs request traffic to the servers assigned to each service. Experimental results from a prototype confirm that the system adapts to offered load and resource availability, and can reduce server energy usage by 29% or more for a typical Web workload.
Anticipatory scheduling
Authors: Iyer Sitaram , Druschel Peter
Published: October 2004

Disk schedulers in current operating systems are generally work-conserving, i.e., they schedule a request as soon as the previous request has finished. Such schedulers often require multiple outstanding requests from each process to meet system-level goals of performance and quality of service. Unfortunately, many common applications issue disk read requests in a synchronous manner, interspersing successive requests with short periods of computation. The scheduler chooses the next request too early; this induces
deceptive idleness,
a condition where the scheduler incorrectly assumes that the last request issuing process has no further requests, and becomes forced to switch to a request from another process.We propose the
anticipatory disk scheduling framework
to solve this problem in a simple, general and transparent way, based on the non-work-conserving scheduling discipline. Our FreeBSD implementation is observed to yield large benefits on a range of microbenchmarks and real workloads. The Apache webserver delivers between 29% and 71% more throughput on a disk-intensive workload. The Andrew filesystem benchmark runs faster by 8%, due to a speedup of 54% in its read-intensive phase. Variants of the TPC-B database benchmark exhibit improvements between 2% and 60%. Proportional-share schedulers are seen to achieve their contracts accurately and efficiently.
Mesh-based content routing using XML
Authors: Snoeren Alex C. , Conley Kenneth , Gifford David K.
Published: October 2004

We have developed a new approach for reliably multicasting time-critical data to heterogeneous clients over mesh-based overlay networks. To facilitate intelligent content pruning, data streams are comprised of a sequence of XML packets and forwarded by application-level XML routers. XML routers perform content-based routing of individual XML packets to other routers or clients based upon queries that describe the information needs of downstream nodes. Our PC-based XML router prototype can route an 18 Mbit per second XML stream.Our routers use a novel Diversity Control Protocol (DCP) for router-to-router and router-to-client communication. DCP reassembles a received stream of packets from one or more senders using the first copy of a packet to arrive from any sender. When each node is connected to
n
parents, the resulting network is resilient to (
n
− 1) router or independent link failures without repair. Associated mesh algorithms permit the system to recover to (
n
− 1) resilience after node and/or link failure. We have deployed a distributed network of XML routers that streams real-time air traffic control data. Experimental results show multiple senders improve reliability and latency when compared to tree-based networks.
Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility
Authors: Rowstron Antony , Druschel Peter
Published: October 2004

This paper presents and evaluates the storage management and caching in PAST, a large-scale peer-to-peer persistent storage utility. PAST is based on a self-organizing, Internet-based overlay network of storage nodes that cooperatively route file queries, store multiple replicas of files, and cache additional copies of popular files.In the PAST system, storage nodes and files are each assigned uniformly distributed identifiers, and replicas of a file are stored at nodes whose identifier matches most closely the file's identifier. This statistical assignment of files to storage nodes approximately balances the number of files stored on each node. However, non-uniform storage node capacities and file sizes require more explicit storage load balancing to permit graceful behavior under high global storage utilization; likewise, non-uniform popularity of files requires caching to minimize fetch distance and to balance the query load.We present and evaluate PAST, with an emphasis on its storage management and caching system. Extensive trace-driven experiments show that the system minimizes fetch distance, that it balances the query load for popular files, and that it displays graceful degradation of performance as the global storage utilization increases beyond 95%.
Wide-area cooperative storage with CFS
Authors: Dabek Frank , Kaashoek M. Frans , Karger David , Morris Robert , Stoica Ion
Published: October 2004

The Cooperative File System (CFS) is a new peer-to-peer read-only storage system that provides provable guarantees for the efficiency, robustness, and load-balance of file storage and retrieval. CFS does this with a completely decentralized architecture that can scale to large systems. CFS servers provide a distributed hash table (DHash) for block storage. CFS clients interpret DHash blocks as a file system. DHash distributes and caches blocks at a fine granularity to achieve load balance, uses replication for robustness, and decreases latency with server selection. DHash finds blocks using the Chord location protocol, which operates in time logarithmic in the number of servers.CFS is implemented using the SFS file system toolkit and runs on Linux, OpenBSD, and FreeBSD. Experience on a globally deployed prototype shows that CFS delivers data to clients as fast as FTP. Controlled tests show that CFS is scalable: with 4,096 servers, looking up a block of data involves contacting only seven servers. The tests also demonstrate nearly perfect robustness and unimpaired performance even when as many as half the servers fail.
From the Chair
Authors: Sipior Janice C. , Schatzberg Laurie
Published: October 2004

With this issue, please join me in welcoming our new
Data Base
Co-Editors, Wynne Chin of the University of Houston and Dorothy Leidner of Texas Christian University (Baylor University from Summer 2002). SIGMIS looks forward to their contributing to the continued success of Data Base.You will soon be asked to vote for the merger of ACM-SIGMIS and ACM-SIGCPR (Special Interest Group on Computer Personnel Research). The fields of MIS and CPR broadly overlap, as is evident by the high degree of membership overlap between these two SIGs. The merger is a natural development that will strengthen SIGMIS through the coordination of previously separate activities. I wish to thank Fred Niederman for his insight in preparing the merger proposal. Please look for a postal mailing of the proposal letter detailing the merger and a ballot to be issued by ACM. I strongly recommend approval of the proposed merger.Please look for the Call for Participation for the 11th International Conference on Information and Knowledge Management (CIKM2002) in this issue. Your participation is welcome! Additional information may be found at http://www.cikm.org/2002. CIKM is sponsored by ACM-SIGIR (Special Interest Group on Information Retrieval) and ACM-SIGMIS.Finally, I would like to thank all of our members and their guests who attended the "First Annual ACM-SIGMIS Recognition Reception," held as an ACM-SIGMIS event on Saturday, December 15, 2001, prior to the International Conference on Information Systems (ICIS2001) in New Orleans, Louisiana, USA. The reception was very well attended. We intend for this to be an annual event to recognize the accomplishments of SIGMIS members in areas such as teaching, research, and service to SIGMIS.Thank you for your support of SIGMIS. We encourage your comments and suggestions. Should you have any questions, ideas, or other input, please feel free to contact any one of us.
Enterprise resource planning (ERP) systems as a technology of power
Authors: Sia Siew Kien , Tang May , Soh Christina , Boh Wai Fong
Published: October 2004

This paper explores ERP as an ambivalent technology of power. On the one hand, it may tighten management control by bringing a new level of panoptic visibility to organizational activities; on the other hand, the embedded business model within the ERP may drive empowerment of employees and greater control relaxation through the configuration of new process design. How will the implementation of an ERP system affect organizational control? Our This research seeks to understand how the different forces play out in the context of ERP implementation, and to explore the implications for traditional power distribution in organizations.This paper adopts a mixed qualitative-quantitative methodology in an intensive case study of a restructured hospital in Singapore. A survey of 260 users was administered, supplemented by approximately 27 hours of individual interviews with 23 people. Results reveal that although ERP as a technology can facilitate both empowerment and panoptic control, management has consciously resisted empowerment by working to re-institute the "loss of power" driven by power lost through the ERP implementation. On the other hand, the new panoptic visibility, though partially unintended, appears to have evolved naturally and was readily learnted and applied in the organization. This study is significant in exposing the likelihood of ERP implementation as a technology to that perpetuates management power. At least in the context of the hospital studied, it is yet another means of enlarging the management authority for "total control."
Tell me a good story
Authors: Alvarez Rosío , Urla Jacqueline
Published: October 2004

This paper reports on a participant-observation study examining how clients use narratives to convey information during ERP requirements analysis interviews. Techniques drawn from narrative analysis are used to analyze the structure and content of different types of narratives clients tell during requirements analysis interviews. First, findings reveal that interviewees organized their experience, sought to persuade listeners, and conveyed information to analysts using "stories," "habitual," and "hypothetical" narratives. We argue that cClient narratives provide a pragmatic view of the information system, offering insight into the ways the system is actually used and the habitual practices of the work environment. Second, narratives function to signal the embeddedness of the information system in its larger organizational and social context.While analysts may be inclined to dismiss narratives as messy or asuncodeable data, we argue that the insights they provide merit attention. To the degree that narratives give insight into users' perspectives on organizational issues, they provide knowledge that is essential to any information systems project. This is especially true for ERP projects that, unlike other systems projects, seek to integrate processes spanning the entire organization. ERP projects typically require departments with very different priorities and vocabularies to radically rethink the organization and its habitual practices. Work habits, values, and dilemmas faced by users as recounted in narratives are likely to carry over after the legacy system has been removed. Hence, a sound grasp of these factors is surely advantageous for analysts in assessing the current and future environment of the organization. Future implications for research and practice are also discussed.
Analysis of the autonomous system network topology
Authors: Magoni Damien , Pansiot Jean Jacques
Published: October 2004

Mapping the Internet is a major challenge for network researchers. It is the key to building a successful modeling tool able to generate realistic graphs for use in networking simulations. In this paper we provide a detailed analysis of the inter-domain topology of the Internet. The collected data and the resulting analysis began in November 1997 and cover a period of two and a half years. We give results concerning major topology properties (nodes and edges number, average degree and distance, routing policy, etc.) and main distributions (degree, distance, etc.). We also present many results about the trees of this network. The evolution of these properties is reviewed and major trends are highlighted. We propose some empirical laws that match this current evolution. Four new power-laws concerning the number of shortest paths between node pairs and the tree size distribution are provided with their detailed validation.
An analysis of using reflectors for distributed denial-of-service attacks
Authors: Paxson Vern
Published: October 2004

Attackers can render distributed denial-of-service attacks more difficult to defend against by bouncing their flooding traffic off of
reflectors
; that is, by spoofing requests from the victim to a large set of Internet servers that will in turn send their combined replies to the victim. The resulting dilution of locality in the flooding stream complicates the victim's abilities both to isolate the attack traffic in order to block it, and to use traceback techniques for locating the source of streams of packets with spoofed source addresses, such as ITRACE [Be00a], probabilistic packet marking [SWKA00], [SP01], and SPIE [S+01]. We discuss a number of possible defenses against reflector attacks, finding that most prove impractical, and then assess the degree to which different forms of reflector traffic will have characteristic signatures that the victim can use to identify and filter out the attack traffic. Our analysis indicates that three types of reflectors pose particularly significant threats: DNS and Gnutella servers, and TCP-based servers (particularly Web servers) running on TCP implementations that suffer from predictable initial sequence numbers. We argue in conclusion in support of "reverse ITRACE" [Ba00] and for the utility of packet traceback techniques that work even for low volume flows, such as SPIE.
Child-proof authentication for MIPv6 (CAM)
Authors: O'Shea Greg , Roe Michael
Published: October 2004

We present a unilateral authentication protocol for protecting IPv6 networks against abuse of mobile IPv6 primitives. A mobile node uses a partial hash of its public key for its IPv6 address. Our protocol integrates distribution of public keys and protects against falsification of network addresses. Our protocol is easy to implement, economic to deploy and lightweight in use. It is intended to enable experimentation with (mobile) IPv6 before the transition to a comprehensive IPSEC infrastructure.
TCP/IP traffic dynamics and network performance
Authors: Joo Youngmi , Ribeiro Vinay , Feldmann Anja , Gilbert Anna C. , Willinger Walter
Published: October 2004

The main objective of this paper is to demonstrate in the context of a simple TCP/IP-based network that depending on the underlying assumptions about the inherent nature of the dynamics of network traffic, very different conclusions can be derived for a number of well-studied and apparently well-understood problems in the area of performance evaluation. For example, a traffic workload model can either completely ignore the empirically observed high variability at the TCP connection level (i.e., assume "infinite sources") or explicitly account for it with the help of heavy-tailed distributions for TCP connection sizes or durations. Based on detailed
ns-2
simulation results, we illustrate that these two commonly-used traffic workload scenarios can give rise to fundamentally different buffer dynamics in IP routers. Using a second set of
ns-2
simulation experiments, we also illustrate a qualitatively very different queueing behavior within IP routers depending on whether the traffic arriving at the router is assumed to be endogenous in nature (i.e., a result of the "closed loop" nature of the feedback-based congestion control algorithm of TCP) or exogenously determined (i.e., given by some conventional traffic model --- a fixed "open loop" description of the traffic as seen by the router).
Optimised batch patching with classes of service
Authors: White Paul P. , Crowcroft Jon
Published: October 2004

In this paper we present a new technique called Optimised Batch Patching with Classes of Service(OBP with CoS) which can be used to leverage the benefits of multicast within the context of 'near' video-on-demand systems in IP networks. OBP with CoS builds on an earlier scheme, known as Optimised Patching, but is different in two respects. Firstly, in OBP with CoS, the server artificially delays requests in order to increase the probability of accumulating duplicates, thereby allowing greater exploitation of multicast compared to Optimised Patching albeit at the expense of higher latency until commencement of service. Secondly, the client is able to request a latency class of service which reflects how long the client is prepared to wait until playout of the video. The server scheduling algorithm attempts to minimise network bandwidth consumption within the constraints imposed by the class of each request. We present analysis and simulations of our scheme in order to validate its effectiveness.
Synthesis of fractional gaussian noise using linear approximation for generating self-similar network traffic
Authors: Ledesma Sergio , Liu Derong
Published: October 2004

The present paper focuses on self-similar network traffic generation. Network traffic modeling studies the generation of synthetic sequences. The generated sequences must have similar features to the measured traffic. Exact methods for generating self-similar sequences are not appropriate for long traces. Our main objective in the present paper is to improve the efficiency of Paxson's method for synthesizing self-similar network traffic. Paxson's method uses a fast, approximate synthesis for the power spectrum of the FGN and uses the inverse Fourier transform to obtain the time-domain sequences. We demonstrate that a linear approximation can be used to determine the power spectrum of the FGN. This linear approximation reduces the complexity of the computation without compromising the accuracy in synthesizing the power spectrum of the FGN. Our results show that long traces can be generated in much less time. To compare our method with existing ones, we will measure the running time in generating long and short sample paths from the FGN. We will also conduct experiments to show that our method can generate self-similar traffic for specified Hurst parameters with high accuracy.
Notes on the use of RTP for shared workspace applications
Authors: Perkins Colin , Crowcroft Jon
Published: October 2004

The Real-time Transport Protocol, RTP, has become the dominant protocol for streaming audio and video in IP-based environments. A number of proposals have been made which attempt to build on this success and apply RTP for shared workspace applications. We discuss the needs of such applications and the features provided by RTP, with an aim to showing why RTP is not appropriate for such uses.
Analysis of errors in network load measurements
Authors: Belenki Stanislav , Tafvelin Sven
Published: October 2004

The paper identifies elements in network monitoring systems that cause errors in the load measurements found in recent reports on network statistics from an academic backbone network. Two types of network monitors are investigated: counter-based and packet capturing. The paper explains how to assign an accuracy term to the load values in case of counter-based monitors and how to eliminate distortion in the case of packet capturing monitors. The paper also suggests an MIB to reduce the counter-based measurement error.
Effects of ensemble-TCP
Authors: Eggert Lars , Heidemann John , Touch Joe
Published: October 2004

TCP currently recalculates the state of each connection from a fixed set of initial parameters; this recalculation occurs over several round trips, during which the connection can be less than efficient. TCP control block sharing is a technique for reusing information among connections in series and aggregating it among connections in parallel. This paper explores the design space of a modified TCP stack that utilizes these two ideas, and one possible design (E-TCP) is presented in detail. E-TCP has been designed so that the network transmission behavior of group of parallel E-TCP connections closely resembles that of a single TCP/Reno connection. Simulated web accesses using HTTP/1.0 over E-TCP show a significant performance improvement compared to TCP/Reno connection bundles. This paper is first to evaluate performance using four different intra-ensemble schedulers for different workloads. In one scenario simulating a common case, E-TCP is 4-75% faster than Reno for transmitting the HTML parts of various pages, and 17-61% faster transmitting the whole pages. In the same scenario, reusing cached state speeds up repeated E-TCP page accesses by 17-53% for the HTML parts and 10-28% for the whole pages, compared to the initial access. E-TCP can also be integrated with other proposed TCP extensions (such as TCP/Vegas or TCP/SACK), to further improve performance.
The Eifel algorithm
Authors: Ludwig Reiner , Katz Randy H.
Published: October 2004

We propose an enhancement to TCP's error recovery scheme, which we call the
Eifel algorithm
. It eliminates the retransmission ambiguity, thereby solving the problems caused by spurious timeouts and spurious fast retransmits. It can be incrementally deployed as it is backwards compatible and does not change TCP's congestion control semantics. In environments where spurious retransmissions occur frequently, the algorithm can improve the end-to-end throughput by several tens of percent. An exact quantification is, however, highly dependent on the path characteristics over time. The Eifel algorithm finally makes TCP truly wireless-capable without the need for proxies between the end points. Another key novelty is that the Eifel algorithm provides for the implementation of a more optimistic retransmission timer because it reduces the penalty of a spurious timeout to a single (in the common case) spurious retransmission.
A survey of web caching schemes for the Internet
Authors: Wang Jia
Published: October 2004

The World Wide Web can be considered as a large distributed information system that provides access to shared data objects. As one of the most popular applications currently running on the Internet, the World Wide Web is of an exponential growth in size, which results in network congestion and server overloading. Web caching has been recognized as one of the effective schemes to alleviate the service bottleneck and reduce the network traffic, thereby minimize the user access latency. In this paper, we first describe the elements of a Web caching system and its desirable properties. Then, we survey the state-of-art techniques which have been used in Web caching systems. Finally, we discuss the research frontier in Web caching.
Operational and performance issues of a CBQ router
Authors: Risso Fulvio , Gevros Panos
Published: October 2004

The use of scheduling mechanisms like Class Based Queueing (CBQ) is expected to play a key role in next generation multiservice IP networks. In this paper we attempt an experimental evaluation of ALTQ/CBQ demonstrating its sensitivity to a wide range of parameters and link layer driver design issues. We pay attention to several CBQ internal parameters that affect performance drastically and particularly to "borrowing", a key feature for flexible and efficient link sharing. We are also investigating cases where the link sharing rules are violated, explaining and correcting these effects wheneverpossible. Finally we evaluate CBQ performance and make suggestions for effective deployment in real networks.
A fair certification protocol
Authors: Mitchell Chris J. , Rantos Konstantinos
Published: October 2004

In this paper a 'fair' key generation and certification protocol for Diffie-Hellman keys is proposed, which is intended for use in cases where neither User nor CA are trusted to choose the User's key on their own. This protocol also ensures that key agreement mechanism 1 in ISO/IEC 11770-3 [2] provides 'fair key agreement' [4].
Wireless data communications using DECT air interface
Authors: Muchaxo António , Sousa Alexandre , Pereira Nuno , Sarmento Helena
Published: October 2004

DECT is an approved ETSI standard for cordless communications, defined as a general radio access technology that can be used as the air interface to any network. In addition to the well-established voice service, it supports data communications. DECT currently addresses low bit rates, but additional modulation options have recently been included for high-speed, up to 2Mbps. In this paper, we describe the hardware and software design of an entire wireless communications system to be used in SOHO applications. While putting the emphasis on data communication, we demonstrate the feasibility of maintaining the compatibility with existent voice terminals. We developed generic hardware and software components, which revealed a very flexible approach. We easily created a wireless LANs, extended an Ethernet LAN and provided access to ISDN 1.
A review of port scanning techniques
Authors: de Vivo Marco , Carrasco Eddy , Isern Germinal , de Vivo Gabriela O.
Published: October 2004

This paper reports the most important techniques used by

TCP
port scanners

. TCP port scanners are specialized programs used to determine what TCP ports of a host have processes
listening on
them for possible connections. Since these ports characterize, in part, the amount of exposure of the hosts to potential external attacks, knowing their existence is a fundamental matter for network and/or security administrators. Moreover, as scanners are also used by hackers, administrators need to know how they work and what possible weakness they exploit to be able to prevent unwanted scanning or at least to record each scanning attempt.
Independent active program representation using ASN. 1
Authors: Williamson Brad , Farrell Craig
Published: October 2004

The future success of computer communications will largely depend on how effectively applications achieve their desired quality of service (QoS). Active networks move closer to the goal of application specified QoS by allowing user-specified network related computation to be
injected
into the network elements. Although research into active networks is in its infancy, one area that has not yet received much attention is the representation of active programs. The Active Network Encapsulation Protocol (ANEP) has made a significant effort towards producing a common definition, however, as the name suggests, ANEP has only gone as far as the packet header for encapsulating an active program. The contribution of this paper is to show how an independent packet representation such as Abstract Syntax Notation One (ASN.1) can be used as a common substrate for representing active programs. An active networking framework, using ASN.1 whereby any active network solution can be deployed independently of the active network element's architecture is discussed. In this paper, we demonstrate the independent representation using a simple procedural language. This technique however is language independent and can be extended to cover any language including all those currently used in active networks. ASN.1 is ideally suited to this purpose since it was originally conceived as a language for the representation of programs and data types in protocol data units (PDUs). This solution maintains security, mobility and efficiency.
Context-agile encryption for high speed communication networks
Authors: Pierson Lyndon G. , Witzke Edward L. , Bean Mark O. , Trombley Gerry J.
Published: October 2004

Different applications have different security requirements for data privacy, data integrity, and authentication. Encryption is one technique that addresses these requirements. Encryption hardware, designed for use in high-speed communications networks, can satisfy a wide variety of security requirements if the hardware implementation is key-agile, key length-agile, mode-agile, and algorithm-agile. Hence, context-agile encryption provides enhanced solutions to the secrecy, interoperability, and quality of service issues in high-speed networks. Moreover, having a single context-agile encryptor at an ATM aggregation point (such as a firewall) reduces hardware and administrative costs. While single-algorithm, key-agile encryptors exist, encryptors that are agile in a cryptographic robustness sense, are still research topics.
Cellular IP
Authors: Valkó András G.
Published: October 2004

This paper describes a new approach to Internet host mobility. We argue that by separating local and wide area mobility, the performance of existing mobile host protocols (e.g. Mobile IP) can be significantly improved. We propose Cellular IP, a new lightweight and robust protocol that is optimized to support local mobility but efficiently interworks with Mobile IP to provide wide area mobility support. Cellular IP shows great benefit in comparison to existing host mobility proposals for environments where mobile hosts migrate frequently, which we argue, will be the rule rather than the exception as Internet wireless access becomes ubiquitous. Cellular IP maintains distributed cache for location management and routing purposes. Distributed paging cache coarsely maintains the position of 'idle' mobile hosts in a service area. Cellular IP uses this paging cache to quickly and efficiently pinpoint 'idle' mobile hosts that wish to engage in 'active' communications. This approach is beneficial because it can accommodate a large number of users attached to the network without overloading the location management system. Distributed routing cache maintains the position of active mobile hosts in the service area and dynamically refreshes the routing state in response to the handoff of active mobile hosts. These distributed location management and routing algorithms lend themselves to a simple and low cost implementation of Internet host mobility requiring no new packet formats, encapsulations or address space allocation beyond what is present in IP.