计算机网络学习笔记

MaoCaiMao 发布于

最后更新于

资料：《计算机网络：自顶向下》第七版和上课PPT

Chapter 1 Introduction

  1. 网络结构：
    1. 网络边缘：服务器、用户主机等终端
    2. 连接网络与物理媒介：
      1. 有线：同双绞线、同轴电缆、光纤；无线；广播：地面微波、WiFi、广域网、卫星
      2. 物理媒介决定带宽$B$，进一步决定数据率$R$（比特率）：香农定理$R=B\log_2(1+S/N)$，$S/N$信噪比
    3. 网络核心：
      1. 回路交换：专用、无共享，频分或时分使用
      2. 包交换
  2. 延迟=节点内部处理延迟+排队延迟+发送延迟+传输延迟
    1. 发送延迟=包数据量L/宽带R
    2. 传输延迟=链路长度d/传输速度s
  3. 吞吐量（throughput）：每个比特传输速率bits/sec
    1. 平均吞吐量
    2. 瞬时吞吐量：各链路最小传输速率
  4. 层次结构：应用层、传输层、网络层、链路层、物理层

Chapter 2 Application Layer

  1. 应用结构：
    1. 服务器-客户：服务器IP几乎永久，用户IP可以动态
    2. P2P(Peer to Peer)
  2. 进程间通信：
    1. 同一主机内：OS控制的进程间沟通
    2. 不同主机间：主机间交换讯息，通过套接字，Round Trip Time(RTT)为从客户到服务器来回传输一次包的时间
  3. HTTP（Hypertext Transfer Protocol）：服务器-客户模型，使用TCP连接，端口80
    1. 非永久HTTP：一个TCP连接最多传输一个对象，需要2RTT+文件发送时间，经常并行TCP连接
      1. 客户向域名服务器发送连接请求
      2. 服务器在端口80接受TCP连接，通知客户
      3. 客户通过TCP套接字发送请求对象的路径信息
      4. 服务器发送含有对象的响应信息
      5. 服务器关闭TCP连接
      6. 客户接收相应信息，自己处理
      7. 重复该过程
    2. 永久HTTP：一个TCP连接传输多个对象
      1. without pipelining：每个请求完成后才发送下一个请求，每个对象需要1RTT
      2. with pipelining：只要有请求就发送，最快所有对象只需要1RTT
    3. 调用方法：GET、POST、HEAD【、PUT、DELETE】（new）
    4. 响应状态码：200-OK，301-Moved Permanently，400-Bad Request（服务器没理解请求信息），404-Not Found，505-HTTP Version Not Supported
  4. Cookies工作流程：
    1. 服务器接受HTTP连接请求，并生成专属ID，在响应中含Set-cookie：ID
    2. ID保存在用户的Cookie文件和服务器数据库里
    3. 用户再次发送HTTP请求时，在服务器端就能够通过认证并访问服务器数据库里的用户状态
  5. 网络缓存（代理服务器）：一般用户的HTTP请求首先由代理服务器解决，否则代理服务器向根服务器请求
  6. FTP（File Transfer Protocol）：服务器-客户模型，TCP，端口21
    1. 通过认证后，客户通过发送控制命令来浏览FTP服务器中的文件夹，命令如（USER，PASS，LIST列出文件夹内文件，RETR下载，STOR上传）
    2. 服务器接收到命令就开启TCP连接，每传输完一个文件就关闭连接，但是保存当前文件夹、先前的认证等状态
    3. 响应状态码：331-用户名OK需要密码，125-连接已开启，425-无法开启连接，452-书写文件错误
  7. Email：
    1. 邮件服务器：有用户待收收件箱、待发送邮件队列
    2. 用户agent：查看收件箱、编写和发送邮件
    3. SMTP：永久TCP连接，端口25，7-bit ASCII码，CRLF结束标识
      1. 传输过程：握手、传输信息、关闭
    4. Multimedia Mail Extension（MIME）：支持附件
    5. 访问邮件协议：
      1. POP：agent-server认证和下载
      2. IMAP：在服务器上操作讯息
  8. DNS（Domain Name System）：UDP
    1. 服务器类型：Root name servers、Top-Level domain（TLD） servers、Authoritative DNS servers、Local name servers
    2. 两种查询方式：（以LNS为中心）
      • 迭代查询: LNS向其他DNS Server，其他Server只告诉LNS下个查询的地址，相比递归查询减小了公共DNS的计算压力
      • 递归查询: 终端设备向LNS，不在乎中间过程，只需要结果
    3. 会缓存映射关系，但一段时候后会删除
    4. Resource Records（RR）：（name，value，type，ttl）
      1. Type=A：name=主机名，value=IP地址
      2. Type=CNAME：name=域别名（如www.ibm.com for servereast.backup2.ibm.com），value=真实域名
      3. Type=NS：name=域名，value=域中签名服务器的主机名
      4. Type=MX：value=name相关的邮件服务器的名称
  9. 常用端口号：
    • SSH：22
    • Telnet：23

