新一代Internet中的多协议标记交换

随着Internet的飞速发展，传统的路由方式已经不能满足高速路由的要求。IEGF努力地对一些最初在20世纪90年代中期被建议的专用多层交换方案标准化，进而形成MPLS标准。MPLS为未来更高速度的Internet的发展提供了广阔空间。     

CLOVER: a faster prior-free approach to rare-category detection

Rare-category detection helps discover new rare classes in an unlabeled data set by selecting their candidate data examples for labeling. Most of the existing approaches for rare-category detection require prior information about the data set without which they are otherwise not applicable. The prior-free algorithms try to address this problem without prior information about the data set; though, the compensation is high time complexity, which is not lower than $O(dN^2)$ where $N$ is the number of data examples in a data set and $d$ is the data set dimension. In this paper, we propose CLOVER a prior-free algorithm by introducing a novel rare-category criterion known as local variation degree (LVD), which utilizes the characteristics of rare classes for identifying rare-class data examples from other types of data examples and passes those data examples with maximum LVD values to CLOVER for labeling. A remarkable improvement is that CLOVER’s time complexity is $O(dN^{2-1/d})$ for $d > 1$ or $O(N\log N)$ for $d = 1$ . Extensive experimental results on real data sets demonstrate the effectiveness and efficiency of our method in terms of new rare classes discovery and lower time complexity.     

ATM上的IP交换技术

本文介绍了异步传输模式（ＡＴＭ）网络体系结构，重点叙述了其上的交换技术，并指出，ＡＴＭ中的ＩＰ交换技术将快速ＡＴＭ硬件直接与ＩＰ集成在一起，提高了信息的交换速度。这种解决方法综合了ＩＰ的简单性、伸缩性和健壮性，以及ＡＴＭ的速度快、容量高及多服务的通讯能力。     

互连网Internet上的接力通信过程与性能改进

研究了互连网Ｉｎｔｅｒｎｅｔ网中的接力通信过程和提高性能的方法，并说明域量转换 ＩＰ地址的作用及使用注意事项。     

HAL: a faster match algorithm

Existing match algorithms treat the matching process like the querying process of relational databases. Owing to the combinatorial nature of the matching process, the match time greatly varies in different recognize-act cycles. Current match algorithms utilize local matching support networks with redundant working memory elements shared among rules involving the same classes. Since the match time is a dominant factor in the total execution time of a production system, such large match time makes production systems with existing match algorithms unsuitable for many applications. To reduce match time, we introduce the Heuristically-Annotated-Linkage (HAL) match algorithm. HAL differs from traditional match algorithms in that HAL employs a fixed-traversal-distance pseudobipartite network approach of treating rules and classes as objects, or nodes, in only one global pseudobipartite-graph-like connection and communication scheme. In addition, HAL is more efficient than other existing match algorithms because it is capable of immediate characterization of any new datum upon arrival. This paper reviews existing match algorithms, presents HAL, and analyzes the performance of HAL in comparison with existing algorithms.     

A faster solution to the horizon problem

An algorithm is developed for calculating the horizons for each point in a digital terrain grid in order N iterations, whereas all previous methods seem to be of O(N²) time complexity. The new method makes horizon computations reasonable, and ought to improve the accuracy of surface climate models in rugged terrain.     

Constructing a Switching Regression with Unknown Switching Points

Switching regression is considered in the case where switching points are unknown. A general method is described to estimate switching points and parameters of linear regression with switching. Examples of its use are given.     

DNF sparsification and a faster deterministic counting algorithm

Given a DNF formula f on n variables, the two natural size measures are the number of terms or size s(f) and the maximum width of a term w(f). It is folklore that small DNF formulas can be made narrow: if a formula has m terms, it can be ${\epsilon}$ -approximated by a formula with width ${{\rm log}(m/{\epsilon})}$ . We prove a converse, showing that narrow formulas can be sparsified. More precisely, any width w DNF irrespective of its size can be ${\epsilon}$ -approximated by a width w DNF with at most ${(w\, {\rm log}(1/{\epsilon}))^{O(w)}}$ terms. We combine our sparsification result with the work of Luby & Velickovic (1991, Algorithmica 16(4/5):415–433, 1996) to give a faster deterministic algorithm for approximately counting the number of satisfying solutions to a DNF. Given a formula on n variables with poly(n) terms, we give a deterministic ${n^{\tilde{O}({\rm log}\, {\rm log} (n))}}$ time algorithm that computes an additive ${\epsilon}$ approximation to the fraction of satisfying assignments of f for ${\epsilon = 1/{\rm poly}({\rm log}\, n)}$ . The previous best result due to Luby and Velickovic from nearly two decades ago had a run time of ${n^{{\rm exp}(O(\sqrt{{\rm log}\, {\rm log} n}))}}$ (Luby & Velickovic 1991, in Algorithmica 16(4/5):415–433, 1996).     

Internet access to a home area network

The AutoHan project implements a self-configuring software architecture for home area networks that offers an XML-based registry and HTTP-based service. The article begins by introducing the low-level architectures of the AutoHan project that enable different networking technologies to interoperate and define one logical IP network. It then describes the two core services that enable resources to export, discover and interoperate with AutoHan by using these low-level architectures. Finally, the article discusses naming and addressing issues for Internet access and shows how XML and HTTP allowed extension of the system to support Internet access through IHan (Internet home area network)     

A faster parallel algorithm for a matrix searching problem

