4 Network Layer
Click on a tile to change the color scheme:
Forwarding (data plane) and routing (control plane)
Control plane: how to determine the forwarding table? Traditional approach or SDN (Software defined networking) approach.
1. Inside a router
Destination-based forwarding or generalized forwarding
The forwarding table is copied from the routing processor to the line cards over a separate bus. Forwarding decisions can be made locally to avoid centralized processing bottleneck.
1.1 Input Port Processing & Destination-Based Forwarding
Lookup:
longest prefix matching rule
on-chip DRAM and faster SRAM; Ternary Content Addressable Memories (TCAMs)
1.1.1 Netmask
Ref: https://www.hacksplaining.com/glossary/netmasks
A netmask is a shorthand for describing a range of IP addresses, e.g. 192.168.0.1/32.
The left hand side of a netmask (e.g. 192.168.0.1) specifies a the host IP address. The right hand side specifies (e.g. /32) how many digits of the host address are significant, when considered as a binary number. Non-significant bits in the binary form are treated as a wild-card.
Apparently, the left part of a subnet mask consists of consecutive 1, and the right part consists of consecutive 0.
1.1.2 Routing Table
Ref: https://en.wikipedia.org/wiki/Routing_table
| Network destination | Netmask | Gateway | Interface | Metric |
|---|---|---|---|---|
| 0.0.0.0 | 0.0.0.0 | 192.168.0.1 | 192.168.0.100 | 10 |
| 127.0.0.0 | 255.0.0.0 | 127.0.0.1 | 127.0.0.1 | 1 |
| 192.168.0.0 | 255.255.255.0 | 192.168.0.100 | 192.168.0.100 | 10 |
| 192.168.0.100 | 255.255.255.255 | 127.0.0.1 | 127.0.0.1 | 10 |
| 192.168.0.1 | 255.255.255.255 | 192.168.0.100 | 192.168.0.100 | 10 |
- The columns Network destination and Netmask together describe the Network identifier as mentioned earlier. For example, destination 192.168.0.0 and netmask 255.255.255.0 can be written as 192.168.0.0/24.
- The Gateway column contains the same information as the Next hop, i.e. it points to the gateway through which the network can be reached.
- The Interface indicates what locally available interface is responsible for reaching the gateway. In this example, gateway 192.168.0.1 (the internet router) can be reached through the local network card with address 192.168.0.100.
- Finally, the Metric indicates the associated cost of using the indicated route.
1.1.3 The Link-State (LS) Routing Algorithm
Each node broadcasts link-state packets to all other nodes in the network.
All nodes have an identical and complete view of the network.
Dijkstra’s algorithm
1.1.4 The Distance-Vector (DV) Routing Algorithm
Iterative, asynchronous, and distribute:
It is distributed in that each node receives some information from one or more of its directly attached neighbors, performs a calculation, and then distributes the results of its calculation back to its neighbors.
It is iterative in that this process continues on until no more information is exchanged between neighbors.
The algorithm is asynchronous in that it does not require all of the nodes to operate in lockstep with each other.
Bellman-Ford equation: \(dist(x, end) = \min_v(w(x, v), dist(v, end))\), while \(v\) is one of x's neighbor.
The solution to the Bellman-Ford equation provides the entries in node x’s forwarding table.
With the DV algorithm, each node x maintains:
- the cost c(x, v) from x to directly attached neighbor, v
- Node x’s distance vector, that is, \(D_x=[D_x(y): y \in N]\), containing x’s estimate of its cost to all destinations y, in N
- Distance vectors of each of its neighbors, that is, \(D_v=[D_v(y): y \in N]\) for each neighbor v of x
1.1.5 Routing Information Protocol
Based on UDP. Relationship and position in the network packets:
IP Header (e.g. 20Bytes)
UDP Header (8 Bytes)
RIP Packet
Structure of RIPv2 (Ref: RFC 2453):
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| command (1) | version (1) | must be zero (2) | // header (4 Bytes)
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address Family Identifier (2) | Route Tag (2) | // entry follows
+-------------------------------+-------------------------------+
| IP Address (4) |
+---------------------------------------------------------------+
| Subnet Mask (4) |
+---------------------------------------------------------------+
| Next Hop (4) |
+---------------------------------------------------------------+
| Metric (4) | // total: 24 Bytes
+---------------------------------------------------------------+
// more entries (total <= 25) may follow
1.2 Switching
1) Switching via mem.
2) Switching via a bus.
3) Switching via an interconnection network.
1.3 Output Port Processing
selecting, de-queueing, link- and physical-layer functions
1.4 Queueing
1.4.1 Input queueing
\(R_{switch} = N R_{line}\), negligible queuing
Problem: head-of-the-line (HOL) blocking (may cause unbounded queue size)
1.4.2 Output queueing
Though \(R_{switch} = N R_{line}\), unbounded queue size!
1.4.3 Buffer size
Rule of thumb: \(RTT \times Capacity\)
(Recent: \(RTT \times Capacity / \sqrt N\), where N denotes the number of TCP flows)
1.4.4 Packet Scheduling
FIFO/FCFS
Priority queueing
Round robin queuing -> weighted fair queuing (WFQ): class i will receive a fraction \(w_i \over \Sigma w_j\) of the bandwidth.
2. The Internet Protocol (IP)
2.1 IPv4
Ref: IPv4 - Wikipedia
Internet Header Length (IHL): [20, 60] Bytes
2.1.1 IPv4 Datagram Fragmentation
Maximum Transmission Unit
2.1.2 Classification
| A类IPv4地址 | B类IPv4地址 | C类IPv4地址 | D类IPv4地址 | E类IPv4地址 | |
|---|---|---|---|---|---|
| 网络标志位 | 0 | 10 | 110 | 1110 | 11110 |
| IP地址范围 | 1.0.0.0~127.255.255.255 | 128.0.0.0~191.255.255.255 | 192.0.0.0~223.255.255.255 | 224.0.0.0~239.255.255.255 | 240.0.0.0~247.255.255.255 |
| 可用IP地址范围 | 1.0.0.1~127.255.255.254 | 128.0.0.1~191.255.255.254 | 192.0.0.1~223.255.255.254 | ||
| 是否可以分配给主机使用 | 是 | 是 | 是 | 否 | 否 |
| 网络数量（个） | 126 (\(2^7 - 2\)) | 16384 (\(2^{14}\)) | 2097152 (\(2^{21}\)) | --- | --- |
| 每个网络中可容纳主机数（个） | 16777214 (\(2^{24}-2\)) | 65534 (\(2^{16}-2\)) | 254 (\(2^8-2\)) | --- | --- |
| 适用范围 | 大量主机的大型网络 | 中等规模主机数的网络 | 小型局域网 | 留给Internet体系结构委员会(IAB)使用【组播地址】 | 保留，仅作为搜索、Internet的实验和开发用 |
IP地址根据网络号和主机号来分，分为A、B、C三类及特殊地址D、E。 全0和全1的都保留不用。
A类：(1.0.0.0-126.0.0.0)（默认子网掩码：255.0.0.0或 0xFF000000）第一个字节为网络号，后三个字节为主机号。该类IP地址的最前面为“0”，所以地址的网络号取值于1~126之间。一般用于大型网络。
B类：(128.0.0.0-191.255.0.0)（默认子网掩码：255.255.0.0或0xFFFF0000）前两个字节为网络号，后两个字节为主机号。该类IP地址的最前面为“10”，所以地址的网络号取值于128~191之间。一般用于中等规模网络。
C类：(192.0.0.0-223.255.255.0)（子网掩码：255.255.255.0或 0xFFFFFF00）前三个字节为网络号，最后一个字节为主机号。该类IP地址的最前面为“110”，所以地址的网络号取值于192~223之间。一般用于小型网络。
D类：是多播地址。该类IP地址的最前面为“1110”，所以地址的网络号取值于224~239之间。一般用于多路广播用户[1] 。
E类：是保留地址。该类IP地址的最前面为“1111”，所以地址的网络号取值于240~255之间。
2.1.3 DHCP
2.1.4 Network Address Translator
3. 网络层的服务方式
3.1 无连接服务
所有的数据包被独立送入网络，每个包独立路由，不提前建立任何设置。
路由算法
3.2 有连接服务
Virtual Circuit
-
逻辑连接，不同于真正的物理连接。
-
所有分组都沿着这条逻辑连接按存储转发发送。
-
转发策略：基于分组标签，i.e. 虚电路号
-
Label Switching：
R4根据输入的端口和标签查表得到出口和“标签”，R4需要将原来的标签L1替换为L2再发出去。
-
按需到达。
-
问题：链路中任何一个环节失效则经过它的所有VC失效。