计算机网络

date

Jun 30, 2024

slug

computer-network

status

Published

Chapter2 The Physical Layer

Bandwidth and Channel Capacity

带宽：通常信道都有一个最高的信号频率（频率是指每秒钟的周期数，而每个周期都会有几次电平变化）和最低的信号频率，只有在这两个频率之间的信号才能通过这个信道，这两个频率的差值就叫做这个信道的带宽，单位是Hz。

信道容量：数据在信道中传输会有他们的速度——比特率，这里面最高的比特率就叫做这个信道的容量，单位是bps。就好象每条公路都有他们的最高限速，那么所有在里面开的车都不会超过这个速度。

注：通常习惯上，平时也会把信道容量叫做“带宽”，比如“带宽10M的网络”，“网络带宽是10M”等等。所以这两个概念也很容易混淆。我们平常所说的“带宽”不是带宽，而是信道容量。

波特率&比特率

波特率：每秒钟传送码元的数目，码元速率的单位为“波特”，常用符号“Baud”表示，简写为“B”

比特率（数据传输率）：单位bit/s

比特率Rb和波特率RB的关系： Rb = RB log2V

Nyquist & Shannon

Nyquist定理：无噪声的理想低通信道，若带宽为B (Hz)，信号电平为V级（码元数），则最大数据传输速率（信道容量）为：

Max. data rate = 2B log2V bits/sec

香农定理：S为信号功率，N为噪声功率，S/N称为信噪比（通常10log10S/N (dB)，比如S/N=1000则为30dB）。信噪比为S/N的信道，若带宽为B(Hz)，则最大数据传输速率（信道容量）为：

Max. data rate = B log2(1 + S/N) bits/sec

例题

例题1

If a binary signal is sent over a 3-kHz channel whose signal-to-noise ratio is 20 dB, what is the maximum achievable data rate?

Ans: A signal-to-noise ratio of 20 dB means S / N = 100. Since log2 101 is about 6.658, the Shannon limit is about 19.975 kbps. The Nyquist limit is 6 kbps. The bottleneck is therefore the Nyquist limit, giving a maximum channel capacity of 6 kbps.

例题2

A CDMA receiver gets the following chips: (−1 +1 −3 +1 −1 −3 +1 +1). Assuming the chip sequences defined as follows, which stations transmitted, and which bits did each one send?

Chapter3 Data Link Layer

功能

将物理层的无结构原始比特流划分成一定长度的结构数据单元—帧（Frame），即组帧（Framing）。

向网络层提供一个定义良好的接口

处理传输错误对帧进行差错控制（error control），实现检错/纠错功能

调节数据流通过合适的流量控制（flow control）协议保证收发双方的传输同步。确保慢速的接收方不会被快速的发送方淹没

MAC&DLC

数据链路控制（DLC）子层处理点对点和广播链接的所有共同问题：错误控制、流量控制、有序交付、透明传输

媒体访问控制（MAC）子层仅处理特定于广播链接的问题：地址解析、管理多播广播、网络访问控制：它决定一个设备何时可以访问物理媒体和如何与其他网络设备共享。例如，在以太网中使用CSMA/CD，而在无线网络中使用CSMA/CA

成帧技术

主要有以下4种组帧方法：

字节计数法

带字节填充的标志字节法

位填充的位标志法

物理层违例编码法

字节计数法

带字节填充的标志字节法

用来填充的转义字符出现在待发送的数据信息当中时，在出现的这个转义字符前插入一个转义字符。

位填充的位标志法

五个1后加个0

物理层违例编码法

海明码

海明距离d

纠错比特数大于 2d+1

检错比特数大于 d+1

假设校验码一共r位，我们想发的原始数据一共m位，要注意我们的校验码也要校验校验码错没错，所以，要校验的一共有m+r位，r位校验码可以检测2^r-1位的码，所以，校验码的位数要满足这个公式 2^r -1 >= m+r

校验和

求和

取反

验证时求和为0（包括校验和）

CRC

校验码的生成过程：假设要发送的信息用多项式 C(x) 表示，将 C(x) 左移 R 位（可表示成 C(x) << R），这样 C(x) 的右边就会空出 R 位，这就是校验码的位置。用 C(x) << R除以 G(x) 得到的余数就是校验码。

G(x)：表示 CRC 的生成多项式，是接收方和发送方的一个约定，由 CRC 规范给定。在整个传输过程中，这个二进制数始终保持不变。例如 CRC-CCITT 的生成多项式为 G(x) = x16 + x12 + x5 + 1。

C(x)：表示发送的原始数据的多项式。例如 C(x) = x5 + x3 + x2 + x + 1 表示发送的数据为 101111

R(x)：表示CRC 码的多项式。R(x) = (C(x) << R) % G(x)T(x)：表示发送的原始数据加上 CRC 码之后的多项式。T(x) = C(x) << R + R(x)

