2X岁，是学生です

0%

发表于 更新于 分类于
本文字数： 3.8k 阅读时长 ≈ 3 分钟

高精度加减乘除，用于处理大整数运算，不但远超INT型上界，也可以远超 Long Long 型上界。

大整数的保存方法

使用vector从个位开始往高位存。

正整数高精度加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void set_val(const string& val, vector<int>& vals)
{
    int m = val.size();
    for(int i = m - 1; i >= 0; --i)
        vals.push_back(val[i] - '0');
}

void sum(const vector<int>& a, const vector<int>& b, vector<int>& res)
{
    int m = a.size(), n = b.size(), t = 0;//t为进位符号
    for(int i = 0; i < m || i < n; ++i)
    {
        if(i < m) t += a[i];
        if(i < n) t += b[i];
        res.push_back(t % 10);
        t /= 10;
    }
    if(t) res.push_back(t);
}

int main()
{
    string val1, val2;
    cin >> val1 >>val2;
    vector<int> a, b, res;
    set_val(val1, a), set_val(val2, b);
    sum(a, b, res);
    for(int i = res.size() - 1; i >= 0; --i)
        cout << res[i];
    return 0;
}

正整数高精度减法

考虑结果为负数的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void set_val(const string& val, vector<int>& vals)
{
    int m = val.size();
    for(int i = m - 1; i >= 0; --i)
        vals.push_back(val[i] - '0');
}

bool cmp(const vector<int>& a, const vector<int>& b)
{
    int m = a.size(), n = b.size();
    if(m != n) return m < n;
    for(int i = m - 1; i >= 0; --i)
    {
        if(a[i] > b[i]) return false;
        else if(a[i] == b[i]) continue;
        else return true;
    }
    return false;
}

void sub(const vector<int>& a, const vector<int>& b, vector<int>& res)
{
    int m = a.size(), n = b.size(), t = 0;
    for(int k = 0; k < m || k < n; ++k)
    {
        int i = 0, j = 0;
        if(k < m) i = a[k];
        if(k < n) j = b[k];
        t = i - j - t;
        res.push_back((t + 10) % 10);
        t = 1 - (t + 10) / 10;//判断当前位是否需要借位
    }
    while(res.size() > 1 && res.back() == 0)
        res.pop_back();
}

int main()
{
    string val1, val2;
    cin >> val1 >> val2;
    vector<int> a, b, res;
    set_val(val1, a), set_val(val2, b);
    bool isminus = cmp(a, b);
    if(isminus) sub(b, a, res);
    else sub(a, b, res);
    if(isminus) cout << "-";
    for(int i = res.size() - 1; i >= 0; --i)
        cout << res[i];
    return 0;
}

高精度乘法（大数乘以一个较小数）

其实两个大数也是可以做的。(LeetCode43.字符串相乘)

这种题目更为简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void set_val(const string& val, vector<int>& vals)
{
    int m = val.size();
    for(int i = m - 1; i >= 0; --i)
        vals.push_back(val[i] - '0');
}

void mul(const vector<int>& a, int b, vector<int>& res)
{
    int m = a.size(), t = 0;
    for(int i = 0; i < m; ++i)
    {
        t += a[i] * b;
        res.push_back(t % 10);
        t /= 10;
    }
    if(t) res.push_back(t);
    while(res.size() > 1 && res.back() == 0)
        res.pop_back();
}

int main()
{
    string val1;
    int b;
    cin >> val1 >> b;
    vector<int> a, res;
    set_val(val1, a);
    mul(a, b, res);
    for(int i = res.size() - 1; i >= 0; --i)
        cout << res[i];
    return 0;
}

高精度除法(一个大数除以一个较小数并求余数)

这个就比较麻烦了。要明确除法是要从高位开始往低位运算的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

void set_val(const string& val, vector<int>& vals)
{
    int m = val.size();
    for(int i = m - 1; i >= 0; --i)
        vals.push_back(val[i] - '0');
}

void div(const vector<int>& a, int b, vector<int>& res, int& mod)
{
	int m = a.size(), t = 0;
	for(int i = m; i >= 0; --i)
	{
		if((t * 10 + a[i]) / b)//够除
		{
			res.push_back((t * 10 + a[i]) / b);
			t = (10 * t + a[i]) % b;
		}
		else //不够除，要借一位
		{
			res.push_back(0);
			t = t * 10 + a[i];
		}
	}
	mod = t;
	reverse(res.begin(), res.end());//注意翻转
	while(res.size() > 1 && res.back() == 0)
		res.pop_back();
}

int main()
{
	string val1;
	int b, mod;
	cin >> val1 >> b;
	vector<int> a, res;
	set_val(val1, a);
	div(a, b, res, mod);
	for(int i = res.size() - 1; i >= 0; --i)
		cout << res[i];
	cout << endl;
	cout << mod << endl;
	return 0;
}

发表于 更新于 分类于
本文字数： 467 阅读时长 ≈ 1 分钟

只要是有二段性质的问题，都可以二分。

二分一定有解，但是这个解不一定是题目要求的解，因此要在二分得到解后判断这个解是否符合条件。

整数二分问题避免边界问题的一点套路

如果整数二分代码中有： $l = mid$，则此时的$mid$应该是更新为 $mid = l + r + 1$。

浮点数二分不必考虑此边界问题。

二分的代码比较简单，但是题目的二段性可以藏的很深。

一道简单的浮点数二分题：

求数的三次方根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;

int main()
{
	double n;
	cin >> n;
	double l, r;
	if (n < 0)
		l = n, r = 0;
	else
		l = 0, r = n;
	while (r - l > 1e-8)
	{
		double mid = (l + r) / 2;
		if (mid <= n / (mid * mid))
			l = mid;
		else
			r = mid;
	}
	cout << l << endl;
	return 0;
}

发表于 更新于 分类于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

快速排序，O($nlogn$)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
int vals[N], n;

void quick_sort(int l, int r)
{
    if(l >= r) return;
    int i = l - 1, j = r + 1, mid = vals[i + j >> 1];
    while(i < j)
    {
        do ++i; while(vals[i] < mid);
        do --j; while(vals[j] > mid);
        if(i < j) swap(vals[i], vals[j]);
    }
    quick_sort(l, j), quick_sort(j + 1, r);
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &vals[i]);
    quick_sort(1, n);
    for(int i = 1; i <= n; ++i)
        printf("%d ", vals[i]);
    return 0;
}

快速选择算法，O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
int vals[N];

int quick_select(int l, int r, int k)
{
    if(l == r) return vals[l];
    int i = l - 1, j = r + 1, mid = vals[i + j >> 1];
    while(i < j)
    {
        do ++i; while(vals[i] < mid);
        do --j; while(vals[j] > mid);
        if(i < j) swap(vals[i], vals[j]);
    }
    int len = j - l + 1;
    if(len >= k) return quick_select(l, j, k);
    return quick_select(j + 1, r, k - len);
}

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &vals[i]);
    printf("%d", quick_select(1, n, k));
    return 0;
}

归并排序，O($nlogn$)，需要额外O(n)的空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
using namespace std;

const int N = 1e5 + 10;
int vals[N], temp[N];

