计算机网络-自顶向下

面试 计算机网络
计算机基础
发布日期:   2020-08-04
更新日期:   2022-03-27
文章字数:   26.6k
阅读时长:   95 分

计算机网络

计网复习笔记, 参考书籍为自顶向下.

计算机网络体系结构

这里的概念都比较散, 大多是一些计网的基础概念和整体知识的框架.

计算机网络的功能:

  1. 数据通信
  2. 资源共享
  3. 分布式处理
  4. 提高可靠性
  5. 负载均衡

计算机网络的分类(距离分):

  • 广域网 - 长距离通信, 几十千米到几千千米
  • 城域网 - 覆盖几个街区或城市
  • 局域网 - 短距离通信, 几十米到几千米
  • 个人区域网 - WPAN, 直径十米

传输类型分类: 广播式, 点对点

主机间的通信方式: C/S, P2P

协议: 定义了在两个或多个通信实体之间交换的报文格式和次序, 以及在报文传输和接收或其它事件方面所采取的动作.

三种交换方式的区别?

电路交换: 整个报文的比特流从源点连续的直达终点, 像在一个管道中传输. 包括建立连接, 传输数据和断开连接三个阶段. 最典型的电路交换网络是传统电话网络.

报文交换: 将整个报文转发到相邻节点, 全部存储下来, 查找转发表, 转发到下一个节点. 是存储-转发类型的网络.

分组交换: 将报文分组转发到相邻节点, 查找转发表, 转发到下一个节点. 也是存储-转发类型的网络. 网络核心是分组交换.

接入网络的三种方式:

  • 住宅接入: modem, xDSL, HFC

  • 公司: LAN

  • 无线接入: Wireless LAN, Wireless WAN

物理媒体:

  • 引导型: 带线的, 光纤, 双绞线, 同轴电缆
  • 非引导性: 波类的, 无线, 卫星

主要性能指标:

  1. 带宽(Bandwidth): 本来表示通信线路允许通过的信号频带范围, 但在计算机网络中, 带宽表示网络的通信线路所能 传送数据的能力, 是数字信道所能传送的”最高数据率”的同义词, 单位是比特/秒( b/s).

  2. 时延(Delay):

  3. 时延带宽积: 指发送端发送的第一个比特即将到达终点时, 发送端已经发送了多少个比特, 因此又称以比特为单位的链路长度, 即时延带宽积 = 传播时延 * 信道带宽.

    流量强度约为0时, 平均排队时延小, 趋于1时时延变大, 大于1时平均时延无穷大.

计算机网络提供的服务的三种分类:

  1. 面向连接服务与无连接服务

    在面向连接服务中, 通信前双方必须先建立连接, 分配相应的资源( 如缓冲区) , 以保证通信能正常进行, 传输结束后释放连接和所占用的资源. 因此这种服务可以分为连接建立, 数据传输和连接释放三个阶段. 例如TCP就是一种面向连接服务的协议. 在无连接服务中, 通信前双方不需要先建立连接, 需要发送数据时可直接发送, 把每个带有目的地址的包( 报文分组) 传送到线路上, 由系统选定路线进行传输. 这是一种不可靠的服务. 这种服务常被描述为”尽最大努力交付”(Best-Effort-Delivery), 它并不保证通信的可靠性. 例如 IP, UDP就是一种无连接服务的协议.

  2. 可靠服务和不可靠服务

    可靠服务是指网络具有纠错, 检错, 应答机制, 能保证数据正确, 可靠地传送到目的地. 不可靠服务是指网络只是尽晕正确, 可靠地传送, 而不能保证数据正确, 可靠地传送到目的地, 是一种尽力而为的服务. 对于提供不可靠服务的网络, 其网络的正确性, 可靠性要由应用或用户来保障. 例如, 用户收到信息后要判断信息的正确性, 如果不正确, 那么用户要把出错信息报告给信息的发送者, 以便发送者采取纠正措施. 通过用户的这些措施, 可以把不可靠的服务变成可靠的服务.

  3. 有应答服务和无应答服务

    有应答服务是指接收方在收到数据后向发送方给出相应的应答, 该应答由传输系统内部自动实现, 而不由用户实现. 所发送的应答既可以是肯定应答, 也可以是否定应答, 通常在接收到的数据有错误时发送否定应答. 例如, 文件传输服务就是一种有应答服务. 无应答服务是指接收方收到数据后不自动给出应答. 若需要应答, 则由高层实现. 例如, 对于WWW服务, 客户端收到服务器发送的页面文件后不给出应答.

网络分层:

层次划分是根据功能划分的, 与实现的方法无关. 譬如RIP协议是网络层协议, 但却是通过应用层和传输层来实现的.

五层协议

应用层 : 为特定应用程序提供数据传输服务, 例如 HTTP, DNS 等协议. 数据单位为报文.

传输层 : 为进程提供通用数据传输服务. 由于应用层协议很多, 定义通用的传输层协议就可以支持不断增多的应用层协议. 运输层包括两种协议: 传输控制协议 TCP, 提供面向连接, 可靠的数据传输服务, 数据单位为报文段, 用户数据报协议 UDP, 提供无连接, 尽最大努力的数据传输服务, 数据单位为用户数据报. TCP 主要提供完整性服务, UDP 主要提供及时性服务. ( 流量控制, 差错控制, 服务质量, 数据传输管理, 端到端)

网络层 : 为主机提供数据传输服务. 而传输层协议是为主机中的进程提供数据传输服务. 网络层把传输层传递下来的报文段或者用户数据报封装成分组. ( 流量控制, 拥塞控制, 差错控制, 网 际互联)

链路层 : 网络层针对的还是主机之间的数据传输服务, 而主机之间可以有很多链路, 链路层协议就是为同一链路的主机提供数据传输服务. 数据链路层把网络层传下来的分组封装成帧. ( 封装成帧, 差错控制, 流量控制, 传输管理)

物理层 : 考虑的是怎样在传输媒体上传输数据比特流, 而不是指具体的传输媒体. 物理层的作用是尽可能屏蔽传输媒体和通信手段的差异, 使数据链路层感觉不到这些差异.

OSI(七层协议)

表示层 : 数据压缩, 加密以及数据描述, 这使得应用程序不必关心在各台主机中数据内部格式不同的问题.

会话层 : 建立及管理会话.

五层协议没有表示层和会话层, 而是将这些功能留给应用程序开发者处理.

端到端: 端到端通信建立在点到点通信的基础上, 它是由一段段的点到点通信信道构成的, 是比点到 点通信更高一级的通信方式, 以完成应用程序( 进程) 之间的通信. “端” 是指用户程序的端口, 端口号标识了应用层中不同的进程.

点到点: 直接相连的结点之间的通信称为点到点通信, 它只提供一台机器到另一台机器之间的通信, 不涉及程序或进程的概念. 同时, 点到点通信并不能保证数据传输的可靠性, 也不能说明源主机与目的主机之间是哪两个进程在通信, 这些工作都是由网络层来完成的.

应用层

应用层讲解了与用户距离最近的网络应用, 网络应用才是计算机网络存在的原因. 应用层传输数据的单位是报文(message).

HTTP 超文本传输协议

WEB网页是由一些对象该组成的, HTML文件涵盖了网页源码, 其中就包括其他媒体流文件对象的链接. 每个对象都能通过URL进行标识.

www.someschool.edu/someDept/pic.gif

HTTP(HyperText Transfer Protocol, 超文本传输协议): HTTP定义了浏览器(万维网客户进程) 怎样向万维网服务器请求万维网文档, 以及服务器怎样把文档传送给浏览器. 从层次的角度看, HTTP 是面向事务的(Transaction-oriented) 应用层协议, 它规定了在浏览器和服务器之间的请求和响应的格式与规则, 是万维网上能够可靠地交换文件( 包括文本, 声音, 图像等各种多媒体文件) 的重要基础.

HTTP使用TCP, 端口号80, 也是无状态的(不保存用户过去的使用信息, Cookie可以解决). 有持久和非持久连接方式. 不同连接方式下所需传输文件的时间必定是不一样的. 定义了往返时延作为衡量标准.

往返时延RRT的定义: 从客户机到服务器发送一个小分组并返回所历经的时间.

假设当前网页有1个HTML对象, 3个JPG对象, 1个Audio对象, 共计5个对象.

非持久: 每个对象都建立连接, 然后再传输.

持久 - 非流水线: 先建立一次连接, 之后串行地传输每个对象, 超时关闭.

持久 - 流水线: 建立连接后, 并行的传输每个对象, 并认为所有对象发送时间约为1个RTT. 但是必须先传输HTML对象, 所以多个对象传输也可以认为总共是3个RTT. 超时关闭.

连接方式所需RTT公式
非持久5 * 2 RTT = 10 RTT2n RTT
持久 - 非流水线(5 + 1)RTT = 6 RTT(n + 1) RTT
持久 - 流水线2 / 3 RTT2 / 3 RTT

请求头:

响应头:

FTP 文件传输协议

FTP(File Transfer Protocol, 文件传输协议): C/S模式的文件传输协议, 因为控制端口和数据端口不是在一起, 所以实现了带外传输. 采用的是TCP协议.

控制端口: 21

数据端口: 20

过程:

  1. 客户机通过控制连接获得授权
  2. 客户机经控制连接通过发送命令浏览远程目录
  3. 当服务器接收到一个文件传输命令时, 该服务器打开到客户机的一个数据连接
  4. 在传输一个文件后, 服务器关闭连接

电子邮件协议

电子邮件协议主要有SMTP, POP3, IMAP.

电子邮件主要由三个部分组成: 用户代理, 邮件服务器, 邮件传输协议.

用户代理: 也叫作邮件阅读器. 用户查看电子邮件就用的是这种应用程序.

邮件服务器: 用户邮件的信息托管在邮件服务器上, 也同样负责用户邮件的发送(通过一个发送队列实现).

邮件传输协议: 邮件服务器见传输邮件通过邮件传输协议来规定格式.

SMTP

简单邮件传输协议(Simple Mail Transfer Protocol, SMTP) 是一种提供可靠且有效的电子邮件传输的协议, 它控制两个相互通信的SMTP 进程交换信息. 由于SMTP 使用客户／服务器方式, 因此负责发送邮件的SMTP 进程就是SMTP 客户, 而负责接收邮件的SMTP 进程就是SMTP 服务器. SMTP 用的是TCP 连接, 端口号为25.

  1. Alice使用UA写作报文并向 bob@someschool.edu发送.
  2. Alice的UA向其邮件服务器发送报文, 报文放置在报文队列中.
  3. SMTP的客户机侧打开与Bob的邮件服务器的TCP连接.
  4. SMTP通过TCP连接发送Alice的报文.
  5. Bob的邮件服务器将该报文放入Bob的邮箱.
  6. Bob调用其用户代理来读报文.

通信三阶段:

  • 握手
  • 报文传输
  • 关闭

交互实例:

S: 220 hamburger.edu
C: HELO crepes.fr
S: 250 Hello crepes.fr, pleased to meet you
C: MAIL FROM: alice@crepes.fr
S: 250 alice@crepes.fr… Sender ok
C: RCPT TO: bob@hamburger.edu
S: 250 bob@hamburger.edu … Recipient ok
C: DATA
S: 354 Enter mail, end with “.” on a line by itself
C: Do you like ketchup?
C: How about pickles?
C: .
S: 250 Message accepted for delivery
C: QUIT
S: 221 hamburger.edu closing connection

由于SMTP比较早, 不能兼容国内的文字和其他多媒体流. 报文必须以7比特ASCII格式.

SMTP与HTTP的异同:

属性HTTPSMTP
协议TCPTCP
端口号8025
推拉拉推
对象封装每个对象用响应报文分别封装所有对象封装成一个响应报文
限制没有报文限制必须用7位ASCII格式

邮件报文格式:

—首部行—

TO:

From:

Subject:

—主体—

Body:

