An efficient IP address lookup algorithm based on a small balanced tree using entry reduction

Due to a tremendous increase in internet traffic, backbone routers must have the capability to forward massive incoming packets at several gigabits per second. IP address lookup is one of the most challenging tasks for high-speed packet forwarding. Some high-end routers have been implemented with hardware parallelism using ternary content addressable memory (TCAM). However, TCAM is much more expensive in terms of circuit complexity as well as power consumption. Therefore, efficient algorithmic solutions are essentially required to be implemented using network processors as low cost solutions.Among the state-of-the-art algorithms for IP address lookup, a binary search based on a balanced tree is effective in providing a low-cost solution. In order to construct a balanced search tree, the prefixes with the nesting relationship should be converted into completely disjointed prefixes. A leaf-pushing technique is very useful to eliminate the nesting relationship among prefixes [V. Srinivasan, G. Varghese, Fast address lookups using controlled prefix expansion, ACM Transactions on Computer Systems 17 (1) (1999) 1-40]. However, it creates duplicate prefixes, thus expanding the search tree.This paper proposes an efficient IP address lookup algorithm based on a small balanced tree using entry reduction. The leaf-pushing technique is used for creating the completely disjointed entries. In the leaf-pushed prefixes, there are numerous pairs of adjacent prefixes with similarities in prefix strings and output ports. The number of entries can be significantly reduced by the use of a new entry reduction method which merges pairs with these similar prefixes. After sorting the reduced disjointed entries, a small balanced tree is constructed with a very small node size. Based on this small balanced tree, a native binary search can be effectively used in address lookup issue. In addition, we propose a new multi-way search algorithm to improve a binary search for IPv4 address lookup. As a result, the proposed algorithms offer excellent lookup performance along with reduced memory requirements. Besides, these provide good scalability for large amounts of routing data and for the address migration toward IPv6. Using both various IPv4 and IPv6 routing data, the performance evaluation results demonstrate that the proposed algorithms have better performance in terms of lookup speed, memory requirement and scalability for the growth of entries and IPv6, as compared with other algorithms based on a binary search.     

A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests

Combinatorial optimization problems are usually modeled in a static fashion. In this kind of problems, all data are known in advance, i.e. before the optimization process has started. However, in practice, many problems are dynamic, and change while the optimization is in progress. For example, in the dynamic vehicle routing problem (DVRP), new orders arrive when the working day plan is in progress. In this case, routes must be reconfigured dynamically while executing the current simulation. The DVRP is an extension of a conventional routing problem, its main interest being the connection to many real word applications (repair services, courier mail services, dial-a-ride services, etc.). In this article, a DVRP is examined, and solving methods based on particle swarm optimization and variable neighborhood search paradigms are proposed. The performance of both approaches is evaluated using a new set of benchmarks that we introduce here as well as existing benchmarks in the literature. Finally, we measure the behavior of both methods in terms of dynamic adaptation.     

Discrete cost optimization of composite floor system using social harmony search model

This paper presents a social harmony search algorithm model for the cost optimization of composite floor system with discrete variables. The total cost function includes the costs of concrete, steel beam and shear studs. The design is based on AISC load and resistance factor design specifications and plastic design concepts. Here, six decision variables are considered for the objective function. In order to demonstrate the capabilities of the proposed model in optimizing composite floor system designs, two design examples taken from the literature are studied. It is shown that use of the presented model results in significant cost saving. Hence, it can be of practical value to structural designers. Also the proposed model is compared to the original harmony search, its recently developed variants, and other meta-heuristic algorithms to illustrate the superiority of the present method in convergence and leading to better solutions. In order to investigate the effects of beam spans and loadings on the cost optimization of composite floor system a parametric study is also conducted.     

A Heuristic Approach to the Discovery of Macro-Operators

This paper describes a heuristic approach to the discovery of useful macro-operators (macros) in problem solving. The approach has been implemented in a program, MACLEARN, that has three parts: macro-proposer, static filter, and dynamic filter. Learning occurs during problem solving, so that performance improves in the course of a single problem trial. Primitive operators and macros are both represented within a uniform representational framework that is closed under composition. This means that new macros can be defined in terms of others, which leads to a definitional hierarchy. The representation also supports the transfer of macros to related problems. MACLEARN is embedded in a supporting system that carries out best-first search. Experiments in macro learning were conducted for two classes of problems: peg solitaire (generalized Hi-Q puzzle), and tile sliding (generalized Fifteen puzzle). The results indicate that MACLEARN'S filtering heuristics all improve search performance, sometimes dramatically. When the system was given practice on simpler training problems, it learned a set of macros that led to successful solutions of several much harder problems.     

Amino acid profiles and liposomes: Their role as chemosensory information carriers in the marine environment

