引入-计算机网络导论

互联网（Internet）

互联网是 “网络的网络”（network of networks），由大量互联网服务提供商（ISP）相互连接而成，包括移动网络、家庭网络、机构网络、区域 ISP、全球 ISP 等层级。

网络结构（Network Structure）

一个计算机网络可以被分为：Network Edge，Network Core，Access Network。

Network Edge

Edge由各种终端、应用等等组成。从edge的视角看，网络有两种模型：

Client/Server 模型：在Client/Server模型下，设备朝服务器请求服务。典型的例子是万维网（www）、邮件等等。
Peer-peer 模型：在P2P模型下，没有专门的服务器。任何一个网络中的设备又作为客户端又作为服务端。典型的例子是BitTorrent。

Network Core

Core由路由、各种网络组成。在Core中，有两种通信方式：

电路交换：占用一个线路进行通信，例如电话线。
分组交换：将数据分为一个个小块发送。

Access Network

接入终端到网络中。通常来说，新加坡这边将其划归成住宅接入网（residential access network），机构接入网（institutional access network）和移动接入网（mobile access network）。

几种Access Network模型

拨号接入网（Dial-up Modem）

这是针对新加坡的模型

这是一种早期拨号上网时期的接入模型，其依附于电话网络。电脑的数据包经过拨号Modem调制，将其调制为电话语音频率的”数据信号”，并依附在电话网络上传输。电话和网络不能同时使用。

拨号Modem调制后的信号通过传统电话线，连接到电话网络的中心局（central office）。电话网络再连接到互联网服务提供商（ISP）的调制解调器，最终接入互联网（Internet）。

数字用户线路（Digital Subscriber Line，DSL）

最开始的Dial-up Modem有个问题：上网无法和电话同时进行，于是就发展出了DSL。

DSL在Modem前面加了一个Splitter，其实则是一个复用器，将电话网络与计算机网络复用在DSL phone line上。家庭的 DSL 线路连接到中心局的 DSL 接入多路复用器（DSLAM），DSLAM 负责把数据信号转发到 ISP 的网络，把语音信号转发到电话网。

在DSL线路中，语音信号与网络信号采用频分复用（FDM）。其上下行是非对称的，下行速率更高

有线电视网络（Cable Network）

与DSL类似，Cable Network将电视信号和网络信号通过splitter复用在电视的同轴线上传输。数据和电视信号被调制到不同的频率频段的信道上，在同一条共享电缆上并行传输。

前端机房（cable headend）是有线电视运营商的核心机房，负责接收和分发电视信号与互联网数据。互联网数据会被传输到对应的ISP中。

与 DSL 的 “专线接入” 不同，Cable 网络是共享式的。同一街区的多个家庭共享一段带宽。高峰时段，用户可能会感受到网速下降。

其上下行是非对称的，下行速率更高

现代家庭接入网（Home Access network）

现代家庭通常有多个设备，他们都接入家庭网关，家庭网关是一台集成了多种功能的设备（通常是家用无线路由器），它扮演了路由器、防火墙、NAT 的角色，负责管理家庭内网与外网的通信。

网关后连接 cable modem 或 DSL modem ，通向运营商的前端机房（headend）或中心局（central office），实现互联网接入。

机构以太网接入网（Enterprise Ethernet Access Networks）

在这种网络架构中：

笔记本电脑、台式机等终端设备，通过有线或无线（Wi-Fi）方式接入网络。
以太网交换机作为企业内网的核心设备，负责转发内网数据流量，将所有终端设备互联起来。
机构路由器通过专线或宽带链路连接到 ISP，实现互联网接入。

核心网

核心网由大量路由器通过链路互联，形成一个网状（mesh）拓扑。其没有单一的中心控制节点，而是通过分布式的方式协同工作。

核心网主要就干两件事：路由（routing）和转发（Forward）

路由（Routing）

作用：确定分组从源到目的所经过的完整路径。
实现：通过路由算法（如 OSPF, BGP），路由器之间交换网络状态信息，计算出最佳路径，并生成转发表。

转发（Forwarding）

作用：在单个路由器内部，根据分组头部的目的地址，查询本地转发表，将分组从正确的输入端口移动到对应的输出端口。
实现：这是一个高速的硬件操作，确保分组能快速通过路由器。

分组交换核心网

应用层的消息会被拆分成一个个小的分组（packet）进行传输。每个分组独立地从源主机出发，经过一系列路由器，可沿着不同的路径转发到目的主机。

由于分组交换中路由器必须先完整地接收一个分组，将其全部存入缓冲区，只有在整个分组都到达并被校验无误后，路由器才会开始将其从输出链路发送出去。这意味着，分组在每一跳都会产生时延。

分组交换的延迟

传输一个长度为 $L$ 比特的分组，通过速率为 $Rbps$ 的链路，所需时间为 $L/R$ 秒。

假设传播时延是0，那么端到端延迟就是$(n\times L)/R$，其中n是所经过的链路数。

排队与丢包

当分组交换的网络拥塞时，会产生一系列的问题：

排队时延（Queueing Delay）：当多个分组同时到达路由器，并且要从同一个输出链路转发时，它们会在输出缓冲区排队等待。