MIME: 多媒体邮件扩展, 能采用多种编码格式和编码数据的方法.

POP3

POP3直接看一个例子:

— 特许阶段 — 对用户信息进行认证

S: +OK POP3 服务器 ready
C: user bob
S: +OK
C: pass hungry
S: +OK user successfully logged on

— 事务阶段 — 用简单的命令执行操作

C: list
S: 1 498 -> content length
S: 2 912
S: .
C: retr 1
S: <message 1 contents>
S: .
C: dele 1
C: retr 2
S: <message 1 contents>
S: .
C: dele 2
C: quit
S: +OK POP3 服务器 signing off

— 更新阶段 — 用户离线后, 服务器进行内容更新

POP3有Download and delete和Download and keep两种模式, 当Download and delete时, 阅读完内容后会在服务器中删除. Download and keep时, 每次阅读都会下载所有的邮件到本地, 不删除邮箱内容.

IMAP

IMAP把所有的报文信息都保存在服务器上, 并允许用户组织文件夹. 保存文件夹名和报文ID和文件夹名之间的映射.

DNS

DNS(Domain Name System): 域名解析是指把域名映射成为IP 地址或把IP 地址映射成域名的过程. 前者称为正向解析, 后者称为反向解析. 当客户端需要域名解析时, 通过本机的DNS 客户端构造一个DNS 请求报文, 以UDP数据报方式发往本地域名服务器. DNS是由分布式数据库实现的, 集中式DNS容易产生单点故障, 而且不利于维护, 当查询量很大的时候也不能进行负载分配. 端口号53, 书中唯一一个UDP协议的应用.

等级制数据库的DNS查询过程:

假设客户机要求www.amazon.com 的IP地址:

  1. 客户机请求根服务器以发现com DNS服务器
  2. 客户机请求com DNS服务器以得到 amazon.com DNS 服务器
  3. 客户机请求amazon.com DNS服务器以得到对 www.amazon.com的IP地址

分布式DNS服务器:

  • 根名字服务器: 当本地名字服务器不能分解名字时联系它, 如果名字映射未知, 联系权威名字服务器.
  • 顶级域服务器: 负责com, org, net, edu等, 以及所有顶级国家域 uk, fr, ca, jp.
  • 权威DNS服务器: 组织的DNS 服务器为组织的服务器(如Web和电子邮件)提供对IP映射的权威主机名. 能够由组织或服务提供商维护.
  • 本地名字服务器: 并不严格属于等级结构, 当主机发出DNS请求时, 请求被发送到其本地名字服务器, 作为代理, 将请求转发到等级结构.

DNS查询方式:

  • 递归请求: 搜索上类似与DFS, “我不知道该名字, 但我可以帮你问问别的服务器”. 会带来沉重的查询负担.
  • 迭代请求: 搜索上类似与BFS, “我不知道该名字, 但你应该问问这个服务器”.

应用层APP的协议和端口号:

ProtocolPort numberTransport layer protocol
HTTP80TCP
FTP21(control)/20(data)TCP
SMTP25TCP
POP3110TCP
IMAP143TCP
DNS53UDP

传输层

传输层已经对上一层, 也就是应用层传输过来的报文进行第二层封装(抽象), 为进程提供通用数据传输服务. 从通信和信息处理的角度看, 传输层向它上面的应用层提供通信服务, 它属于面向通信部分的最高层, 同时也是用户功能中的最低层. 传输层位于网络层之上, 它为运行在不同主机上的进程之间提供了逻辑通信, 而网络层提供主机之间的逻辑通信. 显然, 即使网络层协议不可靠( 网络层协议使分组丢失, 混乱或重复) , 传输层同样能为应用程序提供可靠的服务. 对应的传输层协议就只有两个, TCP和UDP. 在传输层, 传输数据所用的单位是报文段(segment).

传输层的功能:

  1. 传输层提供应用进程之间的逻辑通信( 即端到端的通信) . 与网络层的区别是, 网络层提供的是主机之间的逻辑通信. 从网络层来说, 通信的双方是两台主机, IP 数据报的首部给出了这两台主机的IP地址. 但”两台主机之间的通信”实际上是两台主机中的应用进程之间的通信, 应用进程之间的通信又称端到端的逻辑通信.
  2. 复用和分用. 复用是指发送方不同的应用进程都可使用同一个传输层协议传送数据, 分用是指接收方的传输层在剥去报文的首部后能够把这些数据正确交付到目的应用进程.
  3. 传输层还要对收到的报文进行差错检测( 首部和数据部分) . 而网络层只检查IP 数据报的首部, 不检验数据部分是否出错.
  4. 提供两种不同的传输协议, 即面向连接的TCP 和无连接的UDP . 而网络层无法同时实现两种协议( 即在网络层要么只提供面向连接的服务, 如虚电路, 要么只提供无连接服务, 如数据报, 而不可能在网络层同时存在这两种方式) .

多路复用和多路分解:

  • 多路复用: 从源主机的不同socket中收集数据块, 并为每个数据块封装上首部信息从而生成报文段, 将报文段传递到网络层的工作.
  • 多路分解: 将运输层报文段中的数据交付到正确的socket的工作.

套接字就像门一样, 不同的进程有不同的套接字. 进程从/来自它的套接字发送/接收报文.

标识套接字唯一的方法:

UDP套接字: 目的地IP地址, 目的地端口号组成的二元组.

TCP套接字: 源IP地址, 源端口号, 目的IP地址, 目的端口号组成的四元组.

无论是UDP还是TCP, 报文段结构都有16位源端口, 16位目的端口.

IP地址从在哪获取呢? 报文段中并没有包含IP相关的内容. 但不要忘记多路复用和多路分解, 在多路分解时数据是由网络层以数据报形式往上传输的, 在去掉封装的头部后传输层一定能够知道源IP和目标IP.

UDP

UDP(用户数据报协议):

  1. UDP 无须建立连接. 因此UDP 不会引入建立连接的时延. 试想如果DNS 运行在TCP 而非UDP 上, 那么DNS 的速度会慢很多. HTTP 使用TCP 而非UDP, 是因为对于基于文本数据的Web网页来说可靠性是至关重要的
  2. 无连接状态. TCP 需要在端系统中维护连接状态. 此连接状态包括接收和发送缓存, 拥塞控制参数和序号与确认号的参数. 而UDP 不维护连接状态, 也不跟踪这些参数. 因此, 某些专用应用服务器使用UDP 时, 一般都能支持更多的活动客户机.
  3. 分组首部开销小. TCP 有20B 的首部开销, 而UDP 仅有8B(32*2bit/8)的开销.
  4. 应用层能更好地控制要发送的数据和发送时间. UDP 没有拥塞控制, 因此网络中的拥塞不会影响主机的发送效率. 某些实时应用要求以稳定的速度发送, 能容忍一些数据的丢失, 但不允许有较大的时延, 而UDP 正好满足这些应用的需求. UDP 常用于一次性传输较少数据的网络应用如 DNS , SNMP 等, 因为对千这此应用, 若采用TCP, 则将为连接创建, 维护和拆除带来不小的开销. UDP 也常用于多媒体应用( 如IP 电话, 实时视频会议, 流媒体等) , 显然, 可靠数据传输对 这些应用来说并不是最重要的, 但TCP的拥塞控制会导致数据出现较大的延迟, 这是它们不可容忍的.

UDP 提供尽最大努力的交付, 即不保证可靠交付, 但这并不意味着应用对数据的要求是不可靠的, 因此所有维护传输可靠性的工作需要用户在应用层来完成. 应用实体可以根据应用的需求来灵活设计自己的可靠性机制. 所以UDP常应用在对丢包率可以容忍, 对速率敏感的应用, 即使发生很小一部分的丢包, 仍然不影响用户的体验.

报文段结构:

除了TCP/UDP必备的源端口和目的端口号, UDP有检查和. 检查和能够在传输的报文段中检测一位比特的差错. 发送方将报文段所有内容分批处理多个16位的整数序列, 逐一加和, 进行回卷, 最后取反.

检查和:

接收方也计算和, 看与发送方告诉自己的检查和累加后是否为1111 1111 1111 1111, 如果是的话说明没有检测出错误(检查和并不能检测到所有错误), 如果不是则说明存在错误.

可靠数据传输

可靠数据传输是后面TCP协议能够支持可靠性的设计依据. IP在网络层一定是不可靠的, 为什么说UDP/IP是不可靠的, 而TCP/IP就可靠了? 正是因为下层的传输的不可靠, 所以我们可以通过上层的可靠传输协议来淘汰甚至纠正不可靠的数据. 当然可靠一定伴随着代价, 也就是时间开销和资源开销.

可靠象征着接收到的字节流是完整, 无差错, 有序的. (TCP和UDP都没有保证最低的传输速率!)

Rdt1.0

仅考虑理想化的, 无比特错误, 无丢包. 接收方完全不需要其他额外数据.

Rdt2.0

假设在分组的传输, 传播或缓存过程中具有比特差错, 但无丢包.

  • 解决方法: ARQ协议( 自动重传请求) , 用以下3种协议来处理
    1. 差错检测( 接收方) : 检验和
    2. 反馈
      • 接收方—>确认: 告诉发送方数据包有无错误, 返回肯定应答ACK 与否定应答NAK
      • 发送方—>决定下一步动作
    3. 重传( 发送方) : 发送方重发
  • 与之类似的协议被称为: 停止等待协议(只有发送成功, 才发送给下一个分组, 否则一直重复)

Rdt2.1

在Rdt2.0的基础上, 考虑ACK与NAK本身出现错误的情况.

  • 无其它动作: 无法解决.
  • 增加足够的比特, 发送方可检错与纠错.
  • 当不能确认是ACK还是NAK时, 发送方重发: 引入冗余分组, 接收方混淆？
  • 解决方法: 加入1bit序号(sequence number), 因为发送是交替进行的, 所以引入0和1两个数字就能说明发包的顺序.

Rdt2.2

无NAK的可靠数据传输协议, 用冗余的ACK来代替了多余的NAK. 从逻辑角度来想, 冗余ACK就代表了发送方没有收到接收方接收的响应, 那么一定是出了问题, 也就是NAK的作用.

  • 接收方必须包括由一个ACK报文确认的分组序号, 即对上次正确接收的分组的ACK.

Rdt3.0

不光考虑Rdt2.0比特差错的基础上, 还考虑底层信道的丢包.

  • 定时器( 倒计数器)
    • 时间值: RTT+时延
    • 发送后, 启动定时器
    • 响应定时器中断
    • 终止定时器
  • 功能正确的协议
  • 使用检验和, 序号, 肯定和否定确认, 定时器技术
  • 效率低下(停止等待协议需要等待对方应答才能发下一个, 这个空闲时间很长, 就导致了时间上的利用率非常低, 后面通过流水线协议提升了效率)
无丢包时的运行
分组丢失

因为发送分组1时发生了丢失, 在计时器期间没收到接收方的应答. 计时器超时了, 所以发送方再次发送相同的分组1.

ACK丢失

因为接收方对发送方分组1的ACK丢失了, 发送方在计时器时间内迟迟等不来响应, 超时后发送方重发.

过早超时

在发送分组1后, 可能因为网速的原因, 接收方给发送方的ACK比较晚的到达了. 接收方接收到两次相同的冗余分组, 也就是说发送方有不必要的重传. 如果某个报文段的发送过程被延迟较长时间但并未丢失, 这种情况叫做过早超时.

流水线协议

在Rdt3.0中知道, 其效率是十分低下的. 原因就是发送方必须等待接收方的响应才能继续发送下一个分组. 为什么必须要等待响应才能发下一个分组呢? 如果连续发一串分组出去就能提升效率了, 但是要增加一些资源开销, 比如说要区分分组发出去的先后顺序必须要扩大序号的范围, 而且考虑到接收方处理分组的速度之间的差异, 必须在接收方和发送方之间引入缓冲区. 还要考虑发送方可能发送非按序到达的数据的问题.

