Transcript Slides
Routing NextGen • What are the problems today (inter-domain): – Lack of route selection • One size fits all routing, usually a single best-path to a destination • Selection is limited only to the edge, first hop ISP • Bad for competition between ISPs • Can not do QoS easily – Architecture/implementation • Many complex computations happen in multiple places • How to deal with overlays from the infrastructure standpoint – Traffic engineering • Tussle between overlays and underlays • Overlays are hard to get right and scale • Adaptive traffic engineering How do I change things? • Revolutionary changes – Throw away BGP and replace with something better • Is it is feasible? • Evolutionary changes – Come up with something that can coexist with BGP and can gradually replace it – Extend BGP mechanisms • But many things in BGP are already broken • Add hacks to BGP – Until it breaks completely • Bypass the whole thing – Overlay networks – Can be inefficient and may not scale to the whole Internet size Offering more route selection • Technical problems – End nodes must discover potential routes • Scalability? – Must have some feedback about the QoS on them • Scalability? – Must be able to send their packets over one of them • Performance of source routing? • Per packet overheads for the source route? • Political problems – Will ISPs accept loosing control of their network – How to reconcile end-node route selection with ISP policy constraints Brute force • This is not a new idea – NIMROD (It May Run One Day) • Well, it didn’t • Discover the map of the whole internet – Will it scale? – Can do with a smaller more abstract map • Hierarchical aggregation • IP source routing for selecting different routes – This will not work ok, will need some kind of support from the network for tunneling • Use active monitoring to determine which routes are good – This will not scale to large sizes – It is also optional Better approaches • New architectures • Extend BGP • Overlays – Move the problem to a higher layer – Can be inefficient at the network layer – End-host overlays are usually very bandwidth limited • Active networks – Program routers to do whatever is needed – Security and performance is a problem • We have seen some – RON – Detour: use another node as a detour NIRA • Throw away BGP • Use AS level routes – As most other proposals do, nothing else scales in the inter-domain • Route discovery – Flood AS connectivity information based on policy constraints using a new protocol (TIPP) • Well, more complexity – End nodes can build a topology map of their parents providers towards the core • Route QoS discovery – Use TIPP to send QoS information for a part of the route – End node may have incomplete or inaccurate information • Source gets an error and tries another route, takes a bit too long • Source routing – Take advantage of the hierarchy in the internet – Select a route as a combination of source and destination address – Forwarding must consider source address now MIRO • Extend BGP to understand multiple paths – Focus: achieve this under ISP control – Evolutionary: still use BGP • AS a can ask its neighbor AS b for more paths if it is not happy with the single path it gets – Can specify some policy for the additional path(s) • E.g avoid ISP x • Use IP-in-IP tunneling to force traffic over the alternate paths – Tunnels need to be managed, setup, repaired etc… – Its starts getting a bit too complex • No attempt for getting QoS information for each alternate route Routing as a service (ROSE) • Separation between forwarding infrastructure and path computation • Forwarding infrastructure is an overlay – Of nodes inside the ISPs – ISPs have control of how traffic is routed on their networks – Each node monitors performance of its connections with its neighbors • Loss rate, available b/w, latency • Path computation, done by ROSE using the QoS information – In order to scale decompose the network into domains – Paths are computed by servers in each domain – Servers of different domains cooperate to build an end-end path • Packet forwarding using identifiers very similar to MPLS • Trust? Does path computation trust the QoS reports from the forwarding? – Verify the information, punish the liars Feedback based routing • End nodes are connected to the internet through access routers • Ases exchange topology connectivity information between them – Flooding, advertise periodically and time-out if not refreshed – Access routers build a complete internet map • Scaling? Multiple 10s of Mbytes for storing this information • Access routers monitor the quality of the various routes using active and passive probing – They monitor/use at least two routes for each destination so there is a fast fallback route – In extreme cases can duplicate traffic over both these paths for zero-time fail-over • Uses “internet relay tokens” to forward packets along an AS source route Routing Deflections • Packets can be deflected to an alternate path (deflection) on their way to the destination – Deflections inside the ISP network and among ISPs • Packets contain a single tag that determines which deflections are used inside the network – End-nodes will probe different routes in order to achieve QoS • They is no clear mapping between tags and routes • Can not easily e.g. avoid a certain node/AS • But the overhead in the packet is very small • Deflection decisions are made independently by the transit networks – Must ensure there are no routing loops – Scales better than end-node selection – Deflect to another next-hop whose cost to destination is smaller • Has been used before for IP repair of traffic – Use additional rules to discover more options – Little bit more tricky to do across ISPs but it can be done Internet indirection infrastructure (I^3) • Use indirection as the basic mechanism – There is a rendezvous point between sender and receiver – Receivers register a trigger (id, dest) • And refresh them periodically, soft state – Senders send to data to an id – Indirection node forwards data based on a longest prefix match on the id • Can implement many communication modes – – – – – Multicast, mobility anycast Can have id stacks for implementing source routing Service composition, load balancing large scale multicast with id stacks Very powerful construct • Implementation using a DHT to store the triggers – Demonstrated using chord Declarative routing • Quite a bit more adventurous • Express the query for a route as a prolog query • Execute this query in a distributed way in the network – The result will be the route we are looking for • It is possible to express all types of routings – Unicast, multicast, policy best-path, link state – The ultimate route selection flexibility • BUT: – Security: my query has an infinite loop • It is possible to statically check – It may be too slow and to expensive to compute routes this way • It is possible to optimize execution a lot using techniques from database query execution Fixing BGP • One major problem of BGP is that all changes are visible to all the network – This causes a lot of churn • HLP – Take advantage of provider hierarchies – Topology consists of AS not routers – Do link state inside a hierarchy • Each inter-domain link has a cost – Distance vector between the roots of the hierarchies • Changes inside a hierarchy do not have to be sent to all the network – Such a protocol may not be too hard to implement Separating routing from routers • BGP problems – Each border router performs its own path computation • Needs to be configured with policies etc • Needs to exchange results with other border routers through iBGP – For scalability use route reflectors, backup route reflectors • When there are failures there can be loops • Route reflector will compute the same route for all the routers, not exactly the same as the routes computed by a full iBGP mesh • Centralize routing to a route control point (RCP) – – – – Not unlike a route server Has iBGP peerings with all the border routers, gets all the routes Computes the best route for each router Sends routes to each router in the domain over iBGP • RCPs from different domains peer with each other with eBGP – Enables more interesting inter-domain protocols • Implementing RCP is not too easy – Scalability, redundancy, synchronization between replicas Separating infrastructure from service • An ISP owns the routers and owns the services that run on them – Little coordination between ISPs results in huge difficulty in providing end-to-end service – Introduction of new services is painfully complex • Infrastructure providers provide programmable routers • Service providers build their own virtual networks on top of the infrastructure and provide their service • Part overlay part virtual network – Virtual routers • Isolation and resource sharing – Virtual links • Isolation and sharing – Discovery of physical topology – Setting up the service network • Admission control – Security Overlays • Can provide a lot of extra functionality without having to change the infrastructure • But there are problems: – Inefficient use of the underlying resources • Traffic may flow over a link twice – Failures are repaired at two different layers – Overlay links may violate BGP or other policies – Traffic engineering methods and decisions may be conflicting – Overlays can not scale to encompass the whole internet Sample overlay work • RON: – Provide reliable communication even in the face of network failures and instability – Full mesh of overlay links that are constantly monitored to find paths with good performance • OverQoS: – Overlay links are more active • Shape traffic and attempt to achieve maximum loss rates by ECN and retransmissions • Need to make sure that overlay links are TCP friendly • Optimized placement of the overlay links/nodes – Attempt to optimize the usage of real links and nodes – Not easy to do since we do not know the traffic that overlay links will carry – May have to incrementally evolve the overlay network by moving overlay nodes around as network conditions change Scalable overlays • Overlays can be quite inefficient – Cross the same physical links twice – May match very poorly the underlying network topology – Monitoring the QoS of the virtual links is expensive • We saw RON, a full mesh overlay that did not scale very well • Other attempts build more sparse overlays – Still treat the underlying network as a black box • Can use additional information – Geographical location – AS map of the internet • Can be derived relatively cheaply through the BGP routing tables Traffic Engineering • Major issues – Dynamic TE, adapt quickly to changes in the load of the network • Without waiting weeks for re-optimization • Without requiring knowledge of a hard to measure traffic matrix – MATE etc… • Overlays and their interaction with the underlay – Overlays can be adaptive • Lot of traffic can shit suddenly – Right now there is no coordination • Decisions at each layer may be conflicting – Optimization of the underlay may be totally wrong