[Home Page - Introduction to Computer Network](/@roger61205/Introduction-to-Computer-Network)
[toc]

1. Network is responsible for transporting segment from sending to receiving host.
1. Sender encapsulates segments into datagrams and passes to link layer.
2. Receiver delivers segments to transport layer protocol.
2. Two Key Network-Layer Functions
1. Forwarding moves packets from a router’s input link to appropriate router output link.
2. Routing determines route taken by packets from source to destination
3. What’s Inside a Router
1. Data Plane
Functions in data plane are local, per-router functions, determining how datagram arriving on router input port is forwarded to router output port.
2. Control Plane
Functions in data plane are network-wide, determining how datagram is routed among routers along end-end path from source host to destination host.
# Data Plane
## Forwarding Management
### Input Port Queuing
If datagrams arrive faster than forwarding rate into switch fabric, them form a queue.
### Forwarding Methods
#### Destination-Based Forwarding
Forward based only on destination IP address
* Longest Prefix Matching
When looking for forwarding table entry for given destination address, use longest address prefix that matches destination address.
#### Generalized Forwarding
Forward based on any set of header field values.
### Switching Fabrics
#### Switching via Memory
Packets are copied to system’s memory.
:::info
Speed is limited by memory bandwidth.
:::
#### Switching via a Bus
:::info
Switching speed is limited by bus bandwidth
:::
#### Switching via Interconnection Network
### Queuing
#### Input Queuing
* Head-of-the-Line (HOL) Blocking: queued datagram at front of queue prevents others in queue from moving forward
#### Output Queuing
1. Buffering is required when datagrams arrive from fabric faster than link transmission rate, because datagrams can be lost due to congestion and lack of buffers.
1. With N flows, buffering equal to
$$
\frac{RTT\times C}{\sqrt{N}}
$$
but too much buffering can increase delays
2. Buffer Management
1. Drop
When buffers are full newcoming packets drop.
2. Marking
Packets are marked to signal congestion (ECN, RED).
2. Scheduling discipline chooses among queued datagrams for transmission
Packet scheduling decides which packet to send next on link.
1. FCFS: First come, first served.
2. Priority
Arriving traffic will be classified, queued by class. And packets will be sent from highest priority queue that has buffered packets.
3. Round Robin
Arriving traffic will be classified, queued by class. And server cyclically, repeatedly scans class queues, sending one complete packet from each class (if available) in turn.
4. Weighted Fair Queuing (WFQ)
WFQ is a generalized Round Robin. Each class, $i$, has weight, $w_i$, and gets weighted amount of service in each cycle
$$
\frac{w_i}{\sum_jw_j}
$$
* Minimum bandwidth is guaranteed
## IP
### IP Datagram format
### Subnets
:::info
:::
A subnet is a net that device interfaces can physically reach each other without passing through an intervening router.
:::info
:::
1. Devices in same subnet have common high order bits
2. Host has only low order bits
### IP Addressing CIDR (Classless InterDomain Routing)
#### Address Format
$a.b.c.d/x$, where $x$ is bits in subnet portion of address
#### Hierarchical Addressing
Hierarchical addressing allows efficient advertisement of routing information.
#### How to get one?
1. How does host get IP address?
1. It can be hard-coded by system admin in config file.
2. DHCP (Dynamic Host Configuration Protocol)
Host dynamically obtains IP address from network server when it “joins” network.
:::info
1. Connecting laptops use DHCP to get IP address, address of first-hop router, address of DNS server.
2. DHCP REQUEST message is encapsulated in UDP, encapsulated in IP, encapsulated in Ethernet.
3. Ethernet frame broadcast (dest: FFFFFFFFFFFF) on LAN, is received at router running DHCP server
4. Ethernet is demux’ed from IP to DHCP
5. DCP server formulates DHCP ACK containing client’s IP address, IP address of first-hop router for client, name & IP address of DNS server
6. Encapsulated DHCP server reply forwarded to client, demuxing up to DHCP at client
7. Client now knows its IP address, name and IP address of DNS server, IP address of its first-hop router
:::
1. Allows reuse of addresses (only hold address while connected/on)
2. Supports for mobile users who join/leave network
3. DHCP can return more than just allocated IP address on subnet:
1. Address of first-hop router for client
2. Name and IP address of DNS sever
3. Network mask (indicating network versus host portion of address)
2. How does network get subnet part of IP address?
It gets allocated portion of its provider ISP’s address space.
3. How does an ISP get block of addresses?
ICANN (Internet Corporation for Assigned Names and Numbers)
### Network Address Translation (NAT)
:::info
:::
1. All devices in local network have 32-bit addresses in a “private” IP address space (`10/8`, `172.16/12`, `192.168/16` prefixes) that can only be used in local network
1. Only one IP address is needed from provider ISP for all devices
2. Addresses of host in local network can be changed without notifying outside world
3. ISP can be changed without changing addresses of devices in local network
4. Devices inside local net not directly addressable, visible by outside world
2. Implementation
:::info
:::
1. Outgoing datagrams wil be replaced (source IP address, port number) by (NAT IP address, new port number)
2. Every (source IP address, port number) to (NAT IP address, new port number) translation pair will be remembered in NAT translation table
3. Incoming datagrams will be replace (NAT IP address, new port number) in destination fields with corresponding (source IP address, port number) stored in NAT table
### IPv6
#### Transition from IPv4 to IPv6
* Tunneling and Encapsulation
## Generalized Forwarding
### Rules
1. Match: Patterns values in packet header fields
2. Actions: For matched packet, drops, forwards, modifies, matched packet or send matched packet to controller
3. Priority: Disambiguate overlapping patterns
4. Counters: Number of bytes and number of packets
### Openflow
#### Router
1. Match: Longest Destination IP Prefix
2. Action: Forwards out a link
#### Switch
1. Match: Destination MAC Address
2. Action: Dorwards or floods
#### Firewall
1. Match: IP Addresses and TCP/UDP Port Numbers
2. Action: Permits or denies
#### NAT
1. Match: IP Address and Port
2. Action: Rewrites address and port
## Middleboxes
A middlebox is defined as any intermediary device performing functions other than the normal, standard functions of an IP router on the datagram path between a source host and destination host.
# Control Plane
## Routing Algorithms
### Classification
### Algorithms
1. Message Complexity
1. Link State: If there are $n$ routers, $O(n^2)$ messages will be sent
2. Distance Vector: Messages are exchanged between neighbors. So convergence time varies.
2. Speed of Convergence
* Distance Vector:
Convergence time varies
:::info
It may have routing loops
:::
3. Robustness: What happens if router malfunctions, or is compromised?
1. Link State
1. Router can advertise incorrect link cost
2. Each router computes only its own table
2. Distance Vector
1. Distance vector router can advertise incorrect path cost
2. Each router’s table used by others cause error propagate through network
#### Link State
* Dijkstra’s Link-State Routing Algorithm
1. [Algorithm](/@roger61205/Algorithms-Dijkstras-Algorithm)
2. Properties
The algorithm is
1. Centralized: All routers have complete topology, link cost info
2. Iterative
3. Oscillation
#### Distance Vector
1. Bellman-Ford Equation
$$
D_x(y)=min_v\{c_{x,y}+D_v(y)\}
$$
* $D_x(y)$: The cost of least-cost path from $x$ to $y$
* $min_v$: The min taken over all neighbors $v$ to $x$
* $c_{x,y}$: The direct cost of link from $x$ to $v$
* $D_v(y)$: $v$'s estimated least-cost-path cost to $y$

