Kademlia based routing on locator-ID separated networks for new generation networks

We propose an efficient ID-based routing method using Kademlia on Locator-ID separated networks for New Generation Networks. Due to the increase in Internet traffic, many people pointed out problems of the Internet. Therefore, studies on New Generation Networks by clean-slate approach are hot topics. New Generation Network discussions include locator-ID separation for resolving the problems of routing tables and mobility support. IETF and IRTF proposed some protocols for Locator-ID separation, but they have problems in Name servers for Locator-ID mapping resolutions. Therefore, we propose a method for communicating specified ID hosts using hierarchical Kademlia without resolving Locator-ID mapping explicitly. Our method does not need Name servers of Locator-ID mappings. We can also support host mobility by updating Kademlia links, and hierarchical Kademlia achieves efficient routings considering physical distances. We discuss the communication delay and size of routing tables of our proposed method, and also show the effectiveness of hierarchical Kademlia through simulation experiments.     

互联网路由寻址架构的扩展及其解决方案的研究

单一的地址空间、多宿主和流量工程造成了DFZ中的路由表的规模迅速增长。为了解决这一问题,IETF提议通过分离终端系统标志和路由标志的地址空间来重新考虑互联网的寻址体系结构。论述了最近提出的几个地址空间分离的方案,并对这些方案所带来的优势和缺点进行了比较和总结;最后,探讨了互联网路由寻址体系结构研究中需要进一步考虑的问题。     

Integrating reliability and quality of service in networks with switched virtual circuits

In this paper, we present an optimization model based on cost minimization for traffic engineering of multirate and ATM networks with switched virtual circuits (SVCs). There is an increasing interest for efficient traffic engineering methods for routing and dimensioning of large and robust multiservice networks. In the case of ATM and other types of packet multiservice networks, traffic engineering requires resource allocation and performance optimization at the cell or packet level in order to assure a satisfactory grade of service (GoS) at the call level to the users. Therefore, we are interested in networks with switched connections that are flexible enough so that planners may offer cost-effective networks with guaranteed GoS even in the event of important failures. The model integrates the notions of QoS, GoS, failures and failure propagation between the physical and the logical level as well as circuit routing.     

AMRST: adaptive multicast routing protocol for satellite–terrestrial networks

Multicasting facilitates the distributing of multimedia information to an entire set of destinations simultaneously. However, the subsequent mass of Internet traffic usually increases the network congestion and degrades network utilization. The unexpected congestion together with limited network capacity might challenge the provision of multimedia services especially since multicast subscribers are widely scattered. The desired QoS of the ongoing services cannot be guaranteed. To address this challenge, in addition to installing new terrestrial broadband networks, another feasible solution would be to integrate now available broadcasting-oriented broadband satellite networks into the Internet backbone. This paper presents a novel adaptive multicast routing (AMRST) protocol to deliver reliable and adaptive multicast services to global subscribers, based on an integrated infrastructure, called a satellite–terrestrial network (ST network), which provides dynamic bandwidth allocation, flexible resource management and ubiquitous transmission. In the AMRST, a proposed virtual hierarchical routing tree was applied in constructing an efficient multicast tree. A routing decision model was proposed to determine routing path for the member requests. A “hierarchical membership maintenance” approach was designed to maintain the multicast membership. The scalability of the AMRST was further addressed. The AMRST not only kept the benefits of the traditional terrestrial multicast but also promoted the multicasting performance by employing the satellite broadcasting capability. The simulation results demonstrate that the AMRST performed excellently for the ST network.     

Modeling and analyzing the performance of adaptive hierarchical networks

As networks become larger, scalability and QoS-awareness become important issues that have to be resolved. A large network can be effectively formed as a hierarchical structure, such as the inter/intra-domain routing hierarchy in the Internet and the Private Network-to-Network Interface (PNNI) standard, to resolve these critical issues. Methods of modeling and analyzing the performance of QoS-capable hierarchical networks become an open issue. Although the reduced load approximation technique has been extensively applied to flat networks, the feasibility of applying it to the hierarchical network model has seldom been investigated. Furthermore, most of the research in this area has focused on the performance evaluation with fixed routing. This work proposes an analytical model for evaluating the performance of adaptive hierarchical networks with multiple classes of traffic. We first study the reduced load approximation model for multirate loss networks, and then propose a novel performance evaluation model for networks with hierarchical routing. This model is based on a decomposition of a hierarchical route into several analytic hierarchical segments; therefore the blocking probability of the hierarchical path can be determined from the blocking probabilities of these segments. Numerical results demonstrate that the proposed model for adaptive hierarchical routing yields accurate blocking probabilities. We also investigate the convergence of the analysis model in both the originating-destination (O-D) pair and the alternative hierarchical path. Finally, the blocking probability of the adaptive hierarchical O-D pair is demonstrated to depend on the blocking of all hierarchical paths but not on the order of the hierarchical path of the same O-D pair.     