void merge_sort(int l, int r)
{
    if(l >= r) return;
    int i = l, mid = l + r >> 1, j = mid + 1, k = 1;
    merge_sort(l, mid), merge_sort(j, r);
    while(i <= mid && j <= r)
    {
        if(vals[i] <= vals[j]) temp[k++] = vals[i++];
        else temp[k++] = vals[j++];
    }
    while(i <= mid) temp[k++] = vals[i++];
    while(j <= r) temp[k++] = vals[j++];
    for(int i = l, k = 1; i <= r; ++i, ++k)
        vals[i] = temp[k];
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &vals[i]);
    merge_sort(1, n);
    for(int i = 1; i <= n; ++i)
        printf("%d ", vals[i]);
    return 0;
}

发表于 更新于 分类于
本文字数： 191 阅读时长 ≈ 1 分钟

装饰模式

主要目的是为对象动态扩展功能（由于父类指针指向子类对象时，能够调用的函数只有子类从父类继承过去的实/虚函数，因此只能重写虚函数来扩充功能）。

装饰模式有一个很明显的特征：装饰器类会继承原始基类，且装饰器类中会有原始基对象或指针。继承下来的意义在于可以重写虚函数添加新功能，但又可以通过原始基类指针调用。（我的理解，可能有点偏差）

!alt

参考资料

《大话设计模式》
CS-Notes

发表于 更新于 分类于
本文字数： 211 阅读时长 ≈ 1 分钟

观察者模式

个人感觉，《大话设计模式》里的例子讲解比较清晰。

观察者模式又称发布-订阅(Publish/Subscribe)模式。其定义了一种一对多的关系，让多个观察者对象同时监听某一个主题对象。主题对象在状态发生变化时，会通知所有观察者对象，使它们能够自动更新自己。

!alt

在主题或通知者类中，提供注册或删除具体观察者对象的接口，同时维护一个注册到当前通知类对象中的观察者对象的聚集。

参考资料

《大话设计模式》
CS-Notes

发表于 更新于 分类于
本文字数： 6.3k 阅读时长 ≈ 6 分钟

网络编程常见四种调用方式：

同步/异步主要针对client端。

同步(Sync)

所谓同步，就是在client端发出一个功能调用后，在没有得到结果之前，该调用就不返回。也就是必须一件一件事做,等前一件做完了才能做下一件事。

例：普通B/S模式(同步)：提交请求->等待服务器处理->处理完毕返回。这个期间客户端浏览器不能干任何事。

异步(Async)

异步的概念和同步相对。当client端一个异步过程调用发出后，调用者不能立刻得到结果。实际处理这个调用的部件在完成后，通过状态、通知和回调来通知调用者。
例：ajax请求(异步): 请求通过事件触发->服务器处理(这时浏览器仍然可以处理其他事务)->处理完毕

阻塞/非阻塞主要针对server端

阻塞(Block)

阻塞调用是指在当前线程的调用结果返回前，该线程会被挂起(线程进入非可执行状态，在这个状态下，CPU不会给线程分配时间片，即线程暂停运行)。函数只有在得到结果之后才返回。

非阻塞(Unblock)

非阻塞和阻塞的概念相对应，指在不能立刻得到结果之前，该函数不会阻塞当前线程，而会立刻返回。

总结

  • 同步IO和异步IO的区别就在于：数据拷贝的时候进程是否阻塞

  • 阻塞IO和非阻塞IO的区别就在于：应用程序的调用是否立即返回

阻塞和非阻塞是指当进程访问的数据如果尚未就绪,进程是否需要等待,简单说这相当于函数内部的实现区别,也就是未就绪时是直接返回还是等待就绪;

同步和异步是指访问数据的机制；同步一般指主动请求并等待I/O操作完毕的方式,当数据就绪后在读写的时候必须阻塞(区别就绪与读写二个阶段,同步的读写必须阻塞)。异步则指主动请求数据后便可以继续处理其它任务,随后等待I/O操作完毕的通知,这可以使进程在数据读写时也不阻塞。(等待“通知”)

I/O 模型

一个输入操作通常包括两个阶段：

  • 等待数据准备好
  • 从内核向进程复制数据

对于一个套接字上的输入操作，第一步通常涉及等待数据从网络中到达。当所等待数据到达时，它被复制到内核中的某个缓冲区。第二步就是把数据从内核缓冲区复制到应用进程缓冲区。

Unix五种 I/O 模型：
同步：

  • 阻塞式 I/O
  • 非阻塞式 I/O
  • I/O 复用（select 和 poll）
  • 信号驱动式 I/O（SIGIO）

异步：

  • 异步 I/O（AIO）

阻塞式 I/O

应用进程会一直被阻塞，直到数据从内核缓冲区复制到应用进程缓冲区中才返回。

应该注意到，在阻塞的过程中，其它应用进程还可以执行，因此阻塞不意味着整个操作系统都被阻塞。因为其它应用进程还可以执行，所以不消耗 CPU 时间，这种模型的 CPU 利用率会比较高。

recvfrom() 函数用于接收 Socket 传来的数据，并复制到应用进程的缓冲区 buf 中。这里把 recvfrom() 当成系统调用。

在调用recv()/recvfrom()函数时，发生在内核中等待数据和复制数据的过程。

alt

当调用recv()函数时，系统首先查是否有准备好的数据。如果数据没有准备好，那么系统就处于等待状态。当数据准备好后，将数据从系统缓冲区复制到用户空间，然后该函数返回。在套接应用程序中，当调用recv()函数时，未必用户空间就已经存在数据，那么此时recv()函数就会处于等待状态。

优点：

  • 使用阻塞模式的套接字，开发网络程序比较简单，容易实现。
  • 当希望能够立即发送和接收数据，且处理的套接字数量比较少的情况下，使用阻塞模式来开发网络程序比较合适。

不足：

  • 在大量建立好的套接字线程之间进行通信时比较困难。
  • 当使用“生产者-消费者”模型开发网络程序时，为每个套接字都分别分配一个读线程、一个处理数据线程和一个用于同步的事件，那么这样无疑加大系统的开销。
  • 最大的缺点是当希望同时处理大量套接字时，将无从下手，其扩展性很差

非阻塞式I /O

非阻塞I/O通过进程反复调用I/O函数（多次系统调用，并马上返回）；在数据拷贝的过程中，进程是阻塞的。

应用进程执行系统调用之后，内核返回一个错误码。应用进程可以继续执行，但是需要不断的执行系统调用来获知 I/O 是否完成，这种方式称为轮询（polling）。

一个SOCKET接口设置为非阻塞即告诉内核：当所请求的I/O操作无法完成时，不要将进程睡眠，而是返回一个错误。此时I/O操作函数将不断的测试数据是否已经准备好，如果没有准备好，继续测试，直到数据准备好为止。在这个不断测试的过程中，会大量的占用CPU的时间。

套接字创建时一般默认是阻塞的，因此需要通过调用 ioctlsocket() 或 fcntl() 函数设置为非阻塞。

alt

图中进程多次调用revc() 函数，在数据报未准备完毕时立即返回。

由于 CPU 要处理更多的系统调用，因此这种模型的 CPU 利用率比较低。

I/O 复用

使用 select 或者 poll 等待数据，并且可以等待多个套接字中的任何一个变为可读。这一过程会被阻塞，当某一个套接字可读时返回，之后再使用 recvfrom 把数据从内核复制到进程中。

这两个函数可以同时阻塞多个I/O操作。而且可以同时对多个读操作，多个写操作的I/O函数进行检测，直到有数据可读或可写时，才真正调用I/O操作函数。

