Taogen's Blog

算法分析方法

• 渐进分析（Asymptotic Analysis）

常见的算法设计策略

• 动态规划（Dynamic Programming）
• 分治（Divide and Conquer）
• 贪心（Greedy Algorithm）
• 回溯（Backtracking）

常见的排序算法

• 插入排序（Insertion Sort）
• 冒泡排序（Bubble Sort）
• 选择排序（Selection Sort）
• 希尔排序（Shellsort）
• 归并排序（Mergesort）
• 快速排序（Quicksort）
• 堆排序（Heapsort）
• 基数排序（Radix Sort）

常见的搜索算法

• 二分查找（Binary Search）

常见的数据结构操作算法

• 二叉树的遍历（递归和循环实现方式）
  • 先序遍历（Pre-order Traversal）
  • 中序遍历（In-order Traversal）
  • 后序遍历（Post-order Traversal）
  • 层级遍历（Level-order Traversal）
• 图的搜索
  • 深度优先搜索（Depth-first Search, DFS）
  • 广度优先搜索（Breadth-first Search, BFS）

算法策略

算法策略是指设计和解决一类问题的通用方法或模板。也可以称为算法范式（Algorithm Paradigm）。常见的算法策略，如动态规划、分治、贪心和回溯等。每个算法策略有它的设计思路，解题步骤。算法策略往往提供了优化算法的功能，使用算法策略比直接法（枚举法，穷举法）有更好的效率。

动态规划

介绍动态规划

动态规划（Dynamic Programming）是一种数学优化方法和一种算法策略。这个方法是 Richard Bellman 在1950 年发明的。它指的是通过递归的方式，将问题分解为更简单的子问题，从而简化一个复杂的问题。

动态规划问题必须具备两个属性：最优子结构和重叠的子问题。如果一个问题有最优子结构，但没有重叠的子问题，那么它是一个分治问题。

最优子结构（Optimal Substructure）。如果一个问题可以通过“将问题分解为子问题和递归地找到子问题的最优解”来最优地解决，那么称它有最优子结构。也可以说，得到一个问题的最优解可以通过子问题的最优解来实现。如果一个问题具有最优子结构，较大问题和它的子问题之间的存在关联，这种关系称为 Bellman 方程。

重叠的子问题（Overlapping Sub-Problem）。求解过程中递归地求解相同的子问题，没有产生新的子问题。也可以说，问题和子问题存在一个固定的关系表达式，如 F(n) = F(n-1) + F(n-2) ，F(n) = F(n-1) * 2 + 1。所有的子问题可以用一个固定的算法代码去实现。

解决动态规划问题的两种方法：

• 自顶向下方法（Top-down Approach）。将子问题的结果存储在列表中，当我们要解决新的子问题时，我们会首先检查是否已经解决。如果结果已经记录在列表中，可以直接使用它，否则我们解决子问题并将其结果添加到列表中。如：我们可以通过 F(n) = F(n-1) + F(n-2) 得到问题的结果，先检查子问题结果列表中有没有子问题 F(n-1) 和 F(n-2) 的结果，如果有就直接使用，没有就求解这两个子问题。依次往下递归，每个子问题只计算一次。
• 自底向上方法（Bottom-up Approach）。一旦按照子问题递归地制定了问题地解决方案，我们可以尝试自底向上地去解决问题。自底向上地方法大部分不需要记录每个子问题的结果，只需要替换记录几个需要地子问题结果。具体过程：通过使用较小的子问题的结果迭代生成越来越大的子问题结果。如，已知子问题 F40 和 F41 的结果，可以直接计算出 F42 的结果。

解题步骤

1. 判断一个问题是否是动态规划问题。

判断问题是否具有最优子结构和重叠的子问题等特性。

2. 构造出问题与子问题之间的关系表达式

常见的动态规划问题的子问题关系表达式，见附录一

3. 使用自顶向下或者自底向上求解。

例子

求第 n 个斐波那契数。

直接法简单的解决方法。T(n) = O(2 ^ n), S(n) = O(1)

int fib(int n)
{
	if (n <= 1)
		return n;
	return fib(n-1) + fib(n-2);
}

动态规划自顶向下方法。T(n) = O(n), S(n) = O(n)

int fib(int n, auto &lookup)
{
	if (n <= 1)
		return n;
	if (lookup.find(n) == lookup.end())
		lookup[n] = fib(n-1, lookup) + fib(n-2, lookup);
	return lookup[n];
}

动态规划自底向上方法。T(n) = O(n), S(n) = O(1)

int fib(int n)
{
	if (n < 1)
		return n;
	int prev = 0, curr = 1;
	for (int i = 0; i < n-1; i++)
	{
		int newFib = prev + curr;
		prev = curr;
		curr = newFib;
	}
	return curr;
}

分治

介绍分治

分治（Divide and Conquer）是一个基于多分支递归的算法设计范式。它将一个问题递归的分解为两个或多个子问题，直到它们足够简单能够直接求解。

解题步骤

分析问题得到分解策略。

根据分解策略，递归地求解。

例子

参考快速排序、归并排序算法。

贪心

介绍贪心算法

贪心算法（Greedy Algorithm）是一个算法设计范式。它在每个阶段做出局部最优选择，以寻求全局最优。

解题步骤

根据贪心策略一小段一小段的求解，最后得到问题的最优解。

回溯

介绍回溯

回溯（Backtracking）是一种算法范式，用于查找某些计算问题的所有结果。它逐步的构建候选对象，一旦确定候选对象无法得到有效的结果立刻将其放弃。

回溯是解决约束满足问题的重要工具。它可以快速测试是否能得出满足条件的有效结果。如填字游戏，数独，棋盘等问题。回溯算法通常比对所有对象的暴力枚举（Brute Force Enumeration）更有效率，因为它通过一个测试减少了很多候选对象。

常见类型：

• 路径选择。如：最短路径，是否存在路径，打印所有存在路径。这类问题的背景：迷宫，国际象棋，二维数组，图。

解题步骤

1. 判断是否是一个回溯问题。

2. 设定一个开始点，进行循环遍历。

3. 当前结果是否满足条件。如果是，打印结果。如果不是，循环递归所有的有效的下一个候选对象。

例子

N Queens problem.

#include <iostream>
#include <cstring>
using namespace std;

#define N 8

int count = 0;

bool isSafe(char mat[][N], int row, int col)
{
	for (int i = 0; i < row; i++)
	{
		if (mat[i][col] == 'Q')
		{
			return false;
		}
	}
	
	for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
	{
		if (mat[i][j] == 'Q')
		{
			return false;
		}
	}
	
	for (int i = row, j = col; i >= 0 && j < N; i--, j++)
	{
		if (mat[i][j] == 'Q')
		{
			return false;
		}
	}
	
	return true;
}