Monitoring Edge-to-Edge Traffic Aggregates in Differentiated Services Networks

Differentiated Services (DiffServ), which are currently being standardized in the IETF DiffServ working group, is a solution that can provide different qualities of service to different network users. DiffServ aggregates network packets at edge routers and forwards the aggregated packets to core routers with different priorities. In this paper, we propose methods using the SNMP framework for monitoring edge-to-edge traffic aggregates in a DiffServ domain, which consists of a set of DiffServ-enabled routers. In order to manage each DiffServ router, we have analyzed the DiffServ MIB and instrumented it in the router. Further, we propose monitoring behaviors of edge-to-edge traffic aggregates by combining topology and performance information from MIB II and DiffServ MIB. Construction procedures and graphical representation of the edge-to-edge traffic aggregates are explained in detail. We also extend our efforts to implement a DiffServ domain monitoring system that monitors a set of DiffServ-enabled routers and traffic aggregates between every edge router pair. We believe that the proposed monitoring methods can serve as useful building blocks for managing DiffServ networks.     

Trade-Offs between Stretch Factor and Load-Balancing Ratio in Routing on Growth-Restricted Graphs

An unweighted graph has density rho and growth rate k if the number of nodes in every ball with radius r is bounded by rhor^k. The communication graphs of wireless networks and peer-to-peer networks often have constant bounded density and small growth rate. In this paper, we study the trade-off between two quality measures for routing in growth-restricted graphs. The two measures we consider are the stretch factor, which measures the lengths of the routing paths, and the load-balancing ratio, which measures the evenness of the traffic distribution. We show that if the routing algorithm is required to use paths with stretch factor c, then its load-balancing ratio is bounded by O(rho^1/k(n/c)^1-1/k), and the bound is tight in the worst case. We show the application and extension of the trade-off to the wireless network routing and VLSI layout design. We also present a load-balanced routing algorithm with the stretch factor constraint in an online setting, in which the routing requests come one by one.     

一种区分服务网络的设计与实现

给出了DiffServ网络的一种设计与实现，提出了一种有效的资源管理模型。在该模型中，存在一个带宽代理(Bandwidth Broker)同步多个边界节点的接纳控制，负责区分服务网络之间的SLA(Server Level Agreement)协商，进行路由器配置；边界节点使用RSVP协议为集聚流预留资源；RSVP使用预计算QoS路由寻找路径。整个模型不仅综合了已有资源管理方案的优点，而且保持了区分服务网络的可扩展性。     

位置与标识分离的命名和寻址体系结构研究综述

随着互联网的发展,传统TCP/IP网络体系结构的IP地址语义过载问题所导致的移动性、扩展性和安全性等方面的缺陷逐渐暴露出来,并限制了多宿主、流量工程等新技术的发展.针对这一问题,学术界普遍认为需要对下一代互联网的命名和寻址体系结构进行重新设计,将位置与标识分离作为新一代互联网的基本设计原则之一.近年来,涌现了许多基于位置与标识分离的新技术和解决方案.首先对基于位置与标识分离的网络体系结构研究所面临的关键性问题进行了分析;然后对相关研究工作进行了回顾,并对相关代表性研究成果进行了深入评述;最后展望了未来的一些研究方向.     

Routing performance enhancement in hierarchical torus network by link-selection algorithm

A hierarchical torus network (HTN) is a 2D-torus network of multiple basic modules, in which the basic modules are 3D-torus networks that are hierarchically interconnected for higher-level networks. The static network performance of the HTN and its dynamic communication performance using the popular dimension-order routing algorithm have already been evaluated and shown to be superior to the performance of other conventional and hierarchical interconnection networks. In this paper, we propose a link-selection algorithm for efficient use of physical links of the HTN, while keeping the link-selection algorithm as simple as the dimension-order routing algorithm. We also prove that the proposed algorithm for the HTN is deadlock-free using three virtual channels. We evaluate the dynamic communication performance of an HTN using dimension-order routing and link-selection algorithms under various traffic patterns. We find that the dynamic communication performance of an HTN using the link-selection algorithm is better than when the dimension-order routing algorithm is used.     

一种基于MPLS流量工程的QoS保证路由算法

