Modeling the routing of an autonomous system with C-BGP

Today, the complexity of ISPs' networks make it difficult to investigate the implications of internal or external changes on the distribution of traffic across their network. In this article we explain the complexity of building models of large ISPs' networks. We describe the various aspects important to understanding the routing inside an AS. We present an open source routing solver, C-BGP, that eases the investigation of changes in the routing or topology of large networks. We illustrate how to build a model of an ISP on a real transit network and apply the model on two "what-if" scenarios. The first scenario studies the impact of chances in the Internet connectivity of a transit network. The second investigates the impact of failures in its internal topology.     

Topology control for multi-channel multi-radio wireless mesh networks using directional antennas

Directional antennas are widely used technologies for reducing signal interference and increasing spatial reuse. In this paper, we propose a topology control method for multi-channel multi-radio wireless mesh networks that use directional antennas. We are given a set of mesh routers installed in a region and some of them are gateway nodes that are connected to the Internet via wired lines. Each router has a traffic demand (Internet access traffic) generated from the end-users. The problem is how to adjust antenna orientations of radios and assign channels to them to construct a logical network topology, such that the minimum delivery ratio of traffic demands of routers is maximized. We first formulate the problem to an equivalent optimization problem with a clearer measurable metric, which is to minimize the largest interfering traffic of links in the network. We then propose a three-step solution to solve the problem. Firstly, we construct a set of routing trees, with the objective to balance the traffic among tree links. Secondly, we assign the radios of a node to the links it needs to serve, such that the total traffic load of the links that each radio serves is as balanced as possible. Thirdly, we do a fine-grained adjustment of antenna orientations and assign channels to them, such that the transmission area of each antenna will cover all the links it serves and the largest interfering traffic of links is minimized.     

Recognizing and characterizing dynamics of cellular devices in cellular data network through massive data analysis

The user clients for accessing Internet are increasingly shifting from desktop computers to cellular devices. To be competitive in the rapidly changing market, operators, Internet service providers and application developers are required to have the capability of recognizing the models of cellular devices and understanding the traffic dynamics of cellular data network. In this paper, we propose a novel Jaccard measurement‐based method to recognize cellular device models from network traffic data. This method is implemented as a scalable paralleled MapReduce program and achieves a high accuracy, 91.5%, in the evaluation with 2.9 billion traffic records collected from the real network. Based on the recognition results, we conduct a comprehensive study of three characteristics of network traffic from device model perspective, the network access time, the traffic volume, and the diurnal patterns. The analysis results show that the distribution of network access time can be modeled by a two‐component Gaussian mixture model, and the distribution of traffic volumes is highly skewed and follows the power law. In addition, seven distinct diurnal patterns of cellular device usage are identified by applying unsupervised clustering algorithm on the collected massive traffic data. Copyright © 2014 John Wiley & Sons, Ltd.     

A tutorial on using genetic algorithms for the design of network topology

The design of network topology is an important part of network design, since network topology is directly associated with network operational behavior, capacity, reliability, and cost. This paper is a tutorial paper concerned with illustrating how the optimization capabilities of genetic algorithms can be used to design suitable network topologies considering basic topology problems. Simple genetic algorithms have been developed for the topology problem of mesh networks, considering single node and single link failure tolerance. The algorithms are based on criteria of two important measures: minimizing the length of communication links; and minimizing traffic flow through these links for given traffic loads. The first measure contributes to minimizing the cost of cabling, while the second measure contributes to minimizing the cost of link capacity. The work provides a useful approach and tools to network students and professionals concerned with the topology design of backbone networks. The developed software is made available on the Internet. Copyright © 2006 John Wiley & Sons, Ltd.     

Multi‐topology routing based egress selection approach to achieve hybrid intra‐AS and inter‐AS traffic engineering

Hot‐potato routing is a border gateway protocol policy that selects the ‘closest’ egress router in terms of interior gateway protocol cost. This policy imposes inherent interactions between intra‐AS (Autonomous System) and inter‐AS traffic engineering. In light of this observation, we present a hybrid intra‐AS and inter‐AS traffic engineering scheme named egress selection based upon hot potato routing. This scheme involves link weight optimization, which can not only minimize the time that IP (Internet Protocol) packets travel across the network by assigning specified egress router but also balance the load among the internal links of the transit network. Egress selection based upon hot potato routing also incorporates multi‐topology routing technique to address the problem that one set of link weights might not guarantee specified egress routers. Accordingly, we formulate the link weights optimization problem using multi‐topology routing as a mixed integer linear programming model. And we present a new heuristic algorithm to make the problem tractable. Numerical results show that only a few topologies are needed to guarantee specified egress router, and maximum link utilization is also reduced. Copyright © 2014 John Wiley & Sons, Ltd.     

