Optimizing content-based routers: posets and forests

Event-based systems are seen as good candidates for supporting distributed applications in dynamic and ubiquitous environments because they support decoupled and asynchronous one-to-many and many-to-many information dissemination. Event systems are widely used because asynchronous messaging provides a flexible alternative to RPC. They are typically implemented using an overlay network of routers. A content-based router forwards event messages based on filters that are installed by subscribers and other routers. This paper addresses the optimization of content-based routing tables organized using the covering relation and presents novel configurations for improving local and distributed operation. We present the poset-derived forest data structure and variants that perform considerably better under frequent filter additions and removals than existing data structures. The results offer a significant performance increase to currently known covering-based routing mechanisms. Sasu Tarkoma received his M.Sc. and Ph.Lic degrees in Computer Science from the University of Helsinki, Department of Computer Science. He has over 20 scientific publications and has also contributed to several books on mobile middleware. His research interests include distributed computing and middleware. Jaakko Kangasharju is a PhD student at the University of Helsinki and working as a researcher at the Helsinki Institute for Information Technology. His research is concentrated on XML messaging and processing in the mobile wireless environment. He has participated in related standardization efforts at the Object Management Group and the World Wide Web Consortium.     

基于树结构的分布式BGP路由计算迭代算法

随着互联网规模的迅速增长,下一代核心路由器的研究重点正在向可扩展体系结构的方向发展.分布式路由协议计算是可扩展路由器需要解决的关键问题之一.作为已经在骨干网上广泛部署的重要路由协议,BGP协议的分布式模型及其相关算法的研究是可扩展路由器体系结构中的重要研究课题.本文基于BGP路由计算模型,对“路径选优”这一BGP基本操作的特性进行了深入分析,提出了一种按照树状结构来组织路由计算过程的模型,基于此模型可以分布式计算BGP路由.针对两类典型的可扩展路由器体系结构,本文分别提出了相应的迭代树算法,对算法给出了性能改进的理论分析.通过模拟实验,验证了本文所述模型的实际性能.     

Optimal distributed Kalman filtering fusion for a linear dynamic system with cross-correlated noises

In this article, we study the distributed Kalman filtering fusion problem for a linear dynamic system with multiple sensors and cross-correlated noises. For the assumed linear dynamic system, based on the newly constructed measurements whose measurement noises are uncorrelated, we derive a distributed Kalman filtering fusion algorithm without feedback, and prove that it is an optimal distributed Kalman filtering fusion algorithm. Then, for the same linear dynamic system, also based on the newly constructed measurements, a distributed Kalman filtering fusion algorithm with feedback is proposed. A rigorous performance analysis is dedicated to the distributed fusion algorithm with feedback, which shows that the distributed fusion algorithm with feedback is also an optimal distributed Kalman filtering fusion algorithm; the P matrices are still the estimate error covariance matrices for local filters; the feedback does reduce the estimate error covariance of each local filter. Simulation results are provided to demonstrate the validity of the newly proposed fusion algorithms and the performance analysis.     

Architecture of a Web server accelerator

We describe the design, implementation and performance of a high-performance Web server accelerator which runs on an embedded operating system and improves Web server performance by caching data. It can serve Web data at rates an order of magnitude higher than that which would be achieved by a high-performance Web server running on similar hardware under a conventional operating system such as Unix or NT. The superior performance of our system results in part from its highly optimized communications stack. In order to maximize hit rates and maintain updated caches, our accelerator provides an API which allows application programs to explicitly add, delete, and update cached data. The API allows our accelerator to cache dynamic as well as static data. We describe how our accelerator can be scaled to multiple processors to increase performance and availability. The basic design alternatives include a content router or a TCP router (without content routing) in front of a set of Web cache accelerator nodes, with the cache memory distributed across the accelerator nodes. Content-based routing reduces cache node CPU cycles but can make the front-end router a bottleneck. With the TCP router, a request for a cached object may initially be sent to the wrong cache node; this results in larger cache node CPU cycles, but can provide a higher aggregate throughput, because the TCP router becomes a bottleneck at a higher throughput than the content router. We quantify the throughput ranges in which different designs are preferable. We also examine a combination of content-based and TCP routing techniques. In addition, we present statistics from critical deployments of our accelerator for improving performance at highly accessed Sporting and Event Web sites hosted by IBM.     

