Importance sampling for the estimation of buffer overflow probabilities via trace-driven simulations

We develop an importance sampling technique that can be used to speed up the simulation of a model of a buffered communication multiplexer fed by a large number of independent sources. The sources generate traffic according to a periodic function with a random phase. This traffic model accommodates a wide range of situations of practical interest, including ON-OFF periodic traffic models and sequences of bit rates generated by actual variable bit rate sources, such as MPEG video compressors. The simulation seeks to obtain estimates for the buffer overflow probability that in most cases of interest is very small. We use a large deviations result to devise the change of measure used in the importance sampling technique and demonstrate through numerical results that this change of measure leads to a dramatic reduction in the required simulation time over direct Monte Carlo simulation. Possible practical applications include short-term network resource planning and even real-time call admission control.     

SDU: A Semidefinite Programming-Based Underestimation Method for Stochastic Global Optimization in Protein Docking

This paper introduces a new stochastic global optimization method targeting protein-protein docking problems, an important class of problems in computational structural biology. The method is based on finding general convex quadratic underestimators to the binding energy function that is funnel-like. Finding the optimum underestimator requires solving a semidefinite programming problem, hence the name semidefinite programming-based underestimation (SDU). The underestimator is used to bias sampling in the search region. It is established that under appropriate conditions SDU locates the global energy minimum with probability approaching one as the sample size grows. A detailed comparison of SDU with a related method of convex global underestimator (CGU), and computational results for protein-protein docking problems are provided     

Congestion-dependent pricing of network services

We consider a service provider (SP) who provides access to a communication network or some other form of on-line services. Users initiate calls that belong to a set of diverse service classes, differing in resource requirements, demand pattern, and call duration. The SP charges a fee per call, which can depend on the current congestion level, and which affects users' demand for calls. We provide a dynamic programming formulation of the problems of revenue and welfare maximization, and derive some qualitative properties of the optimal solution. We also provide a number of approximate approaches, together with an analysis that indicates that near-optimality is obtained for the case of many, relatively small, users. In particular, we show analytically as well as computationally, that the performance of an optimal pricing strategy is closely matched by a suitably chosen static price, which does not depend on instantaneous congestion. This indicates that the easily implementable time-of-day pricing will often suffice. Throughout, we compare the alternative formulations involving revenue or welfare maximization, respectively, and draw some qualitative conclusions     

Pricing in multiservice loss networks: static pricing, asymptoticoptimality and demand substitution effects

We consider a communication network with fixed routing that can accommodate multiple service classes, differing in bandwidth requirements, demand pattern, call duration and routing. The network charges a fee per call which can depend on the current congestion level and which affects user's demand. Building on the single-node results of I.Ch. Paschalidis and J.N. Tsitsiklis (see IEEE/ACM Trans. Networking, vol.8, p.171-84, 2000), we consider both problems of revenue and of welfare maximization, and show that static pricing is asymptotically optimal in a regime of many, relatively small, users. In particular, the performance of an optimal (dynamic) pricing strategy is closely matched by a suitably chosen class-dependent static price, which does not depend on instantaneous congestion. This result holds even when we incorporate demand substitution effects into the demand model. More specifically, we model the situation where price increases for a class of service might lead users to use another class as an imperfect substitute. For both revenue and welfare maximization objectives we characterize the structure of the asymptotically optimal static prices, expressing them as a function of a parsimonious number of parameters. We employ a simulation-based approach to tune those parameters and to compute efficiently an effective policy away from the limiting regime. Our approach can handle large, realistic, instances of the problem     

A 10-Bit,Low Power,Successive Approximation,Digitally Auto-Zeroed CMOS ADC Core for the NASA TRIO Smart Sensor System on a Chip