MPLS-based satellite constellation networks

Nongeostationary satellite constellations with intersatellite links are a challenge for networking due to their continuously changing topology. In order to make maximal use of the network's capacities, special attention has to be paid to routing and traffic engineering. Multiprotocol label switching (MPLS) as underlying protocol is an interesting candidate for this task since it offers many possibilities to exert influence on traffic flows and supports today's dominating Internet protocol traffic very well. This paper describes a general MPLS-based networking concept for satellite networks and discusses different scenarios considering the particularities and constraints of the dynamic topology. Functional elements of MPLS like ingress, egress, or core routers have to be mapped onto the physical entities of the network and prerequisites for traffic engineering are discussed. Routing and rerouting of paths is of key interest since this affects route computation effort and routing performance. Thus, an analytical estimation of routing effort is deduced and numerical and simulation results are presented.     

Deriving traffic demands for operational IP networks: methodologyand experience

Engineering a large IP backbone network without an accurate network-wide view of the traffic demands is challenging. Shifts in user behavior, changes in routing policies, and failures of network elements can result in significant (and sudden) fluctuations in load. We present a model of traffic demands to support traffic engineering and performance debugging of large Internet service provider networks. By defining a traffic demand as a volume of load originating from an ingress link and destined to a set of egress links, we can capture and predict how routing affects the traffic traveling between domains. To infer the traffic demands, we propose a measurement methodology that combines flow-level measurements collected at all ingress links with reachability information about all egress links. We discuss how to cope with situations where practical considerations limit the amount and quality of the necessary data. Specifically, we show how to infer interdomain traffic demands using measurements collected at a smaller number of edge links-the peering links connecting to neighboring providers. We report on our experiences in deriving the traffic demands in the AT&T IP Backbone, by collecting, validating, and joining very large and diverse sets of usage, configuration, and routing data over extended periods of time. The paper concludes with a preliminary analysis of the observed dynamics of the traffic demands and a discussion of the practical implications for traffic engineering     

A decade of Internet research — advances in models and practices

The complexity and heterogeneity of the current Internet have rendered traditional analytical models and techniques inadequate for networking researchers and engineers. Many within the networking research community feel that researchers investigating new protocols and architectures, either by simulation or test-bed implementation, need to use common models. Despite the lack of models with universal applicability, there are certain models that are more appropriate than others for analysing certain systems. Researchers in different areas tend to use established models, typically to allow comparison of results. In addition, researchers have made considerable progress in understanding the statistical nature of Internet traffic. Despite the widespread use of simulation and test-bed implementation for modelling the Internet, there is little consensus today on analysis techniques and their validation. This paper summarises the main advances made in the last ten years or so in understanding the nature of Internet traffic, models and practices developed for Internet topology and protocol dynamics analysis.     

QoS abstraction layer in 4G access networks

Emerging access networks will use heterogeneous wireless technologies such as 802.11, 802.16 or UMTS, to offer users the best access to the Internet. Layer 2 access networks will consist of wireless bridges (access points) that isolate, concatenated, or in mesh provide access to mobile nodes. The transport of real time traffic over these networks may demand new QoS signalling, used to reserve resources. Besides the reservation, the new signalling needs to address the dynamics of the wireless links, the mobility of the terminals, and the multicast traffic. In this paper a new protocol is proposed aimed at solving this problem—the QoS Abstraction Layer (QoSAL). Existing only at the control plane, the QoSAL is located above the layer 2 and hides from layer 3 the details of each technology with respect to the QoS and to the network topology. The QoSAL has been designed, simulated, and tested. The results obtained demonstrate its usefulness in 4G networks.     

Performance Preserving Topological Downscaling of Internet-Like Networks

The Internet is a large, heterogeneous system operating at very high speeds and consisting of a large number of users. Researchers use a suite of tools and techniques in order to understand the performance of complex networks like the Internet: measurements, simulations, and deployments on small to medium-scale testbeds. This work considers a novel addition to this suite: a class of methods to scale down the topology of the Internet that enables researchers to create and observe a smaller replica, and extrapolate its performance to the expected performance of the larger Internet. This is complementary to the work of Psounis, 2003, where the authors presented a way to scale down the Internet in time, by creating a slower replica of the original system. The key insight that we leverage in this work is that only the congested links along the path of each flow introduce sizable queueing delays and dependencies among flows. Hence, one might hope that the network properties can be captured by a topology that consists of the congested links only. Using extensive simulations with transmission control protocol (TCP) traffic and theoretical analysis, we show that it is possible to achieve this kind of performance scaling even on topologies the size of the CENIC backbone (that provides Internet access to higher education institutions in California). We also show that simulating a scaled topology can be up to two orders of magnitude faster than simulating the original topology     

