计算机网络

第一章、概述

  1. 端系统通过通信链路和分组交换机连接在一起

  2. OSI

  3. 协议的基本要素：语法、语义和同步

    1. 语法：报文格式
    2. 语义：各字段的含义
    3. 同步：报文传输的先后顺序

  4. 最著名的分组交换机：

    • 路由器
    • 链路层交换机

  5. 端系统通过因特网服务提供商（Internet Server Provider,ISP）接入因特网，较低的ISP通过国家的国际的较高的ISP互联

  6. 网络边缘：

    • 通常把与因特网相连的计算机和其他设备称为端系统，因它们位于因特网边缘所以被称为端系统
    • 端系统也称为主机（host）
    • 主机可划分为：客户（client）和服务器（server）
    • 接入网：将端系统物理连接到其边缘路由器（edge router）的网络，边缘路由器是端系统到任何其他远程端系统的路径上的第一台路由器

  7. 网络核心：

    • 分组交换:

      1. **存储转发:**在交换机能够开始向输出链路传输该分组的第一个比特之前，必须接受到整个分组
      2. 特点：（1）报文分组，加首部（2）经路由器储存转发（3）在目的地合并

    • 电路交换：

      1. 频分复用（FDM）
      2. 时分复用(TDM)
      3. 特点：建立电路连接、通话、拆除连接

    • 排队时延和分组丢失（丢包）

    • ISP互联：

  8. 时延，丢包和吞吐量

    • **节点处理时延 $d_{proc}$**（P25）
    • 排队时延 $d_{queue}$
    • 传输时延 $d_{trans}$
    • 传播时延 $d_{prop}$
    • 传输时延是由路由器推出分组所需要的时间，与路由器距离无关；传播时延是一比特从一台路由器传播到另一台路由器所需要的时间，与分组长度或链路传输速率无关
    • 总时延：$d_{nodal}=d_{proc}+d_{queue}+d_{trans}+d_{prop}$

  9. 瞬时吞吐量是在任何时间主机接收到文件的速率

  10. 协议分层：各层的所有协议被称为协议栈

    • 应用层：是网络应用程序及它们的应用层协议存留的地方。包含HTTP,SMTP,FTP,DNS

    • 运输层：因特网的运输层在应用程序断电之间传送应用层报文，运输层的分组称为报文段（segment）

    • 网络层：负责将称为数据报（datagram）的网络层分组从一台主机移动到另一台主机。包含TCP,UDP，IP

    • 链路层：网络层将数据报下传给链路层，链路层沿着路径将数据报出传递给下一个节点。链路层分组称为帧（frame）

    • 物理层：物理层的任务是将该帧中的一个个比特从一个节点移动到下一个节点。该层中的协议是链路相关的并且进一步与该链路的实际传输媒体相关

  11. 增加控制信息:构造协议数据单元 (PDU)

  12. 控制信息主要包括:

  13. 地址（Address）: 标识发送端/接收端

  14. 差错检测编码（Error-detecting code）: 用于差错检测或纠正

  15. 协议控制（Protocol control）: 实现协议功能的附加信息，如: 优先级（priority）、服务质量（QoS） 和安全控制等

  16. OSI模型（7层）:应用层、表示层、会话层、传输层、网络层、数据链路层、物理层

第二章、应用层

2.1、应用层协议原理

  1. 应用程序体系结构：
    1. 客户-服务器体系结构（client-server architecture）
      • 有一个总是打开的主机称为服务器，它服务于来自其他称为客户的主机的请求
      • 客户之间不直接通信
    2. P2P体系结构
      • 应用程序在间断连接的主机之间使用直接通信，这些主机被称为对等方
      • 自扩展性（书P57）
  2. 进程通信：
    1. 发起通信的进程标识为客户，会话开始时等待联系的进程是服务器
    2. 进程寻址：通过IP（32比特），目的地端口号实现
  3. TCP：
    1. 面向连接的服务
      • 连接是全双工的，即连接双方的进程可以在此连接上同时进行报文收发
    2. 可靠的数据传输服务
    3. 面向连接、可靠数据传输、流量控制、拥塞控制；无时延和带宽保证
  4. UDP：
    1. UDP是一种不提供不必要服务的轻量级运输协议，它仅提供最小服务
    2. UDP无连接
    3. 提供不可靠数据传送服务
    4. 不提供建立连接，可靠性，流量控制，拥塞控制；时延和带宽保证
  5. 应用层协议定义了运行在不同端系统上的应用程序进程如何相互传递报文

2.2、Web和HTTP

  1. HTTP概况

    1. Web的应用层协议是超文本传输协议HTTP

    2. Web页面（Web page）（也叫文档）是由对象组成的。一个对象只是一个文件

    3. 多数Web页面含有一个HTML基本文件以及几个引用对象

    4. HTTP使用TCP

    5. HTTP服务器不保存关于客户的任何信息，是一个无状态协议（stateless protocol）

  2. 持续连接：每个请求/响应经一个单独的TCP连接发送

  3. 非持续连接：所有请求/响应经相同的TCP连接发送

  4. 往返时间（Round-Tip Time，RTT）指一个短分组从客户到服务器然后再返回客户所花费的时间

  5. HTTP报文格式：

    1. HTTP请求报文request：

      • 第一行为请求行，后继的行叫做首部行

    • 请求行：

      1. 有三个字段：方法字段，URL字段，HTTP版本字段
      2. 方法字段：GET,POST,HEAD,PUT,DELETE

      • 首部行：

        1. Host指明了对象所在的主机

        2. Connection：close 浏览器告诉服务器在发送完请求对象后关闭连接（close为非持续连接）

        3. User-agent 指明用户代理，即向服务器发送请求的浏览器类型

        4. Accept 表示用户想得到该对象的语法版本

      1. 请求报文通用格式：

      使用GET方法实体体为空，POST方法才使用实体体，其中包含用户在表单字段中的输入值

      使用GET方法，表单(各字段)输入值被上载,以URL请求行的字段: www.somesite.com/animalsearch?monkeys&banana

      • 当服务器收到一个HEAD方法方法的请求时，将会用一个HTTP报文响应但不返回请求对象

    • PUT方法允许用户上传对象到指定的Web服务器上的指定路径

      • DELETE方法允许用户删除Web服务器上的对象

    1. HTTP响应报文response：

      • 分为1个初始状态行，6个首部行然后是实体体（entity body）

      • 实体体部分是报文的主要部分，它包含了所请求对象本身

      • 状态行有3个字段：协议版本字段、状态码和相应状态信息

      • 首部行：

        1. Connection：close代表发送完报文后关闭该TCP连接

    2. Date指示服务器产生并发送该相应报文的日期和时间

      1. Server指示该报文是由什么服务器产生的
      2. Last 指示对象创建或最后修改的日期和时间
      3. Content-Length指示了被发送对象中的字节数
      4. Content-Type指示实体体汇总的对象是HTML文本

    • 响应报文通用格式：

    • 常用状态码及相关短语：

  6. cookie:

    1. 允许站点对用户进行跟踪

  7. Web缓存：

    1. 也叫代理服务器
    2. 目标:在不访问服务器的前提下满足客户端的HTTP请求
    3. 缓存既充当客户端，也充当服务器
    4. 一般由ISP(Internet服务提供商)架设
    5. 为什么需要Web缓存器?
      • 减少对客户机请求的响应时间
      • 减少内部网络与接入链路上的通信量
      • 能从整体上大大降低因特网上的Web流量

  8. 条件GET方法：

    1. 目的:证实缓存器中的对象是否为最新
    2. 缓存器：在请求报文中包含对象最后修改时间 If-modified-since: date
    3. 服务器: 如果对象是最新的则响应报文中不包含对象且状态行为 HTTP/1.0 304 Not Modified

