网络拓扑发现综述与展望

随着网络技术的迅速发展，网络规模不断扩大，网络结构越来越复杂，网络功能越来越强大，因而网络管理成了网络系统正常运行的关键，而网络拓扑发现恰是网络管理的基础。同时，要对网络性能及流量进行分析，首先也必须得到正确的拓扑结构和相关信息。网络拓扑发现正是利用网管协议或网络提供的可用工具开发出的一种拓扑算法或拓扑工具，用此算法或工具，可发现网络中所有主机、路由器、节点及其连接关系，从而得到完整的拓扑图。在实际中，准确高效地完成网络拓扑发现并非易事。国外大公司均有成熟的拓扑工具，且大多是基于网络管理协议（S…     

基于合并分层聚类的网络拓扑推断算法

针对HTE（Hierarchical Topology Estimation）算法计算复杂度较高的问题及其在节点相关性估计方差较大条件下性能下降的问题，提出基于合并分层聚类的网络拓扑推断算法.该算法采用自底向上的合并分层聚类，每次聚类仅使用与最大相关节点对有关的数据，相对HTE算法降低了运算复杂度；建立了改进的有限混合模型，增加了参数推断的有效数据，提高了算法的参数估计精度.仿真结果表明相对HTE算法，本文方法可以更快地推断出网络拓扑，且在节点相关性估计方差较大条件下，有更高的拓扑推断精度.     

MPLS流量工程及基于约束路由计算的研究

论述了 MPLS 网络的架构及其对流量工程的支持,研究了基于 MPLS 流量工程要解决的几个主要问题：如何把数据包映射为转发等价类等,并对其中最重要的一个——通过 LSP 把流量中继映射到实际网络拓扑,提出了一种约束最短路径优先算法的实现方法。     

WDM对终端业务和高层协议的影响

主要从基于 WDM网络的网络层及其高层出发 ,描述了以下问题 :业务准备算法以便最小化电复用的代价 ;波长分配算法 ;光层和电层联合保护和恢复 ;光网络拓扑对高层协议 ,如 IP选路、TCP流量控制和多层交换对光网络拓扑的影响。     

基于混合流量数据的连通分量计算技术

连通分量计算技术作为网络拓扑结构分析的重要研究领域,能够获取和维护网络节点的连接关系信息。文中围绕网络连通分量计算的高效准确处理要求,提出了基于混合流量数据的连通分量计算方法,利用深度优先搜索算法实现了对IPv4/IPv6混合流量数据的连通分量计算,并在此基础上实现了增量连通分量计算,提高了算法对新增数据的计算效率,最后进行了相关的实验。经验证,该方法功能上能够对混合流量数据进行连通分量计算,性能上当原流量数据和新加入流量数据的数据量大小接近时,算法提升效率提高70%左右。     

引入流量因素的路由表查找算法

分析了流量因素对路由表查找算法性能的影响，在CPU缓存技术的基础上提出引入流量分布因素的路由表查找算法，并对算法性能及适用性进行了讨论。     

基于最小干扰路由的流量工程动态路由算法研究

分析目前流量工程动态路由算法研究现状,以提高网络吞吐量为目标,提出一种改进的流量工程动态路由算法,综合考虑了网络拓扑和流量分布状况,提出分级的链路关键度定义,将流量工程目标有效转化为路径约束。仿真结果表明所提算法性能比Kodialam算法及其它几种典型的动态路由算法好。     

一种改进的IP网络拓扑发现算法

网络拓扑发现已经成为网络上任何业务及性能分析的基础。该文在对网络拓扑发现的各种概念深入分析的基础上,提出了一种基于Ping和Traceroute的拓扑发现改进算法。该改进算法使用范围广,较以前基于Ping和Traceroute提出的算法速度大为提高。     

IP over WDM网络中一种新型虚拓扑构造算法

对IP over WDM的虚拓扑设计算法进行了研究，选择网络整体流量的均衡性作为优化目标，提出了一种新型的虚拓扑构造算法。在算法中，选择负载分布方差作为评价流量均衡性的指标，并给出其定义和计算方法。主要针对拥塞概率性能，在光层和IP层将提出的新型虚拓扑构造算法与其他算法进行比较。在光层的算法比较部分，选择负载均衡启发式路由算法（RLBH，routing with load balancing heuristics）与提出的算法进行比较；在IP层的算法比较部分，选择固定路径最小拥塞路由算法（FPLC，fixed-path least-congestion）与提出的算法进行比较，并对比较结果进行了讨论。比较结果显示在拥塞概率性能方面，提出的新型虚拓扑构造算法优于RLBH算法和FPLC算法。     

