Improving Convergence Speed and Scalability in OSPF: A Survey
---
paper_title: The Birth of Link-State Routing

paper_content:

‘‘Routing is a hard problem.’’ That’s what colleagues told me when I joined BBN in 1971, right after getting my undergraduate and master’s degrees in computer science at Harvard University. As a student, I had built the hardware and software to connect Harvard’s first interactive computer, the DEC PDP-1, to the infant Arpanet (the first packet switching computer network and precursor of the Internet). I had also taken a Harvard course taught by two senior BBN engineers who built the original interface message processors (IMPs), the switching nodes that routed traffic across the network. While at BBN, and with almost all the course requirements for a PhD in hand, it was time to find a possible dissertation topic. So I was glad to learn that dynamic routing—determining the best paths for network traffic in real time—was considered a difficult computer science issue because I planned to tackle it. By 1971, the Arpanet had been up and running long enough to disclose shortcomings in the performance and stability of the original design. My job at BBN was to redesign and rewrite all the software for the IMP, not just the routing module. I fondly recall releasing new IMP software to the whole network (amounting to a few dozen nodes at the time) every other Tuesday morning for two years. Fifty software versions later, the IMPs had more stable congestion management, better reliability, and higher throughput. But routing still remained a challenging area for further study. By the end of 1974 I had completed my PhD dissertation for Harvard on routing while working full-time at BBN. This dissertation described the problem, analyzed and compared many routing algorithms, and pointed out topics for further work, such as hierarchical routing for networks of networks. But I had not resolved some of the nagging network accidents, outages, and other crises caused by the original Arpanet routing system.
---
paper_title: On the building blocks of quality of service in heterogeneous IP networks

paper_content:

After more than a decade of active research on Quality of Service in IP networks and the Internet, the majority of IP traffic relies on the conventional best-effort IP service model. Nevertheless, some QoS mechanisms are deployed in current networking infrastructures, while emerging applications pose QoS challenges. This survey brings into the foreground a broad range of research results on Quality of Service in IP-based networks. First, a justification of the need for QoS is provided, along with challenges stemming from the convergence of IP and wireless networks and the proliferation of QoS-demanding IP applications (such as VoIP). It is also emphasized that a global uniform end-to-end IP QoS solution is not realistic. Based on this remark, packet-level QoS mechanisms are classified as certain building blocks, each one fulfilling different objectives in certain parts of a heterogeneous IP network. This taxonomy, being in line with the ITU-T initiative toward a QoS architectural framework for IP networks, gives rise to a thorough presentation of QoS “building blocks,” as well as their associated mechanisms. This presentation is followed by an illustration of how the various building blocks are combined in the scope of modern IP networks. However, offering QoS in a large scale IP-based network demands that additional (i.e. non-packet-level) QoS mechanisms are deployed in some parts. Therefore, we also present prominent technologies and mechanisms devised to augment the QoS capabilities of access, wireless, and optical networks. We illustrate how these mechanisms boost end-to-end QoS solutions and reveal interworking issues with packet-level mechanisms.
---
paper_title: A survey of QoS routing solutions for mobile ad hoc networks

paper_content:

In mobile ad hoc networks (MANETs), the provision of quality of service (QoS) guarantees is much more challenging than in wireline networks, mainly due to node mobility, multihop communications, contention for channel access, and a lack of central coordination. QoS guarantees are required by most multimedia and other time- or error-sensitive applications. The difficulties in the provision of such guarantees have limited the usefulness of MANETs. However, in the last decade, much research attention has focused on providing QoS assurances in MANET protocols. The QoS routing protocol is an integral part of any QoS solution since its function is to ascertain which nodes, if any, are able to serve applications? requirements. Consequently, it also plays a crucial role in data session admission control. This document offers an up-to-date survey of most major contributions to the pool of QoS routing solutions for MANETs published in the period 1997?2006. We include a thorough overview of QoS routing metrics, resources, and factors affecting performance and classify the protocols found in the literature. We also summarize their operation and describe their interactions with the medium access control (MAC) protocol, where applicable. This provides the reader with insight into their differences and allows us to highlight trends in protocol design and identify areas for future research.
---
paper_title: Voice over the internet: A tutorial discussing problems and solutions associated with alternative transport

paper_content:

This article provides a tutorial overview of voice over the Internet, examining the effects of moving voice traffic over the packet switched Internet and comparing this with the effects of moving voice over the more traditional circuit-switched telephone system. The emphasis of this document is on areas of concern to a backbone service provider implementing Voice over IP (VoIP). We begin by providing overviews of the Plain Old Telephone Service (POTS) and VoIP. We then discuss techniques service providers can use to help preserve service quality on their VoIP networks. Next, we briefly discuss Voice over ATM (VoATM) as an alternative to VoIP. Finally, we offer some conclusions.
---
paper_title: The New Routing Algorithm for the ARPANET

paper_content:

The new ARPANET routing algorithm is an improvement over the old procedure in that it uses fewer network resources, operates on more realistic estimates of network conditions, reacts faster to important network changes, and does not suffer from long-term loops or oscillations. In the new procedure, each node in the network maintains a database describing the complete network topology and the delays on all lines, and uses the database describing the network to generate a tree representing the minimum delay paths from a given root node to every other network node. Because the traffic in the network can be quite variable, each node periodically measures the delays along its outgoing lines and forwards this information to all other nodes. The delay information propagates quickly through the network so that all nodes can update their databases and continue to route traffic in a consistent and efficient manner. An extensive series of tests were conducted on the ARPANET, showing that line overhead and CPU overhead are both less than two percent, most nodes learn of an update within 100 ms, and the algorithm detects congestion and routes packets around congested areas.
---
paper_title: OSPF: Anatomy of an Internet Routing Protocol

paper_content:

From the Publisher: ::: Written for TCP/IP network administrators, protocol designers, and network application developers, this book gives the most complete and practical view ever into the inner workings of Internet routing. The book focuses on OSPF (Open Shortest Path First), a common TCP/IP routing protocol that provides robust and efficient routing support in the most demanding Internet environments. A methodical and detailed description of the protocol is offered and OSPF's role within the wider context of a TCP/IP network is demonstrated. ::: Practical throughout, the book provides not only a theoretical description of Internet routing, but also a real-world look into how theory translates into practice. It shows how algorithms are implemented, and how the routing protocols function in a working network where transmission lines and routers routinely break down. ::: You will find clear explanations of such routing fundamentals as how a router forwards packets, IP addressing, CIDR (Classless Inter-Domain Routing), the routing table, Internet routing architecture, and the two main routing technologies: Distance Vector and link-state algorithms. OSPF is discussed in depth, with an examination of the rationale behind OSPF's design decisions and how it has evolved to keep pace with the rapidly changing Internet environment. OSPF topics covered by the book include the following: ::: OSPF areas and virtual links NBMA (Nonbroadcast multi-access) and Point-to-MultiPoint network segments OSPF configuration and management Interaction with other routing protocols OSPF cryptographic authentication OSPF protocol extensions, including the Demand Circuit extensions and the multicast extensions to OSPF (MOSPF) An OSPF FAQ ::: ::: IP multicast and multicast routing are also discussed. Methods for debugging routing problems are explained, including a catalog of available debugging tools. The book also offers side-by-side comparisons of all the unicast and multicast routing protocols currently in use in the Internet. ::: You will come away from this book with a sophisticated understanding of Internet routing and of the OSPF protocol in particular. Moreover, the book's practical focus will enable you to put this deeper understanding to work in your network environment.
---
paper_title: Outage Analysis of a University Campus Network

paper_content:

Understanding outage and failure characteristics of a network is important to assess the availability of the network, determine failure source for trouble-shooting, and identify weak areas for network availability improvement. However, there has been virtually no failure measurement and analysis on access networks. In this paper, we carry out an in-depth outage and failure analysis of a university campus network using a rich set of both node outage and link failure data. We investigate the aspects of spatial and temporal localities of failures and outages, the relation of link failure and node outage, and the impact of the hierarchical and redundant network design on outage. We find most of link failure events are not caused by node failures; frequent link up-down events may not lead to the corresponding node's outage; for access layer switches that connect to end hosts, their link up-down events exhibit periodic patterns.
---
paper_title: Optical Layer Monitoring Schemes for Fast Link Failure Localization in All-Optical Networks

