A routing framework for providing robustness to node failures in mobile ad hoc networks

Nodes in a mobile ad hoc network are often vulnerable to failures. The failures could be either due to fading effects, battery drainage, or as a result of compromised nodes that do not participate in network operations. Intermittent node failures can disrupt routing functionalities. As such, it is important to provide redundancy in terms of providing multiple node-disjoint paths from a source to a destination. In line with this objective, we first propose a modified version of the widely studied ad hoc on-demand distance vector routing protocol to facilitate the discovery of multiple node-disjoint paths from a source to a destination. We find that very few of such paths can be found. Furthermore, as distances between sources and destinations increase, bottlenecks inevitably occur and thus, the possibility of finding multiple paths is considerably reduced. We conclude that it is necessary to place what we call reliable nodes (in terms of both being robust to failure and being secure) in the network to support efficient routing operations. We propose a deployment strategy that determines the positions and the trajectories of these reliable nodes such that we can achieve a framework for reliably routing information. We define a notion of a reliable path which is made up of multiple segments, each of which either entirely consists of reliable nodes, or contains a preset number of multiple paths between the end points of the segment. We show that the probability of establishing a reliable path between a random source and destination pair increases tremendously even with a small number of reliable nodes when we use our algorithm to appropriately position these reliable nodes.     

北电网络安全路由技术

北电网络提供的Contivity解决方案不仅可以使用户建立各种类型的VPN，而且还可以把这些VPN集成到未来的融合话音和数据的网络中。该方案已实现了安全路由选择；可通过多种技术支持鉴权功能，从而实现安全接入；允许用户使用其各自的安全性配置文件设置；其设计中没有“后门”，重点介绍了Contivity 2700网关的主要特征及其优势。     

Compact and localized distributed data structures

This survey concerns the role of data structures for compactly storing and representing various types of information in a localized and distributed fashion. Traditional approaches to data representation are based on global data structures, which require access to the entire structure even if the sought information involves only a small and local set of entities. In contrast, localized data representation schemes are based on breaking the information into small local pieces, or labels , selected in a way that allows one to infer information regarding a small set of entities directly from their labels, without using any additional (global) information. The survey concentrates mainly on combinatorial and algorithmic techniques, such as adjacency and distance labeling schemes and interval schemes for routing, and covers complexity results on various applications, focusing on compact localized schemes for message routing in communication networks.Received: August 2001, Accepted: May 2002, Supported in part by a grant from the Israel Science Foundation.     

Treatment of Natural Geometry in Finite Volume River Flow Computations

A method is proposed for the treatment of irregular bathymetry in one-dimensional finite volume computations of open-channel flow. The strategy adopted is based on a reformulation of the Saint-Venant equations. In contrast with the usual treatment of topography effects as source terms, the method accounts for slope and nonprismaticity by modifying the momentum flux. This makes it possible to precisely balance the hydrostatic pressure contributions associated with variations in valley geometry. The characteristic method is applied to the revised equations, yielding topographic corrections to the numerical fluxes of an upwind scheme. Further adaptations endow the scheme with an ability to capture transcritical sections and wetting fronts in channels of abrupt topography. To test the approach, the scheme is first applied to idealized benchmark problems. The method is then used to route a severe flood through a complex river system: the Tanshui in Northern Taiwan. Computational results compare favorably with gauge records. Discrepancies in water stage represent no more than a fraction of the magnitude of typical bathymetry variations.     

Study on a Distributed Wavelength Routing Algorithm in WDM Optical Transport Networks

A new design scheme for a distributed algorithm for routing and wavelength assignment (RWA) is developed in this paper, and the communication rules between the nodes to exchange signaling packets are discussed. The Adaptive-Alternate-Routing-Least-Load (AARLL) algorithm is implemented in the distributed scheme for the first time. Under dynamic traffic circumstances, the influence of the race condition, which does not exist in centralized scheme, on the network performance is analyzed and the analyzed results show that the race condition has a major impact on network performance only under light traffic load, while under medium and heavy traffic load the impact is very small. To analyze the performance loss caused by adopting the distributed algorithm for RWA, the capacity loss factor (CLF) is introduced and the calculated results show that CLF does not exceed 6% under medium traffic load.     