丢包（Packet Loss）：如果到达的分组速率持续超过链路的传输能力，路由器的缓冲区会被填满。当缓冲区已满时，新到达的分组会被丢弃，这就是丢包。

电路交换核心网

不同于分组交换将数据拆分成分组传输，电路交换在通信开始前，为源和目的之间的整条路径预留端到端的链路资源（如带宽）。这些资源在整个通话期间被独占，即使没有数据传输，资源也不会释放。

资源独享：没有共享，保证了稳定的性能。
资源浪费：如果通话中没有数据传输，预留的电路就会闲置，造成资源浪费。
典型应用：传统的电话网络就是电路交换的典型代表。

常见的电路交换使用FDM或TDM切分不同的信道。

分组交换vs电路交换

分组交换适合突发数据；可以信道资源共享，利用率高；更简单，无需呼叫设置。但肯呢个存在过度拥塞，导致数据包延迟和丢失（需要协议来实现可靠传输和拥塞控制）。

电路交换更为稳定。

现在分组交换在尝试提供类似电路交换的表现，对于音频 / 视频等对时延和抖动敏感的应用，需要带宽保证。这仍然是一个未完全解决的问题。

例题：计算35个用户下分组网络拥塞的概率

假设有一个1Mbps的网络，每个用户需求100Kbps, 但是只有10%的时间在使用。当处于分组交换时，他们使用网络的可能性相互独立，那么有n个用户正在使用网络的可能性就是：

$P(n)=\frac{35!}{n!(35-n)!}(10\%)^n(90\%)^{(35-n)}$

那么，同时使用网络的人数大于10个的可能性是：

$\sum_{n=11}^{35}p(n)=\sum_{n=11}^{35}\frac{35!}{n!(35-n)!}(10\%)^n(90\%)^{(35-n)}=0.0004$

因此，使用分组交换的网络，1Mbps下承载35个用户网络出现阻塞的可能性为0.0004，在99.9996%的情况下网络都是畅通的。

互联网结构

全世界的设备都通过ISP（Internet Service Provider）接入互联网。为了使互联网中的任意设备都可以互相发送数据包，不同ISP间需要互相联通。

全球有非常多不同的ISP，不同国家也有不同的政策。因此互联网的拓补是经济和国家政策的融合产物。

全球有很多个ISP接入点，如果将他们点对点连接，则N个接入点就需要$N^2$条链路进行连接，如下图（a）。这很明显不现实。

我们对其进行改进，设置一个全球中继ISP，所有的接入ISP都通向全球ISP，这样可以大大缩减链路数量，如下图（b）。各个ISP需要向全球ISP缴纳费用以维护其运行。

但是，全球ISP是一个商业业务，其必然会出现竞争对手，有多个全球ISP出现，如下图（c）。此时，不同的全球ISP间就需要进行连接，这个互联点被称为互联网交换点（Internet Exchange Point，IXP）；同时，部分ISP间也会有直连链路（peer link），如下图（d）。

同时，一些互联网巨头（例如Google），他们作为内容提供商，有非常庞大的机构网络。他们的机构网络也可以作为与全球ISP同一级的存在，方便用户访问。

最终，就得到了这样一个层级：

Tier 1 ISP（骨干网）：位于互联网中心的少数大型商业 ISP（如 Level 3、Sprint、AT&T、NTT）。拥有全国乃至全球的覆盖能力，是互联网的 “骨干”。它们之间通过对等互联（peering）直接交换流量。

Regional ISP（区域 ISP）：连接多个接入 ISP，并通过 IXP 与 Tier 1 ISP 或其他区域 ISP 互联。作为中间层，负责区域内的流量汇聚和转发。

Access ISP（接入 ISP）：最底层的 ISP，直接服务于家庭、企业和校园用户（如电信、联通的家庭宽带）。它们是用户接入互联网的 “最后一公里”。

Content Provider Network（内容提供商网络）：如 Google 这样的大型公司，会构建自己的私有网络。通过 IXP 直接与 Tier 1 和区域 ISP 互联，将数据中心和服务 “推” 到离用户更近的地方，绕过 Tier-1 ISP，从而降低成本、提升速度。

计算机网络中的延迟与丢包

延迟

链路上的各个延迟

延迟由网络中的转发和传播和处理产生。

在一条链路上，总节点时延由四部分组成：

$d_{nodal}=d_{proc}+d_{queue}+d_{trans}+d_{prop}$

其中：

$d_{proc}$：节点处理时延。路由器对分组进行初步检查和决策，检查分组头部是否存在比特错误，根据目的地址，决定分组应该从哪个输出链路转发。（在这门课中通常忽略）
$d_{queue}$：排队时延。分组在路由器输出缓冲区中等待被发送的时间。当网络空闲时，排队时延接近 0；当网络拥塞时，时延会显著增加，甚至导致丢包。
$d_{trans}$：传输时延。将比特流注入传输链路所需的时间。$d_{trans}=L/R$，L是链路长度，R是链路速率。
$d_{prop}$：传播时延。分组的第一个比特从链路起点传播到终点所需的时间，$d_{prop}=d/s$，其中d是物理链路的长度，s是信号在链路中的传播速度（约$ 2×10^8 m/sec$）