它可以让单个进程具有处理多个 I/O 事件的能力。又被称为 Event Driven I/O，即事件驱动 I/O。

如果一个 Web 服务器没有 I/O 复用，那么每一个 Socket 连接都需要创建一个线程去处理。如果同时有几万个连接，那么就需要创建相同数量的线程。相比于多进程和多线程技术，I/O 复用不需要进程线程创建和切换的开销，系统开销更小。

alt

信号驱动 I/O

应用进程使用 sigaction 系统调用，内核立即返回，应用进程可以继续执行，也就是说等待数据阶段应用进程是非阻塞的。内核在数据到达时向应用进程发送 SIGIO 信号，应用进程收到之后在信号处理程序中调用 recvfrom 将数据从内核复制到应用进程中。

相比于非阻塞式 I/O 的轮询方式，信号驱动 I/O 的 CPU 利用率更高。

alt

异步I/O

数据拷贝的时候进程无需阻塞。

应用进程执行 aio_read 系统调用会立即返回，应用进程可以继续执行，不会被阻塞，内核会在所有操作完成之后向应用进程发送信号。

异步 I/O 与信号驱动 I/O 的区别在于，异步 I/O 的信号是通知应用进程 I/O 完成，而信号驱动 I/O 的信号是通知应用进程可以开始 I/O。

当一个异步过程调用发出后，调用者不能立刻得到结果。实际处理这个调用的部件在完成后，通过状态、通知和回调来通知调用者的输入输出操作

alt

同步IO引起进程阻塞，直至IO操作完成。异步IO不会引起进程阻塞。IO复用是先通过select调用阻塞。

I/O 模型比较

alt

  • 同步 I/O：将数据从内核缓冲区复制到应用进程缓冲区的阶段（第二阶段），应用进程会阻塞。
  • 异步 I/O：第二阶段应用进程不会阻塞。

同步 I/O 包括阻塞式 I/O、非阻塞式 I/O、I/O 复用和信号驱动 I/O ，它们的主要区别在第一个阶段。

非阻塞式 I/O 、信号驱动 I/O 和异步 I/O 在第一阶段不会阻塞。

I/O 复用

select/poll/epoll 都是 I/O 多路复用的具体实现，select 出现的最早，之后是 poll，再是 epoll。

select

1
int select(int n, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);

select 允许应用程序监视一组文件描述符，等待一个或者多个描述符成为就绪状态，从而完成 I/O 操作。本质上是通过设置或者检查存放 fd 标志位的数据结构来进行下一步处理。

  • fd_set 使用数组实现，数组大小使用 FD_SETSIZE 定义，所以只能监听少于 FD_SETSIZE 数量的描述符。有三种类型的描述符：readset、writeset、exceptset，分别对应读、写、异常条件的描述符集合。

  • timeout 为超时参数，调用 select 会一直阻塞直到有描述符的事件到达或者等待的时间超过 timeout。

  • 成功调用返回结果大于 0，出错返回结果为 -1，超时返回结果为 0。

由于是通过检查 fd 标志位，可能带来以下缺点：

  • 单个进程可监视的fd数量被限制，即能监听端口的大小有限。与系统内存有关，32位机默认是1024个，64位机默认是2048。

  • 对socket进行扫描时是线性扫描，即采用轮询的方法，效率较低。当套接字比较多的时候，每次select()不管哪个Socket是活跃的,都遍历一遍，浪费CPU时间。

  • 需要维护一个用来存放大量 fd 的数据结构，使得用户空间和内核空间在传递该结构时复制开销变大。

poll

1
int poll(struct pollfd *fds, unsigned int nfds, int timeout);

poll 中的描述符是 pollfd 类型的数组，pollfd 的定义如下：

1
2
3
4
5
struct pollfd {
    int fd;         /* file descriptor */
    short events;     /* requested events */
    short revents;    /* returned events */
    };

poll 的功能与 select 类似，也是等待一组描述符中的一个成为就绪状态。

poll本质上和select没有区别，它将用户传入的数组拷贝到内核空间，然后查询每个fd对应的设备状态，如果设备就绪则在设备等待队列中加入一项并继续遍历，如果遍历完所有fd后没有发现就绪设备，则挂起当前进程，直到设备就绪或者主动超时，被唤醒后它又要再次遍历fd。这个过程经历了多次无谓的遍历。

由于采用链表存储，因此没有最大连接数的限制，但有以下缺点：

  • 大量的fd的数组被整体复制于用户态和内核地址空间之间，而不管这样的复制是不是有意义。
  • poll还有一个特点是“水平触发”，如果报告了fd后，没有被处理，那么下次poll时会再次报告该fd。

select 与 poll 比较

1. 功能

  • select 会修改描述符，而 poll 不会；
  • select 的描述符类型使用数组实现，FD_SETSIZE 大小默认为 1024，因此默认只能监听少于 1024 个描述符。如果要监听更多描述符的话，需要修改 FD_SETSIZE 之后重新编译；而 poll 没有描述符数量的限制；
  • poll 提供了更多的事件类型，并且对描述符的重复利用上比 select 高。
  • 如果一个线程对某个描述符调用了 select 或者 poll，另一个线程关闭了该描述符，会导致调用结果不确定。

2. 速度

select 和 poll 速度都比较慢，每次调用都需要将全部描述符从应用进程缓冲区复制到内核缓冲区。

3. 可移植性

几乎所有的系统都支持 select，但是只有比较新的系统支持 poll。

epoll

1
2
3
int epoll_create(int size);
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);

epoll_ctl() 用于向内核注册新的描述符或者是改变某个文件描述符的状态。已注册的描述符在内核中会被维护在一棵红黑树上，通过回调函数内核会将 I/O 准备好的描述符加入到一个链表中管理，进程调用 epoll_wait() 便可以得到事件完成的描述符。

从上面的描述可以看出，epoll 只需要将描述符从进程缓冲区向内核缓冲区拷贝一次，并且进程不需要通过轮询来获得事件完成的描述符。

epoll 仅适用于 Linux OS。

epoll 比 select 和 poll 更加灵活而且没有描述符数量限制。

epoll 对多线程编程更有友好，一个线程调用了 epoll_wait() 另一个线程关闭了同一个描述符也不会产生像 select 和 poll 的不确定情况。

工作模式

epoll 的描述符事件有两种触发模式：LT（水平触发，level trigger）和 ET（边缘触发，edge trigger）。

1. LT 模式（默认工作模式）

当 epoll_wait() 检测到描述符事件到达时，将此事件通知进程，进程可以不立即处理该事件，下次调用 epoll_wait() 会再次通知进程。是默认的一种模式，并且同时支持 Blocking 和 No-Blocking。

即只要 fd 处于可读或可写状态，就会通知用户。

2. ET 模式（高速工作模式）

和 LT 模式不同的是，通知之后进程必须立即处理事件，下次再调用 epoll_wait() 时不会再得到事件到达的通知。

很大程度上减少了 epoll 事件被重复触发的次数，因此效率要比 LT 模式高。只支持 No-Blocking，以避免由于一个文件句柄的阻塞读/阻塞写操作把处理多个文件描述符的任务饿死。

即 ET 只有不可读变为可读，或不可写变为可写之时，才会通知用户。因此 ET 对系统的调用比 LT 要少得多，所以 ET 是高速工作模式，效率高很多。