柔性制造系统的负荷分配及路径规划方法

柔性是柔性制造系统（ＦＭＳ）的一个基本优点，但这一基本优点却往往被人们忽视，许多现在运行的ＦＭＳ不是缺乏柔性，就是没能充分利用可获得的柔性来提高生产效率。柔性制造系统的负荷分配和路径规划问题正是这种柔性的一个主要方面，然而，路规划决策却往往被。其中一个主要原因人们仍不能从传统的生产管理概念中解放出来。本文在明确概念区分的基础上，提出了一种柔性制造系统的负荷分配和路径规划的线性规划模型，其主要特点是     

一种可靠多播认证方案及其C语言实现

传统的认证技术对于多播认证并不适用,因为多播认证有它自身的特殊要求。论文介绍了两种针对多播认证特点的解决方案,并结合两种方案的特点阐述了一种改进的适合可靠多播的认证方案,最后给出了C语言的实现。     

多芯片组件的布线

布线是多芯片组件（ＭＣＭ）ＣＡＤ中的一个关键步骤，由于ＭＣＭ的封装密度很高，因此，因此，其布线问题也较传统的ＩＣ或ＰＣＢ布线更为困难，指出了ＭＣＭ布线中存在的问题，介绍了当前用于ＭＣＭ布线的几种方法，着重讨论了ＳＬＩＣＥ布线法和４通孔布线法，对这几种方法进行了比较，４通孔布线法可直接产生详细布线结果，有利于节省成本和提高布线效率。     

Greedy hot-potato routing on the two-dimensional mesh

Summary We propose hot-potato (or, deflection) packet routing algorithms on the two-dimensional mesh. The algorithms are strongly greedy in the sense that they attempt to send packets in good directions whenever possible. Furthermore, the routing operations are simple and independent of the time that has elapsed. The first algorithm gives the best evacuation time known for delivering all the packets to their destinations. A batch ofk packets with maximal source-to-destination distanced _max is delivered in 2(k-1)+d _max. The second algorithm improves this bound tok+d _max when all packets are destined to the same node. This also implies a new bound for the multitarget case, which is the first to take into account the number of in-edges of a node. The third algorithm is designed for routing permutations with source-to-destination distance at most three, in which case the algorithm terminates in at most seven steps. We also show a lower bound of five steps for this problem. Ishai Ben-Aroya received the B.A. and M.Sc. in computer science from the Technion (Israel Institute of Technology). He is currently working with Microsoft Israel R&D group. His main interests include Routing Algorithms, Cryptography and Computer Security. Tamar Eilam received the B.A. degree in Computer Science from the Technion IIL in 1995, and is currently studying towards her M.A. degree. Assaf Schuster received his B.A., M.A. and Ph.D. degrees in Computer Science from the Hebrew University of Jerusalem (the last one in 1991). He is currently a lecturer at the Technion IIL. His main interests include Networks and Routing Algorithms, Parallel and Distributed Computation, Optical Computation and Communication, Dynamically Reconfiguring Networks, and Greedy Hot Potato Routing.This work was supported in part by the French-Israeli grant for cooperation in Computer Science, and by a grant from the Israeli Ministry of Science. An extended abstract appeared in proc. 2nd European Symposium on Algorithms, September 1994     

一种面向车辆实时数据并行处理的任务调度算法

车辆实时监管正面临着不断增长的大规模车辆监测数据的实时处理需求,需要采用分布式的并行计算架构来提升大规模车辆监测数据处理的性能,支撑多样化的车辆监测数据处理任务,应对支撑环境的伸缩性需求。在这种架构下,对系统中不同计算节点间的车辆监测数据处理任务的调度提出了更高的要求。针对这一要求,并结合流式到达及历史积累的车辆监测数据的持续化处理需求以及大规模车辆监测数据实时处理中内存敏感的特征,提出一种基于路由表的并行任务调度算法。该算法基于车辆监测数据时空属性以及各计算节点的内存信息建立路由表,并以路由表的形式来进行任务的并行划分和分配调度,从而使得各计算节点达到负载均衡的状态。实验表明该算法能够使计算节点间的负载差异缩小到12%以内。此外,该算法在某市车辆监管实时系统中的实际应用也证明了其有效性。