2.3、电子邮件

  1. 三个组成部分：用户代理user agents，邮件服务器mail servers，简单邮件传送协议（SMTP）和邮件接收协议

  2. 客户使用TCP来可靠传输邮件消息到服务器端口号25

  3. SMTP：

    1. 用于从发送方的邮件服务器发送报文到接收方的邮件服务器
    2. 直接传送: 发送服务器到接收服务器
    3. 命令: ASCII文本格式
    4. 应答: 状态码及其短语
    5. 邮件消息(header & body)必须是7-bit ASCII
    6. SMTP使用持久连接
    7. SMTP服务器使用CRLF.CRLF 来判断邮件消息的结束
    8. 传输的3个阶段：握手 (问候)，邮件消息的传输，结束

  4. SMTP和HTTP对比：

    1. HTTP：拉协议（用户使用HTTP从该服务器拉取这些信息）,SMTP：推协议（发送邮件服务器把文件推向接收服务器）
    2. 都有ASCII 命令/应答交互, 状态码
    3. HTTP: 每个对象封装在它各自的HTTP响应消息中发送
    4. SMTP: 把所有报文对象放在一个报文中

  5. 邮件消息的格式：

    1. 每个首部行必须包含一个From首部行和一个To首部行，一个首部也许包含一个Subject首部行及其他可选首部行

  6. MIME: Multipurpose Internet mail Extensions多用途因特网邮件扩展, RFC 2045, 2046，增添额外的信头头部声明MIME content-type

  7. 邮件访问协议：

    1. 因SMTP是推协议，而用户代理从邮件服务器中取得报文是拉动作，所以不能用SMTP
    2. POP3
      • 身份认证 (代理 <–>服务器) 并下载邮件消息
      • 使用TCP连接
    3. IMAP
      • 允许用户像对待本地邮箱那样操纵远程邮箱的邮件
      • 所有邮件消息保存在一个位置: 服务器
      • 允许用户利用文件夹组织管理邮件消息
      • 允许用户代理获取报文某些部分的命令
    4. HTTP：
      • 在邮件服务器之间接收和发送邮件仍使用SMTP，但其他两个地方使用HTTP

2.4、DNS

  1. 功能：

    1. 主机名到IP地址的转换
    2. 主机别名：一个主机可以有一个规范主机名和多个主机别名
    3. 邮件服务器别名
    4. 负载分配：
      • DNS实现冗余服务器：一个IP地址集合可以对应于同一个规范主机名

  2. DNS协议运行在UDP上，使用53号端口

  3. DNS特点分布式数据库：

    1. 一个由分层DNS服务器实现的分布式数据库
    2. 应用层协议：DNS服务器实现域名转换 (域名/地址转换)

  4. 分布式、层次数据库：

  5. 根DNS服务器，顶级域（Top-Level Domain，TLD）DNS服务器，权威DNS服务器

  6. 本地DNS服务器：

    1. 严格来说不属于该服务器的层次结构
    2. 每个ISP（如居民区ISP、公司、大学）都有一个本地DNS，也叫默认服务器
    3. 主机发出DNS请求时，该请求被发往本地DNS服务器。起着代理的作用，转发请求到层次结构中

  7. DNS查询方法：

    1. 递归查询
      • 名字解析的负担交给被查询的名字服务器
    2. 迭代查询
    3. 任何DNS查询可以既是递归的也是迭代的
    4. 实践中通常为从请求主机到本地DNS服务器的查询是递归的，其余查询是迭代的

  8. DNS记录：

    1. DNS: 存储资源记录(RR，Resource Records)的分布式数据库，RR提供了主机名到ip地址的映射

    2. 资源记录（Resource Records，RR）书P89

      • 格式: (name, value, type,ttl)
      • ttl是该记录的生存时间，它决定了资源记录应当从缓存中删除的时间
      • Name和Value的值取决于Type
      • Type=A（Address），name = 主机名，value = IP地址（A类型的RR提供了标准主机名到ip地址的映射）
      • Type=NS（ name server ），name = 域名（如foo.com）， value = 该域权威名字服务器的主机名（这个RR用于沿着查询链来路由DNS查询）
      • Type=CNAME（canonical），name = 主机别名 （如 www.ibm.com的真名为servereast.backup2.ibm.com） ，value = 真实的规范主机名
      • Type=MX（mail exchange），name =邮件服务器的主机别名，value =邮件服务器的真实规范主机名

    3. 如果一台DNS服务器是用于某特定主机名的权威DNS服务器，那么该DNS服务器会有一条包含用于该主机名的类型A记录（即使该DNS服务器不是其权威DNS服务器，它也可能在缓存中包含有一条类型A记录)

    4. 如果服务器不是用于某主机名的权威服务器,那么该服务器将包含一条类型NS记录，该记录对应于包含主机名的域;它还将包括一条类型A记录，该记录提供了在NS记录的Value字段中的 DNS服务器的IP地址

  9. DNS报文：

    1. DNS只有查询和回答报文，且具有相同格式

    2. 前12字节是首部区域

      • 标识符: 16位，查询和应答报文使用相同的标识符
      • 标志:有若干个标志构成，分别标识不同的功能
      • 问题区域包含正在进行的查询信息，包含名字字段和类型字段

  10. 在DNS数据库中插入记录

  11. 内容分发网络(Content distribution networks, CDN)：主要是截获和重定向请求

第三章、运输层

3.1、多路分解与多路复用

  1. 在接收主机多路分解:将接收到的数据段传递到正确的套接字

  2. 在发送主机多路复用:从多个套接字收集数据, 用首部封装数据，然后将报文段传递到网络层

  3. 网络层:两个主机之间的逻辑通信；

    传输层:两个进程之间的逻辑通信

  4. 端口号大小为16比特，0-1023范围的端口号称为周知端口号

  5. 无连接多路分解：

    1. UDP套接字由二元组标识（目的地IP地址, 目的地端口号）
    2. 具有不同的源IP地址且/或源端口号，但具有相同的目的IP地址和目的端口号的IP报文段指向同样的套接字

  6. 面向连接的多路分解：

    1. TCP 套接字由4部分指定: （源IP地址，源端口号，目的IP地址，目的端口号）

3.2、UDP

  1. “尽力而为”服务，UDP段可能：

    • 丢包

    • 对应用程序交付失序

  2. 为何要有 UDP协议?

    • 无连接创建(它将增加时延)

    • 简单：在发送方、接收方无连接状态

    • 段首部小，UDP首部只有8字节，TCP有20字节

    • 无拥塞控制: UDP能够尽可能快地传输

  3. 应用层交给 UDP 多长的报文，UDP 就照样发送，即一次发送一个报文

  4. UDP首部格式：

    • 首部字段有 8 个字节，由 4 个字段组成，每个字段都是两个字节

  5. 经UDP的可靠传输 : 在应用层增加可靠性

    • 应用程序特定的差错恢复

  6. UDP校验和

    加法有溢出则进行回卷

    在计算检验和时，临时把“伪首部”和 UDP 用户数据报连接在一起