Chapter 4 Network Layer-Data Plane

  1. 平面概念：
    1. 数据平面即每台路由器的功能，决定到达路由器输入链路之一的数据报如何转发到它的输出链路之一
    2. 控制平面即网络范围的逻辑，控制数据报端到端发送路径中路由器之间的路由方式
  2. 路由器架构
    1. 输入端口：含物理层、链路层处理，以及排队缓存
      1. 通用转发
      2. 基于目的地（IP地址）转发：维护一张转发表，一定的地址范围对应一条链路，使用最长前缀匹配
    2. 交换结构：
      1. 内存式：内存带宽限制
      2. 总线式：总线带宽限制
      3. 互联网络式：更好
    3. 输出端口
      1. 排队缓存
      2. 优先级规则：先进先出、优先权排队、循环排队、加权公平排队（有权值的循环排队）
    4. 路由选择处理器
  3. IP协议，在路由器中对应的Interface指路由器的链路口，即1，2，3，4等
    1. 文件头：40字节+选项
    2. CIDR（无类别域间路由）：如200.23.16.0/23
    3. Dynamic Host Configuration Protocol（DHCP）：DHCP discover/offer/request/ack，使用流程即客户与服务器两次对话，客户发现DHCP服务器、DHCP服务器提供IP租约、客户广播其已接受一个租约、DHCP服务器提供租约信息且其他DHCP服务器放弃租约。封装在UDP数据报中
    4. NAT：含有（源IP，端口）-（内部IP，端口）翻译表，对外表现为唯一IP
    5. IPv6：
      • 无选项和检验和，固定40字节
      • 网络不支持IPv6时IPv6数据报会被包装在IPv4中

Chapter 5 Network Layer-Control Plane

  1. 路由协议：
    1. link-state：Dijsktra算法，复杂度最优为$O(n\log n)$。每个节点通过广播得到完整的网络视图，自己计算整张表。
    2. Distance vector：Bellman-Ford算法，对于每个节点维护其与其他所有节点之间的距离，节点间通过互相通知以不断更新。当某条链路突然变大时，因为路由会广播不正确的路径，所以与它相关的路由变化很慢。解决方法是毒性逆转技术，离故障通路最近的路由会广播故障通路距离为无穷大，其他路由会得知；水平分割技术，不向接到新情报的方向发送情报
  2. AS（自治系统）内路由或Interior Gateway Protocol(IGP)：
    1. Routing Information Protocol(RIP)：基于DV算法，跳数大于15视为不可达，每30秒广播一次路由表
    2. Open Shortest Path First(OSPF)：link-state，代价用带宽计算，允许多条相同代价路径，信息加密。使单个AS内部可分层，即分为与外界沟通的主干区域和非主干区域。
    3. Interior Gateway Routing Protocol(IGRP)：升级版RIP，距离用带宽等复合度量，跳数大于255视为不可达，每90秒广播一次路由表，思科私有协议，已淘汰。
    4. Enhanced Interior Gateway Routing Protocol(EIGRP)：扩散更新算法，距离用带宽等复合度量，为每个目标路由维护最短路径和备用路径，优势是资源消耗小、路径切换快，劣势是仅思科设备支持
  3. AS间路由Border Gateway Protocol（BGP）：网关即AS间存在链路的路由器
    1. AS内链路称为iBGP连接，AS间为eBGP连接
    2. 网关会广播可达路径（如AS2、AS3、X）
    3. 在AS内存在多个网关都可达目标时有多种选择策略：
      1. 网关偏好
      2. 最短AS路径
      3. 最近的网关：热土豆路由
    4. AS可通过不向其他AS广播自己向其他AS的可达路径来避免其他AS经过自己
  4. 因特网控制信息协议ICMP：通知网络信息如发生错误、目标不可达等。ping使用80 echo request和00 echo reply
  5. 简单网络管理协议SNMP：应用层协议
    1. 请求响应模式：Manager服务器轮询设备上的Agent获取状态
    2. 陷阱报文：设备异常时，Agent通知管理信息库（MIB）某个对象值改变