为解决上述基本问题, 引入了两种方法, 分别是GBN(Go-Back-N, 滑动窗口协议)和SR(选择重传).

Go-Back-N
  • 允许发送多个分组而不需要等待确认, 受限于窗口长度N.
  • 累积确认: 接收方返回的ACK号代表的含义是”该号和该号之前的分组已经成功收到“.
  • 窗口共享计时器, 当最早发出去未被响应的分组超时则重传所有分组.
  • 数据按序交付, 失序则丢弃.
  • 回退机制:
    • 表示需要再退回来重传已发送过的 N 个分组
    • 当通信线路质量不好和N过大时, 连续 ARQ 协议会带来负面影响

当pkt2发生丢失时, 接收方一直收到了乱序的pkt, 所以一直在不停的返回ACK1, 即”ACK1和ACK1以前的分组我已经收到了!”, 希望接收方发送ACK2. 之后收到的乱序pkt3, pkt4, pkt5全都被丢弃, 直到pkt2被发送方重新补上, 才继续发送下去.

Selective Repeat

GBN改善了信道效率, 但仍然有不必要重传问题. 与GBN风格不同, 针对每个不同的分组都有不同的计时器和确认.

  • 窗口长度必须小于或等于序号空间大小的一半
  • 逐一确认
  • 只重发未被确认的分组(发送方定时器对每个没有确认的分组计时)
  • 失序缓存, 但最终仍是按序交付

可靠数据传输机制及用途总结

机制用途和说明
检验和用于检测在一个传输分组中的比特错误.
确认接收方用于告诉发送方一个分组或一组分组已被正确地接收到了. 确认报文通常携带着被确认的分组或多个分组的序号. 确认可以是逐个的或累积的, 这取决于协议.
序号用于为发送的数据分组进行按序编号. 所接收分组的序号间的空隙可使接收方检测出丢失的分组. 具有相同序号的分组可使接收方检测出一个分组的冗余拷贝.
定时器用于检测超时/重传一个分组, 可能因为该分组( 或其ACK) 在信道中丢失了. 由于当一个分组被时延但未丢失( 过早超时) , 或当一个分组已被接收方收到但从接收方到发送方的ACK丢失时, 可能产生超时事件, 所以接收方可能会收到一个分组的多个冗余拷贝.
窗口, 流水线 GO-BACK-N Selective Repeat发送方也许被限制仅发送那些序号落在一个指定范围内的分组. 通过允许一次发送多个分组但未被确认, 发送方的利用率可在停等操作模式的基础上得到增加. 我们很快将会看到, 窗口长度可根据接收方接收和缓存报文的能力或网络中的拥塞程度, 或两者情况来进行设置.

TCP

在看完可靠数据传输后, 再去理解TCP就不困难了. TCP 是在不可靠的IP 层之上实现的可靠的数据传输协议, 它主要解决传输的可靠, 有序, 无丢失和不重复问题. TCP 是TCP/IP 体系中非常复杂的一个协议, 它更像是GBN和SR的混合体, 主要特点如下:

  1. TCP 是面向连接的传输层协议

  2. 每条TCP 连接只能有两个端点, 每条TCP 连接只能是点对点的( 一对一) .

  3. TCP 提供可靠的交付服务, 保证传送的数据无差错, 不丢失, 不重复且有序.

  4. TCP 提供全双工通信, 允许通信双方的应用进程在任何时候都能发送数据, 为此TCP 连接的两端都设有发送缓存和接收缓存, 用来临时存放双向通信的数据.

    发送缓存用来暂时存放以下数据:

    • 发送应用程序传送给发送方TCP 准备发送的数据

    • TCP 已发送但尚未收到确认的数据

    接收缓存用来暂时存放以下数据:

    • 按序到达但尚未被接收应用程序收取的数据
    • 不按序到达的数据

重传在TCP中, 当产生超时事件或者重复ACK才会被触发. 并像GBN一样采用单个重传计时器.

序号和确认号

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

确认号(ACK): 期望从对方收到下一个字节的序号, 且是累计应答. 即”我希望你下一次发从这个号开始的分组“.

捎带确认: 确认号被装载在服务器到客户机的数据的报文段中.

对于失序的报文段, TCP没有明确指出, 应该是根据不同情况而定的.

报文段结构

头部一共32*5/8 = 20bytes, 比UDP的8bytes冗长很多.

传输过程

  1. 从应用层接收数据:
    • 根据序号创建报文段
    • 序号是报文段中第一个数据字节的数据流编号
    • 如果未启动, 启动计时器 (考虑计时器用于最早的没有确认的报文段)
  2. 超时
    • 重传导致超时的报文段
    • 重新启动计时器
  3. 收到确认
    • 如果确认了先前未被确认的报文段, 更新被确认的报文段序号, 如果还有未被确认的报文段, 重新启动计时器

ACK产生

接收方事件TCP接收方行为
所期望序号的报文段按序到达. 所有在期望序号及以前的数据都已经被确认延迟的ACK. 对另一个按序报文段的到达最多等待500 ms. 如果下一个按序报文段在这个时间间隔内没有到达, 则发送一个ACK
有期望序号的报文段按序到达. 另一个按序报文段等待发送ACK立即发送单个累积ACK, 以确认两个按序报文段
比期望序号大的失序报文段到达, 检测出数据流中的间隔.立即发送冗余ACK, 指明下一个期待字节的序号( 也就是间隔的低端字节序号)
部分或者完全填充已接收到, 数据间隔的报文段到达倘若该报文段起始于间隔的低端, 则立即发送ACK

重传情况

丢失确认

主机B发送的ACK丢失, 超时后主机A重传丢失的Seq=92分组.

过早超时

主机A在重传Seq=92分组后, 分别收到了ACK=100和ACK=120, 累计确认, 更新了应该发送的起始序号. 下次发送从Seq=120开始.

累计确认

主机B响应的ACK=100丢失, 但是主机B已经收到了120以前的所有分包. 当主机A收到ACK=120时, 代表120号之前的分组主机B已经收到, 虽然没有ACK=100的响应但也无妨(累计确认). 所以下次发送新分组应该是Seq=120.

快速重传

因为超时间隔常常相对较长, 重传丢失报文段以前有长时延. 所以引入快速重传, 如果对相同数据, 发送方收到3个重复ACK, 假定被确认的报文段以后的报文段丢失了. 在定时器超时之前就能重传.

流量控制

为了解决发送方和接收方在速度上的不匹配, 在发送方和接收方都各自设计了缓冲区. 发送方不能发送太多, 太快的数据让接收方缓冲区溢出. 接收方在报文段接收窗口字段中通告其接收缓冲区的剩余空间.

缓冲区的剩余空间(也叫接收窗口 RcvWindow):
$$
\rm RcvWindow = RcvBuffer-[LastByteRcvd - LastByteRead]
$$
只要接收方的总Buffer的承载能力超过接收方已经确认的数据就能保证接收方缓冲区不溢出.

连接管理

三次握手, 四次挥手. 面试巨高频考点. 连接管理就是TCP为什么是面向连接的协议的原因.

三次握手
  1. 客户机的TCP 首先向服务器的TCP 发送一个连接请求报文段. 这个特殊的报文段中不含应用层数据, 其首部中的SYN标志位被置为1 . 另外, 客户机会随机选择一个起始序号seq = x( 连接请求报文不携带数据, 但要消耗一个序号) .
  2. 服务器的TCP 收到连接请求报文段后, 如同意建立连接, 就向客户机发回确认, 并为该 TCP 连接分配TCP 缓存和变量. 在确认报文段中, SYN 和ACK 位都被置为1, 确认号字段的值为 x + 1, 并且服务器随机产生起始序号seq= y( 确认报文不携带数据, 但也要消耗一个序号) . 确认 报文段同样不包含应用层数据.
    • 这里大写的ACK和小写的ack, 其中一个是确认值, 当ACK为1时代表确定连接. 还有一个ack是确认编号, 响应seq = x + 1.
  3. 当客户机收到确认报文段后, 还要向服务器给出确认, 并且也要给该连接分配缓存和变量. 这个报文段的ACK 标志位被置1, 序号字段为x+ 1, 确认号字段ack=y+ 1 . 该报文段可以携带数据, 若不携带数据则不消耗序号.

成功进行以上三步后, 就建立了TCP 连接, 接下来就可以传送应用层数据. TCP 提供的是全双工通信, 因此通信双方的应用进程在任何时候都能发送数据. 另外, 值得注意的是, 服务器端的资源是在完成第二次握手时分配的, 而客户端的资源是在完成第三次握手时分配的, 这就使得服务器易于受到SYN 洪泛攻击.

为什么不采用”两次握手”建立连接呢？

这主要是为了防止两次握手情况下已失效的连接请求报文段突然又传送到服务器而产生错误. 考虑下面这种情况. 客户A 向服务器B 发出TCP 连接请求, 第一个连接请求报文在网络的某个结点长时间滞留, A 超时后认为报文丢失, 千是再重传一次连接请求, B 收到后建立连接. 数据传输完毕后双方断开连接. 而此时, 前一个滞留在网络中的连接请求到达服务器B, 而B 认为A 又发来连接请求, 此时若使用”三次握手”, 则B 向A 返回确认报文段, 由于是一个失效的请求, 因此A 不予理睬, 建立连接失败. 若采用的是”两次握手”, 则这种情况下B 认为传输连接已经建立, 并一直 等待A 传输数据, 而A 此时并无连接请求, 因此不予理睬, 这样就造成了B的资源白白浪费.

四次挥手
  1. 客户机打算关闭连接时, 向其TCP 发送一个连接释放报文段, 并停止发送数据, 主动关闭TCP 连接, 该报文段的FIN 标志位被置1, seq= u, 它等于前面已传送过的数据的最后一个字节的序号加1 (FIN 报文段即使不携带数据, 也要消耗一个序号) . TCP 是全双工的, 即可以想象为一条TCP 连接上有两条数据通路. 发送FIN 报文时, 发送FIN 的一端不能再发送数据, 即关闭了其中一条数据通路, 但对方还可以发送数据.
  2. 服务器收到连接释放报文段后即发出确认, 确认号是ack = u + 1, 而这个报文段自己的序号是V, 等于它前面已传送过的数据的最后一个字节的序号加1 . 此时, 从客户机到服务器这个方向的连接就释放了, TCP 连接处于半关闭状态. 但服务器若发送数据, 客户机仍要接收, 即从服务器到客户机这个方向的连接并未关闭.
  3. 若服务器已经没有要向客户机发送的数据, 就通知TCP 释放连接, 此时其发出FIN= 1 的连接释放报文段.
  4. 客户机收到连接释放报文段后, 必须发出确认. 在确认报文段中, ACK 字段被置为1, 确认号ack= w + 1, 序号seq= u + 1 . 此时TCP 连接还未释放, 必须经过时间等待计时器设置的时间 2MSL 后, A 才进入连接关闭状态.

为何不采用”三次握手”释放连接, 且发送最后一次握手报文后要等待2MSL 的时间呢？

原因有两个:

  1. 保证A 发送的最后一个确认报文段能够到达B . 如果A 不等待2MSL, 若A 返回的最后确认报文段丢失, 则B 不能进入正常关闭状态, 而A 此时已经关闭, 也不可能再重传.
  2. 防止出现”已失效的连接请求报文段”. A 在发送最后一个确认报文段后, 再经过2MSL可保证本连接持续的时间内所产生的所有报文段从网络中消失.

服务器结束TCP 连接的时间要比客户机早一些, 因为客户机最后要等待2MSL 后才可进入CLOSED状态.

Summary

三次握手:

  1. SYN = 1, seq = x
  2. SYN = 1, ACK = 1, seq = y, ack = x + 1
  3. ACK = 1, seq = x + 1, ack = y + 1

