计算机网络课程笔记

概论

因特网概述

网络、互联网、和因特网

网络由若干节点和连接这些节点的链路组成
多个网络还可以通过路由器连接起来，构成互联网(internet)
因特网是最大的互联网(Internet)

基于ISP的三层结构因特网

因特网的组成

从功能上看：

边缘部分：连接在因特网上的主机组成
核心部分：大量网络和连接网络的路由器组成

三种交换方式

电路交换

每一部电话都连接到电话交换机上

电路交换的三个步骤：

建立连接（分配通信资源）
通话（一直占用通信资源）
释放连接（归还通信资源）

计算机数据是突发式的，使用电路交换效率很低

分组交换

报文->数据段->包（分组）

发送方：

构造分组
发送分组

路由器：

缓存分组
转发分组

接收方：

接受分组
还原报文

存储转发传输

在一个速率为R bps的链路，一个长度为 L bits的分组的存储转发延时：L/R

排队延迟和丢失

如果到达速率>链路的输出速率：

分组将会排队，等待传输
如果路由器缓存用完了，分组将会被抛弃

网络核心的关键功能

路由
转发

数据报和虚电路

数据报：在通信之前，无需建立起一个连接，有数据就传输，每一个分组都包含目标主机的全部信息，每一个分组都独立路由
虚电路：有连接

对比

电路交换优点：

通信时延小
有序传输
没有冲突
适用范围广
实时性强
控制简单

电路交换缺点：

建立连接时间长
线路独占，使用效率低
灵活性差
难以规格化
不够可靠，一个节点被破坏造成大量损坏

报文交换优点：

无需建立连接
动态分配线路
提高线路可靠性
提高线路利用率
提供多目标服务

报文交换缺点：

引起了转发时延（缓存）
需要较大的存储缓存空间
需要传输额外的信息量

分组交换优点：

无需建立连接
线路利用率高
简化了存储管理
加速传输
减少出错概率和重发数据量（分组比报文小）

分组交换缺点：

引起了转发时延
需要传输额外信息量（目的信息等）
失序，丢失，重复分组等问题

接入网和物理媒体

住宅接入：modem

将上网数据调制加载在音频信号上在电话线上传输

住宅接入：线缆网络

有线电视线缆双向改造，用于传输网络数据

物理媒体

导引性媒体

双绞线
同轴电缆
光缆：级宽带宽，误码率低

无线链路

地面微波
LAN（WiFi）
wide-area（蜂窝 5G）

分组延时、丢失和吞吐量

分组延时和丢失

分组到达链路的速率超过了链路输出的能力

四种分组延时

分组处理延时：检查bit级差错，检查分组首部和决定分组导向何处
排队延时：等待输出时间，取决于拥塞程度
- 流量强度= La/R
- 流量强度>=1，平均排队延时趋于无穷大
传输延时: 将分组发送链路上的时间
传播时延

分组丢失

链路的队列缓冲有线
当分组到达一个满的队列时，该分组将会丢失
丢失的分组可能会被前一个节点或源端系统重传，或者根本不重传

吞吐量

在源端和目标端之间的速率

瓶颈链路：限制了端到端传输速率的链路

协议层次和服务模型

将复杂的网络功能分成多个层次的功能

服务：低层实体向上层实体提供它们之间通信的能力

原语：服务提供者向服务用户提供服务的形式

服务访问点：用于区分上层服务用户的信息

服务的类型

面向连接
无连接

Internet协议栈

应用层：网络应用
- FTP，HTTP
传输层：进程到进程之间的区分，加强网络服务，不可靠服务转为可靠服务
网络层：以分组为单位进行端到端的数据传输（完成转发，路由）
链路层：相邻两点传输以帧为单位的数据
物理层：实现物理信号和数字数据（bit）之间的转换

ISO/OSI 参考模型

应用层

应用层原理

网络应用的体系结构

可能的应用架构：

客户-服务器（C/S）架构：服务器在固定地址和端口先跑起来
p2p：几乎没有一直运行的服务器
p2p 和 C/S混合架构

进程通信

客户端进程：发起通信的进程

服务器进程：等待连接的进程

所面临的问题：

