容迟／容断网络路由技术研究

容迟／容断网络（DTN）由于其长延迟、高误码率及频繁断路等网络特性不满足互联网较短传输延迟、低误码率及存在端到端路径的基本假设,传统Internet体系结构和协议无法直接用于DTN。DTN路由机制可以按照连接的确定性分为确定性路由和随机性路由。确定性路由主要有基于树的路由、时空路由和修正的最短路径路由等方法;随机性路由主要有流行性路由、基于历史消息的路由、基于模型的路由、可控移动路由和基于编码的路由。DTN在游牧计算、军事战场通信、紧急营救及灾后重建方面具有广泛应用前景。     

Geographical awareness hybrid routing protocol in Mobile Ad Hoc Networks

This paper proposes a geographical awareness routing protocol based on a hybrid routing protocol, the Zone Routing Protocol (ZRP), in Mobile Ad Hoc Networks (MANETs). ZRP is created from combining proactive routing protocol and on-demand routing protocol; therefore, it inherits the advantages of both these routing protocols. The long delay time of the on-demand routing protocol and the huge routing overhead of the proactive routing approach are reduced in ZRP. However, ZRP still produces a large amount of redundant routing overhead in the route discovery process, which not only wastes energy but also increases the workload of the network, while limited bandwidth is a challenge for MANETs. To mitigate routing overhead, a geographical awareness approach that is applied to limit the discovered route area in ZRP is proposed and is called the Geographical awareness ZRP (GeoZRP). Simulation results confirm that the proposed algorithm alleviates routing overhead and end-to-end delay with only a slightly decrease in the packet delivery ratio.     

A survey of multicast routing protocols for mobile Ad-Hoc networks

A Mobile Ad-hoc NETwork (MANET) is composed of Mobile Nodes (MNs) without any infrastructure. MNs selforganize to form a network over radio links. In this environment, multicast routing protocols are faced with the challenge of producing multi-hop routing under host mobility and bandwidth constraint. Multicast routing plays a significant role in MANETs. In recent years, various multicast routing protocols with distinguishing feature have been newly proposed. In order to provide a comprehensive understanding of these multicast routing protocols designed for MANETs and pave the way for the further research, a survey of the multicast routing protocols is discussed in detail in this paper. Qualitatively, based on their primary multicast routing selection principle, we show that all these protocols could be placed under one of two broad routing selection categories: multicast routing based on application independence and multicast routing based on application dependence.     

UMIR系统设计与实现

随着互联网应用快速增长,域间路由系统的选路灵活性和路由质量面临着重大挑战。多路径路由是提高互联网可靠性和顽健性、满足用户选路灵活性的重要方法。基于前期的研究成果以及面向用户定制路由服务的需求,设计并开发了一套域间多路径路由系统UMIR。 该路由系统包括控制管理、路由发现与计算和路由激励三大功能,具体由控制管理子系统、路由控制子系统、路由激励子系统等构成。在美国Utah大学的Emulab网络测试平台上,对UMIR系统进行了实际部署与测试实验,结果表明该路由系统运行正确,达到了系统预期的设计目标。     

A design framework and taxonomy for hybrid routing protocols in mobile Ad Hoc networks

Routing protocols for mobile ad hoc networks can be classified into two categories: topological routing and geographic routing. Hybrid routing protocols that take advantage of both schemes have attracted a lot of attention recently. This article provides a systematic survey of these hybrid routing protocols. We first analyze the three types of routing information used in the hybrid routing protocols, namely, topological information, geographic information, and hierarchy information. Then, based on a review of the representative hybrid routing protocols, we summarize the three design options for hybrid routing protocols, namely, radius of the routing zone (1, k, or D), geographic information (position or position plus partition), and routing structure (flat or hierarchical). Finally, we propose a three-dimensional design framework that can accommodate well all of the existing hybrid routing protocols. The framework also helps find the unexplored design space, motivating the design of new hybrid routing protocols.     

一个基于整体优化分析的区域布线算法——DRAFT