四次挥手:

  1. FIN = 1, seq = u
  2. ACK = 1, seq = v, ack = u + 1
  3. FIN = 1, ACK = 1, seq = w, ack = u + 1
  4. ACK = 1, seq = u + 1, ack = w + 1

拥塞控制

某段时间, 若对网络中某资源的需求超过了该资源所能提供的可用部分, 即现有的负荷超过了网络能够承受的最大负荷, 太多的源发送太多太快的数据, 使网络来不及处理, 产生拥塞(congestion). 不同于流量控制. 经常导致丢包(路由器缓冲区溢出)和高延迟(路由器缓冲区中排队). 拥塞控制是一个全局性的过程, 涉及到所有的主机, 所有的路由器, 以及与降低网络传输性能有关的所有因素.

控制拥塞有两种方法:

  • 端到端的拥塞控制: 不能从网络得到明确的反馈, 从端系统根据观察到的时延和丢失现象推断出拥塞.
  • 网络辅助的拥塞控制: 路由器为端系统提供反馈.

TCP采用的是端到端的拥塞控制.

设置一个拥塞窗口ConWin, 通过拥塞窗口来限制发送方的传输:
$$
\rm LastByteSent-LastByteAcked \leq CongWin
$$
当然这个拥塞窗口是动态的, 应该根据感知到的网络拥塞情况进行调整. 也就是当发生丢失时间, 即超时或3次冗余确认时降低拥塞窗口大小.

通过三个机制来调整拥塞窗口:

  • AIMD - 加增倍减
  • 慢启动
  • 超时事件后的保守机制
AIMD 乘性减, 加性增
  • 乘性减: 丢包事件后, 拥塞窗口值减半
  • 加性增: 如没有检测到丢包事件, 每个RTT时间拥塞窗口值增加一个MSS (最大报文段长度)
慢启动

当连接开始的时候, 速率呈指数式上升, 直到第1次报文丢失事件发生为止.

超时事件后的保守机制

基本思想是3个冗余ACK指示网络还具有某些传送报文段的能力, 那么3个冗余ACK以前的超时,则更为”严重”.

收到3个冗余确认后:

  • $\rm CongWin$减半
  • 窗口再线性增加

超时事件以后:

  • $\rm CongWin$值设置为1 MSS
  • 窗口再指数增长
  • 到达一个阈值 (Threshold) 后, 再线性增长

在丢包事件发生时, 阈值$\rm Threshold$设置为发生丢包以前的拥塞窗口的一半, 这样能够减轻网络压力, 到达一个相对原来比较低的阈值后线性增加.

图中先是慢启动, 在$\rm TTR$为4时到达阈值, 从指数型增长变为线性增长, 在$\rm TTR$为9时下方蓝线超时事件, 拥塞窗口置1, 阈值减半, 重新指数增加, 到达阈值后线性增加. 上方黑线发生的是3次冗余确认, 拥塞窗口减半, 之后线性增加.

拥塞控制小结:

  • 当$\rm CongWin < Threshold$时, 发送者处于慢启动阶段, $\rm CongWin$指数增长.

  • 当$\rm CongWin > Threshold$时, 发送者处于拥塞避免阶段, $\rm CongWin$线性增长.

  • 当出现3个冗余确认时, 阈值Threshold设置为$\rm CongWin/2$, 且$\rm CongWin$设置为$\rm Threshold$.

  • 当超时发生时, 阈值$\rm Threshold$设置为$\rm CongWin/2$, 并且$\rm CongWin$设置为1 MSS.

TCP和UDP比较

比较项TCPUDP
套接字四元组二元组
连接及状态需要建立, 有状态无需建立连接, 无状态
拥塞控制, 流量控制有无, 流量不可调节
分组首部开销20字节(大)8字节(小)
应用层对发送的数据和发送时间不可控制可控制
服务原则可靠交付尽力交付
传送的数据单位报文段, 大小可变报文, 大小不变
协议类型点对点协议可支持一对一, 一对多, 多对一和多对多
差错检测手段校验和: 出错重传校验和: 丢弃
应用层协议SMTP, TELNET, FTP, HTTP, VoIPDNS, SNMP, RIP, VoIP

网络层

网络层是对传输层协议的数据进行进一步封装(抽象). 无视传输层的具体内容, 以数据报(datagram)作为单位传输. 网络层研究的就是, 我知道A到B主机要传信息, 但是怎么传最好的问题. 涉及转发, 路径选择等算法. 网络层负责完成的是主机到主机间, 也就是点到点之间的通信. 实现也全是在网络内部实现的, 当IP数据报通过路由器时, 路由器检查只所有数据报的首部字段.

转发: 微观上的, 一个分组从一条入链路到一台路由器中的出链路的传送, 是路由器的本地动作.

选路: 宏观上的, 分组从发送方流向接收方时, 网络层决定分组从源到目的地节点所采用的路径. 涉及到一个网络中的所有路由器, 它们经选路协议共同交互才能完成.

Internet采用的是数据报网络, 其网络层服务模型是尽力而为的. 没有任何的顺序, 带宽, 丢失保证. 但其他协议譬如ATM, 帧中继, X.25因为使用了虚电路, 从一定程度上保证了传输的稳定性.

虚电路和数据报网络

数据报网络能提供网络层的无连接服务, 而虚电路可以提供连接服务.

虚电路

虚电路名字的由来是”源到目的地路径与电话电路行为非常相似”, 其性能是明确的, 并且一定是沿着源到目的地路径的网络动作.

在数据流动之前, 先建立呼叫, 然后在结束时拆除. 在源到目的地路径上的每台路由器为每条经过的连接维护维护状态, 链路, 路由器资源(带宽, 缓存)可能分配给VC.

VC组成:

  • 源和目的主机之间的路径(由一系列链路和路由器组成)
  • VC号(VC号是标识沿路径每条链路的号码)
  • 沿路径路由器中转发表中的项

虚电路的分组的首部会携带一个VC号, 因为一条虚电路在每条链路上的VC号可能不同, 所以每次经过新的路由器, 都会分配一个新的VC号来代替原来的VC号, 新的VC号是从新的转发表中获得的.

虚电路路由器维护的转发表形式和下表类似, 上图网络中西北处路由器的转发表为:

入接口入VC#出接口出VC#
112222
263118
37217
197387
…………

这个转发表是路由器一定会维护的. 路由器通过存放接入口的VC#和出口的VC#之间的映射, 来完成VC#的转换.

数据报网络

数据报网络的数据传输不依赖于”连接”, 路由器也没有端到端连接的状态.

路由器也不需要维护像虚电路内容的转发表. 只需要根据数据报的目的地信息就能知道数据报应该往路由器的哪个端口发送. 所以它的转发表仅仅包含了目的地址相关的信息和链路接口两个项.

最长前缀匹配

因为转发表中含有的项非常多, 查找起来比较慢, 肯定不能挨个去查, 这样效率太低了. 所以它的转发表不再存储每条目的地址, 而是存储一个前缀匹配法则. 做最长的前缀匹配, 就能确定出口.

目的地址范围链路接口
11001000 00010111 00010000 00000000 到 11001000 00010111 00010000 111111110
11001000 00010111 00011000 00000000 到 11001000 00010111 00011000 111111111
11001000 00010111 00011001 00000000 到 11001000 00010111 00011111 111111112
其他3

但是上面这个表只能确定IP范围, 还没有做到最长的前缀匹配, 上面存储的内容有些过于冗杂了.

前缀匹配链路接口
11001000 00010111 000100
11001000 00010111 000110001
11001000 00010111 000112
其他3

只要根据最符合前缀匹配式的接口进行匹配, 就达到了和上面储存地址范围相同的效果.

例如:

11001000 00010111 00010110 10100001和第一个式子匹配度最高, 所以导向接口0.

11001000 00010111 00011000 10101010和第二个式子匹配度最高(第三个式子没有000, 但是第二个式子有), 导向接口1.

虚电路服务与数据报服务的对比

对比的方面虚电路服务数据报服务
思路可靠通信应当由网络来保证可靠通信应当由用户主机来保证
网络层连接提供主机到主机的连接服务不提供主机到主机的连接服务
终端与网络终端简单, 网络复杂终端复杂, 网络简单
终点地址仅在连接建立阶段使用, 每个分组使用短的虚电路号每个分组都有终点的完整地址
分组的转发属于同一条虚电路的分组均按照同一路由进行转发每个分组独立选择路由进行转发
当结点出故障时所有通过出故障的结点的虚电路均不能工作出故障的结点可能会丢失分组, 一些路由可能会发生变化
分组的顺序总是按发送顺序到达终点到达终点时不一定按发送顺序
端到端的差错处理和流量控制可以由网络负责, 也可以由用户主机负责由用户主机负责

路由器

其实之前说的网络层实现的功能, 转发与路径选择, 也是路由器实现的, 换句话说网络层的核心硬件其实就是路由器. 路由器实现了选路算法, 并将数据报转发到另一个路由器上.

路由器由四部分组成:

  • 输入端口: 物理层, 链路层的接入功能及查找功能, 以”线速”完成输入端口处理
  • 交换结构: 完成输入端与输出端的交换
  • 输出端口: 执行与输入端口完全相反的流程.
  • 选路处理器: 执行选路协议.

在输入端口, 如果数据报到达的速度比交换结构转发速率快, 就需要排队. 同理, 在输出端口, 如果交换结构的数据报到达速度比数据报发送的速率更快时, 也要发生排队. 当队列满时, 就会发生溢出, 无论是在输入还是输出端口都有可能发生溢出. 排队时就会产生时延.

线头(HOL)阻塞: 排队的数据报在队列的前面阻碍队列中的其他数据报转发.

IP

互联网服务被定义成不可靠的, 尽力而为, 无连接分组交付系统.

  • 服务是不可靠的, 因为分组可能丢失, 重复, 延迟或不按序交付等, 但服务不检测这些情况, 也不提醒发送方和接收方.
  • 服务是尽力而为的, 互联网并不随意地丢弃分组, 只有当资源用完或底层网络出现故障时才可能出现不可靠性.
  • 服务是无连接的, 因为每个分组都是独立对待的. 分组序列可能经过不同的传输路径或者有的丢失有的到达.

数据报格式

在加上IP的头之后, TCP的开销就显得非常大了. IP一共是32bit*5/8=20bytes, 加上TCP报文段的20B信息一共是40B.

其中的寿命(Time to live, TTL)为0时数据报结束传输.

网络链路有MTU (Maximum Transmission Unit, 最大传输单元) – 最大可能的链路级帧, 大的IP数据报会被拆成很多个小段分别发送, 并在最终的目的地进行整合.

分片后头部信息的长度, ID, 偏移量, 段标识需要进行改变. 同一组分片的ID都是相同的, 偏移量总是依次向上加$\frac{MTU-20}{8}$. 每组最后一个片的段标识为0. 长度指的是包含IP头部所有的长度. 最终分片出来的个数应该是$\lceil \frac{\rm datagram-20}{\rm MTU-20}\rceil$片.

假设有4000B数据报, MTU为1500B.

因为分片前的数据报ID为X, 所以分片后也都是X. 一共分了$\lceil \frac{4000-20}{1500-20}\rceil=3$片, 前两片的长度都是MTU, 段标识都是1. 偏移量依次向上增加$\frac{1500-20}{8}=185$. 最后一片因为不是正好凑齐, 所以长度为$(4000-20) - (1500-20)\times 2+20=1040$, 段标识为0代表是分片的末尾.

再举个例子:

datagram: 3000B

MTU: 500

ID: 422

应该一共有$\lceil \frac{3000-20}{500-20}\rceil=7$片, 所有ID均为422, 偏移量依次向上增加$\frac{500-20}{8}=60$. 前6片的长度为500, 段标识为1. 最后一片的段标识为0, 长度为$(3000-20)-(500-20)\times6+20=120$.

IPv4编址