In spacecraft applications there is a great need for robust analogue to digital converters (ADC) that can withstand the harsh space environment. Commercially available ADCs cannot operate in the space environment due to radiation effects. In this paper we present an ADC that has been developed for the NASA TRIO smart sensor system on a chip (SoC), a versatile low power device specifically designed for spacecraft data acquisition and telemetry of several types of sensors such as temperature, voltage/current transducers, radFETs, etc. It is required for the ADC to operate in excess of 300 Krad total ionizing dose and to be robust to single event upsets. The successive approximation topology was chosen and it was enhanced with a special auto-zeroing technique to compensate for possible lifetime offset errors. Due to the comparator design, a rail-to-rail input capability is achieved, a feature very useful in some type of Vdd ratio metric sensors. It has 10-bit resolution for a reference in the range 0.1 to Vdd + 1 V, and for power supply in the range 2.5 to 5.5 V; the positive reference terminal V_ref+ is settable up to Vdd + 0.5 V and the negative voltage terminal is settable down to GND-0.5 V. The power dissipation is less than 2 mW at 50 Ksamlles/sec. The TRIO chip is used in several NASA spacecraft including CONTOUR, STEREO, MESSENGER, EUROPA, PLUTO, etc.George Kottaras was born in Athens, Greece in 1974. He received the Diploma degree (five years with thesis) in Electrical Engineering from Democritos University of Thrace, Greece in 1996. He is currently pursuing the Ph.D. degree on Scientific Space Instruments and spacecraft avionics at Space Research Laboratory, DUTh. He has specialized in VLSI technologies at JHU/APL for about five years.His research interests include mixed signal analog/digital design, ADCs, design for testability, testing, smart sensors and data acquisition.Nikolaos P. Paschalidis was born is Serres, Greece in 1963. He received the Diploma and Ph.D. degrees in Electrical Engineering from the Democritus University of Thrace (DUTh), Greece, in 1985 and 1992 respectively. He has been in appointment with the Johns Hopkins University, since 1989, where his research specialized in advanced microelectronics, space instrumentation, and space physics.He later joined the Space Department of JHU Applied Physics Laboratory (JHU/APL) Laurel, MD, as a postdoctoral fellow and presently he is Principal Staff. His research interests are in analog and mixed signal microelectronics, microsensors, microsystems and their applications in in-situ and remote sensing spacecraft instruments and avionics. He pioneered in the Advanced Technology Development program of NASA for smaller better faster missions by leading efforts in the circuit level of: amplifiers, comparators, voltage references, ADC and DAC, PLLs, TDCs, SEU and radiation tolerant design, physical design, design for testability, testing and space qualification; in the system on a chip level flight ready chips including: the Time of Flight chip for precise time pickoff and time digitization, Energy chip for radiation energy measurement, the TRIO smart sensor chip for spacecraft data acquisition and control etc; in the instrument and spacecraft level: application of these technologies in particle and plasma spectrometers, laser altimeters, photon/particle imagers, TOF mass spectrometers, X-ray and gamma-ray instruments, spacecraft avionics. Space missions using these technologies include: Cassini, Image, Contour, Messenger, Pluto, Mars missions, etc. Dr. Paschalidis published extensively in microelectronics, space instrumentation, and space physics. He supervises research of graduate students in ECE and Applied Physics. He supervised DUTh graduate students at JHU/APL for many years. He participates as principal investigator and co-investigator in several space programs; he participates in communities with space related activities including: the IEEE Aerospace, Nuclear Sciences, NASA VLSI, IAA, and American Geophysical Union.Emmanuel T. Sarris was bom in Athens, Greece, in 1945. He received the physics degree from the University of Athens in 1967 and the Ph.D. degree in space physics from the University of Iowa, Iowa City, in 1973.He was a Postdoctoral Fellow in the Applied Physics Laboratory, The Johns Hopkins University, Baltimore, MD, from 1974 to 1976. From 1976 to 1977, he was a Research Scientist at the Max-Planck-Institut. He has been a Professor of Electrodynamics, Department of Electrical Engineering, University of Thrace, Greece, and Director of the Laboratory of Electrodynamics and Space Research since 1977. He was the Director of the Institute of Ionospheric and Space Physics, National Observatory of Athens from 1990 to 1996. His research interests include space plasma electrodynamics, design, construction, and testing of space instrumentation, satellite communications, satellite remote sensing. He is coinvestigator in the international space missions: Ulysses, Geotail, Interball, Cluster. He is the author of 270 refereed publications and 300 presentations at international meetings. Dr. Sarris is a member of the COSPAR Council. He was elected Johns Hopkins Scholar Award in 1992 and received the Award for Academic Excellence in 1994.Nikos Stamatopoulos was born in Peloponnisos, Greece in 1969. He received the diploma degree (five years with thesis) of Electrical Engineering from Democritos University of Thrace, Greece in 1994. He is currently pursuing the Ph.D. degree on Scientific Space Instruments at Space Research Laboratory, DUTh. He has specialized in VLSI technologies with emphasis in low noise analog design at JHU/APL for about five years.His main research interests are on Analogue CMOS VLSI design for fast time acquisition.Kostas Karadamoglou was born in Macedonia, Greece, in 1970. He received the diploma degree (five years with thesis) of Electrical Engineering from Democritos University of Thrace, Greece in 1994. He is currently pursuing the Ph.D. degree on Scientific Space Instruments at Space Research Laboratory, DUTh. He has specialized in VLSI technologies with emphasis in high-speed digital design at JHU/APL for about five years.His main research interests are on the design of application specific Time to Digital Converters.Vassilis Paschalidis was born in Serres, Greece in 1964. He received the B.S. degree in Electrical Engineering from the Technological Institute of Kabala, Greece in 1988. He worked n the industry for electronic automation. He has specialized in VLSI technologies at JHU/APL for about five years with emphasis in physical design. His research interests include mixed signal analog/digital VLSI design.     