对方进程寻址和标识的问题
- IP+TCP/UDP（port）
下层提供的服务是怎样的？（地点和形式）
- SAP
  - 数据本身sdu
  - 我方的进程标识
  - 对方的进程标识
- socket API：（源IP，源端口，目标IP，目标端口）。由本地操作系统管理，较少了层间传输的信息。socket是一个整数，就像文件句柄一样，代表两个主机的会话关系。
- UDP socket：本IP，本端口，但是传输报文时必选还要提供对方IP，端口
如何使用下层服务，实现网络应用
- 制定应用层协议：公开协议：http
- 编写程序

应用层协议

定义了运行在不同端系统上的应用进程如何相互交换报文

交换报文的类型
各种报文类型的语法
字段的语义
进程何时，如何发送报文以及如何对报文响应的规则

公有协议：

RFC文档定义
http，smtp

私有协议：

不公开，如skype

应用层需要传输层提供什么服务？

损失率
延迟
吞吐
安全
- tcp udp都是明文传输
- ssl库，在应用层，https

UDP存在的必要性

能够区分进程，而IP服务不能
- 在IP服务提供了主机到主机功能的基础上，UDP能够区分应用进程
无需建立连接，省去了建立连接的时间，适合事务性较强的应用
不做可靠性的工作，如检错重发，适合那些对实时性较高而准确性要求不高的应用
没有拥塞控制和流量控制，可以按照设定的速度发送

Web 与Http

一些术语

Web页：有一些对象组成
Web页含有一个基本的HTML文件，该HTML又含有其他对象的引用
通过URL对每个对象进行引用
URL格式

HTTP

HTTP：超文本传输协议

应用层协议
客户/服务器模式
使用tcp
http是无状态的：服务器不维护关于客户的任何信息

非持久http

最多只有一个对象在TCP连接上发送
http1.0

持久http

多个对象可以在TCP连接上传输
http1.1
- 非流水方式的持久HTTP
  - 客户端只有在收到前一个的响应时才发出新的请求
  - 每个对象只需要一个RTT
- 流水方式的持久HTTP
  - 默认模式
  - 所有小对象只花费一个RTT是可能的

响应模型

往返时间RTT：一个小的分组从客户端到服务器，再回到客户端的时间

响应时间：

用一个RTT来发起TCP连接
一个RTT用来HTTP请求并等待HTTP响应
文件传输时间

总共：2RTT+传输时间（注意：请求的传输时间忽略不计）

非持久HTTP缺点：

每个对象都要两个HTTP
操作系统必须为每个TCP连接分配资源

HTTP报文

两种类型：请求、响应

HTTP请求报文：

ASCII

HTTP响应报文：

cookies

http是一种无状态的协议，服务端不维护客户端的状态

cookie包含4个组成部分：

在http响应报文中有一个cookie的首部行
在http请求报文中有一个cookie的首部行
用户端系统有一个cookie文件，由浏览器管理
web站点有一个后端数据库

web缓存

通常缓存由ISP安装

降低客户端的响应时间
减少web服务器的负载
减少网络的负担

FTP

向远程主机上传文件或从远程主机下载文件

端口：21

客户端和服务器通过21端口联系，并使用TCP为传输协议

客户端通过控制连接获得身份确认

主动模式：服务器主动向客户端20号端口建立数据连接。数据连接和控制连接是两个tcp连接

Email

3个组成部分：

用户代理：软件客户端
邮件服务器
简单邮件传输协议：SMTP

邮件服务器

管理和维护发送给用户的邮件

邮件服务器之间的SMTP协议：发送Email协议

SMTP

使用TCP，端口为25

使用持久连接

传输的3个阶段：

握手
传输报文
关闭

与HTTP的比较：

HTTP pull
SMTP push
二者都是ASCII形式的命令/响应交互、状态码

HTTP: 每个对象封装在各自的响应报文中

SMTP：多个对象包含在一个报文中

邮件访问协议：

DNS

域名和ip地址mac地址，以及主机都不是一一对应关系

DNS总体思路和目标

主要思路：

分层的命名
分布式的数据库
运行在UDP之上端口53的应用服务

主要目标：

实现主机名-IP地址的转换
其他目的：
- 主机别名和规范名字的转换
- 负载均衡

DNS命名空间

DNS域名结构：