第三章 运输层

  1. 网络层提供主机间的逻辑通信，运输层提供不同主机上的进程间的逻辑通信。
  2. 因特网的运输层提供了UDP (User Data-gram Protocol) 和 TCP (Transport Control Protocol)，它们基于因特网网络层的IP协议，该协议是尽力而为交付服务 (best-effort delivery service)，即不可靠服务。

多路分解与多路复用

  1. 套接字 (socket) 在运输层的报文段中，多路分解 (demultiplexing) 即将运输层报文段中的数据交付到正确的套接字，多路复用 (multiplexing) 从套接字中收集数据块后将数据块加上header、生成报文段并传递给网络层。
  2. 运输层Header中含有源端口号和目的端口号，它们是用来唯一地标识用于处理该报文段的套接字的，是16比特数。周知端口号用于表示通用的周知应用层协议，大小在 $0 \;to \;1023$。通常，应用的客户端让运输层自动地分配端口号，而服务器端分配一个特定的端口号。
  3. UDP是无连接的多路复用与多路分解。UDP套接字是一个二元组，包含目的IP地址和目的端口号，所以UDP报文段只要这两个信息相同就会被定向到同一进程。
  4. TCP是面向连接的多路复用与多路分解。TCP套接字是一个四元组，除了UDP的目的IP和端口外，还含有源IP和端口，所以就算目的IP和端口相同，只要源IP或端口不同就会被定位到不同的套接字，进而为来自不同源的报文段定向到不同的进程。

UDP

用于DNS、SNMP、NFS、流媒体、网络电话等应用中。

  1. 优势
    • 无拥塞控制，所以无发送延迟
    • 无须握手建立连接
    • 无需维护连接状态
    • 仅8字节，开销小
  2. 报文段构成：四个字段，每个2字节
    • 源端口号、目的端口号
    • header加data的字节数、检验和
  3. 检验和 (checksum): 将所有的16比特字加在一起，首位进位溢出被回卷到尾位，再进行反码运算。接收方只要将所有的16比特字加和，结果为16个1时说明无差错。意义在于如果端到端的应用层协议要进行差错检测，UDP也必须提供端到端的差错检测。

可靠数据传输

  1. 可以将发送方与接收方抽象成有限状态机 (Finite-State Machine, FSM)。
  2. 自动重传请求 (Automatic Repeat reQuest, ARQ) 协议基于重传机制实现可靠数据传输，包括了三种协议功能：
    • 差错检测
    • 接收方反馈 (ACK or NAK)
    • 重传
    • 此外还需要停等 (stop-and-wait) 协议
  3. 对于ACK和NAK可能出错或丢失，接收方可能需要发送冗余ACK、发送方则是冗余packet，而为了让接收方明白是哪个数据段丢失，发送方的ACK需要含有缺失数据段的序号。
  4. 对于包可能整个丢失，发送方需要countdown timer来进行超时重传。
  5. 信道利用率 (utilization): 发送比特的时间 / 总发送时间。
  6. 流水线 (pipeline): 连续发送N个包，引入了两种差错恢复机制
    • 回退N步 (Go-Back-N, GBN, 又称滑动窗口协议):
      • 发送方: 累积确认 (Cumulative Acknowledgment) 表明接收方已正确接收到序号为n及以前的所有包。超时出现时，重传所有已发送未确认的包。
      • 接收方: 按序向上层交付包。丢弃所有失序包并重新发送按序ACK，不缓存失序包是因为如果分组n丢失而n + 1被缓存，发送方还是会发送包括n和n + 1在内的所有已发送的包。
    • 选择重传 (Selective Repeat, SR):
      • 接收方: 不管是否按序，确认一个正确接收的包，失序包将被缓存直到按序包都被收到为止。
      • 发送方: 每个窗口内的包都有自己的定时器，超时只重传一个包。
      • 此外，窗口长度必须小于或等于最大序号的一半，以免接收方混淆重传的包和等待的包。原因是接收方全部接收到包，但是ACK全部丢失，导致发送方窗口没移动但接收方窗口已经到下一轮序号，两方错位进行。

