TY - CONF T1 - Applying graphics processor acceleration in a software defined radio prototyping environment T2 - 2011 22nd IEEE International Symposium on Rapid System Prototyping (RSP) Y1 - 2011 A1 - Plishker,W. A1 - Zaki, G.F. A1 - Bhattacharyya, Shuvra S. A1 - Clancy, C. A1 - Kuykendall, J. KW - Acceleration KW - coprocessors KW - dataflow foundation KW - GNU radio KW - Graphics processing unit KW - graphics processor acceleration KW - Kernel KW - Libraries KW - multicore platforms KW - Multicore processing KW - PARALLEL PROCESSING KW - Pipelines KW - Protocols KW - software defined radio prototyping environment KW - software radio KW - stand-alone GPU accelerated library AB - With higher bandwidth requirements and more complex protocols, software defined radio (SDR) has ever growing computational demands. SDR applications have different levels of parallelism that can be exploited on multicore platforms, but design and programming difficulties have inhibited the adoption of specialized multicore platforms like graphics processors (GPUs). In this work we propose a new design flow that augments a popular existing SDR development environment (GNU Radio), with a dataflow foundation and a stand-alone GPU accelerated library. The approach gives an SDR developer the ability to prototype a GPU accelerated application and explore its design space fast and effectively. We demonstrate this design flow on a standard SDR benchmark and show that deciding how to utilize a GPU can be non-trivial for even relatively simple applications. JA - 2011 22nd IEEE International Symposium on Rapid System Prototyping (RSP) ER - TY - CONF T1 - On Computing Compression Trees for Data Collection in Wireless Sensor Networks T2 - 2010 Proceedings IEEE INFOCOM Y1 - 2010 A1 - Li,Jian A1 - Deshpande, Amol A1 - Khuller, Samir KW - Approximation algorithms KW - Base stations KW - Communications Society KW - Computer networks KW - Computer science KW - computing compression trees KW - Costs KW - data collection KW - Data communication KW - data compression KW - designing algorithms KW - Educational institutions KW - Entropy KW - graph concept KW - Monitoring KW - Protocols KW - trees (mathematics) KW - weakly connected dominating sets KW - Wireless sensor networks AB - We address the problem of efficiently gathering correlated data from a wireless sensor network, with the aim of designing algorithms with provable optimality guarantees, and understanding how close we can get to the known theoretical lower bounds. Our proposed approach is based on finding an optimal or a near-optimal compression tree for a given sensor network: a compression tree is a directed tree over the sensor network nodes such that the value of a node is compressed using the value of its parent. We focus on broadcast communication model in this paper, but our results are more generally applicable to a unicast communication model as well. We draw connections between the data collection problem and a previously studied graph concept called weakly connected dominating sets, and we use this to develop novel approximation algorithms for the problem. We present comparative results on several synthetic and real-world datasets showing that our algorithms construct near-optimal compression trees that yield a significant reduction in the data collection cost. JA - 2010 Proceedings IEEE INFOCOM PB - IEEE SN - 978-1-4244-5836-3 M3 - 10.1109/INFCOM.2010.5462035 ER - TY - CONF T1 - Replication and automation of expert judgments: Information engineering in legal e-discovery T2 - IEEE International Conference on Systems, Man and Cybernetics, 2009. SMC 2009 Y1 - 2009 A1 - Hedin,B. A1 - Oard, Douglas KW - authorisation KW - authority control KW - Automation KW - civil litigation KW - CYBERNETICS KW - Delay KW - digital evidence retrieval KW - discovery request KW - Educational institutions KW - expert judgment automation KW - Human computer interaction KW - Human-machine cooperation and systems KW - human-system task modeling KW - information engineering KW - Information retrieval KW - interactive task KW - Law KW - law administration KW - legal e-discovery KW - Legal factors KW - PROBES KW - Production KW - Protocols KW - search effort KW - Search methods KW - text analysis KW - text retrieval conference legal track KW - United States KW - USA Councils KW - User modeling AB - The retrieval of digital evidence responsive to discovery requests in civil litigation, known in the United States as ¿e-discovery,¿ presents several important and understudied conditions and challenges. Among the most important of these are (i) that the definition of responsiveness that governs the search effort can be learned and made explicit through effective interaction with the responding party, (ii) that the governing definition of responsiveness is generally complex, deriving both from considerations of subject-matter relevance and from considerations of litigation strategy, and (iii) that the result of the search effort is a set (rather than a ranked list) of documents, and sometimes a quite large set, that is turned over to the requesting party and that the responding party certifies to be an accurate and complete response to the request. This paper describes the design of an ¿interactive task¿ for the text retrieval conference's legal track that had the evaluation of the effectiveness of e-discovery applications at the ¿responsive review¿ task as its goal. Notable features of the 2008 interactive task were high-fidelity human-system task modeling, authority control for the definition of ¿responsiveness,¿ and relatively deep sampling for estimation of type 1 and type 2 errors (expressed as ¿precision¿ and ¿recall¿). The paper presents a critical assessment of the strengths and weaknesses of the evaluation design from the perspectives of reliability, reusability, and cost-benefit tradeoffs. JA - IEEE International Conference on Systems, Man and Cybernetics, 2009. SMC 2009 PB - IEEE SN - 978-1-4244-2793-2 M3 - 10.1109/ICSMC.2009.5346118 ER - TY - CONF T1 - Approximation Algorithms for Computing Capacity of Wireless Networks with SINR Constraints T2 - IEEE INFOCOM 2008. The 27th Conference on Computer Communications Y1 - 2008 A1 - Chafekar,D. A1 - Kumart,V. S.A A1 - Marathe,M. V A1 - Parthasarathy,S. A1 - Srinivasan, Aravind KW - Algorithm design and analysis KW - approximation algorithm KW - Approximation algorithms KW - approximation theory KW - Computer networks KW - Computer science KW - graph theory KW - graph-based model KW - Interference constraints KW - polynomial time algorithm KW - Propagation losses KW - Protocols KW - radio networks KW - radiofrequency interference KW - signal to interference plus noise ratio KW - Signal to noise ratio KW - Throughput KW - wireless interference KW - wireless network KW - Wireless networks AB - A fundamental problem in wireless networks is to estimate its throughput capacity - given a set of wireless nodes, and a set of connections, what is the maximum rate at which data can be sent on these connections. Most of the research in this direction has focused on either random distributions of points, or has assumed simple graph-based models for wireless interference. In this paper, we study capacity estimation problem using the more general Signal to Interference Plus Noise Ratio (SINR) model for interference, on arbitrary wireless networks. The problem becomes much harder in this setting, because of the non-locality of the SINR model. Recent work by Moscibroda et al. (2006) has shown that the throughput in this model can differ from graph based models significantly. We develop polynomial time algorithms to provably approximate the total throughput in this setting. JA - IEEE INFOCOM 2008. The 27th Conference on Computer Communications PB - IEEE SN - 978-1-4244-2025-4 M3 - 10.1109/INFOCOM.2008.172 ER - TY - JOUR T1 - Efficient lookup on unstructured topologies JF - IEEE Journal on Selected Areas in Communications Y1 - 2007 A1 - Morselli,R. A1 - Bhattacharjee, Bobby A1 - Marsh,M.A. A1 - Srinivasan, Aravind KW - Computer science KW - DHT KW - distributed algorithms KW - Distributed computing KW - distributed hash table KW - Least squares approximation KW - LMS KW - local minima search KW - lookup protocol KW - Network topology KW - node failures KW - Peer to peer computing KW - Performance analysis KW - Protocols KW - replication strategy KW - Resilience KW - Robustness KW - table lookup KW - telecommunication network topology KW - unstructured network topology AB - We present LMS, a protocol for efficient lookup on unstructured networks. Our protocol uses a virtual namespace without imposing specific topologies. It is more efficient than existing lookup protocols for unstructured networks, and thus is an attractive alternative for applications in which the topology cannot be structured as a Distributed Hash Table (DHT). We present analytic bounds for the worst-case performance of LMS. Through detailed simulations (with up to 100,000 nodes), we show that the actual performance on realistic topologies is significantly better. We also show in both simulations and a complete implementation (which includes over five hundred nodes) that our protocol is inherently robust against multiple node failures and can adapt its replication strategy to optimize searches according to a specific heuristic. Moreover, the simulation demonstrates the resilience of LMS to high node turnover rates, and that it can easily adapt to orders of magnitude changes in network size. The overhead incurred by LMS is small, and its performance approaches that of DHTs on networks of similar size VL - 25 SN - 0733-8716 CP - 1 M3 - 10.1109/JSAC.2007.07007 ER - TY - CONF T1 - Assessing the Attack Threat due to IRC Channels Y1 - 2006 A1 - Meyer,R. A1 - Michel Cukier KW - attack threat assessment KW - channel activity KW - client-server systems KW - computer crime KW - intrusion-resilient channels KW - IRC channels KW - IRC protocols KW - Protocols KW - telecommunication channels KW - telecommunication security AB - This practical experience report presents the results of an investigation into the threat of attacks associated with the chat medium IRC. A combination of simulated users (i.e., bots), some configured with scripts that simulated conversations, and regular users were used. The average number of attacks per day a user on IRC can expect, the effect of channel activity, gender based on the name, and network type on the number of attacks were determined. The social structure of IRC channels and the types of users that use it were analyzed. The results indicate that attacks through IRC channels come from human users selecting targets rather than automated scripts targeting every user in a channel M3 - 10.1109/DSN.2006.12 ER - TY - JOUR T1 - Resilient multicast using overlays JF - IEEE/ACM Transactions on Networking Y1 - 2006 A1 - Banerjee,S. A1 - Lee,Seungjoon A1 - Bhattacharjee, Bobby A1 - Srinivasan, Aravind KW - application-layer multicast protocols KW - Computer science KW - Data communication KW - Delay KW - Internet KW - Internet-like topologies KW - IP networks KW - loss recovery technique KW - Multicast KW - multicast data recovery scheme KW - Multicast protocols KW - Network topology KW - NETWORKS KW - overlays KW - Performance loss KW - probabilistic forwarding KW - probabilistic resilient multicast KW - Protocols KW - Resilience KW - Streaming media KW - telecommunication network topology KW - Terminology AB - We introduce Probabilistic Resilient Multicast (PRM): a multicast data recovery scheme that improves data delivery ratios while maintaining low end-to-end latencies. PRM has both a proactive and a reactive components; in this paper we describe how PRM can be used to improve the performance of application-layer multicast protocols especially when there are high packet losses and host failures. Through detailed analysis in this paper, we show that this loss recovery technique has efficient scaling properties-the overheads at each overlay node asymptotically decrease to zero with increasing group sizes. As a detailed case study, we show how PRM can be applied to the NICE application-layer multicast protocol. We present detailed simulations of the PRM-enhanced NICE protocol for 10 000 node Internet-like topologies. Simulations show that PRM achieves a high delivery ratio (>97%) with a low latency bound (600 ms) for environments with high end-to-end network losses (1%-5%) and high topology change rates (5 changes per second) while incurring very low overheads (<5%). VL - 14 SN - 1063-6692 CP - 2 M3 - 10.1109/TNET.2006.872579 ER - TY - CONF T1 - Detection of denial-of-message attacks on sensor network broadcasts Y1 - 2005 A1 - McCune, J.M. A1 - Elaine Shi A1 - Perrig, A. A1 - Reiter, M.K. KW - authenticated acknowledgments KW - broadcast channels KW - broadcast protocols KW - broadcasting base station KW - countermeasures KW - denial-of-message attacks KW - DoM KW - game theory KW - game-theoretic approach KW - malicious sensor nodes KW - Mobile computing KW - optimal attacker KW - probabilistic detection KW - probability KW - Protocols KW - Sampling methods KW - secure implicit sampling KW - sensor network broadcasts KW - SIS KW - telecommunication security KW - Wireless sensor networks AB - So far sensor network broadcast protocols assume a trustworthy environment. However in safety and mission-critical sensor networks this assumption may not be valid and some sensor nodes might be adversarial. In these environments, malicious sensor nodes can deprive other nodes from receiving a broadcast message. We call this attack a denial-of-message attack (DoM). In this paper we model and analyze this attack, and present countermeasures. We present SIS, a secure implicit sampling scheme that permits a broadcasting base station to probabilistically detect the failure of nodes to receive its broadcast, even if these failures result from an attacker motivated to induce these failures undetectably. SIS works by eliciting authenticated acknowledgments from a subset of nodes per broadcast, where the subset is unpredictable to the attacker and tunable so as to mitigate acknowledgment implosion on the base station. We use a game-theoretic approach to evaluate this scheme in the face of an optimal attacker that attempts to maximize the number of nodes it denies the broadcast while remaining undetected by the base station, and show that SIS significantly constrains such an attacker even in sensor networks exhibiting high intrinsic loss rates. We also discuss extensions that permit more targeted detection capabilities. ER - TY - JOUR T1 - End-to-end analysis of distributed video-on-demand systems JF - IEEE Transactions on Multimedia Y1 - 2004 A1 - Mundur, Padma A1 - Simon,R. A1 - Sood,A. K KW - Admission control KW - admission control strategies KW - Analytical models KW - Computer science KW - distributed architecture KW - distributed video-on-demand systems KW - end-to-end analysis KW - global request handling KW - High-speed networks KW - Network servers KW - Next generation networking KW - Performance analysis KW - performance evaluation methodology KW - Protocols KW - request handling KW - reservation protocols KW - resource allocation KW - Resource management KW - signaling protocols KW - telecommunication congestion control KW - video on demand KW - Video sharing AB - The focus of the research presented in this paper is the end-to-end analysis of a distributed Video-on-Demand (VoD) system. We analyze the distributed architecture of a VoD system to design global request handling and admission control strategies and evaluate them using global metrics. The performance evaluation methodology developed in this paper helps in determining efficient ways of using all resources in the VoD architecture within the constraints of providing guaranteed high quality service to each request. For instance, our simulation results show that request handling policies based on limited redirection of blocked requests to other resources perform better than load sharing policies. We also show that request handling policies based on redirection have simpler connection establishment semantics than load sharing policies and, therefore, are easily incorporated into reservation or signaling protocols. VL - 6 SN - 1520-9210 CP - 1 M3 - 10.1109/TMM.2003.819757 ER - TY - JOUR T1 - The dangers of mitigating security design flaws: a wireless case study JF - IEEE Security & Privacy Y1 - 2003 A1 - Petroni,N. L. A1 - Arbaugh, William A. KW - Communication system security KW - computer security KW - cryptography KW - design flaw mitigation KW - Dictionaries KW - legacy equipment KW - privacy KW - Protection KW - Protocols KW - security design flaws KW - security of data KW - synchronous active attack KW - telecommunication security KW - Telecommunication traffic KW - wired equivalent privacy protocol KW - Wireless LAN KW - wireless local area networks KW - Wireless networks AB - Mitigating design flaws often provides the only means to protect legacy equipment, particularly in wireless local area networks. A synchronous active attack against the wired equivalent privacy protocol demonstrates how mitigating one flaw or attack can facilitate another. VL - 1 SN - 1540-7993 CP - 1 M3 - 10.1109/MSECP.2003.1176993 ER - TY - CONF T1 - Dynamic load balancing across mirrored multimedia servers T2 - 2003 International Conference on Multimedia and Expo, 2003. ICME '03. Proceedings Y1 - 2003 A1 - Matthur,A. A1 - Mundur, Padma KW - client-server systems KW - Delay KW - Internet KW - load balancing protocols KW - Load management KW - media streaming KW - metropolitan area network KW - metropolitan area networks KW - mirrored multimedia servers KW - Multimedia communication KW - multimedia servers KW - network packet loss KW - Network servers KW - packet transmission delay KW - Propagation losses KW - Protocols KW - Streaming media KW - Topology KW - Traffic control KW - Web server AB - The purpose of this paper is to present protocols for efficient load balancing across replicated multimedia servers in a metropolitan area network. Current multimedia infrastructures, even when they use mirrored servers, do not have standardized load balancing schemes. Existing schemes frequently require participation from the clients in balancing the load across the servers efficiently. We propose two protocols in this paper for fair load balancing without any client-side processing being required. Neither protocol requires any change to the network-level infrastructure. Using network packet loss and packet transmission delay as the chief metrics, we show the effectiveness of the protocols through extensive simulations. JA - 2003 International Conference on Multimedia and Expo, 2003. ICME '03. Proceedings PB - IEEE VL - 2 SN - 0-7803-7965-9 M3 - 10.1109/ICME.2003.1221551 ER - TY - CONF T1 - A secure service discovery protocol for MANET T2 - 14th IEEE Proceedings on Personal, Indoor and Mobile Radio Communications, 2003. PIMRC 2003 Y1 - 2003 A1 - Yuan Yuan A1 - Arbaugh, William A. KW - ad hoc networks KW - centralized administration KW - Computer architecture KW - Computer science KW - dynamic service discovery infrastructure KW - Educational institutions KW - MANET KW - Manuals KW - mobile ad hoc network KW - Mobile ad hoc networks KW - Mobile computing KW - mobile radio KW - noninfrastructure network KW - Pervasive computing KW - Protocols KW - routing protocols KW - secure service discovery protocol KW - Security KW - service discovery techniques KW - service discovery technologies KW - telecommunication computing KW - telecommunication services KW - XML AB - Service discovery technologies are exploited to enable services to advertise their existence in a dynamic way, and can be discovered, configured and used by other devices with minimum manual efforts. It plays an essential role in future network scenarios especially with development of mobile ad hoc network (MANET) and emergence of pervasive computing. Because MANET allows these devices to communicate dynamically without fixed infrastructure and centralized administration, it gives rise to the challenges of the service discovery techniques. In this paper, we present a dynamic service discovery infrastructure that uses XML to describe services and match using the semantic content of service descriptions for MANET. We believe that the architecture we have designed is a necessary component of service discovery in non-infrastructure network by further exploring the secure and performance issues of this infrastructure. JA - 14th IEEE Proceedings on Personal, Indoor and Mobile Radio Communications, 2003. PIMRC 2003 PB - IEEE VL - 1 SN - 0-7803-7822-9 M3 - 10.1109/PIMRC.2003.1264322 ER - TY - CONF T1 - An adaptive framework for tunable consistency and timeliness using replication Y1 - 2002 A1 - Krishnamurthy, S. A1 - Sanders,W. H. A1 - Michel Cukier KW - adaptive framework KW - concurrent multiple client service KW - consistency requirements KW - dependability requirements KW - distributed object management KW - flexible QoS model KW - lazy update propagation KW - performance history KW - probabilistic approach KW - Protocols KW - quality of service KW - replication KW - temporal requirements KW - timely consistent response KW - tunable consistency KW - tunable timeliness AB - One well-known challenge in using replication to service multiple clients concurrently is that of delivering a timely and consistent response to the clients. In this paper, we address this problem in the context of client applications that have specific temporal and consistency requirements. These applications can tolerate a certain degree of relaxed consistency, in exchange for better response time. We propose a flexible QoS model that allows these clients to specify their temporal and consistency constraints. In order to select replicas to serve these clients, we need to control of the inconsistency of the replicas, so that we have a large enough pool of replicas with the appropriate state to meet a client's timeliness, consistency, and dependability requirements. We describe an adaptive framework that uses lazy update propagation to control the replica inconsistency and employs a probabilistic approach to select replicas dynamically to service a client, based on its QoS specification. The probabilistic approach predicts the ability of a replica to meet a client's QoS specification by using the performance history collected by monitoring the replicas at runtime. We conclude with experimental results based on our implementation. M3 - 10.1109/DSN.2002.1028882 ER - TY - CONF T1 - Formal specification and verification of a group membership protocol for an intrusion-tolerant group communication system Y1 - 2002 A1 - Ramasamy,H. V. A1 - Michel Cukier A1 - Sanders,W. H. KW - computer network reliability KW - distributed processing KW - distributed systems KW - fault tolerant computing KW - formal specification KW - formal verification KW - group membership protocol KW - intrusion-tolerant group communication system KW - PROMELA KW - Protocols AB - We describe a group membership protocol that is part of an intrusion-tolerant group communication system, and present an effort to use formal tools to model and validate our protocol. We describe in detail the most difficult part of the validation exercise, which was the determination of the right level of abstraction of the protocol for formally specifying the protocol. The validation exercise not only formally showed that the protocol satisfies its correctness claims, but also provided information that will help us make the protocol more efficient without violating correctness. M3 - 10.1109/PRDC.2002.1185613 ER - TY - CONF T1 - P5 : a protocol for scalable anonymous communication T2 - 2002 IEEE Symposium on Security and Privacy, 2002. Proceedings Y1 - 2002 A1 - Sherwood,R. A1 - Bhattacharjee, Bobby A1 - Srinivasan, Aravind KW - Broadcasting KW - communication efficiency KW - Computer science KW - cryptography KW - data privacy KW - Educational institutions KW - Internet KW - large anonymous groups KW - P5 protocol KW - packet-level simulations KW - Particle measurements KW - Peer to peer computing KW - peer-to-peer personal privacy protocol KW - privacy KW - Protocols KW - receiver anonymity KW - scalable anonymous communication KW - security of data KW - sender anonymity KW - sender-receiver anonymity KW - Size measurement KW - telecommunication security AB - We present a protocol for anonymous communication over the Internet. Our protocol, called P5 (peer-to-peer personal privacy protocol) provides sender-, receiver-, and sender-receiver anonymity. P5 is designed to be implemented over current Internet protocols, and does not require any special infrastructure support. A novel feature of P5 is that it allows individual participants to trade-off degree of anonymity for communication efficiency, and hence can be used to scalably implement large anonymous groups. We present a description of P5, an analysis of its anonymity and communication efficiency, and evaluate its performance using detailed packet-level simulations. JA - 2002 IEEE Symposium on Security and Privacy, 2002. Proceedings PB - IEEE SN - 0-7695-1543-6 M3 - 10.1109/SECPRI.2002.1004362 ER - TY - CONF T1 - Smart videoconferencing T2 - 2000 IEEE International Conference on Multimedia and Expo, 2000. ICME 2000 Y1 - 2000 A1 - Zotkin,Dmitry N A1 - Duraiswami, Ramani A1 - Philomin,V. A1 - Davis, Larry S. KW - acoustical processing KW - Automatic control KW - CAMERAS KW - computerised control KW - control software KW - Control systems KW - Intelligent sensors KW - Layout KW - Microphones KW - multi-camera multi-microphone set-up KW - multimedia systems KW - Protocols KW - prototype implementation KW - Prototypes KW - sensor fusion KW - smart videoconferencing KW - Switches KW - Teleconferencing KW - unattended videoconferencing KW - video processing AB - The combination of acoustical and video processing to achieve a smart audio and video feed from a set of N microphones and M cameras is a task that might conventionally be accomplished by camera persons and control room staff. However, in the context of videoconferencing, this process needs to be performed by control software. We discuss the use of a multi-camera multi-microphone set-up for unattended videoconferencing, and present details of a prototype implementation being developed JA - 2000 IEEE International Conference on Multimedia and Expo, 2000. ICME 2000 PB - IEEE VL - 3 SN - 0-7803-6536-4 M3 - 10.1109/ICME.2000.871075 ER - TY - CONF T1 - Benchmarking a network of PCs running parallel applications T2 - Performance, Computing and Communications, 1998. IPCCC '98., IEEE International Y1 - 1998 A1 - Hollingsworth, Jeffrey K A1 - Guven, E. A1 - Akinlar, C. KW - 100 Mbit/s KW - 125 mus KW - Aerodynamics KW - Application software KW - communication micro-benchmarks KW - default mathematical libraries KW - Delay KW - Ethernet KW - Ethernet networks KW - gcc KW - latency KW - lightweight message-passing protocol KW - Linux KW - Local area networks KW - mathematics computing KW - Message passing KW - microcomputer applications KW - Microsoft Windows NT KW - NAS parallel benchmarks KW - network operating systems KW - Numerical simulation KW - parallel applications KW - PARALLEL PROCESSING KW - PC network benchmarking KW - performance comparison KW - performance evaluation KW - Personal communication networks KW - Protocols KW - PVM KW - running time KW - software libraries KW - System software KW - system software configurations KW - TCP/IP KW - TCPIP KW - Transport protocols KW - U-Net active messages KW - Visual C++ AB - Presents a benchmarking study that compares the performance of a network of four PCs connected by a 100 Mbit/s fast Ethernet running three different system software configurations: TCP/IP on Windows NT, TCP/IP on Linux and a lightweight message-passing protocol (U-Net active messages) on Linux. For each configuration, we report results for communication micro-benchmarks and the NAS (Numerical Aerodynamics Simulation) parallel benchmarks. For the NAS benchmarks, the overall running time using Linux TCP/IP was 12-500% less than the Windows NT TCP/IP configuration. Likewise, the Linux U-Net based message-passing protocol outperformed the Linux TCP/IP version by 5-200%+. We also show that, by using Linux U-Net, we are able to achieve 125 μs latency between two processes using PVM. Finally, we report that the default mathematical libraries supplied with NT (for both gcc and Visual C++) are substantially slower than the one supplied with Linux JA - Performance, Computing and Communications, 1998. IPCCC '98., IEEE International PB - IEEE SN - 0-7803-4468-5 M3 - 10.1109/PCCC.1998.659876 ER - TY - JOUR T1 - The SwitchWare active network architecture JF - IEEE Network Y1 - 1998 A1 - Alexander,D. S A1 - Arbaugh, William A. A1 - Hicks, Michael W. A1 - Kakkar,P. A1 - Keromytis,A. D A1 - Moore,J. T A1 - Gunter,C. A A1 - Nettles,S. M A1 - Smith,J. M KW - active extensions KW - active packets KW - Authentication KW - Computer languages KW - Computer networks KW - cryptography KW - cryptography-based authentication KW - high-integrity base KW - integrity checking KW - IP networks KW - LAN interconnection KW - mobile programs KW - network operating systems KW - packet switching KW - programmable network infrastructure KW - programming languages KW - Protocols KW - Safety KW - safety requirements KW - scalability KW - secure active router infrastructure KW - Security KW - security requirements KW - services KW - strong type checking KW - Switches KW - SwitchWare active network architecture KW - telecommunication network routing KW - Tin KW - usability KW - verification techniques AB - Active networks must balance the flexibility of a programmable network infrastructure against the safety and security requirements inherent in sharing that infrastructure. Furthermore, this balance must be achieved while maintaining the usability of the network. The SwitchWare active network architecture is a novel approach to achieving this balance using three layers: active packets, which contain mobile programs that replace traditional packets; active extensions, which provide services on the network elements and can be dynamically loaded; and a secure active router infrastructure, which forms a high-integrity base on which the security of the other layers depends. In addition to integrity checking and cryptography-based authentication, security in our architecture depends heavily on verification techniques from programming languages, such as strong type checking VL - 12 SN - 0890-8044 CP - 3 M3 - 10.1109/65.690959 ER - TY - CONF T1 - Probabilistic verification of a synchronous round-based consensus protocol Y1 - 1997 A1 - Duggal,H.S. A1 - Michel Cukier A1 - Sanders,W. H. KW - business-critical applications KW - consensus protocol correctness KW - crash failures KW - formal verification KW - network environment KW - probabilistic verification KW - probabilities KW - probability KW - program verification KW - proper behavior KW - protocol behavior KW - Protocols KW - realistic environment KW - reliable distributed systems KW - safety-critical applications KW - simple consensus protocol KW - software reliability KW - stochastic assumptions KW - synchronous round based consensus protocol KW - synchronous round based consensus protocols KW - traditional proof techniques AB - Consensus protocols are used in a variety of reliable distributed systems, including both safety-critical and business-critical applications. The correctness of a consensus protocol is usually shown, by making assumptions about the environment in which it executes, and then proving properties about the protocol. But proofs about a protocol's behavior are only as good as the assumptions which were made to obtain them, and violation of these assumptions can lead to unpredicted and serious consequences. We present a new approach for the probabilistic verification of synchronous round based consensus protocols. In doing so, we make stochastic assumptions about the environment in which a protocol operates, and derive probabilities of proper and non proper behavior. We thus can account for the violation of assumptions made in traditional proof techniques. To obtain the desired probabilities, the approach enumerates possible states that can be reached during an execution of the protocol, and computes the probability of achieving the desired properties for a given fault and network environment. We illustrate the use of this approach via the evaluation of a simple consensus protocol operating under a realistic environment which includes performance, omission, and crash failures M3 - 10.1109/RELDIS.1997.632812 ER - TY - CONF T1 - Splitters and near-optimal derandomization T2 - , 36th Annual Symposium on Foundations of Computer Science, 1995. Proceedings Y1 - 1995 A1 - Naor,M. A1 - Schulman,L. J A1 - Srinivasan, Aravind KW - Boosting KW - Circuit testing KW - computational complexity KW - computational linguistics KW - Computer science KW - Contracts KW - derandomization KW - deterministic constructions KW - Educational institutions KW - Engineering profession KW - exhaustive testing KW - fairly general method KW - fixed-subgraph finding algorithms KW - hardness of approximation KW - Information systems KW - k-restrictions KW - learning KW - local-coloring protocol KW - MATHEMATICS KW - near-optimal constructions KW - near-optimal derandomization KW - Parallel algorithms KW - probabilistic bound KW - probability KW - Protocols KW - randomised algorithms KW - Set cover KW - splitters AB - We present a fairly general method for finding deterministic constructions obeying what we call k-restrictions; this yields structures of size not much larger than the probabilistic bound. The structures constructed by our method include (n,k)-universal sets (a collection of binary vectors of length n such that for any subset of size k of the indices, all 2k configurations appear) and families of perfect hash functions. The near-optimal constructions of these objects imply the very efficient derandomization of algorithms in learning, of fixed-subgraph finding algorithms, and of near optimal ΣIIΣ threshold formulae. In addition, they derandomize the reduction showing the hardness of approximation of set cover. They also yield deterministic constructions for a local-coloring protocol, and for exhaustive testing of circuits JA - , 36th Annual Symposium on Foundations of Computer Science, 1995. Proceedings PB - IEEE SN - 0-8186-7183-1 M3 - 10.1109/SFCS.1995.492475 ER - TY - CONF T1 - A theory of testing for real-time T2 - , Proceedings of Sixth Annual IEEE Symposium on Logic in Computer Science, 1991. LICS '91 Y1 - 1991 A1 - Cleaveland, Rance A1 - Zwarico,A. E KW - Algebra KW - Character generation KW - Computer science KW - Delay KW - formal logic KW - Licenses KW - nondeterminism KW - Process control KW - Protocols KW - Real time systems KW - real-time KW - System testing KW - testing preorders KW - testing theory KW - timed testing KW - Timing KW - timing behavior KW - transition systems AB - A framework for generating testing preorders that relate processes on the basis of their timing behavior as well as their degree of relative nondeterminism is developed. The basic concepts of transition systems and testing are reviewed, and timed testing, which takes account of the delay exhibited by a process as it attempts to pass a test, is introduced. The framework is then applied to two different scenarios. In the first, relations are constructed that relate processes on the basis of all timing considerations. In the second, relations are constructed that relate processes on the basis of their relative speeds. In both cases, alternative denotational characterizations of the resulting preorders are presented, and examples are given to illustrate the utility of the approach JA - , Proceedings of Sixth Annual IEEE Symposium on Logic in Computer Science, 1991. LICS '91 PB - IEEE SN - 0-8186-2230-X M3 - 10.1109/LICS.1991.151635 ER - TY - JOUR T1 - Trie hashing with controlled load JF - IEEE Transactions on Software Engineering Y1 - 1991 A1 - Litwin,W. A A1 - Roussopoulos, Nick A1 - Levy,G. A1 - Hong,W. KW - B-tree file KW - Computer science KW - controlled load KW - Databases KW - disk access KW - dynamic files KW - file organisation KW - high load factor KW - information retrieval systems KW - key search KW - load factor KW - Military computing KW - ordered insertions KW - Predictive models KW - primary key access method KW - Protocols KW - random insertions KW - TH file KW - THCL KW - Tree data structures KW - trees (mathematics) KW - trie hashing AB - Trie hashing (TH), a primary key access method for storing and accessing records of dynamic files, is discussed. The key address is computed through a trie. A key search usually requires only one disk access when the trie is in core and two disk accesses for very large files when the trie must be on disk. A refinement to trie hashing, trie hashing with controlled load (THCL), is presented. It is designed to control the load factor of a TH file as tightly as that of a B-tree file, allows high load factor of up to 100% for ordered insertions, and increases the load factor for random insertions from 70% to over 85%. It is shown that these properties make trie hashing preferable to a B-tree VL - 17 SN - 0098-5589 CP - 7 M3 - 10.1109/32.83904 ER - TY - JOUR T1 - Multiparty Grammars and Related Features for Defining Interactive Systems JF - IEEE Transactions on Systems, Man and Cybernetics Y1 - 1982 A1 - Shneiderman, Ben KW - Application software KW - Computer aided instruction KW - Computer displays KW - Computer languages KW - Computer networks KW - Debugging KW - HUMANS KW - interactive systems KW - Protocols KW - Writing AB - Multiparty grammars are introduced which contain labeled nonterminals to indicate the party that produces the terminal string. For interactive person-computer systems, both the user commands and system responses can be described by the linked BNF grammars. Multiparty grammars may also be used to describe communication among several people (by way of computers or in normal dialogue), network protocols among several machines, or complex interactions involving several people and machines. Visual features such as underlining, reversal, blinking, and color, window declarations, and dynamic operations dependent on cursor movement are also covered. VL - 12 SN - 0018-9472 CP - 2 M3 - 10.1109/TSMC.1982.4308798 ER -