A Smart Sensor Integrated Circuit for NASA's New Millennium Spacecraft

The modern space era can greatly benefit from the rapidly growingmicroelectronics technologies in order to enable the ambitious exploratoryand commercial space endeavors of the new millennium. A smart sensor, analog/digital, integrated circuit, suitable for spacecraft avionics dataacquisition and control is presented. The Remote Input/Output (RIO) device isdeveloped by The Johns Hopkins University/Applied Physics Laboratory, for NASA's Jet Propulsion Laboratory, to support many oncoming new millenniumspace missions. TRIO—the first version of RIO—is designed to interface totemperature, pressure, total radiation dose sensors, and generally to voltage/current transducers. The microchip includes front-end conditioningcircuitry, an ADC, memory, serial and CPU interface, and a digital port.Furthermore the device is developed to meet extreme space qualification specifications such as radiation effects. This versatile system-on-a-chipdevice is becoming a key enabling technology for new-generation NASA andCommercial spacecraft systems. Missions that are intended to use the TRIOdevice are the: Europa Orbiter, Deep Space 4, Solar Probe, Pluto Express,Mars Sample Return, Stereo, Contour, etc.     

Class-specific quality of service guarantees in multimedia communication networks

We consider the problem of quality-of-service (QoS) provisioning in modern high-speed, multimedia, communication networks. We quantify QoS by the probabilities of loss and excessive delay of an arbitrary packet, and introduce the model of a multiclass node (switch) which provides network access to users that may belong to multiple service classes. We treat such a node as a stochastic system which we analyze and control. In particular, we develop an analytical approach to estimate both the delay and the buffer overflow probability per service class, based on ideas from large deviations and optimal control. We exploit these performance analysis results by devising a call admission control algorithm which can provide per class QoS guarantees. We compare the proposed approach to alternative worst-case and effective bandwidth-based schemes and argue that it leads to increased efficiency. Finally, we discuss extensions to the network case in order to provide end-to-end QoS guarantees.     

Asymptotically Optimal Transmission Policies for Large-Scale Low-Power Wireless Sensor Networks

We consider wireless sensor networks with multiple gateways and multiple classes of traffic carrying data generated by different sensory inputs. The objective is to devise joint routing, power control and transmission scheduling policies in order to gather data in the most efficient manner while respecting the needs of different sensing tasks (fairness). We formulate the problem as maximizing the utility of transmissions subject to explicit fairness constraints and propose an efficient decomposition algorithm drawing upon large-scale decomposition ideas in mathematical programming. We show that our algorithm terminates in a finite number of iterations and produces a policy that is asymptotically optimal at low transmission power levels. Furthermore, we establish that the utility maximization problem we consider can, in principle, be solved in polynomial time. Numerical results show that our policy is near-optimal, even at high power levels, and far superior to the best known heuristics at low power levels. We also demonstrate how to adapt our algorithm to accommodate energy constraints and node failures. The approach we introduce can efficiently determine near-optimal transmission policies for dramatically larger problem instances than an alternative enumeration approach     

Spatio-Temporal Network Anomaly Detection by Assessing Deviations of Empirical Measures

We introduce an Internet traffic anomaly detection mechanism based on large deviations results for empirical measures. Using past traffic traces we characterize network traffic during various time-of-day intervals, assuming that it is anomaly-free. We present two different approaches to characterize traffic: (i) a model-free approach based on the method of types and Sanov's theorem, and (ii) a model-based approach modeling traffic using a Markov modulated process. Using these characterizations as a reference we continuously monitor traffic and employ large deviations and decision theory results to ldquocomparerdquo the empirical measure of the monitored traffic with the corresponding reference characterization, thus, identifying traffic anomalies in real-time. Our experimental results show that applying our methodology (even short-lived) anomalies are identified within a small number of observations. Throughout, we compare the two approaches presenting their advantages and disadvantages to identify and classify temporal network anomalies. We also demonstrate how our framework can be used to monitor traffic from multiple network elements in order to identify both spatial and temporal anomalies. We validate our techniques by analyzing real traffic traces with time-stamped anomalies.