I/O 复用三种具体实现：select、poll 和 epoll 的区别总结：

1. 支持一个进程所能打开的最大连接数

类型 特点
select 单个进程所能打开的最大连接数由FD_SETSIZE宏定义，其大小是32个整数的大小（在32位的机器上，大小就是 $32 \times 32$，同理 64 位机器上FD_SETSIZE为 $32 \times 64$ ）；可以对进行修改，然后重新编译内核，但是性能可能会受到影响。
poll 没有最大连接数的限制，原因是它是基于链表来存储的。
epoll 连接数有上限，但是很大，1G内存的机器上可以打开10万左右的连接，2G内存的机器可以打开20万左右的连接。

2. FD(描述符)剧增后带来的I/O效率问题

类型 特点
select 每次调用时都会对连接进行线性遍历，所以随着FD的增加会造成遍历速度慢的“线性下降性能问题”。
poll 存在与 select 相同的问题。
epoll 因为 epoll 内核中是根据每个 fd 上的 callback() 函数实现的，只有活跃的 socket 才会主动调用 callback，所以在活跃 socket 较少的情况下，使用 epoll 没有线性下降的性能问题；但是所有socket都很活跃的情况下，可能会有性能问题。

3. 消息传递方式

类型 特点
select 内核需要将消息传递到用户空间，都需要内核拷贝动作。
poll 存在与 select 相同的问题。
epoll epoll通过内核和用户空间共享一块内存实现。

应用场景

1. select 应用场景

select 的 timeout 参数精度为微秒，而 poll 和 epoll 为毫秒，因此 select 更加适用于实时性要求比较高的场景，比如核反应堆的控制。

select 可移植性更好，几乎被所有主流平台所支持。

2. poll 应用场景

poll 没有最大描述符数量的限制，如果平台支持并且对实时性要求不高，应该使用 poll 而不是 select。

3. epoll 应用场景

只需要运行在 Linux 平台上，有大量的描述符需要同时轮询，并且这些连接最好是长连接。

需要同时监控小于 1000 个描述符，就没有必要使用 epoll，因为这个应用场景下并不能体现 epoll 的优势。

需要监控的描述符状态变化多，而且都是非常短暂的，也没有必要使用 epoll。因为 epoll 中的所有描述符都存储在内核中，造成每次需要对描述符的状态改变都需要通过 epoll_ctl() 进行系统调用，频繁系统调用降低效率。并且 epoll 的描述符存储在内核，不容易调试。

参考资料

CS-Notes
socket阻塞与非阻塞，同步与异步、I/O模型

发表于 更新于 分类于
本文字数： 3.2k 阅读时长 ≈ 3 分钟

DNS 域名系统

DNS 是一个分布式数据库，提供了主机名和 IP 地址之间相互转换的服务。这里的分布式数据库是指，每个站点只保留它自己的那部分数据。

域名具有层次结构，从上到下依次为：根域名、顶级域名、二级域名。

DNS 可以使用 UDP 或者 TCP 进行传输，使用的端口号都为 53。大多数情况下 DNS 使用 UDP 进行传输，这就要求域名解析器和域名服务器都必须自己处理超时和重传从而保证可靠性。

在两种情况下会使用 TCP 进行传输：

  • 如果返回的响应超过的 512 字节（UDP 最大只支持 512 字节的数据）。
  • 区域传送（区域传送是主域名服务器向辅助域名服务器传送变化的那部分数据）。

FTP 文件传送协议

FTP 使用 TCP 进行连接，它需要两个连接来传送一个文件：

  • 控制连接：服务器打开端口号 21 等待客户端的连接，客户端主动建立连接后，使用这个连接将客户端的命令传送给服务器，并传回服务器的应答。
  • 数据连接：用来传送一个文件数据。

根据数据连接是否是由服务器端主动建立，FTP 有主动和被动两种模式：

  • 主动模式：服务器端主动建立数据连接，其中服务器端的端口号为 20，客户端的端口号随机，但是必须大于 1024，因为 0~1023 是熟知端口号。

alt

  • 被动模式：客户端主动建立数据连接，其中客户端的端口号由客户端自己指定，服务器端的端口号随机。

alt

主动模式要求客户端开放端口号给服务器端，需要去配置客户端的防火墙。被动模式只需要服务器端开放端口号即可，无需客户端配置防火墙。但是被动模式会导致服务器端的安全性减弱，因为开放了过多的端口号。

DHCP 动态主机配置协议

DHCP (Dynamic Host Configuration Protocol) 提供了即插即用的连网方式，用户不再需要手动配置 IP 地址等信息。

DHCP 配置的内容不仅是 IP 地址，还包括子网掩码、网关 IP 地址。

DHCP 工作过程如下：

  • 客户端发送 Discover 报文，该报文的目的地址为 255.255.255.255:67，源地址为 0.0.0.0:68，被放入 UDP 中，该报文被广播到同一个子网的所有主机上。如果客户端和 DHCP 服务器不在同一个子网，就需要使用中继代理。

  • DHCP 服务器收到 Discover 报文之后，发送 Offer 报文给客户端，该报文包含了客户端所需要的信息。因为客户端可能收到多个 DHCP 服务器提供的信息，因此客户端需要进行选择。

  • 如果客户端选择了某个 DHCP 服务器提供的信息，那么就发送 Request 报文给该 DHCP 服务器。

  • DHCP 服务器发送 Ack 报文，表示客户端此时可以使用提供给它的信息。

Telnet 远程登录协议

TELNET 用于登录到远程主机上，并且远程主机上的输出也会返回。

TELNET 可以适应许多计算机和操作系统的差异，例如不同操作系统系统的换行符定义。

电子邮件协议

一个电子邮件系统由三部分组成：用户代理、邮件服务器以及邮件协议。

邮件协议包含发送协议和读取协议，发送协议常用 SMTP，读取协议常用 POP3 和 IMAP。

alt

1. SMTP

SMTP 只能发送 ASCII 码，而互联网邮件扩充 MIME 可以发送二进制文件。MIME 并没有改动或者取代 SMTP，而是增加邮件主体的结构，定义了非 ASCII 码的编码规则。

2. POP3

POP3 的特点是只要用户从服务器上读取了邮件，就把该邮件删除。但最新版本的 POP3 可以不删除邮件。

3. IMAP

IMAP 协议中客户端和服务器上的邮件保持同步，如果不手动删除邮件，那么服务器上的邮件也不会被删除。IMAP 这种做法可以让用户随时随地去访问服务器上的邮件。

常用端口

应用 应用层协议 端口号 传输层协议 备注
域名解析 DNS 53 UDP/TCP 长度超过 512 字节时使用 TCP
动态主机配置协议 DHCP 68/67 UDP
简单网络管理协议 SNMP 161/162 UDP
文件传送协议 FTP 20/21 TCP 控制连接21，数据连接20
远程终端协议 Telnet 23 TCP
超文本传送协议 HTTP 80 TCP
简单邮件传送协议 SMTP 25 TCP
邮件读取协议 POP3 110 TCP
网际报文存取协议 IMAP 143 TCP

Web 页面请求过程

1. DHCP 配置主机信息

假设主机最开始没有 IP 地址以及其它信息，那么就需要先使用 DHCP 来获取。

主机生成一个 DHCP 请求报文，并将这个报文放入具有目的端口 67 和源端口 68 的 UDP 报文段中。

