Automated network management and configuration using Probabilistic Trans-Algorithmic Search

Online configuration of large-scale systems such as networks requires parameter optimization within a limited amount of time, especially when configuration is needed as a response to recover from a failure in the system. To quickly configure such systems in an online manner, we propose a Probabilistic Trans-Algorithmic Search (PTAS) framework which leverages multiple optimization search algorithms in an iterative manner. PTAS applies a search algorithm to determine how to best distribute available experiment budget among multiple optimization search algorithms. It allocates an experiment budget to each available search algorithm and observes its performance on the system-at-hand. PTAS then probabilistically reallocates the experiment budget for the next round proportional to each algorithm’s performance relative to the rest of the algorithms. This “roulette wheel” approach probabilistically favors the more successful algorithm in the next round. Following each round, the PTAS framework “transfers” the best result(s) among the individual algorithms, making our framework a trans-algorithmic one. PTAS thus aims to systematize how to “search for the best search” and hybridize a set of search algorithms to attain a better search. We use three individual search algorithms, i.e., Recursive Random Search (RRS) (Ye and Kalyanaraman, 2004), Simulated Annealing (SA) (Laarhoven and Aarts, 1987), and Genetic Algorithm (GA) (Goldberg, 1989), and compare PTAS against the performance of RRS, GA, and SA. We show the performance of PTAS on well-known benchmark objective functions including scenarios where the objective function changes in the middle of the optimization process. To illustrate applicability of our framework to automated network management, we apply PTAS on the problem of optimizing link weights of an intra-domain routing protocol on three different topologies obtained from the Rocketfuel dataset. We also apply PTAS on the problem of optimizing aggregate throughput of a wireless ad hoc network by tuning datarates of traffic sources. Our experiments show that PTAS successfully picks the best performing algorithm, RRS or GA, and allocates the time wisely. Further, our results show that PTAS’ performance is not transient and steadily improves as more time is available for search.     

Overlapping Schwarz and Spectral Element Methods for Linear Elasticity and Elastic Waves

The classical overlapping Schwarz algorithm is here extended to the spectral element discretization of linear elastic problems, for both homogeneous and heterogeneous compressible materials. The algorithm solves iteratively the resulting preconditioned system of linear equations by the conjugate gradient or GMRES methods. The overlapping Schwarz preconditioned technique is then applied to the numerical approximation of elastic waves with spectral elements methods in space and implicit Newmark time advancing schemes. The results of several numerical experiments, for both elastostatic and elastodynamic problems, show that the convergence rate of the proposed preconditioning algorithm is independent of the number of spectral elements (scalability), is independent of the spectral degree in case of generous overlap, otherwise it depends inversely on the overlap size. Some results on the convergence properties of the spectral element approximation combined with Newmark schemes for elastic waves are also presented.     

在协议集成测试系统上开展路由协议测试

在分析路由协议的特性及其测试需求的基础上，提出利用窗口黑盒来描述被测协议，利用多通道测试方法扩展对被测实现的控制和观察，通过扩充参考实现增强系统的测试能力。将这些理论，技术应用于系统中，对路由协议开展了有效的测试活动，为国产高性能路由器的开发提供了有力的支持，也进一步增强了PITS系统的功能和适用性。     

New two‐dimensional slope limiters for discontinuous Galerkin methods on arbitrary meshes

In this paper, we introduce an extension of Van Leer's slope limiter for two‐dimensional discontinuous Galerkin (DG) methods on arbitrary unstructured quadrangular or triangular grids. The aim is to construct a non‐oscillatory shock capturing DG method for the approximation of hyperbolic conservative laws without adding excessive numerical dispersion. Unlike some splitting techniques that are limited to linear approximations on rectangular grids, in this work, the solution is approximated by means of piecewise quadratic functions. The main idea of this new reconstructing and limiting technique follows a well‐known approach where local maximum principle regions are defined by enforcing some constraints on the reconstruction of the solution. Numerical comparisons with some existing slope limiters on structured as well as on unstructured meshes show a superior accuracy of our proposed slope limiters. Copyright © 2004 John Wiley & Sons, Ltd.     