TCP

  1. 三次握手指建立TCP连接时：

    1. 客户端发送SYN报文段，不包含应用层数据，但SYN bit为1，初始序号被随机选择。
    2. 服务器端发送SYNACK报文段，不包含应用层数据，SYN bit为1，ACK字段为客户端初始序号+1，服务器也选择了自己的初始序号。
    3. 客户端发送第三个报文段，可以包含数据，SYN bit置零，序号为服务器初始序号+1。

    结束连接时：

    1. 客户端发送FIN bit为1的终止报文段，服务器收到后回送ACK。
    2. 服务器发送终止报文段，客户端收到后回送ACK。

    整个TCP连接过程中客户端存在以下6个状态：

    服务器端。

    当客户端发送了一个目标主机目的端口不接受连接的SYN报文时，目标主机会回送一个RST bit为1的报文以提示没有该socket。

  2. 最大报文段长度 (MSS) 通常与发送端的最大链路层帧长度 (又称最大传输单元，MTU) 相同，它是一个TCP报文段中应用层数据的最大长度。

  3. TCP的Header在不含选项时为20字节，除源、目的端口号、检验和以外还含有以下结构：
    • 4字节的序号字段。初始序号可以自由选择，可以帮助规避相同端口号的新进程误接收先前已终止的进程的包。序号指的是字节序号
    • 4字节的ACK字段。由于报文段中总是有该字段，在双向数据传输中，ACK可以看成被捎带 (piggybacked) 在数据报文段中。
    • 2字节的接收窗口字段
    • 4 bit的首部长度，由于选项，TCP首部长度可变
    • 可选的选项
    • 6 bit的标志字段：ACK bit——ACK字段的有效性，RST、SYN、FIN bit——连接建立与拆除，CWR、ECE bit——前者表示拥塞窗口已缩减、后者为明确拥塞通告回显、它们由路由器在网络层的ECN bit的明确拥塞通告引起，PSH bit——数据交付上层，URG bit——存在紧急数据（其最后一个字节位置由4字节的紧急数据指针字段给出）
    • 还有时间戳可唯一标识该包
  4. TCP估计往返时间 (RTT) 时仅为传输一次 (非重传) 的报文段测量SampleRTT，且一般只在特定时间做一次测量。并且每次的结果会以指数加权移动平均得到EstimatedRTT:还会测量RTT偏差DevRTT：，最终超时时间会被设为。推荐值为1秒，超时后该值还会被加倍。
  5. TCP可靠传输使用单一的超时定时器（减小开销）、累积ACK（减少重传，三个冗余ACK才快速重传）、超时时间加倍、快速重传（冗余ACK）、由于接收方缓存机制因此一次至多重传一个包（GBN与SR的结合，接收方总发送等待的下一个连续包ACK）。
  6. 流量控制是为了防止接收方缓存溢出，在TCP报文段中维护一个接收窗口字段 (rwnd)，$rwnd=RevBuffer - [LastByteRevd - LastByteRead]$，我们需要$rwnd \geq 0$。此外，当一方接收缓存已满即$rwnd = 0$且没有任何数据需要发送时，如果其缓存已清空，它也不会发新报文段。为解决该问题，我们让发送方继续发送一个报文段且接收方再发送的确认报文里将包含一个非0的rwnd。

拥塞控制

  1. 拥塞的后果：丢包和长时延。
  2. 控制方法分为两种：
    • 端到端拥塞控制：主机的运输层自己想办法。
    • 网络辅助的拥塞控制：路由器向发送方直接反馈阻塞信息（choke packet）或最大发送速率（如ABR），更常用间接地标记包中的某个字段来指示拥塞。