K：发送数据的长度。其等于 C(x) 中的最高次的幂 + 1。如上例子的 C(x) 中，K = 5 + 1 = 6

R： CRC 码的长度。CRC校验码位数 = 生成多项式G(x)位数 - 1。

x + 1 检查所有奇数位错误

Go-Back-N

W<=2^m -1

Selective Repeat

W<=2^(m-1)

例题

长度为2000位的数据帧，在数据传输速率为1 M bps、最大长度为1 km的物理线路上传输。假设线路的单向传输延迟时间为199ms/km，试计算下列协议中发送者的发送窗口大小，以及每种协议下物理通信线路可达到的最大利用率？（数据帧的序列号为4位，确认帧的发送时间忽略不计） (1) stop-and-wait协议(2) Go-Back-N帧的滑动窗口协议(3) Selective Repeat的滑动窗口协议

Chapter4 Medium Access Control Sublayer

功能：确定多路访问信道的下一个使用者，信道控制

ALOHA

有数据就发送

会冲突

易损期：两个帧时

Slotted ALOHA

时间槽到了才能发

冲突

CSMA

先听后发

1坚持：持续监听信道，一空就发

非坚持：不持续对信道进行监听，监听的时候空就发，忙则随机等待一个时间

p坚持：监听信道，如果空则以p概率发送，忙则等待下一个时间槽重复上述过程

会冲突：

信号传输的延迟造成的冲突；比如，由于时延第一个站的信号还没到达第二个站，第二个站则会认为信道空闲，会立即发送数据；多个站点在监听到信道空闲时，同时发送。

CSMA/CD

Transmission delay >= 2 * Propagation delay

无冲突协议

7.以下不属于无冲突协议的是（ D ）。

A.Bitmap B. Token Ring C. Binary Countdown D. Adaptive Tree Walk

隐藏终端&暴露终端

MACA

为什么CSMA/CD不能解决暴露终端问题？它只能检测冲突，不能避免冲突，无线介质上难以检测碰撞

MAC地址

6个比特，：分16进制

CSMA/CA

CSMA/CA与CSMA/CD的不同：在CSMA/CD中，节点侦听到信道空闲时立即发送；而在CSMA/CA中，节点要推迟发送，每新尝试一次都要随机回退。这是为了避免有多个站同时等待信道空闲，并发现信道空闲后立即发送而造成的冲突。

设备工作层

应用层	应用网关
传输层	传输网关
网络层	路由器
数据链路层	网桥、交换机
物理层	集线器、中继器

集线器是没法隔离冲突域。网桥交换域，可以隔离冲突域。路由器是隔离广播域。

VLAN

字母表示来源的颜色

其他

Ethernet头长度是14Bytes=Destination6Bytes+Source6Bytes+Type2Bytes

最小帧长度为64B

Chapter5 Network Layer

面向连接&无连接特点

无连接服务

每个数据包独立处理

网络层只负责将数据包从信源传送到目的地

信息中的数据包可能通过相同路径到达目的地，也可能不通过相同路径到达目的地。

面向连接的服务

在发送报文中的所有数据报之前，应建立一个虚拟连接来定义数据报的路径。

建立连接后，所有数据报都能沿着相同的路径发送。

数据包包含源地址和目的地址，还包含一个流标签，即定义数据包应遵循的虚拟路径的虚拟电路标识符。

链路状态路由

Dijkstra算法

距离矢量路由

Bellman-ford 算法

根据邻居节点的距离矢量更新自己的距离矢量

Count-to-Infinity Problem（无穷计算问题）

例题

Broadcast Routing

Multicast Routing

Sparse Case：

Anycast Routing

把所有的1节点看成一个1节点

Congestion Control V.s Flow Control

流量控制：

是为了控制发送方的发送速率，让发送方的发送速率不要太快，确保接收方来得及接收。具体来说，TCP是利用滑动窗口机制来实现对发送方的流量控制，接收方通过在发送的确认报文中填写窗口字段来控制发送方窗口大小，从而限制发送方的发送速率

拥塞控制：

是防止过多的数据注入网络中，从而确保网络中的路由器或链路不致过载。拥塞控制是一个全局性的过程，和流量控制不同，流量控制指点对点通信量的控制。

Packet Fragmentation分片

IPV4

IPV4分片

Hierarchy in IP Address

网络号、主机号、子网id

主机数要去掉全0和全1的主机号

IPV4 地址分类

A类 0xxxxx… 24host位

B类 10xxxxx… 16host位

C类 110xxxxx… 8host位

Subnet

把host号一部分拿出来当子网号

Supernet

Longest Matching Prefix

NAT转换

IPV6

ARP

例题

Consider the following network. With the indicated link costs, use Dijkstra’s shortest path algorithm to compute the shortest path from F to all network nodes.