A family of lower- and higher-order transversal linearization techniques in non-linear stochastic engineering dynamics

Sample pathwise numerical integration of noise-driven engineering dynamical systems cannot generally be performed beyond a limited level of accuracy, especially when the noise processes are modelled using (filtered) white noises. Recently, a locally transversal linearization (LTL) strategy has been proposed by the author (Proc Roy Soc London A 2001; 457 :539–566) for direct integration of deterministic and stochastic non-linear dynamical systems. The present effort is focussed on a host of extensions along with detailed theoretical error analyses of the linearization approach, especially as applied to problems in non-linear stochastic engineering dynamics. Thus, to begin with, estimates of local and global error orders in the basic LTL scheme are obtained separately for the displacement and velocity vectors when the system is driven either by a set of additive noises or by an arbitrary combination of (independently evolving) additive and multiplicative noises. Following this, a new family of higher-order LTL schemes is proposed in order to improve upon the basic LTL method and the associated error orders are established. A stepwise implementation of the lower- and higher-order versions of the LTL method, along with certain computational aspects, is also outlined. The proposed schemes are numerically illustrated, to a limited extent, for a single degree-of-freedom (SDOF) and a two degree-of-freedom (TDOF) non-linear engineering systems under additive and/or multiplicative white noise excitations. Copyright © 2004 John Wiley & Sons, Ltd.     

Implicit–Explicit Schemes for BGK Kinetic Equations

In this work a new class of numerical methods for the BGK model of kinetic equations is presented. In principle, schemes of any order of accuracy in both space and time can be constructed with this technique. The methods proposed are based on an explicit–implicit time discretization. In particular the convective terms are treated explicitly, while the source terms are implicit. In this fashion even problems with infinite stiffness can be integrated with relatively large time steps. The conservation properties of the schemes are investigated. Numerical results are shown for schemes of order 1, 2 and 5 in space, and up to third-order accurate in time.     

Coordinating production and distribution of jobs with bundling operations

We consider an integrated scheduling and distribution model in which jobs completed by two different machines must be bundled together for delivery. The objective is to minimize the sum of the delivery cost and customers' waiting costs. Such a model not only attempts to coordinate the job schedules on both machines, but also aims to coordinate the machine schedules with the delivery plan. Polynomial-time heuristics and approximation schemes are developed for the model with only direct shipments as well as the general model with milk-run deliveries.     

中国的三种非同步轨道卫星移动通信系统星座方案

本文介绍基于我国的三种非同步轨道卫星移动通信系统星座方案：低、中轨系统各有２４和１８颗星，轨道高度分别为１３２６和８０３５ｋｍ，两系统各以５°和３０°的仰角对我国的覆盖率为９９．７８％和９９．９６％；椭圆轨道系统１２颗星，近、远地点分别为４２７和２９０６ｋｍ，以７°和１５°仰角对我国北纬２０°以上地区覆盖率分别为９７．９０％和８９．６１％，若增加４颗中轨卫星，以１５°仰角对我国的覆盖率为９９．９９％。     

Lower bounds on the information rate of secret sharing schemes with homogeneous access structure

We present some new lower bounds on the optimal information rate and on the optimal average information rate of secret sharing schemes with homogeneous access structure. These bounds are found by using some covering constructions and a new parameter, the k-degree of a participant, that is introduced in this paper. Our bounds improve the previous ones in almost all cases.     

Experience with Applying Formal Methods to Protocol Specification and System Architecture

In the last three years or so we at Enterprise Platforms Group at Intel Corporation have been applying formal methods to various problems that arose during the process of defining platform architectures for Intel's processor families. In this paper we give an overview of some of the problems we have worked on, the results we have obtained, and the lessons we have learned. The last topic is addressed mainly from the perspective of platform architects.