A hardware algorithm for fast logarithmic computation with exponential convergence rate

Abstract

A hardware algorithm is proposed for improving the speed of the linear digit‐recurrence logarithmic algorithm. The convergence rate of this logarithmic algorithm is exponential. Furthermore, the size of the lookup tables used in the algorithm is smaller than the size of the lookup tables used in the digit‐recurrence algorithms. When the word length of the operand is less than or equal to 64 bits, the operations involved in each stage of the logarithmic computation only include small table lookup operation, digit‐multiplication, and simple square operations. We conclude that the hardware implementation of our proposed algorithm is very efficient.     

动态快速路由查找算法

给出了动态快速路由查找算法（DFR）的原理和实现。该算法采用特殊的数据结构来构建索引表，能支持动态插入、删除和更新路由；DFR算法最多4次访存，最少2次访存，就能找到完整的路由信息。该算法不仅适用于软件实现，而且由于查找简单，也适合于硬件实现。     

A fast algorithm for polynomial evaluation in Reed-Solomon codec

An efficient lookup table algorithm for computing the values of message polynomials during high throughput encoding of Reed–Solomon (RS) codes is presented in this paper. The algorithm can be applied to RS codes encoders, which are based on Vandermonde matrix and the polynomial computations. The lookup table derived from the algorithm can then be applied not only to an encoder of RS codes but also to syndromes evaluation in the decoding of RS codes. By comparison with Horner’s rule, one of the advantages of utilizing this algorithm is that the table lookup operations for computing the values of the message polynomial are reduced by a factor of three. It would reduce the encoding time by fifty-percent using the linear feedback shift register to encode the (204, 188, t = 8) RS code. The algorithm can also be used to evaluate the syndromes needed in part of the RS decoder, and thus the speed is much faster than Horner’s rule. Ultimately, the proposed encoding and syndrome evaluation algorithm for RS codes can be made regular, simple and suitable for software implementations.     

高性能安全路由器BW7000的设计与实现

高性能和安全是计算机网络研究的两个主要问题。路由器在保证转发性能的前提下提供网络安全保护已经成为当前的研究热点。文章介绍了在完成国家"八六三"计划重大课题"高性能安全路由器"的过程中解决的若干关键技术问题。高性能安全路由器BW7000基于自主设计的高性能路由器操作系统HEROS。为保证高性能的路由转发,设计实现了基于RAM的高性能路由查找算法;为支持服务质量控制和安全管理,设计实现了基于无冲突HashTrie树的分组分类算法和基于反馈的分布式分组调度算法;为保证网络安全,提出了基于分布式密钥管理的路由器安     

Automated image mosaicking

Abstract

This paper developed and implemented automated image mosaicking procedures to produce seamless and smooth mosaics from random sequences of digital aerial images and satellite images. The procedure employs automated algorithms for global image registration, seam line extraction, radiometric adjustment, and composition of overlap images. Results of the experimentation on mosaicking black and white orthorectified aerial images and on mosaicking multi‐resolution color infrared SPOT‐2 and Landsat‐5 satellite images show that the implementation of automated conjugate point extraction and image matching algorithms automates the establishment of geometric registration among overlapped images, while the seam line selection and two‐step lookup table histogram matching approaches facilitate creating globally smooth and qualitative mosaics. The system developed in this paper makes complex composition of multi‐source multi‐resolution multi‐band images with different geometric and radiometric characteristics an easy and efficient solution for producing reliable mosaic images.     

Graph contractability problem for VLSI layer assignment

Abstract

The layer assignment problem for VLSI routing is the problem of determining which layers can be used for routing the wire segments in the interconnections of nets so that the number of vias is minimized. In this paper, we transform the problem of layer assignment for three‐layer routing to the contractability problem of 3‐colorable graph. This problem is shown to be NP‐complete and a heuristic algorithm is proposed on the basis of the graph contractability model. From our experimental results, the algorithm is faster and efficient to generate very good results. In the average, the number of vias can be reduced by 30 percent or so.     

Development of a genetic algorithm‐based lookup table approach for efficient numerical integration in the method of finite spheres with application to the solution of thin beam and plate problems