本文提出一种新的基于整体优化分析的区域布线算法──DRAFT,它可以解决通道布线和四边布线问题。该算法分二个阶段完成区域详细布线:定向布线和最终布线。定向布线阶段给出各线网可行走线区间和最佳走线位置,其结果在最终布线阶段引导各线网的实际走线。布线在两层上进行,但不限制不同方向的走线必须走在不同层上。实验结果令人满意,对于大多数发表在文献中的通道布线和四边布线例子,DRAFT都得到了相当满意的解。     

多总线结构MHAL路由方法

在分析传统调制解调级硬件抽象层（Modem Hardware Abstract Layer,MHAL）路由方法局限性的基础上,提出了一种多总线结构MHAL路由方法,并详细介绍了该方法的设计实现及验证。基于多总线结构MHAL路由方法在不违反软件通信结构规范的前提下,解决了传统方法不能解决的处理器间多总线路由、处理器多端口路由以及数据包路由转发问题。该技术已在某大型软件无线电系统中得到应用。     

Full-Chip Scalable Routing Framework Considering Congestion and Performance

提出一个全新的全芯片可控布线系统框架,同时考虑布线拥挤度和芯片性能.为了在总体布线和详细布线之间架起桥梁,该框架把总体布线和详细布线集成起来,交互进行,每完成一个线网的布线,都及时对布线资源进行更新,由此可以得到精确的资源估计结果,有利于指导后续总体布线决策.该系统框架的主要特征包括快速的基于模式的和基于外框约束下最短路算法的总体布线器、基于迷宫算法的拥挤度驱动的详细布线器以及在两个布线器之间很好的交互性.在该布线系统框架中,为了优化电路性能,在布线中关键线网被赋予更高的优先级.同时,为了优化不同的布线目标,可以采用不同的线网排序策略.该布线系统框架在一套公用的测试电路上完成测试,并与之前提出的多级布线系统框架进行比较,实验结果表明,文中提出的布线系统框架在电路性能、布通率和运行时间方面都取得了很大改进.     

A survey and analysis of multipath routing protocols in wireless multimedia sensor networks

The main objective of this research is to conduct a performance analysis of various multipath routing protocols in wireless multimedia sensor networks for the efficient transmission of the image, audio and video data. To provide efficient routing for the large sized multimedia content, various multipath routing protocols such as energy-aware routing, QoS based routing and geographical routing methods are analyzed. In this analysis, the efficient routing techniques including geographical routing techniques such as GPSR, DGR, PW-DGR presented for wireless multimedia sensor networks are studied and the performance of each technique is evaluated to determine the efficient multipath routing technique. Comparisons are made for evaluated protocols and it is proved that the PW-DGR provides better routing performance for the multimedia data. The findings of the research also show that the PW-DGR method efficiently overcomes the routing problems such as energy bottleneck problem, energy-hole, reduced network lifetime and high delay in packet transmission.     

可信路由机理及关键技术

文章认为由于网络规模的增大以及节点移动、多宿主、网络流量工程等需求的不断增强,使得路由可扩展性、安全性、可靠性等问题凸显。尽管与可信路由相对应的理论技术方案不断提出,但未能从根本上解决网络路由的可信任问题。为此文章提出可信路由体系结构模型、可信域内路由、可信域间路由等新网络环境下的可信路由参考机制,并对可信路由涉及的关键技术,如映射可扩展技术、路由信任机制、多径路由技术、服务质量保证、路由监测管理技术,进行了研究和探讨。     

一种安全的Ad Hoc On-demand路由协议

由于Ad Hoc网络固有的弱点,设计安全、有效的Ad Hoc路由协议是困难的.本文从新的角度设计了一个简单、安全的On-demand路由协议.在路径请求和响应阶段,源节点和目的节点的身份分别被隐藏,只有那些位于目的节点选择的最优路径上的节点可以获得完整的路由信息,从而产生有效的前向和反向路径.同时,一个公开的单向Hash函数可以利用隐藏的路由信息构建单向Hash链用于路由信息的认证,从而不需要预先的共享密钥.在一次路由计算中,只有源节点和目的节点需要进行一次非对称密码运算.     