有效提高Internet传输性能的社团结构改善策略

提出一种增添能最有效减弱网络社团特性的边以提高Internet网络传输性能的策略,即减弱社团结构策略（简称WCS策略）,并基于光逻辑链路可以提供与实际物理链路相当的高性能,以实现WCS策略的Internet网络的拓扑重构。在伪随机网络、具有社团结构的无标度人工网络和实际Internet网络上分别进行了基于全局最短路径路由和局部路由的实验。实验结果表明,利用WCS策略在社团之间少量边的添加,就能实现网络负载能力和平均最短路径的大幅改善。     

Dynamic link sleeping reconfigurations for green traffic engineering

The high volume of energy consumption has become a great concern to the Internet community because of high energy waste on redundant network devices. One promising scheme for energy savings is to reconfigure network elements to sleep mode when traffic demand is low. However, due to the nature of today's traditional IP routing protocols, network reconfiguration is generally deemed to be harmful because of routing table reconvergence. To make these sleeping network elements, such as links, robust to traffic disruption, we propose a novel online scheme called designate to sleep algorithm that aims to remove network links without causing traffic disruption during energy‐saving periods. Considering the nature of diurnal traffic, there could be traffic surge in the network because of reduced network capacity. We therefore propose a complementary scheme called dynamic wake‐up algorithm that intelligently wakes up minimum number of sleeping links needed to control such dynamicity. This is contrary to the normal paradigm of either reverting to full topology and sacrificing energy savings or employing on‐the‐fly link weight manipulation. Using the real topologies of GEANT and Abilene networks respectively, we show that the proposed schemes can save a substantial amount of energy without affecting network performance.     

An energy‐efficient algorithm based on sleep‐scheduling in IP backbone networks

This paper relates to the problem of energy conservation in Internet backbone networks. We propose a new Distributed Green Algorithm based on Sleep‐scheduling (DGAS) to switch off some network links and nodes resulting in less energy consumption. Our solution does not depend on any centralized controller and uses a link‐state protocol like Open Shortest Path First to share required information. In addition, DGAS does not require any knowledge of traffic matrix and switches off network nodes and links in 2 phases. In the first phase, some core nodes are switched off on the basis of their usage in network paths. In the second phase, DGAS starts with a minimal topology on the basis of resulted topology from the first phase and adds some links to it to minimize network paths length. Results, obtained by several real network scenarios, show that DGAS can switch off up to 27% of core nodes and up to 80% of links compared to the maximum number of switchable links.     

Dynamics of key management in secure satellite multicast

Security is an important concern in today's information age and particularly so in satellite systems, where eavesdropping can be easily performed. This paper addresses efficient key management for encrypted multicast traffic transmitted via satellite. We consider the topic of encrypting traffic in large multicast groups, where the group size and dynamics have a significant impact on the network load. We consider life cycle key management costs of a multicast connection, and show for a logical key hierarchy (LKH) how member preregistration and periodic admission reduces the initialization cost, and how the optimum outdegree of a hierarchical tree varies with the expected member volatility and rekey factor. This improves network utilization, but encryption at the network layer can pose problems on satellite links. We, therefore, propose and analyze an interworking solution between multilayer Internet protocol security (IPSEC) and LKH that also reduces key management traffic while enabling interworking with performance enhancing modules used on satellite links.     

利用Cisco路由器的ACL技术实现对中小型网络的安全管理

随着计算机网络的迅速发展,中小型网络作为互联网的基本组成部分,其安全问题不容忽视。本文通过具体的网络配置实例,说明了如何利用Cisco路由器的ACL技术实现对中小型网络进行控制和管理,限制特定网络流量,提高网络性能和安全。     

Bitcoin's dynamic peer‐to‐peer topology

Topology discovery is a prerequisite when investigating the network properties; with the enormous number of Bitcoin users and performance issues, it becomes critical to analyse the network in a fashion that makes it possible to detect all Bitcoin's nodes and understand their behaviour. In massive, dynamic, and distributed peer‐to‐peer (P2P) networks like Bitcoin, where thousands of updates occur per second, it is hard to obtain an accurate topology representing the structure of the network as a graph with nodes and links by using the traditional local measurement approaches based on batches, offline data, or on the discovery of the topology around a small set of nodes and then combine them to discover an approximate network topology. All of which present some limitation when applying them on blockchain‐based networks. In this paper, we propose a topology discovery system that performs a real‐time data collection and analysis for Bitcoin P2P links, which assembles incoming nodes information for deeper graph analysis processing. The topology discovery system allows us to gain knowledge on the Bitcoin network size, the network stability in terms of reachable, churn, and well‐connected nodes, as well as some data regarding the effects of some countries' Internet infrastructure on Bitcoin traffic.     