3.3、可靠数据传输协议

  1. rdt1.0

  2. rdt2.0

    • 停等协议：发送方发送一个报文，然后等待接受方的响应，在等待时不能从上层获得更多的数据

  3. rdt2.1

    • 处理冗余:

      • 发送方对每个分组增加序列号

      • 如果ACK/NAK受损，发送方重传当前的分组

      • 接收方丢弃(不再向上交付)冗余分组

  4. rdt2.2：一个不要NAK的协议

    • 同 rdt2.1一样的功能, 只用 ACKs

    • 代替NAK,接收方对最后正确接收的分组发送ACK

      • 接收方必须明确包含被确认的报文的序号

    • 发送方收到重复 ACK 将导致和 NAK一样的处理: 重发当前报文

  5. rdt3.0：具有出错和丢失的信道

    • 发送方等待ACK一段“合理的”时间

      • 如在这段时间没有收到ACK则重传

      • 如果分组(或ACK)只是延迟(没有丢失)：

      ​ 重传将是冗余的，但序号的使用已经处理了该情况；

      ​ 接收方必须定义被确认的分组序号

      • 需要倒计时定时器

  6. 流水线可靠数据传输协议：

    • 流水线: 发送方允许发送多个 “在路上的”, 还没有确认的报文

      • 序号数目的范围必须增加

      • 在发送方/接收方必须有缓冲区

  7. 解决流水线的差错恢复的两种基本方法：回退N步（Go-Back-N,GBN）和选择重传（Selective Repeat,SR）

  8. 回退N步：

    1. 又称为滑动窗口协议

    2. 发送方：

      • ACK(n): 确认所有的（包括序号n）的分组 - “累计ACK”（可能收到重复的ack）

      • 对每个传输中的分组的用同一个计时器

        对第一个发送未被确认的报文定时

      • timeout(n):若超时，重传窗口中的分组n及所有更高序号的分组

    3. 接收方：

      • 对失序的分组:

        • 丢弃 (不缓存) -> 没有接收缓冲区!

        • 重新确认具有按序的分组

      • 只有ACK: 对接收的分组总是发送具有最高按序序号的ACK

  9. 选择重传：

    1. 接收方分别确认已经收到的分组，必要时，缓冲报文, 最后按序提交给上层
    2. 发送者只重发没有收到确认的分组对每个没有确认的报文发送者都要启动一个定时器(每个未被确认的报文都有一个定时器)
    3. 窗口长度必须小于或等于序号空间大小的一半