IP地址是对主机, 路由器接口的32-bit 标识符. 一般情况下, 路由器通常具有多个接口, 主机可能具有多个接口, IP编址与每个接口相联系. 在早期, 32位的IP地址被严格划分为8位一段, 即主机号和子网号必须严格是8的倍数. 子网号是高位地址, 主机号是低位地址. 直到有了CIDR协议, 打破了这种限制.

当然有一些关键的IP地址是要保留的, 因为他们很重要, 不能被占用.

主机号全为0的地址表示网络本身.

主机号全为1的保留作为定向广播, 是子网内的广播地址.

127.xxx.xxx.xxx的任意IP保留作为环路测试TCP/IP以及本机进程之间的通信, 它不是一个网络地址. 如果还不理解, 它就是我们常见的localhost.

子网掩码也是一个32位的地址, 它将所有子网位置1, 主机位置0.

子网

子网: 具有IP地址相同的子网部分的设备接口, 能够物理上互相到达而没有中间路由器的网络叫做子网.

图中有三个子网, 三个子网通过一个路由器相连接. 与子网之外的主机互相通信必须借助路由器.

图中除去最上方, 最下方一共三个子网外, 由于路由器和路由器不同接口的通信也满足子网定义, 所以一共有六个子网.

CIDR

CIDR(Classless InterDomain Routing, 无类型域间选路): 子网部分长度可以为任意位, 地址格式修改为a.b.c.d/x, 其中x为子网部分的长度.

IP地址计算

假设有一个已知的IP地址204.110.113.86/22, 请分别计算:

  1. 子网掩码
  2. 网络本身地址
  3. 广播地址
  4. 网络中主机号的数量
  5. IP地址范围

要计算出上述问题, 我们只关心主机和子网的一部分, 所以我们没必要将其全部化为二进制形式, 只需要将所需的段化为二进制即可.

  1. 子网掩码: 255.255.252.0
  2. 网络本身地址: 204.110.112.0
  3. 广播地址: 204.110.115.255
  4. 网络中主机号的数量: $1022$
  5. IP地址范围: 204.110.112.0 ~ 204.110.115.254

一共有22位子网号, 所以所有分割一定以第三段IP的二进制为基础. 113是$64+32+16+1$, 转为二进制为01110001. 前6位被子网号所占, 后2位被主机号所占.

子网掩码将子网号全置1, 所以是255.255.255-2-1.0, 即255.255.252.0.

将01110001后两位置0, 即01110000, 也就是$113-1=112$, 故网络本身地址为204.110.112.0.

广播地址同理, 后两位置1, 即01110011, $112+2+1=115$, 广播地址为204.110.112.255.

因为网络主机号有$32-22=10$位, 除去网络本身和广播地址保留, 一共主机有$2^{10}-2=1022$个.

IP地址范围沿着上面写, 就是去除掉广播地址和网络本身的所有IP地址, 即204.110.112.0 ~ 204.110.115.254.

再来一个例子:

假设有一个已知的IP地址190.168.100.5/20, 请分别计算:

  1. 子网掩码
  2. 网络本身地址
  3. 广播地址
  4. 网络中主机号的数量
  5. IP地址范围

还是与上面一样, 直接放答案:

  1. 子网掩码: 255.255.240.0
  2. 网络本身地址: 190.168.96.0
  3. 广播地址: 190.168.111.0
  4. 网络中主机号的数量: $4094$
  5. IP地址范围: 190.168.96.1 ~ 190.168.111.254

DHCP

动态主机配置协议(Dynamic Host Configuration Protocol, DHCP) 常用于给主机动态地分配IP 地址, 它提供了即插即用联网的机制, 这种机制允许一台计算机加入新的网络和获取IP 地址而不用手工参与. DHCP 是应用层协议, 它是基于UDP 的.
DHCP 的工作原理如下:

使用客户／服务器方式. 需要IP 地址的主机在启动时就向DHCP 服务器广播发送发现报文, 这时该主机就成为DHCP 客户. 本地网络上所有主机都能收到此广播报文, 但只有DHCP 服务器(静态IP)才回答此广播报文. DHCP 服务器先在其数据库中查找该计算机的配置信息. 若找到, 则返回找到的信息. 若找不到, 则从服务器的IP 地址池中取一个地址分配给该计算机. DHCP 服务器的回答报文称为提供报文.

DHCP 服务器聚合DHCP 客户端的交换过程如下:

  1. DHCP 客户机广播”DHCP 发现“消息, 试图找到网络中的DHCP 服务器, 以便从DHCP服务器获得一个IP 地址.
  2. DHCP 服务器收到”DHCP 发现消息后, 向网络中单播”DHCP 提供“消息, 其中包括提供DHCP客户机的IP 地址和相关配置信息.
  3. DHCP 客户机收到”DHCP 提供”消息, 如果确认接收DHCP 服务器所提供的相关参数, 那么通过广播”DHCP 请求“消息向DHCP 服务器请求提供IP 地址.
  4. DHCP 服务器收到”DHCP 请求”消息后, 单播一个”DHCP响应“.

NAT

NAT(Network Address Translation, 网络地址转换): 因为外部关注本地网络只使用的一个IP地址, 所以对于某个局域网下的设备完全可以对外共用一个IP地址. 通俗的说就是将网络划分为了公网和私网, 当多台私网内设备访问外部时, 都是通过一个中心设备做一次IP地址映射, 以同一个公网IP访问外部.

当私网内的IP发生变化时, 根本不用通知外网, 并且增强了私网设备的安全性, 大大的节省了IPv4数量.

ICMP

为了提高IP 数据报交付成功的机会, 在网络层使用了网际控制报文协议(Internet Control Message Protocol, ICMP) 来让主机或路由器报告差错和异常情况. ICMP 报文作为网络层数据报的数据, 加上数据报的首部, 组成IP 数据报发送出去. ICMP 是IP 层协议. ICMP 报文的种类有两种, 即ICMP 差错报告报文和ICMP 询问报文. ICMP 差错报告报文用于目标主机或到目标主机路径上的路由器向源主机报告差错和异常情况.

  1. 终点不可达. 当路由器或主机不能交付数据报时, 就向源点发送终点不可达报文.
  2. 源点抑制. 当路由器或主机由于拥塞而丢弃数据报时, 就向源点发送源点抑制报文, 使源点知道应当把数据报的发送速率放慢.
  3. 时间超过. 当路由器收到生存时间(TTL) 为零的数据报时, 除丢弃该数据报外, 还要向源点发送时间超过报文. 当终点在预先规定的时间内不能收到一个数据报的全部数据报片时, 就把已收到的数据报片都丢弃, 并向源点发送时间超过报文.
  4. 参数问题. 当路由器或目的主机收到的数据报的首部中有的字段的值不正确时, 就丢弃该数据报, 并向源点发送参数问题报文.
  5. 改变路由(重定向) . 路由器把改变路由报文发送给主机, 让主机知道下次应将数据报发送给另外的路由器(可通过更好的路由) .

IPv6

IPv6开始是为解决32位IPv4地址很快分配完而诞生的. 稍作了解即可.

  • 128位的IP地址
  • 固定长度 40 字节首部
  • 只能在源与目的上进行分片与重组装
  • 没有检查和
  • 选项部分被移到首部之外

IPv6和IPv4目前只能通过隧道的方式混用, 也就是在IPv路由器之间IPv6数据报作为IPv4数据报的负载.

所谓的双栈不是一个很好的解决方法, 在一台设备上同时启用IPv4协议栈和IPv6协议栈, 同时分别配置了IPv4地址和IPv6地址, 对于IP地址耗尽的问题却没有任何帮助, 反而增加了网络的复杂度.

选路算法

选路是为了决定从源到目的地通过网络的”好的路径”, 选路问题可以抽象成图论问题.

全局的或分散的信息?

分散的:

  • 路由器知道物理相连的邻居, 到邻居的链路费用
  • 计算的迭代过程, 与邻居交换信息
  • “距离矢量(DV)” 算法

全局的:

  • 所有路由器具有完全的拓扑, 链路费用信息
  • “链路状态(LS)”算法

静态的或动态的?

静态(非自适应): 路由随时间缓慢变化

动态(自适应): 路由更快地变化, 周期的更新, 适应链路费用变化

LS采用的图论算法是Dijkstra算法, 所有节点知道网络拓扑, 链路费用, 经”链路状态广播”完成, 所有节点具有相同信息, 因此LS是全局的算法. 然后利用Dijkstra算法迭代得到最短路径.

$c(x,y)$: 从节点$x$到$y$的链路费用, 如果不是直接邻居则为$\infty$.

$D(v)$: 从源到目的地$v$路径的代价.

$p(v)$: 从源到$v$沿路径的前驱节点.

$N’$: 已知最小代价的节点集合.

1 初始化:
2 N’ = {u}
3 对所有节点v
4 if v 临近 u
5 then D(v) = c(u,v)
6 else D(v) = ∞
7
8 Loop
9 找出w不在N‘中使得D(w)最小
10 将w加入N’
11 对于所有v临近w并不在N’中, 更新D(v):
12 D(v) = min( D(v), D(w) + c(w,v) )
13 / 到v的新费用或是到v的老费用或到w加上从w到v的已知最短路费用/
15 until 所有节点在 N‘中

本题从u出发, 步骤0初始化先写好所有与u节点相邻的节点距离, 选择一个最小的, 即节点x, 加入已知集合N’.

步骤1对距离进行更新, 选择节点y(此处选择v会有不同的顺序, 但会有相同的结果)加入已知集合. 反复迭代, 最后得到结果.

Distance Vector Algorithm

DV算法是一个分布式的, 可迭代的异步动态算法. 它采用的是贝尔曼 - 福特方程(动态规划里的一种解法). 每个路由器将自身的路由信息发送给邻居, 每个路由器将邻居发送来的信息更新自己的路由表, 若路由表更新则发送信息更新信息给邻居, 否则不发送. 但距离向量算法具有路由自环的缺点, 会导致好消息传的快, 坏消息传的慢的现象, 且可能会导致无穷计算的问题. 发生这种情况的话, 可以采用毒性逆转, 即当一条路径信息变为无效之后, 路由器并不立即将它从路由表中删除, 而是用不可达的度量值将它广播出去.

$d_x(y)$: x到y的最低费用.

$c(x, v)$: 节点x到邻居v的代价.

$D_x$: 节点x到其他所有节点距离的向量, $D_x=[d_x(y): y\in N]$.

$S_x$: 节点x到其他所有节点后继的向量, $S_x=[s_x(y): y\in N]$. $s_x(y)$为节点x到y的后继节点.

当节点x接收到来自邻居的新距离向量估计, 它使用B-F方程更新其自己的距离向量:
$$
D_x(y) \leftarrow \min_v\{c(x, y)+D_v(y): y\in N\}
$$

在节点u计算完到达其他所有节点的$d_u(x)$后, 产生一个距离向量$D_u$, 和一个后继向量$S_u$.

因此, 每个节点要做的只是等待通知 -> 重新计算 -> 通知邻居的循环. 所以说它是一个能够自适应的分布式动态异步算法.

LS和DV的对比

LS 算法DV 算法
原理使用全局信息的算法, 网络拓扑和所有的链路费用是已知的, 通过让每个节点向网络中的所有其它路由器广播链路状态分组来完成.每个节点的选路表包括了它的距离向量和它的每个邻居的距离向量, 并不时地向它的每个邻居发送它的距离向量拷贝.
算法Dijkstra算法, 是迭代算法是一种迭代的, 异步的和分布式的算法
计算方法计算从源节点到网络中所有其它节点的最低费用路径 经算法迭的第K次迭代后, 可知道到K个目的节点的最低费用.从邻居接收更新距离向量, 重新计算选路表项和通知邻居到目的地的最低费用路径的费用已经变化的过程继续下去, 直到无更新报文发送为止.
特性报文复杂, 收敛速度快报文少, 收敛速度慢

层次路由

由于网络规模增大到一定程度时候, 路由表不可能存放下所有的信息. 将某区域的路由器聚合成为 “自治系统” (AS), 在相同AS中的路由器运行相同的选路协议, 在不同AS中可以不用运行相同的选路协议. 连接AS间的路由器称为网关.