EPTR: expected path throughput based routing protocol for wireless mesh network

For effective routing in wireless mesh networks, we proposed a routing metric, expected path throughput (EPT), and a routing protocol, expected path throughput routing protocol (EPTR), to maximize the network throughput. The routing metric EPT is based on the estimated available bandwidth of the routing path, considering the link quality, the inter- and intra-flow interference and the path length. To calculate the EPT of a routing path, we first calculate the expected bandwidth of the link and the clique, and then consider the decay caused by the path length. Based on EPT, a distributed routing protocol EPTR is proposed, aiming to balance the network load and maximize the network throughput. Extensive simulations are conducted to evaluate the performance of the proposed solution. The results show that the proposed EPTR can effectively balance the network load, achieve high network throughput, and out-perform the existing routing protocols with the routing metrics previously proposed for wireless mesh networks.     

Routing Optimization in IP Networks Utilizing Additive and Concave Link Metrics

Routing optimization provides network operators with a powerful method for traffic engineering. Its general objective is to distribute traffic flows evenly across available network resources in order to avoid network congestion and quality of service degradation. In this paper we consider routing optimization based on conventional routing protocols where packets are forwarded hop-by-hop in a destination-based manner. Unlike other work in this area, we consider routing protocols, which are able to take into account concave routing metrics in addition to additive ones. The concave link metric introduces an additional degree of freedom for routing optimization, thus, increasing its optimization potential. We present and evaluate a mixed-integer programming model, which works on these metrics. This model unifies the optimization for single-metric and dual-metric routing concepts and also includes the consideration of multipath routing. Furthermore, we propose a heuristic algorithm usable for larger network instances. Numerical results indicate that employment of both the dual-metric concept and multipath routing can achieve considerably better utilization results than default-configured single-metric routing. A significant finding is that metric-based routing optimization with two link metrics often comes close to the results obtainable by optimization of arbitrarily configurable routing.     

基于非对称有向网络的拓扑抽象算法研究

网络规模的扩大导致了路由可扩展性的下降,因此未来的网络将向着分层多域的层次路由体系结构发展.在层次路由中,每个路由域通过拓扑抽象算法对内部拓扑进行汇聚并广播给外部节点,拓扑抽象算法将直接影响到网络的路由性能.本文提出了一种用于非对称有向网络的新型拓扑抽象算法——SHEF算法,该算法结合了面向源的拓扑抽象方法和最小生成树的概念,基于重边优先的准则对非对称的有向网络进行拓扑抽象和汇聚.仿真结果证明,该算法的权值偏差比传统方法减少了75%,较好地解决了路由信息复杂度和准确性之间的矛盾,具有良好的路由性能.     

An Energy-Efficient Routing Algorithm Based on Relative Identification and Direction for Wireless Sensor Networks

In studies of wireless sensor networks (WSNs), routing protocols in network layer is an important topic. To date, many routing algorithms of WSNs have been developed such as relative direction-based sensor routing (RDSR). The WSNs in such algorithm are divided into many sectors for routing. RDSR could simply reduce the number of routes as compared to the convention routing algorithm, but it has routing loop problem. In this paper, a less complex, more efficient routing algorithm named as relative identification and direction-based sensor routing (RIDSR) algorithm is proposed. RIDSR makes sensor nodes establish more reliable and energy-efficient routing path for data transmission. This algorithm not only solves the routing loop problem within the RDSR algorithm but also facilitates the direct selection of a shorter distance for routing by the sensor node. Furthermore, it saves energy and extends the lifetime of the sensor nodes. We also propose a new energy-efficient algorithm named as enhanced relative identification and direction-based sensor routing (ERIDSR) algorithm. ERISDR combines triangle routing algorithm with RIDSR. Triangle routing algorithm exploits a simple triangle rule to determine a sensor node that can save more energy while relaying data between the transmitter and the receiver. This algorithm could effectively economize the use of energy in near-sensor nodes to further extend the lifetime of the sensor nodes. Simulation results show that ERIDSR get better performance than RDSR, and RIDSR algorithms. In addition, ERIDSR algorithm could save the total energy in near-sensor nodes more effectively.     