3.4、TCP

  1. 概述：

    1. **点到点: **一个发送方, 一个接收方

    2. 面向连接:

      • 在进行数据交换前，初始化发送方与接收方状态，进行握手(交换控制信息)。

      • 连接状态与端系统有关，不为路由器所知

    3. 全双工数据:

      • 同一连接上的双向数据流

    4. TCP采用累计确认

  2. 发送和接收缓冲区

  3. MSS: 最大报文段长度，通常根据最初确定的由本地发送主机发送的最大链路层帧（最大传输单元，MTU）长度来设置

  4. 设置MSS要保证一个TCP报文段加TCP/IP首部长度（通常40字节）将适合单个链路层帧

  5. MSS指在报文段里应用层数据的最大长度，而不包括首部的TCP报文段的长度

  6. TCP面向流的概念：

    1. **可靠、有序的字节流:**没有 “报文边界”
    2. 流水线: TCP拥塞和流量控制设置滑动窗口协议
    3. 流量控制: 发送方不能淹没接收方
    4. 拥塞控制: 抑止发送方速率来防止过分占用网络资源

  7. TCP报文段结构：

    1. TCP首部一般为20字节（选项字段为空）：

      1. 源端口和目的端口字段——各占 2 字节

        • 端口是运输层与应用层的服务接口。运输层的复用和分解功能都要通过端口才能实现

      2. 序号字段——占 4 字节

        • TCP 连接中传送的数据流中的每一个字节都编上一个序号

        • 序号字段的值则指的是本报文段所发送的数据的第一个字节的序号

      3. 确认号字段——占 4 字节

        • 是期望收到对方的下一个报文段的数据的第一个字节的序号

      4. 首部长度（即数据偏移）——占 4 比特

        • 指示了以32比特的字为单位的TCP首部长度。也就是说，它指出 TCP 报文段的数据起始处距离 TCP 报文段的起始处有多远，因TCP首部长度可变

        • “数据偏移”的单位是 32 位字（以 4 字节为计算单位）

      5. 保留字段——占 6 比特

        • 保留为今后使用，但目前应置为 0

      6. 标志字段——占6比特

        • 紧急 URG —— 当 URG = 1 时，表明紧急指针字段有效。它告诉系统此报文段中有紧急数据，应尽快传送(相当于高优先级的数据)，紧急数据的最后一个字节由16比特的紧急数据指针字段指出

        • 确认 ACK —— 只有当 ACK = 1 时确认号字段才有效。当ACK = 0 时，确认号无效

        • 推送 PSH (PuSH) —— 接收 TCP 收到 PSH = 1 的报文段，就尽快地交付接收应用进程，而不再等到整个缓存都填满了后再向上交付

        • 复位 RST (ReSeT) —— 当 RST = 1 时，表明 TCP 连接中出现严重差错（如由于主机崩溃或其他原因），必须释放连接，然后再重新建立运输连接

        • 同步 SYN —— 同步 SYN = 1 表示这是一个连接请求或连接接受报文

        • 终止 FIN (FINis) —— 用来释放一个连接。FIN = 1 表明此报文段的发送端的数据已发送完毕，并要求释放运输连接

      7. 窗口字段 —— 占 2 字节

        • 用来让对方设置发送窗口的依据，单位为字节。

        • 用于流量控制，用于指示作为接受方，愿意接受的字节数量

      8. 检验和 —— 占 2 字节

        • 检验和字段检验的范围包括首部和数据这两部分

        • 在计算检验和时，要在 TCP 报文段的前面加上 12 字节的伪首部

      9. 紧急指针字段 —— 占 16 位

        • 指出紧急数据最后一个字节的位置，也就是指出在本报文段中，紧急数据共有多少个字节（紧急数据放在本报文段数据的最前面）

      10. 选项字段——可扩展

      11. 填充字段 —— 这是为了使整个首部长度是 4 字节的整数倍

    2. 序号: 报文段中第1个数据字节在字节流中的位置编号

    3. 确认号:

      • 期望从对方收到下一个字节的序号

      • 累积确认

    4. 问：接收方如何处理失序报文段？

      回答：TCP规范没有说明， 由实现者自行选择实现: 抛弃/缓存

  8. TCP往返时延的估计和超时：

    1. 估计往返时间：

      • 样本RTT（SampleRTT）: 测量从报文段发送到收到确认的时间

      • TCP维持一个SampleRTT均值（称为EstimatedRTT）

      • 一旦获得一新RTT，TCP根据指数加权平均更新EstimatedRTT, $\alpha$ 推荐值为0.125

        $EstimatedRTT = (1-\alpha)*EstimatedRTT+\alpha *SampleRTT$

      • DevRTT：RTT的偏差，用于估算SampleRTT一般会偏离EstimatedRTT的程度, $\beta$ 推荐值为0.25

        $DevRTT=(1-\beta)*DevRTT+\beta *|SampleRTT-EstimatedRTT|$

    2. 设置超时：

      • 超时间隔应等于EstimtedRTT 加上 “安全余量”

        EstimatedRTT变化大 -> 更大的安全余量

      • 超时间隔：$TimeoutInterval = EstimatedRTT + 4*DevRTT$

    3. 初始化超时：

      • 初始时TimeoutInterval设置为1秒

      • 第一个样本RTT获得后，

        $EstimatedRTT=SampleRTT$，

        $DevRTT=SampleRTT/2$，

        $TimeoutInterval =EstimatedRTT + max (G, K*DevRTT) $

        （K=4，G是用户设置的时间粒度）

  9. 可靠数据传输：

    1. TCP在IP不可靠服务的基础上创建可靠数据传输服务

      • 肯定确认和定时器

      • 序号、重传

    2. TCP使用单个重传计时器

    3. 重传被下列事件触发:

      • 超时事件

      • 重复ACK

    4. 定时器与最早没有被确认的报文段关联

    5. 超时间隔加倍：

      • TCP每次重传，都会把下一次的超时间隔设置为先前值的两倍
      • 但是当收到上层应用的数据和收到ACK两个事件中的任何一个发生时，定时器的TimeoutInterval值恢复为由近期的EstimatedRTT和DevRTT计算得到
      • 这种修改，提供了一种形式受限的拥塞控制

    6. 快速重传

      1. 发送方可以在超时之前通过重复的ACK检测丢失报文段

      2. 如果发送方收到3个对同样报文段的冗余确认，则发送方认为该报文段之后的数据已经丢失。

        • 启动快速重传: 在定时器超时之前重发丢失的报文段

      3. 冗余ACK：再次确认某个报文段的ACK

  10. 流量控制（书P165）

    1. 流量控制：发送方不能发送的太多太快，让接收缓冲区溢出

    2. TCP通过让发送方维护一个接收窗口的变量来提供流量控制

    3. 发送方要限制未确认的数据不超过缓存

      $LastByteSent-LastByteAcked <= RcvBuffer$

    4. 缓冲区的剩余空间也就是接收窗口：$rwnd= RcvBuffer-[LastByteRcvd -LastByteRead] $

    5. 由于该空间是随时间变化的，所以rwnd也是动态的

    6. 接收方在报文段接收窗口字段中通告其接收缓冲区的剩余空间

    7. 当主机B的接收窗口为0时，主机A继续发送只有一个字节数据的报文段（防止主机A被永远阻塞，书上例子很详细）

  11. TCP连接管理

    1. 三次握手：

      1. 步骤 1: 客户机向服务器发送 TCP SYN报文段
        • 随机指定初始序号（client_isn）放于TCP报文段首部的序号字段中
        • 没有数据
        • 首部SYN比特置1
      2. 步骤 2: 服务器收到SYN报文段, 用SYNACK报文段回复
        • 服务器为该连接分配缓冲区和变量
        • 指定服务器初始序号（server_isn）放于TCP报文段首部的序号字段中
        • 首部SYN比特置1
        • 首部确认号字段置client_isn+1
      3. 步骤3：客户机接收到 SYNACK
        • 客户机为该连接分配缓冲区和变量
        • 用ACK报文段确认回复（该客户通过将值server_isn+1放置到TCP报文段首部的确认字段中完成）
        • 可能包含数据
        • SYN比特置0

    2. 关闭连接：

      1. Step 1: 客户发送 TCP FIN 控制报文段到服务器

      2. Step 2: 服务器接收 FIN, 回复 ACK. 半关闭连接, 并发送FIN到客户

      3. Step 3: 客户接收 FIN, 回复 ACK.

        进入 “timed wait”状态

        等待结束时释放连接资源

      4. Step 4: 服务器接收 ACK. 连接关闭

    3. TCP状态转化：

      1. 客户端

      2. 服务器端

  12. 拥塞控制原理

    1. 拥塞: 从信息角度看: “太多源主机发送太多的数据，速度太快以至于网络来不及处理”
    2. 表现:
      • 丢失分组 (路由器的缓冲区溢出)
      • 长延迟 (在路由器的缓冲区排队)
    3. 拥塞网络的代价：
      1. 当分组的到达速率接近链路容量时，分组经历巨大的排队时延
      2. 发送方必须执行重传以补偿因为缓存溢出而丢弃（丢失）的分组
      3. 发送方在遇到大时延时所进行的不必要重传会引起路由器利用其链路带宽来转发不必要的分组副本
      4. 当一个分组沿一条路径被丢弃时，每个上游路由器用于转发该分组到丢弃该分组而使用的传输容量最终被浪费掉了
    4. 拥塞控制方法：
      1. 根据网路层是否为运输层拥塞控制提供了显示帮助，来区分拥塞控制方法
      2. 端到端拥塞控制
        1. 网路层没有为运输层提供显示的支持
        2. 从端系统根据观察到的时延和丢失现象推断出拥塞
        3. TCP采用此方法
        4. TCP报文段的丢失（超时或3次冗余确认）被认为是网络拥塞的一个迹象
      3. 网络辅助的拥塞控制
        1. 路由器向发送方提供关于网络中拥塞状态的显示反馈信息
        2. 一个bit指示一条链路出现拥塞(SNA,DECnet)
        3. 指示发送方按照一定速率发送（ATM）
        4. 两种形式发送拥塞信息
          • 直接反馈信息可以由网络路由器发给发送方。这种方式的通知通常采用了一种阻塞分组 （choke packet)的形式（主要是说:“我拥塞了!”)。
          • 路由器标记或更新从发送方流向接收方的分组中的某个字段来指示拥塞的产生。一旦收到一个标记的分组后，接收方就会向发送方通知该网络拥塞指示。注意到后一种形式的通知至少要经过一个完整的往返时间。

  13. TCP拥塞控制

    1. 采用端到端控制 (没有网络辅助)

    2. 发送方通过cwnd拥塞窗口（congestion window）限制传输:LastByteSent-LastByteAcked<=min{ cwnd，rwnd}

    3. 拥塞窗口是动态的, 通过调节cwnd的值，发送方因此能调整它向连接发送数据的速率

    4. 发送方如何感知网络拥塞?

      • 丢失事件 = 超时或者 3个重复ACK

      • 发生丢失事件后，TCP发送方降低速率(拥塞窗口)

      • 正常时增加发送速率，自计时

    5. TCP发送方怎样确定它应当发送的速率呢?

      1. 一个丢失的报文段意味着拥塞，应当降低TCP发送速率
      2. 当收到未确认报文段的确认到达时，能够增加发送方的速率
      3. 带宽探测

    6. TCP拥塞控制算法

      1. 包括三个部分：慢启动，拥塞避免，快速恢复
      2. 慢启动和拥塞避免是TCP的强制部分，快速恢复是推荐部分，对TCP发送方并非是必需的
      3. 慢启动
        • 连接开始的时候, cwnd = 1 MSS，并且每当传输报文段首次被确认就增加一个MSS
        • 故开始以指数方式增加速率，直到产生丢失事件，或者达到某个阈值ssthresh
        • 如何结束：
          1. 超时指示的丢包事件：发送方将cwnd = 1 MSS，ssthresh（慢启动阈值）=cwnd/2
          2. 与ssthresh值相关：当到达或超过ssthresh值时线性增长，TCP转移到拥塞避免模式
          3. 收到3个冗余确认后：TCP执行一种快速重传并进入快速恢复状态
      4. 拥塞避免
        • 一旦进入拥塞避免状态，CongWin的值大约是上次遇到拥塞时的一半，即距离阻塞可能并不遥远
        • 每个RTT只将CongWin的值增加一个MSS
        • 超时事件以后，迁移到慢启动状态：CongWin值设置为1 MSS，Ssthresh= CongWin /2
        • 收到3个冗余确认后: CongWin减半+3个MSS，Ssthresh= CongWin /2 ，进入快速恢复阶段
      5. 快速恢复
        • 对于引起TCP进入快速恢复状态的缺失报文段，每收到一个冗余的ACK，CongWin的值增加一个MSS
        • 最终，当对丢失的报文段的一个ACK到达时，TCP在降低 CongWin后进入拥塞避免状态，cwnd=ssthresh
        • 如果出现超时事件，迁移到慢启动状态

第四章、网络层

