移动自组网络N次空间重用的离散时间马氏链模型

移动自组网络(简称MANET)目前已经成为4G中的重要研究课题.本文在一个典型的随选型路由协议即动态源路由(DSR)协议的基础上,通过对信号强度进行分级来描述节点之间的相对距离,同时利用定向天线技术,建立了移动自组网络有空间重用的离散时间马氏链模型.通过计算平稳分布,进一步分析了节点相邻的概率和节点的平均邻居数两个基本的网络参数.并以定向天线发送信号的特性为基础,给出了一个具体实例,分析相应的参数.这对路由协议的评价和性能分析具有理论上的指导意义.     

Ad Hoc网络马氏模型路由维护的性能分析

Ad Hoc网络可以用许多数学模型来描述.本文以DSR协议为基础,把每条链边的长度看作是一个生灭过程,建立了马氏模型.在此模型中,我们考虑了空间可重用和请求分组带有跳限的情形.基于马氏模型,本文引入了链边Υ-时有效的概念,推导了链边有效的概率,得出了路由有效的条件概率和路由的平均恢复次数.     

基于CCN节点内容流行规律的缓存路由策略

针对内容中心网络(CCN)中缓存路由策略的缓存可用性差、路径外缓存难以有效利用的问题,提出了一种动态缓存通告及节点内容流行规律的缓存路由策略.依据不同节点内容流行度进行差异化动态缓存通告,利用缓存通告信息及节点内容流行规律依概率进行缓存决策,增加高流行度内容的缓存概率及临近缓存的差异性;基于缓存通告信息建立局部吸引势场,并结合内容源建立全网吸引势场,实现内容请求的就近响应.仿真结果表明,在保证存储开销和传输开销的前提下,本策略可有效降低平均请求时延,提高缓存命中率.     

网络结构、采纳者偏好与创新扩散:基于采纳者决策过程的创新扩散系统动力学模型仿真分析

在对采纳者决策过程分析的基础上,将网络结构和采纳者偏好作为核心参数,构建基于采纳者决策过程的创新扩散系统动力学模型。对模型进行仿真发现,在采纳者趋同化偏好条件下,网络平均度、网络重连概率与采纳者偏好强度的变动趋势与创新扩散效率的变动趋势相同,而在采纳者差异化偏好条件下则与创新扩散效率变动趋势相反。网络平均路径长度对创新扩散的影响方向与采纳者偏好特征无关,提高网络平均路径长度会始终降低创新扩散的效率。采纳者的趋同化偏好能够放大创新扩散对网络结构变量与采纳者偏好强度变量的敏感程度,采纳者差异化偏好则会缩小创新扩散对网络结构变量与采纳者偏好强度变量的敏感程度。研究结果对于制定创新推广策略具有一定的指导意义。     

基于韧性度的低轨卫星通信网络抗毁性度量及优化

低轨卫星通信网络的抗毁性是描述网络安全可靠的有效工具,在网络体系结构设计和路由策略等领域得到了广泛的应用。根据低轨卫星通信网络中卫星在轨道平面内移动,需要不断进行切换的特点,从建立抗毁性测度模型以及网络抗毁性优化两个角度来评估和提高网络抗毁性,提出一种基于韧性度的低轨卫星通信网络抗毁性度量方法。通过对移动模型以及切换模型的结构分析,对每种结构以一定概率出现的低轨卫星通信网络,应用韧性度函数,求得网络在某个时刻及某一段时间段内的抗毁性,并针对切换模型的不足之处进行优化,用赋权韧性度来体现优化的效果,得到了优化后的网络抗毁性。以铱星系统为应用实例进行仿真,结果表明:任意时刻网络的抗毁性跟拓扑结构的韧性度值有关,并且是一种线性关系,即随着韧性度的增加,其抗毁性也增加。通过对铱星通信系统切换模型的优化,网络的抗毁性与平均抗毁性都得到了提升,说明本文所构建模型的有效性和实用性。     