It is observed that for the solution of thin beam and plate problems using the meshfree method of finite spheres, Gaussian and adaptive quadrature schemes are computationally inefficient. In this paper, we develop a novel technique in which the integration points and weights are generated using genetic algorithms and stored in a lookup table using normalized coordinates as part of an offline computational step. During online computations, this lookup table is used much like a table of Gaussian integration points and weights in the finite element computations. This technique offers significant reduction of computational time without sacrificing accuracy. Example problems are solved which demonstrate the effectiveness of the procedure. Copyright © 2006 John Wiley & Sons, Ltd.     

区域标记交换路由查找的性能分析

介绍了一种新的标记交换体制——基于区域编码的标记交换(RILS)。着重分析了RILS和传统IP网络的路由查找性能,并采用仿真对它们的可扩展性进行了比较。结果表明,RILS路由查找与现有的IP路由查找相比,需要更少的存储空间,具有更低的操作复杂度、更新复杂度以及更好的可扩展性。     

The design of a DFSA based pattern matcher

Abstract

In order to eliminate the irrelevant data being transferred from disks into memory, many database machines adopt a data filter to filter out the irrelevant data on‐the‐fly. This paper proposes a new DFSA (Deterministic Finite State Automata) based pattern matcher to be implemented as the data filter. It can perform various searching operations, including fixed and variable length don't care patterns. The architecture of this pattern matcher is relatively simple and can be easily implemented by off‐the‐shelf LSI chips. In our design, it only requires one 16K×8 SRAM and five LSI chips for a given state transition table of 128 states.

A test has been conducted to compare the performance of dBASE III and our data filter. The result shows that the data filter is, on average, five times better than the performance of dBASE III.     

OSPF routing with optimal oblivious performance ratio under polyhedral demand uncertainty

We study the best OSPF style routing problem in telecommunication networks, where weight management is employed to get a routing configuration with the minimum oblivious ratio. We consider polyhedral demand uncertainty: the set of traffic matrices is a polyhedron defined by a set of linear constraints, and a routing is sought with a fair performance for any feasible traffic matrix in the polyhedron. The problem accurately reflects real world networks, where demands can only be estimated, and models one of the main traffic forwarding technologies, Open Shortest Path First (OSPF) routing with equal load sharing. This is an NP-hard problem as it generalizes the problem with a fixed demand matrix, which is also NP-hard.     

基于IPv6的PIM-SMv2协议的设计与实现

在新一代互联网中,支持组播已成为对路由器的基本要求。PIM-SM是一个不依赖于某一特定单播路由协议的组播路由协议,为组播数据转发提供路由信息。本文介绍了高性能：IPv6路由器协议栈软件中基于原始套接字(Raw Socket)通信机制的PIM—SMv2协议的设计与实现,并搭建实验环境对实现的系统进行了测试。实验结果表明,该系统已具备IPv6组播功能。     

An expert system for network management control

Abstract

Due to the varying time and the complexity of the commercial telecommunication network configuration, routing of the communication traffic becomes very important for telecommunication systems. No one can keep in mind all the complex routing plans used in networks, so it is hard to quickly take proper actions while the switching node is being blocked.

In this paper, we propose an expert system which can collect traffic data, monitor network status, reason and take appropriate actions for extreme traffic congestion on a network just as a network management expert can do. It would certainly streamline the whole network control procedure, and. provide dynamic routing functions based on the original static routing method adopted in Taiwan. It does improve both network efficiency and network reliability.     

Numerical techniques for high-throughput reflectance interference biosensing

Abstract

We have developed a robust and rapid computational method for processing the raw spectral data collected from thin film optical interference biosensors. We have applied this method to Interference Reflectance Imaging Sensor (IRIS) measurements and observed a 10,000 fold improvement in processing time, unlocking a variety of clinical and scientific applications. Interference biosensors have advantages over similar technologies in certain applications, for example highly multiplexed measurements of molecular kinetics. However, processing raw IRIS data into useful measurements has been prohibitively time consuming for high-throughput studies. Here we describe the implementation of a lookup table (LUT) technique that provides accurate results in far less time than naive methods. We also discuss an additional benefit that the LUT method can be used with a wider range of interference layer thickness and experimental configurations that are incompatible with methods that require fitting the spectral response.     

DHT系统的安全性优化方法研究

对分布式哈希表(DHT)系统的安全脆弱性问题进行了研究,提出了多种安全性优化策略,并给出了一个原型系统。进行了真实网络实验,实验数据表明,现有DHT网络易受索引毒害和路由污染攻击,产生的错误查询结果甚至会引发更大规模的网络安全事件。通过改进一个个DHT系统的节点ID生成机制、路由表更新机制和搜索路径选择机制,从系统运行的各个阶段提升其安全场,抵御攻击者共谋。基于上述方法设计的原型系统在保证平均查询跳数增加不到1跳的情况下,在共谋攻击节点占比60%的网络中,将系统查询成功率保持在65%以上,其方法适用于各种分布式哈希表结构,具有重要的实际应用前景。     

