Design and performance analysis of an inductive QoS routing algorithm

Routing mechanism is key to the success of large-scale, distributed communication and heterogeneous networks. Consequently, computing constrained shortest paths is fundamental to some important network functions such as QoS routing and traffic engineering. The problem of QoS routing with multiple additive constraints is known to be NP-complete but researchers have been designing heuristics and approximation algorithms for multi-constrained paths algorithms to propose pseudo-polynomial time algorithms. This paper introduces a polynomial time approximation quality of service (QoS) routing algorithm and constructs dynamic state-dependent routing policies. The proposed algorithm uses an inductive approach based on trial/error paradigm combined with swarm adaptive approaches to optimize lexicographically various QoS criteria. The originality of our approach is based on the fact that our system is capable to take into account the dynamics of the network where no model of the network dynamics is assumed initially. Our approach samples, estimates, and builds the model of pertinent aspects of the environment which is very important in heterogeneous networks. The algorithm uses a model that combines both a stochastic planned pre-navigation for the exploration phase and a deterministic approach for the backward phase. Multiple paths are searched in parallel to find the K best qualified ones. To improve the overall network performance, a load adaptive balancing policy is defined and depends on a dynamic traffic path probability distribution function. We conducted a performance analysis of the proposed QoS routing algorithm using OPNET based on a platform simulated network. The obtained results demonstrate substantial performance improvements as well as the benefits of learning approaches over networks with dynamically changing traffic.     

Measurement and performance of a cognitive packet network

As the size of the Internet grows by orders of magnitude both in terms of users, number of IP addresses, and number of routers, and as the links we use (be they wired, optical or wireless) continuously evolve and provide varying reliability and quality of service, the IP based network architecture that we know so well will have to evolve and change. Both scalability and QoS have become key issues. We are currently conducting a research project that revisits the IP routing architecture issues and proposes new designs for routers. As part of this effort, this paper discusses a packet network architecture called a cognitive packet network (CPN), in which intelligent capabilities for routing and flow control are moved towards the packets, rather than being concentrated in the nodes. In this paper we outline the design of the CPN architecture, and discuss the quality-of-service based routing algorithm that we have designed and implemented. We then present our test-bed and report on extensive measurement experiments that we have conducted.     

Energy-aware routing in the Cognitive Packet Network

An energy aware routing protocol (EARP) is proposed to minimise a performance metric that combines the total consumed power in the network and the QoS that is specified for the flows. The algorithm uses source routing based on the functionalities provided by the Cognitive Packet Network (CPN), running autonomously at each input node to the network based on smart packets which gather relevant information throughout the network using reinforcement learning at each of the intermediate nodes. Measurements on an experimental test-bed that uses EARP are presented and they indicate that it offers a reduction in power consumption, as compared to a purely QoS driven approach, and also respects the requested QoS level.     

Edge-limited scalable QoS flow set-up

Although the Differentiated Services architecture supports scalable packet forwarding based on aggregate flows, the detailed procedure of Quality of Service (QoS) flow set-up within this architecture has not been well established. In this paper we explore the possibility of a scalable QoS flow set-up using a sink-tree paradigm. The paradigm initially constructs a sink tree at each egress edge router using network topology and bandwidth information provided by a QoS extended version of Open Shortest Path First (OSPF), which is a widely used link-state routing protocol. Our sink-tree paradigm dynamically reallocates network bandwidths online according to traffic demands. As a consequence, our paradigm easily supports QoS routing, resource allocation, and admission control at ingress edge routers without consulting core routers in a way that the QoS flow set-up time and overhead are minimized. Simulation results are very encouraging in that the proposed methodology requires significantly less communication overhead in setting up QoS flows compared to the traditional per-flow signaling-based methodology while still maintaining high resource utilization.     

Providing QoS in OSPF based best effort network using load sensitive routing

In an open shortest path first (OSPF) based best effort network, when a packet experiences congestion, the routing subsystem cannot send it through an alternate path. Thus, it fails to provide desired quality of service (QoS) during congestion. In order to provide QoS we have reported three different load sensitive routing (LSR) protocols in [A. Sahoo, An OSPF based load-sensitive QoS routing algorithm using alternate paths, in: IEEE International Conference on Computer Communication Networks, October 2002; A. Tiwari, A. Sahoo, Providing QoS support in OSPF based best effort network, in: IEEE International Conference on Networks, November 2005; A. Tiwari, A. Sahoo, A local coefficient based load sensitive routing protocol for providing QoS, in: IEEE International Conference on Parallel and Distributed Systems, July 2006]. The LSR protocol forwards packets through alternate paths in case of congestion. The number of alternate paths at any node depends on the value of operating parameter or coefficient used for alternate path calculation. Though the basic protocol in these cases was the same, the methods of choosing operating parameter were different. We referred to these three methods as LSR [A. Sahoo, An OSPF based load-sensitive QoS routing algorithm using alternate paths, in: IEEE International Conference on Computer Communication Networks, October 2002], E-LSR [A. Tiwari, A. Sahoo, Providing QoS support in OSPF based best effort network, in: IEEE International Conference on Networks, November 2005] and L-LSR [A. Tiwari, A. Sahoo, A local coefficient based load sensitive routing protocol for providing QoS, in: IEEE International Conference on Parallel and Distributed Systems, July 2006] coefficient methods. In this paper, we present the LSR protocol along with the three coefficient calculation methods pointing out the reason for going from one method to the next. The main strength of our LSR protocol is that it provides loop free alternate paths in the event of congestion and can interwork with routers running vanilla OSPF protocol. We show through simulation that the LSR protocol based on any of the three different coefficient calculation methods performs much better than OSPF and that out of the three methods proposed by us, L-LSR performs the best.     