随着因特网流量的快速增加和对服务质量要求的不断提高,基于MPLS流量工程的QoS路由算法成为业界研究的重点。文章介绍了MPLS流量工程的工作机制和原理,在传统的Dijkstra算法的基础之上,提出了一种新颖的基于遗传优化的QoS保证的路由选择算法,同时配置一批LSP,并克服了一条一条配置时的先占先优的“顶端优势”。最后的仿真实验说明了算法在优化网络资源、平衡网络负载中是有效的和实用的。     

Internet路由仿真系统研究与实现

随着Internet不断的发展扩大,如何测量路由协议实现在实际网络环境中的运行特性成为一个重要难题.针对这个问题,设计实现了Internet路由仿真系统IRES(Internet routing emulation system),为这种特性的测试和评价提供了试验床.首先提出了一种将Internet拓扑生成和路由协议实现相结合的思想,并基于此给出了IRES的总体结构.接着研究了将GT-ITM网络拓扑模型转换到面向BGP-OSPF的Internet拓扑结构的方法.最后给出了IRES的应用实例,通过与CISCO2600路由器的路由交互,分析得到了被测系统OSPF协议实现的复杂度为O((lgN)⁴),并给出了其所支持的网络规模上限.实验证明,IRES系统作为试验床,具有其他测试系统不可取代的重要作用.     

A game–theoretic analysis of the implications of overlay network traffic on ISP peering

Inter-ISP traffic flow determines the settlement between ISPs and affects the perceived performance of ISP services. In today’s Internet, the inter-ISP traffic flow patterns are controlled not only by ISPs’ policy-based routing configuration and traffic engineering, but also by application layer routing. The goal of this paper is to study the economic implications of this shift in Internet traffic control assuming rational ISPs and subscribers. For this purpose, we build a general traffic model that predicts traffic patterns based on subscriber distribution and abstract traffic controls such as caching functions and performance sensitivity functions. We also build a game–theoretic model of subscribers picking ISPs, and ISPs making provisioning and peering decisions. In particular, we apply this to a local market where two ISPs compete for market share of subscribers under two traffic patterns: “Web” and “P2P overlay”, that typifies the transition the current Internet is going through. Our methodology can be used to quantitatively demonstrate that (1) while economy of scale is the predominant property of the competitive ISP market, P2P traffic may introduce unfair distribution of peering benefit (i.e. free-riding); (2) the large ISP can restore more fairness by reducing its private capacity (bandwidth throttling), which has the drawback of hurting business growth; and (3) ISPs can reduce the level of peering (e.g. by reducing peering bandwidth) to restore more fairness, but this has the side-effect of also reducing the ISPs’ collective bargaining power towards subscribers.     

Traffic Engineering of Management Flows by Link Augmentations on Confluent Trees

Service providers rely on the management systems housed in their Network Operations Centers (NOCs) to remotely operate, monitor and provision their data networks. Lately there has been a tremendous increase in management traffic due to the growing complexity and size of the data networks and the services provisioned on them. Traffic engineering for management flows is essential for the smooth functioning of these networks to avoid congestion, which can result in loss of critical data such as billing records, network alarms, etc. As is the case with most intra-domain routing protocols, the management flows in many of these networks are routed on shortest paths connecting the NOC with the service provider’s POPs (points of presence). This collection of paths thus forms a “confluent” tree rooted at the gateway router connected to the NOC. The links close to the gateway router may form a bottleneck in this tree resulting in congestion. Typically this congestion is alleviated by adding layer two tunnels (virtual links) that offload the traffic from some links of this tree by routing it directly to the gateway router. The traffic engineering problem is then to minimize the number of virtual links needed for alleviating congestion. In this paper we formulate a traffic engineering problem motivated by the above mentioned applications. We show that the general versions of this problem are hard to solve. However, for some simpler cases in which the underlying network is a tree, we design efficient algorithms. In particular, we design fully polynomial-time approximate schemes (FPTAS) for different variants of this problem on trees. We use these algorithms as the basis for designing efficient heuristics for alleviating congestion in general (non-tree) service provider network topologies.     

一种基于OLSR的新型层次路由算法*

提出了一种新型的基于OLSR的层次化改进算法HOLSR,旨在提高OLSR的整体效率。该算法通过分层设置洪泛范围和灵活调整各层拓扑控制分组的更新周期,降低路由执行开销;同时采用差值路由补偿技术提高数据分组的传输效率。仿真实验结果表明：HOLSR与OLSR路由算法相比,数据分组成功传输率高,端到端延迟小,路由协议开销少;与DSR、AODV、DSDV等典型路由算法相比,在不同节点移动速度和不同通信负载下,综合性能也有优势,尤其在通信负载较大时（880 kbps）,优势更加明显。     

Qualitative analysis of mapping systems in the Internet architectures based on identifier/locator separation