基于前缀区间和前缀层次(PRPL)的IPv6路由查找算法

通过对前缀区间（PR）和前缀层次（PL）的研究,并结合IPv6全球单播地址和IPv6骨干网路由表的特征,提出了一种基于前缀区间和前缀层次（PRPL）的高性能的IPv6路由查找算法。通过使用合成的不同数据量的IPv6路由表对该算法进行了测试,测试结果表明该算法的可扩展性非常出色,它能够支持数据量达到。200k的大路由表。与同样环境下的经典算法的测试结果进行了比较,比较结果也表明该算法在平均查找速度和内存消耗方面都有一定的优势。出色的性能和对大路由表的支持,使得该算法能够应用到骨干网IPv6路由器中。     

基于有效性验证的V-D算法研究

论述了TCP／IP网络中距离向量（V－D）算法中的慢收敛问题，以及一些解决方法的不足，针对路由信息的有效性问题，提出了基于有效性验证的V－D算法，有效地防止了无效路由信息对路由表的修改，解决了慢收敛问题，同时提出采用环路消除分组的方法，以防止环路产生，并可以快速消除环路上的无效信息。     

Hierarchical wireless mobile MPLS mechanism using foreign tracking agent based on M/G/1 with capacity c queueing model

Within the Multiprotocol Label Switching (MPLS) network, packets with the same forwarding equivalent class can easily be identified by their attached label value. The cross-layer topology associates with access protocol and IP mobility agents. The necessity of agent discovery is reduced and an approach to enhance handoff efficiency proposed. This efficient handoff scheme is performed by a foreign tracking agent (FTA) that plays a role as an administrator of a hierarchy that consists of some foreign agents (FAs) to localise the routing operation of forwarded packets. To analyse the performance of a hierarchical mobile MPLS network, the system is modelled as an M/G/1 system with capacity c, where c represents the number of FAs that can be administered for an FTA. The mean delay time of the FTA to process the forwarding of packets is analysed using M/M/l with capacity c queueing model. The minimum number of FAs that can be administered for an FTA is derived to improve network performance by minimising mean delay time.     

A vehicle routing problem with time windows and stochastic demands

Abstract

This study presents an approach for considering a vehicle routing problem where customers’ pickup demands are uncertain and require serving within some settled time windows. Customers’ demands are assumed to follow given discrete probability distributions. This study proposes a nonlinear stochastic integer program with recourse to formulate the vehicle routing problem with stochastic demands and time windows (VRPTW‐SD, for short). The objective of the VRPTW‐SD is to minimize the total cost of the first‐stage solution and expected recourse cost of the second‐stage solution. The total cost of the first‐stage problem includes the total travel cost for all links and the total waiting cost at all nodes. When a vehicle capacity is attained or exceeded, recourse actions are needed and recourse costs incurred in order to finish the planned route schedules. Two categories of schedule failure are introduced in this work; the recourse costs derive from the variations in travel time travel time, waiting time, and penalties of late arrival for time windows. In addition, an optimization algorithm is developed for solving the VRPTW‐SD, according to the framework of the L‐shaped method. Numerical results are given to demonstrate its validity.     

Transfer coefficients on the shell progressive poisoning model

Abstract

The idle server first (ISF) routing strategy in a finite queueing system with multiple unequal‐rate synchronous servers is studied. This paper extends the work of [4] by considering unequal‐rate servers. The input is assumed to be a batch Poisson distribution. The state transition equations used to describe the queueing behavior of the system are successfully solved. The performance measures, including average message blocking probability, average packet delay, average message delay, and system throughput, are obtained. The results show that ISF routing can have pretty good performance, and its effective measures are almost independent of routing probabilities. Validity of the analysis has also been verified by computer simulations.     

A key‐lock‐pair mechanism based on generalized Chinese remainder theorem

Abstract

A new key‐lock‐pair mechanism of access control in information system is proposed. Our method is inspired by Wu and Hwang's result. The most important and common advantages of our method are as follows: 1. The memory storage required for keys and locks is small.

2. The determination of an access right value is fast.

3. The construction of keys and locks is simple.