Tracker中一种具有拓扑意识的结点选择算法(TAPS)

BitTorrent系统是当前最流行的P2P文件共享系统,但因其Tracker采用随机的结点选择算法从而造成了大量的冗余网络流量。文章提出一种基于拓扑意识的结点选择算法TAPS,根据网络拓扑信息进行结点选择。经过仿真实验证明,TAPS(10,40,∞)在保证BitTorrent应用性能的前提下极大地减少了骨干网流量和网络负载。     

Virtual rate control algorithm for active queue management in TCPnetworks

A virtual rate control (VRC) algorithm for active queue management (AQM) to regulate the queue length with small variation and to achieve high utilisation with small packet loss is proposed. Through ns simulations, the effectiveness of the proposed VRC algorithm as compared with several well-known AQM schemes such as random early detection (RED), random exponential marking (REM), and adaptive virtual queue (AVQ) algorithms is shown     

An adaptive virtual queue (AVQ) algorithm for active queue management

Virtual queue-based marking schemes have been recently proposed for Active Queue Management (AQM) in Internet routers. We consider a particular scheme, which we call the Adaptive Virtual Queue (AVQ), and study its following properties: its stability in the presence of feedback delays, its ability to maintain small queue lengths, and its robustness in the presence of extremely short flows (the so-called web mice). Using a linearized model of the system dynamics, we present a simple rule to design the parameters of the AVQ algorithm. We then compare its performance through simulation with several well-known AQM schemes such as RED, REM, Proportional Integral (PI) controller, and a nonadaptive virtual queue algorithm. With a view toward implementation, we show that AVQ can be implemented as a simple token bucket using only a few lines of code.     

Advances in Active Queue Management (AQM) Based TCP Congestion Control

Current end-to-end Internet congestion control under tail-drop (TD) queue management experiences performance degradations such as multiple packet losses, high queueing delay and low link utilization. In this paper, we review recently proposed active queue management (AQM) algorithms for supporting end-to-end transmission control protocol (TCP) congestion control. We focus recently developed control theoretic design and analysis method for the AQM based TCP congestion control dynamics. In this context, we analyze the problems of existing AQM proposals in which congestion is detected and controlled reactively based on current and/or past congestion. Then we argue that AQM based TCP congestion control should be adaptive to the dynamically changing traffic situation in order to detect, control and avoid the current and the incipient congestion proactively. Finally, we survey two adaptive and proactive AQM algorithms, PID-controller and Pro-Active Queue Management (PAQM), designed using classical proportional-integral–derivative (PID) feedback control to overcome the reactive congestion control dynamics of existing AQM algorithms. A comparative study of these AQM algorithms with existing AQM algorithms is given. A simulation study under a wide range of realistic traffic conditions suggests that PID-controller and PAQM outperform other AQM algorithms such as random early detection (RED) [Floyd and Jacobson, 18] and proportional-integral (PI) controller [Hollot et al., 24].     

Generalized threshold replenishment: an adaptive vectorquantization algorithm for the coding of nonstationary sources

In this paper, we describe a new adaptive-vector-quantization (AVQ) algorithm designed for the coding of non-stationary sources. This new algorithm, generalized threshold replenishment (GTR), differs from prior AVQ algorithms in that it features an explicit, online consideration of both rate and distortion. Because of its online nature, GTR is more amenable to real-time hardware and software implementation than are many prior AVQ algorithms that rely on traditional batch training methods. Additionally, as rate-distortion cost criteria are used in both the determination of nearest-neighbor codewords and the decision to update the codebook, GTR achieves rate-distortion performance superior to that of other AVQ algorithms, particularly for low-rate coding. Results are presented that illustrate low-rate performance surpassing that of other AVQ algorithms for the coding of both an image sequence and an artificial non-stationary random process. For the image sequence, it is shown that (1) most AVQ algorithms achieve distortion much lower than that of nonadaptive VQ for the same rate (about 1.5 b/pixel), and (2) GTR achieves performance substantially superior to that of the other AVQ algorithms for low-rate coding, being the only algorithm to achieve a rate below 1.0 b/pixel.     

