1 06-NetworkControl

Previous: 05-Security.html

1.1 Audio-recording

• Password for the Vimeo videos is in Zulip chat.
  • Part 1: 2022-04-20
    • https://vimeo.com/708014012
    • https://vimeo.com/708014107
• Tip: If anyone want to speed up the lecture videos a little, inspect the page, go to the browser console, and paste this in: document.querySelector('video').playbackRate = 1.2

1.2 Extra reading

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

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

Intronetworks
* 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

• A routing protocol specifies how routers communicate information that enables them to select routes between any two nodes on a computer network.
• Routers perform the “traffic directing” functions on the Internet.
• Data packets are forwarded through the networks of the internet from router to router until they reach their destination computer.
• Routing algorithms determine the specific choice of route.
• Each router has prior knowledge only of networks attached to it directly.
• A routing protocol shares this information first among immediate neighbors, and then throughout the network.
• This way, routers gain knowledge of the topology of the network.
• The ability of routing protocols to dynamically adjust to changing conditions, such as disabled data lines or computers, and still route data around obstructions is what gives the Internet its survivability and reliability.
• The specific characteristics of routing protocols include:
  • the manner in which they avoid routing loops,
  • the manner in which they select preferred routes,
• The protocols use information about
  * hop costs,
  * the time they require to reach routing convergence,
  * their scalability, and
  * other factors.

1.3.3 Convergence

https://en.wikipedia.org/wiki/Convergence_(routing)
* 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

https://en.wikipedia.org/wiki/Routing_protocol
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.

1.3.5.1 Autonomous system (AS)

https://en.wikipedia.org/wiki/Autonomous_system_(Internet)
* 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.

1.3.5.2 Routing domain

https://en.wikipedia.org/wiki/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

https://en.wikipedia.org/wiki/Distance-vector_routing_protocol

a distributed routing table building algorithm

• In a decentralized routing algorithm, the calculation of the least-cost path is carried out in an iterative, distributed manner.
• No node has complete information about the costs of all network links.
• Instead, each node begins with only the knowledge of the costs of its own directly attached links.
• Through an iterative process of calculation and exchange of information with its neighboring nodes (that is, nodes that are at the other end of links to which it itself is attached), a node gradually calculates the least-cost path to a destination or set of destinations.

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.

https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
A very interesting algorithm used for shortest path calculation here.

1.4.2 Link-state

https://en.wikipedia.org/wiki/Link-state_routing_protocol

a central routing table building algorithm

• A centralized global routing algorithm computes the least-cost path between a source and destination using complete, global knowledge about the network.
• That is, the algorithm takes the connectivity between all nodes and all link costs as inputs.
• Link-state methods broadcast connectivity information to all nodes in the network, and then centrally perform Dijkstra’s algorithm to find the shortest path on a graph

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:
https://intronetworks.cs.luc.edu/current2/uhtml/bigrouting.html#hierarchical-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

• A very important difference between intra-domain and inter-domain routing are the routing policies that are used by each domain.
• Inside a single domain, all routers are considered equal, and when several routes are available to reach a given destination prefix, the best route is selected based on technical criteria such as
  • the route with the shortest delay,
  • the route with the minimum number of hops, or
  • the route with the highest bandwidth.
• When we consider the interconnection of domains that are managed by different organizations, this is no longer true.
• Each domain implements its own routing policy.
• A routing policy is composed of three elements (more below):
  2. an import filter that specifies which routes can be accepted by a domain,
  3. an export filter that specifies which routes can be advertised by a domain, and
  4. a ranking algorithm that selects the best route when a domain knows several routes towards the same destination prefix.
• As we will see later, another important difference is that the objective of the inter-domain routing protocol is to find the cheapest route towards each destination.

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

1.5.1 Interior gateway

https://en.wikipedia.org/wiki/Interior_gateway_protocol

• An interior gateway protocol (IGP) is a type of protocol used for exchanging routing information between gateways (commonly routers) within an autonomous system (for example, a system of corporate local area networks).
• This routing information can then be used to route network-layer protocols like IP
• Several primary interior gateway algorithms:

1.5.1.1 Intra-AS RIP

https://en.wikipedia.org/wiki/Routing_Information_Protocol

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 Routing Information Protocol (RIP) is one of the oldest distance-vector routing protocols, which employs the hop count as a routing metric.
• RIP prevents routing loops, by implementing a limit on the number of hops allowed in a path from source to destination.
• The largest number of hops allowed for RIP is 15, which limits the size of networks that RIP can support.
• In RIPv1 routers broadcast updates with their routing table every 30 seconds.
• In the early deployments, routing tables were small enough that the traffic was not significant.
• As networks grew in size, however, it became evident there could be a massive traffic burst every 30 seconds, even if the routers had been initialized at random times.
• In most networking environments, RIP is not the preferred choice of routing protocol, as its time to converge and scalability are poor compared to EIGRP, OSPF, or IS-IS.

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

1.5.1.2 Intra-AS OSPF

https://en.wikipedia.org/wiki/Open_Shortest_Path_First

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.

1.5.1.3 Intra-AS IS-IS

https://en.wikipedia.org/wiki/IS-IS

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

1.5.1.4 Intra-AS EIGRP

https://en.wikipedia.org/wiki/Enhanced_Interior_Gateway_Routing_Protocol

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

1.5.2 Exterior gateway

https://en.wikipedia.org/wiki/Exterior_gateway_protocol
* 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.

1.5.2.1 Inter-AS EGP

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