void NQueen(char mat[][N], int row)
{	
	if (row == N)
	{
		cout << ++count << endl;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cout << mat[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;
		return;
	}
	
	// place Queen at every square in current row r
    // and recur for each valid movement 
	for (int k = 0; k < N; k++)
	{
		if (isSafe(mat, row, k))
		{
			// place queen on current square
			mat[row][k] = 'Q';
			// recur for next row
			NQueen(mat, row+1);
			// backtrack and remove queen from current square 
			mat[row][k] = '-';
		}
	}
	return;
}

int main()
{
	// mat[][] keeps track of position of Queens in current configuration
	char mat[N][N];
	
	// initalize mat[][] by '-'
    memset(mat, '-', sizeof mat);
	
	int row = 0;
	NQueen(mat, row); // N=8 has 92 possible N-Queen result 
	return 0;
}

关于算法设计的思路

1. 思考问题的直接法的解决方法。

2. 考虑优化。是否存在大量重复的操作？是否存在不必要的操作？

3. 考虑算法设计策略。

问题的局部最优解能不能得到全局最优。如果能，考虑使用贪心算法。

问题能不能递归地分解为子问题求解（是否具有最优子结构）。如果能，考虑使用分治法，或者动态规划。

附录一

常见的动态规划问题的子问题关系表达式。

Fibonacci

         | n                  (n <= 1)
Fib(n) = |
         | Fib(n-1) + F(n-2)   (n > 1)

Longest Common Subsequence (LCS)

             | 0                              (i == 0 or j == 0)
LCS[i][j] =  | LCS[i-1][j-1] + 1              (X[i-1] = Y[j-1])
             | max(LCS[i-1][j], LCS[i][j-1])  (X[i-1] != Y[j-1])

Shortest Common Supersequence (SCS)

             | i+j                            (i=0 or j=0)
SCS[i][j] =  | SCS[i-1][j-1] + 1              (X[i-1] = Y[j-1])
             | min(SCS[i-1][j] + 1, SCS[i][j-1] + 1)  (X[i-1] != Y[j-1])

Longest Increasing Subsequence (LIS)

         | 1    (n=1)
LIS(n) = | 
         | max(L(i))    0 < i <= n

The Levenshtein distance (Edit distance)

             | max(i, j)                       when min(i, j) = 0
             
dist[i][j] = | dist[i - 1][j - 1]              when X[i-1] == Y[j-1]
             
             | 1 + minimum { dist[i - 1][j],   when X[i-1] != Y[j-1]
             |               dist[i][j - 1],
             |               dist[i - 1][j - 1] }

References

[1] Dynamic programming - Wikipedia

[2] How to solve a Dynamic Programming Problem ? - Geeksforgeeks

[3] Introduction to Dynamic Programming - Techie Delight

[4] Divide-and-conquer algorithm - Wikipedia

[5] Backtacking - Wikipedia

基本数据结构

List

List 的抽象数据类型

列表（List）包含一组按顺序排列的相同类型的元素，它的操作如下：

• get() - 返回给定位置的一个元素。
• insert() - 插入一个元素在指定位置。
• remove() - 删除第一个元素。
• removeAt() - 删除一个特定位置的元素。
• size() - 返回列表元素的数量。
• isEmpty() - 返回列表是否为空。
• isFull() - 返回列表是否已满。
• clear() - 清空列表的内容。

List 的实现

Array List

数组是列表的一种实现，它在内存中是连续的空间。

优点

• 它可以快速的随机访问。

缺点

• 插入和删除性能不太好，需要大量的元素位置移动。

应用场景

• 简单的存储一组数据。

Linked List

链表是一个线性结构，它是列表的另一种实现，它在内存中是非连续的空间。每个元素称为节点，相邻的两个节点由指针进行连接。

优点

• 它具有很好的扩展性，快速的插入和删除。

缺点

• 随机访问（按位置访问）性能不好。节点的访问必须从前往后依次遍历。
• 比数组消耗更多的内存。在使用的指针上。
• 需要更多的读取时间。在内存中是不连续的，CPU 一次只能获取一个元素，

应用场景

• 迭代器。

Array List vs Linked List

Stack

Stack 的抽象数据类型

栈（Stack）是一个线性的数据结构。它遵循一个特殊的操作顺序。后进先出（Last In First Out, LIFO），它的操作如下：

• push()
• pop()
• peek()
• size()
• claer()

Stack 的实现

栈可以基于数据实现，也可以基于链表实现。

优点

• 方便的按照某种循序访问数据。

缺点

• 只用于特定场合。

应用场景

• 逆序输出。
  • 进制转换。
• 递归嵌套。
  • 括号匹配
  • 栈混洗（Stack Permutation）。通过一个中间栈，重新排序原始栈的数据顺序。。
• 延迟缓冲。
  • 中缀表达式。操作符以中缀形式处于操作数中间的算术表达式。
  • 逆波兰表达式。不需要括号的后缀表达式。
• 栈式计算。

Queue

Queue 的抽象数据类型

队列（Queue）是一个线性结构。它和栈类似有特殊的操作顺序。先进先出（First In First Out, FIFO）。它的操作如下：

• enquque()
• dequeue()
• peek()
• size()
• claer()

Queue 的实现

队列可以基于数组实现，也可以基于链表实现。

优点

• 方便的按照某种循序访问数据。

缺点

• 只使用在特定的场合。

应用场景

• 系统任务调度。

Binary Tree

Binary Tree 的抽象数据类型

二叉树（Binary Tree）是一个树结构，每个节点最多有两个子节点，分别表示为左子树和右子树。它的操作：

• getRoot()
• isEmpty()
• size()
• contains()
• find()
• toString()
• iteratorInOrder()
• iteratorPreOrder()
• iteratorPostOrder()
• iteratorLevelOrder()

Binary Tree 的实现

二叉树通过指针关联节点实现。

优点

• 可以表示树结构的数据关系。

缺点

• 大量的指针消耗。

应用场景

• 用于搜索。通过 binary search tree 可以支持快速的搜索、插入和删除，复杂度都是 O(log n)。
• 用于压缩。使用在 Huffman Coding。
• 用于数据库的索引的实现。

Graph

Graph 的抽象数据类型

图（Graph）由一组有限个顶点（Vertex）和有限的边（Edge）组成。它的操作如下：

• addVertex(vert)
• addEdge(fromVert, toVert)
• addEdge(fromVert, toVert, weight)
• getVertex(vertKey)

Graph 的实现

图可以通过邻接表（adjacency List），也可以邻接矩阵（adjacency Matrix）实现。

应用场景：

• 用于计算机网络的路由，找到最小花费路径。

• 社交媒体应用，用户之间的关联。

• 地图应用。如，找到最优的行驶路线。

• 电商网站。推荐商品。

其它数据结构

Dictionary

Dictionary 的抽象数据类型

字典（Dictionary）高效地组织数据，支持快速地存储和查找。每个元素由一个 key 和一个复合类型（对象）组成<key, E>。通过 key 来唯一标识一个对象，可以通过 key 来查找对象。它的操作如下：

• insert(key, object)
• remove(key)
• find(key)
• size()
• clear()

Hash Table

Hash Table 的抽象数据类型

哈希表（Hash Table）是一个由链表组成的数组结构。它使用哈希函数计算一个元素值在数组中的索引。它的操作：

• put(key, value)
• get(key)
• containsKey(key)
• contains(value)
• remove(key)

Hash Table 的实现

哈希表由链表数组实现。

优点

• 快速的查找。
• 快速的插入和删除。

缺点

• 不保证元素的顺序。不能随机访问。

数据结构的选择

插入删除/扩展性

数据的容量需要很好的扩展性，或者频繁的插入和删除，选择动态的数据结构（指针关联）比较合适。如链表，二叉树等等。不足之处是指针结构对随机存取效率没有静态结构（连续空间）好。

搜索

简单的搜索即从第一个元素一直比较直到最后一个元素。如数组，它的复杂度是 O(n)。

更高效率搜索的数据结构，哈希表的复杂度为 O(1)，有序数组复杂度为 O(log n)，搜索二叉树的复杂度为 O(log n)

综合考虑

兼顾搜索和插入：可以考虑哈希表和搜索二叉树。有序数组虽然搜索复杂度和搜索二叉树一样，但是有序数组的插入性能不好。

兼顾搜索和随机存取：可以考虑有序数组。

数据结构的总结

组成形式：连续空间，不连续（指针）空间。

结构关系类型：线性，树状，图

本质：存储一组元素，表示元素之间的关系，提供操作元素的方法。

数据结构的总结：

• 数据结构是用来表示数据和操作数据的。

• 有些数据结构只适用于特殊的场景。

• 一个好的数据结构可以大幅度提高算法的效率。

• 不存在一种数据结构在所有方面都优于另一个数据结构，每个数据结构都有自己的优缺点。数据结构的选择是一个权衡利弊和妥协的过程。

References

[1] Data Structures and Algorithm Analysis in C++ (3rd) by Clifford A. Shaffer

[2] Abstract Data Types - GeeksforGeeks

[3] The BinaryTree ADT

[4] The Graph Abstract Data Type

[5] Linked List - Wikipedia

[6] What are the applications of binary trees? - Stack Overflow

[7] What are real life applications of graphs? - Quora

大多数计算机程序的主要目的不是计算，而是存储和取出信息。面对大量的信息，我们要如何组织信息，使它能支持更高效的处理？这就是数据结构需要解决的问题。在特定问题下，我们可以根据不同的数据结构它们对应的花费和收益，选择一个更高效更快的数据结构。

解决一个问题常常由很多方法。我们要如何选择？首先，我们要知道程序设计的核心是什么？它主要是实现以下两个目标：

1. 设计一个易于理解、实现和调试的算法。
2. 设计一个更高效的使用计算机资源的算法。

第一点指的是程序的优雅，第二点是指程序的效率。在算法领域，我们主要是探究算法的效率。一个问题最优的解决方案就是找到一个效率最高的算法。

如何知道一个算法比另一个算法更好？这就要测量一个算法的效率。一个常见的用来估计算法的效率的方法称为渐进分析（Asymptotic Analysis）。

抽象数据类型和数据结构

类型（Type）是指一组值。如布尔类型由 true 和 false 组成。整数也是一个类型。类型可以分为：简单类型（Simple Type）和复合类型（Composite Type）。一个数据项只有一个成员的类型称为简单类型。如整数类型。一个数据单元由多个成员组成的类型称为复合类型。如银行帐号的个人信息。

数据类型（Data Type）它指的是一个类型和一组操作。

抽象数据类型（Abstract Data Type，ADT）它定义了一个类型和一组的操作。它是数据类型的逻辑实现。

数据结构（Data Structure）是一个 ADT 的在编程语言上的具体实现。它是数据类型的物理实现。

数据类型只是一个称呼，它没有具体的内容。抽象数据类型是数据类型的抽象的（或逻辑的）表示，它表示了有哪些具体的操作，定义了类型的名称和操作的名称，它是描述文字。数据结构是用具体的编程语言代码对 ADT 的定义，它是可执行的代码。

问题，算法和程序

问题是一个要执行的任务。它表示为任意的输入得到匹配的输出。问题必须是明确定义的和能清晰理解的。问题的定义应该包含计算机资源的限制，如内存，硬盘和时间。

算法是解决一个问题的方法（或过程）。一个算法必须具备以下属性：

• 正确性。每一个输入能够转换为正确的输出。
• 可行性。算法中任何计算步骤可以被分解为基本的可执行的操作。
• 确定性。没有歧义的。
• 有穷性。能在执行有限个步骤之后终止。
• 输入项。0个或多个输入。
• 输出项。一个或多个输出。

程序是一个由编程语言实现的算法的实例（或具体的表现）。程序不像算法，程序是可以一直运行不终止的，如操作系统。

数据结构的选择

给定一个足够的空间去存储一组数据项，无论使用什么数据结构去表示这些数据，每种数据结构总是可能执行所有必要的操作，如搜索，排序，插入，删除等。然而使用不同的数据结构的区别在于，执行一个程序，一个只需要几秒钟，另一个则需要好几天。一个选择数据结构的方法如下：

• 分析问题需要哪些基本的操作。如插入，删除，查找。
• 量化每个操作的资源约束（时间和空间）。
• 选择满足需求的最好的数据结构。

每个数据结构有它相应的花费和收益。没有一个数据结构在任何情况下都比另一个数据结构好。你需要根据问题需求选择合适的数据结构。

算法的选择

一个好的数据结构的选择，可以做到事半功倍的效果。一个算法实现策略的选择也十分关键。简单地使用直接法（枚举法）可以解决问题，但效率很低，它与贪心策略或动态规划相比，算法执行的时间往往是数量级的差别。

算法的核心优化思路是去除不必要的操作和去除重复的操作。几乎所有的算法策略都是这个思路，如动态规划、分治法。

References

[1] Data Structures and Algorithm Analysis in C++ (3rd) by Clifford A. Shaffer

计算机网络的核心概念

应用层

你必须知道的应用层

• 应用层提供了两个进程之间的信息交换。它的报文定义了信息的格式和规则。
• HTTP 协议：它用于 Web 应用，它的报文格式为：请求/相应行 + 头部行 + 数据负载。
• DNS ：DNS 系统的等级结构？如何配置域名解析？获取一个域名的 IP 地址的过程？
• CDN 内容分发网络的基本概念。

传输层

你必须知道的传输层

• 传输层是两个进程之间的数据传输。它的报文定义了传输服务所需要的字段。
• TCP 是如何实现可靠数据传输和拥塞控制的？
• UDP 和 TCP 的区别？不同的场合如何选择合适传输层协议？

网络层

你必须知道的网络层

• 网络层是两个终端主机之间的数据交换。
• 数据包是如何在路由器中转发的？路由器的结构和工作原理？
• IP 寻址和子网的概念。
• 因特网的组成结构：它是由许多个 ISP 相互连接而成的图状结构。每个 ISP 是自治的网络。
• 路由算法是为了寻找两个主机之间的最小花费路径。常见的路由算法有哪些？它们是如何实现的？
• 网络是如何管理的？

链路层

你必须知道的链路层

• 链路层是两个相邻的节点之间的数据传输。
• 主机和路由器的每个网络接口既有 IP 地址也有 MAC 地址。
• 链路层使用 MAC 地址进行数据转发。
• ARP 协议可以通过一个局域网的 IP 地址获得对应的 MAC 地址。
• 以太网是流行的构建局域网技术。NAT 可以用来扩展局域网。
• 如何搭建一个安全、隔离、可扩展的局域网。

网络安全

你必须知道的网络安全

• 网络安全是保障网络服务的安全。
• 网络安全分为网络通信安全和运营安全。
• 实现网络通信安全的基本要素：保密性，完整性，终端认证。
• 实现网络通信安全的基础技术：加密算法，消息摘要算法，数字签名，服务端的公钥证书，客户端认证等。
• 网络安全协议：SSL，IPsec。它们的实现原理。它们的基本原理？
• 实现运营安全的技术：防火墙，入侵侦测系统和入侵防御系统。它们的基本原理？

网络协议

网络协议是为网络通信定义的规范。所有的网络协议的报文基本上是由三部分组成：

• 我（报文）从哪里来，要到哪里去。
• 报文的基本属性。
• 携带的通信数据。

五层网络协议栈总结：

计算机网络的五层网络协议栈，可用用现实生活中寄快递的例子来类比。

• 应用层：用户发送快递和接收快递。
• 传输层：用户选择使用哪家快递公司，即哪种运输服务。（不同的快递公司，运输的方式和快慢不一样）
• 网络层：快递公司如何将货物从出发地点运输到目标地点。如何规划合理的运输路线（一个运输路线由多个节点组成）。
• 数据链路层：快递公司如何保证两个相邻的节点之间的运输没有问题。
• 物理层：如何在两个相邻节点之间运输货物。如：司机驾驶货车在公路上运输货物、空运等。

介绍计算机网络安全

传统的网络协议在网络通信时，消息都是明文的传输。如 HTTP，TCP，IP，Ethernet 等等协议。然而，明文传输会遭到他人恶意的攻击，这些攻击会窃取客户端用户的隐私信息，阻止服务端的正常工作等等。常见的安全攻击类型有：恶意软件攻击，拒绝服务攻击，数据嗅探，IP 欺骗等等。

计算机网络安全问题可以归为两类：网络通信安全，运维安全。

常见的网络通信安全问题有：

• 消息窃听。
• 消息篡改。插入，删除消息内容。
• 消息伪造和重复消息。

保证网络通信的安全所需要的必要属性：

• 保密性（Confidentiality）。消息进行加密，保证只有通信双方知道消息的内容。
• 消息完整性（Integrity）。保证消息没有被修改。
• 终端认证（End-point Authentication）。确认通信对方的身份。

一个网络安全协议必须实现以上所需的功能，从而实现安全的网络通信。常见的网络安全协议有 PGP，SSL，IPsec 等。

运维安全是指阻止外界对服务提供机构网络的恶意网络攻击。常见的防御措施有：建立防火墙，入侵侦测系统和入侵防御系统等。

通过本小节我们了解了网络安全的基本概念，接下来我们将介绍实现网络安全功能的基础技术，如机密和完整性校验等；网络安全协议的基本概念；最后我们将了解防火墙和入侵侦测系统是如何保护一个组织网络的安全的。

实现网络安全的技术

加密算法

加密是指发送端发送加密的数据，入侵者不能从拦截的数据中获取原始的信息，接收端可以恢复原始的数据。原始消息称为明文（Plaintext），经过加密算法加密后的消息称为密文（Ciphertext）。加密算法通过明文 m 和密钥 K1 作为输入，产生密文作为输出。密文表示为 K1(m)。解密算法通过密文和密钥 K2 作为输入，产生明文作为输出。解密表示为 K2(K1(m)) = m。

我们常常把其它操作与加密（Encryption）产生混淆。如编码（Encoding）和消息摘要（Message Digest）。加密需要通过密钥来加密和解密，其他人没有密钥无法进行加密和解密。区分是不是加密的关键因素是：1. 只有使用密钥才能进行相关操作。2. 数据可以加密和还原。

编码是将一种数据格式转换为另一种格式，相应的操作为编码和解码。编码是任何人都可以操作，它不满足只有使用密钥才能进行相关操作的条件，所以它不是加密算法。常见的编码方式如 Base64。

消息摘要算法。通过 Hash 算法产生一个固定长度的值。它的转换是单向的。常用于数据完整性校验，存储用户密码信息。它没有密钥，也无法还原数据，所以它不是加密算法。常见的消息摘要算法如 MD5。

对称加密（Symmetric Encryption）

对称加密算法共享唯一的密钥进行加密和解密操作，常见的对称加密算法有：DES，3DES，AES 等。对称加密技术的类型有两种：流加密（Stream Ciphers），分组加密（Block Ciphers）。网络安全协议 PGP，SSL，IPsec 等大多使用分组加密技术。这里主要介绍分组加密技术。

分组加密：将消息明文划分为等长的块。每一个块独立加密。密文使用一对一映射，将 k bit 长度的明文块转换为 k bit 长度的密文块。一个 k bit 长的密文所有可能的有 2^k !，暴力破解几乎不可能做到。如暴力破解一个 128 位的 AES 密文大约需要100万亿年。

非对称加密（Asymmetric encryption）

非对称加密使用一对密钥即公钥（Public Key）和私钥（Private Key）来进行加密和解密，常见的算法如 RAS 算法。它可以让公钥公开在网络上分发，让客户端加密消息，但只有服务端才能解密。非对称加密不仅可以用于加密，也可以用于认证和数字签名。一般的用法时公钥加密，私钥解密。私钥签名，公钥验签。

RSA 的实现原理

生成公钥和私钥过程

• 选择两个大质数 p 和 q。
• 计算 n = pq, z= (p-1)(q-1)。
• 选择一个数字 e，小于 n，且与 z 没有公共因数。
• 找到一个数字 d，始得 ed - 1 能被 z 整除即 (ed - 1) % z = 0。
• 公钥是一对数字 (n, e)，私钥是(n, d)

加密和解密过程

设消息明文表示为 m，密文为 c。公钥为 (n, e)，私钥为 (n, d)

使用公钥对明文加密。加密计算公式： c = m ^ e % n

使用私钥对密文解密。解密计算公式： m = c ^ d % n

例子，

设 p=5, q=7, n= 35, z=24, e=5, d= 29

若明文为 m=12

加密计算 c = 12 ^ 5 % 35 = 17

解密计算 m = 17 ^ 29 % 35 = 12

RSA 算法工作原理

RSA 用到的基础理论：

• 取模运算转换公式：(a % n)^d % n = a^d % n。
• 数值理论转换。如果 p，q时质数，n=pq，z=(p-1)(q-1)，则 x^y % n = x ^ (y % z) % n。下面应用计算应用 x=m, y=ed.

证明过程：

RSA 加密公式为：c = m^e % n，解密公式为： m = c^d % n

由 c = m ^ e % n 推导 m = c ^ d % n 过程如下：

（1）将 c = m ^ e % n 代入解密公式等式，得 m = (m ^ e % n) ^ d % n

（2）由取模运算转换公式，得 m = m ^ ed % n

（3）由数值理论转换和已知条件 (ed - 1) % z = 0，得 m = m ^ (ed % z) % n = m ^ 1 % n = m % n

（4）由 m < n，得 m = m。等式左边等于右边，证明原等式成立。

消息完整性和数字签名

介绍消息完整性

认证消息的完整性（Message Integrity）需要实现以下功能：

• 验证消息来源自合法的终端。
• 验证消息没有被篡改。

实现消息完整性常用的技术有：数字签名（Digital Signatures）和终端认证（End-point Authentication）。

哈希算法和消息认证码

哈希算法将输入转换为固定长度的哈希值。哈希算法保证了任意的两个不同的值得到不同的 hash 值。常见的哈希算法有：MD5，Secure Hash Algorithm (SHA-1)。

传统的网络协议使用 checksum 校验消息完整性（数据分片和校验和相加结果为n个1），这种方式存在不同的消息可以存在相同的checksum。哈希值有唯一的特性，可以使用消息的哈希值检验完整性，这样更加安全可靠。

消息认证码

简单的使用哈希进行完整性校验的方式为：将消息 m 的哈希值 H(m) 附加到消息后面，组成新的消息message(m, H(m))。但是，这样的处理很容易被伪造消息。使用伪造一个新的消息，后面附加新消息的哈希值 message(m’, H(m’))，这同样也是一个具有完整性的消息。

为了防止伪造消息，可以使用加密的哈希方法（Cryptographic Hash Function），通信的双方需要共享一个密码 s 称为认证码（Authentication Code）。新的消息可以表示为 message(m+s, H(m+s))。这样入侵者不知道认证码，生成不了正确的哈希值。

数字签名（Digital Signature）

数字签名是一个加密技术，它指出了一个文档的拥有者是谁。数字签名具有的特性：可验证的，不可伪造的。

数字签名可以使用非对称加密实现。使用私钥加密，使用公钥验证。私钥是被唯一拥有的，公钥可以分发在网络上进行验证。可以对整个消息加密作为数字签名K(m)，但这样太耗费了。更好的做法是对消息的哈希值进行加密作为数字签名K(H(m))。

公钥证书（Public Key Certification）

数字签名的一个重要的应用就是公钥证书。公钥证书它证明一个公钥属于一个具体的实体。公钥证书使用在很多流行的安全网络协议，如 IPsec 和 SSL。

认证机构（Certification Authority, CA），它可以绑定一个公钥和一个特定的实体。它的工作是验证身份和发布证书。

CA 验证实体的身份后，CA 创建一个证书（Certificate），它绑定实体的公钥和身份。证书包含了公钥和实体的认证信息（人的名称，有效期）等等。

实际使用场景，如客户端浏览器访问一个 HTTPS 网址，建立 SSL Socket 连接时，服务器给客户端发送自己的公钥，客户端可以通过 CA 来验证接收到的公钥是不是该网址的公钥。

终端认证

终端认证（End-Point Authentication）指的是在网络上一个实体提供它的身份给另一个实体的过程。

不安全的客户端终端认证方式：

• 明文密码认证。可能被窃听，被他人获取密码。
• 加密密码认证。可能受到回放攻击（Playback Attack）。被他人窃取和利用加密后的密码。

安全的客户端终端认证：

• 使用 nonce 和加密的密码。一个 nonce 是一个数字仅仅在网络通信中使用一次，即每次通信使用不同的 nonce。这样可以防止他人利用加密后的密码。

网络安全协议

SSL

Secure Sockets Layer（SSL）是一个传输层协议，提供增强 TCP 的安全服务。SSL 提供了保密性，完整性，服务器认证，客户端认证等服务。SSL 的修改版本 SSL version 3 称为 Transport Layer Secure（TLS）。

SSL 建立连接的过程

• 三次握手
  • 客服端，发送 SYN。
  • 服务端，响应 SYN/ACK
  • 客服端，发送 ACK。
• 协商（Negotiation）
  • 客户端发送 Hello，以及支持的加密算法列表，和客户端 nonce（Random Number #1）。
  • 服务端响应，发送服务端选择的一个对称加密算法，一个非对称加密算法，一个 MAC 算法，SSL 证书，和服务端 nonce（Random Number #2）。
  • 客服端，验证证书，提取服务端公钥，生成一个 Pre-Master Secret（PMS），使用公钥加密 PMS，发送 PMS 和客户端证书（可选项）给服务端。
  • 服务端，使用私钥解密 Pre-Master Secret。
• 共享密码
  • 客户端和服务端，通过随机数 #1，#2 和 PMS 计算得到 Master Secret（MS）。使用MS 生成 两个 加密密钥，两个 MAC 密钥。
• 握手完成
  • 客服端，发送一个哈希消息使用主密码（MS）
  • 服务端，发送一个哈希消息使用主密码（MS）

SSL 实现安全通信的方法

• 保密性
  • SSL 使用非对称加密算法交换共享的对称加密密钥。
  • SSL 使用对称加密算法加密通信的数据。
• 完整性
  • 使用报文数据域附加的 MAC 进行完整性校验。
  • 通过 CA 验证服务端公钥的合法性。从而认证消息来自合法的终端。
• 服务端认证
  • 通过 CA 验证公钥的合法性。从而认证服务端。
• 防止回放攻击
  • 使用 nonce 防御连接回放攻击（Connection Playback Attack）
  • 使用MAC key + Sequence Number 生成MAC，防御数据包传输途中的回放攻击。

IPsec

IPsec （IP Security Protocol）提供网络层通信安全。它能够在所有主机和路由器上安全地传输网络层报文。IPsec 协议常用来在公共的因特网上创建一个虚拟专用网络（Virtual Private Network, VPN）。

一个机构跨越多个不同的地理区域常常想要自己的专用 IP 网络。但是搭建一个物理的专用网络代价太昂贵了，需要购买、安装和维护自己的物理网络基础设施。所以现实中通常使用 VPN 来搭建专用网络。

IPsec 的实现原理

IPsec 将原来正常的 IP 数据报转换为一个新的加密的 IP 数据报。

IPsec 创建一个新的 IP 报文：

• 创建新的 IP 报文头部。
• 将原始的IP 报头部和原始数据负载进行加密，加上 IPsec 头部，尾部和MAC等，组成新的 IP 报文的数据负载。

新的 IP 数据报头部和传统的 IPv4 头部相同，对于路由器来说它和正常的 IP 报文没什么区别。

IPsec 在客户端主机中将传输层的数据封装成加密的 IP 报文，在服务端主机中解密 IP 报文传给传输层。

AH 和 ESP 协议

Authentication Header（AH）协议和 Encapsulation Security Payload （ESP）协议为 IPsec 提供安全通信服务的子协议。IPsec 协议套件需要使用其中的一个协议来实现安全通信。

AH 协议提供终端认证和数据完整性，不提供保密性。

ESP 协议提供 终端认证，数据完整性，和保密性。

因为 ESP 协议提供完整的安全通信功能，所以它比 AH 协议使用更广泛。

安全关联

在 IPsec 协议中，源地址和目标地址创建的一个逻辑连接称为一个安全关联（Security Association，SA）。它是单向的，所以两个终端之间的通信需要建立两个 SA。SA 维护了 IPsec 通信的重要信息，如 加密算法类型，加密密钥，认证密钥等等。客户端和服务端都需要维护 SA 信息，SA 存储在 Security Association Database （SAD）中。通过 SA 中的信息终端主机可以进行加密，解密和认证等操作。

IPsec 的数据报

IPsec 的数据报格式如下图所示：

IPsec vs SSL

• 安全性。IPsec 和 SSL 都可以提供了安全的网络通信。
• 便利性。IPsec 需要一个第三方客户端软件。实现更复杂，更高的维护成本。SSL 已经在浏览器中支持了不需要额外的软件和配置。
• 服务。IPsec 位于网络层，提供全接入的安全网络，即两个主机之间建立安全连接。而 SSL 位于传输层，只能针对某个应用进程提供安全连接。

HTTPS

HTTPS 它是 HTTP 的一个扩展。它本身并不提供安全服务，它使用传输层 SSL 来进行安全通信。HTTPS 本质是 HTTP + SSL。所以，严格意义上它不算是网络安全协议。

HTTPS 和 HTTP 报文格式相同，只是 HTTPS 建立的是 SSL Socket 连接，而 HTTP 建立的是 TCP Socket 连接。

其它安全协议

更多安全网络通信协议，如 Email 安全和无线网络安全，可阅读后面给出的参考书籍。

运维安全

运维安全（Operational Security）是指阻止外界对服务提供机构网络的恶意网络攻击。它的是实现方法为：在一个计算机网络中，进入和离开一个网络时，进行安全的检查，记录，丢弃，和转发。它的实现技术为：防火墙（Firewall），入侵检测系统（Intrusion Detection System, IDS）和入侵防御系统（Intrusion Prevention System, IPS）

防火墙

防火墙允许网络管理员可以控制网络访问，在外部网络和内部网络之间。

防火墙的定义：

• 所有的进入和外出的网络流量需要经过防火墙。
• 只有授权的流量时允许通过的。
• 防火墙本身是免疫渗透攻击的。

防火墙分为三种类型：

• 传统的数据包过滤器（Traditional Packet Filter）。通过检查报文的头部进行过滤，过滤的规则定义在接入控制列表中。
• 有状态的过滤器（Stateful Filter）。它追踪 TCP 连接，根据 TCP 连接状态来进行过滤。所有的 TCP 连接记录在过滤列表中。非法 TCP 状态的连接将被过滤。
• 应用程序网关（Application Gateway）。检查一个具体应用程序的所有进入和外出的报文头部和数据负载。

入侵侦测系统

防火墙只是检测数据包的头部，然而，侦测更多的攻击类型，我们需要执行深度数据包检查，同时检查报文的头部和数据负载。虽然应用程序网关可以进行数据包检查，但是它只针对一个具体的应用程序。

入侵侦测系统（Intrusion Detection System）可以对所有通过它的数据包进行深度检查，当观察到恶意攻击流量时，生成报警信息。

入侵防御系统（Intrusion Prevention System）它可以直接过滤有嫌疑的网络流量。

References

[1] Computer Networking: A Top-Down Approach, by Jim Kurose

[2] Base64 - Wikipedia

[3] MD5 - Wikipedia

要实现一个 HTTP 请求，大致可以分为三个阶段。首先客户端要连接网络，获取自己的 IP 地址；然后客户端通过 DNS 域名解析得到目标域名的 IP 地址；最后客户端和服务端建立一个 TCP 连接进行网络通信。

一、客户端连接网络，获取一个 IP 地址

要访问 HTTP 服务器，首先客户端需要连接网络。获取到一个 IP 地址的过程如下：

• 广播一个 DHCP 请求报文，报文封装成 UDP 报文段，设置源端口和目标端口。进而封装成 IP 数据报，目标 IP 地址为 255.255.255.255，源地址 IP 地址为 0.0.0.0。
• IP 数据报封装成 以太网帧，目标 MAC 地址为 FF:FF:FF:FF:FF:FF。
• DHCP 服务器在路由器中。路由器接收到 DHCP 请求。路由器可以分配的地址的 CIDR block 68.85.2.0/24。DHCP 服务器分配地址 68.85.2.101 给客户端。DHCP 服务器创建一个 DHCP ACK 报文，包含分配的 IP 地址，DNS 服务器 IP 地址 68.87.71.226，默认网关路由器IP地址 68.85.2.1，子网掩码 68.85.2.0/24。DHCP ACK 报文封装为 UDP 报文，进而封装为 IP 数据报，最后封装为 以太网帧，源 MAC 地址为路由器的 MAC 地址，目标 MAC 地址为客户端 MAC 地址。
• 客户端收到 DHCP ACK 报文，获取到自己的IP地址和其它地址。

二、域名解析

浏览器输入要访问的 URL。浏览器创建一个 TCP Socket 来发送 HTTP 请求。为了创建 Socket 需要知道目标域名的 IP 地址。因此需要进行 DNS 解析。

• 创建一个 DNS query 报文。封装为 UDP 报文段。设置目标端口。封装为 IP 数据报目标地址为域名服务器的 IP 地址（通过之前 DHCP 获取的）。
• 客户端以太网帧需要知道目标地址的 MAC 地址。通过 ARP 协议获取到网关路由器的 MAC 地址。
• 客户端创建 ARP query 报文。目标IP 地址为默认网关 IP 地址。ARP 报文封装为以太网帧，通过广播报文到达路由器。
• 路由器接收到 ARP query 报文，响应请求，发送 ARP replay 报文。包含路由器的 MAC 地址。
• 客户端收到 路由器的 MAC 地址，将 DNS query 报文发送给路由器。DNS query 报文封装为 IP 报文，目标 IP 地址是 DNS 服务器，最后封装为链路层报文目标地址是路由器的 MAC 地址。
• 路由器收到 DNS query 报文，根据转发表将报文转发到下一跳路由器。
• 经过 ISP 内路由协议和 ISP 之间的路由协议，最终 IP 报文到达 DNS 服务器。DNS 服务器查询缓存得到目标域名的 IP 地址，响应请求，发送 DNS reply 报文。
• 客户端通过 DNS reply 报文得到目标域名的 IP 地址。

三、通过 HTTP 和 TCP 请求服务器

客户端创建 TCP Socket，发送 HTTP GET 报文给服务器。首先需要 TCP 三次握手。

• 客户但创建一个 TCP SYN 报文段，目标端口为 80。TCP 报文封装为 IP 报文，目标地址为服务器 IP 地址。最后封装为链路层报文，目标 MAC 地址为网关路由器 MAC 地址。
• 路由器转发包含 TCP SYN 的 IP 报文给服务器。经过 ISP 内路由协议和 ISP 之间的路由协议，最终 IP 报文到达服务器。
• 服务器响应一个 TCP SYNACK 报文。
• 客户端收到 TCP SYNACK 报文，发送应答报文。TCP 连接成功建立。
• 客户端浏览器创建 HTTP GET 报文，将 HTTP 报文写入 Socket 中，HTTP GET 报文作为 TCP 报文段的负载，进而封装为 IP 报文，经过路由转发请求报文发送到服务器。
• 服务器通过 Socket 收到 HTTP GET 请求报文，然后创建一个 HTTP response 报文，把网页内容放到 HTTP 响应报文的 body 中。把报文发送给 Socket。通过报文封装和路由转发，响应报文发送到客户端。
• 客户端通过 Socket 收到收到 HTTP 响应报文，提取 HTTP 响应报文 body，显示网页。

介绍链路层

两个相邻的连接的节点之间的通信路径称为链路。任何设备运行一个链路层协议称为一个节点。链路层的主要功能是通过把网络层的数据报封装为链路层的帧（Frame）在链路上传播，从而将网络层数据报从一个节点传输到另一个相邻的节点。链路的信道（Channel）主要有两种类型：点到点通信链路（Point-to-point Link）和广播信道（Broadcast Channel）。常见的点到点通信链路有：以太网链路和广域网链路。

链路层提供的服务

• 封装。将网络层的数据报封装成链路层的帧。
• 链路接入。
• 不可靠数据传输。
• 错误侦测和纠正。

链路层的硬件组成

网络接口控制器（Network Interface Controller，NIC），也称网卡（Network Card），网络适配器（Network Adapter），局域网适配器，物理网络接口等等。它是一个计算机的硬件组件，它连接了计算机和计算机网络。本篇主要使用网络适配器作为名称，网络适配器的外观如下图所示。

在一台主机中应用层、传输层和网络层都是软件组件，而链路层一部分是软件组件，一部分是硬件组件。网络协议栈与主机软件和硬件组件之间的关系如下图所示。

链路层软件组件主要和网络层交互。在客户端组装链路层寻址信息，激活网络适配器；在服务端响应网络适配器的 interrupt 信号，传递数据报给网络层。硬件组件功能是错误侦测，以及物理层交互。

错误检测与纠正

奇偶校验

1. 简单的奇偶校验 （One-bit Parity）

通过使用一个 parity bit 来侦察错误。将1位 parity bit 放在数据包的后面。

偶数校验，保证 data bits + parity bit 所有 1 的个数等于偶数。如果 data 中所有的1的个数为奇数，则 parity bit 为 1，否则为0。data中所有的1的个数为偶数，则parity bit 为 0。

奇数校验则保证 data bits + parity bit 所有 1 的个数等于奇数。

2. 二维奇偶检验 （Two-Dimensional Parity，2D parity）

将报文的二进制数据分为 i 行 j 列，每行的末尾和每列的末尾都添加一个 parity bit，一共添加 i+j+1 个 parity bits。它的每行每列都遵循奇偶校验规则。它不仅可以侦测错误，还可以进行错误纠正。

奇偶检验的缺点：

• 简单的奇偶检验和二维奇偶校验都不能侦测所有错误。
• 简单的奇偶检验仅能侦测到一位发生错误。不能侦测一位0和一位1交换错误，两位0或1变为两位1或0错误。
• 二维奇偶校验能更好的侦测错误，但需要更多的检验位。

检验和

检验和（Checksum）实现原理是将数据作分为多个16位二进制求和，求和的反码作为检验和携带在报文头部。接收方将数据划分为多个16位与检验和求和，结果所有的位都是 1 则正确，出现 0 表示错误。

循环冗余校验

循环冗余校验（Cyclic Redundancy Check （CRC））编码也称多项式编码。要得到 CRC code 需要定义一个生成器多项式。这个多项式的系数作为除数，数据报文作为被除数，得到的余数为 CRC code。如，多项式为 x^7 + x^6 + x^4 + x^3 + x + 1，1x^7 + 1x^6 + 0x^5 + x^4 + x^3 + 0x^2 + 1x + 1x^0，除数为 11011011。

发送方：

• n 个 0 附加在数据报文后面，n 是位数小于 CRC generator。
• 新的数据单元除以 CRC generator 得到的余数称为 CRC。
• 将数据单元之前添加的 n 个 0 替换成 CRC。
• 数据单元加上 CRC 传输给接收方。

接收方：

• 接收的数据除以 CRC generator，检查余数。
• 如果余数为 0 则数据正确，否则数据错误。

多点连接链路和协议

广播链路可以有多个发送端和接收端同时连接同一个广播信道。解决多个节点同时发送和接收在同一个信道的问题称为多点连接问题（Multiple Access Problem）。多个节点直接通过一个广播信道会产生数据帧的碰撞（Collide），造成数据丢失。多点连接协议就是为了解决多点连接碰撞问题的。常见的多点连接协议类型有：信道划分协议（Channel Partitioning Protocols），随机接入协议（Random Access Protocols），轮流协议（Taking-turns Protocols）

信道划分协议可分为：

• 时分多路复用（Time-Division Multiplexing，TDM）。每个节点轮流使用一小段时间。
• 频分多路复用（Frequency-Division Multiplexing，FDM）。每个节点使用不同的频率。频率的带宽为 R/N bps。
• 码分多址（Code Division Multiple Access，CDMA）。每个节点使用唯一的代码去编码数据。多个的节点可以同时发送和接收编码的数据。

局域网

链路层寻址和 ARP 协议

链路层通信使用的是 MAC 地址，数据报文的转发依靠 Switch Table 查询目标 MAC 地址对应的输出链路来进行转发。主机和路由器每个网络接口既有一个 IP 地址也有一个 MAC 地址。ARP 协议可以通过广播 ARP 查询请求得到目标 IP 地址对应的 MAC 地址。链路层广播地址为 FF-FF-FF-FF-FF。

MAC 地址

MAC 地址是链路层地址，也称物理地址。每个主机或路由器的网络接口都有一个唯一的固定的 MAC 地址。一个 MAC 地址占 6 个字节，使用十六进制数字表示。如，5c-66-AB-90-75-B1。MAC 地址是由 IEEE 组成统一管理的，它保证了世界上每个设备网络接口 MAC 地址是唯一。

为什么有了 IP 地址还需要 MAC 地址呢？因为当设备位置发生改变时，它的 IP 地址也会改变。而 MAC 地址是设置在硬件上的，一般是固定不变的。这样可以唯一的标识一个设备。IP 地址就像是一个人的邮寄地址，而 MAC 地址就行是一个人的身份证号码。

ARP 协议

ARP（Address Resolution Protocol）协议可以将 IP 地址转换为 MAC 地址。它是怎么做到的呢？每一个主机和路由器都有一个 ARP 表，它记录了一个子网中的 IP 地址对应的 MAC 地址。ARP 表结构如下图所示：

ARP 只能处理在同一个子网的 IP 地址，因为它使用的是广播的方式。在一个局域网中，一个主机 A 直到另一个主机 B 的 IP 地址，主机 A 发生链路层报文时，需要知道主机 B 的 MAC 地址。其过程如下：

• 主机 A 在它的 ARP 表中寻找主机 B 的记录，如果找到了，使用里面的 MAC 地址即可。
• 如果没找到，则需要通过链路层广播，发送 ARP 查询请求。在这个局域网中的所有主机和路由器都会收到这个请求。
• 每个设备检查 ARP 报文中目标 IP 地址是否与自己的匹配，主机 B 的IP 地址与目标地址匹配，主机 B 单播响应请求，发送的 ARP 响应报文包含自己的 MAC 地址。其它不匹配的主机不做响应。
• 主机 A 接收到响应，知道了主机 B 的 MAC 地址，然后封装 链路层报文与主机 B 通信，并更新自己的 ARP 表。

ARP 时即插即用的，不需要配置。

发送报文在两个不同的子网

在同一个局域网两个主机通信是通过 MAC 地址进行数据转发的，如交换机的 switch table 记录了MAC 地址对应的链路接口。

不同的两个局域网需要通过在路由器进行 IP 转发。其过程如下：

• 主机 A 将广播 ARP 请求，想要目标 IP 地址的 MAC 地址。
• 路由器的网络接口发现目标 IP 地址不在这个子网，需要通过路由器 IP 转发，所以路由器响应自己的 MAC 地址给主机 A。
• 主机 A 把路由器当作目标主机。主机 A 把报文发给路由器，路由器通过转发表传给下一跳路由器，经过多个路由器的转发，最终到达目标 IP 地址的主机 B。

以太网协议

以太网（Ethernet）是最流行的构建局域网的技术。早先的以太网使用的是广播的形式通信，后来使用交换机存储转发的形式。

以太网的帧结构如下图所示：

Preamble：唤醒接收端的网络适配器，以及时钟同步。占8字节。

Destination address：表示目标网络适配器的 MAC 地址。占6字节。

Source address：表示源网络适配器 MAC 地址。占6字节。

Type：表示上层协议的类型。占2字节。

Data：IP 报文数据。46 到 1500 字节。

CRC：错误校验。循环冗余检验码。占4字节。

链路层交换机

交换机接收链路报文和转发它们到指定的输出链路。交换机对于路由器和主机是透明的，它们不会意识到交换机的存在。交换机没有 IP 地址和 MAC 地址。

交换机的主要功能：

• 过滤。交换机可以判断什么帧可以转发，什么帧需要丢弃。
• 转发。将接收到的帧转发到某个输出链路。

交换机的工作原理：

• 交换机通过查询转换表（Switch Table）来进行转发。交换表格式如下图所示。
• 如果找到了输出链路，则进行转发；没有找到指定的输出链路，则进行广播。

交换机是自学习的，转换表是自动的更新和维护的。初始转换表设置为空。每个请求经过交换机都会更新路由交换表，记录请求中源 MAC 地址对应的输入链路。当一定时间内，转换表中的一个 MAC 地址没有接收任何报文，这个记录就会被删除。

交换机是即插即用不用配置和不同人工干预的。它是全双工的，每个接口可以同时接收和发送数据。

交换机和路由器的对比

References

[1] Computer Networking: A Top-Down Approach, by Jim Kurose

[2] Network interface controller - Wikipedia

[3] Cyclic redundancy check - Wikipedia

[4] Cyclic redundancy check - SlideShare

介绍网络层

网络层提供了两个主机（终端）的信息传输服务。相比于应用层和传输层，它们提供的服务是一台主机的一个进程与另一台主机的一个进程之间的通信，它们是与进程绑定的，而网络层是与主机绑定的，一个主机在网络中通过 IP 地址进行唯一标识。

因特网的结构

因特网可以分为网络的边缘和网络的中心。网络的边缘是一个路由器连接着各种各样的终端设备，如电脑，手机等。网络的中心是由许许多多的路由连接起来的一个网状结构，它组成了网络的骨架，。因特网的结构如下图所示：

应用层和传输层只出现网络边缘的终端设备上。在网络的中心的路由器上没有应用层和传输层，最高层为网络层，它负责传输网络层数据。

应用层和传输层是两个终端设备上的进程之间的通信，它们只关心进程发给网络层的数据是什么样的，以及从网络层接收到的数据是什么样的。它们不管网络的结构是什么样的，数据是如何在网络中传输的。

网络层实现的功能

网络层主要实现在两个主机之间的网络通信，它要将一个主机上的数据，经过网络（多个路由器），传递给另一个主机。要实现这个功能，需要解决两个问题：1. 网络层数据如何在一个路由器节点上传输？2. 网络层数据如何选择一条最快的网络路径进行数据传输？

路由器上的数据传输是指数据包从路由器的一个输入链路接口传输到一个输出链路接口。这个功能是通过硬件实现的。而选择路径即路由，路由一般是通过软件实现的。

网络层的数据转发（Forwarding）

网络层的信息通信，是将网络层的数据报（Datagram）从客户端主机，经过许多个路由器的转发，最终传递到服务端主机。为了了解网络层数据是如何转发的？我们先介绍路由器的内部工作原理。然后介绍数据报转发过程中用到的 IP 协议。

路由器是如何工作的

路由器的结构

路由器结构如下图所示。它主要由以下四个部分组成。

• 输入端口（Input Port）：输入端口执行三个步骤。第一步执行物理层的功能，终止传入的物理链路。第二步执行链路层功能，与传入链路另一侧的链路层相互操作。第三步，查询转发表，判断将数据传送到哪个输出端口。
• 交换结构（Switch Fabric）：连接输入端口和输出端口。
• 输出端口（Output Port）：接受交换结构的数据，传播这些数据到输出链路。
• 路由选择处理器（Routing Processor）：维护路由表和链路状态信息，计算路由器的转发表。

路由表和转发表的区别是什么？

路由表是每个路由器用来计算和维护网络拓扑结构中的最小花费路径。它每一个行记录了目标地址（Destination），网络掩码（Mask），和下一跳 IP 地址（Next Hop）等等。

转发表用来查询 IP 报文转发到哪个输出端口。

路由器的工作原理

1. 输入端口主要是实现查询报文的输出端口的功能。通过在转发表中查询匹配目标 IP 地址的前缀，从而得到对应的输出端口。如果目标地址匹配多个前缀，则使用最长前缀匹配规则（Longest Prefix Matching Rule）。

2. 转换组织的实现方式有很多种。常用的三种实现方式如下：

Memory（内存）。拷贝数据包到输出端口的内存区域。缺点是多个数据包不能同时读写内存。

Bus（总线）。输入端口将数据包直接传输给输出端口。缺点是多个数据包不能同时使用 bus。

Crossbar（交叉开关矩阵）。由 2N 个bus 连接 N 个输入端口和 N 个输出端口。可以同时传输多个数据包。缺点是不能同时传输多个同一输出端口的数据包。

3. 输出端口，从内存区域的队列中选择一个数据包出队，将使数据包封装成帧在链路上传输。

路由器的等待队列和数据调度

路由器的等待队列可能发生在输入端口和输出端口。队列的长度却决于网络的负载与路由器的处理的速度。当网络的负载超过路由器的处理速度，最终会导致没有足够的内存可用，产生丢包后果。

输入端口队列中的数据包等待着通过交换结构传输到输出端口。输出端口队列中的数据包等待传输到链路上。

在输出端口通常使用调度算法，控制数据包的传输的顺序。常见的调度算法有：

• First-in-First-Out (FIFO)，先进先出算法，使用简单的规则，最先到达的数据包最先处理。
• Priority Queueing，优先队列，按优先度分为不同的队列，先处理高优先度的队列，再处理低优先度的队列。
• Round Robin and Weighted Fair Queuing (WFQ)，循环与加权公平队列，按照优先度分为不同的队列，每个队列依次循环处理。

IP 协议和 IP 寻址

IPv4 协议

IPv4 的报文格式

IPv4 协议定义了 IP 报文的数据格式。IPv4的数据报文格式如下图所示。

报文字段解释

• Version：占4位，指定了 IP 协议的版本。
• Header length：表示头部的长度。长度=20字节+Options的长度。
• Type of service：用于标识报文是实时应用，还是非实时应用报文。实时应用如网络电话。非实时应用如FTP。
• Datagram length：表示整个报文的长度，头部+数据域。
• Identifier，Flags，Fragmentation offset：用于 IP 报文分片。
• Time-to-live：可存活的时间。当TTL=0时，数据报需要被丢弃。
• Protocol：指出使用的传输层的协议。
• Header checksum：用于 IP 报文错误检查。
• Source IP address，Destination IP address：表示客户端和服务端主机的 IP 地址。
• Options：用于 IP 头部的扩展。一般很少使用。
• Data：数据负载。传输层数报文段或者ICMP消息。

IPv4 报文分片（Datagram Fragmentation）

链路层有不同的链路类型，不同的链路有不同的最大传输单元（Maximum Transmission Unit，MTU）。在链路上，一般一个网络层的 IP 报文封装一个链路层的帧。由于不同的链路有不同的 MTU，会导致一个 IP 报文在一个链路能传输，而在另一个链路由于 IP 报文长度大于该链路的 MTU，而不能在该链路传输。如，以太网链路最大传输单元为1500 bytes，而广域网链路最大传输单元为 576 bytes。

为了解决这个问题，需要用到 IP 报文分片。当 IP 报文长度大于该链路的 MTU 时，将 IP 报文分为多个分片（Fragment），每个分片封装成一个帧在链路上传输。

IP 报文分片头部设置为：每个分片设置相同的 identification number；前面的分片 flag bit 设为 1，最后一个分片 flag bit 设为 0；offset 指定分片在原始的 IP 报文中的相对位置，第一个分片 offset 设为 0。

IP 报文分片检查。路由器通过相同的 identification number 判断是一个 IP 报文分片，通过 flag 判断分片是否结束，通过 offset 知道分片的顺序。

IP 寻址

IP 寻址（IP Addressing）是指对某个 IP 地址进行定位。其中涉及到许多网络概念，如 IP 地址，接口，子网，子网掩码等等。下面对这些概念进行简单描述。

接口（Interface）：连接主机和物理链路边界。每台主机有一个接口，路由器通常由多个接口。

IP 地址：每个接口必须有一个 IP 地址。IPv4 地址占 32 位。地址的表示为，4个十进制的数字以点分隔，如193.32.216.9。

子网（Subnet）：由一个路由器接口和多个主机（或路由器）接口互相连接的网络称为一个子网。IP 网络可以划分为很多个子网。同一个子网的所有接口具有相同的 IP 地址前缀。

子网掩码：表示一个子网的相同的 IP 地址前缀。一般形式为 a.b.c.d/x，其中 x 表示前缀的长度。如一个子网的子网掩码为 233.1.1.0/24，那么这个子网中所有的接口 IP 地址有共同的24位前缀 233.1.1…，IP 地址可以为 233.1.1.1，233.1.1.2，233.1.1.3 等等。

有类别的寻址（Classful Addressing）：网络划分中IP地址的前缀位数限制为8，16，24位。

无类域间路由（Classless Inter-Domain Routing, CIDR）：CIDR用 13-27位长的前缀取代了有类别寻址限制的3种前缀。

IP 广播地址（Broadcast Address）：IP 广播地址为 255.255.255.255，发送报文给广播地址，这个子网的所有主机都能收到这个消息。

获取一组 IP 地址

一个机构或公司想要获取一组 IP 地址，构建自己的子网。需要从网络提供商（Internet Support Provider, ISP） 那里获取。如中国电信和中国移动等。

ISP 如何获得一组 IP 地址。IP 地址是被一个权威组织 ICANN （Internet Corporation for Assigned Names and Numbers）所管理的。ISP 可以从权威组织那里获取一组 IP 地址。

获取一个主机的 IP 地址

一台主机想要连接互联网，需要获取一个 IP 地址。为主机分配 IP 地址可以手动配置，也可以使用DHCP（ Dynamic Host Configuration Protocol）协议来自动分配。DHCP 协议是即插即用的零配置的协议。

DHCP 协议分配IP地址的过程：

• 新接入网络的主机发送获取 IP 地址请求，通过广播 DHCP discover message。
• DHCP 服务器响应请求，返回分配的 IP 地址，子网掩码，和 IP 地址租用时间。通过广播 DHCP offer message。
• 主机发送请求确认，通过广播 DHCP request message。
• DHCP 服务器响应请求，确认请求参数。通过广播 DHCP ACK message。

NAT

一台服务器主机需要被网络访问，优先需要拥有一个广域网 IP 地址。当服务器主机不断扩展增加，没有足够的 IP 地址时，可以通过 Network Address Translation (NAT) 可以进行 IP 地址扩展。可以将一个广域网 IP 地址，扩展为多个局域网 IP 地址。即一个广域网 IP 地址，通过映射局域网 IP 地址，可以为多台主机提供网络接入。

NAT 的工作原理是：

• 所有的主机与 NAT 路由器连接，所有的主机对于外部世界看作是单个设备和一个 IP 地址，通过这一个 IP 地址不同的端口来区分内部的主机。
• NAT 使用 NAT 转换表（NAT Translation Table） 将这个公开的 IP 地址加端口和所有内网 IP 地址加端口之间有一对一映射关系。也就是 NAT 转换表的一个记录，将公网 IP 和一个端口映射一个内网的进程。
• 外部客户端请求 NAT 内的主机，是通过请求 NAT 路由器的 IP 地址和指定端口，NAT 路由器接收到请求后，通过修改报文的目标地址为局域网地址，修改目标端口为进程的端口，将这个报文转发给内网的主机的一个进程。
• NAT 内的主机访问外部的主机，请求经过 NAT 路由器的时候，NAT 路由器修改报文的源地址为 NAT 路由器的地址，修改源端口为 NAT 路由器的一个端口。
• 所有内网中的主机不直接与外部的通信，所有的通信都是 NAT 路由器与外部进行的。NAT 通过修改报文的内容从而达到与内网的通信。

NAT 转换表如下图所示：

IPv6 协议

由于 IPv4 的地址空间快用完了。需要一个新的 IP 协议支持更多的 IP 地址，所有 IPv6 诞生了。

IPv6 相比与IPv4有哪些重大的改变：

• 扩展了地址空间。IP 地址由原来的32位变成128位。
• 支持任播 anycast address。多个主机使用相同的 IP 地址，路由器优先访问离自己最近的一个。相当于 CDN 的功能。
• 固定的40字节的报文头部。固定的报文头部使得 IP 报文可以被路由器处理得更快。
• 流标签。定义报文数据流的类型。

IPv6 的报文格式如下图所示：

报文字段解释

• Version：表示协议的版本。
• Traffic class：表示服务的类型。指定报文的优先度。
• Flow label：表示流的类型。实时应用还是非实时应用。
• Payload length：数据域的长度。
• Next header：指定传输层的协议类型。TCP 还是 UDP。
• Hop limit：在路由器中转发的次数。当 hot limit 为0是该报文将被丢弃。
• Source and destination address：源 IP 地址和目标 IP 地址。
• Data：数据域。

IPv6 相对于 IPv4 去除的字段

• Fragmentation：IPv6 不需要分片。当报文长度大于链路最大传输单元时，该报文直接被丢弃，而不是进行分片。
• Header checksum：不再执行错误检查。传输层和链路层的错误检查已经足够了。
• Options：IPv6 使用固定的头部，不需要可选字段。

网络层的路由管理（Routing）

路由表记录和维护着网络通信的最小花费路径，通过路由表使整个网络通信更加高效。路由表则是通过路由算法和路由协议得到的。这一小节主要讲述常见的路由算法和路由协议。

路由算法

网络结构像是一个由多个节点相互连接的图。一个图结构有 N 个节点和 E 条边组成。每一个相邻的节点称为邻居，任意两个连通的节点形成的一条路径。路由算法就是算出任意两个节点之间的最小花费路径（Least-cost path）。

路由算法可以通过很多方式实现，可以将它们进行分类：

• 集中路由算法，分散路由算法
• 静态路由算法，动态路由算法
• 负载敏感算法，负载不敏感的算法

Link-state (LS) 路由算法

LS 算法是一个集中式路由算法，它采用了 Dijkstra 算法计算最小花费路径。使用的方式是：每个路由器运行 LS 算法，计算与其它每个节点的最小花费路径。

LS 算法的描述

初始化过程：计算相邻的节点的路径花费。不相邻的节点初始化为无穷大。

循环过程：循环计算当源节点到目标节点（邻居的邻居节点）的最小路径，直到所有节点都经过计算。

算法伪代码如下：

/* 
D(v): cost of least-cost path from the source node to desination v.
c(u,v): cost of from u to directly attached neighbor v.
N: all nodes
N': subset of nodes.
Time complexity: O(n^2)
*/
Initialization:
N' = {u}
for all nodes v
	if v is a neighbor of u
		then D(v) = c(u,v)
	else D(v) = ∞

Loop
find w not in N' such that D(w) is a minimum
add w to N'
update D(v) for each neighbor v of w and not in N'
	D(v) = min(D(v), D(w) + c(w,v))
util N' = N

Distance-Vector (DV) 路由算法

DV 算法是一个异步，分散的算法。

DV 算法描述

Initialization:
for all destination y in N:
	Dx(y) = c(x,y) /* if y is not a neighbor then c(x,y) = ∞ */
for each neighbor w
	Dw(y) = ? for all destinations y in N
for each neighbor w
	send distance vector Dx = [Dx(y): y in N] to w

loop
	wait (until I see a link cost change to some neighbor w or until I receive a distance vector form some neighbor w)
	for each y in N:
		Dx(y) = min{c(x,v) + Dv(y)}
	if Dx(y) changed for any destination y
		send distance vector Dx = [Dx(y): y in N] to all neighbors
forever

LS 和 DV 路由算法的比较

• 消息复杂度。LS 算法需要直到每一条网络链路的花费。这需要 O(NE) 消息发送。当一个链路花费发生改变时需要把新的花费发给所有节点。DV 算法需要在所有直接连接的邻居之间交换消息。这个复杂度取决于很多因素。当一个链路花费发送改变时，新的花费将通过一个节点向和它连接的节点进行传播。
• 收敛速度。LS 是一个 O(N^2) 的算法需要 O(NE) 个消息传递。DV 算法没有明确的复杂度，可能会导致无限死循环。
• 鲁棒性。LS 算法计算是每个路由器独立的，一个路由器的计算机结果不会受其它路由器的影响。DV 算法根据所有的邻居来计算，当一个节点出现错误时，可能导致整个网络出现错误计算。

两个算法都有自己的优缺点，它们都使用在当今的因特网中。

路由协议

想要计算和维护任何一个路由器节点到世界范围内的其它所有路由器节点的最小花费路径，是一件很复杂的事情。主要的问题有两个方面。

• 网络规模。目前世界上有数亿的路由器节点。想要计算和存储如此多的路径信息，需要很多的计算时间和存储空间。
• 网络管理。每个国家每个地区，希望能够自己控制和管理自己的网络，以及隐藏自己内部的网络结构。

为了解决这些问题，每个地区可以通过一组路由器构建一个自治系统（Autonomous System, AS）。如今世界上存在的因特网，就是由很多个 AS 组成的网络，一个 AS 与另一个 AS 之间直接或间接地连接和沟通，就连通了整个因特网。一个 ISP（网络服务提供商） 通常会组建一个自己的网络自治系统，也有的 ISP 会组建多层级的自治系统。当今世界的因特网的结构大致如下图所示：

一个 AS （或者 ISP ）内部的路由管理，通过自治系统内部路由协议（Intra-Autonomous System Routing Protocol）实现，一个 AS 内的所有路由器运行相同的路由算法。常见的协议，如 OSPF 协议。

AS 之间的路由管理，通过自治系统间的路由协议（Inter-Autonomous system routing protocol）实现，每个 AS 运行相同的自治系统间的路由协议进行交流。常见的协议，如 BGP 协议。

ISP 内部路由管理：OSPF 协议

OSPF 协议使用 link-state 路由算法计算 ISP 内部任何两个节点之间的最小花费路径。OSPF 不是当链路发生改变时运行，而是每个路由器定期（每30分钟）向其它路由器的广播路由信息。OSPF 消息是使用 IP 报文进行负载的。

ISP之间的路由管理：BGP 协议

在因特网中，所有的AS运行相同的 inter-AS 路由协议称为边界网关协议（Border Gateway Protocol, BGP）。在 BGP 协议中，每个 AS 有自己的一组 IP 地址，通常是连续的有相同前缀的 IP 地址。一个 AS 通过CIDR 前缀向其它 AS 广播自己的存在。

BGP 协议提供的服务

• 一个 AS 通过 AS 邻居获取可到达的网络 IP 前缀信息。
• 提供一个最好的路径从一个 AS 到达另一个 AS。

关于 BGP 协议是如何广播一个 AS 的存在，以及如何计算最佳的AS 间的路径，这里不详细展开。详细内容可以查阅最后的参考书籍。

网络的管理

ICMP 协议

通过 ICMP (Internet Control Message Protocol) 协议，主机和路由器之间可以进行交流。ICMP 报文是使用 IP 报文进行负载的，通过设置头部的 upper-layer protocol number 为 1，主机可以识别这个一个 ICMP 报文，而不是 TCP 或 UDP 报文。ICMP 报文有类型和代码表示不同的含义。如，当一个主机不可访问时，路由器会返回 ICMP 报文给客户端，报文设置为 type=3,code=1 表示目标主机不可接入。

ICMP 常见的功能

• 报告错误。
• 实现 ping 程序。
• 拥塞控制。
• 实现路由追踪程序。

网络管理和 SNMP 协议

一个网络有很多的硬件和软件组件构成，如链路，交换机，路由器，主机等。当成千上万的组件组成一个网络，想要把保持网络的持续稳定的运行，是一件很有挑战的事。通过一些网络管理工具和技术可以帮助网络管理员监控，管理，和控制网络。

关键的网络管理组件

• 管理服务器。
• 管理的设备。
• 管理信息。定义了管理信息的格式。
• 网络管理代理。运行在设备上，可以与服务器进行交流。
• 网络管理协议。网络协议允许管理服务器查询和修改设备的状态。网络管理代理可以给管理服务器通知异常时间。常见的网络管理协议 SNMP。

SNMP 协议(The Simple Network Management Protocol) 是一个应用层协议。它在管理服务器和网络管理代理之间传达网络管理控制和信息。

References

[1] Computer Networking: A Top-Down Approach, by Jim Kurose

[2] IP 寻址的工作原理

介绍传输层

什么是传输层

应用层提供的服务是让两个终端的进程进行信息交换。而传输层提供是在两个终端的进程之间数据传输服务（Process-to-Process Delivery Service）。传输层的硬件组成部分，和应用层一样依然是两个终端设备，软件部分是传输层协议，如，UDP 和 TCP。

传输层位于应用层和网络层之间。它给应用层提供数据传输服务，同时，它利用了网络层提供的服务。虽然网络层的 IP （Internet Protocol）协议提供的是尽力传递服务（Best-Effort Delivery Service），也就是说网络层提供的是不可靠的数据传输，但是传输层自身可以通过相关的算法，从而实现可靠的数据传输服务。

传输层提供的服务有：

• 数据传输。
• 错误检查。
• 可靠数据传输。数据的正确性和有序性。
• 拥塞控制。

传输层主要有 TCP 和 UDP 两个协议，不同的协议提供不同的服务，适用于不同的应用场景。其中，TCP 协议提供的是可靠传输，它包含了上面所有的服务。而 UDP 协议提供的是不可靠传输，包含部分服务，即数据传输和错误检查。

传输层是如何工作的

传输层发送数据的过程：

• 客户端进程组装应用层报文
• 进程根据传输层协议，创建相应的 Socket。
• 进程将应用层消息传给 Socket。
• Socket 将应用层报文（Message）分成多份，加上传输层报文头。封装成传输层报文段（Segment）传递给网络层。

传输层接收数据的过程：

• 网络层将组装好的报文段传给传输层。
• 传输层接收到报文段，根据报文段的头部信息中的目标端口，将报文段传给指定的 Socket。
• Socket 收集到所有的报文段后，将报文段转换为应用层报文。
• 进程读取 Socket 中的应用层报文。

上述过程涉及到的一些重要的概念，接下来进行解释。

进程

在操作系统中，一个运行的程序称为一个进程。进程是分配计算机资源的最小单元。网络通信宏观上是两个可计算的终端设备之间的通信，微观上是两个进程之间的通信。

端口

端口（Port Number）一个逻辑的实体，它用于在终端设备进行网络通信时标识一个进程。一个进程可以绑定多个端口。一个端口只能属于一个进程。

网络套接字 （Network Socket）

Socket 是一个软件组件。它帮助计算机程序连接本地网络或者广域网。Socket 为进程打开网络连接，允许进程通过网络读写数据。Socket 是进程间网络通信的一个终端。Socket 是连接应用层和网络层的大门。

一个 Socket 有三个部分组成：传输层协议，IP 地址，端口。Socket 绑定了一个具体的端口，运输层通过端口知道把报文段传送给哪个进程。

UDP 协议

UDP 协议的数据传输服务有以下特征：

• 不可靠数据传输
• 无连接
• 最大网速传输
• 更小的报文头部

UDP 协议使用使用起来更简单，不需要三次握手建立连接，没有拥塞控制，简单的报文格式等。如果不需要严格的可靠数据传输，允许部分数据丢失，可以考虑使用 UDP 协议。如，应用层协议 DNS 就是使用 UDP。

UDP 报文段结构

Source_port  Dest_port
Length       Checksum
(Application data)

UDP 报文段头部共占8字节。由4个字段组成，每个字段2个字节。

Source port：表示客户端进程端口。

Dest port：表示服务端进程端口。

Length：表示报文段的头部和数据的总字节数。

Checksum：用来检查报文段是否出现错误。

TCP 协议

介绍 TCP

TCP 协议有以下特点：

• 可靠的数据传输
• 面向连接

TCP 报文段格式如下图所示：

TCP 报文段头部共占20个字节（Options为空时）。其中

Source port，Dest port，checksum 和 UDP 协议类似。

Sequence number 和 Acknowledgement number 用来实现可靠数据传输服务。

Header length 用来表示报文头部的长度，当 Options 为空时，长度为20。

Flag field 包含6个bit。其中 ACK bit 表示应答客户端是否成功接收，RST，SYN，FIN 用于连接设置。

Receive window 用于流控制。

TCP 连接管理

客户端进程和服务端进程建立 TCP 连接的过程：三次握手（Three-Way Handshake）

• 客户端发送一个特殊的 TCP 报文段（SYN segment），请求建立连接。这个特殊的报文段没有应用层数据。报文段头部设置为：SYN bit 设为1；随机设置一个initial sequence number（client_isn）。
• 服务端收到 TCP SYN 报文段。响应给客户端一个 TCP 报文段，这个响应的报文段也没有应用层数据，报文段头部设置为：SYN bit 设为1；acknowledgement number 设为 client_isn + 1；设置一个initial sequence number（server_isn）。
• 客户端收到 SYNACK 报文段。分配连接的缓存和变量。然后发送一个 TCP 报文段给服务端，表示收到服务端的响应。这个报文段同样没有应用层数据，报文段头部设置为：SYN bit 设置为0；acknowledgement number 设置为 server_isn + 1；设置 sequence number 为 client_isn + 1。

为什么建立 TCP 连接需要三次握手？

三次握手为了确定双方都准备好了，确保可以正常通信了。

关闭 TCP 连接的过程：四次挥手

• 客户端请求关闭 TCP 连接。发送一个特殊的报文段，报文段头部设置为： FIN bit 设为1。
• 服务端响应客户端请求。
• 服务端确认可以关闭TCP请求后，发送关闭 TCP 请求。发送一个特殊的报文段，报文头部设置为：FIN bit 设为1.
• 客户端响应服务端请求。

通过四次通信后，客户端和服务端可以关闭 TCP 连接，释放 TCP 连接资源，如缓存和变量。

可靠数据传输的实现原理

可靠的数据传输服务要保证服务端接收到的数据有以下特征：

• 没有数据错误
• 没有数据缺少
• 没有数据重复
• 正确的顺序

解决以上问题的方法

• 解决数据错误。通过报文头 checksum 字段的错误校验和错误重发机制，确保没有数据错误。
• 解决数据缺少。通过报文头 acknowledgement number 字段和超时重发机制，确保没有数据缺少。
• 解决数据重复。通过报文头 sequence number 字段，确保没有重复的数据。
• 正确的顺序。通过报文头 sequence number 字段，确保数据的顺序正确。

具体细节没有展开，有兴趣可以阅读参考资料中的书籍。

流控制的实现原理

流控制就是控制 TCP 报文发送的速率。它的实现是通过客户端和服务端定义的相关变量来控制的。具体的实现原理如下。

服务端

TCP 连接建立后，服务端分配 TCP 连接缓存，定义 RcvBuffer 变量表示缓存的大小，应用进程读取缓存中的数据。定义两个变量：

LastByteRcvd：网络达到的最后一个字节数。

LastByteRead：应用进程读取的最后一个字节数。

TCP 不允许数据溢出分配的缓存。所以必须保证 LastByteRcvd - LastByteRead <= RcvBuffer

客户端

客户端为了不使服务端的缓存溢出，会根据服务端缓存剩余空间大小，控制发送数据的速度。

客户端定义了一个接受窗口（Receive Window）变量 rwnd。这个变量动态变化的，它等于服务端缓存剩余空间的大小。LastByteSent 表示最后发送的一个字节，它对应服务端的LastByteRcvd。LastByteAcked 表示最后一个应答的字节，它对应服务端的 LastByteRead。变量之间的关系为：

rwnd = RcvBuffer - (LastByteSent - LastByteAcked)

TCP 连接成功后，服务端会返回它的缓存大小给客户端，客户端初始化自己的接收窗口变量 rwnd = RcvBuffer。然后客户端根据发送和应答的情况动态改变接收窗口变量大小。当 rwnd=0 时，表示服务端的缓存已经满了，客户端则停止发送 TCP 数据。

拥塞控制的实现原理

拥塞控制的实现利用了 TCP 的流控制，当拥塞发生时，通过减少客户端的发送 TCP 报文的速率，从而减少网络的拥塞。一般通过是否丢包来判断网络是否拥塞。如何避免拥塞？如何控制客户端的速率更合理？这就是拥塞控制算法需要解决的问题。

造成网络拥塞的原因：

• 路由器排队延迟。数据包到达路由器的速度接近链路容量。
• 不必要的数据包重发。大量的重复的数据包在网络中传播，占用了链路的带宽。
• 丢包。如果一个数据包在第n个路由器被丢弃了，那么这个数据包需要重新在1~n的路由器路径上传递。可以给一个优先权，已经在经过了许多路由器的数据包优先通过路由器。

拥塞控制的方法：

• 端到端拥塞控制（End-to-End Congestion Control）。如果一个 TCP 报文段丢失，表示网络出现拥塞，TCP 自动降低（流控制）接受窗口大小。
• 网络协助拥塞控制（Network-assisted Congestion Control）。网络出现拥塞，路由器直接反馈给客户端。

拥塞控制算法

• 慢热启动（Slow Start）。TCP 开始传输的初始速率很低，然后以指数增长，直到出现丢包后停止增长，速率变为当前速度的一半。
• 拥塞避免（Congestion Avoidance）。当第一次丢包发生后，由慢热启动状态转为拥塞避免状态，传输速率由原来的指数增长，变为线性增长。
• 快速恢复（Fast Recovery）。
  • TCP Tahoe. 如果在拥塞避免的状态下（即线性增长）再次发生丢包。重新回到慢热启动状态，传输速度设为初始速度。
  • TCP Reno. 如果在拥塞避免的状态下（即线性增长）再次发生丢包。传输速度回到拥塞避免状态的初始速度。

通过拥塞控制算法，最终所有的连接会平均分配链路带宽，它们的传输速度会在平均线上下震荡，所有TCP 连接公平的使用网络。

TCP 协议和 UDP 协议的区别

1. TCP 是面向连接（三次握手），UDP 是无连接的。
2. TCP 提供可靠数据传输服务，UDP 提供不可靠传输。
3. TCP 有拥塞控制（传输速度根据丢包情况调整），UDP 最大速度传输。
4. TCP 报文头 20 字节，UDP 报文头 8 字节

References

[1] Computer Networking: A Top-Down Approach, by Jim Kurose

[2] Socket Definition