AFDX协议性能分析及调度算法研究

本文围绕航空电子网络数据传输协议AFDX的关键技术--虚电路调度算法,进行了深入分析,提出了AFDX静态优先级队列调度算法AVLSP.运用Network Calculus理论与方法,对AVLSP算法进行理论证明,并构建仿真平台,对所提出的AVLSP调度算法进行仿真验证,结果证明AVLSP调度算法有效地减少了紧急数据的最大延迟抖动,较好地满足了航空电子网络数据传输的实时性要求.     

无线自组织网络中一种拥塞意识的多径路由算法

提出了无线自组织网络中一种拥塞意识的多径路由算法。该算法在路由发现过程中,综合节点的队列长度和路径跳数来动态确定路由请求消息的转发概率,可以在保证路由请求消息有一定送达率的条件下,降低路由开销;在路径选择和流量分配过程中,综合考虑节点的队列长度和路径质量作为路由度量,发现流量高吞吐量低拥塞路径,并基于该度量值进行流量分配。仿真结果显示,所提出的多径路由算法能有效提高网络性能。     

WSN中基于能量感知的最小跳数路由算法

无线传感器网络的拓扑往往由于节点死亡而发生变化。网络拓扑的重新构建加速了剩余传感器节点的死亡,缩短了网络的生存时间。针对无线传感器网络对网络生存时间的苛刻要求,提出了一种基于能量感知的最小跳数路由算法。建立路由时,该算法综合考虑了节点剩余能量和该节点潜在的转发能力。仿真结果显示,该算法在生存时间、存活节点数和吞吐量方面的性能要远优于LEACH算法和HEED算法。     

一类基于网络服务品质要求的单播路由算法

本文提出了一类基于网络服务品质QoS（quality of service）要求的单播路由算法。首先,我们给出了基于网络分组调度机制WFQ的延迟和带宽相耦合的分析模型,从而推导出了最佳端到端通信延迟的上界。基于该模型,我们改造了传统最小跳数和最短延迟的两类路由算法以支持实时通信的服务品质要求。此外,我们还给出了两种新的服务品质路由算法,它们是多路径第k条最短延迟路由算法以及组合带宽和跳数（hop counts）的最大能量路由算法。仿真实验结果表明,四种算法尤其是后两种算法在满足用户带宽、延迟服务要求以及增加网络资源使用效率和网络吞吐率等方面各有特色。     

最小化平均跳数的WDM网络逻辑拓扑优化算法

对波长路由光网络中的逻辑拓扑设计问题进行了探讨,并选择最小化平均分组跳数作为优化目标.理论分析表明:最小化平均分组跳数对于同时优化网络的拥塞率下限、拥塞概率、平均时延以及波长数下限具有一定的作用.以此为基础,结合最小跳数算法的局限性,提出一种改进的最小化平均分组跳数的启发式算法,并以NSFNET为仿真网络,比较了该算法与最短路径算法(分布式Bellman-Ford算法)、最小跳数算法(Minimum Hop)两种常用的基础算法在拓扑设计中的性能优劣.     

基于预期延迟值的扩散转发路由算法

针对现有延迟容忍网络路由算法在消息传递过程中分发不灵活的问题,提出基于节点通话历史记录计算预期通断时长以及消息传递延迟值,并根据结果选择节点、分配副本数进行消息转发的路由算法（MDESF）。在算法不同阶段,根据节点的活跃度选择中继节点,再分配传递消息的副本数目,加快分发,降低延迟。同时为保证消息及时传递,在单副本阶段选择最优节点转发。本算法同时提出内存管理策略,提高消息转发成功率。仿真实验表明,该算法相对其他同类算法在投递率、交付时延和网络拥塞比率方面综合表现更优。     

ADLE:一种Ad hoc网络分布式领导者选取算法

Ad hoc网络的动态拓扑结构和节点自组织给分布式算法的实现带来了诸多困难.Ad hoc网络分布式领导者选举算法:ADL.该算法基于广播机制,采用逻辑时戳保证消息的时序性,避免了节点饿死.同时,它通过缩小算法执行范围降低了消息复杂度,而且不需要节点了解系统中所有节点的信息,因而能够适应Ad hoc网络的动态拓扑结构和节点频繁出入.分析与仿真结果表明该算法具有较低的消息复杂度、小响应延迟和公平性.     