4.1、概述

  1. 数据平面功能：每台路由器的功能。

    控制平面功能：全网范围决定路由的功能

  2. 网络层提供的服务和功能

    • 主机通信

    • 虚电路和数据报

    • 转发

    • 选路

  3. 网络层的功能：转发和路由选择

    • 转发：将分组从路由器的一个输入链路接口转移到一个合适的输出链路接口的本地动作

    • 路由选择：指分组从源到目的地的端到端路径的网络范围动作

  4. 转发表：每台路由器有一张

  5. 控制平面：SDN方法

    • 一个分离的（通常是远程的）控制器和路由器本地的控制代理 (local control agents，CAs) 交互

  6. 分组交换机：一台通用分组交换设备，根据分组首部值，从输入链路接口到输出链路接口传送分组

    链路层交换机：根据链路层字段值作转发决定的分组交换机

    路由器：根据网络层字段值作转发决定的分组交换机

  7. 网络层可能提供的服务：

    1. 确保交付：确保分组到达目的地。
    2. 有序分组交付：按发送顺序到达。
    3. 具有时延上界的确保交付：主机到主机的时延。
    4. 确保最小带宽：当发送主机以低于特定比特率的速率发送比特，分组不会丢失，在一定时延到达。
    5. 确保最大时延抖动：发送方发送两个连续分组的时间间隔与接收到的间隔相同

  8. 因特网的网络层提供单一服务，称为尽力而为服务

4.2、数据报网络

  1. 数据报转发表
    • 转发表是由路由选择处理器计算和更新的或者转发表接收来自远程SDN控制器的内容
    • 用目的地址前缀与转发表的前缀匹配
    • 存在匹配：向对应链路转发
    • 不存在匹配：选择“其他”项对应的链路转发
    • 存在多个匹配：使用最长前缀匹配规则，即向与最长前缀匹配的链路接口转发分组
    • 一个端系统发送给另一个端系统的一批分组可能在网络中选择不同的路径，到达的顺序可能不一致

4.3、路由器工作原理

  1. 网络层转发功能：将分组从路由器的输入链路传送到适当的输出链路

  2. 路由器体系结构

  3. 输入端口功能

    1. 第一个线路端接模块：将一条物理链路端接到路由器的物理层

    2. 第二个数据链路处理模块：实现路由器的数据链路层功能；

    3. 第三个查找与转发模块：实现查找与转发功能，以便分组通过路由器交换结构转发到适当的输出端口；

  4. 查（转发）表方法：

    1. 线性查找
    2. 二分查找
    3. 三态内容可寻址内存(TCAM)
    4. 将最近被访问的表项保存在高速缓存(cache)中

  5. 交换结构

    1. 三种交换技术：经内存交换，经总线交换，经互联网络交换

    2. 经内存交换：

      • 输入端口与输出端口之间的交换由CPU(选路处理器)控制完成

    3. 经总线交换：

      • 输入端口通过一条共享总线将分组直接传送到输出端口，不需要选路处理器的干预
    • 每次只能有一个分组通过总线传送

    1. 经互联网络交换：

      • 纵横式交换机：由2n 条总线组成，n 个输入端口与n 个输出端口连接

      • 到达输入端口的分组沿水平总线穿行，直至与所希望的输出端口的垂直总线交叉点：

      • 若该条垂直总线空闲，则分组被传送到输出端口；

      • 否则，该到达的分组被阻塞，必须在输入端口排队

  6. 输出端口（Output ports）

    1. 取出存放在输出端口内存中的分组，并将其传输到输出链路上
    2. 当输出端口的缓冲区溢出时，就会出现延时和丢包

  7. 输入端口排队

    • 线路前部 HOL (head-of-the-line)阻塞：输入队列中后面的分组被位于线路头的一个分组阻塞(即使输出端口空闲的)，等待通过交换结构发送

  8. 输出端口排队

    • 分组丢弃方法：
      1. 丢弃后到的分组（弃尾）
      2. 删除一个或多个已排队的分组
    • 少量TCP流：缓存数量（B）应当等于平均往返时延（RTT）乘以链路的容量（C）
    • 大量TCP流（N条）：$B=RTT*C/ \surd{N}$

  9. 分组调度

    1. 先来先服务FCFS：简单
    2. 优先权排队：具有优先级
      • 根据到达分组的类型，引导到不同优先级的队列中
      • 优先发送具有最高优先级队列中的分组
    3. 循环队列规则 RR
      • 根据到达分组的类型，引导到不同类别的队列中
      • 循环调度器在这些不同类所对应的队列中轮流提供服务
    4. 加权公平排队WFQ：在具有排队分组的不同端到端连接之间公平地共享输出链路
      • 但是不同类的队列，在每个循环周期中，所获得的服务量并不平等，而是由其权值决定