假设AS1要将接收到的数据报转发到外部, 此时网关不唯一, 那么AS1必须要知道AS2能到达哪些目的地, AS3能到达哪些目的地, 还必须将这些信息传播到AS1内部的所有路由器. 这些内容都由AS之间的选路协议负责. 层次路由应运而生, 如何管理跨越AS之间的路由情况, 就是AS间选路协议要解决的问题.

在AS1中选择网关时, 是由AS间路由协议完成, 采用热土豆路由, 也就是直接发送给离自己最近的网关即可.

互联网中的选路

RIP和OSPF都属于IGP(Interior Gateway Protocol, 内部网关协议), 即AS内的协议, 而BGP属于EGP(Exterior Gateway Protocol, 外部网关协议), 也就是AS间的协议.

RIP

  • 是最早的AS内部因特网选路协议, 是一种距离向量协议.
  • 使用跳数(hop) 做为其费用测度, 一条路径的最大费用被限制为15(防止无穷计算).
  • RIP中, 选路信息在邻居之间通过RIP响应报文交换, 约30秒交换一次.
  • 每台路由器维护一张RIP表, 称为选路表, 包括该路由器的距离向量和该路由器的转发表.
    • 选路表的更新
  • RIP使用IP协议之上的UDP协议来实现网络层功能, 该UDP报文段在标准IP数据报中承载在路由器之间.
  • RIP被设置在较低层ISP和企业网中.
  • RIP协议通过应用层进程进行管理, 周期性通过UDP数据报发送.

OSPF

OSPF(Open Shortest Path First)是开放最短路径优先算法, 开放指协议是公开发表, 公众可用的, 最短路径优先指的是使用了Dijkstra提出的最短路径算法(采用LS分组扩散). 也是一个作用域AS内部的算法.

  • OSPF通常被设置在较顶层的ISP中.
  • 它的核心是一个使用洪泛链路状态信息的链路状态协议和一个Dijkstra 最低费用路径算法.
  • 一台路由器构建了一幅关于整个AS的完整拓扑图.
  • 使用OSPF时, 路由向自治系统内所有其它路由器广播选路信息. OSPF报文直接封装在IP数据报中, 必须实现可靠传输.
  • 仅当链路状态发生变化时, 路由器才向所有路由器洪泛发送信息.

OSPF优点:

  • 安全: 交换都是经过鉴别的
  • 多条费用相同的路径: 费用相同时, 可以使用多条(负载均衡, RIP中只能用一条)
  • 对单播选路与多播选路的综合支持
  • 支持在单个选路域内的层次结构
  • AS内的一个OSPF区域配置成主干区域, 区域间选路要求分组首先路由到一个区域边界路由器, 再通过主干路由器到目的区域的区域边界路由器, 最后到达目的.

有局部(Area)和主干(Backbone)两级分层, 链路的状态通告仅在区内, 每个节点具有详细的区域拓扑, 仅知道到其他区域网络的方向(最短路径). 区边界路由器(Area border routers)汇总了到在自己区域网络的距离, 向其他区域边界路由器通告. 主干路由器(Backbone Routers)在主干区运行OSPF算法, 边界路由器(Boundary routers)要连接其他的AS.

BGP

边界网关协议(Border Gateway Protocol, BGP) 是不同自治系统的路由器之间交换路由信息的协议, 是一种外部网关协议. 边界网关协议常用于互联网的网关之间. 路由表包含已知路由器的列表, 路由器能够达到的地址及到达每个路由器的路径的跳数. 内部网关协议主要设法使数据报在一个AS 中尽可能有效地从源站传送到目的站. 在一个AS内部不需要考虑其他方面的策略. 然而BGP 使用的环境却不同, 主要原因如下:

  1. 因特网的规模太大, 使得自治系统之间路由选择非常困难.
  2. 对于自治系统之间的路由选择, 要寻找最佳路由是很不现实的.
  3. 自治系统之间的路由选择必须考虑有关策略.

边界网关协议(BGP) 只能力求寻找一条能够到达目的网络且比较好的路由(不能兜圈子) , 而并非寻找一条最佳路由. BGP 采用的是路径向量路由选择协议, 它与距离向量协议和链路状态协议有很大的区别. BGP 的实现是应用层协议(BGP本身肯定是网络层协议), 基于TCP (AS间的策略比性能更加重要), 端口号179. 支持CIDR.
BGP 的工作原理如下: 每个AS的管理员要选择至少一个路由器(可以有多个) 作为该自治系统的”BGP 发言人“. 一个BGP 发言人与其他自治系统中的BGP 发言人要交换路由信息, 就要先建立TCP 连接(可见BGP 报文是通过TCP 传送的, 也就是说BGP 报文是TCP 报文的数据部分) , 然后在此连接上交换BGP 报文以建立BGP 会话, 再利用BGP 会话交换路由信息. 当所有BGP 发言人都相互交换网络可达性的信息后, 各BGP 发言人就可找出到达各个自治系统的较好路由. 每当可达性信息发生变化时, 才进行交换, 否则不交换.

  • eBGP: 跨越两个AS的BGP会话(外部)
  • iBGP: 同一个AS中的两台路由器之间的BGP会话(内部)

广播和多播选路

广播和多播是什么?

广播选路: 从一个源节点到网络中的所有其它节点交付分组.

多播选路: 使单个源节点能够向其它网络节点的一个子集发送分组的拷贝.

当向多个接收方发送相同的数据时, 为了更好的带宽利用率, 较少的主机/路由器处理和更快的参与, 就需要多播.

广播选路算法

无控制洪泛: 要求源节点向它的所有邻居发送该分组拷贝, 产生广播风暴.

受控洪泛:

  • 序号控制洪泛: 加入控制序号, 重复时, 直接丢弃. 否则, 保存并广播.
  • 反向路径转发RPF: 考虑是否为最短路径上转发的分组. 仅当该分组到达的链路正好是位于源节点到该节点的最短单播路径上, 它才向其所有出链路(除了它接收的那个) 传输报文. 否则, 丢弃入分组.

生成广播树: 避免环的产生, 因此可以完全避免冗余广播.

这是一种基于中心的生成树构造过程:

定义一个中心节点, 其他节点都向中心节点进行单播, 并将路径加入这棵树, 如果路径的一部分已经在树中了, 那么取剩下未加入的部分加入到树中.

多播选路算法

在多播通信中, 面临两个问题, 即怎样标识多播分组的接收方, 以及怎样为发送到这些接收方的分组编址. 在因特网体系结构中, 多播数据报使用间接地址来编址. 表示一组接收方的单一标识就是一个 D 类多播地址. 与一个 D 类地址相关联的多个接收方称为一个多播组.

IGMP(Internet Group Management Protocol, 互联网组管理协议) 运行在一台主机与其直接相连的路由器之间. IGMP 为一台主机提供了手段, 可让它通知与其相连的路由器, 在本主机上运行的一个应用程序如何加入一个特定的多播组.

在实践中有两种方法用于确定多播选路树:

使用一棵组共享树进行多播选路. 像在生成树广播的场合中一样, 跨越组的共享树多播选路基于一棵多播树, 该树包括所有具有属干该多播组的相连主机的边缘路由器. 在使用基于中心方法来构造多播选路树, 具有属于多播组相连主机的边缘路由器向中心节点(经单播)发送加入消息. 像在广播情况下一样, 一个加入报文使用单播选路朝着中心转发, 直到它到达已经属干多播树的一台路由器或到达这个中心.

使用一棵基于源的树进行多播选路. 为多播组中的每个源构建一棵多播选路树. 在实践中, 使用 RPF 算法来构造一棵多播转发树, 以用于转发来自源节点的多播数据报.

第一个用于因特网中的多播选路协议是距离向量多播选路协议(Distance Vector Multicast Routing Protocol, DVMRP).

  • 洪泛与剪枝: 反向路径转发, 基于源的树
  • 基于DVMRP自己的选路表的RPF 树, 通过DVMRP路由器的通信构造
  • 向多播组发起的数据报经RPF洪泛到各处
  • 无组成员的路由器: 发送上游剪枝报文

链路层和局域网

因为网络层考虑的是解决路径选择和转发的问题, 链路层更加的贴近于物理层, 解决的是同一链路主机的数据如何在连路上进行传输的问题. 比如说解决在链路传播比特级的差错和纠错, 半双工全双工, 链路上的流量控制, 链路冲突问题等. 链路层把网络层传下来的分组封装成帧(frame). 不同的链路完全可以提供不同的链路协议而不互相干扰, 在链路上的传输控制免不了物理设备的配合, 即网卡(NIC).

差错检测

EDC(Error Detection and Correction bits), 实际上差错检测是差错的检测和纠错. 差错检测可能保护各层的头信息. 但是差错检测也不是完全可靠, 因为协议可能会漏掉某些差错.

奇偶校验

奇偶校验比较简单, 能够检测出错误, 但是不能对错误进行纠正.

奇校验: 添加冗余位使得整个序列中1的个数为奇数.

偶校验: 添加冗余位使得整个序列中1的个数为偶数.

比如0111000110101011|0添加了一位冗余, 使得整个序列中1的个数为9, 即奇数, 所以这是奇校验. 添加一位冗余的奇偶校验只能检测出有1比特的错误, 也不能确定位置.

二维比特奇偶校验不但能检测出1比特差错, 还能将其纠正.

图中所示的是二维偶校验, 将原始序列按照行列排好, 每行每列都产生一位冗余位, 最后再按照同样奇偶规则将产生的冗余位再加一位校验冗余位. 最下面左侧的图是还没有发送前保存的数据, 右侧是接收方接收到的数据. 将冗余位进行比对, 由于第二行不满足1个数为偶数, 所以说第二行有错误. 第二列也不满足, 所以错误定位到第二行第二列. 这样就完成了错误差错检测.

检查和

检查和就是之前传输层的检查和, 只能做到差错检测, 如果有错自己做其他处理.

CRC循环冗余校验

将数据比特$\rm D$视为一个二进制数, 选择$r$个CRC比特$\rm R$, 使得接收方通过某个生成多项式转换为$r+1$位二进制数$\rm G$能整除$\rm <D, R>$. 如果有非零余数即检测到差错.

$\rm R$就是我们最终要计算出来的东西. 在写出$\rm <D,R>$ 前, 需要根据多项式位数对数据$\rm D$进行移位, 多项式$\rm G$ 是$r+1$位, 就将数据$\rm D$ 后添加$r$ 个0(也就是下述式子所述的$\rm D\cdot 2^r$), 从而满足求出来的余数一定是$r$ 位.
$$
\rm R = 余数[\frac{D\cdot2^r}{G}]
$$
如何将生成多项式转化为二进制数? 其实就是取多项式系数的过程. 假设生成多项式为$x^5+x^4+x+1$, 那么对应的二进制数就是110011, 从$1\times x^5+1\times x^4+0\times x^3+0\times x^2+1\times x+1\times x^0$ 提取系数得来.

看一个例子:

假设多项式为$\rm G(x)=x^3 + 1$, 数据$\rm D=101110$, 求CRC位$\rm R$.

先将多项式转化为二进制, 即1001, 是4位, 则将D的右侧补3个0. 然后进行二进制除法. 二进制除法的本质是异或(XOR), 因为每一位除的结果不影响其他位, 加法不进位，减法不借位, 所以实际上就是异或.

只要遵循够$r+1$位商1, 否则商0的原则, 就能得到结果. 如下所示:

除到最后时, 如果不满足$r$ 位不要忘记添0.

再来一个例子检验一下:

假设多项式为$\rm G(x)=x^3 + 1$, 数据$\rm D=100101110$, 求CRC位$\rm R$.

结果为11010.

多路访问协议

