Routing protocols and architectures/Inter-domain routing

Inter-domain routing is in charge of deciding and propagating information about external routes among multiple interconnected ASes over the network.

Autonomous Systems

An Autonomous System (AS) is a set of IP networks that are under control of a set of entities that agree to present themselves as a unique entity, everyone adopting the same set of routing policies.

From the inter-domain routing point of view, Internet is organized into ASes: an AS represents an homogeneous administrative entity, generally an ISP, at the highest hierarchical level on the network. Each AS is uniquely identified by a 32-bit number (it was 16-bit in the past) assigned by IANA.

Each AS is completely independent: it can decide internal routing according to its own preferences, and IP packets are routed inside it according to internal rules. Each AS can have one or more internal routing domains served by IGP protocols: each domain can adopt its favourite IGP protocol, and thanks to redistribution it can exchange routing information with other domains.

A network being AS can keep under its control incoming and outgoing traffic thanks to routing policies, but is subject to a greater responsibility: routing is more difficult to configure, and possible configuration mistakes may affect traffic of other ASes.

For network portions who are going to become ASes, in the past some additional rules were enforced which nowadays have been relaxed:

• all the network has to be on the same administrative domain:

  nowadays the administrative entity of an AS does not necessarily coincides with the organization actually managing internally the network: for example, the network at the Politecnico di Torino, although being owned by the university and being under the control of bodies inside it, is one of the subnetworks inside the AS administered by the GARR research body, which is in charge of deciding long-distance interconnections toward other ASes;

• the network has to be of at least a given size:

  in recent years content providers have needed to have some ASes spread around the world of very small size: for example, Google owns some web servers in Italy which distribute custom content for the Italian audience (e.g. advertisements) and which, being closer to users, return more quickly search results acting as a cache ( B8. Content Delivery Networks) → if those web servers constitute themselves an AS, Google has control over the distribution of its content to Italian ISPs, and can make commercial agreements with the latter favouring some of them at the expense of other ones;

• the AS has to be connected with at least two other ASes to guarantee, at least technically, transit across it for traffic from an AS to another one:

  a local ISP of small size (Tier 3) may buy by a national ISP of big size (Tier 2) the whole connectivity toward the Internet: B4. Inter-domain routing: peering and transit in the Internet#Commercial agreements among ASes.

EGP protocol class

A single border router put between ASes belonging to different ISPs arises some issues:

• who owns it? who configures it?
• who is responsible in case of failure?
• how to prevent an ISP from collecting information about a competitor's network?

The solution is to use two border routers, each one administered by either of the two ISPs, separated by a sort of intermediate 'free zone' handled by a third routing protocol instance of type Exterior Gateway Protocol (EGP).

Through an EGP protocol, every border router at the border of an AS exchanges external routing information with other border routers:

• it propagates to other ASes information about destinations which are inside its AS;
• it propagates to other ASes information about destinations which are inside other ASes but can be reached through its AS.

EGP protocols differentiate from IGP protocols especially for support to routing policies reflecting commercial agreements among ASes.

EGP protocols

• static routing: configuration of routers by hand:
  • this is the best "algorithm" to implement complex policies and to have the complete control over network paths;
  • no control traffic is needed: information about destinations is avoided to be exchanged;
  • it does not react to topological changes;
  • it is easy to introduce inconsistencies;
• Exterior Gateway Protocol (EGP): it was the first protocol completely dedicated to routing among domains, but currently nobody uses it because it provides just information about reachability and not about distance:
  • if the reachability of a destination is advertised across multiple paths, the least-cost best path can not be chosen;
  • if the reachability of a destination is advertised across multiple paths, all routers are not guaranteed that will choose a coherent path → this can be used only in networks without closed paths where no loop can form;
• Border Gateway Protocol (BGP): it is the only EGP protocol which has been adopted in the whole Internet at the expense of other EGP protocols: all border routers in the whole network of interconnected ASes must adopt the same EGP protocol for exchanging external routes, because if two ASes would choose to use different EGP protocols, their border routers could not communicate one with each other ( B5. Border Gateway Protocol);
• Inter-Domain Routing Protocol (IDRP): it was created as an evolution to BGP in order to support OSI addressing, but currently nobody uses it because:
  • it is made up of rather complex parts;
  • since then improvements introduced by IDRP have been ported to the next versions of BGP;
  • it is not compatible with BGP → its adoption by an AS would break interoperability with the rest of the network which is still using BGP.

Redistribution

On every border router a redistribution process is running from the IGP protocol inside the AS to the EGP protocol outside the AS and vice versa → routes are redistributed first from an AS to the intermediate area and then from here to the other AS:

Example of redistribution between ASes belonging to different ISPs.

• the IGP protocol learns external routes toward destinations which are in other ASes, and propagates them into the AS as internal routes;
• the EGP protocol learns internal routes toward destinations which are in the AS, and propagates them to other ASes as external routes.

Routes are redistributed both between hierarchical domains inside the AS, and between the AS itself and the external world.

Redistribution defines:

• which internal networks must be known to the outside world: private networks for example must not be propagated to other ASes;
• which external networks must be known inside the AS: the amount of announced routing information can be reduced by avoiding to include full details about external networks:
  • announced addresses can be 'collapsed' into aggregate routes when they share part of their network prefixes;
  • a single default route can be announced when the AS has a single exit point.

Redistribution must not introduce incoherences in routing:

• a routing loop may form if, for example, a route learnt in IGP and exported in EGP is then re-imported in IGP appearing as an external route;
• if a certain AS is reachable across multiple border routers of the same AS, these border routers need to agree in order to internally redistribute a single exit point for that route.

Often redistribution on a border router at the border of an AS is enabled in one way only from the IGP protocol to the EGP protocol: internal routes are exported to the external world, while external routes are replaced by a default route.