Internet分为几百个顶级域:
- 通用：.com .edu .gov
- 国家：.cn
每个（子）域都可以划分为若干子域
树叶是主机

域名的管理：

一个域管理其下的子域

域和物理网络无关：

域的划分是逻辑的，而不是物理的

DNS根域名服务器

共有13个根名字服务器

DNS解析问题

区域：

将DNS命名空间划分为互不相交的区域，每个区域都有一个名字服务器
名字服务器：
- 每个区域都有一个名字服务器：维护着它所管辖区域的权威信息

区域名字服务器维护资源记录：

资源记录：
- 作用：维护域名-IP转换关系
- 位置：名字服务器的分布式数据库中
RR格式：
- domian name
- ttl：如果ttl有限就是一个缓冲
- class：对于Internet，值为IN
- value
- type

域名服务器

目标名字在本地名字服务器中：

情况1：该域名在区域内部
情况2：缓存

递归查询：根服务器负担大

迭代查询：

维护问题

在上级域中增加两条记录，指向这个子域的域名和域名服务器的地址

在新增子域的名字服务器上运行名字服务器，负责本域的名字解析：名字->IP地址

p2p应用

纯p2p架构

没有（或者极少）一直运行的服务器
任意端都可以直接通信
利用peer的服务能力

例子：

文件分发
流媒体

非结构化p2p

覆盖网的结构是随机的的

集中化目录

用户输入关键字，目录服务器返回具有该资源的节点的地址，客户端再去相应节点请求资源。客户端同时又可以向其他节点提供服务。目录服务器维护正在活跃的peer节点

纯在的问题：

单点故障
性能瓶颈
版权问题

完全分布式

构建覆盖网：

客户端具有配置文件，配置文件中具有长期活跃的若干节点。客户端ping长期活跃节点，长期活跃节点返回pong，并转发ping到其邻居，邻居返回pong到客户端，并继续转发。

查询：

泛洪：向邻居发送查询，邻居继续向其邻居发送查询，拥有资源的节点做出应答

混合体

每个peer要么是一个组长，要么隶属于一个组长

组长跟踪其所有孩子的内容

结构化p2p

覆盖物网具有结构，如：环，树

CDN

DASH

CDN（content distribution networks）

方式1：单个的，大的超级服务中心

服务器到客户端路径上跳数较多，瓶颈链路的带宽小导致停顿
“二八规律”决定了网络同时充斥着同一个视频的多个拷贝，效率低（付费高、带宽浪费、效果差）
单点故障，性能瓶颈
周边网络拥塞
简单，不可扩展

方式2：通过CDN，全网部署缓存节点，存储服务内容，就近为用户提供服务，提高用户体验

TCP socket编程

服务器首先运行起来等待连接建立：

创建欢迎socket
socket绑定本地端口
在欢迎socket上阻塞式的等待接收用户的连接

客户端主动和服务器建立连接：

创建客户端socket（隐式捆绑本地port）
指定服务器的ip和port
与服务器进程建立连接

服务器接受来自客户端的请求，解除阻塞式等待，返回一个新的sokcet与客户端通信

允许服务器与多个客户端通信
通过源IP和源端口区分客户端

传输层概述和传输层服务

为运行在不同主机上的进程提供逻辑通信

网络层：主机之间的逻辑通信（点到点通信）

传输层：进程之间的逻辑通信（端到端通信）

依赖于网络层的服务：带宽，延时（这是无法加强的服务）
加强网络层的服务：可靠

多路复用/解复用(分用)

复用：从多个套接字接收来自多个进程的报文，根据套接字对应的IP地址和端口号等信息对报文段用头部加以

封装 (该头部信息用于以后的解复用)。（不同的应用进程都可以使用同一个传输层协议传送数据）

解复用：根据报文段的头部信息中的IP地址和端口号将接收到的报文段发给正确的套接字(和对应的应用进程)（接收方的传输层在剥去报文的头部后能够把这些数据正确交付到相应的应用进程）

无连接传输：UDP

尽力而为的服务，报文可能丢失，报文段乱序，不提供流量控制和拥塞控制

只提供两个功能：

多路复用
差错检测

使用UDP进行数据传输，必须在应用层完成可靠性方面的全部工作。

无连接：

发送端，接收端之间没有握手
每个UDP报文段都被独立处理