基于全局可达点的中国教育网平均最短路径近似算法

平均最短路径长度是复杂网络的一个重要特性,但由于计算时间的限制,求解大规模网络的平均最短路径长度很困难.以中国教育网数据为例,分析了中国教育网的拓扑结构,提出了全局可达点和局部可达点的概念,发现整个网络的平均最短路径长度由全局可达点决定.通过分析全局可达点的平均单源最短路径长度分布,发现整个网络的平均最短路径长度可由少数随机选取的点的平均最短路径长度来近似.通过三个网络验证了近似计算方法的有效性,并通过随机选取的数百个点,计算得到了含49041472个点的中国教育网的平均最短路径长度在14-15之间.     

求解最小Steiner树的蚁群优化算法及其收敛性

最小Steiner树问题是NP难问题,它在通信网络等许多实际问题中有着广泛的应用．蚁群优化算法是最近提出的求解复杂组合优化问题的启发式算法．本文以无线传感器网络中的核心问题之一,路由问题为例,给出了求解最小Steiner树的蚁群优化算法的框架．把算法的迭代过程看作是离散时间的马尔科夫过程,证明了在一定的条件下,该算法所产生的解能以任意接近于1的概率收敛到路由问题的最优解．     

具有相依结构离散时间模型破产概率的上界

研究两类具有相依结构的离散时间风险模型的破产概率问题.其中,索赔和利率过程假设为2个不同的自回归移动平均模型.利用更新递归技巧,首先得到了该模型下破产概率所满足的递归方程.然后,根据该递归方程得到了破产概率的上界估计.最后对两类风险模型的破产概率的上界进行了比较.     

度特征遗传的复杂网络竞争增长模型

复杂网络是一种介于规则网络和随机网络之间的网络模型,受生物进化的启发,结合无标度网络的优先连接特性,将进化过程中资源竞争和基因遗传引入到网络的增长过程中,提出一种新的增长模型.仿真实验发现,竞争增长网络模型度分布不再是幂律的,而是服从指数分布.完全遗传竞争增长网络则呈负偏态,且平均度与网络规模取对数后呈线性关系,从数学推导上也证明了这一关系.新模型具有优越的抗恶意攻击能力,且遗传系数越高这种能力越强.另外,网络的平均聚集系数随遗传系数增大而减小,平均路径长度随遗传系数增大而增大.整个模型是拓扑可调的,不同的参数组合可产生具有不同性质的网络模型.     

单自由度摩擦系统离散模型

发展了两种随机离散数学模型:导出了一个以二维平均映射描述的随机模型,并建立了一个概率预报模型.通过实例对不同模型进行了比较,对于平均映射模型,分岔图指出了外噪声对系统性质的影响,通过符号动力学方法分析指出概率预报模型的随机性质.     

Performance Analysis for Mobile Ad Hoc Network in Random Graph Models with Spatial Reuse

In this paper,we present a random graph model with spatial reuse for a mobile ad hoc network(MANET) based on the dynamic source routing protocol.Many important performance parameters of theMANET are obtained,such as the average flooding distance (AFD),the probability generating function of theflooding distance,and the probability of a flooding route to be symmetric.Compared with the random graphmodel without spatial reuse,this model is much more effective because it has a smaller value of AFD and alarger probability for finding a symmetric valid route.     

Jittering performance of random deflection routing in packet networks

This paper reports a study of random deflection routing protocol and its impact on delay-jitter over packet networks. In case of congestion, routers with a random deflection routing protocol can forward incoming packets to links laying off shortest paths; namely, packets can be “deflected” away from their original paths. However, random deflection routing may send packets to several different paths, thereby introducing packet re-ordering. This could affect the quality of receptions, it could also impair the overall performance in transporting data traffic. Nevertheless, the present study reveals that deflection routing could actually reduce delay-jitter when the traffic loading on the network is not heavy.     

