Analysis of Topology Aggregation techniques for QoS routing
ACM Computing SurveysPublished 3 September 2007
Suleyman Uludag, King‐Shan Lui, Klara Nahrstedt, G.B. Brewster
Citations61
SJR quartileQ1
SJR score5.80
SNIP11.03
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The current TA techniques are surveyed, methodology to classify, evaluate, and compare their complexities and efficiencies are provided, and the techniques' advantages and disadvantages are compared.
Abstract
We study and compare topology aggregation techniques used in QoS routing. Topology Aggregation (TA) is defined as a set of techniques that abstract or summarize the state information about the network topology to be exchanged, processed, and maintained by network nodes for routing purposes. Due to scalability, aggregation techniques have been an integral part of some routing protocols. However, TA has not been studied extensively except in a rather limited context. With the continuing growth of the Internet, scalability issues of QoS routing have been gaining importance. Therefore, we survey the current TA techniques, provide methodology to classify, evaluate, and compare their complexities and efficiencies.
Keywords
Computer Science
Journal of the Operational Research SocietyNetwork Flows: Theory, Algorithms, and Applications.
8,138 Citations1994David K. Smith, Ravindra K. Ahuja +2 more
In-depth, self-contained treatments of shortest path, maximum flow, and minimum cost flow problems, including descriptions of polynomial-time algorithms for these core models are presented.
Border Gateway Protocol 3 (BGP-3)
1,990 Citations1991K. Lougheed, Y. Rekhter
This memo, together with its companion document, "Application of the Border Gateway Protocol in the Internet", define an inter-autonomous system routing protocol for the Internet.
IEEE Journal on Selected Areas in CommunicationsQuality-of-service routing for supporting multimedia applications
1,629 Citations1996Zheng Wang, Jon Crowcroft
This paper first examines the basic problem of QoS routing, namely, finding a path that satisfies multiple constraints, and its implications on routing metric selection, and presents three path computation algorithms for source routing and for hop-by-hop routing.
IEEE Communications MagazineDelay-tolerant networking: an approach to interplanetary Internet
1,405 Citations2003Scott Burleigh, Adrian J. Hooke +6 more
This work identifies three fundamental principles that would underlie a delay-tolerant networking (DTN) architecture and describes the main structural elements of that architecture, centered on a new end-to-end overlay network protocol called Bundling.
IEEE NetworkAn overview of quality of service routing for next-generation high-speed networks: problems and solutions
873 Citations1998Shigang Chen, Klara Nahrstedt
An overview of the QoS routing problem as well as the existing solutions is given, the strengths and weaknesses of different routing strategies, and the challenges are outlined.
Encyclopedia of Wireless and Mobile CommunicationsOptical Communication Networks
792 Citations2007N.K. Singhal, A. Gencata +1 more
A comprehensive explanation of the newest developments in optical networks in the MCGRAW-HILL COMPUTER COMMUNICATIONS series.
Discrete & Computational GeometryOn sparse spanners of weighted graphs
600 Citations1993Ingo Althöfer, Gautam Das +3 more
This paper gives a simple algorithm for constructing sparse spanners for arbitrary weighted graphs and applies this algorithm to obtain specific results for planar graphs and Euclidean graphs.
Overview and Principles of Internet Traffic Engineering
587 Citations2002D.O. Awduche, A.L. Chiu +3 more
The principles, architectures, and methodologies for performance evaluation and performance optimization of operational IP networks are discussed throughout this document.
Characterizing the Internet hierarchy from multiple vantage points
565 Citations2003L. Subramanian, Sharad Agarwal +2 more
The topological structure of the Internet in terms of customer-provider and peer-peer relationships between autonomous systems, as manifested in BGP routing policies, is investigated and a five-level classification of AS is proposed.
Requirements for IP Version 4 Routers
456 Citations1995
This memo defines and discusses requirements for devices that perform the network layer forwarding function of the Internet protocol suite.
Computer Networks (1976)Hierarchical routing for large networks Performance evaluation and optimization
403 Citations1977Leonard Kleinrock, Farouk Kamoun
The specification, analysis and evaluation of some hierarchical routing procedures which are effective for large store-and-forward packet-switched computer networks are dealt with, finding that in the limit of a very large network, enormous table reduction may be achieved with essentially no increase in network path length.
Quality of service based routing
337 Citations1998George Apostolopoulos, R. Guérin +2 more
Extensions to the basic QoS routing are developed that can achieve good routing performance with limited update generation rates and the impact on the results of a number of secondary factors such as topology, high level admission control, and characteristics of network traffic.
The landmark hierarchy: a new hierarchy for routing in very large networks
325 Citations1988Paul F. Tsuchiya
The Landmark Hierarchy is described, analyzes it, and compares it with the area hierarchy, allowing for very large, dynamic networks.
There is a planar graph almost as good as the complete graph
235 Citations1986Paul Chew
Given a source, a destination, and a set of polygonal obstacles of size n, an size data structure can be used to find a reasonable approximation to the shortest path between the source and the destination in &Ogr;(n log n) time.
The Nimrod Routing Architecture
172 Citations1996Isidro Castiñeyra, N. Chiappa +1 more
The Nimrod architecture is designed to accommodate a dynamic internetwork of arbitrary size with heterogeneous service requirements and restrictions and to admit incremental deployment throughout an internetwork.
NIRA
159 Citations2003Xiaowei Yang
This paper explores various technical problems that would have to be solved to give users the ability to choose: how a user discovers routes and whether the dynamic conditions of the routes satisfy his requirements, how to efficiently represent routes, and how to properly compensate providers if a user chooses to use them.
ACM SIGCOMM Computer Communication ReviewQuality of service based routing
153 Citations1998George Apostolopoulos, R. Guérin +2 more
Evidence that Quality of Service (QoS) routing can provide increased network utilization compared to routing that is not sensitive to QoS requirements of traffic is provided.
The Recommendation for the IP Next Generation Protocol
153 Citations1995S. Bradner, Allison Mankin
This document presents the recommendation of the IPng Area Directors on what should be used to replace the current version of the Internet Protocol.
ACM SIGCOMM Computer Communication ReviewTopology aggregation for hierarchical routing in ATM networks
122 Citations1995Whay C. Lee
This paper examines some issues of topology aggregation for hierarchical PNNI Routing in ATM networks, presents a complex node representation, and provides some guidelines forTopology aggregation.
IEEE Communications Surveys & TutorialsConstraint-based routing in the internet: Basic principles and recent research
118 Citations2003Ossama Younis, Sonia Fahmy
This article discusses several constraint-based routing approaches and explains their requirements, complexity, and recent research proposals, and illustrates how these approaches can be integrated with Internet label switching and QoS architectures.
An optimal synchronizer for the hypercube
101 Citations1987David Peleg, Jeffrey D. Ullman
A novel technique for constructing network synchronizers is presented, developed from some basic relationships between synchronizers and the structure of a t-spanning subgraph over the network, and a synchronizer for the hypercube with optimal time and communication complexities is obtained.
Spanning tree method for link state aggregation in large communication networks
97 Citations2002W.C. Lee
The key idea for the method is to first reduce the original subnetwork topology to a full-mesh representation that consists of a logical link for each pair of border nodes in the subnetwork, and then encode the link state information associated with the full- mesh representation with an appropriate spanning tree.
Discrete Applied MathematicsTree spanners in planar graphs
94 Citations2001Sándor P. Fekete, Jana Kremer
On scalable QoS routing: performance evaluation of topology aggregation
93 Citations2002Hao Fang, Ellen Zegura
This work evaluates the performance of techniques that can reduce the QoS routing protocol overhead and proposes two new methods of aggregating routing information, which perform much better than conventional star aggregation and approaches unaggregated performance.
NetworksOptimal clustering structures for hierarchical topological design of large computer networks
89 Citations1980Leonard Kleinrock, Farouk Kamoun
IEEE/ACM Transactions on NetworkingRouting With Topology Aggregation in Delay-Bandwidth Sensitive Networks
86 Citations2004Ki Lui, K. Nahrstedt +1 more
A novel quality-of-service (QoS) parameter representation with a new aggregation algorithm and a QoS-aware routing protocol that achieves very good performance in terms of delay deviation, success ratio, and crankback ratio.
ACM Transactions on Modeling and Computer SimulationSource-oriented topology aggregation with multiple QoS parameters in hierarchical networks
83 Citations2000Turgay Korkmaz, Marwan Krunz
Lecture notes in computer scienceA Simple Linear Time Algorithm for Computing a (2k — 1)-Spanner of O(n 1+1/k ) Size in Weighted Graphs
79 Citations2003Surender Baswana, Sandeep Sen
This paper presents an extremely simple linear time randomized algorithm that constructs (2k - 1)-spanner of size matching the conjectured lower bound, and thus can be adapted suitably to obtain efficient distributed and parallel algorithms.
Discrete Applied MathematicsNP-completeness of minimum spanner problems
78 Citations1994Leizhen Cai
It is shown that for any fixed t ≥ 2, the problem of determining, for a graph G and a positive integer K, whether G contains a t -spanner with at most K edges is NP-complete, even if G is a bipartite graph.
Lecture notes in computer scienceQuality of Service Routing
74 Citations2003Piet Van Mieghem, Fernando Kuipers +7 more
The need for constraint-based routing algorithms with a fast running time has resulted in the proposal of numerous heuristics and a few exact solutions.
IEEE/ACM Transactions on NetworkingTopology aggregation for directed graphs
71 Citations2001Baruch Awerbuch, Yuval Shavitt
The paper presents a solution with distortion that is bounded by the logarithm of the number of border nodes and the square-root of the asymmetry in the cost of a link, the first time that a theoretical bound is given to an undirected graph.
IEEE Journal on Selected Areas in CommunicationsDistributed, scalable routing based on vectors of link states
70 Citations1995J.J. Garcia‐Luna‐Aceves, Jochen Behrens
Link vector algorithms (LVA) are introduced for the distributed maintenance of routing information in large networks and internets using link-state information.
IEEE Transactions on ComputersAn adaptive hierarchical routing protocol
69 Citations1989W.T. Tsai, C. V. Ramamoorthy +2 more
An adaptive hierarchical routing protocol based on the extension of the new Arpanet scheme is proposed and its simulated performance is presented and the tradeoff between two conflicting performance criteria, response speed and communication overhead, is shown.
Hierarchical routing using link vectors
67 Citations2002Jochen Behrens, J.J. Garcia‐Luna‐Aceves
Simulation results are presented showing that the ALVA outperforms the OSPF in terms of communication and storage overhead.
Computer Networks (1976)Stochastic performance evaluation of hierarchical routing for large networks
63 Citations1979Farouk Kamoun, Leonard Kleinrock
This paper evaluating the tradeoff between the reduction in routing table length and the increase in network path length in terms of the more meaningful network performance measures of delay and throughput shows the enormous efficiency of optimized hierarchical routing for a class of large networks.
Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE<title>Hierarchical structure of the logical Internet graph</title>
60 Citations2001Zihui Ge, Daniel R. Figueiredo +2 more
This paper characterize the logical graph using various metrics and identifies the presence of power laws in the number of customers that a provider has and defines a structural model of the AS graph, which highlights the hierarchical nature of logical relationships and the preferential connection to larger providers.
Scalable inter-domain routing architecture
58 Citations1992Deborah Estrin, Yakov Rekhter +1 more
This paper evaluates the algorithmic design choices for the NR component in terms of scalability and functionality, and discusses mechanisms for improving the scaling properties of link-state SDR, and for integrating the two components of the architecture.
Commentary on Inter-Domain Routing in the Internet
58 Citations2001Geoff Huston
This document examines the various longer term trends visible within the characteristics of the Internet's BGP table and identifies a number of operational practices and protocol factors that contribute to these trends.
QOS aggregation algorithms in hierarchical ATM networks
43 Citations2002A. Iwata, Hiroshi Suzuki +2 more
A new three step aggregation scheme for hierarchical ATM networks, based on large-scale simulations with different network topologies, traffic scenarios, and performance metrics, delivers good network performance while significantly reducing the network complexity.
Routing through networks with hierarchical topology aggregation
37 Citations2002Baruch Awerbuch, Yuanqi Du +2 more
The minimum spanning tree is a good aggregation scheme; exponential link cost functions perform better than min-hop routing; and the suggested logarithmic update scheme that determines when re-aggregation should be computed can significantly reduce the computational overhead due to re- Aggregation with a negligible decrease in performance.
IEEE/ACM Transactions on NetworkingOptimal PNNI complex node representations for restrictive costs and minimal path computation time
35 Citations2000Ilias Iliadis
This paper presents a method for constructing the set of the optimal complex node representations in the sense that they use the minimum possible number of links, and considers the symmetric case.
An Architecture for Inter-Domain Policy Routing
32 Citations1993Martha Steenstrup
The IDPR architecture is designed to accommodate an internetwork containing tens of thousands of administrative domains with heterogeneous service requirements and restrictions.
Hierarchical QoS routing in delay-bandwidth sensitive networks
31 Citations2002King‐Shan Lui, Klara Nahrstedt +1 more
The novelty in this research is the new network QoS representation which is line segments on the delay-bandwidth plane and a distributed routing mechanism that works with the representation.
Scalable Routing Design Principles
29 Citations2000Jiadi Yu
This document identifies major factors affecting routing scalability as well as basic principles of designing scalable routing for large networks.
Source-oriented topology aggregation with multiple QoS parameters in hierarchical ATM networks
28 Citations2003Turgay Korkmaz, Marwan Krunz
A source-oriented approach to TA is introduced, which provides better performance than existing approaches and is integrated into three new TA schemes that provide different tradeoffs between compaction and accuracy.
QoS information approximation for aggregated networks
27 Citations2004Yong Tang, Shigang Chen
A unified account of state aggregation based on the concept of service curves is given, which shows that new approximation methods based on polynomial curves, cubic splines and polylines approximate the network state far more accurate than the existing methods.
On state aggregation for scalable QoS routing
24 Citations2002Longjiang Guo, Ibrahim Matta
This paper compares the performance of three different aggregation schemes, namely, the simple-node scheme, the full-mesh scheme, and the star scheme, which represent a given group of nodes by a single logical node, a complete graph between border nodes, and a star-like graph connecting all of the border nodes; and obtains transient performance measures for multi-service networks using the Z-iteration method.
Minimum equivalent subspanner algorithms for topology aggregation in ATM networks
24 Citations2003Whay Chiou Lee
This paper presents some algorithms that can be used to determine, for a given topology, a minimum representation with no compromise on accuracy, and the application of these algorithms to generate complex node representations for topology aggregation in ATM networks is discussed.
Computer CommunicationsEfficient hierarchical QoS routing in ATM networks
17 Citations2001Ben‐Jye Chang, Ren‐Hung Hwang
A dynamic update policy, referred to as the dynamic cost-based update (DCU) policy, is proposed to improve the accuracy of the aggregated information and the performance of hierarchical routing, while decreasing the frequency of re-aggregation and information distribution.
Transition matrix generation for complex node representation
10 Citations2003Ilias Iliadis, Paolo Scotton
A novel graph coloring technique to compute the transition matrix of a PNNI peer group with a computational complexity of O(eloge), e being the number of edges in the peer group is presented.
A probabilistic scheme for hierarchical QoS routing
9 Citations2005D. Ghosh, Raj Acharya
A Probabilistic scheme for topology aggregation in large networks which are QoS sensitive and a modification to an existing probabilistic QoS routing algorithm for concave QoS parameters is proposed, which increases the global network resource utilization.
2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No.04CH37601)On generating Internet hierarchical topology
7 Citations2004Songlin Cai, Lixin Gao +2 more
This study classify Internet AS level topology into hierarchical structure based on the logical relationship between ASs, which is widely adopted in the literature and derives the formulae of degree distribution for this mechanism.
Analysis of IDR requirements and History
6 Citations2007Avri Doria, Elwyn Davies
This document analyses the current state of IDR routing with respect to RFC1126 and other IDR requirements and design efforts and discusses requirements for the future routing architecture and future routing protocols.
Performance analysis of capacity-aware state aggregation for inter-domain QoS routing
6 Citations2005Venkatesh Sarangan, D. Ghosh +1 more
This paper study the efficacy of a new bandwidth aggregation scheme, and compare its performance with that of the existing schemes, showing that for active networks, the proposed aggregation scheme is more accurate, and gives a better routing performance than the current schemes.
Link state aggregation using a shufflenet in ATM PNNI networks
6 Citations2002Younghwan Yoo, Sanghyun Ahn +1 more
An algorithm for efficiently aggregating link state information needed for source routing in PNNI networks by mapping each border node in a peer group to a node of a shufflenet which performs as good as the full-mesh approach, with only a much smaller amount of information.
State aggregation using network flows for stochastic networks
6 Citations2003Venkatesh Sarangan, D. Ghosh +1 more
A new fast heuristic algorithm to estimate the PMF of "maximum-flow" through a probabilistic flow network and shows that stochastic estimation of traffic capacity is better than deterministic estimation and gives a better bandwidth admission ratio when compared with existing state aggregation techniques.
ACM SIGCOMM Computer Communication ReviewScalable inter-domain routing architecture
5 Citations1992Deborah Estrin, Yakov Rekhter +1 more
Journal of Communications and NetworksTopology aggregation schemes for asymmetric link state information
1 Citations2004Younghwan Yoo, Sanghyun Ahn +1 more
The de Bruijn algorithm needs smaller computational complexity than most previous algorithms for asymmetric networks, including the shufflenet algorithm, and performs far better than the star approach which is one of the most widely accepted schemes.
Using network flows in hierarchical QoS routing
1 Citations2005Venkatesh Sarangan, Raj Acharya
This paper proposes a new scheme for aggregating bandwidth that enables a domain to update the aggregate sent by another domain and thus keep track of resources available in other domains, and results show that this method gives a better bandwidth admission ratio when compared to existing aggregation techniques.