一种新的路由优化计算方法

随着网络规模的扩大,路由算法的优劣对改善整个网络的可扩展性起到至关重要的作用。传统中分级路由算法既保持源路由算法的优点,又有分布式路由算法的优越性,但因路由计算由许多节点承担必然带来路由质量的代价,如聚合信息不精确会严重影响路由的质量甚至影响网络的连通性。为了适当地减少路由计算的频度并快速提高计算效率,本文基于传统的路由算法提出了一种新的并行路由优化计算方法。     

Fuzzy-based Adaptive Routing Algorithm for Networks-on-Chip

In this paper, we propose two adaptive routing algorithms to alleviate congestion in the network. In the first algorithm, the routing decision is assisted by the number of occupied buffer slots at the corresponding input buffer of the next router and the congestion level of that router. Although this algorithm performs better than the conventional method, DyXY, in some cases the proposed algorithm leads to non-optimal decisions. Fuzzy controllers compensate for ambiguities in the data by giving a level of confidence rather than declaring the data simply true or false. To make a better routing decision, we propose an adaptive routing algorithm based on fuzzy logic for Networks-on-chip where the routing path is determined based on the current condition of the network. The proposed algorithm avoids congestion by distributing traffic over the routers that are less congested or have a spare capacity. The output of the fuzzy controller is the congestion level, so that at each router, the neighboring router with the lowest congestion value is chosen for routing a packet. To evaluate the proposed routing method, we use two multimedia applications and two synthetic traffic profiles. The experimental results show that the fuzzy-based routing scheme improves the performance over the DyXY routing algorithm by up to 25% with a negligible hardware overhead.     

State estimation of nonlinear dynamic systems using weighted variance-based adaptive particle swarm optimization

New heuristic filters are proposed for state estimation of nonlinear dynamic systems based on particle swarm optimization (PSO) and differential evolution (DE). The methodology converts state estimation problem into dynamic optimization to find the best estimate recursively. In the proposed strategy the particle number is adaptively set based on the weighted variance of the particles. To have a filter with minimal parameter settings, PSO with exponential distribution (PSO-E) is selected in conjunction with jDE to self-adapt the other control parameters. The performance of the proposed adaptive evolutionary algorithms i.e. adaptive PSO-E, adaptive DE and adaptive jDE is studied through a comparative study on a suite of well-known uni- and multi-modal benchmark functions. The results indicate an improved performance of the adaptive algorithms relative to original simple versions. Further, the performance of the proposed heuristic filters generally called adaptive particle swarm filters (APSF) or adaptive differential evolution filters (ADEF) are evaluated using different linear (nonlinear)/Gaussian (non-Gaussian) test systems. Comparison of the results to those of the extended Kalman filter, unscented Kalman filter, and particle filter indicate that the adopted strategy fulfills the essential requirements of accuracy for nonlinear state estimation.     

内容发布订阅系统路由算法和自配置策略研究

路由算法和动态自配置特性是实现大规模基于内容的发布订阅系统的两个关键问题.尽管已经有多种路由算法被提了出来,但是它们没有充分利用组播技术提高系统性能和节省网络带宽;此外,已有系统的网络都是静态的,不能够进行网络的自动配置.首先,提出了具有组播集群的层次性系统模型,设计了混合式路由算法,充分利用物理网络组播的特性,节省网络带宽.然后,提出了组播集群复制协议和基于内容的组播树协议CMTP,分别处理节点或者链路失效导致的网络分割以及路由的重建.实验结果表明,这些算法和协议的引入节省了网络带宽,显著提高了系统的性能,保证了系统的自配置特性.     

An algorithm for interest management in High Level Architecture