该报文段则被放入在一个具有广播 IP 目的地址(255.255.255.255) 和源 IP 地址（0.0.0.0）的 IP 数据报中。

该数据报则被放置在 MAC 帧中，该帧具有目的地址 FF:FF:FF:FF:FF:FF，将广播到与交换机连接的所有设备。

连接在交换机的 DHCP 服务器收到广播帧之后，不断地向上分解得到 IP 数据报、UDP 报文段、DHCP 请求报文，之后生成 DHCP ACK 报文，该报文包含以下信息：IP 地址、DNS 服务器的 IP 地址、默认网关路由器的 IP 地址和子网掩码。该报文被放入 UDP 报文段中，UDP 报文段有被放入 IP 数据报中，最后放入 MAC 帧中。

该帧的目的地址是请求主机的 MAC 地址，因为交换机具有自学习能力，之前主机发送了广播帧之后就记录了 MAC 地址到其转发接口的交换表项，因此现在交换机就可以直接知道应该向哪个接口发送该帧。

主机收到该帧后，不断分解得到 DHCP 报文。之后就配置它的 IP 地址、子网掩码和 DNS 服务器的 IP 地址，并在其 IP 转发表中安装默认网关。

2. ARP 解析 MAC 地址

主机通过浏览器生成一个 TCP 套接字，套接字向 HTTP 服务器发送 HTTP 请求。为了生成该套接字，主机需要知道网站的域名对应的 IP 地址。

主机生成一个 DNS 查询报文，该报文具有 53 号端口，因为 DNS 服务器的端口号是 53。

该 DNS 查询报文被放入目的地址为 DNS 服务器 IP 地址的 IP 数据报中。

该 IP 数据报被放入一个以太网帧中，该帧将发送到网关路由器。

DHCP 过程只知道网关路由器的 IP 地址，为了获取网关路由器的 MAC 地址，需要使用 ARP 协议。

主机生成一个包含目的地址为网关路由器 IP 地址的 ARP 查询报文，将该 ARP 查询报文放入一个具有广播目的地址（FF:FF:FF:FF:FF:FF）的以太网帧中，并向交换机发送该以太网帧，交换机将该帧转发给所有的连接设备，包括网关路由器。

网关路由器接收到该帧后，不断向上分解得到 ARP 报文，发现其中的 IP 地址与其接口的 IP 地址匹配，因此就发送一个 ARP 回答报文，包含了它的 MAC 地址，发回给主机。

3. DNS 解析域名

知道了网关路由器的 MAC 地址之后，就可以继续 DNS 的解析过程了。

网关路由器接收到包含 DNS 查询报文的以太网帧后，抽取出 IP 数据报，并根据转发表决定该 IP 数据报应该转发的路由器。

因为路由器具有内部网关协议（RIP、OSPF）和外部网关协议（BGP）这两种路由选择协议，因此路由表中已经配置了网关路由器到达 DNS 服务器的路由表项。

到达 DNS 服务器之后，DNS 服务器抽取出 DNS 查询报文，并在 DNS 数据库中查找待解析的域名。

找到 DNS 记录之后，发送 DNS 回答报文，将该回答报文放入 UDP 报文段中，然后放入 IP 数据报中，通过路由器反向转发回网关路由器，并经过以太网交换机到达主机。

4. HTTP 请求页面

有了 HTTP 服务器的 IP 地址之后，主机就能够生成 TCP 套接字，该套接字将用于向 Web 服务器发送 HTTP GET 报文。

在生成 TCP 套接字之前，必须先与 HTTP 服务器进行三次握手来建立连接。生成一个具有目的端口 80 的 TCP SYN 报文段，并向 HTTP 服务器发送该报文段。

HTTP 服务器收到该报文段之后，生成 TCP SYN ACK 报文段，发回给主机。

连接建立之后，浏览器生成 HTTP GET 报文，并交付给 HTTP 服务器。

HTTP 服务器从 TCP 套接字读取 HTTP GET 报文，生成一个 HTTP 响应报文，将 Web 页面内容放入报文主体中，发回给主机。

浏览器收到 HTTP 响应报文后，抽取出 Web 页面内容，之后进行渲染，显示 Web 页面。

参考资料

CS-Notes

发表于 更新于 分类于
本文字数： 4.1k 阅读时长 ≈ 4 分钟

网络层只把分组发送到目的主机，但是真正通信的并不是主机而是主机中的进程。传输层提供了进程间的逻辑通信，传输层向高层用户屏蔽了下面网络层的核心细节，使应用程序看起来像是在两个传输层实体之间有一条端到端的逻辑通信信道。

UDP 的特点

用户数据报协议 UDP(User Datagram Protocol)是无连接的，尽最大可能交付（不提供可靠性：将应用程序传给IP的数据发送出去，但是并不保证能到达目的地），没有拥塞控制，面向报文（对于应用程序传下来的报文不合并也不拆分，只是添加 UDP 首部），支持一对一、一对多、多对一和多对多的交互通信。

UDP是制造IP分片的主要协议，数据长度超过MTU，就要对IP数据报进行分片

UDP三大应用：

  • 1.查询DNS（不需要TCP的三次握手，fast，多个DNS同时查询）
  • 2.数据传输TFTP：停止等待协议
  • 3.语音视频流：支持广播和组播，支持丢包保障效率

UDP 首部格式

alt
首部字段只有 8 个字节，包括源端口、目的端口、长度、检验和。12 字节的伪首部是为了计算检验和临时添加的。

TCP 的特点

传输控制协议 TCP（Transmission Control Protocol）是面向连接的，提供可靠交付，有流量控制，拥塞控制，提供全双工通信，面向字节流（把应用层传下来的报文看成字节流，把字节流组织成大小不等的数据块），每一条 TCP 连接只能是点对点的（一对一）。

面向连接意味着两个使用TCP的应用（一般是一个C一个S）在彼此交换数据前要建立TCP连接.

TCP放在IP数据报中（即可靠的TCP交给不可靠的IP(IP无连接)）

TCP 首部格式

alt

  • 每个TCP段都包含源端口和目的端口的端口号，用于寻找发送端和接收端应用进程。这两个值加上IP首部中的源端IP地址和目的端IP地址唯一确定一个TCP连接。
    一个IP地址和一个端口号称为一个插口（Socket）。

  • 序号 ：用于对字节流进行编号，例如序号为 301，表示第一个字节的编号为 301，如果携带的数据长度为 100 字节，那么下一个报文段的序号应为 401。

  • 确认号 ：期望收到的下一个报文段的序号。例如 B 正确收到 A 发送来的一个报文段，序号为 501，携带的数据长度为 200 字节，因此 B 期望下一个报文段的序号为 701，B 发送给 A 的确认报文段中确认号就为 701。确认序号应当是上次已成功接收到的数据字节序号加1，且只有在ACK为1时，确认号才有效。

  • 数据偏移 ：指的是数据部分距离报文段起始处的偏移量，实际上指的是首部的长度。（在别的书中，这个地方就是4位首部长度）
    4位首部长度不是指整个首部的长度，而是指首部有几个4字节的部分；TCP默认首部长度为5，即20字节，首部长度为4位二进制数，所以最多有15，即60字节，比20字节多的部分都是选项，这也是TCP为什么要有32位的序号的原因之一

  • 确认 ACK ：当 ACK=1 时确认号字段有效，否则无效。TCP 规定，在连接建立后所有传送的报文段都必须把 ACK 置 1。

  • 同步 SYN ：在连接建立时用来同步序号。当 SYN=1，ACK=0 时表示这是一个连接请求报文段。若对方同意建立连接，则响应报文中 SYN=1，ACK=1。

  • 终止 FIN ：用来释放一个连接，当 FIN=1 时，表示此报文段的发送方的数据已发送完毕，并要求释放连接。

  • 窗口 ：窗口值作为接收方让发送方设置其发送窗口的依据。之所以要有这个限制，是因为接收方的数据缓存空间是有限的。