应用于：

优势：

不会引入建立连接的时延
无连接状态，不用维护连接状态
分组头部更小
应用层能更好的控制发送的数据和发送时间（按照设定的速度发送），因为没有拥塞控制
udp支持一对一，一对多，多对一，多对多通信

UDP是面向报文的，保留了报文的边界

UDP：用户数据段协议

校验和填充为0代表不使用校验和功能

UDP的一些优势：

不需要连接（延时低）
报文段的头部小（减少开销）
没有拥塞控制和流量控制，可以快速地发生报文段

UDP检验和

数据报会被分为很多个16bit

如果不使用校验和方式，则校验和字段设置为0，如果正好校验和字段为全0 则应该修改为全1

检验和：

检验方式：

可靠连接传输

可靠连接传输：问题描述

网路top 10的问题

下层不可靠，但是需要为上层提供可靠的服务

一些前提:

只考虑单向通信（双向通信等于两个单向通信）
使用有限状态机描述机制

Rdt1.0：在可靠信道上的可靠数据传输

下层信道完全可靠：

没有比特出错
没有分组丢失

Rdt2.0：可能出错的信道

下层信道可能出错，可能比特翻转

发送方：

接收方：

Rdt2.1 ACK/NAK出错

ACK/NAK出错时，发送方不知道发送是否成功，需要再次重新发送，而接收方不知道发送方的是重发的还是新发的，所以需要序号的机制。

发送方：

两个序号0，1就够了：每次只发送一个未被确认的分组

接收方：必须检测接收到的分组是否重复

Rdt2.2 无NAK

功能同2.1，但是只有ACK（增加了序号）

Rdt3.0：具有比特出错和分组丢失的信道

发送方：

下层信道可能丢失分组：
- 造成死锁
增加一个机制：超时重传
- 问题：可能是ACK丢失，可以用序列号解决
- 过早超时：造成大量重复
性能：

滑动窗口协议

SW：

sw = 1，rw = 1，停止等待协议
sw > 1, rw = 1, GBN(流水线)
sw > 1, rw > 1, SR（流水线）

发送缓冲区:

内存当中的一个区域，用于存放已发送但是没有接收到确认的分组
若缓冲区已满，上层停止交付分组

发送窗口：

已经发出的，但未收到确认的一个范围，是发送缓冲的一个子集

GBN和SR协议的异同：

窗口尺寸的大小：

面向连接的传输：TCP

特点：

面向连接的传输层协议
每条TCP连接只能有两个端点，只能是端到端的
TCP提供可靠的交付服务
提供全双工通信
面向字节流

报文段结构

序号是body部分第一个字节在整个字节流中的偏移量
校验和：包括头部和数据部，需要加上12B的伪首部（伪首部包括目标IP，源IP，协议字段（6））

TCP往返延时和超时

设置TCP超时：

比RTT要大
根据短时间内的RTT进行设置超时

求RTT：

simpleRTT：测量从报文段发出到收到确认的时间，对最近的几次RTT求平均
estimateRTT：越过去的RTT的贡献越小

可靠数据传输

TCP在IP的不可靠传输服务的基础建立了rdt，对报文段增加了确认机制

累计确认（GBN）
单个重传定时器（SR）

从应用层接收数据：

用nextseq创建报文段
如果还没运行，创建定时器：
- 定时器与最早未确认的报文相关联

快速重传

重传有两种触发方式：

超时（重传计时器的时间是一种自适应算法）
冗余ACK

如果发送方接收到三个冗余的ACK，直接重传（不等定时器）即快速重传

TCP流量控制

消除发送方发送数据太快使得接收方缓冲区溢出的可能性

接收方在其向发送方的TCP段头部的rwnd字段“通告”其空闲buffer大小
- RcvBuffer大小通过socket选项设置 (典型默认大小为4096 字节)
- 很多操作系统自动调整RcvBuffer
发送方限制未确认字节的个数<=接收方发送过来的rwnd值

TCP连接控制

问题：两次握手可以吗？

失败的场景：

3次握手连接可以解决半连接和收老数据的问题

TCP释放连接

客户端、服务器分别关闭自己这一侧的连接

发送FIN bit=1的TCP段

一旦接收到FIN段，用ACK回应