Performance & packet traffic dynamics of Packet Switching Network model

Dynamics of packet traffic in data communication networks can be complex and often not well understood. Understanding of these complex dynamics is important for their control, prediction purposes and for the data networks design. The engineering community has described wired data networks architectures and studied them by means of a layered, hierarchical abstraction called ISO OSI (International Standard Organization Open System Interconnect) Reference Model. The Network Layer of the ISO OSI Reference Model is responsible for routing packets across the network from their sources to their destinations and for control of congestion in data networks. Using an abstraction of the Network Layer that we developed, we investigate packet traffic dynamics in our data network models of data communication networks of packet switching type, in particular near the phase transition point from free flow to congestion. We explore how these dynamics and network performance indicators are affected by network connection topology and routing algorithms. We consider static and adaptive routing algorithms. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Deterministic Routing With Bounded Buffers: Turning Offline Into Online Protocols

In this paper we present a deterministic protocol for routing arbitrary permutations in arbitrary networks. The protocol is analyzed in terms of the size of the network and the routing number of the network. Given a network H of n nodes, the routing number of H is defined as the maximum over all permutations on {1, ..., n} of the minimal number of steps to route offline in H. We show that for any network H of size n with routing number R our protocol needs time to route any permutation in H using only constant size edge buffers. This significantly improves all previously known results on deterministic routing. In particular, our result yields optimal deterministic routing protocols for arbitrary networks with diameter or bisection width , constant. Furthermore we can extend our result to deterministic compact routing. This yields, e.g., a deterministic routing protocol with runtime O(R logn) for arbitrary bounded degree networks if only O(logn) bits are available at each node for storing routing information. Our protocol is a combination of a generalized ``routing via simulation' technique with an new deterministic protocol for routing h-relations in an extended version of a multibutterfly network. This protocol improves upon all previous routing protocols known for variants of the multibutterfly network. The ``routing via simulation' technique used here extends a method previously introduced by the authors for designing compact routing protocols. Received July 18, 1997     

A meta-model for multiobjective routing in MPLS networks

MPLS (Multiprotocol Label Switching) enables the utilisation of explicit routes and other advanced routing mechanisms in multiservice packet networks, capable of dealing with multiple and heterogeneous QoS (Quality of Service) parameters. Firstly the paper presents a discussion of conceptual and methodological issues raised by multiobjective routing optimisation models for MPLS networks. The major contribution is the proposal of a multiobjective routing optimisation framework for MPLS networks. The major features of this modelling framework are: the formulation of a three-level hierarchical routing optimisation problem including network and service performance objectives, the inclusion of fairness objectives in the different levels of optimisation and a two-level stochastic representation of the traffic in the network (traffic flow and packet stream levels). A variant of the general model for two classes of traffic flows, QoS traffic and Best Effort traffic, is also presented. Finally a stochastic teletraffic modelling approach, underlying the optimisation model, is fully described. Work partially supported by programme POSI of the III EC programme cosponsored by FEDER and national funds.     

Loss circuit switched communication network-performance analysis and dynamic routing

We investigate a loss circuit switched communication network with state-dependent dynamic routing strategy, wherein the state of the network at the time of call arrival determines whether or not the call is accepted and, if accepted, its route. We develop an approximate approach to the network performance analysis. The approach enhances the Fixed Point Model by treating multiple solutions of the Fixed Point Equations. Assuming that the multiple solutions correspond to the long-living network modes, we develop the aggregated Markov chain that describes the network transitions among these modes. We also propose and discuss a new state-dependent dynamic routing strategy which we call Least-Expected-Blocking strategy (LEB). LEB accepts an incoming call only if this results in a decrease in the expected blocking probability and it chooses a route that yields the maximum decrease. The new strategy outperforms the previously known strategies by the criterion of network steady blocking probability.     

On the Hardness of Equal Shortest Path Routing

