Project topics and materials
Get Complete Project Material File(s) Now! »
Current inter-domain routing protocol
BGP (Border Gateway protocol) is currently the inter-domain routing protocol.
As illustrated in Figure 1.2 a router running BGP first receives routing information (aka BGP updates) from neighbors, could they be external or internal. These updates are filtered at the entrance (e.g., to avoid loop) and stored in the Routing Information Base (RIB) which serve as BGP update cache (i.e., information stored but not always used). The RIB may contain several routes toward a single destination. The router then compute the best route thanks to the BGP decision process and put this route into the routing table of the router (called FIB: Forwarding Information Base). From that point, if some data packets are to be forwarded to this destination, only the route inserted in the routing table is used. Alternate routes cached in the RIB are not taken into account for packet forwarding. Then the routes contained in the routing table are potentially sent to neighbors.
Motivations for Inter-Domain Multipath
The use of internet is very diverse. All the flows that cross it have not the same properties and do not need the same path characteristics. For instance on one hand Voice Over IP sends very few amount of data but requires very small propagation delays and very low jitter. On the other hand downloading a file may require the sending of an important quantity of data while not requiring a small propagation delay or jitter, compared to other uses. A lot of other application flows (e.g., mail, chat, streaming, P2P… [12]) require different profiles which are commonly expressed with criteria like delay, jitter, bandwidth and packet loss rate [13].
Even if there exists a lot of different application needs, a global over-dimensioning of network service provider capacities may fit all these needs. Nevertheless overcapacity is not generally adopted. Consequently a lot of congestion points exist in the internet, and half of them are located in inter-domain exchange points [11].
Bypassing these congestion points would probably make the path length increase, which increases the propagation delay, or go through links which price are higher. Path characteristics differ a lot and a path which is good for one application could be bad for another.
Beside the technical characteristics of flows and their adequacy with the paths, some specific flows are critical, in the sense that they should not drop for a long time, even if the underlying path fails. Such flows require at least a second usable path which is to be used if the first one fails (i.e., a disjoint path). Paths are currently not well protected by the convergence of BGP. For instance, path exploration can make the Internet converge in several minutes [48, 49], which is a too high convergence delay, even for the uses that do not specifically require high reliability (e.g., web browsing).
Incentive and cost effectiveness
By “incentive” we mean that an AS must be readily willing to adopt the nove architecture. The first domain that adopts it must be able to benefit from it immediately. In the case of inter-domain path diversity, early adopters must benefit from the routing diversity they already receive thanks to multiple eBGP peerings with neighbor domains, which is normally truncated by the BGP selection. Furthermore, a non multi-path domain connected to multi-path domains must easily identify value in migrating to the new solution. Firstly, it should benefit from the diversity it already receives (as previously described for early adopters), and secondly, it should even further increase its utility by setting up muti-path neighboring relationships with other domains.
“Cost effectiveness” is closely related to the incentive. It means that, despite the adoption of a new technology represents a cost, it must allow for either a higher revenue increase or a higher cost saving.
Table of contents :
1 Introduction
1.1 The Internet
1.1.1 The Current Single Route Internet
1.1.2 Current inter-domain routing protocol
1.1.3 Internet policies
1.1.4 Potential diversity
1.2 Motivations for Inter-Domain Multipath
1.3 Solution Requirements
1.3.1 Provided services
1.3.2 Control plane changes
1.3.3 Data plane changes
1.3.4 Backward compatibility
1.3.5 Incremental deployability
1.3.6 Incentive and cost effectiveness
1.3.7 Reliance on existing technologies
1.3.8 Respecting Internet paradigms
1.3.9 Respecting NSPs’ commercial information
1.3.10 Scalability
1.4 Related Work
1.4.1 Multipath BGP
1.4.2 Source selectable path diversity via routing deflections
1.4.3 Path Splicing
1.4.4 BGP Add-Path
1.4.5 D-BGP and B-BGP
1.4.6 Reliable interdomain routing through multiple complementary routing processes
1.4.7 R-BGP: Staying Connected In a Connected World
1.4.8 MIRO: Multi-path interdomain routing
1.4.9 NIRA: A New Inter-Domain Routing Architecture
1.4.10 YAMR: Yet Another Multipath Routing
1.4.11 Pathlet routing
1.5 Contributions of this thesis
2 Enabling the locally received path diversity
2.1 Introduction
2.1.1 Locator/ID Separation Protocol (LISP)
2.2 Architecture
2.2.1 Description of the architecture
2.2.2 Control-plane
2.2.3 Traffic forwarding
2.3 Deployment Use Cases
2.3.1 Stub’s local diversity usage
2.3.2 Stub’s provider diversity usage
2.3.3 Route Selection Process Policies
2.4 Evaluation Methodology
2.4.1 Getting eBGP routes
2.4.2 Limitations of Route Views data
2.4.3 Evaluation process
2.5 Results
2.5.1 Examples of allowed path diversity
2.5.2 Churn: the cost of path diversity
2.6 Discussion
2.6.1 Impact of architectural choices
2.6.2 Potential error due to the lack of BGP feeds
2.6.3 Potential error due to the lack of BGP relationship knowledge
2.6.4 Outcomes
2.7 Conclusion
3 IDRD: Enabling Inter-Domain Route Diversity
3.1 Introduction
3.2 Architecture for route diversity
3.2.1 IDRD Data Plane
3.2.2 IDRD Control Plane
3.2.3 An MPLS-based architecture
3.2.4 A functional representation of the architecture
3.3 Relaxation of ISP policies
3.3.1 Need for stability
3.3.2 Stability verification models and definitions
3.3.3 Proof of stability
3.4 Evaluation
3.4.1 Evaluation process
3.4.2 Results
3.5 Conclusions
4 Wide path diversity propagation: scalability analysis of path identification schemes
4.1 Introduction
4.2 Path identification:
4.2.1 The need for identification
4.2.2 Identifying what and where ?
4.2.3 Path identification challenges
4.2.4 Local ways of identification
4.2.5 Where can the scalability issue be addressed?
4.3 Analysis of specific path-ID schemes
4.3.1 Stub-to-Stub Path-ID use:
4.3.2 Stub-to-Transit Path-ID use:
4.3.3 Source label stacking:
4.4 Worst case evaluation: Impact on the potential bottlenecks
4.4.1 Results
4.4.2 Intermediate conclusion
4.5 What about filtering ?
4.5.1 FEC assumption
4.5.2 FIB assumption
4.6 Conclusion
5 Auction-type framework for selling inter-domain paths
5.1 Introduction
5.2 Background
5.2.1 Context
5.2.2 Inter-domain constraints
5.3 Framework required properties
5.3.1 Notations
5.3.2 Properties
5.3.3 On the difficulty to both being truthful and form the grand coalition
5.3.4 On the difficulty to both being truthful and maximize the seller’s revenue
5.3.5 Related work
5.4 Framework
5.4.1 Computation process
5.4.2 How to rank bids fairly?
5.4.3 Consequences on bids
5.5 Forming the grand coalition
5.5.1 Core concept and auctions
5.5.2 Incentive to form the grand coalition
5.6 An example of payment function
5.6.1 Payment function presentation
5.6.2 Bidding concatenation
5.6.3 Telling the truth
5.6.4 Formation of the grand coalition
5.7 Evaluation
5.7.1 Computation complexity
5.7.2 Relation between maximum revenue point and number of goods
5.7.3 Ratio between revenue and valuations
5.8 Conclusion
6 Conclusion
6.1 Summary
6.2 Further work
6.2.1 Architecture test-lab
6.2.2 Software Defined Networking
6.2.3 Path auction extension
6.2.4 What about the end host ?
6.2.5 CDNs and cloud
Index