Multicast-based inference of network-internal loss characteristics

Robust measurements of network dynamics are increasingly important to the design and operation of large internetworks like the Internet. However, administrative diversity makes it impractical to monitor every link on an end-to-end path. At the same time, it is difficult to determine the performance characteristics of individual links from end-to-end measurements of unicast traffic. In this paper, we introduce the use of end-to-end measurements of multicast traffic to infer network-internal characteristics. The bandwidth efficiency of multicast traffic makes it suitable for large-scale measurements of both end-to-end and internal network dynamics. We develop a maximum-likelihood estimator for loss rates on internal links based on losses observed by multicast receivers. It exploits the inherent correlation between such observations to infer the performance of paths between branch points in the tree spanning a multicast source and its receivers. We derive its rate of convergence as the number of measurements increases, and we establish robustness with respect to certain generalizations of the underlying model. We validate these techniques through simulation and discuss possible extensions and applications of this work     

Understanding and improving TCP performance over networks withminimum rate guarantees

A large number of Internet applications are sensitive to overload conditions in the network. While these applications have been designed to adapt somewhat to the varying conditions in the Internet, they can benefit greatly from an increased level of predictability in network services. We propose minor extensions to the packet queueing and discard mechanisms used in routers, coupled with simple control mechanisms at the source that enable the network to guarantee minimal levels of throughput to different sessions while sharing the residual network capacity in a cooperative manner. The service realized by the proposed mechanisms is an interpretation of the controlled-load service being standardized by the Internet Engineering Task Force. Although controlled-load service can be used in conjunction with any transport protocol, our focus in this paper is on understanding its interaction with Transmission Control Protocol (TCP). Specifically, we study the dynamics of TCP traffic in an integrated services network that simultaneously supports both best-effort and controlled-load sessions. In light of this study, we propose and experiment with modifications to TCP's congestion control mechanisms in order to improve its performance in networks where a minimum transmission rate is guaranteed. We then investigate the effect of network transients, such as changes in traffic load and in service levels, on the performance of controlled-load as well as best-effort connections. To capture the evolution of integrated services in the Internet, we also consider situations where only a selective set of routers are capable of providing service differentiation between best-effort and controlled-load traffic. Finally, we show how the service mechanisms proposed here can be embedded within other packet and link scheduling frameworks in a fully evolved integrated services Internet     

NewReno拥塞控制方式下路由器缓冲区容量研究

 路由器缓冲区容量的设置问题是近年来路由器研究中的热点课题之一.已有的研究主要集中在流量模型、网络拓扑及设置、路由器体系结构及设置、网络的动态性以及性能评价指标五个维度在研究.本文在现有基于评价指标和流量模型所作研究的基础上,提出了一种新的评价指标——流完成时间比.该评价指标具有不依赖网络属性的优点.本文使用这一评价指标进行了基于自相似流量的仿真实验分析,对SFCTR、AFCTR和FCU这三个流完成时间比的相关性能指标进行了监测,得出过大和过小的缓冲区容量都会造成性能下降的结论,并给出了合理设置路由器缓冲区容量的方法.     

Self-similar traffic and network dynamics

One of the most significant findings of traffic measurement studies over the last decade has been the observed self-similarity in packet network traffic. Subsequent research has focused on the origins of this self-similarity, and the network engineering significance of this phenomenon. This paper reviews what is currently known about network traffic self-similarity and its significance. We then consider a matter of current research, namely, the manner in which network dynamics (specifically, the dynamics of transmission control protocol (TCP), the predominant transport protocol used in today's Internet) can affect the observed self-similarity. To this end, we first discuss some of the pitfalls associated with applying traditional performance evaluation techniques to highly-interacting, large-scale networks such as the Internet. We then present one promising approach based on chaotic maps to capture and model the dynamics of TCP-type feedback control in such networks. Not only can appropriately chosen chaotic map models capture a range of realistic source characteristics, but by coupling these to network state equations, one can study the effects of network dynamics on the observed scaling behavior We consider several aspects of TCP feedback, and illustrate by examples that while TCP-type feedback can modify the self-similar scaling behavior of network traffic, it neither generates it nor eliminates it