Dynamic survivable mapping through reconfiguration in IP over WDM network

A new approach for network survivability problem in Intemet protocol （IP） over wavelength division multiplexing （WDM） optical network is proposed to enhance the IP layer restorability under physical link failure through logical topology reconfiguration. More specifically, after traffic arrival and departure, reconfiguring the logical topology correspondingly is helpful to minimize the traffic disruption after physical link failure. So, in this paper, this problem is proposed for first time and formulated as an integer linear programming （ILP） problem. And then, two heuristic algorithms are proposed. The performance of proposed algorithms have been evaluated through simulations, and the results show that reconfiguring the logical topology dynamically could achieve more than 20% improvement of the restorability of traffic in IP layer, but with acceptable resource cost.     

Dynamic load balancing in WDM packet networks with and without wavelength constraints

We develop load balancing algorithms for WDM-based packet networks where the average traffic between nodes is dynamically changing. In WDM-based packet networks, routers are connected to each other using wavelengths (lightpaths) to form a logical network topology. The logical topology may be reconfigured by rearranging the lightpaths connecting the routers. Our algorithms reconfigure the logical topology to minimize the maximum link load. In this paper, we develop iterative reconfiguration algorithms for load balancing that track rapid changes in the traffic pattern. At each reconfiguration step, our algorithms make only a small change to the network topology hence minimizing the disruption to the network. We study the performance of our algorithms under several dynamic traffic scenarios and show that our algorithms perform near optimally. We further show that these large reconfiguration gains are achievable in systems with a limited number of wavelengths.     

PDAVQ：一种基于PD控制的自适应虚拟队列管理算法

提出了一种新的基于比例差分控制的自适应虚拟队列管理(AVQ)算法—PDAVQ,用于对网络链路中产生的拥塞进行控制,以达到有效利用网络带宽,使整个网络系统达到稳定,缓解网络拥塞的目的。而且本文对所提算法运用控制理论对系统的稳定性进行了证明,给出了满足系统稳定性条件的参数选择方法和 PDAVQ 算法的具体描述。最后,通过 ns2 仿真实验与现有的 AVQ 算法比较,结果表明,所提 PDAVQ 算法具有较高的吞吐率、较低的链路延迟和数据丢失率,并能更快的使整个网络系统达到稳定,具有较好的网络性能。     

Advances in internet congestion control

In this survey, we first review the concept of congestion control with a focus on the Transmission Control Protocol⁄Internet Protocol (TCP⁄IP). We describe many recently proposed algorithms to combat congestion and improve performance, particularly active queue management (AQM) algorithms such as random early detection (RED) and its variants. We then survey control-theoretic analysis and design of TCP congestion control with an AQM scheme. In addition, we discuss three problems associated with AQM proposals: parameter setting, the insensitivity to the input traffic load variation, and the mismatch between macroscopic and microscopic behavior of queue length dynamics. As alternatives to AQM algorithms, we also survey architectural approaches such as modification of source or network algorithms, and economic approaches including pricing or optimization of allocated resources. Finally, we list many open issues that persist in the design, operation, and control of the Internet.     

几种主动式队列管理算法的比较研究

主动式队列管理(Active Queue Management,AQM)技术是IETF为了解决Internet拥塞控制问题而提出的一种路由器缓存管理技术.本文对几种主要AQM算法RED、BLUE、ARED和SRED的性能在基于ns-2仿真实验的基础上进行了比较研究.研究的性能包括队列长度、丢包概率、丢包率、连接数对吞吐量的影响及缓冲区大小对链路利用率的影响等.仿真结果表明BLUE、ARED和SRED在这几方面的性能都要优于RED算法.     

SABlue:一种带加速因子的自适应AQM算法

该文在分析SBlue算法的基础上,提出了一种带加速因子的自适应AQM算法SABlue(Self-tune Accelerate Blue)。算法将瞬时队长作为早期拥塞检测参量,根据队列负载因子控制丢包步长,实现丢包概率幅度的自适应调整,最终将路由队列长度稳定在目标区域内。为了提高网络突变跨度较大情况时算法的响应速度,在队列警戒区域内引入了加速因子。实验表明,SABlue面对突变流和不同RTT的网络场景,队列收敛时间短,丢包率小,且具有较好的鲁棒性,算法综合性能优于其他AQM算法。