接收到FIN段，ACK可以和它自己发出的FIN段一起发送

对称释放，并不完美，存在两军问题

拥塞控制原理

网络中top 10的问题

拥塞控制指防止过多的数据注入网络，保证网络中的路由器或链路不至于过载

端到端的拥塞控制：

端系统根据延迟和丢失事件来推断网络中拥塞情况
如何检测：
- 超时：拥塞
  - 网络拥塞
  - 分组在传输时收到干扰，因出错而被抛弃
- 三次冗余ACK：轻微拥塞
  - 还没超时，收到三个冗余ACK
控制策略：
- 超时或者冗余ACK，CongWIn下降
- 否则，CongWin尝试上升
- 同时考虑拥塞控制和流量控制（对方缓冲区的空闲大小）
TCP慢启动：
当收到三个冗余ACK（快恢复，因为减少了慢启动过程）：
- CongWin减为一半
- 再线性增加
超时：
- ComgWin被设置成1，阈值减小为当前拥塞窗口的一半（但是不能小于2）
- 进入慢启动阶段（指数增加）
- 直到阈值（上次的一半）之后再线性增加（即拥塞避免算法）

网络辅助拥塞控制：

路由器提供给段系统反馈信息
- 单个bit位，显示是否拥塞
- 显示提供发送端可以发送的速率

TCP公平性

如果 K个TCP会话分享一个链路带宽为R的瓶颈，每一个会话的有效带宽为 R/K

# 网络层：数据平面

导论

网络层功能：

转发：将分组从路由器的输入接口转发到合适的输出接口
路由：使用路由算法来决定分组从发送主机到目标接收主机的路径

数据平面：

决定数据报如何从路由器输入端口转发到输出端口
本地，每个路由器的功能
转发功能：
- 传统：基于目标地址和转发表（基于目标的转发）
- SDN方式：基于多个字段+流表（通用转发）

控制平面：

决定了数据报如何在路由器之间路由，决定了数据报从源主机到目标主机的端到端路径
网络范围的逻辑

网络服务模型：

路由器的组成

结构：

注意每个输入端口也是输出端口（双向）。

输入端口：

交换结构

通过内存交换
- 第一代路由器
- 在CPU直接控制下的交换，采用传统的计算机
- 分组被拷贝到系统内存，CPU从分组的头部提取出目标地址，查找转发表，找到对应的输出端口，拷贝到输出端口
- 转发速率被内存的带宽限制 (数据报通过BUS两遍)
- 一次只能转发一个分组
通过总线交换
- 总线竞争：交换速度受限于总线带宽（一次bus）
- 一次只转发一个分组
通过crossbar的交换
- 支持同时转发多个分组

输出端口

调度机制

FIFO
优先级调度
RR：
- 循环扫描不同类型的队列, 发送完一类的一个分组，再发送下一个类的一个分组，循环所有类
WFQ（加权优先级队列）：
丢弃规则：
- 丢弃刚到的分组
- 丢弃优先级低的分组
- 随机丢弃

IP协议

IP数据报格式

ipv

IP分片和重组

把一个大的数据报变成若干小的数据报

传输到对方时，根据identifier 和offset重组，flag中有一位表示后面是否还有分组

IP地址

32地址，对主机或者路由器接口编址

子网：

IP地址：
- 子网部分：高位地址
- 主机部分：低位地址
一个子网内的节点，它们的ip地址的子网部分相同，不需要借助路由器就可以在物理上相互达到（一跳可达）

ip地址分类

一些特定的ip地址：

CIDR

无类域间路由：

子网部分可以是任意部分
地址格式：a.b.c.d/x其中x代表子网部分的长度
子网掩码：

注意：只有最后一个路由器才需要主机部分ip地址

IPv6

解决“IP地址耗尽”的问题有以下三种措施：

采用无类别编址CIDR，使IP地址的分配更加合理
采用网络地址转换（NAT）的方式以节约IP地址
采用更大地址空间的新版本的IPv6

IPv6：地址128bit，首部没有校验和字段，传输路径中的路由器不允许分片

40 字节头部：

从IPv4到IPv6的平移：

隧道：在IPv4路由器之间传输的IPv4数据报携带了IPv6数据报

DHCP

