Internetworking

class: title, smokescreen, shelf, bottom, no-footer
background-image: url(images/internetworking.png)

# 181U Spring 2020
### Internetworking
<style>
h1 {
  border-bottom: 8px solid rgb(32,67,143);
    border-radius: 2px;
    width: 90%;
}

.smokescreen h1 {
    border-bottom: none;
}

.small {font-size: 80%}
  .smaller {font-size: 70%}
  .small-code.remark-slide-content.compact code {font-size:1.0rem}
  .very-small-code.remark-slide-content.compact code {font-size:0.9rem}

.line-numbers{
  /* Set "line-numbers-counter" to 0 */
  counter-reset: line-numbers-counter;
}

.line-numbers .remark-code-line::before {
  /* Increment "line-numbers-counter" by 1 */
    counter-increment: line-numbers-counter;
    content: counter(line-numbers-counter);
    text-align: right;
    width: 20px;
    border-right: 1px solid #aaa;
    display: inline-block;
    margin-right: 10px;
    padding: 0 5px;
}

</style>

---
layout: true
.footer[
- 181U
- See acknowledgements
]

---
class: compact
# Agenda

* Internetworks
* Addresses
  * Global
  * Subnets
  * CIDR
* Routing
  * packet forwarding
  * intranet routing
  * internet routing
  
---
class: compact
# Internetwork

**An arbitrary collection of networks connected to provide host-host packet delivery**