基于软件定义的WSNs非均匀分簇QoS路由算法

针对传统无线传感器网络非均匀分簇QoS路由中节点资源受限,无法动态管理等问题,提出一种基于软件定义的无线传感器网络非均匀分簇QoS路由算法(SDNUCQS)。控制器考虑节点能量、节点间距离和QoS指标,采用熵权法竞选出高质量簇头,并对网络进行非均匀分簇。利用交叉分类法将所要传输的数据通过时延和丢失率分成不同类型。在簇间路由中,控制器以链路QoS指标和节点负载度为参数,采用集中式方式分别计算QoS数据和普通数据传输的最佳路径。仿真实验结果表明,SDNUCQS算法能显著降低网络时延和丢失率,与LEACH、EEUC、CRIPSO和tPSOEB算法比较,能降低簇头能耗且延长了网络生命周期。     

RIDSI:一种融合SDN和兴趣域划分的ICN路由机制

信息中心网络(Information-Centric Networking,ICN)中的服务质量(Quality of Service,QoS)路由是分布式的,无法感知其它路由器缓存的内容,因此,基于软件定义网络(Software Defined Networking,SDN)的全局视图和集中控制功能,本文提出了一种基于兴趣域划分的ICN路由机制.这种机制旨在减轻内容节点的负载、提高路由成功率和提高PIT命中率.首先,本文提出了基于SDN的ICN网络模型,即软件定义信息中心型网络(Software Defined Information Centric Networking,SD-ICN)模型和QoS评价模型.然后,采用蜂群算法将网络中的路由器划分到不同的兴趣域.最后,基于改进的QoS依赖多播路由(QoS Dependent M ulticast Routing,QDM R)算法计算满足多个兴趣请求的转发路径.仿真实验结果表明,本文提出的路由机制与对比机制相比在路由成功率、平均路由延迟、负载均衡度等方面都具有较好的性能.     

Binary and m-ary encoding in applications of tree-based genetic algorithms for QoS routing

Ubiquitous and Pervasive Computing (UPC) applications often have Quality of Service (QoS) requirements. These become constraints for the UPC network infrastructure. In this paper, we refer to Mobile ad Hoc Networks, one of the most important technologies supporting UPC, and investigate on Genetic Algorithms (GAs) for QoS routing. GAs are part of the soft computing paradigm and can solve the NP search of QoS routes with multiple constraints. We elaborate on tree-based GAs, which represent the set of paths from source to destination as a tree and encode them through the crossed junctions. While their most well-known applications use m-ary encoding representing single paths in the chromosomes, in this paper we discuss a binary encoding with the objective of improving the convergence speed. The binary encoding represents classes of paths in the chromosomes and allows local search on classes of paths. These classes are both collectively exhaustive and mutually exclusive. Simulation results compare convergence speed and scalability of GA applications with binary and m-ary encoding in networks with an increasing number of nodes and links per node. As the per-class processing is reason of additional computational cost, an hybrid GA application that uses both binary and m-ary encoding is introduced.     

Performance evaluation of the Cognitive Packet Network in the presence of network worms

Reliable networks that provide good service quality are expected to become more crucial in every aspect of communication, especially as the information transferred between network users gets more complex and demanding and as malicious users try to deliberately degrade or altogether deny legitimate network service. The Cognitive Packet Network (CPN) routing protocol provides Quality of Service (QoS) driven routing and performs self-improvement in a distributed manner, by learning from the experience of special packets, which gather on-line QoS measurements and discover new routes. Although CPN is generally very resilient to network changes, it may suffer worse performance during node failures caused by network threats, such as network worms. Here we evaluate the performance of CPN in such crises and compare it with the Open Shortest Path First (OSPF) routing protocol, an industry standard and widely used in Internet Protocol networks. We also improve it by introducing a failure detection element that reduces packet loss and delay during failures. Our experiments were performed in a real networking testbed.     

Agent system for inter-AS routing error diagnosis

The basic unit of Internet routing is called an autonomous system, or AS, defined as a set of routers under a single technical administration. The Internet currently comprises more than 12,000 AS's. Some are university or corporate networks; others are ISP networks. Inside an AS, a single authority controls the deployment of policies and protocols by which routers compute intra-AS paths, including paths to gateway or border routers. For inter-AS routing, the situation is more complicated. Most AS's manage the exchange of routing information through the Internet Engineering Task Force's border gateway protocol. BGP lets an AS advertise "reachability" information throughout the Internet by sending update information when network topology or routing policies change. BGP is a hop-by-hop protocol, which sends the information only to a gateway router's immediate neighbors. At NTT Network Innovation Laboratories, we have developed and are currently testing a multiagent-based system called Encore to automatically diagnose inter-AS routing problems. We briefly describe the problem addressed by the system, its design and current implementation, and recent test results