The current Internet has several known challenges, such as routing scalability, mobility, multihoming, traffic engineering, etc. due to the overloaded semantics of IP address, i.e. it is used as a node identifier (ID) and a node locator (LOC). Thus, the research community has redesigned the Internet architecture based on ID/LOC separation to overcome the limitations of the current Internet. In all Internet architectures based on ID/LOC separation, ID to LOC mapping system is necessarily required to bind ID and its LOC, since ID is no longer dependent to its LOC logically or physically. Thus, how to design the mapping system is a key challenge in ID/LOC separation architecture. In this paper, we analyse qualitatively the mapping systems proposed in ID/LOC separation architectures to provide insights into designing a new mapping system. The main contribution in this paper is that we categorise ID to LOC mapping systems according to the mapping server structure and provide the pros and cons of the mapping systems belonging to each category. Based on our qualitative analysis, we also examine intuitively if the mapping systems in each category satisfy their requirements.     

Link weight assignment and loop-free routing table update for link state routing protocols in energy-aware internet

In order to lessen the greenhouse effects and diminish environmental pollution, reducing energy usage is important in designing next generation networks. Shutting down the network devices that carry light load and redirecting their traffic flows to other routes is the most common way to reduce network energy consumption. Since traffic demands among node pairs vary in different time periods, an energy efficient network has to dynamically determine the optimal active links to adapt itself to network traffic changes. However, in current IP networks, shutting down and/or turning on links would trigger link state routing protocols to reconverge to a new topology. Since the convergence time would take tens of seconds, routing table inconsistencies among routers would result in network disconnection and even worse, generating traffic loops during the convergence interval. Removing routing images inconsistent among routers to prevent loops is a critical issue in energy efficient network and this issue is still not considered in the green network design yet. The contribution of the paper is presented in two parts. First, we propose a comprehensive approach to determine a network topology and a link metric for each time period. Traffic engineering is considered in our design such that flows going on the energy-aware network are within a predetermined percentage of the link capacity such that no congestion occurs in a statistical manner. Second, to avoid transient loops during time period changes, we propose a Distributed Loop-free Routing Update (DLRU) scheme to determine the correct sequence for updating the routing table. A scrupulous proof was also presented to ensure the loop-free property of the DLRU. In this paper, we formulate an integer linear programming to determine this multi-topology and link weight assignment problem. Due to its NP-hard property, we propose an efficient algorithm, termed Lagrangian Relaxation and Harmonic Series (LR&HS) heuristic. Numerical results demonstrate that the proposed LRHS approach outperforms the other approaches on several benchmark networks and random networks by providing up to 35%-50% additional energy saving in our experimental cases.     

CoreCast: How core/edge separation can help improving inter-domain live streaming

The rapid growth of broadband access has popularized multimedia services, which nowadays contribute to a large part of Internet traffic. Among this content, the broadcasting of live events requires streaming from a single source to a large set of users. For such content, network-layer multicast is the most efficient solution, but it has not found wide-spread adoption due to its high deployment cost. As a result, several application-layer solutions have been proposed based on large-scale P2P systems. These solutions however, are unable to provide a satisfactory quality of experience to all users, mainly because of the variability of the peers and their limited upload capacity. In this paper we advocate for a network-layer solution that circumvents the prohibitive deployment costs of previous approaches, taking advantage of the rare window of opportunity offered by the locator/identifier separation protocol (LISP). This new architecture, motivated by the alarming growth rate of the default-free zone (DFZ) routing table, is developed within the IETF, and aims to upgrade the current inter-domain routing system. We present CoreCast, an efficient inter-domain live streaming architecture operating on top of LISP. LISP involves upgrading some Internet routers and our proposal can be introduced along with these new deployments. To evaluate its feasibility in terms of processing overhead in networking equipment we have implemented CoreCast in the Linux kernel. Further, we compare the performance of CoreCast to the popular P2P streaming services both analytically and experimentally. The results show that CoreCast reduces inter-domain bandwidth consumption and that introduces negligible processing overhead in network equipment.     

流量工程中多维目标优化的路由算法综述

互联网中传统的最短路径路由算法本质上存在导致拥塞的可能。网络拥塞不仅会降低网络性能,而且会使得服务提供商难以完成对客户的服务质量保证。通过在路由选择阶段面向流量工程实施优化,能够避免拥塞,提高网络资源利用率。概述面向流量工程的约束路由算法的研究进展。首先阐述了三类主要的流量工程优化目标：最小化网络资源占用、负载平衡和最小干涉,然后分析了各类典型算法,最后对此方向的研究进行了总结和展望。