Computer Networks Dr. Jorge A. Cobb Stable Internet Routing Without Global Coordination Lixin Gao, & Jennifer Rexford,2 Problem l Too much overhead to maintain path histories (dynamic execution solution) l Difficult to gather all policies and check for cycles in dispute graphs l Can we select some practical guidelines? • If the guidelines are followed, the system is stable (always reaches a steady state) l Their approach: hierarchies • You avoid circular conflicts by introducing hierarchies of nodes • Policies are based on the hierarchy3 Background l We need some background before presenting the technique l In particular, the difference between export, import, and route selection policies.4 BGP Import, Export, Path Selection l There are three types of policies: • Import Policy: of the paths offered by my neighbors, which ones will I allow? (i.e. “import” the path) • Path Selection: given the paths offered by my neighbors which satisfy my import policy, which one do I like the best? • Export Policy: given my current path, will I tell my neighbor of this path or tell my neighbor that I have no path? (i.e., “export” the path) l Note: in the Griffin paper, import/export policy was not explicit, only “list of allowed paths” was given. • A path is allowed in an “SPP instance” only if it exists in the export policy of my neighbour and in my import policy5 Neighbor Relationships l For each neighbour B of AS A, we have one of the following three relationships: • B is the service provider of A: in this case, B is the “access point” (or perhaps one of several) over which A accesses the rest of the Internet • B is a customer of A: in this case, A is the service provider or B • B is a peer of A: neither is a provider or customer of the other. They are simply “peers” who help each other.6 AS relationship graph Provider-to-customer edges must form a directed acyclic graph (DAG)7 Export policy restrictions l Convergence is assured by restricting the export policies • i.e., you can’t tell everything to everyone8 Export policy restrictions - providers l Exporting to a provider: In exchanging routing information with a provider: • An AS can only export its networks and the routes of its customers. • However, it can not export routes learned from other providers or peers. • That is, an AS does not provide transit services for its provider. Exported path to destination Provider-to-customer relationship9 Export policy restrictions - peers l Exporting to a peer: In exchanging routing information with a peer: • An AS can only export its networks and the routes of its customers • However, it can not export the routes learned from other providers or peers. • That is, an AS does not provide transit services for its peers. Exported path to destination Provider-to-customer relationship10 In Summary (previous rules) l A node can export to its peer and to its provider only paths that it has learned from its customers Exported path to destination Provider-to-customer relationship11 Exporting to peers or providers l I say that a route r is a “cust_only” route if for every pair of adjacent nodes (A,B) in the route, A is a service provider of B l Lemma 0 : a node can only export a “cust_only” path to its peers and service providers g h l What can h export to its provider g or its peer x? l only what it receives from a customer (i.e. i) l What can i export to its provider h? l only what it receives from its customer (i.e. j) l What can j export to its provider i? l only what it receives from its customer … i j x12 Export policy restrictions - customers l Exporting to a customer: In exchanging routing information with a customer: • An AS can export everything: its customer routes, as well as routes learned from its providers and peers. • That is, an AS does provide transit services for its customers. Exported path to destination Provider-to-customer relationship13 Exporting to customers l Lemma 1: A path exported by a provider P to a customer C can only be subsequently exported by providers to their customers (exported via provider à customer edges). • If g exports the path to h, h cannot export it to y nor to x • h can export to y or x only a path via a customer • You can repeat the argument between h and i, etc. g h i j x y14 Still not good enough l The following system, even though it satisfies the export policies, is not safe l Every node starts directly to zero l Then choose the neighbour clockwise l Have we seen this one before? 1 0 3 2 (1 3 0) (1 0) (3 2 0) (3 0) (2 1 0) (2 0)15 Additional Policy Requirements Must prefer customer paths over those of peers and providers16 The end result l Theorem 1: For a BGP system that has only customer–provider and peer-to-peer relationships (no backup links), if all ASms follow guideline A, and the provider-customer graph is acyclic, then the BGP system is inherently safe (always converges) l We will show that the system cannot have a dispute wheel.17 Proof l Let Qi = eQ’i, and Ri-1 = R’i-1e’, where e and e’ are edges. u1 u2 u(i+1) uk Q0 Q1 Q2 Qk Q(i+1) Qi R0 R1 Ri Rk 0 u0 ui Qi Ri-1 0 e' e ui-118 Proof (continued) l Assume e is provider-customer (ui is provider of wi). l Since ui prefers customer paths, and from the wheel λ(Qi) < λ(RiQi+1) • This implies the first hop in Ri is via a customer x. • From lemma 0, the entire path RiQi+1 is a cust_only path. • In particular, first edge in Qi+1 is a provider-customer edge ui Qi Ri-1 0 e' e wi Ri ui+1 Qi+1 l Repeat the argument at ui+1, and you have that all edges on the rim of the wheel are provider-customer edges (actually, all edges in the entire wheel J ) l This is not possible (provider-customer graph is acyclic) x19 Proof (continued, remaining cases) l e CANNOT be provider-customer l Consider e’ • If e’ is peer-to-peer, • Because wi is not a customer of of ui (e is not provider-customer), it is illegal for ui to export Qi to its peer vi-1. • If e’ is provider-customer edge • Same thing. • If e’ is a customer-provider edge (This is the only case remaining!) • vi-1 is
View Full Document
Unlocking...