一种基于拓扑势的虚拟网络映射算法

该文针对现有的虚拟网络映射算法对网络中节点的拓扑属性考虑不够周到,导致其请求接受率和收益开销比较低的问题,将物理学里的场论思想引入了虚拟网络映射,并提出一种基于拓扑势的虚拟网络映射算法。该算法在节点映射阶段,通过计算节点的拓扑势、节点的资源能力、待映射节点与已映射节点之间的距离,将虚拟节点映射至最佳的物理节点。在链路映射阶段,通过计算物理路径的可用带宽和路径跳数,将虚拟链路映射至最佳的物理路径。仿真实验表明,该算法在多种虚拟网络到达强度下的请求接受率和收益开销比均优于当前的虚拟网络映射算法。     

面向卫星网络的流量工程路由算法

针对卫星网络链路长时延、拓扑时变等特征,将链路传输时延引入并基于MPLS网络中源-目的节点对已知这一先验知识,提出了一种面向卫星网络的MPLS流量工程路由算法。该算法基于卫星网络时变拓扑模型的卫星拓扑快照,定义链路初始权重为链路剩余带宽、传输时延的综合函数,在为当前节点对建路时考虑其余节点对将来建路的可能需求计算链路的关键度,在此基础上通过链路权重的动态调整及延期选用实现流量工程,从而优化卫星网络的链路利用。实验表明,此算法在请求拒绝数、吞吐量、平均跳数及平均时延等方面性能都有较理想的提升。     

基于名声、可用带宽和最小跳数的多量度自适应Ad hoc路由协议

通过对实际Ad hoc网络中节点通信情况的研究,考虑到网络中节点的自私性以及单纯使用最小跳数选路方法的缺陷,综合考虑名声、可用带宽和最小跳数,该文提出了一种新的参数量度。基于这个量度,借鉴TOPP(Trains Of Packet Pairs)测量可用带宽的思想,设计了一种快速测量逐跳可用带宽的方法,并通过MAC层和网络层的跨层设计,提出了一个基于以上混合量度的路由协议(Ad hoc Routing Based on Fame,Available Bandwidth and Minimum Hops, ARBFAM)。通过使用该协议在不同场景的网络环境中仿真证明,该路由协议在节点公平性,网络的拥塞控制和负载均衡,网络的平均寿命,网络的端到端吞吐量,平均端到端延迟方面较DSR都有较大的改善。     

Efficient Scheduling Algorithms for Real-Time Service on WDM Optical Networks

One of the important issues in the design of future generation high-speed networks is the provision of real-time services to different types of traffic with various time constraints. In this paper we study the problem of providing real-time service to hard and soft real-time messages in Wavelength-Division-Multiplexing (WDM) optical networks. We propose a set of scheduling algorithms which prioritize and manage message transmissions in single-hop WDM passive star networks based on specific message time constraints. In particular, we develop time-based priority schemes for scheduling message transmissions in order to increase the real-time performance of a WDM network topology. We formulated an analytical model and conducted extensive discrete-event simulations to evaluate the performance of the proposed algorithms. We compared their performances with that of the state-of-the-art WDM scheduling algorithms which typically do not consider the time constraint of the transmitted messages. This study suggests that when scheduling real-time messages in WDM networks, one has to consider not only the problem of resources allocation in the network but also the problem of sequencing messages based on their time constraints.     

实时WDM网络的全光流量疏导算法

为解决波分复用(Wavelength Division Multiplexing,WDM)网络中实时性业务流疏导问题,提出一种考虑了网络端对端延迟的疏导算法.建立了WDM网络模型和实时消息模型,用网络演算理论分析了有连续时隙和没有连续时隙分配下实时消息的端对端的最大延迟,并推导出了算法的延迟关键性参数时隙距离.提出的实...     

Providing deterministic quality-of-service guarantees on WDM optical networks

A major challenge in the design of future generation high-speed networks is the provision of guaranteed quality-of-service (QoS) for a wide variety of multimedia applications. In this paper we investigate the problem of providing QoS guarantees to real-time variable length messages (e.g., IP packets) in wavelength division multiplexing (WDM) optical networks. In particular, we propose a systematic mechanism comprised of admission control, traffic regulation, and message scheduling that provide guaranteed performance service for real-time application streams made up of variable-length messages. We formulate an analytical model based on the theory of max-plus algebra to evaluate the deterministic bounded message delay in a WDM network environment using our proposed QoS guarantee mechanism to determine the "schedulability conditions" of multimedia application streams, We also conduct a series of discrete-event and trace-driven simulations to verify the accuracy of the analytical model. The simulation results demonstrate that the analytic delay bound we obtained for our WDM optical network is valid and accurate.     