2. Distance Vector Algorithm
* Algorithm
1. From time-to-time, each node sends its own distance vector estimate to neighbors.
2. When $x$ receives new DV estimate from any neighbor, it updates its own DV using B-F equation
$D_x(y)\leftarrow min_v\{c_{x,y}+D_v(y)\},\ for\ all\ y\in N$
Under minor, natural conditions, the estimate $D_x(y)$ converge to the actual least cost $d_x(y)$
3. Each local iteration caused by local link cost change and DV update message from neighbor
4. Each node notifies neighbors only when its DV changes, so if no notification is received, no actions are taken.

:::info
:::
The solution of count-to-infinity is that, instead of sending "my new cost to $x$ will be $6$" to $z$, $y$ should send "my new cost to $x$ will be $\infty$", then $z$ will realize its shortest path to $x$ is $50$.
## Routing Protocols of Autonomous System (AS)
1. Intra-AS: Routing among within Same AS
1. All routers in AS must run same intra-domain protocol
2. Routers in different AS can run different intra-domain routing protocols
3. Gateway routers are routers at edge of its own AS, having link(s) to router(s) in other AS’es.
2. Inter-AS: Routing among AS'es
Forwarding table is configured by intraand inter-AS routing algorithms.
### Inter-AS and Intra-AS
#### Inter-AS
To determine which gateway router should the packet outside of the AS sent to, AS1 inter-domain routing must
1. learn which destinations reachable through AS2, which through AS3
2. propagate this reachability info to all routers in AS1
* BGP(Border Gateway Protocol)
* BGP allows subnet to advertise its existence, and the destinations it can reach, to rest of Internet.
* BGP provides each AS a means to
1. eBGP: obtain subnet reachability information from neighboring ASes
2. iBGP: propagate reachability information to all AS-internal routers.