In telecommunication networks packets are carried from a source s to a destination t on a path that is determined by the underlying routing protocol. Most routing protocols belong to the class of shortest path routing protocols. In such protocols, the network operator assigns a length to each link. A packet going from s to t follows a shortest path according to these lengths. For better protection and efficiency, one wishes to use multiple (shortest) paths between two nodes. Therefore the routing protocol must determine how the traffic from s to t is distributed among the shortest paths. In the protocol called OSPF-ECMP (for Open Shortest Path First-Equal Cost Multiple Path) the traffic incoming at every node is uniformly balanced on all outgoing links that are on shortest paths. In that context, the operator task is to determine the “best” link lengths, toward a goal such as maximizing the network throughput for given link capacities.In this work, we show that the problem of maximizing even a single commodity flow for the OSPF-ECMP protocol cannot be approximated within any constant factor ratio. Besides this main theorem, we derive some positive results which include polynomial-time approximations and an exponential-time exact algorithm. We also prove that despite their weakness, our approximation and exact algorithms are, in a sense, the best possible.     

A packet filter placement problem with application to defense against spoofed denial of service attacks

We analyze a problem in computer network security, wherein packet filters are deployed to defend a network against spoofed denial of service attacks. Information on the Internet is transmitted by the exchange of IP packets, which must declare their origin and destination addresses. A route-based packet filter verifies whether the purported origin of a packet is correct with respect to the current route map. We examine the optimization problem of finding a minimum cardinality set of nodes to filter in the network such that no spoofed packet can reach its destination. We prove that this problem is NP-hard, and derive properties that explicitly relate the filter placement problem to the vertex cover problem. We identify topologies and routing policies for which a polynomial-time solution to the minimum filter placement problem exists, and prove that under certain routing conditions a greedy heuristic for the filter placement problem yields an optimal solution.     

A model for the capacitated,hop-constrained,per-packet wireless mesh network design problem

Three critical factors in wireless mesh network design are the number of hops between supply and demand points, the bandwidth capacity of the transport media, and the technique used to route packets within the network. Most previous research on network design has focused on the issue of hop constraints and/or bandwidth capacity in wired networks while assuming a per-flow routing scheme. However, networks that employ per-packet routing schemes in wireless networks involve different design issues that are unique to this type of problem. We present a methodology for designing wireless mesh networks that consider bandwidth capacity, hop constraints, and profitability for networks employing a per-packet routing system.     

Processor interconnection networks from Cayley graphs

Cayley graphs of groups are presently being considered by the computer science community as models of architectures for large scale parallel processor computers. In the first section of this paper we discuss Cayley graphs and show how they may be used as a tool for the design and analysis of network architectures for these types of computers.

Observing that routing on a Cayley graph is equivalent to a certain factoring problem in the associated group, we have been able to use a known powerful factoring technique in computational group theory to produce a fast efficient routing algorithm on the associated Cayley graph. In the second section of this paper we present this work. This research can be regarded as a first attempt to find general purpose routing algorithms for interconnection networks.

Believing that average diameter of a network for a large scale MIMD machine is the predominant factor in determining network performance, we designed Cayley graphs to be used in a special study performed at the Supercomputing Research Center (SRC). The importance of the average diameter in determining network performance was supported by the fact that the graphs found by us had the smallest average diameter and outperformed all other graphs evaluated in the study. In fact, before being driven into saturation, one of our graphs sustained 9.4% more network traffic than the next best candidate, a butterfly architecture, and 74.3% better than the bench mark 2-d mesh. The last section of our paper is devoted to this work.

This paper is divided into three sections. In the first section we discuss Cayley graphs and show how they may be used as a tool for the design and analysis of network architectures for parallel computers. In the second section we present our research on the routing problem. This research can be regarded as a first attempt to find general purpose routing algorithms for interconnection networks. In the last section we present some evidence that average diameter of a network for a large scale MIMD machine is the predominant factor in determining network performance.