对于链路, 往往有两种, 一种是点对点类型的, 还有一种市广播类型的. 多路访问协议能够一定程度上解决两个节点的并行传输问题, 也称为碰撞. 在这个过程中, 被共享的信道必须通过其自身解决, 不增加外来信道进行协调, 否则也失去了多路访问协议存在的意义.

在理想的多路访问协议中, 一个节点传输时, 应该达到信道的最大传输速率, 多个节点传输时应该达到平均最大传输速率. 并且没有其他的特殊节点协调, 也没有同步时钟和间隙.

MAC协议分为三大类:

  • 信道划分: 将信道划分为较小的“段” (时隙，频率，编码), 为节点分配一部分专用.
  • 随机访问: 不划分信道，允许碰撞, 但想方设法从“碰撞”恢复.
  • 轮转: 节点轮转，但有更多信息要发送的能够轮转的较长时间.

信道划分

信道划分实际上有四个算法, 分别是时分多路访问TDMA, 频分多路访问FDMA, 波分多路复用WDM, 码分多路访问CDMA.

TDMA

TDMA(Time division multiple access, 时分多路访问):

每个站点在每个循环中获得固定长度时隙, 循环访问信道, 不占用空闲的时隙. 上图中时隙2, 5, 6空闲.

FDMA

FDMA(Frequency division multiple access, 频分多路访问):

为信道频谱划分为多个频带, 每个站点分配固定的频带, 每个频带上分别传输, 也不占用空闲的频带. 上图中频带2, 5, 6空闲.

CDMA

CDMA(Code Division Multiple Access, 码分多路访问):

码分多路访问下, 所有用户共享相同的频道, 也共享相同的时间. 每个比特时间被划分为m个更短的时间槽, 称为”码片“. 每个用户用自己的”码片序列”对数据进行编码, 在输出端进行解码, 这些序列应该是相互”正交”的, 所以不会相互干扰. 在WIFI经常用到这种技术.

WDM

WDM(Wavelength Division Multiplexing, 波分多路复用):

波分多路复用就是光的频分多路复用，在一根光纤中传输多种不同波长(频率) 的光信号，由于波长(频率) 不同，所以各路光信号互不干扰，最后再用波长分解复用器将各路波长分解出来.

随机访问协议

时隙ALOHA

一句话概括: 时隙 + 概率重传.

假定:

  • 所有帧有相同长度
  • 时间划分为等长时隙，能够传输1个帧
  • 节点是同步的, 且节点仅在时隙开始时开始传输帧
  • 如果2个或多个节点在时隙中传输，所有节点检测碰撞

操作:

  • 当节点获得新帧，将在下一个时隙中传输
  • 无碰撞，节点能够在下一个时隙中发送新帧
  • 如果碰撞，节点在每个后继时隙中以概率p重传帧直到成功

这么搞看起来是没啥问题, 但是实际上时隙空闲的概率非常高.

假定$N$个有许多帧要发送节点，每个时隙以概率$p$发送.

某个节点在一个时隙中成功发送的概率为$p(1-p)^{N-1}$, 即除自己外的其他节点都重传失败. 那么任何节点成功发送的概率为$Np(1-p)^{N-1}$.

下面来求一下这个概率的最大值$p_{max}$,
$$
\begin{aligned}
E(p)&=Np(1-p)^{N-1} \\
E’(p)&=N(1-p)^{N-1} -Np(1-p)^{N-2} \\
&=N(1-p)^{N-2}((1-p)-p(N-1))\\
E’(p)&=0 \Rightarrow p_{max}=\frac{1}{N}
\end{aligned}
$$

当有无穷多个节点, 即$N\rightarrow \infty$时,
$$
\displaylines{
\lim_{N\to\infty}E(p_{max})=N\frac{1}{N}(1-\frac{1}{N})^{N-1} = \frac{(1-\frac{1}{N})^N}{1-\frac{1}{N}} \\
\lim_{N\to \infty}{1-\frac{1}{N}}=1 \qquad\lim_{N\to \infty}({1-\frac{1}{N}})^N=\frac{1}{e} \\
\lim_{N\to \infty}{E(p_{max})}=\frac{1}{e}=37\%
}
$$
即在节点无穷多时, 效率最终只有$37\%$.

优点:

  • 单个活跃节点能够连续地以信道的全速传输
  • 仅节点中的时隙需要同步, 即高速分散
  • 简单

缺点:

  • 碰撞后可能浪费时隙
  • 空闲时隙无法利用
  • 节点可能能够以小于传输分组的时间检测到碰撞
  • 所有节点时钟同步
纯ALOHA

一句话概括: 想发就发 + 随机重传.

也就是非时隙的ALOHA, 更简单, 没有同步的要求. 当帧到达时立即进行传输. 增加了碰撞的概率. 如果接收方在一定时间内没有收到, 那就判断发生了冲突.

从效率角度考虑一下呢? 仍然采用帧传输时间为时间单元. 在任意给定时间, 某节点传输一个帧的概率为$p$. 假设该帧在$t_0$ 时刻开始传输, 为了使得这帧传输成功, 则在$[t_0-1, t_0]$不能有其他节点进行传输. 所有其他节点在这个时间间隔不开始传输的概率是$(1-p)^{N-1}$, 同样在$t_0$时刻也不能有其他节点进行传输, 概率也是$(1-p)^{N-1}$. 所以对于$t_0$时刻一个节点传输成功的概率是$(1-p)^{2(N-1)}$.

仍然先求出发送成功概率的最大值$p_{max}$.
$$
\begin{aligned}
E(p)&=Np(1-p)^{2(N-1)} \\
E’(p)&=N(1-p)^{2(N-1)} -Np2(N-1)(1-p)^{2(N-2)} \\
&=N(1-p)^{2N-3}((1-p)-p2(N-1))\\
E’(p)&=0 \Rightarrow p_{max}=\frac{1}{2N-1}
\end{aligned}
$$
然后再求出当节点区域无穷时的极限.
$$
\displaylines{
\lim_{N\to\infty}E(p_{max})=\frac{N}{2N-1}(1-\frac{1}{2N-1})^{2(N-1)} \\
\lim_{N\to \infty}{\frac{N}{2N-1}}=\frac{1}{2} \qquad\lim_{N\to \infty}({1-\frac{1}{2N-1}})^{2N-1}=\frac{1}{e} \\
\lim_{N\to \infty}{E(p_{max})}=\frac{1}{2} \cdot \frac{1}{e} = 18\%}
$$
实际上纯ALOHA的效率还不如时隙ALOHA, 也就是时隙ALOHA的一半.

CSMA

CSMA(Carrier Sense Multiple Access, 载波侦听多路访问). 前面的信道划分协议都是不管别人有没有在传输, 都会直接传输试试, 再判断是否有人传输, 这从逻辑上就有点反常. 在别人已经进行传输时, 自己再进行传输, 岂不是白费功夫? 别人在说话时候你打岔, 就大大增加了冲突的概率. CSMA就是一个在传输前侦听的访问协议. 如果侦听到信道正忙, 则推迟传输. 先听听有没有人在说话, 如果有就等别人说完了再说. 碰撞仍然会出现, 但是概率会减小.

但是考虑到传播时延, 也许节点已在传播数据, 但还在路上, 有些节点可能还没有检测到信道忙信号. 这当然会有一些问题, 叫最小帧长问题, 后面会说.

CSMA实际上有三种:

  • 1-坚持 CSMA: 节点发送数据时先侦听信道是否空闲, 如果空闲则立即发送, 如果忙就一直侦听, 等到空闲时再发送. 发生冲突时, 随机等待一段时间后再重新侦听. “1-坚持”指的是信道忙时继续坚持侦听信道, 信道空闲时发送的概率为1, 立刻发送数据.
  • 非坚持 CSMA: 节点发送数据时先侦听信道是否空闲, 如果空闲则立即发送, 如果忙就放弃侦听, 等待随机一段时间后再侦听, 发送, 重复上述过程.
  • p-坚持 CSMA: 用于时分信道, 发送数据前先侦听信道, 如果信道忙就继续侦听, 直到信道空闲. 如果信道空闲, 有概率p发送数据, 有概率1-p推迟到下个时隙. 如果下个时隙信道仍然空闲, 仍然重复上述过程, 直到信道忙为止. 如果信道忙则等到下个时隙再重新开始侦听.
CSMA/CD

CSMA/CD(Carrier Sense Multiple Access with Collision Detection, 载波监听多点接入/碰撞检测):

  • CS: 载波监听/侦听，每一个站在发送数据之前以及发送数据中都要检测一下总线上是否有其他计算机在发送数据。
  • MA: 多点接入，说明这是总线型网络，许多计算机以多点接入的方式连接在一根总线上。
  • CD: 碰撞检测(冲突检测) , 边发送边监听，适配器边发送数据边检测信道上信号电压的变化情况，以便判断自己在发送数据时其他站是否也在发送数据。如果一个站发现了总线上出现了碰撞，其适配器就要立即停止发送，免得继续进行无效的发送，白白浪费网络资源，然后等待一段时间随机时间后再次发送, 半双工网络.

如果几个发生碰撞的站都在监听信道，那么都会同时发现信道变成了空闲，如果此时都同时发送，那么肯定在原来的地方又发生了碰撞，所以碰撞后使用二进制指数退避算法, 往往等待时间再发送.

先听后发, 边听边发

冲突停发, 随机重发

最小帧长问题

A节点发了一个很短的帧, 但是发生了碰撞. 这个帧是在发送完毕的时候才检测到发生碰撞, 没法停止发送, 已经发完了. CSMA/CD希望能及时控制局面, 就必须有一个最小帧长来限制最短帧的发送, 最起码要在帧没发送完的时候检测到碰撞. 下面来探究一下这个问题.

假设A与B两个节点都需要传输数据, 单程传播时延为$\tau$. 在$t=0$时刻A开始发送数据, B检测到信道空闲. 在$t=\tau-\delta$ 时刻A的数据还没到达B, B检测到信道空闲而发送数据. 但发送数据$\delta/2$ 后, 即$t=\tau-\delta/2$ 时刻, A和B发生的数据发生碰撞, 但返回的信息还没到达A和B, 所以A和B都不知道. 在$t=\tau$时, B检测到碰撞, 于是停止发送数据. 在$t=2\tau-\delta$ 时刻, A检测到碰撞, 于是也停止发数据. 因此明显在CSMA/CD协议下只能进行半双工通信.

A在发送帧后最多经过$2\tau(\delta \to 0)$ 的时间就能知道发送的帧是否发生碰撞. 因此将这个$2\tau$ 叫做争用期(也称冲突窗口或碰撞窗口). 只有经过这段争用期后, 才能确定这次不会产生发送冲突.

因此, 为确保发送站在发送数据的同时能检测到可能存在的冲突, 需要在发送完帧之前就能接收到自己发送出去的数据, 即帧的传输时延最少要两倍于信号在总线中的传播时延. 所以必须要有一个最小帧长来约束, 任何小于最小帧长的帧都是被打断的异常帧.
$$
最小帧长=总线传播时延\times数据传输率\times2
$$

以太网规定取$51.2\mu s$为争用期的长度. 对于10Mb/s的以太网, 在争用期内可发送512bit, 即64B. 如果前64B未发生冲突, 那么剩下的后续数据肯定不会发生冲突(表示已经抢占信道). 因此因特网规定最小帧长为64B, 小于64B的都是冲突而终止的无效帧.

如果只发送小于64B的帧, 需要在MAC子层中于数据字段后面加入填充字段保证帧长不小于64B.

轮转协议

轮转协议兼顾了信道划分和随机访问的优点, 使用一个”令牌”进行传递, 使得大家轮流进行传输.

轮询

  • 指定一个主节点，主节点轮询每个节点.

  • 主节点依次通知每个节点它被允许的传输量，在该节点传输完毕后(传完最大传输量或无更多待传输数据) ，主节点再通知下一个节点.

  • 引入了轮询时延，即主节点通知从节点的时延.

  • 主节点故障会导致信道崩溃.