可以用下图这样的形式来标记传输延迟和传播延迟。下图两端分别表示发送端和接收端。两端的上下表示整体延迟（下图中T+P/R）。蓝色条条的宽度表示传输延迟（P/R），蓝色条条斜率造成的延迟表示传播延迟（T）。

上图中上半图是$传播延迟>>传输延迟$的情况；下半图是$传播延迟<<传输延迟$的情况。

流量强度与排队时延

使用下式定义链路上的流量强度：

$\frac{La}{R}$

R：链路带宽（bps）
L：分组长度（bits）
a：平均分组到达速率（分组 / 秒）

这是当前链路的传输数据量与链路承载能力的比值。

时延趋势

当 $\frac{L a}{R} \approx 0$ ：流量远小于链路能力，平均排队时延很小，几乎可以忽略。
当 $\frac{L a}{R} \to 1$ ：流量接近链路极限，平均排队时延急剧增大，网络变得非常拥塞。
当 $\frac{L a}{R} > 1$ ：到达的“工作量”超过了链路能处理的极限，缓冲区会被持续填满，平均排队时延趋向于无穷大，最终导致大量丢包。

在现实中，使用traceroute工具，可以发送一个ICMP数据包，来测量从源主机到目的主机路径上，每一跳路由器的时延。

丢包

丢包原因

路由器的缓冲区（buffer）容量是有限的。
当分组到达的速率超过链路的传输速率时，分组会在缓冲区排队。
如果缓冲区已满，新到达的分组就会被丢弃，即发生丢包。

丢包处理

被丢弃的分组可能会被上一跳节点重传，也可能由源端系统重传，或者在某些应用中（如实时视频通话）干脆不重传，以保证实时性。

吞吐量

定义：吞吐量是指在单位时间内，从发送端到接收端成功传输的比特数（bits/time unit），它衡量了数据传输的实际速率。

两种类型：

瞬时吞吐量（Instantaneous）：在某个特定时间点的传输速率。
平均吞吐量（Average）：在一段较长时间内的平均传输速率，更能反映整体性能。

瓶颈链路（Bottleneck Link）

在端到端的传输路径上，吞吐量由速率最慢的链路决定，这条链路就是瓶颈链路。如下例，当$R_sR_c$时，链路速率由$R_c$决定；

互联网场景下的吞吐量

在多用户共享的互联网环境中，吞吐量仍旧由链路中最慢的一环限制：

$\text{Throughput}=\min(R_s,\frac{R}{n},R_c)$

其中，$R_s$是服务器发送速率；$\frac{R}{n}$是被n个连接公平共享骨干链路时，每个连接能分到的带宽；$R_c$是客户端速率。

例题

考虑从 A 发送一条 F 位的信息到 B，其中 A 和 B 之间通过两条链路连接，中间有一个交换机。设链路不拥塞，因此没有排队延迟。两个链路的传输速率均为 R bps。假设 A 将消息分割成每个 S 位的段，并向每个段添加 h 位的开销，以形成其传输给 B 的每个数据包。

交换机以存储转发模式工作。（对于接收到的每个数据包，它会在开始在输出链路上发送数据包之前缓冲整个数据包；然而，它可以在发送第i个数据包的同时接收第(i+1)个数据包。）假设传播延迟可以忽略，并且数据包可以在无需确认的情况下连续发送。

1.如果 S=F，从 A 发送消息到 B 会产生多少延迟？

此时，只有一个段，段长度为$S+h$。传输时延为$\frac{S+h}{R}$。由于传播时延可以忽略，传播过程如下图所示

因此总时间是$2\times\frac{S+h}{R}$

2.如果 S=F/n（n 是 A 用来传递消息的分段数量），从 A 发送消息到 B 会产生多长时间的延迟？

此时单个段的传输时延为$\frac{F/n+h}{R}$，总时延为$n+1$个传输时延，整理得：

$t_{total}=(n+1)\frac{F/n+h}{R}=(n+1)\frac{F+nh}{nR}=\frac{n+1}{n}\cdot\frac{F+nh}{R}$

3.根据在第2步推导的公式，推导出使从A发送消息到B的总延迟最小的分段大小S。

整理第二步的公式：

$t_{totoal}=\frac{n+1}{n}\cdot\frac{F+nh}{R}=\frac{hn^2+(F+h)n+F}{nR}$ $=\frac{hn}{R}+\frac{F+h}{R}+\frac{F}{nR}$

对n求导，令其等于0来寻找极值点，$(\frac{hn}{R})’=\frac{h}{R}$，$(\frac{F+h}{R})’=0$，$(\frac{F}{nR})’=-\frac{F}{n^2R}$

$\frac{dt_{totoal}}{dn}=\frac{h}{R}-\frac{F}{n^2R}=0$

整理得：$n=\sqrt{\frac{F}{h}}$，因此，将F bits的数据切分成$\sqrt{\frac{F}{h}}$段，整体传输时延最小。$S=F/n=\sqrt{Fh}$。