A cost-based scheduling algorithm for differentiated service on WDM optical networks

One of the important issues in the design of future generation of high-speed networks is to provide differentiated services to different types of traffic with various time constraints. We propose an adaptive scheme to manage message transmission in single-hop passive-star coupler based wavelength-division multiplexing (WDM) optical networks. This study suggests that when scheduling message transmission in WDM networks a differentiated service should be considered in order to meet the time constraint to transmission of real-time messages while non real-time messages are being served so that the overall performance of the network could be improved.     

Robust Design of Virtual Topology for WDM Networks under Bandwidth Demand Uncertainties

In this paper, a novel method is proposed to address the problem of designing virtual topology over wavelength division multiplexing （WDM） networks under bandwidth demand uncertainties. And a bandwidth demand model under uncertainties is presented. The optimization goal of virtual topology design is defined as minimizing the maximum value amongp percentiles of the bandwidth demand distribution on all Hght-paths. Correspondingly, we propose a heuristic algorithm called an improved decreasing multi-hop logical topology design algorithm （ID-MLTDA） that involves with a degree of uncertainties to design virtual topology. The proposed algorithm yields better performance than previous algorithms. Additionally, the simplicity and efficiency of the proposed algorithm can be in favor of the feasibility for topology design of large networks.     

Delivery time analysis of a low Earth orbit satellite network forseamless PCS

The message delivery time on a low Earth orbit (LEG) satellite network is analyzed. The LEO network is assumed to be seamless and virtual cut-through switching is proposed for use. Equations to calculate the message delivery time and the probability of a message being delivered successfully using no more than a time delay bound for LEO networks, varying in size and connectivity, are derived. The message delivery times of different LEO networks, varying in network connectivity, are compared. Numerical examples show that with the probability of successful delivery =0.99 and the probability of cut-through =0.5, an 8×8 LEO network with six crosslinks per node can deliver messages 40% faster than with four crosslinks per node for communicating satellites, separated by D hops, where D is the network diameter     

A novel robust routing algorithm for multi-granularity connection requests in wavelength division multiplexing mesh networks

In this paper, we propose a novel robust routing algorithm based on Valiant load-balancing under the model of polyhedral uncertainty (i.e., hose uncertainty model) for WDM (wavelength division multiplexing) mesh networks. Valiant load-balanced robust routing algorithm constructs the stable virtual topology on which any traffic patterns under the hose uncertainty model can be efficiently routed. Considering there are multi-granularity connection requests in WDM mesh networks, we propose the method called hose-model separation to solve the problem for the proposed algorithm. Our goal is to minimize total network cost when constructing the stable virtual topology that assures robust routing for the hose model in WDM mesh networks. A mathematical formulation (integer linear programming, ILP) about Valiant load-balanced robust routing algorithm is presented. Two fast heuristic approaches are also proposed and evaluated. We compare the network throughput of the virtual topology constructed by the proposed algorithm with that of the traditional traffic grooming algorithm under the same total network cost by computer simulation.     

弹性光网络中基于安全性感知的差异化虚拟光网络的映射策略

针对虚拟环境下底层网络中光纤的概率性故障,传统的100%保护至少需要配置一条保护路径,造成资源冗余度高和虚拟网络请求接受率低的问题,该文提出一种基于安全性感知的差异化虚拟光网络的映射(SA-DVNM)策略,在链路发生故障时为差异化虚拟网络请求提供安全保证。在SA-DVNM策略中,设计了一个综合考虑物理节点对之间跳数和相邻带宽大小的节点权重式避免链路映射过长,并提出路径频谱资源使用均衡的链路映射机制,最小化瓶颈链路的数量。当单路径传输失败时,SA-DVNM策略设计允许路径分割的资源分配机制,为保障时延敏感业务的安全性,SA-DVNM策略在路由选择中设计了基于时延差优化的多路径路由频谱分配方法。仿真结果表明该文所提策略在概率故障环境中能够降低带宽阻塞率,提高频谱资源利用率和虚拟光网络接受率。