Yellowfin tuna enhance their hunting success in the vast pelagic environment by using their sense of smell to detect intact (uninjured) prey that are beyond visual range. However, the olfactory cues that tuna use would normally face huge and rapid dilution in the open ocean. We demonstrate that these prey odors are complexed within biologically derived lipid structures that probably delay the dilution of the amino acids to subthreshold concentrations and provide persistent arousal and search cues for the tuna. This may be the first demonstration of an extracorporeal biological function for liposomes. Tuna may also form chemical search images to maximize feeding efficiency. We demonstrate that the amino acid profiles of various prey species are consistent over time and between schools, which makes the formation of search images feasible.     

A heuristic 0–1 integer programming method

Summary In this paper, we present a novel relaxation method for the integer programming problem:Ax=b,A {–1,0,+1}^m×N,x {0,1}^N, N>m. The report includes experimental results of problems with up tom=100 equations andN=400 variables.     

Parallel depth first search. Part II. Analysis

This paper presents the analysis of a parallel formulation of depth-first search. At the heart of this parallel formulation is a dynamic work-distribution scheme that divides the work between different processors. The effectiveness of the parallel formulation is strongly influenced by the work-distribution scheme and the target architecture. We introduce the concept of isoefficiency function to characterize the effectiveness of different architectures and work-distribution schemes. Many researchers considered the ring architecture to be quite suitable for parallel depth-first search. Our analytical and experimental results show that hypercube and shared-memory architectures are significantly better. The analysis of previously known work-distribution schemes motivated the design of substantially improved schemes for ring and shared-memory architectures. In particular, we present a work-distribution algorithm that guarantees close to optimal performance on a shared-memory/-network-with-message-combining architecture (e.g. RP3). Much of the analysis presented in this paper is applicable to other parallel algorithms in which work is dynamically shared between different processors (e.g., parallel divide-and-conquer algorithms). The concept of isoefficiency is useful in characterizing the scalability of a variety of parallel algorithms.This work was supported by Army Research Office Grant No. DAAG29-84-K-0060 to the Artificial Intelligence Laboratory, and Office of Naval Research Grant N00014-86-K-0763 to the Computer Science Department at the University of Texas at Austin.     

基于绿色证书交易机制的含风电场电力系统动态环境经济调度

为了促进风电消纳以及提高电力系统的经济性,构建基于绿色证书交易机制的含风电场电力系统多目标动态环境经济调度（DEED）模型,提出一种基于反向学习混沌搜索的OLCS-MOEA/D算法的DEED调度求解方法。首先,采用广义反向学习初始化种群提高种群多样性,并引入基于Logistic映射的混沌搜索算法以增强算法局部搜索能力。然后,为了验证算法的性能,采用标准测试函数F1—F7进行测试,同时将该算法对模型进行求解,获得了比其他算法范围更广和分布均匀的Pareto解集前沿。最后,对基于绿色证书交易机制的动态环境经济调度与传统动态环境经济调度进行结果对比分析,通过仿真算例验证该模型和算法的有效性和优越性。     

基于改进狮群算法和BP神经网络模型的房价预测

将狮群算法(lion swarm optimization, LSO)与海鸥算法的迁徙机制和螺旋搜索机制结合,增强算法的局部搜索能力;同时增加监督机制,提高算法的全局搜索能力。与粒子群算法和狮群算法对比,在常用的测试函数上验证改进狮群算法的优越性。采用改进后的狮群算法优化BP神经网络模型,对房屋价格预测问题进行研究,通过房屋的户型、面积等相关指标有效地对青岛市的二手房价格进行预测。改进后的狮群算法对BP神经网络的权值和偏置进行优化,提高BP神经网络的收敛速度和训练精度。试验结果表明,提出的螺旋搜索狮群和BP结合算法(spiral search lion swarm optimization-BP, SLSO-BP)模型在房价预测问题上预测效果更好。     

FBMC-OQAM系统中一种改进的OPTS算法

针对采用重叠部分传输序列(overlapping partial transmit sequence, OPTS)算法来抑制滤波器组多载波-偏移正交幅度调制(filter bank multicarrier-offset quadrature amplitude modulation, FBMC-OQAM)信号的峰均比(peak-to-average power ratio, PAPR)时会导致计算量过高的问题,在对现有的禁忌搜索算法进行改进后提出一种基于并行禁忌搜索的OPTS(parallel tabu search overlapping partial transmit sequence algorithm, parallel-TS-OPTS)算法,通过将h路传统禁忌搜索算法得出的各自最优解进行遗传交叉操作来优化传统禁忌搜索算法的初始解,从而进一步增大算法搜索到最佳相位因子向量的概率。理论分析与仿真结果表明,本研究的算法可以在获得接近于OPTS算法PAPR抑制效果的同时显著降低算法的计算复杂度,进一步提高FBMC-OQAM系统应用在5G场景中的鲁棒性。