TCP 的三次握手

alt

假设 A 为客户端，B 为服务器端。

  • 首先 B 处于 LISTEN（监听）状态，等待客户的连接请求。

  • A 向 B 发送连接请求报文，SYN=1，ACK=0，选择一个初始的序号 x。(初始序列号ISN是一个随时间变化的量，每4ms加一，避免不同连接有相同的序列号而出错连接TCP连接终止)

  • B 收到连接请求报文，如果同意建立连接，则向 A 发送连接确认报文，SYN=1，ACK=1，确认号为 x+1，同时也选择一个初始的序号 y。

  • A 收到 B 的连接确认报文后，还要向 B 发出确认，确认号为 y+1，序号为 x+1。

  • B 收到 A 的确认后，连接建立。

三次握手的原因

第三次握手是为了防止失效的连接请求到达服务器，让服务器错误打开连接。

客户端发送的连接请求如果在网络中滞留，那么就会隔很长一段时间才能收到服务器端发回的连接确认。客户端等待一个超时重传时间之后，就会重新请求连接。但是这个滞留的连接请求最后还是会到达服务器，如果不进行三次握手，那么服务器就会打开两个连接。如果有第三次握手，客户端会忽略服务器之后发送的对滞留连接请求的连接确认，不进行第三次握手，因此就不会再次打开连接。

TCP 的四次挥手

alt

  • A 发送连接释放报文，FIN=1。

  • B 收到之后发出确认，此时 TCP 属于半关闭状态，B 能向 A 发送数据但是 A 不能向 B 发送数据。

  • 当 B 不再需要连接时，发送连接释放报文，FIN=1。

  • A 收到后发出确认，进入 TIME-WAIT 状态，等待 2 MSL（最大报文存活时间）后释放连接。

  • B 收到 A 的确认后释放连接。

应用层应用程序发送FIN，该侧TCP就关闭，另一侧接收到FIN，返回ACK，同时需要返回一个自己的FIN通知源侧，源侧接收到这个FIN后，虽然TCP连接已关闭，但是会返回一个ACK

四次挥手的原因

客户端发送了 FIN 连接释放报文之后，服务器收到了这个报文，就进入了 CLOSE-WAIT 状态。这个状态是为了让服务器端发送还未传送完毕的数据，传送完毕之后，服务器会发送 FIN 连接释放报文。

TIME_WAIT

客户端接收到服务器端的 FIN 报文后进入此状态，此时并不是直接进入 CLOSED 状态，还需要等待一个时间计时器设置的时间 2MSL。这么做有两个理由：

  • 确保最后一个确认报文能够到达。如果 B 没收到 A 发送来的确认报文，那么就会重新发送连接释放请求报文，A 等待一段时间就是为了处理这种情况的发生。

  • 等待一段时间是为了让本连接持续时间内所产生的所有报文都从网络中消失，使得下一个新的连接不会出现旧的连接请求报文。

TCP 可靠传输

TCP 使用超时重传来实现可靠传输：如果一个已经发送的报文段在超时时间内没有收到确认，那么就重传这个报文段。

一个报文段从发送再到接收到确认所经过的时间称为往返时间 $RTT$，加权平均往返时间 RTTs 计算如下：

其中，$0 \leq a ＜ 1$，$RTTs$ 随着$a$的增加更容易受到$ RTT $的影响。
超时时间 $RTO$ 应该略大于 $RTTs$，TCP 使用的超时时间计算如下：

其中 $RTT_d$ 为偏差的加权平均值。

TCP 滑动窗口

滑动窗口协议滑动窗口实现了TCP流量控制。

窗口是缓存的一部分，用来暂时存放字节流。发送方和接收方各有一个窗口，接收方通过 TCP 报文段中的窗口字段告诉发送方自己的窗口大小，发送方根据这个值和其它信息设置自己的窗口大小。

发送窗口内的字节都允许被发送，接收窗口内的字节都允许被接收。如果发送窗口左部的字节已经发送并且收到了确认，那么就将发送窗口向右滑动一定距离，直到左部第一个字节不是已发送并且已确认的状态；接收窗口的滑动类似，接收窗口左部字节已经发送确认并交付主机，就向右滑动接收窗口。

接收窗口只会对窗口内最后一个按序到达的字节进行确认，例如接收窗口已经收到的字节为 {31, 34, 35}，其中 {31} 按序到达，而 {34, 35} 就不是，因此只对字节 31 进行确认。发送方得到一个字节的确认之后，就知道这个字节之前的所有字节都已经被接收。

alt

TCP 流量控制

滑动窗口协议滑动窗口实现了TCP流量控制。

流量控制是为了控制发送方发送速率，保证接收方来得及接收。

接收方发送的确认报文中的窗口字段可以用来控制发送方窗口大小，从而影响发送方的发送速率。将窗口字段设置为 0，则发送方不能发送数据。

TCP 拥塞控制

如果网络出现拥塞，分组将会丢失，此时发送方会继续重传，从而导致网络拥塞程度更高。因此当出现拥塞时，应当控制发送方的速率。这一点和流量控制很像，但是出发点不同。流量控制是为了让接收方能来得及接收，而拥塞控制是为了降低整个网络的拥塞程度。

alt

TCP 主要通过四个算法来进行拥塞控制：慢启动、拥塞避免、快速重传、快速恢复。

发送方需要维护一个叫做拥塞窗口（cwnd）的状态变量，注意拥塞窗口与发送方窗口的区别：拥塞窗口只是一个状态变量，实际决定发送方能发送多少数据的是发送方窗口。

alt

慢启动与拥塞避免

发送的最初执行慢启动，令 $cwnd = 1$，发送方只能发送 1 个报文段；当收到确认后，将 cwnd 加倍，因此之后发送方能够发送的报文段数量为：2、4、8 …

注意到慢启动每个轮次都将 cwnd 加倍，这样会让 cwnd 增长速度非常快，从而使得发送方发送的速度增长速度过快，网络拥塞的可能性也就更高。设置一个慢启动门限 ssthresh，当 $cwnd \geq ssthresh$ 时，进入拥塞避免，每个轮次只将 cwnd 加 1。

如果出现了超时，则令 $ssthresh = cwnd / 2$，然后重新执行慢启动。

快速重传与快速恢复

在接收方，要求每次接收到报文段都应该对最后一个已收到的有序报文段进行确认。例如已经接收到 M1 和 M2，此时收到 M4，应当发送对 M2 的确认。

在发送方，如果收到三个重复确认，那么可以知道下一个报文段丢失，此时执行快重传，立即重传下一个报文段。例如收到三个 M2，则 M3 丢失，立即重传 M3。