and determine “good” routes to other networks based on reachability information and policy.
1. BGP Path Advertisment
:::info
Two BGP routers exchange BGP messages over semi-permanent TCP connection advertising paths to different destination network prefixes (BGP is a “path vector” protocol).
When AS3 gateway 3a advertises path AS3,X to AS2 gateway 2c and AS3 promises to AS2 it will forward datagrams towards X.
:::
1. Path Attributes and BGP Routes
1. BGP Advertised Route: Prefix + Attributes
1. Prefix: destination being advertised
2. Two Important Attributes:
1. AS-PATH: list of ASes through which prefix advertisement has passed
2. NEXT-HOP: indication of specific internal-AS router to next-hop AS
2. Policy-Based Routing
1. Gateway receiving route advertisement uses import policy to accept/decline path
2. AS policy also determines whether to advertise path to other other neighboring ASes
3. Hot Potato Routing
BGP will choose local gateway that has least intra-domain cost, even though more AS hops to $X$.

:::info
:::
2. BGP messages
1. OPEN: It opens TCP connection to remote BGP peer and authenticates sending BGP peer
2. UPDATE: It advertises new path or withdraws old path
3. KEEPALIVE: It keeps connection alive in absence of UPDATES and ACKs OPEN request
4. NOTIFICATION: It reports errors in previous msg and is used to close connection
3. Route Selection
1. Local Preference value attribute: Policy decision
2. Shortest AS-PATH
3. Closest NEXT-HOP Router: Hot potato routing
4. Additional Criteria
2. Intra-AS
1. RIP(Routing Information Protocol)
2. EIGRP(Enhanced Interior Gateway Routing Protocol)
* Distance vector based protocol
3. OSPF(Open Shortest Path First)
1. Link-State Routing
1. Each router floods OSPF link-state advertisements (directly over IP rather than using TCP/UDP) to all other routers in entire AS
2. Each router has full topology, uses Dijkstra’s algorithm to compute forwarding table
2. Security
All OSPF messages are authenticated
## SDN Control Plane
### Per-Router Control Plane and Software-Defined Networking (SDN) Control Plane
1. Per-Router Control Plane
Individual routing algorithm components in each and every router interact in the control plane to computer forwarding tables
2. Software-Defined Networking (SDN) Control Plane
Remote controller computes, installs forwarding tables in routers
### Structures
1. Data-Plane Switches
1. Fast, simple, commodity switches will implement generalized data-plane forwarding in hardware.
2. Flow table will be computed and installed under controller supervision.
2. SDN Controller (Network OS)
1. Functionalities
1. Maintainance of network state information
2. Interaction with network control applications “above” via northbound API
3. Interaction with network switches “below” via southbound API
4. Implementing as distributed system for performance, scalability, fault-tolerance, robustness
2. Components
* OpenFlow Protocol
1. It operates between controllers, switches
2. TCP is used to exchange messages
3. Three Classes of OpenFlow Messages
1. Controller-to-Switch
1. Features: Controller queries switch features, switch replies
2. Configure: Controller queries/sets switch configuration parameters
3. Modify-State: Controller adds, deletes, modifies flow entries in the OpenFlow tables
4. Packet-Out: Controller can send this packet out of specific switch port
2. Asynchronous (Switch to Controller)
1. Packet-In: It transfers packet (and its control) to controller and see packet-out message from controller
2. Flow-Removed: Flow table entry will be deleted at switch
3. Port Status: It informs controller of a change on a port.
3. Symmetric
3. OpenDaylight (ODL) controller and ONOS controller
3. Network-Control Apps
### Control/Data Plane Interaction Example
:::info
:::
## ICPM(Internet Control Message Protocol)
ICPM is used by hosts and routers to communicate network-level information
1. Error Reporting: unreachable host, network, port, protocol
2. It echos request/reply (used by ping)
### ICMP Messages
ICMP messages are carried in IP datagrams, including type, code plus first 8 bytes of IP datagram causing error.
### Traceroute
:::info
:::
## Network Management
### Componenets
### Network Operator Approaches to Management
#### CLI (Command Line Interface)
#### SNMP/MIB
Operator queries/sets devices data (MIB) using Simple Network Management Protocol (SNMP).
1. SNMP
2. MIB
#### NETCONF/YANG
1. NETCONF operates between managing server and managed network devices
1. Actions: retrieve, set, modification, activation of configurations
2. Atomic-commit actions over multiple devices
3. It queries operational data and statistics
4. It subscribes to notifications from devices
2. YANG
YANG is a data modeling language used to specify structure, syntax, semantics of NETCONF network management data

**Reference**
NCKU 1102_F723500 Introduction to Computer Network
Computer Networking: A Top-Down Approach 8th edition Jim Kurose, Keith Ross Pearson, 2020