4.4、网际协议（IPv4，DHCP，NAT）

  1. IPv4数据报格式

    1. 一个 IP 数据报由首部和数据两部分组成
    2. 首部的前一部分是固定长度，共 20 字节，是所有 IP 数据报必须具有的
    3. 在首部的固定部分的后面是一些可选字段，其长度是可变的
    4. 报文段：
      1. 版本——占 4 位
        • 指 IP 协议的版本目前的 IP 协议版本号为 4 (即 IPv4)
      2. 首部长度——占 4 位
        • 可表示的最大数值是 15 个单位(一个单位为 4 字节)
        • 因此 IP 的首部长度的最大值是 60 字节
      3. 区分服务——占 8 位
        • 用来获得更好的服务在旧标准中叫做服务类型，一般不使用
      4. 总长度——占 16 位
        • 指首部和数据之和的长度，单位为字节
        • 因此数据报的最大长度为 65535 字节
        • 总长度必须不超过最大传送单元 MTU
      5. 标识(identification) 占 16 位
        • 它是一个计数器，用来产生数据报的标识
      6. 标志(flag) 占 3 位
        • 目前只有前两位有意义
        • 标志字段的最低位是 MF (More Fragment)，MF = 1 表示后面“还有分片”。MF = 0 表示最后一个分片。
        • 标志字段中间的一位是 DF (Don’t Fragment) ，只有当 DF = 0 时才允许分片
      7. 片偏移(12 位)
        • 指出：较长的分组在分片后某片在原分组中的相对位置
        • 片偏移以 8 个字节为偏移单位
      8. 生存时间(8 位)记为 TTL (Time To Live)
        • 数据报在网络中可通过的路由器数的最大值
        • 值为0则丢弃该数据报
      9. 协议(8 位)字段
        • 指出此数据报携带的数据用于何种协议，以便目的主机的 IP 层将数据部分上交给哪个处理过程
      10. 首部检验和(16 位)字段
        • 只检验数据报的首部，不检验数据部分
        • 这里不采用 CRC 检验码而采用简单的计算方法
      11. 源地址和目的地址都各占 4 字节
      12. 选项字段的长度可变，从 1 个字节到 40 个字节不等，取决于所选择的项目

  2. IP数据报分片和重组

    1. MTU指的是数据链路帧的数据区的最大字节数

    2. 在添加源地址和目的地址时，还会为该报文段，添加标识字段， 分片后的每个片，都具有相同的源地址和目的地址，以及相同的标识

    3. MF=0，表示最后一个片

    4. 通过片偏移字段，标识该片在初始IP数据报中的哪个位置

      注意：4000数据段字节大小包含数据3980字节和20字节首部

  3. IP地址

    1. IP 地址: 分配给主机或路由器接口的标识符
    2. 接口: 主机/路由器与物理链路之间的边界
      • 路由器有多个接口
      • 主机可以有多个接口
      • 每个接口有一个IP地址
    3. IPV4：32个二进制位长（4字节），常用点分十进制表示
    4. IPV6：128个二进制位长（16字节），常用冒号分隔表示

  4. IPv4编址

    1. 32比特的二进制表示和点分十进制表示法

  5. IP地址结构

    1. IP 地址是一种分等级的地址结构，包括两部分：
    • 网络号：指明主机所在网络的编号
    • 主机号：主机在网络中的编号
    • 主机号为全0和全1的两个地址不能使用，用于特殊的目的！

    1. 好处：

      1. IP 地址管理机构在分配 IP 地址时只分配网络号
      2. 路由器仅根据目的主机所连接的网络号来转发分组

    2. 特殊IP地址段：

      1. 0.0.0.0

        这个地址严格上来说都不是真正意义上的IP地址。主要是用来标识不清楚的网络和主机的。系统遇到无法识别的网络或主机的时候会统一的归纳到这个地址

      2. 255.255.255.255

        这个地址是受限的广播地址。主要指一个网段内的所有主机

      3. 127.0.0.1

        这个是预留的一个IP地址，主要是用来识别电脑自己本身的地址。也叫做“localhost”一般用来测试使用的

    3. 同一局域网上的主机或路由器的IP地址中的网络号必须相同。用IP术语来说，具有相同网络号的局域网，称为子网

    4. 路由器总是具有两个或两个以上IP地址

    5. 子网：

      • 设备接口的IP地址具有同样的网络部分
      • 没有路由器的介入，物理上能够相互到达
      • 分开主机和路由器的每个接口，产生几个隔离的网络岛，使用接口端接这些隔离的网络的端点。这些隔离的网络中的每一个都叫做一个子网

  6. 无类别域间路由( Classless Inlerdomain Routing,CIDR )

    1. 因特网的地址分配策略称为CIDR
    2. 使用斜线记法，又称为CIDR记法来区分网络前缀和主机号，即在IP地址后面加上一个斜线“/”，斜线后面用一个数字指定网络前缀的长度
    3. 地址格式: a.b.c.d/x, 这里 x 是地址网络部分的bit数
    4. 其中/x 的记法，也称为子网掩码

  7. 子网掩码

    1. 子网掩码用来确定网络前缀和主机地址的长度
    2. 子网掩码长为32位比特，其中的1对应于IP地址中的网络号，而子网掩码中的0对应于主机号

  8. 路由聚合：使用单个网路前缀通告多个网络的能力通常称为地址聚合，也称为路由聚合（书P220）

  9. 子网划分！！！

    子网划分总结：

    • 对于子网划分，建议先把主机数量最多的子网划分了，再划分主机数量较小的子网。
    • 对于子网划分，一个子网能使用的IP的范围，其起始IP一定是奇数、其截止的IP一定是一个偶数
    • 两个主机号相邻的子网，小序号子网的截止IP和大序号子网的起始IP，中间的差值为3，因为其间间隔了两个主机号为全1和全0的IP
    • 对于网络号的表示，用于主机的所有bit都要为0

  10. 动态主机配置协议DHCP（Dynamic Host Configuration Protocol）

    1. 自动从一个DHCP服务器得到IP地址

    2. DHCP是应用层协议

    3. DHCP分配的不仅仅是IP地址，还可分配：

      • 客户的第一跳路由器的地址（网关）

      • DNS服务器的IP地址或域名

      • 子网掩码

    4. 又被称为plug-and-play（即插即用）协议或zeroconf（零配置）协议

    5. DHCP概述：

      • 主机广播 DHCP发现报文，在UDP分组中向端口67发送该报文，使用广播地址255.255.255.255，本机源IP地址0.0.0.0
      • DHCP 服务器广播DHCP提供报文
      • 主机从一个或多个服务器中选择一个并发送DHCP请求报文进行响应
      • DHCP 服务器用DHCP ACK报文回应确认
      • DHCP 终止租用期，发送DHCP RELEASE报文

    6. DHCP中继代理(relay agent)：通常为一台路由器

      • 当 DHCP 中继代理收到主机发送的发现报文后，就以单播方式向 DHCP 服务器转发此报文，并等待其回答。收到 DHCP 服务器回答的提供报文后，DHCP 中继代理再将此提供报文发回给主机

  11. ISP获取地址块方法——从ICANN获取

  12. NAT：网络地址转换

    1. 动机: 对外部网络来讲，本地网络只用一个IP地址
    2. 在NAT转换表中，记录了每个(源IP 地址, 端口号)到 (NAT IP地址, 新端口号) 的对应关系
    3. 16-bit 端口号

  13. ICMP(Internet Control Message Protocol，因特网控制报文协议）PPT第四章P146，书P272

    1. 用于主机路由器之间彼此交流网络层信息：
      • 差错报告: 不可到达的主机, 网络,端口,协议
      • 请求/应答 (用于ping,traceroute)
    2. 位于IP之上：因为ICMP消息是装载在IP分组里的

4.5、IPv6

  1. IPv6首部：

    1. 流量类型:表示流中分组的优先级,类似IPv4中的TOS字段，可用于给出给出一个流中某些数据的优先级
    2. 流标签: 表示分组在同一个 “流”中 (“流”的概念尚未完全定义)
    3. 下一个首部: 表示数据的上层协议，类似IPv4中的协议字段
    4. 定长40字节首部，选项字段可能出现在“下一个首部”指出的位置上

  2. IPv6地址表示：

    1. 冒号十六进制表示法

    • 例如：

      105.220.136.100.255.255.255.255.0.0.18.128.140.10.255.255

      用冒号十六进制表示为：

      69DC:8864:FFFF:FFFF:0:1280:8C0A:FFFF

    1. 零压缩表示法

      • 每一块多个前导的0可以省略，一个块全为0可以简写为一个0,多个块为连续0的话可以简写为::

        例如：FF0C:0:0:0:0:0:B1

        零压缩表示为：

        FF0C::B1

    2. IPv6分为三种地址类型：

      1. 单播地址：一个单播地址对应一个接口，发往单播地址的数据包会被对应的接口接收
      2. 多播(组播)地址：一个组播地址对应一组接口，发往组播地址的数据包会被这组的所有接口接收；目的地为多个主机的数据包在特殊的多播地址上发送
      3. 任播地址：一个任播地址对应一组接口，发往任播地址的数据包会被这组接口的其中一个接收，被哪个接口接收由具体的路由协议确定
      4. IPv6不使用广播地址，广播地址的功能由多播地址代替

  3. IPv6与IPv4的不同

    1. 分片与重新组装：IPv6 不允许在中间路由器上进行分片与重新组装

    2. 校验和: 全部去掉，减少每一跳的处理时间

    3. 选项: 允许, 但是不是标准首部的一部分，而是用下一个首部域指出

    4. ICMPv6:新版本的 ICMP

      • 增加消息类型, 例如“分组太大”

      • 多播组管理功能

  4. IPv4到IPv6的过渡

    • 双栈：一些路由器具有双重栈 (v6, v4) 能够在两种格式中转换
    • 隧道: 在穿过IPv4路由器时，IPv6分组作为 IPv4分组的负载

4.6、路由选择算法

  1. 默认路由器：与主机直接相连的路由器，又叫第一跳路由器
  2. 路由算法：是确定一个分组从源路由器到目的路由器所经路径的算法
  3. 路由算法分类：
    1. 集中式（全局）选路算法，分散式路由选择算法
    2. 静态选路算法，动态选路算法
  4. 链路状态路由选择算法！！！
    1. 转发表：存放从源节点到每个目的节点的最低费用路径上的下一跳节点
    2. 所有迭代中需要搜寻的节点总数为n(n+1)/2
    3. 算法复杂性为n平方阶序O(n^2^)

4.7、层次选路

  1. 自治系统(Autonomous System) AS：

    • 按区域划分的系统。每个AS由一组在相同管理控制下的路由器组成。
    • 同一个AS内的路由器可运行相同的选路算法，且拥有相互之间的信息

  2. 层次选路：

    ➢将一个大的系统划分成若干小系统（自治系统），

    ➢按区域或自治系统的形式组织路由器。

    ➢自治系统之间再互连

  3. 网关路由器（gateway router）：互连各AS，负责转发目的地在本AS之外的分组（将本AS内的分组转发到另一个AS的路由器）

  4. 当一个AS知道从一个相邻的AS可以到达目的地，向某些他的相邻AS通告该选路信息

  5. 因特网中的路由选择

    1. AS内部选路协议：

      ✓ RIP选路信息协议：基于距离向量的路由协议

      ✓ OSPF开放最短路径优先：采用Dijkstra最短费用路径算法，是一种链路状态协议

    2. AS间选路协议：

      ✓ BGP边界网关协议：基于距离向量的路由协议。相邻BGP路由器相互交换路径信息

  6. OSPF

    1. 用链路状态算法
    2. 每个router都以洪泛的方式广播OSPF通告，OSPF通告里为每个邻居路由器设一个表项
    3. 通告会散布到整个自治系统
    4. OSPF信息直接通过 IP传输 (不是 TCP 或 UDP）
    5. 优点：
      1. 安全
      2. 多条相同开销的路径
      3. 对单播与多播路由选择的综合支持
      4. 支持在单个AS中的层次结构

  7. Internet 域间选路: 边界网关协议BGP

    1. BGP (Border Gateway Protocol)：事实上的标准

    2. 路由器对（BGP对等方）通过TCP连接来交换选路信息：BGP 会话

    3. 在BGP中，目的地不是主机地址，而是CIDR化前缀

    4. eBGP：跨越两个AS的BGP连接

    5. iBGP：在相同AS中的两台路由器之间的BGP会话

    6. 确定最好的路由：

      1. AS-PATH: 包含了前缀的通告已经通告过的那些AS
      2. NEXT-HOP: AS-PATH起始的路由器接口的IP地址（可能存在多条从当前AS到达下一个AS的链路）

    7. BGP路由选择：

      排除规则（应用排除规则直到有一条留下）

      • 本地偏好值属性: 具有最高偏好值的路由被选择

      • 最短AS-PATH的路由 （使用AS跳数）

      • 最靠近 NEXT-HOP路由器的路由 : 热土豆路由（AS内部路由算

      法决定）。

      • 其他标准

    8. IP任播

      1. BGP还常被用于实现IP任播（ anycast ） 服务
      2. 所谓任播，也叫“选播”，就是对具有相同IP地址的一组服务器中的任意一台，发送消息

    9. 为什么AS内选路和AS间选路采用不同的协议 ?

      策略:

      • AS间: 管理员想控制本AS内产生的通信流怎样选路，以及什么通信流穿过自己的网络

      • AS内:单个管理者, 因此不需要策略

4.8、SDN

  1. 软件定义网络（SDN，SoftwareDefinedNetwork）源自美国斯坦福大学CLeanState研究组提出的一种新型网络创新架构，可通过软件编程的形式定义和控制网络，具有控制平面和转发平面分离及开放性可编程的特点

  2. SDN的核心思想是建立一个通用转发体系——每个交换设备包含一个流表(flow table).。流表由一个逻辑上中心化的控制器（远程控制器）来计算和分发

  3. 基于目的转发的两个步骤：匹配+动作

  4. 通用转发：通用意义上的匹配加动作

    ➢ 匹配：根据协议中多个首部中的字段进行匹配。

    ➢ 动作：包括转发、丢弃、修改、负载均衡、向特定服务器转发等不同动作

  5. SDN体系特征

    1. 基于流的转发
    2. 数据平面与控制平面分离
    3. 网络控制功能：位于数据平面交换机外部
    4. 可编程的网络

  6. OpenFlow

    1. OpenFlow网络由 OpenFlow网络设备（OpenFlow Switch）和控制器（OpenFlow Controller）通过OpenFlow通道（OpenFlow Channel）组成

第五章、链路层

5.1、概述

  1. 节点 (node)：主机、交换机和路由器、WiFi接入点等
  2. 链路(link)：连接相邻节点的通信信道
  3. 数据链路层的职责：将分组通过一个链路，从一个节点传输到临近的另一个节点
  4. 交换的数据单元称为*帧 (frame)*，封装了一个网络层的数据报
  5. 链路层提供的服务
    1. 封装成帧 (framing)
    2. 链路访问
    3. 在相邻节点之间可靠交付
    4. 差错检查(error detection)
    5. 错误纠正(error correction)
    6. 流量控制(flow control)

5.2、差错检测与纠正

  1. 三种主要差错检测技术
    1. 奇偶校验：最基本的方法
    2. Internet校验和：常用于运输层
    3. 循环冗余检测：常用于链路层
  2. 奇偶校验
    1. 一比特奇偶校验
      • 偶校验：发现奇数个“1”，至少有一个比特发生差错（奇数个比特差错）
      • 奇校验：发现偶数个“1”，至少有一个比特发生差错
      • 可以查出任意奇数个错误，但不能发现偶数个错误
    2. 二维奇偶校验
      • 可以检测并纠正单个比特差错（数据或校验位中）
      • 能够检测(但不能纠正)分组中任意两个比特的差错
  3. 循环冗余检测CRC (cyclic redundancy check)
    1. 特点：能检测小于 r+1 位的突发差错、任何奇数个差错，长度大于r+1比特的突发差错以概率 1 -0. 5^r^ 被检测到

5.3、多路访问链路和协议

  1. 两种访问链路：

    1. 点对点链路：链路两端各一个节点。一个发送和一个接收。如点对点协议PPP
    2. 广播链路： 多个节点连接到一个共享的广播信道

  2. 冲突（collide）：两个以上的节点同时传输帧，使接收方收不到正确的帧（所有冲突的帧都受损丢失）

  3. 三类多路访问协议：

    1. 信道划分协议
      • 把信道划分为小“片” (时隙)
      • 给节点分配专用的小“片”
    2. 随机访问协议
      • 不划分信道，允许冲突
      • 能从冲突中“恢复”
    3. 轮流协议
      • 通过轮流访问信道避免冲突，要发送的节点越多轮流时间越长

  4. 信道划分协议

    1. 主要有TDMA、FDMA、CDMA三种
    2. 时分多路访问TDMA (time division multiple access)
      • 将时间划分为时间帧，每个时间帧再划分为N个时隙（长度保证发送一个分组），分别分配给N个节点。每个节点只在固定分配的时隙中传输
    3. 频分多路访问FDMA (frequency division multiple access)
      • 将总信道带宽 R b/s划分为 N 个较小信道（频段，带宽为R/N），分别分配给N 个节点
    4. 码分多路访问CDMA (frequency division multiple access)
      • 每个节点分配一个唯一的编码
      • 每个节点用它唯一的编码来对它发送的数据进行编码
      • 允许多个节点“共存” ，信号可叠加，即可以同时传输数据而无冲突

  5. 随机访问协议

    1. ALOHA

      1. 时隙ALOHA

        • 当节点有新的帧要发送，需等到下一个时隙开始，才传输整个帧
        • 无冲突：节点成功传输帧
        • 有冲突：节点检测到冲突后，以概率p在后续的每一个时隙重传该帧，直到成功

      2. 纯 ALOHA

        • 帧一到达，立即传输

        • 如果与其他帧产生冲突，在该冲突帧传完之后：

          • 以概率p立即重传该帧；

          • 或等待一个帧的传输时间，再以概率p 传输该帧，或者以概率1-p 等待另一个帧的时间

    2. CSMA（载波侦听多路访问）

      1. 载波侦听：某个节点在发送之前，先监听信道

    3. 带冲突检测的CSMA(CSMA/CD)

      1. 增加“载波侦听”和“冲突检测”两个规则

      2. 基本原理： 传送前侦听

        • 信道忙：延迟传送

        • 信道闲：传送整个帧

      3. 发送同时进行冲突检测：一旦检测到冲突就立即停止传输， 尽快重发

  6. 轮流协议

    1. 轮询(polling)协议
      • 主节点“邀请”从节点依次传送
    2. 令牌传递(token passing)协议
      • 控制令牌顺序从一个节点传递到下一个节点

  7. 多路访问控制协议的总结

    1. 信道划分：时分，频分，码分
    2. 随机接入：
      • ALOHA, S-ALOHA, CSMA, CSMA/CD
      • 载波侦听：在某些技术中容易实现(有线)，在有些技术中比较困难(无线)
      • CSMA/CD used in Ethernet
      • CSMA/CA used in 802.11
    3. 轮流
      • 来自中心站的轮询
      • 令牌传递

5.4、交换局域网（ARP）

  1. 局域网：Local Area Network ( LAN )

  2. 多址访问协议广泛应用于局域网

  3. 局域网按拓扑结构进行分类：星形网、环形网、总线网、树形网和网状网

  4. 基于随机访问的CSMA/CD广泛应用于局域网

  5. 链路层寻址和ARP

    1. 每个接口有网络层地址和链路层地址

    2. 链路层地址：MAC地址，用于把数据帧从一个节点传送到另一个节点(同一网络中)

    3. MAC地址

      1. 节点“网卡”本身所带的地址（唯一）
      2. MAC地址长度通常为6字节(48比特)，共2^48^个。 1A-2F-BB-76-09-AD
      3. 6字节地址用16进制表示，每个字节表示为一对16进制数
      4. 网卡的MAC地址是永久的
      5. MAC 地址是平面（扁平）结构带有同一网卡的节点，在任何网络中都有同样的MAC地址

    4. MAC地址识别

      1. 广播信道的局域网中，一个节点发送的帧，在信道上广播传输，其他节点都可能收到该帧
      2. 发送适配器：将目的MAC地址封装到帧中，并发送。所有其他适配器都会收到这个帧
      3. 接收适配器：检查帧的目的MAC地址是否与自己MAC地址相匹配：
        • 匹配：接收该帧，取出数据报，并传递给上层。
        • 不匹配：丢弃该帧
      4. 广播帧：发送给所有节点的帧 。全1地址：FF-FF-FF-FF-FF-FF

    5. 地址转换：主机名 → IP地址 → MAC地址

      • DNS域名系统：将主机名解析到IP地址。

        • DNS为在因特网中任何地方的主机解析主机名

      • ARP地址解析协议：将IP地址解析到MAC地址。

        • ARP只为在同一个LAN上的节点解析IP地址

  6. ARP：地址解析协议

    1. ARP表: 局域网上的每个节点(主机、路由器)都有这个表

      • 为某些局域网节点进行IP/MAC地址映射：**< IP address; MAC address; TTL>**
      • TTL (存活时间): 地址映射将被删除的时间（通常为20分钟）

    2. 查询过程：

      A 希望发送数据报给 B 但B的MAC地址不在A的ARP映射表中

      A广播包含B的IP地址的ARP查询分组

      ​ • 目的MAC地址= FF-FF-FF-FF-FF-FF

      ​ • 在局域网上的所有机器都能收到ARP查询

      ​ • 每个适配器把该帧中的ARP查询分组向上传递给ARP模块，并由ARP模块检查是否与查询IP匹配

      B收到ARP分组，回给A一个带有B的MAC地址的分组

      ​ • ARP响应分组单播发送给A的MAC地址

    3. ARP协议是跨越链路层和网络层两边的协议

  7. 以太网(Ethernet)

    1. 到目前为止，以太网是最为著名的有线局域网技术

    2. 物理拓扑结构：星形(star)目前流行

    3. 以太网帧结构：

      1. 前同步码（8字节）
        • 前7字节是“10101010”，最后一个字节是“10101011”。
        • 使接收方和发送方的时钟同步，接收方一旦收到连续的8字节前同步码，可确定有帧传过来。
        • 前同步码是“无效信号”，接收方收到后删除，不向上层传。
        • CRC的校验范围不包括前同步码
      2. 源、目的MAC地址(各6字节)
      3. 类型字段(2 字节)
        • 以太网可以“多路复用”（支持）多种网络层协议。通过“类型”字段区分
      4. 数据字段(46～1500 字节)
        • 以太网的最大传输单元MTU是1500字节
        • 若IP数据报超过1500字节，必须将该数据报分片
        • 最小长度是46字节
        • 如果IP数据报小于46字节，必须填充为46字节。接收方网络层去除填充内容
      5. 循环冗余检测CRC(4字节)
        • 接收主机进行CRC校验：接收主机对收到的帧校验。若计算结果，余数不等于0(CRC校验失败)，该帧有差错

  8. CSMA/CD:以太网的多路访问协议

    1. 未使用时隙：适配器可以在任何时刻开始传输

    2. 使用载波侦听：当一个节点要发送数据时，首先监听信道，看是否有载波。

      • 如果信道空闲，则发送数据。

      • 如果信道忙，则继续对信道进行监听（1－坚持CSMA）。一旦发现空闲，便立即发送

    3. 使用冲突检测：如果在发送过程中检测到碰撞，则停止自己的正常发送，转而发送一短暂的干扰信号jam，强化冲突，使其它站点都能知道出现了冲突

    4. 重传：发送了干扰信号后，退避一随机时间，重新尝试发送

    5. 基本后退时间：以512 比特时间为单位；

      ✓第n次冲突后退让时间：K × 512 比特时间

      K与冲突次数有关，是{ 0～2m-1}之间的一个随机整数。 m = min(n，10)

  9. 以太网向网络层提供的服务：

    1. 无连接服务
      1. 不可靠的服务
    2. 以太网的MAC协议：使用无时隙的CSMA/CD协议

5.5、链路层交换机

  1. 集线器Hub：集线器本质上是物理层的中继器

  2. 互联网络中所有的网段属于同一个冲突域

  3. 每个交换机有一个交换机转发表，其中每个条目：(主机的MAC地址，到达主机的端口，时戳)类似于路由表

  4. 通过自学习建立转发表中的条目

  5. 过滤(filtering)：交换机判断一个帧是应该转发到某个接口还是丢弃

  6. 转发(forward)：交换机决定一个帧应该被指向哪个接口，并引导到该接口

  7. 自学习：交换机会学习通过哪些端口可以到达哪些主机。即交换机表可以自动地、动态地和自主地建立

  8. 交换机是即插即用设备 (plug-and-play device)

  9. 路由器与交换机比较

    1. 两者都是存储转发设备:
      • 路由器: 网络层设备(检查网络层头部)
      • 交换机：链路层设备(检查链路层头部)
    2. 两者都有转发表
      • 路由器：使用路由算法计算转发表，基于IP地址转发
      • 交换机：通过洪泛、自学习来学习转发表，基于MAC地址转发

  10. 交换机优缺点：

    1. ✓即插即用：不需网络管理员干预；

      ✓较高的分组过滤和转发率：

      ✓拓扑结构为一棵生成树。

      ✓可能产生“广播风暴”：

      某台主机失控，并传输无穷的以太网广播帧流，交换机将转发所有这些帧，导致整个以太网的崩溃

5.6、VLAN虚拟局域网

  1. 支持VLAN的交换机允许经一个单一的物理局域网基础设施定义多个虚拟局域网
  2. 基于端口、MAC地址、IP地址、网络层协议等不同的方式划分 VLAN
  3. 基于端口的VLAN：
    1. 流量隔离: 来至端口1-8的流量，只能到达端口1-8
      • 每个VLAN形成独立的广播域
    2. 端口动态的分配: 一个端口可以由管理员动态的分配给一个VLAN，只需通过软件进行配置
    3. VLAN间的转发: 只能通过VLAN间的路由实现
      • 在实践中厂商把交换机加路由器包含在一台设备中，就是所谓的三层交换机
    4. 干线端口(trunk port): 用于在多个物理交换机之间交换帧