1 06-NetworkControl

Previous: 05-Security.html

1.1 Audio-recording

1.2 Extra reading

* https://www.computer-networking.info/1st/html/network/network.html#routing-in-ip-networks

* https://www.computer-networking.info/2nd/html/protocols/routing.html
* https://www.computer-networking.info/2nd/html/protocols/bgp.html

* http://intronetworks.cs.luc.edu/current2/uhtml/routing.html
* http://intronetworks.cs.luc.edu/current2/uhtml/bigrouting.html

1.3 Routing algorithms

Recall: forwarding versus routing

1.3.1 Overview

Abstract graph model of a computer network
* Given any two nodes x and y, there are typically many paths between the two nodes, with each path having a cost.
* One or more of these paths is a least-cost path.

1.3.2 Routing protocols

1.3.3 Convergence

* Convergence is the state of a set of routers that have the same topological information about the inter-network in which they operate.
* For a set of routers to have converged, they must have collected all available topology information from each other via the implemented routing protocol, the information they gathered must not contradict any other router’s topology information in the set, and it must reflect the real state of the network.
* In a converged network all routers “agree” on what the network topology looks like.
* All Interior Gateway Protocols rely on convergence to function properly.
* To have converged, is a normal state of an operational autonomous system (AS).
* The Exterior Gateway Routing Protocol, BGP, typically never converges, because the Internet is too big for changes to be communicated fast enough.
* When a routing protocol process is enabled, every participating router will attempt to exchange information about the topology of the network.
* The extent of this information exchange, the way it is sent and received, and the type of information required vary widely depending on the routing protocol in use, see e.g. RIP, OSPF, BGP4.
* A state of convergence is achieved once all routing protocol-specific information has been distributed to all routers participating in the routing protocol process.
* Any change in the network that affects routing tables will break the convergence temporarily until this change has been successfully communicated to all other routers.

1.3.4 Scope

How do the various scales of sub-networks and inter-networks share routing tables?

Different protocols for inter-domain/AS versus intra-domain/AS routing:

1.3.5 Networks of networks

40.000-50,000 AS/domains in the internet today:
* See http://bgp.potaroo.net/index-as.html for reports on the evolution of the number of Autonomous Systems over time. Autonomous system (AS)

* An autonomous system (AS) is a collection of connected Internet Protocol (IP) routing prefixes under the control of one or more network operators on behalf of a single administrative entity or domain that presents a common, clearly defined routing policy to the internet. Routing domain

* A routing domain is a collection of networked systems that operate common routing protocols, and are under the control of a single administration.
* For example, this might be a set of routers under a control of a single organization, some of them operating a corporate network, some others a branch office network, and the rest the data center network.
* A given autonomous system can contain multiple routing domains, or a set of routing domains can be coordinated without being an Internet-participating autonomous system.

++++++++++++ Cahoot-6-1

1.4 Algorithm types

Central, distributed, hybrid, and hierarchical:


Although there are many types of routing protocols, three major classes are in widespread use on IP networks:

  1. Interior gateway protocols type 1, link-state routing protocols, such as OSPF and IS-IS

  2. Interior gateway protocols type 2, distance-vector routing protocols, such as Routing Information Protocol, RIPv2, IGRP.

  3. Exterior gateway protocols are routing protocols used on the Internet for exchanging routing information between Autonomous Systems, such as Border Gateway Protocol (BGP), Path Vector Routing Protocol.

1.4.1 Distance vector


a distributed routing table building algorithm

Distance-vector (DV) algorithm
* In these protocols, each router does not possess information about the full network topology.
* It advertises its distance value (DV) calculated to other routers and receives similar advertisements from other routers unless changes are done in local network or by neighbours (routers).
* Using these routing advertisements each router populates its routing table.
* In the next advertisement cycle, a router advertises updated information from its routing table.
* This process continues until the routing tables of each router converge to stable values.

A very interesting algorithm used for shortest path calculation here.


a central routing table building algorithm

Least cost path and forwarding table for nodule u
* In link-state routing protocols, each router possesses information about the complete network topology.
* Each router then independently calculates the best next hop from it for every possible destination in the network using local information of the topology.
* The collection of best-next-hops forms the routing table.
* This contrasts with distance-vector routing protocols, which work by having each node share its routing table with its neighbors.
* In a link-state protocol, the only information passed between the nodes is information used to construct the connectivity maps.

1.4.3 Hierarchical

A good discussion of why CIDR and hierarchical routing exist at the highest scale of Internet routing:

Hierarchical routing: paths between interconnected autonomous systems (AS)