TCP拥塞控制

  1. TCP拥塞控制算法分为慢启动、拥塞避免和快速恢复三个技巧，非常易于理解
    • 慢启动：发送窗口cwnd从1MSS开始指数增大
    • 拥塞避免：cwnd>=ssthreshhou开始线性增长
    • 快速恢复：阈值等于上一次的窗口峰值砍半，窗口减半+3
  2. TCP RENO有快恢复（收到3个冗余ACK就减半并+3，阈值减到当前峰值的一半），TCP Tahoe直接减到1并慢启动。超时时都会减到1并慢启动。
  3. TCP吞吐量在确定最大值的理想情况下，平均为$ 0.75 \times WindowSize / RTT $。若与带宽相联系，我们引入丢包率$L$，则平均为$1.22 \times MSS / RTT \sqrt{L}$。

第六章 链路层和LAN 8分选择题+8分大题

  • 节点(node)：运行链路层协议的设备；
  • 链路(link)：连接相邻节点的通信信道，分为点对点链路(point-to-point link)和广播链路(broadcast link)；
  • 链路层服务：成帧(framing)、链路接入(如MAC)、可靠交付(本地纠错)、差错检测和纠正；
  • 网络适配器(Network Adapter)：实现链路层的主体。

差错检测和纠正技术

  • 差错检测和纠正比特(EDC)、数据(D)。无法保证一定检测出所有的差错！
  • 前向纠错(Forward Eorror Correction, FEC)：接收方检测和纠错。

  1. 奇偶校验：加单个奇偶校验位(parity bit)，偶数个差错发生时无法检出。二位奇偶校验(two-dimensional parity)：可以通过行检测和列检测，检测和纠正单个差错，可以检测但无法纠正同分组中的两个比特差错。对一列32bit数可以分成4行4列进行检验。

  2. 检验和：将每k(如16)个bit数据当作整数加和，和的反码即检验和。接收方只要看所有整数包括检验和的和是否为全1即可。

  3. 循环冗余检测(Cyclic Redundancy Check, CRC or Polymial Code)：要素包括长度为d+r的CRC比特、长度为r+1的生成多项式G、长度为r的CRC比特R。其中$R=D \cdot 2^r XOR \; G$，$CRC=D \cdot 2^r XOR \; R$，即把R替换补位零来做异或，检测方式为CRC是否为G的倍数。CRC能检测所有小于r+1比特的差错。