paper_content:

Optical layer monitoring and fault localization serves as a critical functional module in the control and management of optical networks. An efficient monitoring scheme aims at minimizing not only the hardware cost required for 100% link failure localization, but also the number of redundant alarms and monitors such that the network fault management can be simplified as well. In recent years, several optical layer monitoring schemes were reported for fast and efficient link failure localization, including simple, non-simple monitoring cycle (m-cycle) and monitoring trail (m-trail). Optimal ILP (Integer Linear Program) models and heuristics were also proposed with smart design philosophy on flexibly trading off different objectives. This article summarizes those innovative ideas and methodologies with in-depth analysis on their pros and cons. We also provide insights on future research topics in this area, as well as possible ways for extending the new failure localization approaches to other network applications.
---
paper_title: Impact of link failures on VoIP performance

paper_content:

We use active and passive traffic measurements to identify the issues involved in the deployment of a voice service over a tier-1 IP backbone network. Our findings indicate that no specific handling of voice packets (i.e. QoS differentiation) is needed in the current backbone but new protocols and mechanisms need to be introduced to provide a better protection against link failures. We discover that link failures may be followed by long periods of routing instability, during which packets can be dropped because forwarded along invalid paths. We also identify the need for a new family of quality of service mechanisms based on fast protection of traffic and high availability of the service rather than performance in terms of delay and loss.
---
paper_title: Characterization of Failures in an Operational IP Backbone Network

paper_content:

As the Internet evolves into a ubiquitous communication infrastructure and supports increasingly important services, its dependability in the presence of various failures becomes critical. In this paper, we analyze IS-IS routing updates from the Sprint IP backbone network to characterize failures that affect IP connectivity. Failures are first classified based on patterns observed at the IP-layer; in some cases, it is possible to further infer their probable causes, such as maintenance activities, router-related and optical layer problems. Key temporal and spatial characteristics of each class are analyzed and, when appropriate, parameterized using well-known distributions. Our results indicate that 20% of all failures happen during a period of scheduled maintenance activities. Of the unplanned failures, almost 30% are shared by multiple links and are most likely due to router-related and optical equipment-related problems, respectively, while 70% affect a single link at a time. Our classification of failures reveals the nature and extent of failures in the Sprint IP backbone. Furthermore, our characterization of the different classes provides a probabilistic failure model, which can be used to generate realistic failure scenarios, as input to various network design and traffic engineering problems.
---
paper_title: Stability issues in OSPF routing

paper_content:

We study the stability of the OSPF protocol under steady state and perturbed conditions. We look at three indicators of stability, namely, (a) network convergence times, (b) routing load on processors, and (c) the number of route flaps. We study these statistics under three different scenarios: (a) on networks that deploy OSPF with TE extensions, (b) on networks that use subsecond HELLO timers, and (c) on networks that use alternative strategies for refreshing link-state information. Our results are based on a very detailed simulation of a real ISP network with 292 nodes and 765 links.
---
paper_title: Network Recovery: Protection and Restoration of Optical, SONET-SDH, IP, and MPLS

paper_content:

Chapter 1: Introduction 1.1 Communications networks today 1.2 Network reliability 1.3 Different phases in a recovery process 1.4 Performance of recovery mechanisms: criteria 1.5 Classification of single-layer recovery mechanisms 1.6 Multi-layer recovery 1.7 Conclusion Chapter 2: SONET-SDH 2.1 Introduction: transmission networks 2.2 SDH and SONET Networks 2.3 Operational aspects 2.4 Ring protection 2.5 Linear Protection 2.6 Restoration 2.7 Case study 2.8 Summary 2.9 Recommended reference work and research-related topics Chapter 3: Optical Networks 3.1 Evolution of the optical network layer 3.2. The Optical Transport Network 3.3 Fault detection and propagation 3.4 Recovery in optical networks 3.5 Recovery mechanisms in ring-based optical networks 3.6 Recovery mechanisms in mesh-based optical networks 3.7 Ring-based versus mesh-based recovery schemes 3.8 Availability 3.9 Som recent trends in research 3.10 Summary Chapter 4: IP Routing 4.1 IP routing protocols 4.2 Analysis of the IP recovery cycle 4.3 Failure profile and fault detection 4.4 Dampening algorithms 4.5 FIS propagation (LSA origination and flooding) 4.6 Route computation 4.7 Temporary loops during network states changes 4.8 Load balancing 4.9 QOS guarantees during failure 4.10 Non Stop Forwarding: an example with OSPF 4.11 A case study with IS-IS 4.12 Summary 4.13 Algorithm complexity 4.14 Incremental SPF 4.15 Interaction between fast IGP convergence and NSF 4.16 Research related topics Chapter 5: MPLS Traffic Engineering 5.1 MPLS Traffic Engineering refresher 5.2. Analysis of the recovery cycle 5.3. MPLS Traffic Engineering global default restoration 5.4 MPLS Traffic engineering global path protection 5.5 MPLS Traffic Engineering local protection 5.6. Another MPLS Traffic Engineering recovery alternative 5.7. Load balancing 5.8 Comparison of global protection and local protection 5.9 Revertive versus non revertive modes 5.10 Failure profiles and fault detection 5.11 Case Studies 5.12 Standardization 5.13 Summary 5.14 RSVP signaling extensions for MPLS TE local protection 5.15 Backup path computation 5.16 Research related topics Chapter 6 Multi-Layer Networks 6.1 ASON / GMPLS networks 6.2 Generic multi-layer recovery approaches 6.3 Case studies 6.4 Conclusion 6.5 References
---
paper_title: Achieving faster failure detection in OSPF networks

paper_content:

A network running OSPF takes several tens of seconds to recover from a failure, using the current default parameter settings. The main component of this delay is the time required to detect a failure using the hello protocol. Reducing the value of the hellointerval can speed up the failure detection time. However, too small a value of the hellointerval can result in an increase in network congestion, potentially causing multiple consecutive hellos to be lost. This can lead to a false breakdown of adjacencies between routers. Such false alarms not only disrupt network traffic by causing unnecessary routing changes, but also increase the processing load on the routers, which may potentially lead to routing instability. In this paper, we investigate the following question - what is the optimal value for the hellointerval that will lead to fast failure detection in the network, while keeping occurrences of false alarms within acceptable limits? We examine the impact of both network congestion and the network topology on the optimal value for the hellointerval. Additionally, we investigate the effectiveness of faster failure detection in achieving fast failure recovery in OSPF networks.
---
paper_title: The Birth of Link-State Routing

paper_content:

‘‘Routing is a hard problem.’’ That’s what colleagues told me when I joined BBN in 1971, right after getting my undergraduate and master’s degrees in computer science at Harvard University. As a student, I had built the hardware and software to connect Harvard’s first interactive computer, the DEC PDP-1, to the infant Arpanet (the first packet switching computer network and precursor of the Internet). I had also taken a Harvard course taught by two senior BBN engineers who built the original interface message processors (IMPs), the switching nodes that routed traffic across the network. While at BBN, and with almost all the course requirements for a PhD in hand, it was time to find a possible dissertation topic. So I was glad to learn that dynamic routing—determining the best paths for network traffic in real time—was considered a difficult computer science issue because I planned to tackle it. By 1971, the Arpanet had been up and running long enough to disclose shortcomings in the performance and stability of the original design. My job at BBN was to redesign and rewrite all the software for the IMP, not just the routing module. I fondly recall releasing new IMP software to the whole network (amounting to a few dozen nodes at the time) every other Tuesday morning for two years. Fifty software versions later, the IMPs had more stable congestion management, better reliability, and higher throughput. But routing still remained a challenging area for further study. By the end of 1974 I had completed my PhD dissertation for Harvard on routing while working full-time at BBN. This dissertation described the problem, analyzed and compared many routing algorithms, and pointed out topics for further work, such as hierarchical routing for networks of networks. But I had not resolved some of the nagging network accidents, outages, and other crises caused by the original Arpanet routing system.
---
paper_title: The New Routing Algorithm for the ARPANET

paper_content:

The new ARPANET routing algorithm is an improvement over the old procedure in that it uses fewer network resources, operates on more realistic estimates of network conditions, reacts faster to important network changes, and does not suffer from long-term loops or oscillations. In the new procedure, each node in the network maintains a database describing the complete network topology and the delays on all lines, and uses the database describing the network to generate a tree representing the minimum delay paths from a given root node to every other network node. Because the traffic in the network can be quite variable, each node periodically measures the delays along its outgoing lines and forwards this information to all other nodes. The delay information propagates quickly through the network so that all nodes can update their databases and continue to route traffic in a consistent and efficient manner. An extensive series of tests were conducted on the ARPANET, showing that line overhead and CPU overhead are both less than two percent, most nodes learn of an update within 100 ms, and the algorithm detects congestion and routes packets around congested areas.
---
paper_title: Improving OSPF dynamics on a broadcast LAN

paper_content:

In this paper, we analyze OSPF's interface state machine and propose modifications in order to reduce the time/processing requirements of the leader election process in a broadcast LAN environment. The proposed modifications are based on dynamic adjustment of wait time duration rather than using a static value.
---
paper_title: The New Routing Algorithm for the ARPANET

paper_content:

The new ARPANET routing algorithm is an improvement over the old procedure in that it uses fewer network resources, operates on more realistic estimates of network conditions, reacts faster to important network changes, and does not suffer from long-term loops or oscillations. In the new procedure, each node in the network maintains a database describing the complete network topology and the delays on all lines, and uses the database describing the network to generate a tree representing the minimum delay paths from a given root node to every other network node. Because the traffic in the network can be quite variable, each node periodically measures the delays along its outgoing lines and forwards this information to all other nodes. The delay information propagates quickly through the network so that all nodes can update their databases and continue to route traffic in a consistent and efficient manner. An extensive series of tests were conducted on the ARPANET, showing that line overhead and CPU overhead are both less than two percent, most nodes learn of an update within 100 ms, and the algorithm detects congestion and routes packets around congested areas.
---
paper_title: Multi-point Relaying Techniques with OSPF on Ad Hoc Networks

paper_content:

Incorporating multi-hop ad hoc wireless networks in theIP infrastructure is an effort to which a growing communityparticipates. One instance of such activity is theextension of the most widely deployed interior gatewayrouting protocol on the Internet, OSPF (Open Shortest PathFirst), for operation on Mobile Ad hoc Networks (MANETs).Such extension allows OSPF to work on heterogeneousnetworks encompassing both wired and wireless routers,which may self-organize as multi-hop wireless subnetworks,and be mobile. Three solutions have been proposed for thisextension, among which two based on techniques derivedfrom multi-point relaying (MPR). This paper analyzes thesetwo approaches and identifies some fundamental discussionitems that pertain to adapting OSPF mechanisms to multihopwireless networking, before concluding with a proposalfor a unique, merged solution based on this analysis.
---
paper_title: Improving OSPF dynamics on a broadcast LAN

paper_content:

In this paper, we analyze OSPF's interface state machine and propose modifications in order to reduce the time/processing requirements of the leader election process in a broadcast LAN environment. The proposed modifications are based on dynamic adjustment of wait time duration rather than using a static value.
---
paper_title: On the building blocks of quality of service in heterogeneous IP networks

paper_content:

After more than a decade of active research on Quality of Service in IP networks and the Internet, the majority of IP traffic relies on the conventional best-effort IP service model. Nevertheless, some QoS mechanisms are deployed in current networking infrastructures, while emerging applications pose QoS challenges. This survey brings into the foreground a broad range of research results on Quality of Service in IP-based networks. First, a justification of the need for QoS is provided, along with challenges stemming from the convergence of IP and wireless networks and the proliferation of QoS-demanding IP applications (such as VoIP). It is also emphasized that a global uniform end-to-end IP QoS solution is not realistic. Based on this remark, packet-level QoS mechanisms are classified as certain building blocks, each one fulfilling different objectives in certain parts of a heterogeneous IP network. This taxonomy, being in line with the ITU-T initiative toward a QoS architectural framework for IP networks, gives rise to a thorough presentation of QoS “building blocks,” as well as their associated mechanisms. This presentation is followed by an illustration of how the various building blocks are combined in the scope of modern IP networks. However, offering QoS in a large scale IP-based network demands that additional (i.e. non-packet-level) QoS mechanisms are deployed in some parts. Therefore, we also present prominent technologies and mechanisms devised to augment the QoS capabilities of access, wireless, and optical networks. We illustrate how these mechanisms boost end-to-end QoS solutions and reveal interworking issues with packet-level mechanisms.
---
paper_title: Voice over the internet: A tutorial discussing problems and solutions associated with alternative transport

paper_content:

This article provides a tutorial overview of voice over the Internet, examining the effects of moving voice traffic over the packet switched Internet and comparing this with the effects of moving voice over the more traditional circuit-switched telephone system. The emphasis of this document is on areas of concern to a backbone service provider implementing Voice over IP (VoIP). We begin by providing overviews of the Plain Old Telephone Service (POTS) and VoIP. We then discuss techniques service providers can use to help preserve service quality on their VoIP networks. Next, we briefly discuss Voice over ATM (VoATM) as an alternative to VoIP. Finally, we offer some conclusions.
---
paper_title: Optimal configuration of OSPF aggregates

paper_content:

Open shortest path first (OSPF) is a popular protocol for routing within an autonomous system (AS) domain. In this paper, we address the important practical problem of configuring OSPF aggregates to minimize the error in OSPF shortest path computations due to subnet aggregation. We first develop an optimal dynamic programming algorithm that, given an upper bound k on the number of aggregates to be advertised and a weight-assignment function for the aggregates, computes the k aggregates that result in the minimum cumulative error in the shortest path computations for all source-destination subnet pairs. Subsequently, we tackle the problem of assigning weights to OSPF aggregates such that the cumulative error in the computed shortest paths is minimized. We demonstrate that, while for certain special cases (e.g., unweighted cumulative error) efficient optimal algorithms for the weight-assignment problem can be devised, the general problem itself is /spl Nscr//spl Pscr/-hard. Consequently, we have to rely on search heuristics to solve the weight-assignment problem. To the best of our knowledge, our work is the first to address the algorithmic issues underlying the configuration of OSPF aggregates and to propose efficient configuration algorithms that are provably optimal for many practical scenarios.
---
paper_title: Why are we scared of SPF? IGP scaling and stability

paper_content:

The present invention relates to a process for preparing high purity inorganic higher oxides of the alkali and alkaline earth metals by subjecting the hydroxide of the alkali or alkaline earth metal to a radio frequency discharge sustained in oxygen. The invention is particularly adaptable to the production of high purity potassium superoxide (KO2) by subjecting potassium hydroxide to glow discharge sustained in oxygen under the pressure of about 0.75 to 1.00 torr.
---
paper_title: An efficient algorithm for OSPF subnet aggregation

paper_content:

Multiple addresses within an OSPF area can be aggregated and advertised together to other areas. This process is known as address aggregation and is used to reduce router computational overheads and memory requirements and to reduce the network bandwidth consumed by OSPF messages. The downside of address aggregation is that it leads to information loss and consequently sub-optimal (non-shortest path) routing of data packets. The resulting difference (path selection error) between the length of the actual forwarding path and the shortest path varies between different sources and destinations. This paper proves that the path selection error from any source to any destination can be bounded using only parameters describing the destination area. Based on this, the paper presents an efficient algorithm that generates the minimum number of aggregates subject to a maximum allowed path selection error. A major operational benefit of our algorithm is that network administrators can select aggregates for an area based solely on the topology of the area without worrying about remaining areas of the OSPF network. The other benefit is that the algorithm enables trade-offs between the number of aggregates and the bound on the path selection error. The paper also evaluates the algorithm's performance on random topologies. Our results show that in some cases, the algorithm is capable of reducing the number of aggregates by as much as 50% with only a relatively small introduction of maximum path selection error.
---
paper_title: Reverse path forwarding of broadcast packets

paper_content:

A broadcast packet is for delivery to all nodes of a network. Algorithms for accomplishing this delivery through a store-and-forward packet switching computer network include (1) transmission of separately addressed packets, (2) multidestination addressing, (3) hot potato forwarding, (4) spanning tree forwarding, and (5) source based forwarding. To this list of algorithms we add (6) reverse path forwarding, a broadcast routing method which exploits routing procedures and data structures already available for packet switching. Reverse path forwarding is a practical algorithm for broadcast routing in store-and-forward packet switching computer networks. The algorithm is described as being practical because it is not optimal according to metrics developed for its analysis in this paper, and also because it can be implemented in existing networks with less complexity than that required for the known alternatives.
---
paper_title: Topology Broadcast Algorithms

paper_content:

Abstract This paper describes efficient distributed algorithms to broadcast network topology to all nodes in a network. They also build minimum depth spanning trees, one rooted at each node. The broadcast of the topology takes place simultaneously with the building of the spanning trees, in a way that insures that each node receives information exactly once. The algorithms are extended to work in presence of link and node failures.
---
paper_title: Models for IP/MPLS routing performance: convergence, fast reroute, and QoS impact

paper_content:

We show how to model the black-holing and looping of traffic during an Interior Gateway Protocol (IGP) convergence event at an IP network and how to significantly improve both the convergence time and packet loss duration through IGP parameter tuning and algorithmic improvement. We also explore some congestion avoidance and congestion control algorithms that can significantly improve stability of networks in the face of occasional massive control message storms. Specifically we show the positive impacts of prioritizing Hello and Acknowledgement packets and slowing down LSA generation and retransmission generation on detecting congestion in the network. For some types of video, voice signaling and circuit emulation applications it is necessary to reduce traffic loss durations following a convergence event to below 100 ms and we explore that using Fast Reroute algorithms based on Multiprotocol Label Switching Traffic Engineering (MPLS-TE) that effectively bypasses IGP convergence. We explore the scalability of primary and backup MPLS-TE tunnels where MPLS-TE domain is in the backbone-only or edge-to-edge. We also show how much extra backbone resource is needed to support Fast Reroute and how can that be reduced by taking advantage of Constrained Shortest Path (CSPF) routing of MPLS-TE and by reserving less than 100% of primary tunnel bandwidth during Fast Reroute.
---
paper_title: Why are we scared of SPF? IGP scaling and stability

paper_content:

The present invention relates to a process for preparing high purity inorganic higher oxides of the alkali and alkaline earth metals by subjecting the hydroxide of the alkali or alkaline earth metal to a radio frequency discharge sustained in oxygen. The invention is particularly adaptable to the production of high purity potassium superoxide (KO2) by subjecting potassium hydroxide to glow discharge sustained in oxygen under the pressure of about 0.75 to 1.00 torr.
---
paper_title: Models for IP/MPLS routing performance: convergence, fast reroute, and QoS impact

paper_content:

We show how to model the black-holing and looping of traffic during an Interior Gateway Protocol (IGP) convergence event at an IP network and how to significantly improve both the convergence time and packet loss duration through IGP parameter tuning and algorithmic improvement. We also explore some congestion avoidance and congestion control algorithms that can significantly improve stability of networks in the face of occasional massive control message storms. Specifically we show the positive impacts of prioritizing Hello and Acknowledgement packets and slowing down LSA generation and retransmission generation on detecting congestion in the network. For some types of video, voice signaling and circuit emulation applications it is necessary to reduce traffic loss durations following a convergence event to below 100 ms and we explore that using Fast Reroute algorithms based on Multiprotocol Label Switching Traffic Engineering (MPLS-TE) that effectively bypasses IGP convergence. We explore the scalability of primary and backup MPLS-TE tunnels where MPLS-TE domain is in the backbone-only or edge-to-edge. We also show how much extra backbone resource is needed to support Fast Reroute and how can that be reduced by taking advantage of Constrained Shortest Path (CSPF) routing of MPLS-TE and by reserving less than 100% of primary tunnel bandwidth during Fast Reroute.
---
paper_title: Optimal configuration of OSPF aggregates

paper_content:

Open shortest path first (OSPF) is a popular protocol for routing within an autonomous system (AS) domain. In this paper, we address the important practical problem of configuring OSPF aggregates to minimize the error in OSPF shortest path computations due to subnet aggregation. We first develop an optimal dynamic programming algorithm that, given an upper bound k on the number of aggregates to be advertised and a weight-assignment function for the aggregates, computes the k aggregates that result in the minimum cumulative error in the shortest path computations for all source-destination subnet pairs. Subsequently, we tackle the problem of assigning weights to OSPF aggregates such that the cumulative error in the computed shortest paths is minimized. We demonstrate that, while for certain special cases (e.g., unweighted cumulative error) efficient optimal algorithms for the weight-assignment problem can be devised, the general problem itself is /spl Nscr//spl Pscr/-hard. Consequently, we have to rely on search heuristics to solve the weight-assignment problem. To the best of our knowledge, our work is the first to address the algorithmic issues underlying the configuration of OSPF aggregates and to propose efficient configuration algorithms that are provably optimal for many practical scenarios.
---
paper_title: OSPF: Anatomy of an Internet Routing Protocol

paper_content:

From the Publisher: ::: Written for TCP/IP network administrators, protocol designers, and network application developers, this book gives the most complete and practical view ever into the inner workings of Internet routing. The book focuses on OSPF (Open Shortest Path First), a common TCP/IP routing protocol that provides robust and efficient routing support in the most demanding Internet environments. A methodical and detailed description of the protocol is offered and OSPF's role within the wider context of a TCP/IP network is demonstrated. ::: Practical throughout, the book provides not only a theoretical description of Internet routing, but also a real-world look into how theory translates into practice. It shows how algorithms are implemented, and how the routing protocols function in a working network where transmission lines and routers routinely break down. ::: You will find clear explanations of such routing fundamentals as how a router forwards packets, IP addressing, CIDR (Classless Inter-Domain Routing), the routing table, Internet routing architecture, and the two main routing technologies: Distance Vector and link-state algorithms. OSPF is discussed in depth, with an examination of the rationale behind OSPF's design decisions and how it has evolved to keep pace with the rapidly changing Internet environment. OSPF topics covered by the book include the following: ::: OSPF areas and virtual links NBMA (Nonbroadcast multi-access) and Point-to-MultiPoint network segments OSPF configuration and management Interaction with other routing protocols OSPF cryptographic authentication OSPF protocol extensions, including the Demand Circuit extensions and the multicast extensions to OSPF (MOSPF) An OSPF FAQ ::: ::: IP multicast and multicast routing are also discussed. Methods for debugging routing problems are explained, including a catalog of available debugging tools. The book also offers side-by-side comparisons of all the unicast and multicast routing protocols currently in use in the Internet. ::: You will come away from this book with a sophisticated understanding of Internet routing and of the OSPF protocol in particular. Moreover, the book's practical focus will enable you to put this deeper understanding to work in your network environment.
---
paper_title: An efficient algorithm for OSPF subnet aggregation

paper_content:

Multiple addresses within an OSPF area can be aggregated and advertised together to other areas. This process is known as address aggregation and is used to reduce router computational overheads and memory requirements and to reduce the network bandwidth consumed by OSPF messages. The downside of address aggregation is that it leads to information loss and consequently sub-optimal (non-shortest path) routing of data packets. The resulting difference (path selection error) between the length of the actual forwarding path and the shortest path varies between different sources and destinations. This paper proves that the path selection error from any source to any destination can be bounded using only parameters describing the destination area. Based on this, the paper presents an efficient algorithm that generates the minimum number of aggregates subject to a maximum allowed path selection error. A major operational benefit of our algorithm is that network administrators can select aggregates for an area based solely on the topology of the area without worrying about remaining areas of the OSPF network. The other benefit is that the algorithm enables trade-offs between the number of aggregates and the bound on the path selection error. The paper also evaluates the algorithm's performance on random topologies. Our results show that in some cases, the algorithm is capable of reducing the number of aggregates by as much as 50% with only a relatively small introduction of maximum path selection error.
---
paper_title: Enhancing the network scalability of link-state routing protocols by reducing their flooding overhead

paper_content:

We consider scalability issues of routing protocols for large-scale networks. Link-state routing protocols play an important role in generalized multiprotocol label switching (GMPLS) networks based on photonic technologies as well as in conventional packet-based IP networks. The scalability of a link-state routing protocol mainly depends on the overhead of protocol-related messages, which are disseminated by flooding. We propose ways to reduce this overhead in link-state routing protocols such as OSPF and IS-IS, and also present extensions to OSPF that provide support for our techniques. The basic approach is to limit the sets of neighboring nodes in the flooding of link-state information, while maintaining reliability in the distribution of link-state information. We also report on extensive simulation to evaluate the performance of our algorithm in terms of reducing the flooding overhead. Our algorithm provides improved network scalability as well as efficient and reliable convergence of routing information.
---
paper_title: A survey of QoS routing solutions for mobile ad hoc networks

paper_content:

In mobile ad hoc networks (MANETs), the provision of quality of service (QoS) guarantees is much more challenging than in wireline networks, mainly due to node mobility, multihop communications, contention for channel access, and a lack of central coordination. QoS guarantees are required by most multimedia and other time- or error-sensitive applications. The difficulties in the provision of such guarantees have limited the usefulness of MANETs. However, in the last decade, much research attention has focused on providing QoS assurances in MANET protocols. The QoS routing protocol is an integral part of any QoS solution since its function is to ascertain which nodes, if any, are able to serve applications? requirements. Consequently, it also plays a crucial role in data session admission control. This document offers an up-to-date survey of most major contributions to the pool of QoS routing solutions for MANETs published in the period 1997?2006. We include a thorough overview of QoS routing metrics, resources, and factors affecting performance and classify the protocols found in the literature. We also summarize their operation and describe their interactions with the medium access control (MAC) protocol, where applicable. This provides the reader with insight into their differences and allows us to highlight trends in protocol design and identify areas for future research.
---
paper_title: QoS Routing Mechanisms and OSPF Extensions

paper_content:

This memo describes extensions to the OSPF [Moy98] protocol to support QoS routes. The focus of this document is on the algorithms used to compute QoS routes and on the necessary modifications to OSPF to support this function, e.g., the information needed, its format, how it is distributed, and how it is used by the QoS path selection process. Aspects related to how QoS routes are established and managed are also briefly discussed. The goal of this document is to identify a framework and possible approaches to allow deployment of QoS routing capabilities with the minimum possible impact to the existing routing infrastructure.
---
paper_title: Reverse path forwarding of broadcast packets

paper_content:

A broadcast packet is for delivery to all nodes of a network. Algorithms for accomplishing this delivery through a store-and-forward packet switching computer network include (1) transmission of separately addressed packets, (2) multidestination addressing, (3) hot potato forwarding, (4) spanning tree forwarding, and (5) source based forwarding. To this list of algorithms we add (6) reverse path forwarding, a broadcast routing method which exploits routing procedures and data structures already available for packet switching. Reverse path forwarding is a practical algorithm for broadcast routing in store-and-forward packet switching computer networks. The algorithm is described as being practical because it is not optimal according to metrics developed for its analysis in this paper, and also because it can be implemented in existing networks with less complexity than that required for the known alternatives.
---
paper_title: A reliable, efficient topology broadcast protocol for dynamic networks

paper_content:

We present, prove correctness for, and evaluate a protocol for the reliable broadcast of topology and link-state information in a multihop communication network with a dynamic topology, such as a wireless network with mobile nodes. The protocol is called topology broadcast based on reverse path forwarding (TBRPF), and uses the concept of reverse-path forwarding (RPF) to broadcast link-state updates in the reverse direction along the spanning tree formed by the minimum-hop paths from all nodes to the source of the update TBRPF uses the topology information received along the broadcast trees to compute the minimum-hop paths that form the trees themselves, and is the first topology broadcast protocol based on RPF with this property. The use of minimum-hop trees instead of shortest-path trees (based on link costs) results in less frequent changes to the broadcast trees and therefore less communication cost to maintain the trees. Simulations show that TBRPF achieves up to a 98% reduction in communication cost compared to flooding in a 20-node network.
---
paper_title: Topology Broadcast Algorithms

paper_content:

Abstract This paper describes efficient distributed algorithms to broadcast network topology to all nodes in a network. They also build minimum depth spanning trees, one rooted at each node. The broadcast of the topology takes place simultaneously with the building of the spanning trees, in a way that insures that each node receives information exactly once. The algorithms are extended to work in presence of link and node failures.
---
paper_title: Quality of service based routing: a performance perspective

paper_content:

Recent studies provide evidence that Quality of Service (QoS) routing can provide increased network utilization compared to routing that is not sensitive to QoS requirements of traffic. However, there are still strong concerns about the increased cost of QoS routing, both in terms of more complex and frequent computations and increased routing protocol overhead. The main goals of this paper are to study these two cost components, and propose solutions that achieve good routing performance with reduced processing cost. First, we identify the parameters that determine the protocol traffic overhead, namely (a) policy for triggering updates, (b) sensitivity of this policy, and (c) clamp down timers that limit the rate of updates. Using simulation, we study the relative significance of these factors and investigate the relationship between routing performance and the amount of update traffic. In addition, we explore a range of design options to reduce the processing cost of QoS routing algorithms, and study their effect on routing performance. Based on the conclusions of these studies, we develop extensions to the basic QoS routing, that can achieve good routing performance with limited update generation rates. The paper also addresses the impact on the results of a number of secondary factors such as topology, high level admission control, and characteristics of network traffic.
---
paper_title: Packet Switching in Radio Channels: Part I -- Carrier sense multiple-access modes and their throughput-delay characteristics

paper_content:

Radio communication is considered as a method for providing remote terminal access to computers. Digital byte streams from each terminal are partitioned into packets (blocks) and transmitted in a burst mode over a shared radio channel. When many terminals operate in this fashion, transmissions may conflict with and destroy each other. A means for controlling this is for the terminal to sense the presence of other transmissions; this leads to a new method for multiplexing in a packet radio environment: carrier sense multiple access (CSMA). Two protocols are described for CSMA and their throughput-delay characteristics are given. These results show the large advantage CSMA provides as compared to the random ALOHA access modes.
---
paper_title: Multi-point Relaying Techniques with OSPF on Ad Hoc Networks

paper_content:

Incorporating multi-hop ad hoc wireless networks in theIP infrastructure is an effort to which a growing communityparticipates. One instance of such activity is theextension of the most widely deployed interior gatewayrouting protocol on the Internet, OSPF (Open Shortest PathFirst), for operation on Mobile Ad hoc Networks (MANETs).Such extension allows OSPF to work on heterogeneousnetworks encompassing both wired and wireless routers,which may self-organize as multi-hop wireless subnetworks,and be mobile. Three solutions have been proposed for thisextension, among which two based on techniques derivedfrom multi-point relaying (MPR). This paper analyzes thesetwo approaches and identifies some fundamental discussionitems that pertain to adapting OSPF mechanisms to multihopwireless networking, before concluding with a proposalfor a unique, merged solution based on this analysis.
---
paper_title: Experience in black-box OSPF measurement

paper_content:

OSPF (Open Shortest Path First) is a widely used intra-domain routing protocol in IP networks. Internal processing delays in OSPF implementations impact the speed at which updates propagate in the network, the load on individual routers, and the time needed for both intra-domain and inter-domain routing to reconverge following an internal topology or a configuration change. An OSPF user, such as an Internet Service Provider, typically has no access to the software implementation, and no way to estimate these delays directly. In this paper, we present black-box methods (i.e., measurements that rely only on external observations) for estimating and trending delays for key internal tasks in OSPF: processing Link State Advertisements (LSAs), performing Shortest Path First calculations, updating the Forwarding Information Base, and flooding LSAs. Corresponding measurements are reported for production routers from Cisco Systems. To help validate the methodology, black-box and white-box (i.e., measurements that rely on internal instrumentation) are reported for a open source OSPF implementation, GateD.
---
paper_title: Introduction to Algorithms

paper_content:

From the Publisher: ::: The updated new edition of the classic Introduction to Algorithms is intended primarily for use in undergraduate or graduate courses in algorithms or data structures. Like the first edition,this text can also be used for self-study by technical professionals since it discusses engineering issues in algorithm design as well as the mathematical aspects. ::: In its new edition,Introduction to Algorithms continues to provide a comprehensive introduction to the modern study of algorithms. The revision has been updated to reflect changes in the years since the book's original publication. New chapters on the role of algorithms in computing and on probabilistic analysis and randomized algorithms have been included. Sections throughout the book have been rewritten for increased clarity,and material has been added wherever a fuller explanation has seemed useful or new information warrants expanded coverage. ::: As in the classic first edition,this new edition of Introduction to Algorithms presents a rich variety of algorithms and covers them in considerable depth while making their design and analysis accessible to all levels of readers. Further,the algorithms are presented in pseudocode to make the book easily accessible to students from all programming language backgrounds. ::: Each chapter presents an algorithm,a design technique,an application area,or a related topic. The chapters are not dependent on one another,so the instructor can organize his or her use of the book in the way that best suits the course's needs. Additionally,the new edition offers a 25% increase over the first edition in the number of problems,giving the book 155 problems and over 900 exercises thatreinforcethe concepts the students are learning.
---
paper_title: Semi-Dynamic Shortest Paths and Breadth-First Search in Digraphs

paper_content:

We show how to maintain a shortest path tree of a general directed graph G with unit edge weights and n vertices, during a sequence of edge deletions or a sequence of edge insertions, in O(n) amortized time per operation using linear space. Distance queries can be answered in constant time, while shortest path queries can be answered in time linear in the length of the retrieved path. These results are extended to the case of integer edge weights in [1,C], with a bound of O(Cn) amortized time per operation.
---
paper_title: The New Routing Algorithm for the ARPANET

paper_content:

The new ARPANET routing algorithm is an improvement over the old procedure in that it uses fewer network resources, operates on more realistic estimates of network conditions, reacts faster to important network changes, and does not suffer from long-term loops or oscillations. In the new procedure, each node in the network maintains a database describing the complete network topology and the delays on all lines, and uses the database describing the network to generate a tree representing the minimum delay paths from a given root node to every other network node. Because the traffic in the network can be quite variable, each node periodically measures the delays along its outgoing lines and forwards this information to all other nodes. The delay information propagates quickly through the network so that all nodes can update their databases and continue to route traffic in a consistent and efficient manner. An extensive series of tests were conducted on the ARPANET, showing that line overhead and CPU overhead are both less than two percent, most nodes learn of an update within 100 ms, and the algorithm detects congestion and routes packets around congested areas.
---
paper_title: Scheduling routing table calculations to achieve fast convergence in OSPF protocol

paper_content:

Fast convergence to topology changes is now a key requirement in routing infrastructures while reducing the routing protocol’s processing overhead continues to be as important as before. In this paper, we examine the problem of scheduling routing table updates in link state routing protocols. Commercial routers typically use a hold time based scheme to limit the number of routing table updates as new LSAs arrive at the router. The hold time schemes limit the number of routing table updates at the expense of increased delay in convergence to the new topology, which is clearly not acceptable any more. We analyze the performance of different hold time schemes and propose a new approach to schedule routing table updates, called LSA Correlation. Rather than using individual LSAs as triggers for routing table updates, LSA Correlation scheme correlates the information in the LSAs to identify the topology change that led to their generation. A routing table update is performed when a topology change has been identified. The analysis and simulation results presented in this paper suggest that the LSA Correlation scheme performs much better than the hold time based schemes for both isolated and large scale topology change scenarios.
---
paper_title: New dynamic SPT algorithm based on a ball-and-string model

paper_content:

A key functionality in today's widely used interior gateway routing protocols such as OSPF and IS-IS involves the computation of a shortest path tree (SPT). In many existing commercial routers, the computation of an SPT is done from scratch following changes in the link states of the network. As there may coexist multiple SPTs in a network with a set of given link states, such recomputation of an entire SPT not only is inefficient but also causes frequent unnecessary changes in the topology of an existing SPT and creates routing instability. This paper presents a new dynamic SPT algorithm that makes use of the structure of the previously computed SPT. This algorithm is derived by recasting the SPT problem into an optimization problem in a dual linear programming framework, which can also be interpreted using a ball-and-string model. In this model, the increase (or decrease) of an edge weight in the tree corresponds to the lengthening (or shortening) of a string. By stretching the strings until each node is attached to a tight string, the resulting topology of the model defines an (or multiple) SPT(s). By emulating the dynamics of the ball-and-string model, we can derive an efficient algorithm that propagates changes in distances to all affected nodes in a natural order and in a most economical way. Compared with existing results, our algorithm has the best-known performance in terms of computational complexity as well as minimum changes made to the topology of an SPT. Rigorous proofs for correctness of our algorithm and simulation results illustrating its complexity are also presented.
---
paper_title: Avoiding instability during graceful shutdown of OSPF

paper_content:

In this paper, we describe an enhancement to OSPF, called the IBB (I'll Be Back) capability, that enables other routers to use a router whose OSPF process is inactive for forwarding traffic for a certain period of time. The IBB capability can be used for avoiding route flaps that occur when the OSPF process is brought down in a router to facilitate protocol software upgrade, operating system upgrade, router ID change, AS and interface renumbering, etc. When the OSPF process in an IBB-capable router is inactive, it cannot adapt its forwarding table to reflect changes in network topology. This can lead to routing loops and/or black holes. We provide a detailed analysis of how and when loops or black holes are formed and propose solutions to prevent them. Using the GateD platform, we have developed an IBB extension to OSPF incorporating these solutions. Using this system in an experimental setup, we demonstrate that the overhead of the IBB extension is modest compared to the benefit it offers, and has good scaling behavior in terms of network size and the number of routers with inactive OSPF processes.
---
paper_title: An Incremental Algorithm for a Generalization of the Shortest-Path Problem

paper_content:

Thegrammar problem, a generalization of the single-source shortest-path problem introduced by D. E. Knuth (Inform. Process. Lett.6(1) (1977), 1?5) is to compute the minimum-cost derivation of a terminal string from each nonterminal of a given context-free grammar, with the cost of a derivation being suitably defined. This problem also subsumes the problem of finding optimal hyperpaths in directed hypergraphs (under varying optimization criteria) that has received attention recently. In this paper we present an incremental algorithm for a version of the grammar problem. As a special case of this algorithm we obtain an efficient incremental algorithm for the single-source shortest-path problem with positive edge lengths. The aspect of our work that distinguishes it from other work on the dynamic shortest-path problem is its ability to handle “multiple heterogeneous modifications”: between updates, the input graph is allowed to be restructured by an arbitrary mixture of edge insertions, edge deletions, and edge-length changes.
---
paper_title: Semi-Dynamic Shortest Paths and Breadth-First Search in Digraphs

paper_content:

We show how to maintain a shortest path tree of a general directed graph G with unit edge weights and n vertices, during a sequence of edge deletions or a sequence of edge insertions, in O(n) amortized time per operation using linear space. Distance queries can be answered in constant time, while shortest path queries can be answered in time linear in the length of the retrieved path. These results are extended to the case of integer edge weights in [1,C], with a bound of O(Cn) amortized time per operation.
---
paper_title: The New Routing Algorithm for the ARPANET

paper_content:

The new ARPANET routing algorithm is an improvement over the old procedure in that it uses fewer network resources, operates on more realistic estimates of network conditions, reacts faster to important network changes, and does not suffer from long-term loops or oscillations. In the new procedure, each node in the network maintains a database describing the complete network topology and the delays on all lines, and uses the database describing the network to generate a tree representing the minimum delay paths from a given root node to every other network node. Because the traffic in the network can be quite variable, each node periodically measures the delays along its outgoing lines and forwards this information to all other nodes. The delay information propagates quickly through the network so that all nodes can update their databases and continue to route traffic in a consistent and efficient manner. An extensive series of tests were conducted on the ARPANET, showing that line overhead and CPU overhead are both less than two percent, most nodes learn of an update within 100 ms, and the algorithm detects congestion and routes packets around congested areas.
---
paper_title: Avoiding instability during graceful shutdown of multiple OSPF routers

paper_content:

Many recent router architectures decouple the routing engine from the forwarding engine, allowing packet forwarding to continue even when the routing process is not active. This opens up the possibility of using the forwarding capability of a router even when its routing process is brought down for software upgrade or maintenance, thus avoiding the route flaps that normally occur when the routing process goes down. Unfortunately, current routing protocols, such as BGP, OSPF and IS-IS do not support such operation. In an earlier paper [1], we described an enhancement to OSPF, called the IBB (I'll Be Back) capability, that enables a router to continue forwarding packets while its routing process is inactive.When the OSPF process in an IBB-capable router is inactive, it cannot adapt its forwarding table to reflect changes in network topology. This can lead to routing loops and/or black holes. In this paper, we focus on the loop problem and provide a detailed analysis of how and when loops are formed and propose solutions to prevent them. We develop two necessary conditions for the formation of routing loops in the general case when multiple routers are inactive. These conditions can easily be checked by the neighbors of the inactive routers. Simulations on several network topologies showed that checking the two conditions together signaled a loop in most cases only when a loop actually existed.
---
paper_title: New dynamic SPT algorithm based on a ball-and-string model

paper_content:

A key functionality in today's widely used interior gateway routing protocols such as OSPF and IS-IS involves the computation of a shortest path tree (SPT). In many existing commercial routers, the computation of an SPT is done from scratch following changes in the link states of the network. As there may coexist multiple SPTs in a network with a set of given link states, such recomputation of an entire SPT not only is inefficient but also causes frequent unnecessary changes in the topology of an existing SPT and creates routing instability. This paper presents a new dynamic SPT algorithm that makes use of the structure of the previously computed SPT. This algorithm is derived by recasting the SPT problem into an optimization problem in a dual linear programming framework, which can also be interpreted using a ball-and-string model. In this model, the increase (or decrease) of an edge weight in the tree corresponds to the lengthening (or shortening) of a string. By stretching the strings until each node is attached to a tight string, the resulting topology of the model defines an (or multiple) SPT(s). By emulating the dynamics of the ball-and-string model, we can derive an efficient algorithm that propagates changes in distances to all affected nodes in a natural order and in a most economical way. Compared with existing results, our algorithm has the best-known performance in terms of computational complexity as well as minimum changes made to the topology of an SPT. Rigorous proofs for correctness of our algorithm and simulation results illustrating its complexity are also presented.
---
paper_title: An overview of routing optimization for internet traffic engineering

paper_content:

Traffic engineering is an important mechanism for Internet network providers seeking to optimize network performance and traffic delivery. Routing optimization plays a key role in traffic engineering, finding efficient routes so as to achieve the desired network performance. In this survey we review Internet traffic engineering from the perspective of routing optimization. A taxonomy of routing algorithms in the literature is provided, dating from the advent of the TE concept in the late 1990s. We classify the algorithms into multiple dimensions: unicast/multicast, intra-/inter- domain, IP-/MPLS-based and offline/online TE schemes. In addition, we investigate some important traffic engineering issues, including robustness, TE interactions, and interoperability with overlay selfish routing. In addition to a review of existing solutions, we also point out some challenges in TE operation and important issues that are worthy of investigation in future research activities.
---
paper_title: Constraint-Based Routing in the Internet: Basic Principles and Recent Research

paper_content:

Novel routing paradigms based on policies, quality of service (QoS) requirements, and packet content have been proposed for the Internet over the last decade. Constraint-based routing algorithms select a routing path satisfying constraints that are either administrative-oriented (policy routing) or service-oriented (QoS routing). The routes, in addition to satisfying constraints, are selected to reduce costs, balance network load, or increase security. In this article, we discuss several constraint-based routing approaches and explain their requirements, complexity, and recent research proposals. In addition, we illustrate how these approaches can be integrated with Internet label switching and QoS architectures. We also discuss examples of application-level routing techniques used in today's Internet.
---
paper_title: A survey of IP and multiprotocol label switching fast reroute schemes

paper_content:

One of the desirable features of any network is its ability to keep services running despite a link or node failure. This ability is usually referred to as network resilience and has become a key demand from service providers. Resilient networks recover from a failure by repairing themselves automatically by diverting traffic from the failed part of the network to another portion of the network. This traffic diversion process should be fast enough to ensure that the interruption of service due to a link or node failure is either unnoticeable or as small as possible. The new path taken by a diverted traffic can be computed at the time a failure occurs through a procedure called rerouting. Alternatively the path can be computed before a failure occurs through a procedure called fast reroute. Much attention is currently being paid to fast reroute because service providers who are used to the 50-ms failure recovery time associated with SONET networks are demanding the same feature from IP and MPLS networks. While this requirement can easily be met in SONET because it operates at the physical layer, it is not easily met in IP and MPLS networks that operate above the physical layer. However, over the last few years, several schemes have been proposed for accomplishing 50-ms fast reroutes for IP and MPLS networks. The purpose of this paper is to provide a survey of the IP fast reroute and MPLS fast reroute schemes that have been proposed.
---
paper_title: IP fast rerouting for single-link/node failure recovery

paper_content:

Failure recovery in IP networks is critical to high quality service provisioning. The main challenge is how to achieve fast recovery without introducing high complexity and resource usage. Today’s networks mainly use route recalculation and lower layer protection. However, route recalculation could take as long as seconds to complete; while lower layer protection usually requires considerable bandwidth redundancy. We present two fast rerouting algorithms to achieve recovery from single-link and single-node failures, respectively. The idea is to calculated backup paths in advance. When a failure is detected, the affected packets are immediately forwarded through backup paths to shorten the service disruption. This paper answers the following questions: 1. How to find backup paths? 2. How to coordinate routers during the rerouting without explicit signaling? 3. How to realize distributed implementation? The schemes react to failures very fast because there are no calculations on the fly. They are also cost efficient because no bandwidth reservation is required. Our schemes guarantee 100% failure recovery without any assumption on the primary paths. Simulations show that our schemes yield comparable performance to shortest path route recalculation. This work illuminates the possibility of using pure IP layer solutions to build highly survivable yet cost-efficient networks.
---
paper_title: Disruption Free Topology Reconfiguration in OSPF Networks

paper_content:

A few modifications to software and/or hardware of routers have been proposed recently to avoid the transient micro loops that can occur during the convergence of link-state interior gateway protocols like IS-IS and OSPF. We1 propose in this paper a technique that does not require modifications to ISIS and OSPF, and that can be applied now by ISPs. Roughly, in the case of a manual modification of the state of a link, we progressively change the metric associated with this link to reach the required modification by ensuring that each step of the progression will be loop-free. The number of changes that are applied to a link to reach the targeted state by ensuring the transient consistency of the forwarding inside the network is minimized. Analysis performed on real regional and tier-1 ISP topologies show that the number of required transient changes is small. The solution can be applied in the case of link metric updates, manual set up, and shut down of links.
---
paper_title: OSPF: Anatomy of an Internet Routing Protocol

paper_content:

From the Publisher: ::: Written for TCP/IP network administrators, protocol designers, and network application developers, this book gives the most complete and practical view ever into the inner workings of Internet routing. The book focuses on OSPF (Open Shortest Path First), a common TCP/IP routing protocol that provides robust and efficient routing support in the most demanding Internet environments. A methodical and detailed description of the protocol is offered and OSPF's role within the wider context of a TCP/IP network is demonstrated. ::: Practical throughout, the book provides not only a theoretical description of Internet routing, but also a real-world look into how theory translates into practice. It shows how algorithms are implemented, and how the routing protocols function in a working network where transmission lines and routers routinely break down. ::: You will find clear explanations of such routing fundamentals as how a router forwards packets, IP addressing, CIDR (Classless Inter-Domain Routing), the routing table, Internet routing architecture, and the two main routing technologies: Distance Vector and link-state algorithms. OSPF is discussed in depth, with an examination of the rationale behind OSPF's design decisions and how it has evolved to keep pace with the rapidly changing Internet environment. OSPF topics covered by the book include the following: ::: OSPF areas and virtual links NBMA (Nonbroadcast multi-access) and Point-to-MultiPoint network segments OSPF configuration and management Interaction with other routing protocols OSPF cryptographic authentication OSPF protocol extensions, including the Demand Circuit extensions and the multicast extensions to OSPF (MOSPF) An OSPF FAQ ::: ::: IP multicast and multicast routing are also discussed. Methods for debugging routing problems are explained, including a catalog of available debugging tools. The book also offers side-by-side comparisons of all the unicast and multicast routing protocols currently in use in the Internet. ::: You will come away from this book with a sophisticated understanding of Internet routing and of the OSPF protocol in particular. Moreover, the book's practical focus will enable you to put this deeper understanding to work in your network environment.
---
paper_title: IGP Link Weight Assignment for Transient Link Failures

paper_content:

Intra-domain routing in IP backbone networks relies on link-state protocols such as IS-IS or OSPF. These protocols associate a weight (or cost) with each network link, and compute traffic routes based on these weight. However, proposed methods for selecting link weights largely ignore the issue of failures which arise as part of everyday network operations (maintenance, accidental, etc.). Changing link weights during a short-lived failure is impractical. However such failures are frequent enough to impact network performance. We propose a Tabu-search heuristic for choosing link weights which allow a network to function almost optimally during short link failures. The heuristic takes into account possible link failure scearios when choosing weights, thereby mitigating the effect of such failures. We find that the weights chosen by the heuristic can reduce link overload during transient link failures by as much as 40% at the cost of a small performance degradation in the absence of failures (10%).
---
paper_title: Relaxed multiple routing configurations: IP fast reroute for single and correlated failures

paper_content:

Multi-topology routing is an increasingly popular IP network management concept that allows transport of different traffic types over disjoint network paths. The concept is of particular interest for implementation of IP fast reroute (IP FRR). The authors have previously proposed an IP FRR scheme based on multi-topology routing called multiple routing configurations (MRC). MRC supports guaranteed, instantaneous recovery from any single link or node failure in biconnected networks as well as from many combined failures, provided sufficient bandwidth on the surviving links. Furthermore, in MRC different failures result in routing over different network topologies, which gives a good control of the traffic distribution in the networks after a failure. In this paper we present two contributions. First we define an enhanced IP FRR scheme which we call "relaxed MRC" (rMRC). Through experiments we demonstrate that rMRC is an improvement over MRC in all important aspects. Resource utilization in the presence of failures is significantly better, both in terms of paths lengths and in terms of load distribution between the links. The requirement to internal state in the routers is reduced as rMRC requires fewer backup topologies to provide the same degree of protection. In addition to this, the preprocessing needed to generate the backup topologies is simplified. The second contribution is an extension of rMRC that can provide fast reroute in the presence of multiple correlated failures. Our evaluations demonstrate only a small penalty in path lengths and in the number of backup topologies required.
---
paper_title: Making IGP Routing Robust to Link Failures

paper_content:

An important requirement of a robust traffic engineering solution is insensitivity to changes, be they in the form of traffic fluctuations or changes in the network topology because of link failures. In this paper we focus on developing a fast and effective technique to compute traffic engineering solutions for Interior Gateway Protocol (IGPs) environments that are robust to link failures in the logical topology. The routing and packet forwarding decisions for IGPs is primarily governed by link weights. Our focus is on computing a single set of link weights for a traffic engineering instance that performs well over all single logical link failures. Such types of failures, although usually not long lasting, of the order of tens of minutes, can occur with high enough frequency, of the order of several a day, to significantly affect network performance. The relatively short duration of such failures coupled with issues of computational complexity and convergence time due to the size of current day networks discourage adaptive reactions to such events. Consequently, it is desirable to a priori compute a routing solution that performs well in all such scenarios. Through computational evaluations we demonstrate that our technique yields link weights that perform well over all single link failures and also scales well, in terms of computational complexity, with the size of the network.
---
paper_title: Evaluation of IP Fast Reroute Proposals

paper_content:

With the increasing demand for low-latency applications in the Internet, the slow convergence of the existing routing protocols is a growing concern. A number of IP fast reroute mechanisms have been developed by the IETF to address the issue. The goal of the IPFRR mechanisms is to activate alternate routing paths which avoid micro loops under node or link failures. In this paper we present a comprehensive analysis of these proposals by evaluating their coverage for a variety of inferred and synthetic ISP topologies.
---
paper_title: Multi-Topology (MT) Routing in OSPF

paper_content:

This draft describes an extension to OSPF in order to define ::: independent IP topologies called Multi-Topologies (MTs). The MT ::: extension can be used for computing different paths for unicast ::: traffic, multicast traffic, different classes of service based on ::: flexible criteria, or an in-band network management topology. ::: [M-ISIS] describes a similar mechanism for ISIS. An optional ::: extension to exclude selected links from the default topology is also ::: described.
---
paper_title: A Survey for Open Shortest Path First Weight Setting (OSPFWS) Problem

paper_content:

Open shortest path first (OSPF) is the most commonly used intera-domain routing protocol. It used to select the paths along which traffic is routed within autonomous systems (AS), OSPF calculates routes as follow. Each link is assigned weights by operator. Each node in the autonomous system computes shortest paths and creates destination tables used to route data to next node on the path to its destination. Shortest paths are selected according to path cost. Path cost is determined by sum of its weight links. Then link weights determine the shortest paths, in which turn determine the routing of network traffic flow. OSPF weights setting problem is to find a set of OSPF weights that optimizes network performance. OSPF weights setting problem is an NP-hard problem. In the last couple of years, various algorithms for OSPF weights setting problem have been proposed. In this paper, we present a survey of OSPF weights setting algorithms and compare their performances.
---
paper_title: A Framework for Loop-free Convergence

paper_content:

This draft describes mechanisms that may be used to prevent or to ::: suppress the formation of micro-loops when an IP or MPLS network ::: undergoes topology change due to failure, repair or management action.
---
paper_title: Internet traffic engineering by optimizing OSPF weights

paper_content:

Open shortest path first (OSPF) is the most commonly used intra-domain Internet routing protocol. Traffic flow is routed along shortest paths, splitting flow at nodes where several outgoing links are on shortest paths to the destination. The weights of the links, and thereby the shortest path routes, can be changed by the network operator. The weights could be set proportional to their physical distances, but often the main goal is to avoid congestion, i.e., overloading of links, and the standard heuristic recommended by Cisco is to make the weight of a link inversely proportional to its capacity. Our starting point was a proposed AT&T WorldNet backbone with demands projected from previous measurements. The desire was to optimize the weight setting based on the projected demands. We showed that optimizing the weight settings for a given set of demands is NP-hard, so we resorted to a local search heuristic. Surprisingly it turned out that for the proposed AT&T WorldNet backbone, we found weight settings that performed within a few percent from that of the optimal general routing where the flow for each demand is optimally distributed over all paths between source and destination. This contrasts the common belief that OSPF routing leads to congestion and it shows that for the network and demand matrix studied we cannot get a substantially better load balancing by switching to the proposed more flexible multi-protocol label switching (MPLS) technologies. Our techniques were also tested on synthetic internetworks, based on a model of Zegura et al., (1996), for which we did not always get quite as close to the optimal general routing.
---

Title: Improving Convergence Speed and Scalability in OSPF: A Survey

Section 1: INTRODUCTION
Description 1: This section provides an overview of the OSPF protocol, its history, challenges, and the motivation for improving its convergence speed and scalability.

Section 2: CONVERGENCE TO A TOPOLOGY CHANGE IN OSPF: AN OVERVIEW
Description 2: This section outlines the general process of OSPF convergence following a topology change, divided into multiple steps.

Section 3: FASTER FAILURE DETECTION IN OSPF
Description 3: This section describes the default failure detection mechanisms in OSPF, and recent proposals for speeding up failure detection.

Section 4: FASTER AND FEWER ADJACENCY ESTABLISHMENTS
Description 4: This section covers proposed enhancements to the process of establishing adjacency between routers and reducing the number of required adjacencies, especially in broadcast/NBMA LANs and MANETs.

Section 5: LSA GENERATION AND FLOODING
Description 5: This section discusses the mechanisms and optimizations related to the generation and flooding of link state advertisements (LSAs) in OSPF.

Section 6: ROUTING TABLE CALCULATION
Description 6: This section elaborates on the processes involved in routing table calculations in OSPF, including mechanisms to avoid frequent recalculations and dynamic shortest path tree algorithms.

Section 7: GRACEFUL RESTART
Description 7: This section explains the concept of graceful restart in OSPF, allowing planned control plane reboots without affecting network-wide routing.

Section 8: PROACTIVE APPROACHES TO FAILURE RECOVERY
Description 8: This section details proactive mechanisms for failure recovery, specifically MPLS fast reroute and IP fast reroute.

Section 9: CONCLUSION
Description 9: This section summarizes the survey, discusses the challenges and recent improvements in OSPF, and suggests directions for future research.