Autonomous systems (AS) consist of a group of routers typically under the same administrative control
* (e.g., operated by the same ISP or belonging to the same company network).
* Routers within the same AS all run the same routing algorithm and have information about each other.
* The routing algorithm running within an autonomous system is called an intra-autonomous system routing protocol.

Obtaining reachability information from neighboring ASs and propagating the reachability information to all routers internal to the AS, are handled by the inter-AS routing protocol.
* Since the inter-AS routing protocol involves communication between two ASs, the two communicating ASs must run the same inter-AS routing protocol.
* In the Internet all ASs run the same inter-AS routing protocol, called BGP4

1.4.4 Centralized control (software defined networking)

Classic model: Fascinating and robust distributed algorithm runs on each router:

Meh… SDN: Just centralize the computation:

1.5 Internet routing at the global scale

Actual internet algorithms


++++++++++++ Cahoot-6-2

1.5.1 Interior gateway

https://en.wikipedia.org/wiki/Interior_gateway_protocol Intra-AS RIP


Distributed: Routing Information Protocol (RIP)
* Each router maintains a RIP table known as a routing table.
* A router’s routing table includes both the router’s distance vector and the router’s forwarding table.

Distributed: Routing Information Protocol (RIP)

The best thing about RIP jokes is that they’re funny 15 more times… Intra-AS OSPF


Central algorithm (computed on all routers): Open Shortest Path First (OSPF)
* Used by mega-ISPs, OSPF was conceived as the successor to RIP and as such has a number of advanced features.
* At its heart however, OSPF is a link-state protocol that uses flooding of link-state information and a Dijkstra least-cost path algorithm.
* With OSPF, a router constructs a complete topological map (that is, a graph) of the entire autonomous system.
* The router then locally runs Dijkstra’s shortest-path algorithm to determine a shortest-path tree to all sub-nets, with itself as the root node.
* Individual link costs are configured by the network administrator

Q. What did the OSPF router say to the other OSPF router ?
R. Hello. Hello. Hello. Hello. Hello. Hello. Hello. Hello.

My new OSPF neighbor told me all his jokes, after we said hello to each other.
Then he tells me the whole database of jokes every 30 minutes. Intra-AS IS-IS


Central algorithm (computed on all routers): Intermediate System to Intermediate System (IS-IS, also written ISIS) Intra-AS EIGRP


Hybrid/advanced-distributed: Enhanced Interior Gateway Routing Protocol (EIGRP)

1.5.2 Exterior gateway

* An exterior gateway protocol is a routing protocol used to exchange routing information between autonomous systems.
* This exchange is crucial for communications across the Internet.
* BGP is really the only big player here.

06-NetworkControl/dynamic-routing-protocols.png Inter-AS EGP

Here for historical purposes (obsolete)
https://en.wikipedia.org/wiki/Exterior_Gateway_Protocol Inter-AS BGP


The strange thing about BGP jokes is that they’re borderline funny but everybody repeats them anyway.

Border Gateway Protocol version 4 (BGP4)

I would tell a BGP joke, but everyone probably already knows it.

BGP provides each A.S. a means to:
1. Obtain sub-net reachability information from neighboring ASs.
2. Propagate the reachability information to all routers internal to the AS.
3. Determine “good” routes to sub-nets based on the reachability information and on AS policy.

Border Gateway Protocol version 4 (BGP4)
* BGP session that spans two ASs is called an external BGP (eBGP) session
* BGP session between routers in the same AS is called an internal BGP (iBGP) session

I'd like to tell you a full joke about a BGP table, but I don't think you can remember it all. Politics and money!

Why is this a sub-heading under Exterior gateway protocols?? Types of domain
06-NetworkControl/stub-transit-domains.png Non-technical routing decisions Types of relationship

There are different types of economic relationships that can exist between domains.
* Inter-domain routing converts these relationships into peering relationships between domains that are connected via peering links.

  1. customer->provider
  2. shared-cost peering
  3. sibling
  1. the import filter that specifies, for each peering relationship, the routes that can be accepted from the neighboring domain (the non-acceptable routes are ignored and the domain never uses them to forward packets)

  2. the export filter that specifies, for each peering relationship, the routes that can be advertised to the neighboring domain

  3. the ranking algorithm that is used to select the best route among all the routes that the domain has received towards the same destination prefix

1.6 Which layer does routing use?

Routing protocols, according to the OSI routing framework, are layer management protocols for the network layer, regardless of their transport mechanism:

1.7 Broadcast, multicast, anycast

1.7.1 Broadcast

How to broadcast?

Several possible mechanisms, with pros and cons:

1.7.2 Multicast

1.7.3 Anycast

Next: 07-DataLink.html