One of the most important design concerns when implementing large-scale high-level architecture (HLA) simulations is how to perform effective interest management. HLA interest management separates routing from data delivery so as to filter out unnecessary data communication between federated computers. One of the more scalable mechanisms for such interest management, data distributed management (DDM), distributes and filters data based on regional clustering. Essential to DDM, therefore, are the algorithms for dividing routing space and for matching regions. In this article, we describe how the spatial hierarchy of routing space is defined, and introduce a technique based on n-dimensional binary trees to solve the problem of region matching. We then introduce two algorithms: one to compute the coding of hierarchically structured regions, and the other to match regions based on this coding. Finally, we outline our general strategy for data filtering in HLA, and analyze the advantageous and limitations of the algorithm through experiments.     

支持时延-带宽约束的动态层次组播路由

层次网络及层次路由成为解决大规模网络QoS路由可扩展性问题的一个主要手段.文中对PNNI层次网络模型下的时延-带宽多QoS约束的动态组播路由问题进行了全面研究:在已提出支持时延-带宽约束的拓扑聚集算法(Stair)的基础上,进一步对组播树节点需维护的组播树状态信息及其聚集问题进行研究,并提出"伪树上边界节点"模式的域内组播树状态信息的聚集方法,最后设计了基于聚集拓扑信息和组播树状态信息的动态层次组播路由算法.仿真结果显示,该路由不仅大量压缩了存储和扩散的拓扑信息和组播树状态信息,同时还保持了与平面网络近似的路由效率,实现了大规模网络情况下组播路由的扩展.     

Compressionless wormhole routing: an analysis for hypercube with virtual channels

Several recent studies have shown that adaptive routing algorithms based on deadlock recovery have superior performance characteristics than those based on deadlock avoidance. Most of these studies, however, have relied on software simulation due to the lack of analytical modelling tools. In an effort towards filling this gap, this paper presents a new analytical model of compressionless routing in wormhole-routed hypercubes. This routing algorithm exploits the tight coupling between wormhole routers for flow control to detect and recover from potential deadlock situations. The advantages of compressionless routing include deadlock-free adaptive routing with no extra virtual channels, simple router design, and order-preserving message transmission. The proposed analytical model computes message latency by determining the message transmission time, blocking delay at each router, multiplexing delay at each network channel, and waiting time in the source before entering the network. The validity of the model is demonstrated by comparing analytical results with those obtained through simulation experiments.     

基于端用户可控的IP网络路由体系结构和算法

IP网络的路由体系结构及算法是网络有效运行的关键技术.现行的路由体系结构及算法在实际应用中存在着一些问题.针对该问题,提出一种端用户可控的IP网络路由体系结构和具体的路由算法.在提出的端用户可控的路由体系中,利用用户级别的自组织路由方法来简化路由器的负荷,增强端用户的智能性.模拟仿真实验表明,该路由体系的使用,将使路由器的任务简化为通报网络信息和协调用户决断这两个较为简单的功能,且路由选择的决断考虑到端用户的实际需求.该体系结构可以更好地适应网络规模和应用需求的不断扩大,形成一个分布式、扩展性较好的路由体系和有效的路由算法.     

On the cost and safety of handoffs in content-based routing systems

Content-based routing of information and publish/subscribe have been proposed as a communication paradigm for advanced and mobile applications. In content-based routing, messages are forwarded based on queries on their content that clients and routers establish beforehand. In this paper, we examine the cost and safety of handoff protocols for subscribers and publishers in content-based routing networks. We examine two useful properties for mobility-aware content-based routing systems, namely completeness and mobility-safety. Then we determine the upper and lower bound handoff costs for three interesting topologies, a number of optimizations, and show that if completeness cannot be assumed the signalling cost is considerably higher and flooding needs to be used. We present simulation results for subscriber mobility and mobility-safety proofs for the investigated protocols. Both theoretical and experimental results show that rendezvous points may be used to significantly reduce the signalling cost of handoffs.     

An algorithmic approach to adaptive state filtering using recurrentneural networks