令牌传递

  • 令牌 小特殊帧，以某种次序在所有节点间传播.

  • 当节点收到令牌时，当且仅当它有数据要传输时，它才持有该令牌并传输一个最大限制内的数据而后将令牌传递给下一个节点. 否则，它立即向下一个节点传输令牌.

  • 一个节点的故障(如不肯释放令牌) 可能导致信道崩溃.

链路层编址

虽然高层程序希望设备用IP地址进行通信, 但是传输起来的实际通信必须采用设备的物理地址.

MAC地址

MAC地址(Media Access Control Address)是48bit的物理地址. 用于使数据报从一个接口到达另一个物理连接的接口, 在网络设备出厂时MAC地址就已经烧入了设备, 全球唯一.

广播地址: FF-FF-FF-FF-FF-FF

ARP

ARP(Address Resolution Protocol, 地址解析协议) 完成了从局域网IP到MAC物理地址的映射. 每个主机, 路由器都有ARP表, 存放了<IP, MAC, TTL>, 是一张动态表.. TTL是地址映射能存活的时间, 一般是20分钟.

相同网络的ARP协议

在相同的局域网中, A要向B发送数据报, 但B的MAC地址不在A的ARP表中, 需要执行下述步骤:

在相同的局域网中, A要向B发送数据报, 但B的MAC地址不在A的ARP表中, 需要执行下述步骤:

  1. A通过FF-FF-FF-FF-FF-FF广播ARP查询分组, 包括了B的IP, 在局域网内的所有机器都收到了ARP请求.
  2. B接收ARP分组, 用自身的MAC地址通过单播回答了A.
  3. A在ARP表中缓存了B的IP到MAC地址映射, 直到TTL为0.

上述ARP查询和ARP响应分组为:

ARP query packetARP response packet
Sip: 137.196.7.78Sip: 137.196.7.14
Dip: 137.196.7.14Dip: 137.196.7.78
Smac: 1A-2F-BB-76-09-ADSmac: 58-23-D7-FA-20-B0
Dmac: FF-FF-FF-FF-FF-FFDmac: 1A-2F-BB-76-09-AD
不同网络的ARP协议

仍然是A给B发送数据报, 但这回A和B属于两个不同的网络. 假定A知道B的IP地址.

在连接局域网LAN1和LAN2的路由器R中有两张ARP表, 每张表对应了一个局域网.

  1. A生成具有源A, 目的地B的数据报.
  2. A使用ARP从111.111.111.110得到R的MAC地址 .
  3. A生成以R的MAC地址作为目的地的链路层帧,帧包含A-to-B IP 数据报.
  4. A的适配器发送帧, B的适配器接收帧.
  5. R从以太网帧取出IP数据报，看到它目的地是B.
  6. R使用ARP得到B的MAC地址.
  7. R生成包含A-to-B IP数据报的帧向B发送.

其分组如下:

Frame A to RFrame R to B
Sip: 111.111.111.111Sip: 111.111.111.111
Dip: 222.222.222.222Dip: 222.222.222.222
Smac: 74-29-9C-E8-FF-55Smac: 1A-23-F9-CD-06-9B
Dmac: E6-E9-00-17-BB-4BDmac: 49-BD-D2-C7-56-2A

可以这样理解, 网络层不牵扯到物理地址, 所以IP始终没发生变化. 但是实际上在下层传输的链路层用到了物理地址, IP和MAC的地址映射工作完全交给中间人路由器完成了.

以太网

以太网是全球使用最广泛的局域网技术，以至于好多人都以为以太网就是我们所说的网络。我们平时所说的交换机，其实专业说法叫以太网交换机。而一般的光纤交换机其实也是采用以太网技术，只是传输介质由网线改成光纤. 一般以太网的MTU设为1500字节，加上以太帧首部的长度14字节，也就是一个以太帧不会超过1500+14 = 1514字节. 最小帧长以太网的最小帧长是64字节, 凡是长度小于64字节的都是发生冲突而异常的无效帧(详见最小帧长).

网络的拓扑结构也是岁时代更新. 20世纪90年代总线拓扑流行, 现在已经流行星型拓扑结构, 中心连接通过集线器或交换机完成. 当然也有其他类型的网络:

无连接: 在发送和接收适配器之间没有握手

不可靠: 接收适配器不向发送适配器发送应答或否定应答. 传送给网络层的数据报流可能有间隙, 如果应用程序使用TCP, 间隙将能弥补, 否则应用程序将看到该间隙.

以太网帧结构

发送适配器在以太网帧(或其他网络层协议分组)中封装IP数据报.

前导码(Preamable): 用于同步接收方，发送方时钟速率. 前7个字节为10101010 的重复(前同步码, 像踏步走的121, 121循环), 最后一个字节是10101011(帧开始界定符), 结束后就说明接收方可以开始接收数据了. 但是前导码并不是链路层插入的, 而是物理层插入的!

地址: 6字节, 如果适配器接收具有匹配的目的地址或广播地址(如ARP分组)的帧, 它将帧中的数据提交给网络层协议

类型: 2字节, 指示较高层协议(网络层协议).

数据: 最小46B, 最大1500B. 链路层的MTU是1500字节. 以太网的最小帧长是64字节, 那么$64-6-6-2-4=46$字节.

CRC: 4字节, CRC循环冗余校验码.

以太网的CSMA/CD

  1. 适配器从网络层接收数据报并生成帧.
  2. 如果适配器侦听到信道空闲，开始传输帧. 如果侦听到信道忙，等待信道空闲再传输.
  3. 如果适配器传输整个帧而没有检测到另一个帧的传输，该适配器已经处理完帧.
  4. 如果适配器传输过程中检测到另一次传输, 中止并发送强化冲突信号, 放大冲突, 确保所有的其他传输方都知道发生了碰撞.
  5. 中止后, 适配器进入指数退避.
指数退避

  • 比特时间: 对10 Mbps 以太网是 0.1 μs; 对K=1023, 等待时间约为50 msec

  • 首次碰撞: 从$\{0,1\}$中选择$K$；时延是$K \cdot 512$bit 的传输时间

  • 多次碰撞: 从$[0, 2^n] n \in Z$中选择$K$.

CSMA/CD的效率

$t_{prop}$: LAN中的2站点之间的最大传播时间.

$t_{trans}$: 传输最长帧的时间.
$$
\eta = \frac{1}{1+5t_{prop/t_{trans}}}
$$
这样来看, 传播时间越短, 传输时间越长, 效率都越高.

以太网技术

主要是10 BASE-5, 10 BASE-2, 10 BASE-T, 100 BASE-T, 100 BASE-T.

每个BASE前都有一个数字, 代表速度, 单位Mbps. BASE代表基带传输, 即baseband transmission.

10 BASE-5, 10 BASE-2最后的数字代表最大网段长度分别是500m和200m.

10 BASE-T, 100 BASE-T, 100 BASE-T最后的字母代表的是双绞线, 即twisted pair.

10 BASE-T, 100 BASE-T, 是速度为10/100Mbps的快速以太网, 使用了星型拓扑结构. 所有节点连接到中心的一台集线器, 节点和集线器最大的距离为100m.

曼切斯特编码

曼彻斯特编码在每个周期中都会发生一次突变, 以判断是否还有新的数据在传输. 这就是以太网帧结构前要加上前导码, 但却没有结束码的原因. 这种编码是由物理层实现的.

集线器和交换机

集线器

集线器(Hub)可以看做是物理层中继器, 只对物理电信号放大中继，所有端口同属一个冲突域，主要用来延伸网络访问距离，扩展终端数量:

  • 来自一条链路的比特从其他所有链路出去(广播).
  • 链路上以相同的速率传输.
  • 无帧缓存(直通).
  • 在集线器中无CSMA/CD : 适配器检测碰撞.
  • 将多个结点连接成一个共享式 的局域网.

交换机

交换机(Switch)是链路层设备, 它的每个端口相当于一个集线器，原理是根据数据帧头的MAC地址转发帧到合适的端口，每个端口是一个独立的冲突域:

  • 存储, 转发以太网帧.
  • 检查帧首部并基于MAC目的地址选择性地转发帧.
  • 当帧在网段上转发时，使用CSMA/CD 访问网段.
  • 无碰撞, 全双工.

透明: 主机不知道交换机的存在.

即插即用, 自学习: 交换机不必配置.

转发

交换机连接了三个LAN, 怎样决定向哪个LAN段转发帧?

每个交换机都有一个交换机表, 表项为<MAC地址, 接口, 时间戳>. 时间戳用于淘汰陈旧项. 交换机知道通过哪个接口可以到达哪个主机, 因为当帧收到时, 交换机记录下发送方的MAC和进入时的接口.

过滤后转发

如果目的站点所属LAN和源站点所属LAN相同, 则丢弃该帧. 如果目的站点所属LAN和源站点所属LAN不同, 则转发该帧. 如果目的站点所属的LAN未知, 则进行洪泛. 交换机减少了在不必要LAN内的重复扩散, 节约了资源.

即相同LAN段的帧通常不在其他LAN段上转发, 分割成了不同的碰撞域.

集线器, 交换机, 路由器

集线器路由器交换机
流量隔离×√√
即插即用√×√
优化选路×√×
直通√×√
隔离广播×√×
所属层级物理层网络层链路层

PPP

PPP(Point to Point Protocol，点到点协议) 是为在同等单元之间传输数据包这样的简单链路设计的链路层协议。这种链路提供全双工操作，并按照顺序传递数据包。设计目的主要是用来通过拨号或专线方式建立点对点连接发送数据，使其成为各种主机, 网桥和路由器之间简单连接的一种共通的解决方案。

PPP设计要求

  • 分组成帧: 在数据链路帧中封装网络层数据报, 在相同时间承载任何网络层协议(不止是IP)的网络层数据.
  • 比特透明性: 在数据字段必须承载任何比特模式.
  • 连接活跃性: 对网络层检测, 通知链路故障.
  • 差错检测: 仅进行差错的检测而不纠正.
  • 网络层地址协商: 端点能学习/配置每个其他网络地址.

不要求纠错/恢复, 流量控制, 数据重排序, 多点链路支持, 这些所有额外功能全部移交到高层处理.

PPP数据帧

标志: 定界符(成帧).

地址: 不起作用 (仅是一个选项).

控制:不起作用, 以后可能多控制字段.

协议: 该帧交付的高层协议 (如 PPP-LCP, IP, IPCP等).

信息: 高层承载的数据.

校验: 对差错检测的冗余循环校验.

比特填充/字节填充

有时候起始和结束的Flag01111110 也会出现在数据中啊, 可能是无意出现的. 处理方法其实和我们编程时字符串中用到的转义方法如出一辙. 如果数据中无意出现了01111110, 就在这个字节旁边额外加一个01111110, 是不是有转义内味了?

在接收方视角中, 在一排中出现01111110 01111110 , 丢弃第一个字节, 继续数据接收即可. 如果是单个01111110, 那它就是起始和结束的Flag.

文章作者: DaNing
文章链接: https://ADAning.github.io/posts/40485.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 DaNing !
面试 计算机网络
评论
 上一篇
机器学习之逻辑回归与线性回归 机器学习之逻辑回归与线性回归
2020.08.22: 附加了后续的逻辑回归部分. 逻辑回归想要了解逻辑回归，必须了解线性回归. 线性回归 Logistcs Regression线性回归是监督学习中最简单的模型了, 它具有非常好的可解释性, 也有一种简洁的典雅美.
2020-08-05 机器学习
线性回归
下一篇 
机器学习之特征缩放 机器学习之特征缩放
特征缩放 Feature scaling特征缩放还有另外一个名字, 叫做标准化. 标准化能够尽可能的使得模型快速收敛, 如果某个特征的方差比别的特征大几个数量级的话, 用距离度量的算法就会受到非常大的影响, 比如神经网络, SVM, 逻辑回
2020-08-03 机器学习
特征缩放
  目录