考虑拥挤度和性能的全芯片可控布线系统框架

提出一个全新的全芯片可控布线系统框架,同时考虑布线拥挤度和芯片性能.为了在总体布线和详细布线之间架起桥梁,该框架把总体布线和详细布线集成起来,交互进行,每完成一个线网的布线,都及时对布线资源进行更新,由此可以得到精确的资源估计结果,有利于指导后续总体布线决策.该系统框架的主要特征包括快速的基于模式的和基于外框约束下最短路算法的总体布线器、基于迷宫算法的拥挤度驱动的详细布线器以及在两个布线器之间很好的交互性.在该布线系统框架中,为了优化电路性能,在布线中关键线网被赋予更高的优先级.同时,为了优化不同的布线目标,可以采用不同的线网排序策略.该布线系统框架在一套公用的测试电路上完成测试,并与之前提出的多级布线系统框架进行比较,实验结果表明,文中提出的布线系统框架在电路性能、布通率和运行时间方面都取得了很大改进.     

基于增强学习的协作主动路由信息交换机制

分组交换网是当今全球通信基础设施的重要部分，IP网络终将与其他网络相互融合，演化成为新一代网络技术，现有路由协议的实现是单一的，并且将数据库、最优路径计算和网络状态分发机制捆绑在一起。主动路由选择是一个把上述困难作为目标的新路由选择策略。主动路由选择机制被设计用来提供基于用户服务模式的路由选择。本文提出了一种基于增强学习的协作主动路由信息交换机制，主动路由代理获悉网络基础结构不同属性的当前状态，并在这个基础上建立和维护路由表，实现主动路由选择机制。     

基于形状的朝向目标布线算法

在传统布线算法的基础上,本文提出了一种无网格布线算法——基于形状的朝向目标线探索法.该布线算法主要针对障碍物外形尺寸多样,已布连线线宽及线间距离可变的布线情况,尤其适用于印刷电路板及集成电路的布线,该算法的基本要素是障碍物的包容矩形和带有预定终点的探索线,且所需存储空间小、布线速度快、布线路径短,具有良好的布线效果.     

Multihour engineering and traffic routing optimization in hierarchical telephone networks

Classical hierarchical routing in telephone networks is extended to a wider class called out-of-chain routing in such a way that some useful properties of hierarchical routing are retained. This new routing pattern offers more potential paths than the fixed hierarchical one and can be introduced as a dynamic routing where the fixed alternate sequences change at some predetermined instants during the day. The effect of this new routing pattern on the network performances is examined. The main topic of this paper is to present heuristic methods used to optimise such routings in large networks. We show on artificial networks that the throughput of a given network can be significantly improved by suitable routing choices. We demonstrate that the integration of routing changes within a multihour dimensioning process is possible but the lack of realistic data does not permit at this time to quantify the value of routing optimization on real networks.     

Oblivious Routing in Fat-Tree Based System Area Networks With Uncertain Traffic Demands

We study oblivious routing in fat-tree-based system area networks with deterministic routing under the assumption that the traffic demand is uncertain. The performance of a routing algorithm under uncertain traffic demands is characterized by the oblivious performance ratio that bounds the relative performance of the routing algorithm with respect to the optimal algorithm for any given traffic demand. We consider both single-path routing, where only one path is used to carry the traffic between each source-destination pair, and multipath routing, where multiple paths are allowed. For single-path routing, we derive lower bounds of the oblivious performance ratio for different fat-trees and develop routing schemes that achieve the optimal oblivious performance ratios for commonly used topologies. Our evaluation results indicate that the proposed oblivious routing schemes not only provide the optimal worst-case performance guarantees but also outperform existing schemes in average cases. For multipath routing, we show that it is possible to obtain an optimal scheme for all traffic demands (an oblivious performance ratio of 1). These results quantitatively demonstrate the performance difference between single-path routing and multipath routing in fat-trees.