Practical algorithms are presented for adaptive state filtering in nonlinear dynamic systems when the state equations are unknown. The state equations are constructively approximated using neural networks. The algorithms presented are based on the two-step prediction-update approach of the Kalman filter. The proposed algorithms make minimal assumptions regarding the underlying nonlinear dynamics and their noise statistics. Non-adaptive and adaptive state filtering algorithms are presented with both off-line and online learning stages. The algorithms are implemented using feedforward and recurrent neural network and comparisons are presented. Furthermore, extended Kalman filters (EKFs) are developed and compared to the filter algorithms proposed. For one of the case studies, the EKF converges but results in higher state estimation errors that the equivalent neural filters. For another, more complex case study with unknown system dynamics and noise statistics, the developed EKFs do not converge. The off-line trained neural state filters converge quite rapidly and exhibit acceptable performance. Online training further enhances the estimation accuracy of the developed adaptive filters, effectively decoupling the eventual filter accuracy from the accuracy of the process model.     

Experimental validation of resilient tree-based greedy geometric routing

Geometric routing is an alternative for IP routing based on longest prefix matching. Using this routing paradigm, every node in the network is assigned a coordinate and packets are forwarded towards their intended destination following a distance-decreasing policy (greedy forwarding). This approach makes the routers significantly more memory-efficient compared to the current IP routers. In this routing, greedy embeddings are used to guarantee a 100% successful delivery to every destination in the network. Most of the existing proposals lack resiliency mechanisms to react efficiently to network changes. We propose a distributed algorithm to calculate a greedy embedding based on a spanning tree of the network. In this algorithm, nodes are triggered to re-calculate their coordinates upon a change in the topology such as link or node failures. The advantage of this approach is that it recovers from topology failures within a very short period of time. We further extend the algorithm to generate backups to apply protection in distributed setups. Different trade-offs and trends of re-convergence for geometric routing have been evaluated in an emulation environment. Realistic results are achieved through emulation as no model or abstraction is involved. The proposed routing scheme is implemented in Quagga routing software and new elements are developed in Click modular router to enable greedy forwarding. For the first time, the performance of this scheme is evaluated through emulation on a large topology of 1000 nodes and the results are compared with BGP. The experimental results indicate that the proposed scheme has interesting characteristics in terms of convergence time upon a change in the network topology.     

一种基于内容的双向共享组播路由协议

针对组播协议在大规模分布式交互系统应用中面临的可扩展性问题,提出一种基于内容的双向共享组播路由协议CBSMRP(content-based bi-directional shared multicast routing protocol).该协议结合运用了主动路由思想和基于内容的发布-订购模式,在基于CBT(core-based tree)结构的双向共享组播树中,根据数据包的内容实现主动路由和双向过滤,不仅解决了组播地址的维护和分配等问题,而且能够有效地减轻系统的网络负载.仿真实验及实际应用表明,该协议具有较好的扩展性,能够满足大规模分布式交互系统的网络通信要求.     

内容发布订阅服务网络中的路由策略

发布/订阅系统为分布式网络中系统间的异步通讯提供了便捷的途径,事件的路由策略是基于内容发布/订阅系统的关键问题之一。文章提出了应用于内容发布/订阅服务网络中的改良后的层次形拓扑结构及先合后分的路由策略,提高了基于内容发布/订阅系统的可扩展性和传输效率。     

The Dynamic Bloom Filters

A Bloom filter is an effective, space-efficient data structure for concisely representing a set, and supporting approximate membership queries. Traditionally, the Bloom filter and its variants just focus on how to represent a static set and decrease the false positive probability to a sufficiently low level. By investigating mainstream applications based on the Bloom filter, we reveal that dynamic data sets are more common and important than static sets. However, existing variants of the Bloom filter cannot support dynamic data sets well. To address this issue, we propose dynamic Bloom filters to represent dynamic sets, as well as static sets and design necessary item insertion, membership query, item deletion, and filter union algorithms. The dynamic Bloom filter can control the false positive probability at a low level by expanding its capacity as the set cardinality increases. Through comprehensive mathematical analysis, we show that the dynamic Bloom filter uses less expected memory than the Bloom filter when representing dynamic sets with an upper bound on set cardinality, and also that the dynamic Bloom filter is more stable than the Bloom filter due to infrequent reconstruction when addressing dynamic sets without an upper bound on set cardinality. Moreover, the analysis results hold in stand-alone applications, as well as distributed applications.