多路访问链路和协议

  • 多路访问问题(multiple access problem)：如何协调多个发送和接收节点对一个共享广播信道的访问；
  • 多路访问协议(multiple access protocol)：规范节点的行为。要求有：对于单个广播信道，单个节点传输时能占满传输速率、多个节点能平均得到速率、节点间相互非依赖、开销小；
  • 碰撞(collide)：节点同时接到多个帧；
  • 时隙多路访问协议的效率：大量活跃节点且大量帧要发送时，长期运行中成功时隙的占比。
  1. 信道划分协议(Channel Partitioning Protocol)
    1. 时分多路复用(TDM)：将时间分为时间帧并进一步分为N个时隙(slot)分配给N个节点，通常时隙长度能传输单个分组。优点避免碰撞、公平，缺点限速和等待、未使用时直接浪费。
    2. 频分多路复用(FDM)：均分带宽，优缺点相似。
    3. 码分多址(CDMA)：为每个节点分配一种不同的编码，使不同节点能同时传输。
  2. 随机接入协议(Random Access Protocol)：节点总是以信道最大速率发送，碰撞时节点等待随机时延后重发，且节点的选择之间相互独立。
    1. Slotted ALOHA：假设所有帧等长、时间被分成等长时隙、节点只在时隙开始时发送帧，该方法在检测到碰撞后以概率$p$在后续的每个时隙中重传该帧直到成功。其效率为$Np(1-p)^{N-1}$，最大效率为$1/e=0.37$；
    2. ALOHA：没有时隙，直接完整传输帧，检测到碰撞后立即以概率$p$重传，否则等待一个帧传输时间。效率为$p(1-p)^{2(N-1)}$，最大效率为$1/(2e)$。
    3. 载波侦听多路访问(CSMA)：
      • 载波侦听(carrier sensing)：等待使用同一信道的其他正在传输的节点；
      • 碰撞检测(collision detection)：传输的同时侦听此信道，如果有另一个节点正在传输干扰帧，立即停止传输。接着等待随机时间后进入载波侦听状态。发生原因：端到端传输路径中可能经过多条信道，有时前方的信道正闲，但必须给来自后方的数据让路。有该机制的协议称为CSMA/CD（用在以太网中），而发现碰撞后的等待时间使用下面的算法：
      • 二进制指数后退(binary expotional backoff)：在同一帧经历连续n次碰撞后，节点均匀地从${0, 1, …, 2^n-1}$中选择一个值乘以512作为等待时间，集合长度随碰撞次数呈指数增长。
      • CSMA/CD效率$\approx \frac{1}{1+5d_{prop}/d_{trans}}$，$d_{prop}$为信号能量在两个适配器间传播所需地最大时间，$d_{trans}$为传输一个最大长度的以太网帧的时间。
      • CSMA/CA（用在IEEE 802.11中）：有ACK，接收方接收完后等待SIFS时间后发送ACK
      • RTS-CTS：发送方先用CSMA发送request-to-send（RTS）包到BS，BS广播clear-to-send（CTS）作为回应，其他节点推迟传输，发送方开始传输
  3. 轮流协议(Taking-turns Protocol)：为了解决同时传输时的平均要求。
    1. 轮询协议(polling protocol)：主节点依次循环轮询每个节点，告诉它们能够最多传输的帧数量。优点效率高，缺点引入轮询时延(即轮到同一节点的时间)对主节点的依赖性。
    2. 令牌传递协议(token-passing protocol)：将特殊帧(令牌)按固定次序相互传递，持有令牌的节点可以传输最大数量的帧数。优点效率高、分散性，缺点中间环节故障。
  4. LAN：
    1. MAC地址：48位（6字节），一般用16进制表示，每个网络适配器都有一个MAC地址，并且是独一无二的。广播地址（FF-FF-FF-FF-FF-FF）
    2. Address resolution protocol（ARP）：依赖以太网的广播功能
      1. ARP表：记录(IP地址；MAC地址；TTL（存在时间）)三元组
      2. 只为同一LAN内的主机工作，发送方广播ARP查询分组（含IP），匹配方发送响应ARP分组。
      3. 向子网外发送数据报：向连接子网的路由器发送IP数据报（链路层目的地址为路由器MAC地址），路由器查询ARP表并将链路层目的地址改写为下一跳路由器或者最终目的MAC地址。
      4. ARP欺骗：通过发送伪造的ARP响应可以声称假身份，从而实现中间人拦截
    3. Neighbor Discovery Protocol (NDP)：IPv6引入，ARP的升级版，纯网络层协议
      1. 解析地址：获取未知MAC地址时会通过已知IPv6地址生成组播请求而非广播，降低网络总体负担
      2. Duplicate Address Detection (DAD): 发送自己IP地址的请求报文确保没有回复
      3. 无状态地址自动配置 (SLAAC)：上线后通过路由器获知网络前缀，结合自己的MAC地址生成IPv6地址，再DAD。
      4. First-Hop Security：
        • RA Guard (路由器通告保护)：直接在交换机上配置，只允许特定的上联端口转发路由器通告
        • ND Inspection (ND 检测)：交换机通过监听合法的地址分配过程，在内存中维护一张合法“IPv6-MAC-端口”绑定表
    4. 以太网（Ethernet）：无连接，不可靠，使用无时隙、二进制退避的CSMA/CD
    5. 交换机：
      1. 链路层机器，对主机相当于透明可忽略
      2. 缓存/发送以太网帧，CSMA/CD接入
      3. 根据帧来向自学习三元表，接收到发向未知地址的帧时会向除发送方接口外的所有接口广播该帧
猫才毛

猫才毛

Live for what I love ~

24
8
5
TITLES
  1. Chapter 1 Introduction
  2. Chapter 2 Application Layer
  3. Chapter 4 Network Layer-Data Plane
  4. Chapter 5 Network Layer-Control Plane
  5. 第三章 运输层
    1. 多路分解与多路复用
    2. UDP
    3. 可靠数据传输
    4. TCP
    5. 拥塞控制
    6. TCP拥塞控制
  6. 第六章 链路层和LAN 8分选择题+8分大题
    1. 差错检测和纠正技术
    2. 多路访问链路和协议
NOTICE

欢迎访问阿毛的小书桌，我偶尔会更新自己的学习内容和项目经验，也有可能闲话生活！

CATEGORIES
TAGS
实用工具 数字图像处理 压缩 机器学习 赛博八股 项目经验