在这种情况下，只是丢失个别报文段，而不是网络拥塞。因此执行快速恢复，令 $ssthresh = cwnd / 2$，$cwnd = ssthresh$，注意到此时直接进入拥塞避免。

慢启动和快速恢复的快慢指的是 cwnd 的设定值，而不是 cwnd 的增长速率。慢启动 cwnd 设定为 1，而快速恢复 cwnd 设定为 ssthresh。

总结

  • 正常时：cwnd（拥塞窗口）值指数上升，直到达到慢启动门限值（ssthresh）后开始加性增长（线性）。
  • 超时：cwnd值变为1，慢启动门限变为原来cwnd值的一半，然后慢启动，到达慢启动门限值后进入拥塞避免。
  • 重复3个ACK（报文丢失）：首先，快速重传；之后快速恢复：快速恢复时，cwnd值设置为慢启动门限值（实际是慢启动门限值的一半加3）。

参考资料

CS-Notes

发表于 更新于 分类于
本文字数： 3k 阅读时长 ≈ 3 分钟

网络层是整个互联网的核心，因此应当让网络层尽可能简单。网络层向上只提供简单灵活的、无连接的、尽最大努力交互的数据报服务。

与 IP 协议配套使用的三个协议：

  • 地址解析协议 ARP（Address Resolution Protocol）
  • 网际控制报文协议 ICMP（Internet Control Message Protocol）
  • 网际组管理协议 IGMP（Internet Group Management Protocol）

IP数据报格式

alt

  • 版本 : 有 4（IPv4）和 6（IPv6）两个值；

  • 首部长度 : 占 4 位，因此最大值为 15。值为 1 表示的是 1 个 32 位字的长度，也就是 4 字节。因为固定部分长度为 20 字节，因此该值最小为 5。如果可选字段的长度不是 4 字节的整数倍，就用尾部的填充部分来填充。

  • 区分服务 : 用来获得更好的服务，一般情况下不使用。不置位表示一般传输。

  • 总长度 : 包括首部长度和数据部分长度。总长度16位表明最大65535字节。

  • 标识 : 在数据报长度过长从而发生分片的情况下，相同数据报的不同分片具有相同的标识符。

  • 标志 : 占3位。df，一旦大于mtu就丢弃，并返回icmp回显错误；mf：是否有更多的帧more fragment

  • 片偏移 : 和标识符一起，用于发生分片的情况的重新组装。片偏移的单位为 8 字节。

alt]

  • 生存时间 ：TTL，它的存在是为了防止无法交付的数据报在互联网中不断兜圈子。以路由器跳数为单位，每过一个路由器值就减一，当 TTL 为 0 时丢弃数据报。

  • 协议 ：指出携带的数据应该上交给哪个协议进行处理，例如 ICMP、TCP、UDP 等。即该数据报在IP头部之后的头部类型。

  • 首部检验和 ：因为数据报每经过一个路由器，都要重新计算检验和，因此检验和不包含数据部分可以减少计算的工作量。发送与接收时各校验一遍。

IP地址编址

IP地编址的三个历史阶段

  • 分类
  • 子网划分
  • 无分类（CIDR）

1. 分类

IP地址由两部分组成：网络号和主机号。
IP 地址::= {< 网络号 >, < 主机号 >}

alt

2. 子网划分

通过在主机号字段中拿一部分作为子网号，把两级 IP 地址划分为三级 IP 地址。

IP 地址 ::= {< 网络号 >, < 子网号 >, < 主机号 >}

要使用子网，必须配置子网掩码。

一个 B 类地址的默认子网掩码为 255.255.0.0，如果 B 类地址的子网占两个比特，那么子网掩码为 11111111 11111111 11000000 00000000，也就是 255.255.192.0。

外部网络看不到子网的存在。

3. 无分类

无分类编址 CIDR 消除了传统 A 类、B 类和 C 类地址以及划分子网的概念，使用网络前缀和主机号来对 IP 地址进行编码，网络前缀的长度可以根据需要变化。

IP 地址 ::= {< 网络前缀号 >, < 主机号 >}

CIDR 的记法上采用在 IP 地址后面加上网络前缀长度的方法，例如 128.14.35.7/20 表示前 20 位为网络前缀。

CIDR 的地址掩码可以继续称为子网掩码，子网掩码首 1 长度为网络前缀的长度。

一个 CIDR 地址块中有很多地址，一个 CIDR 表示的网络就可以表示原来的很多个网络，并且在路由表中只需要一个路由就可以代替原来的多个路由，减少了路由表项的数量。把这种通过使用网络前缀来减少路由表项的方式称为路由聚合，也称为 构成超网 。

在路由表中的项目由“网络前缀”和“下一跳地址”组成，在查找时可能会得到不止一个匹配结果，应当采用最长前缀匹配来确定应该匹配哪一个。

地址解析协议ARP

ARP 实现由 IP 地址得到 MAC 地址。

网络层实现主机之间的通信，而链路层实现具体每段链路之间的通信。因此在通信过程中，IP 数据报的源地址和目的地址始终不变，而 MAC 地址随着链路的改变而改变。

每个主机都有一个 ARP 高速缓存，里面有本局域网上的各主机和路由器的 IP 地址到 MAC 地址的映射表。

如果主机 A 知道主机 B 的 IP 地址，但是 ARP 高速缓存中没有该 IP 地址到 MAC 地址的映射，此时主机 A 通过广播的方式发送 ARP 请求分组，主机 B 收到该请求后会发送 ARP 响应分组给主机 A 告知其 MAC 地址，随后主机 A 向其高速缓存中写入主机 B 的 IP 地址到 MAC 地址的映射。

网际控制报文协议 ICMP

ICMP 是为了更有效地转发 IP 数据报和提高交付成功的机会。它封装在 IP 数据报中，但是不属于高层协议。

alt

ICMP 报文分为差错报告报文和询问报文。

alt

1. Ping

Ping 是 ICMP 的一个重要应用，主要用来测试两台主机之间的连通性。

Ping 的原理是通过向目的主机发送 ICMP Echo 请求报文，目的主机收到之后会发送 Echo 回答报文。Ping 会根据时间和成功响应的次数估算出数据包往返时间以及丢包率。

2. Traceroute

Traceroute 是 ICMP 的另一个应用，用来跟踪一个分组从源点到终点的路径。

Traceroute 发送的 IP 数据报封装的是无法交付的 UDP 用户数据报，并由目的主机发送终点不可达差错报告报文。

  • 源主机向目的主机发送一连串的 IP 数据报。第一个数据报 P1 的生存时间 TTL 设置为 1，当 P1 到达路径上的第一个路由器 R1 时，R1 收下它并把 TTL 减 1，此时 TTL 等于 0，R1 就把 P1 丢弃，并向源主机发送一个 ICMP 时间超过差错报告报文；
  • 源主机接着发送第二个数据报 P2，并把 TTL 设置为 2。P2 先到达 R1，R1 收下后把 TTL 减 1 再转发给 R2，R2 收下后也把 TTL 减 1，由于此时 TTL 等于 0，R2 就丢弃 P2，并向源主机发送一个 ICMP 时间超过差错报文。
  • 不断执行这样的步骤，直到最后一个数据报刚刚到达目的主机，主机不转发数据报，也不把 TTL 值减 1。但是因为数据报封装的是无法交付的 UDP，因此目的主机要向源主机发送 ICMP 终点不可达差错报告报文。
  • 之后源主机知道了到达目的主机所经过的路由器 IP 地址以及到达每个路由器的往返时间。

