第一章 计算机网络和因特网
线路交换（Circuit switching）中的时分复用（Time Division Multiplexing (TDM)）与频分复用（Frequency Division Multiplexing (FDM)）
首先通过信令系统，在网络核心中为两者之间的通信分配一条独享的线路。由于两个交换节点之间的链路带宽较大，可以采用时分多路复用、频分多路复用、码分多路复用（多用于接入网）、波分多路复用（多用于光纤（光通信））等多种方法分解成小片(pieces)，从而实现同时为多个用户进行服务。
- 时分多路复用
- 时间被划分为周期性时隙；
- 每个呼叫分配的周期时隙，可以以（更宽）频带的最大速率传输，但只能在其时隙内传输；
- 频分多路复用
- 光、电磁频率被划分为（窄）频带；
- 每个呼叫分配自己的频带，可以以该窄带的最大速率传输；
五层结构和协议
Internet协议栈：应用层——传输层——网络层——链路层——物理层
- 应用层：网络应用
- 为人类用户或者其他应用进程提供网络应用服务
- 协议：FTP，SMTP，HTTP，DNS
- 传输层：主机之间的数据传输
- 在网络层提供的端到端通信基础上，细分为进程到进程；TCP将IP提供的不可靠的通信变成可靠地通信
- 协议：TCP，UDP
- 网络层：为数据报从源到目的选择路由
- 主机主机之间的通信，端到端通信，不可靠
- 协议：IP，ICMP，ARP
- 链路层：相邻网络节点间的数据传输（从比特流确定一帧的开始和结束，以帧为单位进行传输）
- 相邻两点的通信，点到点通信，可靠或不可靠
- 协议：点对点PPP，802.11(wifi)，Ethernet
- 物理层：在线路上传送bit
各层次的协议数据单元(PDU)
- 应用层：报文(message)
- 传输层：报文段(segment)：TCP段，UDP数据报
- 网络层：分组(packet)（如果无连接方式：数据报datagram）
- 数据链路层：帧(frame)
- 物理层：位(bit)
第二章 应用层
C/S架构与P2P架构
- 客户-服务器模式（C/S:client/server）
- 服务器:
- 一直运行
- 固定的IP地址和周知的端口号（约定）
- 扩展性：服务器场
- 数据中心进行扩展
- 扩展性差
- 客户端:
- 主动与服务器通信
- 与互联网有间歇性的连接
- 可能是动态IP地址
- 不直接与其它客户端通信
- 服务器:
- 对等模式(P2P:Peer To Peer)
- （几乎）没有一直运行的服务器
- 任意端系统之间可以进行通信
- 每一个节点既是客户端又是服务器
- 自拓展性（self-scalability）：新peer节点带来新的服务能力，当然也带来新的服务请求
- 参与的主机间歇性连接且可以改变IP地址
- 难以管理
- 例子: Gnutella，迅雷
进程寻址（Addressing processes）
- 进程为了接收报文，必须有一个标识，即：SAP（发送也需要标示）
- 主机：唯一的 32位IP地址
- 仅仅有IP地址不能够唯一标示一个进程；在一台端系统上有很多应用进程在运行
- 所采用的传输层协议：TCP or UDP
- 端口号（Port Numbers）
- 主机：唯一的 32位IP地址
- 一些知名端口号的例子：
- HTTP: TCP 80
- Mail: TCP 25
- Ftp: TCP 22
- 一个进程：用 IP + port 标示端节点
- 本质上，一对主机进程之间的通信由2个端节点构成
TCP/UDP提供的服务
- TCP服务：
- TCP socket：
- TCP服务，两个进程之间的通信需要之前要建立连接
- 两个进程通信会持续一段时间，通信关系稳定
- 可以用一个整数表示两个应用实体之间的通信关系，本地标示
- 穿过层间接口的信息量最小
- TCP socket：源IP，源端口，目标IP，目标端口
- TCP服务，两个进程之间的通信需要之前要建立连接
- 对于使用面向连接服务（TCP）的应用而言，套接字是4元组的一个具有本地意义的标示
- 4元组：（源IP，源port，目标IP，目标port）
- 唯一的指定了一个会话（2个进程之间的会话关系）
- 应用使用这个标识，与远程的应用进程通信
- 不必在每一个报文的发送都要指定这4元组
- 就像使用操作系统打开一个文件，OS返回一个文件句柄一样，以后使用这个文件句柄，而不是使用这个文件的目录名、文件名
- 简单，便于管理
- TCP socket：
- UDP服务：
- UDP socket：
- UDP服务，两个进程之间的通信需要之前无需建立连接
- 每个报文都是独立传输的
- 前后报文可能给不同的分布式进程
- 因此，只能用一个整数表示本应用实体的标示
- 因为这个报文可能传给另外一个分布式进程
- 穿过层间接口的信息大小最小
- UDP socket：本IP，本端口
- 但是传输报文时：必须要提供对方IP，port
- 接收报文时：传输层需要上传对方的IP，port
- UDP服务，两个进程之间的通信需要之前无需建立连接
- 对于使用无连接服务（UDP）的应用而言，套接字是2元组的一个具有本地意义的标示
- 2元组：IP，port（源端指定）
- UDP套接字指定了应用所在的一个端节点（endpoint）
- 在发送数据报时，采用创建好的本地套接字（标示ID），就不必在发送每个报文中指明自己所采用的ip和port
- 但是在发送报文时，必须要指定对方的ip和udp port(另外一个段节点)
- UDP socket：
WEB应用
- WEB应用通过URL对每个对象进行引用
- 访问协议，用户名，口令字，端口，目录文件等；
- URL格式：
Prot://user:[email protected]:port/someDept/pic.gif- （
协议名://用户:口令@主机名:端口号/路径/文件名）
- 常见WEB应用：
- 电子邮件
- 目录服务
- 流式视频
- P2P
HTTP概况
- HTTP:超文本传输协议
- Web的应用层协议
- C/S模式
- 客户：请求、接收和显示Web对象的浏览器
- 服务器：对请求进行响应，发送对象的Web服务器
- HTTP 1.0: RFC 1945
- HTTP 1.1: RFC 2068
- 使用TCP:
- 客户发起一个与服务器的TCP连接 (建立套接字)，端口号为 80
- 服务器接受客户的TCP连接
- 在浏览器(HTTP客户端) 与 Web服务器(HTTP服务器 server) 交换 HTTP报文 (应用层协议报文)
- TCP连接关闭
- HTTP是无状态的
- 服务器并不维护关于客户的任何信息（因此需要Cookie）
HTTP两种连接
- 非持久HTTP
- 最多只有一个对象在TCP连接上发送
- 下载多个对象需要多个TCP连接
- HTTP/1.0使用非持久连接
- 持久HTTP
- 多个对象可以在一个（在客户端和服务器之间的）TCP连接上传输
- HTTP/1.1默认使用持久连接
HTTP请求报文与响应报文的格式
- HTTP请求报文：
01 GET /somedir/page.html HTTP/1.1 请求行(GET, POST, HEAD等命令)
02 Host: www.someschool.edu
03 User-agent: Mozilla/4.0 中间四行
04 Connection: close 为首部行
05 Accept-language:fr
06 换行回车符，表示报文结束
通用格式如下：
01 Method Url Version（换行）
02 Header field name:Value（换行）
...
0n （换行）
- HTTP响应报文：
01 HTTP/1.1 200 OK\r\n 状态行 (协议版本、状态
02 Connection close\r\n 码和相应状态信息)
03 Date: Thu, 06 Aug 1998 12:00:15 GMT\r\n
04 Server: Apache/1.3.0 (Unix) \r\n
05 Last-Modified: Mon, 22 Jun 1998 …... \r\n 02~07首部行
06 Content-Length: 6821\r\n
07 Content-Type: text/html\r\n \r\n
08 \r\n 09~10两个空行后为数据
09 \r\n
10 data data data data data ... 数据，如请求的HTML件
SMTP
- 用户代理
- 又名 “邮件阅读器”
- 撰写、编辑和阅读邮件
- 如Outlook、Foxmail
- 输出和输入邮件保存在服务器上
- 邮件服务器
- 邮箱中管理和维护发送给用户的邮件
- 输出报文队列保持待发送邮件报文
- 邮件服务器之间的SMTP协议：发送email报文
- 客户：发送方邮件服务器
- 服务器：接收端邮件服务器
- 简单邮件传输协议：SMTP
- 使用TCP在客户端和服务器之间传送报文，端口号为25
- 直接传输：从发送方服务器到接收方服务器
- 传输的3个阶段
- 握手
- 传输报文
- 关闭
- 命令/响应交互
- 命令：ASCII文本
- 响应：状态码和状态信息
- 报文必须为7位ASCII码
DNS基本功能
- 实现主机名-IP地址的转换(name/IP translate)
- 其它目的
- 主机别名到规范名字的转换：Host aliasing
- 邮件服务器别名到邮件服务器的正规名字的转换：Mail server aliasing
- 负载均衡（Load Distribution）：繁忙的站点被冗余分布在多台服务器上，每台服务器运行在不同的端系统上，每个都有着不同的IP地址。由于这些冗余的Web服务器，一个IP地址集合与一个规范主机名相联系。当客户对映射到某处到某地址集合的名字发出一个DNS请求时，该服务器用IP地址的整个集合进行响应，但在每个回答中循环这些地址次序。因为客户通常总是向IP地址排在最前面的服务器发送HTTP请求报文，所以DNS就在所有这些冗余的Web服务器之间循环分配了负载；
DNS概述
- 集中式设计的问题包括：
- 单点故障（a single point of failure）；
- 通信容量（traffic volume）；
- 远距离的集中式数据库（distant centralized database）；
- 维护（maintenance）；
- 因此采取分层的、基于域的命名机制
- 根DNS服务器（root DNS servers）；
- 顶级域服务器（Top-Level Domain DNS servers）；
- 权威DNS服务器（authoritative DNS servers）；
- 本地服务器（local DNS servers）：实际上不属于该服务器的层次结构，但它对DNS层次结构是至关重要的；
- 若干分布式的数据库完成名字到IP地址的转换
- 运行在UDP之上端口号为53的应用服务
- 核心的Internet功能，但以应用层协议实现
- 在网络边缘处理复杂性
第三章 传输层
运输层的功能
运输层协议为运行在不同的主机上的应用进程之间提供了逻辑通信（logic communication） 功能；从应用程序的角度看，通过逻辑通信，运行不同进程的主机好像直接相连一样。逻辑通信的概念如下：
- 传输层服务：（即进程间的逻辑通信）
- 依赖于网络层的服务
- 延时、带宽
- 并对网络层的服务进行增强
- 数据丢失、顺序混乱、加密
- 依赖于网络层的服务
UDP
- “no frills,”“bare bones”Internet传输协议
- “尽力而为”的服务，报文段可能
- 丢失
- 送到应用进程的报文段乱序
- 无连接：
- UDP发送端和接收端之间没有握手
- 每个UDP报文段都被独立地处理
- UDP被用于:
- 流媒体（丢失不敏感，速率敏感、应用可控制传输速率）
- DNS
- SNMP
- 在UDP上可行可靠传输:
- 在应用层增加可靠性
- 应用特定的差错恢复
TCP
- 点对点：
- 一个发送方，一个接收方
- 可靠的、按顺序的字节流：
- 没有报文边界
- 管道化（流水线）：
- TCP拥塞控制和流量控制设置窗口大小
- 发送和接收缓存
- 全双工数据：
- 在同一连接中数据流双向流动
- MSS：最大报文段大小
- 面向连接：
- 在数据交换之前，通过握手（交换控制报文） 初始化发送方、接收方的状态变量
- 有流量控制：
- 发送方不会淹没接收方
TCP：序号和确认号
- 序号（Sequence number）32bits：
- 报文段首字节的在字节流的编号
- 确认号（Acknowledgement number）32bits:
- 期望从另一方收到的下一个字节的序号
- 累积确认
- Q：接收方如何处理乱序的报文段
- A：没有规定
TCP：数据传输
- 从应用层接收数据：
- 用nextseq创建报文段
- 序号nextseq为报文段首字节的字节流编号
- 如果还没有运行，启动定时器
- 定时器与最早未确认的报文段关联
- 过期间隔：
- TimeOutInterval
- 超时：
- 重传后沿最老的报文段
- 重新启动定时器
- 收到确认：
- 如果是对尚未确认的报文段确认
- 更新已被确认的报文序号
- 如果当前还有未被确认的报文段，重新启动定时器
- 如果是对尚未确认的报文段确认
- TCP在IP不可靠服务的基础上建立了rdt
- 管道化的报文段
- GBN or SR
- 累积确认（像GBN）
- 单个重传定时器（像GBN）
- 是否可以接受乱序的，没有规范
- 管道化的报文段
- 通过以下事件触发重传
- 超时（只重发那个最早的未确认段：SR）
- 重复的确认
- 例子：收到了ACK50,之后又收到3个ACK50
- 超时周期往往太长：
- 在重传丢失报文段之前的延时太长
- 通过重复的ACK来检测报文段丢失
- 发送方通常连续发送大量报文段
- 如果报文段丢失，通常会引起多个重复的ACK
- 如果发送方收到同一数据的3个冗余ACK，重传最小序号的段：
- 快速重传：在定时器过时之前重发报文段
- 它假设跟在被确认的数据后面的数据丢失了
- 第一个ACK是正常的；
- 收到第二个该段的ACK，表示接收方收到一个该段后的乱序段；
- 收到第3，4个该段的ack，表示接收方收到该段之后的2个，3个乱序段，可能性非常大段丢失了
TCP：流量控制
TCP通过让发送方维护一个称为接收窗口（receive window） 的变量来提供流量控制。通俗的说，接收窗口用于给发送方一个指示——该接收方还有多少可用的缓存空间。因为TCP是全双工通信，在连接两端的发送方都各自维护一个接收窗口。
- 接收方在其向发送方的TCP段头部的rwnd字段“通告”其空闲buffer大小
- RcvBuffer大小通过socket选项设置 (典型默认大小为4096 字节)
- 很多操作系统自动调整RcvBuffer
- 发送方限制未确认(“inflight”)字节的个数≤接收方发送过来的rwnd值
- 保证接收方不会被淹没
TCP：三次握手、四次挥手
- 本质：
- 双方知道要和对方通信
- 为这次通信建立好缓冲区，准备好资源
- 一些控制变量需要做置位，两者需要互相告知自己的初始序号，初始化的RcvBuffer
- 3次握手（变化的初始序号+双方确认对方的序号）
- 第一次：client–>server：客户端一方的初始序号 x x x
- 第二次：server–>client：发送确认 A C K n u m = x + 1 ACKnum=x+1 ACKnum=x+1 和服务器一方的初始序号 y y y （捎带）
- 第三次：client–>server：发送确认 A C K n u m = y + 1 ACKnum=y+1 ACKnum=y+1 和客户端data（捎带）
- 也即
- Send：SYN=1，seq=client_isn
- Receive：SYN=1，seq=server_isn，ack=client_isn+1
- Send：SYN=0，seq=client_isn，ack=server_isn+1
- 4次挥手
- 客户端，服务器分别关闭它自己这一侧的连接
- 发送FIN bit = 1的TCP段
- 一旦接收到FIN，用ACK回应
- 接到FIN段，ACK可以和它自己发出的FIN段一起发送
- 可以处理同时的FIN交换
- “对称释放，并不完美”
- 客户端，服务器分别关闭它自己这一侧的连接
- 为什么连接的时候是三次握手，关闭的时候却是四次握手？
- 答：因为当S收到C的SYN连接请求报文后，可以直接发送SYN+ACK报文。其中ACK报文是用来应答的，SYN报文是用来同步的。关闭连接时，当S收到FIN报文时，很可能并不会立即关闭SOCKET，所以只能先回复一个ACK报文，告诉C，“你发的FIN报文我收到了”。只有S所有的报文都发送完了，我才能发送FIN报文，因此不能一起发送。故需要四步握手。
TCP：拥塞控制
- 拥塞原因（The Causes and the Costs of Congestion）：
- 当分组的到达速率接近链路容量时，分组经历巨大的排队时延；
- 发送方在遇到大时延时所进行的不必要重传会引起路由器利用其链路带宽来转发不必要的分组副本；
- 当一个分组沿一条路径被丢弃时，每个上游路由器用于转发该分组到丢弃该分组而使用的传输容量最终被浪费掉；
- 拥塞控制方法（Approaches to Congestion Control）：
- 端到端拥塞控制（End-to-end congestion control）：在端到端拥塞控制方法中，网络层没有为运输层拥塞控制显示支持。即使网络中存在拥塞，端系统也必须通过对网络行为的观察来判断；
- 网络辅助的拥塞控制（Network-assisted congestion control）：网络辅助的拥塞控制中，路由器向发送方提供关于网络中拥塞状态的显示反馈信息；
- TCP拥塞控制（TCP Congestion Control）：
运行在发送方的TCP拥塞控制机制跟踪一个额外的变量，即拥塞窗口（congestion window）。拥塞窗口表示为cwnd，它对一个TCP发送方能向网络中发送流量的速率进行限制。发送方中未被确认的数据量不会超过cwnd和rwnd中的最小值，即： L a s t B y t e S e n t − L a s t B y t e A C K ≤ min { c w n d , r w n d } LastByteSent-LastByteACK\le \min\{cwnd,rwnd\} LastByteSent−LastByteACK≤min{cwnd,rwnd}
因为TCP使用确认来触发（或计时）增大它的拥塞窗口长度，TCP被说成是自计时（self-clocking）的。TCP基于本地信息设置它们的发送速率的指导性原则：- 一个丢失的报文段表意味着拥塞，因此当丢失报文段时应当降低TCP发送方的速率；
- 一个确认报文段指示该网络正在向接收方交付发送方的报文段，因此，当对先前未确认报文段的确认到达时，能够增加发送方的速率；
- 带宽探测；
- TCP拥塞控制算法（TCP congestion control algorithm）
- 该算法主要包括3个部分：慢启动（slow-start）、拥塞避免（congestion avoidance）、快速恢复（fast recovery）：
- 在慢启动（slow-start）状态，cwnd的值以1个MSS开始并且每当传输的报文段首次被确认就增加1个MSS。TCP发送速率起始很慢，但在慢启动阶段以指数增长。
- 如果存在一个由超时指示的丢包事件，TCP发送方将cwnd设置为1并重新开始慢启动过程。它还将第二状态变量ssthresh（慢启动阈值）设置为cwnd/2
- 一旦进入拥塞避免状态，cwnd的值大约是上次遇到拥塞时的值的一半，即距离拥塞可能并不遥远
- 在任意状态冗余ACK达到3个就会进入快速恢复状态的缺失报文段。因此，TCP拥塞控制常常被称为加性增、乘性减（Additive-Increase，Multiplicative-Decrease，AIMD） 拥塞控制方式。
- 该算法主要包括3个部分：慢启动（slow-start）、拥塞避免（congestion avoidance）、快速恢复（fast recovery）：
流量控制和拥塞控制的区别
- 流量控制：
- 流量控制的目的是防止发送方发送数据的速率超过接收方的处理能力。其关键机制是滑动窗口协议，特别是TCP中的接收窗口（Receiver Window）机制。
- 接收窗口：接收方会在每个TCP报文段中通告一个窗口大小（window size），表示它当前可以接收的最大数据量。发送方根据这个窗口大小来调整发送速率，以确保不会超过接收方的处理能力。
- 实现机制：
- 滑动窗口：发送方维护一个发送窗口，只有在接收到接收方的确认（ACK）并通告新的窗口大小后，发送方才能继续发送新的数据。
- 零窗口通告：如果接收方的接收缓冲区已满，它会通告一个零窗口，通知发送方暂停发送数据，直到缓冲区有足够的空间。
- 拥塞控制（Congestion Control）
- 拥塞控制的目的是防止网络中出现拥塞，从而保证网络的稳定性和公平性。它通过调节发送方的发送速率来避免在网络中出现过多的数据包积压。
- 慢启动（Slow Start）：在连接开始时，发送方会逐渐增加发送窗口的大小，直到检测到网络中可能出现拥塞的信号（如包丢失）。
- 拥塞避免（Congestion Avoidance）：当发送窗口达到慢启动阈值（ssthresh）后，进入拥塞避免阶段，发送窗口增长速度变慢，以避免引起网络拥塞。
- 快速重传（Fast Retransmit）和快速恢复（Fast Recovery）：在检测到丢包（通过重复ACK或超时）后，发送方会迅速重传丢失的数据包，并通过减少拥塞窗口（cwnd）来降低发送速率，然后缓慢恢复，以防止再次发生拥塞。
- 拥塞窗口（Congestion Window，cwnd）：这是一个动态调整的窗口，用于控制发送方的发送速率，根据网络拥塞状况进行增减。
- 区别
- 目标：流量控制是为了避免发送方超载接收方，拥塞控制是为了避免网络拥塞。
- 机制：流量控制通过接收窗口大小调节发送速率，拥塞控制通过拥塞窗口大小调节发送速率。
- 触发条件：流量控制基于接收方的能力，拥塞控制基于网络状况。
第四章 网络层-数据平面
转发与路由选择
- 基本概念：
- 输入端口（input port）：
- 在路由器中终结进入物理链路的物理层；
- 与位于入链路远端的数据链路层交互；
- 查找转发表决定路由器的输出端口；
- 控制分组从输入端口转发到路由选择处理器；
- 输出端口（output port）：
- 存储从交换结构接收的分组；
- 执行必要的链路层和物理层功能在输出链路上传输这些分组；
- 交换结构（switch fabric）：
- 将路由器的输入端口；连接到它的输出端口；
- 路由选择处理器（routing process）：
- 执行控制平面功能；
- 传统路由器中，执行路由选择协议，维护路由选择表与关联链路状态信息，并由该路由器计算转发表；
- SDN路由器中，负责与远程控制器通信；
- 执行网络管理功能；
- 输入端口（input port）：
- 转发与路由选择：
- 转发（forwarding）——数据平面：将分组从一个输入链路接口转移到适当的输出链路接口的路由器的本地动作（主要利用硬件）；
- 每台网络路由器中有一个关键元素是它的转发表（forwarding table）。路由器检查到达分组首部的一个或多个字段值，进而使用这些首部值在其转发表中索引，通过这种方法来转发分组。
- 路由选择（routing）——控制平面：确定分组从源到目的地所采取的端到端路径的网络范围处理过程（主要利用软件）
- 传统方法是由路由器器中的路由选择算法决定转发表中的值。
- 软件定义网络（Software-Defined Networking，SDN）方法是从路由器物理上分离的另一种方法，远程控制器计算和分发转发表以供每台路由器所使用。
- 转发（forwarding）——数据平面：将分组从一个输入链路接口转移到适当的输出链路接口的路由器的本地动作（主要利用硬件）；
IP报的格式
至少5行&32列
第一行：
1~4bit：版本号（4bit）
5~8bit：首部长度（4bit）
9~16bit：服务类型（8bit）
17~32bit：数据报长度（16bit）
第二行：
1~16bit：标识（16bit）
17~19bit：标志（3bit）
21~32bit：片漂移（13bit）
第三行：
1~8bit：寿命（8bit）
9~16bit：上层协议（8bit）
17~32bit：首部检验和（16bit）
第四行：
1~32bit：源IP地址（32bit）
第五行：
1~32bit：目的IP地址（32bit）
第六行（可选）：
1~32bit：选项（32bit）
第七行及其余行（可选）：
1~nbit：数据（nbit）
- 版本号（Version）：规定了数据报的IP协议版本；
- 首部长度（Header length）：在无选项（Options）首部时，IP具有==20字节==的首部；
- 服务类型（Type of service）：不同类型的数据报可以相互区分；
- 数据报长度（Datagram length）：IP数据报的总长度（首部加上数据），以字节计数；
- 标识（Identifier）、标志（Flags）、片漂移（Fragmentation offset）：用于IP分片；
- 寿命（Time-to-live，TTL）：确保数据段不会永远在网络中循环；
- 上层协议（Upper-layer protocol）：指示IP数据报应交付给哪个运输层协议；
- 首部检验和（Header checksum）：帮助路由器检测收到的IP数据报中的比特错误；
- 源和目的IP地址（Source and Destination IP address）；
- 选项（Options）：允许IP首部被扩展；
- 数据（Data）：一般为运输层报文段；
IP：数据报分片
- 一个链路层帧能承载的最大数据量叫作最大传送单元（Maximum Transmission Unit，MTU）。
组装，字段怎么变化
IP：编址
- 主机与物理链路之间的边界叫做接口（interface）。每个IP地址长度为32比特（4字节），因此总共有
2
32
2^{32}
232个可能的IP地址。这些地址通常按所谓点分十进制记法（dotted-decimal notation） 书写，及地址中的每个字节用它的十进制形式书写，各字节以句点隔开。地址
192.32.216.9的二进制记法是：11000001 00100000 11011000 00001001。 - 因特网的地址分配策略被称为无类别域间路由选择（Classless Interdomain Routing，CIDR）。当使用子网寻址时，32比特的IP地址被划分为两部分，并且也具有点分十进制形式
a.b.c.d/x，其中x指示了地址的第一部分中的比特数，并且该部分经常被称为该地址的前缀（prefix）（或网络前缀）。
IP：子网的确定与子网掩码
- 用IP的术语说，连接到中心路由器的网络都算作一个子网（subnet）。IP编址为这个子网分配一个地址
233.1.1.0/24，其中/24称为子网掩码（network mask），指示该子网IP32bit中的左侧24bit定义子网地址。 - 便于理解，可以将网络地址（子网地址）想象为街道名，主机地址想象为门牌号；子网掩码用于确定该IP地址街道与门牌号的分界线。
DHCP
DHCP协议是一个4个步骤过程，yiaddr指示分配给该新到达用户的地址
- (非必要步骤) 发现 DHCP 服务器: 在
UDP分组中向67端口发送DHCP 发现报文（DHCP discover message）;- DHCP 发现报文使用广播目的地址
255.255.255.255:67, 使用 “本主机” 源 IP 地址0.0.0.0:68;- 使用广播地址是因为客户不知道 DHCP 服务器地址;
- 该报文将会通过链路层广播, 达到该子网所连接的所有节点;
- DHCP 发现报文使用广播目的地址
- (非必要步骤) DHCP 服务器提供服务: DHCP 收到 DHCP 发现报文时, 用 DHCP 提供报文（DHCP offer message） 响应;
- DHCP 提供报文可能使用广播目的地址
255.255.255.255:68(一般情况下);- 广播和单播的选择与客户端的标志位设置有关, 具体不明 (待补充);
- DHCP 提供报文中包括以下内容:
- 分配给客户的 IP 地址;
- 默认网关 (第一跳路由器) 的 IP 地址;
- DNS 服务器的域名和 IP 地址;
- 子网掩码;
- IP 地址租用期 (address lease time): 用来指示分配的 IP 地址的有效期;
- DHCP 提供报文可能使用广播目的地址
- (必要步骤) DHCP 请求: 从收到的 DHCP 提供报文中选择一个, 并发出 （DHCP 请求报文 (DHCP request message） 进行相应, 回显配置的参数;
- (必要步骤) DHCP ACK: 当 DHCP 服务器收到 DHCP 请求报文时, 使用 （DHCP ACK） 响应该请求报文, 证实所请求的参数;
- 收到 DHCP ACK 后, 客户即可在租期内使用分配到的 IP 地址了;
网络地址转换（Network Address Translation (NAT)）
就外界而言，本地网络中的所有设备只共享一个IPv4地址。
- 通过 NAT 转换表 (NAT translation table) 区分分组
| WAN 端 | LAN 端 |
|---|---|
| 广域网一侧接口的 IP 地址 : 一个任意的源端口号 | 内网中的 IP 地址 : 该主机中初始的端口号 |
- 发送时, WAN 端将内网中的专用地址, 换为自己的在外网中的 IP 地址, 同时使用一个在 NAT 转换表中尚未使用过的端口号, 替换源主机中发送进程对应的端口号;
- 端口号 16 bit, 因此可以维护 6 万多个并行的单 IP 地址连接;
- 接收时, 反过来执行替换操作, 将分组转发给具有内网中的专用地址的主机, 进而达到对应原始的端口号的进程;
IPV6
- 相比 IPv4 的变化
- 中间路由器不允许分片、重组, 只在源、目的地执行;
- 如果数据报太大, 导致路由器无法转发, 路由器将丢掉该分组, 然后发送“分组太大”的 ICMP 差错报文
- 固定的 40 bytes 基本首部;
- 首部中去除了检验和: IPv4 每次路由首部字段的 TTL 等都会发生变化, 导致需要重新计算检验和, 这是一件十分耗时的操作;
- 中间路由器不允许分片、重组, 只在源、目的地执行;
第五章 网络层控制平面
路由选择算法（Routing Algorithms）
- 集中式路由选择算法（centralized routing algorithm）：
- 用完整、全局性的网络知识计算出从源到目的地之间的最低开销路径。具有全局状态信息的算法常被称作链路状态（Link State，LS）算法，因为该算法必须知道网络中每条链路的开销。
- 在实践中，这经常由链路状态广播（link state broadcast）算法完成。下面给出的链路状态路由选择算法叫做
Dijkstra算法，其计算从某节点（源节点u）到网络中所有其他节点的最低开销路径。 - 基本思想：经算法的第k次迭代后，可知道到k个目的节点的最低开销路径，在到所有目的节点的最低开销路径之中，这k条路径具有k个最低开销。
- 我们定义如下符号：
D(v)：到算法的本次迭代，从源节点到目的节点v的最低开销；p(v)：从源到v沿着当前最小开销路径的前一个节点（v的邻居）；N'：节点子集；如果从源到v的最低开销路径已经确定，v在N'中；
- 路线上的流量变化和拥塞会使LS算法产生路由震荡（Routing Oscillations）。
- 源节点u的链路状态（LS）算法如下：
Initialization:
N'={u}
for all nodes v
if v is a neighbor of u
then D(v)=c(uv)
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(wv))
/* new cost to vis either old cost to vor knownleast path cost to wplus cost from wto v*/
until N'N
- 分散式路由选择算法（decentralized routing algorithm）：
- 路由器以迭代、分布式计算的方式计算出最低开销路径。没有节点拥有关于网络链路开销的完整信息。一个分散式路由选择算法为距离向量（Distance-Vector，DV）算法，每个节点维护到网络中所有其他节点的开销估计的向量。
- 距离向量（Distance-Vector，DV） 算法是一种迭代的（iterative）、异步的（asynchronous）、分布式的（distributed）和自我终止的（self-termination）算法。
- 令 d x ( y ) d_x(y) dx(y)是从节点x到节点y的最低开销路径。则该最低开销与著名的Bellman-Ford方程相关，即： d x ( y ) = min v { c ( x , v ) + d v ( y ) } d_x(y)=\min_v\{c(x,v)+d_v(y)\} dx(y)=minv{c(x,v)+dv(y)}
- 方程中的 min v \min_v minv是对于x的所有邻居的。
- 算法基本思想：每个节点x以 D x ( y ) D_x(y) Dx(y)开始，对在N中的所有节点y，估计从x到y的最低开销路径的开销路径。
- 距离向量算法具体过程如下：
Initialization:
for all destinations yin N:
D (y)= c(x,y) /* if y is not a neighbor then c(x,y)=∞*/
for each neighbor w
D (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 from some neighbor w)
for each y in N:
Dx(y)= minv{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
开放最短路优先（Open Shortest Path First(OSPF)）
- OSPF是一种链路状态协议，它使用洪泛链路状态信息和Dijkstra最低开销路径算法。使用OSPF，一台路由器构建了一幅关于整个自治系统的完整拓扑图。于是，每台路由器在本地运行Dijkstra的最短路径算法，以确定一个自身为根节点到所有子网的最短路径树。
- 使用OSPF时，路由器向自治系统内所有其他路由器广播路由选择信息，而不仅仅是向其相邻路由器广播。每当一条链路的状态发生变化时，路由器就会广播链路状态信息。
- OFPF的优点：
- 安全（Security）：能够鉴别OSPF路由器之间的交换；
- 多条相同开销的路径（Multiple same-cost paths）：允许使用多条路径；
- 对单播与多播路由选择的综合支持（Integrated support for unicast and multicast routing）；
- 支持在单个AS中的层次结构（Support for hierarchy within a single AS）；
ISP之间的路由选择：BGP
- 当分组跨越多个AS进行路由时，我们需要一个自治系统间路由协议（inter-autonomous system routing protocol）。在因特网中，所有的AS运行相同的AS间路由选择协议，称为边界网关协议（Broder Gateway Protocol，BGP）。
- BGP的作用：
- 在BGP中，分组并不是路由到一个特定的目的地址，相反是路由到CIDR化的前缀，其中每个前缀表示一个子网或者一个子网集合。
- BGP为每台服务器提供完成以下任务的手段：
- 从邻居AS获得前缀的可达性信息；
- 确定到该前缀的“最好”的路由；
- 通告BGP路由信息
- 对于每个AS，每台路由器要么是一台网关路由器（getaway router），要么是一台内部路由器（internal router）。在BGP中，每对路由器通过使用
179端口的半永久TCP连接交换路由选择信息。跨越两个AS的BGP连接称为外部BGP（eBGP） 连接，而在相同AS中的两台路由器之间的BGP会话称为内部BGP（iBGP） 连接。
- 对于每个AS，每台路由器要么是一台网关路由器（getaway router），要么是一台内部路由器（internal router）。在BGP中，每对路由器通过使用
- 确定最好的路由
- 通告前缀包括一些BGP属性（BGP attribute），前缀及其属性称为路由（route）。
ICMP（Internet Control Message Protocol）两种应用
因特网控制报文协议（the Internet Control Message Protocol，ICMP），被主机和路由器用来彼此沟通网络层的信息。ICMP最典型的用途是差错报告。最常见用于Ping与TTL查询：
| ICMP Type | Code | Descripion |
|---|---|---|
| 0 | 0 | echo reply (to ping) |
| 3 | 0 | destination network unreachable |
| 3 | 1 | destination host unreachable |
| 3 | 2 | destination protocol unreachable |
| 3 | 3 | destination port unreachable |
| 3 | 6 | destination network unknown |
| 3 | 7 | destination host unknown |
| 4 | 0 | source quench (congestion control) |
| 8 | 0 | echo request |
| 9 | 0 | router advertisement |
| 10 | 0 | router discovery |
| 11 | 0 | TTL expired |
| 12 | 0 | IP header bad |
第六章 链路层和局域网
链路层的功能
- 成帧 (framing)
- 几乎所有链路层协议都会将网络层数据报使用链路层帧封装起来;
- 链路接入
- 媒体访问控制 (Medium Access Control, MAC) 协议: 规定帧在链路上的传输规则;
- 可靠交付
- 保证无差错地经过链路层移动每个网络层数据报;
- 目的: 在差错发生的单个链路上纠错, 而不是在运输层/应用层协议被迫进行端到端的数据重传 (涉及很多链路);
- 该服务通常用于易产生差错的链路, 例如无线链路;
- 对于比特差错率低的链路, 链路层提供的可靠交付服务可能是不必要的, 于是很多链路层协议不提供此服务;
- 保证无差错地经过链路层移动每个网络层数据报;
- 差错检测和纠正
差错检测
- 差错检测
- 比特级差错检测和纠正 (bit-level error detection and correction): 对从一个节点发送到另一个物理上连接的邻近节点的链路层帧中的比特损伤进行检测和纠正;
- 差错检测和纠正比特 (Error Detection and Correction, EDC)
- 前向纠错 (Forward Error Correction, FEC): 在接收方检测和纠正差错的能力;
- 可以节省重传所需的往返时延, 适合实时网络应用和具有长传播时延的链路;
- 奇偶校验
- 单个奇偶校验位（parity bit）：发送d比特信息附加一个比特使d+1比特中1的总数是偶数（偶校验）或奇数（奇校验）
- 只能检测不能纠错，不能检测超过1比特位的错误；
- **二维奇偶校验（two-dimension parity）
- 能检测并纠正1bit差错；
- 单个奇偶校验位（parity bit）：发送d比特信息附加一个比特使d+1比特中1的总数是偶数（偶校验）或奇数（奇校验）
- 因特网检验和（Internet checksum）
- 基于这种方法，即数据的字节作为16比特的整数对待并求和。
- 循环冗余检测（Cyclic Redundancy Check(CRC)）
- 计算机网络中广泛应用的差错检测技术基于循环冗余检测（Cyclic Redundancy Check，CRC） 编码，也称为多项式编码（polynomial code）
R计算： R = r e m a i n d e r D ⋅ 2 r G R=remainder\frac{D\cdot2^r}{G} R=remainderGD⋅2r
媒体访问控制协议（MAC(Medium Access Control)）
- 概述
- 解决多路访问问题: 如何协调多个发送和接收节点对一个共享广播信道的访问;
- MAC 协议规范这些节点在同一个共享广播信道上的传输行为;
- MAC 协议的分类
- 信道划分协议
- 随机接入协议
- 轮流协议
- 碰撞问题 (collide)
- 当多个节点同时传输帧时, 所有节点同时接收到多个帧, 这些帧在所有的接收方处发生了 “碰撞”;
- 一般情况下, 碰撞帧的信号被纠缠在一起, 导致没有一个节点能够有效获得碰撞帧中的任何一个, 碰撞帧都丢失了;
- 需要使用 MAC 协议进行协调, 以解决碰撞问题带来的信道带宽浪费;
- 理想的 MAC 协议