主机如何获取IP地址：

系统管理员将地址配置在一个文件中
主机广播DHCP discover 报文
DHCP 服务器用 “DHCP offer”提供报文响应
主机请求IP地址：发送 “DHCP request” 报文
DHCP服务器发送地址：“DHCP ack” 报文

不仅返回地址：

IP地址
第一跳的路由器（默认网关）
DNS服务器的域名和IP地址
子网掩码

如何获得一个网络的子网部分：

从ISP获得

NAT（网络地址转换）

本地网络只需要一个IP地址：

不需要从ISP分配一块地址，可用一个IP地址用于所有的（局域网）设备-（省钱）
可以在局域网改变设备的地址情况下而无须通知外界
可以改变ISP而无需改变局域网内部设备地址
内部的设备没有明确的地址，对外不可见-安全

通用转发和SDN

传统方式实现网络功能的问题：

垂直集成，价格昂贵，不利于创新生态
分布式实现，功能固化 -> 网络设备繁多

SDN

数据平面和转发平面分离：

数据平面：分组交换机
控制平面：控制器+网络应用

一个远程控制器和CA交互，控制器决定分组转发的逻辑（可编程），CA所在设备执行逻辑

优势：

水平集成控制平面开放实现，创造出良好的产业生态，促进发展
集中式实现控制逻辑，便于网络管理
基于流表的匹配+动作的工作方式，允许可编程的分组交换机

网络层：控制层面

自治系统：单一技术管理下的一组路由器，这些路由器使用一种AS内部的路由选择协议和共同的度量来确定分组在该AS内的路由，同时还使用一种AS之间的路由选择协议来确定分组在AS之间的路由

路由算法

Link State

各点通过各种渠道获得整个网络拓扑，网络中所有链路代价等信息
使用LS算法，得到汇集树（dijkstra算法），得到路由表
按此路由表转发分组

LS工作过程：

可能造成路径震荡的情况

距离矢量

具体例子：

每个节点更新的情况：

距离矢量的特点：

好消息传得快，坏消息传得慢（无穷计算问题）
解决办法：水平分裂（即毒性逆转），能够改进坏消息传递慢，但是也无法杜绝无穷计算

两种算法的比较

协议

RIP

基于距离矢量协议，最大的有点就是简单

代价为跳数
每隔30s，和邻居交换DV
每一个通告报文最多25个目标子网

优点：简答，开销小，收敛速度快

缺点：

RIP限制了它的网络规模，它能使用的最大距离为15
路由器之间交换的是完整路由表，因此网络规模越大，开销也越大
网络出现故障时出现慢收敛现象（即需要较大时间才能将此消息传送到所有路由），俗称“坏消息传得慢”

RIP是应用层协议，它使用UDP（端口520）传送数据，RIP选择的路径不一定是时间最短的，但一定是具有最少路由器的路径。

OSPF

OSPF的基本特点：

OSPF使用洪泛法向本自治系统中所有路由器发送信息，而RIP只向相邻的路由器发送信息
发送的信息是与本路由器相邻的所有路由器的链路状态，但这只是路由器知道的部分信息。”链路状态“是指本路由器和哪些路由器相邻以及这些链路的”度量/代价“。而RIP发送的信息是本路由器知道的全部信息，即整个路由表
只有当链路状态发生改变时，路由器才使用洪泛法向所有路由器发送此信息。并且更新过程收敛得快，不会出现RIP”坏消息传得慢“得问题。而且不管网络拓扑是否发生变化，RIP都会定期向相邻路由器交换路由表得信息。
OSPF为网络层协议，它不使用UDP或TCP而直接使用IP数据报传送（其IP数据报首部得协议字段为89），而RIP使用应用层协议，使用UDP
OSPF对不同得链路可根据IP分组得不同服务类型而设置成不同的代价。
如果到同一目的地址有多条相同代价的路径，那么可以将通信量分配给这几条路径。这称为多路径间的负载平衡
所有在OSPF路由器之间的交换的分组都具有鉴别功能，因而保证了仅在可信赖的路由器之间交换链路状态
支持可变长度的子网划分和无分类编址CIDR。RIP不支持，RIP2支持
每个链路状态都带上一个32位的序号，序号越大，状态就越新

基于链路状态算法：