网络层设备：路由器

路由器从功能上可以划分为：路由选择和分组转发。

分组转发结构由三个部分组成：交换结构、一组输入端口和一组输出端口。

alt

路由器分组转发流程

  • 从数据报的首部提取目的主机的 IP 地址 D，得到目的网络地址 N。
  • 若 N 就是与此路由器直接相连的某个网络地址，则进行直接交付；
  • 若路由表中有目的地址为 D 的特定主机路由，则把数据报传送给表中所指明的下一跳路由器；
  • 若路由表中有到达网络 N 的路由，则把数据报传送给路由表中所指明的下一跳路由器；
  • 若路由表中有一个默认路由，则把数据报传送给路由表中所指明的默认路由器；
  • 报告转发分组出错。

路由选择协议

路由选择协议都是自适应的，能随着网络通信量和拓扑结构的变化而自适应地进行调整。

互联网可以划分为许多较小的自治系统 AS，一个 AS 可以使用一种和别的 AS 不同的路由选择协议。

可以把路由选择协议划分为两大类：

  • 自治系统内部的路由选择：RIP 和 OSPF
  • 自治系统间的路由选择：BGP

1. 内部网关协议 RIP

RIP 是一种基于距离向量的路由选择协议。距离是指跳数，直接相连的路由器跳数为 1。跳数最多为 15，超过 15 表示不可达。

RIP 按固定的时间间隔仅和相邻路由器交换自己的路由表，经过若干次交换之后，所有路由器最终会知道到达本自治系统中任何一个网络的最短距离和下一跳路由器地址。

2. 内部网关协议 OSPF

3. 外部网关协议 BGP

BGP（Border Gateway Protocol，边界网关协议）

BGP 只能寻找一条比较好的路由，而不是最佳路由。

每个 AS 都必须配置 BGP 发言人，通过在两个相邻 BGP 发言人之间建立 TCP 连接来交换路由信息。

参考资料

CS-Notes
子网

发表于 更新于 分类于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

数据链路层

将比特组合成字节，再将字节组合成帧，使用链路层地址（以太网使用MAC地址）来访问介质，并进行差错检测。

以太网帧格式

alt

  • 以太网目的地址源地址48位
  • 以太网的帧都有最小长度要求46字节

alt

  • 类型 ：标记上层使用的协议；
  • 数据 ：长度在 46-1500 之间，如果太小则需要填充；
  • FCS ：帧检验序列，使用的是 CRC 检验方法；

封装成帧

将网络层传下来的数据包（Packet）分组添加首部和尾部，用于标记帧的开始和结束。

透明传输

透明表示一个实际存在的事物看起来好像不存在一样。（对特定类型用户不可见）

帧使用首部和尾部进行定界，如果帧的数据部分含有和首部尾部相同的内容，那么帧的开始和结束位置就会被错误的判定。需要在数据部分出现首部尾部相同的内容前面插入转义字符。如果数据部分出现转义字符，那么就在转义字符前面再加个转义字符。在接收端进行处理之后可以还原出原始数据。这个过程透明传输的内容是转义字符，用户察觉不到转义字符的存在。

差错检测

数据链路层广泛使用循环冗余检验（CRC）来检查比特差错。
发送方和接收放首先协商一个 r + 1 位的二进制数（生成多项式）。将要发送的数据左移 r 位后，除以协商好的二进制数。
接收方收到数据后，收到的数据除以生成多项式所得的余数为 0 则说明数据无差错。

信道分类

广播信道

一对多通信，一个节点发送的数据能够被广播信道上所有的节点接收到。
所有的节点都在同一个广播信道上发送数据，因此需要有专门的控制方法进行协调，避免发生冲突（也称碰撞）。
主要有两种控制方法进行协调，一个是使用信道复用技术，一是使用 CSMA/CD 协议。

点对点信道

一对一通信。
不会发生碰撞，比较简单；使用 PPP 协议进行控制。

信道复用技术

1. 频分复用

频分复用的所有主机在相同的时间占用不同的频率带宽资源。

2. 时分复用

时分复用的所有主机在不同的时间占用相同的频率带宽资源。

以上两种通信方式在通信的过程中主机会一直占用一部分信道资源。但是由于计算机数据的突发性质，通信过程没必要一直占用信道资源而不让出给其它用户使用，因此这两种方式对信道的利用率都不高。

3. 统计时分复用

对时分复用的一种改进，不固定每个用户在时分复用帧中的位置，只要有数据就集中起来组成统计时分复用帧然后发送。

4. 波分复用

光的频分复用。由于光的频率很高，因此习惯上用波长而不是频率来表示所使用的光载波。

5. 码分复用

CSMA/CD 协议

CSMA/CD 表示载波监听多点接入 / 碰撞检测。

  • 多点接入 ：说明这是总线型网络，许多主机以多点的方式连接到总线上。
  • 载波监听 ：每个主机都必须不停地监听信道。在发送前，如果监听到信道正在使用，就必须等待。
  • 碰撞检测 ：在发送中，如果监听到信道已有其它主机正在发送数据，就表示发生了碰撞。虽然每个主机在发送数据之前都已经监听到信道为空闲，但是由于电磁波的传播时延的存在，还是有可能会发生碰撞。

PPP 协议

互联网用户通常需要连接到某个 ISP 之后才能接入到互联网，PPP 协议是用户计算机和 ISP 进行通信时所使用的数据链路层协议。

MTU

即最大传输单元， 属于链路层的传输特性，比MTU大的数据报需要“分片”。

MAC 地址

物理地址。是链路层地址，长度为 6 字节（48 位），用于唯一标识网络适配器（网卡）。
一台主机拥有多少个网络适配器就有多少个 MAC 地址。例如笔记本电脑普遍存在无线网络适配器和有线网络适配器，因此就有两个 MAC 地址。

ARP协议

地址解析协议（Address Resolution Protocol），基本功能为通过目标设备的IP地址，查询目标设备的MAC地址，保证通信的顺利进行。它是 IPv4 中网络层必不可少的协议，不过在IPv6中已不再适用，并被邻居发现协议（NDP）所替代。

局域网

局域网是一种典型的广播信道，主要特点是网络为一个单位所拥有，且地理范围和站点数目均有限。
主要有以太网、令牌环网、FDDI 和 ATM 等局域网技术，目前以太网占领着有线局域网市场。
alt

以太网

以太网是一种星型拓扑结构局域网。

早期使用集线器进行连接，集线器是一种物理层设备， 作用于比特而不是帧，当一个比特到达接口时，集线器重新生成这个比特，并将其能量强度放大，从而扩大网络的传输距离，之后再将这个比特发送到其它所有接口。如果集线器同时收到两个不同接口的帧，那么就发生了碰撞。

目前以太网使用交换机替代了集线器，交换机是一种链路层设备，它不会发生碰撞，能根据 MAC 地址进行存储转发。

数据链路层设备：交换机

交换机具有自学习能力，学习的是交换表的内容，交换表中存储着 MAC 地址到接口的映射。
由于具有自学习能力，交换机是一种即插即用设备，不需要网络管理员手动配置交换表内容。

虚拟局域网

虚拟局域网可以建立与物理位置无关的逻辑组，只有在同一个虚拟局域网中的成员才会收到链路层广播信息。

参考资料

CS-Notes