1.5.2.2 Inter-AS BGP

https://en.wikipedia.org/wiki/Border_Gateway_Protocol

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.

• Most importantly, BGP allows each sub-net to advertise its existence to the rest of the Internet.
• A sub-net screams “I exist and I am here,” and BGP makes sure that all the ASs in the Internet know about the sub-net and how to get there.
• If it weren’t for BGP, each sub-net would be isolated, alone and unknown by the rest of the Internet.

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.

1.5.2.3 Politics and money!

Why is this a sub-heading under Exterior gateway protocols??

1.5.2.3.1 Types of domain

• Each domain contains a set of routers.
• From a routing point of view, these domains can be divided into two classes:
  1. A transit domain is a domain that provides a transit service for other domains, i.e. the routers in this domain forward packets whose source and destination do not belong to the transit domain.
  2. A stub domain sends and receives packets whose source or destination are one of its own hosts.
     • As of this writing, about 85% of the domains in the Internet are stub domains.
     • A stub domain that is connected to a single transit domain is called a single-homed stub.
     • A multi-homed stub is a stub domain connected to two or more transit providers.
     • The stub domains can be further classified by considering whether they mainly send or receive packets.
       • An access-rich stub domain is a domain that contains hosts that mainly receive packets.
         • Typical examples include small ADSL- or cable modem-based Internet Service Providers or enterprise networks.
       • On the other hand, a content-rich stub domain is a domain that mainly produces packets.
         • Examples of content-rich stub domains include google, yahoo, microsoft, facebook or content distribution networks such as akamai or limelight
         • For the last few years, we have seen a rapid growth of these content-rich stub domains.

1.5.2.3.2 Non-technical routing decisions

• In the early days of the Internet, domains would simply exchange all the routes they know to allow a host inside one domain to reach any host in the global Internet.
• However, in today’s highly commercial Internet, this is no longer true as inter-domain routing mainly needs to take into account the economical relationships between the domains.
• Furthermore, while intra-domain routing usually prefers some routes over others based on their technical merits (e.g. prefer route with the minimum number of hops, prefer route with the minimum delay, prefer high bandwidth routes over low bandwidth ones, etc) inter-domain routing mainly deals with economical issues.
• For inter-domain routing, the cost of using a route is often more important than the quality of the route measured by its delay or bandwidth.

1.5.2.3.3 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
   • Such a relationship is used when a customer domain pays an Internet Service Provider to be able to exchange packets with the global Internet over an inter-domain link.
   • A similar relationship is used when a small Internet Service Provider pays a larger Internet Service Provider to exchange packets with the global Internet.
2. shared-cost peering
   • Such a relationship usually does not involve a payment from one domain to the other in contrast with the customer->provider relationship.
   • A shared-cost peering relationship is usually established between domains having a similar size and geographic coverage. For example, consider the figure above.
   • If AS3 and AS4 exchange many packets via AS1, they both need to pay AS1.
   • A cheaper alternative for AS3 and AS4 would be to establish a shared-cost peering.
   • Such a peering can be established at IXPs where both AS3 and AS4 are present or by using private peering links.
   • This shared-cost peering should be used to exchange packets between hosts inside AS3 and hosts inside AS4.
   • However, AS3 does not want to receive on the AS3-AS4 shared-cost peering links packets whose destination belongs to AS1 as AS3 would have to pay to send these packets to AS1.
3. sibling
   • Such a relationship is used when two domains exchange all their routes in both directions.
   • In practice, such a relationship is only used between domains that belong to the same company.
     

• These different types of relationships are implemented in the inter-domain routing policies defined by each domain.
• The inter-domain routing policy of a domain is composed of three main parts:

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:

• IS-IS runs on the data link layer (Layer 2)
• Open Shortest Path First (OSPF) is encapsulated in IP, but runs only on the IPv4 subnet, while the IPv6 version runs on the link using only link-local addressing.
• IGRP, and EIGRP are directly encapsulated in IP.
  • EIGRP uses its own reliable transmission mechanism, while IGRP assumed an unreliable transport.
• Routing Information Protocol (RIP) runs over the User Datagram Protocol (UDP).
  • Version 1 operates in broadcast mode, while version 2 uses multicast addressing.
• BGP runs over the Transmission Control Protocol (TCP).

1.7 Broadcast, multicast, anycast

• In broadcast routing, the network layer provides a service of delivering a packet sent from a source node to all other nodes in the network.
• Multicast routing enables a single source node to send a copy of a packet to a subset of the other network nodes.
• IPv6 has introduced a new type of address, called an anycast address, which allows a datagram to be delivered to any one of a group of hosts.
  • This feature could be used, for example, to send an HTTP GET to the nearest of a number of mirror sites that contain a given document

1.7.1 Broadcast

• When a host sends a datagram with destination address 255.255.255.255, the message is delivered to all hosts on the same sub-net.

How to broadcast?

Several possible mechanisms, with pros and cons:

• Flooding:
  • when node receives broadcast packet, sends copy to all neighbors
  • problems: cycles & broadcast storm
• Controlled flooding:
  • node only broadcasts packet, if it hasn’t broadcast same packet before
  • node keeps track of packet ids already broadacsted
  • or reverse path forwarding (RPF):
    • only forward packet, if it arrived on shortest path between node and source
• Spanning tree:
  • no redundant packets received by any node
• more detail on broadcasts and routing trees from old slides?

1.7.2 Multicast

• TODO

1.7.3 Anycast

• TODO

Next: 07-DataLink.html