We give an improved parallel algorithm for the problem of computing the tube minima of a totally monotonen ×n ×n matrix, an important matrix searching problem that was formalized by Aggarwal and Park and has many applications. Our algorithm runs inO(log logn) time withO(n²/log logn) processors in theCRCW-PRAM model, whereas the previous best ran inO((log logn)²) time withO(n²/(log logn)² processors, also in theCRCW-PRAM model. Thus we improve the speed without any deterioration in thetime ×processors product. Our improved bound immediately translates into improvedCRCW-PRAM bounds for the numerous applications of this problem, including string editing, construction of Huffmann codes and other coding trees, and many other combinatorial and geometric problems.This research was supported by the Office of Naval Research under Grants N00014-84-K-0502 and N00014-86-K-0689, the Air Force Office of Scientific Research under Grant AFOSR-90-0107, the National Science Foundation under Grant DCR-8451393, and the National Library of Medicine under Grant R01-LM05118. Part of the research was done while the author was at Princeton University, visiting the DIMACS center.     

Computing sparse permanents faster

Bax and Franklin (2002) gave a randomized algorithm for exactly computing the permanent of any n×n zero-one matrix in expected time exp[−Ω(n1/3/(2lnn))]n². Building on their work, we show that for any constant C>0 there is a constant ?>0 such that the permanent of any n×n (real or complex) matrix with at most Cn nonzero entries can be computed in deterministic time n(2−?) and space O(n). This improves on the Ω(n²) runtime of Ryser's algorithm for computing the permanent of an arbitrary real or complex matrix.     

Evolutionary programming made faster

Evolutionary programming (EP) has been applied with success to many numerical and combinatorial optimization problems in recent years. EP has rather slow convergence rates, however, on some function optimization problems. In the paper, a “fast EP” (FEP) is proposed which uses a Cauchy instead of Gaussian mutation as the primary search operator. The relationship between FEP and classical EP (CEP) is similar to that between fast simulated annealing and the classical version. Both analytical and empirical studies have been carried out to evaluate the performance of FEP and CEP for different function optimization problems. The paper shows that FEP is very good at search in a large neighborhood while CEP is better at search in a small local neighborhood. For a suite of 23 benchmark problems, FEP performs much better than CEP for multimodal functions with many local minima while being comparable to CEP in performance for unimodal and multimodal functions with only a few local minima. The paper also shows the relationship between the search step size and the probability of finding a global optimum and thus explains why FEP performs better than CEP on some functions but not on others. In addition, the importance of the neighborhood size and its relationship to the probability of finding a near-optimum is investigated. Based on these analyses, an improved FEP (IFEP) is proposed and tested empirically. This technique mixes different search operators (mutations). The experimental results show that IFEP performs better than or as well as the better of FEP and CEP for most benchmark problems tested     

快速倒序算子的研究

为了有效地处理建筑块,Bagley最先提出了应用倒序算子来对定义建筑块的基因进行适应性聚集。但是Bagley和Frantz的研究都表明,倒序算子太慢,作用不明显。针对TSP问题,郭涛提出一个“带导向的”倒序算子,取得了很好的效果。为了设计更快速的倒序算子,提出结合粒子群优化的方法改进郭涛算法,更好地利用当前最优解指导倒序,同时对个体施加倒序运算后立即评估,如有改进马上保存,从而巩固所获取的建筑块,不至于因为后面的错误而导致前功尽弃。实验结果证明了新算法的可行性。     

Optical networking chips get faster in a slow market

Tremendous network traffic growth, along with an increase in multimedia and other data-intensive traffic, has driven the potential need for high-performance networking technology offering transmission rates of 10 to 40 Gbits per second. Companies such as Internet exchange providers, which connect ISPs to one another, are currently buying 10-Gbps networking products. Companies such as Broadcom, Intel, and Quake Technologies are thus continuing to produce new, faster optical networking chips and hoping their business will turn around when the economy does.     

从互联网到物联网

结合对互联网发展历程的回顾,本文阐述物联网与互联网的联系,分析物联网的主要特点、技术和应用领域。     

更好更快地完成工程项目

更高的效率是一个工程师始终不断追求的目标,尤其当这个效率是由改进的操作方式与更有效的个人工作流程共同作用下的产物时,对工程师们的吸引力就更大了。在由ReedBusiness Information组织的2009＂工程师的心＂大型调查中,     

Even faster lr parsing

Conventional LR parser generators create tables which are used to drive a standard parser procedure. Much faster parsers can be obtained by compiling the table entries into code that is directly executed. A possible drawback with a directly executable parser is its large size. In this paper, we introduce optimization techniques that increase the parsing speed even further while simultaneously reducing the size of the parser.     

A faster distributed protocol for constructing a minimum spanning tree

This paper studies the problem of constructing a minimum-weight spanning tree (MST) in a distributed network. This is one of the most important problems in the area of distributed computing. There is a long line of gradually improving protocols for this problem, and the state of the art today is a protocol with running time due to Kutten and Peleg [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40-66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20-27], where Λ(G) denotes the diameter of the graph G. Peleg and Rubinovich [D. Peleg, V. Rubinovich, A near-tight lower bound on the time complexity of distributed MST construction, in: Proc. 40th IEEE Symp. on Foundations of Computer Science, 1999, pp. 253-261] have shown that time is required for constructing MST even on graphs of small diameter, and claimed that their result “establishes the asymptotic near-optimality” of the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40-66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20-27].In this paper we refine this claim, and devise a protocol that constructs the MST in rounds, where μ(G,ω) is the MST-radius of the graph. The ratio between the diameter and the MST-radius may be as large as Θ(n), and, consequently, on some inputs our protocol is faster than the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40-66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20-27] by a factor of . Also, on every input, the running time of our protocol is never greater than twice the running time of the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40-66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20-27].As part of our protocol for constructing an MST, we develop a protocol for constructing neighborhood covers with a drastically improved running time. The latter result may be of independent interest.