![](images/space.png# w-30pct)
![](images/2019-12-06-08-19-17.png# w-40pct)

---
class: compact
# Internetwork Layers

![](images/2019-12-06-08-19-17.png# w-40pct)
![](images/space.png# w-10pct)
![](images/2019-12-06-08-21-29.png# w-40pct)

---
class: compact
# Global Addresses

![](images/2019-12-06-08-24-06.png# w-30pct fr)

* Originally, the IP address space was carved up into networks of various sized
* Routing was between networks and then within networks
* This led to a terrible inefficiency in IP address utilization

---
class: compact
# Original IP Address allocation [rfc790](https://tools.ietf.org/html/rfc790)

```plaintext
Internet Address  Name          Network                 References
      ----------------  ----          -------                 ----------
      000.rrr.rrr.rrr                 Reserved                     [JBP]
      001.rrr.rrr.rrr   BBN-PR        BBN Packet Radio Network    [DCA2]
      002.rrr.rrr.rrr   SF-PR-1       SF Packet Radio Network (1)  [JEM]
      003.rrr.rrr.rrr   BBN-RCC       BBN RCC Network              [SGC]
      004.rrr.rrr.rrr   SATNET        Atlantic Satellite Network  [DM11]
      005.rrr.rrr.rrr   SILL-PR       Ft. Sill Packet Radio Network[JEM]
      006.rrr.rrr.rrr   SF-PR-2       SF Packet Radio Network (2)  [JEM]
      007.rrr.rrr.rrr   CHAOS         MIT CHAOS Network           [MOON]
      008.rrr.rrr.rrr   CLARKNET      SATNET subnet for Clarksburg[DM11]
      009.rrr.rrr.rrr   BRAGG-PR      Ft. Bragg Packet Radio Net   [JEM]
      010.rrr.rrr.rrr   ARPANET       ARPANET                 [17,1,VGC]
      011.rrr.rrr.rrr   UCLNET        University College London     [PK]
      012.rrr.rrr.rrr   CYCLADES      CYCLADES                     [VGC]
```
---
class: compact
# Datagram forwarding in IP (old school)

* Every IP datagram contains the IP address of the destination host
* The network part of the IP address uniquely identifies network
* All hosts/routers with same network address are connected to the same network

```
if (NetworkNum of destination = NetworkNum of one of my interfaces) then
    deliver packet to destination over that interface
else
    if (NetworkNum of destination is in my forwarding table) then
        deliver packet to NextHop router
    else
        deliver packet to default router
```

---
class: compact, col-2
# Routing Example

![](images/2019-12-06-08-19-17.png# w-80pct)

* Suppose H5 wants to send a datagram to H8
* Forwarding table for R2

| NetworkNum | NexHop |
| --- | --- |
| 1 | R1 |
| 2 | Interface 1|
| 3 | Interface 0 |
| 4 | R3 |

---
class: compact
# Subnetting

* Because the original network addressing mechanism didn't scale, a new mechanism was created called subnetting
* This allowed one class A,B, or C network to be arbitrarily subdivided with a "subnet mask"

![](images/2019-12-06-08-37-26.png# w-30pct)
![](images/space.png# w-20pct)
![](images/2019-12-06-08-38-08.png# w-30pct)

---
class: compact
# Subnetting (example)

```C
D = destination IP address
for each forwarding table entry (SubnetNumber, SubnetMask, NextHop)
    D1 = SubnetMask & D
    if D1 = SubnetNumber
        if NextHop is an interface
            deliver datagram directly to destination
        else
            deliver datagram to NextHop (a router)
```

| Subnet Number | Subnet Mask | NextHop |
| --- | --- | --- |
| 128.96.34.0	| 255.255.255.128	| Interface 0 |
| 128.96.34.128	| 255.255.255.128	| Interface 1 |
| 128.96.33.0	| 255.255.255.0	| R2 |

---
class: compact
# Classless Addressing

![](images/2019-12-06-08-45-40.png# w-30pct fr)
* Classless Interdomain Routing (CIDR) does away with classes altogether
* Routes are aggregated by address ranges (called "prefixes") -- think of these as the number of leading ones in a mask
* 20-bit prefix for all the networks 192.4.16 through 192.4.31 is represented as 192.4.16/20
* a single class C network number, which is 24 bits long, we would write it 192.4.16/24

---
class: compact
# CIDR Routing

* Routing table consists of rules of the form  (prefix, nexthop)
* There can be multiple matches
  * We might find both 171.69.0.0/16 (a 16-bit prefix) and 171.69.10.0/24 (a 24-bit prefix) 
  * 171.69.10.5 matches both
  * Selection is made on the longest matching prefix (171.69.10.0/24)
* There has been a lot of research on implementing this efficiently
  * For small tables, a cache is used
  * For large tables (core routers) a tree is implemented in hardware

---
class: compact
# ARP and DHCP
![](images/dhcprelay.png# w-40pct fr)

* Clearly there is a "bootstrapping" process for routing
  * How do nodes get their IP addresses ? 
      * Static assignment (typically for servers, router interfaces)
      * DHCP  -- a local server temporarily assigns addresses (a lease) from a reserved pool.
         * Newly booted host sends a message to a special IP broadcast address (255.255.255.255)
  * How do nodes find out addresses of local servers, routers, etc
      * Address Translation (ARP) protocol -- depends upon broadcasting a special packet at the link-level (e.g. ethernet)

---
class: compact
# Routing

How do switches and routers learn about network topology so they can build their routing tables ?

![](images/networkgraph.png# w-30pct fr)

* Basic approach is to treat the network as a graph.  Communication links are edges with cost (for example based upon bandwidth)
* Building a routing table is then a matter of computing the lowest cost route between two points
  * This doesn't deal with failures
  * This doesn't deal with changes

---
class: compact
# Distance-Vector Routing (RIP)

![](images/space.png# w-10pct)
![](images/bellmanfordtable.png# w-3-12th)
![](images/initialtable.png# w-3-12th)
![](images/finaltable.png# w-20pct)

![](images/space.png# w-40pct)
![](images/networkgraph.png# w-3-12th)

---
class: compact
# Link-state routing (OSPF)

![](images/ospf.png# w-40pct fr)

* Assumptions
  * Every node is assumed to be capable of finding out the state of the link (up/down) connecting with its neighbors
  * Nodes communicate their knowledge to their neighbors 
    * The ID of the node creating the LSP packet
    * A list of directly connected neighbors and the cost of the link to each one
    * A sequence number
    * A TTL (time to live)
* Once a node has a copy of data from every other nodes, it computes the routing table using Dijkstra's shortest path algorithm

---
class: compact
# Scaling Up

![](images/routingareas.png# w-40pct fr)

* RIP and OSPF don't scale and  are used primarily on *intranets*  -- for example the 5C's
* We can think of the internet as is composed of multiple independent networks - recursively
* A corporate or university network might be treated as a set of "areas" each of which implements RIP or OSPF route table maintenance.

---
class: compact
# Interdomain Routing (BGP)

![](images/autonomousystems.png# w-30pct fr)

* The real internet is partitioned across providers (Autonomous Systems, or AS)
* Routing between ASs is based upon service contracts
* Each AS determines its own policies
  
* AS3659  CLAREMONT - Claremont University Consortium

Primary Interdomain routing protocol is called Border Gateway Protocol (BGP)

* BGP makes no assumptions about how ASs are interconnected

---
class: compact
# Autonomous Systems

![](images/multi-providerinternet.png# w-30pct)
![](images/space.png# w-10pct)
![](images/topas.png# w-50pct)

---
class: compact
# Integration of Routing Systems

![](images/igbp.png# w-30pct fr)

* Boarder routers (A,E,D) run BGP
* All routers run iBGP and an intra-domain routing protocol

---
class: compact
# Integrated Routing Tables

![](images/space.png# w-2-12th)
![](images/igbp.png# w-30pct)
![](images/space.png# w-10pct)
![](images/integratedroutingtables.png# w-30pct)

---
class: compact
# Summary

* Internetworks
* Addresses
  * Global
  * Subnets
  * CIDR
* Routing
* https://blog.apnic.net/2019/01/16/bgp-in-2018-the-bgp-table/
* Acknowledgement :  content and slides from https://book.systemsapproach.org/index.html